AI Planning 學習筆記（7）：探索與利用的平衡，Active Reinforcement Learning

AI Planning 學習筆記（7）：探索與利用的平衡，Active Reinforcement Learning

Active Reinforcement Learning

前面介紹的 Passive Reinforcement Learning 有一個共同特點：Policy 已經固定。

Agent 不需要思考該採取什麼 Action，只需要評估這個 Policy 的好壞即可。

然而，大多數真實世界的 Reinforcement Learning 問題並非如此。

例如：

  • 自駕車需要決定何時加速或煞車。
  • 機器人需要決定下一步該往哪裡移動。
  • AlphaGo 需要自己決定下一步棋。

換句話說，Policy 並不是事先給定，而是 Agent 必須自己主動學習。

這就是 Active Reinforcement Learning 所要解決的問題。

除了估計每個 State 的 Value 之外，Agent 還需要找出能夠獲得最大 Expected Return 的 Optimal Policy。

Exploration vs. Exploitation

一旦 Agent 可以自由選擇 Action，就會遇到 Reinforcement Learning 中最經典的問題：Exploration（探索）與 Exploitation（利用）的平衡。

假設你剛搬到一個新的城市。

第一天，你在公司附近找到一間很好吃的便當店。

隔天中午，你有兩種選擇：

  • 繼續去昨天那家店（Exploitation）
  • 嘗試另一間沒吃過的餐廳（Exploration）

如果每天都選擇 Exploitation（利用），你可能永遠不知道附近是否有更好的餐廳。

但如果每天都只想 Exploration（探索），又可能一直踩雷，無法享受已知的好選擇。

Reinforcement Learning 面臨的問題也是如此。

Agent 必須在利用目前已知的最佳策略與探索未知、可能更好的策略之間取得平衡。

ε-Greedy 與 GLIE

最常見的探索策略之一，就是 ε-Greedy。

它的做法非常簡單：

  • 以 1−ε1-\varepsilon 的機率，選擇目前估計最好的 Action。
  • 以 ε\varepsilon 的機率，隨機探索其他 Action。

例如：

若設定 ε=0.1\varepsilon = 0.1

代表：

  • 90% 的時間採用目前最佳策略。
  • 10% 的時間隨機探索。

這樣既能利用目前學到的知識，也能持續收集新的經驗。

然而，如果永遠維持固定的探索機率，Agent 後期仍會不斷做出隨機行為，無法完全收斂。

因此，實務上通常會採用 GLIE（Greedy in the Limit with Infinite Exploration）。

其核心思想是在學習初期，多探索；隨著經驗增加，逐漸降低探索比例。

常見的做法是令 ε=1t\varepsilon=\frac{1}{t}

其中 tt 為訓練步數。

隨著訓練進行，ε\varepsilon 會逐漸趨近於 0，Agent 最終便會依照目前學到的最佳策略行動。

Model-Based Active Reinforcement Learning

如果採用 Model-Based 方法，Agent 的第一步仍然是學習環境模型。

與 Passive ADP 不同的是，現在 Agent 不再只觀察固定 Policy，而是需要嘗試不同的 Action，估計每個 Action 對應的 Transition Probability。

當模型逐漸建立後，再利用 Bellman Equation 或 Policy Iteration 求解最佳 Policy。

然而，如果 Agent 每次都只選擇目前看起來最好的 Action，就可能永遠沒有機會發現更好的策略。

因此，Model-Based Active RL 同樣需要 Exploration 機制，例如前面介紹的 ε-Greedy。

Model-Free Active Reinforcement Learning

除了建立環境模型之外，更常見的方法是不建立任何模型，而是直接學習每個 State-Action Pair 的價值。

這就是 Model-Free Reinforcement Learning。

與前面介紹的 Utility Function 不同，這裡我們學習的是 Q-Function：Q(s,a)Q(s,a)

它表示：在 State (s) 執行 Action (a) 後，未來所能獲得的 Expected Return。

只要知道每個 Action 的 Q Value，就可以直接選擇 π(s)=arg⁡maxa⁡Q(s,a)\pi(s)=\arg\max_aQ(s,a)

因此，許多 Reinforcement Learning 演算法都圍繞著 Q Function 展開。

Monte Carlo Control

Monte Carlo 不只能估計 State Value，也能直接估計每個 State-Action Pair 的 Q Value。

其做法與前面介紹的 Monte Carlo Learning 十分類似。

Agent 每完成一個 Episode，便計算每個 State-Action Pair 所對應的 Return，再利用 Running Average 更新 Q Value。

由於需要等到 Episode 結束，因此 Monte Carlo Control 的更新速度仍然較慢。

