Petit guide du machine learning – partie 4 : l’apprentissage par renforcement

Pour rappel, au sein de l’apprentissage supervisé, le data scientist fournit à un algorithme des exemples de la stratégie à adopter (par exemple, l’objet A correspond à la catégorie 1) puis le modèle de machine learning apprend à relier ses observations aux labels donnés par l’expert. Il faut donc au préalable disposer d’un ensemble de données labellisées.

En apprentissage par renforcement, il n’est pas nécessaire de posséder un historique de données pour laisser l’algorithme prendre des décisions par lui-même. En effet, seule la connaissance du contexte actuel est nécessaire. C’est en interagissant avec ce dernier que les décisions de l’algorithme deviendront de plus en plus pertinentes, à l’image d’un être humain en phase d’apprentissage !

Apprentissage par renforcement : lexique pour les néophytes

Commençons par un peu de vocabulaire, nécessaire à la bonne compréhension de l’apprentissage par renforcement. Dans cet article, nous parlerons d’agent, d’actions, d’états, de récompenses, de transitions, de politique, d’environnements, et enfin de regret. Nous prendrons l’exemple du célèbre jeu Super Mario pour illustrer le tout (voir schéma ci-dessous).

• L’agent est celui qui prend des décisions, qui agit. Prenons le personnage de Mario pour notre exemple.
• Ses décisions sont appelées actions, elles sont définies à l’avance, par exemple aller à droite, à gauche, sauter, se baisser…
• Les états sont ce qui définit le contexte dans lequel évolue l’agent à un instant t, par exemple il y a un trou en face, un bloc en hauteur, ou encore un monstre sur ma route.
• A chaque action effectuée, l’agent impacte le prochain état en modifiant l’environnement. L’état suivant ne sera ainsi pas le même si l’agent va par exemple à droite ou à gauche. Cependant, l’état suivant n’est pas toujours prévisible : un monstre peut soudainement apparaître sur la route de Mario par exemple ! On parle donc de probabilité de transition entre les états.
• La politique est la stratégie adoptée par l’agent face à l’environnement, pour opérer ses choix d’actions. Mathématiquement parlant, il s’agit d’une fonction qui associe l’action à effectuer face à un état donné.
• En choisissant une action dans un état donné, l’agent va recevoir une récompense. Il s’agit d’un objectif chiffré que l’agent va chercher à optimiser au fil du temps. Dans notre exemple il s’agira de savoir si Mario va rester en vie, mourir ou gagner une pièce (attention à la connotation du terme employé, la récompense peut donc être une conséquence positive ou négative !).
• Tous ces éléments définissent l’environnement dans lequel l’agent évolue. Au début de l’expérience, l’agent connaît uniquement les états existants et les actions réalisables dans l’environnement. En revanche, il ne connaît ni les récompenses, ni les transitions, et ne sait donc pas encore comment atteindre son objectif. Il devra donc explorer, c’est-à-dire faire l’expérience de différentes actions dans chaque état, et ce plusieurs fois car les récompenses obtenues peuvent varier sensiblement d’une fois à l’autre. On parle ici d’environnement probabiliste. Attention : cette exploration ne doit pas s’effectuer au hasard, au risque de voir le temps de compréhension de l’environnement s’allonger !
• Enfin, pour mesurer la performance d’un algorithme d’apprentissage par renforcement, on mesure le regret : il s’agit de la différence entre la récompense moyenne obtenue par l’agent, et la récompense moyenne qu’il aurait obtenue s’il avait appliqué la politique optimale depuis le début. Plus cet écart est faible, moins l’agent a mis de temps à apprendre et plus l’algorithme est performant.

Apprentissage par renforcement : à vous de jouer !

L’apprentissage par renforcement est une forme de machine learning très utilisée pour faire fonctionner les intelligences artificielles des jeux. L’application dont on a le plus entendu parler est probablement la solution AlphaGo Zero, développée par Google DeepMind, capable de battre les meilleurs joueurs du monde de Go. Les premières versions de l’algorithme essayaient de reproduire le comportement humain en analysant des parties réellement jouées par des amateurs et professionnels. Il s’agissait donc d’apprentissage supervisé. Dans sa solution finale, DeepMind a ensuite utilisé uniquement de l’apprentissage par renforcement et entraîné le modèle à jouer… contre lui-même !

Comme vu dans notre exemple, l’apprentissage par renforcement a également été utilisé pour apprendre à jouer à Super Mario. Pour cela, il y a d’abord eu un travail humain à effectuer, pour définir les états. Il faut donc bien connaître le jeu pour être capable de résumer un état, puis de le restituer à l’ordinateur.

