强化学习理论与实践（学长授课）

第一课：

问题是和后续状态无关的，不考虑状态
多步就变成了强化学习问题
智能体是强化学习需要优化的部分，可控
环境不能直接控制
定义奖励的方式要和目标一致
回报值： $w_{t+n} = \gamma^n$
当 $\gamma$ = 0时,退化成了问题
当 $\gamma$ = 1时,变成无衰减回报值
当 $\gamma \in (0,1)$ 时， $\gamma$ 值衡量了我们对未来奖励的关注度，越大表示关注长期奖励，越小表示关注短期奖励。 $\gamma$ 表示衰减系数。
全观测和部分观测，不做特殊申明，环境指全观测环境。
部分观测下的马尔可夫决策问题
策略：确定性策略和随机策略
确定性策略： $a= \pi(s)$
随机策略： $\pi(a|s) = Pr(a|s)$
按智能体的环境分类：
全观测环境下的强化学习
部分观测环境下的强化学习
按照智能体的成分分类：
基于值函数：学习值函数
基于策略：学习策略
Actor Critic：同时学习值函数和策略
还有别的分类，这里就写这两个

第二课马尔可夫决策过程

马尔可夫决策过程
最优控制问题可以描述为连续MDP
部分观测环境可以转化为POMDP
问题是只有一个状态的MDP
*强化学习中从初始状态到终止状态的序列过程，被称为一个片段。
如果一个任务总是以终止状态结束，那么这个任务被称为片段任务
如果一个任务没有终止状态，那么被称为连续性任务
MRP：马尔可夫奖励过程
MDP：马尔可夫决策过程
MRP贝尔曼方程
MDP贝尔曼期望方程
MRP引入决策成为MDP

第三课动态规划

策略评价
策略提升
前面两个合起来是策略迭代
提前停止
广义策略迭代（Generalized Policy Iteration）
它包含：

策略评价
策略提升
形成了一个框架，而不限制具体评价和提升的算法。

值迭代
动态规划引申：
就地动态规划
同步更新：

