Intelligence artificielle

Exploration vs Exploitation dans le réglage Bandit multi-armes.

Exploration vs Exploitation dans le réglage Bandit multi-armes.


Épisode 5, démystification du dilemme exploration-exploitation, algorithmes gloutons, gloutons et UCB dans le cas des bandits à plusieurs bras.

Exploration vs. Exploitation

La prise de décision en ligne implique un choix fondamental; exploration, où nous recueillons plus d’informations qui pourraient nous amener à prendre de meilleures décisions à l’avenir ou à l’exploitation, où nous prenons la meilleure décision compte tenu des informations actuelles.

Cela vient parce que nous apprenons en ligne. Dans le cadre de l'apprentissage par renforcement, personne ne nous fournit un lot de données, comme dans l'apprentissage supervisé. Nous collectons des données au fur et à mesure, et les actions que nous prenons affectent les données que nous voyons. Il est donc parfois utile de prendre différentes mesures pour obtenir de nouvelles données.

Un problème de bandit armé

Considérez le problème d'apprentissage suivant. Vous êtes confronté à plusieurs reprises à un choix parmi k différentes options ou actions. Après chaque choix, vous recevez une récompense numérique choisie parmi une distribution de probabilité stationnaire qui dépend de l'action sélectionnée. Votre objectif est de maximiser la récompense totale attendue sur une période donnée, par exemple 1 000 sélections d’action ou pas de temps.

Ceci est la forme originale de la kbandit armé, ainsi nommé par analogie à une machine à sous, sauf qu'il a k leviers au lieu d'un. Chaque sélection d’action est comme un jeu de l’un des leviers de la machine à sous, et les récompenses sont les récompenses pour avoir touché le jackpot. En sélectionnant des actions répétées, vous maximisez vos gains en concentrant vos actions sur les meilleurs leviers.

Chacun de k actions a une récompense attendue ou moyenne étant donné que cette action est sélectionnée; appelons cela la valeur de cette action. On note l'action sélectionnée sur le pas de temps t comme À, et la récompense correspondante en tant que Rt. La valeur alors d'une action arbitraire une, noté q * (a), est la récompense attendue étant donné que une est sélectionné:

Exploration vs Exploitation dans le réglage Bandit multi armes - Exploration vs Exploitation dans le réglage Bandit multi-armes.

Si nous connaissions la valeur de chaque action, il serait trivial de résoudre le problème kproblème de bandit armé: vous choisiriez toujours l'action avec la plus grande valeur. Nous supposons que nous ne connaissons pas les valeurs d’action avec certitude, bien que nous puissions avoir des estimations. On note la valeur estimée de l'action une au pas de temps t comme Qt (a). Nous voudrions Qt (a) être proche de q * (a).

Si vous conservez des estimations des valeurs d'action, il existe à tout moment au moins une action dont la valeur estimée est la plus grande. Nous appelons cela la glouton actes. Lorsque vous sélectionnez l'une de ces actions, nous disons que vous exploitez votre connaissance actuelle des valeurs des actions. Si, au lieu de cela, vous sélectionnez l’une des actions non-gourmandes, nous dirons que vous explorez, car cela vous permet d’améliorer votre estimation de la valeur de l’action non-gourmande. L'exploitation est la bonne chose à faire pour maximiser la récompense escomptée sur une étape, mais l'exploration peut produire la plus grande récompense totale à long terme, alors que devrions-nous faire pour résoudre ce dilemme?.

Principes d'exploration

Nous commençons par examiner les méthodes permettant d’estimer les valeurs des actions et d’utiliser ces estimations pour prendre des décisions de sélection d’action, appelées collectivement méthodes d’action-valeur. Rappelons que le vrai La valeur d'une action est la récompense moyenne lorsque cette action est sélectionnée. Une façon naturelle d’estimer cela est de faire la moyenne des récompenses réellement reçues:

Si le dénominateur est zéro, alors nous définissons à la place Qt (a) comme une valeur par défaut, telle que 0. Comme le dénominateur va à l'infini, par la loi des grands nombres, Qt (a) converge vers q * (a). Nous appelons cela la méthode de la moyenne de l'échantillon pour estimer les valeurs d'action, car chaque estimation est une moyenne de l'échantillon de récompenses pertinentes. Bien entendu, il ne s’agit que d’une façon d’estimer les valeurs d’action, et pas nécessairement la meilleure.

