Markov Decision Process (MDP)

Quy trình quyết định Markov (MDP) là mô hình toán học của một bài toán ra quyết định tuần tự: một agent quan sát trạng thái, chọn hành động, nhận reward và chuyển sang trạng thái tiếp theo, vốn phụ thuộc một phần vào lựa chọn của agent và một phần vào yếu tố ngẫu nhiên. Về mặt hình thức, MDP gồm tập trạng thái, tập hành động, xác suất chuyển trạng thái P(s′ | s, a), hàm reward R(s, a) và thường có hệ số chiết khấu γ từ 0 đến 1. Giải bài toán này nghĩa là tìm một policy — quy tắc chọn hành động ở mỗi trạng thái — để tối đa hóa tổng reward tương lai kỳ vọng đã chiết khấu. MDP bắt nguồn từ nghiên cứu vận trù học vào thập niên 1950, khi quy hoạch động của Richard Bellman cung cấp các phương pháp giải; đây là cách phát biểu bài toán tiêu chuẩn cho học tăng cường (RL).

Tính chất Markov#

Giả định cốt lõi là tính chất Markov: trạng thái tiếp theo và reward chỉ phụ thuộc vào trạng thái hiện tại và hành động, không phụ thuộc vào đường đi đã dẫn đến đó. Nhờ vậy, trạng thái là bản tóm tắt đầy đủ của agent về mọi yếu tố liên quan. Một khung hình camera đơn lẻ vi phạm giả định này đối với vật thể đang chuyển động, vì khung hình cho biết vị trí nhưng không cho biết vận tốc; do đó, DQN chơi Atari của DeepMind đưa bốn khung hình gần nhất xếp chồng lên nhau vào mạng để mạng có thể nhận biết chuyển động.

Khi agent không thể quan sát toàn bộ trạng thái, chẳng hạn robot có cảm biến nhiễu hoặc bị che khuất, bài toán được gọi là MDP quan sát một phần (POMDP). Khi đó, thay vì dựa trên chính trạng thái, agent hành động dựa trên niềm tin về trạng thái, được duy trì bằng bộ lọc hoặc mạng hồi quy.

Các thành phần của MDP#

• Trạng thái: Các tình huống agent có thể gặp, chẳng hạn góc khớp của robot và vị trí vật thể mà robot đang với tới.
• Hành động: Các lựa chọn có sẵn ở mỗi trạng thái. Không gian hành động có thể rời rạc (rẽ trái, rẽ phải) hoặc liên tục (góc đánh lái tính bằng độ).
• Xác suất chuyển trạng thái: Khả năng xảy ra của từng trạng thái tiếp theo sau một hành động, bao gồm bánh xe trượt, các tài xế khác và mọi nguồn bất định khác.
• Reward: Phản hồi số tức thời cho một lần chuyển trạng thái. Lựa chọn reward của người thiết kế xác định tác vụ; lựa chọn thiếu thận trọng có thể dẫn đến reward hacking.
• Hệ số chiết khấu: Mức độ reward tương lai được tính đến so với reward tức thời. Với γ = 0.9, một reward ở cách 10 bước có giá trị bằng 0.9¹⁰ ≈ 0.35 lần reward tương tự nhận ngay bây giờ.

Mỗi timestep lặp lại cùng một tương tác cho đến khi episode kết thúc:

Giải MDP#

Giá trị của một trạng thái là return kỳ vọng từ trạng thái đó theo một policy; giá trị tối ưu thỏa mãn phương trình Bellman: giá trị của mỗi trạng thái bằng reward tức thời tốt nhất cộng với giá trị của các trạng thái mà hành động đó dẫn đến, được chiết khấu và tính trọng số theo xác suất. Khi đã biết xác suất chuyển trạng thái và reward, quy hoạch động giải trực tiếp phương trình này. Value iteration (Bellman, 1957) áp dụng lặp lại phương trình cho đến khi các giá trị ngừng thay đổi; policy iteration (Howard, 1960) luân phiên giữa đánh giá policy và cải thiện policy.

Ví dụ NumPy này chạy value iteration trên robot tái chế trong Reinforcement Learning: An Introduction của Sutton và Barto. Robot phải chọn giữa tìm lon, chờ và sạc lại khi pin ở mức cao hoặc thấp:

import numpy as np

