强化学习

这部分将根据周志华老师的西瓜书对强化学习部分做一个简单介绍，该部分按照以下章节进行组织:

• 思想介绍——任务与奖赏
• K-摇臂赌博机
• 有模型学习
• 免模型学习
• 值函数近似
• 模仿学习

思想介绍-任务与奖赏

考虑这样病人看病的场景，假设我们是看病的医生，在我们与病人的交互过程中，大概是这么一个交互顺序:

• 病人本身有一个状态，记做$S$，表示病人目前的身体状况。
• 在看病的过程中，我认为病人处于某个状态$S’$，然后对病人施加了一个动作A，比如给病人吃了一些药，或者打了针。
• 在病人接受了治疗之后，其本身状态发生了一个变化，该状态的转移我们用概率矩$P$来表示，表示病人状态发生了一个变化，比如痊愈了或者病情更加严重了。
• 在病人的状态发生了变化之后，会给作为医生的我们一个反馈，记做$R$,如果病人痊愈了，那我们得到的反馈可能会是一面锦旗和很多钱，如果病情更加严重了，我们得到的反馈可能就是埋怨。

上面我所描述的场景其实就构成了一轮强化学习的过程，强化学习任务常用马尔可夫决策过程来描述，这意味着环境下一时刻的状态仅仅与当前时刻状态有关而与之前状态无关:

$$P(s_{t+1}| s_t,\dots, s_1) = P(s_{t+1}|s_{t})$$

综合起来，强化学习对应了四元组$E = $,其中:

$$P: X \times A \times X \rightarrow \mathbb{R}$$

而:

$$R: X \times A \times X \rightarrow \mathbb{R}$$

指定了奖赏，在有的应用中，状态可能仅与状态转移有关，即$R: X \times X \rightarrow \mathbb{R}$, 下面给出一个种瓜的马尔可夫决策过程的栗子。

在该过程中只有四个状态:健康、缺水、溢水和凋亡和两个动作:浇水和不浇水。在每一步转移后，若状态是保持瓜苗健康则获得奖励1，瓜苗缺水或者溢水奖赏为-1，这时通过浇水或者不浇水可以让瓜苗恢复健康状态，当瓜苗凋零时奖赏是最小值-100且无法恢复。图中箭头表示状态转移，$a、p、r$分别表示导致状态转移的动作、转移概率以及返回的奖赏。容易看出，最优策略是在“健康”和“缺少”状态下选择浇水，而在“溢水”状态下选择不浇水。

需要注意区分“机器”和“环境”的界限，在下棋中，棋盘是环境与对手；在机器人控制中，环境是机器人的躯体与物理世界。总之，在环境中状态的转移以及奖赏的返回是不受机器控制的，机器只能通过选择要执行的动作来影响环境，也只能通过观察转移后的状态和返回的奖赏来感知世界。

机器要做的是学习到一个策略$\pi$，根据这个策略，在状态$x$下就能得知想要执行的动作$a = \pi(x)$, 例如看到瓜苗状态为缺水时，能返回动作“浇水”。策略有两种表示:

• 一种是将策略表示为函数$\pi: X \rightarrow A$,确定性策略通常用这种表示。
• 一种是概率表示$\pi: X \times A \rightarrow R$ ,随机性概率通常用这种表示，$\pi(x,a)$为状态$x$下选择动作$a$的概率，这里必须有$\sum_a \pi(x,a) = 1$

策略的优劣取决于长期执行这一策略后得到的累计奖赏，例如某个策略使得瓜苗枯死，那么它的累积奖赏会很小，另一个策略种出了好瓜，它的累积奖赏会很大。在强化学习中，学习的目的就是要找到能使长期累积奖赏最大化的策略。长期累积奖赏有多种计算方式，常用的有两种:

• T步累积奖赏$E[\frac{1}{T} \sum_{t=1}^T r_t]$
• $\gamma$折扣累积奖赏: $E[\sum{t=0}^\infty] \gamma^t r{t+1}$, 其中$\gamma$表示贴现系数。

最后讨论下强化学习与监督学习的关系:

• 强化学习中的“状态”对应于监督学习中的“示例”。
• 强化学习中的“动作”对应于监督学习中的“标记”
• 强化学习中的“策略”实际上就相当于监督学习中的“分类器”或“回归性”

但是在强化学习中，并没有监督学习中的有标记样本，换言之，没有人直接告诉机器在什么状态下应该做什么动作，只有等到最终结果揭晓，才能通过“反思”之前的动作是否正确来进行学习，因此，强化学习在某种意义上可以看作具有“延迟标记信息”的监督学习问题。

