Questions tagged [importance-sampling]
For questions related to the concept of importance sampling (which comes up, for example, in reinforcement learning).
40
questions
2
votes
2
answers
57
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?
- 21
2
votes
0
answers
73
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, ...
- 21
1
vote
1
answer
171
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 ...
- 208
1
vote
1
answer
180
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}...
- 13
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 ...
- 31
1
vote
0
answers
82
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 ...
- 151
0
votes
0
answers
45
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 ...
- 101
1
vote
0
answers
73
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}(...
- 492
1
vote
1
answer
371
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_{\...
- 41
2
votes
1
answer
406
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(...
- 133
0
votes
1
answer
190
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 ...
- 1
2
votes
1
answer
54
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 ...
- 359
1
vote
1
answer
263
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} + \...
- 113
2
votes
2
answers
305
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.
...
- 221
4
votes
0
answers
99
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(\...
- 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 ...
1
vote
0
answers
85
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 ...
- 233
3
votes
1
answer
193
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 ...
- 233
1
vote
0
answers
98
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_{...
- 683
1
vote
0
answers
76
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 <...
- 11
1
vote
0
answers
122
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 ...
- 33
1
vote
1
answer
383
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 (...
- 371
3
votes
0
answers
59
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)}...
- 1,251
2
votes
0
answers
114
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 ...
- 227
3
votes
1
answer
823
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 ...
- 4,665
2
votes
2
answers
760
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(...
- 147
1
vote
0
answers
77
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 ...
- 147
2
votes
0
answers
83
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 ...
- 1,251
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 ...
- 1,251
5
votes
2
answers
564
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 ...
- 333
3
votes
1
answer
461
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 ...
1
vote
0
answers
63
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}(...
- 41
3
votes
0
answers
70
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.
...
- 227
2
votes
0
answers
73
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'...
3
votes
1
answer
64
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(...
- 2,028
6
votes
2
answers
595
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:
$$...
- 311
1
vote
2
answers
266
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 ...
- 13
2
votes
1
answer
275
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 ...
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^...
- 106
29
votes
2
answers
18k
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?
- 443