Answers.Body: <p>In general on-policy Sarsa algo with your epsilon greedy behavior policy actually is the action value version of TD(0) algo, thus it has the same convergence property of TD(0) and is confirmed in the same section of your example reference:</p>
  <blockquote>
  <p>The convergence properties of the Sarsa algorithm depend on the nature of the policy’s dependence on <span class="math-container">$Q$</span>. For example, one could use &quot;<span class="math-container">$\epsilon$</span>-greedy or &quot;<span class="math-container">$\epsilon$</span>-soft policies. Sarsa converges with probability 1 to an optimal policy and action-value function, under the usual conditions on the step sizes (2.7), as long as all state–action pairs are visited an infinite number of times and the policy converges in the limit to the greedy policy</p>
  </blockquote>
  <p>In practice your learning algo may not strictly satisfy all the above mentioned theoretical stochastic convergence conditions such as the usual possibly constant learning rate and your specific problem's all state–action pairs won't be visited an infinite number of times from your mere 500 episodes. You may try to increase your episodes or epsilon values to see better convergence result. Your same reference also mentioned this practical issue yet sometimes it's even desirable:</p>
  <blockquote>
  <p>but not for the case of constant step-size parameter, <span class="math-container">$\alpha_n(a)=\alpha$</span>. In the latter case, the second condition is not met, indicating that the estimates never completely converge but continue to vary in response to the most recently received rewards. As we mentioned above, this is actually desirable in a nonstationary environment, and problems that are effectively nonstationary are the most common in reinforcement learning. In addition, sequences of step-size parameters that meet the conditions (2.7) often converge very slowly or need considerable tuning in order to obtain a satisfactory convergence rate. Although sequences of step-size parameters that meet these convergence conditions are often used in theoretical work, they are seldom used in applications and empirical research.</p>
  </blockquote>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-11-07T14:39:08.577Z
Answers.Text: Couple of things: (1) - I would like to argue that even if I increase the number of episodes to guarantee visiting all state action pairs infinite times, the algorithm won't converge because our estimate of Q value is taking random action Q into account to update the existing Q when epsilon is not decreasing. (2) - Where can I find the second reference? Could you please tell me the paragraph/page number?
Answers.UserDisplayName: Prabhjot Singh Rai
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-11-07T16:50:49.300Z
Answers.Text: Epsilon is just for exploration, as shown in my referenced answer once it's enough to converge to the greedy policy, and all state–action pairs are visited an infinite number of times satisfying (2.7), the greedy policy would converge to the optimal policy w.p. 1 which is assumed to exist and deterministic in most applications with stable environment such as yours. My 2nd reference is just around the condition (2.7) section.
Answers.UserDisplayName: cinch
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-11-08T14:13:35.050Z
Answers.Text: I think we both mean the same thing. I am trying to satisfy the condition "and the policy converges in the limit to the greedy policy" by slowly decreasing the epsilon and not dropping it directly from a given value to 0. I believe if I drop the epsilon to 0 instantaneously, even if I have explored all the states, my estimates of Q would not be the optimal (I am not converging my epsilon greedy policy to a greedy policy).
Answers.UserDisplayName: Prabhjot Singh Rai
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-11-08T19:47:50.097Z
Answers.Text: Glad to hear that we could converge so quickly with a few single-digit iterations compared to TD/Sarsa as this indicates ours may not be RL. As for the typical slow convergence of Sarsa as you observed, the off-policy Q-learning is usually better in this aspect since you can always keep an independent exploratory b-policy which is no longer constrained by a usual small conservative epsilon as specified in any epsilon-soft policies, in addition to your target.
Answers.UserDisplayName: cinch
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-11-07T06:57:37.273Z
Answers.LastActivityDate: 2023-11-07T06:57:37.273Z
Answers.UserDisplayName: cinch
Body: <p>If I create a policy using the q-values of an epsilon greedy policy using the Sarsa algorithm (not changing the epsilon with each episode), will it converge to the optimal solution to the MDP? I am observing that sometimes it does not. Specifically, example 6.5 in Introduction to RL by Sutton and Barto, when I run Sarsa for 500 episodes and form a greedy policy (no exploration after 500 episodes) using the Q-values of epsilon greedy policy, I am getting different results. Is the reason for suboptimal solution that we are converging the Q values to the estimates of next state action which could be random in case of epsilon greedy (with no epsilon decay)?</p>
  <p>Here are the two greedy policies (from epsilon greedy policy iterated for 500 episodes) with two different runs of Sarsa:</p>
  <p><a href="https://i.sstatic.net/JjI8q.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/JjI8q.png" alt="Policy 1" /></a>
  <a href="https://i.sstatic.net/6ENMq.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/6ENMq.png" alt="Policy 2" /></a></p>
  
