Học tăng cường: Q-learning

Mở đầu: không ai bảo con chó phải làm gì để có bánh thưởng

Dạy một con chó ngồi, bạn không viết ra 47 bước cơ sinh học của việc gập khớp gối. Bạn chỉ thưởng bánh khi nó tình cờ ngồi xuống, và phạt (hoặc lờ đi) khi nó không làm vậy. Con chó tự khám phá ra "hành động nào dẫn tới bánh" thông qua thử-sai, không ai dạy nó QUY TẮC. Đây chính xác là ý tưởng của học tăng cường (reinforcement learning) — nhánh thứ ba của học máy, khác hẳn Bài 1–3 (có nhãn đúng cho từng ví dụ) và Bài 4 (không nhãn nhưng có toàn bộ dữ liệu để nhìn cùng lúc).

Bài này tự xây Q-learning — thuật toán reinforcement learning cổ điển và dễ hiểu nhất — từ đúng một phương trình (Bellman), thả một agent vào mê cung 5×5 có bẫy, và verify bằng số đo thật hai điều: agent tự tìm ra đúng đường ngắn nhất sau khi train (không phải "trông có vẻ đúng"), và một pitfall kinh điển — quên khám phá (exploration) khiến agent có thể không bao giờ tìm ra phần thưởng, dù thuật toán hoàn toàn đúng.

1. Nhánh thứ ba của học máy: chỉ có reward thưa và đến trễ

Cả 4 bài học máy trước đều có một điểm chung: dữ liệu đi kèm tín hiệu dạy học đầy đủ — nhãn đúng (Bài 1–3) hoặc chí ít là toàn bộ tập dữ liệu để tự tìm cấu trúc (Bài 4). Học tăng cường sống trong một thế giới nghèo tín hiệu hơn nhiều: một agent tương tác với một môi trường (environment) theo vòng lặp lặp đi lặp lại:

Khác biệt cốt lõi với supervised learning: không ai bảo agent "đáng lẽ phải đi hướng nào" — nó chỉ nhận được điểm số CHO TOÀN BỘ chuỗi hành động, thường chỉ có ở CUỐI (tới đích hay sa bẫy). Đây gọi là credit assignment problem (bài toán quy trách nhiệm): nếu agent đi 8 bước rồi mới nhận +10, bước nào trong 8 bước đó "xứng đáng" được ghi công? Toàn bộ phần còn lại của bài là lời giải cho chính câu hỏi này. Học tăng cường là nền tảng của: chơi game (AlphaGo, Atari), điều khiển robot, và — nối thẳng tới Bài 18 — RLHF, kỹ thuật huấn luyện ChatGPT "cư xử như trợ lý" bằng chính reward do con người chấm.

2. Phương trình Bellman: giá trị = phần thưởng tức thời + tương lai

Ý tưởng trung tâm để giải bài toán credit assignment: định nghĩa một hàm $Q(s, a)$ — "giá trị lâu dài của việc thực hiện action $a$ tại state $s$" — không chỉ tính phần thưởng NGAY LẬP TỨC, mà cộng dồn cả những gì có thể đạt được SAU ĐÓ nếu chơi tối ưu tiếp. Phương trình Bellman diễn đạt chính xác ý này:

