El algoritmo bandido más conocido es el de límite superior de confianza (UCB), que popularizó esta clase de algoritmos. Desde entonces, supongo que ahora hay algoritmos mejores. ¿Cuál es el mejor algoritmo actual (en términos de rendimiento empírico o de límites teóricos)? ¿Es este algoritmo óptimo en algún sentido?
Respuestas
¿Demasiados anuncios?
mr_
Puntos
26
Un artículo de NIPS 2011 ("An empirical evaluation of Thompson Sampling") muestra, en los experimentos, que Thompson Sampling supera a UCB. El UCB se basa en elegir la palanca que promete la mayor recompensa bajo supuestos optimistas (es decir, la varianza de tu estimación de la recompensa esperada es alta, por lo que tiras de palancas que no conoces tan bien). En cambio, el muestreo de Thompson es totalmente 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 ésta fuera la verdadera configuración (es decir, tira de la palanca con la mayor recompensa esperada).
La regla de control bayesiano (" Un principio de entropía relativa mínima para aprender y actuar ", JAIR), una generalización del Muestreo de Thompson, deriva el Muestreo de Thompson de los principios de la teoría de la información y la causalidad. En particular, se demuestra que la Regla de Control Bayesiana es la estrategia óptima cuando se quiere minimizar el KL entre su estrategia y la estrategia óptima (desconocida) y si se tienen 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).
Usuario no registrado
Puntos
0
El UCB es, de hecho, casi óptimo en el caso estocástico (hasta un factor log T para un juego de T rondas), y hasta una brecha en la desigualdad de Pinsker en un sentido más dependiente del problema. Un artículo reciente de Audibert y Bubeck elimina esta dependencia logarítmica en el peor de los casos, pero tiene un límite peor en el caso favorable cuando los diferentes brazos tienen recompensas bien separadas.
En general, el UCB es un candidato de una familia más amplia de algoritmos. En cualquier momento del juego, se pueden considerar todos los brazos que no están "descalificados", es decir, cuyo límite superior de confianza no es menor que el límite inferior de confianza de algún brazo. Escoger en base a cualquier distribución de tales brazos calificados 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 la UCB suele ser bastante buena.
La mayor parte de la investigación más reciente se ha centrado en ampliar los problemas de bandidos más allá del simple escenario de K brazos con recompensas estocásticas, a espacios de acción muy grandes (o infinitos), con o sin información lateral, y bajo retroalimentación estocástica o adversaria. También se ha trabajado en escenarios en los que los criterios de rendimiento son diferentes (como la identificación del mejor brazo únicamente).
Yuval Filmus
Puntos
123
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 $T$ es el número de rondas, $K$ el número de brazos, $\Delta$ la verdadera diferencia entre el mejor y el segundo mejor brazo (brecha).
