知识四：强化学习-无模型强化学习
4.1 介绍
-
Model-free方法
- 蒙特卡罗学习（A方法）
- 时序差分学习（B方法）
- TD（ λ \lambda λ）（A+B混合）、
-
为了评估和优化一个未知 MDP 价值函数
4.2 蒙特卡罗强化学习
- MC方法可直接从分幕（游戏回和，可能是一个游戏回合）的经验中学习
- MC是无模型的算法：不需要了解状态转移矩阵/奖励
- MC要求需要完整的episodes（回合）中学习（不是用在不能结束的游戏上）
- MC使用最简单的思想：价值（value）= 平均回报（mean return），一个状态的价值，就是在这个状态行不断重复的进行游戏，最后取平均就是这个状态的价值。
4.2.1 MC策略评估
- 目标：在给定策略 π \pi π下，从一系列的episodes经验中学习价值函数 v π v_\pi vπ。
- MC策略评估使用每个状态的平均回报，来代替期望的回报。（很多次回报的平均值作为对应状态的价值。）
4.2.2 首次访问型MC策略评估
-
目标：评估状态 s s s,就是计算状态 s s s的价值。
-
每幕中，状态 s s s 第一次出现进行如下操作
- 增加计数个数 N ( s ) ← N ( s ) + 1 N(s)\leftarrow N(s)+1 N(s)←N(s)+1
- 增加回报总和 S ( s ) ← S ( s ) + G t S(s)\leftarrow S(s)+G_t S(s)←S(s)+Gt
- 价值由平均回报估算 V ( s ) = S ( s ) / N ( s ) V(s)=S(s)/N(s) V(s)=S(s)/N(s)
-
根据大数定律：$V(s)\to V_\pi(s) as N(s)\to\infty $
-
如下图所示只计算第一次出现的状态的价值，蓝色框的回报不进行计算，只计算第一次出现的状态的回报。
4.2.3 每次访问型MC策略评估
- 目标：评估状态 s s s,就是计算状态 s s s的价值。
- 每幕中，状态
s
s
s 每次出现一次进行如下操作
- 增加计数个数 N ( s ) ← N ( s ) + 1 N(s)\leftarrow N(s)+1 N(s)←N(s)+1
- 增加回报总和 S ( s ) ← S ( s ) + G t S(s)\leftarrow S(s)+G_t S(s)←S(s)+Gt
- 价值由平均回报估算 V ( s ) = S ( s ) / N ( s ) V(s)=S(s)/N(s) V(s)=S(s)/N(s)
- 根据大数定律： V ( s ) → V π ( s ) a s N ( s ) → ∞ V(s)\to V_\pi(s) as N(s)\to\infty V(s)→Vπ(s)asN(s)→∞
- 如下图所示，每一个回和，把要评估状态的所有回报全都要计算，最后求平均，如下图所示，所有的红色和蓝色框的回报都要算出来。
4.2.4 累进式均值更新
-
只存储当前的回报和进行了多少轮，就行了，不用记以前的回报。
-
只要知道，上一次的价值函数（也就是均值），和这一次的回报就行了。如下所示：
μ k = 1 k ∑ j = 1 k x j = 1 k ( x k + ∑ j = 1 k − 1 x j ) = 1 k ( x k + ( k − 1 ) μ k − 1 ) = μ k − 1 + 1 k ( x k − μ k − 1 ) \begin{aligned} \mu_{k}& =\frac1k\sum_{j=1}^kx_j \\ &=\frac1k\left(x_k+\sum_{j=1}^{k-1}x_j\right) \\ &=\frac1k\left(x_k+(k-1)\mu_{k-1}\right) \\ &=\mu_{k-1}+\frac{1}{k}\left(x_{k}-\mu_{k-1}\right) \end{aligned} μk=k1j=1∑kxj=k1(xk+j=1∑k−1xj)=k1(xk+(k−1)μk−1)=μk−1+k1(xk−μk−1)
4.2.5 累进式蒙特卡罗更新
- 对于每个具有回报 G t G_t Gt的状态 S t S_t St，公式如下：
N ( S t ) ← N ( S t ) + 1 V ( S t ) ← V ( S t ) + 1 N ( S t ) ( G t − V ( S t ) ) \begin{aligned}&N(S_{t})\leftarrow N(S_{t})+1\\&V(S_{t})\leftarrow V(S_{t})+\frac{1}{N(S_{t})}(G_{t}-V(S_{t}))\end{aligned} N(St)←N(St)+1V(St)←V(St)+N(St)1(Gt−V(St))
- 在非平稳问题中（环境也在变），跟踪连续平均值（即忘掉旧幕）
V ( S t ) ← V ( S t ) + α ( G t − V ( S t ) ) V(S_t)\leftarrow V(S_t)+\alpha\left(G_t-V(S_t)\right) V(St)←V(St)+α(Gt−V(St))
- 就最近的几次的起作用，远的就不起作用了。
4.3 时序差分学习（TD）
- 现在很多的方法都是基于TD的思想来做的。（很少用MC的，因为MC每次游戏都要打完不好）
- TD方法直接从经验中学习
- TD是无模型的：不需要了解 MDP 转移矩阵/奖励
- TD通过自举，从不完全的幕中学习
- 自举的意思就是用猜测的结果去更新猜测。
- 注：在很多复杂的情况下，不是严格的MDP的时候，收敛性都无法证明。这也是强化学习遇到的问题之一。
4.3.1 MC和TD
-
目标：根据策略 π \pi π得到的经验学习价值函数 v π v_\pi vπ
-
增量式every-visit MC
- 朝着实际回报 G t G_t Gt的方向更新价值 V ( S t ) V(S_t) V(St)
V ( S t ) ← V ( S t ) + α ( G t − V ( S t ) ) V(S_t)\leftarrow V(S_t)+\alpha\left(G_t-V(S_t)\right) V(St)←V(St)+α(Gt−V(St))
-
最简单的时序差分算法：TD（0）
- 朝着估计回报 R t + 1 + γ V ( S t + 1 ) R_{t+1}+\gamma V(S_{t+1}) Rt+1+γV(St+1)的方向更新价值 V ( S t ) V(S_t) V(St)
V ( S t ) ← V ( S t ) + α ( R t + 1 + γ V ( S t + 1 ) − V ( S t ) ) V(S_t)\leftarrow V(S_t)+\alpha\left(R_{t+1}+\gamma V(S_{t+1})-V(S_t)\right) V(St)←V(St)+α(Rt+1+γV(St+1)−V(St))
- R t + 1 + γ V ( S t + 1 ) R_{t+1}+\gamma V(S_{t+1}) Rt+1+γV(St+1)被称为TD target
- δ t = R t + 1 + γ V ( S t + 1 ) − V ( S t ) \delta_{t}=R_{t+1}+\gamma V(S_{t+1})-V(S_{t}) δt=Rt+1+γV(St+1)−V(St)被称为TD error
-
用下一个状态预测的状态价值＋动作奖励作为目标。然后去预测新的状态价值。（也就是用估计的价值去更新估计价值）依赖于下一个状态的价值，也就是依赖于下一个动作（注，他也依赖于转移概率）
-
算TD的时候其实隐含了计算状态转移矩阵。
4.3.2 MC和TD的优点缺点
- TD可以在知道最终结果之前学习
- TD可以在每一步之后在线学习
- MC必须等到episode结束才能知道回报
- TD可以在没有最终结果的情况下学习
- TD可以从不完整的序列中学习
- MC只能从完整序列中学习
- TD在连续（非终止）环境中工作
- MC仅适用于episode（终止）环境
4.3.3 偏差和方差的平衡
- 回报 G t = R t + 1 + γ R t + 2 + ⋯ + γ T − 1 R t + 2 G_{t}=R_{t+1}+\gamma R_{t+2}+\cdots+\gamma^{T-1}R^{t+2} Gt=Rt+1+γRt+2+⋯+γT−1Rt+2 是 v π ( S t ) v_{\pi}(S_{t}) vπ(St)的无偏估计
- 真实的TD target R t + 1 + γ v π ( S t + 1 ) R_{t+1}+\gamma v_{\pi}(S_{t+1}) Rt+1+γvπ(St+1)是 v π ( S t ) v_{\pi}(S_{t}) vπ(St)的无偏估计
- TD target R t + 1 + γ V ( S t + 1 ) R_{t+1}+\gamma V(S_{t+1}) Rt+1+γV(St+1)是 v π ( S t ) v_{\pi}(S_{t}) vπ(St)的有偏估计
- TD target
R
t
+
1
+
γ
V
(
S
t
+
1
)
R_{t+1}+\gamma V(S_{t+1})
Rt+1+γV(St+1)的方差比回报
G
t
G_{t}
Gt 低得多
- 回报取决于一序列随机的动作、转移与奖励
- TD target取决于一个动作及其对应的转移与奖励
4.3.4 MC和TD的优点缺点（2）
- MC具有高方差，零偏差
- 良好的收敛性
- 对初始值不太敏感
- 很容易理解和使用
- TD方差低，但存在偏差
- 通常比MC更高效，收敛更快
- TD(0)收敛至 v π ( S t ) v_{\pi}(S_{t}) vπ(St)
- 对初始值更敏感
4.3.5 Batch MC and TD
- 在线是遍迭代遍评估，离线是都打完之后，一起读数据。
- MC和TD收敛： : V ( s ) → V π ( s ) : V(s)\to V_{\pi} (s) :V(s)→Vπ(s)当 e x p e r i e n c e → ∞ experience\to\infty experience→∞
- 但是对于有限经验比如 K K K条经验，如何计算呢?
s 1 1 , a 1 1 , r 2 1 , . . . , s T 1 1 ⋮ s 1 K , a 1 K , r 2 K , . . . , s T K K \begin{array}{c}s_1^1,a_1^1,r_2^1,...,s_{T_1}^1\\\vdots\\s_1^K,a_1^K,r_2^K,...,s_{T_K}^K\end{array} s11,a11,r21,...,sT11⋮s1K,a1K,r2K,...,sTKK
- 重复采样episode k ∈ [ 1 , K ] k\in[1,K] k∈[1,K]
- 对episode 应用MC和TD(0)
4.3.6 MC和TD的优点缺点（3）
- TD利用了马尔可夫性
- 通常在马尔可夫环境中效率更高
- MC没有利用马尔科夫性
- 通常在非马尔可夫环境中更有效
4.3.7 MC，TD，DP的比较
-
Bootstrapping：更新涉及估计
-
MC不自举（采样完了，和深度优先一样）
-
DP自举
-
TD自举
-
-
Sampling：更新采样
- MC采样
- DP不采样
- TD采样
4.3 TD( λ \lambda λ)
4.3.1 n步TD
- 让TD target 看更多步未来的状态
- 考虑n步回报，其中$n=1,2,\infty $：
n = 1 ( T D ) G t ( 1 ) = R t + 1 + γ V ( S t + 1 ) n = 2 G t ( 2 ) = R t + 1 + γ R t + 2 + γ 2 V ( S t + 2 ) n = ∞ ( M C ) G t ( ∞ ) = R t + 1 + γ R t + 2 + . . . + γ T − 1 R T \begin{aligned}&n=1\quad(TD)\quad G_t^{(1)}=R_{t+1}+\gamma V(S_{t+1})\\&n=2\quad G_t^{(2)}=R_{t+1}+\gamma R_{t+2}+\gamma^2V(S_{t+2})\\&n=\infty\quad(MC)\quad G_t^{(\infty)}=R_{t+1}+\gamma R_{t+2}+...+\gamma^{T-1}R_T\end{aligned} n=1(TD)Gt(1)=Rt+1+γV(St+1)n=2Gt(2)=Rt+1+γRt+2+γ2V(St+2)n=∞(MC)Gt(∞)=Rt+1+γRt+2+...+γT−1RT
- 定义n步回报为：
G t ( n ) = R t + 1 + γ R t + 2 + . . . + γ n − 1 R t + n + γ n V ( S t + n ) G_t^{(n)}=R_{t+1}+\gamma R_{t+2}+...+\gamma^{n-1}R_{t+n}+\gamma^nV(S_{t+n}) Gt(n)=Rt+1+γRt+2+...+γn−1Rt+n+γnV(St+n)
- n步时序差分算法：
V ( S t ) ← V ( S t ) + α ( G t ( n ) − V ( S t ) ) V(S_t)\leftarrow V(S_t)+\alpha\left(G_t^{(n)}-V(S_t)\right) V(St)←V(St)+α(Gt(n)−V(St))
4.3.2 TD( λ \lambda λ)
-
$G_t^\lambda 整合了所有的 n 步回报 整合了所有的n步回报 整合了所有的n步回报G_t^{(n)}$
-
加和时，使用权重 ( 1 − λ ) λ n − 1 (1-\lambda)\lambda^{n-1} (1−λ)λn−1
G t λ = ( 1 − λ ) ∑ n = 1 ∞ λ n − 1 G t ( n ) G_{t}^{\lambda}=(1-\lambda)\sum_{n=1}^{\infty}\lambda^{n-1}G_{t}^{(n)} Gtλ=(1−λ)n=1∑∞λn−1Gt(n)
- 得到TD( λ \lambda λ)
V ( S t ) ← V ( S t ) + α ( G t λ − V ( S t ) ) V(S_{t})\leftarrow V(S_{t})+\alpha\left(G_{t}^{\lambda}-V(S_{t})\right) V(St)←V(St)+α(Gtλ−V(St))
G t λ = ( 1 − λ ) ∑ n = 1 ∞ λ n − 1 G t ( n ) G_{t}^{\lambda}=(1-\lambda)\sum_{n=1}^{\infty}\lambda^{n-1}G_{t}^{(n)} Gtλ=(1−λ)n=1∑∞λn−1Gt(n)
- 得到TD( λ \lambda λ)
V ( S t ) ← V ( S t ) + α ( G t λ − V ( S t ) ) V(S_{t})\leftarrow V(S_{t})+\alpha\left(G_{t}^{\lambda}-V(S_{t})\right) V(St)←V(St)+α(Gtλ−V(St))
标签：Rt,Gt,MC,模型,知识,St,TD,强化,gamma From： https://blog.csdn.net/pengyunfenn/article/details/142819679