zhkmxx930 blog

一、摘要二、先序工作三、方法3.1 Overview（1）使用few-shot 方法解决非确定性环境下的连续自适应问题存在的问题:
agent必须从有限的过往经验中学习，并且这些过往经验是在没有环境变化下收集的。
（2）解决方法：
​ 基于MAML进行构建，其中MAML (gradient-based model-agnostic meta-learning)，在few-shot方法中效果较好。
​ 本文从概率的角度对MAML在multi-task RF方向上进行扩展，并最终将其扩展到动态变化的任务中去。

3.2 MAML的概率视角2-1 定义
给定任务的分布 $D(T)$，对于每个任务$T$，$T$是一个如下的四元组

$L_T$表示任务相关的Loss function，其将trajectory $\tau:=(x_0,a_1,x_1,R_1,…a_H,x_H,R_H)$与loss值进行映射;
$P_T(x)$和$P_T(x_{t+1}|x_t,a_t)$定义了任务$T$中的马尔科夫决策过程;
$H$表示任务的时间域(Horizon)；
$x_t$表示observations, $a_t$表示actions,

对于每个任务的Loss function $L_T$定义为：
2-2 Adaption Update

元学习的目标是找到一个过程，该过程能够通过在从$D(T) $采样的任务中获得有限经验的情况下，产生解决元学习问题的良好策略。具体为：

在使用策略$\pi_\theta$，从$D(T)$上采样了$K$个task $T \sim D(T)$，表示成$\tau_\theta^{1:K}$之后，构建一个新的针对采样出来的某个特定任务的策略$\pi_\phi$， 该策略的目标是在任务$T$上减小子序列的loss的期望 (expected subsequent loss)。

公式化上述描述即Adaption Update（Meta Upate）过程，MAML使用参数为$\theta$的$L_T$的梯度，构建了针对特定任务策略的参数$\phi$:

2-3 Meta Loss定义
Meta-Loss的定义如下：

一般情况下，$\phi$从某种条件概率分布 $P_T(\phi|\theta, \tau_{1:k})$ 中生成， Meta Update公式等价于假设delta分布，即

2-4 Meta Loss优化

对于优化Meta-Loss，可以采用策略梯度的方法(TRPO，PPO等)按下述梯度进行优化。

3.3 通过Meta-Learning实现连续自适应​ 在经典的多任务中，我们不假设任务的分布，$D(T)$。当环境是non-stationary时，可以把它看作是在某个时间尺度上的一系列stationary任务，其中任务对应于环境的不同动态。然后，$D(T)$由环境变化定义，任务将依赖于一定连续任务。因此，利用连续任务和meta-learn之间的依赖性，不断update policy，从而最大限度地减少与不断变化的环境交互过程中遇到的总loss期望。
​ 例如，在Multi-agent中，当与不断优化自身策略的对手（例如，由于学习）进行比赛时，我们的agent应该理想地进行元学习，以预测更改并相应地更新其策略。
3-1 non-stationary的马尔科夫表示

​ 以概率的角度来描述non-stationary环境，该环境等价于上图所示的Markov 链表示的任务序列分布。 其目标是最小化某个长度$L$的马尔科夫任务序列上的loss期望。

​ 其中$P(T_0)$和$P(T_{i+1}|T_i)$表示初始概率及任务序列的马尔科夫链的概率转移。 值得注意的是，
​ （1）这里的动态马尔科夫链是二级层次化的，其中高层为任务的动态变化，下层为具体任务的MDP；
​ （2）目标$L_{T_i,T_{i+1}}$依赖于Meta learning过程定义的形式。
3-2 连续任务的Meta Loss定义
​ 由于我们对任务间马尔可夫变换的最佳Adaption Update感兴趣，因此我们将一对连续任务的Meta Loss 定义如下：

​ 对于连续任务的Meta Loss与第二章定义的Meta Loss的不同之处在于：
（1） 连续任务的Meta Loss的trajectory $\tau_{i,\theta}^{1:K} $来自当前的任务$T_i$ , 并且用来构建Policy $\pi_\phi$ ，以便于执行下一个任务$T_{i+1}$；（2） 虽然策略参数$\phi_i$是依赖于序列的，但是在上面连续任务的Meta Loss中一般初始参数设置为$\theta$。 P.S.(这是出于稳定性考虑。我们从经验上发现优化顺序更新$\phi_{i}$到$\phi_{i+1}$是不稳定的，通常倾向于发散，而从相同的初始化开始导致更好的行为。)
​ 因此，优化$L_{T_i，T_{i + 1}}(θ)$ 相当于使用任务链中的单位滞后，截断随着时间的推移反向传播。
3-3 连续任务的Adaption Update
​ 为了构建任务$T_{i+1}$的策略参数，我们从参数$\theta$开始，使用adaptive update进行多次 meta-gradient step。(假设step数是$M$，经验参考值为2~5次): 【原文中的公式(7)】
​ 其中${\alpha_m}^M_{m=1}​$是meta-gradient step sizes 集合，其优化与$\theta​$ 相关。 这部分的meta-update计算图如下图所示:

3-4 连续任务的Meta Loss优化
​ 连续任务的Meta Loss优化和Meta Loss优化的形式基本相同，只是现在要同时考虑$T_i$和$T_{i+1}$的期望：【原文中的公式(8)】

