Answers.Body: <p>The Markov assumption is used when deriving the Bellman equation for state values:</p>
  <p><span class="math-container">$$v(s) = \sum_a \pi(a|s)\sum_{r,s'} p(r,s'|s,a)(r + \gamma v(s'))$$</span></p>
  <p>One requirement for this equation to hold is that <span class="math-container">$p(r,s'|s,a)$</span> is consistent. The current state <span class="math-container">$s$</span> is a key argument of that function. There is no adjustment for history of previous states, actions or rewards. This is the same as requiring the Markov trait for state, i.e. that <span class="math-container">$s$</span> holds all information necessary to predict outcome probabilities of the next step.</p>
  <p>The one step TD target that is sampled in basic TD learning is simply the inner part of this:</p>
  <p><span class="math-container">$$G_{t:t+1} = R_{t+1} + \gamma \hat{v}(S_{t+1})$$</span></p>
  <p>which when sampled is equal to <span class="math-container">$v(s)$</span> in <em>expectation</em> *, when <span class="math-container">$S_t = s$</span>. That is, when you measure a single instance of the TD target and use it to update a value function, you implicitly assume that the values or <span class="math-container">$r_{t+1}$</span> and <span class="math-container">$s_{t+1}$</span> that you observed occur with probabilities determined by <span class="math-container">$\pi(a|s)$</span> and <span class="math-container">$p(r,s'|s,a)$</span> as shown by the Bellman equation.</p>
  <p>So the theory behind TD learning uses the Markov assumption, otherwise the sampled TD targets would be incorrect.</p>
  <p>In practice you can get away with slightly non-Markov environments - most measurements of state for machinery are approximations that ignore details at some level, for instance, and TD learning can solve optimal control in many robotics environments. However, Monte Carlo methods are more robust against state representations that are not fully Markov.</p>
  <hr />
  <p>* Technically this sample is biased because <span class="math-container">$\hat{v}(S_{t+1})$</span> is not correct when learning starts. The bias reduces over time and multiple updates. So the expected value during learning is <em>approximately</em> the same as the true value as shown by the Bellman equation.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-08-09T05:52:59.110Z
Answers.Text: If we're working in the domain of deterministic policies, we don't have to worry about the expectation of the TD target, right? I suppose in that case the expectation of the TD target would equal itself. Please correct me if I'm wrong!
Answers.UserDisplayName: stoic-santiago
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-08-09T05:55:05.817Z
Answers.Text: If the statement mentioned in the comment above is right, would we still require the Markov assumption for TD learning in the case of deterministic policies?
Answers.UserDisplayName: stoic-santiago
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-08-09T08:53:29.677Z
Answers.Text: @cogito_ai No, both the first statement is wrong, and your suggestsed consequence in the second statement. For the first statement, the environment would also need to be deterministic before a single sample of the TD target was also guaranteed equal to the expected TD target. To answer the second comment, even in that case you need the Markov assumption - if the Markov asumption is broken, then one or both $s'$ or $r$ could be arbitrarily different when starting from the same state, so any TD target would be wrong, even one generated over many samples.
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-05-29T00:21:54.317Z
Answers.Text: A beautiful answer! I think the critical intuition here is this: While $Q$-learning and other TD methods are model-free, they still leverage Markovity through the consistence of the Bellman equation (which means we can sample our TD targets properly)!
Answers.UserDisplayName: FountainTree
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-08-07T08:34:44.840Z
Answers.LastActivityDate: 2020-08-07T15:34:24.030Z
Answers.LastEditDate: 2020-08-07T15:34:24.030Z
Answers.UserDisplayName: Neil Slater
Body: <p>One of my friends and I were discussing the differences between Dynamic Programming, Monte-Carlo, and Temporal Difference (TD) Learning as policy evaluation methods - and we agreed on the fact that <strong>Dynamic Programming</strong> <strong>requires</strong> the Markov assumption while <strong>Monte-Carlo</strong> policy evaluation does <strong>not</strong>.</p>
  <p>However, he also pointed out that <strong>Temporal Difference Learning cannot handle non-Markovian domains</strong>, i.e. it depends on the Markov assumption. Why is it so?</p>
  <p>The way I understand it, the TD learning update is, in essence, the same as the Monte-Carlo update, except for the fact that the return instead of being calculated using the entire trajectory, is bootstrapped from the previous estimate of the value function, i.e. we can update the value as soon as we encounter a <span class="math-container">$(s,a,r,s')$</span> tuple, we don't have to wait for the episode (if finite) to terminate.</p>
  <p><strong>Where is the <em>Markov assumption</em> being used here, i.e the <em>future is independent of the past given the present</em>?</strong></p>
  
Tags: <reinforcement-learning><monte-carlo-methods><temporal-difference-methods><markov-property><dynamic-programming>
Title: Why does TD Learning require Markovian domains?
UserDisplayName: stoic-santiago
ThreadText: # Why does TD Learning require Markovian domains?
  
  (Asked by: username_0 on 2020-08-07)
  
  One of my friends and I were discussing the differences between Dynamic Programming, Monte-Carlo, and Temporal Difference (TD) Learning as policy evaluation methods - and we agreed on the fact that **Dynamic Programming** **requires** the Markov assumption while **Monte-Carlo** policy evaluation does **not**.
  
  However, he also pointed out that **Temporal Difference Learning cannot handle non-Markovian domains**, i.e. it depends on the Markov assumption. Why is it so?
  
  The way I understand it, the TD learning update is, in essence, the same as the Monte-Carlo update, except for the fact that the return instead of being calculated using the entire trajectory, is bootstrapped from the previous estimate of the value function, i.e. we can update the value as soon as we encounter a $(s,a,r,s')$ tuple, we don't have to wait for the episode (if finite) to terminate.
  
  **Where is the *Markov assumption* being used here, i.e the *future is independent of the past given the present*?**
  
  **Tags:** reinforcement-learning, monte-carlo-methods, temporal-difference-methods, markov-property, dynamic-programming
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2020-08-07. Score: 7 | Accepted answer
  
  The Markov assumption is used when deriving the Bellman equation for state values:
  
  $$v(s) = \sum\_a \pi(a|s)\sum\_{r,s'} p(r,s'|s,a)(r + \gamma v(s'))$$
  
  One requirement for this equation to hold is that $p(r,s'|s,a)$ is consistent. The current state $s$ is a key argument of that function. There is no adjustment for history of previous states, actions or rewards. This is the same as requiring the Markov trait for state, i.e. that $s$ holds all information necessary to predict outcome probabilities of the next step.
  
  The one step TD target that is sampled in basic TD learning is simply the inner part of this:
  
  $$G\_{t:t+1} = R\_{t+1} + \gamma \hat{v}(S\_{t+1})$$
  
  which when sampled is equal to $v(s)$ in *expectation* \*, when $S\_t = s$. That is, when you measure a single instance of the TD target and use it to update a value function, you implicitly assume that the values or $r\_{t+1}$ and $s\_{t+1}$ that you observed occur with probabilities determined by $\pi(a|s)$ and $p(r,s'|s,a)$ as shown by the Bellman equation.
  
  So the theory behind TD learning uses the Markov assumption, otherwise the sampled TD targets would be incorrect.
  
  In practice you can get away with slightly non-Markov environments - most measurements of state for machinery are approximations that ignore details at some level, for instance, and TD learning can solve optimal control in many robotics environments. However, Monte Carlo methods are more robust against state representations that are not fully Markov.
  
  ---
  
  \* Technically this sample is biased because $\hat{v}(S\_{t+1})$ is not correct when learning starts. The bias reduces over time and multiple updates. So the expected value during learning is *approximately* the same as the true value as shown by the Bellman equation.
  
  > **Comments:**
  > **username_0**: If we're working in the domain of deterministic policies, we don't have to worry about the expectation of the TD target, right? I suppose in that case the expectation of the TD target would equal itself. Please correct me if I'm wrong!  
  > **username_0**: If the statement mentioned in the comment above is right, would we still require the Markov assumption for TD learning in the case of deterministic policies?  
  > **username_1**: @cogito_ai No, both the first statement is wrong, and your suggestsed consequence in the second statement. For the first statement, the environment would also need to be deterministic before a single sample of the TD target was also guaranteed equal to the expected TD target. To answer the second comment, even in that case you need the Markov assumption - if the Markov asumption is broken, then one or both $s'$ or $r$ could be arbitrarily different when starting from the same state, so any TD target would be wrong, even one generated over many samples.  
  > **username_2**: A beautiful answer! I think the critical intuition here is this: While $Q$-learning and other TD methods are model-free, they still leverage Markovity through the consistence of the Bellman equation (which means we can sample our TD targets properly)!  
  
  ---
  
  