Temporal difference learning

Un article de Wikipédia, l'encyclopédie libre.
Sauter à la navigation Sauter à la recherche


Le Temporal Difference (TD) learning est une classe d'algorithmes d'apprentissage par renforcement sans modèle. Ces méthodes échantillonnent l'environnement de manière aléatoire, à la manière des méthodes de Monte Carlo et mettent à jour leur modèle en se basant sur les estimations actuelles, comme les méthodes de programmation dynamique[1].

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[2]. C'est une forme de bootstrap qui peut être illustrée par l'exemple suivant :

« Imaginez que chaque jour de la semaine, vous vouliez prédire si il va pleuvoir samedi. L'approche conventionnelle serait de conserver ces résultats et de les comparer, le samedi, au temps qu'il fait vraiment afin de mettre à jour le modèle. Une approche TD serait de comparer chaque prédiction avec celle faite le jour suivant. Si la prédiction faite le lundi était de 50% de chance de pluie et celle de mardi de 75%, les méthodes TD vont augmenter les prédictions pour des cas similaires à celui de lundi[2]. »

Les méthodes TD ont un lien avec les modèles TD dans l'apprentissage animal[3],[4],[5],[6],[7].

Formulation mathématique[modifier | modifier le code]

La méthode tabulaire TD(0), l'une des méthodes TD les plus simples, estime la fonction de valeur d'un processus de décision markovien (PDM) selon une politique . Soit la fonction de valeur du PDM ayant les états , la récompense et l'amortissement selon la politique  :

donne l'espérance lorsque l'agent suit la politique . La fonction de valeur satisfait l'équation de Hamilton-Jacobi-Bellman :

donc est une estimation non-biaisée de . Cette observation motive l'algorithme suivant pour estimer .

L'algorithme commence par initialiser un tableau arbitrairement, avec une valeur pour chaque état du PDM. Un taux d'apprentissage positif est choisi.

On répète ensuite : évaluer la politique , obtenir une récompense 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.

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 la fonction d'erreur des algorithmes TD[3],[4],[5],[6],[7]. La fonction d'erreur 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 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 »(ArchiveWikiwixArchive.isGoogleQue faire ?), )
  3. 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)
  4. 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)
  5. 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)
  6. 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)
  7. 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)
  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 8 février 2010)