ONE is preparing: 01 / INITIALIZING MODEL ROUTER. Evaluating routing across providers.
Current state
01 / INITIALIZING MODEL ROUTER.

Evaluating routing across providers.

Start learning
← Học tăng cường

AI Researcher

Q-Learning

Vietnamese onlyThe learning content is available in Vietnamese only. The surrounding interface follows your language.

Thuật toán học tăng cường cơ bản học giá trị hành động tối ưu từ trải nghiệm

lesson120 minHọc tăng cườngAI Researcher

Dự đoán

Grab cần tìm đường ngắn nhất cho tài xế. Mỗi ngã tư có nhiều hướng, không biết trước đường nào kẹt. Tài xế học bằng cách nào?

Q-Learning: tại mỗi ngã tư (state), thử hành động (rẽ trái/phải/thẳng), nhận reward (nhanh = +, chậm = -). Dần dần xây dựng 'bản đồ giá trị' (Q-table): tại mỗi ngã tư, biết rẽ hướng nào có giá trị cao nhất.

Khoảnh khắc Aha

Sau nhiều lần thử, agent học được bản đồ giá trị (Q-table): tại mỗi ô, biết đi hướng nào có giá trị cao nhất. Q values lan ngược từ đích — ô gần đích có Q cao, ô xa hơn thì Q thấp dần. Agent đi theo gradient của Q values — giống nước chảy từ núi xuống thung lũng!

Đây là điểm khác biệt then chốt so với supervised learning: không ai dạy agent "đi đâu". Agent tự khám phá, tự chấm điểm, và tự xây bản đồ của riêng nó. Tín hiệu duy nhất là reward.

Thử thách

Agent có ε = 0.3. Sau 1000 episodes, nó đã học tốt. Nên giảm ε xuống 0.05 không?

Epsilon decay: ban đầu explore nhiều (0.3-1.0) để khám phá, sau đó giảm dần (0.05-0.01) để khai thác kiến thức. ε = 0 nguy hiểm: môi trường thay đổi thì agent không adapt được. Giữ ε khoảng 0.01-0.05 là cân bằng tốt.

Một ô có Q = [2.0, 5.0, 1.5, 3.0] cho [Up, Right, Down, Left]. Action Right đưa agent vào ô có max Q' = 6, reward = -0.1. Với α = 0.5, γ = 0.9, Q(s, Right) mới là?

Q(s, Right) mới là bao nhiêu?

