Answers.Body: <p>Q-learning is guaranteed to converge (in the tabular case) under some mild conditions, one of which is that in the limit we visit each state-action tuple infinitely many times. If your random random policy (i.e. 100% exploration) is guaranteeing this and the other conditions are met (which they probably are) then Q-learning will converge.</p>
  <p>The reason that different state-action pairs have longer arrows, i.e. higher Q-values, is simply because the value of being in that state-action pair is higher. An example would be the arrow pointing down right above the trophy -- obviously this has the highest Q-value as the return is 1. For all other states it will be <span class="math-container">$\gamma^k$</span> for some <span class="math-container">$k$</span> -- to see this remember that a Q-value is defined as</p>
  <p><span class="math-container">$$Q(s, a) = \mathbb{E}_\pi \left[\sum_{j=0}^\infty \gamma^j R_{t+j+1} |S_t = s, A_t = a \right]\;;$$</span>
  so for any state-action pair that is not the block above the trophy with the down arrow <span class="math-container">$\sum_{j=0}^\infty \gamma^j R_{t+j+1}$</span> will be a sum of <span class="math-container">$0$</span>'s plus <span class="math-container">$\gamma^T$</span> where <span class="math-container">$T$</span> is the time that you finally reach the trophy (assuming you give a reward of 1 for reaching the trophy).</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-02-20T21:34:10.453Z
Answers.Text: Thank you for your explanation. I am also confused why certain arrows (not necessarily in the same state) should converge towards the same lengths. Why is this the case? is it because of the 100% exploration rate?
Answers.UserDisplayName: Rim Sleimi
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-02-21T01:10:35.177Z
Answers.Text: This just means that they have the same Q-value. For your example this makes sense due to the symmetry of the board (ignoring the alien). For instance, If you take the two states on the top row and one to the left and right of the trophy, then you can reach the trophy in the same amount of steps (3, when acting optimally, and remember Q-learning converges to the optimal Q-values) from either state so they have the same Q-value.
Answers.UserDisplayName: David
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-02-20T14:37:46.597Z
Answers.LastActivityDate: 2021-02-20T14:37:46.597Z
Answers.UserDisplayName: David
Body: <p>I am working on this assignment where I made the agent learn state-action values (Q-values) with Q-learning and 100% exploration rate. The environment is the classic gridworld as shown in the following picture.</p>
  <p><a href="https://i.sstatic.net/2yj8o.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/2yj8o.png" alt="enter image description here" /></a></p>
  <p>Here are the values of my parameters.</p>
  <ul>
  <li>Learning rate = 0.1</li>
  <li>Discount factor = 0.95</li>
  <li>Default reward = 0</li>
  </ul>
  <p>Reaching the trophy is the final reward, no negative reward is given for bumping into walls or for taking a step.</p>
  <p>After 500 episodes, the arrows have converged. As shown in the figure, some states have longer arrows than others (i.e., larger Q-values). Why is this so? I don't understand how the agent learns and finds the optimal actions and states when the exploration rate is 100% (each action: N-S-E-W has 25% chance to be selected)</p>
  
Tags: <reinforcement-learning><q-learning><convergence><epsilon-greedy-policy><exploration-strategies>
Title: Why does Q-learning converge under 100% exploration rate?
UserDisplayName: Rim Sleimi
ThreadText: # Why does Q-learning converge under 100% exploration rate?
  
  (Asked by: username_0 on 2021-02-20)
  
  I am working on this assignment where I made the agent learn state-action values (Q-values) with Q-learning and 100% exploration rate. The environment is the classic gridworld as shown in the following picture.
  
  [![enter image description here](https://i.sstatic.net/2yj8o.png)](https://i.sstatic.net/2yj8o.png)
  
  Here are the values of my parameters.
  
  * Learning rate = 0.1
  * Discount factor = 0.95
  * Default reward = 0
  
  Reaching the trophy is the final reward, no negative reward is given for bumping into walls or for taking a step.
  
  After 500 episodes, the arrows have converged. As shown in the figure, some states have longer arrows than others (i.e., larger Q-values). Why is this so? I don't understand how the agent learns and finds the optimal actions and states when the exploration rate is 100% (each action: N-S-E-W has 25% chance to be selected)
  
  **Tags:** reinforcement-learning, q-learning, convergence, epsilon-greedy-policy, exploration-strategies
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2021-02-20. Score: 5 | Accepted answer
  
  Q-learning is guaranteed to converge (in the tabular case) under some mild conditions, one of which is that in the limit we visit each state-action tuple infinitely many times. If your random random policy (i.e. 100% exploration) is guaranteeing this and the other conditions are met (which they probably are) then Q-learning will converge.
  
  The reason that different state-action pairs have longer arrows, i.e. higher Q-values, is simply because the value of being in that state-action pair is higher. An example would be the arrow pointing down right above the trophy -- obviously this has the highest Q-value as the return is 1. For all other states it will be $\gamma^k$ for some $k$ -- to see this remember that a Q-value is defined as
  
  $$Q(s, a) = \mathbb{E}\_\pi \left[\sum\_{j=0}^\infty \gamma^j R\_{t+j+1} |S\_t = s, A\_t = a \right]\;;$$
  so for any state-action pair that is not the block above the trophy with the down arrow $\sum\_{j=0}^\infty \gamma^j R\_{t+j+1}$ will be a sum of $0$'s plus $\gamma^T$ where $T$ is the time that you finally reach the trophy (assuming you give a reward of 1 for reaching the trophy).
  
  > **Comments:**
  > **username_0**: Thank you for your explanation. I am also confused why certain arrows (not necessarily in the same state) should converge towards the same lengths. Why is this the case? is it because of the 100% exploration rate?  
  > **username_1**: This just means that they have the same Q-value. For your example this makes sense due to the symmetry of the board (ignoring the alien). For instance, If you take the two states on the top row and one to the left and right of the trophy, then you can reach the trophy in the same amount of steps (3, when acting optimally, and remember Q-learning converges to the optimal Q-values) from either state so they have the same Q-value.  
  
  ---
  
  