參考: 李宏毅老師課件

PPO = Policy Gradient 從 On-policy 到 Off-policy, 再加一些constraint

【資料圖】

Policy GradientBasic Conception

Actor: 動(dòng)作執(zhí)行者(智能體)

Env: 環(huán)境

Reward Function: 獎(jiǎng)勵(lì)函數(shù)

Policy \(\pi\) : a network with parameter \(\theta\).

Input: 當(dāng)前的 Env.

Output: actor 要采取的下一個(gè) action 的分布.

Trajectory \(\tau\): 一系列的 Env 和 Action, \(\set{s_1,a_1,s_2,a_2, \dots}\)在參數(shù)為 \(\theta\) 情況下, 發(fā)生\(\tau\)的概率: \(p_{\theta}(\tau)=p(s_1)p_{\theta}(a_1|s_1)p(s_2|s_1,a_1)p_{\theta}(a_2|s_2)\cdots\)

OptimizationObject

給定 \(\tau\), 可以計(jì)算 \(\tau\) 的 reward, \({R(\tau)}\).

對于參數(shù)為 \(\theta\) 的 Policy下, Trajectory \(\tau\) 是采樣得到的, 因此實(shí)際上需要計(jì)算的是 reward 的期望值\(\overline{R_\theta}\). 我們希望 \(\overline{R_\theta}\) 越大越好.

Policy Gradient

Reward 的期望:

\[\begin{equation} \begin{aligned} \overline{R_\theta}=\sum_\tau R(\tau)p_\theta(\tau) \end{aligned}\end{equation}\]

求 \(\theta\) 的梯度:

\[\begin{equation} \begin{aligned} \nabla \overline R_\theta &= \sum_\tau R(\tau)\nabla p_\theta(\tau) \\ &=\sum_\tau R(\tau) p_\theta(\tau) \frac{\nabla p_\theta(\tau)}{p_\theta(\tau)}\quad &&\text{分子分母同乘} p_\theta(\tau)\\ &=\sum_\tau R(\tau) p_\theta(\tau) {\nabla \log p_\theta(\tau)}\\ &=E_{\tau\sim p_\theta(\tau)}[R(\tau)\nabla \log p_\theta(\tau)]\\ &\approx \frac 1 N \sum_{n=1}^{N} R(\tau^n)\nabla \log p_\theta(\tau^n)\\ &= \frac 1 N \sum_{n=1}^{N} \sum_{t=1}^{T_n} R(\tau^n)\nabla \log p_\theta(a^n_t|s^n_t) \end{aligned}\end{equation}\]

然后由 \(\nabla \log p_\theta(\tau)=\frac{\nabla p_\theta(\tau)}{p_\theta(\tau)}\), 可得到第三行公式.此處可延伸出一個(gè)公式:

\[\begin{equation}\nabla f(x) = f(x) \nabla \log f(x)\end{equation}\]

由\(\sum_\tau p_\theta(\tau)f(\tau)=E_{\tau\sim p_\theta(\tau)}[f(\tau)]\), 可得第四行

通過采樣的方式估計(jì)期望值, 采樣 \(N\) 個(gè) Trajectory, 既第五行公式

最后將 \(p_\theta(\tau)\) 展開代入, 得第六行公式

Implementation

最大化 Reward 的期望 \(\overline{R_\theta}\), 由公式(2)中梯度的計(jì)算, 可以反推出目標(biāo)函數(shù)在實(shí)現(xiàn)時(shí)定義如下:

\[\begin{equation} \begin{aligned} J(\theta) = \frac 1 N \sum_{n=1}^{N} \sum_{t=1}^{T_n} R(\tau^n) \log p_\theta(a^n_t|s^n_t) \end{aligned}\end{equation}\]

最大化 \(object\) 等價(jià)于最小化 \(loss\):

\[\begin{equation} \begin{aligned} loss = -\frac 1 N \sum_{n=1}^{N} \sum_{t=1}^{T_n} R(\tau^n) \log p_\theta(a^n_t|s^n_t) \end{aligned}\end{equation}\]

其中, \(a^n_t, s^n_t\) 是在參數(shù)為 \(\theta\) 的 policy 下采樣得到的.

與交叉熵?fù)p失對比: 其實(shí)就是將采樣得到的 \(a^n_t\) 視作grand truth計(jì)算交叉熵, 區(qū)別在于針對不同的 Trajectory \(\tau^n\), 要多乘了一個(gè) \(R(\tau^n)\)

