How to correctly compute $\rho$ in reinforcement learning with importance sampling?

Question

This question regards off-policy reinforcement learning using importance sampling.

From the paper Off-Policy Temporal Difference Learning with Function Approximation, page 3:

$\rho_t = \frac{\pi(s_t,a_t)}{b(s_t,a_t)}$

where $\rho_t$ is the importance sampling ratio for time $t$, which will get multiplied by the $\alpha$ step factor / learning rate during parameter updating.

From what I understand, $\pi(s_t,a_t)$ is the probability of selecting action $a_t$ in state $s_t$ according to the target policy $\pi$. Assuming that $\pi$ is the greedy policy (and here I'm probably wrong), wouldn't this value always be 0 (exploration action) or 1 (greedy action)? Meaning that the algorithm would never learn when performing exploratory actions?

It seems I don't quite understand how to compute $\rho$ by not understanding what exactly is being computed by that ratio. How are $\pi(s_t,a_t)$ and $b(s_t,a_t)$ (and consequently $\rho$) really computed?

Answer 1

The answer is tucked in the abstract (emphasis mine): "We prove that, given training under any $\epsilon$-soft policy [...] to the action-value function for an arbitrary target policy."

The authors also write, "We always use $\pi$ to denote the target policy, the policy that we are learning about."

Epsilon-soft is, as defined here, synonymous with epsilon-greedy:

An epsilon-soft policy chooses one action with probability $(1 - \epsilon + \frac{\epsilon}{|A(s)|)}$ and all other actions with probability $\frac{\epsilon}{|A(s)|)}$, where $|A(s)|$ is the number of actions in state $s$. This is equivalent to saying that the policy is to choose a random action with some small probability epsilon, and another single (dominant) action otherwise.

Wiki defines epsilon-greedy similarly:

One such method is $\epsilon$-greedy, when the agent chooses the action that it believes has the best long-term effect with probability $1-\epsilon$, and it chooses an action uniformly at random, otherwise.

That is, there are no restrictions on the target policy $\pi$; $b$ is epsilon-soft.

Answer 2

You are correct that with a greedy target policy $\pi$, $\pi(s_t, a_t)$ always equals either $1$ or $0$. This does not mean the algorithm cannot learn though. It only means that the algorithm can only learn from the sequence of steps up until an action was taken that the target policy (which can be greedy) would never take, because only from that point on you start multiplying by $0$.

In Section 4, it is described that the sum of all updates that occur during an episode can be written as:

\begin{equation} \sum_{t=0}^{T-1} \alpha (\bar{R}_t^\lambda - \theta^T \phi_t)\phi_t c_t, \end{equation}

where:

\begin{equation} c_t = \sum_{k=0}^{t} g_k \prod_{j=k+1}^{t} \rho_j \end{equation}

Suppose you want the target policy $\pi$ to be the greedy policy. Suppose, for example, that we took actions that match the greedy action at $t=0$ and $t=1$. This means that $c_0 > 0$ and $c_1 > 0$. Suppose that we took a non-greedy action at $t=2$. Then, from $t=2$ onwards, every $c_t$ will involve a multiplication by $0$, and therefore equal $0$. However, we still have non-zero $c_0$ and $c_1$, so the sum of all updates during the entire episode still consists of non-zero terms for $t=0$ and $t=1$, and we can still learn something from those steps.

This obviously does still mean that learning with a greedy target policy is often quite slow though, because sooner or later you'll have a multiplication by $0$ and you'll be unable to continue learning from that sequence of actions (that is: you'll be unable to continue learning more about the value of the first state-action pair in that sequence. You can still start learning again about another state-action pair, treat it as the beginning of a new sequence).

This is not a problem just with a greedy target policy though. The method has high variance whenever the target policy and the policy used to select actions are very different from each other. Whenever the policies are very different from each other, the multiplications can rapidly get very close to $0$ if you keep playing actions that are unlikely according to the target policy, or rapidly become way too large if, by chance, you happen to keep playing many actions that were unlikely according to the policy $b$, but coincidentally are all really likely according to the target policy.

---

The assumption that Sean was talking about holds for the policy used to select actions (the policy $b$), this assumption is not required for the target policy $\pi$. $b(s_t, a_t)$ needs to be nonzero for any $s_t$, $a_t$ pair, because otherwise you get a division by zero.