RL 入门:Intro & Markov Decision Process
有人说人工智能就是 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)})$ 的。
学习的目标:最好的 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)$, justhow 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 的处理过程如下:
累积的 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
算法的思路,总结如下:
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:只与初始状态有关
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)$ 。
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 Imporvement
$$\hat\pi(s) \leftarrow \arg \max_{a} \sum_{s’}{P(s’|s;a)[R(s,a,s’) + + \gamma V_{\pi}(s’)]}$$