Muestreo de Thompson

Tipo de técnica heurística

Ejemplo concreto de muestreo de Thompson aplicado para simular la evaluación de la eficacia del tratamiento

El muestreo de Thompson , ^{[1] [2] [3]} llamado así por William R. Thompson , es una heurística para elegir acciones que aborden el dilema de exploración-explotación en el problema de las máquinas tragamonedas . Consiste en elegir la acción que maximice 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 . El objetivo del jugador es realizar acciones en los diversos contextos, como maximizar las recompensas acumuladas. Específicamente, en cada ronda, el jugador obtiene un contexto , realiza una acción y recibe una recompensa siguiendo una distribución que depende del contexto y la acción emitida. ${\displaystyle {\mathcal {X}}}$ ${\displaystyle {\mathcal {A}}}$ ${\displaystyle \mathbb {R} }$ ${\displaystyle x\in {\mathcal {X}}}$ ${\displaystyle a\in {\mathcal {A}}}$ ${\displaystyle r\in \mathbb {R} }$

Los elementos del muestreo de Thompson son los siguientes:

1. una función de verosimilitud ; ${\displaystyle P(r|\theta ,a,x)}$
2. un conjunto de parámetros de la distribución de ; ${\displaystyle \Theta }$ ${\displaystyle \theta }$ ${\displaystyle r}$
3. una distribución previa de estos parámetros; ${\displaystyle P(\theta )}$
4. observaciones pasadas tripletes ; ${\displaystyle {\mathcal {D}}=\{(x;a;r)\}}$
5. una distribución posterior , 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 la acción según la probabilidad de que maximice la recompensa esperada; la acción se elige con probabilidad. ${\displaystyle a^{\ast }\in {\mathcal {A}}}$ ${\displaystyle a^{\ast }}$

${\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 ,}$

¿Dónde está la función indicadora ? ${\displaystyle \mathbb {I} }$

