Skip to main content
Share Your Experience: Take the 2024 Developer Survey
30 votes
Accepted

What is sample efficiency, and how can importance sampling be used to achieve it?

An algorithm is sample efficient if it can get the most out of every sample. Imagine yourself playing PONG for the first time. As a human, it would take you within seconds to learn how to play the ...
Jaden Travnik's user avatar
7 votes

Why do we need importance sampling?

Importance sampling is typically used when the distribution of interest is difficult to sample from - e.g. it could be computationally expensive to draw samples from the distribution - or when the ...
David's user avatar
  • 4,920
7 votes

What is sample efficiency, and how can importance sampling be used to achieve it?

Sample Efficiency denotes the amount of experience that an agent/algorithm needs to generate in an environment (e.g. the number of actions it takes and number of resulting states + rewards it observes)...
Dennis Soemers's user avatar
  • 10.3k
6 votes

Why is the log probability replaced with the importance sampling in the loss function?

I am not 100% sure if the following is the only/complete story, but I'm quite confident it's at least part of the story: In the PPO paper, after describing the standard policy gradient objective $L^{...
Dennis Soemers's user avatar
  • 10.3k
4 votes

Why is the log probability replaced with the importance sampling in the loss function?

For everybody getting here from google, like me: the $\log$ might have been replaced in the loss function, but I think it is still there when taking the gradient of both functions (correct me, if I am ...
mglss's user avatar
  • 81
4 votes

What is the intuition behind importance sampling for off-policy value evaluation?

Recall that our goal is to be able to accurately estimate the true value of each state by computing a sample average over returns starting from that state: $$v_{q}(s) \doteq \mathbb{E}_{q}\left[G_{t} |...
user5093249's user avatar
4 votes
Accepted

How can the importance sampling ratio be different than zero when the target policy is deterministic?

You're correct, when the target policy $\pi$ is deterministic, the importance sampling ratio will be $\geq 1$ along the trajectory where the behaviour policy $b$ happened to have taken the same ...
Dennis Soemers's user avatar
  • 10.3k
3 votes

With Monte Carlo off-policy learning what do we correct by using importance sampling?

We estimate a value using sampling on whole episodes, and we take this values to construct the target policy. The crucial bit that you are missing is that there is no single value of $V(s)$ (or $Q(s,...
Kostya's user avatar
  • 2,534
3 votes
Accepted

Why we don't use importance sampling in tabular Q-Learning?

In Tabular Q-learning the update is as follows $$Q(s,a) = Q(s,a) + \alpha \left[R_{t+1} + \gamma \max_aQ(s',a) - Q(s,a) \right]\;.$$ Now, as we are interested in learning about the optimal policy, ...
David's user avatar
  • 4,920
3 votes
Accepted

Do we need the transition probability function when calculating the importance sampling ratio?

There is one thing I don't particularly understand. Why do we need the state-transition probability function when calculating the importance sampling ratio for off-policy prediction? It is not needed ...
Neil Slater's user avatar
  • 32.5k
3 votes

How can we compute the ratio between the distributions if we don't know one of the distributions?

It is common in Bayesian statistics to only know the posterior up to a constant of proportionality. This means that we can't directly sample from the posterior. However, using importance sample we are ...
David's user avatar
  • 4,920
3 votes
Accepted

How can we compute the ratio between the distributions if we don't know one of the distributions?

The rationale behind importance sampling is that $q(x)$ is difficult to sample from but easy to evaluate. Or at least you can easily evaluate some $\tilde{q}$ such that: $$ \tilde{q}(z) = Zq(z) $$ ...
Tomasz Bartkowiak's user avatar
2 votes
Accepted

How is the incremental update rule derived from the weighted importance sampling in off-policy Monte Carlo control?

By definition of $V_{n+1}$, we have: $V_{n+1} = \frac{\sum_{k=1}^{n} W_{k} G_{k}}{\sum_{k=1}^{n} W_{k}} \; \tag{1}$ Then, taking the $n^{th}$ term out of the sum in the numerator, we have: $V_{n+1} ...
user5093249's user avatar
2 votes
Accepted

Are successive actions independent?

This is a consequence of the Markovian assumption, which underpins all of RL. The Markovian assumption says that it doesn't matter how we reached a given state, only that we reached it, when ...
John Doucette's user avatar
2 votes

What is the intuition behind importance sampling for off-policy value evaluation?

In the application of importance sampling to RL, is the expectation of the function $f$ equivalent to the value of the trajectories, which is represented by the trajectories $x$? I believe what you ...
David's user avatar
  • 4,920
2 votes

Does importance sampling really improve sampling efficiency of TRPO or PPO?

The point of importance sampling is to use the same episode(s) to do multiple policy gradient updates. It will definitely increase sample efficiency over the strictly on-policy case, simply because in ...
Taw's user avatar
  • 1,261
2 votes
Accepted

How does this TD(0) off-policy value update formula work?

This would mean we decrease the value of this state. Yes. This update that reduces the estimate is correct because it adjusts for the inevitable over-estimate of value when the exploration policy ...
Neil Slater's user avatar
  • 32.5k
2 votes

What is the intuition behind importance sampling for off-policy value evaluation?

Let's fix some notation: we're collecting data from behavior policy $\pi_0$ and we want to evaluate a policy $\pi$. Of course, if we had plenty of data from policy $\pi$ that would be the best way to ...
kaiwenw's user avatar
  • 151
2 votes

What happens when the probability of either one of the policies is 0 in Importance Sampling?

Background: Importance sampling is used in many off-policy RL algorithms when the data is generated with one policy, yet it is being used to update another policy. The policy generating the data is ...
DeepQZero's user avatar
  • 1,399
2 votes
Accepted

How does off-policy Monte Carlo weighted importance sampling bias converge to zero (Sutton & Barto Section 5.5)

Short explanation The bias converges asymptotically to zero with more visits of the state $s$. The value function is estimated in the following way: \begin{equation} v_{\pi}(s) = \frac{\sum_{t \in \...
pythonic833's user avatar
2 votes
Accepted

What would be the importance sampling ratio for off-policy TD learning control using Q values?

Since $A_t$ is already determined (because we are calculating $Q(S_t,A_t)$), I think $\pi(A_t|S_t)$ is definitely 1. But what about $\mu (A_t|S_t)$? Is it 1 or not? You could assign values of 1 to ...
Neil Slater's user avatar
  • 32.5k
1 vote

What happens when the probability of either one of the policies is 0 in Importance Sampling?

Very simply, one of the requirements of off-policy RL to converge, is that the behavioral policy $b$ has at least the same support of the target policy $\pi$, thus: $$ \forall s \in S \forall a \in A \...
Alberto's user avatar
  • 2,233
1 vote
Accepted

In off-policy MC learning, why is the probability of sampling a trajectory the same as having a return?

The expected value notation $\mathbb{E}$ can easily cause mistakes, which I think is what happened here. It's not always clear what exact group of things and probably distribution the expected value ...
KarelPeeters's user avatar
1 vote

How to prove importance sampling ratio is uncorrelated with action-value (or state-value) estimate?

Sutton and Barto explain it themselves in section 5.9. I post it with a bit of context. The equation you're looking for is 5.13.
tnfru's user avatar
  • 348
1 vote

When learning off-policy with multi-step returns, why do we use the current behaviour policy in importance sampling?

According to my understanding, you don't use just the current behavior policy for sampling. The importance sampling ratio is calculated as the product of the probability ratios for both the target and ...
Shreyans Jain's user avatar
1 vote

How is trajectory sampling different than normal (importance) sampling in reinforcement learning?

Here is my understanding: In trajectory sampling as the book describes it, we use the current policy on the simulator to get (next-state, action) pairs. The advantage is that if some states occur more ...
pecey's user avatar
  • 333
1 vote

How can the importance sampling ratio be different than zero when the target policy is deterministic?

Good question. I think this part of the book is not well explained. Off-policy evaluation of $V$ by itself doesn't make sense, IMO. I think there are two cases here is if $\pi$ is deterministic, as ...
Maverick Meerkat's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible