1. 有模型数值迭代
1.1 主要思想
有模型数值迭代主要利用动态规划（Dynamic Programming，DP）的思想。
动态规划迭代算法运用了自益的思想。但在实际问题中，直接使用动态规划算法常出现困难，从下面的状态动作价值迭代可以看出，实际问题的状态空间非常大，仅仅是扫描一遍所有的状态都是不可能的事情。
$$
q_{pi}(s_t,a_t)=r(s_t,a_t)+\gamma \sum_{s’}p(s’|s_t,a_t)v_{\pi}(s’)
$$
自益：用一个估计值来估计另外一个估计值
方法改进：异步动态规划
异步动态规划的思想是，每次扫描不再完整的更新一整套状态价值函数，而只是部分更新感兴趣的值。例如，有的状态s不会转移到另一些状态（$p(s’|s,a)=0$$的状态$$s’$）
1.2 理论基础
理论基础：度量空间上的Banach不动点定理
之所以是有模型的价值迭代，是因为我们知道其动力系统$p(s’|s,a)$，即转移概率，这样我们就可以从从一个确定性策略出发，经过不断策略评估，策略改进……最后收敛到最优策略。背后的数学证明就是度量空间上的Banach不动点定理。
DP的特点
- 利用bootstraping自益的思想
- 没有利用异步动态规划的方法，每次迭代需要更新所有的状态
2. 无模型的数值迭代
2.1 Monte Carlo(MC)
基本思想：利用MC估计期望值$V_{\pi}(s)$和$Q_{\pi}(s,a)$
举例：对于一个具体的策略$\pi$来说，利用这个策略玩n个回合
$S_0^1=s,A_0^1=a,R_1^1,S_1^1,A_1^1,R_2^1…… \qquad G^1$
$S_0^2=s,A_0^2=a,R_1^2,S_1^2,A_1^2,R_2^2…… \qquad G^2$
$……$
$S_0^n,A_0^n,R_1^n,S_1^n,A_1^n,R_2^n…… \qquad G^n$
利用Monte Carlo来估计价值函数$V_{\pi}(s)=\frac{1}{k}(G^1+G^2+……)$，从相同状态s出发的回合累计回报平均值。$Q_{\pi}(s,a)=\frac{1}{k}(G^1+G^2+……)$，从相同状态动作对出发的回合累计回报平均值。
利用Monte Carlo进行更新，实际应用中又分为每次访问回合更新和首次访问回合更新
MC的特点
- 没有利用自益的思想
- 利用经验平均回报的方法来估计
- 局限：只能用在有终止的MDP，每一步的R 都是一个变量，累积后的G方差较大。
- 每个回合只需要更新一条该回合轨迹上的状态
2.2 Temporal Difference(TD)
2.2.1 TD(n)
对于状态价值来说，n步时序差分$TD(n)$目标为：
$U_{t:t+n}^{(v)}=R_{t+1}+\gamma R_{t+2}+…+\gamma ^nq(S_{t+n},A_{t+n})$
对于动作状态价值来说，将上图的白圆和黑圆互换。以TD(0)为例，更新动作状态价值可以表示为
$$
U_t=R_{t+1}+\gamma q(S_{t+1},A_{t+1}) \
q(S_t,A_t)\gets q(S_t,A_t)+\alpha[U_t-q(S_t,A_t)]
$$
从上式可以看出，TD(n)是利用了自益的思想。
对于时序差分来说
$$
q_{target}(S_t,A_t)=E[R_{t+1}+ q(S_{t+1},A_{t+1}]
$$
在实际应用中我们用
$$
U_t=R_{t+1}+\gamma q(S_{t+1},A_{t+1})\approx q_{target}(S_t,A_t)
$$
2.2.2 SARSA
单步SARSA：单步时序差分目标（策略评估） + 策略改进
多步SARSA：多步时序差分目标（策略评估） + 策略改进
期望SARSA：$U_t=R_{t+1}+\gamma \sum_{a\in \mathcal{A}}\pi(a|S_{t+1})q(S_{t+1},a)$ 也有单步和多步
TD的特点：
- 可以从不完整的轨迹中学习
- 介于MC和DP之间的方法
- 有sampling（期望的近似）和bootstraping
- 方差较于MC更小
- 可以在线学习，每走一步就更新