K 摇臂赌博机

概念介绍

与一般监督学习不同，强化学习最终奖赏需要在多步动作后才能够观察到，这里我们首先考虑最简单的情形:最大化单步奖赏。
欲最大化单步奖赏需要考虑两个方面:一是需要知道每个动作带来的奖赏，二是要执行奖赏最大的动作。若每个动作对应的奖赏是确定值，那么尝试一遍所有动作便可以找到奖赏最大的动作。但更一般的情形是，一个动作的奖赏值是来自一个概率分布，仅通过一次尝试并不能确切地获得平均奖赏值。
实际上，单步强化学习任务对应了一个理论模型-“K-摇臂赌博机”，K摇臂赌博机有K个摇臂，赌徒在投入硬币后可选择按下其中一个摇臂，每个摇臂以一定的概率吐出硬币，但这个概率赌徒并不知道，赌徒的目标是通过一定的策略最大化自己的奖赏，即获得最多的硬币。

若仅为获知每个摇臂的期望奖赏，则可以采用“仅搜索法”:将所有尝试机会平均分配给每个摇臂，最后以每个摇臂各自平均的吐币概率作为其奖赏期望的近似估计。若仅为执行奖赏最大的动作，则可采用“仅利用”法: 按下目前最优的摇臂。显然，“仅探索”法能够很好地估计每个摇臂的奖赏，却会失去很多选择最优摇臂的机会；仅利用法则相反，它没有很好地估计摇臂期望奖赏，很可能经常选不到最优摇臂。因此，这两种方法都难以使得最终累积奖赏最大化。
事实上，“探索”和“利用”这两者是矛盾的，因为尝试次数有限，加强了一方则自然就会削弱另一方，这就是强化学习所面临的“探索-利用”窘境。显然，如欲累积奖赏最大，则必须在探索与利用之间达成较好的折衷。

$\epsilon-$贪心

$\epsilon-$贪心基于一个概率$\epsilon$来对探索和利用进行折中: 每次尝试时，以$\epsilon$概率进行探索，即以均匀概率随机选取一个摇臂；以$1- \epsilon$概率进行利用，即选择当前平均奖赏最高的摇臂。
令$Q(k)$记录摇臂$k$的平均奖赏，若摇臂$k$被尝试了$n$次，得到的奖赏为$v_1,v_2,\dots, v_n$,则平均奖赏为:

$$Q(k) = \frac{1}{n} \sum_{i=1}^n v_i$$

更高效的方法是进行增量式计算，即每一次尝试后就立刻更新$Q(k)$，不妨用下标来表示尝试的次数，初始时$Q0(k) = 0$。对于任意的$n \geq 1$,若第$n-1$次尝试后的平均奖赏为$Q{n-1}(k)$,则在经过第$n$次尝试获得奖赏$v_n$后，平均奖赏应更新为:

$$\begin{aligned} Q_n(k) &= \frac{1}{n} ((n-1) \times Q_{n-1}(k) + v_n) \\ &= Q_{n-1}(k) + \frac{1}{n} (v_n - Q_{n-1}(k)) \end{aligned}$$

若摇臂奖赏的不确定性较大， 例如概率分布较宽时，则需要更多的探索，此时需要较大的$\epsilon$值；若摇臂的不确定性较小，例如概率分布较集中时，此时只需要少量的探索即可，将$\epsilon$设置值较小即可。随着尝试次数的增多，在一段时间后，摇臂的奖赏都能够较好地近似出来，不再需要探索，这种情况下可以让$\epsilon$随着尝试次数的增加而逐步减小，例如取$\epsilon = \frac{1}{\sqrt{t}}$

Softmax

Softmax 算法中摇臂概率的分配是基于Boltzmann分布:

$$P(k) = \frac{e^{\frac{Q(k)}{\tau}}}{\sum_{i=1}^K e^{\frac{Q(k)}{\tau}}}$$

其中$q(i)$记录当前摇臂的平均奖赏，$\tau >0$称为温度，$\tau$越小则平均奖赏高的摇臂被选取的概率越高，$\tau$趋于0时Softmax将趋于“仅利用”，$\tau$趋于无穷大时Softmax将趋于“仅搜索”。

总结

