Policy Criterion Ⅱ

假设修改马尔可夫决策过程的奖励, 在原奖励的基础上增加一个熵奖励, 即 $r^t\to r_t+{\alpha }_{H}H[\pi (\cdot |s_t)]$. ($H[\pi (\cdot |s)]=-{\sum }_a\pi (a|s)\ln \pi (a|s)$)

显然, 更改奖励后的马尔可夫决策过程仍然构成一个马尔可夫决策过程, 设其奖励函数为 $R^{(H)}$, 则
$$R_H(s,a,s^{\prime })=R(s,a,s^{\prime })+{\alpha }_{H}H[\pi (\cdot |s)],s\in \mathcal{S},a\in \mathcal{A},s^{\prime }\in \mathcal{S}$$

(修改奖励后的其他概念均加注下标或上标$H$以表区分)

Soft Q

引入一个抛去首个奖励中的熵奖励的动作价值函数(柔性动作价值函数):
$$Q_{soft}^{\pi }(s,a)={\mathbb{E}}_{{\tau }_{|}{s}_0=s,a_0=a\pi }[r_0+\sum _{i=1}^{\infty }{\gamma }^i{r}_i^H]={\mathbb{E}}_{{\tau }_t|s_t=s,a_t=a,\pi }[r_t+\sum _{i=1}^{\infty }{\gamma }^i{r}_{i+t}^H],s\in \mathcal{S},a\in \mathcal{A}$$
显然:
$$Q_{soft}^{\pi }(s,a)=Q_H^{\pi }(s,a)-{\alpha }_{H}H[\pi (\cdot |s)],s\in \mathcal{S},a\in \mathcal{A}$$

“柔性” 译自 “soft”

此外, $V_H^{\pi }$ 与 $Q_{soft}^{\pi }$ 具有这样的关系:

[1] $V_H^{\pi }(s)={\mathbb{E}}_{a\sim \pi (\cdot |s)}{Q}_{soft}^{\pi }(s,a)+{\alpha }_{H}H[\pi (\cdot |s)]$, $s\in \mathcal{S}$.

证明:
VHπ(s)=Ea∼π(⋅∣s)QHπ(s,a)=Ea∼π(⋅∣s){Qsoftπ(s,a)+αHH[π(⋅∣s)]}=Ea∼π(⋅∣s)Qsoftπ(s,a)+αHH[π(⋅∣s)], s∈S \begin{align} V^{\pi}_{H}(s) &= \mathbb{E}_{a\sim \pi(\cdot|s)}Q_{H}^{\pi}(s,a)\notag\\ &= \mathbb{E}_{a\sim \pi(\cdot|s)} \{Q^{\pi}_{soft}(s,a) + \alpha_{H}H[\pi(\cdot|s)]\}\notag\\ &=\mathbb{E}_{a\sim \pi(\cdot|s)}Q_{soft}^{\pi}(s,a) + \alpha_{H}H[\pi(\cdot|s)], \ s\in \mathcal{S} \end{align} VHπ​(s)​=Ea∼π(⋅∣s)​QHπ​(s,a)=Ea∼π(⋅∣s)​{Qsoftπ​(s,a)+αH​H[π(⋅∣s)]}=Ea∼π(⋅∣s)​Qsoftπ​(s,a)+αH​H[π(⋅∣s)], s∈S​​
[2] $Q_{soft}^{\pi }(s,a)={\mathbb{E}}_{s^{\prime }\sim T(s,a)}[R(s,a,s^{\prime })+\gamma V_H^{\pi }(s^{\prime })]$, $s\in \mathcal{S}$, $a\in \mathcal{A}$.

证明:
$$Q_{soft}^{\pi }(s,a)=Q_H^{\pi }(s,a)-{\alpha }_{H}H[\pi (\cdot |s)]$$

$$Q_H^{\pi }(s,a)={\mathbb{E}}_{{\tau }_t|s_t=s,a_t=a,\pi }[r_t^H+\gamma V_H^{\pi }(s_{t+1})]={\mathbb{E}}_{{\tau }_t|s_t=s,a_t=a,\pi }[r_t+\gamma V_H^{\pi }(s_{t+1})]+{\alpha }_{H}H[\pi (\cdot |s)]$$

$$Q_{soft}^{\pi }(s,a)={\mathbb{E}}_{{\tau }_t|s_t=s,a_t=a,\pi }[r_t+\gamma V_H^{\pi }(s_{t+1})]$$

