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

The concepts of on-policy vs off-policy and online vs offline are separate, but do interact to make certain combinations more feasible. When looking at this, it is worth also considering the difference between prediction and control in Reinforcement Learning (RL). Online vs Offline These concepts are not specific to RL, many learning systems can be ...


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 ...


5

As for your first two questions: there is indeed a behaviour and a target policy, which can be different. In the example image of the $3$-step tree-backup update in the beginning of the section you mention, the actions $A_t$, $A_{t+1}$, and $A_{t+2}$ are assumed to be selected according to some behaviour policy, whereas a (different) target policy is used to ...


5

Absolutely, it’s a really interesting problem. Here is a paper detailing off policy actor critic. This is important because this method can also support continuous actions. The general idea of off-policy algorithms is to compare the actions performed by a behaviour policy (which is actually acting in the world) with the actions the target policy (the ...


5

I'm using OpenAI's cartpole environment. First of all, is this environment not Markov? The OpenAI Gym CartPole environment is Markov. Whether or not you know the transition probabilities does not affect whether the state has the Markov property. All that matters is that knowing the current state is enough to be determine the next state and reward in ...


4

A non-starving policy is a (behavior) policy that is theoretically guaranteed to visit each state and take all possible actions from each state an infinite number of times, so that to always update $Q(s, a)$, $\forall s, \forall a$, an infinite number of times. In the context of off-policy prediction, this criterion implies that any trajectory will have no ...


4

This post contains many answers that describe the difference between on-policy vs. off-policy. Your book may be referring to how the current (DQN-based) state-of-the-art (SOTA) algorithms, such as Ape-X, R2D2, Agent57 are technically "off-policy", since they use a (very large!) replay buffer, often filled in a distributed manner. This has a number ...


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

In the book, the phrase "generate the data" refers to the data from observations about states, actions, next states and rewards, that then get used to make value estimate updates. In both the SARSA and Q learning pseudocode from the book, there is a behaviour policy that selects the next action to take. Other than the initial start state, this ...


3

In respect of RL, is model-free and off-policy the same thing, just different terminology? No, they are entirely different terms, with the only thing they have in common is that they are both ways in which an RL agent can vary. An agent is generally either working off-policy or on-policy, and is generally either model-based or model-free. These things can ...


3

The Q values are updated using a "greedy policy" because, in the Q-learning algorithm, the $\max$ operator is used to determine the "target", which is denoted by $$\color{green}{R_{t+1}} + \gamma \color{blue}{\max_{a}Q(S_{t+1}, a)}$$ Intuitively, the $\max$ operator is used to take the "greedy" action, that is, the action ...


3

The twist here is that the $a_{t+1}$ in (11) and the $\mu(s_{t+1})$ in (16) are the same and actually the $a_t$ in the on-policy case and the $a_t$ in the off-policy case are different. The key to the understanding is that in on-policy algorithms you have to use actions (and generally speaking trajectories) generated by the policy in the updating steps (to ...


3

What I want to know is whether I can add expert data to the replay buffer, given that DDPG is an off-policy algorithm? You certainly can, that is indeed one of the advantages of off-policy learning algorithms; they're still "correct", regardless of which policy generated the data that you're learning from (and a human expert providing the ...


2

Multiplying the entire update by $\rho$ has the desirable property that experience affects $Q$ less when the behavior policy is unrelated to the target policy. In the extreme, if the trajectory taken has zero probability under the target policy, then $Q$ isn't updated at all, which is good. Alternatively, if only $G$ is scaled by $\rho$, taking zero ...


2

The pseudocode you have copied looks incorrect to me, and I think it is from the first edition. The main issue is at the end of the loop. Where the book has $\qquad W \leftarrow W \frac{1}{\mu(A_t|S_t)}$ $\qquad \text{If } W = 0 \text{ then ExitForLoop}$ It should have either $\qquad W \leftarrow W \frac{1}{\mu(A_t|S_t)}$ $\qquad \text{If } \pi(S_t) \neq ...


2

Expected SARSA can be used either on-policy or off-policy. The policy that you use in the update step determines which it is. If the update step uses a different weighting for action choices than the policy that actually took the action, then you are using Expected SARSA in an off-policy way. Q-learning is a special case of Expected SARSA, where the target ...


2

You cannot really do that because you have no way of knowing how good the action really is to make reasonable labels for supervised learning (that's the whole point why we need reinforcement learning). The only way to possibly know that is to make labels based on the return that you got from that action but the return is based on an old trajectory with the ...


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

First, some preliminary questions: in this case, what is the optimal policy? It is the policy that maximises return from any given time step $G_t$. You need to be careful with your definition of return with continuing environments. The simple expected sum of future rewards is likely to be positive or negative infinity. There are three basic approaches: ...


2

DDPG is an off-policy algorithm simply because of the objective taking expectation with respect to some other distribution that we are not learning about, i.e. the deterministic policy gradient can be expressed as $$\nabla _{\theta^\mu} J \approx \mathbb{E}_{s_t \sim \rho^\beta} \left[ \nabla _{\theta^\mu} Q(s,a|\theta^Q) | s=s_t, a=\mu(s_t ; \theta ^\mu) \...


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}$ ...


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

What you're describing is off-policy learning. A classic example is $Q$-learning, where you follow some policy $\pi$ whilst learning about the greedy policy. If you're interested in actor-critic methods then a popular off-policy method is the Deep Deterministic Policy Gradient.


1

DQN is famous for doing over-approximation on Q function. However, having over approximated Q does not imply that it does not perform well in the environment. (unless it looks ridiculously high) From my experience, high learning rate usually cause over approximated Q, or mistakes made in the code. Best way to check is to see plot of Q function when running ...


1

As mentioned in the comments your assumption about independence is wrong. Here's why. To prove independence we need to show the following holds: $$P(X=x, Y=y) = P(X=x)P(Y=y)$$ in the case of RL this becomes: $$P(X=a, X=a') = P(X=a)P(Y=a')$$ The left hand side has the value: $$P(X=a, Y=a') = b(A_t = a| S_t = s) p(s'|a,s) b(A_{t+1} = a'|, S_{t+1} = s')$$ while ...


1

You can simply train a policy from the inputs to predict the actions in your dataset. You can use the cross entropy loss for this, i.e. maximize the the log probability that the policy assigns to the actions in the data set when given the corresponding inputs. This is called behavioral cloning. The result is an approximation of the behavioral policy that ...


1

In the DRL nanodegree in Udacity, the instructor says it is possible to combine on- and off-policy learning and suggests the following paper where this has been done: Q-Prop: Sample-Efficient Policy Gradient with An Off-Policy Critic (ICLR 2017). Citing the paper: The core idea is to use the first-order Taylor expansion of the critic as a control ...


1

First part is correct \begin{align} &\sum_{n=1}^{\infty} \alpha(1-\lambda)\lambda^{n-1} (\bar R_t^{(n)} - \theta^T \phi_t)\\ =& \alpha[\sum_{n=1}^{\infty} (1-\lambda)\lambda^{n-1} \bar R_t^{(n)} - \sum_{n=1}^{\infty} (1-\lambda)\lambda^{n-1} \theta^T \phi_t] \end{align} $\sum_{n=1}^{\infty} (1-\lambda)\lambda^{(n-1)}$ sums to $1$ so we have \begin{...


1

If your game agent performs any kind of advance learning from self play or database of moves, that will generate parameters for some kind of model (e.g. a table of expected values, or neural network weights to select a preferred action). This is unavoidable, and if you want to re-use the results of that machine learning, you absolutely have to store the ...


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