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. Les méthodes TD ont un lien avec les modèles TD dans l'apprentissage animal.

Principe vignette|151x151px 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 (Une version mise à jour est disponible sur la page de publication de Richard Sutton's ). C'est une forme de bootstrap qui peut être illustrée par l'exemple suivant provenant d'un article de Richard Sutton :

Diagramme ci-contre : 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).

Formulation mathématique

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 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 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 :

évaluer la politique en fonction du tableau courant obtenir une récompense et mettre à jour la fonction pour l'ancien état en utilisant la règle :

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

Algorithmes Voici une liste d'algorithmes TD :

Q-learning Algorithme SARSA

Exemples d'applications

L'algorithme TD-Lambda, initialement développé par Richard S. Sutton 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.

Algorithmes TD et neurosciences

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. 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 Q-learning Modèle Rescorla-Wagner

Références

Catégorie:Algorithme Catégorie:Apprentissage automatique