What is the equation for action-value Q(s,a) in Monte Carlo Off-policy Prediction problem?

Question

This is a question (Exercise 5.6) from Page 108 in Sutton's RL book (2nd edition). In Chapter 5, the authors mentioned that the state value function after importance-scaling is given by the following:

$$ V(s) \doteq \frac{\sum_{t\in\mathcal{T(s)}} \rho_{t:T(t)-1}G_t}{\sum_{t\in\mathcal{T(s)}} \rho_{t:T(t)-1}} $$

The question asks for an equation analogous to the above equation but for action-value $Q(s,a)$ given returns generated using the behavior policy $b$.

While some people were kind enough to share their answers on Github: $$ Q(s,a) \doteq \frac{\sum_{t\in\mathcal{T(s,a)}} \rho_{t+1:T(t)-1}G_t}{\sum_{t\in\mathcal{T(s,a)}} \rho_{t+1:T(t)-1}} $$

But I couldn't figure this out. Why does $\rho$ starts from $t+1$ in $Q(s,a)$?

I appreciate if you could explain this to me, thanks!

Answer 1

Why does $\rho$ starts from $t+1$ in $Q(s,a)$?

In general, when accounting for any stochastic effect in estimates of value functions in reinforcement learning, you need to pay attention to which random elements you have already conditioned on.

When you are estimating $Q(s_t,a_t)$ then you are looking at all the events that happen after choosing $a_t$. It does not matter at that point which policy chose the action in time step $t$, so there is no need to correct for probability ratios between behaviour and target policy. This is unlike estimates for $V(s_t)$ where you do care about differences in policy affecting which action will happen on time step $t$.

The target policy could have a probability of zero for selecting $a_t$, and you can still update your estimate of $Q(s_t,a_t)$ - if this were not possible then the agent could never learn about alternative actions to the greedy policy.

Single-step Q learning is an interesting case where because you have already conditioned on the action $a_t$ at time step $t$ and are using the target policy (greedy action choice) to establish $a_{t+1}$ at time step $t+1$, then there is no need to use importance sampling.