Tags: <reinforcement-learning><temporal-difference-methods><sarsa>
Title: Convergence of epsilon greedy policy (with no epsilon decay) using TD Learning?
UserDisplayName: Prabhjot Singh Rai
ThreadText: # Convergence of epsilon greedy policy (with no epsilon decay) using TD Learning?
  
  (Asked by: username_0 on 2023-11-04)
  
  If I create a policy using the q-values of an epsilon greedy policy using the Sarsa algorithm (not changing the epsilon with each episode), will it converge to the optimal solution to the MDP? I am observing that sometimes it does not. Specifically, example 6.5 in Introduction to RL by Sutton and Barto, when I run Sarsa for 500 episodes and form a greedy policy (no exploration after 500 episodes) using the Q-values of epsilon greedy policy, I am getting different results. Is the reason for suboptimal solution that we are converging the Q values to the estimates of next state action which could be random in case of epsilon greedy (with no epsilon decay)?
  
  Here are the two greedy policies (from epsilon greedy policy iterated for 500 episodes) with two different runs of Sarsa:
  
  [![Policy 1](https://i.sstatic.net/JjI8q.png)](https://i.sstatic.net/JjI8q.png)
  [![Policy 2](https://i.sstatic.net/6ENMq.png)](https://i.sstatic.net/6ENMq.png)
  
  **Tags:** reinforcement-learning, temporal-difference-methods, sarsa
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2023-11-07. Score: 1
  
  In general on-policy Sarsa algo with your epsilon greedy behavior policy actually is the action value version of TD(0) algo, thus it has the same convergence property of TD(0) and is confirmed in the same section of your example reference:
  
  > The convergence properties of the Sarsa algorithm depend on the nature of the policy’s dependence on $Q$. For example, one could use "$\epsilon$-greedy or "$\epsilon$-soft policies. Sarsa converges with probability 1 to an optimal policy and action-value function, under the usual conditions on the step sizes (2.7), as long as all state–action pairs are visited an infinite number of times and the policy converges in the limit to the greedy policy
  
  In practice your learning algo may not strictly satisfy all the above mentioned theoretical stochastic convergence conditions such as the usual possibly constant learning rate and your specific problem's all state–action pairs won't be visited an infinite number of times from your mere 500 episodes. You may try to increase your episodes or epsilon values to see better convergence result. Your same reference also mentioned this practical issue yet sometimes it's even desirable:
  
  > but not for the case of constant step-size parameter, $\alpha\_n(a)=\alpha$. In the latter case, the second condition is not met, indicating that the estimates never completely converge but continue to vary in response to the most recently received rewards. As we mentioned above, this is actually desirable in a nonstationary environment, and problems that are effectively nonstationary are the most common in reinforcement learning. In addition, sequences of step-size parameters that meet the conditions (2.7) often converge very slowly or need considerable tuning in order to obtain a satisfactory convergence rate. Although sequences of step-size parameters that meet these convergence conditions are often used in theoretical work, they are seldom used in applications and empirical research.
  
  > **Comments:**
  > **username_0**: Couple of things: (1) - I would like to argue that even if I increase the number of episodes to guarantee visiting all state action pairs infinite times, the algorithm won't converge because our estimate of Q value is taking random action Q into account to update the existing Q when epsilon is not decreasing. (2) - Where can I find the second reference? Could you please tell me the paragraph/page number?  
  > **username_1**: Epsilon is just for exploration, as shown in my referenced answer once it's enough to converge to the greedy policy, and all state–action pairs are visited an infinite number of times satisfying (2.7), the greedy policy would converge to the optimal policy w.p. 1 which is assumed to exist and deterministic in most applications with stable environment such as yours. My 2nd reference is just around the condition (2.7) section.  
  > **username_0**: I think we both mean the same thing. I am trying to satisfy the condition "and the policy converges in the limit to the greedy policy" by slowly decreasing the epsilon and not dropping it directly from a given value to 0. I believe if I drop the epsilon to 0 instantaneously, even if I have explored all the states, my estimates of Q would not be the optimal (I am not converging my epsilon greedy policy to a greedy policy).  
  > **username_1**: Glad to hear that we could converge so quickly with a few single-digit iterations compared to TD/Sarsa as this indicates ours may not be RL. As for the typical slow convergence of Sarsa as you observed, the off-policy Q-learning is usually better in this aspect since you can always keep an independent exploratory b-policy which is no longer constrained by a usual small conservative epsilon as specified in any epsilon-soft policies, in addition to your target.  
  
  ---
  
  