Answers.Body: <blockquote>
  <p>What would be the standard approach in this case? Better use TD learning or Monte Carlo?</p>
  </blockquote>
  <p>Both should be fine, but they <em>might</em> lead to different estimates, if both these things apply:</p>
  <ul>
  <li><p>The amount of data is relatively small compared to all possibilities from the given environment and policy.</p>
  </li>
  <li><p>Either the policy or the environment are stochastic.</p>
  </li>
  </ul>
  <p>The difference is that for each state/action pair estimated:</p>
  <ul>
  <li><p>Monte Carlo will estimate based on overall average returns, ignoring individual state transitions and policy choices.</p>
  </li>
  <li><p>Temporal Difference will estimate based on observed state transitions and policy choices.</p>
  </li>
  </ul>
  <p>There is a good example of what this might mean numerically in <a href="http://incompleteideas.net/book/RLbook2020trimmed.pdf" rel="nofollow noreferrer">Sutton &amp; Barto</a> chapter 6, example 6.4. In that case it shows an advantage to TD learning when some states might be sparsely represented in the data whilst others have more instances. Monte Carlo learning will only learn the value of those rarer states from the trajectories where they occur, whilst TD learning will be able to use estimates of <em>other</em> trajectories, provided two or more trajectories overlap later on.</p>
  <p>This doesn't necessarily make TD learning better. If a trajectory that overlaps with others also happens to include an unusual policy choice, state transition or reward, this may spread sample bias into multiple estimates, whilst Monte Carlo would be affected less by such an outlier.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-05-12T09:44:56.743Z
Answers.Text: Thanks! So in some sense TD has high bias and less variance, while MC has low bias and high variance, right?
Answers.UserDisplayName: Onil90
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-05-12T11:03:22.567Z
Answers.Text: @Onil90: Yes, although this bias in not the same bias as referred in other scenarios discussing TD vs MC. In your scenario with a fixed data set, and assuming process until convergence, it is that both MC and TD respond to sample bias differently.
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-05-12T09:21:45.350Z
Answers.LastActivityDate: 2022-05-12T09:32:46.860Z
Answers.LastEditDate: 2022-05-12T09:32:46.860Z
Answers.UserDisplayName: Neil Slater
Answers.Body: <p>Your trajectories must contain rewards, so I'm assuming you've forgotten them in your original post, i.e., we must have <span class="math-container">$$\tau_j = (s_0^j, a_0^j, r_1^j, ..., s_{N_j}, a_{N_j}, r_{N_j+1})$$</span></p>
  <p>Given that you have access to the full trajectories, I would use the Monte Carlo estimates. You want to use TD methods when you need to estimate <span class="math-container">$Q^\pi$</span> incrementally as new transitions <span class="math-container">$(s_t, a_t, r_{t+1})$</span> arrive.</p>
  <p>You can estimate <span class="math-container">$Q^\pi$</span> as follows (adapted from the <a href="http://incompleteideas.net/book/RLbook2020trimmed.pdf" rel="nofollow noreferrer">Sutton&amp;Barto book</a>, chapter 5.1):</p>
  <p>Initialise <span class="math-container">$\text{Returns}(s,a)$</span> to an empty list for all <span class="math-container">$(s, a)$</span> pairs in the trajectories.</p>
  <p>For each <span class="math-container">$j$</span>:<br />
    Initialise the cumulative discounted reward <span class="math-container">$G$</span> to 0.<br />
    For <span class="math-container">$t$</span> in <span class="math-container">${N_j, N_{j-1}, ..., 0}$</span>:<br />
      Set <span class="math-container">$G = \gamma G + r_{t+1}$</span><br />
      If <span class="math-container">$(s_t, a_t)$</span> is <strong>not</strong> in <span class="math-container">$((s_0, s_0), ... (s_{t-1}, a_{t-1}))$</span>:<br />
        Append <span class="math-container">$G$</span> to <span class="math-container">$\text{Returns}(s_t, a_t)$</span>.<br />
        Set <span class="math-container">$Q^\pi(s_t, a_t) = \text{Average}(\text{Returns}(s_t, a_t))$</span></p>
  <p>For completeness the method is called &quot;First visit Monte Carlo&quot; because we only update the estimate of <span class="math-container">$Q^\pi$</span> using first visits to an <span class="math-container">$(s, a)$</span> pair.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-05-11T20:15:31.660Z
Answers.LastActivityDate: 2022-05-12T18:36:55.610Z
Answers.LastEditDate: 2022-05-12T18:36:55.610Z
Answers.UserDisplayName: Raphael Lopez Kaufman
Body: <p>Let's say that I have a set of trajectories <span class="math-container">$\mathcal{D} = \{\tau_1, \dots, \tau_n\}$</span> produced by an agent acting in a (episodic) MDP with a fixed policy <span class="math-container">$\pi$</span>. I would like to estimate the <span class="math-container">$Q$</span> function of <span class="math-container">$\pi$</span> from <span class="math-container">$\mathcal{D}$</span>. Just to be clear, each trajectory <span class="math-container">$\tau_j$</span> is a finite sequence
  <span class="math-container">$$
  \tau_j = s_0^j, a_0^j, r_0^j s_1^j, a_1^j, r_1^j \dots, s_{N_j}^j
  $$</span>
  representing an episode performed w.r.t. <span class="math-container">$\pi$</span>.</p>
  <p>What would be the standard approach in this case? Better use TD learning or Monte Carlo?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-05-11T20:00:07.193Z
