# Reinforcement Learning
## Introduction
最基本的 RL 可以利用 Markov Decision Process 來描述，也就是有一個 set of states $S$ 、 a set of actions $A$ ，透過 action $a$ 從 state $s$ 轉移到 state $s'$ 的機率為 $P_a(s, s') = Pr(S_{t+1} = s' | S_t =s, A_t = a)$ ，並且定義從透過 $a$ 從 $s$ 轉移到 $s'$ 的獎勵是 $R_a(s, s')$ 。 RL 、 supervised-learning 和 unsupervised-learning 可以將機器學習方法分類為這三大類，其他 RL 特別適合用來解決一些難以做 label 並且人類不知道正確答案為何的問題。以下我們先從數學角度切入試圖理解 RL 。
## Markov Decision Process
### Markov Property
Describe the **memoryless property** of a stochastic process, **it's future evolution is independent of its history**. 描述成數學式為以下
$$
Pr(X_n = x_n | X_{n-1} = x_{n-1} , \cdots , X_0 = x_0) = Pr(X_n = x_n | X_{n-1} = x_{n-1})
$$
### Discrete-time Markov Chain
描述 a sequence of random variable $X_1, X_2, \cdots$ with Markov Property ，也就是如果 $Pr(X_1 = x_1, \cdots, X_n = x_n) > 0$ 則 $Pr(X_{n+1} = x | X_1 = x_1, X_2 = x_2, \cdots, X_n = x_n) = Pr(X_{n+1} = x | X_n = x_n)$ 。
白話的描述即是從當前狀態轉移到下一個狀態的機率只依賴當前的狀態，而跟之前任何狀態都無關。
這些 random variable 的集合 $S$ 又可以稱為 state space of the chain ，並且是**可數集**。
當 $S$ 為**有限**時 ，則轉移的機率分佈可以被定義為 **Transition matrix** $P$ 滿足
$$
p_{ij} = Pr(X_{n+1} = j | X_n = i)
$$
每個 row 的和會是 1 ，且 $P$ 是一個 right stochastic matrix 。
### Markov decision process
一個 MDP 可以用一個 4-tuple 來描述， $(S, A, P_a, R_a)$ ，其中
* $S$ : state space
* $A$ : action space ($A_s$ 代表從 $s$ 開始的 available action set)
* $P_a(s, s') = Pr(s_{t+1} = s' | s_t = s, a_t = a)$
* $R_a(s, s')$ : Reward

如果我們把每個狀態轉移到下一個狀態會採取的動作固定，則 MDP 會收斂成一個 Markov chain ，其中每個 Markov chain 都可以計算出一組 discount sum 定義如下
$$
E[\sum_{t=0}^{\infty} \gamma^t R_{a_t}(s_t, s_{t+1})], 0 \le \gamma \le 1
$$
Markov Decision Process 的目標是找到一個函式 $\pi : S \rightarrow A$ 使得對應產生的 Markov chain 有最大的 discount sum 。 $\pi(s) = a$ ，代表狀態 $s$ 會採取動作 $a$ 。其中一種解法是利用 DP 也就是動態規劃，定義兩個陣列 $V(s), \pi(s)$ 分別如下
* $V(s)$ : 依照該解一路轉變成狀態 $s$ 的 discount sum
* $\pi(s)$ : action solution

遞迴式如下
$$
V(s) = \sum_{s'} P_{\pi(s)}(s, s')(R_{\pi(s)}(s, s') + \gamma V(s'))
$$
$$
\pi(s) = \ argmax_a \{ \sum_{s'} P_a(s, s')(R_a(s, s') + \gamma V(s')) \}
$$

## RL Algorithm
RL 即是 MDP 的一種，在機率分佈和 reward 都未知的狀況下，嘗試最大化以下函式
$$
Q(s, a) = \sum_{s'}P_a(s, s')(R_a(s, s') + \gamma V(s'))
$$
利用每個 $(s, a)$ pair 來學習，以下詳細解說學習的演算法

### Algorithm Details
RL 最主要的精神在於利用它之前的經驗來判斷下一個動作該做什麼以獲得最高的 reward 。
* **policy**
$\pi : A \times S \rightarrow [0, 1]$ , $\pi(a, s) = Pr(A_t = a | S_t = s)$ ，代表在狀態 $s$ 底下採取動作 $a$ 的可能性。
* **state-value function**
$V_{\pi}(s) = E[G | S_0 = s] = E[\sum_{t=0}^{\infty} \gamma^t R_{t+1} | S_0 = s] , G = \sum_{t=0}^{\infty} \gamma^r R_{t+1}$
$V_{\pi}(s)$ 代表從狀態 $s$ 開始的 expected discounted return