Answers.Body: <p>The paper <a href="http://users.isr.ist.utl.pt/~mtjspaan/readingGroup/ProofQlearning.pdf" rel="nofollow noreferrer">Convergence of Q-learning: A Simple Proof</a> (by Francisco S. Melo) shows (theorem 1) that Q-learning, a TD(0) algorithm, converges with probability 1 to the optimal Q-function as long as the Robbins-Monro conditions, for all combinations of states and actions, are satisfied. In other words, the Robbins-Monro conditions are <a href="https://en.wikipedia.org/wiki/Necessity_and_sufficiency" rel="nofollow noreferrer">sufficient</a> for Q-learning to converge to the optimal Q-function in the case of a finite MDP. The proof of theorem 1 uses another theorem from <a href="https://en.wikipedia.org/wiki/Stochastic_approximation" rel="nofollow noreferrer">stochastic approximation</a> (theorem 2).</p>
  
  <p>You are interested in the <a href="https://stats.stackexchange.com/q/340462/82135">prediction</a> problem, that is, the problem of predicting the expected return (i.e. a value function) from a fixed policy. However, Q-learning is <em>also</em> a control algorithm, given that it can find the optimal policy from the corresponding learned Q-function.</p>
  
  <p>See also the question <a href="https://ai.stackexchange.com/q/11679/2444">Why doesn&#39;t Q-learning converge when using function approximation?</a>.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-02-24T23:23:39.107Z
Answers.Text: Thanks for that, I was wondering is it true that TD(0) converges to the value function in Expected value when $\alpha$ is constant? Is there a condition that $\alpha \in (0,1)$?
Answers.UserDisplayName: KaneM
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-02-24T23:28:09.190Z
Answers.Text: @KaneM Right now, I am not aware of this result. Please, ask another question on the site because may someone else can answer your question.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-02-25T00:05:21.327Z
Answers.Text: The result is in Sutton's [Learning to Predict by the Methods of Temporal Differences](http://incompleteideas.net/papers/dayan-92.pdf) , on page 24 of this version. I think I understand the result now. It is saying that there is some range of  alphas $\alpha \in (0,t)$ such that TD(0) converges to the value function in expected value.
Answers.UserDisplayName: KaneM
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-02-24T21:47:00.300Z
Answers.LastActivityDate: 2020-02-24T21:54:13.623Z
Answers.LastEditDate: 2020-02-24T21:54:13.623Z
Answers.UserDisplayName: nbro
Body: <p>Does the learning rate parameter <span class="math-container">$\alpha$</span> require the Robbins-Monro conditions below for the TD(0) algorithm to converge to the true value function of a policy?</p>
  
  <p><span class="math-container">$$\sum \alpha_t =\infty \quad \text{and}\quad \sum \alpha^{2}_t &lt;\infty$$</span></p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-04-15T20:02:27.353Z
Comments.Text: This question was also asked at [https://stats.stackexchange.com/q/451115/82135](https://stats.stackexchange.com/q/451115/82135).
Comments.UserDisplayName: nbro
Tags: <reinforcement-learning><math><proofs><convergence><temporal-difference-methods>
Title: Does TD(0) prediction require Robbins-Monro conditions to converge to the value function?
UserDisplayName: KaneM
ThreadText: # Does TD(0) prediction require Robbins-Monro conditions to converge to the value function?
  
  (Asked by: username_0 on 2020-02-24)
  
  Does the learning rate parameter $\alpha$ require the Robbins-Monro conditions below for the TD(0) algorithm to converge to the true value function of a policy?
  
  $$\sum \alpha\_t =\infty \quad \text{and}\quad \sum \alpha^{2}\_t <\infty$$
  
  **Tags:** reinforcement-learning, math, proofs, convergence, temporal-difference-methods
  
  > **Comments:**
  > **username_1**: This question was also asked at [https://stats.stackexchange.com/q/451115/82135](https://stats.stackexchange.com/q/451115/82135).  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2020-02-24. Score: 1
  
  The paper [Convergence of Q-learning: A Simple Proof](http://users.isr.ist.utl.pt/~mtjspaan/readingGroup/ProofQlearning.pdf) (by Francisco S. Melo) shows (theorem 1) that Q-learning, a TD(0) algorithm, converges with probability 1 to the optimal Q-function as long as the Robbins-Monro conditions, for all combinations of states and actions, are satisfied. In other words, the Robbins-Monro conditions are [sufficient](https://en.wikipedia.org/wiki/Necessity_and_sufficiency) for Q-learning to converge to the optimal Q-function in the case of a finite MDP. The proof of theorem 1 uses another theorem from [stochastic approximation](https://en.wikipedia.org/wiki/Stochastic_approximation) (theorem 2).
  
  You are interested in the [prediction](https://stats.stackexchange.com/q/340462/82135) problem, that is, the problem of predicting the expected return (i.e. a value function) from a fixed policy. However, Q-learning is *also* a control algorithm, given that it can find the optimal policy from the corresponding learned Q-function.
  
  See also the question [Why doesn't Q-learning converge when using function approximation?](https://ai.stackexchange.com/q/11679/2444).
  
  > **Comments:**
  > **username_0**: Thanks for that, I was wondering is it true that TD(0) converges to the value function in Expected value when $\alpha$ is constant? Is there a condition that $\alpha \in (0,1)$?  
  > **username_1**: @username_0 Right now, I am not aware of this result. Please, ask another question on the site because may someone else can answer your question.  
  > **username_0**: The result is in Sutton's [Learning to Predict by the Methods of Temporal Differences](http://incompleteideas.net/papers/dayan-92.pdf) , on page 24 of this version. I think I understand the result now. It is saying that there is some range of  alphas $\alpha \in (0,t)$ such that TD(0) converges to the value function in expected value.  
  
  ---
  
  