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

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

right|thumb|400x400px|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 $(S,A,P$\cdot(\cdot,\cdot),R\cdot(\cdot,\cdot),\gamma), trong đó

• $S$ là một tập hữu hạn các trạng thái,
• $A$ là một tập hữu hạn các hành động (ngoài ra, $A\_s$ là tập hữu hạn các hành động có sẵn từ trạng thái $s$),
• $P\_a(s,s\text{'})\; =\; \backslash Pr(s\_\{t+1\}=s\text{'}\; \backslash mid\; s\_t\; =\; s,\; a\_t=a)$ là xác suất mà hành động $a$ trong trạng thái $s$ tại thời gian $t$ sẽ dấn đến trạng thái $s\text{'}$ tại thời gian $t+1$,
• $R\_a(s,s\text{'})$ 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 $s\text{'}$ từ trạng thái $s$,
• $\backslash gamma\; \backslash 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 $S$ hoặc $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 $\backslash pi$ mà xác định hành động $\backslash pi(s)$ rằng người ra quyết định sẽ chọn khi trong trạng thái $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 $\backslash 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: : $\backslash sum^\{\backslash infty\}${t=0} {\gamma^t R{a_t} (st, s{t+1})}    (trong đó ta chọn $a\_t\; =\; \backslash pi(s\_t)$) trong đó $\backslash \; \backslash gamma\; \backslash$ là hệ số chiết khấu và thỏa mãn . (Ví dụ, $\backslash gamma\; =\; 1/(1+r)$ khi tốc độ chiết khấu là r.) $\backslash 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 $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$P$ và hàm phần thưởng $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ị $V$, chứa các giá trị thực, và nguyên tắc $\backslash pi$ chứa các hành động.  Cuối cùng của thuật toán này, $\backslash pi$ sẽ chứa lời giải/ đáp số và $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 $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: : $\backslash pi(s):=\; \backslash arg\; \backslash max$a \left{ \sum{s'} P_a(s,s') \left(R_a(s,s') + \gamma V(s') \right) \right}

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

Thay thế tính toán của $\backslash pi(s)$ vào tính toán của $V(s)$ cho ta bước kết hợp: : $V\_\{i+1\}(s):=\; \backslash max$a \left{ \sum{s'} P_a(s,s') \left(R_a(s,s') + \gamma V_i(s') \right) \right}, trong đó $i$ là số lần lặp. Giá trị lặp bắt đầu tại $i\; =\; 0$ và $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 $V${i+1} cho tất cả các trạng thái $s$, cho đến khi $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 $\backslash 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 $V$ hoặc $\backslash 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 $s$ đã biết khi hành động được thực hiện; nếu không thì $\backslash 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). 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 $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ó): : $\backslash \; Q(s,a)\; =\; \backslash sum\_\{s\text{'}\}\; P\_a(s,s\text{'})\; (R\_a(s,s\text{'})\; +\; \backslash gamma\; V(s\text{'})).\backslash$ 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 $(s,\; a)$ (cùng với kết quả $s\text{'}$); đó là, "Tôi đã ở trong trạng thái $s$ và tôi cố gắng thực hiện $a$ và $s\text{'}$ xảy ra"). Vì vậy, ta có một dãy $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 $(S,A,P)$ có thể được hiểu trong khuôn khổ của Lý thuyết Phân loại. Cụ thể. cho $\backslash 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 [http://ncatlab.org/nlab/show/Giry+monad Giry monad]. Thì một hàm tử $\backslash mathcal\{A\}\backslash to\backslash 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ả $(\backslash mathcal\{C\},\; F:\backslash mathcal\{C\}\backslash to\; \backslash 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 $\backslash 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,

• $\backslash mathcal\{S\}$: Không gian trạng thái;
• $\backslash mathcal\{A\}$: Không gian hành động;
• $q(i|j,a)$: $\backslash mathcal\{S\}\backslash times\; \backslash mathcal\{A\}\; \backslash rightarrow\; \backslash triangle\; \backslash mathcal\{S\}$, hàm tốc độ chuyển tiếp;
• $R(i,a)$: $\backslash mathcal\{S\}\backslash times\; \backslash mathcal\{A\}\; \backslash rightarrow\; \backslash 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,
• $\backslash mathcal\{X\}$: Không gian trạng thái.;
• $\backslash mathcal\{U\}$: Không gian kiểm soát tốt;
• $f(x,u)$: $\backslash mathcal\{X\}\backslash times\; \backslash mathcal\{U\}\; \backslash rightarrow\; \backslash triangle\; \backslash mathcal\{X\}$, hàm tốc độ chuyển tiếp;
• $r(x,u)$: $\backslash mathcal\{X\}\backslash times\; \backslash mathcal\{U\}\; \backslash rightarrow\; \backslash mathbb\{R\}$, hàm tốc độ phần thưởng kiểu như$r(x(t),u(t))dt=dR(x(t),u(t))$, trong đó  $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: : $\backslash max\; \backslash quad\; \backslash mathbb\{E\}\_u[\backslash int\_0^\{\backslash infty\}\backslash gamma^t\; r(x(t),u(t)))dt|x\_0]$ Trong đó 

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 [http://www.springer.com/mathematics/applications/book/978-3-642-02546-4 Quá trình Quyết định Markov thời gian Liên tục]), nếu hàm giá trị tối ưu  $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: : $g\backslash geq\; R(i,a)+\backslash sum\_\{j\backslash in\; S\}q(j|i,a)h(j)\; \backslash quad\; \backslash forall\; i\; \backslash in\; S\; \backslash ,\backslash ,\; and\; \backslash ,\backslash ,\; a\backslash in\; A(i)$ Nếu tồn tại một hàm $h$, thì $\backslash bar\; V^$ sẽ là  g nhỏ nhất thỏa mãn phương trình ở trên. Để tìm $\backslash 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) :
• Quy hoạch tuyến tính kép(D-LP) : {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{align} $y(i,a)$ là một lời giải khả thi cho D-LP nếu $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 $y^*(i,a)$ cho D-LP được cho là một lời giải tối ưu nếu : $\backslash begin\{align\}\; \backslash sum\_\{i\backslash in\; S\}\backslash sum\_\{a\backslash in\; A(i)\}R(i,a)y^*(i,a)\; \backslash geq\; \backslash sum\_\{i\backslash in\; S\}\backslash sum\_\{a\backslash in\; A(i)\}R(i,a)y(i,a)\; \backslash end\{align\}$ đố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 $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 :

D($\backslash cdot$) là hàm phần thưởng cuối, $x(t)$ là vector trạng thái hệ thống, $u(t)$ là vector điều khiển hệ thống, ta sẽ phải đi tìm. f($\backslash 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: : $0=\backslash text\{max\}\_u\; (r(t,x,u)\; +\backslash frac\{\backslash partial\; V(t,x)\}\{\backslash 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 $u(t)$, sẽ cho chúng ta giá trị tối ưu $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 $\backslash beta$ or $\backslash 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 $\backslash alpha$. 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 $Pr(s,a,s\text{'})$, $Pr(s\text{'}|s,a)$ hoặc, hiếm hoi hơn, $p\_\{s\text{'}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.

• 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.