Markovove rozhodovacie procesy: stavy, akcie, odmeny a Bellmanove rovnice

Nech

1. S je konečná neprázdna množina (množina stavov),
2. A je konečná neprázdna množina (množina akcií),
3. P : S × A × S → [0, 1], (s, a, s′) ↦ P(s′ | s, a), je funkcia taká, že ∑_{s′ ∈ S} P(s′ | s, a) = 1 pre všetky s ∈ S a a ∈ A (prechodové pravdepodobnosti — pre každú dvojicu (s, a) je P(· | s, a) rozdelenie na S),
4. R : S × A × S → ℝ je funkcia (odmena za prechod z s akciou a do s′),
5. γ ∈ [0, 1) je číslo (diskontný faktor).

Markovov rozhodovací proces (MDP) je pätica

(S, A, P, R, γ).

Priebeh procesu: v časoch t = 0, 1, 2, … je agent v stave s_t ∈ S, zvolí akciu a_t ∈ A, svet ho presunie do stavu s_t+1 a agent dostane odmenu r_t+1 = R(s_t, a_t, s_t+1). Stavy s_t a akcie a_t sú náhodné veličiny a platí Markovova vlastnosť: pre každé t ∈ ℕ₀ a všetky s₀, …, s_t−1, s, s′ ∈ S, a₀, …, a_t−1, a ∈ A, pre ktoré má podmienka kladnú pravdepodobnosť,

P(s_t+1 = s′ | s_t = s, a_t = a, s_t−1, a_t−1, …, s₀, a₀) = P(s′ | s, a).

Ďalší stav teda závisí len od súčasného stavu a akcie, nie od histórie — rovnako ako pri Markovovom reťazci, len prechod navyše ovplyvňuje voľba agenta. Stav s ∈ S je koncový práve vtedy, keď P(s | s, a) = 1 a R(s, a, s) = 0 pre každé a ∈ A: kto doň vstúpi, už v ňom zostane a nič ďalšie nedostane — tým sa modeluje koniec epizódy (u nás útes a oba ciele).

Agent stojí na políčku vpravo od štartu (nad ním je stena, pod ním útes) a zvolí „doprava“, p = 0,2:

• 0,8 — ďalšie políčko vpravo,
• 0,1 — útes (odmena −10, koniec),
• 0,1 — políčko vpravo od štartu (pošmykne sa hore do steny a zostane na mieste),

spolu 0,8 + 0,1 + 0,1 = 1 (farby podľa vzorca vyššie: zamýšľaný krok a pošmyknutie nabok). Očakávaná okamžitá odmena tohto ťahu je 0,8 · 0 + 0,1 · (−10) + 0,1 · 0 = −1: v priemere každý desiaty taký krok skončí pádom.

Nech (S, A, P, R, γ) je MDP a r₁, r₂, … ∈ ℝ sú odmeny, ktoré agent postupne dostane. Výnos z času t ∈ ℕ₀ je diskontovaný súčet budúcich odmien

G_t = ∑_k=0^∞ γ^k r_t+k+1 = r_t+1 + γ r_t+2 + γ² r_t+3 + …

(rad konverguje, pozri vetu nižšie; po vstupe do koncového stavu sú všetky ďalšie odmeny 0).

Stratégia (policy) je pravidlo, podľa ktorého agent volí akciu podľa súčasného stavu:

1. deterministická stratégia je funkcia π : S → A; agent v čase t volí a_t = π(s_t);
2. stochastická stratégia je funkcia π : A × S → [0, 1], (a, s) ↦ π(a | s), taká, že ∑_{a ∈ A} π(a | s) = 1 pre každé s ∈ S; agent volí akciu náhodne s P(a_t = a | s_t = s, história) = π(a | s).