On peut par exemple découper l’environnement visible autour de Mario par tranches de pixels (par exemple tous les 10 pixels) et noter ce qu’on observe dans chaque carré (un monstre, une pièce, un trou, etc). Il faut ensuite définir les actions, pour faire simple disons droite, gauche, bas, haut. Et enfin il faut donner une valeur aux récompenses, par exemple : -1000 si l’action tue Mario, 0 si rien ne se passe, +10 si Mario tue un monstre, +100 pour chaque pièce ramassée par Mario et +10000 si Mario gagne le niveau. Il ne reste alors plus qu’à laisser Mario jouer et apprendre par lui-même. Et voilà !

Et le marketing dans tout ça ?

En marketing, les applications de l’apprentissage par renforcement sont infinies… mais le modèle reste peu utilisé à date, car assez complexe à mettre en oeuvre.

On pourrait par exemple utiliser l’apprentissage par renforcement sur un site e-commerce pour trouver le meilleur prix pour chaque produit, dans le but d’optimiser les ventes. Dans ce cas : l’état du modèle correspondrait au jour de l’année, associé aux ventes passées et au stock de produits disponibles ; les actions consisteraient à augmenter ou à baisser les prix ; le nombre de ventes seraient les récompenses. En faisant varier les prix, on impacterait le nombre de ventes (les récompenses) ce qui ferait évoluer notre stock, c’est-à-dire l’état dans lequel on se trouvera le lendemain. Ce nouvel état serait donc incertain au moment où l’on fait les choix de prix, puisqu’on ne connaîtrait pas le nombre de ventes exactes que l’on va réaliser (on parle d’état probabiliste).

En e-commerce, il est également possible d’optimiser l’ordonnancement des produits sur une page pour améliorer les ventes. En effet, au sein d’une liste de produits, la performance d’un produit ne reflète pas forcément son attractivité réelle, puisqu’elle est biaisée par son placement au sein de la page. De facto, les produits placés en haut de page sont plus susceptibles d’être vus, donc d’être achetés. Un algorithme pourrait permettre de faire la différence entre la performance réelle du produit, et l’impact de sa visibilité. L’apprentissage par renforcement permet, en testant plusieurs positions (les états) de trouver l’ordre optimal. Et bien sûr, cet ordre optimal évolue constamment étant donné que les produits (et leur disponibilité) changent tous les jours !

Apprentissage par renforcement et recommandation : notre algorithme présenté à la conférence NeurIPS

fifty-five, Criteo et Facebook ont récemment créé et publié un algorithme de renforcement à l’occasion de la conférence NeurIPS : cet algorithme permet d’étudier l’évolution de la performance d’une activation marketing (par exemple d’un algorithme de recommandation) en fonction du nombre de fois où l’utilisateur a été exposé à cette activation par le passé. Prenons deux exemples en illustration.

Premier exemple : supposons qu’une plateforme de VoD cherche à savoir quel genre de film recommander à un utilisateur (Action, Romance, Comédie, Thriller…) à un instant t. Son envie de voir un film du genre Action ne sera pas la même s’il vient de voir 10 films d’action au cours du mois passé ou 1 seul, même si son goût pour les films d’action reste inchangé. L’algorithme de renforcement proposé par la plateforme doit donc être capable d’anticiper la lassitude de l’utilisateur, pour lui proposer d’autres genres de film, en fonction de ses interactions passées. Cela permet de diversifier les recommandations proposées à l’utilisateur.

Deuxième exemple : sur un site ecommerce, si l’on choisit de mettre le bloc “promotions” à droite, l’utilisateur qui vient régulièrement sur le site s’habituera progressivement à ce placement, jusqu’à ne plus y prêter attention. Pour pallier ce problème, l’algorithme par renforcement peut anticiper cette forme de lassitude en déplaçant le bloc à gauche du site, après une période donnée, pour garder l’attention de l’utilisateur en continu. L’algorithme que nous avons développé permet alors de mesurer cette évolution, afin d’améliorer la connaissance client et d’alterner entre les diverses possibilités pour maximiser l’engagement sur le long terme !

En résumé, il faut garder en tête que chaque action que l’on entreprend influence potentiellement l’environnement futur et peut biaiser les analyses. Avec l’apprentissage par renforcement, on laisse donc l’algorithme apprendre “tout seul”, en interagissant avec son environnement et en observant ce qui s’y passe. Cette forme de machine learning est donc la plus proche de l’apprentissage humain : c’est comme cela qu’apprend un enfant, qui par exemple essaie de mettre des objets de formes géométriques variées dans des trous suivant ces formes. Enfin, contrairement à l’apprentissage supervisé qui cherche simplement la meilleure action à effectuer à un instant précis, l’apprentissage par renforcement cherche à optimiser la performance sur le long terme, ce qui l’oblige parfois à “reculer pour mieux sauter” !

Merci à tous ceux qui ont lu cette série d’articles, le machine learning n’a (presque) plus de secret pour vous !