Are successive actions independent?

Question

The proof of the consistency of the per-decision importance sampling estimator assumes the independence of $$\frac{\pi(A_t|S_t)}{b(A_t|S_t)}R_{t+1}\quad\text{ and }\quad \prod_{k=t+1}^{T-1}\frac{\pi(A_k|S_k)}{b(A_k|S_k)}.$$

See the proof of Theorem 1 in "Eligibility Traces for Off-Policy Policy Evaluation".
The result is also stated in Equation (5.14) of Sutton and Barto's RL book.

I'm guessing that this is itself a consequence of an assumption of independence between $$\frac{\pi(A_t|S_t)}{b(A_t|S_t)}\quad\text{ and }\quad \frac{\pi(A_{t+1}|S_{t+1})}{b(A_{t+1}|S_{t+1})}.$$

I don't understand how this assumption can be justified. Consider the extreme case of a nearly deterministic policy $\pi$ and deterministic MDP dynamics. It would seem to me that the two values above are then surely not independent.

Am I missing something?

Answer 1

This is a consequence of the Markovian assumption, which underpins all of RL.

The Markovian assumption says that it doesn't matter how we reached a given state, only that we reached it, when deciding how likely it is that we move to subsequent states. This naturally implies that our choice of actions must also depend only on the current state.

You are correct that the assumption is somewhat unrealistic. However, it usually can be made to yield a reasonable approximation of the true dynamics without involving too many state variables. By solving this approximation, we hope to find a policy that also works well in the real problem.

Here's an example. In robot navigation, the real dynamics of the robot do depend on where the robot has been in the past, because as the robot's battery drains, the voltage levels it outputs will change slightly, and its wheels may become more prone to slippage. Thus, logically, our choice of action should change based on both the current state and our choice of actions in previous states (which drained the battery to a greater or lesser degree). However, if we try to incorporate this into the model, we'll end up having a combinatorial explosion in size of the dynamics function $P(S_{t+1} | S_t, a_{t}, S_{t-1}, a_{t-1} ... S_0, a_0)$ that actually captures this process (in particular, it will now be a function of 2t inputs). This, in turn, will necessitate a combinatorial blowup in the complexity of our policy (it will increase in complexity by an exponent of 2t). To keep things tractable, we accept that the dynamics will become lossy, or we can add some extra detail to the local state (e.g. a battery level) to capture the more complex dynamics in a Markovian way. Either way though, we'll be back to a world where future actions won't depend on past ones.

To be clearer, if we assume that $P(S_{t+1} | S_t) = P(S_{t+1} | S_{t}, S_{t-i})$ for any $i$, then the other relationships you mention should not seem surprising. That assumption is the Markovian assumption. It converts the state transition function into a Matrix that represents a Markov Chain. If we don't make that assumption, then most RL algorithms do not apply to our problem.