En apprentissage par renforcement, l'agent ou le décideur génère ses données d'entraînement en interagissant avec le monde. L’agent doit apprendre les conséquences de ses actions par essais et erreurs, plutôt que de se voir explicitement indiquer l’action correcte.

Problème de bandit à plusieurs bras

Dans l'apprentissage par renforcement, nous utilisons le problème des bandits multi-bras pour formaliser la notion de prise de décision dans l'incertitude à l'aide de bandits à cinq bras. Un décideur ou un agent est présent dans Multi-Armed Bandit Problem pour choisir entre k actions différentes et reçoit une récompense en fonction de l'action qu'il choisit. Le problème du bandit est utilisé pour décrire les concepts fondamentaux de l'apprentissage par renforcement, tels que les récompenses, les intervalles de temps et les valeurs.

L'image ci-dessus représente une machine à sous également connue sous le nom de bandit à deux leviers. Nous supposons que chaque levier a une distribution distincte de récompenses et qu'il existe au moins un levier qui génère une récompense maximale.

La distribution de probabilité de la récompense correspondant à chaque levier est différente et est inconnue du joueur (décideur). L’objectif ici est donc d’identifier quel levier actionner pour obtenir la récompense maximale après une série d’essais donnée.

Par exemple:

Imaginez un essai de publicité en ligne dans lequel un annonceur souhaite mesurer le taux de clics de trois publicités différentes pour le même produit. Chaque fois qu'un utilisateur visite le site Web, l'annonceur affiche une annonce au hasard. L'annonceur vérifie ensuite si l'utilisateur clique ou non sur l'annonce. Au bout d'un moment, l'annonceur remarque qu'une annonce semble mieux fonctionner que les autres. L’annonceur doit désormais choisir entre s’en tenir à l’annonce la plus performante ou poursuivre l’étude randomisée.
Si l'annonceur n'affiche qu'une seule annonce, alors il ne peut plus collecter de données sur les deux autres annonces. Peut-être que l'une des autres publicités est meilleure, elle semble seulement pire à cause du hasard. Si les deux autres annonces sont moins bonnes, la poursuite de l'étude peut avoir un impact négatif sur le taux de clics. Cet essai publicitaire illustre la prise de décision dans l’incertitude.
Dans l’exemple ci-dessus, le rôle d’agent est joué par un annonceur. L'annonceur doit choisir entre trois actions différentes pour afficher la première, la deuxième ou la troisième annonce. Chaque annonce est une action. Choisir cette annonce rapporte une récompense inconnue. Enfin, le profit de l'annonceur après la diffusion de la publicité est la récompense que l'annonceur reçoit.

Valeurs d'action :

Pour que l’annonceur puisse décider quelle action est la meilleure, nous devons définir la valeur de chaque action. Nous définissons ces valeurs à l’aide de la fonction action-valeur en utilisant le langage des probabilités. L’intérêt de sélectionner une action q_*(un) est définie comme la récompense attendue R._t nous recevons lorsque nous effectuons une action un à partir de l’ensemble possible d’actions.

Le but de l’agent est de maximiser la récompense attendue en sélectionnant l’action qui a la valeur d’action la plus élevée.

Estimation de la valeur de l'action :

modèle de conception singleton java

Puisque la valeur de la sélection d'une action, c'est-à-dire Q_*(un) n'est pas connu de l'agent, nous utiliserons donc le moyenne de l'échantillon méthode pour l’estimer.

Exploration vs Exploitation :

Action gourmande : Lorsqu'un agent choisit une action qui a actuellement la plus grande valeur estimée. L'agent exploite ses connaissances actuelles en choisissant l'action gourmande. Action non gourmande : Lorsque l'agent ne choisit pas la plus grande valeur estimée et sacrifie la récompense immédiate dans l'espoir d'obtenir plus d'informations sur les autres actions. Exploration : Elle permet à l'agent d'améliorer ses connaissances sur chaque action. Espérons que cela mènera à un bénéfice à long terme. Exploitation : Elle permet à l'agent de choisir l'action gourmande pour tenter d'obtenir le plus de récompense pour un bénéfice à court terme. Une sélection d’actions purement gourmande peut conduire à un comportement sous-optimal.

Un dilemme apparaît entre l’exploration et l’exploitation car un agent ne peut pas choisir d’explorer et d’exploiter en même temps. Par conséquent, nous utilisons le Limite de confiance supérieure algorithme pour résoudre le dilemme exploration-exploitation

Sélection d'action avec limite de confiance supérieure :
La sélection d’actions avec limite de confiance supérieure utilise l’incertitude dans les estimations de la valeur d’action pour équilibrer l’exploration et l’exploitation. Puisqu'il existe une incertitude inhérente à l'exactitude des estimations de la valeur d'action lorsque nous utilisons un ensemble échantillonné de récompenses, UCB utilise l'incertitude des estimations pour piloter l'exploration.

Q_t(un) représente ici l'estimation actuelle de l'action un au moment t . Nous sélectionnons l'action qui a la valeur d'action estimée la plus élevée plus le terme d'exploration de la limite de confiance supérieure.

Q(R) dans l'image ci-dessus représente l'estimation actuelle de la valeur de l'action pour l'action UN . Les parenthèses représentent un intervalle de confiance autour de Q_*(UN) ce qui dit que nous sommes convaincus que la valeur réelle de l'action UN se trouve quelque part dans cette région.

code absc

La tranche inférieure est appelée limite inférieure et la tranche supérieure est appelée limite supérieure. La région entre parenthèses est l’intervalle de confiance qui représente l’incertitude des estimations. Si la région est très petite, nous devenons alors très certains que la valeur réelle de l'action UN est proche de notre valeur estimée. D’un autre côté, si la région est vaste, nous devenons alors incertains de la valeur de l’action UN est proche de notre valeur estimée.

Le Limite de confiance supérieure suit le principe de l'optimisme face à l'incertitude qui implique que si nous sommes incertains quant à une action, nous devons supposer avec optimisme que c'est la bonne action.

Par exemple, disons que nous avons ces quatre actions avec les incertitudes associées dans l’image ci-dessous, notre agent n’a aucune idée quelle est la meilleure action. Ainsi, selon l'algorithme UCB, il sélectionnera de manière optimiste l'action qui a la limite supérieure la plus élevée, c'est-à-dire : UN . En faisant cela, soit il aura la valeur la plus élevée et obtiendra la récompense la plus élevée, soit en prenant cela, nous apprendrons une action que nous connaissons le moins.

Supposons qu'après avoir sélectionné l'action UN nous nous retrouvons dans un état représenté dans l’image ci-dessous. Cette fois, UCB sélectionnera l'action B depuis Q(B) a la limite de confiance supérieure la plus élevée car son estimation de la valeur d'action est la plus élevée, même si l'intervalle de confiance est petit.

Dans un premier temps, UCB explore davantage pour réduire systématiquement l'incertitude, mais son exploration diminue avec le temps. On peut ainsi dire qu'UCB obtient en moyenne une plus grande récompense que d'autres algorithmes tels que Epsilon-greedy, Optimistic Initial Values, etc.