Bandit manchot (mathématiques)

Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?

Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.

Découvrez-en plus sur les applications Graph.

vignette|Une rangée de machines à sous à Las Vegas. En mathématiques, plus précisément en théorie des probabilités, le problème du bandit manchot (généralisable en problème du bandit à K bras ou problème du bandit à N bras) se formule de manière imagée de la façon suivante : un utilisateur (un agent), face à des machines à sous, doit décider quelles machines jouer. Chaque machine donne une récompense moyenne que l'utilisateur ne connait pas a priori. L'objectif est de maximiser le gain cumulé de l'utilisateur. C'est un exemple d'apprentissage par renforcement. Typiquement, la politique de l'utilisateur oscille entre exploitation (utiliser la machine dont il a appris qu'elle récompense beaucoup) et exploration (tester une autre machine pour espérer gagner plus). Le problème de bandit manchot peut être vu comme un processus de décision markovien avec un seul état. Dans cette section, nous formalisons le problème en reprenant quelques notations de l'article d'Auer et al. Considérons K machines à sous. L'entrée du problème est donnée par des variables aléatoires Xi,n pour tout 1 ≤ i ≤ K, et n ≥ 1, où l'indice i représente une des K machines (ou un « bras » du bandit) et l'indice n représente un tour de jeu. On suppose toutes ces variables aléatoires indépendantes et que les variables d'une même machine i, c'est-à-dire les variables Xi,1, Xi,2, etc., suivent la même distribution de probabilité inconnue de l'agent, d'espérance μi. Au tour numéro n, l'utilisateur va recevoir une récompense qui dépend de la machine qu'il choisit. Un exemple classique de bandit manchot est le cas où la machine i apporte une récompense de 1 avec une probabilité pi et 0 avec la probabilité 1-pi. L'utilisateur essaye de trouver la machine à sous qui apporte la plus grande récompense moyenne. Une politique ou stratégie pour le problème du manchot est un algorithme qui choisit la machine suivante à jouer, en se basant sur les choix précédents et sur les récompenses obtenues.

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Publications associées (5)

Afficher plus

Personnes associées (4)

Concepts associés (2)

Cours associés (9)

Séances de cours associées (28)

Bandit manchot (mathématiques)

Apprentissage automatique

L'apprentissage automatique (en anglais : machine learning, « apprentissage machine »), apprentissage artificiel ou apprentissage statistique est un champ d'étude de l'intelligence artificielle qui se fonde sur des approches mathématiques et statistiques pour donner aux ordinateurs la capacité d'« apprendre » à partir de données, c'est-à-dire d'améliorer leurs performances à résoudre des tâches sans être explicitement programmés pour chacune. Plus largement, il concerne la conception, l'analyse, l'optimisation, le développement et l'implémentation de telles méthodes.

EE-735: Online learning in games

This course provides an overview of recent developments in online learning, game theory, and variational inequalities and their point of intersection with a focus on algorithmic development. The prima

COM-406: Foundations of Data Science

We discuss a set of topics that are important for the understanding of modern data science but that are typically not taught in an introductory ML course. In particular we discuss fundamental ideas an

EE-618: Theory and Methods for Reinforcement Learning

This course describes theory and methods for decision making under uncertainty under partial feedback.

Agents d'apprentissage: Tradeoff Exploration-Exploitation

Explore le compromis exploration-exploitation dans l'apprentissage des effets inconnus des actions en utilisant des bandits multi-armés et Q-learning.

Renforcement de l'apprentissage : bases et applications

Couvre les bases de l'apprentissage de renforcement, y compris l'apprentissage d'essai et d'erreur, l'apprentissage Q, le RL profond, et les applications dans le jeu et la planification.

Renforcement de l'apprentissage : Q-Learning

Couvre Q-Learning, un algorithme d'apprentissage par renforcement sans modèle, et son application à Tic-Tac-Toe avec des exemples et des quiz.

Asymptotically Optimal Contextual Bandit Algorithm Using Hierarchical Structures

Hakan Gökcesu, Kaan Gökcesu

We propose an online algorithm for sequential learning in the contextual multiarmed bandit setting. Our approach is to partition the context space and, then, optimally combine all of the possible mapp

2019

Big-Data Streaming Applications Scheduling Based on Staged Multi-armed Bandits

David Atienza Alonso, Cem Tekin, Karim Kanoun

Several techniques have been recently proposed to adapt Big-Data streaming applications to existing many core platforms. Among these techniques, online reinforcement learning methods have been propose

Institute of Electrical and Electronics Engineers2016

Big-Data Streaming Applications Scheduling Based on Staged Multi-Armed Bandits

David Atienza Alonso, Cem Tekin, Karim Kanoun

Institute of Electrical and Electronics Engineers2016