# Policy in on-policy algorithms and experience replay

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)|}$$.

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, 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?

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.

• 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. Commented Apr 7 at 13:30
• @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. Commented Apr 10 at 8:49