TipsAdd a baseline

\(R(\tau^n)\) 可能總為正數(shù), 這樣在 training時(shí), 相當(dāng)于告訴 model, 不論時(shí)什么action 都要將它的概率提升.

理想情況下, 這樣是沒有問題的, 因?yàn)?Reward 即使總是正的, 也有大有小.

當(dāng)時(shí)實(shí)際上, action 是采樣得到的, 這會(huì)導(dǎo)致如果有的 action 沒有被采樣到, 它的概率相對于被采樣到的 action 就會(huì)下降, 而這時(shí), 并不能表示當(dāng)前環(huán)境下采取這個(gè) action 不好.

改進(jìn): 減去一個(gè) baseline, \(b\).

Assign Suitable Credit

再來看一下目標(biāo)函數(shù):

\[\begin{equation} \begin{aligned} J(\theta) = \frac 1 N \sum_{n=1}^{N} \sum_{t=1}^{T_n} R(\tau^n) \log p_\theta(a^n_t|s^n_t) \end{aligned}\end{equation}\]

對于同一個(gè) Trajectory \(\tau\) 中, 針對每個(gè)狀態(tài) \(s\) 下, 執(zhí)行 動(dòng)作 \(a\), 都有相同的 Reward 系數(shù). 這是不合理的.例如圖的左邊, 在 \(s_b\) 執(zhí)行 \(a_2\) 不是一個(gè)好的選擇, 他會(huì)導(dǎo)致接下來進(jìn)入 \(s_c\), 并執(zhí)行 \(a_3\), 得到 -2 分.由此, 提出改進(jìn)1.

改進(jìn)1: 每個(gè)時(shí)刻的 reward 改為, 當(dāng)前時(shí)刻到結(jié)束時(shí)刻的 reward 的總和

某時(shí)刻的 action, 經(jīng)過越長時(shí)間, 它的影響力就越小. 也就是與該 action 間隔很久的 reward 與該 action 的關(guān)系很小. 由此提出改進(jìn)2.

改進(jìn)2: 加一個(gè)衰減系數(shù).

最后, 將整個(gè)系數(shù)項(xiàng)稱為 Advantage Function, \(A^\theta(s_t, a_t)\).其含義為, 在某 state 下, \(a_t\) 相較于其他的 action, 有多好. (這個(gè) \(A\), 通?？梢允怯靡粋€(gè)網(wǎng)絡(luò)來預(yù)測的 ???)

最終, 得梯度公式:

\[\begin{equation}\nabla \overline R_\theta \approx \frac 1 N \sum_{n=1}^{N} \sum_{t=1}^{T_n} A^\theta(s_t, a_t) \nabla\log p_\theta(a^n_t|s^n_t)\end{equation}\]On-policy \(\rightarrow\) Off-policyOn-policy

梯度計(jì)算公式:

\[\begin{equation} \nabla \overline R_\theta =E_{\tau\sim p_\theta(\tau)}[R(\tau)\nabla \log p_\theta(\tau)]\\\end{equation}\]

目前為止的做法其實(shí)是一種 on-policy 的方法:

每次更新梯度前, 都需要從 \(\pi_\theta\) 中采樣 \(\tau\).參數(shù)更新后, 又需要用更新后的參數(shù)重新采樣 \(\tau\).

