适用于:
- MDP model 未知:经验的采样可以获取
- MDP model 已知:无法使用(e.g.原子级动力学),采样可以使用
策略、非策略学习:
- On-policy:采样来自policy (pi)
- Off-policy:采样来自μ (pi)
On-policy MC control
model-free policy using action-value function
贪婪策略梯度法如果用V(s),需要MDP已知
用Q(s,a),不需要已知MDP
为了避免局部最优,引入(epsilon),使(pi)以小概率随机选择剩余动作,避免每次都选择已知较优动作
GLIE MC control
保证试验进行一定次数是,所有a-s状态都被访问到很多次
TD与MC control 区别
ON-policy TD learning
Sasra(one-step)
由贝尔曼公式推导
算法实现过程
要保证Q值收敛,需要服从下列定理
n-step Sarsa
Forward view Sarsa((lambda))
Backward view Sarsa((lambda))
在正向视角中,迭代一次Q值,需要完整的一次episode
为了解决这个问题,每次s改变时,就能迭代一次,引入迹的概念
算法流程
Off-policy learning
需求
- 从人类和其他agents的表现中学习
- 从old policies (pi_1, pi_2...)中学习
- 从随机策略中,学习到最优策略
- 从一个策略中,学习到多个策略
采样不同分布
[
egin{aligned}
mathbb{E}_{X sim P}[f(X)] &=sum P(X) f(X) \
&=sum Q(X) frac{P(X)}{Q(X)} f(X) \
&=mathbb{E}_{X sim Q}left[frac{P(X)}{Q(X)} f(X)
ight]
end{aligned}
]
off-policy MC learning
缺点:
- 方差会增加
- (mu =0)无法计算
off-policy TD learning
利用期望分布的概念,在更新目标前x一个系数,对当前策略的置信度
优点:
- 低方差
- 单步策略需要相似
Q-learning
特点
- 采用Q(s,a) instead of V(s)
- 不需要重要性采样 系数
- 下次动作用 (A_{t+1} ∼ μ(·|S_t))
- 动作服从策略 as (A′ ∼ π(·|S_t))
更新方程如下
[
Qleft(S_{t}, A_{t}
ight) leftarrow Qleft(S_{t}, A_{t}
ight)+alphaleft(R_{t+1}+gamma Qleft(S_{t+1}, A^{prime}
ight)-Qleft(S_{t}, A_{t}
ight)
ight)
]
off-policy control with Q-learning
- 同时优化 behaviour 和 target policies
- 目标策略(pi) is greedy :
[
pileft(S_{t+1} ight)=underset{a^{prime}}{operatorname{argmax}} Qleft(S_{t+1}, a^{prime} ight)
]
Q-learning target 简化为:
[
egin{aligned}
& R_{t+1}+gamma Qleft(S_{t+1}, A^{prime}
ight) \
=& R_{t+1}+gamma Qleft(S_{t+1}, underset{a^{prime}}{operatorname{argmax}} Qleft(S_{t+1}, a^{prime}
ight)
ight) \
=& R_{t+1}+max _{a^{prime}} gamma Qleft(S_{t+1}, a^{prime}
ight)
end{aligned}
]
迭代使(Q(s,a) ightarrow q_* (s,a))
算法流程
总结
DP TD的关系