强化学习——基础概念

2020-11-27 本文已影响0人 7NIC7

机器学习分为：监督学习、非监督学习、强化学习。
下面从强化学习的概念、应用、特点等方面带大家认识强化学习，让大家对强化学习有一个初步的了解，最后会比较一下强化学习与监督学习、非监督学习之间的区别。

一基本概念

1.1 强化学习的概念：

抽象模型.png
还有一个重要的概念在图中没有直观的显示出来：policy策略，即给定一个state，应该选取什么样的action。强化学习的最终目标是找到一个最优的策略使得agent获得最多的reward。

举例：

	Agent	Environment	state	reward	action
下棋	自己	对手	棋现在的布局	最后输赢	下一步的落子
扫地机器人	机器人	机器人所在的房间	房间的整洁程度以及机器人自己现有的电量	捡垃圾获得正向奖励，没电获得负向奖励	去充电；不动；去捡垃圾

1.2 强化学习的应用

无人驾驶
机器翻译
推荐系统（工业落地：快手）
游戏（Atari）
…………
reference: 十大现实应用

1.3 强化学习的特点：

1.trial and error 不断试验并在错误中总结经验，以便下次试验能成功
2.reward是延迟的，你做了这个动作之后不一定会立刻得到奖励，但是可能会在结束时得到奖励
3.explore探索和exploit利用

1.4 三者的区别和联系：

强化学习 vs 监督学习
强化学习的反馈是完全依据所采取的动作，而监督学习的反馈与采取的动作完全无关，它只参照正确的动作。
一个形象的比喻：监督学习，是有家教的好孩子，每一步都有指导方针，每天都有纠错，改错，进步，没什么随机性。而RL就是个野生的，一学期没人管，期末考试没考好，回家被揍一顿，类似于这种效果。
强化学习 vs 非监督学习
没有标签的强化学习是非监督学习吗？非监督学习是根据已有的数据寻找内在的规律或者模式，比如聚类、关联规则。强化学习的最终目的是最大化自己的收益。

二 Bellman Equation 贝尔曼方程

2.1 如何量化？

    前面讲述了强化学习的最终目标是获得一个最优策略来最大化agent获得的奖励，那么，什么样的策略是最优的呢？
    我们通过定义状态价值函数 $v(s)$ 和动作价值函数 $q(s,a)$ 来回答上述的问题。
    先将之前强化学习中涉及的定义数学化：

原始定义	数学符号	含义
reward	$R_{t}$	表示t时刻agent获得的奖励
state	$S_{t}$	表示t时刻agent所处的状态
action	$A_{t}$	表示t时刻agent采取的行为动作

$0 \leq t \leq T$ ， $T$ 代表一个终止态（可以没有终止状态）。

2.1.1 状态价值函数

一般的，reward是随机变量，所以我们定义求其期望。
$v_{\pi}(s) = E_{\pi}(G_t|S_t=s)$
其中 $G_t = R_{t+1} + \gamma R_{t+2} + \gamma^{T-t-1} R_{T}$ 代表从t时刻开始一直到终止状态agent获得的reward之和； $\gamma$ $(0\lt \gamma \leq 1)$ 是一个衰减值，代表我们更关注眼前的“利益”，若 $\gamma=1$ ，表示不进行reward衰减；下标 $\pi$ 表示一个策略。
现在就可以回答最优策略是什么这一问题了，最优策略就是可以最大化 $v_{\pi}(s)$ 的那个策略 $\pi$ 了。即
$v_{*}(s) = v_{\pi^*}(s)=\max_{\pi}v_{\pi}(s)$
称 $v_{*}(s)$ 为最优价值函数。

2.1.2 动作价值函数

对应的动作价值函数是：
$q_{\pi}(s,a) = E_{\pi}(G_t| S_t=s, A_t=a)$
最优动作价值函数：
$q_*(s,a) = q_{\pi^*}(s,a) = \max_{\pi}q_{\pi}(s,a)$

2.2 如何求解最优策略？

有了价值函数，那么如何求解最优策略？就需要引入bellman方程以及bellman最优方程，基于此，可以在寻找最优策略的“道路上”给予你一些灵感。
首先，来看一下状态价值函数与动作价值函数之间有什么关系，
$v_{\pi}(s) = \sum_{a}\pi(a|s)q_{\pi}(s,a) \tag{1}$

