22
$\begingroup$

Apparently, in reinforcement learning, temporal-difference (TD) method is a bootstrapping method. On the other hand, Monte Carlo methods are not bootstrapping methods.

What exactly is bootstrapping in RL? What is a bootstrapping method in RL?

$\endgroup$
20
$\begingroup$

Bootstrapping in RL can be read as "using one or more estimated values in the update step for the same kind of estimated value".

In most TD update rules, you will see something like this SARSA(0) update:

$$Q(s,a) \leftarrow Q(s,a) + \alpha(R_{t+1} + \gamma Q(s',a') - Q(s,a))$$

The value $R_{t+1} + \gamma Q(s',a')$ is an estimate for the true value of $Q(s,a)$, and also called the TD target. It is a bootstrap method because we are in part using a Q value to update another Q value. There is a small amount of real observed data in the form of $R_{t+1}$, the immediate reward for the step, and also in the state transition $s \rightarrow s'$.

Contrast with Monte Carlo where the equivalent update rule might be:

$$Q(s,a) \leftarrow Q(s,a) + \alpha(G_{t} - Q(s,a))$$

Where $G_{t}$ was the total discounted reward at time $t$, assuming in this update, that it started in state $s$, taking action $a$, then followed the current policy until the end of the episode. Technically, $G_t = \sum_{k=0}^{T-t-1} \gamma^k R_{t+k+1}$ where $T$ is the time step for the terminal reward and state. Notably, this target value does not use any existing estimates (from other Q values) at all, it only uses a set of observations (i.e., rewards) from the environment. As such, it is guaranteed to be unbiased estimate of the true value of $Q(s,a)$, as it is technically a sample of $Q(s,a)$.

The main disadvantage of bootstrapping is that it is biased towards whatever your starting values of $Q(s',a')$ (or $V(s')$) are. Those are are most likely wrong, and the update system can be unstable as a whole because of too much self-reference and not enough real data - this is a problem with off-policy learning (e.g. Q-learning) using neural networks.

Without bootstrapping, using longer trajectories, there is often high variance instead, which, in practice, means you need more samples before the estimates converge. So, despite the problems with bootstrapping, if it can be made to work, it may learn significantly faster, and is often preferred over Monte Carlo approaches.

You can compromise between Monte Carlo sample based methods and single-step TD methods that bootstrap by using a mix of results from different length trajectories. This is called TD($\lambda$) learning, and there are a variety of specific methods such as SARSA($\lambda$) or Q($\lambda$).

$\endgroup$
  • $\begingroup$ This probably should be another question. However, if you want to answer, why exactly is $R_{t+1} + \gamma Q(s',a')$ and estimate for $Q(s, a)$? $\endgroup$ – nbro Jan 23 '18 at 18:18
  • 1
    $\begingroup$ @nbro: Because at convergence, $Q(s,a) = \mathbb{E}[R_{t+1} + \gamma Q(S_{t+1},A_{t+1}) | S_t = s, A_t =a]$ (these equations and most RL is driven by Bellman equations for MDPs). By looking at an actual event that occurred starting with state $s$ and action $a$, then you are essentially sampling from that expectation. The problem is though that the value you have for $Q(S_{t+1},A_{t+1})$ has probably not converged yet, so the sample is biased. $\endgroup$ – Neil Slater Jan 23 '18 at 18:31
  • 1
    $\begingroup$ What prevents one from using MC methods as a burn in phase, before switching to bootstrapping? Or might this be considered a sub-case of $\lambda-TD$? $\endgroup$ – n1k31t4 Jun 15 '18 at 12:34
  • 1
    $\begingroup$ @n1k31t4: Nothing prevents doing this, and it should be a valid RL approach. It would be different to TD($\lambda$), but motivated by the same idea of trying to get good features from both algorithms. You would need to try it and compare learning efficiency with TD($\lambda$) - you still have a hyper parameter to tune, which is the number of episodes to run MC for. A more general version would be to allow $\lambda$ to change - start with $\lambda = 1$ and decay it down to e.g. $0.4$ or whatever value seems most optimal. However, that has 2 hyper parameters, decay rate and target for $\lambda$ $\endgroup$ – Neil Slater Jun 15 '18 at 12:39
  • $\begingroup$ @NeilSlater, when using bootstrapping, can it converge? I cannot understand why it should since Q(s',a') is just an arbitrary guess which then distorts the estimate for Q(s,a). Also, why does MC have a high-variance as compared to TD? $\endgroup$ – d56 Jun 15 at 19:40
4
$\begingroup$

In general, bootstrapping in RL means that you update a value based on some estimates and not on some exact values. E.g.

Incremental Monte Carlo Policy Evaluation updates:

$V(S_t) = V(S_t) + \alpha(G_t - V(S_t))$

TD(0) Policy Evaluation updates:

$V(S_t) = V(S_t) + \alpha(R_{t+1} + \gamma V(S_{t+1}) - V(S_t))$

In TD(0), the return starting from state $s$ is estimated (bootstrapped) by $R_{t+1} + \gamma V(S_{t+1})$ while in MC we use the exact return $G_t$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.