Le regret

Plutôt que de prendre en compte le montant de la récompense que nous avons, nous pourrions poser une question: combien avons-nous fait de pire que le meilleur que nous aurions pu éventuellement faire? La valeur optimale V * est le meilleur que nous aurions pu faire si nous savions quelle machine rapportait le plus:

1543909965 893 Exploration vs Exploitation dans le réglage Bandit multi armes - Exploration vs Exploitation dans le réglage Bandit multi-armes.

Le regret est à quel point nous sommes loin de V *, c’est la perte d’opportunité pour un pas d’espoir,

1543909966 321 Exploration vs Exploitation dans le réglage Bandit multi armes - Exploration vs Exploitation dans le réglage Bandit multi-armes.

Le regret total est le total des pertes d’opportunité sur toutes les étapes,

Nous voulons maximiser la récompense cumulée, ce qui signifie que nous voulons minimiser le regret total. Il est utile de penser au regret car cela nous aide à comprendre à quel point un algorithme peut être efficace. Nous voulons trouver des algorithmes qui font regretter chaque pas vers zéro.

Nous pouvons formuler le regret d'une autre manière. Considérer Nt (a)- le nombre - soit le nombre attendu de fois que nous avons sélectionné l'action une . Le gab Δa est la différence de valeur entre l'action uneet action optimale une*,

1543909966 536 Exploration vs Exploitation dans le réglage Bandit multi armes - Exploration vs Exploitation dans le réglage Bandit multi-armes.

Maintenant, nous pouvons faire des regrets en fonction des lacunes et des chiffres,

Si nous résumons tout ce que nous avons perdu à chaque fois que nous passions à l’action une, cela revient à compter combien de fois nous avons choisi cette action et à le multiplier par le nombre de pertes que nous avons perdues à chaque fois que nous choisissons cette action.

Chaque fois que le gab est énorme, c’est-à-dire qu’une machine est vraiment horrible, nous devons nous assurer que nous tirons ce bras très peu de fois, alors que s’il ya une autre machine qui a un petit gab, nous voulons maintenant tirer de plus en plus ce bras. . Un bon algorithme assure de petits comptes pour les gros gabs. Le problème est que les gabs ne sont pas connus car on ne sait pas V * .

Algorithme Gourmand
Fig.1 courtoisie de David Silver

Cette figure montre le regret total en fonction des pas de temps et de différents algorithmes pour la sélection des actions. La première et la plus simple consiste à sélectionner l’une des actions ayant la valeur estimée la plus élevée, c’est-à-dire l’une des actions gourmandes. Une action gourmande est l'action dont la valeur estimée est la plus grande. S'il y a plus d'une action gourmande, une sélection est effectuée de manière arbitraire, peut-être au hasard. Nous écrivons cette méthode de sélection d'action gourmande comme,

1543909966 404 Exploration vs Exploitation dans le réglage Bandit multi armes - Exploration vs Exploitation dans le réglage Bandit multi-armes.

où le argmax dénote l'action unepour lequel l'expression qui suit est maximisée. La sélection d'actions gloutonnes exploite toujours les connaissances actuelles pour maximiser la récompense immédiate; il ne passe pas du tout du temps à échantillonner des actions apparemment inférieures pour voir si elles pourraient vraiment être meilleures. Si gourmand peut rester bloqué sur une action sous-optimale, ce qui rend le regret total linéaire pour toujours.

Les valeurs d'action initiales peuvent également être utilisées comme un moyen simple d'encourager l'exploration. C'est appelé “Gourmand à initialisation optimiste” . Supposons qu'au lieu de définir la valeur d'action initiale sur zéro, nous les fixons à +5, étant donné que la moyenne de toutes les actions est 0 par exemple, donc une estimation initiale de +5 est largement optimiste. Nous allons supposer que tout est vraiment bon jusqu'à preuve du contraire.

