多臂老虎机问题 MAB

一个有K个拉杆的老虎机，拉动每一个拉杆都有对应的概率R获得奖励。目标是在操作T次拉杆后获得的奖励最大

可以这样描述：该问题可以表示为一个元组<A,R>,其中：

A为动作集合，，由于有K个拉杆，动作空间就是集合${a_1,…a_K}$
R为奖励概率分布，拉动每一根拉杆的动作a都对应一个奖励的概率分布$R(r｜a)$，不同拉杆奖励不同

每个时间步只能拉动一个拉杆，则该任务的目标为最大化时间步T内累计奖励： $\max \overset{T}{\underset{t=1}{\sum}}r_t,r_t\sim R(\cdot｜a_t)$

期望奖励$Q(a)$：$E_{r\sim R(\cdot a)}[r]$
最优期望奖励$Q^*=\max_{a\in A}Q(a)$
懊悔$R(a)=Q^*-Q(a)$
累计懊悔$\sigma_R=\overset{T}{\underset{t=1}{\sum}}R(a_t)$

MAB问题等价位最小化累计懊悔

估值期望奖励：可以采用迭代法，即 $Q_k=\frac{1}{k}\sum^k_{i=1}r_i = Q_{k-1}+\frac{1}{k}[r_k-Q_{k-1}]$

$\epsilon$ - 贪心算法

一种平衡探索（Exploration）和利用（Exploitation）的简单策略。算法在每个时间步$t$选择动作$a_t$的规则如下：

$ a_t = \begin{cases} \underset{a \in A}{\arg\max} \ Q_t(a) & \text{以概率 } 1-\epsilon
\text{从A中随机选择一个动作} & \text{以概率 } \epsilon \end{cases} $

$Q_t(a)$: 在时间$t$时，对动作$a$的价值估计（即期望奖励）。
利用 (Exploitation): 以 $1-\epsilon$ 的概率，选择当前看来奖励最高的动作。这能充分利用已知的信息来获取最大回报。
探索 (Exploration): 以 $\epsilon$ 的概率，随机选择一个动作。这使得算法有机会探索未知的动作，可能会发现更好的选择，避免陷入局部最优。

上置信界算法 (UCB)

UCB算法对不确定性高的动作持乐观态度，它会给那些被选择次数较少的动作一个额外的“探索奖励”，鼓励算法去尝试它们。选择动作的准则是最大化预估价值和不确定性之和。

$ a_t = \underset{a \in A}{\arg\max} \left[ Q_t(a) + c \sqrt{\frac{\ln t}{N_t(a)}} \right] $

$Q_t(a)$: 动作$a$的当前平均奖励，代表“利用”。
$c \sqrt{\frac{\ln t}{N_t(a)}}$: 置信区间的上界，代表“探索”。
- $t$: 当前的总试验次数。
- $N_t(a)$: 动作$a$到目前为止被选择的次数。
- $c$: 探索常数，用于调节探索的权重。$c>0$，c越大越偏向于探索。

核心思想: 当一个动作被选择的次数$N_t(a)$越少，其不确定性项（公式右侧）的值就越大，从而增加了它被选中的机会。随着试验次数的增加，所有动作都会被充分探索，最终算法会收敛到最优动作。

汤普森采样算法

该算法通常利用Beta分布为动作的奖励概率建模。Beta分布是一个定义在(0, 1)区间的连续概率分布，由两个参数$\alpha 、\beta$控制其形状，非常适合为如“成功/失败”这类事件的概率进行建模。

核心思想: 算法假设每个拉杆的奖励概率服从一个特定的概率分布，然后根据这个分布进行采样，选择采样中奖励最大的动作。这可以看作是一种蒙特卡卡罗方法，用于估计所有拉杆中产生最高奖励的概率。
算法流程:
1. 分布建模: 我们通常使用Beta分布对每个动作的奖励概率进行建模。假设一个动作被执行了 $N$ 次，其中 $S$ 次成功（奖励为1），$F$ 次失败（奖励为0），那么该动作的奖励概率就服从参数为 $B(S+1, F+1)$ 的Beta分布。
2. 采样: 在每个时间步，为每个动作（每个拉杆）的Beta分布进行一次采样，得到一组奖励样本。
3. 选择: 选择样本中奖励值最大的动作并执行。
4. 更新: 根据执行动作后得到的实际奖励（1或0），更新对应动作的Beta分布参数。如果奖励为1，则 $S \leftarrow S+1$；如果奖励为0，则 $F \leftarrow F+1$。

