1. 强化学习基本概念

1.1 A grid-world example（网格世界）

在本课程中，网格世界的例子将贯穿始终（如上图所示）

在这个网格世界中，有一个机器人在行走。

网格世界中的每一个小网格，它们有不同的类型，比如有的网格是accessible，即可以进入的，用白色来表示；有的网格是forbidden，即不可进入的，用黄色来表示；另外还有一个target area，即我们希望机器人进入的网格。

此外，这个网格世界还有一个边界。

不同机器人可以在相邻的网格之间移动，但不能再斜的方向进行移动。

我们为什么要考虑这样一个例子呢？因为这个例子非常易于理解，方便我们理解强化学习的很多概念

那么，强化学习在这个例子中所要完成的任务是什么呢？强化学习需要再这个例子中找到一个比较好的路径以到达目标位置，即target area。

在这里面，我们会遇到很多问题。比如我们该如何去定义一个路径它究竟是好是坏？这其实是一个非常核心的问题，我们在后面会详细讨论这个问题，即如何作出最好的决策。

下面我们便用这个例子来解释强化学习中我们遇到的第一个概念

1.2 State（状态）

state描述的便是agent（智能体）相对于环境的状态

那么在grid-world example中，state指的是什么？便是location。

在上面这个网格中，一共有9个格子，即有9个location。我们便用$s_1,s_2,...,s_9$ 这几个字母来表示状态。这些字母本，比如$s_1$，实际上它是一个索引，它在这个网格中对应的真正的状态当然是代表二维平面的位置，即

$\mathbf {s_1} = {\begin{bmatrix} x \\ y \end{bmatrix}}$

如果是更加复杂的问题，那么我们除了位置之外，还需要考虑速度，而如果是机器人的话，还要对加速度等其他类型的状态信息加以考虑

1.3 State space（状态空间）

在上面我们已经了解了状态的概念。

如果我们把所有的状态放到一起，我们就得到了状态空间state space。

状态空间的本质其实是一个集合set，什么意思呢？

如果我们以$S$来表示状态空间，那么它就是把所有的状态$s_i$放到一起得到的一个集合，用数学表达式表达即为：

$S={\{s_i\}}^{9}_{i=1}$

1.4 Action（动作）

action（动作）代表的就是我们在每一个状态实际上是有一系列的可采取的行动，在grid-world example中，可采取的行动一共有五种，我们用$a_1,...,a_5$来表示：

$a_1$：向上移动 $a_2$：向右移动 $a_3$：向下移动 $a_4$：向左移动 $a_5$：原地不动

1.5 Action space（动作空间）

当我们将所用的动作放在一起，我们就得到了action space（动作空间）

和状态空间一样，它也是一个集合：

$A(s_i)=\{a_i\}^{5}_{i=1}$

这里值得指出的一点是：动作空间是依赖于状态的，也就是说在不同状态下，便会有不同的动作空间。这也就是为什么在上面这个式子中要用到“$(s_i)$”，这就表示动作空间A实际上是$s_i$的一个函数

1.6 State transition（状态转移）

1.6.1 什么是 state transition？

当我们采取了一个action（动作）后，我们在grid-world example中便从一个状态转移到另外一个状态，这样的过程就被称为state transition。

举个例子，比如说在状态$s_1$，我们采取的动作是$a_2$（即向右移动），那么我们下一个状态就会跳到$s_2$。这样一个过程用式子表示出来即：

$s_{1} \xrightarrow{a_{2}} s_{2}$

当我们在状态$s_1$，我们采取的动作是$a_1$（即向上移动），那么由于机器人不能走出边界，所以我们的状态还是$s_1$，用式子表示出来即：

$s_{1} \xrightarrow{a_{1}} s_{1}$

通过上面两个例子，我们知道state transition实际上是定义agent和环境的一种交互的行为，那我们在这里能否用其他的方式来定义这种交互的行为呢？首先，因为grid-world example是一种仿真，这是一个游戏，实际上我们可以任意去作定义，比如我们刚才在上面例子中是往上走的时候撞到边界了，我会被弹回到$s_1$，其实也有可能被弹到另一个地方，比如$s_4$，甚至可能会被弹到$s_7$。因为grid-world example是一个游戏，我们想怎么定义就怎么定义。

而在实际当中并非如此，实际情况是不允许任意定义的。

1.6.2 考虑复杂情况