Cet optimisme encourage la méthode gourmande à explorer. Quelle que soit l'action sélectionnée à l'origine, la récompense est inférieure aux estimations initiales. l'agent passe à d'autres actions étant «déçu» de la récompense qu'il reçoit. Il en résulte que toutes les actions sont essayées plusieurs fois avant que les estimations de valeur ne convergent. Le système effectue beaucoup d’exploration, même si des actions gourmandes sont sélectionnées en permanence. C’est un truc simple qui peut s’avérer très efficace sur les problèmes fixes, c’est-à-dire pour les problèmes pour lesquels les probabilités de récompense ne changent pas dans le temps. Mais cette méthode est loin d’être une approche généralement utile pour encourager l’exploration.

Si la tâche change, ce qui crée un besoin d'exploration renouvelé, cette méthode ne peut pas vous aider. Toute méthode qui se concentre sur les conditions initiales de manière particulière est peu susceptible d’aider le cas général non stationnaire. Le début des temps ne se produit qu'une seule fois et nous ne devrions donc pas trop nous concentrer sur cela.

Un autre problème de cette méthode est que peu d’échantillons malchanceux peuvent verrouiller pour toujours des actions optimales. Supposons que j’ai commencé par penser que l’action a1est le meilleur. J'ai essayé, je suis malchanceux. Je réessaye, je suis malchanceux. Maintenant, je peux finir par verrouiller cette action pour toujours parce que je pourrais essayer une autre action. a2 , et il s’avère être meilleur et je n’explore jamais a1 encore. Nous finissons donc par avoir des regrets à chaque pas.

ε-greey Algorithme

Une alternative simple à la sélection d'action gourmande consiste à se comporter avec avidité la plupart du temps, mais de temps en temps, par exemple avec une faible probabilité ε, sélectionnez au hasard parmi toutes les actions ayant la même probabilité, indépendamment des estimations de la valeur d'action. L’un des avantages de cette méthode est que, dans la mesure où le nombre d’étapes augmente, chaque action est échantillonnée un nombre infini de fois, garantissant ainsi la Qt (a)converger vers q * (a).

L'algorithme ε-greedy continue d'explorer pour toujours, avec la probabilité 1- ε de sélectionner la meilleure action, avec la probabilité ε de sélectionner une action aléatoire. Chaque fois que nous explorons au hasard, nous risquons fort de commettre des erreurs sans tirer le meilleur bras. Nous continuons donc à regretter à chaque pas de temps. ε-gourmand a un regret total linéaire.

Pour évaluer l'efficacité relative des algorithmes gloutons et gloutons, nous les comparons numériquement sur une suite de problèmes de test. Ceci est un ensemble de 2000 générés aléatoirement k problèmes de bandits armés k= 10. Pour chaque problème de bandit, tel que celui présenté dans la figure,

Les valeurs d'action, q * (a) , une = 1,…., 10 ont été sélectionnés selon une distribution normale avec moyenne 0 et variance 1. Ensuite, lorsqu'une méthode d'apprentissage appliquée à ce problème a sélectionné l'action, Àau pas de temps t, la récompense réelle, Rt , a été sélectionné parmi une distribution normale avec q * (At) et la variance 1. Ces distributions sont indiquées en gris sur la figure. Nous appelons cette suite de tâches de test le banc d'essai à 10 bras.

Pour toute méthode d'apprentissage, nous pouvons mesurer ses performances et son comportement à mesure que l'expérience s'améliore avec l'expérience de plus de 1000 pas de temps lorsqu'elle est appliquée à l'un des problèmes de bandit. Cela constitue une course. En répétant ceci pour 2000 exécutions indépendantes, chacune avec un problème de bandit différent, nous obtenons des mesures du comportement moyen de l’algorithme d’apprentissage.

Ce graphique compare une méthode gourmande à deux méthodes ε-gourmandes (ε = 0.01 et ε = 0.1) sur le banc d'essai à 10 bras. Toute la méthode a formé leurs estimations de valeur d’action en utilisant la technique de la moyenne d’échantillon mentionnée ci-dessus. La méthode gourmande s'est améliorée légèrement plus rapidement que les autres méthodes au début, mais s'est ensuite stabilisée à un niveau inférieur. La méthode gourmande a bien moins bien fonctionné à long terme, car elle était souvent bloquée dans ses actions sous-optimales.

