RL Fundamentals

What You Should Understand

• 能用 MDP framework 描述一個 RL 問題
• 理解 Bellman equation 和 value function 的意義
• 知道 value-based vs policy-based methods 的差異
• 能解釋 exploration vs exploitation tradeoff
• 了解 RL 和 supervised learning 的根本差異

RL vs Supervised Learning

Markov Decision Process (MDP)

Components

An MDP is defined by a tuple $(S, A, P, R, \gamma)$:

The Markov Property

The future depends only on the current state, not on how we got here. 這大幅簡化了問題 — 不需要記住完整歷史。

面試中的常見 challenge：「什麼時候 Markov property 不成立？」— 當 state representation 不完整時（例如在推薦系統中只看 current page 而沒有 browsing history → 需要用 history 作為 state 的一部分）。

Discount Factor $\gamma$

$\gamma < 1$ 確保 infinite sum converges，也反映了 uncertainty（未來越遠越不確定）和 time preference（現在的 reward 比未來的更有價值）。

Policy

A policy $\pi$ maps states to actions:

• Deterministic: $a = \pi(s)$
• Stochastic: $a \sim \pi(a \mid s)$

RL 的 goal: find the optimal policy $\pi^*$ that maximizes expected cumulative reward。

Value Functions

State-Value Function $V^\pi(s)$

Expected cumulative reward starting from state $s$, following policy $\pi$:

「在 state $s$，如果我一直按 policy $\pi$ 做決策，期望能拿到多少 total reward？」

Action-Value Function $Q^\pi(s, a)$

Expected cumulative reward starting from state $s$, taking action $a$, then following $\pi$:

「在 state $s$ 做 action $a$，然後一直按 $\pi$ 做，期望能拿到多少 total reward？」

Relationship

$V$ = averaged over all actions according to policy。$Q$ = specific to a particular action。

Bellman Equations

Bellman Expectation Equation

$V$ and $Q$ satisfy recursive relationships:

直覺：current value = immediate reward + discounted future value。把 long-term planning 分解成 one-step lookahead。

Bellman Optimality Equation

For the optimal policy $\pi^*$:

$V^*$ 取 max（選最好的 action），不是 average over policy。如果知道 $Q^*$，optimal policy 就是 $\pi^*(s) = \arg\max_a Q^*(s, a)$。

Value-Based Methods

Q-Learning (Off-Policy)

Learn $Q^*$ directly without knowing the transition model:

