RL笔记

马尔可夫决策过程 MDPs(Markov Decision Processes)

概述

马尔可夫决策过程 (Markov Decision Processes, 简称 MDPs) 是强化学习、运筹学和随机控制理论中的核心数学框架

马尔可夫性 Markov Property

MDP 的基石是马尔可夫性质，即“无后效性”。它指的是系统未来的状态仅取决于当前状态和当前采取的动作，而与过去的历史状态或动作序列完全无关。用数学概率表达为：

在这个公式中，竖线 | 是概率论中代表条件概率 (Conditional Probability) 的标准符号,可以理解为给定……的条件下
这个符号的作用是将问题划分为两部分:

1. 竖线右侧 (Right side): 代表已知的信息或已经发生的前提条件。
2. 竖线左侧 (Left side): 代表在这些已知条件下,要预测或计算其发生概率的目标事件 所以此公式的含义可以解读为:在做出一系列决策后,下一个状态的发生概率只与当前状态相关
   这就是马尔可夫性

马尔可夫过程 MP

马尔可夫过程是最基础的模型,仅描述了一个系统状态如何随着时间自然演变的随机过程
数学定义:一个元组$(S, P)$

• $S$(状态空间): 系统可能处于的所有状态
• $P$(状态转移矩阵):定义了从当前状态转移到下一个状态的概率$P_{ss’} = P(S_{t+1} = s’ | S_t = s)$

马尔可夫奖励过程 MRP (Markov Reward Process)

在 MP 的基础上加入了"奖励"机制和"时间观念(折扣因子),系统在自动演变的基础上每次状态转移都会伴随一个数值反馈:如果处于某个状态,未来预期能收获多少总奖励(数学期望),数学定义: 一个四元组 $(S, P, R, \gamma)$

• $S, P$: 同上
• $R$ (奖励函数): 在状态 $s$ 下能够获得的预期即时奖励
• $R_s = \mathbb{E}[R_{t+1} | S_t = s]$
• $\gamma$ (折扣因子): 取值 $[0,1]$，表示对未来奖励的打折程度 核心产物:价值函数V(s)

贝尔曼方程

在MRP中引入了状态价值函数,通过最基础的贝尔曼方程将当前价值与下一个状态的价值联系起来:

后半部分可以理解为一个递归,这样看,完全展开后的式子就是

简单来说,就是越靠后的期望奖励折扣次方越大，即:越靠后、越远的期望越不可信,同时也避免了无限循环导致奖励发散

马尔可夫决策过程 MDP (Markov Decision Processz)

在MRP的基础上加入了"动作(Action)“的能力,环境的走向不再自然发生,而是由动作和环境的随机性共同决定
数学定义： 一个五元组 $(S, A, P, R, \gamma)$

• $S, \gamma$: 同上
• $A$ (动作空间): 智能体可以执行的所有动作
• $P$ (动态转移概率): 现在转移概率受动作影响
• $P_{ss’}^a = P(S_{t+1} = s’ | S_t = s, A_t = a)$
• $R$ (奖励函数): 奖励也受动作影:$R_s^a = \mathbb{E}[R_{t+1} | S_t = s, A_t = a]$ 核心产物：策略$\pi$与动作价值函数$Q(s, a)$
  在MDP中,我们需要寻找一个策略 $\pi(a|s)$(在状态$s$下该选什么动作$a$)
  除了状态价值$V(s)$，更重要的是引入了动作价值函数$Q(s,a)$,表示在状态$s$下采取动作$a$后,遵循当前策略能获得的期望回报

贝尔曼方程

在MDPs完备后,可以得到两个蕴含的贝尔曼方程:

1. 状态价值函数
   • $$V^\pi(s) = \sum_{a \in A} \pi(a|s) Q^\pi(s, a)$$
   • 表示在状态 $s$ 下,遵循策略$\pi$的预期回报,等于在该状态下所有可能采取的动作的$Q$值的加权平均(权重就是策略 $\pi$ 选择该动作的概率),也就是全概率公式\