马尔可夫决策过程

马尔可夫性质：下一个状态只取决于当前状态，而不会受到过去状态的影响的性质
马尔可夫过程：具有马尔可夫性质的随机过程，也被称为马尔可夫链，用元组$<S,P>$表示
状态转移矩阵：P，每行/每列的和为1。$p_{ij}=P(s_j s_i)$
马尔可夫奖励过程：在马尔可夫过程基础上加入奖励函数r和折扣因子$\gamma$，表示为$<S,P,r,\gamma>$
- $S$：有限状态集合
- $P$：状态转移矩阵
- $r$：奖励函数
- $\gamma$：折扣因子，$0\sim 1$范围，用于形容远期利益和近期利益哪个大，接近1更关注远期
回报：所有奖励衰减之后的和 $G_t = R_t+\gamma R_{t+1}+\gamma^2 R_{t+2}+...=\sum_{k=0}^\infty \gamma^kR_{t+k}$

马尔可夫奖励过程 MRP

即在马尔可夫过程基础上加入奖励函数$r$和折扣因子$\gamma$。

回报：在马尔可夫奖励过程中，从$t$时刻$S_t$装题啊开始到最终状态时，所有奖励的衰减之和。

\[G_t = R_t+\gamma R_{t+1} + \gamma^2 R_{t+2}+...=\sum^\infty_{k=0}\gamma^kR_{t+k}\]

价值：一个状态期望的回报
价值函数：输入为某个状态，输出为该状态的价值

\[V(s)=E[G_t|S_t=s] =E[R_t+\gamma V(S_t+1)|S_t=s]\]

