Answers.Body: <p>The paper <a href="https://link.springer.com/content/pdf/10.1023/A:1007678930559.pdf" rel="nofollow noreferrer">Convergence Results for Single-Step On-Policy Reinforcement-Learning Algorithms</a> by Satinder Singh et al. proves that SARSA(0), in the case of a tabular representation of the value functions, converges to the optimal value function, provided certain assumptions are met</p>
  
  <ol>
  <li>Infinite visits to every state-action pair </li>
  <li>The learning policy becomes greedy in the limit</li>
  </ol>
  
  <p>The properties are more formally stated in lemma 1 (page 7 of the pdf) and theorem 1 (page 8). The <a href="https://arxiv.org/pdf/1808.00245.pdf" rel="nofollow noreferrer">Robbins–Monro conditions should ensure that each state-action pair is visited infinitely often</a>.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-02-27T13:40:42.483Z
Answers.Text: I was already writing this answer before [the other answer](https://ai.stackexchange.com/a/18279/2444) was published, but these answers are equivalent. I am only citing the paper that originally proved this.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-02-27T13:45:30.737Z
Answers.Text: Thanks for the answer. Sorry about my poor formatting of posts here. Just learning about markdown.
Answers.UserDisplayName: KaneM
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-02-27T13:48:40.740Z
Answers.Text: @KaneM No problem! I have a look at source code of my and your answer (now after my edits) to understand better how markdown works :) Anyway, I am not completely sure that the Robbins-Monro conditions ensure that each state is visited infinitely often. Maybe it's the other way around: if each state-action pair is visited infinitely often, then the Robbins-Monro conditions are satisfied.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-02-27T13:59:25.467Z
Answers.Text: I believe they are separate conditions. From my understanding, the RM conditions ensure that the Q function eventually converges to **a** value while the condition that every state-action pair is visited infinitely often ensure that it converges to the correct value.
Answers.UserDisplayName: KaneM
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-02-27T14:03:57.477Z
Answers.Text: @KaneM These conditions are very related. I'm linking to a paper that seems to relate the two in a more precise way, but I haven't yet fully read this paper.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-02-27T14:32:34.420Z
Answers.Text: I wonder if the Robbins-Monro conditions are not present, does there exist some range of $\alpha$ such that the policy converges in some notion of expectation to the optimal policy.
Answers.UserDisplayName: KaneM
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-02-27T14:43:54.107Z
Answers.Text: @KaneM This is an interesting question. Maybe ask on the site! I wouldn't currently be able to answer it, but maybe there's already some research work that goes in this direction. In all convergence results I've seen so far, the RM conditions are assumed (essentially, because these RL theorems and proofs follow from the original results by Robbins and Monro, AFAIK).
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-02-27T13:40:12.440Z
Answers.LastActivityDate: 2020-02-27T13:40:12.440Z
Answers.UserDisplayName: nbro
Answers.Body: <p>I have the conditions for convergence in these notes <a href="https://webee.technion.ac.il/shimkin/LCS11/ch7_exploration.pdf" rel="nofollow noreferrer">SARSA convergence</a> by <a href="https://webee.technion.ac.il/shimkin/" rel="nofollow noreferrer">Nahum Shimkin</a>.</p>
  
  <ol>
  <li><p>The Robbins-Monro conditions above hold for <span class="math-container">$α_t$</span>.</p></li>
  <li><p>Every state-action pair is visited infinitely often</p></li>
  <li><p>The policy is greedy with respect to the policy derived from <span class="math-container">$Q$</span> in the limit</p></li>
  <li><p>The controlled Markov chain is communicating: every state can be reached from any other with positive probability (under some policy).</p></li>
  <li><p><span class="math-container">$\operatorname{Var}{R(s, a)} &lt; \infty$</span>, where <span class="math-container">$R$</span> is the reward function</p></li>
  </ol>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-02-27T13:29:22.227Z
Answers.LastActivityDate: 2020-02-27T14:10:40.440Z
Answers.LastEditDate: 2020-02-27T14:10:40.440Z
Answers.UserDisplayName: KaneM
Body: <p>Is it correct that for SARSA to converge to the optimal value function (and policy)</p>
  
  <ol>
  <li><p>The learning rate parameter  <span class="math-container">$\alpha$</span> must satisfy the conditions:
  <span class="math-container">$$\sum \alpha_{n^k(s,a)} =\infty \quad \text{and}\quad \sum \alpha_{n^k(s,a)}^{2} &lt;\infty \quad \forall s \in \mathcal{S}$$</span>
  where <span class="math-container">$n_k(s,a)$</span> denotes the <span class="math-container">$k^\text{th}$</span> time <span class="math-container">$(s,a)$</span> is visited</p></li>
  <li><p><span class="math-container">$\epsilon$</span> (of the <span class="math-container">$\epsilon$</span>-greedy policy) must be decayed so that the policy converges to a greedy policy.</p></li>
  <li><p>Every state-action pair is visited infinitely many times.</p></li>
  </ol>
  
  <p>Are any of these conditions redundant?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-02-27T13:17:15.150Z
