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 animalModèle:,Modèle:,Modèle:,Modèle:,.

Principe

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 :

Modèle:Citation blocDiagramme 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 $\pi$. 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 $V^{\pi }$ la fonction de valeur du PDM selon la politique $\pi$. En tout état s, $V^{\pi }(s)$ est l'espérance des sommes récompenses obtenues avec un amortissement $\gamma$, lorsque l'agent suit la politique $\pi$ depuis l'état s. Formellement, en notant $E_{\pi }\{...\}$ l'espérance lorsque l'agent suit la politique $\pi$, la suite des états $s_0,s_1,s_2,\dots$, la suite des récompenses $r_0,r_1,r_2,\dots$ et l'amortissement $\gamma$ , on a

$V^{\pi }(s)=E_{\pi }\left\{\sum _{t=0}^{\mathrm{\infty }}{\gamma }^t{r}_t\right|s_0=s\}$.

La fonction de valeur $V^{\pi }$ satisfait l'équation de Hamilton-Jacobi-Bellman :

$V^{\pi }(s)=E_{\pi }\{r_0+\gamma V^{\pi }(s_1)|s_0=s\},$

donc $r_0+\gamma V^{\pi }(s_1)$ est une estimation non-biaisée de $V^{\pi }(s)$. Cette observation motive l'algorithme TD(0) pour estimer $V^{\pi }$.

Description de l'algorithme

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

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

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

$V(s)\leftarrow V(s)+\alpha (\stackrel{\text{Objectif TD}}{\overbrace{r+\gamma V(s^{\prime })}}-V(s))$

où $s$ et $s^{\prime }$ sont les ancien et nouvel états respectivement. La valeur $r+\gamma V(s^{\prime })$ 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 TDModèle:,Modèle:,Modèle:,Modèle:,. 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