前面通过K摇臂赌博机给出了单步强化学习的概念，同时介绍了单步强化学习实现的两种算法:$\epsilon$-贪心算法和Softmax算法，这两种算法并无绝对优劣差距，在进行应用中需要具体问题具体分析。
对于离散状态空间、离散动作空间上的多步强化学习任务，一种直接的办法是将每个状态上动作的选择看作是一个K摇臂赌博机问题，用强化学习任务的累积奖赏来代替K摇臂赌博机算法中的奖赏函数，即可将赌博机算法应用于每个状态: 对每个状态分别记录各动作的尝试次数、当前平均累积奖赏等信息，基于赌博机算法选择想要尝试的动作。然而这样做有很多局限，因为它没有考虑强化学习任务马尔可夫决策过程的结构。

有模型学习

考虑一个多步强化学习任务，我们假设任务对应的马尔可夫决策过程四元组$E =$均为已知，这样的情形称为模型已知,即机器已经对环境进行了建模。在已知模型的环境中学习称为“有模型学习”。此时，对于任意状态$x,x’$和动作$a$，在$x$状态下执行动作$a$转移到状态$x’$的概率$P{x \rightarrow x’}^a$ 是已知的，该转移所带来的奖赏$R{x \rightarrow x’}^a$也是已知的。为便于讨论，不妨假设状态空间和动作空间均有限。

策略评估

在模型已知时，对任意策略能估计出该策略带来的期望累积奖赏，令函数$V^\pi(x)$表示从状态$x$出发，使用策略$\pi$所带来的累积奖赏。函数$Q^{\pi}(x,a)$ 表示从状态$x$出发，执行动作$a$后再使用策略$\pi$所带来的累积奖赏，这里:

• $V(\cdot)$ 称为“状态值”函数，表示指定“状态”上的累积奖赏
• $Q(\cdot)$ 称为“状态-动作值”函数，表示指定“状态-动作”上的累积奖赏。

由累积奖赏的定义，有状态值函数:

