(1/3) 強化學習 Reinforcement Learning (RL) 介紹
— — 強化學習簡介、應用案例，與 MDP 馬可夫決策過程
前言
本文為筆者參加由國立清華大學、國立成功大學、與 Google 合作舉辦的 2022 Fun AI Camp 時所記錄的筆記。此為「強化學習 Reinforcement Learning (RL) 介紹」的第一篇筆記。
課程筆記會比較制式一點，活動中還有 Game AI 卡丁車的小組競賽，希望有機會也來寫成文章分享！
活動中其他課程筆記連結：
- （寫完回來放）
目錄
一、系列文章架構介紹
說明建立於馬可夫決策過程之上，不同強化學習的方法與關聯介紹。
二、強化學習的定義與應用範例
此段落介紹強化學習的基本運行方法，以及訓練時需考量的因素等。段落後也有實際應用案例介紹。
三、MDP (Markov Decision Process, 馬可夫決策過程)
本篇最後段落介紹馬可夫鏈的概念、馬可夫決策過程的基本要素、以及如何應用於強化學習中。
一、系列文章架構介紹
如下圖課程大綱，本系列文章將會由最左上角的 MDP (Markov Decision Process, 馬可夫決策過程) 出發，按照不同的學習條件一個個講解至右下角。
在上述以 MDP（後面會再介紹到）為基礎的架構下，被定義為強化學習的首要條件是第一層的：轉移機率是否已知。
Transition Probability (轉移機率)，以 P(s’|s, a) 表示，用來形容在特定狀況 (s) 下，特定行動 (a) 可以促使轉移至下一個狀況 (s’) 的機率。如果知道不同行動與狀態間的發生機率，則稱轉移機率已知。
P(s’|s, a) 已知：DP (Dynamic Programming, 動態規劃)
轉移機率已知下所使用的解題方法稱為「動態規劃」。是一種在數學、管理科學、電腦科學、經濟學、和生物資訊學中，常用的將原問題分解為相對簡單子問題的方法。
P(s’|s, a) 未知：RL (Reinforcement Learning, 強化學習)
未知的狀況下就是強化學習的問題。必須以 sample 的方式，模擬環境資訊作為 training data 做訓練。也是本系列文章的說明重點。
強化學習下還有不同分支，包括：
- 是否測量轉移機率（是則為 Model-based，否則為 Model-free）
- 基於價值 (Value-based，代表演算法：Q-Learning, DQN)；或是基於策略 (Policy-based，代表演算法：Policy Gradient, PPO, PPO2)
- 此外也有結合 Value-based 與 Policy-based 的 Actor-Critic 方法（代表演算法：A2C, A3C）
而目前不直接測量的 Model-free 是較主流的方法，也因此本系列文章會較為著重介紹右下角 Model-free 下的各個部分。
二、強化學習的定義與應用案例
強化學習 (Reinforcement Learning, RL) 是機器學習一個領域，用以研究「主體 (Agent) 」如何與「環境 (Environment)」 互動。
如下圖，強化學習可以計算在每個離散的時步 (discrete time step) 上的 ENDY (Environment Dynamics, 動態環境：即持續在變化的環境資料)，以考慮未來狀態並做出決策/行動 (action)，終而達到設定目標。
如訓練資料會在與環境的互動中，透過環境回饋的「觀察 (Observation)」與「獎勵 (Reward)」取得。
Observation 為環境狀態，用以讓 agent 進行下一步決策；Reward 則是為了讓 agent 做出最佳化解答，通常為手動設置，也有其他應用如吃到金幣可以加分，吃到烏龜則扣分等。
整體運作流程為：
- agent 執行 action
- action 根據 environment 狀態，拿到 observation & reward
- agent 再根據 observation，繼續選下一個 action
在訓練過程中，需考量的問題有三：
1.【Uncertainty】 — — 未來事件通常是隨機的 (stochastic)
後面會提及由 Transition Probability 模擬 Uncertainty
2.【Temporal Relation】 — — 需考慮未來的狀態來做現在的決策
如下圖，直接往右推的速率不夠，無法觸及目標。正確解法是要先往左推使其加速。
3.【Exploration】 — — agent 要先四處探索才能知道如何達到目標
如上圖例子，在隨機探索環境中走上左邊的坡，才會發現解法。
應用案例部分，強化學習很常被用來玩遊戲。如下方影片是訓練模型在 Atari 遊戲平台中打磚塊的範例。可以看到隨著訓練，越來越能夠準確接到球：
另外也有物理的 Physics-Based Control 應用案例，讓兩腳人在不同介質的地面上都可以好好走路不要倒下（如果不控制兩腳人移動，站在原地是會倒下的）：
也有這種，筆者覺得滿酷的，exploration 的問題（探測器前面的紅線可以視作紅外線，可以讓 agent 知道自己與周邊障礙物的距離，進而達到目標）：
三、MDP (Markov Decision Process, 馬可夫決策過程)
MDP 是強化學習 (RL) 中最基本的假設，課程大綱中所列的各種方法都基於 MDP 進行實作。
MDP 基於「Markov Chain (馬可夫鏈)」，用以研究「一連串隨機事件可能組合成的系統，會如何隨著時間變化」
如上圖，同色相加機率為 1，線上數字則代表由一個事件轉移至下一事件的機率。
在數學中表現方式如下圖。鉛筆所指處意思為：從位置 Sa 到 Sb 的機率，記作 P(Sb|Sa)。
需要留意的是，現有狀態僅取決於「前一狀態」：
在馬可夫鏈的概念基礎上，馬可夫決策過程 (MDP) 的目標就是做出一系列能夠達到目標的決策，也就是在每一個「時步/時間點 (time step)」做出一個「決策/行為 (action)」。
數學表現式如下：
- 每一個回合 (episode) 中：時間從 t=0 到 t=T（T 可以為 ∞）
- 每一個時步 (time step) 中：都有一個狀態 sₜ和要做的行動 aₜ
而訓練的目標是要「最大化總獎勵 (maximize total reward)」
接下來以 Grid World 遊戲作為範例，介紹 MDP 馬可夫決策過程。
1.【策略 (Policy) 】
目標是要讓圖片中角色拿到寶箱並不要觸碰尖刺。可以透過生成如下右圖中的「策略 (policy)」達到，即位於哪一個方塊上，就按該方塊上的箭頭行動。這也是我們在訓練時希望達到的最終目標。
2.【狀態 (State)】
State 描述的是目前狀態，但不一定是環境下的所有資訊，而可以設定為想要觀察的特定參數。舉例而言，在賽車的例子中就可能是車子的位置、速度、與旋轉角度等。
定義上會說：s ∈ S，即 state 屬於 state space。
state space 指的是所有可能存在的狀態，在 Grid World 的案例中，指的就是如下圖 4x3 的格子。
3.【行動 (Action)】
action 指的是在遊戲中可以做的任何行為，以 Grid World 為例，可以做的事有四種：往上下左右四個方向走。
可以的所有選項也被稱為 action space。定義上會說：a ∈ A，即 action 屬於 action space。
4.【獎勵 (Reward)】
Reward 是一個 state 跟 action 的函數，即 r(sₜ,aₜ)。可以被視作用來引導 agent 做出正確決策的提示。
如下圖所示，寶物 (+1) 與尖刺 (-1) 以外的方塊都被定義為 -0.01，在目標是要最大化 reward 總值的前提下，就可以避免 agent 在原地踏步或繞遠路。
5.【轉移機率 (Transition Probability)】
Transition Probability 用來形容每一個行動各自可能發生的機率，必需模擬未來的不確定，是非常重要的一個參數。
定義上表示為：s’ ~ P(s’|s, a)，即在既有的 state 與 action 下，會轉移到下一個 state (s’) 的機率為何。
以下圖範例而言，可以看到 agent 往上轉移至 S₂,₁ 的機率為 0.8、往左往右轉移至 S₃,₀ 與 S₁,₀ 的機率分別是 0.1，轉移至其他方塊的機率則為 0。
6.【折扣因子 (Discount Factor)】
Discount Factor 是一個介於 0 與 1 之間的數，乘在每一項的 reward 前面。用途有二：
- 為了確認 total reward 有辦法收斂；
- 確保盡快拿到 reward：現在這一步拿到更多 reward，比走了兩步之後才拿到 reward 重要。
7. 回到【策略 (Policy)】
如第 1 點提及，Policy 是希望形成的最終目標，用以指示 agent 做出最佳行動。而 Policy 又分為兩種：
- 確定性 (Deterministic)：在哪一個位置就做出什麼樣的相應行動。
- 隨機性 (Stochastic)：根據 state 取樣 (sample) 可能採取的 action。以下方右圖為例，紅色箭頭即為在每一個 state 下最有可能採取的 action。
後者隨機性的方法可拆分為兩個步驟：
- 在走到一個 state 時，會先 sample 一次 action；
- 接著再根據前方提到的 Transition Probability，以已知的 state 與 action 再 sample 下一步的 state。
即動作中會有兩次 sample。
以上為「強化學習 Reinforcement Learning (RL) 介紹」的第一篇筆記，後續筆記連結可見：
- （寫完回來放）
感謝您的閱讀！
