Temporal difference learning

Un article de Wikipédia, l'encyclopédie libre.

Le Temporal Difference (TD) learning est une classe d'algorithmes d'apprentissage par renforcement sans modèle. Ces algorithmes échantillonnent l'environnement de manière aléatoire à la manière des méthodes de Monte Carlo. Ils mettent à jour la politique (i.e. les actions à prendre dans chaque état) en se basant sur les estimations actuelles, comme les méthodes de programmation dynamique[1]. Les méthodes TD ont un lien avec les modèles TD dans l'apprentissage animal[2],[3],[4],[5],[6].

Principe[modifier | modifier le code]

Diagramme backup. Les algorithmes TD choisissent une action (le point), puis utilisent l'estimation de la valeur de l'état successeur (le cercle du bas) pour mettre à jour la valeur de l'état courant (le cercle du haut).

Alors que les méthodes de Monte Carlo ajustent leur estimations seulement lorsque l'issue finale est connue, les méthodes TD ajustent leurs estimations en se basant sur leurs prédictions[7]. C'est une forme de bootstrap qui peut être illustrée par l'exemple suivant provenant d'un article de Richard Sutton :

« Imaginez que vous souhaitiez prédire le temps qu'il va faire le samedi et que vous disposer d'un modèle de prédiction qui tient compte du temps qu'il a fait chaque jour de la semaine. L'approche conventionnelle serait de conserver ces résultats et d'attendre le samedi afin de mettre à jour le modèle. Cependant quand vous êtes vendredi vous pourriez avoir une bonne idée du temps qu'il fera samedi et ainsi modifier le modèle avant l'arrivée du samedi.[7]. »

Formulation mathématique[modifier | modifier le code]

Donnons la formulation mathématique de la méthode tabulaire TD(0), l'une des méthodes TD les plus simples, qui estime la fonction de valeur d'un processus de décision markovien (PDM) selon une politique . Le PDM n'est pas utilisé par l'algorithme, notamment l'algorithme n'a pas accès aux probabilités ; c'est pourquoi on parle d'apprentissage par renforcement sans modèle.

Notations[modifier | modifier le code]

Soit la fonction de valeur du PDM selon la politique . En tout état s, est l'espérance des sommes récompenses obtenues avec un amortissement , lorsque l'agent suit la politique depuis l'état s. Formellement, en notant l'espérance lorsque l'agent suit la politique , la suite des états , la suite des récompenses et l'amortissement , on a

.

La fonction de valeur satisfait l'équation de Hamilton-Jacobi-Bellman :

donc est une estimation non-biaisée de . Cette observation motive l'algorithme TD(0) pour estimer .

Description de l'algorithme[modifier | modifier le code]

L'algorithme commence par initialiser un tableau arbitrairement, c'est-à-dire est une valeur arbitraire pour chaque état du PDM. On choisit un taux d'apprentissage positif .

On répète ensuite les opérations suivantes :

  1. évaluer la politique en fonction du tableau courant
  2. obtenir une récompense
  3. et mettre à jour la fonction pour l'ancien état en utilisant la règle[8] :

et sont les ancien et nouvel états respectivement. La valeur est appelée objectif TD.

Algorithmes[modifier | modifier le code]

Voici une liste d'algorithmes TD :

Exemples d'applications[modifier | modifier le code]

L'algorithme TD-Lambda, initialement développé par Richard S. Sutton[1] a été appliqué par Gerald Tesauro pour créer TD-Gammon, un programme qui a appris à jouer au backgammon à un niveau de joueur humain expert[9].

Algorithmes TD et neurosciences[modifier | modifier le code]

Les algorithmes TD ont aussi reçu de l'attention en neurosciences. Des chercheurs ont souligné une similitude entre le taux de dopamine et le signal d'erreur de prédiction des algorithmes TD[2],[3],[4],[5],[6]. Le signal d'erreur de prédiction fournit la différence entre la récompense estimée à une itération et la récompense réellement reçue.

Voir aussi[modifier | modifier le code]

Références[modifier | modifier le code]

  1. a et b Richard Sutton et Andrew Barto, Reinforcement Learning, MIT Press, (ISBN 978-0-585-02445-5, lire en ligne[archive du ])
  2. a et b Schultz, W, Dayan, P & Montague, PR., « A neural substrate of prediction and reward », Science, vol. 275, no 5306,‎ , p. 1593–1599 (PMID 9054347, DOI 10.1126/science.275.5306.1593, CiteSeerx 10.1.1.133.6176)
  3. a et b P. R. Montague, P. Dayan et T. J. Sejnowski, « A framework for mesencephalic dopamine systems based on predictive Hebbian learning », The Journal of Neuroscience, vol. 16, no 5,‎ , p. 1936–1947 (ISSN 0270-6474, PMID 8774460, DOI 10.1523/JNEUROSCI.16-05-01936.1996)
  4. a et b P.R. Montague, P. Dayan, S.J. Nowlan, A. Pouget et T.J. Sejnowski, « Using aperiodic reinforcement for directed self-organization », Advances in Neural Information Processing Systems, vol. 5,‎ , p. 969–976 (lire en ligne)
  5. a et b P. R. Montague et T. J. Sejnowski, « The predictive brain: temporal coincidence and temporal order in synaptic learning mechanisms », Learning & Memory, vol. 1, no 1,‎ , p. 1–33 (ISSN 1072-0502, PMID 10467583)
  6. a et b T.J. Sejnowski, P. Dayan et P.R. Montague, « Predictive hebbian learning », Proceedings of Eighth ACM Conference on Computational Learning Theory,‎ , p. 15–18 (DOI 10.1145/230000/225300/p15-sejnowski, lire en ligne)
  7. a et b Richard Sutton, « Learning to predict by the methods of temporal differences », Machine Learning, vol. 3, no 1,‎ , p. 9–44 (DOI 10.1007/BF00115009) (Une version mise à jour est disponible sur la page de publication de Richard Sutton's « https://web.archive.org/web/20170330002227/http://incompleteideas.net/sutton/publications.html »(Archive.orgWikiwixArchive.isGoogleQue faire ?), )
  8. Reinforcement learning : An introduction (lire en ligne[archive du ]), p. 130
  9. Gerald Tesauro, « Temporal Difference Learning and TD-Gammon », Communications of the ACM, vol. 38, no 3,‎ , p. 58–68 (DOI 10.1145/203330.203343, lire en ligne, consulté le )