Comments.Text: Where are the rewards in your data? Usually I would expect to see them in the trajectories ie. $\tau_j = s_0^j, a_0^j, r_1^j,  s_1^j, a_1^j, r_2^j, \dots$
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-05-12T08:01:34.917Z
Comments.Text: Yes, I forgot the rewards! I edit the question
Comments.UserDisplayName: Onil90
Tags: <reinforcement-learning><algorithm-request><monte-carlo-methods><temporal-difference-methods>
Title: Given a set of trajectories produced by a fixed policy, what is the the standard approach to estimate Q?
UserDisplayName: Onil90
ThreadText: # Given a set of trajectories produced by a fixed policy, what is the the standard approach to estimate Q?
  
  (Asked by: username_0 on 2022-05-11)
  
  Let's say that I have a set of trajectories $\mathcal{D} = \{\tau\_1, \dots, \tau\_n\}$ produced by an agent acting in a (episodic) MDP with a fixed policy $\pi$. I would like to estimate the $Q$ function of $\pi$ from $\mathcal{D}$. Just to be clear, each trajectory $\tau\_j$ is a finite sequence
  $$
  \tau\_j = s\_0^j, a\_0^j, r\_0^j s\_1^j, a\_1^j, r\_1^j \dots, s\_{N\_j}^j
  $$
  representing an episode performed w.r.t. $\pi$.
  
  What would be the standard approach in this case? Better use TD learning or Monte Carlo?
  
  **Tags:** reinforcement-learning, algorithm-request, monte-carlo-methods, temporal-difference-methods
  > **Comments:**
  > **username_1**: Where are the rewards in your data? Usually I would expect to see them in the trajectories ie. $\tau_j = s_0^j, a_0^j, r_1^j,  s_1^j, a_1^j, r_2^j, \dots$  
  > **username_0**: Yes, I forgot the rewards! I edit the question  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_1 on 2022-05-12. Score: 1 | Accepted answer
  
  > What would be the standard approach in this case? Better use TD learning or Monte Carlo?
  
  Both should be fine, but they *might* lead to different estimates, if both these things apply:
  
  * The amount of data is relatively small compared to all possibilities from the given environment and policy.
  * Either the policy or the environment are stochastic.
  
  The difference is that for each state/action pair estimated:
  
  * Monte Carlo will estimate based on overall average returns, ignoring individual state transitions and policy choices.
  * Temporal Difference will estimate based on observed state transitions and policy choices.
  
  There is a good example of what this might mean numerically in [Sutton & Barto](http://incompleteideas.net/book/RLbook2020trimmed.pdf) chapter 6, example 6.4. In that case it shows an advantage to TD learning when some states might be sparsely represented in the data whilst others have more instances. Monte Carlo learning will only learn the value of those rarer states from the trajectories where they occur, whilst TD learning will be able to use estimates of *other* trajectories, provided two or more trajectories overlap later on.
  
  This doesn't necessarily make TD learning better. If a trajectory that overlaps with others also happens to include an unusual policy choice, state transition or reward, this may spread sample bias into multiple estimates, whilst Monte Carlo would be affected less by such an outlier.
  
  > **Comments:**
  > **username_0**: Thanks! So in some sense TD has high bias and less variance, while MC has low bias and high variance, right?  
  > **username_1**: @Onil90: Yes, although this bias in not the same bias as referred in other scenarios discussing TD vs MC. In your scenario with a fixed data set, and assuming process until convergence, it is that both MC and TD respond to sample bias differently.  
  
  ---
  
  ### Answer by username_2 on 2022-05-11. Score: 2
  
  Your trajectories must contain rewards, so I'm assuming you've forgotten them in your original post, i.e., we must have $$\tau\_j = (s\_0^j, a\_0^j, r\_1^j, ..., s\_{N\_j}, a\_{N\_j}, r\_{N\_j+1})$$
  
  Given that you have access to the full trajectories, I would use the Monte Carlo estimates. You want to use TD methods when you need to estimate $Q^\pi$ incrementally as new transitions $(s\_t, a\_t, r\_{t+1})$ arrive.
  
  You can estimate $Q^\pi$ as follows (adapted from the [Sutton&Barto book](http://incompleteideas.net/book/RLbook2020trimmed.pdf), chapter 5.1):
  
  Initialise $\text{Returns}(s,a)$ to an empty list for all $(s, a)$ pairs in the trajectories.
  
  For each $j$:  
    Initialise the cumulative discounted reward $G$ to 0.  
    For $t$ in ${N\_j, N\_{j-1}, ..., 0}$:  
      Set $G = \gamma G + r\_{t+1}$  
      If $(s\_t, a\_t)$ is **not** in $((s\_0, s\_0), ... (s\_{t-1}, a\_{t-1}))$:  
        Append $G$ to $\text{Returns}(s\_t, a\_t)$.  
        Set $Q^\pi(s\_t, a\_t) = \text{Average}(\text{Returns}(s\_t, a\_t))$
  
  For completeness the method is called "First visit Monte Carlo" because we only update the estimate of $Q^\pi$ using first visits to an $(s, a)$ pair.
  
  
  ---
  
  