Answers.Body: <blockquote>
  <p>For now, I am still confused about the definition of on-policy. Could anyone please provide some clarification on this?</p>
  </blockquote>
  <p>Here's how Q values are updated in the SARSA algorithm:</p>
  <p><span class="math-container">$$ Q(S,A) \leftarrow Q(S,A) + \alpha\left[R + \gamma Q(S', A') - Q(S,A)\right]$$</span></p>
  <p>Now compare it to the similar update in Q-learning:</p>
  <p><span class="math-container">$$ Q(S,A) \leftarrow Q(S,A) + \alpha\left[R + \gamma \max_a Q(S', a) - Q(S,A)\right]$$</span></p>
  <p>The difference is subtle but important - the <span class="math-container">$A'$</span> action in SARSA could be a greedy action (as you mentioned <span class="math-container">$A'=\arg\max_aQ(S',a)$</span> ) bit it also could be a random action with probability <span class="math-container">$\varepsilon$</span>.</p>
  <p>So SARSA uses the <span class="math-container">$Q$</span> values from the state-action pairs that it actually followed according to <span class="math-container">$\varepsilon$</span>-greedy policy. While Q-learning follows <span class="math-container">$\varepsilon$</span>-greedy policy, but uses &quot;fully&quot; greedy policy in its updates.</p>
  <p>As a result SARSA will converge to <span class="math-container">$Q$</span> values that are optimal, but given the knowledge that agent acts randomly with probability <span class="math-container">$\varepsilon$</span>. The Q-learning, on the other hand, should converge to true optimal policy. Although that only happens if several tricky assumptions are true - most notably the &quot;<em>Greedy in the Limit with Infinite Exploration</em>&quot; (GLIE) assumption.</p>
  <p>That is, in essence, the difference between on-policy (SARSA) and off-policy (Q-learning) algorithms.</p>
  <p>You are right, though, that in SARSA the policy (both target and behavior) is constantly updated as you go through the episode. It is still considered on-policy since this &quot;non-static&quot; policy is still both the behavior policy and the target for the update.</p>
  <blockquote>
  <p>However, it does not change with time; we cannot update it, can we? Can we use the experience replay with SARSA when the policies are different per iteration?</p>
  </blockquote>
  <p>Notice that we are interested in the <em>control</em> problem -- the problem of finding an optimal policy. If all you have is experience replay episodes from some fixed policy - then optimizing your target policy inevitably means that you are doing off-policy learning.</p>
  <p>So no, on-policy control algorithms won't work with experience replay.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-04-07T13:30:43.370Z
Answers.Text: Thanks for your comment! I understand the update formulas of SARSA and $Q$-learning: with SARSA all $S,A,R,S',A'$ come from a single policy (in one iteration), while with $Q$-learning the agent tries to learn the optimal $Q$ ($\arg\max$ operator) independent with behavior policy. What I really do not understand here is the part "improve the policy that is used to make decisions", as every iteration we obtain a new behavior policy, not a "static" policy.
Answers.UserDisplayName: k2pctdn
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-04-10T08:49:58.007Z
Answers.Text: @k2pctdn You are right that the policy is constantly updated as you go through the episode. It is still considered on-policy since this "non-static" policy is still both the behavior policy and the target for the update.
Answers.UserDisplayName: Kostya
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-04-05T16:23:33.113Z
Answers.LastActivityDate: 2024-04-05T16:23:33.113Z
Answers.UserDisplayName: Kostya
Body: <p>For SARSA algorithm, assuming that we initialize all <span class="math-container">$Q(s,a)$</span> to <span class="math-container">$0$</span>, then in the first iteration, all actions are the best actions as <span class="math-container">$Q$</span> values are the same (<span class="math-container">$0$</span>). So the behavior policy in this iteration is like, with probability <span class="math-container">$1 - \varepsilon$</span>, we select an action from <span class="math-container">$\mathcal{A}(S_1)$</span> with probability <span class="math-container">$\dfrac{1}{|\mathcal{A}(S_1)|}$</span> (as all actions for this state have the same <span class="math-container">$Q$</span> values), and with probability <span class="math-container">$\varepsilon$</span>, we also select an action from <span class="math-container">$\mathcal{A}(S_1)$</span> with probability <span class="math-container">$\dfrac{1}{|\mathcal{A}(S_1)|}$</span>. Let's denote this policy as <span class="math-container">$\pi_1$</span>.
  In the second iteration and so on, the <span class="math-container">$Q$</span> values have changed. We can have fewer best actions for a certain state, so the policy <span class="math-container">$\pi_2, \pi_3, \dots$</span> is now changed. For example, the policy <span class="math-container">$\pi_n$</span> can be: with probability <span class="math-container">$1-\varepsilon$</span>, choose action <span class="math-container">$A_{n+1} = \underset{a}{\arg\max}Q(S_n,a)$</span>, and with probability <span class="math-container">$\varepsilon$</span>, we select an action from <span class="math-container">$\mathcal{A}(S_n)$</span> with probability <span class="math-container">$\dfrac{1}{|\mathcal{A}(S_n)|}$</span>.</p>
  <p><a href="https://i.sstatic.net/VWHb3.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/VWHb3.png" alt="enter image description here" /></a></p>
  <p>From Sutton's book:</p>
  <blockquote>
  <p>On-policy methods attempt to evaluate or improve the policy that is used to make decisions, whereas off-policy methods evaluate or improve a policy different from that used to generate the data.</p>
  </blockquote>
  <p>What I do not understand here is that an on-policy method tries to &quot;improve <em><strong>the policy</strong></em> that is used to make decisions,&quot;  but at different iterations, the policies are not the same. They might belong to the <span class="math-container">$\varepsilon$</span>-greedy policy class, but the operator <span class="math-container">$\underset{a}{\arg\max}$</span> can output different actions per iteration, thus leading to different <span class="math-container">$\pi_n$</span>. For now, I am still confused about the definition of on-policy. Could anyone please provide some clarification on this?</p>
  <p>At the moment, the only way of thinking that makes sense to me is that the behavior policy in SARSA is a <em>class of policy</em>, for example, the <span class="math-container">$\varepsilon$</span>-greedy policy class. As long as the value <span class="math-container">$\varepsilon$</span> does not change, and with probability <span class="math-container">$1 - \varepsilon$</span>, we choose greedy action with respect to the <span class="math-container">$Q$</span> values, we are still &quot;on-policy.&quot;</p>
  <p>Furthermore, in this <a href="https://core-robotics.gatech.edu/2022/02/28/bootcamp-summer-2020-week-4-on-policy-vs-off-policy-reinforcement-learning/" rel="nofollow noreferrer">article</a>, the author stated that:</p>
  <blockquote>
  <p>On-policy algorithms can only utilize experience replay when the behavior policy is static.</p>
  </blockquote>
  <p>From my point of view, a static policy is one that does not change with time. However, it does not change with time; we cannot update it, can we? Can we use the experience replay with SARSA when the policies are different per iteration?</p>
  
Tags: <reinforcement-learning><policies><on-policy-methods>
Title: Policy in on-policy algorithms and experience replay
UserDisplayName: k2pctdn
ThreadText: # Policy in on-policy algorithms and experience replay
  
  (Asked by: username_0 on 2024-04-05)
  
  For SARSA algorithm, assuming that we initialize all $Q(s,a)$ to $0$, then in the first iteration, all actions are the best actions as $Q$ values are the same ($0$). So the behavior policy in this iteration is like, with probability $1 - \varepsilon$, we select an action from $\mathcal{A}(S\_1)$ with probability $\dfrac{1}{|\mathcal{A}(S\_1)|}$ (as all actions for this state have the same $Q$ values), and with probability $\varepsilon$, we also select an action from $\mathcal{A}(S\_1)$ with probability $\dfrac{1}{|\mathcal{A}(S\_1)|}$. Let's denote this policy as $\pi\_1$.
  In the second iteration and so on, the $Q$ values have changed. We can have fewer best actions for a certain state, so the policy $\pi\_2, \pi\_3, \dots$ is now changed. For example, the policy $\pi\_n$ can be: with probability $1-\varepsilon$, choose action $A\_{n+1} = \underset{a}{\arg\max}Q(S\_n,a)$, and with probability $\varepsilon$, we select an action from $\mathcal{A}(S\_n)$ with probability $\dfrac{1}{|\mathcal{A}(S\_n)|}$.
  
  [![enter image description here](https://i.sstatic.net/VWHb3.png)](https://i.sstatic.net/VWHb3.png)
  
  From Sutton's book:
  
  > On-policy methods attempt to evaluate or improve the policy that is used to make decisions, whereas off-policy methods evaluate or improve a policy different from that used to generate the data.
  
  What I do not understand here is that an on-policy method tries to "improve ***the policy*** that is used to make decisions," but at different iterations, the policies are not the same. They might belong to the $\varepsilon$-greedy policy class, but the operator $\underset{a}{\arg\max}$ can output different actions per iteration, thus leading to different $\pi\_n$. For now, I am still confused about the definition of on-policy. Could anyone please provide some clarification on this?
  
  At the moment, the only way of thinking that makes sense to me is that the behavior policy in SARSA is a *class of policy*, for example, the $\varepsilon$-greedy policy class. As long as the value $\varepsilon$ does not change, and with probability $1 - \varepsilon$, we choose greedy action with respect to the $Q$ values, we are still "on-policy."
  
  Furthermore, in this [article](https://core-robotics.gatech.edu/2022/02/28/bootcamp-summer-2020-week-4-on-policy-vs-off-policy-reinforcement-learning/), the author stated that:
  
  > On-policy algorithms can only utilize experience replay when the behavior policy is static.
  
  From my point of view, a static policy is one that does not change with time. However, it does not change with time; we cannot update it, can we? Can we use the experience replay with SARSA when the policies are different per iteration?
  
  **Tags:** reinforcement-learning, policies, on-policy-methods
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2024-04-05. Score: 1
  
  > For now, I am still confused about the definition of on-policy. Could anyone please provide some clarification on this?
  
  Here's how Q values are updated in the SARSA algorithm:
  
  $$ Q(S,A) \leftarrow Q(S,A) + \alpha\left[R + \gamma Q(S', A') - Q(S,A)\right]$$
  
  Now compare it to the similar update in Q-learning:
  
  $$ Q(S,A) \leftarrow Q(S,A) + \alpha\left[R + \gamma \max\_a Q(S', a) - Q(S,A)\right]$$
  
  The difference is subtle but important - the $A'$ action in SARSA could be a greedy action (as you mentioned $A'=\arg\max\_aQ(S',a)$ ) bit it also could be a random action with probability $\varepsilon$.
  
  So SARSA uses the $Q$ values from the state-action pairs that it actually followed according to $\varepsilon$-greedy policy. While Q-learning follows $\varepsilon$-greedy policy, but uses "fully" greedy policy in its updates.
  
  As a result SARSA will converge to $Q$ values that are optimal, but given the knowledge that agent acts randomly with probability $\varepsilon$. The Q-learning, on the other hand, should converge to true optimal policy. Although that only happens if several tricky assumptions are true - most notably the "*Greedy in the Limit with Infinite Exploration*" (GLIE) assumption.
  
  That is, in essence, the difference between on-policy (SARSA) and off-policy (Q-learning) algorithms.
  
  You are right, though, that in SARSA the policy (both target and behavior) is constantly updated as you go through the episode. It is still considered on-policy since this "non-static" policy is still both the behavior policy and the target for the update.
  
  > However, it does not change with time; we cannot update it, can we? Can we use the experience replay with SARSA when the policies are different per iteration?
  
  Notice that we are interested in the *control* problem -- the problem of finding an optimal policy. If all you have is experience replay episodes from some fixed policy - then optimizing your target policy inevitably means that you are doing off-policy learning.
  
  So no, on-policy control algorithms won't work with experience replay.
  
  > **Comments:**
  > **username_0**: Thanks for your comment! I understand the update formulas of SARSA and $Q$-learning: with SARSA all $S,A,R,S',A'$ come from a single policy (in one iteration), while with $Q$-learning the agent tries to learn the optimal $Q$ ($\arg\max$ operator) independent with behavior policy. What I really do not understand here is the part "improve the policy that is used to make decisions", as every iteration we obtain a new behavior policy, not a "static" policy.  
  > **username_1**: @k2pctdn You are right that the policy is constantly updated as you go through the episode. It is still considered on-policy since this "non-static" policy is still both the behavior policy and the target for the update.  
  
  ---
  
  