1 基本概念
return：trajectory上的reward之和（discounted） discount rate：reward的折现率
episode：可到达终点的 trajectory，也叫 trial episodic task：有限步的task，continuing task：无限步的task
decision (即policy) 确定后，Markov decision process 变为 Markov process
2 Bellman公式
这里用
state-value是对所有trajectory的return的平均值
Bellman公式描述了不同状态的state-value之间的关系。
每个状态一个bellman公式
dynamic model 即 环境模型
最终是为了最优策略
给定policy后，求解state values就是policy评估
用迭代法求解
3 Bellman最优公式
证明BOE需要收缩映射定理：
重要的是reward的相对值，而不是绝对值
4
值迭代
值更新对
Matrix-vector形式用于理论分析，Elementwise形式用于实现
给定最优策略，直接就能求值
策略迭代
策略迭代是蒙特卡洛法的基础
*给定一个策略，迭代求
迭代求
截断的策略迭代
为作比较，假设值迭代的初始值
VI和PI是TPI的特例
迭代求
5 蒙特卡洛法
model-free是基于采样的
MC Exploring Starts
计算
visit是对episode而言的
first-visit：比如对original episode，只计算第一个出现的
拿到一个 episode 就更新 action value
通用策略迭代GPI：策略评估和改进交替进行，策略评估有些许改进就行
- g初始表示第t步之后的return
是个集合，存放所有episode的从 开始的return
MC ε-greedy
soft policy：采取任何行动的概率都不为0
近似ε概率去探索
用every-visit
6 随机近似
随机近似是时序差分法的基础
SA：Stochastic Approximation
RM算法
条件2)：
实践中
均值估算法是RM算法的特例
SGD：随机梯度下降
SGD的收敛分析
现将SGD变换为RM算法的形式
然后让SGD满足RM算法的收敛性要求
- 当迭代值
距离最优值 很远时，SGD呈现的行为类似GD - 当迭代值
距离最优值 较近时，SGD呈现出较大的随机性
BatchGD是全量，MiniBatchGD是有放回抽样
注：神经网络训练时的mini-batch是无放回抽样
7 时序差分
TD learning
给定策略，估计出state值
在model-free情况下计算bellman公式
用采样替代最优策略的值
TD是有偏估计（自举），但方差小
Sarsa
给定策略，估计出action值
Expected Sarsa
n-steps Sarsa
Sarsa、n-steps Sarsa、MC 仅仅是 TD-target (即
Q-learning
估计出 最优action值
off-policy vs. on-policy
异策略 vs. 同策略
q-learning只比sarsa多一个
为什么更新目标策略用greedy，不用ε-greedy？ 因为目标策略不再需要作为行为策略去探索。
8 值函数近似
用函数近似表格，如：价值函数表格
平稳分布
用采样代替期望
TD learning + 函数近似
Sarsa + 函数近似
Q-learning + 函数近似
DQN: Deep Q-learning
用神经网络作为非线性函数逼近器
main network用mini-batch数据更新，target network隔一段时间复制main network参数
在mini-batch上最小化目标函数J
9 策略梯度
策略函数近似 用函数近似表格，如 (state, action) -> π(state, action)
用梯度上升法最大化
REINFORCE
实践中不会等d变为平稳分布再采样S
Value update: 蒙特卡洛法
10 Actor-Critic法
QAC
value update: TD + 值函数近似
A2C
用
off-policy AC
与前面 on-policy policy gradient 的公式比较：
A的分布从
对比确定性AC（DPG）
式中
value update: TD + 值函数近似
