Temporal difference learning

<h2 id="mathematical-formulation">Mathematical formulation</h2>
The tabular TD(0) method is one of the simplest TD methods. It is a special case of more general stochastic approximation methods. It estimates the <a href="/facts/Reinforcement_learning/NrgPPS0Q">state value function</a> of a finite-state <a href="/facts/Markov_decision_process/cVlWIDrw">Markov decision process</a> (MDP) under a policy 
 
 
 
 π
 
 
 {\displaystyle \pi }
 
. Let 
 
 
 
 
 V
 
 π
 
 
 
 
 {\displaystyle V^{\pi }}
 
 denote the state value function of the MDP with states 
 
 
 
 (
 
 S
 
 t
 
 
 
 )
 
 t
 ∈
 
 N
 
 
 
 
 
 {\displaystyle (S_{t})_{t\in \mathbb {N} }}
 
, rewards 
 
 
 
 (
 
 R
 
 t
 
 
 
 )
 
 t
 ∈
 
 N
 
 
 
 
 
 {\displaystyle (R_{t})_{t\in \mathbb {N} }}
 
 and discount rate<a class="footnote-ref" id="fnref:9" href="#fn:9">9</a> 
 
 
 
 γ
 
 
 {\displaystyle \gamma }
 
 under the policy 
 
 
 
 π
 
 
 {\displaystyle \pi }
 
:<a class="footnote-ref" id="fnref:10" href="#fn:10">10</a>

V
          
            π
          
        
        (
        s
        )
        =
        
          E
          
            a
            ∼
            π
          
        
        
          {
          
            
              ∑
              
                t
                =
                0
              
              
                ∞
              
            
            
              γ
              
                t
              
            
            
              R
              
                t
                +
                1
              
            
            
              
                |
              
            
            
              S
              
                0
              
            
            =
            s
          
          }
        
        .
      
    
    {\displaystyle V^{\pi }(s)=E_{a\sim \pi }\left\{\sum _{t=0}^{\infty }\gamma ^{t}R_{t+1}{\Bigg |}S_{0}=s\right\}.}

We drop the action from the notation for convenience. 
 
 
 
 
 V
 
 π
 
 
 
 
 {\displaystyle V^{\pi }}
 
 satisfies the <a href="/facts/Hamilton-Jacobi-Bellman_equation/6EoqXTgo">Hamilton-Jacobi-Bellman Equation</a>:

V
          
            π
          
        
        (
        s
        )
        =
        
          E
          
            π
          
        
        {
        
          R
          
            1
          
        
        +
        γ
        
          V
          
            π
          
        
        (
        
          S
          
            1
          
        
        )
        
          |
        
        
          S
          
            0
          
        
        =
        s
        }
        ,
      
    
    {\displaystyle V^{\pi }(s)=E_{\pi }\{R_{1}+\gamma V^{\pi }(S_{1})|S_{0}=s\},}

so 
 
 
 
 
 R
 
 1
 
 
 +
 γ
 
 V
 
 π
 
 
 (
 
 S
 
 1
 
 
 )
 
 
 {\displaystyle R_{1}+\gamma V^{\pi }(S_{1})}
 
 is an unbiased estimate for 
 
 
 
 
 V
 
 π
 
 
 (
 s
 )
 
 
 {\displaystyle V^{\pi }(s)}
 
. This observation motivates the following algorithm for estimating 
 
 
 
 
 V
 
 π
 
 
 
 
 {\displaystyle V^{\pi }}
 
.
The algorithm starts by initializing a table 
 
 
 
 V
 (
 s
 )
 
 
 {\displaystyle V(s)}
 
 arbitrarily, with one value for each state of the MDP. A positive <a href="/facts/Learning_rate/EClSgMCR">learning rate</a> 
 
 
 
 α
 
 
 {\displaystyle \alpha }
 
 is chosen.
We then repeatedly evaluate the policy 
 
 
 
 π
 
 
 {\displaystyle \pi }
 