En la práctica, la regla se implementa mediante muestreo. En cada ronda, se toman muestras de los parámetros de la distribución posterior y se elige una acción que maximice , 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 aleatoriamente 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 tomar muestras de una distribución posterior sobre los modelos. Como tal, el muestreo de Thompson se utiliza a menudo junto con técnicas de muestreo aproximado. ^[3] ${\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 originalmente por Thompson en 1933. ^[1] Posteriormente fue redescubierto numerosas veces de forma independiente en el contexto de problemas de bandidos multiarmados. ^{[4] [5] [6] [7] [8] [9]} Una primera prueba de convergencia para el caso de los bandidos se ha mostrado en 1997. ^[4] La primera aplicación a los procesos de decisión de Markov fue en 2000. ^[6] Un enfoque relacionado (ver regla de control bayesiana) se publicó en 2010. ^[5] En 2010 también se demostró que el muestreo de Thompson se autocorrige instantáneamente . ^[9] Los resultados de convergencia asintótica para bandidos contextuales se publicaron en 2011. ^[7] 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, ^[10] y el aprendizaje acelerado en la toma de decisiones descentralizada. ^[11] Se ha propuesto un algoritmo de muestreo doble de Thompson (D-TS) ^{[12] 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

La coincidencia de probabilidad 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 ejemplos negativos 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 los casos y una etiqueta de clase de "negativo" en el 40 % de los casos.

Regla de control bayesiana

Se ha demostrado que una generalización del muestreo de Thompson a entornos dinámicos arbitrarios y estructuras causales, conocida como regla de control bayesiana , es la solución óptima al problema de codificación adaptativa con acciones y observaciones. ^[5] En esta formulación, un agente se conceptualiza como una mezcla de 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. Sean las acciones emitidas por un agente hasta el momento y sean las observaciones recopiladas por el agente hasta el momento . Luego, el agente emite la acción con probabilidad: ^[5] ${\displaystyle a_{1},a_{2},\ldots ,a_{T}}$ ${\displaystyle T}$ ${\displaystyle o_{1},o_{2},\ldots ,o_{T}}$ ${\displaystyle T}$ ${\displaystyle a_{T+1}}$

${\displaystyle P(a_{T+1}|{\hat {a}}_{1:T},o_{1:T}),}$

donde la notación "sombrero" denota el hecho de que se trata de una intervención causal (ver Causalidad ), y no de una observación ordinaria. Si el agente tiene creencias sobre sus comportamientos, entonces la regla de control bayesiana se convierte en ${\displaystyle {\hat {a}}_{t}}$ ${\displaystyle a_{t}}$ ${\displaystyle \theta \in \Theta }$

${\displaystyle P(a_{T+1}|{\hat {a}}_{1:T},o_{1:T})=\int _{\Theta }P(a_{T+1}|\theta ,{\hat {a}}_{1:T},o_{1:T})P(\theta |{\hat {a}}_{1:T},o_{1:T})\,d\theta }$,

donde es la distribución posterior sobre el parámetro dadas las acciones y observaciones . ${\displaystyle P(\theta |{\hat {a}}_{1:T},o_{1:T})}$ ${\displaystyle \theta }$ ${\displaystyle a_{1:T}}$ ${\displaystyle o_{1:T}}$

En la práctica, el control bayesiano consiste en 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 únicamente 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 acciones . ${\displaystyle \theta ^{\ast }}$ ${\displaystyle P(\theta |{\hat {a}}_{1:T},o_{1:T})}$ ${\displaystyle o_{1},o_{2},\ldots ,o_{T}}$ ${\displaystyle a_{1},a_{2},\ldots ,a_{T}}$ ${\displaystyle a_{T+1}^{\ast }}$ ${\displaystyle P(a_{T+1}|\theta ^{\ast },{\hat {a}}_{1:T},o_{1:T})}$

Algoritmos de límite de confianza superior (UCB)

Los algoritmos de muestreo de Thompson y de límite superior de confianza comparten una propiedad fundamental que subyace a muchas de sus garantías teóricas. En términos generales, ambos algoritmos asignan un esfuerzo exploratorio a acciones que podrían ser óptimas y son, 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 ^[13] o unificar el análisis de arrepentimiento en ambos algoritmos y en muchas clases de problemas. ^[14]

Referencias

1. Thompson, William R. "Sobre la probabilidad de que una probabilidad desconocida exceda a otra en vista de la evidencia de dos muestras". Biometrika , 25(3–4):285–294, 1933.
2. Thompson, WR (1935). Sobre la teoría de la distribución. American Journal of Mathematics , 57(2), 450-456.
3. Daniel J. Russo, Benjamin Van Roy, Abbas Kazerouni, Ian Osband y Zheng Wen (2018), "Un tutorial sobre muestreo de Thompson", Fundamentos y tendencias en aprendizaje automático: vol. 11: n.º 1, págs. 1-96. https://web.stanford.edu/~bvr/pubs/TS_Tutorial.pdf
4. 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.
5. PA Ortega y DA Braun. "Un principio de entropía relativa mínima para el aprendizaje y la actuación", Journal of Artificial Intelligence Research , 38, páginas 475–511, 2010, http://arxiv.org/abs/0810.3605
6. MJA Strens. "Un marco bayesiano para el aprendizaje por refuerzo", Actas de la decimoséptima conferencia internacional sobre aprendizaje automático , Universidad de Stanford, California, 29 de junio–2 de julio de 2000, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.140.1701
7. BC May, BC, N. Korda, A. Lee y DS Leslie. "Muestreo bayesiano optimista en problemas de bandidos contextuales". Informe técnico, Grupo de Estadística, Departamento de Matemáticas, Universidad de Bristol, 2011.
8. 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
9. O.-C. Granmo. "Resolución de problemas de la máquina tragamonedas de dos brazos utilizando un autómata de aprendizaje bayesiano", Revista internacional de computación inteligente y cibernética , 3 (2), 2010, 207-234.
10. Ian Clarke . "Pruebas A/B proporcionales", 22 de septiembre de 2011, http://blog.locut.us/2011/09/22/proportionate-ab-testing/
11. Granmo, OC; Glimsdal, S. (2012). "Aprendizaje bayesiano acelerado para la toma de decisiones descentralizada basada en máquinas tragamonedas con aplicaciones al juego de Goore". Inteligencia Aplicada . 38 (4): 479–488. doi :10.1007/s10489-012-0346-z. hdl : 11250/137969 . S2CID  8746483.
12. Wu, Huasen; Liu, Xin; Srikant, R (2016), Muestreo de doble Thompson para bandidos en duelo , arXiv : 1604.07101 , Bibcode :2016arXiv160407101W
13. Russo, Daniel J.; Van Roy, Benjamin (2014). "Aprendiendo a optimizar mediante muestreo posterior". Matemáticas de la investigación de operaciones . 39 (4): 1221–1243. arXiv : 1301.2609 . doi :10.1287/moor.2014.0650.
14. Daniel J. Russo y Benjamin Van Roy (2013), "Dimensión de elusión y complejidad de muestra de la exploración optimista", Advances in Neural Information Processing Systems 26, págs. 2256-2264. https://proceedings.neurips.cc/paper/2013/file/41bfd20a38bb1b0bec75acf0845530a7-Paper.pdf