Muestreo de Thompson

Thompson toma de muestras, el nombre de William R. Thompson, es un algoritmo heurístico para la elección de acciones que resuelven el dilema de exploración de la explotación en el bandido armado K- problema . Consiste en elegir la acción que maximiza la recompensa esperada frente a una creencia extraída al azar.

La descripcion

Considere un conjunto de contextos , un conjunto de acciones y recompensas en . En cada turno, el jugador recibe un contexto , realiza una acción y recibe una recompensa siguiendo una distribución que depende del contexto y la acción realizada. El objetivo del jugador es realizar las acciones que maximicen las ganancias acumuladas. ${\ mathcal {X}}$ ${\ mathcal {A}}$ $\ mathbb {R}$ ${\ Displaystyle x \ in {\ mathcal {X}}}$ $a \ in \ mathcal {A}$ ${\ Displaystyle r \ in \ mathbb {R}}$

Los elementos del muestreo de Thompson son los siguientes:

una función de verosimilitud ; ${\ Displaystyle P (r | \ theta, a, x)}$
un conjunto de parámetros de la distribución de ; $\ Theta$ $\ theta$ $r$
distribución a priori ; ${\ Displaystyle P (\ theta)}$
observaciones ; ${\ Displaystyle {\ mathcal {D}} = \ {(x; a; r) \}}$
distribución a posteriori , donde es la función de verosimilitud. ${\ Displaystyle P (\ theta | {\ mathcal {D}}) \ propto P ({\ mathcal {D}} | \ theta) P (\ theta)}$ ${\ Displaystyle P ({\ mathcal {D}} | \ theta)}$

El muestreo de Thompson consiste en jugar que maximiza la expectativa de la ganancia esperada: ${\ Displaystyle a ^ {\ ast} \ in {\ mathcal {A}}}$

{\ Displaystyle \ int \ mathbb {I} \ left [\ mathbb {E} (r | a ^ {\ ast}, x, \ theta) = \ max _ {a '} \ mathbb {E} (r | a ', x, \ theta) \ right] P (\ theta | {\ mathcal {D}}) d \ theta,}

donde está la función del indicador . ${\ mathbb {I}}$

En la práctica, esta regla se implementa muestreando, en cada turno, los parámetros de la distribución a posteriori , y eligiendo la acción que maximiza , la expectativa de la ganancia esperada teniendo en cuenta el parámetro muestreado, la acción y el contexto actual. Conceptualmente, esto significa que el jugador instancia al azar sus creencias en cada turno y actúa de manera óptima a partir de esta información. En la mayoría de las aplicaciones prácticas, es computacionalmente costoso mantener en memoria y muestrear a partir de distribuciones posteriores exactas. El muestreo de Thompson se utiliza a menudo con técnicas de muestreo grueso. ${\ Displaystyle \ theta ^ {\ ast}}$ ${\ Displaystyle P (\ theta | {\ mathcal {D}})}$ ${\ Displaystyle a ^ {\ ast}}$ ${\ Displaystyle \ mathbb {E} [r | \ theta ^ {\ ast}, a ^ {\ ast}, x]}$

Historia

El muestreo de Thompson fue descrito por Thompson en 1933. Posteriormente fue redescubierto en numerosas ocasiones de forma independiente en el contexto de los problemas de los bandidos armados K. Una primera prueba de convergencia para la aplicación a los bandidos se presentó en 1997. La primera aplicación a los procesos de toma de decisiones de Markov se remonta al año 2000. Un enfoque relacionado se publicó en 2010. En 2010, también se demostró que el muestreo de Thompson corrige automáticamente de forma instantánea . Los resultados que muestran la convergencia asintótica para los bandidos de la información contextual se publicaron en 2011.

En la actualidad, el muestreo de Thompson se utiliza ampliamente en muchos problemas de aprendizaje electrónico: el muestreo de Thompson también se ha aplicado a las pruebas A / B en diseño web y publicidad en línea; El muestreo de Thompson sirve como base para el aprendizaje acelerado en la toma de decisiones descentralizada.

Vínculos con otros enfoques

Coincidencia de probabilidad

La probabilidad de coincidencia ( coincidencia de probabilidad ) es una decisión de política en la que la clase de pronóstico de membresía es proporcional a las tasas de la clase base. El muestreo de Thompson es una aplicación de este principio general al problema de los bandidos.

Por lo tanto, si, en el entrenamiento, se observan empates positivos en el 60% de los casos y empates negativos en el 40% de los casos, el observador que usa una estrategia de coincidencia de probabilidad predecirá (para ejemplos no etiquetados) un resultado. casos, y un resultado "negativo" en el 40% de los casos.

Algoritmos de límite de confianza superior (UCB)

Los algoritmos de muestreo de Thompson y los algoritmos relacionados con el límite de confianza superior son ambos algoritmos "optimistas": tienen en cuenta la incertidumbre en la estimación de los parámetros y exploran acciones con una probabilidad distinta de cero de ser óptimas.

Al explotar esta propiedad, es posible traducir los límites de arrepentimiento establecidos para los algoritmos UCB en límites de arrepentimiento bayesianos para el muestreo de Thompson o unificar el análisis de arrepentimiento entre estos algoritmos y otras clases de problemas.

Referencias

Thompson, William R. "en la probabilidad de que una probabilidad desconocida supera otro en vista de la evidencia de dos muestras" . Biometrika , 25 (3-4): 285-294, 1933.
Daniel J. Russo, Benjamin Van Roy, Abbas Kazerouni, Ian Osband y Zheng Wen (2018), "Un tutorial sobre Thompson muestreo", Fundamentos y Tendencias en Aprendizaje Automático: vol. 11: núm. 1, págs. 1-96. https://web.stanford.edu/~bvr/pubs/TS_Tutorial.pdf
J. Wyatt. Exploración e inferencia en el aprendizaje a partir del refuerzo . Tesis doctoral, Departamento de Inteligencia Artificial, Universidad de Edimburgo. Marzo de 1997.
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.
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 al 2 de julio de 2000, http://citeseerx.ist.psu.edu/viewdoc/summary?doi= 10.1.1.140.1701
BC mayo, 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
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/
OC Granmo y S. Glimsdal , “ Aprendizaje bayesiano acelerado para la toma de decisiones descentralizada basada en bandidos de dos brazos con aplicaciones para Goore Game ”, Inteligencia aplicada ,2012( DOI 10.1007 / s10489-012-0346-z )
Daniel J. Russo y Benjamin Van Roy (2014), "Aprendiendo a optimizar a través del 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 la exploración optimista", Avances en los sistemas de procesamiento de información neuronal 26, págs. 2256-2264. http://papers.nips.cc/paper/4909-eluder-dimension-and-the-sample-complexity-of-optimistic-exploration.pdf