Answers.Body: <p>There are different TD algorithms, e.g. Q-learning and SARSA, whose convergence properties have been studied separately (in many cases). </p>
  
  <p>In some convergence proofs, e.g. in the paper <a href="http://users.isr.ist.utl.pt/~mtjspaan/readingGroup/ProofQlearning.pdf" rel="noreferrer">Convergence of Q-learning: A Simple Proof</a> (by Francisco S. Melo), the required conditions for Q-learning to converge (in probability) are the Robbins-Monro conditions</p>
  
  <ol>
  <li><span class="math-container">$\sum_{t} \alpha_t(s, a) = \infty$</span></li>
  <li><span class="math-container">$\sum_{t} \alpha_t^2(s, a) &lt; \infty,$</span></li>
  </ol>
  
  <p>where <span class="math-container">$\alpha_t(s, a)$</span> is the learning rate at time step <span class="math-container">$t$</span> (that can depend on the state <span class="math-container">$s$</span> and action <span class="math-container">$a$</span>), and that each state is visited infinitely often. </p>
  
  <p>(The Robbins-Monro conditions (1 and 2) are due to Herbert Robbins and Sutton Monro, who started the field of <a href="https://en.wikipedia.org/wiki/Stochastic_approximation" rel="noreferrer">stochastic approximation</a> in the 1950s, with the paper <a href="https://projecteuclid.org/download/pdf_1/euclid.aoms/1177729586" rel="noreferrer">A Stochastic Approximation Method</a>. The fields of RL and stochastic approximation are related. See <a href="https://ai.stackexchange.com/a/20273/2444">this answer</a> for more details.)</p>
  
  <p>However, note again that the specific required conditions for TD methods to converge may vary depending on the proof and the specific TD algorithm. For example, the Robbins-Monro conditions are not assumed in <a href="https://link.springer.com/content/pdf/10.1007%2FBF00115009.pdf" rel="noreferrer">Learning to Predict by the Methods of Temporal Differences</a> by Richard S. Sutton (because this is not a proof of <a href="https://en.wikipedia.org/wiki/Convergence_of_random_variables" rel="noreferrer">convergence in probability but in expectation</a>).</p>
  
  <p>Moreover, note that the proofs mentioned above are only applicable to the tabular versions of Q-learning. If you use function approximation, Q-learning (and other TD algorithms) may not converge. Nevertheless, there are cases when Q-learning combined with function approximation converges. See <a href="https://gaips.inesc-id.pt/~fmelo/pub/melo08icml.pdf" rel="noreferrer">An Analysis of Reinforcement Learning with Function Approximation</a> by Francisco S. Melo et al. and <a href="https://arxiv.org/pdf/1712.10285.pdf" rel="noreferrer">SBEED: Convergent Reinforcement Learning with Nonlinear Function Approximation</a> by Bo Dai et al.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-05-26T02:55:11.310Z
Answers.Text: Hi, thanks for the reply! Is there any requirement on the environment? What if the environment is totally random, and for each state, action, there is not even a fixed value in essence?
Answers.UserDisplayName: MJeremy
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-06-02T15:29:36.707Z
Answers.Text: @MJeremy I don't know what you mean exactly by "totally random". There are some restrictions on the environment in certain proofs. For example, in the paper [Convergence of Q-learning: A Simple Proof](http://users.isr.ist.utl.pt/~mtjspaan/readingGroup/ProofQlearning.pdf), F. Melo e.g. assumes that the reward function is deterministic. So, the assumptions probably vary from one proof to the other. It's probably a better idea that you read the specific papers that provide the proofs, if you want to know more details.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-05-22T13:10:44.963Z
Answers.LastActivityDate: 2020-05-23T18:41:37.073Z
Answers.LastEditDate: 2020-05-23T18:41:37.073Z
Answers.UserDisplayName: nbro
Body: <p>In reinforcement learning, temporal difference seem to update the value function in each new iteration of experience absorbed from the environment. </p>
  
  <p>What would be the conditions for temporal-difference learning to converge in the end? How is it guaranteed to converge?</p>
  
  <p>Any intuitive understanding of those conditions that lead to the convergence?</p>
  
