SARSA算法

机器学习与数据挖掘
范式 监督学习 無監督學習 線上機器學習 元学习（英语：Meta-learning (computer science)） 半监督学习 自监督学习 强化学习 基于规则的机器学习（英语：Rule-based machine learning） 量子機器學習
问题 统计分类 生成模型 迴歸分析 聚类分析 降维 密度估计（英语：density estimation） 异常检测 数据清洗 自动机器学习 关联规则学习 語意分析 结构预测（英语：Structured prediction） 特征工程 表征学习 排序学习（英语：Learning to rank） 语法归纳（英语：Grammar induction） 本体学习（英语：Ontology learning） 多模态学习（英语：Multimodal learning）
监督学习 (分类 · 回归) 学徒学习（英语：Apprenticeship learning） 决策树学习 集成学习 Bagging 提升方法 随机森林 k-NN 線性回歸 朴素贝叶斯 人工神经网络 邏輯斯諦迴歸 感知器 相关向量机（RVM） 支持向量机（SVM） 迁移学习 微调
聚类分析 BIRCH CURE算法（英语：CURE algorithm） 层次 k-平均 Fuzzy 期望最大化（EM） DBSCAN OPTICS 均值飘移（英语：Mean shift）
降维 因素分析 CCA ICA LDA NMF（英语：Non-negative matrix factorization） PCA PGD（英语：Proper generalized decomposition） t-SNE（英语：t-distributed stochastic neighbor embedding） SDL
结构预测（英语：Structured prediction） 圖模式 貝氏網路 條件隨機域 隐马尔可夫模型
异常检测 RANSAC k-NN 局部异常因子（英语：Local outlier factor） 孤立森林（英语：Isolation forest）
人工神经网络 自编码器 認知計算 深度学习 DeepDream（英语：DeepDream） 多层感知器 RNN LSTM GRU（英语：Gated recurrent unit） ESN（英语：Echo state network） 储备池计算（英语：reservoir computing） 受限玻尔兹曼机 GAN SOM CNN U-Net Transformer Vision transforme（英语：Vision transformer） 脉冲神经网络（英语：Spiking neural network） Memtransistor（英语：Memtransistor） 电化学RAM（英语：Electrochemical RAM）（ECRAM）
强化学习 Q学习 SARSA 时序差分（TD） 多智能体（英语：Multi-agent reinforcement learning） Self-play（英语：Self-play (reinforcement learning technique)） RLHF
与人类学习 主动学习（英语：Active learning (machine learning)） 众包 Human-in-the-loop（英语：Human-in-the-loop）
模型诊断 学习曲线（英语：Learning curve (machine learning)）
数学基础 内核机器（英语：Kernel machines） 偏差–方差困境（英语：Bias–variance tradeoff） 计算学习理论（英语：Computational learning theory） 经验风险最小化 奥卡姆学习（英语：Occam learning） PAC学习（英语：Probably approximately correct learning） 统计学习 VC理论
大会与出版物 NeurIPS ICML（英语：International Conference on Machine Learning） ICLR ML（英语：Machine Learning (journal)） JMLR（英语：Journal of Machine Learning Research）
相关条目 人工智能术语（英语：Glossary of artificial intelligence） 机器学习研究数据集列表（英语：List of datasets for machine-learning research） 机器学习概要（英语：Outline of machine learning）
查 论 编

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算法使用五元组(s_t, a_t, r_t, s_t+1, a_t+1)来进行更新，其中s、a、r分别为马可夫决策过程（MDP）中的状态、动作、奖励，t和t+1分别为当前步和下一步。^[3]

算法

for each step in episode
 执行动作 ${\displaystyle a_{t}}$，观察奖励 ${\displaystyle r_{t}}$ 和下一步状态 ${\displaystyle s_{t+1}}$
 基于当前的 ${\displaystyle Q}$ 和 ${\displaystyle s_{t+1}}$，根据特定策略（如ε-greedy）选择 ${\displaystyle a_{t+1}}$
 ${\displaystyle Q^{new}(s_{t},a_{t})\leftarrow Q(s_{t},a_{t})+\alpha \,[r_{t}+\gamma \,Q(s_{t+1},a_{t+1})-Q(s_{t},a_{t})]}$
 ${\displaystyle s_{t}\leftarrow s_{t+1}}$；${\displaystyle a_{t}\leftarrow a_{t+1}}$
until 状态 ${\displaystyle s}$ 终止

在选择下一步动作${\displaystyle a_{t+1}}$时，采用ε-greedy策略，即：

• 以 ε 的概率随机选择下一个动作
• 以 1-ε 的概率选择可以最大化${\displaystyle Q(s_{t+1},a_{t+1})}$的下一个动作

在该算法中，超参数 ${\displaystyle \alpha }$ 为学习速率，${\displaystyle \gamma }$ 为折扣因子。

在更新${\displaystyle Q}$时，对比Q学习使用 ${\displaystyle {\text{max}}_{a}Q(s_{t+1},a)}$ 作为预估，SARSA则使用 ${\displaystyle Q(s_{t+1},a_{t+1})}$ 作为预估。^[4]一些针对Q学习的提出优化方法也可以应用于SARSA上。^[5]

相关条目

• 强化学习
• Q学习
• 馬可夫決策過程

参考文献