由此可知
$$Q_{soft}^{\pi }(s,a)={\mathbb{E}}_{s^{\prime }\sim T(s,a)}[R(s,a,s^{\prime })+\gamma V_H^{\pi }(s^{\prime })]$$
定义策略的评判标准为如下. 若策略 $\pi$ 和 $\tilde{\pi }$ 满足: $Q_{soft}^{\pi }(s,a)\ge Q_{soft}^{\tilde{\pi }}(s,a)$, $s\in \mathcal{S}$, $a\in \mathcal{A}$, 则称 $\pi$ 不差于 $\tilde{\pi }$, 进一步地若存在 $s_0\in \mathcal{S}$, $a_0\in \mathcal{A}$, 使得 $Q_{soft}^{\pi }(s_0,a_0)>Q_{soft}^{\tilde{\pi }}(s_0,a_0)$, 则称 $\pi$ 优于 $\tilde{\pi }$.

Soft V

定义柔性状态价值函数: Vsoftπ(s)=αHln⁡∑aexp⁡{1αHQsoftπ(s,a)}V^{\pi}_{soft}(s)=\alpha_{H}\ln \sum_{a}\exp\{\frac{1}{\alpha_{H}}Q^{\pi}_{soft}(s,a)\}Vsoftπ​(s)=αH​ln∑a​exp{αH​1​Qsoftπ​(s,a)}, $s\in \mathcal{S}$.

引入记号 $\mathrm{logsumexp}$, $\underset{x\in \mathcal{X}}{\mathrm{logsumexp}}(f(x))$: logsumexpx∈X(x)=ln⁡∑x∈Xexp⁡{f(x)}\mathop{\mathrm{logsumexp}}\limits_{x\in \mathcal{X}}(x)= \ln \sum_{x\in \mathcal{X}}\exp\{f(x)\}x∈Xlogsumexp​(x)=ln∑x∈X​exp{f(x)}.

则 $V_{soft}^{\pi }(s)={\alpha }_H\underset{a\in \mathcal{A}}{\mathrm{logsumexp}}(\frac{1}{{\alpha }_H}{Q}_{soft}^{\pi }(s,a))$.

定义柔性优势函数: $A_{soft}^{\pi }(s,a)=Q_{soft}^{\pi }(s,a)-V_{soft}^{\pi }(s)$.

Policy Improvement Theorem

定理. 如果一个策略 $\tilde{\pi }$ 满足:
$$V_H^{\pi }(s)={\alpha }_{H}H[\pi (\cdot |s)]+{\mathbb{E}}_{a\sim \pi (\cdot |s)}[Q_{soft}^{\pi }(s,a)]\le {\alpha }_{H}H[\tilde{\pi }(\cdot |s)]+{\mathbb{E}}_{a\sim \tilde{\pi }(\cdot |s)}[Q_{soft}^{\pi }(s,a)],s\in \mathcal{S}$$
则这个策略比当前的策略更好.

证明: 这个条件等价于:
$$V_H^{\pi }(s)\le {\alpha }_{H}H[\tilde{\pi }(\cdot |s)]+{\mathbb{E}}_{a\sim \tilde{\pi }(\cdot |s)}{\mathbb{E}}_{s^{\prime }\sim T(s,a)}[R(s,a,s^{\prime })+\gamma V^{\pi }(s^{\prime })]$$
其中 $RHS={\mathbb{E}}_{a_t,s_{t+1}|s_t=s,\tilde{\pi }}[{\alpha }_{H}H[\tilde{\pi }(\cdot |s_t)]+r_t+\gamma V_H^{\pi }(s_{t+1})]={\mathbb{E}}_{a_t,s_{t+1}|s_t=s,\tilde{\pi }}[r_t^H+\gamma V^{\pi }(s_{t+1})]$, (RHS: Right-Hand-Side, 表示右侧的式子; LHS: Left-Hand-Side, 表示左侧的式子)
$$V_H^{\pi }(s_t){|}_{s_t=s}\le {\mathbb{E}}_{a_t,s_{t+1}|s_t=s,\tilde{\pi }}[{\alpha }_{H}H[\tilde{\pi }(\cdot |s_t)]+r_t+\gamma V_H^{\pi }(s_{t+1})]={\mathbb{E}}_{a_t,s_{t+1}|s_t=s,\tilde{\pi }}[r_t^H+\gamma V^{\pi }(s_{t+1})]$$

$${\mathbb{E}}_{\tau |s_0=s,\tilde{\pi }}{V}_H^{\pi }(s_t)={\mathbb{E}}_{s_t|s_0=s,\tilde{\pi }}{V}_H^{\pi }(s_t)\le {\mathbb{E}}_{s_t|s_0=s,\tilde{\pi }}{\mathbb{E}}_{a_t,s_{t+1}|s_t,\tilde{\pi }}[r_t^H+\gamma V_H^{\pi }(s_{t+1})]={\mathbb{E}}_{\tau |s_0=s,\tilde{\pi }}[r_t^H+\gamma V_H^{\pi }(s_{t+1})]$$

