1
$\begingroup$

I want to clarify I have understood how SARSA works in nuances. Consider an original definition taken from ON-LINE Q-LEARNING USING CONNECTIONIST SYSTEMS. G. A. Rummery & M. Niranjan. CUED/F-INFENG/TR 166. September 1994 (which is the first publication where SARSA wss mentioned, according to a Wikipedia article).

The authors proposed an update rule which "... differs from normal Q-learning in the use of the Qt+1 associated with the action selected, rather than the greedy max(Qt+1 | a) used in Q-learning." (A citation from page 6.)

Please note that this is essential to on-policy nature of the algorithm. The term SARSA mentioned in the footnote for this definition.

And a later pseudo-code of SARSA update used in many readings:

begin

  initialize Q[S,A] arbitrarily
  observe current state s
  select action using a policy based on Q

repeat forever:

carry out an action a
observe reward r and state s'
select action a' using a poicy based on Q
Q[s,a] <- Q[s,a] + alpha * (r + gamma * Q[s', a'] - Q[s, a])
s <- s'
a <- a'

end-repeat

end

source: http://www.cse.unsw.edu.au/~cs9417ml/RL1/algorithms.html

I want to understand if I must use exactly the same Q function (and policy) to get A and A'. If I update Q function in each iteration, it follows that the next action in a subsequent iteration will be derived using the latest Q updated, while the previous action was obtained using the former Q.\ On the other hand, I really can make A and A' with exactly the same Q, and only after that update the Q. So I will always consider A and A' derived using the same function.

Which is more orthodox / correct?

$\endgroup$
2
  • $\begingroup$ @NeilSlater, I corrected my answer, removing images. $\endgroup$ Commented Feb 2, 2018 at 12:18
  • $\begingroup$ @NeilSlater, I don't want to be misunderstood here. I am asking exactly about on-policy algorithm (not trying to make comparison between off-line and online realizations). The way that SARSA workflow is presented makes some room for interpretation of whether one should use exactly the same Q function (e.g., a neural network) to get both A and A'. As I wrote in my question, It is not clear that besides using the same (e-greedy) behaviour policy as an estimation policy, the policy should also be based on the same Q-function or not. $\endgroup$ Commented Feb 2, 2018 at 12:22

1 Answer 1

1
$\begingroup$

I want to understand if I must use exactly the same Q function (and policy) to get A and A'. If I update Q function in each iteration, it follows that the next action in a subsequent iteration will be derived using the latest Q updated, while the previous action was obtained using the former Q.\ On the other hand, I really can make A and A' with exactly the same Q, and only after that update the Q. So I will always consider A and A' derived using the same function.

Which is more orthodox / correct?

The algorithm pseudocode given is more orthodox, since in order to revise the value of $A$ you would have to "roll back" the environment and see where the newly-sampled $A$ would take you from state $S$. To make this clearer, you can see that:

select action a' using a policy based on Q

could be re-phrased:

select action a' by sampling epsilon-greedy function over Q(s',*)

. . . you cannot do that unless you have the value of $S'$, and you may only have that value if you have already taken action $A$ when in state $S$. Changing $A$ at that stage therefore means going back in time . . .

In practice it doesn't matter much, even if you have capability to roll back (in a simulator, or in a planning algorithm). If your policy is based on e.g. $\epsilon$-greedy over the current Q values, then you are performing SARSA for optimal control (as opposed to prediction). In that case, changing Q means changing the policy. "On-policy" in SARSA for control must allow for the non-stationarity of the policy. Occasionally that means that the $A'$ value you just chose would have been chosen with a lower probability in a more optimal policy. But you chose it anyway this time, and the agent should choose it less often in future. The learning-rate based updates will remove estimation bias due to earlier poor/too-frequently-sampled choices over time.

Revising a single step "mistake" is possible, but not common practice in a purely online algorithm. I have not seen it in planning look-ahead or offline algorithms either that I have studied. I don't know for certain, but I suspect the occasional boost to learning you might get from revising the immediate part of the trajectory is too small to be worth the loss of generality of the algorithm. You may find it does help sometimes though, and worth an experiment to review whether it is helpful, provided you are working with a simulator/planner where rolling back state is relatively easy.


Note that the way you are thinking does turn up again when using function approximators (e.g. linear functions or neural networks) in semi-gradient versus "true gradient" methods, where instead of this being an issue with which Q values to use, it is an issue with calculating gradients due to the TD error, when your TD target is based on the same parameters that you are are taking the gradient for. In semi-gradient methods, this issue is ignored, and the methods still work OK. However, the "true gradient" methods are more theoretically correct.

$\endgroup$
8
  • $\begingroup$ Thank you! It is a bit over my head, but is it about right that the following is a normal practice: (note that I start with 'next') 1) from S' take A' based on π(Q) (behaviour policy), observe associated Q; draw previous iteration's data from a very small buffer (one-step back size): S, A, R; update Q; transit S' -> S, A' -> A. 2) Iterate to get new S', A' (using updated Q). This way a logical purity of the true on-policy goes away, since the new A' is based on the updated Q (hence the new Q value). $\endgroup$ Commented Feb 2, 2018 at 13:28
  • $\begingroup$ Another way to go: get S, take A, get R, move to S', take A'; now observe Q value and update the Q. Iterate over environment without updating Q unless a new set of S, A, R, S', A' emerge based on the same π(Q). Thus Q updating is to be done every 3 iterations of the call to the environment for reward. $\endgroup$ Commented Feb 2, 2018 at 13:31
  • 1
    $\begingroup$ @AlexeyBurnakov: For first idea, yes you could use an "experience replay" off-policy approach, but this will have a lot of the problems of off-policy (higher variance, poor quality bootstrapping from states that you may not of visited yet) without aiming directly for an optimal policy such as with Q-Learning. $\endgroup$ Commented Feb 2, 2018 at 13:47
  • 1
    $\begingroup$ @AlexeyBurnakov: I'm not sure I fully understand the second idea, but it seems to want to preserve the "purity" of on-policy decision making by discarding every other data point. I think the cost/benefit of this is not good. Also, if states occur in any regular structure, you may have a systematic failure to learn from them as would be effectively sampling every other TD target. $\endgroup$ Commented Feb 2, 2018 at 13:51
  • 1
    $\begingroup$ The first approach is off-policy since you are looking at choices that you made under an older version of the policy. You can get most recent Q values for Q(S,A) and Q(S',A'), but your value for A (and therefore S') will be chosen with probability according to what the old Q value was. $\endgroup$ Commented Feb 2, 2018 at 13:58

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.