​ 需要注意的是：
​ 计算adaption update的时候需要在策略$\pi_\theta$下与环境进行交互并同时计算meta-loss。

3.4 训练过程中的Meta-Learning​ 当获得了一系列连续任务对的分布$P(T_{i-1},T_i)$之后，我们可以通过使用梯度方法，对参数$\theta$和$\alpha$同时优化来实现对 adaptation updates 的 meta learn。

Algorithm1： 在任务$T_{i+1}$中交互时，使用$\pi_\theta$ 策略从$T_i$和$\pi_\phi$收集 trajectory。(line 5)
​ 直观地说，该算法搜索$θ$和$α$，这样根据$T_i$的轨迹计算出的adaptive update(参照原文公式(7))，产生一个策略$π_\phi$，这有助于对于求解$T_{i+1}$。这里的主要假设是，$T_i$的轨迹包含了一些关于$T_{i+1}$的信息。注意，将adaption steps 作为计算图(图c)的一部分，并通过整个图的反向传播来优化$θ$和$α$，这需要计算二阶导数。

3.5 执行过程中的自适应​ 为了在training过程中计算无偏自适应梯度，必须要使用策略$\pi_\theta $在任务$T_i$上收集经验。在test过程中，由于环境的不确定性，通常很难多次遇到同样的任务。因此，保持使用$\pi_\phi$进行决策，并且对每个新任务，reuse过往经验来计算更新参数$\phi$ (参考algorithm2)：

​ 为了修正过往经验的策略与当前的策略$\pi_\theta$的区别，使用重要性采样进行修正，在每一个单步meta update过程中，执行以下操作：【原文中的公式(9)】

​ 其中$\pi_{\phi_{i-1}}$和$\pi_{\phi_i}$分别用来从任务$T_{i-1}$和$T_{i}$中生成轨迹。对于公式(7)中的多步更新，直接将对应项按照公式(9)换成重要性采样就行了

一、概述
提出一种较为通用的，去除繁杂假设的，高效的算法层次强化学习算法框架；

框架
$High-Level \space\space\space\space\space {———>}^{auto} \space\space\space\space Goal ————> ^{supervised} \space\space\space\space Low-Level controller$

使用Off-Policy进行High-level及Low-level训练，通用化的设计，使得较好的在low-level controller中使用DDPG，TD3等确定性、off-policy的算法，兼容性强；

提出针对于High-level的Off-Policy Correction。

二、 方法HIRO(HIerarchical Reinforcement learning with Off-policy correction)

[Low-level $\mu^{lo}$]
使用 Parameterized reward function 来表达特定的底层策略(潜在的无穷集合)；
通过训练相关策略，使其能够将obs $S_t$ 与期望Goal $g_t$相匹配。

[High-level $\mu^{hi}$]
为temporally-extended experience选择目标序列；
使用off-policy correction使得其可以使用过往经验，来适应新的底层控制器策略。

[综合]

高层控制器构建较粗的抽象的目标给底层；

这些目标直接对应于底层控制器想要尝试去达到的states；

每一个timestep, 高层控制器使用由环境交互产生的state，并通过
​ ①每隔一段时间从高层控制器网络$\mu^{hi}$中进行采样($g_t\sim\mu^{hi}$)，或者
​ ②使用一个固定的目标转换函数$g_t=h(s_{t-1},g_{t-1},s_t)$
等方式来生成high-level action(or goal) $g_t\in\mathbb{R}^{d_s}$；

对于上述产生的目标成为临时目标，每固定c步将进行重新采样；

底层控制器通过当前的状态及目标进行决策到仿真环境的动作$a_t \sim \mu^{lo}(s_t,g_t)$；

高层控制器使用一个固定的Parameterized reward function $r$ 向底层控制器提供一个内在的回报函数(intrinsic reward) $r_t=r(s_t,g_t,a_t,s_{t+_1})$；

底层策略将存储经验$(s_t,g_t,a_t,r_t,s_{t+1},h(s_t,g_t,s_{t+1}))$用于off-policy training；

高层控制器每隔c步获取环境回报$R_t$，存储高层状态转移序列$(s_{t:t+c-1},g_{t:t+c-1},a_{t:t+c-1},R_{t:t+c-1},s_{t+c})​$用于off-policy training。

三、具体策略
Parameterized reward function
(1) 如何理解目标$g_t$
​ 高层控制器产生的Goal $g_t$ 意味着对于当前的观测状态的期望相对变化，即$g_t$代表着从当前$s_t$开始，底层控制器应该如何决策才能使得c步之后的$s_{t+c}$与$s_t+g_t$能够足够的接近。
(2) 如何设计一个比较泛化的目标空间
​ 为了在不考虑状态变化的情况下保持目标的相同绝对位置，目标转换模型$h$定义为:
(3) 如何设计高层到底层的内在回报函数Parameterized reward function
​ 该回报函数通过定义当前状态与目标状态之间的欧式距离来表示:
(4) 底层控制器的策略算法如何选择
​ 通过简单的将目标$g_t$加入观测元组的方式，使得底层框架可以使用强化学习的标准方法进行学习。
​ 比如使用DDPG那么loss就加入目标：
(5) 与以往工作的不同
​ Parameterized reward function 在之前的工作中也用过，但是他们用的时候目标都是间接通过表征学习给出的，而本文直接将目标当做一种预期的状态给到底层，更加直接。

