AI Planning 學習筆記（6）：當環境未知時，AI 如何學習？Reinforcement Learning 基礎介紹

AI Planning 學習筆記（6）：當環境未知時，AI 如何學習？Reinforcement Learning 基礎介紹

在上一篇文章中，我們介紹了 Markov Decision Process（MDP），並利用 Value Iteration、Policy Iteration 等方法求解最佳 Policy。

不過，這些方法都有一個重要的前提，那就是 Agent 擁有上帝視角，已經知道整個環境模型（Environment Model）。

也就是說，我們已知：

  • Transition Function T(s,a,s′)T(s,a,s’)
  • Reward Function R(s,a,s′)R(s,a,s’)

因此，只要套用 Bellman Equation，就能計算每個 State 的 Value，進而找到最佳 Policy。

然而，真實世界並非如此。

例如，一台全新的掃地機器人，並不知道每個房間的格局；自駕車也不知道所有駕駛人的行為模式；AlphaGo 在面對新的對手時，也無法預先知道對方每一步棋。

換句話說，Agent 並不知道環境的規則，而只能透過不斷與環境互動，一步步學習。

這就是 Reinforcement Learning（強化學習） 所要解決的問題。

Reinforcement Learning 是什麼？

Reinforcement Learning（RL）是一種讓 Agent 透過 Trial and Error（嘗試與錯誤） 學習最佳策略的方法。

它並不是另一種 Decision Model，而是建立在上一篇介紹的 Markov Decision Process（MDP） 之上。

不同的點有以下兩個：

  • 在 MDP 中，我們已經知道 Transition Function 與 Reward Function。
  • 在 RL 中，環境仍然可以用 MDP 的數學模型來描述，但 Agent 不知道 Transition Function 與 Reward Function。

因此，Agent 必須透過與環境互動，不斷收集經驗（Experience），逐漸學會如何做出最佳決策。

可以用下圖表示 Reinforcement Learning 的基本流程：

整個學習過程會不斷重複：

  1. Agent 根據目前的 Policy 選擇一個 Action
  2. Environment 回傳新的 State 與 Reward
  3. Agent 根據這次經驗更新自己的知識
  4. 再次選擇下一個 Action

經過大量互動後，Agent 最終學會一個接近 Optimal Policy 的策略。

Reinforcement Learning 的問題設定

雖然 Agent 不知道環境模型，但 Reinforcement Learning 仍然假設環境符合 Markov Property。

也就是說下一個 State 只與目前的 State 和 Action 有關，而與更早之前的歷史無關。

因此，一個 Reinforcement Learning 問題仍然可以利用 MDP 表示，只是其中的 Transition Function 和 Reward Function 對 Agent 而言是未知的。

Agent 所能做的只有：

  • 觀察目前的 State
  • 選擇一個 Action
  • 接收 Reward
  • 觀察新的 State

再利用這些 Experience，不斷修正自己的 Policy。

Episode 與 Return

在 Reinforcement Learning 中，一次完整的互動通常稱為一個 Episode。

例如：

  • 玩完一局遊戲。
  • 機器人成功走到終點。
  • 自駕車完成一次導航。

都可以視為一個 Episode。

Episode 中，每一步都會得到一個 Reward。

但 Agent 真正想最大化的，不只是當前的 Reward，而是整個 Episode 的累積 Reward。

因此，我們定義 Return：

Gt=Rt+1+γRt+2+γ2Rt+3+⋯G_t = R_{t+1}+\gamma R_{t+2}+\gamma^2R_{t+3}+\cdots

其中：

  • RtR_t 是每一步得到的 Reward。
  • γ\gamma 是上一篇介紹過的 Discount Factor。

Return 可以理解成從現在開始，一直到未來所有 Reward 的折扣總和。

因此，Reinforcement Learning 的目標，就是找到一個 Policy，使 Expected Return 最大化。

Reinforcement Learning 的兩種分類方式

Reinforcement Learning 的演算法非常多，但大多可以從兩個角度分類。

第一種是是否建立環境模型。

類型核心想法
Model-based先學習環境模型，再利用模型求解最佳 Policy。
Model-free不建立模型，直接學習 Value Function 或 Policy。

第二種則是學習目標。

