AI & Machine Learning

Học tăng cường (Reinforcement Learning) và Thuật toán Q-Learning

Khác với học có giám sát cần nhãn sẵn hay học không giám sát chỉ tìm cụm, Học tăng cường (Reinforcement Learning - RL) mô phỏng cách sinh vật sống học hỏi thông qua tương tác thử và sai với môi trường để tối đa hóa phần thưởng tích lũy.

Ý chính
  • Mô hình tương tác Tác tử - Môi trường: Trọng tâm của học tăng cường là vòng lặp khép kín: Tác tử (Agent) quan sát trạng thái (State), thực hiện hành động (Action) tác động lên Môi trường (Environment), và nhận lại trạng thái mới kèm phần thưởng số học (Reward).
  • Phương trình Cập nhật Bellman: Thuật toán Q-Learning ước tính giá trị hành động tối ưu \(Q(s, a)\) thông qua quy hoạch động ngẫu nhiên: \(Q(s, a) \leftarrow Q(s, a) + \alpha [r + \gamma \max_{a'} Q(s', a') - Q(s, a)]\), đảm bảo hội tụ về chính sách tối ưu toàn cục.
  • Cân bằng Khám phá và Khai thác: Chiến lược \(\epsilon\)-greedy điều hòa mâu thuẫn cốt lõi giữa việc khai thác hành động đã biết có điểm cao (Exploitation) và khám phá các hành động mới tiềm năng tìm đường tắt (Exploration).

1. Giới thiệu Bức tranh Toàn cảnh của Học Tăng cường

Trong tam giác trụ cột của Trí tuệ Nhân tạo:

  1. Học có giám sát (Supervised Learning): Cần một "người thầy" chấm bài, cung cấp dữ liệu đầu vào \(\mathbf{X}\) kèm nhãn chuẩn xác \(\mathbf{y}\).
  2. Học không giám sát (Unsupervised Learning): Chỉ có dữ liệu \(\mathbf{X}\), mô hình tự động tìm kiếm các quy luật ẩn hoặc phân cụm dữ liệu.
  3. Học tăng cường (Reinforcement Learning - RL): Hoàn toàn không có nhãn đúng sai có sẵn. Mô hình đóng vai trò như một Tác tử (Agent) được thả vào một Môi trường (Environment) xa lạ. Tác tử phải tự mình hành động, nếm trải thất bại (bị phạt điểm âm) hoặc thành công (được thưởng điểm dương), từ đó đúc kết kinh nghiệm để đưa ra các quyết định thông minh nhất.

Học tăng cường là nền tảng đứng sau những chiến công lẫy lừng nhất của AI trong lịch sử:

  • Hệ thống AlphaGo của DeepMind đánh bại nhà vô địch thế giới cờ vây Lee Sedol năm 2016.
  • Các siêu AI làm chủ các tựa game chiến thuật thời gian thực phức tạp như StarCraft II (AlphaStar) và Dota 2 (OpenAI Five).
  • Xe tự hành học cách điều khiển vô lăng và phanh xe an toàn trong môi trường giao thông hỗn loạn.
  • Đặc biệt, giai đoạn căn chỉnh RLHF (Reinforcement Learning from Human Feedback) chính là chìa khóa biến một mô hình dòng GPT-3.5 thành ChatGPT biết giao tiếp hữu ích và an toàn.
Học Tăng Cường (Reinforcement Learning) Tác tử tương tác với môi trường và tối ưu hóa chính sách qua phần thưởng Tác Tử (Agent) Chính sách Policy π Bảng giá trị Q(s, a) Môi Trường Quy luật thế giới Phản hồi trạng thái Hành Động (Action A_t) Phần Thưởng (R_t+1) & Trạng Thái (S_t+1) Tối đa hóa tổng phần thưởng tích lũy dài hạn qua phương trình Bellman
Học Tăng Cường 1. Tác tử (Agent): Quan sát trạng thái và ra quyết định Cân bằng Khám phá và Khai thác 2. Môi trường phản hồi: Cung cấp trạng thái kế tiếp S' Trả về điểm thưởng Reward R 3. Thuật toán Q-Learning: Cập nhật giá trị hành động Q Tiến dần đến chiến lược tối ưu
Vòng lặp tương tác giữa tác tử và môi trường trong học tăng cường cùng nguyên lý cập nhật Bellman

2. Khung Toán học Nền tảng: Quy trình Quyết định Markov (MDP)

Mọi bài toán học tăng cường chuẩn mực đều được mô hình hóa toán học dưới dạng Quy trình Quyết định Markov (Markov Decision Process - MDP), được định nghĩa bởi một bộ 5 thành phần \((\mathcal{S}, \mathcal{A}, \mathcal{P}, \mathcal{R}, \gamma)\):

  1. Không gian trạng thái (\(\mathcal{S}\)): Tập hợp tất cả các trạng thái có thể có của môi trường mà tác tử có thể quan sát được (\(s \in \mathcal{S}\)). Ví dụ: tọa độ của quân cờ trên bàn cờ vua, vị trí và vận tốc của xe ô tô.
  2. Không gian hành động (\(\mathcal{A}\)): Tập hợp tất cả các hành động mà tác tử có thể thực hiện (\(a \in \mathcal{A}\)). Ví dụ: rẽ trái, rẽ phải, tăng ga, phanh.
  3. Mô hình chuyển trạng thái (\(\mathcal{P}\)): Xác suất chuyển từ trạng thái \(s\) sang trạng thái mới \(s'\) khi thực hiện hành động \(a\): \[\mathcal{P}(s' \mid s, a) = P(S_{t+1} = s' \mid S_t = s, A_t = a)\]
  4. Hàm phần thưởng (\(\mathcal{R}\)): Điểm số thực nhận được sau khi thực hiện hành động \(a\) tại trạng thái \(s\): \[\mathcal{R}(s, a) = \mathbb{E}[R_{t+1} \mid S_t = s, A_t = a]\]
  5. Hệ số chiết khấu (\(\gamma \in [0, 1)\)): Thể hiện mức độ quan tâm của tác tử đối với phần thưởng tương lai xa so với phần thưởng trước mắt:
    • Nếu \(\gamma = 0\): Tác tử thiển cận (myopic), chỉ chăm chăm tối đa hóa phần thưởng ngay lập tức tại bước hiện tại.
    • Nếu \(\gamma \to 1\): Tác tử có tầm nhìn xa trông rộng (far-sighted), sẵn sàng chấp nhận chịu điểm phạt trước mắt để đổi lấy phần thưởng khổng lồ ở đích đến cuối cùng.

Tính chất Markov (The Markov Property)

Điều kiện tiên quyết của một MDP là tính chất phi lịch sử Markov: \[P(S_{t+1} \mid S_t, A_t, S_{t-1}, A_{t-1}, \dots, S_0, A_0) = P(S_{t+1} \mid S_t, A_t)\] Nghĩa là: Tương lai chỉ phụ thuộc vào hiện tại, hoàn toàn độc lập với toàn bộ quá khứ. Trạng thái hiện tại \(S_t\) đã chứa đựng đầy đủ toàn bộ thông tin cần thiết để đưa ra quyết định tối ưu.

3. Hàm Giá trị và Phương trình Bellman Tuyệt đẹp

Mục tiêu tối thượng của tác tử là tìm ra một Chính sách (Policy \(\pi(a \mid s)\)) - phân phối xác suất chọn hành động \(a\) khi ở trạng thái \(s\) - sao cho tối đa hóa tổng phần thưởng tích lũy có chiết khấu:

\[G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \dots = \sum_{k=0}^\infty \gamma^k R_{t+k+1}\]

Để đo lường mức độ "tốt" của một trạng thái hoặc hành động, ta định nghĩa hai hàm giá trị:

  1. Hàm giá trị trạng thái (State-Value Function \(V^\pi(s)\)): Điểm số kỳ vọng nếu bắt đầu từ trạng thái \(s\) và tuân thủ chính sách \(\pi\): \[V^\pi(s) = \mathbb{E}_\pi [G_t \mid S_t = s]\]
  2. Hàm giá trị hành động (Action-Value Function \(Q^\pi(s, a)\)): Điểm số kỳ vọng nếu tại trạng thái \(s\), tác tử thực hiện hành động \(a\), sau đó tuân thủ chính sách \(\pi\): \[Q^\pi(s, a) = \mathbb{E}_\pi [G_t \mid S_t = s, A_t = a]\]

Nhà toán học Richard Bellman đã khám phá ra rằng các hàm giá trị này có thể phân rã thành dạng đệ quy tuyệt đẹp:

\[Q^*(s, a) = \mathcal{R}(s, a) + \gamma \sum_{s' \in \mathcal{S}} \mathcal{P}(s' \mid s, a) \max_{a'} Q^*(s', a')\]

Ý nghĩa trực giác của Phương trình Tối ưu Bellman: Giá trị của hành động ở hiện tại bằng phần thưởng nhận được ngay lập tức cộng với giá trị của hành động tối ưu nhất ở trạng thái tiếp theo (có chiết khấu \(\gamma\)).

Học cùng giảng viên

Chủ đề này nằm trong Lecture 14 - Neural Networks của Khóa AI. Xem đề cương

4. Thuật toán Q-Learning (Model-Free, Off-Policy)

Trong thế giới thực tế, tác tử thường không biết trước ma trận xác suất chuyển trạng thái \(\mathcal{P}\) và hàm thưởng \(\mathcal{R}\) của môi trường (bài toán Không có mô hình - Model-Free). Tác tử bắt buộc phải tự mình khám phá thông qua trải nghiệm.

Năm 1989, Chris Watkins đề xuất giải thuật Q-Learning. Q-Learning lưu trữ các giá trị \(Q(s, a)\) trong một bảng tra cứu gọi là Q-Table (kích thước \(|\mathcal{S}| \times |\mathcal{A}|\)).

Quy tắc Cập nhật Temporal Difference (TD):

Mỗi khi tác tử thực hiện hành động \(a\) tại trạng thái \(s\), nhận được phần thưởng thực tế \(r\) và chuyển sang trạng thái mới \(s'\), giá trị \(Q(s, a)\) được cập nhật như sau:

\[Q(s, a) \leftarrow Q(s, a) + \alpha \underbrace{\left[ r + \gamma \max_{a'} Q(s', a') - Q(s, a) \right]}_{\text{Sai số TD Error } \delta}\]

Trong đó:

  • \(\alpha \in (0, 1]\) là tốc độ học (Learning Rate).
  • \(r + \gamma \max_{a'} Q(s', a')\) được gọi là Mục tiêu TD (TD Target): ước lượng tốt hơn về giá trị tương lai sau khi đã có thêm trải nghiệm bước \(t+1\).
  • \(\delta = \text{TD Target} - Q(s, a)\) là Sai số chênh lệch thời gian (TD Error).

Q-Learning thuộc nhóm Off-Policy (Ngoài chính sách): Giá trị mục tiêu cập nhật luôn sử dụng hành động tối ưu tham lam \(\max_{a'} Q(s', a')\) bất kể hành động tiếp theo mà tác tử thực sự chọn để khám phá môi trường là gì. Watkins & Dayan (1992) đã chứng minh rằng nếu tất cả các cặp trạng thái-hành động đều được ghé thăm vô hạn lần và tốc độ học thỏa mãn điều kiện Robbins-Monro (\(\sum \alpha_t = \infty, \sum \alpha_t^2 \lt \infty\)), bảng \(Q(s, a)\) chắc chắn hội tụ 100% về hàm giá trị tối ưu toàn cục \(Q^*(s, a)\).

5. Cân bằng Khám phá và Khai thác: Chiến lược Epsilon-Greedy

Một thách thức muôn thuở trong học tăng cường là sự mâu thuẫn giữa:

  • Khai thác (Exploitation): Chọn hành động đã biết có điểm \(Q\) cao nhất trong bảng: \(a = \arg\max_a Q(s, a)\) để gặt hái phần thưởng.
  • Khám phá (Exploration): Chọn các hành động chưa từng thử nghiệm hoặc có điểm thấp hơn để tìm xem liệu có con đường nào đưa tới phần thưởng lớn hơn không.

Nếu chỉ khai thác, tác tử sẽ bị kẹt mãi mãi ở cực tiểu cục bộ (ví dụ: tìm được con đường ngắn dẫn tới 1 điểm thưởng mà không bao giờ tìm ra con đường dài dẫn tới 1.000 điểm thưởng).

Chiến lược \(\epsilon\)-greedy là giải pháp cân bằng kinh điển:

  • Với xác suất \(1 - \epsilon\): Tác tử thực hiện khai thác hành động tốt nhất hiện tại: \(a = \arg\max Q(s, a)\).
  • Với xác suất \(\epsilon\): Tác tử chọn ngẫu nhiên một hành động bất kỳ từ tập \(\mathcal{A}\) để khám phá thế giới.

Trong thực tế huấn luyện, người ta áp dụng kỹ thuật Suy giảm \(\epsilon\) (Epsilon Decay): Bắt đầu với \(\epsilon = 1.0\) (tác tử dành 100% thời gian ban đầu để khám phá ngẫu nhiên), sau đó giảm dần \(\epsilon\) theo từng ván đấu (episode) cho đến khi đạt mức nhỏ ổn định \(\epsilon_{\min} = 0.01\) (ưu tiên khai thác khi đã dày dạn kinh nghiệm).

6. Cài đặt thuật toán kiểm thử: Bước cập nhật Bellman Q-Update

Dưới đây là mã nguồn cài đặt chính xác công thức cập nhật giá trị Q theo phương trình sai số Bellman trong cả Python và C++17:

def bellman_q_update(q_current, reward, max_q_next, gamma, alpha):
    target = reward + gamma * max_q_next
    q_new = q_current + alpha * (target - q_current)
    return round(q_new, 4)

Phân tích độ phức tạp thuật toán

  • Độ phức tạp thời gian: Công thức cập nhật Q-Learning là một phép tính số học trực tiếp, chỉ bao gồm 2 phép nhân, 2 phép cộng và 1 phép trừ, độ phức tạp \(\mathcal{O}(1)\) khi đã có sẵn \(\max_{a'} Q(s', a')\); tính cả bước tìm giá trị lớn nhất này trên Q-table thì mỗi lần cập nhật tốn \(\mathcal{O}(|\mathcal{A}|)\).
  • Độ phức tạp không gian: Với bảng Q-table truyền thống, bộ nhớ cần thiết là \(\mathcal{O}(|\mathcal{S}| \cdot |\mathcal{A}|)\).

7. Đột phá Deep Q-Network (DQN): Vượt qua Giới hạn của Q-Table

Khi không gian trạng thái \(\mathcal{S}\) trở nên quá lớn hoặc liên tục (ví dụ: màn hình game Atari gồm \(210 \times 160\) pixels với bảng 128 màu có tới \(128^{33600}\) khung hình khác nhau), việc lưu trữ một bảng Q-table là bất khả thi.

Năm 2013, phòng nghiên cứu DeepMind công bố mạng Deep Q-Network (DQN), sử dụng một mạng nơ-ron sâu tích chập (CNN) tham số hóa bởi trọng số \(\theta\) để xấp xỉ hàm giá trị: \(Q(s, a; \theta) \approx Q^*(s, a)\).

DQN giải quyết bài toán mất ổn định khi kết hợp nơ-ron sâu với học tăng cường thông qua hai cơ chế đột phá:

  1. Bộ nhớ phát lại kinh nghiệm (Experience Replay Buffer): Trong học tăng cường, các mẫu dữ liệu liên tiếp \((s_t, a_t, r_t, s_{t+1})\) có tương quan thời gian rất cao (highly correlated), vi phạm giả định i.i.d (độc lập và phân phối đồng nhất) của việc tối ưu hóa mạng nơ-ron. DQN lưu trữ hàng triệu trải nghiệm quá khứ vào một bộ nhớ đệm replay buffer và lấy mẫu ngẫu nhiên từng mini-batch để huấn luyện, phá vỡ hoàn toàn tương quan dữ liệu.
  2. Mạng nơ-ron mục tiêu độc lập (Target Network \(\theta^-\), bổ sung trong bài báo DQN đăng trên Nature năm 2015): Nếu dùng chung một mạng nơ-ron để vừa tính toán dự đoán \(Q(s, a; \theta)\) vừa tính toán mục tiêu \(r + \gamma \max_{a'} Q(s', a'; \theta)\), việc cập nhật trọng số sẽ khiến mục tiêu liên tục dao động và chạy trốn (moving target problem). DQN đóng băng một mạng mục tiêu \(\theta^-\) riêng biệt và chỉ sao chép trọng số từ mạng chính sau mỗi vài nghìn bước lặp, giúp quá trình hội tụ diễn ra êm ái.

8. Bài tập vận dụng và câu hỏi phỏng vấn

  1. Câu hỏi: Sự khác biệt cốt lõi giữa thuật toán Q-Learning (Off-policy) và thuật toán SARSA (On-policy) là gì?
    • Gợi ý trả lời:
      • Khác biệt nằm ở cách tính giá trị tương lai:
        • Q-Learning: \(Q(s, a) \leftarrow Q(s, a) + \alpha [r + \gamma \max_{a'} Q(s', a') - Q(s, a)]\). Luôn giả định bước tiếp theo sẽ đi nước cờ tối ưu nhất, bất kể thực tế tác tử có thể đi ngẫu nhiên do \(\epsilon\)-greedy. Q-Learning học con đường tối ưu mạo hiểm.
        • SARSA: \(Q(s, a) \leftarrow Q(s, a) + \alpha [r + \gamma Q(s', a') - Q(s, a)]\). Giá trị cập nhật sử dụng chính xác hành động \(a'\) mà tác tử thực sự sẽ thực hiện ở bước tiếp theo dựa trên chính sách \(\epsilon\)-greedy. SARSA học con đường an toàn thận trọng hơn (ví dụ trong bài toán đi dọc vách đá, SARSA sẽ tránh xa mép vực vì sợ hành động ngẫu nhiên rơi xuống vực).
  2. Câu hỏi: Tại sao trong bài toán xe tự hành, người ta thường sử dụng các thuật toán Policy Gradient (như PPO, SAC) thay vì dùng Q-Learning hoặc DQN?
    • Gợi ý trả lời: Vì không gian hành động của xe tự hành là liên tục (Continuous Action Space): góc đánh lái vô lăng có thể là bất kỳ góc thực nào trong khoảng \([-45^\circ, +45^\circ]\), chân ga và phanh là giá trị thực liên tục từ \(0\%\) đến \(100\%\). Để áp dụng Q-Learning, hệ thống buộc phải tìm \(\max_a Q(s, a)\), việc tối ưu hóa hàm phi tuyến trên không gian liên tục tại mỗi bước mili-giây là cực kỳ tốn kém. Các thuật toán Policy Gradient trực tiếp tối ưu hóa chính sách \(\pi_\theta(a \mid s)\) và xuất ra các tham số phân phối xác suất (như trung bình \(\mu\) và độ lệch chuẩn \(\sigma\)) của hành động liên tục, phù hợp hoàn hảo cho các bài toán điều khiển cơ học.
Muốn học bài bản cùng giảng viên?

Khóa AI – Introduction to Machine Learning: nền tảng Máy học từ thuật toán cơ bản đến Neural Networks và LLM, học bằng Python. Học thử buổi 1 miễn phí.

Xem Khóa AI

Nguồn tham khảo

Chia sẻ: Facebook LinkedIn
Nhắn Zalo tư vấnZalo Gọi 0937 401 483