CSE510 Deep Reinforcement Learning (Lecture 15)

Motivation

For policy gradient methods over stochastic policies

\pi_\theta(a|s) = P[a|s,\theta]

Advantages

Potentially learning optimal solutions for multi-agent settings
Dealing with partial observable settings
Sufficient exploration

Disadvantages

Can not learning a deterministic policy
Extension to continuous action space is not straightforward

On-Policy vs. Off-Policy Policy Gradients

On-Policy Policy Gradients:

Training samples are collected according to the current policy.

Off-Policy Algorithms:

Enable the reuse of past experience.
Samples can be collected by an exploratory behavior policy.

How to design off-policy policy gradient?

Using importance sampling

Off-Policy Actor-Critic (OffPAC)

Stochastic Behavior Policy for exploration.

For collecting data. Labelled as $\beta(a|s)$

The objective function is:

\begin{aligned} J(\theta)=\mathbb{E}_{s\sim d^\beta}[V^{\pi}(s)] &= \sum_{s\in S} d^\beta(s) \sum_{a\in A} \pi_\theta(a|s) Q^{\pi}(s,a)\\ \end{aligned}

$d^\beta(s)$ is the stationary distribution under the behavior policy $\beta(a|s)$ .

Solving the Off-Policy Policy Gradient

\begin{aligned} \nabla_\theta J(\theta) &= \nabla_\theta \mathbb{E}_{s\sim d^\beta}\left[\sum_{a\in A} \pi_\theta(a|s) Q^{\pi}(s,a)\right]\\ &= \mathbb{E}_{s\sim d^\beta}\left[\sum_{a\in A} \nabla_\theta \pi_\theta(a|s) Q^{\pi}(s,a)+\pi_\theta(a|s) \nabla_\theta Q^{\pi}(s,a)\right]\\ &= \mathbb{E}_{s\sim d^\beta}\left[\sum_{a\in A} \nabla_\theta \pi_\theta(a|s) Q^{\pi}(s,a)\right]\\ &= \mathbb{E}_{s\sim d^\beta}\left[\sum_{a\in A} \beta(a|s) \frac{1}{\beta(a|s)} \nabla_\theta \pi_\theta(a|s) Q^{\pi}(s,a)\right]\\ &= \mathbb{E}_{s\sim d^\beta}\left[\sum_{a\in A} \beta(a|s) \nabla_\theta \log \beta(a|s) Q^{\pi}(s,a)\right]\\ &= \mathbb{E}_{\beta}\left[\frac{1}{\beta(a|s)} \nabla_\theta \pi_\theta(a|s) Q^{\pi}(s,a)\right]\\ &= \mathbb{E}_{\beta}\left[\frac{\pi_\theta(a|s)}{\beta(a|s)} Q^{\pi}(s,a)\nabla_\theta \log \pi_\theta(a|s)\right]\\ \end{aligned}

To compute the off-policy policy gradient, $Q^{\pi}(s,a)$ is estimated given data collected by $\beta$ .

Common solution:

Importance sampling
Tree backup
Gradient temporal-difference learning
Retrace [Munos et al., 2016] IMPALA

Importance Sampling

Assume that samples come in the form of episodes.

$M$ is the number of episodes containing $(s,a), t_m$ be the first time when $(s,a)$ appears in episode $m$ .

The first-visit importance sampling estimator of $Q^{\pi}(s,a)$ is:

Q^{IS}(s,a)\coloneqq \frac{1}{M}\sum_{m=1}^M R_m w_m

$R_m$ is the return following $(s,a)$ in episode $m$ .

R_m\coloneqq r_{t_m +1}+\gamma r_{t_m +2}+\cdots+\gamma^{T_m-t_m -1} r_{T_m}

$w_m$ is the importance sampling weight:

w_m\coloneqq \frac{\pi(a_{t_m}|s_{t_m})}{\beta(a_{t_m}|s_{t_m})}\frac{\pi(a_{t_m+1}|s_{t_m+1})}{\beta(a_{t_m+1}|s_{t_m+1})}\cdots\frac{\pi(a_{T_m}|s_{T_m})}{\beta(a_{T_m}|s_{T_m})}

Per-decision algorithm

Consider the parts we used in importance sampling:

R_m w_m=\sum_{i=t_m+1}^{T_m}\gamma^{i-t_m-1} r_i \frac{\pi(a_{t_m}|s_{t_m})}{\beta(a_{t_m}|s_{t_m})}\cdots \frac{\pi(a_{t_{i-1}}|s_{t_{i-1}})}{\beta(a_{t_{i-1}}|s_{t_{i-1}})}\frac{\pi(a_{t_i}|s_{t_i})}{\beta(a_{t_i}|s_{t_i})}\cdots \frac{\pi(a_{T_m-1}|s_{T_m-1})}{\beta(a_{T_m-1}|s_{T_m-1})}

Intuitively, $r_i$ should not depend on the actions taken after $t_i$ .

This gives the per-decision importance sampling estimator:

Q^{PD}(s,a)\coloneqq \frac{1}{M}\sum_{m=1}^M \sum_{k=1}^{T_m-t_m} \gamma^{k-1} r_{t_m+k}\prod_{i=t_m}^{t_m+k-1} \frac{\pi(a_{t_i}|s_{t_i})}{\beta(a_{t_i}|s_{t_i})}

The per-decision importance sampling estimator is consistence and unbiased estimator of $Q^{\pi}(s,a)$ .

Proof as exercise.

Hints

- Show the expectation of $Q^{PD}(s,a)$ is the same as $Q^{IS}(s,a)$. - $Q^{IS}(s,a)$ is a consistence and unbiased estimator of $Q^{\pi}(s,a)$.

Deterministic Policy Gradient (DPG)

The objective function is:

J(\theta)=\int_{s\in S} \rho^{\mu}(s) r(s,\mu_\theta(s)) ds

where $\rho^{\mu}(s)$ is the stationary distribution under the behavior policy $\mu_\theta(s)$ .

Proof along the same lines of the standard policy gradient theorem.

\nabla_\theta J(\theta) = \mathbb{E}_{\mu_\theta}[\nabla_\theta Q^{\mu_\theta}(s,a)]=\mathbb{E}_{s\sim \rho^{\mu}}[\nabla_\theta \mu_\theta(s) \nabla_a Q^{\mu_\theta}(s,a)\vert_{a=\mu_\theta(s)}]

Issues for DPG

The formulations up to now can only use on-policy data.