Cấu trúc dữ liệu cho Quy trình Quyết định Markov

Question

Tôi đã triển khai thuật toán lặp giá trị cho quy trình quyết định đơn giản Markov Wikipedia bằng Python. Để giữ cho cơ cấu (tiểu bang, hành động, hiệu ứng chuyển, khen thưởng) của quá trình Markov nói riêng và lặp trên nó Tôi đã sử dụng các cấu trúc dữ liệu sau:

1. từ điển cho tiểu bang và hành động mà có sẵn cho những khẳng định:

   SA = { 'state A': {' action 1', 'action 2', ..}, ...}

2. từ điển cho xác suất chuyển đổi:

   T = {('state A', 'action 1'): {'state B': probability}, ...}

3. từ điển cho phần thưởng:

   R = {('state A', 'action 1'): {'state B': reward}, ...}.

Câu hỏi của tôi là: đây có phải là cách tiếp cận phù hợp không? Cấu trúc dữ liệu thích hợp nhất (bằng Python) cho MDP là gì?

Answer 1

Cấu trúc dữ liệu có phù hợp hay không chủ yếu phụ thuộc vào những gì bạn làm với dữ liệu. Bạn đề cập rằng bạn muốn lặp lại quá trình này, vì vậy hãy tối ưu hóa cấu trúc dữ liệu của bạn cho mục đích này.

Chuyển tiếp trong quy trình Markov thường được mô hình hóa bằng phép nhân ma trận. Các xác suất chuyển đổi Pa(s1,s2) và các phần thưởng Ra(s1,s2) có thể được mô tả bởi (có thể thưa thớt) ma trận Pa và Ra được các quốc gia lập chỉ mục. Tôi nghĩ rằng điều này sẽ có một vài lợi thế:

• Nếu bạn sử dụng mảng nhiều mảng cho việc này, lập chỉ mục có thể sẽ nhanh hơn từ điển.
• Chuyển đổi trạng thái cũng có thể được mô tả đơn giản bằng phép nhân ma trận.
• Mô phỏng quy trình với lựa chọn bánh xe roulette ví dụ sẽ nhanh hơn và được triển khai rõ ràng hơn vì bạn chỉ cần chọn cột tương ứng của ma trận chuyển đổi.

Answer 2

Tôi đã triển khai Markov Quy trình quyết định bằng Python trước và thấy mã sau hữu ích.

http://aima.cs.berkeley.edu/python/mdp.html

Mã này được lấy từ Artificial Intelligence: Một cách tiếp cận hiện đại bởi Stuart Russell và Peter Norvig.

Answer 3

Có triển khai MDP với trăn gọi là pymdptoolbox. Nó được phát triển dựa trên việc thực hiện với Matlab gọi là MDPToolbox. Cả hai đều đáng chú ý.

Về cơ bản, ma trận chuyển đổi khả năng được biểu diễn dưới dạng một (A × S × S) mảng, và phần thưởng là một (S × A) ma trận, nơi S và A đại diện cho số của tiểu bang và số hành động. Các gói phần mềm có một số điều trị đặc biệt cho ma trận thưa thớt là tốt.