Deep Learning - Reinforcement Learning

Reinforcement Learning

• Agent 在環境 (environment) 中採取行動 (actions) 以最大化累積獎勵 (reward)。
• 狀態 (state) $s_t$、行動 $a_t$、獎勵 $r_t$。
• 目標: 學習策略 (policy) $\pi(a|s)$ 以最大化期望累積獎勵

Compared to Supervised / Unsupervised Learning

• 資料 $s_t$ 不是獨立同分佈 (i.i.d.)，而是依賴於先前的行動和狀態。
• 沒有明確的標籤 (labels)，只有獎勵信號 (reward signal)。

Markov Decision Process (MDP)

Markov Property

• 未來狀態只依賴於當前狀態和行動，而不依賴於過去的狀態和行動。

  $$
  P(s_{t+1} | s_t, a_t) = P(s_{t+1} | s_1, a_1, \ldots, s_t, a_t)
  $$

MDP

• 狀態空間 $S$、行動空間 $A$
• 開始狀態 $s_0$
• $P(s’|s,a)$: 狀態轉移分佈
• $R(s,a,s’) \in \mathbb{R}$: 獎勵函數
• $\gamma \in [0,1]$: 折扣因子 (discount factor)，控制未來獎勵的重要性
• $H \in \mathbb{N}$: horizon，決定任務的長度，有限或無限

Reward 計算:

$$
R(s^{(0)} , a^{(0)} , s^{(1)} ) + \gamma R(s^{(1)} , a^{(1)} , s^{(2)} ) + \ldots + \gamma^{H-1} R(s^{(H-1)} , a^{(H-1)} , s^{(H)} )
$$

• $\gamma$ 讓 reward 越早走到目標越好

目標:

$$
V_\pi = E_{s^{(0)}, \ldots , s^{(H)} \sim \pi} \left[ \sum_{t=0}^H \gamma^t R(s^{(t)} , \pi(s^{(t)}) , s^{(t+1)}; \pi ) \right]
$$

$$
\pi^* = \arg\max_\pi V_\pi
$$

Optimal Value Function

$$
V^{*(h)}(s) = \max_\pi E_{s^{(1)}, \ldots , s^{(h)} \sim \pi} \left[ \sum_{t=0}^h \gamma^t R(s^{(t)} , \pi(s^{(t)}) , s^{(t+1)} ) | s^{(0)} = s; \pi \right]
$$

假設我現在有 $V*(h-1)$，要怎麼算 $V*(h)$？

$$
\pi^*(s) = \arg\max_a \sum_{s’} P(s’|s,a) [ R(s,a,s’) + \gamma V^{*(h-1)}(s’) ], \forall s
$$

• Time complexity: $O(|S||A|)$
• Dynamic Programming

Bellman Equation

$$
V^*(s) = \max_a \sum_{s’} P(s’|s,a) [ R(s,a,s’) + \gamma V^*(s’) ], \forall s
$$

• 無限 horizon 下的最優值函數
• Stationary policy
  • 不隨時間改變
• Memoryless policy
  • 只依賴當前狀態

Convergence

$$
\begin{aligned}
V^{(s)} - V^{(H)}(s) &= \gamma^{H+1} R(s^{(H+1)}, a^{(H+1)}, s^{(H+2)}) + \gamma^{H+2} R(s^{(H+2)}, a^{(H+2)}, s^{(H+3)}) + \ldots \newline
& \leq \gamma^{H+1} R_{max} + \gamma^{H+2} R_{max} + \ldots \newline
&= \frac{\gamma^{H+1}}{1 - \gamma} R_{max} \newline
\end{aligned}
$$

當 $H \to \infty$ 時，$V^{(H)}(s) \to V^(s)$。

Value Iteration

• 初始化 $V_0(s) = 0, \forall s$

• 重複以下更新直到收斂:

  $$
  V_{k+1}(s) = \max_a \sum_{s’} P(s’|s,a) [ R(s,a,s’) + \gamma V_k(s’) ], \forall s
  $$

  • 收斂到最優值函數 $V^*(s)$

• 可以用來計算最優策略:
  $$
  \pi^*(s) = \arg\max_a \sum_{s’} P(s’|s,a) [ R(s,a,s’) + \gamma V^*(s’) ], \forall s
  $$

Policy Iteration

先解決 Value Function，再更新 Policy。

$$
V_\pi(s) = \sum_{s’} P(s’|s,\pi(s)) [ R(s,\pi(s),s’) + \gamma V_\pi(s’) ], \forall s
$$

• 用線性方程組解 $V_\pi$，Time complexity: $O(|S|^3)$
• Dynamic Programming

