Aller au contenu

Échantillonnage de Thompson

Un article de Wikipédia, l'encyclopédie libre.
Animation pour visualiser l'échantillonnage de Thompson
Exemple d'utilisation de l'échantillonnage de Thompson.

L'échantillonnage de Thompson [1],[2] nommé d'après William R. Thompson, est un algorithme heuristique permettant de choisir des actions qui résolvent le dilemme exploration-exploitation dans le problème des bandits à K bras. Elle consiste à choisir l'action qui maximise la récompense attendue par rapport à une croyance tirée au hasard.

La description

[modifier | modifier le code]

Soit un ensemble de contextes , un ensemble d'actions , et des récompenses dans . A chaque tour, le joueur reçoit un contexte , effectue une action et reçoit une récompense suivant une distribution qui dépend du contexte et de l'action effectuée. L'objectif du joueur est d'effectuer les actions qui maximisent les gains cumulés.

Les éléments de l'échantillonnage de Thompson sont les suivants:

  1. une fonction de vraisemblance ;
  2. un ensemble de paramètres de la distribution de ;
  3. une distribution à priori ;
  4. des observations ;
  5. une distribution a posteriori , où est la fonction de vraisemblance.

L’échantillonnage de Thompson consiste à jouer qui maximise l'espérance du gain attendu:

est la fonction indicatrice.

En pratique, cette règle est implémenté par échantillonnage, à chaque tour, des paramètres à partir de la distribution a posteriori , et en choisissant l'action qui maximise , l'espérance du gain attendu prenant en compte le paramètre échantillonné, l'action et le contexte actuel. Conceptuellement, cela signifie que le joueur instancie aléatoirement ses croyances à chaque tour et agit optimalement à partir de ces informations. Dans la plupart des applications pratiques, il est informatiquement coûteux de maintenir en mémoire et d'échantillonner à partir des distributions a posteriori exactes. L'échantillonnage de Thompson est souvent utilisé avec des techniques d'échantillonnage approximative[2].

L'échantillonnage de Thompson a été décrit par Thompson en 1933 [1]. Il a par la suite été redécouvert de nombreuses fois indépendamment dans le contexte de problèmes de bandits à K bras[3],[4],[5],[6],[7],[8]. Une première preuve de convergence pour dans l'application aux bandits a été présentée en 1997[3]. La première application à des processus de décision markovien remonte à l'an 2000 [5]. Une approche connexe a été publiée en 2010[4]. En 2010, il a également été démontré que l'échantillonnage de Thompson se corrige automatiquement de manière instantanée [8]. Des résultats montrant la convergence asymptotique pour les bandits à information contextuelle ont été publiés en 2011[6].

Aujourd'hui, l'échantillonnage de Thompson est largement utilisé dans de nombreux problèmes d'apprentissage en ligne: l’échantillonnage de Thompson a également été appliqué aux tests A / B dans la conception de sites Web et la publicité en ligne[9]. L'échantillonnage de Thompson sert de base à l'apprentissage accéléré dans la prise de décision décentralisée[10].

Liens avec d'autres approches

[modifier | modifier le code]

Correspondance de probabilité

[modifier | modifier le code]

La correspondance de probabilité (Probability matching) est une stratégie de décision dans laquelle les prévisions d'appartenance à une classe sont proportionnelles aux taux de base de la classe. L'échantillonnage de Thompson est une application de ce principe général au problème de bandits.

Ainsi, si, à l’entraînement, des tirages positifs sont observés dans 60% des cas et des tirages négatifs dans 40% des cas, l’observateur qui utilise une stratégie de correspondance des probabilités prédira (pour les exemples non étiquetés) un résultat "positif" dans 60% des cas, et un résultat "négatif" sur 40% des cas.

Algorithmes de borne supérieure de confiance (UCB)

[modifier | modifier le code]

Les algorithmes d'échantillonnage de Thompson et les algorithmes liés à la borne supérieure de confiance sont tous deux des algorithmes "optimistes": ils prennent en compte l'incertitude sur l'estimation des paramètres et explorent des actions ayant une probabilité non nulle d'être optimales.

En exploitant cette propriété, il est possible de traduire les limites de regret établies pour les algorithmes UCB en limites de regret bayésiennes pour l'échantillonnage de Thompson [11] ou d'unifier l'analyse de regret entre ces algorithmes et d'autres classes de problèmes[12].

Références

[modifier | modifier le code]
  1. a et b Thompson, William R. "On the likelihood that one unknown probability exceeds another in view of the evidence of two samples". Biometrika, 25(3–4):285–294, 1933.
  2. a et b Daniel J. Russo, Benjamin Van Roy, Abbas Kazerouni, Ian Osband and Zheng Wen (2018), "A Tutorial on Thompson Sampling", Foundations and Trends in Machine Learning: Vol. 11: No. 1, pp 1-96. https://web.stanford.edu/~bvr/pubs/TS_Tutorial.pdf
  3. a et b J. Wyatt. Exploration and Inference in Learning from Reinforcement. Ph.D. thesis, Department of Artificial Intelligence, University of Edinburgh. March 1997.
  4. a et b P. A. Ortega and D. A. Braun. "A Minimum Relative Entropy Principle for Learning and Acting", Journal of Artificial Intelligence Research, 38, pages 475–511, 2010.
  5. a et b M. J. A. Strens. "A Bayesian Framework for Reinforcement Learning", Proceedings of the Seventeenth International Conference on Machine Learning, Stanford University, California, June 29–July 2, 2000, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.140.1701
  6. a et b B. C. May, B. C., N. Korda, A. Lee, and D. S. Leslie. "Optimistic Bayesian sampling in contextual-bandit problems". Technical report, Statistics Group, Department of Mathematics, University of Bristol, 2011.
  7. Chapelle, Olivier, and Lihong Li. "An empirical evaluation of thompson sampling." Advances in neural information processing systems. 2011. http://papers.nips.cc/paper/4321-an-empirical-evaluation-of-thompson-sampling
  8. a et b O.-C. Granmo. "Solving Two-Armed Bernoulli Bandit Problems Using a Bayesian Learning Automaton", International Journal of Intelligent Computing and Cybernetics, 3 (2), 2010, 207-234.
  9. Ian Clarke. "Proportionate A/B testing", September 22nd, 2011, http://blog.locut.us/2011/09/22/proportionate-ab-testing/
  10. O. C. Granmo et S. Glimsdal, « Accelerated Bayesian learning for decentralized two-armed bandit based decision making with applications to the Goore Game », Applied Intelligence,‎ (DOI 10.1007/s10489-012-0346-z)
  11. Daniel J. Russo and Benjamin Van Roy (2014), "Learning to Optimize Via Posterior Sampling", Mathematics of Operations Research, Vol. 39, No. 4, pp. 1221-1243, 2014. https://pubsonline.informs.org/doi/abs/10.1287/moor.2014.0650
  12. Daniel J. Russo and 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