强化学习

基本定义

强化学习的核心思想是通过机器与环境的交互来学习最优行为策略，最终目标是让机器在特定任务中获得最大的长期累积奖励

基本过程为机器处于一个环境中，观察当前的环境状态 x，选择并执行一个动作 a，环境根据机器的动作返回一个奖励 r 并以一定的概率 p 转移到新的状态，所有的环境状态组成一个状态空间 X，机器可执行的所有动作组成一个动作空间 A，奖励根据一个奖励函数 R 来返回，环境状态的转移概率为 P，强化学习任务通常用马尔可夫决策过程表示，对应一个四元组 $E=\{X,A,P,R\}$

强化学习的过程就是让机器学习一个“状态 ->动作”的策略 $\pi$，使得机器根据当前环境状态 x 即可得知要执行的动作 a，即计算 $a=\pi(x)$，策略有两种表示方法

• 确定性策略：$\pi:X\mapsto A$
• 随机性策略：$\pi:X\times A\mapsto\mathbb{R}$，其中 $\pi(x,a)$ 为在状态 x 下选择动作 a 的概率 $P(a|x)$，有 $\sum_{a\in A}\pi(x,a)=1$

奖励函数有两种常用的函数，其中 $r_{t}$ 表示第 t 步的奖励值，$\mathbb{E}$ 为随机变量期望

• T 步累积奖励：$R=\mathbb{E}\left[ {1\over T}\sum^T_{t=1}r_{t} \right]$
• 折扣累积奖励：$R=\mathbb{E}\left[ \sum^{+\infty}_{t=0}\gamma^{t}r_{t+1} \right],\gamma\in[0,1]$

探索与利用

强化学习与监督学习不同，强化学习中机器要学习的是一个“状态 ->动作”的映射规则，而通常情况下没有该形式的训练数据，机器需要通过尝试来发现各个动作的结果

考虑最大化单步奖赏的情形，这对应了一个理论模型：K- 摇臂赌博机。赌徒有有限次的机会，在投入一个硬币后可选择按下其中一个摇臂，每个摇臂以一定的概率吐出硬币，但这个概率赌徒并不知道，赌徒的目标是通过一定的策略最大化自己的奖赏，即获得最多的硬币

该问题有两种极端的策略，分别是“仅探索”和“仅利用”

• 仅探索：平等对待所有摇臂，将所有机会平均分配给所有摇臂，经过尝试后，可以得到所有摇臂的平均吐币概率，进而得到每个摇臂的奖赏期望，这是一种探索未知概率分布的做法，由于尝试机会被平均分配，因此不会更多的尝试吐币概率高的摇臂
• 仅利用：只尝试目前吐币概率最大的摇臂，若存在多个摇臂的吐币概率最大，则随机选择一个，这是一种贪心的做法，更多尝试的摇臂可能不是真实吐币概率最大的摇臂

若要获取最大的奖赏，则应该探索不同的摇臂并且更多的尝试已知概率最高的摇臂，这反映了“仅探索”和“仅利用”两种策略是矛盾的，需要达成折中

贪心算法

用一个概率 $\epsilon$ 来对探索和利用进行折中，每次尝试时，以 $\epsilon$ 的概率进行探索，以均匀概率选取一个摇臂进行尝试，以 $1-\epsilon$ 的概率进行利用，选择目前吐币概率最大的摇臂进行尝试

当摇臂奖赏的不确定性大，需要更多确定摇臂的奖赏表现时，应该进行更多的探索，设置较大的 $\epsilon$ 值，若摇臂奖赏的概率分布较集中，不需要太多探索即可近似真实情况，则可以设置较小的 $\epsilon$ 值，此外，还可以让 $\epsilon$ 值随着尝试次数的增加而减小，即先探索后利用

Softmax 算法

令 $Q(k)$ 为摇臂 k 的平均奖赏，若摇臂 k 被尝试了 n 次，记录奖赏值为 $v_{1},v_{2},v_{3},\dots$，则平均奖赏为

$$Q(k)=\frac{1}{n}\sum^n_{i=1}v_{i}$$

探索和利用的概率服从如下分布

$$P(k)=\frac{e^{\frac{Q(k)}{\tau}}}{\sum^K_{i=1}e^{\frac{Q(i)}{\tau}}},\tau>0$$

其中，$\tau$ 称为温度，当 $\tau\to 0$ 时，算法将趋于仅利用，当 $\tau\to \infty$ 时，算法将趋于仅探索，该算法对于平均奖赏高的摇臂，它的利用概率就高

有模型学习