$$\left\{\begin{array}{l} V_{T}^{\pi}(x)=\mathbb{E}_{\pi}\left[\frac{1}{T} \sum_{t=1}^{T} r_{t} \mid x_{0}=x\right], \quad T \text { 步累积奖赏 } \\ V_{\gamma}^{\pi}(x)=\mathbb{E}_{\pi}\left[\sum_{t=0}^{+\infty} \gamma^{t} r_{t+1} \mid x_{0}=x\right], \quad \gamma \text { 折扣累积奖赏. } \end{array}\right.$$

令$x_0$表示起始状态，$a_0$表示起始状态上采取的第一个动作；对于$T$步累积奖赏，用下标$t$表示后续执行的步数，我们有状态动作值函数:

$$\left\{\begin{array}{l} Q_{T}^{\pi}(x,a)=\mathbb{E}_{\pi}\left[\frac{1}{T} \sum_{t=1}^{T} r_{t} \mid x_{0}=x, a_0 = a\right], \quad T \text { 步累积奖赏 } \\ Q_{\gamma}^{\pi}(x,a)=\mathbb{E}_{\pi}\left[\sum_{t=0}^{+\infty} \gamma^{t} r_{t+1} \mid x_{0}=x, a_0 = a\right], \quad \gamma \text { 折扣累积奖赏. } \end{array}\right.$$

根据马尔可夫决策过程的马尔可夫性，值函数可以有更加简单的递推形式，对于$T$步累积奖赏有:

$$\begin{aligned} V_T^\pi (x) &= E_{\pi} [\frac{1}{T} \sum_{t=1}^T r_t| x =x_0] \\ &= E_{\pi} [\frac{1}{T} r_1 + \frac{T-1}{T} \frac{1}{T-1} \sum_{t=2}^T r_t | x_0 = x] \\ &= \sum_{a \in A} \pi(x,a) \sum_{x' \in X} P_{x \rightarrow x'}^a (\frac{1}{T} R_{x \rightarrow x'}^a + \frac{T-1}{T} E_{\pi} [\frac{1}{T-1} \sum_{t=1}^{T-1} r_t|x_0 = x']) \\ &= \sum_{a \in x} \pi(x,a) \sum_{x' \in X} P_{x \rightarrow x'} (\frac{1}{T} R_{x \rightarrow x'}^a + \frac{T-1}{T} V_{T-1}^\pi (x')) \end{aligned}$$

类似的，对于$\gamma$折扣累积奖赏有:

$$V_{\gamma}^{\pi}(x)=\sum_{a \in A} \pi(x, a) \sum_{x^{\prime} \in X} P_{x \rightarrow x^{\prime}}^{a}\left(R_{x \rightarrow x^{\prime}}^{a}+\gamma V_{\gamma}^{\pi}\left(x^{\prime}\right)\right)$$

值函数的递推方程也被称作Bellman方程。
用这种递归等式来计算值函数，实际上就是一种动态规划算法。换言之，从值函数的初始值$V_0(\pi)$出发，通过每一次迭代能够计算出每个状态的单步奖赏$V_1^\pi$,进而从单步奖赏出发，通过一次迭代计算出两步累积奖赏$V_2^\pi$,对于$T$步累积奖赏，只需要迭代$T$轮就能精确地求解出值函数。
可以总结基于$T$步累积奖赏的策略评估办法:

输入: MDP四元组$E = $; 被评估的策略$\pi$; 累积奖赏参数$T$
算法流程:

• 初始化$V(x) = 0$
• 递推计算$V_1^\pi, V_2^\pi, \dots, V_t^\pi, \dots$
• 递推直到$V_t^\pi = V_T^\pi$

输出: 状态值函数$V$

对于$\gamma$折扣累积奖赏算法，与普通$T$步累积累积奖赏递推类似，同时考虑到当$t$很大时，$\gamma^t$ 会趋于0，因此算法计算终止常通过阈值来进行确定:

$$\max_{x \in X} |V(x) - V'(x)| < 0$$

有了状态值函数，就能直接计算出状态-动作值函数:

$$\left\{\begin{array}{l} Q_{T}^{\pi}(x, a)=\sum_{x^{\prime} \in X} P_{x \rightarrow x^{\prime}}^{a}\left(\frac{1}{T} R_{x \rightarrow x^{\prime}}^{a}+\frac{T-1}{T} V_{T-1}^{\pi}\left(x^{\prime}\right)\right) \\ Q_{\gamma}^{\pi}(x, a)=\sum_{x^{\prime} \in X} P_{x \rightarrow x^{\prime}}^{a}\left(R_{x \rightarrow x^{\prime}}^{a}+\gamma V_{\gamma}^{\pi}\left(x^{\prime}\right)\right) \end{array}\right.$$

策略改进

对某个策略的累积奖赏进行评估后，若发现某个策略并非最优策略，则自然期望改变策略以使累积奖赏最大：

$$\pi^\ast = \argmax_{\pi} \sum_{x \in X} V^{\pi}(x)$$

一个强化学习任务可能有多个最优策略，最优策略所对应的值函数$V^\ast$称为最优值函数，即:

$$\forall x \in X: V^{\ast} (x) = V^{\pi^\ast} (x)$$

注意，当策略空间无约束时$V^\ast$才是最优策略所对应的值函数，对于离散状态空间与离散动作空间，策略空间是状态上所有动作的组合，共有$|A|^|X|$种不同的策略，若策略空间有约束，则违背约束的策略是“不合法”的，即便其值函数所取得的累积奖赏最大，也不能作为最优值函数。
对于前面值函数的递推方程Bellman方程稍加改动便可得到最优值函数的递推公式:

$$\left\{\begin{array}{l} V_{T}^{*}(x)=\max _{a \in A} \sum_{x^{\prime} \in X} P_{x \rightarrow x^{\prime}}^{a}\left(\frac{1}{T} R_{x \rightarrow x^{\prime}}^{a}+\frac{T-1}{T} V_{T-1}^{*}\left(x^{\prime}\right)\right) \\ V_{\gamma}^{*}(x)=\max _{a \in A} \sum_{x^{\prime} \in X} P_{x \rightarrow x^{\prime}}^{a}\left(R_{x \rightarrow x^{\prime}}^{a}+\gamma V_{\gamma}^{*}\left(x^{\prime}\right)\right) \end{array}\right.$$

换言之:

$$V^{*}(x)=\max _{a \in A} Q^{\pi^{*}}(x, a)$$

将该式代入状态-动作值函数刻度可得最优状态-动作值函数:

$$\left\{\begin{array}{l} Q_{T}^{*}(x, a)=\sum_{x^{\prime} \in X} P_{x \rightarrow x^{\prime}}^{a}\left(\frac{1}{T} R_{x \rightarrow x^{\prime}}^{a}+\frac{T-1}{T} \max _{a^{\prime} \in A} Q_{T-1}^{*}\left(x^{\prime}, a^{\prime}\right)\right) \\ Q_{\gamma}^{*}(x, a)=\sum_{x^{\prime} \in X} P_{x \rightarrow x^{\prime}}^{a}\left(R_{x \rightarrow x^{\prime}}^{a}+\gamma \max _{a^{\prime} \in A} Q_{\gamma}^{*}\left(x^{\prime}, a^{\prime}\right)\right) \end{array}\right.$$

上述关于最优值函数的等式，称为最优Bellman等式，其唯一解是最优值函数。
最优Bellman等式揭示了非最优策略的改进方式: 将策略选择的动作改编为当前最优的动作。显然，这样的改变能使策略更好，不妨记动作改变后对应的策略为$\pi’$,改变动作的条件为$Q^\pi (x, \pi^i(x)) \geq V^\pi(x)$, 以$\gamma$折扣累积奖赏为例，由式可计算递推不等式:

$$\begin{aligned} V^{\pi}(x) &\leq Q^{\pi}(x, \pi'(x)) \\ &= \sum_{x' \in X} P_{x \rightarrow x'}^{\pi'(x)} (R_{x \rightarrow x'}^{\pi'(x)} + \gamma V^\pi(x')) \\ &\leq \sum_{x' \in X} P_{x \rightarrow x'}^{\pi'(x)} (R_{x \rightarrow x'}^{\pi'(x)} + \gamma Q^{\pi}(x', \pi'(x'))) \\ &= .... \\ &= V^{\pi'}(x) \end{aligned}$$

值函数每一次对于策略的改进都是递增的，因此对于当前的策略$\pi$，可以放心地将其改进为:

$$\pi'(x) = \argmax_{a \in A} Q^{\pi}(x, a)$$

直到$\pi’$与$\pi$一致、不再发生变化，此时就满足了最优Bellman等式，即找到了最优策略。

策略迭代与值迭代

在前面介绍了两部分内容:

• 如何评估一个策略的值函数
• 在策略评估后如何改进以获得最优策略

将这两者结合起来即可得到求解最优解的方法:

从一个初始策略(通常是随机策略)出发，先进性策略评估，然后改进策略，评估改进的策略，再进一步改进策略，……不断迭代进行策略评估和改进直到策略不再改变为止，这样的做法称为“策略迭代”.

下面给出基于$T$步累积奖赏的策略迭代算法:

策略迭代算法在每次改进策略后都需要进行策略评估，这通常比较耗时。但是实际上策略改进与值函数的改进是一致的，因此可讲策略改进视为值函数的改善:

$$\left\{\begin{array}{l} V_{T}(x)=\max _{a \in A} \sum_{x^{\prime} \in X} P_{x \rightarrow x^{\prime}}^{a}\left(\frac{1}{T} R_{x \rightarrow x^{\prime}}^{a}+\frac{T-1}{T} V_{T-1}\left(x^{\prime}\right)\right) \\ V_{\gamma}(x)=\max _{a \in A} \sum_{x^{\prime} \in X} P_{x \rightarrow x^{\prime}}^{a}\left(R_{x \rightarrow x^{\prime}}^{a}+\gamma V_{\gamma}\left(x^{\prime}\right)\right) \end{array}\right.$$

于是可以得到值迭代算法:

在模型已知时，强化学习任务能归结为基于动态规划的寻优问题。与监督学习不同，这里并未涉及泛化能力，仅仅是为每一个状态寻找的一个最佳动作。

免模型学习

在现实的强化学习任务中，环境的转移概率、奖赏函数往往很难得知，甚至很难直到环境中有几个状态，若学习算法不依赖于环境建模，则称为“免模型学习”。

蒙特卡罗强化学习

在免模型情况下，策略迭代算法首先碰到的问题便是策略无法评估，这是由于模型未知而导致无法做全概率展开。此时，只能通过在环境中执行选择的动作，来观察转移的状态和得到的奖赏。受K摇臂赌博机的启发，一种直接的策略评估方法是“多次采样”，然后求取平均累积奖赏作为期望累积奖赏的近似，这称为蒙特卡罗强化学习方法，由于采样必须为有限次数，因此该方法更适合于使用$T$步累积奖赏的强化学习任务。

另一方面，策略迭代算法估计的是值函数，而在进行策略选择时依赖的是状态-动作值函数$Q$，当模型已知时，从$V$到$Q$有很简单的转化方法，而当模型未知时，这也会出现困难。于是我们将估计对象从$V$转变为$Q$,即估计每一对“状态-动作”的值函数。

$$\begin{aligned} az^{-1} u(k) &= au(k-1) \\ a z^{-1} u(k)^2 &= au(k-1) u(k) \end{aligned}$$