最近因為在探討新的研究方向，所以開始踏入了 Reinforcement Learning (以下簡稱 RL) 的領域。 這篇文章記錄了我學習 RL 的過程與理解，以供需要其他打算學習 RL 的人參考。
RL 問題簡介
RL 問題指的是設計一個策略 (policy)，讓他取得當下環境的狀態 (state)，來決定要做什麼樣動作 (action)，以讓我們最後使用該策略可以取得最大的總報酬 (total reward) 的問題。RL 可以拿來解決許多實務的問題，例如走迷宮、下圍棋、打遊戲、自動駕駛車等等。
更正式來說，一個 RL 問題包含以下幾個要素：
- State $s^{(t)}$：在一個環境中時間 $t$ (或是稱為第 $t$ 步) 的狀態，隨時間改變
- 一般假設環境本身不會改變，例如迷宮的路是固定的，狀態則代表人在迷宮的位置等等資訊。
- Action $a^{(t)}$：在時間 $t$ 採取的行動
- Reward $R^{(t)}$：在時間 $t$ 採取行動之後取得的報酬
目標：找到一個策略 policy $\pi$，以取得最大的總和報酬 (total reward)： $\Sigma_t R^{(t)}$。
Markov Decision Processes
Reinforcement Learning 為了方便計算，一般會假設問題是一個 Markov Decision Processes (以下簡稱 MDP)。
MDP 假設
首先我們先假設要解決的問題之中的 state 的序列是一個 Markov Process。意思就是一個 state $s^{(t)}$ 出現的機率只跟它的上一個 state $s^{(t-1)}$ 有關，而跟更早之前的 state 無關。換句話說，考慮了之前所有狀態跟只考慮當下狀態的基礎上，下一個狀態的機率分布是相同的。寫成數學式如下：
$$
P(s^{(t+1)}|s^{(t)},s^{(t-1)},…)=P(s^{(t+1)}|s^{(t)})
$$
如果這個假設成真，解 RL 問題時就可以不需要考慮更早之前的狀態，只要關注當下的狀態就好。
而 Reinforcement Learning 則是在解 Markov Decision Process，也就是 state 的變換是在我們的控制中的 Markov Process。
基本要素
一個 Markov Decision Process 包含以下幾個基本要素與符號：
- State space $\mathbb{S}$: 定義所有可能出現的 state
- Action space $\mathbb{A}$: 定義所有可能的 action
- Initial state $s^{(0)}$: 初始狀態
- Transition distribution $P(s’|s;a)$: 給定狀態 $s$ 與動作 $a$ 之後，某一個狀態 $s’$ 出現的機率
- 這個要特別注意。一般會以為我在某個時間點做了一個動作就一定會轉換到想要的狀態，然而實際上可能會有些意外發生。例如我在橋上往前走，除了前進之外可能也會不小心掉到橋下 (雖然我選擇的動作是前進)。這個 distribution 其實考慮了現實生活中的隨機性。
- 這邊假設這個 distribution 在給定相同狀態與動作時都是固定的，不隨時間改變。
- Deterministic reward function $R(s, a, s’)$: 在狀態 $s$ 時做了動作 $a$ 轉換到狀態 $s’$ 獲得的報酬 (reward)
- Discount factor $\gamma \in [0,1]$: 折扣係數
- 用來降低越晚得到的 reward 帶來的效果 => 越早拿到 reward 越好
- Horizon $H \in \mathbb{N}$: 步數的上限
因此總報酬 total reward 可以寫成以下式子：
$$
R(s^{(0)}, a^{(0)}, s^{(1)}) + \gamma R(s^{(1)}, a^{(1)}, s^{(2)}) + … + \gamma^{H-1} R(s^{(H-1)}, a^{(H-1)}, s^{(H)})
$$
MDP 目標
假設我們把策略 policy 用一個 function $\pi$ 表示，其中 $\pi$ 給定一個狀態可以告訴我們下一個動作該做甚麼。那它的預期總報酬 $V_\pi$ 可以寫成：
$$
V_\pi = E_{s^{(0)},…,s^{(H)}}(\sum^H_{t=0}\gamma^t R(s^{(t)}, a^{(t)}, s^{(t+1)});\pi)
$$
其中 $a^{(t)} = \pi(s^{(t)})$
這邊使用期望值表示是因為執行一個動作並不一定會轉換到想要的 state，而是由一個 transition distribution $P$ 決定。所以必須要用期望值來代表有考慮到其他可能性。
MDP 的目標就是要找到可以得到最大期望總報酬 (total reward) 的最佳的 policy $\pi^*$：
$$
\pi^* = \arg \max_\pi V_\pi
$$
關於下一份筆記
接下來會寫兩種找到最佳 policy 的基本作法：value iteration 與 policy iteration。
參考資料
以上筆記為我看清華大學資訊工程學系的吳尚鴻教授的 CS565600 深度學習課程第 16 課，再轉化成我的理解記錄下來，有興趣的人可以直接看課程：