本文主要讲解 Sarsa 算法以及 Sarsa($\lambda$) 算法的相关内容,同时还会分别附上一个莫烦大神写的例子。
一、Sarsa 算法
Sarsa 算法与 Q-Learning 算法相似,也是利用 Q 表来选择动作,唯一不同的是两者 Q 表的更新策略不同。该算法由于更新一次动作值函数需要用到 5 个量 $(s,a,r,s′,a′)$,所以被称为 Sarsa 算法。
1. Sarsa 算法基本思想
Sarsa 算法中 Q 表的更新公式如下:
$$
Q(S_t,A_t)\leftarrow Q(S_t,A_t)+\alpha[R_{t+1}+\gamma\cdot Q(S_{t+1},A_{t+1})-Q(S_t,A_t)]
$$
其中 $Q(S_{t+1},A_{t+1})$ 是下一时刻的状态和实际采取的行动对应的 Q 值;而在 Q-Larning 中是下一时刻的状态对应的 Q 值的最大值,但是在实际中可能不采用该最大值对应的动作。Sarsa 算法和 Q-Learning 算法除了在 Q-target 上有所不同,其他的都一样。
Sarsa 是 on-policy 学习方法,因为它始终只有一个策略,使用 $\epsilon$ 贪婪方法选择出 $Q(S_t,A_t)$ 和 $Q(S_{t+1}’,A_{t+1}’)$ 。而 Q-Learning 算法是 off-policy 算法,选择 $Q(S_t,A_t)$ 时使用 $\epsilon$ 贪婪方法,而计算 $Q(S’,A’)$ 时使用了最大值算法,学习和行动分别采用了两套不同的策略。
2. Sarsa 算法流程:
初始化 Q 表(令其值为 0)
对于每个 episode(回合):
1. 初始化状态 s
2. 在当前状态 s 的所有可能动作中选取一个动作 a (以 $\epsilon$ 的概率安装 Q 表数值最大的动作行动,以 $1-\epsilon$ 的概率随机行动)
3. 如果当前状态 s 不是终止状态,则重复执行以下步骤:
(1)执行动作 a 并得到下一个状态 s‘ 和相应的奖励 r
(2)在当前状态 s’ 的所有可能动作中选取一个动作 a’
(3)更新 Q 表:$Q(s,a)\leftarrow Q(s,a)+\alpha[r+\gamma\cdot Q(s’,a’)-Q(s,a)]$
(4)更新状态和动作:s=s’, a=a’
二、 Sarsa ($\lambda$) 算法
1. Sarsa ($\lambda$) 算法基本思想
Q-Learning 和 Sarsa 都是在得到奖励后只更新上一步状态和动作对应的 Q 表值,是单步更新算法,也就是 Sarsa(0)。但是在得到当前奖励值之前所走的每一步(即一个轨迹)都多多少少和最终得到的奖励值有关,所以不应该只更新上一步状态对应的 Q 值。于是就有了多步更新算法——Sarsa(n)。当 n 的值为一个回合(episode)的步数时就变成了回合更新。对于多步更新的 Sarsa 算法我们用 $Sarsa(\lambda)$ 来统一表示,其中 $\lambda$ 的取值范围是 [ 0 , 1 ],其本质是一个衰减值。
所谓的轨迹就是指状态、动作和奖励的一个历史序列,很多时候会遇到这个概念,所以这里简单提一句。
2. Sarsa ($\lambda$) 算法流程
$Sarsa(\lambda)$ 算法比 $Sarsa$ 算法中多了一个矩阵E (eligibility trace),它用来保存在路径中所经历的每一步,并其值会不断地衰减。该矩阵的所有元素在每个回合的开始会初始化为 0,如果状态 s 和动作 a 对应的 E(s,a) 值被访问过,则会其值加一。并且矩阵 E 中所有元素的值在每步后都会进行衰减,这保证了离获得当前奖励越近的步骤越重要,并且如果前期智能体在原地打转时,经过多次衰减后其 E 值就接近于 0 了,对应的 Q 值几乎没有更新。
值得注意的是,在更新 Q(s,a) 和 E(s,a) 时,是对“整个表”做更新,但是因为矩阵 E 的初始值是 0,只有智能体走过的位置才有值,所以并不是真正的对“整个表”做更新,而是更新获得奖励值之前经过的所有步骤。而那些没有经过的步骤因为对应的 E(s,a) 值为0,所以 $Q(s,a)=Q(s,a)+\alpha\cdot\delta\cdot E(s,a)=Q(s,a)$,会保持原值不变。
3. 矩阵 E 的两种更新方式
(1) accumulating trace:每次走到当前状态,则将当前的矩阵 E 的元素值+1,即:
$$
E(s,a)=E(s,a)+1
$$
(2) replacing trace:给矩阵 E 的元素值设置上限,使得其所有值在 [0 , 1] 之间,所以每次更新时先将当前状态所在的行清零,再将对应的 E(s,a) 置一,即:
$$
E(s,:)=0
$$
$$
E(s,a)=1
$$
从实践来说,第二种更新方式会更好一点。
- 本文作者: 俎志昂
- 本文链接: zuzhiang.cn/2019/10/10/sarsa/
- 版权声明: 本博客所有文章除特别声明外,均采用 Apache License 2.0 许可协议。转载请注明出处!