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 , và người ra quyết định có thể chọn bất kỳ hành động  nào có hiệu lực trong trạng thái . 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 , và đưa ra cho người ra quyết định một phần thưởng tương ứng .
Xác suất mà quá trình di chuyển vào trạng thái mới của nó  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 . Do đó, trạng thái kế tiếp  phụ thuộc vào trạng thái hiện tại  và hành động của người ra quyết định . Nhưng   và  đã 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.

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  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  hoặc  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  đã biết khi hành động được thực hiện; nếu không thì  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.

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  có thể được hiểu trong khuôn khổ của Lý thuyết Phân loại. Cụ thể. cho  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ử  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ả  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  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).

Ứ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ố.