3
$\begingroup$

I have come across a David Silver's slide which contains both the terms "bootstrapping" and "sampling". Is there any realistic example which helps me to understand the concepts better.

$\endgroup$
  • $\begingroup$ You may need to reproduce and/or paraphrase some of the text from the slide to give enough context to answer. In RL, it is possible to have both bootstrapping and sampling occurring within a single update rule, and it is not clear whether you need the distinction made in that context or whether the context is e.g. Monte Carlo vs TD learning. $\endgroup$ – Neil Slater Apr 24 '18 at 7:22
  • $\begingroup$ I just wanted to know the distinction between them in a general sense. @NeilSlater $\endgroup$ – James K J Apr 24 '18 at 20:13
2
$\begingroup$

I will try to answer this question conceptually and not technically so you get a grasp of the mechanisms in RL.

  • Bootstrapping: When you estimate something based on another estimation. In the case of Q-learning for example this is what is happening when you modify your current reward estimation $r_t$ by adding the correction term $\max_a' Q(s',a')$ which is the maximum of the action value over all actions of the next state. Essentially you are estimating your current action value Q by using an estimation of the future Q. Neil has answered that in detail here.

  • Sampling: Imagine samples as realizations (different values) of a function. Many times it is really difficult to estimate, or come up with an analytical expression, of the underlying process that generated your observations. However sampling values can help you determine lots of characteristics of the underlying generative mechanism and even make assumptions of its properties. Sampling can come in many forms in RL. For example, Q learning is a sampled-based point estimation of the optimal action value function (Bellman equation). In a world that your agent knows nothing you cannot use Dynamic Programming to determine the expected reward form every state. Thus, you need to sample "experience" from your world and estimate the expected reward from any state. In Policy Gradient methods in order to determine the gradient of your expected reward you need to sample trajectories over states and actions from a probability distribution as you cannot determine it analytically.

Hope this helps!

$\endgroup$
  • $\begingroup$ Monte Carlo methods use sampling, but not bootstrapping. But is there an example of a bootstrapping method which doesn't use sampling? $\endgroup$ – nbro Feb 18 at 14:09
  • $\begingroup$ In the context of RL as I explain above sampling comes in many forms. I am not quite sure why what you suggest would be useful. You will always receive a reward from the environment (which is a sample), why not using it? $\endgroup$ – Constantinos Feb 19 at 0:54

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.