Off-policy: Updates use $\max_{a'}$（best possible action），不管 agent 實際做了什麼 action。所以可以 explore freely（例如用 $\epsilon$-greedy）但仍然 learn the optimal Q。

SARSA (On-Policy)

$a'$ 是 agent 實際選的 action（according to current policy），不是 $\max$。

On-policy: Updates based on what the agent actually does → learns the value of the current policy（包括 exploration 的 cost）。

Q-Learning vs SARSA

Deep Q-Network (DQN)

When state space is too large for a table → use a neural network to approximate $Q(s, a; \theta)$:

Key innovations (Mnih et al., 2015):

import torch
import torch.nn as nn

class DQN(nn.Module):
    def __init__(self, state_dim, action_dim):
        super().__init__()
        self.net = nn.Sequential(
            nn.Linear(state_dim, 128), nn.ReLU(),
            nn.Linear(128, 128), nn.ReLU(),
            nn.Linear(128, action_dim),  # output Q(s, a) for each action
        )

    def forward(self, state):
        return self.net(state)  # [batch, action_dim]

# Select action: epsilon-greedy
def select_action(state, q_net, epsilon):
    if random.random() < epsilon:
        return random.randint(0, action_dim - 1)  # explore
    with torch.no_grad():
        return q_net(state).argmax().item()  # exploit

Policy-Based Methods

Why Not Just Q-Learning?

REINFORCE (Monte Carlo Policy Gradient)

Directly optimize the policy $\pi_\theta(a \mid s)$ by gradient ascent on expected return:

• $G_t$ = total return from time step $t$ onwards
• $\nabla_\theta \log \pi_\theta$ = score function — direction to update policy
• 直覺：如果 action $a$ 得到 high return → increase $\pi(a \mid s)$。Low return → decrease。

Problem: $G_t$ has very high variance（depends on entire future trajectory）→ slow convergence。

Baseline and Advantage

Subtract a baseline $b(s)$ to reduce variance without introducing bias:

Natural choice for baseline: $V(s)$。

Advantage function: $A(s, a) = Q(s, a) - V(s)$ — how much better is action $a$ compared to the average。

$A > 0$ → action 比平均好 → increase probability。$A < 0$ → worse than average → decrease。

Actor-Critic

Combine the best of both worlds:

• Actor (policy $\pi_\theta$): Decides which action to take
• Critic (value $V_\phi$): Evaluates how good the action was

Actor: π_θ(a|s) → action
          ↓
    Environment → reward, next state
          ↓
Critic: V_ϕ(s) → evaluate (compute advantage)
          ↓
    Update actor using advantage
    Update critic using TD error

A2C / A3C

Advantage Actor-Critic (A2C):

• Critic estimates $V(s)$
• Advantage = $r + \gamma V(s') - V(s)$（TD error as advantage estimate）
• Actor updates: $\nabla_\theta J \propto \nabla_\theta \log \pi_\theta(a \mid s) \cdot A$

A3C (Asynchronous): Multiple agents explore in parallel → faster + more diverse experience。

PPO (Proximal Policy Optimization)

The de facto standard for modern RL:

where $r_t(\theta) = \frac{\pi_\theta(a \mid s)}{\pi_{\theta_{\text{old}}}(a \mid s)}$ = probability ratio。

核心思想：限制 policy update 的幅度 → 避免 catastrophic policy collapse → 比 vanilla policy gradient 穩定得多。

PPO 被用在 ChatGPT 的 RLHF（Reinforcement Learning from Human Feedback）中。

Exploration vs Exploitation

Reward Design

Reward design 是 RL 中最重要也最困難的部分：

Common Pitfalls

Reward Shaping

Add intermediate rewards to guide learning without changing the optimal policy:

where $\Phi$ is a potential function。只要 shaping reward 是 potential-based → optimal policy 不變（只加速 learning）。

Real-World Use Cases

Case 1: 推薦系統 — RL for Sequential Recommendation

推薦不是 one-shot classification — 而是 sequential decisions：

面試 follow-up：「為什麼不用 supervised learning？」— Supervised learning 只 optimize one-step prediction。RL considers long-term: 推薦 clickbait → immediate clicks ↑ but user leaves platform → long-term value ↓。RL 可以 learn to sacrifice short-term clicks for long-term retention。

Case 2: 廣告出價 — Dynamic Bidding

RL 可以學到 dynamic bidding strategy — 根據 remaining budget 和 expected ROI 調整出價，比 fixed-bid 策略更有效率。

Case 3: RLHF — ChatGPT 的訓練

RLHF 的 reward = human preference（比 next-token prediction 更 aligned with user intent）。PPO 的 clipping 機制確保 GPT 不會偏離 SFT 太多。

Method Comparison

Hands-on: RL in Python

Q-Learning (Tabular)

import numpy as np

class QLearning:
    def __init__(self, n_states, n_actions, lr=0.1, gamma=0.99, epsilon=0.1):
        self.Q = np.zeros((n_states, n_actions))
        self.lr = lr
        self.gamma = gamma
        self.epsilon = epsilon

    def select_action(self, state):
        if np.random.random() < self.epsilon:
            return np.random.randint(self.Q.shape[1])  # explore
        return self.Q[state].argmax()  # exploit

    def update(self, state, action, reward, next_state):
        td_target = reward + self.gamma * self.Q[next_state].max()
        td_error = td_target - self.Q[state, action]
        self.Q[state, action] += self.lr * td_error

DQN (PyTorch)

import torch
import torch.nn as nn
from collections import deque
import random

class ReplayBuffer:
    def __init__(self, capacity=10000):
        self.buffer = deque(maxlen=capacity)

    def push(self, state, action, reward, next_state, done):
        self.buffer.append((state, action, reward, next_state, done))

    def sample(self, batch_size):
        return random.sample(self.buffer, batch_size)

class DQN(nn.Module):
    def __init__(self, state_dim, action_dim):
        super().__init__()
        self.net = nn.Sequential(
            nn.Linear(state_dim, 128), nn.ReLU(),
            nn.Linear(128, 128), nn.ReLU(),
            nn.Linear(128, action_dim),
        )

    def forward(self, x):
        return self.net(x)

# Training: sample batch from replay buffer → compute TD loss → update

Interview Signals

What interviewers listen for:

• 你能用 MDP framework 描述一個 real-world 問題（states, actions, rewards）
• 你知道 Bellman equation 的直覺（current value = immediate reward + discounted future value）
• 你能區分 value-based 和 policy-based methods 的適用場景
• 你理解 exploration vs exploitation 的 tradeoff 和常見策略
• 你知道 RL 和 supervised learning 的根本差異

Practice

Flashcards

Quiz