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=^{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 采取一定动作后得到的。
这个数是有一定含义的：如果这个数是正数，则代表我们对这样的动作是鼓励的，而如果这个数是一个负数，代表我们不希望这样的行为发生，或者是对这个行为的一个惩罚。
这里面我们会遇到两个问题：
- 首先，如果我不设置 reward，或者将 reward 设置为0的话会代表什么呢？如果深究的话可能会有些复杂，笼统地说就是代表没有 punishment，而没有 punishment 在一定程度上就是鼓励。
- 还有一个问题是，我们能否用一个正数来代表 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 框架当中，用更加正式的方式来重新介绍一下这些概念。
这里直接放图来解释（其实因为我太懒了…）：
小结：