# MDP robot tái chế: trạng thái 0 = pin cao, 1 = pin thấp; hành động 0 = tìm kiếm, 1 = chờ, 2 = sạc lại
gamma = 0.9  # hệ số chiết khấu
P = np.zeros((2, 3, 2))  # P[s, a, s'] = xác suất đến s' sau khi thực hiện a tại s
P[0, 0] = [0.7, 0.3]  # tìm kiếm khi pin cao có thể làm pin tụt xuống mức thấp
P[1, 0] = [0.4, 0.6]  # tìm kiếm khi pin thấp có thể làm cạn pin (robot được cứu và sạc lại)
P[:, 1] = np.eye(2)  # chờ sẽ giữ nguyên mức pin
P[:, 2] = [1.0, 0.0]  # sạc lại luôn khôi phục pin lên mức cao
R = np.array([[2.0, 1.0, 0.0], [0.0, 1.0, 0.0]])  # R[s, a] kỳ vọng; tìm kiếm khi pin thấp: 0.6 * 2 + 0.4 * -3 = 0

# Value iteration: áp dụng cập nhật tối ưu Bellman cho đến khi các giá trị ngừng thay đổi
V = np.zeros(2)
for _ in range(500):
    Q = R + gamma * P @ V  # giá trị của mỗi hành động tại mỗi trạng thái
    V = Q.max(axis=1)

actions = ["search", "wait", "recharge"]
print("Optimal values:", V.round(2))
print("Optimal policy:", {s: actions[a] for s, a in zip(["high", "low"], Q.argmax(axis=1))})

Kết quả in ra giá trị 15.75 khi pin cao và 14.17 khi pin thấp, cùng policy tìm kiếm khi pin cao và sạc lại khi pin thấp: rủi ro 40% phải chịu mức phạt cứu hộ −3 khiến việc tìm kiếm khi pin thấp kém giá trị hơn sạc lại.

Khi chưa biết xác suất chuyển trạng thái, học tăng cường ước lượng các giá trị tương tự từ kinh nghiệm. Q-learning cập nhật giá trị hành động từ các lần chuyển trạng thái được lấy mẫu; phương pháp policy gradient điều chỉnh trực tiếp policy; còn học tăng cường sâu sử dụng mạng neural khi không gian trạng thái quá lớn để liệt kê. Các thuật toán lập kế hoạch như tìm kiếm cây Monte Carlo giải MDP quy mô lớn trực tuyến bằng cách chỉ mô phỏng những trạng thái tương lai có thể đạt được từ trạng thái hiện tại.

MDP và các mô hình liên quan#

• Chuỗi Markov: Một chuỗi các trạng thái ngẫu nhiên không có hành động hay reward. MDP bổ sung các lựa chọn và mục tiêu.
• Mô hình Markov ẩn (HMM): Chuỗi Markov có các trạng thái chỉ được quan sát thông qua tín hiệu nhiễu. POMDP có quan hệ tương tự với MDP.
• Bandit đa nhánh: MDP chỉ có một trạng thái, trong đó mỗi hành động mang lại kết quả độc lập với quá khứ.
• Học tăng cường: Nhóm các phương pháp học cách hành động hiệu quả trong MDP thông qua tương tác, mà không được cung cấp xác suất chuyển trạng thái.

Ứng dụng#

• Robot học và điều khiển: Các tác vụ gắp, đi bộ và điều hướng được mô hình hóa thành MDP; policy thường được huấn luyện trong môi trường mô phỏng. Trong điều khiển dựa trên camera, bộ phát hiện như Ultralytics YOLO26 có thể cung cấp trạng thái, chuyển mỗi khung hình thành một danh sách ngắn gồm class đối tượng và tọa độ box — đầu vào nhỏ hơn nhiều cho policy so với pixel thô.
• Huấn luyện model ngôn ngữ: RLHF và RLVR xem quá trình tạo văn bản như một MDP, trong đó trạng thái là prompt cộng với các token đã sinh, hành động là token tiếp theo và reward được nhận khi hoàn tất câu trả lời.
• Nghiên cứu vận trù học: Bổ sung hàng tồn kho, bảo trì thiết bị và định giá linh hoạt là các MDP kinh điển; Ronald Howard đã phát triển policy iteration khi tối ưu hóa việc gửi catalog của Sears.