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?
2 Answers
$\begingroup$
$\endgroup$
4
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$).
answered Jan 23, 2018 at 8:22
-
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$– n1k31t4Jun 15, 2018 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$ Jun 15, 2018 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$– d56Jun 15, 2019 at 19:40
-
$\begingroup$ @d56 Those are two different questions. I think the variance question has been asked before on Data Science, AI or Cross Validated (and I have answered it). As for converging, the short answer is yes it can, and despite the initial bias it can often converge faster than MC. The basic reason is that the bias reduces on each update - although in some cases that requires some extra work. $\endgroup$ Jun 15, 2019 at 20:44
$\begingroup$
$\endgroup$
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$.