SARSA算法

SARSA算法机器学习领域的一种强化学习算法,得名于“状态-动作-奖励-状态-动作”(State–Action–Reward–State–Action)的英文首字母缩写。

SARSA算法最早是由G.A. Rummery, M. Niranjan在1994年提出的,当时称为“改进型联结主义Q学习”(Modified Connectionist Q-Learning)。[1]Richard S. Sutton英语Richard S. Sutton提出了使用替代名SARSA。[2]

SARSA算法和Q学习算法的区别主要在期望奖励Q值的更新方法上。SARSA算法使用五元组(st, at, rt, st+1, at+1)来进行更新,其中s、a、r分别为马可夫决策过程(MDP)中的状态、动作、奖励,t和t+1分别为当前步和下一步。[3]

算法

for each step in episode
 执行动作  ,观察奖励   和下一步状态  
 基于当前的   ,根据特定策略(如ε-greedy)选择  
  
   
until 状态   终止

在选择下一步动作 时,采用ε-greedy策略,即:

  • 以 ε 的概率随机选择下一个动作
  • 以 1-ε 的概率选择可以最大化 的下一个动作

在该算法中,超参数英语Hyperparameter (machine learning)   为学习速率,  为折扣因子。

在更新 时,对比Q学习使用   作为预估,SARSA则使用   作为预估。[4]一些针对Q学习的提出优化方法也可以应用于SARSA上。[5]

相关条目

参考文献

  1. ^ Online Q-Learning using Connectionist Systems" by Rummery & Niranjan (1994). [2022-07-14]. (原始内容存档于2013-06-08). 
  2. ^ Jeevanandam, Nivash. Underrated But Fascinating ML Concepts #5 – CST, PBWM, SARSA, & Sammon Mapping. Analytics India Magazine. 2021-09-13 [2021-12-05]. (原始内容存档于2021-12-05) (英语). 
  3. ^ Richard S. Sutton and Andrew G. Barto. Sarsa: On-Policy TD Control. Reinforcement Learning: An Introduction. [2022-07-14]. (原始内容存档于2020-07-05). 
  4. ^ TINGWU WANG. Tutorial of Reinforcement: A Special Focus on Q-Learning (PDF). cs.toronto. [2022-07-14]. (原始内容存档 (PDF)于2022-07-14). 
  5. ^ Wiering, Marco; Schmidhuber, Jürgen. Fast Online Q(λ) (PDF). Machine Learning. 1998-10-01, 33 (1): 105–115 [2022-07-14]. ISSN 0885-6125. S2CID 8358530. doi:10.1023/A:1007562800292 . (原始内容存档 (PDF)于2018-10-30) (英语).