下面我们再来关注一下forbidden area。比如说我们在 $s_5$ ，如果我们采取了动作 $a_2$，那么下一个状态是？

情况一：forbidden area 可以进入，但是会伴随着惩罚，那么 $s_{5} \xrightarrow{a_{2}} s_{6}$

情况二：forbidden area 不可进入，那么 $s_{5} \xrightarrow{a_{2}} s_{5}$

在这两种情况中，情况一其实更加一般化，但也更加困难。为什么呢？

因为如果我们把一些状态给排除掉的话，状态空间就会变小，实际上我们做搜索的时候会更加容易。

而如果我们认为 forbidden area 是可以进入的话，其实就会出现一些比较有意思的现象，比如说虽然进入 forbidden area 会得到惩罚，但也许进入之后，通往 target area 反而是最近的路径，所以 agent 可能会冒险进入到 forbidden area ，然后通过 forbidden area 再抵达 target area。之后我们会详细介绍这些。

1.6.3 state transition 的表达方式（两种）

state transition 可以用下面这种 tabular 的形式表现出来：

	$a_1$（upwards）	$a_2$（rightwards）	$a_3$（downwards）	$a_4$（leftwards）	$a_5$（unchanged）
$s_1$	$s_1$	$s_2$	$s_4$	$s_1$	$s_1$
$s_2$	$s_2$	$s_3$	$s_5$	$s_1$	$s_2$
$s_3$	$s_3$	$s_3$	$s_6$	$s_2$	$s_3$
$s_4$	$s_1$	$s_5$	$s_7$	$s_4$	$s_4$
$s_5$	$s_2$	$s_6$	$s_8$	$s_4$	$s_5$
$s_6$	$s_3$	$s_6$	$s_9$	$s_5$	$s_6$
$s_7$	$s_4$	$s_8$	$s_7$	$s_7$	$s_7$
$s_8$	$s_5$	$s_9$	$s_8$	$s_7$	$s_8$
$s_9$	$s_6$	$s_9$	$s_9$	$s_8$	$s_9$

上面的表格中，每一行对应一个状态，每一列对应一个动作

然而，虽然表格看起来很直观，但是在实际生活中，它的使用是受限的，因为它只能表示确定性的情况，而现实中的情况一般是有各种各样状态的，这时候表格就无法表达了。

所以这个时候，我们更一般的方法是什么呢？

便是用 State transition probability。（这里是我们第一次把 probability 引入到强化学习理论中来）

这个直观表达是什么呢？比如说我目前的状态是 $s_1$ ，我作出了动作 $a_2$ ，也就是要往右移动，下一个状态就是 $s_2$。用数学表示即为： $p({s_2}|s_1,a_2)=1$
$p({s_i}|s_1,a_2)=0(i\neq2)$

虽然在上面这个例子中我们描述为确定性的状态，但是条件概率是可以用来描述随机性状态的例子的。比如说有北风的时候，我们在 $s_1$ 状态下作出动作 $a_2$ 后，可能我们下一个状态是 $s_2$ 的概率是0.5、状态是 $s_5$ 的概率是0.5，那么我们用数学表达式表示即为： $p({s_2}|s_1,a_2)=0.5$ $p({s_5}|s_1,a_2)=0.5$

由此可见，写成概率的形式比写成表格的形式更加一般化。

1.7 Policy（策略）

1.7.1 什么是 Policy？

Policy 是强化学习当中独有的一个概念。什么是 Policy ？Policy会告诉 agent 在一个 state 状态下应该作出哪一个 action 动作。

1.7.2 如何表示 Policy？（两种）

若要直观上理解 Policy，我们是用箭头来表示的。

我们可以看到上图中含有9个状态，而每一个状态都对应一个箭头（$s_9$处的圆圈代表的是原地不动~）。基于这些箭头表示的策略，我们可以得到一些 path 或者叫 trajectory（如下图所示，之后会详细介绍）

用箭头来表示还是比较直观的。然而在现实当中，我们对于稍微复杂一点的情况便无法用如此直观的形式来表示，所以我们需要用一种能够描述复杂情况、一般化情况的方法，是什么呢？便是数学表达式，这里我们仍然选择条件概率。