高层训练使用的Off-policy Correction
(1)以往的工作大多基于on-policy ，这里引入了off-policy进行学习会带来怎样的问题
​ 引入off-policy的话，由于底层策略网络$\mu^{lo}$在当前和从replay buffer中采样的时候的策略网络是不同的，因而对于同一个目标，在前后两种策略网络下的状态转移序列是不同的。
(2) 如何解决以上问题
​ 高层策略网络的状态转移序列为$(s_{t:t+c-1},g_{t:t+c-1},a_{t:t+c-1},R_{t:t+c-1},s_{t+c})$，我们将其转换为可以push到replay buffer中的state-action-reward 转移序列$(s_t,g_t\sum R_{t:t+c-1},s_{t+c})$，以兼容各种标准off-policy强化学习方法。
​ 更改$g_t$使其能够适应新的$\mu^{lo}$:

先前的目标$g_t$诱导底层产生$a_{t:t+c−1} ∼ \mu^{lo}(s_{t:t+c−1}, g_{t:t+c−1})$行为。
调整上述目标变成$\tilde {g_t}$使其能够诱导新的底层策略产生最大化概率：$\mu^{lo}(a_{t:t+c−1}|s_{t:t+c−1}, \tilde{g}_{t:t+c−1})$
$\tilde{g}$使用固定的目标转移函数$h$来得到

(3) 如何获得新目标$\tilde{g}​$的最大化概率
​ 对于一般的强化学习算法而言策略的log概率可以表示为:
​ 这里文章通过离散采样的方式选择一个较大的值作为最大概率的估计，采样10个点为：

$g_t$

• 按高斯分布在以$s_{t+c} − s_{t}​$为中心的分布上采样得到8个点

• $s_{t+c} − s_t$

​

参考

一、确定性策略梯度​ Deepmind的D.Silver等在2014年提出DPG： Deterministic Policy Gradient， 即确定性的行为策略，每一步的行为通过函数$μ$直接获得确定的值：
​ 这个函数$μ$即最优行为策略，不再是一个需要采样的随机策略。为何需要确定性的策略？简单来说，PG方法有以下缺陷：
​ 即使通过PG学习得到了随机策略之后，在每一步行为时，我们还需要对得到的最优策略概率分布进行采样，才能获得action的具体值；而action通常是高维的向量，比如25维、50维，在高维的action空间的频繁采样，无疑是很耗费计算能力的。在PG的学习过程中，每一步计算policy gradient都需要在整个action space进行积分:
​ 这个积分我们一般通过Monte Carlo 采样来进行估算，需要在高维的action空间进行采样，耗费计算能力。如果采取简单的Greedy策略，即每一步求解$ argmax_a Q(s,a)$也不可行，因为在连续的、高维度的action空间，如果每一步都求全局最优解，太耗费计算性能。​ 将DPG算法融合进actor-critic框架，结合Q-learning或者Gradient Q-learning这些传统的Q函数学习方法，经过训练得到一个确定性的最优行为策略函数。

二、DPGDPG算法本身采用的是PG方法,且是Off-Policy方法(也可以是On-Policy)，因而直接对轨迹的价值回报进行求导。如下式求导，其中$\mu_\theta (s)$为生成确定性行动的策略函数。
根据链式法则，由于$\mu_\theta(s)$与确定性策略价值函数$q_\mu$有关,因而：
由于是确定性策略，在价值函数$q(s,μ_\theta(s))$中有策略参数$\theta$，因此需要将价值函数对策略求导。
相较于随机策略梯度算法而言,如下是随机性策略梯度的目标函数梯度:
在DPG这个梯度公式中，没有了与动作有关的期望项，因此相对于随机性策略，确定性策略需要的学习数据少，算法效率高，尤其对于动作空间维数很大的情况。

三、策略模型参数的一致性​ 在DPG中为了更好地使用Off-policy,并使用TD降低方差，定义函数 $Q^\omega (s,a):S×A→R$ 用来拟合真实的状态动作值函数$\hat{Q}^\pi(s,a)$，如果$Q^\omega$收敛，那么L2范数梯度将满足如下公式:
​ 在计算梯度时可以使用$Q^ω:S×A→R $代替真实的动作状态值函数$Q(s,a) $。并且神经网络满足这个性质，因此可以使用神经网络拟合动作状态值函数。这样价值模型不需要遵循某个具体的策略，因此可以使用off-policy的方式进行学习更新。

四、DPG目标函数
on-policy的确定性策略梯度算法

off-policy的确定性策略梯度算法(Replay buffer中的数据是通过$\beta$采样得到的)

​ 上两式的区别就是使用了不同的数据采样分布。可以看到off-policy缺少了重要性采样，这是由于确定性策略的动作是固定值，不是一个分布；其次是因为确定性策略值函数的评估采用的是Q-learning的方法，即使用TD(0)估计动作值函数并忽略重要性权重，值函数不依赖于任何策略，并贪心获取下一个动作。
​ 这个$β$不是我们想要得到的最优策略，仅仅在训练过程中，生成下达给环境的action， 从而获得我们想要的数据集，比如状态转换(transitions)、或者agent的行走路径等，然后利用这个数据集去 训练策略$μ$，以获得最优策略。在test 和 evaluation时，使用$μ$，不会再使用$β$。

[Actor]衡量一个策略网络的表现(策略网络目标函数)，最大化策略目标: (根据上面推导的DPG)

​ $s$是环境的状态，这些状态(或者说agent在环境中走过的状态路径)是基于agent的behavior策略产生的，它们的分布函数(pdf) 为$ρ^β$；​ $Q^\omega(s,μ(s))$ 是在每个状态下，如果都按照$μ$策略选择acton时，能够产生的$Q$值。 也即，$J_β(μ)$是在$s$根据$ρ^β$分布时，$Q^\omega(s,μ(s))​$ 的期望值。

[Critic]最小化值网络目标:

最终DPG的目标函数为:（$\omega$是值网络(SGD优化)，$\theta$是策略网络(SGA优化)）
​
参数更新为：

五、DDPGDDPG借用了target net还有滑动平均方法更新behavior网络参数
其更新方法如下：

对比一下DQN

六、TD3
参考：

TD3(Twin Delayed Deep Deterministic policy gradient algorithm )主要对DDPG做了一些改进:

引入DoubleDQN的思想，来消除过拟合问题(两个Critic, 一个Actor)
DoubleDQN中使用Current Net（Behavior net）来代替TargetNet，以减小Bias。
映射到DPG过程中,其中$\pi_φ(s’)$是CurrentNet:
即critic用更新较慢的target network，actor还是更新快的；但由于本身actor更新也不快，所以没啥效果。
如果类比double Q-learning，使用两个actor、两个critic写出来的更新目标为

本着“宁可低估，也不要高估”的想法（因为actor会选择高的，因此高估的会累积起来），再把目标改写成

最后发现两个actor也没啥用，就用一个actor，这个actor根据 $Q_{\theta_1}​$ 来更新。两个critic的更新目标都是一样的，即 $y_2 = y_1​$ 。这样的算法相比于改变之前的就等于多了一个和原来critic同步更新的辅助critic $Q_{\theta_2} ​$，在更新target的时候用来取min。

使用TargetNet
实验结果表明，当policy固定不变的时候，是否使用target network其价值函数都能最后收敛到正确的值；但是actor和critic同步训练的时候，不用target network可能使得训练不稳定或者发散。因此算法的中critic的更新目标都由target network计算出来

并且，价值函数估计准确之后再来更新policy会更好，因此采用了delayed policy update，即以较高的频率更新价值函数，以较低的频率更新policy。

使用Target Policy 平滑正则
希望学到的价值函数在action的维度上更平滑，因此价值函数的更新目标每次都在action上加一个小扰动

七、D4PG
论文

总体框架与DDPG相同，引入了一些trick：

支持分布式，由于是off-policy的算法，因此可以使用多个actor去分布式地采样，然后存储在同一个replay buffer中，learner从buffer中采样，更新之后再将权重同步到各个actor上

critic使用价值函数分布，损失函数变为(d是距离度量)：
其中$(T_\pi Z)(x, a)=r(x,a)+\gamma\mathbb{E}[Z(x’,\pi(x’))|x,a]$ 为 distributional Bellman operator, $Z$是用来估计Q的， $Q_\pi(x,a) = \mathbb{E}Z_\pi(x,a)$

引入n-step TD error：这样可以减少更新的variance

使用prioritized experience replay：可以加速学习

距离衡量指标
参考：

聚类效果衡量指标
参考:

常用评估:

类别信息已知

调和兰德系数 (ARI)
调和互信息 (AMI)
调和平均 (V-Measure)

类别信息未知

轮廓系数 (Silhouette Coefficient)

基于划分的聚类
KMeans 参考:
K-mediods聚类，将Kmeans的平均值换成中值，避免噪声的干扰
KMeans++: 优化KMeans的聚类中心初始化，选择距离当前聚类中心的距离概率最大可能的点作为下一个聚类中心。参考:

层次聚类

自上而下的分裂层次聚类(DIANA)

自下而上的凝聚层次聚类(AGNES)

密度聚类
DBSCAN : 参考
密度最大值聚类: 参考
AP ：参考

谱聚类
谱聚类基本原理: 参考
谱聚类与PCA的异同: 参考

一般步骤：
1）输入：相似度矩阵S（Rn∗n）、目标聚类数目k （在此之前需要完成两项工作： 1.选择合适的相似度函数，2.选择合适的聚类数目k）2）构造出相似图及其赋权的邻接矩阵（weighted adjacency matrix） （这一步需要选择：相似图的类型以及相应的参数）3）计算出相似图的Laplacian矩阵 （这一步需要选择：Laplacian矩阵的类型）4）计算Laplacian矩阵的前k个特征值对应的特征向量，以这k个特征向量为列，拼出新的矩阵Un∗k）5）视矩阵U的每一行为Rk中的一个点，对这n个点y1，y2，…yn进行k−means聚类，得到k个聚类C1，C2，…Ck6）输出聚类结果A1,A2,…Ak：yi被分到Cj中的哪一类，xi就被分到相应的Aj类

[Leetcode 198]
解法：一个经典的dp题，从选与不选的角度进行考虑，
终止条件是第0个的时候只有一个可以选，有两个的时候，选二者中大的那个。

参考：

代码：

[Leetcode 213]
解法：由于有环，那么给他拆分成[0,n-1] 和 [1,n]两个部分进行分别dp，最后取两个区间中取值大的。
代码：

[Leetcode 139]
解法(4种)

解法一: DFS

解法二: 记忆化DFS

解法三: bottom up DP
[子问题定义] : DP子问题是从0开始到当前位置的子串是否可分(dp[i] == true?)，当前位置总共有n个可能，所以子问题的个数是n个。
使用hashset转储dict
构建dp数组，默认初始空串是可分的即dp[0]=1,
遍历初始串，验证从前面可分的子串尾部到当前位置的字符串([j为dp[j]==1, i])是否在字典中，如果在字典中则记录当前位置可分

解法四: Bottom up DP + max trick

代码:

[Leetcode 124]
解法:
找二叉树中的最大路径和，首先要考虑清楚是从上往下找，还是从下往上找，通过观察树的结构， 我们发现从下到上最好找。

1、最优子结构 因为树是由一个个更小的结点树组成，所以我们可以把问题分解成一个个更小的树。 当树的结点只有一个时，最大的路径就是他自身，让树的高度为2时，根节点的最大路径为左右结点中的最大值加上根节点本身的值：max(l, r) + root.val， 如果左右结点都为负数，还没有自身的值大呢，所以我们取其中的最大值。maxSubSubTree = max(max(l, r) + root.val, root.val) 知道了二叉树的最优左右路径，我们需要比较整体路径，maxSubTree = max(maxSubSubTree, l+r+root.val)。 再将以该结点为根节点的二叉树的最大路径和，和全局的路径和比较，取两者最大值，res = max(res, maxSubTree)2、重叠子问题 从下往上走，当底层的最优路径找出来了， 上一层结点就能直接用下一层的结果,依次向上递推，求解过程都简化成了对若干个个高度为2 的二叉树的操作。当递归完成时，根节点的值就是整颗二叉树的最大路径和。

代码:

[Leetcode 128]
解法：(参考)
使用hashmap来构建，将数组中的值作为键，连续元素数目作为边界值，并存储在hashmap的连续区域边界节点中。
节点更新有三种情况:

当前元素在hashmap中没有左右邻居，那么该节点的hashmap值为1 ;
当前元素在hashmap中有左或右邻居(只存在一边)，那么该节点的hashmap值为其对应左右边界的连续值加1
当前元素能够桥接两个连续区域，那么该节点的hashmap值可以不关心，但是其左侧的左边界值与右侧部分的右边界值对应加一。

代码：

一、 重要性采样TRPO和PPO主要思想的数学基础是重要性采样

重要性采样：$x_i $是从$p(x)$分布中采样得到的， 但是$p(x)$的值往往无法直接获得，需要通过其他分布$q(x)$进行间接采样获得。

条件：

$p$分布与$q$分布需要相近，才能得到较好的效果。

用在强化学习里面:

由于策略梯度原始公式中的 新策略分布难以得到，因而使用旧策略进行间接采样，以使得未知项变成可估计的已知项进行计算。

二、 梯度与参数更新1. 回报的期望：最大化全部采样轨迹上的策略回报值，$R(\tau)$ 表示某一个轨迹$\tau$的回报值
2. 回报的期望的梯度：(第三个等号用到的公式：$\nabla f(x) = f(x) \nabla \log f(x)​$)
式中

$N​$表示采样了$N​$条trajectory, $T_n​$表示每条trajectory的step数量。

关于$p_{\theta}(\tau)$
由两部分组成一部分是来自环境的 $p_\theta(s_{t+1}|s_t, a)$， 一部分是来自agent的 $p_\theta {(a_t|s_t)}$, 其中来自环境的部分不带入计算，策略更新只考虑agent这部分。所以最后一步并没有$t+1$这部分。

3. 参数更新：

三、 实际算法中对策略梯度的处理方法
策略梯度方法：
加入baseline

$b$ 的加入保证reward不是恒大于0的，若reward一直大于0，则会导致未被采样的action无法得到提升，但其实该action并不是不好而是未被采样。

状态值函数估计轨迹回报：
$R(\tau^n)-b$ 部分使用状态值函数来替代

优势函数估计轨迹回报：
$R(\tau^n)-b​$ 部分用以下Advantage function来替代

TD-Error估计轨迹回报：(A3C)使用值网络估计值，引入bias减小variance
$R(\tau^n)-b​$ 部分用以下TD-Error 代替

四、GAE(Generalized Advantage Estimation)
GAE的作用

GAE的意思是泛化优势估计，因而他是用来优化Advantage Function优势函数的。
GAE的存在是用来权衡variance和bias问题的：
On-policy直接交互并用每一时刻的回报作为长期回报的估计$\sum_{t’=t}^{T} \gamma^{t’-t}r_{t’}$ 会产生较大的方差，Variance较大。
而通过基于优势函数的AC方法来进行回报值估计，则会产生方差较小，而Bias较大的问题。

GAE 推导
满足$\gamma$-just条件。(未完待续)

GAE形式
GAE的形式为多个价值估计的加权平均数。
运用GAE公式进行优势函数的估计：

​ 为了快速估计序列中所有时刻的估计值，采用倒序计算，从t+1时刻估计t时刻：

五、PPO关于策略梯度的目标函数以上所述的策略梯度算法属于on-policy的算法，而PPO属于off-policy的算法

on-policy: 使用当前策略$\pi_\theta$收集数据，当参数$\theta$更新后，必须重新采样。