目標(biāo)是: 從另一個(gè) policy, \(\pi_{\theta"}\) 中采樣數(shù)據(jù), 用來訓(xùn)練 \(\pi_\theta\). 這樣就可以重復(fù)利用這些采樣得到的數(shù)據(jù).

Importance Sampling(重要性采樣)

\(x\) 服從 \(p\) 分布時(shí), 計(jì)算 \(f(x)\) 期望 \(E_{x\sim p}[f(x)]\) 的做法: 一般是從 \(p\) 中采樣一些 \(x\), 帶入 \(f(x)\) 求平均, 用這個(gè)值來估計(jì)所求期望.

現(xiàn)在, 假設(shè)無法從 \(p\) 中直接采樣 \(x\), 但可以從另一個(gè)分布 \(q\) 中采樣 \(x\). 可以對 \(E_{x\sim p}[f(x)]\) 做如下變形:

\[\begin{equation} \begin{aligned} E_{x\sim p}[f(x)] &= \int f(x)p(x) \, dx\\ &=\int f(x)\frac{p(x)}{q(x)}q(x) \, dx\\ &= E_{x\sim q}[f(x)\frac{p(x)}{q(x)}] \end{aligned}\end{equation}\]

這樣, 我們就可以用 \(q\) 中采樣的數(shù)據(jù)來估計(jì)期望值 \(E_{x\sim p}[f(x)]\). 這就是 Importance Sampling.

Issue of Importance Sampling理論上, 我們已經(jīng)得出兩個(gè)期望值是相等的:

\[\begin{equation} E_{x\sim p}[f(x)] = E_{x\sim q}[f(x)\frac{p(x)}{q(x)}].\end{equation}\]

那么它們的方差是否相等呢? \(Var_{x\sim p}[f(x)] == Var_{x\sim q}[f(x)\frac{p(x)}{q(x)}] ?\)

由公式

\[\begin{equation}Var[x] = E[x^2]-(E[x])^2\end{equation}\]

可以得出:

\[\begin{equation} \begin{aligned} Var_{x\sim p}[f(x)]&=E_{x\sim p}[f^2(x)]-(E_{x\sim p}[f(x)])^2\\ Var_{x\sim q}[f(x)\frac{p(x)}{q(x)}] &=E_{x\sim q}[(f(x)\frac{p(x)}{q(x)})^2]-(E_{x\sim q}[f(x)\frac{p(x)}{q(x)}])^2\\ &=\int (f(x)\frac{p(x)}{q(x)})^2q(x) \, dx - (E_{x\sim p}[f(x)])^2\\ &=\int f^2(x)\frac{p(x)}{q(x)}p(x) \, dx - (E_{x\sim p}[f(x)])^2\\ &=E_{x\sim p}[f^2(x)\frac{p(x)}{q(x)}]-(E_{x\sim p}[f(x)])^2 \end{aligned}\end{equation}\]

對比發(fā)現(xiàn), 第一項(xiàng)中后者比前者多乘了一個(gè) \(\frac{p(x)}{q(x)}\), 也就是說當(dāng) \(p\) 與 \(q\) 相差很多時(shí), 它們的方差也會(huì)差很多.

這樣就會(huì)出現(xiàn)一問題: 理論上, 無論 \(p,q\) 的分布是什么樣的, 當(dāng)我們從 \(p\) 和 \(q\) 采樣足夠多次時(shí), 是可以得到 \(E_{x\sim p}[f(x)] = E_{x\sim q}[f(x)\frac{p(x)}{q(x)}]\) 的.但是當(dāng) \(p,q\) 差距過大, 而我們采樣的次數(shù)又不夠多時(shí), 因?yàn)樗鼈冎g的方差差距很大, 所以最后很可能導(dǎo)致期望差距很大.

一個(gè)直觀的例子:圖中 \(p,q\)兩個(gè)分布的差異很大.

當(dāng)我們采樣次數(shù)不夠多, 導(dǎo)致沒有采樣到最左邊那個(gè)樣本時(shí), 就會(huì)出現(xiàn)實(shí)際上 \(E_{x\sim p}[f(x)]\) 應(yīng)是一個(gè)負(fù)值, 但我們用 \(E_{x\sim q}[f(x)\frac{p(x)}{q(x)}]\) 計(jì)算出來的卻是一個(gè)正值.

而當(dāng)我們采樣到最左邊那個(gè)樣本時(shí), 因?yàn)榇藭r(shí) \(\frac{p(x)}{q(x)}\) 的值將會(huì)非常大, 所以可以把 \(E_{x\sim q}[f(x)\frac{p(x)}{q(x)}]\) 拉回負(fù)值.

Off-policy

將 Importance Sampling 用在 policy gradient 中, 我們就可以得到:

\[\begin{equation} \begin{aligned} \nabla \overline R_\theta &=E_{\tau\sim p_\theta(\tau)}[R(\tau)\nabla \log p_\theta(\tau)]\\ &=E_{\tau\sim p_{\theta"}(\tau)}[\frac{p_{\theta}(\tau)}{p_{\theta"}(\tau)}R(\tau)\nabla \log p_\theta(\tau)] \end{aligned}\end{equation}\]

