3
$\begingroup$

After reading several questions here and browsing some pages on the topic, here is my understanding of the key difference between Q-learning (as an example of off-policy) and SARSA (as an example of on-policy) methods. Please correct me if I am misled.

1) With an on-policy algorithm we use the current policy (a regression model with weights W, and ε-greedy selection) to generate the next state's Q.

2) With an off-policy algorithm we use a greedy version of the current policy to generate the next state's Q.

3) If an exploration constant ε is set to 0, then the off-policy method becomes on-policy, since Q is derived using the same greedy policy.

4) However, on-policy method uses one sample to update the policy, and this sample comes from on-line world exploration since we need to know exactly which actions the policy generates in current and next states. While off-policy method may use experience replay of past trajectories (generated by different policies) to use a distribution of inputs and outputs to the policy model.

enter image description here

Source: https://courses.engr.illinois.edu/cs440/fa2009/lectures/Lect24.pdf

One more reading: http://mi.eng.cam.ac.uk/~mg436/LectureSlides/MLSALT7/L3.pdf

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

1) With an on-policy algorithm we use the current policy (a regression model with weights W, and ε-greedy selection) to generate the next state's Q.

Yes. To avoid confusion, it may be better to use the terms "behaviour policy" for the the policy that controls current actions and "target policy" for the policy being evaluated and/or learned.

2) With an off-policy algorithm we use a greedy version of the current policy to generate the next state's Q.

Sort of. The only requirement for an algorithm to be off-policy is that the target policy is different to the behaviour policy. The usual target policy in Q-learning is not necessarily a greedy version of the behaviour policy, but is the maximising policy over Q. However, if the behaviour policy is ε-greedy over Q, and adapting to updates in Q, then yes your statement holds.

3) If an exploration constant ε is set to 0, then the off-policy method becomes on-policy, since Q is derived using the same greedy policy.

This is true when comparing SARSA with Q learning, but may not hold when looking at other algorithms. This greedy-only action selection would not be a very efficient learner in all environments.

4) However, on-policy method uses one sample to update the policy, and this sample comes from on-line world exploration since we need to know exactly which actions the policy generates in current and next states. While off-policy method may use experience replay of past trajectories (generated by different policies) to use a distribution of inputs and outputs to the policy model.

Experience replay is not directly related to on-policy vs off-policy learning. Technically though, yes when the experience is stored and used later, that makes it off-policy for SARSA if Q values have changed enough between the sample and current parameters of the learning agent.

However, you will see experience replay used more often with off-policy methods, since off-policy learners that boot-strap (i.e. use Q value of next state/action to help estimate current Q value) are less stable when used with function approximators. Experience replay helps to address that problem.

Improve this answer
$\endgroup$
5
  • $\begingroup$ thank you! Could you please clarify one point? "Experience replay is about online vs offline methods, and not directly related to on-policy vs off-policy learning." If we use an experience replay with SARSA as an on-policy method, don't we mess up actions that must follow both state_1 and state_2 (current and next), rewards that are attribute of taking these actions using the current behaviour policy, with those actions and rewards that resulted from past learned policies stored in an experience replay buffer? Doesn't it make the method off-policy? $\endgroup$
    – Alexey Burnakov
    Commented Jan 10, 2018 at 12:54
  • 1
    $\begingroup$ Yes it gets more complex, and my answer skates over that issue. If you use experience replay with SARSA you can either store the full S, A, R, S', A' for each step (as opposed to Q-learning), which is technically history of on-policy decisions but may be off-policy wrt to current Q values, or you can re-generate the choice of A' based on current Q which is off-policy wrt to stored data but on-policy wrt the learning algorithm. Both are technically off-policy I suppose, but both will work - a reasonable compromise is to keep a more limited history so that the policies diverge less. $\endgroup$
    – Neil Slater
    Commented Jan 10, 2018 at 13:26
  • 1
    $\begingroup$ @AlexeyBurnakov: I have adjusted my answer, to be a little less assertive about the experience replay, because it kind of lives in an in-between area where you can compare it to online vs offline and on-policy vs off-poilcy, but in general it can be used to interpolate between those things depending on how it is used. $\endgroup$
    – Neil Slater
    Commented Jan 10, 2018 at 13:31
  • $\begingroup$ thank you! With respect to the Experience Replay, I have been thinking of any notion of the regenerating A or A', as well as R in major papers like DeepMind's, but did not recall any, so I believe that a common approach was to get Q' (A') for a batch of examples using the current policy while using R, and S' from the old policies. Besides, storing A' in the replay buffer is also not so common (I learned it from you only). On the other hand reproducing: A, R, S', A' for the batch of examples may be expensive. It looks like the replay described so far is a trade-off of some sort? $\endgroup$
    – Alexey Burnakov
    Commented Jan 10, 2018 at 14:05
  • 1
    $\begingroup$ The DQN in Deep Mind's Atari paper does store S, A, R, S' then re-generate Q(S', A') for all A' in order to find $max_{a'} \hat{q}(S', a')$ for the update TD Target. I don't think you will see many SARSA variants with experience replay, because you also have to fiddle with decaying $\epsilon$ when looking for an optimal solution. However, SARSA does have some advantages over Q-learning depending on the problem. $\endgroup$
    – Neil Slater
    Commented Jan 10, 2018 at 20:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.