Deterministická stratégia je osobitný prípad stochastickej s π(a | s) = 1 práve vtedy, keď a = π(s). Pevná stratégia π urobí z MDP Markovov reťazec na S s prechodovými pravdepodobnosťami p_ss′ = ∑_{a ∈ A} π(a | s) P(s′ | s, a). Cieľom je stratégia s čo najväčším očakávaným výnosom (presne v definícii hodnotovej funkcie nižšie).

Nech (S, A, P, R, γ) je MDP s γ ∈ [0, 1) a R_max = max_{s, s′ ∈ S, a ∈ A} |R(s, a, s′)| (maximum existuje, pretože S aj A sú konečné). Potom pre každú stratégiu, každé t ∈ ℕ₀ a každý priebeh procesu rad G_t absolútne konverguje a

|G_t| ≤ R_max (1 + γ + γ² + …) = R_max/1 − γ,

aj keby epizóda nikdy neskončila.

Dôkaz. Každá odmena je r_t+k+1 = R(s_t+k, a_t+k, s_t+k+1), takže |r_t+k+1| ≤ R_max. Trojuholníková nerovnosť dá |G_t| ≤ ∑_{k ≥ 0} γ^k |r_t+k+1| ≤ R_max ∑_{k ≥ 0} γ^k a geometrický rad s kvocientom 0 ≤ γ < 1 má súčet 1/1 − γ. ∎

U nás R_max = 10 a γ = 0,9, takže |G| ≤ 10/0,1 = 100. Bez ceny za krok je to ešte oveľa menej: nenulovú odmenu dá len vstup do cieľa alebo útesu, a to najviac raz za epizódu, takže |G| ≤ 10. Preto sa γ = 1 dá použiť len tam, kde epizóda určite skončí.

Na pevnej podlahe vedie najkratšia cesta k cieľu +10 cez 6 krokov. Prvých päť krokov dá odmenu 0, šiesty (vstup do cieľa) +10. S γ = 0,9:

G₀ = 0 + 0,9 · 0 + 0,9² · 0 + 0,9³ · 0 + 0,9⁴ · 0 + 0,9⁵ · 10 = 0,59049 · 10 = 5,9049.

Na pevnej podlahe sa nič náhodné nedeje, takže toto je priamo hodnota štartu — a výpočet hodnotovou iteráciou v oddiele o stratégiách dá skutočne 5,90. Malý cieľ +1 by aj za 3 kroky dal len 0,9² · 1 = 0,81.

Nech (S, A, P, R, γ) je MDP s γ ∈ [0, 1), π stratégia a E_π značí strednú hodnotu pri správaní podľa π. Hodnotová funkcia stratégie π je funkcia V^π : S → ℝ a hodnota akcie je funkcia Q^π : S × A → ℝ,

V^π(s) = E_π[G_t | s_t = s],   Q^π(s, a) = E_π[G_t | s_t = s, a_t = a]

(vďaka Markovovej vlastnosti nezávisia od t). V^π(s) je teda očakávaný výnos, keď agent začne v s a riadi sa π; pri Q^π(s, a) prvú akciu a určíme sami a až potom sa agent riadi π. Optimálne hodnoty sú

V*(s) = max_π V^π(s),   Q*(s, a) = max_π Q^π(s, a)   pre všetky s ∈ S, a ∈ A,

a stratégia π* je optimálna práve vtedy, keď V^π*(s) = V*(s) pre všetky s ∈ S. (Pri konečnom MDP s γ < 1 maximá existujú a existuje optimálna deterministická stratégia.)

Platí (Richard Bellman, 1957):

1. Bellmanova rovnica pre deterministickú stratégiu π: pre všetky s ∈ S V^π(s) = ∑_{s′ ∈ S} P(s′ | s, π(s)) [R(s, π(s), s′) + γ V^π(s′)];
2. Bellmanova rovnica optimality: pre všetky s ∈ S a a ∈ A Q*(s, a) = ∑_{s′ ∈ S} P(s′ | s, a) [R(s, a, s′) + γ V*(s′)],   V*(s) = max_{a ∈ A} Q*(s, a), a V* je jediná funkcia S → ℝ, ktorá tieto rovnice spĺňa;
3. každá deterministická stratégia π* s π*(s) ∈ argmax_{a ∈ A} Q*(s, a) pre všetky s ∈ S je optimálna.