Áp dụng: Q ← Q + α·[r + γ·maxQ' − Q] = 5.0 + 0.5·(−0.1 + 5.4 − 5.0) = 5.0 + 0.5·0.3 = 5.15. Q dịch nhẹ về phía target. Lặp nhiều lần, Q hội tụ tới giá trị kỳ vọng thật sự.

Bellman và quy tắc cập nhật

Q-Learning là thuật toán RL học giá trị Q(s,a)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:

Q∗(s,a)=E[r+γmax⁡a′Q∗(s′,a′)∣s,a]Q^{*}(s, a) = \mathbb{E}\left[ r + \gamma \max_{a'} Q^{*}(s', a') \mid s, a \right]

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

Q(st,at)←Q(st,at)+α[rt+γmax⁡a′Q(st+1,a′)−Q(st,at)]Q(s_t, a_t) \leftarrow Q(s_t, a_t) + \alpha \left[ r_t + \gamma \max_{a'} Q(s_{t+1}, a') - Q(s_t, a_t) \right]

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.
  • rtr_t — reward nhận được khi chuyển từ sts_t sang st+1s_{t+1}.
  • ϵ\epsilon — xác suất explore trong epsilon-greedy.

Hội tụ

Điều kiện hội tụ: Q-Learning hội tụ tới Q∗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ả ∑αt=∞,∑αt2<∞\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.

Code mẫu

Q-Learning với NumPy — grid world 5×5

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)

Double Q-Learning — khắc phục overestimation bias

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)

Vì sao Q-Learning overestimate

Toán tử max⁡a′Q(s′,a′)\max_{a'} Q(s', a') có tính chất: E[max⁡X]≥max⁡E[X]\mathbb{E}[\max X] \ge \max \mathbb{E}[X] . Khi Q có nhiễu ước lượng (đương nhiên, do mẫu hữu hạn), max trên các ước lượng nhiễu sẽ luôn nghiêng về phía lớn — đẩy Q lên cao hơn giá trị thật. Càng nhiều action, bias càng nặng.

Double Q-Learning (van Hasselt 2010) tách đôi: một mạng chọn action, mạng khác đánh giá. Hai ước lượng độc lập hủy bớt bias. Double DQN áp dụng ý tưởng này cho deep RL.

Chọn γ thế nào

Discount factor γ ∈ [0, 1) quyết định "tầm nhìn xa" của agent. γ = 0 → chỉ quan tâm reward ngay; γ → 1 → lên kế hoạch dài hạn. Ảnh hưởng thực tế:

  • γ = 0.9 → "horizon hiệu dụng" khoảng 1/(1−γ)=101 / (1 - \gamma) = 10 bước.
  • γ = 0.99 → horizon ≈ 100 bước.
  • γ = 0.999 → horizon ≈ 1000 bước. Cần cẩn thận: gradient lan xa làm training không ổn định.

Trong Atari, γ = 0.99 là chuẩn. Trong robotics dài hạn, người ta dùng γ = 0.995-0.999. Trò chơi cờ — γ có thể bằng 1.0 vì episode hữu hạn rõ ràng.

MDP và các hàm giá trị

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

  • S\mathcal{S} — tập các state (ví dụ: toạ độ ô trong mê cung).
  • A\mathcal{A} — tập các action (ví dụ: 4 hướng di chuyển).
  • P(s′∣s,a)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′)R(s, a, s') — reward nhận được khi chuyển từ s sang s' bằng action a.
  • γ∈[0,1)\gamma \in [0, 1) — discount factor.

Agent muốn tìm chính sách tối ưu π∗(s)\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:

J(π)=Eπ[∑t=0∞γtrt]J(\pi) = \mathbb{E}_{\pi} \left[ \sum_{t=0}^{\infty} \gamma^t r_t \right]

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

Vπ(s)=Eπ[∑t=0∞γtrt∣s0=s]V^{\pi}(s) = \mathbb{E}_{\pi}\left[ \sum_{t=0}^{\infty} \gamma^t r_t \mid s_0 = s \right]
Qπ(s,a)=Eπ[∑t=0∞γtrt∣s0=s,a0=a]Q^{\pi}(s, a) = \mathbb{E}_{\pi}\left[ \sum_{t=0}^{\infty} \gamma^t r_t \mid s_0 = s, a_0 = a \right]

Liên hệ giữa hai hàm: Vπ(s)=∑aπ(a∣s)Qπ(s,a)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: π∗(s)=arg⁡max⁡aQ∗(s,a)\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∗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.

So sánh và ứng dụng

Ứ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.

Tóm tắt

  • Q(s,a) = giá trị kỳ vọng của việc thực hiện action a tại state s rồi theo chính sách tối ưu. Agent chọn action có Q cao nhất.
  • Update rule Bellman: Q(s,a) ← Q(s,a) + α·[r + γ·max_{a'} Q(s',a') − Q(s,a)]. Đây là cốt lõi của Q-Learning.
  • Epsilon-greedy cân bằng explore (random) và exploit (best Q). Giảm ε dần theo thời gian để chuyển từ khám phá sang khai thác.
  • Off-policy: học từ best action (max Q) bất kể action thực sự → linh hoạt, cho phép experience replay.
  • Q-table chỉ dùng được với state/action rời rạc nhỏ. State lớn (ảnh, cảm biến) → Deep Q-Network (DQN) thay Q-table bằng neural network.
  • Bẫy cần biết: overestimation bias (dùng Double Q-Learning), reward sparse (dùng reward shaping, HER), và sai γ (chọn γ theo horizon bài toán).

Continue the module

Lesson 2 of 5