0
$\begingroup$

In the Reinforcement Learning book (Prof. Sutton et al.) the authors explain a few basic algorithms of Reinforcement Learning. A particular kind of algorithms called n-step Temporal Difference Learning algorithms use the following formula for their updates for actions-value function:

$$ Q_{t+n}(S_t,A_t) = Q_{t+n-1}(S_t,A_t) + \alpha \rho(G_{t:t+n} - Q_{t+n-1}(S_t,A_t)) $$ where $$ \textrm{for ordinary SARSA:} \quad$$ $$ G_{t:t+n} = \sum_{k=t}^{min(t+n,T)-1} \gamma^{k-t} R_{t+1} + \gamma^n Q_{t+n-1}(S_{t+n},A_{t+n}) $$ $$\\ \rho = \prod_{k=t+1}^{min(t+n,T)-1}\frac{\pi(A_k|S_k)}{ b(A_k|S_k)} $$ $$\textrm{ for Expected SARSA:} \quad$$ $$ G_{t:t+n} = \sum_{k=t}^{min(t+n,T)-1} \gamma^{k-t} R_{t+1} + \gamma^n \sum_{a}{\pi(a|S_{t+n})Q_{t+n-1}(S_{t+n}, a)} $$

$$\rho = \prod_{k=t+1}^{min(t+n-1,T)-1}\frac{\pi(A_k|S_k)}{ b(A_k|S_k)} $$

Although the authors do a very good job explaining the algorithms, there is still something that escapes from my understanding. What is the rationale for the different time limits for Importance Sampling ratio expression $\rho: \{t+1,\dots,t+n-1\}$ and $\rho: \{t+1,\dots,t+n-2\}$?

Importance sampling as I could understand would compensate the fact of sampling from a different distribution by factoring the return by relative probability of observing the experience sequence (only as far as the rewards were sampled) under target and behaviour policy. As the effective actions sampled for a state-action pair $S_t,A_t$ for n-step SARSA and Expected SARSA are the same (meaning the actions that were used to generate rewards), the only difference between them is the way they use estimates of $Q_{t+n}$.

But how one would understand the difference of the involved importance samling rations $\rho: \{t+1,\dots,t+n-1\}$ and $\rho: \{t+1,\dots,t+n-2\}$ when the both algorithms use the same experience for their updates?

Even if we assume that the last step $A_{t+n}$ in the Expected SARSA should not count in the $\rho$ formula, then that would only affect the factor $\frac{\pi(A_{t+n}|S_{t+n})}{ b(A_{t+n}|S_{t+n})}$, and not the one with $t+n-1$ that was removed.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Those are two quite involved questions. Although they are related, I find that I can answer Q2 easily enough, but not Q1, so putting them together here means I cannot answer. $\endgroup$
    – Neil Slater
    Mar 28, 2018 at 19:17
  • $\begingroup$ @NeilSlater I have modified the question, so that only the second part is left. Hope you could share your understanding of the subject, even if that will be only some intuitive hints. Thanks $\endgroup$
    – avenir
    Mar 28, 2018 at 21:10

1 Answer 1

Reset to default
1
$\begingroup$

As the effective actions sampled for a state-action pair $S_t,A_t$ for n-step SARSA and Expected SARSA are the same (meaning the actions that were used to generate rewards)

That's where you are wrong.

The sampling in regular SARSA continues into the final step using the behaviour policy $b$ and thus to get an estimate from the correct distribution* you need importance sampling.

In Expected SARSA, the last step doesn't sample, it is a sum over all possible actions, and the sum is weighted over the target policy, $\pi$, not the behaviour policy, and as a result already gives an estimate from the correct distribution. Therefore, there is no need to correct probabilities from $b$ to $\pi$ because you are already using $\pi$.

* "Correct" from the point of view of bootstrapped Q values, which are themselves biased estimates of value function, but that's not the point here, the Q values are biased estimates of $q_{\pi}(s,a)$ not of $q_{b}(s,a)$

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thank you for your answer. I intentially said that SARSA samples the same set of actions, while it is straightforward from the algorithm that it samples an extra action to just bootstrap towards the $Q$ value of the next state, but this is at time step $t+n$. The problem with IS-ratio is still there, because those actions at time step $t+n$ are not used for its calculation in both algorithms, the one that is discarded in Expected SARSA is $t+n-1$. And this action is related to generating experience (by definition) in both algorithms, and as I understand should be included in both IS-ratios. $\endgroup$
    – avenir
    Mar 29, 2018 at 8:13
  • $\begingroup$ @monsieur-tout-le-monde: The actions at t+n are used in both algorithms to estimate the value of the action at t+n-1 (from its Bellman equation form related to action at t+n). The substitution with the estimate is why the formulae only sum to t+n-1 then have the additional term (calculated from t+n, but giving value of action at t+n-1). In off-policy SARSA, this estimate will be sampled using $b$. In Expected SARSA, this estimate will be sampled using $\pi$ . . . so Expected SARSA does indeed drop the importance sampling ratio at t+n-1 $\endgroup$
    – Neil Slater
    Mar 29, 2018 at 8:49
  • $\begingroup$ Thank you for taking your time to respond. But I would disagree with your explanation. The easiest way to see where the problem lies is to note that action $A_{t+n-1}$ in both algorithms is sampled from behaviour policy. And the imidiate reward following that action (and that probabilistically conditioned by this action) is used in both algorithms in explicit form in the target, not as an implicit element of estimation $Q(S_{t+n},A_{t+n})$. In one algorithm the experience is corrected for this action, in the other is not. $\endgroup$
    – avenir
    Mar 29, 2018 at 11:35
  • $\begingroup$ Yes the action to score is sampled t+n-1 from behaviour, but the correction to its value (estimate of continuing G to terminal state or forever, discounted) is taken from the succeeding evaluation at t+n. Sorry you disagree with my explanation, but I believe it to be correct, so will leave the answer as-is $\endgroup$
    – Neil Slater
    Mar 29, 2018 at 11:47

Your Answer

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

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