Comments.Text: There is probably some relation between the fact that the TD(0) function converge to the true Value function with probability 1 when the learning rate parameter is decayed like above. There also exists some interval of alphas $\alpha \in (0,p)$ such that the TD estimate converges in expected value to the true value function
Comments.UserDisplayName: KaneM
Tags: <reinforcement-learning><math><proofs><convergence><sarsa>
Title: What are the conditions for the convergence of SARSA to the optimal value function?
UserDisplayName: KaneM
ThreadText: # What are the conditions for the convergence of SARSA to the optimal value function?
  
  (Asked by: username_0 on 2020-02-27)
  
  Is it correct that for SARSA to converge to the optimal value function (and policy)
  
  1. The learning rate parameter $\alpha$ must satisfy the conditions:
     $$\sum \alpha\_{n^k(s,a)} =\infty \quad \text{and}\quad \sum \alpha\_{n^k(s,a)}^{2} <\infty \quad \forall s \in \mathcal{S}$$
     where $n\_k(s,a)$ denotes the $k^\text{th}$ time $(s,a)$ is visited
  2. $\epsilon$ (of the $\epsilon$-greedy policy) must be decayed so that the policy converges to a greedy policy.
  3. Every state-action pair is visited infinitely many times.
  
  Are any of these conditions redundant?
  
  **Tags:** reinforcement-learning, math, proofs, convergence, sarsa
  
  > **Comments:**
  > **username_0**: There is probably some relation between the fact that the TD(0) function converge to the true Value function with probability 1 when the learning rate parameter is decayed like above. There also exists some interval of alphas $\alpha \in (0,p)$ such that the TD estimate converges in expected value to the true value function  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_1 on 2020-02-27. Score: 2 | Accepted answer
  
  The paper [Convergence Results for Single-Step On-Policy Reinforcement-Learning Algorithms](https://link.springer.com/content/pdf/10.1023/A:1007678930559.pdf) by Satinder Singh et al. proves that SARSA(0), in the case of a tabular representation of the value functions, converges to the optimal value function, provided certain assumptions are met
  
  1. Infinite visits to every state-action pair
  2. The learning policy becomes greedy in the limit
  
  The properties are more formally stated in lemma 1 (page 7 of the pdf) and theorem 1 (page 8). The [Robbins–Monro conditions should ensure that each state-action pair is visited infinitely often](https://arxiv.org/pdf/1808.00245.pdf).
  
  > **Comments:**
  > **username_1**: I was already writing this answer before [the other answer](https://ai.stackexchange.com/a/18279/2444) was published, but these answers are equivalent. I am only citing the paper that originally proved this.  
  > **username_0**: Thanks for the answer. Sorry about my poor formatting of posts here. Just learning about markdown.  
  > **username_1**: @username_0 No problem! I have a look at source code of my and your answer (now after my edits) to understand better how markdown works :) Anyway, I am not completely sure that the Robbins-Monro conditions ensure that each state is visited infinitely often. Maybe it's the other way around: if each state-action pair is visited infinitely often, then the Robbins-Monro conditions are satisfied.  
  > **username_0**: I believe they are separate conditions. From my understanding, the RM conditions ensure that the Q function eventually converges to **a** value while the condition that every state-action pair is visited infinitely often ensure that it converges to the correct value.  
  > **username_1**: @username_0 These conditions are very related. I'm linking to a paper that seems to relate the two in a more precise way, but I haven't yet fully read this paper.  
  > **username_0**: I wonder if the Robbins-Monro conditions are not present, does there exist some range of $\alpha$ such that the policy converges in some notion of expectation to the optimal policy.  
  > **username_1**: @username_0 This is an interesting question. Maybe ask on the site! I wouldn't currently be able to answer it, but maybe there's already some research work that goes in this direction. In all convergence results I've seen so far, the RM conditions are assumed (essentially, because these RL theorems and proofs follow from the original results by Robbins and Monro, AFAIK).  
  
  ---
  
  ### Answer by username_0 on 2020-02-27. Score: 1
  
  I have the conditions for convergence in these notes [SARSA convergence](https://webee.technion.ac.il/shimkin/LCS11/ch7_exploration.pdf) by [Nahum Shimkin](https://webee.technion.ac.il/shimkin/).
  
  1. The Robbins-Monro conditions above hold for $α\_t$.
  2. Every state-action pair is visited infinitely often
  3. The policy is greedy with respect to the policy derived from $Q$ in the limit
  4. The controlled Markov chain is communicating: every state can be reached from any other with positive probability (under some policy).
  5. $\operatorname{Var}{R(s, a)} < \infty$, where $R$ is the reward function
  
  
  ---
  
  