Answers.Body: <p>The main idea is that you can estimate <span class="math-container">$V^\pi(s)$</span>, the value of a state <span class="math-container">$s$</span> under a given policy <span class="math-container">$\pi$</span>, even if you don't have a model of the environment, by visiting that state <span class="math-container">$s$</span> and following the policy <span class="math-container">$\pi$</span> after that state. If you repeat this process many times, you'll get many samples of trajectories starting at <span class="math-container">$s$</span> with some total return associated with them. If you average them, you'll have a sample-based estimate of <span class="math-container">$V^\pi(s)$</span>. In a similar way, you can do a sample-based approach to estimate <span class="math-container">$Q^\pi(s, a)$</span>, where you start at <span class="math-container">$s$</span>, take some arbitrary action <span class="math-container">$a$</span>, and then continue following <span class="math-container">$\pi$</span>. After you collect many samples, you can also average the returns to get a sample-based estimate of <span class="math-container">$Q^\pi(s, a)$</span>. Once you have a good enough estimate of <span class="math-container">$Q^\pi(s, a)$</span>, you can see that it's easy to improve the current policy <span class="math-container">$\pi$</span> to get a new policy <span class="math-container">$\pi'$</span> that always chooses the best action on any given state: <span class="math-container">$\pi'(s) = \underset{a}{argmax}\ Q^\pi(s, a)$</span>.</p>
  
  <p>The procedure I described in the last paragraph where you sample an entire trajectory and wait until the end of the episode to estimate a return is the Monte Carlo approach. In contrast, TD exploits the recursive nature of the Bellman equation to learn as you go, even before the episode ends. For example, you can estimate the value function like this: <span class="math-container">$V^\pi(s_0) = r_0 + \gamma V^\pi(s_1)$</span>, where <span class="math-container">$r_0$</span> comes from experience and instead of collecting more <span class="math-container">$r_t$</span> until the end of the episode, you rely on your estimate of the value of the next state (which you also get from experience). At the beginning, your estimates might be random, but after many iterations the process converges to good estimates. The same idea of exploiting this recursive structure can be used to estimate <span class="math-container">$Q^\pi(s, a)$</span>. I guess this approach is known as temporal difference because you sample <span class="math-container">$r_0$</span> which is in some sense the temporal difference between <span class="math-container">$s_0$</span> and <span class="math-container">$s_1$</span>.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-02-15T09:02:37.110Z
Answers.Text: This looks like a solid answer. I think you may want to lead with the intuitive relationship between expectations of distributions and samples from those distributions in a first paragraph, due to how basic the OP's question is. There is also the concept of generalised policy iteration - http://www.incompleteideas.net/book/ebook/node46.html - which helps explain how repeated sample-based estimates and changes to policy can converge.
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-02-15T07:05:51.960Z
Answers.LastActivityDate: 2019-02-15T08:54:43.203Z
Answers.LastEditDate: 2019-02-15T08:54:43.203Z
Answers.UserDisplayName: Mei Zhang
Body: <p>In value iteration, we have a model of the environment's dynamics, i.e <span class="math-container">$p(s', r \mid s, a)$</span>, which we use to update an estimate of the value function.</p>
  <p>In the case of temporal-difference and Monte Carlo methods, we do not use <span class="math-container">$p(s', r \mid s, a)$</span>, but then how do these methods work?</p>
  
Tags: <reinforcement-learning><monte-carlo-methods><temporal-difference-methods><model-based-methods><model-free-methods>
Title: How do temporal-difference and Monte Carlo methods work, if they do not have access to model?
UserDisplayName: strongguy122
ThreadText: # How do temporal-difference and Monte Carlo methods work, if they do not have access to model?
  
  (Asked by: username_0 on 2019-02-15)
  
  In value iteration, we have a model of the environment's dynamics, i.e $p(s', r \mid s, a)$, which we use to update an estimate of the value function.
  
  In the case of temporal-difference and Monte Carlo methods, we do not use $p(s', r \mid s, a)$, but then how do these methods work?
  
  **Tags:** reinforcement-learning, monte-carlo-methods, temporal-difference-methods, model-based-methods, model-free-methods
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2019-02-15. Score: 5
  
  The main idea is that you can estimate $V^\pi(s)$, the value of a state $s$ under a given policy $\pi$, even if you don't have a model of the environment, by visiting that state $s$ and following the policy $\pi$ after that state. If you repeat this process many times, you'll get many samples of trajectories starting at $s$ with some total return associated with them. If you average them, you'll have a sample-based estimate of $V^\pi(s)$. In a similar way, you can do a sample-based approach to estimate $Q^\pi(s, a)$, where you start at $s$, take some arbitrary action $a$, and then continue following $\pi$. After you collect many samples, you can also average the returns to get a sample-based estimate of $Q^\pi(s, a)$. Once you have a good enough estimate of $Q^\pi(s, a)$, you can see that it's easy to improve the current policy $\pi$ to get a new policy $\pi'$ that always chooses the best action on any given state: $\pi'(s) = \underset{a}{argmax}\ Q^\pi(s, a)$.
  
  The procedure I described in the last paragraph where you sample an entire trajectory and wait until the end of the episode to estimate a return is the Monte Carlo approach. In contrast, TD exploits the recursive nature of the Bellman equation to learn as you go, even before the episode ends. For example, you can estimate the value function like this: $V^\pi(s\_0) = r\_0 + \gamma V^\pi(s\_1)$, where $r\_0$ comes from experience and instead of collecting more $r\_t$ until the end of the episode, you rely on your estimate of the value of the next state (which you also get from experience). At the beginning, your estimates might be random, but after many iterations the process converges to good estimates. The same idea of exploiting this recursive structure can be used to estimate $Q^\pi(s, a)$. I guess this approach is known as temporal difference because you sample $r\_0$ which is in some sense the temporal difference between $s\_0$ and $s\_1$.
  
  > **Comments:**
  > **username_2**: This looks like a solid answer. I think you may want to lead with the intuitive relationship between expectations of distributions and samples from those distributions in a first paragraph, due to how basic the OP's question is. There is also the concept of generalised policy iteration - http://www.incompleteideas.net/book/ebook/node46.html - which helps explain how repeated sample-based estimates and changes to policy can converge.  
  
  ---
  
  