Hotové optimálne hodnoty susedov štartu: políčko nad štartom V* = 3,325, políčko vpravo V* = 2,260, samotný štart V* = 2,854; útes je koncový (hodnota 0, odmena −10). Dosadíme do pravej strany pre každú akciu (farby podľa Bellmanovej rovnice vyššie):

• ↑: 0,8 · (0 + 0,9 · 3,325) + 0,1 · (0 + 0,9 · 2,260) + 0,1 · (0 + 0,9 · 2,854) = 2,854,
• →: 0,8 · (0 + 0,9 · 2,260) + 0,1 · (−10 + 0,9 · 0,000) + 0,1 · (0 + 0,9 · 3,325) = 0,926,
• ↓: 0,8 · (−10 + 0,9 · 0,000) + 0,1 · (0 + 0,9 · 2,854) + 0,1 · (0 + 0,9 · 2,260) = −7,540,
• ←: 0,8 · (0 + 0,9 · 2,854) + 0,1 · (0 + 0,9 · 3,325) + 0,1 · (−10 + 0,9 · 0,000) = 1,354,

Výsledky sú Q*(štart, a). Najväčšia (max_a) je ↑ s 2,854, a to je presne V*(štart) — rovnica platí (rozdiel v poslednej číslici je zaokrúhlenie). Akcia „hore“ má cenu aj napriek 10 % šanci, že sa agent pošmykne doľava, narazí na okraj a zostane na štarte: preto sa V*(štart) objavuje aj vpravo. Akcia „dole“ vedie z 80 % do útesu a vyjde hlboko záporná.

Bellmanov operátor MDP (S, A, P, R, γ) je zobrazenie B, ktoré každej funkcii V : S → ℝ priradí funkciu BV : S → ℝ,

(BV)(s) = max_{a ∈ A} ∑_{s′ ∈ S} P(s′ | s, a) [R(s, a, s′) + γ V(s′)].

Hodnotová iterácia je algoritmus:

• vstup: MDP (S, A, P, R, γ) s γ ∈ [0, 1) a tolerancia ε > 0;
• výstup: približné optimálne hodnoty V : S → ℝ a deterministická stratégia π : S → A.

1. Polož V₀(s) = 0 pre všetky s ∈ S a k = 0.
2. Vypočítaj V_k+1 = BV_k, t. j. V_k+1(s) = max_a ∑_s′ P(s′ | s, a) [R(s, a, s′) + γ V_k(s′)] pre všetky s ∈ S.
3. Ak je max_{s ∈ S} |V_k+1(s) − V_k(s)| < ε, pokračuj krokom 4; inak zvýš k o 1 a vráť sa ku kroku 2.
4. Vráť V = V_k+1 a π(s) ∈ argmax_a ∑_s′ P(s′ | s, a) [R(s, a, s′) + γ V(s′)] pre každé s ∈ S.

Pre γ < 1 je B kontrakcia v maximovej norme: pre všetky U, V : S → ℝ platí max_s |(BU)(s) − (BV)(s)| ≤ γ · max_s |U(s) − V(s)|. Keďže BV* = V* (Bellmanova rovnica optimality), vyplýva odtiaľ max_s |V_k(s) − V*(s)| ≤ γ^k · max_s |V₀(s) − V*(s)|: chyba klesá aspoň ako γ^k a algoritmus pre každé ε > 0 skončí. Koncové stavy majú podľa definície MDP V_k = 0 v každom kole, preto ich pseudokód nižšie vôbec neprepočítava.

Sledujeme dve políčka v prostrednom riadku: A hneď vľavo od veľkého cieľa +10 a B o políčko ďalej, hneď vpravo od malého cieľa +1. Nad B je stena, nad A voľno, pod oboma obyčajná podlaha.