此外，如果始終採用 Greedy Policy，也就是每一次都選擇目前看起來價值最高（Value 或 Q Value 最大）的 Action，也可能缺乏足夠的探索。

因此，Monte Carlo Control 通常會搭配 Exploration Function 或 ε-Greedy 使用，以平衡 Exploration 與 Exploitation。

Q-Learning

目前最具代表性的 Reinforcement Learning 演算法之一，就是 Q-Learning。

Q-Learning 的更新公式為：

Q(s,a)←Q(s,a)+α[R+γmaxa′⁡Q(s′,a′)Q(s,a)]Q(s,a) \leftarrow Q(s,a) + \alpha \left[ R + \gamma \max_{a’} Q(s’,a’) Q(s,a) \right]

其中：

  • α\alpha 為 Learning Rate。
  • γ\gamma 為 Discount Factor。
  • maxa′⁡Q(s′,a′)\max_{a’}Q(s’,a’) 代表下一個 State 中，最佳 Action 的 Q Value。

Q-Learning 最大的特色在於：它更新的是「如果下一步採取最佳 Action」所能獲得的回報。

因此，即使 Agent 在實際探索時採用了其他 Action，更新時仍然假設未來會選擇最佳策略。

這種學習方式稱為 Off-Policy Learning。

換句話說，學習的 Policy，與實際執行的 Policy 可以不同。

也正因如此，Q-Learning 往往能夠快速逼近 Optimal Policy，也成為後續 Deep Q-Network（DQN）的核心基礎。

SARSA

另一個經典演算法則是 SARSA。

它的名稱來自一次更新中涉及的五個元素：

  • State
  • Action
  • Reward
  • Next State
  • Next Action

更新公式為：

Q(s,a)←Q(s,a)+α[R+γQ(s′,a′)Q(s,a)]Q(s,a) \leftarrow Q(s,a) + \alpha \left[ R + \gamma Q(s’,a’) Q(s,a) \right]

與 Q-Learning 最大的不同在於：

SARSA 使用的是 Agent 實際採取的下一個 Action。

因此，如果 Agent 使用 ε-Greedy，那麼更新時也會考慮探索所帶來的影響。

這種方式稱為 On-Policy Learning。

也就是學習的 Policy，就是實際執行的 Policy。

由於 SARSA 將探索造成的風險也納入學習，因此通常會比 Q-Learning 更保守。

例如，在有懸崖（Cliff Walking）等高風險環境中，SARSA 往往會選擇較安全的路徑，而 Q-Learning 則可能持續朝理論上的最佳路徑前進。

Q-Learning 與 SARSA 比較

雖然兩者的更新公式十分相似，但學習方式卻有所不同。

Q-LearningSARSA
類型Off-PolicyOn-Policy
更新依據下一個 State 的最佳 Action實際採取的下一個 Action
是否受探索影響否是
學習風格較積極較保守

一般而言：

  • 若希望快速逼近 Optimal Policy，通常使用 Q-Learning。
  • 若需要考慮探索造成的風險，則 SARSA 往往更適合。

Reinforcement Learning 演算法總整理

最後，我們將本篇介紹的演算法整理如下。

PassiveActive
Model-BasedAdaptive Dynamic ProgrammingActive ADP
Model-FreeMonte Carlo Learning、TD LearningMonte Carlo Control、Q-Learning、SARSA

可以發現，這些演算法其實都是圍繞著兩個問題展開：

  1. 是否建立環境模型？
  2. 是否需要自己學習最佳 Policy？

理解這兩個分類方式，往後接觸新的 Reinforcement Learning 演算法時，也能更容易掌握其核心思想。

小結

從上一篇介紹的 Markov Decision Process，到本篇的 Reinforcement Learning，我們可以看到兩者最大的差異：

  • MDP 假設環境模型已知，因此可以直接利用 Bellman Equation 求解最佳 Policy。
  • Reinforcement Learning 則假設 Agent 並不知道環境模型，而必須透過不斷與環境互動，逐步學會如何做出最佳決策。

本文介紹了 Reinforcement Learning 的基本架構，並從 Model-Based 與 Model-Free、Passive 與 Active 兩個角度，整理了常見的演算法。

其中，Q-Learning 與 SARSA 是 Reinforcement Learning 中最具代表性的兩種方法，也是許多現代深度強化學習演算法的基礎。

下一篇文章，我們將正式進入 Deep Reinforcement Learning，看看當 State Space 過於龐大、無法使用表格儲存 Q Value 時，如何利用神經網路近似 Value Function，並介紹經典的 Deep Q-Network（DQN）。

Tags:

發表留言