2.5 Sarsa和Q-learning | 自动驾驶小白说

2.5.1 Sarsa系列

之前减少的时序差分算法是用来计算给定策略和其状态的状态值期望, 那么能不能直接估计动作值期望呢? 这也就是Sarsa方法.

2.5.1.1 Sarsa

给定策略, 我们可以用以下算法估计动作值:

这就是Sarsa算法, 它的名字来源于上式的输入: .

实际上, Sarsa算法是一种随机近似方法, 用于求解使用动作值表达的贝尔曼公式:

2.5.1.2 Expected Sarsa

如果将TD目标改成期望, 就是Expected Sarsa:

其中TD目标项中的期望定义为:

Sarsa中只计算一个带来的动作值, Expected Sarsa完整的计算了状态值

同样, Expected Sarsa也是计算一个贝尔曼公式:

其中的期望可以展开成:

2.5.1.3 n-step Sarsa

我们回顾一下动作值的定义, 给定状态和动作时, 轨迹期望:

其中是指轨迹的discounted return, 定义为:

如果我们额外定义一个上标, 第步时用动作值替代表达式:

时: Sarsa

动作值期望可以写成:

随机近似理论求解上式的更新公式为:

显然这就是Sarsa算法求解的目标贝尔曼公式

时: MC learning

动作值期望可以写成:

求解上式的更新公式为:

是的采样, 这实际就是蒙特卡洛方法

时: n-step Sarsa

当我们采用一个这种的固定值时:

它的更新公式为:

这也就是n-step Sarsa方法.

不过需要说明的是, 不管定义为多少, 它们的值都是一样的, 只是写法不同:

2.5.2 Q-learning

2.5.2.1 定义

Q-learning的更新公式为:

只有TD目标项有变化, 它不再是Sarsa中的给定动作的动作值: , 或者是expected Sarsa中的动作值的期望: .

而是最优动作的动作值: , 同样它也是一个随机近似方法, 要求解的方程为:

2.5.2.2 On-policy 和 Off-policy

首先我们定义两个策略概念:

behavior policy: 行为策略, 用来生成经验样本的策略。

target policy: 目标策略, 不断更新以趋于最优策略的策略。

当行为策略和目标策略相同时, 这种学习过程称为在on-policy学习(Sarsa, MC learning);

当行为策略和目标策略可以不同(也可以相同)时, 这种学习过程称为在off-policy学习(Q-learning);

On-policy版本的Q-learning算法如上图, 它的策略即用来获取经验数据, 也用来更新策略. 因此它是On-policy的.

上图是Off-policy的Q-learning算法, 它的行为策略是一开始给定的, 会基于获取经验数据. 而更新策略时, 并不更新行为策略, 因此是Off-policy的.

2.5.2.3 例子

我们给出这样一个例子, 假设我们已经知道了它的最优策略(a)和最优状态值分布(b)

并且我们给出一个均匀的行为策略(c)和它对应的采样结果(d)

当我们使用Q-learning求解时, 结果非常接近真实的最优解, 过程数据如图.

但是当行为策略并不均匀时, 求解质量会变差:

2.5.3 TD算法总结

所有的TD算法实际上, 都是如下的更新形式:

区别在于, 它们的更新的TD目标不一样:

以及它们对应的求解目标公式: