Answers.Body: <p>This is a consequence of the Markovian assumption, which underpins all of RL. </p>
  
  <p>The Markovian assumption says that it doesn't matter <em>how</em> we reached a given state, only <em>that</em> 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.</p>
  
  <p>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.</p>
  
  <p>Here's an example. In robot navigation, the real dynamics of the robot <em>do</em> 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 <span class="math-container">$P(S_{t+1} | S_t, a_{t}, S_{t-1}, a_{t-1} ... S_0, a_0)$</span> 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 <em>exponent</em> 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.</p>
  
  <p>To be clearer, if we assume that <span class="math-container">$P(S_{t+1} | S_t) = P(S_{t+1} | S_{t}, S_{t-i})$</span> for any <span class="math-container">$i$</span>, then the other relationships you mention should not seem surprising. That assumption <em>is</em> 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.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-04-15T19:53:39.730Z
Answers.LastActivityDate: 2019-04-15T20:12:17.390Z
Answers.LastEditDate: 2019-04-15T20:12:17.390Z
Answers.UserDisplayName: John Doucette
Body: <p>The proof of the consistency of the per-decision importance sampling estimator assumes the independence of 
  <span class="math-container">$$\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)}.$$</span> </p>
  
  <p>See the proof of Theorem 1 in "<a href="https://scholarworks.umass.edu/cgi/viewcontent.cgi?article=1079&amp;context=cs_faculty_pubs" rel="nofollow noreferrer">Eligibility Traces for Off-Policy Policy Evaluation</a>".<br>
  The result is also stated in Equation (5.14) of <a href="http://incompleteideas.net/book/the-book-2nd.html" rel="nofollow noreferrer">Sutton and Barto's RL book</a>.</p>
  
  <p>I'm guessing that this is itself a consequence of an assumption of independence between 
  <span class="math-container">$$\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})}.$$</span> </p>
  
  <p>I don't understand how this assumption can be justified. Consider the extreme case of a nearly deterministic policy <span class="math-container">$\pi$</span> and deterministic MDP dynamics. It would seem to me that the two values above are then surely <strong>not</strong> independent.</p>
  
  <p>Am I missing something?</p>
  
Tags: <reinforcement-learning><markov-decision-process><importance-sampling>
Title: Are successive actions independent?
UserDisplayName: Philip Raeisghasem
ThreadText: # Are successive actions independent?
  
  (Asked by: username_0 on 2019-04-14)
  
  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](https://scholarworks.umass.edu/cgi/viewcontent.cgi?article=1079&context=cs_faculty_pubs)".  
  The result is also stated in Equation (5.14) of [Sutton and Barto's RL book](http://incompleteideas.net/book/the-book-2nd.html).
  
  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?
  
  **Tags:** reinforcement-learning, markov-decision-process, importance-sampling
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2019-04-15. Score: 2 | Accepted answer
  
  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.
  
  
  ---
  
  