Questions tagged [importance-sampling]
For questions related to the concept of importance sampling (which comes up, for example, in reinforcement learning).
32
questions
0
votes
1answer
43 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 ...
2
votes
1answer
31 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 ...
1
vote
1answer
52 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} + \...
2
votes
2answers
168 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.
...
0
votes
0answers
26 views
Which off-policy policy gradient estimator has lower variance?
Let $\pi_\theta$ be a target policy and $\beta_\theta$ be a behavior policy. I have seen the following 2 policy gradient estimators in the literature:
$$ \operatorname*{E}_{\tau \sim \beta_\theta} \...
3
votes
0answers
73 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(\...
1
vote
0answers
38 views
Understanding policy gradient derivation with importance sampling
I was watching a lecture on Policy Gradient and had difficulty following it when importance sampling was introduced.
It was shown that the gradient of the objective can be written as $$\nabla_\theta U(...
5
votes
1answer
162 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
0answers
29 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 ...
2
votes
1answer
88 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 ...
1
vote
0answers
36 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_{...
1
vote
0answers
30 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 <...
1
vote
0answers
42 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 ...
1
vote
1answer
55 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 (...
3
votes
0answers
33 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
vote
0answers
77 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 ...
3
votes
1answer
266 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 ...
2
votes
2answers
381 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(...
1
vote
0answers
55 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 ...
2
votes
0answers
49 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 ...
2
votes
3answers
159 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 ...
5
votes
2answers
351 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 ...
3
votes
1answer
97 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
0answers
53 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}(...
2
votes
0answers
49 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.
...
2
votes
0answers
44 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
1answer
49 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(...
5
votes
2answers
291 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:
$$...
1
vote
2answers
233 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 ...
2
votes
1answer
134 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
2answers
972 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^...
20
votes
2answers
10k 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?
