Apprentissage par renforcement - Définition

Algorithme

On donne ici une version algorithmique basique de l'apprentissage par renforcement, particulièrement du TD-learning. Cette version a pour but de permettre au lecteur intéressé de faire une rapide implémentation informatique de l'algorithme afin d'en mieux comprendre le fonctionnement itératif. On se place ici dans le cas le plus simple où on ne cherche pas à améliorer le comportement (ou politique) de l'agent, mais on cherche à évaluer une politique donnée lorsqu'elle est mise en œuvre par un agent dans un environnement donné.

On initialise V(s) aléatoirement, qui est la valeur que l'agent attribuera à chaque état s.

On initialise la politique π à évaluer.

On répète (pour chaque épisode) :

On initialise s

On répète (à chaque pas de temps de l'épisode) :

a ← action donnée par π pour s

L'agent effectue l'action a; on observe la récompense r et l'état suivant s'

V(s) ← V(s) + α [r + γV(s') - V(s)]

s ← s'

Jusqu'à ce que s soit terminal

Pour plus de détails concernant l'implémentation de cet algorithme, ou concernant la version algorithmique du Q-learning, se référer au livre de Sutton et Barto publié en 1998, dont la totalité du contenu est disponible librement sur Internet (voir le lien externe à la fin de cet article).

Formalisme

Formellement, la base du modèle d'apprentissage par renforcement consiste en:

1. un ensemble d'états S de l'agent dans l'environnement;
2. un ensemble d'actions A que l'agent peut effectuer;
3. un ensemble de valeurs scalaires "récompenses" R que l'agent peut obtenir.

À chaque pas de temps t de l'algorithme, l'agent perçoit son état et l'ensemble des actions possibles A(s_t). Il choisit une action et reçoit de l'environnement un nouvel état s_{t + 1} et une récompense r_{t + 1} (qui est nulle la plupart du temps et vaut classiquement 1 dans certains états clefs de l'environnement). Fondé sur ces interactions, l'algorithme d'apprentissage par renforcement doit permettre à l'agent de développer une politique qui lui permette de maximiser la quantité de récompenses. Cette dernière s'écrit dans le cas des processus de décision markoviens (MDP) qui ont un état terminal, où R = Σ_t γ_t r_t pour les MDPs sans état terminal (où γ est un facteur de dévaluation compris entre 0 et 1 et permettant, selon sa valeur, de prendre en compte les récompenses plus ou moins loin dans le futur pour le choix des actions de l'agent).

Ainsi, la méthode de l'apprentissage par renforcement est particulièrement adapté aux problèmes nécessitant un compromis entre la quête de récompenses à court terme et celle de récompenses à long terme. Cette méthode a été appliquée avec succès à des problèmes variés, tels que le contrôle robotique, le pendule inversé, la planification de tâches, les télécommunications, le backgammon et les échecs.