$$Q(s, a) \leftarrow Q(s, a) + \alpha \Big[ r + \gamma \max_{a'} Q(s', a') - Q(s, a) \Big]$$

Giải nghĩa từng ký hiệu (so với công thức GD của Bài 2, chỉ khác cách tính "mục tiêu"):

• $r$ — phần thưởng tức thời nhận được ngay sau hành động;
• $\gamma$ (gamma, discount factor, $0 \le \gamma < 1$) — hệ số chiết khấu tương lai: phần thưởng nhận được SAU $k$ bước chỉ đáng giá $\gamma^k$ lần giá trị danh nghĩa — vì sao? Tương lai không chắc chắn (môi trường có thể đổi, agent có thể chết trước khi tới đó), và một phần thưởng NGAY BÂY GIỜ luôn thực hơn một lời hứa xa xôi;
• $\max_{a'} Q(s', a')$ — giá trị TỐT NHẤT có thể đạt từ state kế tiếp $s'$, giả định từ giờ chơi tối ưu — đây chính là cách "tương lai" được cộng dồn ngược vào hiện tại;
• $\alpha$ (alpha) — chính là learning rate quen thuộc từ Bài 2: kích thước bước mỗi lần kéo $Q(s,a)$ lại gần "mục tiêu" $r + \gamma \max_{a'} Q(s',a')$ hơn một chút, không nhảy thẳng tới đó ngay (ổn định hơn, tránh dao động).

Tính tay ví dụ tí hon TRƯỚC khi chạy gridworld đầy đủ (đã verify bằng self-test): hành lang thẳng 3 ô $S_0 \to S_1 \to S_2$ (đích, thưởng $+10$), $\alpha = 0{,}5$, $\gamma = 0{,}9$, mọi $Q$ khởi tạo 0.

Nhìn kỹ dòng cuối: $Q(S_0,\text{phải})$ trở thành số DƯƠNG ($1{,}75$) dù $S_0$ chưa từng trực tiếp nhận phần thưởng nào — giá trị $+10$ ở đích đã "chảy ngược" qua $S_1$ rồi tới $S_0$, đúng 1 ô mỗi lần cả hành lang được đi qua. Đây chính là cách credit assignment thật sự hoạt động: không cần biết trước "nước đi nào xứng đáng", giá trị tự lan truyền ngược từ phần thưởng cuối cùng qua nhiều lượt lặp lại.

// Q luu duoi dang Map: key o -> [Q(len), Q(xuong), Q(trai), Q(phai)]
function update(Q, state, action, reward, nextState, done, alpha, gamma) {
  const qs = Q.get(state);
  const qNext = Q.get(nextState);
  const maxNext = done ? 0 : Math.max(...qNext);  // terminal: khong con tuong lai
  qs[action] = qs[action] + alpha * (reward + gamma * maxNext - qs[action]);
}

3. Bảng Q & vòng lặp học trên Gridworld

Với state space nhỏ (hữu hạn ô), $Q$ có thể lưu trực tiếp thành bảng (tabular Q-learning) — mỗi ô một hàng, mỗi action một cột. Gridworld demo dùng lưới $5 \times 5$: agent xuất phát góc trên trái, đích ở góc dưới phải (+10, kết thúc episode), một bẫy ở giữa (−10, kết thúc episode), mỗi bước bình thường −1 (ép tìm đường NGẮN nhất, không lang thang).

Còn một mảnh ghép: agent chọn action thế nào? Luôn chọn action có $Q$ cao nhất (khai thác/exploitation) nghe hợp lý — nhưng nếu $Q$ ban đầu đều bằng 0, agent sẽ không bao giờ biết action khác có tốt hơn không nếu không THỬ nó. Giải pháp chuẩn: $\varepsilon$-greedy — với xác suất $\varepsilon$ chọn action NGẪU NHIÊN (khám phá/exploration), còn lại chọn action tốt nhất theo $Q$ hiện tại (khai thác). $\varepsilon$ thường bắt đầu cao (khám phá nhiều lúc chưa biết gì) rồi decay (giảm dần) về một mức sàn nhỏ khi $Q$ đã học được kha khá.

Train gridworld thật với $\alpha{=}0{,}1$, $\gamma{=}0{,}9$, $\varepsilon$ từ $1{,}0$ decay dần về sàn $0{,}05$, 500 episode, seed cố định — verify agent hội tụ đúng đường 8 bước tối ưu, tránh bẫy hoàn toàn (đã verify ổn định trên 10/10 seed khác nhau, không phải may mắn 1 lần):

function chooseAction(qs, epsilon, rng) {
  if (rng() < epsilon) return Math.floor(rng() * 4);   // KHAM PHA: ngau nhien
  let best = 0;                                         // KHAI THAC: Q cao nhat
  for (let a = 1; a < 4; a++) if (qs[a] > qs[best]) best = a;
  return best;
}
// epsilon giam dan theo tung episode — khong con khai pha nua khi da hoc du
epsilon = Math.max(epsilonMin, epsilon * epsilonDecay);

Ghép cả hai mảnh (Bellman update + $\varepsilon$-greedy) thành vòng lặp train hoàn chỉnh — đúng cấu trúc file tải về cuối bài, mỗi episode là một lần agent đi từ start tới khi kết thúc (tới đích, sa bẫy, hoặc hết số bước cho phép):

function trainQLearning({ episodes, alpha, gamma, epsilonStart, epsilonMin, epsilonDecay, seed }) {
  const Q = new Map();   // key o -> [Q(len), Q(xuong), Q(trai), Q(phai)]
  let epsilon = epsilonStart;
  for (let ep = 0; ep < episodes; ep++) {
    let state = [0, 0];                          // moi episode bat dau lai tu S
    for (let t = 0; t < 100; t++) {               // gioi han buoc, tranh lap vo han
      const action = chooseAction(getQ(state), epsilon, rng);
      const { next, reward, done } = step(state, action);
      update(Q, state, action, reward, next, done, alpha, gamma);  // Bellman
      state = next;
      if (done) break;                            // toi dich hoac sa bay
    }
    epsilon = Math.max(epsilonMin, epsilon * epsilonDecay);  // giam kham pha dan
  }
  return Q;
}

4. Giới hạn của tabular: khi bảng Q không còn vừa bộ nhớ

Gridworld $5 \times 5$ có 25 ô × 4 action = 100 giá trị $Q$ — một bảng bé tí.

Cờ vây có khoảng $10^{170}$ trạng thái bàn cờ khả dĩ; không máy tính nào lưu nổi bảng $Q$ tương ứng. Lời giải công nghiệp: thay bảng tra cứu bằng một mạng neural nhận state làm đầu vào, xuất ra ước lượng $Q(s, a)$ cho mọi action — gọi là DQN (Deep Q-Network, nối thẳng kiến trúc MLP của Bài 6). Bài này KHÔNG cài DQN đầy đủ (ngoài phạm vi — chỉ trình bày ở mức khái niệm): ý tưởng cốt lõi giữ nguyên y hệt — vẫn phương trình Bellman, vẫn $\varepsilon$-greedy, chỉ khác "bảng tra cứu" được thay bằng "hàm xấp xỉ" tổng quát hoá được cho state chưa từng thấy.

5. Thực hành: Gridworld — agent tự học đường đi

Demo dưới đây chạy đúng thuật toán vừa học: bấm ▶ để agent tự chạy nhiều episode, xem bảng Q hiện dần thành các mũi tên chỉ hành động tốt nhất mỗi ô (policy), và biểu đồ tổng reward mỗi episode đi lên dần khi agent học được đường tránh bẫy. Kéo slider $\varepsilon$ về 0 và Reset để tận mắt xem cạm bẫy Mục 3 — agent kẹt cứng, không bao giờ tìm ra đích trong ngân sách nhỏ:

Đối chiếu: bài này thuần JavaScript, không cần snippet PyTorch — cách trình bày và ký hiệu theo đúng chuẩn Reinforcement Learning: An Introduction (Sutton & Barto), sách gối đầu giường của cả ngành:

Khoi tao Q(s, a) tuy y cho moi s, a
Lap moi episode:
    Khoi tao s
    Lap moi buoc trong episode:
        Chon a tu s dung policy suy tu Q (vd epsilon-greedy)
        Thuc hien a, quan sat r, s'
        Q(s,a) = Q(s,a) + alpha [ r + gamma max_a' Q(s',a') - Q(s,a) ]
        s = s'
    cho toi khi s la terminal

Tóm lược

• ✅ Nhánh thứ ba của ML: không nhãn, không cụm — chỉ có reward thưa/trễ; credit assignment là bài toán trung tâm.
• ✅ Phương trình Bellman: $Q(s,a) \leftarrow Q(s,a) + \alpha[r + \gamma \max Q(s',a') - Q(s,a)]$ — giá trị lan truyền ngược từ reward cuối, verified tính tay 3 bước.
• ✅ ε-greedy: cân bằng khám phá/khai thác; verified pitfall $\varepsilon{=}0$ bằng số đo thật (0/20 vs 5/20 seed cùng budget) — thuật toán đúng vẫn có thể không bao giờ tìm ra reward.
• ✅ Tabular → DQN: bảng Q chỉ dùng được với state space nhỏ; mạng neural thay thế khi state nổ (cờ vây $10^{170}$).
• ✅ Reward hacking (CoastRunners): agent tối ưu đúng cái được chấm, không phải cái ta muốn — thiết kế reward sai là lỗi đắt giá nhất của RL.