off-policy: 可以从可重用的样本数据中获取样本来训练当前的策略$\pi _\theta​$，下式用了重要性采样。

1. PPO目标函数
   对于PPO而言，轨迹回报通过采用Advantage function的方式进行估计，因而其梯度更新方式为：
   ​ 其中，从第二个等式用的是重要性采样，第三到第四个约等式由于$\frac{p_\theta(s_t)}{p_\theta^\prime(s_t)}​$这一项来源于重要性采样，前提假设两个分布差别不大，近似为1，且不易计算，故省略，后面的$\nabla \log p_\theta({a_t^n|s_t^n})​$ ,根据公式$\nabla f(x) = f(x) \nabla \log f(x)​$转换。
   ​ 因而，定义目标函数为：
2. PPO对于重要性采样约束的处理
   ​ 为了保证$p_\theta(s_t,a_t) ​$ 与 $p_\theta^\prime(s_t,a_t)​$ 分布的差别不会太大，采用以下约束：

TRPO： 使用约束 $KL(\theta,\theta’)<\delta$，在分布上进行约束。
PPO1(Adaptive KL)：使用$J_{PPO}^{\theta’}(\theta)=J^{\theta’}(\theta)-\beta KL(\theta,\theta’)$，在目标函数上加一个正则项进行约束，注意，这里KL散度衡量的是action之间的距离，而不是参数$\theta$与$\theta’$之间的距离。
PPO2 (Clip，论文中推荐的)：使用$J_{PPO_2}^{\theta’}(\theta)=\sum_{(s_t,a_t)}\min{([\frac{p_\theta(a_t|s_t)}{p_\theta^\prime(a_t|s_t)}A^{\theta^\prime}(s_t,a_t)], [clip(\frac{p_\theta(a_t|s_t)}{p_\theta^\prime(a_t|s_t)},1-\epsilon,1+\epsilon)A^{\theta^\prime}(s_t,a_t)])}​$, 来约束分布距离。

使用GAE对优势函数进行优化

六、 PPO的目标函数PPO的最终目标函数由三部分组成，可使用梯度下降求解，而不是像TRPO一样使用共轭梯度法：

策略梯度目标函数： $L_t^{CLIP}(\theta)​$
值函数目标函数：$L_t^{VF}(\theta)=(V_\theta(s_t)-V_t^{target})^2=((r+\gamma v(s_{t+1}))-v(s_t))^2$
策略模型的熵: $S_{[\pi_\theta]}(s_t)=-\pi_\theta(a|s)\log\pi_\theta(a|s)​$

完整的形式如下：
这部分相应的代码如下：

七、Actor-CriticA2C、A3C等方法采用的是TD方法来替代R-b部分

A3C

方法:

启动N个线程，Agent在N线程中同时进行环境交互收集样本；
收集完样本后，每一个线程将独立完成训练并得到参数更新量，异步更新到全局的模型参数中；
下一次训练的时候，线程的模型参数将与全局参数完成同步，使用新的参数进行下一次训练。

目标函数:
使用TD-$\lambda$减小TD带来的偏差，可以在训练早期更快的提升价值模型。为了增加模型的探索性，目标函数中引入了策略的熵。

A2C
与A3C不同的是参数更新全部在全局master完成，每个子线程只负责env.step()进行探索。

参考

一、 基本概念
符号定义
$D$ 判别模型， $G$ 生成模型
$x​$ 数据集中的数据分布，$z​$ 某种随机分布

目标函数（详细参见第四部分）(找一系列D让其对应的V最大，然后在这些最大的V里面选一个最小的)

D Loss (MC采样，相当于训练二分类器$x \sim P_{data}$一类，$\hat{x} \sim G(z)$一类):

G Loss原始 （MiniMax GAN[MMGAN]）(判别器越好，生成器梯度消失越严重)

G Loss改进 (Non-saturating GAN[NSGAN] )(-log trick) (其实与原始的差别不大)

释义
$G$的目标是最大化生成数据与数据集数据的似然，减小生成数据与数据集数据之间的差距（原始GAN就是JSD）。对于生成器$ G $来说，为了尽可能欺骗$ D$，所以需要最大化生成样本的判别概率 $D(G(z))$，即最小化$ log(1-D(G(z)))$，注意：$log(D(x)) $一项与生成器$ G $无关，所以可以忽略。
$D$要解决的问题是一个二分类问题，$V(D,G)$ 为二分类问题中常见的交叉熵损失。

二、 原理推导
参考:

​ 真实数据的分布$ P_{data}(x)$，$x$ 是一个真实数据，是一个向量，这个向量集合的分布就是 $P_{data}$。我们需要生成一些也在这个分布内的数据，如果直接就是这个分布的话，怕是做不到的。
​ 现有的 Generator 生成的分布可以假设为 $P_G(x;θ)$，这是一个由 $ θ $ 控制的分布，$θ$ 是这个分布的参数（如果是高斯混合模型，那么 $ θ$ 就是每个高斯分布的均值和方差) 。
​ 假设我们在真实分布中取出一些数据，${x_1, x_2, … , x_m}$，我们想要计算一个似然 $P_G(x_i; θ)$。
​ 对于这些数据，在生成模型中的似然就是

GAN原理
最大化上面这个似然，等价于让 Generator 生成那些真实数据分布的概率最大。这就变成了一个最大似然估计的问题了，我们需要找到一个 $θ^*$ 来最大化这个似然。(倒数第三行减掉的$P_{data}$项是为了凑KL，其不包含G的参数相关项，没有影响单调性。)