贝尔曼方程： $V(s)=r(s)+\gamma\sum_{s'\in S}p(s'|s)V(s')$

将所有价值和奖励函数写成一个列向量，可以将贝尔曼方程表示为矩阵形式：

\[V=R+\gamma PV\]

矩阵运算求得解析解：$V=(I-\gamma P)^{-1}R$。计算复杂度较高，因此只使用很小的马尔可夫奖励过程

马尔可夫决策过程 MDP

即是MRP基础上加入了动作，有元组$<S,A,P,r,\gamma>$构成。这里$P(s’

s,a)$是状态转移函数，而不是矩阵

策略： $\pi(a s) = P(A_t=a S_t=s)$
确定性策略/随机性策略：每一个状态只输出一个确定/不确定的动作
状态价值函数： $V^{\pi}(s) = E_\pi [G_t|S_t=s]$
动作价值函数； $Q^\pi(s|a)=E_\pi[G_t|S_t=s,A_t=a]$

在策略$\pi$中，状态的价值等于该状态下所有动作的概率乘动作价值的和

在策略$\pi$中，状态s下采取动作a的价值等于即时奖励加上经过衰减后所有可能的下一状态转移概率与价值的乘积

贝尔曼期望方程；
- 状态价值函数 (state-value function) V(s): $V^{\pi}(s) = \sum_{a \in \mathcal{A}} \pi(a|s) \left(r(s,a)+\gamma \sum_{s', r} p(s'| s, a) V^{\pi}(s')\right)$
- 动作价值函数 (action-value function) Q(s, a): $Q^{\pi}(s, a) = r(s,a) +\gamma \sum_{s'\in S} p(s', r | s, a) \sum_{a' \in \mathcal{A}} \pi(a'|s') Q^{\pi}(s', a')$

计算状态价值函数时，先将其视为一个MRP问题，对于策略的每一个动作的概率看作成一个状态转移概率。求得V后用上式再求Q

蒙特卡洛算法

这里放一段动作选择代码（按照不同动作概率随机选取动作）

for a_opt in A:
    temp += Pi.get(join(s, a_opt), 0)
    if temp > rand:
        a = a_opt
        r = R.get(join(s, a), 0)
        break
rand, temp = np.random.rand(), 0

占用度量

状态访问分布 $\nu^\pi(s)$：策略 $\pi$ 与 MDP 交互时访问状态 $s$ 的概率
$\nu^\pi(s) = (1-\gamma)\sum_{t=0}^\infty \gamma^t P_t^\pi(s)$
- $P_t^\pi(s)$：时刻 $t$ 状态为 $s$ 的概率（$P_0^\pi=\nu_0$ 初始状态分布）
- $(1-\gamma)$：归一化因子
占用度量 $\rho^\pi(s,a)$：策略 $\pi$ 访问状态-动作对 $(s,a)$ 的概率
$\rho^\pi(s,a) = (1-\gamma)\sum_{t=0}^\infty \gamma^t P_t^\pi(s)\pi(a|s)$
\[\rho^\pi(s,a) = \nu^\pi(s) \cdot \pi(a|s)\]

策略等价定理
若两策略 $\pi_1, \pi_2$ 满足 $\rho^{\pi_1} = \rho^{\pi_2}$，则它们在访问过的状态上成比例：
$\pi_1 / \pi_2 \quad \text{(在访问过的状态上成立)}$
策略恢复定理
对合法占用度量 $\rho$（存在策略能生成该度量），可唯一恢复策略：
$\pi_\rho(a|s) = \frac{\rho(s,a)}{\sum_{a'}\rho(s,a')}$
- 分母 $\sum_{a’}\rho(s,a’)$ 等价于状态访问度量 $\nu(s)$

最优策略

计作$\pi^(s)$,且$V^(s)=\underset{\pi}{\max}V^\pi(s)$

最优状态价值函数和最优动作价值函数之间的关系为：

\[Q^*(s,a)=r(r,a)+\gamma\sum_{s'\in S}P(s'|s,a)V^*(s')\] \[V^*(s)=\max_{a\in A}Q^*(s,a)\]

贝尔曼最优方程：

\[V^*(s) = \max_{a \in \mathcal{A}} \left\{ r(s, a) + \gamma \sum_{s' \in \mathcal{S}} p(s'|s, a) V^*(s') \right\}\] \[Q^*(s, a) = r(s, a) + \gamma \sum_{s' \in \mathcal{S}} p(s'|s, a) \max_{a' \in \mathcal{A}} Q^*(s', a')\]

动态规划

策略迭代

策略评估

就是计算一个策略的价值函数$V^\pi (s)$。可以通过迭代的方式

\[V^\pi(s) = \sum_a \pi(a|s) \sum_{s'} P(s'|s,a) [R(s,a,s') + \gamma V(s')]\]

策略优化

对于策略$\pi$，找到一个新的策略$\pi ‘$能满足在任意状态s下，都满足 $Q^\pi (s,\pi '(s))\ge V^ \pi (s)$

于是在任意状态都有：$V^{\pi ‘}(s)\ge V^\pi (s)$ 这就是策略提升定理

策略迭代算法

就是不断重复策略评估-策略提升-策略评估-策略提升知道得到最优策略的过程。当连续两次策略相等时就得到了最优策略

价值迭代

与策略迭代类似，不过策略迭代算法会计算很多轮策略，而价值迭代只在策略评估中进行一轮价值更新然后根据更新后的价值进行策略提升。

价值迭代算法中，计算价值函数不是通过贝尔曼策略方程，而是通过贝尔曼最优方程，因此在计算价值函数的时候不需要考虑策略，即每一次都按照最优策略。

时序差分

用来估计一个策略的价值函数，不需要预先知道环境。

与蒙特卡洛方法不同的是：蒙特卡洛需要采样一条路径到头，然后才能计算这条路径的奖励和该状态的价值；时序差分可以只依据当前步即可计算。即用$r_t = \gamma V(s_{t+1})$

Sarsa 算法

每次使用五元组$(s, a, r, s’, a’)$进行增量更新

每次从$s$出发，采取$a$，获得$r$，到达$s’$，从$s’$按当前策略选取$a’$。

\[Q(s_t,a_t)\leftarrow Q(s_t,a_t)+\alpha [r_t+\gamma Q(s_{t+1},a_{t+1})-Q(s_t,a_t)]\]

多步 Sarsa 算法

就是在Sarsa算法上进行修改，结合了蒙特卡洛（无偏，但方差大）和Sarsa（方差小，但有偏）的特点。

本质上就是取二者的一个折中，将Sarsa的$G_t=r_t+\gamma Q(s_{t+1},a_{t+1})$换成了$G_t=r_t+\gamma r_{t+1}+…+\gamma ^nQ(s_{t+1},a_{t+1})$

\[Q(s_t, a_t) \leftarrow Q(s_t, a_t) + \alpha \left[ r_t + \gamma r_{t+1} + \cdots + \gamma^n Q(s_{t+n}, a_{t+n}) - Q(s_t, a_t) \right]\]

Q-learning 算法

\[Q(s_t, a_t) \leftarrow Q(s_t, a_t) + \alpha \left[ R_t + \gamma \max_a Q(s_{t+1}, a) - Q(s_t, a_t) \right]\]

与Sarsa不同的是，当其更新的时候，采用的是最优的动作价值函数。相当于采用了激进的更新方法，收敛更快，但可能更不稳定。

Dyna-Q 算法

是对Q-learning的改进，是一种基于模型的算法。在进行一步 Q-learning 之后进行N步的 Q-planning。就是通过与环境交互更新一次Q，然后通过自己的模型生成N次训练数据训练自己。相当于是自己“想象交互”。节省了与环境交互的成本。如果 N=0 则退化成Q-learning

DQN 算法

对于 CartPole 环境（一个车，一根杆，就是一阶倒立摆模型），他的状态无法使用有限的离散数据来描述，因为他的状态都是连续的，包括杆的位置、速度、车的位置、速度等。因此他的价值函数便不能用 Q-learning 的方法来解决

因此为了解决这个问题，就使用神经网络来表示动作价值函数，其目标函数如下：

\[\omega^* = \arg\min_{\omega} \frac{1}{2N} \sum_{i=1}^{N} \left[ Q_{\omega}(s_i, a_i) - \left( r_i + \gamma \max_{a'} Q_{\omega}(s'_i, a') \right) \right]^2\]

这个网络存在一个问题，就是神经网络的输出$Q(s’,a’)$在目标函数之中，这样就导致输出不稳定，因为当你神经网络参数一变，输出就变了，输出一边目标函数就变了，目标都变了就出问题。为了解决这个问题，引入了目标网络

首先原训练网络$Q_\omega(s,a)$来计算目标函数的$Q_\omega(s,a)$项，它正常更新参数，另外设计一个目标网络$Q_{\omega ^-}(s,a)$来计算目标函数的$(r+\gamma max_{a’}Q_{\omega^-}(s’,a’))$项，目标网络没隔C步才会与训练网络同步一次

超参数解释

lr = 2e-3 学习率
num_episodes = 500 总训练轮数
hidden_dim = 128 隐藏层数
gamma = 0.98 未来折扣因子，越接近1未来越重要
epsilon = 0.01 探索随机动作概率
target_update = 10 目标网络更新频率
buffer_size = 10000 经验池总大小
minimal_size = 500 开始经验回放时经验池最小大小
batch_size = 64 一批训练的样本数量

改进 DQN 算法

double DQN

DQN算法由于目标网络更新的频率很低，因此容易存在较大的误差。但由于在Q计算的时候是选择动作对应奖励的最大值，因此会产生过高估计。于是此算法将计算$\max_{a’}Q_{\omega^-}(s’,a’)$的过程拆开了，分为先选择动作再计算动作的价值

选择动作：通过训练网络来计算最大的下一步动作$a’$
计算价值：通过目标网络计算下一步动作的价值
DQN 的优化目标可以写为：$r + \gamma Q_{\omega^-}\big(s’, \arg\max_{a’} Q_{\omega^-}(s’, a’)\big),$动作的选取依靠目标网络 $Q_{\omega^-}$；
Double DQN 的优化目标为：$r + \gamma Q_{\omega^-}\big(s’, \arg\max_{a’} Q_{\omega}(s’, a’)\big)$，动作的选取依靠训练网络 $Q_{\omega}$。

dueling DQN

DQN算法在很多时候动作的，比如当直线行驶，前方没有车，道路比较宽的情况下，保持直的向前开和稍微向左或向右有一点偏差的情况下获得的回报没什么区别，也就是这种情况下不是特别关注动作的选择。而当前面有车的情况下，可能稍微偏了一点就导致相撞。因此这个算法思路就是将Q值分解成两个，一个是状态价值函数，一个是优势函数。前者只关注状态的好坏，而后者关注的是选择这个动作相较于其他动作的优势。

\[Q_{\eta, \alpha, \beta}(s,a) = V_{\eta, \alpha}(s)+A_{\eta,\beta}(s,a)\]

由于这里假如V和A一个加一个减可能导致Q不变，因此会导致训练不稳定，所以会将上式调整为：

\[Q_{\eta, \alpha, \beta}(s,a) = V_{\eta, \alpha}(s)+A_{\eta,\beta}(s,a)-\max_{a'}A_{\eta, \beta}(s,a')\]

或者

\[Q_{\eta, \alpha, \beta}(s,a) = V_{\eta, \alpha}(s)+A_{\eta,\beta}(s,a)-\frac{1}{|A|}\sum_{a'}A_{\eta, \beta}(s,a')\]

策略梯度算法

前面的算法都是基于价值函数的，这里是基于策略的算法

REINFORCE

就是训练一个策略模型。模型参数为$\theta$,模型通过梯度上升来训练，目标函数为： $J(\theta) = E_{s_0}[V^{\pi_0}(s_0)]$

对其求梯度为：

\[\nabla_\theta J(\theta)=E_{\pi_0}[Q^\pi_\theta(s,a)\nabla_\theta\log\pi\theta(a|s)]\]

此算法中对策略梯度的计算为：

\[\nabla_\theta J(\theta)=E_{\pi_0}\left[\sum^T_{t=0}\left(\sum^T_{t'=t}\gamma^{t'-t}r_{t'}\right)\nabla_\theta\log\pi\theta(a|s)\right]\]

Actor-Critic 算法

结合了策略网络和价值网络。策略网络的目标函数的梯度就是

\[\nabla_\theta J(\theta)=E_{\pi_0}\left[\sum^T_{t=0}\left(\sum^T_{t'=t}\gamma^{t'-t}r_{t'}\right)\nabla_\theta\log\pi\theta(a|s)\right]\]

价值函数的损失函数是：$L(\omega) = \frac{1}{2}(r+\gamma V_\omega(s_{t+1})-V_\omega(s_t))^2$ 梯度为

\[\nabla_\omega L(\omega)=-(r+\gamma V_\omega(s_{t+1})-V_\omega(s_t))\nabla_\omega\]

这个算法更像是策略梯度算法和DQN的结合。对比策略梯度来说，他将算法中的$\psi$替换成了类似于 dueling DQN 中的优势函数（区别在于优势函数是从当前时间到无穷的折算回报，但在此是下只有当前时间与下一时间的折算回报）。也就是说将原本的轨迹回报替换成了含有价值函数模型的时序差分残差$r+\gamma V_\omega(s_{t+1})-V_\omega(s_t)$。这样就有了策略和价值两个模型：Actor、Critic（是因为策略模型在角色上像演员，而价值模型像评论家）

看上图的步骤中，在更新价值参数和策略参数时，$\delta$是不参与梯度的计算的，因此代码中需要detach

TRPO 算法

在线策略的算法

策略目标

优化目标函数有两种，一种是采样一条路径，然后对这条路径上获得的奖励折算和做期望，即$J(\theta) = E(\sum_t \gamma^t r(s_t,a_t))$，另一种是初始状态的价值的期望，即$E[V^{\pi_\theta}(s_0)]$

新旧目标函数之间的差距为

\[J(\theta ') - J(\theta)=\frac{1}{1-\gamma} \mathbb{E}_{s \sim \nu^{\pi{\theta’}}} \mathbb{E}_{a \sim \pi{\theta’}(\cdot|s)} \left[ A^{\pi_\theta}(s, a) \right]\] \[J(\theta ') = \frac{1}{1-\gamma} \mathbb{E}{s \sim \nu^{\pi{\theta'}}} \mathbb{E}{a \sim \pi\theta(\cdot|s)} \Big[ \frac{\pi_{\theta'}(a|s)}{\pi_{\theta}(a|s)} A^{\pi_\theta}(s,a) \Big]\]

其中$\frac{\pi_{\theta’}(a

s)}{\pi_{\theta}(a

s)}$为重要性权重，就是按照旧策略采样的优势函数乘上一个这个权重就相当于了新策略的优势函数

整体的优化公式为：

$$\max_{\theta ‘}L_\theta(\theta ‘) = \max_{\theta ‘} J(\theta) + \mathbb{E}{s \sim \nu^{\pi{\theta}}} \mathbb{E}{a \sim \pi\theta(\cdot	s)} \Big[ \frac{\pi_{\theta’}(a	s)}{\pi_{\theta}(a	s)} A^{\pi_\theta}(s,a) \Big]$$
$$s.t. \ \ \mathbb{E}{s\sim \nu^{\pi{\theta_k}}}[D_{KL}(\pi_{\theta_k}(\cdot	s), \pi_{\theta ‘}(\cdot	s))]\le \delta$$

KL散度

所谓KL散度，其实是一种相对熵，详细讲是信息论中的内容。简单说就是他是形容两个分布之间的不对称距离，可以说是用分布Q去近似分布P时的信息损失

散度表达式为； $D_{KL}(P||Q) = \sum_xP(x)\log\frac{P(x)}{Q(x)}$

它等于 交叉熵 减去熵，即$-\sum_x P(x) \log Q(x)-(-\sum_x P(x) \log P(x))$。在此算法中就代表了两个策略之间的差别

近似求解

总之就是优化目标的解如下：

\[\theta_{k+1} = \theta_k + \sqrt{\frac{2\delta}{g^TH^{-1}g}}H^{-1}g\]

其中,$g=\nabla_{\theta’}\mathbb{E}{s\sim \nu^{\pi{\theta_k}}}\mathbb{E}{a\sim \pi{\theta_k}(\cdot

s)}\left[\frac{\pi_{\theta’}(a

s)}{\pi_{\theta-k}(a

s)}A^{\pi_{\theta_k}}(s,a)\right]$（目标函数梯度）,$H=\mathbb{H}[\mathbb{E}{s\sim \nu^{\pi{\theta_k}}}[D_{KL}(\pi_{\theta_k}(\cdot

s),\pi_{\theta’}(\cdot

s))]]$(策略之间平均距离的黑塞矩阵)

共轭梯度

共轭梯度法流程，他的目的就是求解方程$Hx=g$

这里面的x是梯度更新的方向，而$\sqrt{\frac{2\delta}{x^THx}}$是参数更新时的最大步长

线性搜索

就是找到一个最小的整数i，使得$\theta_{k+1}=\theta_k + \alpha^i\sqrt{\frac{2\delta}{x^THx}}x$求出来的$\theta_{k+1}$满足KL散度限制。本质上就是找到一个最小的i满足前面所说的不等式。

$\alpha$是一个决定搜索长度的超参数

广义优势估计 GAE

思想就是根据多步时序差分。

有点类似于多步sarsa算法中对G的估计。本质上就是估计一步的优势、多步的优势和无穷步的优势，引入了这个超参数$\lambda$接近1就是接近蒙特卡洛，接近0就是接近一步估计。区别在于一步估计方差大但无偏；蒙特卡洛方差小但有偏

算法步骤

TRPO算法整体步骤如下：

超参数解释

num_episodes = 500 总训练轮数
hidden_dim = 128 隐藏层神经元数
gamma = 0.98 未来价值折扣因子，越大未来越重要
lmbda = 0.95 GAE平滑系数，调大的话优势估计方差变小，偏差变大
critic_lr = 1e-2 价值网络学习率
kl_constraint = 0.0005 kl散度容忍值
alpha = 0.5 决定线性搜索长度，越接近1搜索越长，搜索歩幅越小

PPO 算法

说是一般PPO截断效果比PPO惩罚更好

在线策略的

PPO惩罚

目标函数： $\arg \max_{\theta} \mathbb{E}_{s \sim \nu} \mathbb{E}_{a \sim \pi_{\theta_k}(\cdot|s)} \left[ \frac{\pi_{\theta}(a|s)}{\pi_{\theta_k}(a|s)} A^{\pi_{\theta_k}}(s,a) - \beta D_{KL}[\pi_{\theta_k}(\cdot|s), \pi_{\theta}(\cdot|s)] \right]$

令 $d_k = D_{KL}[\pi_{\theta_k}(\cdot

s), \pi_{\theta}(\cdot

s)]$，$\beta$ 的更新规则如下：

如果 $d_k < \delta / 1.5$，那么 $\beta_{k+1} = \beta_k / 2$
如果 $d_k > \delta \times 1.5$，那么 $\beta_{k+1} = \beta_k \times 2$
否则 $\beta_{k+1} = \beta_k$

PPO 截断

PPO截断的目标函数为 $\arg\max_\theta \mathbb{E}{s \sim \nu^{\pi{\theta_k}}, \, a \sim \pi_{\theta_k}(\cdot|s)} \left[ \min \left( \frac{\pi_\theta(a|s)}{\pi_{\theta_k}(a|s)} A^{\pi_{\theta_k}}(s,a), \mathrm{clip}\!\left(\frac{\pi_\theta(a|s)}{\pi_{\theta_k}(a|s)}, 1-\epsilon, 1+\epsilon\right) A^{\pi_{\theta_k}}(s,a) \right) \right]$

就是将超过KL散度的部分给截掉了，更直接。clip函数就是将策略的比值限制在了$1+\epsilon$和$1-\epsilon$之间了。如果优势函数大于0，说明该动作高于平均值，让目标函数增大就会增加新策略对该动作的概率（但与旧策略比值不会超过$1+\epsilon$），反之当优势函数小于0，则会减小新策略中该动作概率（同样与旧策略比值不会低于$1-\epsilon$）

与TRPO不同的还有一点开始没有注意到的，就是PPO多了一个循环，就是在采样一轮数据后采用这些数据训练epoches次（对应下面的超参数）。意义是每次训练歩幅都很小，可能会浪费数据（采样的价值可能比梯度计算更高）。因此对于同一批数据选择多训练几次，反正有散度在那约束不可能效果变差。

超参数解释

actor_lr = 1e-3 策略网络学习率
critic_lr = 1e-2 价值网络学习率
num_episodes = 500 训练总轮数
hidden_dim = 128 隐藏层神经元数
gamma = 0.98 未来价值重要性参数
lmbda = 0.95 GAE平滑系数，调大的话优势估计方差变小，偏差变大
epochs = 10 每个采样批次训练次数
eps = 0.2 描述PPO截断的范围

DDPG 算法

是一个离线策略算法

这个算法的核心大部分相当于将前几个算法的核心思想拼接起来的。首先它是含有Actor-Critic网络，但是他的critic网络的输出不是状态价值函数，而是动作价值函数，也就是说它需要多一个动作的输入，输出这个动作的价值。然后他又像DQN一样，对动作的选取采取最大动作价值对应的动作，这是它的策略，是一个确定性策略（即返回的是一个动作，而不是一些动作的概率），这个策略用$\mu$表示（我觉得是相对于前面算法的策略分布而言，这个$\mu$相当于分布中的峰值了）。

此外这个算法还设置了目标网络，目标网络更新方式也和之前不一样，采用的是软更新的方式。即

\[\omega^-=\leftarrow\tau\omega+(1-\tau)\omega^-\]

就是让目标网络缓缓接近训练网络。策略网络和价值网络的目标网络都是这样更新

此外，在策略网络选择动作时，为了更好探索，加入了高斯噪声

超参数列表

actor_lr = 3e-4 策略网络学习率
critic_lr = 3e-3 价值网络学习率
num_episodes = 200 训练总轮数
hidden_dim = 64 隐藏层神经元数
gamma = 0.98 未来价值重要性参数
tau = 0.005 软更新接近速度
buffer_size = 10000 经验池大小
minimal_size = 1000 经验池达到多大时开始提取
batch_size = 64 训练一轮样本数
sigma = 0.01 动作输出时加入高斯噪声标准差用于探索

SAC 算法

与前面的强化学习算法不同的是，SAC算法的强化学习目标是最大熵强化学习，前面介绍的目标函数是最大化累计奖励

这里面引入了熵$H( X) = \mathbb{E}_{x~p}[-\log p(x)]$。这我熟啊，热力学里面的熵嘛。

在这里引入了熵来表示策略在该状态下的随机程度。这里的目标函数为：

\[J(\pi) = \mathbb{E}\sum_tr(s_t,a_t)+\alpha H(\pi(\cdot|s_t))\]

使用的贝尔曼方程也变成了soft贝尔曼方程了，将原先的$Q_{t+1}$换成了$V^{soft}(t+1)$,也就是将价值函数给通过softmax平滑了一下

\[V(s_t) = \mathbb{E}_{s_t~\pi}[Q(s_t,a_t)-\alpha\log \pi(a_t|s_t)]=\alpha \log \sum_{a} \exp\Big(\frac{Q(s,a)}{\alpha}\Big)\]

这里面使用的一个策略更新公式为：

\[\pi_{new} \leftarrow \arg\min_{\pi'} D_{KL}\bigg(\pi'(\cdot|s),\frac{\exp(Q^{\pi_{old}}(s,\cdot)/\alpha)}{Z(^{\pi_{old}}s)}\bigg)\]

说明一下，这里第二项就是一个$Q/\alpha$的softmax，Z是归一化常数，就表示对上面的求和。这里其实最理想的是直接求$\frac{\exp(Q^{\pi_{old}}(s,\cdot)/\alpha)}{Z(^{\pi_{old}}s)}$，但是由于这个价值网络Q不好直接求softmax，因为他是连续的（连续动作softmax积分不可解且不好采样）、且不能直接用nn输出一个分布，所以采用了求两个分布的KL散度用一个策略分布$\pi’$来近似它

在SAC算法中，采用两个Q网络和一个策略网络，两个Q网络采用Q值更小的，从而缓解其过高估计的问题（类似 double DQN）

价值网络的损失函数为：

\[L_Q(\omega) = \mathbb{E}_{(s_t,a_t,r_t,s{t+1})\sim \mathcal{R},\,a_{t+1}\sim\pi_\theta(\cdot|s_{t+1})} \left[ \frac{1}{2} \big( Q_\omega(s_t,a_t) - (r_t + \gamma (\min_{j=1,2} Q_{\omega^-j}(s{t+1},a_{t+1}) - \alpha \log \pi(a_{t+1}|s_{t+1}))) \big)^2 \right]\]

策略网络的损失函数为：

\[L_\pi(\theta)=\mathbb{E}_{s_t~R,a_t~\pi_\theta}[\alpha\log(\pi_\theta(f_\theta(\epsilon_t;s_t)|s_t))-\min_{j=1,2}Q_{\omega_j}(f_\theta(\epsilon_t;s_t)|s_t)]\]

可以理解为最大化V的同时，考虑了两个策略函数。这里面的$f_\theta(\epsilon_t;s_t)$是一个重参数化技巧，就是将对a求梯度的过程转换成了$a=f_\theta(\epsilon_t;s_t)=\mu_\theta(s_t)+\sigma_\theta(s_t)\cdot\epsilon$，就是对A的分布的参数$\mu、\sigma$求梯度。这里$\epsilon$就是一个标准正态分布。

此外，SAC算法还设置了让熵正则项可以自动调整。其实就是调整正则项的系数$\alpha$。让这个系数可以训练更新，相当于将其看成一个小型网络，其损失函数为：

\[L(\alpha)=\mathbb{E}_{s_t~R,a_t~\pi(\cdot|s_t)}[-\alpha\log\pi(a_t|s_t)-\alphaH_0]\]

算法流程如下：

多臂老虎机问题 MAB

$\epsilon$ - 贪心算法

上置信界算法 (UCB)

汤普森采样算法

马尔可夫决策过程

马尔可夫奖励过程 MRP

马尔可夫决策过程 MDP

蒙特卡洛算法

占用度量

最优策略

动态规划

策略迭代

策略评估

策略优化

策略迭代算法

价值迭代

时序差分

Sarsa 算法

多步 Sarsa 算法

Q-learning 算法

Dyna-Q 算法

DQN 算法

超参数解释

改进 DQN 算法

double DQN

dueling DQN

策略梯度算法

REINFORCE

Actor-Critic 算法

TRPO 算法

策略目标

KL散度

近似求解

共轭梯度

线性搜索

广义优势估计 GAE

算法步骤

超参数解释

PPO 算法

PPO惩罚

PPO 截断

超参数解释

DDPG 算法

超参数列表

SAC 算法

目录

标签

伙伴