Quá trình quyết định Markov

Quy trình quyết định Markov (MDP) cung cấp một nền tảng toán học cho việc mô hình hóa việc ra quyết định trong các tình huống mà kết quả là một phần ngẫu nhiên và một phần dưới sự điều khiển của một người ra quyết định. MDP rất hữu dụng cho việc học một loạt bài toán tối ưu hóa được giải quyết thông qua quy hoạch động và học tăng cường. MDP được biết đến sớm nhất là vào những năm 1950 (cf. Bellman 1957). Một cốt lõi của nghiên cứu về quá trình ra quyết định Markov là từ kết quả của cuốn sách của Ronald A. Howard xuất bản năm 1960, "Quy hoạch động và quá trình Markov". Chúng được sử dụng trong rất nhiều các lĩnh vực khác nhau, bao gồm robot, điều khiển tự động,kinh tế, vàchế tạo.
Chính xác hơn, một quá trình quyết định Markov là một quá trình điều khiển ngẫu nhiên thời gian rời rạc. Tại mỗi bước thời gian, quá trình này trong một vài trạng thái formula_1, và người ra quyết định có thể chọn bất kỳ hành động formula_2 nào có hiệu lực trong trạng thái formula_1. Quá trình này đáp ứng tại bước thời gian tiếp theo bằng cách di chuyển ngẫu nhiên vào một trạng thái mới formula_4, và đưa ra cho người ra quyết định một phần thưởng tương ứng formula_5.
Xác suất mà quá trình di chuyển vào trạng thái mới của nó formula_4 bị ảnh hưởng bởi hành động được chọn. Đặc biệt, nó được đưa ra bởi hàm chuyển tiếp trạng thái formula_7. Do đó, trạng thái kế tiếp formula_4 phụ thuộc vào trạng thái hiện tại formula_1 và hành động của người ra quyết định formula_2. Nhưng  formula_1 và formula_2 đã cho, lại độc lập có điều kiện với toàn bộ trạng thái và hành động trước đó; nói cách khác, các trạng thái chuyển tiếp của một quá trình MDP thỏa mãn thuộc tính "Markov".
Quá trình quyết định Markov là một phần mở rộng của chuỗi Markov; khác biệt là ở sự bổ sung của các hành động (cho phép lựa chọn) và phần thưởng (cho động cơ). Ngược lại, nếu chỉ có một hành động tồn tại cho mỗi trạng thái và tất cả các phần thưởng là giống nhau (ví dụ: zero), một quá trình quyết định Markov làm giảm một chuỗi Markov.
Định nghĩa.
Một quá trình quyết định Markov là một tập 5-dữ liệu formula_13, trong đó
Bài toán.
Bài toán cốt lõi của MDP đó là tìm một "nguyên tắc" cho người ra quyết định: một hàm formula_30 mà xác định hành động formula_31 rằng người ra quyết định sẽ chọn khi trong trạng thái formula_1. Ghi chú rằng khi một quá trình quyết định Markov được kết hợp với một nguyên tắc theo cách thức như vậy, điều này sẽ làm cho hành động cho mỗi trạng thái và sự kết hợp kết quả sẽ hành xử giống như một xích Markov.
Mục đích là để chọn ra một nguyên tắc formula_30 mà sẽ tối đa hóa vài hàm tích lũy của các phần thưởng ngẫu nhiên, điển hình là tổng khấu hao mong muốn qua một đường vô cực tiềm năng:
trong đó formula_36 là hệ số chiết khấu và thỏa mãn formula_37. (Ví dụ, formula_38 khi tốc độ chiết khấu là r.) formula_39 thường gần với 1.
Do tính chất Markov, chính sách tối ưu cho bài toán cụ thể này thực sự có thể được viết như là một hàm của formula_1, như giả định ở trên.
Các thuật toán.
MDP có thể được giải bằng quy hoạch tuyến tính hoặc quy hoạch. Dưới đây chúng tôi xin trình bày cách tiếp cận thứ hai.
Giả sử chúng ta "đã biết "hàm chuyển tiếp trạng tháiformula_41 và hàm phần thưởng formula_42, và chúng ta muốn tính khả năng mà cực đại hóa phần thưởng không mong muốn dự tính.
Họ tiêu chuẩn của các thuật toán để tính nguyên tắc tối ưu này yêu cầu lưu trữ 2 dãy (array) biểu diễn bởi trạng thái: "giá trị "formula_43, chứa các giá trị thực, và "nguyên tắc "formula_30 chứa các hành động.  Cuối cùng của thuật toán này, formula_30 sẽ chứa lời giải/ đáp số và formula_46 sẽ chứa tổng chiết khấu (discounted sum) của các phần thưởng kiếm được (trị trung bình) bằng cách theo cách giải này từ trạng thái formula_1.
Thuật toán này có hai loại bước sau, được lặp đi lặp lại một số lần cho tất cả các trạng thái cho đến khi không có thay đổi nào diễn ra nữa. Chúng được định nghĩa một cách đệ quy như sau:
Bậc của chúng phụ thuộc vào biến thể của thuật toán; Ai cũng có thể thực hiện cho tất cả các trạng thái cùng một lúc hoặc từng trạng thái một, và một số trạng thái được thực hiện thường xuyên hơn các trạng thái khác. Miễn là không có trạng thái nào bị loại trừ vĩnh viễn từ một trong các bước, thuật toán sẽ cuối cùng đi đến được lời giải đúng.
Các biến thể đáng chú ý.
Phép lặp giá trị.
Trong phép lặp giá trị (Bellman 1957), còn được gọi là quy nạp ngược, hàm formula_30 không được sử dụng, thay vào đó, giá trị của formula_31 được tính toán trong formula_46 bất kể khi nào cần thiết. Nghiên cứu của Shapley vào năm 1953 về stochastic games (trò chơi ngẫu nhiên) bao gồm một trường hợp đặc biệt, phương pháp phép lặp giá trị cho các quá trình quyết định Markov, nhưng công trình này chỉ được công nhận sau này.
Thay thế tính toán của formula_31 vào tính toán của formula_46 cho ta bước kết hợp:
trong đó formula_56 là số lần lặp. Giá trị lặp bắt đầu tại formula_57 và formula_58 là một giả định của hàm giá trị. Sau đó tính toán lặp đi lặp lại formula_59 cho tất cả các trạng thái formula_1, cho đến khi formula_43 hội tụ với phía bên trái bằng phía bên phải (được gọi là "phương trình Bellman cho bài toán này).
Phép lặp nguyên tắc.
Trong phép lặp nguyên tắc (Howard 1960) bước một được thực hiện một lần, sau đó bước 2 được lặp đi lặp lại cho đến khi nó hội tụ. Sau đó bước một được thực hiện lại một lần nữa và vv.
Thay vì lặp đi lặp lại bước hai cho đến khi hội tụ, nó có thể được xây dựng và giải như một tập hợp các phương trình tuyến tính.
Biến thể này có lợi thế là có một điều kiện dừng nhất định: khi dãy formula_30 không thay đổi trong quá trình áp dụng bước 1 cho tất cả các trạng thái, thuật toán sẽ được hoàn thành.
Phép lặp nguyên tắc sửa đổi.
Trong phép lặp nguyên tắc sửa đổi (van Nunen, 1976; Puterman và Shin 1978), bước một được thực hiện một lần, và sau đó bước 2 được lặp đi lặp lại nhiều lần. Sau đó bước một được thực hiện một lần nữa và vân vân.
Quét ưu tiên.
Trong biến thể này, các bước được áp dụng ưu tiên cho các trạng thái quan trọng theo một số cách thức nào đó -  hoặc là dựa trên thuật toán này (có các thay đổi lớn trong formula_43 hoặc formula_30 xung quanh các trạng thái này gần đây) hoặc là dựa trên việc sử dụng (các trạng thái đó nằm gần trạng thái khởi động, hoặc là tùy thuộc vào người hoặc chương tình sử dụng thuật toán này).
Mở rộng và tổng quá hóa.
Quá trình quyết định Markov là một trò chơi ngẫu nhiên với người chơi duy nhất.
Có thể tuân theo từng phần.
Lời giải ở trên giả thiết rằng trạng thái formula_1 đã biết khi hành động được thực hiện; nếu không thì formula_31 không thể được tính toán. Khi giả thiết này không đúng, bài toán được gọi là một quá trình quyết định Markov có thể tuân theo từng phần hoặc POMDP.
Một cải tiến chính trong lĩnh vực này đã được thực hiện bởi Burnetas và Katehakis trong "Optimal adaptive policies for Markov decision processes" (các nguyên tắc thích nghi tối ưu cho các quá trình quyết định Markov). Trong công trình này một lớp các nguyên tắc thích nghi sở hữu các thuộc tính tốc độ hội tụ cực đại đều cho  tổng phần thưởng đường chân trời hữu hạn dự kiến, được xây dựng theo các giả định về các không gian trạng thái-hành động và sự tối giản của luật chuyển tiếp. Các nguyên tắc này quy định rằng sự lựa chọn của các hành động, tại mỗi trạng thái và khoảng thời gian, phải dựa vào các chỉ số là các lạm phát của bên phải của các phương trình tối ưu phần thưởng trung bình được ước lượng.
Học tăng cường.
Nếu xác suất hoặc phần thưởng là chưa biết, bài toán là bài toán học tăng cường (Sutton và Barto, 1998).
Để thực hiện mục đích này, việc định nghĩa một hàm thúc đẩy là rất cần thiết, tương ứng với việc thực hiện hành động formula_2 và sau đó tiếp tục tối ưu hóa (hoặc theo bất kỳ nguyên tắc nào mà ta đang có):
Trong khi hàm này cũng chưa biét, kinh nghiệm trong quá trình học sẽ được dựa trên các cặp formula_69 (cùng với kết quả formula_4); đó là, "Tôi đã ở trong trạng thái formula_1 và tôi cố gắng thực hiện formula_2 và formula_4 xảy ra"). Vì vậy, ta có một dãy formula_74 và sử dụng kinh nghiệm để cập nhật nó trực tiếp. Điều này còn được gọi là Q‑learning.
Học tăng cường có thể giải quyết các quá trình quyết định Markov mà không cần đặc điểm rõ ràng của các xác suất chuyển đổi;Các giá trị của các xác suất chuyển tiếp là cần thiết trong phép lặp giá trị và nguyên tắc.Trong tăng cường việc học, thay vì các đặc điểm rõ ràng của các xác suất chuyển tiếp, các xác suất chuyển tiếp được xử lý thông qua một trình mô phỏng thường khởi động lại nhiều lần từ một trạng thái ngẫu nhiên đầu tiên thống nhất. Học tăng cường cũng có thể được kết hợp với xấp xỉ hàm để giải các bài toán có số lượng trạng thái rất lớn.
Giải thích phân loại lý thuyết.
Ngoại trừ các phần thưởng, một quá trình quyết định Markov formula_75 có thể được hiểu trong khuôn khổ của Lý thuyết Phân loại. Cụ thể. cho formula_76 là ký hiệu của  free monoid với tập con "A". Cho Dist là ký hiệu của Kleisli category của Giry monad. Thì một hàm tử formula_77 mã hóa cả tập "S" của các trạng thái và cả hàm xác suất "P".
Bằng cách này, các quá trình quyết định Markov có thể được tổng quát hóa từ các monoid (các phân loại với một đối tượng) với các thể loại tùy ý. Ta có thể gọi kết quả formula_78 một "quyết định Markov phụ thuộc-ngữ cảnh", bởi vì di chuyển từ một đối tượng sang một đối tượng khác trong formula_79 thay đổi tập các hành động khả dụng và tập các trạng thái có khả năng xảy ra.
Quá trình quyết định Markov thời gian liên tục.
Trong các Quá trình Quyết định thời gian rời rạc Markov, cá quyết định được thực hiện tại các khoảng thời gian rời rạc. Tuy nhiên, đối với các Quá trình Quyết định Markov thời gian liên tục, các quyết định có thể được thực hiện tại bất kỳ thời gian nào mà người ra quyết định chọn. Khi so sánh với Quá trình Quyết định Markov thời gian Liên tục có thể mô hình hóa tốt hơn quá trình ra quyết định cho một hệ thống mà có động năng liên tục, có nghĩa là, các động năng của hệ thống được định nghĩa bởi các phương trình vi phân từng phần (PDE).
Định nghĩa.
Để thảo luận về Quá trình Quyết định Markov thời gian liên tục, chúng tôi xin giới thiệu hai bộ ký hiệu:
Nếu không gian trạng thái và không gian hành động là hữu hạn,
Nếu không gian trạng thái và không gian hành động là liên tục,
Bài toán.
Giống như các Quá trình Quyết định Markov thời gian Rời rạc, trong Quá trình Quyết định Markov thời gian Liên tục, ta muốn tìm "lời giải "hoặc "điều khiển "tối ưu có thể cho chúng ta phần thưởng tích hợp mong  muốn tối ưu:
Trong đó formula_95
Hình thành công thức quy hoạch tuyến tính.
Nếu không gian trạng thái và không gian hành động là hữu hạn, chúng ta có thể sử dụng quy hoạch tuyến tính để tìm lời giải tối ưu, đây là một trong những hướng tiếp cận sớm nhất được áp dụng. Ở đây chúng ta chỉ xem xét mô hình ergodic, nghĩa là MDP thời gian liên tục trở thành một ergodic Xích Markov thời gian rời rạc dưới một lời giải tĩnh. Dưới giả thiết này, mặc dù người ra quyết định có thể ra một quyết định tại bất kỳ thời gian tại trạng thái hiện tại, anh ta không thể thu lợi nhiều bằng cách thực hiện nhiều hơn 1 hành động. Sẽ tốt hơn cho anh ta để thực hiện một hành động tại thời điểm khi hệ thống đang dịch chuyển từ trạng thái hiện tại sang một trạng thái khác. Dưới vài điều kiện, (xem chi tiết Kết quả 3.14 của "Quá trình Quyết định Markov thời gian Liên tục"), nếu hàm giá trị tối ưu  formula_96 của chúng ta là độc lập với trạng thái i, chúng ta sẽ có bất phương trình sau:
Nếu tồn tại một hàm formula_98, thì formula_99 sẽ là  g nhỏ nhất thỏa mãn phương trình ở trên. Để tìm formula_99, chúng ta có thể sử dụng mô hình quy hoạch tuyến tính sau đây:
formula_103 là một lời giải khả thi cho D-LP nếu formula_103 là xa lạ và thỏa mãn các giới hạn trong bài toán D-LP. Một lời giải khả thi formula_105 cho D-LP được cho là một lời giải tối ưu nếu
đối với tất cả các lời giải khả thi y(i,a) đối với D-LP. Khi chúng ta tìm thấy lời giải tối ưu formula_105, chúng ta có thể sử dụng lời giải tối ưu này để thiết lập các giải pháp tối ưu.
Phương trình Hamilton-Jacobi-Bellman.
Trong MDP thời gian liên tục, nếu không gian trạng thái và không gian hành động là liên tục, tiêu chuẩn tối ưu có thể được tìm thấy bằng cách giải phương trình đạo hàm riêng Hamilton-Jacobi-Bellman (HJB). Để thảo luận về phương trình HJB, chúng ta cần để viết lại bài toán của chúng ta như sau
D(formula_109) là hàm phần thưởng cuối, formula_110 là vector trạng thái hệ thống, formula_111 là vector điều khiển hệ thống, ta sẽ phải đi tìm. f(formula_109) chỉ cách thức vector trạng thái thay đổi theo thời gian. Phương trình Hamilton-Jacobi-Bellman có dạng như sau:
Chúng ta có thể giải phương trình trên để tìm điều khiển tối ưu formula_114, sẽ cho chúng ta giá trị tối ưu formula_96
Ứng dụng.
Quá trình quyết định Markov thời gian liên tục được ứng dụng trong các hệ thống xếp hàng, các quá trình dịch bệnh và các quá trình dân số.
Ký hiệu thay thế.
The terminology and notation for MDPs are not entirely settled. There are two main streams — one focuses on maximization problems from contexts like economics, using the terms action, reward, value, and calling the discount factor formula_116 or formula_117, while the other focuses on minimization problems from engineering and navigation, using the terms control, cost, cost-to-go, and calling the discount factor formula_118. In addition, the notation for the transition probability varies.
Ngoài ra, xác suất chuyển tiếp đôi khi được viết dưới dạng formula_119, formula_120 hoặc, hiếm hoi hơn, formula_121
Quá trình quyết định Markov Hạn chế.
Quá trình Quyết định Markov Hạn chế (CMDP) là phần mở rộng của Quá trình Quyết định Markov (MDP). Có ba khác biệt cơ bản giữa MDP và CMDP.
Có rất nhiều ứng dụng của CMDP. Gần đây nó đang được sử dụng trong các kịch bản lập kế hoạch chuyển động trong robotic.