SARSA入門：強化学習のオンポリシー手法をわかりやすく解説—Q学習との違い・収束条件・実装ポイント
エバープレイ編集部SARSAとは何か — 基本概念と直感
SARSA（サーサ）は、強化学習（Reinforcement Learning, RL）における代表的な行動価値（action-value）を学習するオンポリシー型の時刻差（Temporal-Difference, TD）学習アルゴリズムです。名前はアルゴリズムが使う5つの情報項目 State（状態）- Action（行動）- Reward（報酬）- next State（次状態）- next Action（次行動）の頭文字を取ったもの（S-A-R-S-A）に由来します。SARSAは、実際にエージェントが従う「現在の方策（policy）」を用いて価値を更新するため、探索を含む振る舞いをそのまま反映した学習が行われます。
アルゴリズムの数式と更新則
SARSAの基本的な更新則は次の通りです。ある状態sで行動aを取り、報酬rを得て次状態s'に遷移し、次状態で方策に従って行動a'を選んだとき、行動価値Q(s,a)を以下のように更新します。
Q(s,a) ← Q(s,a) + α [ r + γ Q(s', a') − Q(s,a) ]
- α（学習率）：0〜1。新しい情報の取り込み量を決める。
- γ（割引率）：0〜1。将来報酬の現在価値に対する重み。
- r：遷移で得られた報酬。
- Q(s',a')：次状態で選択した行動の価値（オンポリシーなので実際に選ばれるa'を用いる）。
この式から分かるように、SARSAは次の行動a'を明示的に考慮するため、探索（例：ε-greedy）を行っている場合、その探索が学習に反映されます。
オンポリシー vs オフポリシー：SARSAとQ学習の違い
SARSAはオンポリシー法であるのに対し、Q学習（Q-learning）はオフポリシーの代表例です。Q学習の更新則は次のように最大価値を用います：
Q(s,a) ← Q(s,a) + α [ r + γ max_{a'} Q(s', a') − Q(s,a) ]
つまりQ学習は「最良の行動（greedy）」を仮定して更新するため、探索を行っていても最終的に最適行動価値Q*に収束することが期待されます（条件付き）。一方で、SARSAは実際に選択した行動a'に基づいて更新するため、探索の影響を受け、より安全（保守的）な行動になることがあります。典型的な例としてSutton & Bartoで示される“cliff walking”（崖の横を歩く問題）があり、Q学習は最短経路を取るために崖ギリギリを通るが、SARSAはε-greedyの探索により崖へ落ちるリスクを織り込んだやや遠回りの安全な経路を学習することが知られています。
変種と拡張
- SARSA(λ)：資格トレース（eligibility traces）を用いることで、1ステップ更新（TD(0)）よりも効率よく価値を伝播させる。λは過去の状態・行動にどれだけ“責任”を割り振るかを決めるパラメータ。
- Expected SARSA：次状態での期待値を用いることで、分散を減らす。目標ターゲットを r + γ Σ_{a'} π(a'|s') Q(s',a') とする。
- Function approximationとSARSA：テーブルではなく線形近似やニューラルネットを用いる場合、SARSAをそのまま適用できる（例：SARSA with neural networks）。ただし「ブートストラップ（TD）、関数近似、オフポリシー」の組合せは発散し得る（いわゆる“deadly triad”）。SARSAはオンポリシーであるため、Q学習よりは安定しやすいが、依然注意が必要。
収束性と理論的条件
SARSAの収束にはいくつかの前提条件があります。有限な状態・行動空間のマルコフ決定過程（MDP）で、学習率α_tが適切に減衰する（Robbins–Monro条件： Σα_t = ∞, Σα_t^2 < ∞）こと、そして方策が十分な探索を長期間保証する（GLIE: Greedy in the Limit with Infinite Exploration）などが典型的条件です。これらが満たされれば、SARSAは最適方策に収束することが理論的に示されています（Sutton & Barto等）。ただし、関数近似や連続空間を扱う場合、追加の仮定や手法が必要になります。
実務上のポイントとハイパーパラメータ設計
- 探索戦略：ε-greedyが基本。初期は大きめのεで広く探索し、徐々に減少させて方策を収束させる（GLIEを満たすように設計）。ソフトマックス（確率的に行動を選ぶ）も有効。
- 学習率α：固定でも良いが、理論的収束を担保するなら減衰を採用。実務では経験リプレイやバッチ学習と組み合わせる場合が多い。
- 割引率γ：タスクの時間スケールに依存。長期報酬を重視するならγを大きく設定。
- 初期Q値の設定：楽観的初期化（高めに設定）をすると自然に探索が促進される。
- 関数近似の扱い：ニューラルネット等でSARSAを使う場合、ターゲットの分散や相関に注意し、ターゲットネットワークや経験再生（Experience Replay）などの技術を組み合わせると安定する。
具体例（簡易的な擬似コード）
以下はε-greedyと1ステップSARSAの擬似コード（高レベル）です。
Initialize Q(s,a) arbitrarily
for each episode:
initialize state s
choose action a from s using policy derived from Q (e.g., ε-greedy)
while s is not terminal:
take action a, observe r and s'
choose a' from s' using policy derived from Q (ε-greedy)
Q(s,a) ← Q(s,a) + α [ r + γ Q(s',a') − Q(s,a) ]
s ← s'; a ← a'
SARSAを選ぶべき状況・使い分けの指針
- 探索時のリスクを学習に反映させたい（安全性を考慮）場合にはSARSAが向く。探索による不利な結果（例：落下や損害）が学習中の方策に反映されるため、本番での危険な行動を避けやすい。
- 最終的に最短・最良の経路だけを求める（探索フェーズと学習フェーズを明確に分ける）なら、オフポリシーのQ学習やその他手法も検討の余地がある。
- 関数近似を併用する場合は安定化手法（ターゲットネットや経験再生、正則化など）を併用すること。
事例：Cliff Walkingによる直観的違い
Sutton & Bartoで紹介されるcliff walking問題は、SARSAとQ学習の違いを直感的に示す代表例です。エージェントが崖の近くを通る最短ルートを取るかどうかは、探索の影響をどのように学習に反映するかに依存します。SARSAは探索時の偶発的な崖落ちのリスクを学習対象に含めるため、やや遠回りだが安全な経路を学ぶ傾向があります。一方Q学習は理想的な最適行動を目標とするため、崖ギリギリの最短経路を学ぶことがあり、本番での探索がリスクになる場合があります。
まとめ
SARSAはオンポリシーTD制御法として、実際にエージェントが採る方策をそのまま学習に反映する特徴を持ちます。探索の影響を方策に組み込みたい、安全性を考慮した学習を行いたい場面で有効です。拡張としてSARSA(λ)やExpected SARSAがあり、関数近似と組み合わせる場合は安定性確保のための工夫が必要です。理論的収束条件や実務的ハイパーパラメータ調整を理解した上で適用することで、実用的なRLシステムに有用な手法となります。
参考文献
- Richard S. Sutton and Andrew G. Barto, "Reinforcement Learning: An Introduction" (2nd edition) — Online book
- SARSA (Wikipedia) — 概要と参考文献一覧
- C. J. C. H. Watkins and P. Dayan, "Q-learning", Machine Learning (1992)
- G. A. Rummery and M. Niranjan, "On-line Q-learning using connectionist systems" (Technical report, 1994) — SARSAの命名に関する歴史的資料
投稿者プロフィール
