Policy in on-policy algorithms and experience replay

Question

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?

Answer 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.