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 ${\displaystyle s}$, và người ra quyết định có thể chọn bất kỳ hành động ${\displaystyle a}$ nào có hiệu lực trong trạng thái ${\displaystyle s}$. 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 ${\displaystyle s'}$, và đưa ra cho người ra quyết định một phần thưởng tương ứng ${\displaystyle R_{a}(s,s')}$.

Xác suất mà quá trình di chuyển vào trạng thái mới của nó ${\displaystyle s'}$ 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 ${\displaystyle P_{a}(s,s')}$. Do đó, trạng thái kế tiếp ${\displaystyle s'}$ phụ thuộc vào trạng thái hiện tại ${\displaystyle s}$ và hành động của người ra quyết định ${\displaystyle a}$. Nhưng  ${\displaystyle s}$ và ${\displaystyle a}$ đã 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

Ví dụ về một MDP đơn giản với ba trạng thái và hai hành động.

Một quá trình quyết định Markov là một tập 5-dữ liệu ${\displaystyle (S,A,P_{\cdot }(\cdot ,\cdot ),R_{\cdot }(\cdot ,\cdot ),\gamma )}$, trong đó

• ${\displaystyle S}$ là một tập hữu hạn các trạng thái,
• ${\displaystyle A}$ là một tập hữu hạn các hành động (ngoài ra, ${\displaystyle A_{s}}$ là tập hữu hạn các hành động có sẵn từ trạng thái ${\displaystyle s}$),
• ${\displaystyle P_{a}(s,s')=\Pr(s_{t+1}=s'\mid s_{t}=s,a_{t}=a)}$ là xác suất mà hành động ${\displaystyle a}$ trong trạng thái ${\displaystyle s}$ tại thời gian ${\displaystyle t}$ sẽ dấn đến trạng thái ${\displaystyle s'}$ tại thời gian ${\displaystyle t+1}$,
• ${\displaystyle R_{a}(s,s')}$ là phần thưởng trực tiếp (hoặc phần thưởng trực tiếp mong đợi) nhận được sau khi chuyển tiếp sang trạng thái ${\displaystyle s'}$ từ trạng thái ${\displaystyle s}$,
• ${\displaystyle \gamma \in [0,1]}$ là hệ số chiết khấu, sẽ đại diện cho sự khác biệt quan trọng giữa các phần thưởng tương lai và các phần thưởng hiện tại.

(Ghi chú: Lý thuyết của quá trình quyết định Markov không nói rằng ${\displaystyle S}$ hoặc ${\displaystyle A}$ là hữu hạn, nhưng các thuật toán dưới đây giả định rằng chúng là hữu hạn.)

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 ${\displaystyle \pi }$ mà xác định hành động ${\displaystyle \pi (s)}$ rằng người ra quyết định sẽ chọn khi trong trạng thái ${\displaystyle s}$. 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 ${\displaystyle \pi }$ 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:

${\displaystyle \sum _{t=0}^{\infty }{\gamma ^{t}R_{a_{t}}(s_{t},s_{t+1})}}$    (trong đó ta chọn ${\displaystyle a_{t}=\pi (s_{t})}$)

trong đó ${\displaystyle \ \gamma \ }$ là hệ số chiết khấu và thỏa mãn ${\displaystyle 0\leq \ \gamma \ <1}$. (Ví dụ, ${\displaystyle \gamma =1/(1+r)}$ khi tốc độ chiết khấu là r.) ${\displaystyle \gamma }$ 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 ${\displaystyle s}$, 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ái${\displaystyle P}$ và hàm phần thưởng ${\displaystyle R}$, 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ị ${\displaystyle V}$, chứa các giá trị thực, và nguyên tắc ${\displaystyle \pi }$ chứa các hành động.  Cuối cùng của thuật toán này, ${\displaystyle \pi }$ sẽ chứa lời giải/ đáp số và ${\displaystyle V(s)}$ 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 ${\displaystyle s}$.

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:

${\displaystyle \pi (s):=\arg \max _{a}\left\{\sum _{s'}P_{a}(s,s')\left(R_{a}(s,s')+\gamma V(s')\right)\right\}}$

${\displaystyle V(s):=\sum _{s'}P_{\pi (s)}(s,s')\left(R_{\pi (s)}(s,s')+\gamma V(s')\right)}$

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 ${\displaystyle \pi }$ không được sử dụng, thay vào đó, giá trị của ${\displaystyle \pi (s)}$ được tính toán trong ${\displaystyle V(s)}$ 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.^[1]

Thay thế tính toán của ${\displaystyle \pi (s)}$ vào tính toán của ${\displaystyle V(s)}$ cho ta bước kết hợp:

${\displaystyle V_{i+1}(s):=\max _{a}\left\{\sum _{s'}P_{a}(s,s')\left(R_{a}(s,s')+\gamma V_{i}(s')\right)\right\},}$

trong đó ${\displaystyle i}$ là số lần lặp. Giá trị lặp bắt đầu tại ${\displaystyle i=0}$ và ${\displaystyle V_{0}}$ là một giả định của hàm giá trị. Sau đó tính toán lặp đi lặp lại ${\displaystyle V_{i+1}}$ cho tất cả các trạng thái ${\displaystyle s}$, cho đến khi ${\displaystyle V}$ 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 ${\displaystyle \pi }$ 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 ${\displaystyle V}$ hoặc ${\displaystyle \pi }$ 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 ${\displaystyle s}$ đã biết khi hành động được thực hiện; nếu không thì ${\displaystyle \pi (s)}$ 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).^[2] 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 ${\displaystyle a}$ 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ó):

${\displaystyle \ Q(s,a)=\sum _{s'}P_{a}(s,s')(R_{a}(s,s')+\gamma V(s')).\ }$

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 ${\displaystyle (s,a)}$ (cùng với kết quả ${\displaystyle s'}$); đó là, "Tôi đã ở trong trạng thái ${\displaystyle s}$ và tôi cố gắng thực hiện ${\displaystyle a}$ và ${\displaystyle s'}$ xảy ra"). Vì vậy, ta có một dãy ${\displaystyle Q}$ 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 ${\displaystyle (S,A,P)}$ có thể được hiểu trong khuôn khổ của Lý thuyết Phân loại. Cụ thể. cho ${\displaystyle {\mathcal {A}}}$ 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ử ${\displaystyle {\mathcal {A}}\to \mathbf {Dist} }$ 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ả ${\displaystyle ({\mathcal {C}},F:{\mathcal {C}}\to \mathbf {Dist} }$ 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 ${\displaystyle {\mathcal {C}}}$ 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,

• ${\displaystyle {\mathcal {S}}}$: Không gian trạng thái;
• ${\displaystyle {\mathcal {A}}}$: Không gian hành động;
• ${\displaystyle q(i|j,a)}$: ${\displaystyle {\mathcal {S}}\times {\mathcal {A}}\rightarrow \triangle {\mathcal {S}}}$, hàm tốc độ chuyển tiếp;
• ${\displaystyle R(i,a)}$: ${\displaystyle {\mathcal {S}}\times {\mathcal {A}}\rightarrow \mathbb {R} }$,hàm phần thưởng.

Nếu không gian trạng thái và không gian hành động là liên tục,

• ${\displaystyle {\mathcal {X}}}$: Không gian trạng thái.;
• ${\displaystyle {\mathcal {U}}}$: Không gian kiểm soát tốt;
• ${\displaystyle f(x,u)}$: ${\displaystyle {\mathcal {X}}\times {\mathcal {U}}\rightarrow \triangle {\mathcal {X}}}$, hàm tốc độ chuyển tiếp;
• ${\displaystyle r(x,u)}$: ${\displaystyle {\mathcal {X}}\times {\mathcal {U}}\rightarrow \mathbb {R} }$, hàm tốc độ phần thưởng kiểu như${\displaystyle r(x(t),u(t))dt=dR(x(t),u(t))}$, trong đó  ${\displaystyle R(x,u)}$ là hàm phần thưởng mà ta đã thảo luận trong trường hợp ở trên.

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:

${\displaystyle \max \quad \mathbb {E} _{u}[\int _{0}^{\infty }\gamma ^{t}r(x(t),u(t)))dt|x_{0}]}$

Trong đó ${\displaystyle 0\leq \gamma <1}$

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  ${\displaystyle V^{*}}$ 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:

${\displaystyle g\geq R(i,a)+\sum _{j\in S}q(j|i,a)h(j)\quad \forall i\in S\,\,and\,\,a\in A(i)}$

Nếu tồn tại một hàm ${\displaystyle h}$, thì ${\displaystyle {\bar {V}}^{*}}$ sẽ là  g nhỏ nhất thỏa mãn phương trình ở trên. Để tìm ${\displaystyle {\bar {V}}^{*}}$, chúng ta có thể sử dụng mô hình quy hoạch tuyến tính sau đây:

• Quy hoạch tuyến tính nguyên thủy(P-LP)

${\displaystyle {\begin{aligned}{\text{Minimize}}\quad &g\\{\text{s.t}}\quad &g-\sum _{j\in S}q(j|i,a)h(j)\geq R(i,a)\,\,\forall i\in S,\,a\in A(i)\end{aligned}}}$

• Quy hoạch tuyến tính kép(D-LP)

${\displaystyle {\begin{aligned}{\text{Maximize}}&\sum _{i\in S}\sum _{a\in A(i)}R(i,a)y(i,a)\\{\text{s.t.}}&\sum _{i\in S}\sum _{a\in A(i)}q(j|i,a)y(i,a)=0\quad \forall j\in S,\\&\sum _{i\in S}\sum _{a\in A(i)}y(i,a)=1,\\&y(i,a)\geq 0\qquad \forall a\in A(i)\,\,and\,\,\forall i\in S\end{aligned}}}$

${\displaystyle y(i,a)}$ là một lời giải khả thi cho D-LP nếu ${\displaystyle y(i,a)}$ 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 ${\displaystyle y^{*}(i,a)}$ cho D-LP được cho là một lời giải tối ưu nếu

${\displaystyle {\begin{aligned}\sum _{i\in S}\sum _{a\in A(i)}R(i,a)y^{*}(i,a)\geq \sum _{i\in S}\sum _{a\in A(i)}R(i,a)y(i,a)\end{aligned}}}$

đố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 ${\displaystyle y^{*}(i,a)}$, 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

${\displaystyle {\begin{aligned}V(x(0),0)=&{\text{max}}_{u}\int _{0}^{T}r(x(t),u(t))dt+D[x(T)]\\s.t.\quad &{\frac {dx(t)}{dt}}=f[t,x(t),u(t)]\end{aligned}}}$

D(${\displaystyle \cdot }$) là hàm phần thưởng cuối, ${\displaystyle x(t)}$ là vector trạng thái hệ thống, ${\displaystyle u(t)}$ là vector điều khiển hệ thống, ta sẽ phải đi tìm. f(${\displaystyle \cdot }$) 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:

${\displaystyle 0={\text{max}}_{u}(r(t,x,u)+{\frac {\partial V(t,x)}{\partial x}}f(t,x,u))}$

Chúng ta có thể giải phương trình trên để tìm điều khiển tối ưu ${\displaystyle u(t)}$, sẽ cho chúng ta giá trị tối ưu ${\displaystyle V^{*}}$

Ứ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 ${\displaystyle \beta }$ or ${\displaystyle \gamma }$, while the other focuses on minimization problems from engineering and navigation, using the terms control, cost, cost-to-go, and calling the discount factor ${\displaystyle \alpha }$. In addition, the notation for the transition probability varies.

Trong bài viết này	cách dùng khác	Chú giải
hành động ${\displaystyle a}$	điều khiển ${\displaystyle u}$
phần thưởng ${\displaystyle R}$	chi phí ${\displaystyle g}$	${\displaystyle g}$ là phủ định của ${\displaystyle R}$
giá trị ${\displaystyle V}$	chi phí phải trả ${\displaystyle J}$	${\displaystyle J}$ là phủ định của ${\displaystyle V}$
nguyên tắc ${\displaystyle \pi }$	nguyên tắc ${\displaystyle \mu }$
hệ số chiết khấu ${\displaystyle \ \gamma \ }$	hệ số chiết khấu ${\displaystyle \alpha }$
Xác suất chuyển tiếp ${\displaystyle P_{a}(s,s')}$	Xác suất chuyển tiếp ${\displaystyle p_{ss'}(a)}$

Ngoài ra, xác suất chuyển tiếp đôi khi được viết dưới dạng ${\displaystyle Pr(s,a,s')}$, ${\displaystyle Pr(s'|s,a)}$ hoặc, hiếm hoi hơn, ${\displaystyle p_{s's}(a).}$

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.^[3]

• Có rất nhiều chi phí phát sinh sau khi áp dụng một hành động thay vì một.
• CMDP chỉ được giải duy nhất bằng Quy hoạch tuyến tính, và không thể áp dụng Quy hoạch động ở đây.
• Điểm cuối cùng là sự phụ thuộc của trạng thái bắt đầu.

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. ^[4]

Xem thêm

• Tự động xác suất
• Quantum finite automata
• Partially observable Markov decision process
• Quy hoạch động
• Phương trình Bellman cho các ứng dụng trong kinh tế.
• Phương trình Hamilton – Jacobi – Bellman
• Điều khiển tối ưu
• Kinh tế Đệ quy
• Mabinogion sheep problem
• Trò chơi ngẫu nhiên
• Q-learning

Ghi chú

1. Lodewijk Kallenberg, Finite state and action MDPs, in Eugene A. Feinberg, Adam Shwartz (eds.
2. Burnetas, A. N.; Katehakis, M. N. (1997). “Optimal Adaptive Policies for Markov Decision Processes”. Mathematics of Operations Research. 22: 222. doi:10.1287/moor.22.1.222.
3. Altman, Eitan.
4. Feyzabadi, S.; Carpin, S., "Risk-aware path planning using hierarchical constrained Markov Decision Processes," Automation Science and Engineering (CASE), 2014 IEEE International Conference on, vol., no., pp.297,303, 18-22 Aug. 2014

Tham khảo

• R. Bellman. A Markovian Decision Process. Journal of Mathematics and Mechanics 6, 1957.
• R. E. Bellman. Dynamic Programming. Princeton University Press, Princeton, NJ, 1957. Dover paperback edition (2003), ISBN 0-486-42809-5.
• Ronald A. Howard Dynamic Programming and Markov Processes, The M.I.T. Press, 1960.
• D. Bertsekas. Dynamic Programming and Optimal Control. Volume 2, Athena, MA, 1995.
• Burnetas, A.N. and M. N. Katehakis. "Optimal Adaptive Policies for Markov Decision Processes, Mathematics of Operations Research, 22,(1), 1995.
• E.A. Feinberg and A. Shwartz (eds.) Handbook of Markov Decision Processes, Kluwer, Boston, MA, 2002.
• C. Derman. Finite state Markovian decision processes, Academic Press, 1970.
• M. L. Puterman. Markov Decision Processes. Wiley, 1994.
• H.C. Tijms. A First Course in Stochastic Models. Wiley, 2003.
• Sutton, R. S. and Barto A. G. Reinforcement Learning: An Introduction. The MIT Press, Cambridge, MA, 1998.
• J.A. E. E van Nunen. A set of successive approximation methods for discounted Markovian decision problems. Z. Operations Research, 20:203-208, 1976.
• S. P. Meyn, 2007. Control Techniques for Complex Networks Lưu trữ 2010-06-19 tại Wayback Machine, Cambridge University Press, 2007. ISBN 978-0-521-88441-9. Appendix contains abridged Meyn & Tweedie Lưu trữ 2010-06-19 tại Wayback Machine.
• S. M. Ross. 1983. Introduction to stochastic dynamic programming. Academic press
• X. Guo and O. Hernández-Lerma. Continuous-Time Markov Decision Processes, Springer, 2009.
• M. L. Puterman and Shin M. C. Modified Policy Iteration Algorithms for Discounted Markov Decision Problems, Management Science 24, 1978.

Liên kết ngoài

• MDP Toolbox for Matlab Lưu trữ 2004-10-12 tại Wayback Machine -Một hướng dẫn tuyệt vời và Matlab toolbox để làm việc với các MDP.
• MDP Toolbox for Python Một gói phần mềm để giải các MDP
• Reinforcement Learning^{[liên kết hỏng]} Một giới thiệu bởi Richard S. Sutton và Andrew G. Barto
• SPUDD Một cấu trúc giải MDP để tải về bởi Jesse Hoey
• Learning to Solve Markovian Decision Processes bởi Satinder P. Singh
• Optimal Adaptive Policies for Markov Decision Processes bởi Burnetas và Katehakis (1997).