1
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ 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$ $\endgroup$
    – Neil Slater
    May 11 at 20:00
  • $\begingroup$ Yes, I forgot the rewards! I edit the question $\endgroup$
    – Onil90
    May 12 at 8:01

2 Answers 2

Reset to default
1
$\begingroup$

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 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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks! So in some sense TD has high bias and less variance, while MC has low bias and high variance, right? $\endgroup$
    – Onil90
    May 12 at 9:44
  • 1
    $\begingroup$ @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. $\endgroup$
    – Neil Slater
    May 12 at 11:03
2
$\begingroup$

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, 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.

Improve this answer
$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .