CS229 Lesson 20 策略搜索

课程视频地址：http://open.163.com/special/opencourse/machinelearning.html

课程主页：http://cs229.stanford.edu/

更具体的资料链接：https://www.jianshu.com/p/0a6ef31ff77a

笔记参考自中文翻译版：https://github.com/Kivy-CN/Stanford-CS-229-CN

这一讲没有找到对应笔记，这里主要回顾策略搜索。

视频里主要介绍如下内容

• 策略搜索
• Reinforced
• Pegasus

后面两个内容的PPT没有找到，所以这里主要介绍策略搜索。

策略搜索

定义集合$\Pi$为策略集合，我们的目标是找到好的$\pi \in \Pi$。

随机策略是如下函数

$$\pi : S\times A \mapsto \mathbb R$$

其中$\pi(s,a)$是在状态$s$采取行动$a$的概率，因此

$$\sum_{a} \pi (s,a) =1, \pi(s,a)\ge 0$$

考虑倒立摆的例子，$\phi$表示摆和竖直方向的夹角，行动$a_1$表示向右加速，行动$a_2$表示向左加速，定义随机策略

$$\begin{aligned} \pi_\theta (s,a_1) &= \frac 1{1+e^{-\theta^T s}}\\ \pi_\theta (s,a_2) &= 1-\frac 1{1+e^{-\theta^T s}} \end{aligned}$$

例如

$$s= \left( \begin{matrix} 1\\ x \\ \dot x \\ \phi \\ \dot \phi \end{matrix} \right), \theta= \left( \begin{matrix} 0\\ 0 \\ 0 \\ 1 \\ 0 \end{matrix} \right) \\ P(a=\text{"right"})= \frac 1{1+e^{-\theta^T s}} = \frac 1{1+e^{-\phi}}$$

如果有多个行动，我们可以将上述随机策略推广为

$$\theta_1,...,\theta_d , \pi _{\theta}(s,a_i)=\frac{e^{\theta_i^T s}}{\sum_j e^{\theta_j^T s}}$$

我们的目标是

$$\max_{\theta} \mathbb E[R(s_0,a_0)+...+ R(s_T,a_T)| \pi_\theta,s_\theta]$$

不难看出，对于某个固定的初始状态

$$\begin{aligned} \mathbb E[R(s_0,a_0)+...+ R(s_T,a_T)| \pi_\theta,s_\theta] &=\sum_{s_0a_0...s_T a_T}P(s_0a_0...s_T a_T)[R(s_0,a_0)+...+ R(s_T,a_T)]\\ &=\sum_{s_0a_0...s_T a_T}P(s_0)\pi_{\theta}(s_0,a_0)P_{s_0a_0}(s_1) \pi_{\theta}(s_1,a_1)... ...\pi_{\theta}(s_T a_T)[R(s_0,a_0)+...+ R(s_T,a_T)]\\ &=\sum_{s_0a_0...s_T a_T}P(s_0)\pi_{\theta}(s_0,a_0)P_{s_0a_0}(s_1) \pi_{\theta}(s_1,a_1)... ...\pi_{\theta}(s_T a_T)\times \text{pay off} \end{aligned}$$

其中

$$\text{pay off}= R(s_0,a_0)+...+ R(s_T,a_T)$$

对于这个优化问题，我们有如下算法：

• 循环{

  • 取样$s_0,a_0,s_1,a_1,…,s_T,a_T$

  • 计算$\text{pay off}= R(s_0,a_0)+…+ R(s_T,a_T)$

  • 更新：

    $$\theta:= \theta + \alpha \Big[ \frac{\nabla_{\theta}\pi_{\theta}(s_0,a_0)}{\pi_{\theta}(s_0,a_0)}+ ...+ \frac{\nabla_{\theta}\pi_{\theta}(s_T,a_T)}{\pi_{\theta}(s_T,a_t)} \Big]\times \text{pay off}$$

  }

为了解释这个算法，我们来计算

$$\mathbb E\Big[\Big( \frac{\nabla_{\theta}\pi_{\theta}(s_0,a_0)}{\pi_{\theta}(s_0,a_0)}+ ...+ \frac{\nabla_{\theta}\pi_{\theta}(s_T,a_T)}{\pi_{\theta}(s_T,a_t)} \Big)\times \text{pay off} \Big]$$

注意到

$$\frac {d} {d\theta} f(\theta)g(\theta) h(\theta) =f'(\theta)g(\theta) h(\theta)+ f(\theta)g'(\theta) h(\theta)+ f(\theta)g(\theta) h'(\theta)$$

以及

$$\mathbb E[R(s_0,a_0)+...+ R(s_T,a_T)| \pi_\theta,s_\theta] =\mathbb E[\text{pay off}]$$

所以

$$\begin{aligned} \nabla_\theta \mathbb E[\text{pay off}] &=\sum_{s_0a_0...s_T a_T}\Big[ P(s_0)(\nabla_{\theta}\pi_{\theta}(s_0,a_0))P_{s_0a_0}(s_1) \pi_{\theta}(s_1,a_1)......\pi_{\theta}(s_T a_T)+\\ &P(s_0)\pi_{\theta}(s_0,a_0)P_{s_0a_0}(s_1) (\nabla_{\theta}\pi_{\theta}(s_1,a_1))......\pi_{\theta}(s_T a_T)+\\ &P(s_0)\pi_{\theta}(s_0,a_0)P_{s_0a_0}(s_1) \pi_{\theta}(s_1,a_1)......(\nabla_{\theta}\pi_{\theta}(s_T a_T)) \Big]\times \text{pay off}\\ &=\sum_{s_0a_0...s_T a_T}P(s_0)\pi_{\theta}(s_0,a_0)P_{s_0a_0}(s_1) \pi_{\theta}(s_1,a_1)... ...\pi_{\theta}(s_T a_T)\times \Big[ \frac{\nabla_{\theta}\pi_{\theta}(s_0,a_0)}{\pi_{\theta}(s_0,a_0)}+ ...+ \frac{\nabla_{\theta}\pi_{\theta}(s_T,a_T)}{\pi_{\theta}(s_T,a_t)} \Big]\times \text{pay off}\\ &=\sum_{s_0a_0...s_T a_T}P(s_0a_0...s_T a_T)\times\Big[ \frac{\nabla_{\theta}\pi_{\theta}(s_0,a_0)}{\pi_{\theta}(s_0,a_0)}+ ...+ \frac{\nabla_{\theta}\pi_{\theta}(s_T,a_T)}{\pi_{\theta}(s_T,a_t)} \Big]\times \text{pay off}\\ &=\mathbb E\Big[\Big( \frac{\nabla_{\theta}\pi_{\theta}(s_0,a_0)}{\pi_{\theta}(s_0,a_0)}+ ...+ \frac{\nabla_{\theta}\pi_{\theta}(s_T,a_T)}{\pi_{\theta}(s_T,a_t)} \Big)\times \text{pay off} \Big] \end{aligned}$$

所以之前的算法实际上是随机梯度上升算法。

现在，如果我们有对$s​$的近似$\hat s​$（例如可以利用卡尔曼滤波器计算出$\hat s =s_{t|t}​$），然后计算随机策略

$$\pi_{\theta}(\hat s, a)=\frac 1 {1 +e^{-\theta^T \hat s}}$$