固定$G$,求一个最优的$D^​$
那么转为优化$f(D) = P_{data}(x)\log D(x)+P_G(x)\log(1-D(x))$
对$f(D)$求偏导:
可以解得:
对于一个给定的 x，得到最优的 D 如上图，范围在 (0,1) 内，把最优的 $D^{} ​$ 带入V
所以最终(V(G,D)可以看成是JSD)
表示两个分布之间的差异，最小值是$ -2log2​$，最大值为 $0​$。观察上式，当 $P_G(x)=P_{data}(x)​$ 时，G 是最优的。

三、GAN的训练有了上面推导的基础之后，我们就可以开始训练 GAN 了。结合我们开头说的，两个网络交替训练，我们可以在起初有一个 $G_0$ 和 $D_0$，先用Gradient Ascent训练 $D_0$ 找到 ：

然后固定 $D_0​$ 开始训练 $G_0​$， 训练的过程都可以使用 gradient descent，以此类推，训练 $D_1,G_1,D_2,G_2,…​$
但是这里有个问题就是，你可能在 $D_0^*​$ 的位置取到了：

然后更新 $G_0$ 为 $G_1​$，可能会出现：

但是并不保证会出现一个新的点$ D_1^*$ 使得：

这样更新 $G$ 就没达到它原来应该要的效果，如下图所示(G变化太大导致的JS值不稳定)：

避免上述情况的方法就是更新 $G ​$的时候，不要更新 $G ​$太多。
知道了网络的训练顺序，我们还需要设定两个 loss function，一个是$ D$ 的 loss，一个是 $G$ 的 loss。下面是整个 GAN 的训练具体步骤：

