有人说人工智能就是 DL + RL ，前者作为工具、手段提供抽象的、高层的信息，后者作为老板通过这些信息做决策，这才是人工智能。从某种角度来讲，「强化学习」才是人工智能里面的核心。无论用不用「深度学习」，我们都可以通过各类算法、程序去获取、处理信息；但是决策，不是简单的 if-else 而是一个复杂的系统，不能被轻易代替。

接下来，我们开始接触、学习这个有效而又古老的「强化学习」，进入我们的第一课「Markov Decision Process」。

课程资料：ML-16: Reinforcement Learning

Introduction

强化学习最核心三要素是：

  • states s(t) 状态
  • actions a(t) 动作/行为
  • rewards R(t) 奖励/惩罚

除了三要素之外，我们还有一个 Environment 即我们的 agent 所要捕获、观察、决策的环境。一般来说，环境不会随着时间进行改变，但是状态（state）一般而言会跟随动作（action）的执行而变化。

最重要的是，Reward 是基于 $(s^{(t)}, a^{(t)}, s^{(t+1)})$ 的。


Overview of RL

学习的目标：最好的 policy $\pi^{*}(s^{(t)})$ ，使得我们累积起来的 Reward 最大，即 $\sum_{t} {R(t)}$ 最大。

训练过程有两步：不断地尝试、从尝试中学习经验。

对比有监督、无监督学习

强化学习

$\pi^{*}(s^{(t)}) = a^{(t)}$ 最大化我们的 Total Reward 。

=> 数据有前后依赖的，$s^{(t+1)}$ 依赖于 $s^{(t)}$ 甚至是 $s^{(t-1)}$ 等等。

监督、无监督学习

$f(x^{(i)}) = y^{(i)}$ 最小化我们的 Total Loss 。

=> 数据样本都是 i.i.d （独立同分布）的。

No what to predict $(y^{(i)} ‘s)$, just how good a prediction is $(R^{(t)} ‘s)$.

=> RL 不是预测下一步是什么，即 $(y^{(i)} ‘s)$；而是预测下一步有多好，即 $(R^{(t)} ‘s)$ 。

应用

制定序列式决策

比如，下象棋、下围棋之类的，在阿里的商品排序也有应用。

控制问题

比如，机器人、模拟人的行为，国外有学校如 CMU 等都在做。

Markov Property

MDP 中最重要的就是 Markov Property（马尔可夫性），这个性质把各种冗长、复杂的时间序列，变成了抽象的元组。使得 t+1 的状态只与 t 有关，大大简化了我们模型，方便了我们计算。（$P$ 是概率）

$$P(s^{(t+1)}|s^{(t)},s^{(t-1)},…)=P(s^{(t+1)}|s^{(t)})$$

=> 即下一个动作只与当前动作、状态有关

如果满足 Markov Property 我们就可以使用 MDP 来做强化学习，就可以将现实抽象成一个数学模型问题。

Markov Process 常见类型

States are FULLY observable States are PARTIALLY observable
Transition is AUTONOMOUS Markov Chains Hidden Markov models(HMMs)
Transition is CONTROLLED Markov Decision Processes(MDP) Partially observable MDP

Markov Decision Process

Markov Decision Process(MDP) 由以下元素组成：

  • $S$ 所有状态空间（state space）；$A$ 所有可能动作的空间（action space）
  • 起始状态 $s^{(0)}$
  • $P(s’|s;a)$ 转移矩阵（transition distribution），受动作（actions）影响，一般不随时间变化
  • $R(s,a,s’)$ 即 $R(s’)$ ，通常这个是确定的，不是有概率的
  • $\gamma \subset [0,1]$ 是折扣因子（discount factor）
  • $H$ 是深度（Horizon），思考的步数。整数，可以是无穷的（infinite）

给定一个策略（policy） $\pi^{*}(s) = a$ ，则 MDP 的处理过程如下：


Overview of SA

累积的 Total Reward 为：

$$R(s^{(0)}, a^{(0)}, s^{(1)}) + {\gamma}R(s^{(1)}, a^{(1)}, s^{(2)})+…+ {\gamma}^{H-1}R(s^{(H-1)}, a^{(H-1)}, s^{(H)})$$

从上式我们就理解，折扣因子 $\gamma$ 越大则看的越远，越有大局观；反之，则越小越看眼前的利益。

那么我们将上式归纳总结，给定一个策略（policy） $\pi$ ，则期望累积的 Total Reward 为 $V_{\pi}$ 。

$$V_{\pi}=E_{s^{(0)},…,s^{(H)}}(\sum_{(t=0)}^{H}{\gamma}^tR(s^{(t)}, \pi(s^{(t)}), s^{(t+1)});\pi)$$

那么我们的目标就是寻找最优的策略（optimal policy）$\pi^*$ ：

$$\pi^* = \arg \max_{\pi}{V_\pi}$$

通俗的理解就是，我们会有非常多个策略（policy）$\pi$，找到一个 $\pi^*$ 使得 $V_{\pi}$ 最大。

接下来寻找最优策略（policy）$\pi^*$ 的方式有两种：

  • Value Iteration
  • Policy Iteration

注：前提都是问题能被转化成 MDP 。

Value Iteration

我们的目标函数如下：

