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^[1]. Les méthodes TD ont un lien avec les modèles TD dans l'apprentissage animal^{[2],[3],[4],[5],[6]}.

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 disposez 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]. »

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).

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 π {\displaystyle \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.

Soit V π {\displaystyle V^{\pi }} la fonction de valeur du PDM selon la politique π {\displaystyle \pi } . En tout état s, V π ( s ) {\displaystyle V^{\pi }(s)} est l'espérance des sommes récompenses obtenues avec un amortissement γ {\displaystyle \gamma } , lorsque l'agent suit la politique π {\displaystyle \pi } depuis l'état s. Formellement, en notant E π { . . . } {\displaystyle E_{\pi }\{...\}} l'espérance lorsque l'agent suit la politique π {\displaystyle \pi } , la suite des états s 0 , s 1 , s 2 , … {\displaystyle s_{0},s_{1},s_{2},\dots } , la suite des récompenses r 0 , r 1 , r 2 , … {\displaystyle r_{0},r_{1},r_{2},\dots } et l'amortissement γ {\displaystyle \gamma } , on a

V π ( s ) = E π { ∑ t = 0 ∞ γ t r t | s 0 = s } {\displaystyle V^{\pi }(s)=E_{\pi }\left\{\sum _{t=0}^{\infty }\gamma ^{t}r_{t}{\Bigg |}s_{0}=s\right\}} .

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

V π ( s ) = E π { r 0 + γ V π ( s 1 ) | s 0 = s } , {\displaystyle V^{\pi }(s)=E_{\pi }\{r_{0}+\gamma V^{\pi }(s_{1})|s_{0}=s\},}

donc r 0 + γ V π ( s 1 ) {\displaystyle r_{0}+\gamma V^{\pi }(s_{1})} est une estimation non-biaisée de V π ( s ) {\displaystyle V^{\pi }(s)} . Cette observation motive l'algorithme TD(0) pour estimer V π {\displaystyle V^{\pi }} .

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

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

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

V ( s ) ← V ( s ) + α ( r + γ V ( s ′ ) ⏞ Objectif TD − V ( s ) ) {\displaystyle V(s)\leftarrow V(s)+\alpha (\overbrace {r+\gamma V(s')} ^{\text{Objectif TD}}-V(s))}

où s {\displaystyle s} et s ′ {\displaystyle s'} sont les ancien et nouvel états respectivement. La valeur r + γ V ( s ′ ) {\displaystyle r+\gamma V(s')} est appelée objectif TD.

Voici une liste d'algorithmes TD :

• Q-learning
• Algorithme SARSA

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].

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.

• Q-learning
• Modèle Rescorla-Wagner

• Portail de l’intelligence artificielle