Answers.Body: <p>To obtain guarantees of convergence for Q table values, you need to decay the learning rate, <span class="math-container">$\alpha$</span>, at a suitable rate. Too fast and convergence will be to inaccurate values. Too slow and convergence never happens.</p>
  <p>For sticking with theoretical guarantees, the learning rate decay process should generally follow the rule that <span class="math-container">$\sum_t \alpha_t = \infty$</span> but <span class="math-container">$\sum_t \alpha_t^2 \ne \infty$</span> - an example of a learning rate schedule that does this is <span class="math-container">$\alpha_t = \frac{1}{t}$</span>, although in practice that specific choice could lead to very slow convergence.</p>
  <p>Choosing a good starting <span class="math-container">$\alpha$</span> and a good decay schedule will depend on the problem, and you may want to base it on experience with similar problems. However, it is not that common to need to gurantee convergence of action values in value-based reinforcement learning. In control problems you often care more about have finding an optimal policy than about perfectly accurate action values. Further to that, many interesting control problems are too complex to solve perfectly in tabular form, so you expect some approximation. It seems relatively common just to pick a learning rate for the problem and stick with it.</p>
  <p>If you make your learning rate lower, the Q table will converge to more stable Q values, but possibly at the expense of taking longer to converge on the optimal policy.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-02-25T16:42:38.843Z
Answers.Text: Thanks Neil for you answer. It's helpful. So now I think a constant learning rate is only suitable for the non-stationary case?
Answers.UserDisplayName: O'Jhene
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-02-25T18:06:11.283Z
Answers.Text: @O'Jhene A constant learning rate is often fine. If you want really good approximations to Q values, it may just need to be lower. But scaling it down slowly is also good.
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-02-25T16:22:32.900Z
Answers.LastActivityDate: 2021-02-25T16:22:32.900Z
Answers.UserDisplayName: Neil Slater
Body: <p>I have a stochastic environment and I'm implementing a Q-table for the learning that happens on the environment. The code is shown below. In short, there are ten states (0, 1, 2,...,9), and three actions: 0, 1, and 2. The action 0 does nothing, action 1 subtracts 1 with a probability of 0.7, and action 2 adds 1 with a probability of 0.7. We get a reward of 1 when we are in state 5, and 0 otherwise.</p>
  <pre><code>import numpy as np
  import matplotlib.pyplot as plt
  
  def reward(s_dash):
      if s_dash == 5:
          return 1
      else: 
          return 0
  states = range(10)
  Q = np.zeros((len(states),3))
  Q_previous = np.zeros((len(states),3))
  episodes = 2000
  trials = 100
  alpha = 0.1
  decay = 0.995
  gamma = 0.9
  ls_av = []
  ls = []
  for episode in range(episodes):
      print(episode)
      s = np.random.choice(states)
      eps = 1
      for i in range(trials):
          eps *= decay
          p = np.random.random()
          if p &lt; eps:
              a = np.random.randint(0,3)
          else:
              a = np.argmax(Q[s, :])
  
          if a == 0:
              s_dash = s
          elif a == 1:
              if p &gt;= 0.7:
                  s_dash = max(s-1, 0)
              else:
                  s_dash = s
          else:
              if p &gt;= 0.7:
                  s_dash = min(s+1, 9)
              else:
                  s_dash = s
          r = reward(s_dash)
          Q[s][a] = (1-alpha)*Q[s][a] + alpha*(r + gamma*np.max(Q[s_dash]))
          s = s_dash
      ls.append(np.max(abs(Q - Q_previous)))
      Q_previous = np.copy(Q)
  print(Q)
  for i in range(10):
      print(i, np.argmax(Q[i, :]))
  plt.plot(ls)
  plt.show()
  
  </code></pre>
  <p>When I plot the absolute value of the maximum change in the Q-table at the end of each episode, I get the following, which indicates that the Q-table is constantly being updated.</p>
  <p><a href="https://i.sstatic.net/GAv3b.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/GAv3b.png" alt="A plot of absolute value of max change in Q-table with episode" /></a></p>
  <p>However, I see that when I print out the action with the max Q-value for each state, it shows what I expect to be the optimal policy. For each state, the best action is given as shown below:</p>
  <pre><code>(0, 2)
  (1, 2)
  (2, 2)
  (3, 2)
  (4, 2)
  (5, 0)
  (6, 1)
  (7, 1)
  (8, 1)
  (9, 1)
  
  </code></pre>
  <p>My question is: why do I not have convergence in the Q-table? If I had a stochastic environment for which I didn't know before-hand what the optimal policy is, how will I be able to judge if I need to stop training when the Q-table isn't converging?</p>
  
