Processing math: 100%

[RL Notes] 重要度采样和离轨蒙特卡洛预测

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:T1π)=π(At|St)p(St+1|St,At)π(At+1|St+1)p(ST|ST1,AT1)=T1k=tπ(Ak|Sk)p(Sk+1|Sk,Ak)

其中 p 是MDP 的状态转移概率,且通常是未知的。于是可得目标策略和行动策略轨迹下的相对概率即重要度采样比为

ρt:T1T1k=tπ(Ak|Sk)p(Sk+1|Sk,Ak)T1k=tb(Ak|Sk)p(Sk+1|Sk,Ak)=T1k=tπ(Ak|Sk)b(Ak|Sk)

虽然式 (3) 所示的轨迹概率值与 MDP 的状态转移概率 p 有关,但式 (4) 所示的重要度采样比却与 MDP 的状态转移概率无关,而只与两个策略和样本序列数据有关。

  通过式 (4) 所示的重要度采样比对行动策略的样本回报进行修正,得到目标策略的期望值

E[ρt:T1Gt|St=s]=vπ(s)

2. 离轨每次访问型 MC 预测

  只需对蒙特卡洛预测算法进行简单的修改,即可得到对应的离轨策略算法:在对每幕无限循环中,根据行动策略 b 而不是目标策略 π 生成序列,并在更新 G 时引入重要度采样比修正项 W。完整算法如下所示。


离轨每次访问型 MC 预测算法,用于估计 Vπvπ
输入:待评估的策略 π
初始化:
  对所有 sS,任意初始化 V(s)R
  对所有 sSReturns(s)
无限循环(对每幕):
  根据 b 生成一幕序列:S0,A0,R1,S1,A1,R2,,ST1,AT1,RT
  G0W1
  对本幕中的每一步进行循环, t=T1,T2,,0
    GγWG+Rt+1
    将 G 加入 Returns(St)
    V(St)average(Returns(St))
    WWπ(At|St)b(At|St)


  注意上面的算法中对 ρt:T1 计算是增量的,由式 (4) 可知

ρt:T1=T1k=tπ(Ak|Sk)b(Ak|Sk)=ρtρt+1ρt+2ρT2ρT1

算法中对每一幕的序列进行逆序遍历,依次计算

W1ρT1W2W1ρT2=ρT1ρT2W3W2ρT3=ρT1ρT2ρT3

  上面的算法通过计算平均实现重要度采样,称为简单重要度采样