Answers.Body: <blockquote>
  <p>Why is this a convergence criterion?</p>
  </blockquote>
  <p>It is because <span class="math-container">$R$</span> and <span class="math-container">$S'$</span> are stochastic. A large learning rate applied when these values have variance would not converge to mean, but would wander around typically within some value proportional to <span class="math-container">$\alpha\sigma$</span> of the true value, where <span class="math-container">$\sigma$</span> is the standard deviation of the term <span class="math-container">$R + \gamma\text{max}_aQ(S',a)$</span>. If you reduce <span class="math-container">$\alpha$</span> towards zero, then this expected error will also reduce to zero.</p>
  <p>For deterministic environments, it should be possible to prove convergence with large <span class="math-container">$\alpha$</span>.</p>
  <hr />
  <p>In the special case of static policy, tabular learning and <span class="math-container">$\alpha = \frac{1}{N(s,a)}$</span> where <span class="math-container">$N(s,a)$</span> is number of visits to state <span class="math-container">$s$</span>, action <span class="math-container">$a$</span>, then the expected error for each Q value is the MSE from basic stats i.e. <span class="math-container">$\frac{\sigma_{TD}}{\sqrt{N(s,a)}}$</span></p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-04T09:13:44.577Z
Answers.LastActivityDate: 2020-12-04T10:16:26.900Z
Answers.LastEditDate: 2020-12-04T10:16:26.900Z
Answers.UserDisplayName: Neil Slater
Body: <p><em>Q-Learning is guaranteed to converge if <span class="math-container">$\alpha$</span> decreases over time.</em></p>
  <p><a href="http://incompleteideas.net/book/RLbook2020.pdf#page=183" rel="nofollow noreferrer">On page 161</a> of the RL book by Sutton and Barto, 2nd edition, section 8.1, they write that Dyna-Q is guaranteed to converge if each action-state pair is selected an infinite number of times and if <span class="math-container">$\alpha$</span> decreases appropriately over time.</p>
  <p>It seems that it would be better if <span class="math-container">$\alpha$</span> increased over time, as it is the learning rate of the gradient of Q-function values (<span class="math-container">$R+\gamma\max_aQ(S',a)-Q(S,A)$</span>), and, initially, they start off incredibly inaccurate, because they are initialized arbitrarily and over time converge to the true values, hence you'd want to weight them more as time increases rather than decrease it?</p>
  <p>Why is this a convergence criterion?</p>
  
Tags: <reinforcement-learning><q-learning><convergence><learning-rate><dyna>
Title: If $\alpha$ decreases over time, why is Q-learning guaranteed to converge?
UserDisplayName: user8714896
ThreadText: # If $\alpha$ decreases over time, why is Q-learning guaranteed to converge?
  
  (Asked by: username_0 on 2020-12-04)
  
  *Q-Learning is guaranteed to converge if $\alpha$ decreases over time.*
  
  [On page 161](http://incompleteideas.net/book/RLbook2020.pdf#page=183) of the RL book by Sutton and Barto, 2nd edition, section 8.1, they write that Dyna-Q is guaranteed to converge if each action-state pair is selected an infinite number of times and if $\alpha$ decreases appropriately over time.
  
  It seems that it would be better if $\alpha$ increased over time, as it is the learning rate of the gradient of Q-function values ($R+\gamma\max\_aQ(S',a)-Q(S,A)$), and, initially, they start off incredibly inaccurate, because they are initialized arbitrarily and over time converge to the true values, hence you'd want to weight them more as time increases rather than decrease it?
  
  Why is this a convergence criterion?
  
  **Tags:** reinforcement-learning, q-learning, convergence, learning-rate, dyna
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2020-12-04. Score: 5 | Accepted answer
  
  > Why is this a convergence criterion?
  
  It is because $R$ and $S'$ are stochastic. A large learning rate applied when these values have variance would not converge to mean, but would wander around typically within some value proportional to $\alpha\sigma$ of the true value, where $\sigma$ is the standard deviation of the term $R + \gamma\text{max}\_aQ(S',a)$. If you reduce $\alpha$ towards zero, then this expected error will also reduce to zero.
  
  For deterministic environments, it should be possible to prove convergence with large $\alpha$.
  
  ---
  
  In the special case of static policy, tabular learning and $\alpha = \frac{1}{N(s,a)}$ where $N(s,a)$ is number of visits to state $s$, action $a$, then the expected error for each Q value is the MSE from basic stats i.e. $\frac{\sigma\_{TD}}{\sqrt{N(s,a)}}$
  
  
  ---
  
  