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

Questions tagged [importance-sampling]

For questions related to the concept of importance sampling (which comes up, for example, in reinforcement learning).

Filter by
Sorted by
Tagged with
1 vote
0 answers
34 views

How does Importance Sampling compare against Policy Regularization in Offline RL?

In offline RL we are usually equipped with a dataset, often also called Replay Buffer, that contains transitions in an episode, that are created by some behavior policy. This behavior policy could ...
kklaw's user avatar
  • 185
0 votes
0 answers
12 views

Is there a way to mix the Importance weighted VAE with the Beta-VAE?

Is there a way to mix the Importance weighted VAE with the Beta-VAE? It seems that we cannot separate out the KL-term from the IWAE-ELBO, hence we cannot multiply it with Beta. On the other hand, it ...
Clara's user avatar
  • 11
0 votes
0 answers
22 views

Derivation of TD(0) with Gradient Correction (TDC)

I'm trying to understand the derivation of TDC from Sutton and Barto, but I'm stuck on the steps between lines 2 and 3. It seems that the importance sampling ratio just "disappears" between ...
Shitij Govil's user avatar
2 votes
2 answers
66 views

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

I have a general question about the methods that use importance sampling in RL. What happens when the probability of either one of the policies is 0?
A J's user avatar
  • 21
2 votes
0 answers
129 views

Why is $p(x)=\int p(x,z) dz$ intractable for continuous $z$ in VAE?

In VAE we use the importance sampling trick to use $q_\phi(z|x)$ to help maximize $\log p_\theta(x)=\log \int p_\theta(x,z)dz\ge \int q_\phi(z|x)\log \frac{p_\theta(x,z)}{q_\phi(z|x)} dz$. Meanwhile, ...
hjenryin's user avatar
2 votes
1 answer
241 views

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

On Section 5.5 (page 105) of Sutton & Barto's "Reinforcement Learning: An Introduction", they discuss the off-policy Monte Carlo method for learning the value function of a target policy ...
user118967's user avatar
1 vote
1 answer
228 views

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

In Sutton and Barto's RL book, in the section for off-policy learning, we would like to find the expected value of the random variable $G_t$, given $S_t = s$ under our target policy: $$\mathbb{E}_{\pi}...
ArminAshrafi's user avatar
3 votes
0 answers
60 views

How does off-policy monte carlo explore and converge? [duplicate]

Premises to question: Behavior Policy: e-greedy (stochastic) Target Policy: greedy (deterministic) Importance Sampling Included In off-policy Monte-Carlo control, the behavior policy chooses actions ...
Jonah Kim's user avatar
1 vote
0 answers
115 views

Why does importance sampling work with latent variable models?

Caveat: importance sampling doesn't actually work for variational auto-encoders, but the question makes sense regardless In "L4 Latent Variable Models (VAE) -- CS294-158-SP20 Deep Unsupervised ...
Foobar's user avatar
  • 153
0 votes
0 answers
52 views

Why would it be easy to evaluate a probability, when it is hard to sample from for importance sampling?

Suppose we want to perform importance sampling where we have trajectories from some behavioral policy $b$, but we want to perform off-policy evaluation. From these prior questions, I understand that ...
derekchen14's user avatar
1 vote
0 answers
90 views

Why does importance sampling ratio start and end one step later in off-policy SARSA given in Sutton-Barto's RL book?

In Sutton & Barto's RL book (page 149) they say: Sarsa update can be completely replaced by a simple off-policy form $Q_{t+n}(S_t,A_t)=Q_{t+n−1}(S_t,A_t) + \rho_{t+1:t+n} [G_{t:t+n} − Q_{t+n−1}(...
DSPinfinity's user avatar
1 vote
1 answer
484 views

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

