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 ...
- 3,857
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 ...
- 5,030
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)...
- 10.5k
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^{...
- 10.5k
5
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 ...
- 10.5k
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 ...
- 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} |...
- 722
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,...
- 2,562
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, ...
- 5,030
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 ...
- 33.3k
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 ...
- 5,030
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)
$$
...
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} ...
- 722
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 ...
- 9,392
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 ...
- 5,030
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 ...
- 1,301
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 ...
- 33.3k
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 ...
- 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 ...
- 1,703
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 \...
- 332
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 ...
- 33.3k
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 \...
- 2,632
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 ...
- 483
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.
- 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 ...
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 ...
- 343
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 ...
- 422
Only top scored, non community-wiki answers of a minimum length are eligible