Tags: <reinforcement-learning><convergence><temporal-difference-methods>
Title: What are the conditions of convergence of temporal-difference learning?
UserDisplayName: MJeremy
ThreadText: # What are the conditions of convergence of temporal-difference learning?
  
  (Asked by: username_0 on 2020-05-22)
  
  In reinforcement learning, temporal difference seem to update the value function in each new iteration of experience absorbed from the environment.
  
  What would be the conditions for temporal-difference learning to converge in the end? How is it guaranteed to converge?
  
  Any intuitive understanding of those conditions that lead to the convergence?
  
  **Tags:** reinforcement-learning, convergence, temporal-difference-methods
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2020-05-22. Score: 6 | Accepted answer
  
  There are different TD algorithms, e.g. Q-learning and SARSA, whose convergence properties have been studied separately (in many cases).
  
  In some convergence proofs, e.g. in the paper [Convergence of Q-learning: A Simple Proof](http://users.isr.ist.utl.pt/~mtjspaan/readingGroup/ProofQlearning.pdf) (by Francisco S. Melo), the required conditions for Q-learning to converge (in probability) are the Robbins-Monro conditions
  
  1. $\sum\_{t} \alpha\_t(s, a) = \infty$
  2. $\sum\_{t} \alpha\_t^2(s, a) < \infty,$
  
  where $\alpha\_t(s, a)$ is the learning rate at time step $t$ (that can depend on the state $s$ and action $a$), and that each state is visited infinitely often.
  
  (The Robbins-Monro conditions (1 and 2) are due to Herbert Robbins and Sutton Monro, who started the field of [stochastic approximation](https://en.wikipedia.org/wiki/Stochastic_approximation) in the 1950s, with the paper [A Stochastic Approximation Method](https://projecteuclid.org/download/pdf_1/euclid.aoms/1177729586). The fields of RL and stochastic approximation are related. See [this answer](https://ai.stackexchange.com/a/20273/2444) for more details.)
  
  However, note again that the specific required conditions for TD methods to converge may vary depending on the proof and the specific TD algorithm. For example, the Robbins-Monro conditions are not assumed in [Learning to Predict by the Methods of Temporal Differences](https://link.springer.com/content/pdf/10.1007%2FBF00115009.pdf) by Richard S. Sutton (because this is not a proof of [convergence in probability but in expectation](https://en.wikipedia.org/wiki/Convergence_of_random_variables)).
  
  Moreover, note that the proofs mentioned above are only applicable to the tabular versions of Q-learning. If you use function approximation, Q-learning (and other TD algorithms) may not converge. Nevertheless, there are cases when Q-learning combined with function approximation converges. See [An Analysis of Reinforcement Learning with Function Approximation](https://gaips.inesc-id.pt/~fmelo/pub/melo08icml.pdf) by Francisco S. Melo et al. and [SBEED: Convergent Reinforcement Learning with Nonlinear Function Approximation](https://arxiv.org/pdf/1712.10285.pdf) by Bo Dai et al.
  
  > **Comments:**
  > **username_0**: Hi, thanks for the reply! Is there any requirement on the environment? What if the environment is totally random, and for each state, action, there is not even a fixed value in essence?  
  > **username_1**: @MJeremy I don't know what you mean exactly by "totally random". There are some restrictions on the environment in certain proofs. For example, in the paper [Convergence of Q-learning: A Simple Proof](http://users.isr.ist.utl.pt/~mtjspaan/readingGroup/ProofQlearning.pdf), F. Melo e.g. assumes that the reward function is deterministic. So, the assumptions probably vary from one proof to the other. It's probably a better idea that you read the specific papers that provide the proofs, if you want to know more details.  
  
  ---
  
  