Kolo 1 (všade V₀ = 0): z A vedie krok doprava s pravdepodobnosťou 0,8 do cieľa, teda 0,8 · 10 = 8,000. Z B zatiaľ nič vzdialené vidieť nie je, najlepší je krok doľava k malému cieľu: 0,8 · 1 = 0,800.

Kolo 2: z B doprava sa dôjde do A, ktoré už má hodnotu 8: 0,8 · 0,9 · 8 = 5,76, k tomu 0,1 · 0,9 · 0,8 = 0,072 za pošmyknutie hore (stena, zostane v B s V₁ = 0,8) a 0 za pošmyknutie dole — spolu 5,832 (farby podľa Bellmanovej rovnice v predchádzajúcom oddiele; nová hodnota V_k+1 má farbu V*). Najlepšia akcia v B sa preklopila z ← na →: informácia o veľkom cieli doputovala o políčko ďalej.

Iterácia stratégie (Ronald Howard, 1960) je algoritmus:

• vstup: MDP (S, A, P, R, γ) s γ ∈ [0, 1) a počiatočná deterministická stratégia π₀ : S → A;
• výstup: optimálna deterministická stratégia π a jej hodnotová funkcia V^π = V*.

1. Polož i = 0.
2. Vyhodnotenie: vypočítaj V^π_i : S → ℝ ako (jediné) riešenie sústavy |S| lineárnych rovníc V(s) = ∑_{s′ ∈ S} P(s′ | s, π_i(s)) [R(s, π_i(s), s′) + γ V(s′)],   s ∈ S.
3. Zlepšenie: pre každé s ∈ S zvoľ π_i+1(s) ∈ argmax_{a ∈ A} Q^π_i(s, a), kde Q^π_i(s, a) = ∑_s′ P(s′ | s, a) [R(s, a, s′) + γ V^π_i(s′)]; ak je π_i(s) medzi maximami, ponechaj π_i+1(s) = π_i(s).
4. Ak je π_i+1 = π_i (t. j. π_i+1(s) = π_i(s) pre všetky s ∈ S), zastav a vráť π = π_i; inak zvýš i o 1 a vráť sa ku kroku 2.

Že je vrátená stratégia optimálna a že algoritmus vždy skončí, hovorí veta o zlepšení stratégie nižšie.

Nech (S, A, P, R, γ) je MDP s γ ∈ [0, 1), π : S → A deterministická stratégia a π′ : S → A deterministická stratégia taká, že π′(s) ∈ argmax_{a ∈ A} Q^π(s, a) pre všetky s ∈ S. Potom

1. V^π′(s) ≥ V^π(s) pre všetky s ∈ S;
2. ak je Q^π(s, π(s)) = max_{a ∈ A} Q^π(s, a) pre všetky s ∈ S (zlepšenie nemá čo zmeniť, π′ = π), potom V^π spĺňa Bellmanovu rovnicu optimality, V^π = V* a π je optimálna;
3. inak existuje s ∈ S s V^π′(s) > V^π(s).

Náčrt dôkazu. Z voľby π′ je V^π(s) = Q^π(s, π(s)) ≤ Q^π(s, π′(s)) = E[r + γ V^π(s′)]. Do V^π(s′) dosadíme tú istú nerovnosť, potom znova… Po rozvinutí zostane očakávaný výnos stratégie, ktorá hrá π′ vo všetkých krokoch, teda V^π′(s). ∎

Deterministických stratégií je konečne veľa — u nás 4 akcie v 19 nekoncových políčkach, teda 4¹⁹ ≈ 2,7 · 10¹¹. Žiadna sa nemôže zopakovať (každé kolo hodnotu zlepší, alebo skončí), takže iterácia stratégie skončí vždy. V skutočnosti stačí prekvapivo málo kôl: u nás 6.