找到一個 $\pi’$ 使得 $V_{\pi’}(s) \geq V_\pi(s), \forall s$：

$$
\pi’(s) = \arg\max_a \sum_{s’} P(s’|s,a) [ R(s,a,s’) + \gamma V_\pi(s’) ], \forall s
$$

Reinforcement Learning

Model-based RL

• 很多情況不能用 MDP 解決，因為不知道 $P(s’|s,a)$ 和 $R(s,a,s’)$。
• 透過與環境互動來 explore samples，來 estimate $P$ 和 $R$。
• 接著用估計的 $P$ 和 $R$ 來做 value/ Policy Iteration。
• exploit-explore trade-off
  • exploitation: 利用已知資訊來最大化獎勵
  • exploration: 探索未知狀態以獲取更多資訊

問題是 estimate 的 $P$ 和 $R$ 可能樣本不足，根本不準確

Model-free RL

• 不估計 $P$ 和 $R$，直接學習 Value Function 或 Policy

Q-Learning

• 學習 action-value function (Q-function) $Q(s,a)$

• Bellman Equation for Q-function:

  $$
  Q^*(s,a) = \sum_{s’} P(s’|s,a) [ R(s,a,s’) + \gamma \max_{a’} Q^*(s’,a’) ], \forall s,a
  $$

• SARSA

  • on-policy
  • 可以避免 mistake

• Q-Learning

  • off-policy
  • 收斂速度較快

• 兩者需要的空間非常大，無法應用在大型 state space，$O(|S||A|)$

Deep Reinforcement Learning

• 使用深度神經網路來近似 Q-function 或 Policy

Deep Q-Network (DQN)

• 使用神經網路 $Q(s,a;\theta)$ 來近似 Q-function
• Naive TD algorithm 會 diverge
  • 因為目標值和參數同時更新，導致不穩定
  • Sample correlation 也會導致不穩定
• DQN 解決方法:
  • Experience Replay
    • 儲存 agent 的經驗 $(s_t, a_t, r_t, s_{t+1})$ 在 replay buffer 中
    • 隨機抽樣 mini-batch 來更新網路，打破樣本相關性
  • Delayed Target Network
    • 使用一個固定的目標網路 $Q(s,a;\theta^-)$ 來計算目標值
    • 每隔一段時間才更新目標網路的參數 $\theta^- = \theta$
  • Reward Clipping
    • 將獎勵限制在一個範圍內，避免過大或過小的獎勵影響學習穩定性

Imporvements since DQN

Double DQN

• 解決 DQN 過度估計 Q-value 的問題
• 使用兩個網路來分離行動選擇和行動評估
• 目標值計算:
  $$
  y = r + \gamma Q(s’, \arg\max_{a’} Q(s’, a’; \theta); \theta^-)
  $$

Prioritized Replay

• 改進 Experience Replay，優先抽樣重要的經驗
• Rank-based prioritization
• Proportional prioritization
  $$
  | R + \gamma \max_{a’} Q(s’, a’; \theta^-) - Q(s, a; \theta) |
  $$

Dueling DQN

• 將 Q-function 分解為 state-value function 和 advantage function
• 網路結構:
• 兩個分支:
  • Value 分支: $V(s; \theta, \beta)$
  • Advantage 分支: $A(s,a; \theta, \alpha)$
• 合併方式:
  $$
  Q(s,a; \theta, \alpha, \beta) = V(s; \theta, \beta) + \left( A(s,a; \theta, \alpha) - \frac{1}{|A|} \sum_{a’} A(s,a’; \theta, \alpha) \right)
  $$

NoisyNet

• 在神經網路中加入可學習的噪聲，促進探索
• 替代 $\epsilon$-greedy 策略

Policy Gradient Methods

• 直接學習策略 $\pi(a|s;\theta)$
• 透過最大化期望累積獎勵來更新參數 $\theta$
• REINFORCE algorithm
  $$
  \nabla_\theta J(\theta) = E_{\pi} \left[ \nabla_\theta \log \pi(a|s;\theta) Q^{\pi}(s,a) \right]
  $$
• Actor-Critic Methods
  • Actor: 學習策略 $\pi(a|s;\theta)$
  • Critic: 學習價值函數 $V(s;w)$
  • 更新方式:
  • Actor:
    $$
    \nabla_\theta J(\theta) = E_{\pi} \left[ \nabla_\theta \log \pi(a|s;\theta) (r + \gamma V(s’;w) - V(s;w)) \right]
    $$
  • Critic:
    $$
    w \leftarrow w + \alpha (r + \gamma V(s’;w) - V(s;w)) \nabla_w V(s;w)
    $$