Temporal difference learning

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. vignette|151x151px|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. C'est une forme de bootstrap qui peut être illustrée par l'exemple suivant provenant d'un article de Richard Sutton : 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. 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 . L'algorithme commence par initialiser un tableau arbitrairement, c'est-à-dire est une valeur arbitraire pour chaque état du PDM.