El muestreo de Thompson , [1] [2] llamado así por William R. Thompson, es una heurística para elegir acciones que aborda el dilema exploración-explotación en el problema de los bandidos con múltiples brazos . Consiste en elegir la acción que maximiza la recompensa esperada con respecto a una creencia extraída al azar.
Descripción
Considere un conjunto de contextos , un conjunto de acciones y recompensas en . En cada ronda, el jugador obtiene un contexto, juega una acción y recibe una recompensa siguiendo una distribución que depende del contexto y la acción emitida. El objetivo del jugador es realizar acciones tales como maximizar las recompensas acumulativas.
Los elementos del muestreo de Thompson son los siguientes:
- una función de verosimilitud ;
- un conjunto de parámetros de la distribución de ;
- una distribución previa en estos parámetros;
- trillizos de observaciones pasadas ;
- una distribución posterior , dónde es la función de verosimilitud.
El muestreo de Thompson consiste en jugar la acción de acuerdo con la probabilidad de que maximice la recompensa esperada, es decir, la acción se elige con probabilidad
dónde es la función del indicador .
En la práctica, la regla se implementa muestreando, en cada ronda, los parámetros desde la parte posterior , y eligiendo la acción que maximiza , es decir, la recompensa esperada dados los parámetros muestreados, la acción y el contexto actual. Conceptualmente, esto significa que el jugador instancia sus creencias al azar en cada ronda de acuerdo con la distribución posterior, y luego actúa de manera óptima de acuerdo con ellas. En la mayoría de las aplicaciones prácticas, es computacionalmente oneroso mantener y muestrear a partir de una distribución posterior sobre modelos. Como tal, el muestreo de Thompson se usa a menudo junto con técnicas de muestreo aproximado. [2]
Historia
El muestreo de Thompson fue descrito originalmente por Thompson en 1933. [1] Posteriormente fue redescubierto en numerosas ocasiones de forma independiente en el contexto de problemas de bandidos con múltiples brazos. [3] [4] [5] [6] [7] [8] Una primera prueba de convergencia para el caso de los bandidos se mostró en 1997. [3] La primera aplicación a los procesos de decisión de Markov fue en 2000. [5] Un enfoque relacionado (ver la regla de control bayesiano ) se publicó en 2010. [4] En 2010 también se demostró que el muestreo de Thompson se autocorrige instantáneamente . [8] Los resultados de convergencia asintótica para bandidos contextuales se publicaron en 2011. [6] El muestreo de Thompson se ha utilizado ampliamente en muchos problemas de aprendizaje en línea, incluidas las pruebas A / B en el diseño de sitios web y la publicidad en línea, [9] y el aprendizaje acelerado en la toma de decisiones descentralizada. . [10] Se ha propuesto un algoritmo de muestreo doble Thompson (D-TS) [11] para los bandidos en duelo, una variante del MAB tradicional, donde la retroalimentación viene en forma de comparación por pares.
Relación con otros enfoques
Coincidencia de probabilidad
El emparejamiento de probabilidades es una estrategia de decisión en la que las predicciones de pertenencia a una clase son proporcionales a las tasas base de la clase. Por lo tanto, si en el conjunto de entrenamiento se observan ejemplos positivos el 60% del tiempo, y los ejemplos negativos se observan el 40% del tiempo, el observador que utilice una estrategia de coincidencia de probabilidad predecirá (para ejemplos sin etiquetar) una etiqueta de clase de "positivo" en el 60% de las instancias y una etiqueta de clase de "negativo" en el 40% de las instancias.
Regla de control bayesiano
Se ha demostrado que una generalización del muestreo de Thompson a entornos dinámicos arbitrarios y estructuras causales, conocida como regla de control bayesiano , es la solución óptima al problema de codificación adaptativa con acciones y observaciones. [4] En esta formulación, un agente se conceptualiza como una mezcla sobre un conjunto de comportamientos. A medida que el agente interactúa con su entorno, aprende las propiedades causales y adopta el comportamiento que minimiza la entropía relativa al comportamiento con la mejor predicción del comportamiento del entorno. Si estos comportamientos se han elegido de acuerdo con el principio de máxima utilidad esperada, entonces el comportamiento asintótico de la regla de control bayesiana coincide con el comportamiento asintótico del agente perfectamente racional.
La configuración es la siguiente. Dejar Ser las acciones emitidas por un agente hasta el momento. , y deja ser las observaciones recopiladas por el agente hasta el momento . Entonces, el agente emite la acción.con probabilidad: [4]
donde la notación "sombrero" denota el hecho de que es una intervención causal (ver Causalidad ) y no una observación ordinaria. Si el agente tiene creencias sobre sus comportamientos, entonces la regla de control bayesiano se convierte en
- ,
dónde es la distribución posterior sobre el parámetro acciones dadas y observaciones .
En la práctica, el control bayesiano equivale a muestrear, en cada paso de tiempo, un parámetro de la distribución posterior , donde la distribución posterior se calcula utilizando la regla de Bayes considerando solo las probabilidades (causales) de las observaciones e ignorando las probabilidades (causales) de las acciones , y luego muestreando la acción de la distribución de la acción .
Algoritmos de límite de confianza superior (UCB)
El muestreo de Thompson y los algoritmos de límite de confianza superior comparten una propiedad fundamental que subyace a muchas de sus garantías teóricas. A grandes rasgos, ambos algoritmos asignan un esfuerzo exploratorio a acciones que pueden ser óptimas y, en este sentido, "optimistas". Aprovechando esta propiedad, se pueden traducir los límites de arrepentimiento establecidos para los algoritmos UCB a límites de arrepentimiento bayesianos para el muestreo de Thompson [12] o unificar el análisis de arrepentimiento a través de estos algoritmos y muchas clases de problemas. [13]
Referencias
- ^ a b Thompson, William R. "Sobre la probabilidad de que una probabilidad desconocida supere a otra en vista de la evidencia de dos muestras" . Biometrika , 25 (3-4): 285-294, 1933.
- ^ a b Daniel J. Russo, Benjamin Van Roy, Abbas Kazerouni, Ian Osband y Zheng Wen (2018), "Un tutorial sobre muestreo de Thompson", Fundamentos y tendencias en el aprendizaje automático: vol. 11: núm. 1, págs. 1-96. https://web.stanford.edu/~bvr/pubs/TS_Tutorial.pdf
- ^ a b J. Wyatt. Exploración e inferencia en el aprendizaje a partir del refuerzo . Doctor. tesis, Departamento de Inteligencia Artificial, Universidad de Edimburgo. Marzo de 1997.
- ^ a b c d PA Ortega y DA Braun. "Un principio de entropía relativa mínima para aprender y actuar", Journal of Artificial Intelligence Research , 38, páginas 475–511, 2010.
- ^ a b MJA Strens. "A Bayesian Framework for Reinforcement Learning", Actas de la decimoséptima conferencia internacional sobre aprendizaje automático , Universidad de Stanford, California, 29 de junio a 2 de julio de 2000, http://citeseerx.ist.psu.edu/viewdoc/summary?doi= 10.1.1.140.1701
- ↑ a b BC May, BC, N. Korda, A. Lee y DS Leslie. "Muestreo bayesiano optimista en problemas contextuales de bandidos". Informe técnico, Grupo de Estadística, Departamento de Matemáticas, Universidad de Bristol, 2011.
- ^ Chapelle, Olivier y Lihong Li. "Una evaluación empírica del muestreo de Thompson". Avances en sistemas de procesamiento de información neuronal. 2011. http://papers.nips.cc/paper/4321-an-empirical-evaluation-of-thompson-sampling
- ^ a b O.-C. Granmo. "Resolver problemas de bandidos de Bernoulli de dos brazos utilizando un autómata de aprendizaje bayesiano", Revista Internacional de Computación Inteligente y Cibernética , 3 (2), 2010, 207-234.
- ^ Ian Clarke . "Proportionate A / B testing", 22 de septiembre de 2011, http://blog.locut.us/2011/09/22/proportionate-ab-testing/
- ^ Granmo, OC; Glimsdal, S. (2012). "Aprendizaje bayesiano acelerado para la toma de decisiones descentralizada basada en bandidos de dos brazos con aplicaciones para Goore Game". Inteligencia aplicada . 38 (4): 479–488. doi : 10.1007 / s10489-012-0346-z . hdl : 11250/137969 .
- ^ Wu, Huasen; Liu, Xin; Srikant, R (2016), Muestreo doble de Thompson para bandidos en duelo , arXiv : 1604.07101 , Bibcode : 2016arXiv160407101W
- ^ Daniel J. Russo y Benjamin Van Roy (2014), "Aprender a optimizar mediante muestreo posterior", Matemáticas de la investigación de operaciones, vol. 39, núm. 4, págs. 1221-1243, 2014. https://pubsonline.informs.org/doi/abs/10.1287/moor.2014.0650
- ^ Daniel J. Russo y Benjamin Van Roy (2013), "Dimensión Eluder y la complejidad de la muestra de exploración optimista", Avances en sistemas de procesamiento de información neuronal 26, págs. 2256-2264. https://proceedings.neurips.cc/paper/2013/file/41bfd20a38bb1b0bec75acf0845530a7-Paper.pdf