$q_{\pi}(s,a) = \sum_{s'}\sum_{r}p(s', r|s,a)（r+\gamma v_{\pi}(s')) \tag{2}$

该式子可以从下面的回溯图上直观的得到。

回溯图.png

2.2.1 bellman equation

贝尔曼方程就是用于揭示 $v_{\pi}(S_t=s)$ 与 $v_{\pi}(S_{t+1}=s')$ ， $q_{\pi}(S_t=s,A_t=a)$ 与 $q_{\pi}(S_{t+1}=s',A_{t+1}=a')$ 之间关系的等式。
也就是将(1)式代入(2)式，(2)式代入(1)式。bellman方程如下:
$v_{\pi}(s) = \sum_{a}\pi(a|s)\sum_{s'}\sum_{r} p(s',r|s,a)(r + \gamma v_{\pi}(s'))$
$q_{\pi}(s,a) = \sum_{s'}\sum_{r}p(s',r|s,a)(r+\gamma \sum_{a'}\pi(a'|s')q_{\pi}(s',a'))$

2.2.2 bellman optimality equation

得到了bellman方程，就可以轻松得到bellman最优方程，从而得到最终我们想要的寻找最优策略的方法。

引理1：
先上结论：
$v_{\pi^*}(s) = \max_a q_{\pi^*}(s,a)$
证明如下：
$由(1)式可得，v_{\pi^*} = \sum_{a}\pi(a|s)q_{\pi^*}(s,a) \\ 那么，v_{\pi^*} \leq \max_a q_{\pi^*}(s,a) \\ 下证 v_{\pi^*} \lt \max_a q_{\pi^*}(s,a) 不成立 \\ 假如v_{\pi^*} \lt \max_a q_{\pi^*}(s,a) \\ 设 \pi' = \begin{cases} \arg\max_a q_{\pi^*} (s,a) \qquad & 在t时刻 \\ \pi^* \qquad & otherwise \end{cases}$
可以看到 $v_{\pi'}(s)=\max_a q_{\pi^*}(s,a)$ ，而 $v_{\pi^*} \lt \max_a q_{\pi^*}(s,a)$ ，即找到了一个策略 $\pi'$ 是优于 $\pi^*$ 的，假设不成立，结论得证。

基于引理1，我们得到bellman最优方程：
$v_{\pi^*}(s) = \sum_{s'}\sum_{r} p(s',r|s,a)(r + \gamma v_{\pi^*}(s'))$
$q_{\pi^*}(s,a) = \sum_{s'}\sum_{r}p(s',r|s,a)(r + \gamma \max_{a'}q_{\pi^*}(s',a' ))$

2.2.3 策略改进定理

    来到这，就是最后一步了，策略改进定理：
$对\forall s，若 q_{\pi}(s,\pi^{'}(s)) \geq v_{\pi}(s)，则\pi' \geq \pi$
证明如下：
$\begin{align} &v_{\pi}(s) \\ \leq& q_{\pi}(s, \pi'(s))\\ =&E_{\pi}(R_{t+1} + \gamma v_{\pi}(S_{t+1}) | S_{t}=s, A_{t}=\pi'(s)) \\ =&E_{\pi'}(R_{t+1} + \gamma v_{\pi}(s') | S_{t}=s)\\ \leq & E_{\pi'}(R_{t+1} + \gamma q_{\pi}(s',\pi'(s'))|S_{t}=s)\\ = & E_{\pi'}(R_{t+1} + \gamma E_{\pi}(R_{t+2} + \gamma v_{\pi}(s'')|S_{t+1}=s',A_{t+1}=\pi'(s'))|S_{t}=s) \\ = & E_{\pi'}(R_{t+1} + \gamma E_{\pi'}(R_{t+2} + \gamma v_{\pi}(s'')|S_{t+1}=s')|S_{t}=s)\\ = & E_{\pi'}(R_{t+1} + \gamma R_{t+2} + \gamma^2v_{\pi}(s'') | S_t=s)\\ \leq & E_{\pi'}(R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \dots | S_t=s)\\ = & v_{\pi'}(s) \end{align}$
得到 $v_{\pi}(s) \leq v_{\pi'}(s)$ ，那么也就是 $\pi \leq \pi'$ 。
    根据策略改进定理，我们可以得出一个结论，当 $t$ 时刻agent在状态 $s$ 时，若可以找到一个动作 $a=\pi'(s)$ 使得 $q_{\pi}(s,a) \geq v_{\pi}(s)$ ，而剩下的时间遵循原策略 $\pi$ ，那么新策略 $\pi'$ 至少和原策略 $\pi'$ 一样好。
    也就是说我们在每个时间步找到
$a = \arg\max_{a} q_{\pi} (s, a)$
结论：贪心策略就是最好的策略!