SARSA算法

SARSA算法是機器學習領域的一種強化學習算法，得名於「狀態-動作-獎勵-狀態-動作」（State–Action–Reward–State–Action）的英文首字母縮寫。

SARSA算法最早是由G.A. Rummery, M. Niranjan在1994年提出的，當時稱為「改進型聯結主義Q學習」（Modified Connectionist Q-Learning）。^[1]理查德·S·薩頓提出了使用替代名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學習
• 馬可夫決策過程