Wiki

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


{displaystyle s}

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




(

,

)
,

R




(

,

)
,
γ
)


{displaystyle (S,A,P_{cdot }(cdot ,cdot ),R_{cdot }(cdot ,cdot ),gamma )}

, trong đó




  • S


    {displaystyle S}

     là một tập hữu hạn các trạng thái,




  • A


    {displaystyle A}

    là một tập hữu hạn các hành động (ngoài ra,





    A

    s




    {displaystyle A_{s}}

     là tập hữu hạn các hành động có sẵn từ trạng thái




    s


    {displaystyle s}

    ),





  • P

    a


    (
    s
    ,

    s


    )
    =
    Pr
    (

    s

    t
    +
    1


    =

    s




    s

    t


    =
    s
    ,

    a

    t


    =
    a
    )


    {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 




    a


    {displaystyle a}

     trong trạng thái 




    s


    {displaystyle s}

     tại thời gian




    t


    {displaystyle t}

     sẽ dấn đến trạng thái 





    s




    {displaystyle s’}

     tại thời gian 




    t
    +
    1


    {displaystyle t+1}

    ,





  • R

    a


    (
    s
    ,

    s


    )


    {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 





    s




    {displaystyle s’}

     từ trạng thái 




    s


    {displaystyle s}

    ,




  • γ

    [
    0
    ,
    1
    ]


    {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 




S


{displaystyle S}

 hoặc 




A


{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 




π
(
s
)


{displaystyle pi (s)}

 rằng người ra quyết định sẽ chọn khi trong trạng thái




s


{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:







t
=
0







γ

t



R


a

t




(

s

t


,

s

t
+
1


)



{displaystyle sum _{t=0}^{infty }{gamma ^{t}R_{a_{t}}(s_{t},s_{t+1})}}

   (trong đó ta chọn 





a

t


=
π
(

s

t


)


{displaystyle a_{t}=pi (s_{t})}

)

trong đó 




 
γ
 


{displaystyle gamma }

 là hệ số chiết khấu và thỏa mãn 




0

 
γ
 
<
1


{displaystyle 0leq gamma <1}

. (Ví dụ,




γ
=
1

/

(
1
+
r
)


{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 




s


{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




P


{displaystyle P}

 và hàm phần thưởng 




R


{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ị




V


{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à




V
(
s
)


{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




s


{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:




π
(
s
)
:=
arg


max

a



{





s





P

a


(
s
,

s


)

(


R

a


(
s
,

s


)
+
γ
V
(

s


)

)


}



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




V
(
s
)
:=




s





P

π
(
s
)


(
s
,

s


)

(


R

π
(
s
)


(
s
,

s


)
+
γ
V
(

s


)

)



{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




π
(
s
)


{displaystyle pi (s)}

được tính toán trong




V
(
s
)


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

Thay thế tính toán của




π
(
s
)


{displaystyle pi (s)}

vào tính toán của




V
(
s
)


{displaystyle V(s)}

cho ta bước kết hợp:





V

i
+
1


(
s
)
:=

max

a



{





s





P

a


(
s
,

s


)

(


R

a


(
s
,

s


)
+
γ

V

i


(

s


)

)


}

,


{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 đó




i


{displaystyle i}

là số lần lặp. Giá trị lặp bắt đầu tại




i
=
0


{displaystyle i=0}





V

0




{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





V

i
+
1




{displaystyle V_{i+1}}

cho tất cả các trạng thái




s


{displaystyle s}

, cho đến khi




V


{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




V


{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




s


{displaystyle s}

 đã biết khi hành động được thực hiện; nếu không thì 




π
(
s
)


{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). 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


{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ó):




 
Q
(
s
,
a
)
=




s





P

a


(
s
,

s


)
(

R

a


(
s
,

s


)
+
γ
V
(

s


)
)
.
 


{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




(
s
,
a
)


{displaystyle (s,a)}

(cùng với kết quả





s




{displaystyle s’}

); đó là, “Tôi đã ở trong trạng thái




s


{displaystyle s}

và tôi cố gắng thực hiện




a


{displaystyle a}





s




{displaystyle s’}

xảy ra”). Vì vậy, ta có một dãy




Q


{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




(
S
,
A
,
P
)


{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






A




{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ử






A




D
i
s
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ả




(


C


,
F
:


C




D
i
s
t



{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






C




{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,






  • S




    {displaystyle {mathcal {S}}}

    : Không gian trạng thái;






  • A




    {displaystyle {mathcal {A}}}

    : Không gian hành động;




  • q
    (
    i

    |

    j
    ,
    a
    )


    {displaystyle q(i|j,a)}

    :






    S


    ×


    A






    S




    {displaystyle {mathcal {S}}times {mathcal {A}}rightarrow triangle {mathcal {S}}}

    , hàm tốc độ chuyển tiếp;




  • R
    (
    i
    ,
    a
    )


    {displaystyle R(i,a)}

    :






    S


    ×


    A




    R



    {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,






  • X




    {displaystyle {mathcal {X}}}

    : Không gian trạng thái.;






  • U




    {displaystyle {mathcal {U}}}

    : Không gian kiểm soát tốt;




  • f
    (
    x
    ,
    u
    )


    {displaystyle f(x,u)}

    :






    X


    ×


    U






    X




    {displaystyle {mathcal {X}}times {mathcal {U}}rightarrow triangle {mathcal {X}}}

    , hàm tốc độ chuyển tiếp;




  • r
    (
    x
    ,
    u
    )


    {displaystyle r(x,u)}

    :






    X


    ×


    U




    R



    {displaystyle {mathcal {X}}times {mathcal {U}}rightarrow mathbb {R} }

    , hàm tốc độ phần thưởng kiểu như




    r
    (
    x
    (
    t
    )
    ,
    u
    (
    t
    )
    )
    d
    t
    =
    d
    R
    (
    x
    (
    t
    )
    ,
    u
    (
    t
    )
    )


    {displaystyle r(x(t),u(t))dt=dR(x(t),u(t))}

    , trong đó  




    R
    (
    x
    ,
    u
    )


    {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:




max



E


u


[



0






γ

t


r
(
x
(
t
)
,
u
(
t
)
)
)
d
t

|


x

0


]


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

Trong đó 




0

γ
<
1


{displaystyle 0leq 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  





V






{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:




g

R
(
i
,
a
)
+



j

S


q
(
j

|

i
,
a
)
h
(
j
)


i

S


a
n
d


a

A
(
i
)


{displaystyle ggeq R(i,a)+sum _{jin S}q(j|i,a)h(j)quad forall iin S,,and,,ain A(i)}

Nếu tồn tại một hàm 




h


{displaystyle h}

, thì 








V
¯









{displaystyle {bar {V}}^{*}}

 sẽ là  g nhỏ nhất thỏa mãn phương trình ở trên. Để tìm 








V
¯









{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)








Minimize




g





s.t




g




j

S


q
(
j

|

i
,
a
)
h
(
j
)

R
(
i
,
a
)



i

S
,

a

A
(
i
)






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

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








Maximize







i

S





a

A
(
i
)


R
(
i
,
a
)
y
(
i
,
a
)





s.t.







i

S





a

A
(
i
)


q
(
j

|

i
,
a
)
y
(
i
,
a
)
=
0


j

S
,









i

S





a

A
(
i
)


y
(
i
,
a
)
=
1
,





y
(
i
,
a
)

0


a

A
(
i
)


a
n
d



i

S






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




y
(
i
,
a
)


{displaystyle y(i,a)}

 là một lời giải khả thi cho D-LP nếu 




y
(
i
,
a
)


{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 





y




(
i
,
a
)


{displaystyle y^{*}(i,a)}

 cho D-LP được cho là một lời giải tối ưu nếu











i

S





a

A
(
i
)


R
(
i
,
a
)

y




(
i
,
a
)




i

S





a

A
(
i
)


R
(
i
,
a
)
y
(
i
,
a
)






{displaystyle {begin{aligned}sum _{iin S}sum _{ain A(i)}R(i,a)y^{*}(i,a)geq sum _{iin S}sum _{ain 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 





y




(
i
,
a
)


{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








V
(
x
(
0
)
,
0
)
=




max


u





0


T


r
(
x
(
t
)
,
u
(
t
)
)
d
t
+
D
[
x
(
T
)
]




s
.
t
.






d
x
(
t
)


d
t



=
f
[
t
,
x
(
t
)
,
u
(
t
)
]






{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,




x
(
t
)


{displaystyle x(t)}

là vector trạng thái hệ thống,




u
(
t
)


{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:




0
=


max


u


(
r
(
t
,
x
,
u
)
+




V
(
t
,
x
)



x



f
(
t
,
x
,
u
)
)


{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 




u
(
t
)


{displaystyle u(t)}

, sẽ cho chúng ta giá trị tối ưu 





V






{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 




a


{displaystyle a}

điều khiển




u


{displaystyle u}

phần thưởng




R


{displaystyle R}

chi phí




g


{displaystyle g}




g


{displaystyle g}

là phủ định của




R


{displaystyle R}

giá trị 




V


{displaystyle V}

chi phí phải trả




J


{displaystyle J}




J


{displaystyle J}

là phủ định của




V


{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 





P

a


(
s
,

s


)


{displaystyle P_{a}(s,s’)}

Xác suất chuyển tiếp





p

s

s




(
a
)


{displaystyle p_{ss’}(a)}

Ngoài ra, xác suất chuyển tiếp đôi khi được viết dưới dạng 




P
r
(
s
,
a
,

s


)


{displaystyle Pr(s,a,s’)}

,




P
r
(

s



|

s
,
a
)


{displaystyle Pr(s’|s,a)}

 hoặc, hiếm hoi hơn,





p


s


s


(
a
)
.


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

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

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ú


Back to top button