2
$\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$
2
  • $\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$ 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
5
$\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$
1
  • $\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$ Feb 19 '19 at 0:54
1
$\begingroup$
  • Bootstrapping needs just a single transition, or a single tuple (state, action, next_state, reward) in order to perform a value (Q-value) update; thus learning can occur without a full episode of transitions. This is used in Q-learning type recursions. Since we are not waiting for a full episode to make an update, playing can be intertwined with learning. In this kind of learning, we may have a stochastic policy (say, epsilon greed), where we are using the maximum Q-value in the next state to update the current Q-value, but we may not have to take the action that actually maximizes the Q function when we get to that next state. As such, we call Q-learning an off-policy method, since learning is not guided by the policy.

  • Sampling requires several transitions or even a full episode (sequence of transitions from initial state to terminating state) in order to perform the update. Since we hope to learn a policy, and the update is done for a single episode, we must follow the same policy throughout the episode before we can improve it (or update it). This is called policy iteration, and is use in Monte-Carlo learning, and it is on-policy because the policy guides the learning process. Because the episode must end before an update is done, learning would be very slow if episodes consists of so many transitions; thus the method cannot be used for non-episodic tasks (like games with infinite horizons).

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