Les méthodes ε-cupides ont finalement mieux fonctionné, car elles ont continué à explorer et à améliorer leurs chances de reconnaître la meilleure action. La méthode ε = 0.1 a exploré plus, et a généralement trouvé l'action optimale plus tôt, mais elle n'a jamais sélectionné cette action plus de 91% du temps. La méthode ε = 0.01 s’est améliorée plus lentement, mais aurait finalement donné de meilleurs résultats que la méthode ε = 0.1.

Il est également possible de réduire ε au fil du temps et de choisir un calendrier pour réduire la valeur de ε afin de tirer le meilleur parti des deux mondes. E-gourmand en décomposition a un regret total asymptotique logarithmique.

L'avantage de la méthode ε-cupide par rapport à la méthode gloutonne dépend de la tâche. Supposons que la variance de récompense ait été plus grande, disons 10 au lieu de 1. Avec des récompenses plus bruyantes, il faut plus d'exploration pour trouver l'action optimale et les méthodes ε-gourmandes devraient être encore meilleures que celles obtenues par la méthode gourmande. D'autre part, si les variances de récompense étaient nulles, la méthode gourmande saurait la valeur réelle de chaque action après l'avoir essayée une fois.

Supposons que la tâche du bandit ne soit pas stationnaire, c'est-à-dire que les valeurs vraies des actions changent avec le temps. Dans ce cas, l'exploration est nécessaire même dans le cas déterministe pour s'assurer que l'une des actions non-gloutonnes n'a pas changé pour devenir meilleure que celle gloutonne. La non-stationnarité est le cas le plus couramment rencontré dans l'apprentissage par renforcement.

Même si la tâche sous-jacente est fixe et déterministe, l'agent est confronté à un ensemble de tâches de décision semblables à des bandits, chacune d'entre elles évoluant au fil du temps, à mesure que l'apprentissage progresse et que la politique de prise de décision de l'agent change.

Une limite inférieure

La limite inférieure du regret, c’est-à-dire qu’aucun algorithme ne peut éventuellement faire mieux qu’une certaine limite inférieure. Ce qui veut dire qu’il ya une limite inférieure sur la façon dont nous pouvons faire avec regret. nous voulons abaisser de plus en plus nos algorithmes vers cette limite inférieure. Cette limite inférieure est logarithmique dans le nombre de pas de temps, tout comme l'algorithme ε-glouton en décomposition.

Dans le problème des bandits, la performance de tout algorithme est déterminée par la similarité entre le bras optimal et les autres bras. Un problème facile de bandit est celui où vous avez un bras visiblement bon et un bras visiblement mauvais. Vous essayez juste ce bras une fois, et vous donne un bon numéro, vous essayez l’autre une fois et il vous donne un mauvais numéro, puis vous avez terminé.

Un problème de bandit dur est quelque chose où le 1er bras par exemple est le meilleur, nous ne le savons pas encore. Nous essayons chaque bras disponible. Le 1er bras est parfois meilleur que les autres, et parfois c’est mauvais. Il y a beaucoup de bruit dessus, et il est très difficile de les lever de l’ambiguïté. Nous commettons beaucoup d’erreurs et il faut beaucoup de temps pour comprendre que le 1er bras est bien meilleur que le reste. C'est le cas de la non-stationnarité, comme nous l'avons mentionné précédemment.

Les problèmes difficiles ont donc des bras similaires, mais avec des moyens différents. Nous pouvons décrire cela formellement en termes d’écart entre eux et de la similitude de leurs distributions en utilisant la méthode de la divergence de KL, qui mesure la différence d’une distribution de probabilité par rapport à une autre distribution de probabilité de référence.

Formellement, c'est un théorème qui dit,

Théorème (Lai et Robbins): le regret total asymptotique est au moins logarithmique en nombre de pas.
1543909966 955 Exploration vs Exploitation dans le réglage Bandit multi armes - Exploration vs Exploitation dans le réglage Bandit multi-armes.

