[RL Notes] 重要度采样和离轨蒙特卡洛预测
Contents [show]
1. 基于重要度采样的离轨策略
蒙特卡洛预测算法通过计算回报的平均值来估计状态价值,即
vπ(s)≐Eπ[Gt|St=s]=average(Returns(s))
而在离轨策略中,样本是通过行动策略获得的,此时计算回报的平均值估计的是行动策略而非目标策略的状态价值。
为了在离轨策略中估计目标策略的状态价值,需要使用重要度采样比对行动策略的样本回报进行修正,这里重要度采样比 ρ 的定义为
ρ=Pr(策略 π 的轨迹)Pr(策略 b 的轨迹)
给定起始状态 St,后续的状态-动作轨迹 At,St+1,At+1,⋯,ST 在策略 π 下发生的概率为
Pr(At,St+1,At+1,⋯,ST|St,At:T−1∼π)=π(At|St)p(St+1|St,At)π(At+1|St+1)⋯p(ST|ST−1,AT−1)=T−1∏k=tπ(Ak|Sk)p(Sk+1|Sk,Ak)
其中 p 是MDP 的状态转移概率,且通常是未知的。于是可得目标策略和行动策略轨迹下的相对概率即重要度采样比为
ρt:T−1≐T−1∏k=tπ(Ak|Sk)p(Sk+1|Sk,Ak)T−1∏k=tb(Ak|Sk)p(Sk+1|Sk,Ak)=T−1∏k=tπ(Ak|Sk)b(Ak|Sk)
虽然式 (3) 所示的轨迹概率值与 MDP 的状态转移概率 p 有关,但式 (4) 所示的重要度采样比却与 MDP 的状态转移概率无关,而只与两个策略和样本序列数据有关。
通过式 (4) 所示的重要度采样比对行动策略的样本回报进行修正,得到目标策略的期望值
E[ρt:T−1Gt|St=s]=vπ(s)
2. 离轨每次访问型 MC 预测
只需对蒙特卡洛预测算法进行简单的修改,即可得到对应的离轨策略算法:在对每幕无限循环中,根据行动策略 b 而不是目标策略 π 生成序列,并在更新 G 时引入重要度采样比修正项 W。完整算法如下所示。
离轨每次访问型 MC 预测算法,用于估计 Vπ≈vπ
输入:待评估的策略 π
初始化:
对所有 s∈S,任意初始化 V(s)∈R
对所有 s∈S,Returns(s)←空列表
无限循环(对每幕):
根据 b 生成一幕序列:S0,A0,R1,S1,A1,R2,⋯,ST−1,AT−1,RT
G←0W←1
对本幕中的每一步进行循环, t=T−1,T−2,⋯,0:
G←γWG+Rt+1
将 G 加入 Returns(St)
V(St)←average(Returns(St))
W←Wπ(At|St)b(At|St)
注意上面的算法中对 ρt:T−1 计算是增量的,由式 (4) 可知
ρt:T−1=T−1∏k=tπ(Ak|Sk)b(Ak|Sk)=ρtρt+1ρt+2⋯ρT−2ρT−1
算法中对每一幕的序列进行逆序遍历,依次计算
W1←ρT−1W2←W1ρT−2=ρT−1ρT−2W3←W2ρT−3=ρT−1ρT−2ρT−3⋮
上面的算法通过计算平均实现重要度采样,称为简单重要度采样。