Vanilla policy gradient has a loss function: $$\mathcal{L}_{\pi_{\theta}(\theta)} = E_{\tau \sim \pi_{\theta}}[\sum\limits_{t = 0}^{\infty}\gamma^{t}r_{t}]$$ while in TRPO it is: $$\mathcal{L}_{\pi_{\...
Magi Feeney's user avatar
2 votes
1 answer
492 views

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

The update formula for the TD(0) off-policy learning algorithm is (taken from these slides by D. Silver for lecture 5 of his course) $$ \underbrace{V(S_t)}_{\text{New value}} \leftarrow \underbrace{V(...
KoKlA's user avatar
  • 133
0 votes
1 answer
227 views

Derive Importance Sampling as Expected Value Notation

I'm new to RL. Recently, I took a course on Coursera. In the Off-policy MC method, I learned the concept of Importance Sampling as follows: where the importance sampling ratio is the ratio of the ...
HHD's user avatar
  • 1
2 votes
1 answer
59 views

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

In Sutton & Barto (2nd edition), the following is mentioned on page 150 (p. 172 of the pdf), section 7.4: the importance sampling ratio has expected value one (Section 5.9) and is uncorrelated ...
user529295's user avatar
1 vote
1 answer
301 views

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

The off-policy TD learning control using state value function from page 34 of David Silver's RL lecture is: $$ V(S_t) \leftarrow V(S_t) + \alpha \left( \frac{ \pi(A_t|S_t)}{\mu (A_t|S_t)} (R_{t+1} + \...
Cauchy's user avatar
  • 113
2 votes
2 answers
310 views

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

I do not understand the link of importance sampling to Monte Carlo off-policy learning. We estimate a value using sampling on whole episodes, and we take these values to construct the target policy. ...
Hermes Morales's user avatar
4 votes
0 answers
104 views

Where does this variation of the importance sampling weight come from?

I have seeing a variation in importance sampling (IS) in Prioritized Experience Replay (PER) in some implementations regarding the original paper approach stated as (in section 3.4): $$ w_{i}=\left(\...
HenDoNR's user avatar
  • 81
5 votes
1 answer
1k views

Why do we need importance sampling?

I was studying the off-policy policy improvement method. Then I encountered importance sampling. I completely understood the mathematics behind the calculation, but I am wondering what is the ...
Alireza Hosseini's user avatar
1 vote
0 answers
96 views

How to compute the Retrace target for multi-step off-policy Reinforcement Learning?

I am implementing the A3C algorithm and I want to add off-policy training using Retrace but I am having some trouble understanding how to compute the retrace target. Retrace is used in combination ...
Federico Taschin's user avatar
3 votes
1 answer
212 views

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

When learning off-policy with multi-step returns, we want to update the value of $Q(s_1, a_1)$ using rewards from the trajectory $\tau = (s_1, a_1, r_1, s_2, a_2, r_2, ..., s_n, a_n, r_n, s_n+1)$. We ...
Federico Taschin's user avatar
1 vote
0 answers
102 views

How can I derive n-step off-policy temporal difference formula?

I was reading the book "Reinforcement Learning: An Introduction" by Sutton and Barto. In section 7.3, they write the formula for n-step off-policy TD as $$V(S_t) = V(S_{t-1}) + \alpha \rho_{...
Swakshar Deb's user avatar
1 vote
0 answers
85 views

Should the importance sampling ratio be updated at the end of the for loop in the off-policy Monte Carlo control algorithm?

I'm studying RL with Sutton and Barto's book. I'd like to ask about the order of execution of a statement in the algorithm below. Here, $W$ (importance sampling ratio) is updated at the end of the <...
JungYT's user avatar
  • 11
1 vote
0 answers
128 views

Does importance sampling for off-policy estimation also apply to the case of negative rewards?

Importance sampling is a common method for calculating off-policy estimates in RL. I have been reading through some of the original documentation (D.G. Horvitz and D.J. Thompson, Powell, M.J. and ...
curiouscat22's user avatar
1 vote
1 answer
476 views

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

I am using Sutton and Barto's book for Reinforcement Learning. In Chapter 8, I am having difficulty in understanding the Trajectory Sampling. I have read the particular section on trajectory sampling (...
SJa's user avatar
  • 393
3 votes
0 answers
61 views

Why is it the case that off-policy evaluation using importance sampling suffers from high variance?

The average return for trajectories, $V^{\pi_e}$(s) is often computed via the importance sampling estimate $$V^{\pi_e}(s) = \frac{1}{n}\sum_{i=1}^n\prod_{t=0}^{H}\frac{\pi_e(a_t | s_t)}{\pi_b(a_t|s_t)}...
calveeen's user avatar
  • 1,271
2 votes
0 answers
116 views

Does the off-policy evaluation work for non-stationary policies?

As the title says, in reinforcement learning, does the off-policy evaluation work for non-stationary policies? For example, IS (importance sampling)-based estimators, such as weighted IS or doubly ...
Hunnam 's user avatar
  • 227
4 votes
1 answer
956 views

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

Why don't we use an importance sampling ratio in Q-Learning, even though Q-Learning is an off-policy method? Importance sampling is used to calculate expectation of a random variable by using data ...
David's user avatar
  • 4,910
2 votes
2 answers
844 views

How is per-decision importance sampling derived in Sutton & Barto's book?

In per-decison importance sampling given in Sutton & Barto's book: Eq 5.12 $\rho_{t:T-1}R_{t+k} = \frac{\pi(A_{t}|S_{t})}{b(A_{t}|S_{t})}\frac{\pi(A_{t+1}|S_{t+1})}{b(A_{t+1}|S_{t+1})}\frac{\pi(...
ZERO NULLS's user avatar
1 vote
0 answers
85 views

Why does the n-step return being zero result in high variance in off policy n-step TD?

In the paragraph given between eq 7.12 and 7.13 in Sutton & Barto's book: $G_{t:h} = R_{t+1} + G_{t+1:h} , t < h < T$ where $G_{h:h} = V_{h-1}(S_h)$. (Recall that this return is used at ...
ZERO NULLS's user avatar
2 votes
0 answers
92 views

Can weighted importance sampling be applied to off-policy evaluation for continuous state space MDPs?

Can weighted importance sampling (WIS) and importance sampling (IS) be applied to off-policy evaluation for continuous state spaces MDPs? Given that I have trajectories of $(s_t,a_t)$ pairs and the ...
calveeen's user avatar
  • 1,271
3 votes
3 answers
1k views

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

The technique for off-policy value evaluation comes from importance sampling, which states that $$E_{x \sim q}[f(x)] \approx \frac{1}{n}\sum_{i=1}^n f(x_i)\frac{q(x_i)}{p(x_i)},$$ where $x_i$ is ...
calveeen's user avatar
  • 1,271
5 votes
2 answers
606 views

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

Here is my understanding of importance sampling. If we have two distributions $p(x)$ and $q(x)$, where we have a way of sampling from $p(x)$ but not from $q(x)$, but we want to compute the expectation ...
pecey's user avatar
  • 333
3 votes
1 answer
507 views

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

Here's the approximated value using weighted importance sampling $$ V_{n} \doteq \frac{\sum_{k=1}^{n-1} W_{k} G_{k}}{\sum_{k=1}^{n-1} W_{k}}, \quad n \geq 2 $$ Here's the incremental update rule for ...
ExplorationExploitation's user avatar
1 vote
0 answers
64 views

Importance sampling eq. 5 in paper "Residual Energy-based Models for Text Generation"

In the paper "Residual Energy-Based Models for Text Generation" (arXiv), on page 5, they write that equation 5 is an instance of importance sampling. Equation 5 is: $$ P(x_t \mid x_{<t}) = P_{LM}(...
rubencart's user avatar
3 votes
0 answers
73 views

Can the importance sampling estimator have a non-stationary behaviour policy even if the target policy is stationary?

The inverse propensity score (IPS) estimator, which is used for off-policy evaluation in a contextual bandit problem, is well explained in the paper Doubly Robust Policy Evaluation and Optimization. ...
Hunnam 's user avatar
  • 227
2 votes
0 answers
75 views

Can we use imitation learning for on-policy algorithms?

Imitation learning uses experiences of an (expert) agent to train another agent, in my understanding. If I want to use an on-policy algorithm, for example, Proximal Policy Optimization, because of it'...
Khush Agrawal's user avatar
3 votes
1 answer
72 views

Are successive actions independent?

The proof of the consistency of the per-decision importance sampling estimator assumes the independence of $$\frac{\pi(A_t|S_t)}{b(A_t|S_t)}R_{t+1}\quad\text{ and }\quad \prod_{k=t+1}^{T-1}\frac{\pi(...
Philip Raeisghasem's user avatar
6 votes
2 answers
650 views

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

In the book Reinforcement Learning: An Introduction (2nd edition) Sutton and Barto define at page 104 (p. 126 of the pdf), equation (5.3), the importance sampling ratio, $\rho _{t:T-1}$, as follows: $$...
F.M.F.'s user avatar
  • 311
1 vote
2 answers
269 views

In the context of importance sampling ratio, how is the equation $\mathbb{E}\left[\rho_{t: T-1} G_{t} | S_{t}=s\right]=v_{\pi}(s)$ derived?

When reading the book by Sutton and Barto, I came across the importance sampling ratio. The first equation, I believe, describes the probability a particular sequence is obtained given the current ...
Zach Zhao's user avatar
  • 113
2 votes
1 answer
322 views

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

I am reading the book titled "Reinforcement Learning: An Introduction" (by Sutton and Barto). I am at chapter 5, which is about Monte Carlo methods, but now I am quite confused. There is one thing I ...
Manuel Pasieka's user avatar
7 votes
2 answers
2k views

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

In the Trust-Region Policy Optimisation (TRPO) algorithm (and subsequently in PPO also), I do not understand the motivation behind replacing the log probability term from standard policy gradients $$L^...
Mark's user avatar
  • 106
31 votes
2 answers
20k views

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

For instance, the title of this paper reads: "Sample Efficient Actor-Critic with Experience Replay". What is sample efficiency, and how can importance sampling be used to achieve it?
Gokul NC's user avatar
  • 463