Markov Decision Process (MDP) là gì và phương trình Bellman phát biểu điều gì?

MDP là khung toán học mô tả bài toán ra quyết định tuần tự, định nghĩa bởi bộ (S, A, P, R, γ):
- S: tập trạng thái (states)
- A: tập hành động (actions)
- P(s′|s,a): xác suất chuyển trạng thái
- R(s,a): phần thưởng tức thời
- γ ∈ [0,1): hệ số chiết khấu

Cốt lõi là tính Markov: trạng thái kế tiếp chỉ phụ thuộc trạng thái và hành động hiện tại, không phụ thuộc toàn bộ lịch sử trước đó. Mục tiêu là tìm policy π tối đa hoá kỳ vọng tổng phần thưởng chiết khấu.

Phương trình Bellman phân rã giá trị một trạng thái thành phần thưởng tức thời cộng giá trị chiết khấu của trạng thái kế. Với hàm giá trị theo policy π:

V^π(s) = Σ_a π(a|s) Σ_s′ P(s′|s,a) [ R(s,a) + γ·V^π(s′) ]

Phương trình Bellman tối ưu thay trung bình theo π bằng max:

V*(s) = max_a Σ_s′ P(s′|s,a) [ R(s,a) + γ·V*(s′) ]

Đây là nền tảng cho quy hoạch động, value iteration, policy iteration và các thuật toán RL.