Tags: <reinforcement-learning><training><q-learning><markov-decision-process>
Title: What is a good convergence criterion for Q-learning in a stochastic environment?
UserDisplayName: O'Jhene
ThreadText: # What is a good convergence criterion for Q-learning in a stochastic environment?
  
  (Asked by: username_0 on 2021-02-25)
  
  I have a stochastic environment and I'm implementing a Q-table for the learning that happens on the environment. The code is shown below. In short, there are ten states (0, 1, 2,...,9), and three actions: 0, 1, and 2. The action 0 does nothing, action 1 subtracts 1 with a probability of 0.7, and action 2 adds 1 with a probability of 0.7. We get a reward of 1 when we are in state 5, and 0 otherwise.
  import numpy as np
  import matplotlib.pyplot as plt
  
  def reward(s_dash):
      if s_dash == 5:
          return 1
      else: 
          return 0
  states = range(10)
  Q = np.zeros((len(states),3))
  Q_previous = np.zeros((len(states),3))
  episodes = 2000
  trials = 100
  alpha = 0.1
  decay = 0.995
  gamma = 0.9
  ls_av = []
  ls = []
  for episode in range(episodes):
      print(episode)
      s = np.random.choice(states)
      eps = 1
      for i in range(trials):
          eps *= decay
          p = np.random.random()
          if p < eps:
              a = np.random.randint(0,3)
          else:
              a = np.argmax(Q[s, :])
  
          if a == 0:
              s_dash = s
          elif a == 1:
              if p >= 0.7:
                  s_dash = max(s-1, 0)
              else:
                  s_dash = s
          else:
              if p >= 0.7:
                  s_dash = min(s+1, 9)
              else:
                  s_dash = s
          r = reward(s_dash)
          Q[s][a] = (1-alpha)*Q[s][a] + alpha*(r + gamma*np.max(Q[s_dash]))
          s = s_dash
      ls.append(np.max(abs(Q - Q_previous)))
      Q_previous = np.copy(Q)
  print(Q)
  for i in range(10):
      print(i, np.argmax(Q[i, :]))
  plt.plot(ls)
  plt.show()
  
  
  When I plot the absolute value of the maximum change in the Q-table at the end of each episode, I get the following, which indicates that the Q-table is constantly being updated.
  
  However, I see that when I print out the action with the max Q-value for each state, it shows what I expect to be the optimal policy. For each state, the best action is given as shown below:
  (0, 2)
  (1, 2)
  (2, 2)
  (3, 2)
  (4, 2)
  (5, 0)
  (6, 1)
  (7, 1)
  (8, 1)
  (9, 1)
  
  
  My question is: why do I not have convergence in the Q-table? If I had a stochastic environment for which I didn't know before-hand what the optimal policy is, how will I be able to judge if I need to stop training when the Q-table isn't converging?
  
  **Tags:** reinforcement-learning, training, q-learning, markov-decision-process
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2021-02-25. Score: 3 | Accepted answer
  
  To obtain guarantees of convergence for Q table values, you need to decay the learning rate, $\alpha$, at a suitable rate. Too fast and convergence will be to inaccurate values. Too slow and convergence never happens.
  
  For sticking with theoretical guarantees, the learning rate decay process should generally follow the rule that $\sum\_t \alpha\_t = \infty$ but $\sum\_t \alpha\_t^2 \ne \infty$ - an example of a learning rate schedule that does this is $\alpha\_t = \frac{1}{t}$, although in practice that specific choice could lead to very slow convergence.
  
  Choosing a good starting $\alpha$ and a good decay schedule will depend on the problem, and you may want to base it on experience with similar problems. However, it is not that common to need to gurantee convergence of action values in value-based reinforcement learning. In control problems you often care more about have finding an optimal policy than about perfectly accurate action values. Further to that, many interesting control problems are too complex to solve perfectly in tabular form, so you expect some approximation. It seems relatively common just to pick a learning rate for the problem and stick with it.
  
  If you make your learning rate lower, the Q table will converge to more stable Q values, but possibly at the expense of taking longer to converge on the optimal policy.
  
  > **Comments:**
  > **username_0**: Thanks Neil for you answer. It's helpful. So now I think a constant learning rate is only suitable for the non-stationary case?  
  > **username_1**: @O'Jhene A constant learning rate is often fine. If you want really good approximations to Q values, it may just need to be lower. But scaling it down slowly is also good.  
  
  ---
  
  