Q-Learning

Q-Learning là thuật toán RL học giá trị $Q(s, a)$— "hành động a tại state s tốt đến đâu?" — từ trải nghiệm (off-policy, model-free). Khi state space quá lớn (hình ảnh, game), Q-table được thay bằng neural network — xem Deep Q-Network (DQN). Một nhánh khác là học trực tiếp policy thay vì value function — xem Policy Gradient.

Phương trình Bellman tối ưu:

Quy tắc cập nhật Q-Learning:

Trong đó:

• $\alpha$ — learning rate, kiểm soát tốc độ cập nhật.
• $\gamma$ — discount factor, đo mức độ quan trọng của reward tương lai.
• $r_t$ — reward nhận được khi chuyển từ $s_t$ sang $s_{t+1}$.
• $\epsilon$ — xác suất explore trong epsilon-greedy.

Điều kiện hội tụ: Q-Learning hội tụ tới $Q^{*}$ với xác suất 1 nếu:

• Mọi (s, a) được thăm vô hạn lần.
• Learning rate thoả $\sum \alpha_t = \infty, \sum \alpha_t^2 < \infty$.
• State và action rời rạc, hữu hạn.

Thực tế: state lớn → cần xấp xỉ hàm (neural network), mất bảo đảm hội tụ nhưng thường vẫn work tốt.

import numpy as np

GRID = 5
N_ACTIONS = 4              # Up, Right, Down, Left
DELTAS = [(-1, 0), (0, 1), (1, 0), (0, -1)]

WALLS = {(1, 1), (1, 3), (2, 1), (3, 2), (3, 3)}
TRAPS = {(2, 3)}
GOAL = (4, 4)
START = (0, 0)


def step(r: int, c: int, a: int) -> tuple[int, int, float, bool]:
    dr, dc = DELTAS[a]
    nr, nc = r + dr, c + dc
    # Biên và tường
    if not (0 <= nr < GRID and 0 <= nc < GRID) or (nr, nc) in WALLS:
        nr, nc = r, c
    # Reward
    if (nr, nc) == GOAL:
        return nr, nc, 10.0, True
    if (nr, nc) in TRAPS:
        return nr, nc, -5.0, False
    return nr, nc, -0.1, False


def select_action(q: np.ndarray, r: int, c: int, eps: float) -> int:
    if np.random.rand() < eps:
        return np.random.randint(N_ACTIONS)
    return int(np.argmax(q[r, c]))


def train(episodes: int = 1000) -> np.ndarray:
    q = np.zeros((GRID, GRID, N_ACTIONS))
    alpha, gamma = 0.3, 0.95
    eps, eps_min, eps_decay = 0.4, 0.05, 0.995

    for ep in range(episodes):
        r, c = START
        for _ in range(200):  # giới hạn bước
            a = select_action(q, r, c, eps)
            nr, nc, reward, done = step(r, c, a)
            # ── Bellman update ──
            td_target = reward + gamma * q[nr, nc].max()
            q[r, c, a] += alpha * (td_target - q[r, c, a])
            r, c = nr, nc
            if done:
                break
        eps = max(eps_min, eps * eps_decay)
    return q


if __name__ == "__main__":
    q_opt = train(episodes=2000)
    # Chính sách tối ưu π(s) = argmax_a Q(s, a)
    policy = q_opt.argmax(axis=-1)
    print("Optimal policy (0=Up, 1=Right, 2=Down, 3=Left):")
    print(policy)

import numpy as np

# Double Q-Learning: dùng 2 bảng Q luân phiên để tránh max bias.
# Một bảng chọn action, bảng kia đánh giá → giảm overestimation.

def double_q_update(
    qa: np.ndarray,
    qb: np.ndarray,
    s: tuple[int, int],
    a: int,
    r: float,
    s_next: tuple[int, int],
    alpha: float,
    gamma: float,
) -> None:
    if np.random.rand() < 0.5:
        # Cập nhật Qa bằng đánh giá của Qb tại argmax theo Qa
        best_a = int(np.argmax(qa[s_next]))
        target = r + gamma * qb[s_next + (best_a,)]
        qa[s + (a,)] += alpha * (target - qa[s + (a,)])
    else:
        best_a = int(np.argmax(qb[s_next]))
        target = r + gamma * qa[s_next + (best_a,)]
        qb[s + (a,)] += alpha * (target - qb[s + (a,)])


def policy_from_double_q(qa: np.ndarray, qb: np.ndarray) -> np.ndarray:
    """Chính sách dùng trung bình hai bảng."""
    return ((qa + qb) / 2).argmax(axis=-1)

Markov Decision Process (MDP) là khung toán học của RL. Một MDP gồm 5 thành phần $(\mathcal{S}, \mathcal{A}, P, R, \gamma)$:

• $\mathcal{S}$ — tập các state (ví dụ: toạ độ ô trong mê cung).
• $\mathcal{A}$ — tập các action (ví dụ: 4 hướng di chuyển).
• $P(s' \mid s, a)$ — xác suất chuyển state. Ở grid world tất định, P = 1 khi nước đi hợp lệ.
• $R(s, a, s')$ — reward nhận được khi chuyển từ s sang s' bằng action a.
• $\gamma \in [0, 1)$ — discount factor.

Agent muốn tìm chính sách tối ưu $\pi^{*}(s)$ — hàm trả về action tốt nhất cho mỗi state — sao cho kỳ vọng tổng reward tương lai (có chiết khấu) là lớn nhất:

Hàm giá trị trạng thái và hàm giá trị hành động:

Liên hệ giữa hai hàm: $V^{\pi}(s) = \sum_a \pi(a \mid s) Q^{\pi}(s, a)$. Chính sách tối ưu chọn argmax của Q: $\pi^{*}(s) = \arg\max_{a} Q^{*}(s, a)$.

Hội tụ và lý thuyết:Theorem Watkins & Dayan (1992) chứng minh Q-Learning hội tụ tới $Q^{*}$ với xác suất 1 trong MDP tabular, với điều kiện mọi cặp (s, a) được thăm vô hạn lần và learning rate thoả điều kiện Robbins-Monro. Trong thực tế với function approximation (DQN), mất bảo đảm hội tụ nhưng vẫn work nhờ experience replay và target network.

So sánh nhanh các họ RL:

• Value-based (Q-Learning, DQN): học Q, suy ra policy qua argmax. Tốt cho action rời rạc.
• Policy-based (REINFORCE, PPO): học thẳng π(a|s). Tốt cho action liên tục.
• Actor-Critic (A2C, SAC): học đồng thời cả V (critic) và π (actor). Ổn định và dùng nhiều nhất trong thực tế hiện đại.
• Model-based (MuZero, Dreamer): học model môi trường, planning trong mô phỏng. Sample-efficient nhất.

Ứng dụng thực tế:

• Game: AlphaGo, AlphaStar, OpenAI Five, MuZero.
• Robotics: điều khiển tay máy (Boston Dynamics, OpenAI Dactyl).
• Logistics: Grab, Uber phân tuyến tài xế; Amazon sắp xếp kho hàng.
• Hệ thống gợi ý: YouTube, TikTok học thứ tự đề xuất bằng RL.
• LLM: RLHF (Reinforcement Learning from Human Feedback) — ChatGPT, Claude học từ sở thích người dùng.