, obtain a reward 
 
 
 
 r
 
 
 {\displaystyle r}
 
 and update the value function for the current state using the rule:<a class="footnote-ref" id="fnref:11" href="#fn:11">11</a>

V
        (
        
          S
          
            t
          
        
        )
        ←
        (
        1
        −
        α
        )
        V
        (
        
          S
          
            t
          
        
        )
        +
        
          
            
              α
              ⏟
            
          
          
            learning rate
          
        
        [
        
          
            
              
                
                  R
                  
                    t
                    +
                    1
                  
                
                +
                γ
                V
                (
                
                  S
                  
                    t
                    +
                    1
                  
                
                )
              
              ⏞
            
          
          
            The TD target
          
        
        ]
      
    
    {\displaystyle V(S_{t})\leftarrow (1-\alpha )V(S_{t})+\underbrace {\alpha } _{\text{learning rate}}[\overbrace {R_{t+1}+\gamma V(S_{t+1})} ^{\text{The TD target}}]}

where 
 
 
 
 
 S
 
 t
 
 
 
 
 {\displaystyle S_{t}}
 
 and 
 
 
 
 
 S
 
 t
 +
 1
 
 
 
 
 {\displaystyle S_{t+1}}
 
 are the current and next states, respectively. The value 
 
 
 
 
 R
 
 t
 +
 1
 
 
 +
 γ
 V
 (
 
 S
 
 t
 +
 1
 
 
 )
 
 
 {\displaystyle R_{t+1}+\gamma V(S_{t+1})}
 
 is known as the TD target, and 
 
 
 
 
 R
 
 t
 +
 1
 
 
 +
 γ
 V
 (
 
 S
 
 t
 +
 1
 
 
 )
 −
 V
 (
 
 S
 
 t
 
 
 )
 
 
 {\displaystyle R_{t+1}+\gamma V(S_{t+1})-V(S_{t})}
 
 is known as the TD error.

<h2 id="td-lambda">TD-Lambda</h2>
TD-Lambda is a learning algorithm invented by <a href="/facts/Richard_S._Sutton/anEmfcaa">Richard S. Sutton</a> based on earlier work on temporal difference learning by <a href="/facts/Arthur_Samuel_(computer_scientist)/hjG9AfX2">Arthur Samuel</a>.<a class="footnote-ref" id="fnref:12" href="#fn:12">12</a> This algorithm was famously applied by Gerald Tesauro to create <a href="/facts/TD-Gammon/Rbt2ohgQ">TD-Gammon</a>, a program that learned to play the game of <a href="/facts/Backgammon/53mgqvtv">backgammon</a> at the level of expert human players.<a class="footnote-ref" id="fnref:13" href="#fn:13">13</a>
The lambda (
 
 
 
 λ
 
 
 {\displaystyle \lambda }
 
) parameter refers to the trace decay parameter, with 
 
 
 
 0
 ⩽
 λ
 ⩽
 1
 
 
 {\displaystyle 0\leqslant \lambda \leqslant 1}
 
. Higher settings lead to longer lasting traces; that is, a larger proportion of credit from a reward can be given to more distant states and actions when 
 
 
 
 λ
 
 
 {\displaystyle \lambda }
 
 is higher, with 
 
 
 
 λ
 =
 1
 
 
 {\displaystyle \lambda =1}
 
 producing parallel learning to Monte Carlo RL algorithms.<a class="footnote-ref" id="fnref:14" href="#fn:14">14</a>