​ 适当多练D，少练G以免G的变化过大，导致JS大小不稳定，在原始GAN中，D也不要练太多，原始GAN的D是一个二分类器，用sigmoid激活，如果练的太多，导致分布很难继续拟合，形象的说就是土推不动，这块儿可以用 Least square GAN来解决，参见下面这张图(来自李宏毅老师的教程。

四、存在的问题
G的Loss function收敛速度问题：
$G​$ 的 loss function $\mathbb{E}{_{x\sim P_g}}[log(1-D(x))]​$ 还是有一点小问题，下图是两个函数的图像：

​ [问题原因] $log(1-D(x)) $是我们计算时 G 的 loss function，但是我们发现，在$ D(x) $接近于 0 的时候，这个函数十分平滑，梯度非常的小。这就会导致，在训练的初期，$G $想要骗过 $D$，变化十分的缓慢，而上面的函数，趋势和下面的是一样的，都是递减的。但是它的优势是在 $D(x) $接近 0 的时候，梯度很大，有利于训练，在 $D(x) $越来越大之后，梯度减小，这也很符合实际，在初期应该训练速度更快，到后期速度减慢。
​ [解决方案] 所以我们把$ G$ 的 loss function 修改为:

Loss 没有变化，一直都是平的
[问题] 此时$max_DV(G,D)=0$, $JS=log2$, $P_G$和$P_{data}$由于$D$过拟合导致完全没有交集，但是实际上两个分布是有交集的，造成这个的原因是因为，我们无法真正计算期望和积分，只能使用 sample 的方法，如果训练的过拟合了，D 还是能够完全把两部分的点分开:

[问题原因] 对于这个问题，我们是否应该让 $D$变得弱一点，减弱它的分类能力，但是从理论上讲，为了让它能够有效的区分真假图片，我们又希望它能够，所以这里就产生了矛盾。
还有可能的原因是，虽然两个分布都是高维的，但是两个分布都十分的窄，可能交集相当小，这样也会导致 JS divergence 算出来为$log2$，约等于没有交集。
[解决方案] 解决的一些方法，有添加噪声，让两个分布变得更宽，可能可以增大它们的交集，这样 JS divergence 就可以计算，但是随着时间变化，噪声需要逐渐变小，换一种距离计算方法比如使用Wasserstein

Mode Collapse
Mode collapse的出现应该可以说是必然的，其通过不同的散度进行拟合，最优的情况很可能就是出现在某一个密度较高的分布峰上。结局mode collapse的方法可以使用ensemble的方式，我这边还尝试过先聚类后gan的方式。

参考:

Hybrid A* 的使用场景​ 在斯坦福大学2007年参加的DARPA无人车城市挑战赛时使用的Junior，其在行为规划层提出了分层有限状态机的方式，如下图所示。

​ 其中，BAD_RNDF状态表示的是，当前道路与系统的路网图不同的时候，无人车将采用Hybrid A*来进行规划路径。

Hybrid A 与 AHybrid A* 的主要特点是：

考虑物体的实际运动方向约束，不像A假定所有的相邻节点都可以顺利转移
A 的物体总是出现在栅格中心，而 Hybrid A 则不一定
Hybrid A 是连续路径
Hybrid A 基于A

算法流程:主要流程如下图所示，需要说明的是：
​ 算法考虑了车辆的x,y坐标，偏航角。

G值更新策略如下：

H值更新策略如下：
可以支持倒车时计算当前节点到终点的，仅支持前向行驶时计算Dubins曲线；
H值为Reeds-Shepp曲线、Dubins曲线、曼哈顿距离三种cost解算出来的最大值。

代码参考：

Rviz实验效果

参考：

RNN正向传播推导RNN原理图：

变量说明
$W,U,V​$为权重矩阵，在整个RNN网络中是共享的。
$h^t​$代表在序列$t​$时模型的隐藏状态。$h^t​$由$x^t​$和$h^{t-1}​$共同决定。
$o^{t}$代表在序列$t$时模型的输出。$o^t$只由模型当前的隐藏状态$h^{t}$决定。
$x^t$代表在序列$t$时训练样本的输入。
$L_t​$代表在序列$t​$时模型的损失函数。
$y^t$代表在序列$t​$时训练样本序列的真实输出。

前向公式

RNN反向传播推导
$L$对$C$的梯度：

$L$ 对V的梯度：

$L$ 对$h^t$的梯度：

​ 其中：
​ (1)
​ (2)
​ 详细推导：

$L​$ 对$W​$的梯度：

$L$ 对$B$的梯度：

$L$ 对$U$的梯度：

参考文献：

一、参数初始化参数初始化的作用：

目的是为了让神经网络在训练过程中学习到有用的信息
参数梯度不应该全部为0

各层激活值不会出现饱和现象
各层激活值不为0

1.1 标准初始化方法
特点：

隐层的状态的均值为0，方差为常量$\frac{1}{3}$，和网络的层数无关
标准初始化只适用于满足Glorot假设的激活函数，比如tanh。

推导：
符合输入参数的均匀分布，$n$是输入层神经元个数。

​ 权重值的方差为（均匀分布 $D(x)=(b-a)²/12$）:
​ 现在把输入$X$的每一维度$x$看做一个随机变量，并且假设$E(x)=0$, $Var(x)=1$。假设$w$和$x$相互独立，则隐层状态的方差为 :
​ 可以看出标准初始化方法得到一个非常好的特性：隐层的状态的均值为0，方差为常量$\frac{1}{3}$，和网络的层数无关，这意味着对于sigmoid函数来说，自变量落在有梯度的范围内。
1.2 Glorot条件上述参数梯度不应该全部为0的条件只能保证网络能学到东西，而Glorot认为，优秀的初始化应该使得各层的激活值和状态梯度的方差在传播过程中的方差保持一致。

条件：
输入假设
输入的每个特征方差一样：Var(x)

激活函数假设：
激活函数$f(x)$对称：这样就可以假设每层的输入均值都是0
$f\prime(0)=1$
初始时，状态值落在激活函数的线性区域：$f\prime(s_k^i)\approx 1$

符合该条件的特征：
激活值方差和层数相关，反向传播的梯度方差和层数是有关系的，而参数梯度的方差和层数无关
相关推导过程:

1.3 Xavier初始化为了保证前向传播和反向传播时每一层的方差一致，可以将Glorot条件转换成($n_i$为第$i$层的神经元个数)：
输入与输出的个数往往不相等，于是为了均衡考量，根据由Glorot条件，得到方差设定符合：
该方差对应的均匀分布即为Xavier初始化分布：

特点:
激活值的方差和层数无关，反向传播梯度的方差和层数无关

二、正则化正则化的目的是对网络参数进行惩罚，特别是阶数较高项$x^n$ $ (网络表达式： w_1x^n+w_2x^{n-1}+…+w_n)$的系数参数，因为如果该项系数较大，是的拟合曲线复杂，会导致网络过拟合。引入正则化，则不会因为$x$的较小变动导致输出的较大变化，对噪声的容忍程度比较好。
没有正则化：($\eta$是学习率)
2.1 L1正则 （带有特征选择能力）$C$是正则化后的损失函数，$C_0$是正则化前的损失函数。
那么权重更新为：

L1正则的作用是使$w​$在每一次迭代时都变化一个常数：$\frac{\eta\lambda}{n}​$。

当$w​$本身比较小时，L1正则比L2正则衰减得更厉害。L1正则的效果是使不重要的$w​$几乎衰减为0。

因而L1具有一定的稀疏性，并有一定的特征选择的功能。

2.2 L2正则 (与权重衰减不完全等价)$C_0$是正则化之前的损失函数，$λ$是正则项系数，$n$是参数$w$的个数。最小化损失函数$C$的同时也会使$\sum_{i=1}^n{w_i^2}​$尽可能小。
加上正则项后梯度变为:

L2正则项的作用是使$w$在每次迭代时都变小了$\frac{\eta\lambda}{n}$倍。
如果要使这个倍率不变，那么当神经元个数增多（即$n$变大）时，正则项系数$λ$也应该相应调大。

2.3 L2 正则 vs 权值衰减​ L2正则化是在目标函数中直接加上一个正则项，直接修改了我们的优化目标。
​ 权值衰减是在训练的每一步结束的时候，对网络中的参数值直接裁剪一定的比例，优化目标的式子是不变的。
​ 在使用朴素的梯度下降法时二者是同一个东西，因为此时L2正则化的正则项对梯度的影响就是每次使得权值衰减一定的比例。
​ 但是在使用一些其他优化方法的时候，就不一样了。比如说使用Adam方法时，每个参数的学习率会随着时间变化。这时如果使用L2正则化，正则项的效果也会随之变化；而如果使用权值衰减，那就与当前的学习率无关了，每次衰减的比例是固定的。