I'm reading the public draft (pdf) of the 2nd edition of Sutton&Barto's RL Book.

There are a few things I don't understand about the Off-policy n-step Sarsa method described in the book. You can find the pseudo-code at page 159 (177) of the pdf I linked above.

Here's a picture of the pseudo-code for your convenience:

enter image description here

Here are the 3 things I don't understand:

  1. $\rho$ considers the actions $A_{\tau+1},\ldots,A_{\tau+n-1}$. Shouldn't it also consider $A_{\tau+n}$?
  2. In the third to last line, $\rho$ multiplies both $G$ and $Q(S_\tau,A_\tau)$. Shouldn't it multiply just $G$?
  3. The second to last line says that $\pi$, if being learned, must be $\epsilon$-greedy wrt $Q$ (with $\epsilon>0$). I don't understand the reason of this restriction. Can't $\pi$ be greedy just like in Q Learning? The exploration is already taken care of by $\mu$.
  • $\begingroup$ Regarding point 2, I am having the same doubt, I actually asked the question before I found yours: ai.stackexchange.com/questions/11676/… $\endgroup$ Commented Apr 5, 2019 at 14:31
  • $\begingroup$ I even messaged Rich Sutton, hopefully we get an answer. $\endgroup$ Commented Apr 5, 2019 at 14:31
  • $\begingroup$ Were you able to clarify the question (since you asked yourself the same question two years ago :)? $\endgroup$ Commented Apr 5, 2019 at 14:32
  • $\begingroup$ With respect to question 2, both formulas would be correct as $\mathbf{E}[\rho]=1$... $\endgroup$ Commented Dec 9, 2020 at 16:32

2 Answers 2


1) Aτ+n is omitted since it is the state at horizon for the n-step update and estimated value for its action-value will be used so weighting by its importance ratio is skipped.

2) I was wondering the same - it even makes my action-values to grow to infinity(with rewards -1.0 for all steps and 1.0 for goal reached). My implementation for n-Step Q(σ) estimation works fine with σ=1 matching the n-Step Tree Backup as expected but for σ=0 it reproduces the same problem with non-stop growing state-action-values as in the simple Off-Policy n-Step Sarsa.

3) If it is deterministic greedy then all its action probabilities for a given state will be 0 instead of the greedy action(for which will be 1.0) and thus the importance ratio product will be non-zero only when the actions chosen by the behavior policy will match the greedy policy - I don't think this will help exploration.


The original poster is correct on the first and third points. These have long since been corrected in the latest versions of the book. On the second point, Erwan Le Pennec is correct. The rho can appear in either place, essentially because E[rho] is 1. Because Q is uncorrelated with rho, you can insert a rho in front of the Q without changing the expected value. Then you can bring the rho out to the front. It does not change the expected value, but it will normally reduce the variance to position rho in front as written.

Please see http://www.incompleteideas.net/book/errata.html for other errata.


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.