$$Q_{soft}^{\pi }(s,a)={\mathbb{E}}_{\tau |s_0=s,a_0=a,\pi }[r_0+\gamma V_H^{\pi }(s_1)]$$

$r_0$与$V_H^{\pi }(s_{t+1})$都与$\pi$无关, 因此
$${\mathbb{E}}_{\tau |s_0=s,a_0=a,\pi }[r_0+\gamma V_H^{\pi }(s_1)]={\mathbb{E}}_{\tau |s_0=s,a_0=a,\tilde{\pi }}[r_0+\gamma V_H^{\pi }(s_1)]$$

$$\begin{array}{rl}{\mathbb{E}}_{\tau |s_0=s,a_0=a,\tilde{\pi }}[r_0+\gamma V_H^{\pi }(s_1)]& \le {\mathbb{E}}_{\tau |s_0=s,a_0=a,\tilde{\pi }}[r_0+\gamma r_1^H+{\gamma }^2{V}_H^{\pi }(s_2)]\\ & \le {\mathbb{E}}_{\tau |s_0=s,a_0=a,\tilde{\pi }}[r_0+\gamma r_1^H+{\gamma }^2{r}_2^H+{\gamma }^3{V}_H^{\pi }(s_3)]\\ & \le ...\end{array}$$

进而
$$Q_{soft}^{\pi }(s,a)\le {\mathbb{E}}_{\tau |s_0=s,a_0=a,\tilde{\pi }}[r_0+\sum _{i=1}^{\infty }{\gamma }^i{r}_i^H]=Q_{soft}^{\tilde{\pi }}(s,a)$$
注: 这个条件等价于
$$D_{KL}(\tilde{\pi }(\cdot |s)||Q_{soft}^{\pi }(s,a))\ge D_{KL}(\pi (\cdot |s)||Q_{soft}^{\pi }(s,a))$$

证明略.

定理. 策略 $\tilde{\pi }$: π~(a∣s)=exp⁡{1αHAsoftπ(s,a)}\tilde{\pi}(a|s)=\exp\{\frac{1}{\alpha_{H}}A^{\pi}_{soft}(s,a)\}π~(a∣s)=exp{αH​1​Asoftπ​(s,a)}, $s\in \mathcal{S}$, $a\in \mathcal{A}$ 是一个不差于当前策略的策略.

证明: 只需证明: ${\alpha }_{H}H[\pi (\cdot |s)]+{\mathbb{E}}_{a\sim \pi (\cdot |s)}[Q_{soft}^{\pi }(s,a)]\le {\alpha }_{H}H[\tilde{\pi }(\cdot |s)]+{\mathbb{E}}_{a\sim \tilde{\pi }(\cdot |s)}[Q_{soft}^{\pi }(s,a)],s\in \mathcal{S}$.

两边同减 $V_{soft}^{\pi }(s)$, 得:
$${\alpha }_{H}H[\pi (\cdot |s)]+{\mathbb{E}}_{a\sim \pi (\cdot |s)}[A_{soft}^{\pi }(s,a)]\le {\alpha }_{H}H[\tilde{\pi }(\cdot |s)]+{\mathbb{E}}_{a\sim \tilde{\pi }(\cdot |s)}[A_{soft}^{\pi }(s,a)]$$

$$RHS={\mathbb{E}}_{a\sim \tilde{\pi }(\cdot |s)}[-{\alpha }_H\ln \tilde{\pi }(\cdot |s)+A_{soft}^{\pi }(s,a)]={\mathbb{E}}_{a\sim \tilde{\pi }(\cdot |s)}[-{\alpha }_H\ln \tilde{\pi }(\cdot |s)+{\alpha }_H\ln \tilde{\pi }(a|s)]=0$$

$$LHS={\mathbb{E}}_{a\sim \tilde{\pi }(\cdot |s)}[-{\alpha }_H\ln \pi (\cdot |s)+{\alpha }_H\ln \tilde{\pi }(a|s)]={\alpha }_H{\mathbb{E}}_{a\sim \tilde{\pi }(\cdot |s)}[\ln \frac{\tilde{\pi }(a|s)}{\pi (a|s)}]={\alpha }_H{D}_{KL}(\tilde{\pi }(a|s)||\pi (a|s))\ge 0$$

证毕.