2. 动作价值函数
   • $$Q^\pi(s, a) = R_s^a + \gamma \sum_{s' \in S} P_{ss'}^a V^\pi(s')$$
   • 表示在状态$s$下,采取了具体动作$a$后,遵循策略$\pi$的预期回报,等于"即时奖励"加上"未来状态价值数学期望的打折价值”,折扣原理同上
   • $\pi(a|s)$:在状态$s$下采取动作$a$的概率
   • $R_s^a$:在状态$s$采取动作$a$获得的期望即时奖励
   • $P_{ss’}^a$:在状态$s$采取动作$a$后,转移到下一个状态$s’$的概率

贝尔曼最优方程

上面两个贝尔曼方程相当于是蕴含于性质之中,而贝尔曼最优方程则用于在用上述方程处理得出数据后,求解最最优策略
当达到最优策略时,在状态$s$下不再依据概率决定动作可能性,而是选择能带来最大$Q$值的动作,于是采取最优策略得到的价值就不再是全概率公式得到的数学期望,而是来自于价值最大的决策,因此方程从求和变为求最大:

1. 最优状态价值函数
   • $$V^*(s) = \max_{a \in A} Q^*(s, a)$$
   • 即在该状态下，所有可能动作中最大的那个最优$Q$值
2. 最优动作价值函数
   • $$Q^*(s, a) = R_s^a + \gamma \sum_{s' \in S} P_{ss'}^a V^*(s')$$
   • 构与期望方程类似，但未来的状态也必须采纳最优价值 $V^*$ 最终组合两方程进行代换即可得贝尔曼最优方程:
   • $$Q^*(s, a) = R_s^a + \gamma \sum_{s' \in S} P_{ss'}^a \left( \max_{a' \in A} Q^*(s', a') \right)$$
   • 从该方程,可以计算出对于每个状态的各个动作最优价值,从而让决策的选择有了依据

Q学习 Qlearning

概述

Qlearning类似一种黑箱环境的随机性动态规划,Qtable像是一个DP数组,探索过程就类似DP中转移填充DP数组,但存储内容是根据目前获取的已知信息、当前状态对应的最优策略而非传统DP的直接对应全局最优解(但是当充分探后也是逼近全局最优解的),而利用过程就类似DP问题中对于单次询问在线输出对应结果

传统DP

传统DP是一种全知视角的规划,即使在随机性动态规划中,某行动对于其将可能会转移出的状态的概率也是已知的(确定性DP就是100%),在这样的情况下,若任务符合马尔可夫性质,确定性DP可由拓扑序设计状态转移方程,随机性DP则通过贝尔曼方程迭代收敛求解
在随机性动态规划中,状态转移方程是由：以马尔可夫链为基础推导得出的贝尔曼方程,以及根据目标设计的奖励方程共同组成的。通过全概率公式,以行动-状态概率分布求出各个决策的期望收益,然后用贝尔曼最优方程找到最优决策链路
当获取到完整的DP数组后就可以对每个询问执行O(1)的查询,但是这里算是离线查询

黑箱差异

但是在Qlearning中,各个行为对应的状态的概率是未知的,所以需要在不断的试探中了解发生概率

$\epsilon$-greedy策略

既然目前状况是一个黑箱,我们就需要平衡好对已知可利用决策和直接随机探索
因此在Qlearning中通常会采用 $\epsilon$-greedy：以 $\epsilon$ 的概率随机选择动作(探索未知的概率分布),以 $1-\epsilon$ 的概率根据当前的Q-table选择利益最大的动作(利用已知信息)来确保在利用之余还有探索欲望以防总走老路陷入局部最优解
同时$\epsilon$的值可以被设计为随着探索的增长而减小,实现一种Qtable越发完备,探索欲望越低的效果

更新方式

在样本量足够大的时候,试探的结果会逼近与概率,但是我们的核心目的是为了调整Agent的决策,事实上不需要知道完整的概率分布是怎样的,所以通过如下形式的方程更新：

注：此方程是异策略方程(Off-policy),即所采取的行为和更新策略不一定,更新始终按照max更新,但事实上在此状态下可能是通过探索过程走了一个不够优的动作

上述方程蕴含了一个时序差分误差(TD Error) $[ R(s, a) + \gamma \max_{a’} Q(s’, a’) - Q(s, a) ]$
其中$R(s, a) + \gamma \max_{a’} Q(s’, a’)$ 被称为目标值(TD Target),目标值减去当前预估值所得即为误差
用误差乘以学习率$\alpha$便能用于更新原Q值,于是对于决策a会多次出现的状态s',就会被多次用来校准,然后Q(s,a)所对应的期望被极端状况造成的影响就会被逐渐抵消,使得期望逐渐逼近于全概率公式运算的结果,即大数定律代替全知概率
这样表面上似乎是无视了发生概率,但事实上相当于在每一次的探索中不断根据决策结果获取调节决策所对应的优劣
通过探索调整Qtable的各个键-值对中的值,并进行自举(上市),实现各个状态对于不同决策的优劣评估变化,而优劣变化暗含行为对应达到某状态概率的调整,达到一种类似于Agent知其然（决策）而不知其所以然（概率分布）的效果。使得训练后数据中可以在不显式知道概率分布的情况下就能收敛获取最优决策Map——Qtable

缺陷

过估计 Overestimation Bias

在上面的更新方式中提到,通过大数定律我们可以把各个行为的数学期望找出来,但是这依然存在一个问题：
在探索过程中,Q 值是不断波动的。假设在状态 $s’$ 下有多个真实的数学期望相近(甚至全是 0)的动作,由于系统随机性,总会有部分动作当前的Q值碰巧虚高,部分碰巧偏低
而在更新公式中,更新总是会依据最高价值的决策实现,导致即使上一次虚高的决策a1的Q值被拉期望水平了,碰巧正态分布下a2的Q值又开始虚高了,然后max总取高的那个
导致大数定律在这种状况下类似失效了,因为max总是不取s'的真实期望,于是连带着自举的更新也不符合大数定律了

双Q学习 Double Q-learning

概述

如上,Q-learning由于更新策略的max,存在过估计问题,为解决误差被高估的问题,Double Q-learning采用双表更新机制:一方选择一方估计的交叉验证方式,大幅降低了估计的盲目性

实现方式

Double Q-learning通过设置两个权重初始值不同但结构一致的Q-table来独立更新与评估各个决策的价值

选择方式

对于两个表格的选取方式,通过设定一个概率为**50%**的选择器,随机选取其中一个表格来更新,于是用该表格选择目前处于max的Q1(s',a*),然后用另一个表格获取Q2(s',a*)的数据来评估Qtaget的值并更新被选中表格

这样的选择方式使得两个表格在大规模的更新频率下更新机会等价,统计学上独立分布,又由于目标一致,两个表格最终将逼近于同一个全局最优解,也就是说两个表格都会像单表格一样找到最优解,不必担忧多设置表格会让答案出现大幅度偏差
但由于两表格不完全一致,接受到的信息不绝对相同,这就使得两个表格对于同一个Q(s',a*)的估值相近而却极不可能同时出现高估,这就显著降低了过估计问题的发生概率

补全说明

两个表格的更新基本相同,看似可以直接将复杂的等概率选取替换为轮换选择,但是事实上存在风险:

1. 二分奇偶性陷阱
   假设应用场景是一个像国际象棋一样的图,且无法斜线移动,多格移动,那么表格的更新就会存在:白格子数据永远被Q1掌握,黑格子永远被Q2掌握,交叉验证就无法实现
2. 时序耦合
   表格的更新陷入一种周期为2的状态中,如果场景中同样有类似的周期性更新频率,两者的更新就会交叠在一起,两表格各自处于一种极端状况中,评估无效

多层感知机 MLP

概述

从具体实现上来看,MLP就是一种相对复杂一点的机器学习的回归任务,而且复杂仅仅相对于基础回归任务,整体层次分布区别不大,只是比最基础的回归任务的模型多了几个隐藏层,通常构成是矩阵的线性方程形式,然后在对每一层隐藏层套上一个非线性激活的ReLU方程,防止矩阵乘法结合律把多层隐藏层坍缩回等价于一层的线性映射,实现类似分支语句的效果,同时也能实现类似复合函数的效果,为最后一层的函数创造多个折点,让它对于训练数据所对应的函数的拟合性更高,所以,MLP 本质上是一个万能函数逼近器(Universal Function Approximator)

缺陷

灾难性遗忘 Catastrophic Forgetting

MLP 的知识是分布式存储在所有权重参数中的,因而对于某些参数的调整所影响的大概率不仅仅是原本想调整的决策,而是有类似特征的其他情况的决策也会被顺带修改,就像是每次为了学习新的决策,而遗忘了之前对于其他情况的决策方式

深度Q网络 DQN (Deep Q-Network)

概述

DQN是一种加入经验回放池与双网络架构两种结构,打破了时序相关以解决灾难性遗忘问题，解决移动靶导致的评估发散问题,将Q-learning与MLP融洽结合的技术实现

MLP暴力融合缺陷

时序相关

在传统的机器学习分类任务里，给网络的数据是打乱的,但在强化学习里,数据高度时序相关,连续训练相似的数据,MLP会迅速过拟合到一个小区域,从而引发灾难性遗忘

移动靶 Moving Target

用来评估未来状态S’价值的Q(S’,a’),和正在更新的Q(S,a),用的是同一个神经网络,当Q更新后,本不该变化的、作为目标值的Q(S’,a’)同步发生了变化,而且无论调节的是哪里的估值,都会调整到整个网络的估值,使得Target不断移动且完全不稳定,可能导致方向越来越偏,最终使得估计值完全发散

新结构价值

经验回放池 Experience Replay

设定一个大容量循环队列,称为Replay Buffer,将探索到的经验数据压入队列而不立刻用于训练网络,当数据量够多后,每次从池里随机抽出一定量数据组合为Batch,进行训练
打破了数据的时序相关性,使数据回到了机器学习通常的独立同分布状态,且一条数据会被反复抽中多次，极大提高了数据的利用率
同时，其本质是一个经验分布(Empirical Distribution),在大量的数据下,其内容就是真实的物理概率分布,在利用其内容计算时,就绕开了显式概率建模

双网络架构

DQN在内存中实例化了两个相同的MLP:

1. 主网络/策略网络 Main Net
   • 负责做出决策并实时更新网络(负责利用过程,整体依旧是$\epsilon$-greedy策略)
2. 目标网络 Target Net
   • 作为主网络的冷备份,不允许计算梯,参数锁死
   • 负责在计算目标值时提供估计:$Target = R + \gamma \max_{a’} Q_{target_net}(S’, a’)$ 每隔一段较长训练后(如训练上千batch),把Main Net的最新权重 硬拷贝(Hard Copy) 覆盖Target Net,使目标网络更新,继续下一阶段训练
     通过最小化Loss: $L(\theta) = \mathbb{E}[(Target - Q(S, A; \theta))^2]$ (不一定为MSE) 双网络配合,Target每次都会被锁死一段时间,主网络可向着一个稳定的方向收敛
     类似线段树的lazytag,每次都微小调被叠加,硬拷贝时push_down,模拟了Qtable中一个键值对被调整本应该与其他键值对无关的特点
     在忽略微小的更新延迟后,收敛方式相对更加类似于Q-table的更新

细节问题

1. 倾向性调整
   • Qtable在事实上不变时本不该影响各个状态在利用过程中对策略选择的倾向性,但由于决定决策的主网络在事实上被调整,因而其行动倾向实则可能被调整了
   • 但由于目标值计算方式 异策略(Off-policy) 不在乎其数据的行动决策来源是探索或利用,因此不会造成影响
2. 奖励传播延迟
   • 为了让算法稳定不崩溃,采用了冻结网络的方式人为拖慢训练速度,而由于Target Net是冻结的,当训练再次使用相同状态时,目标值没有立刻反映出最新估值,存在细微误差
   • 但是在大量高频的mini-batch训练中,细微偏差可以被一定程度补全

缺陷

1. 过估计
   • 由于整体计算策略依然是Q-learning,所以同样具有过估计问题,同样可以使用Double Q-learning解决
2. 更新突变
   • 双网络架构中的细节问题中提到，硬拷贝造成的奖励传播延迟会导致误差,而且较长期内目标网络处于僵死状态,同时每次硬拷贝都会导致一个类似push_down一样的突变,会造成突然的梯度破坏,对于后续的其他连续动作的算法有重大问题
   • 以及一个偏玄学的超参数敏感问题,对步长设置的小差别可能会造成结果从收敛变成离散
   • 现代做法中通常会使用Soft Update替代,使更新能基本固定目标网络的情况下让更新更加平滑
   • 具体操作为将大量更新后的一次性硬拷贝调整为每次更新都用极小比例$\tau$更新各个参数: $$\theta_{target} \leftarrow \tau \theta_{main} + (1-\tau)\theta_{target}$$
   • 在大量更新后,相当于: $$\theta_{target}^{(t)} = \tau \theta_{main}^{(t)} + \tau(1-\tau)\theta_{main}^{(t-1)} + \tau(1-\tau)^2\theta_{main}^{(t-2)} + \dots + (1-\tau)^t\theta_{target}^{(0)}$$
   • 此时目标网络的参数就是主网络过去所有时刻参数的加权和,或者可理解为对主网络的加权积分,总体就是不断向主网络以极小步长逼近,以使得在Target基本不变的前提下使得目标网络平滑更新
3. 采样效率低
   • 经验回放池的均匀随机采样使得被用过多次的数据和为被用过的数据被抽取概率相同
   • 后续可以被改进变体 Prioritized Experience Replay (PER) 通过 TD Error 的大小来赋予采样权重

决斗网络 Dueling Network Architecture

概述

Dueling 网络架构将神经网络的输出分为了两个并行的通路,分别计算状态价值与动作优势,最后再合并进行估计

直观逻辑

当我们评估一个动作的价值时,其实同时也是基于其所处状态的优劣上再考量,所以当我们评估价值时，其实可以同时评估状态的总体价值与动作的相对价值
而当我们有了状态的核心特征描述后,对于状态本体价值的评估和对此状态下动作的优势的评估是相互独立的进程,可以并行进行
因此,我们可以把价值评估的网络大概拆分如下部分:

1. 共享特征提取层
   • 将宽泛状态特征放入提取层，获取一个可以被状态价值评估和动作优势评估同时高效利用的共享特征f(s)
2. 价值评估层
   1. 动作优势评估层
      • 输入共享特征分别评估各个动作的优势A(s,a)
   2. 状态价值评估层
      • 输入共享特征评估状态本身的价值V(s)
3. 价值合并层
   • 将从上一层获取的各个动作优势分别与状态本身价值合并获取Q(s,a)的价值

核心价值

仅仅从前向传播角度看,Dueling 网络架构仅仅多了一个多余的状态价值评估,显得徒增了计算负担,但是如果考虑反向传播部分,就能体现出其核心优势
但是如何显示出其价值要先从价值合并的公式看:

其中,$\frac{1}{|\mathcal{A}|} \sum_{a’} A(s, a’)$,由各个动作减去其均值,相当于把均值拉回了0,于是A(s,a’)仅仅保留了动作的相对优势,而基准价值则由状态本身的价值决定
此时如果考虑Q对A和V的偏导:

1. 对于状态价值V
   • $$\frac{\partial Q(s, a)}{\partial V(s)} = 1$$
2. 对于被选动作价值A
   • $$\frac{\partial Q(s, a)}{\partial A(s, a)} = 1 - \frac{1}{|\mathcal{A}|}$$
3. 对于未被选动作价值A
   • $$\frac{\partial Q(s, a)}{\partial A(s, a')} = - \frac{1}{|\mathcal{A}|}$$

可以看到，对于一次选择得到的反馈从Loss反馈到Q并依据链式法则传导到A与V调节参数时,完整的反馈会用于调整V,而正相关调整被选动作相关参数，其他动作负相关均摊剩余反馈
从直接意义上来说相当于根据动作的结果调整整个状态价值的水平以调整状态的大方向，并由被选动作对获得结果承担主要奖惩,其他动作均摊性地做小幅度反向调整,这样就突出了对动作的相对价值的调整
这样,每次试探都直接可以对状态本身的价值做出评估与调整,同时又可以细节上调节动作的相对优劣,而不再需要对每个动作都做大量的试探,大幅度提高了学习效率

对决双深度Q网络 D3QN (Dueling Double DQN)

概述

D3QN是一种将上述概念结合运用的一种技术实现,通过将Double Q-learning与Dueling网络架构组合如DQN,实现较为良好的强化学习效果并规避了一些较大的漏洞,提升了效率

Double DQN

原来的Double Q-learning,是设计了另一个基本一致而初始值不同的Q-table等概率抽取更新,而放在DQN,即为两张网络
而刚好DQN本身就有一个决策/目标双网络架构,只不过原来的更新Target全权由目标网络计算获取,同样存在过估计问题,因而现在只需要把选择记分动作的权利交给主网络即可
因为目标网络本就延迟于主网络,所以仅仅简单将Target计算方程改为：

即可实现防止网络过度自信的问题

Dueling DQN

Dueling网络架构本身初始就是为DQN设计的,其自身实现本就适配于DQN的MLP架构,仅仅需要上文所述结合即可

其他附加内容

正如DQN板块中所述,可结合:

1. Soft Update
2. PER 两个附加内容优化D3QN算法