我们举一个例子：针对状态 $s_1$，它的策略 $\pi$（这里的 $\pi$ 一般情况下我们是指圆周率，但是在强化学习中 $\pi$ 就统一指的是策略，一个条件概率）指定了在任何一个状态 state 下作出任何一个动作 action 的概率是多少。对于$s_1$，我们有如下表达式： $\pi({a_1}|{s_1})=0$
$\pi({a_2}|{s_1})=1$
$\pi({a_3}|{s_1})=0$
$\pi({a_4}|{s_1})=0$
$\pi({a_5}|{s_1})=0$
（所有策略的概率之和为1）

这里我们只写出了 $s_1$ ，其实对于这所有的9个状态，每一个状态都要有它对应的策略。此外，这里我们所写的均为确定性的 Policy（Deterministic Policy），也就是说 agent 在 $s_1$ 处一定会选择作出动作 $a_2$。

实际上，我们还存在不确定性的 Policy（Stochastic Policy），如下图所示：

用刚才所述的条件概率的形式来表示其实也非常简单，即： $\pi({a_1}|{s_1})=0$
$\pi({a_2}|{s_1})=0.5$
$\pi({a_3}|{s_1})=0.5$
$\pi({a_4}|{s_1})=0$
$\pi({a_5}|{s_1})=0$

当然，这样的策略也可以用表格的形式来表达出来：

	$a_1$（upwards）	$a_2$（rightwards）	$a_3$（downwards）	$a_4$（leftwards）	$a_5$（unchanged）
$s_1$	0	0.5	0.5	0	0
$s_2$	0	0	1	0	0
$s_3$	0	0	0	1	0
$s_4$	0	1	0	0	0
$s_5$	0	0	1	0	0
$s_6$	0	0	1	0	0
$s_7$	0	1	0	0	0
$s_8$	0	1	0	0	0
$s_9$	0	0	0	0	1

（但是这里我们还是不推荐使用表格，比较没法表示更一般的形式）

1.8 Reward（奖励）

1.8.1 什么是 Reward？

Reward 是强化学习中特有的一个概念。

首先 Reward 是一个数，是一个实数、标量，它是在 agent 采取一定动作后得到的。

这个数是有一定含义的：如果这个数是正数，则代表我们对这样的动作是鼓励的，而如果这个数是一个负数，代表我们不希望这样的行为发生，或者是对这个行为的一个惩罚。

这里面我们会遇到两个问题：

1. 首先，如果我不设置 reward，或者将 reward 设置为0的话会代表什么呢？如果深究的话可能会有些复杂，笼统地说就是代表没有 punishment，而没有 punishment 在一定程度上就是鼓励。
2. 还有一个问题是，我们能否用一个正数来代表 punishment，用负数来代表鼓励？实际上是可以的，而这也是数学上的一种技巧，本质上来说得到的东西是一样的。

1.8.2 如何设计 Reward？

这里我们还是举 grid-world example 的例子。

如果 agent 想要逃出四周的边界，每次它有这样的动作的时候，就令 $r_{bound}=-1$ 如果 agent 想要进入 forbidden area ，那么每次它有这样的动作的时候，就令 $r_{forbid}=-1$ 如果 agent 到达了目标单元格，即 target cell，就令 $r_{target}=+1$ 其他所有的 agent 采取的动作，我们令 $r=0$

Reward 实际上可以被理解为一个 human-machine interface，即我们和机器进行交互的一种手段，因为 reward 设计还是相对比较直观的，所以我们可以借此引导 agent 应该怎样做、不应该怎样做。比如说在上面的例子中，通过设计奖励机制，便可以引导机器人不进入forbidden area 或是出界

1.8.3 如何表示 Reward？

当然我们也可以用一个表格来表示 reward，如下所示：

	$a_1$（upwards）	$a_2$（rightwards）	$a_3$（downwards）	$a_4$（leftwards）	$a_5$（unchanged）
$s_1$	$r_{bound}$	0	0	$r_{bound}$	0
$s_2$	$r_{bound}$	0	0	0	0
$s_3$	$r_{bound}$	$r_{bound}$	$r_{forbid}$	0	0
$s_4$	0	0	$r_{forbid}$	$r_{bound}$	0
$s_5$	0	$r_{forbid}$	0	0	0
$s_6$	0	$r_{bound}$	$r_{target}$	0	$r_{forbid}$
$s_7$	0	0	$r_{bound}$	$r_{bound}$	$r_{forbid}$
$s_8$	0	$r_{target}$	$r_{bound}$	$r_{forbid}$	0
$s_9$	$r_{forbid}$	$r_{bound}$	$r_{bound}$	0	$r_{target}$