$$\pi^*=\arg \max_{\pi}E_{s^{(0)},…,s^{(H)}}(\sum_{t=0}^{H}{\gamma}^tR(s^{(t)}, \pi(s^{(t)}), s^{(t+1)});\pi)$$

Finite Horizon

Optimal Value Function:

$$V^{*(h)}(s)=\max_{\pi}E_{s^{(1)},…,s^{(h)}}(\sum_{t=0}^{h}{\gamma}^tR(s^{(t)}, \pi(s^{(t)}), s^{(t+1)})|s^{(0)}=s;\pi)$$

上式的意思就是，从 $s$ 状态开始走 $h$ 步，我们可以得到最大的 Accumulated Reward 。

那么对每个 $s$ 有了 $V^{*(H-1)}(s)$ ，我们可以更加简单的的解出 $\pi^*$ 通过以下的式子：

$$\pi^{*}(s)=\arg\max_{a}\sum_{s’}{P(s’|s;a)[R(s,a,s’) + \gamma V^{*(H-1)}(s’)]}, \forall s$$

并在 $O(|S||A|)$ 的时间内得出我们的解。

简单粗暴地理解，这个式子分为两部分：一个是采取下一个行为的 Reward ，另一个是执行后状态 $s’$ 累积 Reward 的期望。

那么现在的核心问题就是对于每一个 $s$ 怎么去求解 $\gamma V^{*(H-1)}(s)$ 这个呢？

回顾我们的 Optimal Value Function 的式子，将 $h=H-1$ 、$h=H-2$ 代入，我们可以发现这是一个递归式：

$h=H-1$

$$V^{*(H-1)}(s)=\max_{a}\sum_{s’}{P(s’|s;a)[R(s,a,s’) + \gamma V^{*(H-2)}(s’)]}, \forall s$$

$h=H-2$

$$V^{*(H-2)}(s)=\max_{a}\sum_{s’}{P(s’|s;a)[R(s,a,s’) + \gamma V^{*(H-3)}(s’)]}, \forall s$$

$h=0$ ，初始状态的 value 值

$$V^{*(0)}(s)=\max_{a}\sum_{s’}{P(s’|s;a)[R(s,a,s’) + \gamma V^{*(-1)}(s’)]}, \forall s$$

$h=-1$ ，约定为 $0$ 用于后续计算

$$V^{*(-1)}(s)=0, \forall s$$

如上，这就是 Dynamic Programming 算法的思路，总结如下：


Value Iteration - Finite Horizon

Infinite Horizon

当没有 Horizon 即当 $h \rightarrow \infty$ 时，我们可以得到著名的 Bellman Optimality Equation ：

Bellman Optimality Equation

$$V^{*}(s)=\max_{a}\sum_{s’}{P(s’|s;a)[R(s,a,s’) + \gamma V^{*}(s’)]}, \forall s$$

Optimal Policy

$$\pi^{*}(s)=\arg\max_{a}\sum_{s’}{P(s’|s;a)[R(s,a,s’) + \gamma V^{*}(s’)]}, \forall s$$

我们会发现，当 $h \rightarrow \infty$ 时：

  • Stationary：遇到任何一个 state ，最优 action 是固定的（存储更高效）
  • Memoryless：只与初始状态有关

Value Iteration - Infinite Horizon

Convergence

Value iteration converges and gives the optimal $\pi^{*}$ when $h \rightarrow \infty$.

价值迭代（Value Iteration）最后是会收敛的，且当 $h \rightarrow \infty$ 时会给出最优策略 $\pi^{*}$ 。

Policy Iteration

回顾一下，我们的迭代就是为了找最优的策略（Policy） $\pi^{*}$ ：

$$\pi^* = \arg \max_{\pi}{V_\pi}$$

那么我们可以直接尝试找最好的策略 $^{*}$ 即找最优的 $V_\pi(s)$ ，则我们对给定的 $\pi$ 有如下的 Value Function:

Value Function

$$V_{\pi}(s)=E_{s^{(1)},…,s^{(h)}}(\sum_{t=0}^{\infty}{\gamma}^tR(s^{(t)}, \pi(s^{(t)}), s^{(t+1)})|s^{(0)}=s;\pi)$$

那么很直观的就是，我们随机初始化一个 $\pi(s)$ 然后用 $V_{\pi}(s)$ 去衡量，找到比当前 $\pi(s)$ 有更好表现的 $\hat\pi(s)$ 。


Policy Iteration - Simplified

Evaluate

得到了上面最简版本的算法，那么我们就要去评估 $V_{\pi}(s)$ 的好坏，这就引出了我们的 Bellman Expectation Equation：

Bellman Expectation Equation

$$V_{\pi}(s)=\sum_{s’}{P(s’|s;a)[R(s,a,s’) + \gamma V_{\pi}(s’)]}, \forall s$$

注：Bellman Equation 即指 Bellman Expectation Equation 。

那么面对上式，我们就会有两种方法去解出我们的方程：


Policy Method

Policy Imporvement

$$\hat\pi(s) \leftarrow \arg \max_{a} \sum_{s’}{P(s’|s;a)[R(s,a,s’) + + \gamma V_{\pi}(s’)]}$$


Policy Iteration - Detail