Ce qui signifie que nous ne pouvons jamais faire mieux que cette limite inférieure en termes de pas de temps. Il nous dit que plus les bras sont différents, plus les regrets sont nombreux.

Optimisme face à l'incertitude

Imaginez qu'il y a 3 bras différents. Il existe une distribution de probabilité sur la valeur d’action pour chaque bras. Peut-être avons-nous essayé le vert plusieurs fois, alors nous avons une assez bonne idée de la signification de cette action. Peut-être avons-nous essayé le bleu une ou deux fois, mais nous ne sommes pas tout à fait sûrs de la moyenne et le rouge est entre les deux. La question est: quel bras devrions-nous choisir ensuite?

L’optimisme face au principe d’incertitude dit, ne prenez pas celui que vous considérez actuellement comme le meilleur. Prenez l’action qui a le plus de potentiel pour être la meilleure. L'action bleue a le plus de potentiel pour avoir une moyenne plus élevée. Nous devrions donc essayer et limiter la distribution. Au fur et à mesure que nous réduisons les distributions, nous commençons à avoir de plus en plus confiance en la meilleure action à prendre jusqu'à ce que nous choisissions celle qui a la moyenne maximale.

C’est donc un moyen de réduire notre incertitude et d’essayer en même temps des choses qui ont le plus de potentiel pour réussir.

Limite de confiance supérieure (UCB)

L'exploration est nécessaire car il existe toujours une incertitude quant à l'exactitude des estimations de la valeur d'action. Les actions gourmandes sont celles qui regardent actuellement, mais certaines des autres actions peuvent en réalité être meilleures. La sélection d’actions gloutonnes oblige à juger les actions non gloutonnes, mais sans distinction, sans préférence pour celles qui sont presque avides ou particulièrement incertaines.

Il serait préférable de choisir parmi les actions non-gourmandes en fonction de leur potentiel d’optimalité, en tenant compte à la fois de la façon dont leurs estimations doivent être maximales et des incertitudes de ces estimations.

On ne va pas juste essayer d’estimer la moyenne d’une action, on va estimer une confiance supérieure Ut (a) de ce que nous pensons que la moyenne pourrait être. Pensez-y comme la queue de la distribution ci-dessus. Nous allons estimer une addition, un bonus qui caractérise la taille de la distribution.

Vous pouvez penser à Ut (a)comme une probabilité élevée haute confiance sur ce que la valeur d'une action pourrait être. Ensuite, nous allons choisir l’action avec la valeur de confiance la plus élevée.

Cela dépend de Nt (a) c'est-à-dire le nombre de fois qu'une action a été sélectionnée. Petit Nt (a) signifie le plus grand Ut (a)sera (la valeur estimée est incertaine). Le plus grand Nt (a) , le plus petit Ut (a)sera (la valeur estimée est exacte). Nous allons ajouter de moins en moins de bonus aux actions que nous avons davantage essayées, car nous sommes de plus en plus confiants quant à la signification de cette action. Finalement, nous finissons par utiliser la moyenne.

1543909966 294 Exploration vs Exploitation dans le réglage Bandit multi armes - Exploration vs Exploitation dans le réglage Bandit multi-armes.

Nous sélectionnons les actions maximisant UCB. Ici, la maximisation est au-dessus de la valeur de l'action ajoutée à la confiance supérieure de cette action. Cela nous aide à examiner systématiquement l’espace d’action et à déterminer laquelle de ces actions nous donne les meilleurs résultats.

Alors, comment calculer une limite de confiance supérieure d'une action? Ici, nous ne faisons aucune hypothèse sur la distribution des actions.

Théorème (Inégalité de Hoeffding):

Fondamentalement, si nous avons des variables aléatoires, nous les échantillonnons entre [0, 1], nous continuons à échantillonner ces valeurs X encore et encore, nous prenons une moyenne empirique de tous nos échantillons, quelle est la probabilité que nous nous trompions dans notre estimation de cette moyenne empirique d’au moins vous .

Ceci est vrai pour toute distribution lorsque les récompenses sont liées entre [0,1]. Nous allons appliquer L’inégalité de Hoeffding aux récompenses du bandit conditionnées par la sélection de l'action une,