<h2 id="in-neuroscience">In neuroscience</h2>
The TD <a href="/facts/Algorithm/fnl5NmRt">algorithm</a> has also received attention in the field of <a href="/facts/Neuroscience/o5RV8Cas">neuroscience</a>. Researchers discovered that the firing rate of <a href="/facts/Dopamine/5gNy8Xkd">dopamine</a> <a href="/facts/Neurons/G7CyTVdH">neurons</a> in the <a href="/facts/Ventral_tegmental_area/f1rcxshF">ventral tegmental area</a> (VTA) and <a href="/facts/Substantia_nigra/qDpsqpcJ">substantia nigra</a> (SNc) appear to mimic the error function in the algorithm.<a class="footnote-ref" id="fnref:15" href="#fn:15">15</a><a class="footnote-ref" id="fnref:16" href="#fn:16">16</a><a class="footnote-ref" id="fnref:17" href="#fn:17">17</a><a class="footnote-ref" id="fnref:18" href="#fn:18">18</a><a class="footnote-ref" id="fnref:19" href="#fn:19">19</a> The error function reports back the difference between the estimated reward at any given state or time step and the actual reward received. The larger the error function, the larger the difference between the expected and actual reward. When this is paired with a stimulus that accurately reflects a future reward, the error can be used to associate the stimulus with the future <a href="/facts/Reward_system/fotI0rcM">reward</a>.
<a href="/facts/Dopamine/5gNy8Xkd">Dopamine</a> cells appear to behave in a similar manner. In one experiment measurements of dopamine cells were made while training a monkey to associate a stimulus with the reward of juice.<a class="footnote-ref" id="fnref:20" href="#fn:20">20</a> Initially the dopamine cells increased firing rates when the monkey received juice, indicating a difference in expected and actual rewards. Over time this increase in firing back propagated to the earliest reliable stimulus for the reward. Once the monkey was fully trained, there was no increase in firing rate upon presentation of the predicted reward. Subsequently, the firing rate for the dopamine cells decreased below normal activation when the expected reward was not produced. This mimics closely how the error function in TD is used for <a href="/facts/Reinforcement_learning/NrgPPS0Q">reinforcement learning</a>.
The relationship between the model and potential neurological function has produced research attempting to use TD to explain many aspects of behavioral research.<a class="footnote-ref" id="fnref:21" href="#fn:21">21</a><a class="footnote-ref" id="fnref:22" href="#fn:22">22</a> It has also been used to study conditions such as <a href="/facts/Schizophrenia/FMP4lQ57">schizophrenia</a> or the consequences of pharmacological manipulations of dopamine on learning.<a class="footnote-ref" id="fnref:23" href="#fn:23">23</a>

<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/PVLV/2CA7CcmM">PVLV</a></li>
<li><a href="/facts/Q-learning/emySKrgI">Q-learning</a></li>
<li><a href="/facts/Rescorla%E2%80%93Wagner_model/6ne0Wuq5">Rescorla–Wagner model</a></li>
<li><a href="/facts/State%E2%80%93action%E2%80%93reward%E2%80%93state%E2%80%93action/kmv4vSKG">State–action–reward–state–action</a> (SARSA)</li></ul>
<h2 id="notes">Notes</h2>

