Upper Confidence Bound – UCB

exploração baseada em incerteza

UCB (Upper Confidence Bound) escolhe ações considerando recompensa média mais incerteza. Diferente de ε-greedy, explora ações com poucas amostras ou alta variância. Primeiramente, calcula UCB(a) = Q(a) + c * sqrt(log(N)/n_a). Além disso, c controla o nível de exploração. Por exemplo, ações não exploradas têm n_a=0, incerteza infinita.

balanço entre média e incerteza

UCB equilibra automaticamente exploração baseada em quão incerta é a estimativa. Primeiramente, termo sqrt(log(N)/n_a) decai com mais amostras. Além disso, ações com alta variância ou poucas amostras são exploradas mais. Por exemplo, explora até ter confiança na estimativa. É mais eficiente que ε-greedy.

vantagens teóricas e práticas

UCB tem garantias teóricas de arrependimento logarítmico em bandidos. Primeiramente, reduz exploração desnecessária de ações claramente ruins. Além disso, converge mais rápido para política ótima. Por exemplo, em testes A/B, identifica melhor variante rapidamente. É amplamente utilizado em otimização online.

aplicações e limitações

UCB é ideal para bandidos e problemas com poucas ações. Primeiramente, usado em sistemas de recomendação e experimentos online. Além disso, funciona bem quando ações não têm muitas interações. Por exemplo, escolha de anúncios e otimização de conversão. Para iniciantes, UCB mostra exploração inteligente baseada em incerteza. É uma estratégia poderosa e elegante.