Amostragem Thompson

Thompson amostragem, em homenagem a William R. Thompson, é um algoritmo heurístico para a escolha de ações que resolver o dilema exploração em exploração no bandido K-armada problema . Consiste em escolher a ação que maximiza a recompensa esperada em relação a uma crença desenhada ao acaso.

A descrição

Considere um conjunto de contextos , um conjunto de ações e recompensas em . A cada jogada, o jogador recebe um contexto , realiza uma ação e recebe uma recompensa seguindo uma distribuição que depende do contexto e da ação realizada. O objetivo do jogador é realizar as ações que maximizam os ganhos cumulativos. ${\ mathcal {X}}$ ${\ mathcal {A}}$ $\ mathbb {R}$ ${\ displaystyle x \ in {\ mathcal {X}}}$ $a \ in \ mathcal {A}$ ${\ displaystyle r \ in \ mathbb {R}}$

Os elementos da amostragem de Thompson são os seguintes:

uma função de verossimilhança ; ${\ displaystyle P (r | \ theta, a, x)}$
um conjunto de parâmetros da distribuição de ; $\ Theta$ $\ theta$ $r$
distribuição a priori ; ${\ displaystyle P (\ theta)}$
observações ; ${\ displaystyle {\ mathcal {D}} = \ {(x; a; r) \}}$
distribuição a posteriori , onde é a função de verossimilhança. ${\ displaystyle P (\ theta | {\ mathcal {D}}) \ propto P ({\ mathcal {D}} | \ theta) P (\ theta)}$ ${\ displaystyle P ({\ mathcal {D}} | \ theta)}$

A amostragem de Thompson consiste em jogar o que maximiza a expectativa do ganho esperado: ${\ 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,}

onde está a função do indicador . ${\ mathbb {I}}$

Na prática, esta regra é implementada amostrando, a cada turno, os parâmetros da distribuição a posteriori , e escolhendo a ação que maximiza , a expectativa de ganho esperado levando em consideração o parâmetro amostrado, a ação e o contexto atual. Conceitualmente, isso significa que o jogador instancia aleatoriamente suas crenças em cada turno e age de forma otimizada a partir dessas informações. Na maioria das aplicações práticas, é computacionalmente caro manter e amostrar de distribuições posteriores exatas. A amostragem de Thompson é freqüentemente usada com técnicas de amostragem grosseira. ${\ displaystyle \ theta ^ {\ ast}}$ ${\ displaystyle P (\ theta | {\ mathcal {D}})}$ ${\ displaystyle a ^ {\ ast}}$ ${\ displaystyle \ mathbb {E} [r | \ theta ^ {\ ast}, a ^ {\ ast}, x]}$

História

A amostragem de Thompson foi descrita por Thompson em 1933. Posteriormente, foi redescoberto inúmeras vezes de forma independente no contexto de questões de bandidos armados com K. Uma primeira prova de convergência para a aplicação aos bandidos foi apresentada em 1997. A primeira aplicação aos processos de tomada de decisão Markovianos data do ano 2000. Uma abordagem relacionada foi publicada em 2010. Em 2010, também foi mostrado que a amostragem de Thompson corrige automaticamente instantaneamente . Resultados que mostram convergência assintótica para bandidos de informação contextual foram publicados em 2011.

Hoje, a amostragem de Thompson é amplamente usada em muitos problemas de e-learning: a amostragem de Thompson também foi aplicada a testes A / B em web design e publicidade online; A amostragem de Thompson serve como base para o aprendizado acelerado na tomada de decisão descentralizada.

Links com outras abordagens

Correspondência de probabilidade

A probabilidade de correspondência ( correspondência de probabilidade ) é uma decisão de política em que a classe de previsão de associação é proporcional às taxas da classe base. A amostragem de Thompson é uma aplicação desse princípio geral ao problema dos bandidos.

Assim, se, no treinamento, empates positivos são observados em 60% dos casos e empates negativos em 40% dos casos, o observador que usa uma estratégia de correspondência de probabilidade irá prever (para exemplos não marcados) um resultado. "Positivo" em 60% dos casos, e um resultado "negativo" em 40% dos casos.

Algoritmos de limite de confiança superior (UCB)

Os algoritmos de amostragem de Thompson e os algoritmos relacionados ao limite de confiança superior são ambos algoritmos "otimistas": eles levam em consideração a incerteza na estimativa dos parâmetros e exploram ações com uma probabilidade diferente de zero de serem ótimas.

Ao explorar essa propriedade, é possível traduzir os limites de arrependimento estabelecidos para algoritmos UCB em limites de arrependimento Bayesianos para amostragem de Thompson ou unificar a análise de arrependimento entre esses algoritmos e outras classes de problemas.

Referências

Thompson, William R. "On a probabilidade de que uma probabilidade desconhecido excede outro, tendo em conta a evidência de duas amostras" . Biometrika , 25 (3-4): 285-294,1933.
Daniel J. Russo, Benjamin Van Roy, Abbas Kazerouni, Ian Osband e Zheng Wen (2018), "A Tutorial em Thompson amostragem", fundações e Trends in Machine Learning: Vol. 11: No. 1, pp 1-96. https://web.stanford.edu/~bvr/pubs/TS_Tutorial.pdf
J. Wyatt. Exploração e inferência em aprender com o reforço . Tese de doutorado, Departamento de Inteligência Artificial, Universidade de Edimburgo. Março de 1997.
PA Ortega e DA Braun. "A Minimum Relative Entropy Principle for Learning and Agting", Journal of Artificial Intelligence Research , 38, páginas 475-511, 2010.
MJA Strens. "A Bayesian Framework for Reinforcement Learning", Proceedings of the Seventeenth International Conference on Machine Learning , Stanford University, Califórnia, 29 de junho - 2 de julho de 2000, http://citeseerx.ist.psu.edu/viewdoc/summary?doi= 10.1.1.140.1701
BC Maio, BC, N. Korda, A. Lee, e DS Leslie. "Amostragem Bayesiana otimista em problemas de bandidos contextuais". Relatório técnico, Grupo de Estatísticas, Departamento de Matemática, Universidade de Bristol, 2011.
Chapelle, Olivier e Lihong Li. "Uma avaliação empírica da amostragem de Thompson." Avanços nos sistemas de processamento de informações neurais. 2011. http://papers.nips.cc/paper/4321-an-empirical-evaluation-of-thompson-sampling
O.-C. Granmo. "Resolvendo problemas de dois bandidos de Bernoulli usando um autômato de aprendizagem Bayesian", International Journal of Intelligent Computing and Cybernetics , 3 (2), 2010, 207-234.
Ian Clarke . "Teste A / B proporcional", 22 de setembro de 2011, http://blog.locut.us/2011/09/22/proportionate-ab-testing/
OC Granmo e S. Glimsdal , " Aprendizagem Bayesiana acelerada para tomada de decisão descentralizada baseada em bandidos de dois braços com aplicativos para o jogo Goore ", Inteligência Aplicada ,2012( DOI 10.1007 / s10489-012-0346-z )
Daniel J. Russo e Benjamin Van Roy (2014), "Learning to Optimize Via Posterior Sampling", Mathematics of Operations Research, vol. 39, nº 4, pp. 1221-1243, 2014. https://pubsonline.informs.org/doi/abs/10.1287/moor.2014.0650
Daniel J. Russo e Benjamin Van Roy (2013), "Eluder Dimension and the Sample Complexity of Optimistic Exploration", Advances in Neural Information Processing Systems 26, pp. 2256-2264. http://papers.nips.cc/paper/4909-eluder-dimension-and-the-sample-complexity-of-optimistic-exploration.pdf