<h3>Works cited</h3>
<ul><li>Sutton, Richard S.; Barto, Andrew G. (2018). <a href="http://www.incompleteideas.net/book/the-book.html">Reinforcement Learning: An Introduction</a> (2nd ed.). Cambridge, MA: MIT Press.</li>
<li>Tesauro, Gerald (March 1995). <a href="http://www.research.ibm.com/massive/tdl.html">"Temporal Difference Learning and TD-Gammon"</a>. Communications of the ACM. 38 (3): 58–68. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1145%2F203330.203343">10.1145/203330.203343</a>. <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:6023746">6023746</a>.</li></ul>
<h2 id="further-reading">Further reading</h2>
<ul><li>Meyn, S. P. (2007). Control Techniques for Complex Networks. Cambridge University Press. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-0521884419. See final chapter and appendix.</li>
<li>Sutton, R. S.; Barto, A. G. (1990). <a href="http://incompleteideas.net/sutton/papers/sutton-barto-90.pdf">"Time Derivative Models of Pavlovian Reinforcement"</a> (PDF). Learning and Computational Neuroscience: Foundations of Adaptive Networks: 497–537.</li></ul>
<h2 id="external-links">External links</h2>
<ul><li><a href="http://pitoko.net/tdgravity">Connect Four TDGravity Applet</a> (+ mobile phone version) – self-learned using TD-Leaf method (combination of TD-Lambda with shallow tree search)</li>
<li><a href="http://chet-weger.herokuapp.com/learn_meta_ttt/">Self Learning Meta-Tic-Tac-Toe</a> Example web app showing how temporal difference learning can be used to learn state evaluation constants for a minimax AI playing a simple board game.</li>
<li><a href="https://web.archive.org/web/20131116084228/http://www.cs.colorado.edu/~grudic/teaching/CSCI4202/RL.pdf">Reinforcement Learning Problem</a>, document explaining how temporal difference learning can be used to speed up <a href="/facts/Q-learning/emySKrgI">Q-learning</a></li>
<li><a href="https://www.cal-r.org/index.php?id=TD-sim">TD-Simulator</a> Temporal difference simulator for classical conditioning</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Sutton & Barto (2018), p. 133. - Sutton, Richard S.; Barto, Andrew G. (2018). Reinforcement Learning: An Introduction (2nd ed.). Cambridge, MA: MIT Press. <a href="http://www.incompleteideas.net/book/the-book.html" target="_blank">http://www.incompleteideas.net/book/the-book.html</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Sutton, Richard S. (1 August 1988). "Learning to predict by the methods of temporal differences". Machine Learning. 3 (1): 9–44. doi:10.1007/BF00115009. ISSN 1573-0565. S2CID 207771194. <a href="https://doi.org/10.1007%2FBF00115009" target="_blank">https://doi.org/10.1007%2FBF00115009</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Sutton, Richard S. (1 August 1988). "Learning to predict by the methods of temporal differences". Machine Learning. 3 (1): 9–44. doi:10.1007/BF00115009. ISSN 1573-0565. S2CID 207771194. <a href="https://doi.org/10.1007%2FBF00115009" target="_blank">https://doi.org/10.1007%2FBF00115009</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Schultz, W, Dayan, P & Montague, PR. (1997). "A neural substrate of prediction and reward". Science. 275 (5306): 1593–1599. CiteSeerX 10.1.1.133.6176. doi:10.1126/science.275.5306.1593. PMID 9054347. S2CID 220093382.{{cite journal}}: CS1 maint: multiple names: authors list (link) <a href="/wiki/CiteSeerX_(identifier)" target="_blank">/wiki/CiteSeerX_(identifier)</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Montague, P. R.; Dayan, P.; Sejnowski, T. J. (1996-03-01). "A framework for mesencephalic dopamine systems based on predictive Hebbian learning" (PDF). The Journal of Neuroscience. 16 (5): 1936–1947. doi:10.1523/JNEUROSCI.16-05-01936.1996. ISSN 0270-6474. PMC 6578666. PMID 8774460. <a href="http://papers.cnl.salk.edu/PDFs/A%20Framework%20for%20Mesencephalic%20Dopamine%20Systems%20Based%20on%20Predictive%20Hebbian%20Learning%201996-2938.pdf" target="_blank">http://papers.cnl.salk.edu/PDFs/A%20Framework%20for%20Mesencephalic%20Dopamine%20Systems%20Based%20on%20Predictive%20Hebbian%20Learning%201996-2938.pdf</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Montague, P.R.; Dayan, P.; Nowlan, S.J.; Pouget, A.; Sejnowski, T.J. (1993). "Using aperiodic reinforcement for directed self-organization" (PDF). Advances in Neural Information Processing Systems. 5: 969–976. <a href="http://www.gatsby.ucl.ac.uk/~dayan/papers/mdnps93.pdf" target="_blank">http://www.gatsby.ucl.ac.uk/~dayan/papers/mdnps93.pdf</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Montague, P. R.; Sejnowski, T. J. (1994). "The predictive brain: temporal coincidence and temporal order in synaptic learning mechanisms". Learning & Memory. 1 (1): 1–33. doi:10.1101/lm.1.1.1. ISSN 1072-0502. PMID 10467583. S2CID 44560099. <a href="https://doi.org/10.1101%2Flm.1.1.1" target="_blank">https://doi.org/10.1101%2Flm.1.1.1</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">Sejnowski, T.J.; Dayan, P.; Montague, P.R. (1995). "Predictive Hebbian learning". Proceedings of the eighth annual conference on Computational learning theory - COLT '95. pp. 15–18. doi:10.1145/225298.225300. ISBN 0897917235. S2CID 1709691. <a href="0897917235" target="_blank">0897917235</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn:9">Discount rate parameter allows for a time preference toward more immediate rewards, and away from distant future rewards <a href="/wiki/Time_preference" target="_blank">/wiki/Time_preference</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
<li id="fn:10">Sutton & Barto (2018), p. 134. - Sutton, Richard S.; Barto, Andrew G. (2018). Reinforcement Learning: An Introduction (2nd ed.). Cambridge, MA: MIT Press. <a href="http://www.incompleteideas.net/book/the-book.html" target="_blank">http://www.incompleteideas.net/book/the-book.html</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></li>
<li id="fn:11">Sutton & Barto (2018), p. 135. - Sutton, Richard S.; Barto, Andrew G. (2018). Reinforcement Learning: An Introduction (2nd ed.). Cambridge, MA: MIT Press. <a href="http://www.incompleteideas.net/book/the-book.html" target="_blank">http://www.incompleteideas.net/book/the-book.html</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></li>
<li id="fn:12">Sutton & Barto (2018), p. 130?. - Sutton, Richard S.; Barto, Andrew G. (2018). Reinforcement Learning: An Introduction (2nd ed.). Cambridge, MA: MIT Press. <a href="http://www.incompleteideas.net/book/the-book.html" target="_blank">http://www.incompleteideas.net/book/the-book.html</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></li>
<li id="fn:13">Tesauro (1995). - Tesauro, Gerald (March 1995). "Temporal Difference Learning and TD-Gammon". Communications of the ACM. 38 (3): 58–68. doi:10.1145/203330.203343. S2CID 6023746. <a href="http://www.research.ibm.com/massive/tdl.html" target="_blank">http://www.research.ibm.com/massive/tdl.html</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></li>
<li id="fn:14">Sutton & Barto (2018), p. 175. - Sutton, Richard S.; Barto, Andrew G. (2018). Reinforcement Learning: An Introduction (2nd ed.). Cambridge, MA: MIT Press. <a href="http://www.incompleteideas.net/book/the-book.html" target="_blank">http://www.incompleteideas.net/book/the-book.html</a> <a href="#fnref:14" class="footnote-back-ref">↩</a></li>
<li id="fn:15">Schultz, W, Dayan, P & Montague, PR. (1997). "A neural substrate of prediction and reward". Science. 275 (5306): 1593–1599. CiteSeerX 10.1.1.133.6176. doi:10.1126/science.275.5306.1593. PMID 9054347. S2CID 220093382.{{cite journal}}: CS1 maint: multiple names: authors list (link) <a href="/wiki/CiteSeerX_(identifier)" target="_blank">/wiki/CiteSeerX_(identifier)</a> <a href="#fnref:15" class="footnote-back-ref">↩</a></li>
<li id="fn:16">Montague, P. R.; Dayan, P.; Sejnowski, T. J. (1996-03-01). "A framework for mesencephalic dopamine systems based on predictive Hebbian learning" (PDF). The Journal of Neuroscience. 16 (5): 1936–1947. doi:10.1523/JNEUROSCI.16-05-01936.1996. ISSN 0270-6474. PMC 6578666. PMID 8774460. <a href="http://papers.cnl.salk.edu/PDFs/A%20Framework%20for%20Mesencephalic%20Dopamine%20Systems%20Based%20on%20Predictive%20Hebbian%20Learning%201996-2938.pdf" target="_blank">http://papers.cnl.salk.edu/PDFs/A%20Framework%20for%20Mesencephalic%20Dopamine%20Systems%20Based%20on%20Predictive%20Hebbian%20Learning%201996-2938.pdf</a> <a href="#fnref:16" class="footnote-back-ref">↩</a></li>
<li id="fn:17">Montague, P.R.; Dayan, P.; Nowlan, S.J.; Pouget, A.; Sejnowski, T.J. (1993). "Using aperiodic reinforcement for directed self-organization" (PDF). Advances in Neural Information Processing Systems. 5: 969–976. <a href="http://www.gatsby.ucl.ac.uk/~dayan/papers/mdnps93.pdf" target="_blank">http://www.gatsby.ucl.ac.uk/~dayan/papers/mdnps93.pdf</a> <a href="#fnref:17" class="footnote-back-ref">↩</a></li>
<li id="fn:18">Montague, P. R.; Sejnowski, T. J. (1994). "The predictive brain: temporal coincidence and temporal order in synaptic learning mechanisms". Learning & Memory. 1 (1): 1–33. doi:10.1101/lm.1.1.1. ISSN 1072-0502. PMID 10467583. S2CID 44560099. <a href="https://doi.org/10.1101%2Flm.1.1.1" target="_blank">https://doi.org/10.1101%2Flm.1.1.1</a> <a href="#fnref:18" class="footnote-back-ref">↩</a></li>
<li id="fn:19">Sejnowski, T.J.; Dayan, P.; Montague, P.R. (1995). "Predictive Hebbian learning". Proceedings of the eighth annual conference on Computational learning theory - COLT '95. pp. 15–18. doi:10.1145/225298.225300. ISBN 0897917235. S2CID 1709691. <a href="0897917235" target="_blank">0897917235</a> <a href="#fnref:19" class="footnote-back-ref">↩</a></li>
<li id="fn:20">Schultz, W. (1998). "Predictive reward signal of dopamine neurons". Journal of Neurophysiology. 80 (1): 1–27. CiteSeerX 10.1.1.408.5994. doi:10.1152/jn.1998.80.1.1. PMID 9658025. S2CID 52857162. <a href="/wiki/CiteSeerX_(identifier)" target="_blank">/wiki/CiteSeerX_(identifier)</a> <a href="#fnref:20" class="footnote-back-ref">↩</a></li>
<li id="fn:21">Dayan, P. (2001). "Motivated reinforcement learning" (PDF). Advances in Neural Information Processing Systems. 14. MIT Press: 11–18. <a href="http://books.nips.cc/papers/files/nips14/CS01.pdf" target="_blank">http://books.nips.cc/papers/files/nips14/CS01.pdf</a> <a href="#fnref:21" class="footnote-back-ref">↩</a></li>
<li id="fn:22">Tobia, M. J., etc. (2016). "Altered behavioral and neural responsiveness to counterfactual gains in the elderly". Cognitive, Affective, & Behavioral Neuroscience. 16 (3): 457–472. doi:10.3758/s13415-016-0406-7. PMID 26864879. S2CID 11299945.{{cite journal}}: CS1 maint: multiple names: authors list (link) <a href="https://doi.org/10.3758%2Fs13415-016-0406-7" target="_blank">https://doi.org/10.3758%2Fs13415-016-0406-7</a> <a href="#fnref:22" class="footnote-back-ref">↩</a></li>
<li id="fn:23">Smith, A., Li, M., Becker, S. and Kapur, S. (2006). "Dopamine, prediction error, and associative learning: a model-based account". Network: Computation in Neural Systems. 17 (1): 61–84. doi:10.1080/09548980500361624. PMID 16613795. S2CID 991839.{{cite journal}}: CS1 maint: multiple names: authors list (link) <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:23" class="footnote-back-ref">↩</a></li>
</ol>

Temporal difference learning open-in-new

Temporal difference learning