Luarea deciziilor Markov

Luarea deciziilor Markov ( MDP ), numită după matematicianul Andrej Andreevič Markov (1856-1922) , oferă un cadru matematic pentru modelarea luării deciziilor în situații în care rezultatele sunt parțial aleatorii și parțial sub controlul unui factor de decizie . MDP-urile sunt utile pentru studierea unei game largi de probleme de optimizare rezolvate cu programare dinamică și învățare cu întărire . MDP-urile sunt cunoscute din 1950 ^[1] . Acestea sunt utilizate într-o zonă largă de discipline în care luarea deciziilor are loc într-un mediu dinamic, inclusiv robotică , automatizare , economie și producție industrială .

Mai precis, un proces decizional Markov este un proces de control stocastic în timp discret. Dacă starea și spațiile de acțiune sunt finite, atunci problema se numește MDP finit. MDP-urile finite sunt deosebit de importante pentru teoria dell ' învățării prin întărire (învățare prin întărire).

Definiție

Un MDP terminat este definit de:

un spațiu de stări $S.$ ${\ displaystyle S}$ $S.$ ;
un spațiu pentru acțiuni $A=U_{s}\in _{s}A(s)$ ${\ displaystyle A = U_ {s} \ in _ {s} A (s)}$ $A = U_ {s} \ in _ {s} A (s)$ care poate fi întreprins în funcție de stat;
probabilitățile de tranziție $P_{a}(s,s'):S\times A\times S\mapsto \mathbb {R}$ ${\ displaystyle P_ {a} (s, s '): S \ times A \ times S \ mapsto \ mathbb {R}}$ ${\ displaystyle P_ {a} (s, s '): S \ times A \ times S \ mapsto \ mathbb {R}}$ ele definesc dinamica cu un singur pas a mediului, adică probabilitatea ca, dată fiind o stare $s$ ${\ displaystyle s}$ $s$ și o acțiune $la$ ${\ displaystyle a}$ $la$ la momentul $t$ ${\ displaystyle t}$ $t$ , se ajunge la următoarea stare posibilă $s^{'}$ ${\ displaystyle s '}$ $e$ : $P_{a}(s,s')=\Pr(s_{t+1}=s'\mid s_{t}=s,a_{t}=a)$ ${\ displaystyle P_ {a} (s, s ') = \ Pr (s_ {t + 1} = s' \ mid s_ {t} = s, a_ {t} = a)}$ $P_ {a} (s, s ') = \ Pr (s _ {{t + 1}} = s' \ mid s_ {t} = s, a_ {t} = a)$ ;
valoarea așteptată a recompensei $R_{a}(s,s')$ ${\ displaystyle R_ {a} (s, s ')}$ $R_ {a} (s, s ')$ : a primit un statut $s$ ${\ displaystyle s}$ $s$ și o acțiune $la$ ${\ displaystyle a}$ $la$ , dacă treceți la stat $s^{'}$ ${\ displaystyle s '}$ $e$ primești o recompensă egală cu ( $ȘI$ ${\ displaystyle E}$ $ȘI$ reprezintă valoarea așteptată sau prognoza) $R_{a}(s,s')=R(s'|s,a)=E(r_{t+1}\mid s_{t}=s,a_{t}=a,s_{t+1}=s')$ ${\ displaystyle R_ {a} (s, s ') = R (s' | s, a) = E (r_ {t + 1} \ mid s_ {t} = s, a_ {t} = a, s_ { t + 1} = s ')}$ ${\ displaystyle R_ {a} (s, s ') = R (s' | s, a) = E (r_ {t + 1} \ mid s_ {t} = s, a_ {t} = a, s_ { t + 1} = s ')}$ ;
$\gamma \in [0,1]$ ${\ displaystyle \ gamma \ in [0,1]}$ $\ gamma \ în [0,1]$ este factorul de reducere care reprezintă diferența importantă între recompensele viitoare și recompensele prezente .

(Notă: teoria lui Markov privind luarea deciziilor nu specifică acest lucru $S.$ ${\ displaystyle S}$ $S.$ sau $LA$ ${\ displaystyle A}$ $LA$ sunt finite, dar algoritmii de bază anteriori presupun că sunt.)

Problemă

Problema centrală a unui MDP este de a identifica care este cea mai bună acțiune de efectuat într-o stare dată, pentru a obține valoarea maximă posibilă a unei funcții de recompensă cumulativă. Funcția care pentru fiecare stare $s\in S$ ${\ displaystyle s \ în S}$ $s \ în S$ identifică acțiunea $a\in A$ ${\ displaystyle a \ în A}$ $a \ in A$ de aplicat se numește „politică” (politică) staționară $\pi =S\mapsto A$ ${\ displaystyle \ pi = S \ mapsto A}$ ${\ displaystyle \ pi = S \ mapsto A}$ . De obicei, această funcție de evaluare a recompenselor este valoarea așteptată a unei sume reduse pe un orizont potențial infinit:

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

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

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

unde este

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

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

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

sunt acțiunile date de politică

{\textstyle \pi }

{\ textstyle \ pi}

{\ textstyle \ pi}

,

\gamma

{\ displaystyle \ gamma}

\gamă

este factorul de reducere între 0 și 1.

Datorită proprietății Markov , politica optimă $\pi ^{*}$ ${\ displaystyle \ pi ^ {*}}$ ${\ displaystyle \ pi ^ {*}}$ ceea ce maximizează recompensa cu reducerea așteptată, deoarece această problemă poate fi scrisă doar în funcție de stat ${\textstyle s}$ ${\ textstyle s}$ ${\ textstyle s}$ . Pentru a obține o politică de timp polinomială optimă pentru un anumit MDP, se folosesc adesea algoritmi de programare liniară sau, mai tradițional, algoritmi de programare dinamică ^[2] .

Algoritmi

Familia standard de algoritmi care calculează această politică optimă utilizează doi vectori, indexați cu starea, care se numesc: „valoare” $V.$ ${\ displaystyle V}$ $V.$ , care conține valori reale și „politică” ' $\pi$ ${\ displaystyle \ pi}$ $\ pi$ , care conține acțiunile. Când algoritmul se termină, $\pi$ ${\ displaystyle \ pi}$ $\ pi$ conține politica soluției e $V(s)$ ${\ displaystyle V (s)}$ ${\ displaystyle V (s)}$ conține suma redusă a recompenselor care trebuie obținute (în medie) în urma soluției $\pi (s)$ ${\ displaystyle \ pi (s)}$ ${\ displaystyle \ pi (s)}$ începând de la stat $s$ ${\ displaystyle s}$ $s$ .

Algoritmul are două tipuri de pași: o actualizare a valorii și o actualizare a politicii, care se repetă în toate stările și într-o anumită ordine, până când nu mai există modificări ale valorilor. Cele două actualizări recalculează recursiv o nouă valoare estimată pentru politica optimă și pentru valoarea de stat, utilizând o estimare anterioară a acestor valori.

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

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

{\ 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):=\sum _{s'}P_{\pi (s)}(s,s')\left(R_{\pi (s)}(s,s')+\gamma V(s')\right)

{\ displaystyle V (s): = \ sum _ {s '} P _ {\ pi (s)} (s, s') \ left (R _ {\ pi (s)} (s, s ') + \ gamma V (s ') \ dreapta)}

{\ displaystyle V (s): = \ sum _ {s '} P _ {\ pi (s)} (s, s') \ left (R _ {\ pi (s)} (s, s ') + \ gamma V (s ') \ dreapta)}

Ordinea actualizărilor depinde de varianta algoritmului. Ele pot fi aplicate tuturor statelor împreună, sau stat cu stat, secvențial sau chiar mai des pentru anumite state decât pentru altele. Atâta timp cât nici o stare nu este exclusă din pașii de actualizare, algoritmul va converge în cele din urmă către o soluție ^[3] .

Notă

^ Bellman, R., A Markovian Decision Process , în Journal of Mathematics and Mechanics , vol. 6, 1957.
^ Shoham, Y și Leyton-Brown, K, Sisteme multiagent ( PDF ), 2010 [2009] , p. 476. Adus la 10 decembrie 2018 .
^ (EN) Stewart N. Ethier, Procese Markov: caracterizare și convergență , Wiley, 1986, ISBN 9780470316658 ,OCLC 264 621 186 . Adus la 12 decembrie 2018 .

Bibliografie

Ronald A. Howard, Dynamic Programming and Markov Processes , The MIT Press, 1960.

Elemente conexe

Andrei Andreevich Markov (1856-1922)

Portal IT

Portalul de matematică

[1] Bellman, R., A Markovian Decision Process , în Journal of Mathematics and Mechanics , vol. 6, 1957.

[2] Shoham, Y și Leyton-Brown, K, Sisteme multiagent ( PDF ), 2010 [2009] , p. 476. Adus la 10 decembrie 2018 .

[3] (EN) Stewart N. Ethier, Procese Markov: caracterizare și convergență , Wiley, 1986, ISBN 9780470316658 ,OCLC 264 621 186 . Adus la 12 decembrie 2018 .

[1]

[2]

[3]