AI時代系列(3) 機器學習三部曲: 📘 第三部：《強化學習 —— AI 的決策與進化》
34/100 第四週：📌 時序差分學習 TD
34. SARSA 演算法 🧠 On-policy 控制範例教學！
________________________________________
🎯 單元導讀：
SARSA (State → Action → Reward → State' → Action'。)是一種典型的 On-policy TD 控制演算法，名稱來自其五個核心元素：
State → Action → Reward → State' → Action'。
SARSA 在實際互動中，根據「當下所用策略」來學習與更新 Q 值，並逐步改進策略。
適合用於需要持續互動、策略跟著行為更新的場景。
________________________________________
🧠 一、SARSA 名稱由來
時間 t 時間 t+1
+---------+ a_t +---------+
| s_t | -----------> | s_{t+1}|
+---------+ +---------+
| |
| |
| |
r_{t+1} a_{t+1} (根據策略選)
SARSA 取用的五個元素：
(s_t, a_t, r_{t+1}, s_{t+1}, a_{t+1})
在 SARSA 演算法中，每次更新會用到五個資訊：
當下的狀態 sₜ
當下採取的動作 aₜ
產生的即時獎勵 rₜ₊₁
移動後的新狀態 sₜ₊₁
以及在 sₜ₊₁ 下根據當前策略選出的下一個動作 aₜ₊₁。
SARSA 會將「實際經歷的路徑」拿來修正 Q 值。更新時，先觀察新得到的回報 rₜ₊₁，再加上在新狀態 sₜ₊₁ 下對自己實際選擇 aₜ₊₁ 的預期價值，整體當成新的估計，與原本的 Q(sₜ, aₜ) 做誤差修正。因為用的是當前策略選的 aₜ₊₁，所以稱為 On-policy 學習。
👉 重點口訣：
「做完後馬上看自己下一步選什麼」
這就是 SARSA 和 Q-Learning 最大不同。SARSA 會去取實際選到的 a_{t+1}，而不是取 Q 最大值。
________________________________________
⚙️ 二、SARSA 演算法公式
Q 值更新公式如下：
Q(s_t, a_t) <-- Q(s_t, a_t)
+ α * [r_{t+1} + γ * Q(s_{t+1}, a_{t+1}) - Q(s_t, a_t)]
其中：
• α：學習率
• γ：折扣因子
• Q(st,at)Q(s_t, a_t)Q(st,at)：目前的估計
• Q(st+1,at+1)Q(s_{t+1}, a_{t+1})Q(st+1,at+1)：下一狀態在當前策略下的估計值
SARSA 每次更新時，利用學習率 α 決定修正幅度，折扣因子 γ 反映對未來回報的重視程度。它根據目前狀態與動作的估計值 Q(sₜ, aₜ)，以及下個狀態中依照當前策略實際選出的動作所對應的估計值 Q(sₜ₊₁, aₜ₊₁)，來計算誤差並修正 Q 值。透過不斷累積這些經驗，SARSA 逐步學習出符合策略的最佳行動方案。
📌 SARSA 強調 依據目前策略執行與更新，這與 Q-learning 的最大值選擇不同。
________________________________________
🔁 三、SARSA 執行流程
1️⃣ 初始化 Q(s,a)
2️⃣ 重複進行每一個 episode：
a. 從起始狀態 s，依 ε-greedy 選擇行動 a
b. 執行動作，獲得 rrr、觀察下一狀態 s′
c. 依 ε-greedy 再選擇下一個行動 a′
d. 根據更新公式修正 Q(s,a)
e. 更新公式利用 (s, a, r, s′, a′) 這五個元素修正 Q 值，持續學習更好的策略。
直到 episode 結束。
________________________________________
🧩 四、SARSA 與 Q-learning 比較
SARSA 是 On-policy 方法，在更新 Q 值時使用實際依照當前策略所選出的動作 a′，因此學習過程與行為策略保持一致，收斂較保守，適合需要穩定控制的應用情境，如交通控制或機器人導航。而 Q-learning 屬於 Off-policy 方法，更新時直接取下一狀態所有可能動作中最大 Q 值（argmax a），較激進，收斂速度可能更快，但也容易學到高風險策略，適合像博弈、對戰等追求高效率的任務。
________________________________________
🕹 五、實作範例情境：走迷宮任務（GridWorld）
SARSA 學習讓智能體從起點走到目標，並盡量避免掉入陷阱。
• 狀態：地圖位置 (x, y)
• 行動：上、下、左、右
• 獎勵：到終點 +10，走到陷阱 -10，其餘為 0
• 策略：ε-greedy
• 演算法：SARSA 漸進式更新 Q 值 → 找出穩健路徑
________________________________________
🧪 六、延伸挑戰任務
1️⃣ 嘗試將 SARSA 套用到 21 點遊戲、走迷宮或電玩推薦場景
簡答：
• 21 點遊戲：SARSA 可根據玩家目前手牌總點數、莊家明牌與目前選擇的動作（要牌或停牌）作為狀態與行動，當完成一局後根據輸贏得到回饋，利用 TD 誤差修正 Q 值。經過多次訓練後，AI 可學會在不同情境下做出最佳要牌/停牌決策
。
• 走迷宮任務：每次移動的狀態為目前所在格子位置，行動為上下左右移動，獎勵根據是否抵達目標或掉入陷阱給出。SARSA 透過實際走的路徑更新 Q 值，比較適合在地圖中存在隨機障礙或有危險區域的迷宮訓練，學習保守且穩定的路徑。
• 電玩推薦場景：每次推薦一款遊戲（行動 a）後觀察使用者的反應（例如是否有下載、遊玩時間長短等作為獎勵 r），下一次根據用戶最新行為（狀態 s′）選擇新的推薦。SARSA 可以在實際互動中逐步學習用戶偏好，建立個人化推薦模型。
________________________________________
2️⃣ 改變 ε 值（如 0.1 → 0.3），觀察探索與保守性的變化
簡答：
• ε 代表探索比例：
當 ε 提高時（例如 0.1 → 0.3），AI 增加隨機選擇動作的頻率，會去嘗試更多不熟悉的選擇，有機會發現更好的行動路徑。
• ε 較大時：
o 初期探索更多樣，有助於避免過早陷入局部最優解。
o 但也可能短期內表現較波動，因為有些新嘗試帶來較差的結果。
• ε 較小時：
o AI 較偏向利用現有已知的好策略，學習過程穩定。
o 但若早期策略不佳，可能長期卡在次優策略上。
• 實務建議：常用ε遞減法，讓系統初期多探索，後期逐漸轉向穩定利用。
________________________________________
3️⃣ 與 Q-learning 訓練同樣環境後比較學習穩定性與策略選擇
簡答：
• SARSA (On-policy)：
o 更新使用實際採取的動作，較符合真實行為。
o 學習較穩定，適合風險較高、不可犯錯的應用（如交通控制、醫療決策）。
o 偏向「穩健型學習」，行為一致，避免激進策略。
• Q-learning (Off-policy)：
o 更新時直接取最大 Q 值，追求理論上最好的策略，不考慮實際行為。
o 學習速度較快，容易發現高報酬策略，但可能出現高風險決策。
o 偏向「積極型學習」，在競爭型遊戲、對戰、博弈環境更具優勢。
• 兩者比較：
o SARSA 風險控制較好，穩定性高；Q-learning 收斂速度較快但可能振盪。
o 在環境具高不確定性與風險代價高時，SARSA 較適用；在高度可模擬、允許大量試錯的場景下，Q-learning 較具優勢。
________________________________________
✅ 七、小結與啟示
• SARSA 是 On-policy 強化學習代表，實務中常與 ε-greedy 策略搭配
• 更新是根據實際策略選擇的下一行動，而非理論上最優
• 學習過程更保守，穩定性較好，適合控制問題與風險可控任務
• SARSA 鼓勵「做中學」，一步步累積智慧，穩扎穩打！
