Questions tagged [importance-sampling]
For questions related to the concept of importance sampling (which comes up, for example, in reinforcement learning).
34
questions
1
vote
0
answers
47
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}(...
- 194
0
votes
1
answer
64
views
Does importance sampling really improve sampling efficiency of policy gradient methods such as 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_{\...
0
votes
0
answers
29
views
Can we compute probability of sample in R1-Natural Evolution Strategy with linear time and space?
In R1-NES, the sample is drawn from a multivariate normal distribution, $\vec{\theta} \sim \mathcal{N}\left( \vec{\mu},\mathbf{\Sigma} \right)$, with the covariance matrix is parametrized by $s$ and a ...
- 143
2
votes
1
answer
76
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
59
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
37
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 ...
- 339
1
vote
1
answer
80
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
186
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.
...
- 211
3
votes
0
answers
85
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(\...
- 71
5
votes
1
answer
233
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
37
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 ...
- 223
3
votes
1
answer
101
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 ...
- 223
1
vote
0
answers
42
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_{...
- 665
1
vote
0
answers
41
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
46
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
99
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 (...
- 331
3
votes
0
answers
41
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,201
1
vote
0
answers
84
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 ...
- 207
3
votes
1
answer
381
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,026
2
votes
2
answers
503
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
59
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
54
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,201
2
votes
3
answers
235
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,201
5
votes
2
answers
372
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 ...
- 313
3
votes
1
answer
145
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
60
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
2
votes
0
answers
54
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.
...
- 207
2
votes
0
answers
49
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
51
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(...
- 1,918
5
votes
2
answers
332
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:
$$...
- 291
1
vote
2
answers
242
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
147
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 ...
6
votes
2
answers
1k
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^...
- 96
21
votes
2
answers
12k
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?
- 363