$V_{new(s)} = max_{a \in A}(R(s,a) + \gamma \Sigma_{s^{'} \in S} P_{ss^{'}}^a v_{old}(s^{'}))$
异步动态规划：

$v(s) = max_{a \in A} (R(s,a) + \gamma \Sigma_{s^{'} \in S}P_{ss^{'}}^av(s^{'}))$
优先清理
使用贝尔曼误差来指导状态的选择
选误差最大的更新，每次更新完再更新受到影响状态的贝尔曼误差
然后loop，继续更新
实时动态规划

$v(S_t) = max_{a \in A} (R(S_t,a) + \gamma \Sigma_{s^{'} \in S}P_{S_ts^{'}}^av(s^{'}))$
但不保证所有状态都被遍历到，需要启发式的操作
备份
动态规划是全宽备份
强化学习是样本备份
通过采样得到转移记录，通过采样记录总体
优点：无模型方法，通过采样打破维度灾难，复杂度固定
证明方法：压缩映射
根据压缩映射定理，我们可以直接得到如下的结论：
贝尔曼期望方程收敛于唯一的 $v_{\pi}$
迭代式策略评价算法以 $\gamma$ 的线性速率收敛于 $v_{\pi}$
策略迭代收敛于 $v_{*}$
注意：
动态规划中是不需要探索的，因为动态规划本身即能考虑到所有的状态转移概率。只有当强化学习利用到采样（即智能体和环境发生交互）时，才会需要探索。

第四课无模型方法蒙特卡洛方法

无模型：没有R矩阵和P矩阵
在策略学习：
行为策略和目标策略是同一个策略
离策略学习
行为策略和目标策略不是同一个策略，需要加结合重要性采样。
目标策略是行为策略的子集
蒙特卡洛方法：
无偏，方差小
只适用于片段性任务
蒙特卡洛评价
Firt-visit MC 独立同分布，收敛性可用大数定律
evety-visit MC 收敛性比较难证明
增量MC
广义策略MC
一些理解：
蒙特卡洛方法是基于对样本回报求平均的办法来解决强化学习的问题的。为了保证能够得到良好定义的回报，这里我们定义蒙特卡洛方法仅适用于回合制任务。就是说，我们假设我们的经验被分成一个个的回合，而且对每个回合而言，不管选择什么样的动作，都会结束。只有在事件结束时，我们的价值估计和策略才会改变。蒙特卡洛方法因此能够写成逐个回合的增量形式，而不是逐步（在线）的形式。术语“蒙特卡洛”被广泛的用于任何的在操作中引入了随机成分的估计方法。这里我们使用它来表示基于平均整个回报的方法（区别于那些使用部分的回报的方法。我们将在下一章阐述）。
蒙特卡洛方法有两种：
首次蒙特卡洛方法
每次蒙特卡洛方法
蒙特卡洛要收敛，需要有两个条件：
1.回合都是探索开端的方式
2.有无限个回合可以来评估。
解决第二个假设的办法：每执行一步策略提升，就执行一步策略评估
**解决第一个假设的办法：持续探索，所以使用 $\epsilon$ -贪心策略**
一些思考
所有的控制方法都会面临这样一个两难的问题：一方面，他们需要通过最优的行为来学习动作价值；但另一方面，他们需要表现地不那么好，来探索所有的动作（来找到最优的动作）。那么，如何既能够学到最优策略，又能够在实际中多探索呢？

$\rho_{t:T-1} \doteq \frac{\prod_{k=t}^{T-1} \pi(A_k|S_k)p(S_{k+1}|S_k,A_k)} {\prod_{k=t}^{T-1} b(A_k|S_k)p(S_{k+1}|S_k,A_k)} = \prod_{k=t}^{T-1} \frac{\pi(A_k|S_k)}{b(A_k|S_k)} \tag {5.3}$
注意到上式中的轨迹的概率依赖于MDP的转移概率（常常是未知的），但是它们在分子和分母中都是相同的，能够被消掉。即是说，重要性采样率最终仅仅依赖于两个策略和序列，而与MDP无关。
原始重要性采样 无偏，但是方差大
加权重要性采样 有偏，但是方差小

第五课

大合集
时间差分策略评价：
MC用实际回报值去更新函数 $V(S_t)$ :

$V(S_t) = V(S_t) + \alpha(G_t-V(S_t))$
时间差分(Temporal difference)用奖励去更新函数 $V(S_t)$
使用估计的回报值 $R_{t+1} + \gamma V(S_{t+1})$ 去更新值函数 $V(S_t)$

$V(S_t) = V(S_t) + \alpha(R_{t+1} + \gamma V(S_{t+1}) - V(S_t))$
$\delta_t = R_{t+1} + \gamma V(S_{t+1}) - V(S_t)$ 称为TD误差
MC无偏，但是方差高，学习的过程是用来减小方差
TD有偏，但是方差小，学习的过程是为了减小偏差
MC不自举，TD自举，DP自举
MC和TD采样，DP不采样
图片说明

第六课

n步自举
就回报函数累积n步
n步SARSA学习
n步Q学习
n步离策略学习

第7课

把以来环境的模型称为planning，把不依赖环境的模型称为learning
值函数近似
函数近似器
Dyna-Q流程
Dyna-Q
Dyna-Q算法流程
我的理解是Dyna-Q是一个将无模型和有模型的方法结合的算法
backup
backup：反向更新
更有针对性地改变那些值变化明显的状态，效率会更高
prioritized sweep

第八课

Policy gradient
有两种角度去理解：似然概率角度理解，重要性采样角度理解
似然梯度理解： $\nabla_{\theta}U(\theta) \approx \frac{1}{m} \Sigma_{i=1}^{m} \nabla_{\theta} logP(\tau;\theta)R(\tau)$
$\nabla_{\theta}logP(\tau;\theta)$ 是轨迹 $\tau$ 的概率随参数\theta变化最陡的方向
沿正方向，轨迹出现的概率增大，回报值越大增加越多
沿负方向，轨迹出现的概率减小，回报值越小增加越少
引入baseline减少方差：
baseline
优势函数
A2C流程

第九课

基于表格
基于函数近似
Q learning + DNN
experience replay
target network
TD(0)不需要重要性采样的因子，所以能和Q学习完美结合
double dqn
dueling dqn：分解q函数和a函数
prioritized experience replay:不同经验权重不同
DPG高维连续策略
DDPG融合DPG以及DQN经验回放和target network

第十课

什么是rollout算法？
知道了rollout的含义，我们应该大概猜到rollout算法是一类在仿真轨迹层面上进行更新学习的方法。具体的定义如下：rollout算法是一种基于MC控制的决策时规划算法。看到决策时规划，我们知道规划是针对于当前的状态的，基于MC说明了我们是利用MC来估计当前状态或者行为的值，从而进行规划的。具体是怎么做的呢？为了估计一个给定策略的动作值函数，rollout算法利用MC采样得到很多从当前状态开始的仿真轨迹（当前状态下有多个动作，因此对于每个动作都会得到一些仿真的轨迹）。然后分别用这些轨迹回报的均值来估计每个动作的值。当这个估计值足够准确了，规划算法会执行具有最高估计值的动作。这个动作和环境交互，转移到下一个状态，再利用同样的方法规划出下一个状态的动作。重复下去，就得到了一个完整的plan。