21

An algorithm is sample efficient if it can get the most out of every sample. Imagine learning trying to learn how to play PONG for the first time. As a human, it would take you within seconds to learn how to play the game based on very few samples. This makes you very "sample efficient". Modern RL algorithms would have to see $100$ thousand times more data ...


7

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 distribution is only known up to a multiplicative constant, such as in Bayesian statistics where it is intractable to calculate the marginal likelihood; that is $$...


6

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^{PG}$, they mention the following: While it is appealing to perform multiple steps of optimization on this loss $L^{PG}$ using the same trajectory, doing so ...


6

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) during training in order to reach a certain level of performance. Intuitively, you could say an algorithm is sample efficient if it can make good use of every ...


5

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 actions that $\pi$ would have taken, and turns to $0$ as soon as $b$ makes one "mistake" (selects an action that $\pi$ would not have selected). Before importance ...


4

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} | S_{t}=s\right] \approx \frac{1}{n} \sum_{i=1}^{n} Return_i $$ where $Return_i$ is the return obtained from the $i^{th}$ trajectory. The problem is that the $\...


3

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,a)$) of a state (or a state action pair). These value functions are always defined with respect to some policy $\pi(a|s)$ and is given the notation of $V^{\pi}(...


3

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, this would correspond to the $\max_aQ(s',a)$ term in the TD target because that is how the optimal policy chooses its actions - i.e. $\pi_*(a|s) = \arg\max_aQ_*(...


3

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 able to. Consider our posterior density $\pi$ is only known up to some constant, i.e. $\pi(x) = K \tilde{\pi}(x)$, where $K$ is some constant and we only ...


3

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) $$ where $Z$ (scalar) might be unknown. The geometrical example would be here e.g. sampling uniformly from an area under the curve $q(x)$ (in general it's not easy). ...


3

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 for calculation. It must be included in the theory, to compare the correct probability of each trajectory (on-policy vs off-policy). However, the state ...


2

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 wrong): $$\begin{aligned} \nabla_{\theta} L^{P G}(\theta) &=\nabla_{\theta} \hat{E}_{t}\left[\log \pi_{\theta}\left(a_{t} \mid s_{t}\right) \hat{A}_{t}\...


2

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} = \frac{W_{n}G_{n} \; + \; \sum_{k=1}^{n-1} W_{k} G_{k}}{\sum_{k=1}^{n} W_{k}} \; \tag{2}$ Then, from the definition of $V_n$, $V_{n} = \frac{\sum_{k=1}^{n-1} ...


2

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 evaluate $\pi$ as we just take the empirical average (without any importance sampling) and CLT gives us confidence intervals that shrink at $\frac{1}{\sqrt n}$ ...


2

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 are asking here is if when using importance sampling in the off-policy RL setting that we set $f(x)$ from the general importance sampling formula to be our ...


2

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 each to get the right answer, but the situation is different. You can see that more clearly in the definition of action value, $q(s,a)$: $$q_{\pi}(s,a) = \mathbb{...


1

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.


1

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 behaviour policy throughout the trajectory. See the calculation below, where the product is happening for all the probabilities throughout the trajectories. (...


1

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 frequently than others in that environment, and if we take enough samples, the distribution among the samples would be similar to the actual distribution. On ...


1

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 deciding how likely it is that we move to subsequent states. This naturally implies that our choice of actions must also depend only on the current state. You are ...


1

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 we probably want in the case of "control", i.e. we will determine $\pi$ to be deterministic and in every state choose the action that most likely to ...


Only top voted, non community-wiki answers of a minimum length are eligible