考虑多步强化学习任务，假设任务的马尔可夫决策过程 $E=\{X,A,P,R\}$ 均为已知，该情形称为模型已知，该学习过程称为有模型学习

策略评估

以 T 步累积奖赏函数为例，对于策略 $\pi$，定义状态值函数 $V^\pi_{T}(x)$，表示从状态 x 开始，使用策略 $\pi$ 带来的累积奖赏，策略的效果由状态值函数来评估

$$V^\pi_{T}(x)=\mathbb{E}\left[ \frac{1}{T} \sum^T_{t=1}r_{t}|x_{0}=x \right]$$

最优策略应能最大化累积奖赏

$$\pi^\star=\arg\max_{\pi}\sum_{x\in X}V^\pi(x)$$

策略更新

策略更新的核心步骤是在当前状态 x 下，将策略选择的动作 a 替换为当前最优的动作 a’，定义状态 - 动作值函数 $Q^\pi_{T}(x,a)$，表示从状态 x 开始，执行一步动作 a 后，再使用策略 $\pi$ 带来的累积奖赏

$$Q^\pi_{T}(x,a)=\mathbb{E}\left[ \frac{1}{T} \sum^T_{t=1} r_{t}|x_{0}=x,a_{0}=a \right]$$

策略动作替换的条件表示为 $Q^\pi(x,a')\geq V^\pi(x)$

$V^\pi(x)$ 可转化为 $Q^\pi(x,a)$

$$\begin{aligned} V^\pi_{T}(x)&=\mathbb{E}\left[ \frac{1}{T}\sum^T_{t=1}r_{t}|x_{0}=x \right]\\ &=\mathbb{E}\left[ \frac{1}{T}r_{1}+\frac{T-1}{T} \frac{1}{T-1}\sum^T_{t=2}r_{t}|x_{0}=x \right]\\ &=\sum_{a\in A}\pi(x,a)\sum_{x'\in X}P^a_{x\to x'}\left( \frac{1}{T} R^a_{x\to x'}+\frac{T-1}{T}\mathbb{E}\left[ \frac{1}{T-1}\sum^{T-1}_{t=1}r_{t}|x_{0}=x' \right] \right)\\ &=\sum_{a\in A}\pi(x,a)\sum_{x'\in X}P^a_{x\to x'}\left( \frac{1}{T} R^a_{x\to x'}+\frac{T-1}{T}V^\pi_{T-1}(x') \right) \end{aligned}$$

由定义得

$$\begin{aligned} V^\pi_{T}(x)&=\sum_{a\in A}\pi(x,a)\cdot Q^\pi_{T}(x,a)\\ Q^\pi_{T}(x,a)&=\sum_{x'\in X}P^a_{x\to x'}\left( \frac{1}{T} R^a_{x\to x'}+\frac{T-1}{T}V^\pi_{T-1}(x') \right) \end{aligned}$$

在当前状态 x 下进行策略更新时，将当前策略选择的动作替换为最优的动作，有

$$\pi'(x)=\arg\max_{a\in A}V^\pi(x)$$

此时 $V^\pi(x)$ 已经取到最大值，可作如下变换

$$V^\pi(x)=\sum_{a\in A}\pi(x,a)\cdot Q^\pi(x,a)\quad\rightarrow\quad V^\pi(x)=\max_{a\in A}Q^\pi(x,a)$$

在策略更新时，$V^\pi(x)$ 是单调递增的，因此可直接简化为

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

算法描述如下

免模型学习

免模型学习则是在模型未知的情形下的强化学习，由于模型未知，无法在状态值函数上做全概率展开，策略无法评估，且状态值函数也难以转化为状态 - 动作值函数，策略无法更新

模型未知时只能从初始状态开始探索，此时可以将估计对象转换到状态 - 动作值函数上，从初始状态出发，估计每一步动作的奖赏

蒙特卡罗强化学习

蒙特卡罗强化学习的策略评估方法是对策略进行采样，从起始状态出发，执行该策略 T 步，得到以下执行轨迹

$$<(x_{0},a_{0}),r_{1},(x_{1},a_{1}),r_{2},\dots,(x_{T-1},a_{T-1}),r_{T},x_{T}>$$

每个 $(x_{i},a_{i})$ 对是一个状态 - 动作对，记录其后的奖赏值作为该状态 - 动作对的一次累积奖赏采样值，进行多次采样得到多条轨迹后，将每对状态 - 动作对的累积奖赏采样值取平均，得到状态 - 动作值函数的奖赏估计

为了更好地估计值函数，需要多条不同的采样轨迹，而对于确定性策略 $\pi$，每次选取的动作都是相同的，因此多次采样得到的轨迹都是相同的，此时可以考虑使用 $\epsilon$- 贪心算法将确定性策略转化为随机性策略来进行评估，考虑使用贪心算法的策略 $\pi^\epsilon$

$$\pi^\epsilon(x)=\left\{ \begin{aligned} &\pi(x)&&\text{with}\quad p=1-\epsilon\\ &\text{Action selected uniformly from A.}&&\text{with}\quad p=\epsilon \end{aligned} \right.$$

同策略的蒙特卡罗强化学习算法如下，其中被评估和被改进的都是策略 $\pi^\epsilon$

在评估时我们使用 $\pi^\epsilon$ 进行评估，但在策略更新时，我们希望更新原始的策略 $\pi$

原始策略 $\pi$ 的累积奖赏期望估计为

$$Q^\pi(x,a)=\frac{1}{T}\sum^T_{t=1}r_{t}$$

贪心算法策略 $\pi^\epsilon$ 的累积奖赏则是相当于在原始策略的累积奖赏期望上加权

$$Q^{\pi^\epsilon}(x,a)=\frac{1}{T}\sum^T_{t=1}\frac{P^\pi_{t}}{P^{\pi^\epsilon}_{t}}r_{t}$$

其中，$P^\pi_{i}$ 表示策略 $\pi$ 产生第 i 条轨迹的概率，对于给定的一条轨迹 $<x_{0},a_{0},r_{1},\dots,x_{T-1},a_{T-1},r_{T},x_{T}>$，策略 $\pi$ 产生该轨迹的概率为

$$P^\pi=\prod^{T-1}_{t=0}\pi(x_{t},a_{t})P^{a_{t}}_{x_{t}\to x_{t+1}}$$

则

$$\frac{P^\pi}{P^{\pi^\epsilon}}=\prod^{T-1}_{t=0}\frac{\pi(x_{t},a_{t})P^{a_{t}}_{x_{t}\to x_{t+1}}}{\pi^\epsilon(x_{t},a_{t})P^{a_{t}}_{x_{t}\to x_{t+1}}}=\prod^{T-1}_{t=0}\frac{\pi(x_{t},a_{t})}{\pi^\epsilon(x_{t},a_{t})}$$

其中，策略 $\pi$ 是确定性策略，$\pi(x,a)=1$，策略 $\pi^\epsilon$ 是 $\pi$ 的 $\epsilon$- 贪心策略，选择动作 a 的概率为

$$p_{i}=\left\{ \begin{aligned} &1-\epsilon+\frac{\epsilon}{|A|}&,a_{i}=\pi(x)\\ &\frac{\epsilon}{|A|}&,a_{i}\neq \pi(x) \end{aligned} \right.$$

异策略的蒙特卡罗强化学习算法如下

时序差分学习

蒙特卡罗强化学习需要采样出一个完整的 T 步轨迹，对所有的状态 - 动作对进行更新后，才能对策略进行更新

考虑将状态 - 动作对的更新变为增量式，假设 t 次采样估计出的状态 - 动作值函数已经是一个较好估计，则在第 $t+1$ 次采样时，有

$$\begin{aligned} Q^\pi_{T+1}(x,a)&=\frac{1}{T+1}\sum^{T+1}_{t=1}r_{t}\\ &=\frac{1}{T+1}\left( \sum^{T}_{t=1}r_{t}+r_{T+1} \right)\\ &=\frac{1}{T+1}(T\cdot Q^\pi_{T}(x,a)+r_{T+1})\\ &=\frac{1}{T+1}((T+1)Q^\pi_{T}(x,a)+r_{T+1}-Q^\pi_{T}(x,a))\\ &=Q^\pi_{T}(x,a)+\frac{1}{T+1}(r_{T+1}-Q^\pi_{T}(x,a)) \end{aligned}$$

以 $\gamma$ 折扣累积奖励为例，状态 - 动作值函数可进一步转化为

$$\begin{aligned} r_{T+1}&=R^a_{x\to x'}+\gamma Q^\pi_{T}(x',a')\\ \frac{1}{T+1}&=\alpha\\ Q^\pi_{T+1}&=Q^\pi_{T}(x,a)+\alpha(R^a_{x\to x'}+\gamma Q^\pi_{T}(x',a')-Q^\pi_{T}(x,a)) \end{aligned}$$

通过该函数，就可以在每次执行一步动作时更新一次状态 - 动作值函数，并更新策略，该算法称为 Sarsa 算法，是一个同策略算法

Sarsa 算法的异策略版本，称为 Q-learning 算法