這樣, 我們就可以從 \(\theta"\) 中采樣數(shù)據(jù), 然后多次利用這些數(shù)據(jù)來更新 \(\theta\).

結(jié)合公式(7), 得

\[\begin{equation} \begin{aligned} \nabla \overline R_\theta &=E_{\tau\sim p_{\theta"}(\tau)}[\frac{p_{\theta}(\tau)}{p_{\theta"}(\tau)}R(\tau)\nabla \log p_\theta(\tau)]\\ &=E_{(s_t,a_t)\sim\pi_{\theta"}}[\frac{p_\theta(s_t, a_t)}{p_{\theta"}(s_t, a_t)}A^{\theta"}(s_t, a_t) \nabla\log p_\theta(a^n_t|s^n_t)]\quad &&\text{由公式(6)得}\\ &=E_{(s_t,a_t)\sim\pi_{\theta"}}[\frac{p_\theta(a_t|s_t)p_\theta(s_t)}{p_{\theta"}(a_t|s_t)p_{\theta"}(s_t)}A^{\theta"}(s_t, a_t) \nabla\log p_\theta(a^n_t|s^n_t)]\\ &=E_{(s_t,a_t)\sim\pi_{\theta"}}[\frac{p_\theta(a_t|s_t)}{p_{\theta"}(a_t|s_t)}A^{\theta"}(s_t, a_t) \nabla\log p_\theta(a^n_t|s^n_t)]\quad &&\text{假設(shè)}p_\theta(s_t)=p_{\theta"}(s_t)\\ \end{aligned}\end{equation}\]

再由公式(3)得:

\[\begin{equation} \nabla \overline R_\theta=E_{(s_t,a_t)\sim\pi_{\theta"}}[\frac{\nabla p_\theta(a_t|s_t)}{p_{\theta"}(a_t|s_t)}A^{\theta"}(s_t, a_t)]\end{equation}\]

反推目標(biāo)函數(shù):

\[\begin{equation} J^{\theta"}(\theta)=E_{(s_t,a_t)\sim\pi_{\theta"}}[\frac{p_\theta(a_t|s_t)}{p_{\theta"}(a_t|s_t)}A^{\theta"}(s_t, a_t)]\end{equation}\]Add constraint

目前為止, 我們利用 Importance Sampling 完成了 Policy Gradient 從 On-policy 到 Off-policy 的優(yōu)化.

但是 Importance Sampling 在實(shí)際應(yīng)用中有一個(gè)不得不考慮的限制, 就是我們無法保證能采樣足夠多的數(shù)據(jù), 這時(shí)當(dāng)兩個(gè)分布 \(p_\theta, p_{\theta"}\)差異過大時(shí), 難以保證期望相等.

PPO做的事情, 簡單說就是, 限制兩個(gè)分布 \(p_\theta, p_{\theta"}\) 不能差太多.

\[\begin{equation} J_{PPO}^{\theta"}(\theta)=J^{\theta"}(\theta)-\beta KL(\theta, \theta")\end{equation}\]

注: 此處 KL 散度指的不是將兩個(gè)模型的參數(shù)看作分布,拉近兩個(gè)模型的參數(shù)的距離. 而是兩個(gè)模型行為上的距離, 就是當(dāng)兩個(gè)模型輸入同樣的 state 時(shí), 希望輸出的 action 的分布盡可能像

ConclusionPPO algorithmPPO2

PPO2: 簡化 PPO 的計(jì)算.首先, 我們將橫坐標(biāo) \(x\) 設(shè)為 \(\frac{p_\theta(a_t|s_t)}{p_{\theta^k}(a_t|s_t)}\), 則函數(shù) \(y=x\) 與 \(y=clip(x, 1-\epsilon, 1+\epsilon)\) 的圖像分別為圖中的綠線和藍(lán)線.

當(dāng) \(A>0\) 時(shí), \(J_{PPO2}^{\theta^k}(\theta)\) 就是左圖中紅線, 我們要最大化目標(biāo)函數(shù), 也就希望 \(x\) 越大越好, 但是當(dāng)超過 \(1+\epsilon\) 后, 對目標(biāo)函數(shù)就沒有 benefit 了.當(dāng) \(A<0\) 時(shí), 同理, 如右圖.

目的依舊是保證兩個(gè)分布 \(p_\theta, p_{\theta^k}\) 差距不能過大.