類型目標
Passive RL已知 Policy，只需要評估每個 State 的 Utility。
Active RLPolicy 未知，需要同時學習最佳 Policy。

可以把四種演算法整理成下圖：

PassiveActive
Model-basedAdaptive Dynamic Programming (ADP)Active ADP
Model-freeMonte Carlo、TD LearningQ-Learning、SARSA

其中，Passive RL 最容易理解，因此我們先從這裡開始介紹。

Passive Reinforcement Learning

在 Passive RL 中，Agent 不需要決定該做什麼。

因為 Policy 已經給定。

例如，假設老師規定機器人只能：

  • 一直向右走。
  • 遇到牆壁就往下。

Agent 唯一需要學習的是這個 Policy 好不好？

也就是估計：

Uπ(s)E[∑tγtRt]U^\pi(s) E\left[ \sum_t \gamma^t R_t \right]

其中 π\pi 代表固定的 Policy。

因此，Passive RL 的問題，其實就是上一篇介紹的 Policy Evaluation（固定目前的 Policy，計算每個 State 的 Value）。

Model-Based：Adaptive Dynamic Programming（ADP）

第一種Passive RL 方法稱為 Adaptive Dynamic Programming（ADP）。

它的想法是：既然不知道 Transition Function，那就自己觀察。

Agent 在 State A 執行「向右」。

第一次到達 State B。

第二次仍然到達 State B。

第三次卻到 State C。

經過多次觀察後，

Agent 可以估計：

P(B|A,Right)=23P(B|A,\text{Right})=\frac23
P(C|A,Right)=13P(C|A,\text{Right})=\frac13

也就是利用 Experience 去近似整個 Transition Model。

當模型逐漸完整後，就可以再次使用上一篇介紹的 Bellman Equation、Value Iteration 或 Policy Iteration 求解 Utility。

因此，ADP 的特色就是：先學環境，再利用 MDP 演算法求解。

Model-Free：Monte Carlo Learning

如果連建立模型都不想做，另一種方法就是 Monte Carlo Learning。

Monte Carlo 完全不估計 Transition Function。

它只記錄每次 Episode 最後得到多少 Return。

例如某個 State 曾經出現三次：

  1. 第一次 Return = 12
  2. 第二次 Return = 10
  3. 第三次 Return = 14

那麼 Utility 就可以估計為：

U(s)=12+10+143=12U(s)= \frac{12+10+14}{3}= 12

也就是利用 Running Average，逐漸逼近真正的 Utility。

Monte Carlo 的優點是概念簡單，不需要知道任何環境模型。

但缺點也很明顯：必須等整個 Episode 結束後，才能更新 Utility。

如果 Episode 很長，學習速度就會變得非常慢。

Model-Free：Temporal Difference Learning

為了解決 Monte Carlo 更新太慢的問題，提出了 Temporal Difference Learning（TD Learning）。

TD Learning 不需要等 Episode 結束。

每走一步，就立刻更新 Utility。

其更新公式為：

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

其中：

括號中的部分稱為 TD Error。

它代表：新的觀察結果與目前估計值之間的差距。

如果新的觀察比原本預期更好，TD Error 就是正的，Utility 便會提高。

反之，如果實際結果比預期差，Utility 就會下降。

由於 TD Learning 每一步都能更新，因此通常比 Monte Carlo 收斂得更快，也成為許多現代 Reinforcement Learning 演算法的重要基礎。

小結

到目前為止，我們已經介紹了 Reinforcement Learning 的基本架構，以及 Passive Reinforcement Learning 的三種代表方法：

  • Adaptive Dynamic Programming（ADP）：先學習環境模型，再利用 MDP 求解 Utility。
  • Monte Carlo Learning：透過 Episode 的平均 Return 估計 Utility。
  • Temporal Difference Learning（TD）：利用每一步的觀察即時更新 Utility，因此學習速度更快。

不過，這些方法都有一個共同限制：Policy 是固定的。

如果 Agent 需要自己決定該採取哪一個 Action，又該如何一邊探索未知環境，一邊學會最佳策略？

下一篇，我們將介紹 Active Reinforcement Learning，並深入探討 Q-Learning、SARSA，以及 Reinforcement Learning 中最經典的問題：Exploration 與 Exploitation 的平衡。

Tags:

發表留言