同样的，表格表示的话会有一个问题：它的应用还是比较有限的，因为表格只能表示确定性的情况，而实际上我们会遇到很多不确定的状态。

因此，我们会采用条件概率的方法来表示更加一般化的情况。

比如说，我们举个例子：在状态 $s_1$，如果我们选择了动作 $a_1$，那么我们得到的reward就是-1，用数学表达式表示出来即：

$p(r=-1|s_1,a_1)=1$
$p(r \neq -1|s_1,a_1)=0$

在这里，我们有以下几点需要注意：

在现实中还会存在 stochastic（随机）的奖励。比如说我们学习地非常努力，我们一定会得到一个奖励，但具体可以得到多少是具有一定随机性的 Reward 一定是依赖于当前的状态 state 和动作 action，而不是依赖于下一个状态

1.9 Trajectory

1.9.1 什么是Trajectory？

Trajectory 实际上是一个 state-action-reward 的链

如上图所示的 trajectory 可以表示为： $s_{1} \xrightarrow[r=0]{a_{2}} s_{2} \xrightarrow[r=0]{a_3} s_5 \xrightarrow[r=0]{a_3} s_8 \xrightarrow[r=1]{a_2} s_9$

1.9.2 return

这里我们还要介绍一个非常重要的概念——return。

一条 trajectory 的 return 即是将这条 trajectory 中的所有奖励 reward 相加所得的和，如下所示： $return = 0+0+0+1=1$

1.9.3 比较trajectory优劣

这里我们来看另外一条 trajectory，如下图所示：

将上图中的 trajectory 表示出来即为 $s_{1} \xrightarrow[r=0]{a_{3}} s_{4} \xrightarrow[r=-1]{a_3} s_7 \xrightarrow[r=0]{a_2} s_8 \xrightarrow[r=1]{a_2} s_9$
这条 trajectory 的 return 为 $return = 0-1+0+1=0$

那么在这里，这条 trajectory 和上文1.9.1中所介绍的 trajectory 相比，究竟哪一个 policy 比较好呢？其实直观上来说，我们会觉得第一个 policy 更好，毕竟第一个 policy 没进入到 forbidden area。但实际上我们应该从数学上来思考这个问题：因为第一个 trajectory 的 reward 更高，故其更好。

1.9.4 Discounted return

这里我们考虑一个特殊的情况，如上图所示。图中的 trajectory 表示出来即为： $s_{1} \xrightarrow[r=0]{a_{2}} s_{2} \xrightarrow[r=0]{a_3} s_5 \xrightarrow[r=0]{a_3} s_8 \xrightarrow[r=1]{a_2} s_9 \xrightarrow[r=1]{a_5} s_9 \xrightarrow[r=1]{a_5} s_9 ...$
这时，trajectory 的 reward为 $return=0+0+0+1+1+1+...=\infty$
这里的 trajectory 是无限长的，其 return 沿着其无穷长的轨迹不断累加下去的话，return 会发散掉。那我们应该如何解决这个问题呢？

这里我们需要引入 discount rate $\gamma \in [0,1)$。

有了 discount rate，我们就可以得到 discount return，如下所示 $discount return=0+\gamma0+{\gamma}^{2}{0}+{\gamma}^{3}{1}+{\gamma}^{4}{1}+{\gamma}^{5}{1}+...={\gamma}^{3}(1+{\gamma}+{\gamma}^2+...)={\gamma}^{3}{\frac{1}{1-\gamma}}$

这里我们引入 discount return 得到了什么？首先，之前我们将 reward 相加之后 return 会发散掉，而现在 return 变成了一个有限的值。其次，discount return 能够去平衡这种更远未来能够得到的 reward 和更近未来能够得到的 reward。

同时，这里我们通过控制 $\gamma$ 的取值便能够控制 agent 所学到的策略。简单来说，当 $\gamma$ 较小的时候，agent会变得更加 近视，也就是说它会更加注重最近的一些 reward；而如果 $\gamma$ 比较大的时候它会变得更加远视。

1.10 Episode

类似于深度学习中的轮数，用于区分 terminal states 和 continuing tasks

1.11 MDP（Markov decision process 马尔科夫链）

到此为止，我们已经将强化学习中一些比较基本的概念，通过例子的形式介绍完了。接下来我们需要把这些概念放到 MDP 框架当中，用更加正式的方式来重新介绍一下这些概念。

这里直接放图来解释（其实因为我太懒了…）：

小结：