¿El mejor algoritmo de bandido?

El algoritmo de bandido más conocido es el límite superior de confianza (UCB) que popularizó esta clase de algoritmos. Desde entonces supongo que ahora hay mejores algoritmos. ¿Cuál es el mejor algoritmo actual (en términos de rendimiento empírico o límites teóricos)? ¿Es este algoritmo óptimo en algún sentido?

Un artículo de NIPS 2011 ("Una evaluación empírica de Thompson Sampling") muestra, en experimentos, que Thompson Sampling supera a UCB. UCB se basa en elegir la palanca que promete la recompensa más alta bajo supuestos optimistas (es decir, la variación de su estimación de la recompensa esperada es alta, por lo tanto, tira de palancas que no conoce bien). En cambio, Thompson Sampling es completamente bayesiano: genera una configuración de bandido (es decir, un vector de recompensas esperadas) a partir de una distribución posterior, y luego actúa como si esta fuera la configuración verdadera (es decir, tira de la palanca con la recompensa más alta esperada).

La regla de control bayesiano (" Un principio de entropía relativa mínima para aprender y actuar ", JAIR), una generalización de Thompson Sampling, deriva el muestreo de Thompson de los principios teóricos de la información y la causalidad. En particular, se muestra que la Regla de control bayesiano es la estrategia óptima cuando desea minimizar el KL entre su estrategia y la estrategia óptima (desconocida) y si tiene en cuenta las restricciones causales. La razón por la que esto es importante es porque puede verse como una extensión de la inferencia bayesiana a las acciones: se puede demostrar que la inferencia bayesiana es la estrategia de predicción óptima cuando su criterio de rendimiento es el KL entre su estimador y la distribución verdadera (desconocida).

UCB es de hecho casi óptimo en el caso estocástico (hasta un factor T log para un juego de ronda T), y hasta una brecha en la desigualdad de Pinsker en un sentido más dependiente del problema. El artículo reciente de Audibert y Bubeck elimina esta dependencia de registro en el peor de los casos, pero tiene un límite peor en el caso favorable cuando diferentes brazos tienen recompensas bien separadas.

En general, UCB es un candidato de una familia más grande de algoritmos. En cualquier momento del juego, puedes ver todos los brazos que no están "descalificados", es decir, cuyo límite de confianza superior no es menor que el límite de confianza inferior de algún brazo. La selección basada en cualquier distribución de tales armas calificadas constituye una estrategia válida y obtiene un arrepentimiento similar hasta las constantes.

Empíricamente, no creo que haya habido una evaluación significativa de muchas estrategias diferentes, pero creo que UCB a menudo es bastante bueno.

La mayor parte de la investigación más reciente se ha centrado en extender los problemas de los bandidos más allá del simple entorno armado K con recompensas estocásticas, a espacios de acción muy grandes (o infinitos), con o sin información secundaria, y bajo retroalimentación estocástica o adversaria. También se ha trabajado en escenarios donde los criterios de rendimiento son diferentes (como la identificación del mejor brazo únicamente).

El estado actual de la técnica podría resumirse así:

• estocástico: UCB y variantes (arrepentimiento en )$R_T = O(\frac{K \log T}{\Delta})$
• adversario: EXP3 y variantes (arrepentimiento en )$\tilde{R}_T = O(\sqrt{T K \log K})$
• contextual: es complicado

con es el número de rondas, el número de brazos, la verdadera diferencia entre el mejor y el segundo mejor brazo (brecha).$T$$K$$\Delta$