Quy trình Quyết định Markov (Markov Decision Process - MDP) là một khung toán học tiêu chuẩn và mạnh mẽ được sử dụng để mô hình hóa hầu hết các bài toán trong Học Tăng Cường (Reinforcement Learning - RL). Trong tài liệu này, chúng ta sẽ tập trung vào các Quy trình Quyết định Markov Hữu hạn (Finite Markov Decision Processes - FMDPs), nơi cả không gian trạng thái và không gian hành động đều hữu hạn, nhằm mục đích nắm bắt các ý tưởng cốt lõi và quy trình mô hình hóa toán học.
1. Mô hình hóa bài toán Học Tăng cường với MDP
Khi giải quyết một bài toán học tăng cường, bước quan trọng là xác định các thành phần của môi trường và tác nhân, sau đó trừu tượng hóa chúng thành một mô hình MDP. Sau khi mô hình được thiết lập, các thuật toán RL có thể được áp dụng để tìm ra giải pháp tối ưu.
Xác định bài toán Học Tăng cường
↓
Phân tích các yếu tố
↓
Chuyển đổi sang mô hình MDP
↓
Áp dụng thuật toán RL để giải
2. Quy trình Ngẫu nhiên (Stochastic Process)
2.1. Định nghĩa
Quy trình ngẫu nhiên là một phần của lý thuyết xác suất nghiên cứu các hiện tượng ngẫu nhiên thay đổi theo thời gian. Trong khi lý thuyết xác suất truyền thống tập trung vào các sự kiện tĩnh (ví dụ: tung đồng xu một lần), quy trình ngẫu nhiên khám phá các động thái theo thời gian (ví dụ: biến động giá cổ phiếu, thay đổi thời tiết).
2.2. Mô tả toán học
Trong một quy trình ngẫu nhiên:
- Trạng thái tại thời điểm \(t\): \(S_t\) (là một biến ngẫu nhiên)
- Không gian trạng thái: \(\mathcal{S} = \{s_1, s_2, \ldots, s_n\}\)
- Dãy trạng thái: \((S_1, S_2, \ldots, S_t, \ldots)\)
Thông thường, trạng thái \(S_{t+1}\) tại thời điểm \(t+1\) có thể phụ thuộc vào toàn bộ lịch sử các trạng thái trước đó: \(P(S_{t+1} | S_1, S_2, \ldots, S_t)\).
2.3. Ví dụ: Dự báo thời tiết
Giả sử không gian trạng thái thời tiết \(\mathcal{S} = \{\text{Nắng, Mưa, Mây mù}\}\).
Trong một quy trình ngẫu nhiên tổng quát, dự báo thời tiết ngày mai thường phụ thuộc vào thời tiết của hôm nay, hôm qua, và các ngày trước đó:
P(Ngày mai = Nắng | Hôm nay = Mưa, Hôm qua = Nắng, Hôm kia = Mây mù, ...)
3. Tính chất Markov (Markov Property)
3.1. Định nghĩa
Tính chất Markov phát biểu rằng trạng thái tương lai của một quy trình chỉ phụ thuộc vào trạng thái hiện tại, chứ không phụ thuộc vào toàn bộ lịch sử các trạng thái trước đó. Nói cách khác, khi đã biết trạng thái hiện tại, mọi thông tin trong quá khứ trở nên không cần thiết để dự đoán tương lai.
\(P(S_{t+1} | S_t) = P(S_{t+1} | S_1, S_2, \ldots, S_t)\)
Điều này không có nghĩa là trạng thái hiện tại hoàn toàn độc lập với quá khứ. Thay vào đó, nó ngụ ý rằng trạng thái hiện tại (\(S_t\)) đã gói gọn tất cả thông tin cần thiết từ quá khứ để đưa ra quyết định hoặc dự đoán về tương lai. \(S_t\) được coi là một "thống kê đủ" (sufficient statistic) của lịch sử.
3.2. Ví dụ
Tuân thủ tính chất Markov:
# Cờ vua
Trạng thái bàn cờ hiện tại = S_t // Chứa tất cả thông tin cần thiết về quân cờ, vị trí, lượt đi.
Trạng thái tiếp theo chỉ phụ thuộc vào S_t và nước đi được thực hiện, không cần biết các nước đi trước đó.
Không tuân thủ tính chất Markov:
# Trò chơi bài poker (chỉ nhìn lá bài cuối cùng)
Nếu bạn chỉ quan sát lá bài cuối cùng được chơi, bạn sẽ không biết bài của các người chơi khác hoặc lịch sử các lá bài đã được rút.
Để đưa ra quyết định tối ưu, bạn cần nhớ toàn bộ lịch sử các lá bài đã được chơi.
3.3. Ý nghĩa của tính chất Markov
Tính chất Markov mang lại nhiều lợi ích quan trọng:
- Đơn giản hóa tính toán: Chỉ cần lưu trữ trạng thái hiện tại thay vì toàn bộ lịch sử, giảm đáng kể yêu cầu về bộ nhớ và tính toán.
- Khả năng xử lý toán học: Cho phép mô tả sự chuyển đổi trạng thái bằng các phép toán ma trận, tạo cơ sở cho nhiều thuật toán.
- Nền tảng lý thuyết: Là một giả định cơ bản và thiết yếu trong Học tăng cường, cho phép phát triển các lý thuyết và thuật toán phức tạp.
Lưu ý: Tính chất Markov không có nghĩa là "không liên quan đến lịch sử". Thay vào đó, thông tin lịch sử được "truyền nối tiếp" và đã được tích hợp vào trạng thái hiện tại.
4. Quy trình Markov (Markov Process / Markov Chain)
4.1. Định nghĩa
Quy trình Markov là một quy trình ngẫu nhiên có tính chất Markov. Nó được đặc trưng bởi một tập hợp các trạng thái và các xác suất chuyển đổi giữa chúng.
Mô tả toán học:
\(\langle \mathcal{S}, \mathcal{P} \rangle\)
- \(\mathcal{S}\): Tập hợp các trạng thái, ví dụ \(\{s_1, \ldots, s_n\}\) (không gian trạng thái hữu hạn).
- \(\mathcal{P}\): Ma trận chuyển đổi trạng thái, chứa xác suất chuyển từ trạng thái này sang trạng thái khác.
4.2. Ma trận chuyển đổi trạng thái
Nếu có \(n\) trạng thái, ma trận chuyển đổi trạng thái \(\mathcal{P}\) là một ma trận \(n \times n\):
\[ \mathcal{P} = \begin{bmatrix} P(s_1|s_1) & P(s_2|s_1) & \cdots & P(s_n|s_1) \\ P(s_1|s_2) & P(s_2|s_2) & \cdots & P(s_n|s_2) \\ \vdots & \vdots & \ddots & \vdots \\ P(s_1|s_n) & P(s_2|s_n) & \cdots & P(s_n|s_n) \end{bmatrix} \]
Tính chất:
- Phần tử ở hàng \(i\), cột \(j\) là \(\mathcal{P}_{i,j} = P(s_j | s_i)\), tức là xác suất chuyển từ trạng thái \(s_i\) sang trạng thái \(s_j\).
- Tổng các xác suất trên mỗi hàng phải bằng 1: \(\sum_{j=1}^{n} \mathcal{P}_{i,j} = 1\).
4.3. Lấy mẫu (Sampling)
Từ một trạng thái khởi đầu, chúng ta có thể tạo ra một chuỗi các trạng thái dựa trên ma trận chuyển đổi. Mỗi chuỗi như vậy được gọi là một quỹ đạo (trajectory).
Ví dụ quỹ đạo 1:
\(s_A \to s_B \to s_C \to s_F\)
Ví dụ quỹ đạo 2:
\(s_A \to s_A \to s_B \to s_C \to s_D \to s_E \to s_F\)
Trạng thái kết thúc:
\(s_F\) có thể là một trạng thái hấp thụ (absorbing state). Khi đã đạt đến trạng thái này, tác nhân sẽ luôn ở lại đó, tức là \(P(s_F|s_F) = 1\).
5. Quy trình Phần thưởng Markov (Markov Reward Process - MRP)
5.1. Định nghĩa
MRP là một quy trình Markov được bổ sung thêm khái niệm về phần thưởng (reward) và hệ số chiết khấu (discount factor).
\(\langle \mathcal{S}, \mathcal{P}, r, \gamma \rangle\)
- \(\mathcal{S}\): Tập hợp các trạng thái hữu hạn.
- \(\mathcal{P}\): Ma trận chuyển đổi trạng thái.
- \(r\): Hàm phần thưởng, \(r(s)\) là phần thưởng kỳ vọng khi vào trạng thái \(s\).
- \(\gamma\): Hệ số chiết khấu, \(\gamma \in [0, 1)\), điều khiển tầm quan trọng của các phần thưởng tương lai.
5.2. Hàm phần thưởng
\(r(s) = \mathbb{E}[\text{Phần thưởng} | \text{Đạt trạng thái } s]\)
Phần thưởng \(R_t\) là một biến ngẫu nhiên, \(R_t \sim p(r|s, a, s')\). Hàm phần thưởng thường được định nghĩa là giá trị kỳ vọng của phần thưởng khi đến một trạng thái nhất định.
Ví dụ:
r(s_B) = -2 // Nhận hình phạt khi vào trạng thái B
r(s_D) = +10 // Nhận phần thưởng lớn khi vào trạng thái D
r(s_F) = 0 // Trạng thái kết thúc không có phần thưởng
5.3. Hồi vốn (Return)
Hồi vốn \(G_t\) từ thời điểm \(t\) là tổng các phần thưởng chiết khấu trong tương lai:
\[ G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \ldots = \sum_{k=0}^{\infty} \gamma^k R_{t+k+1} \]
Các thành phần:
- \(R_{t+1}\): Phần thưởng tức thì.
- \(\gamma R_{t+2} + \gamma^2 R_{t+3} + \ldots\): Các phần thưởng tương lai được chiết khấu.
5.4. Hệ số chiết khấu \(\gamma\)
Tại sao cần chiết khấu?
- Tính không chắc chắn: Các phần thưởng trong tương lai thường không chắc chắn hơn.
- Khuyến khích hành động nhanh: Tác nhân được khuyến khích đạt được phần thưởng sớm hơn.
- Đảm bảo sự hội tụ toán học: Ngăn chặn tổng hồi vốn vô hạn trong các môi trường có chu kỳ không kết thúc.
Ảnh hưởng của \(\gamma\):
| Giá trị \(\gamma\) | Đặc điểm | Hành vi chiến lược |
|---|---|---|
| \(\gamma \to 0\) | Chỉ quan tâm hiện tại | Thiển cận |
| \(\gamma = 0.9\) | Cân bằng | Giá trị phổ biến |
| \(\gamma \to 1\) | Rất coi trọng tương lai | Viễn thị |
Ví dụ tính toán:
Giả sử một quỹ đạo: \(A \to B \to C \to D\)
Các phần thưởng tương ứng: \(R_{A \to B} = 2\), \(R_{B \to C} = -1\), \(R_{C \to D} = 5\) (trong đó \(D\) là trạng thái kết thúc)
Hệ số chiết khấu \(\gamma = 0.8\)
Giá trị hồi vốn G tại thời điểm bắt đầu từ trạng thái A sẽ là:
G_A = R_B + γ * R_C + γ² * R_D
= 2 + 0.8 * (-1) + 0.8² * 5
= 2 - 0.8 + 0.64 * 5
= 2 - 0.8 + 3.2
= 4.4
6. Quy trình Quyết định Markov (Markov Decision Process - MDP)
6.1. Định nghĩa
MDP mở rộng MRP bằng cách thêm vào hành động (actions), cho phép tác nhân lựa chọn cách tương tác với môi trường.
\(\langle \mathcal{S}, \mathcal{A}, P, r, \gamma \rangle\)
- \(\mathcal{S}\): Tập hợp các trạng thái.
- \(\mathcal{A}\): Tập hợp các hành động.
- \(P\): Hàm chuyển đổi trạng thái. \(P(s'|s, a)\) là xác suất chuyển đến trạng thái \(s'\) khi thực hiện hành động \(a\) tại trạng thái \(s\).
- \(r\): Hàm phần thưởng. \(r(s, a)\) là phần thưởng kỳ vọng khi thực hiện hành động \(a\) tại trạng thái \(s\).
- \(\gamma\): Hệ số chiết khấu, \(\gamma \in [0, 1)\).
6.2. Hàm chuyển đổi trạng thái
\(P(s'|s, a) = \Pr\{S_{t+1} = s' | S_t = s, A_t = a\}\)
Đây là xác suất chuyển từ trạng thái \(s\) sang \(s'\) khi thực hiện hành động \(a\).
Lưu ý:
- Đây là một hàm ba chiều: trạng thái hiện tại \(s\), hành động \(a\), và trạng thái tiếp theo \(s'\).
- Tổng xác suất của tất cả các trạng thái \(s'\) có thể đạt được từ một cặp \((s, a)\) phải bằng 1: \(\sum_{s' \in \mathcal{S}} P(s'|s, a) = 1\).
Ví dụ: Môi trường Lưới (Grid World)
// Thế giới lưới (Grid World) - chuyển động chắc chắn
P(Ô_B | Ô_A, "Đi phải") = 1.0 // Từ Ô_A, đi phải chắc chắn đến Ô_B
P(Ô_C | Ô_A, "Đi xuống") = 1.0 // Từ Ô_A, đi xuống chắc chắn đến Ô_C
Ví dụ: Môi trường Trượt Băng (Slippery Ice World)
// Thế giới trượt băng (có độ trượt) - chuyển động ngẫu nhiên
P(Ô_B | Ô_A, "Đi phải") = 0.7 // 70% thành công, đến Ô_B
P(Ô_A | Ô_A, "Đi phải") = 0.2 // 20% trượt và ở lại Ô_A
P(Ô_C | Ô_A, "Đi phải") = 0.1 // 10% trượt xuống Ô_C
6.3. Hàm phần thưởng
\(r(s, a) = \mathbb{E}[R_{t+1} | S_t = s, A_t = a]\)
Phần thưởng bây giờ phụ thuộc vào cả trạng thái hiện tại \(s\) và hành động được chọn \(a\).
| Cặp (Trạng thái, Hành động) | Phần thưởng | Ý nghĩa |
|---|---|---|
| \((s_1, \text{Đi phải})\) | 0 | Di chuyển bình thường |
| \((s_1, \text{Đi lên})\) | -1 | Phạt khi va vào tường |
| \((s_8, \text{Đi phải})\) | +1 | Đạt được mục tiêu |
6.4. Chính sách (Policy)
Chính sách \(\pi\) định nghĩa hành vi của tác nhân. Nó là một ánh xạ từ trạng thái đến xác suất chọn các hành động.
\(\pi(a|s) = P(A_t = a | S_t = s)\)
Chính sách xác định (Deterministic Policy):
\(\pi(s) = a\) (Tại trạng thái \(s\), tác nhân luôn chọn hành động \(a\) duy nhất).
Chính sách ngẫu nhiên (Stochastic Policy):
\(\pi(a_1|s) = 0.7, \quad \pi(a_2|s) = 0.3\) (Tại trạng thái \(s\), tác nhân chọn \(a_1\) với xác suất 70% và \(a_2\) với xác suất 30%).
6.5. Quy trình tương tác của MDP
Mục tiêu của học tăng cường trong một môi trường MDP là tìm ra chính sách tối ưu \(\pi^*\) sao cho kỳ vọng của tổng phần thưởng chiết khấu được tối đa hóa:
\[ \max_{\pi} \mathbb{E}_{\pi}\left[\sum_{t=0}^{\infty} \gamma^t R_{t+1}\right] \]
Tức là, tìm một chính sách giúp tác nhân thu được tổng phần thưởng tích lũy cao nhất theo thời gian.
7. Tóm tắt bộ năm yếu tố của MDP
7.1. Định nghĩa đầy đủ
Một Quy trình Quyết định Markov được định nghĩa bởi bộ năm yếu tố sau:
\(\text{MDP} = \langle \mathcal{S}, \mathcal{A}, P, r, \gamma \rangle\)
- \(\mathcal{S}\): Tập hợp các trạng thái.
- \(\mathcal{A}\): Tập hợp các hành động.
- \(P\): Hàm chuyển đổi trạng thái (xác suất chuyển tiếp).
- \(r\): Hàm phần thưởng.
- \(\gamma\): Hệ số chiết khấu.