1543909966 918 Exploration vs Exploitation dans le réglage Bandit multi armes - Exploration vs Exploitation dans le réglage Bandit multi-armes.

C’est dire, quelle est la probabilité que nous nous trompions dans notre estimation de Qpar plus que Ut (a) . Nous allons utiliser cela pour résoudre Ut (a) valeurs et de les régler sur le montant approprié, afin de garantir que cette probabilité est, par exemple, dans les 95%.

Nous allons résoudre pour Ut (a),

et cela nous donne cette valeur de confiance supérieure. Ce qui est bien, c’est que nous n’avons pas besoin de savoir quoi que ce soit à propos des gabs, nous n’avons pas besoin de savoir quoi que ce soit à propos des récompenses, sauf qu’ils sont liés. Ce terme a toutes les propriétés que nous voulons. Le décompte est dans le dénominateur, c’est-à-dire que, à mesure que nous choisissons des choses, ce terme de bonus va être réduit à zéro, et pour les actions que nous n'avons pas souvent essayées, nous aurons un très gros terme de bonus.

Maintenant, nous voulons choisir un calendrier. Nous voulons garantir que nous choisissons l'action optimale à mesure que nous poursuivons, nous voulons que ce regret asymptotique soit logarithmique par pas de temps. Nous ajoutons donc une planification à nos valeurs P à mesure que nous observons plus de récompenses, par exemple. nous pourrions définir P pour être égal à télevé à la puissance de -4. Utilisation de la règle de puissance logarithmique, «Le logarithme de l'exposant de x élevé à la puissance de y est y fois le logarithme de x» ,

1543909966 358 Exploration vs Exploitation dans le réglage Bandit multi armes - Exploration vs Exploitation dans le réglage Bandit multi-armes.

on se retrouve avec cette équation,

Ainsi, nous nous assurons de choisir l’action optimale comme t →.

UCB1

Cela mène à UCB1algorithme, qui est un algorithme assez efficace dans le k réglage de bandit armé.

Chaque pas que nous estimons Q valeurs en utilisant la méthode échantillon-moyenne, puis nous ajoutons le terme bonus qui ne dépend que du nombre de pas de temps tet le nombre de fois que nous avons choisi cette action, Nt (a).

Cela ressemble beaucoup à la limite inférieure, sauf que nous n’avons pas le terme KL, car il n’ya pas d’hypothèse sur la distribution de probabilité.

Résumé
  • Gourmand avec une initialisation optimiste: Nous initialisons les valeurs des actions sur une valeur hautement optimiste et supposons que tout va bien jusqu'à preuve du contraire. En fin de compte, nous supprimons chaque valeur d'action à sa valeur réaliste.
  • Exploration Aléatoire: l'algorithme ε-greedy fait bien, si nous l'accordons juste. La difficulté est que si nous nous trompons, il pourrait être difficile d'arriver à l'action optimale à la fin.
  • Optimisme face à l'incertitude: Nous estimons à quel point nous ne connaissons pas la valeur d’une action et nous l’utilisons pour nous guider vers les actions les plus prometteuses. Ce n'est pas une exploration sûre. Dans l’industrie, les chercheurs et les ingénieurs n’utilisent pas cette approche car elle n’est pas sûre.
  • UCB: Souvent, cet algorithme donne de bons résultats qu’en glouton, mais il est plus difficile de s’étendre au-delà des bandits au cadre plus général de l’apprentissage par renforcement. Lorsque vous utilisez l'approximation de fonctions, la sélection d'action UCB n'est généralement pas pratique. UCB, qui n’a aucune connaissance du problème, s’exécute systématiquement très bien.

Assurez-vous de laisser un réponse exprimer vos pensées, et donner à mon blog un suivre si vous avez apprécié ce post et que vous voulez en voir plus!

Épisodes précédents
Références

Introduction à l’apprentissage par renforcement de Richard Sutton

Show More

SupportIvy

SupportIvy.com : Un lieu pour partager le savoir et mieux comprendre le monde. Meilleure plate-forme de support gratuit pour vous, Documentation &Tutoriels par les experts.

Related Articles

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *

Close
Close