See also temporal difference learning.
Bootstrapping in RL refers to constructing targets for your Value function as a combination of real rewards and itself
by which we don’t need to roll out episodes all the way to the end in order to learn the value function.
Long version:
The value function, defined as the expected return of a state given a policy , could in the simplest case be obtained by just letting the policy gather lots of playouts from the state using the policy and average the sum of future rewards from the environment, which will definitionally converge towards the state-value function for that state and policy.
Link to original
Since this is a bit slow, we improve the performance by bootstrapping:
Instead of calculating, as described above: ,
we set the target for the value function as:
So we move towards the value on the right, consisting of actual rewards + estimate of the state-value of a future state. This way we don’t have to collect actual rewards all the way through but still converges to the right value by encorporating experienced rewards.
Off-Policy Correction
The off-policy nature of this method is an issue which gets resolved in Efficient Zero:
Usually the rewards are drawn as state action sequences from a replay buffer.
The experiences and states of the trajectory depend on the actions that were taken, but these are actions that the current (more trained) agent might not have taken and it would have then also found itself in different states.
So the problem is if the agent would do something different now, but is being updated towards a target as if it would have blindly done the same thing over and over.
→ The older an episode is, the shorter the bootstrap sequence.
If the trajectory that you imagine, giving you the sequence of rewards shown above, is relatively recent, then you’d still probably make the same decisions now. So you can sample from a relatively long trajectory. Your update might look like this:
On the other hand, if the trajectory that you imagine is relatively old, then you’d likely make different decisions now. So you should sample from a relatively short trajectory. Your update might look like this: