Melhor algoritmo de bandido?

O algoritmo de bandido mais conhecido é o limite superior de confiança (UCB), que popularizou essa classe de algoritmos. Desde então, presumo que agora existem algoritmos melhores. Qual é o melhor algoritmo atual (em termos de desempenho empírico ou limites teóricos)? Esse algoritmo é ideal em algum sentido?

Um artigo do NIPS 2011 ("Uma avaliação empírica da Thompson Sampling") mostra, em experimentos, que a Thompson Sampling supera a UCB. O UCB baseia-se na escolha da alavanca que promete a maior recompensa sob premissas otimistas (ou seja, a variação de sua estimativa da recompensa esperada é alta, portanto, você puxa alavancas que não conhece muito bem). Em vez disso, o Thompson Sampling é totalmente bayesiano: gera uma configuração de bandido (ou seja, um vetor de recompensas esperadas) a partir de uma distribuição posterior e depois age como se essa fosse a configuração verdadeira (ou seja, puxa a alavanca com a maior recompensa esperada).

A regra de controle bayesiana (" Um princípio de entropia relativa mínima para aprender e agir ", JAIR), uma generalização da amostragem de Thompson, deriva a amostragem de Thompson dos princípios e da causalidade da teoria da informação. Em particular, é mostrado que a Regra Bayesiana de Controle é a estratégia ideal quando você deseja minimizar o KL entre sua estratégia e a estratégia ótima (desconhecida) e se leva em conta restrições causais. A razão pela qual isso é importante é porque isso pode ser visto como uma extensão da inferência bayesiana para ações: a inferência bayesiana pode ser mostrada como a melhor estratégia de previsão quando seu critério de desempenho é o KL entre seu estimador e a distribuição verdadeira (desconhecida).

UCB é realmente quase ideal no caso estocástico (até um fator T logarítmico para um jogo da rodada T) e até uma lacuna na desigualdade de Pinsker em um sentido mais dependente de problemas. Artigo recente de Audibert e Bubeck remove essa dependência de log no pior dos casos, mas tem um limite pior no caso favorável quando braços diferentes têm recompensas bem separadas.

Em geral, o UCB é um candidato de uma família maior de algoritmos. Em qualquer ponto do jogo, você pode observar todos os braços que não são "desqualificados", ou seja, cujo limite superior de confiança não é menor que o limite inferior de um braço. A escolha com base em qualquer distribuição de armas qualificadas constitui uma estratégia válida e gera um arrependimento semelhante às constantes.

Empiricamente, não acho que tenha havido uma avaliação significativa de muitas estratégias diferentes, mas acho que a UCB geralmente é muito boa.

A maioria das pesquisas mais recentes se concentrou em estender os problemas dos bandidos além do cenário simples com armas K, com recompensas estocásticas, para espaços de ação muito grandes (ou infinitos), com ou sem informações laterais, e sob feedback estocástico ou adversário. Também houve trabalhos em cenários em que os critérios de desempenho são diferentes (como a identificação do melhor braço apenas).

O estado da arte atual pode ser resumido assim:

• $R_T = O(\frac{K \log T}{\Delta})$
• $\tilde{R}_T = O(\sqrt{T K \log K})$
• contextual: é complicado

$T$$K$$\Delta$