前言

昨天提到 Cliff Walking，說提供使用 SARSA 與 Q-Learning 兩種算法的結果，我們使用 Episode per Reward 評估，這兩種算法哪一個表現得比較好。結果如下圖所示：

這個結果支持了 SARSA 比較保守這個想法。

比較保守？

可能有的人會好奇，什麼叫做比較保守，這邊使用觀察到的兩個特點說明：

• 在初期，Q-Learning 常有一些得分特別高的值，SARSA 則是一值很穩定。
• 在後期，SARSA 慢慢維持在接近 0 的地方，但 Q-Learning 卻常出現 -100 的結果。

那麼，為什麼不同的更新方法會造成這樣的結果呢？

這邊給出的解釋是「Q-Learning 的更新方式，會高估動作價值」，請試想以下的情況：

• 情境
  現在你的位置在起點右上方的位置(狀態 25)，原本按照貪婪法你應該往右走，下個狀態(狀態 26)最好的情況也是往右走，但很不幸的在狀態 26 時探索了，所以實際上卻是往下走。那麼使用不同的方法在更新時，就會有不同的結果。

• SARSA 與 Q-Learning 動作價值差異
  以 SARSA 而言，因為會考慮未來採取的動作，所以 q(25, 右) 會因為往下走，所以給予較負的動作價值。然而，以 Q-Learning 而言，並沒有考慮未來採取的狀態，所以 q(25, 右) 會比 SARSA 來的高。

• 造成的影響
  在 cliff-walking 中我們的 固定設為 0.1，所以如果沒有探索，完全按照貪婪法移動，確實會得到好結果，這是 Q-Learning 在初期偶有佳作，超越 SARSA 的原因。

以上是「在初期，Q-Learning 常有一些得分特別高的值，SARSA 則是一值很穩定。」的解釋

• 長期之後
  接續這個思路，對 SARSA 而言因為有強大負回饋的風險，所以 SARSA 選擇避開這些地方。但 Q-Learning 不受影響，繼續追求最佳路線，以下用圖表示兩者策略的差別
  
  因此在長期之後，很少看到 SARSA 方法遇到 -100 的情況，而因為 Q-Learning 靠近 -100 的地方，在未完全收斂或是探索的情況，Q-Learning 會很容易得到 -100 的結果。

此處是「在後期，SARSA 慢慢維持在接近 0 的地方，但 Q-Learning 卻常出現 -100 的結果。」的解釋

總結

這邊提供了一個 cliff walking 下，SARSA 與 Q-Learning 有差異的原因，作為對 TD-Learning 部分的總結。接著我們要考慮下一個問題，「現在我們的狀態都是離散的，那如果狀態是連續的，我們要怎麼評估呢？」