Markovovy rozhodovací procesy: stavy, akce, odměny a Bellmanovy rovnice

MDP na mřížkovém světě s útesem, výnos a diskont, hodnotová funkce a Bellmanova rovnice, hodnotová iterace a iterace strategie napsané od nuly, jak diskont, klouzání a cena kroku mění optimální chování, a kontrola simulací.

11 minut Matěj Žalmánek 2026-10-16

Série Základy AI Díl 78 z 83

Celá osnova série 83 z 83 témat hotovo

Co si odnesete

Jak se úloha posilovaného učení popíše jako MDP.
Co je hodnota stavu a jak ji spočítá Bellmanova rovnice.
Proč drobnosti v odměnách a diskontu úplně změní chování agenta.

Co se hodí znát předem: Markovovy řetězce: přechodová matice, stacionární rozdělení a PageRank, Střední hodnota, rozptyl a kovariance: kde rozdělení leží, jak je široké a co s čím souvisí, Druhy strojového učení: s učitelem, bez učitele, s částečným učitelem a další

Dosud se modely v sérii učily z příkladů se správnou odpovědí, nebo hledaly strukturu v datech. Posilované učení je třetí cesta: agent jedná, svět mu za to dává odměny a tresty a agent má přijít na to, jak jednat, aby jich nasbíral co nejvíc. Než se pustíme do učení, potřebujeme jazyk, kterým takovou úlohu přesně popíšeme. Tím je Markovův rozhodovací proces. V tomhle dílu ho postavíme na malém světě s útesem a spočítáme nejlepší chování přesně — za předpokladu, že pravidla světa známe.

Navazuje na díly Markovovy řetězce, Střední hodnota a Druhy strojového učení.

1. Agent, prostředí, odměna

Definice — Markovův rozhodovací proces (MDP)

Nechť

S je konečná neprázdná množina (množina stavů),
A je konečná neprázdná množina (množina akcí),
P : S × A × S → [0, 1], (s, a, s′) ↦ P(s′ | s, a), je funkce taková, že ∑_{s′ ∈ S} P(s′ | s, a) = 1 pro všechna s ∈ S a a ∈ A (přechodové pravděpodobnosti — pro každou dvojici (s, a) je P(· | s, a) rozdělení na S),
R : S × A × S → ℝ je funkce (odměna za přechod z s akcí a do s′),
γ ∈ [0, 1) je číslo (diskontní faktor).

Markovův rozhodovací proces (MDP) je pětice

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

Průběh procesu: v časech t = 0, 1, 2, … je agent ve stavu s_t ∈ S, zvolí akci a_t ∈ A, svět ho přesune do stavu s_t+1 a agent dostane odměnu r_t+1 = R(s_t, a_t, s_t+1). Stavy s_t a akce a_t jsou náhodné veličiny a platí Markovova vlastnost: pro každé t ∈ ℕ₀ a všechna s₀, …, s_t−1, s, s′ ∈ S, a₀, …, a_t−1, a ∈ A, pro která má podmínka kladnou pravděpodobnost,

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

Další stav tedy závisí jen na současném stavu a akci, ne na historii — stejně jako u Markovova řetězce, jen přechod navíc ovlivňuje volba agenta. Stav s ∈ S je koncový, právě když P(s | s, a) = 1 a R(s, a, s) = 0 pro každé a ∈ A: kdo do něj vstoupí, už v něm zůstane a nic dalšího nedostane — tím se modeluje konec epizody (u nás útes a oba cíle).

Laicky řečeno

Desková hra s kostkou: víte, na jakém jste políčku (stav), vyberete tah (akce), kostka rozhodne, kam se doopravdy posunete (přechod), a za některá políčka dostanete body (odměna). Na tom, jak jste se na políčko dostali, nezáleží — důležité je jen, kde stojíte teď.

Náš svět je mřížka 6 × 5. Agent začíná vlevo (S), může jít nahoru, doprava, dolů nebo doleva. Celý spodní řádek je útes: kdo do něj spadne, dostane −10 a hra končí. Kousek od startu je malý cíl za +1, daleko vpravo velký cíl za +10. Dvě zdi zavírají kratší cestu nahoru. A podlaha může klouzat: s pravděpodobností p agent místo zamýšleného směru uklouzne do jednoho ze dvou kolmých směrů.

P(s′ | s, a) = (1 − p) · [s′ = krok ve směru a] + p/2 · [s′ = krok kolmo vlevo] + p/2 · [s′ = krok kolmo vpravo]

P(s′ | s, a): s jakou pravděpodobností skončí agent po akci a v poli s′ — celé rozdělení, ne jen „kam to má jít“, protože hodnota tahu se bude počítat jako průměr přes všechna možná místa dopadu
(1 − p) · […]: zamýšlený pohyb — dostane většinu pravděpodobnosti; s p = 0 zbude jen tenhle člen a svět je deterministický
p/2 · […]: uklouznutí do strany, rovným dílem vlevo i vpravo — díky němu je pole vedle útesu nebezpečné, i když jdeme podél něj, a ne do něj

[podmínka] je 1, když podmínka platí, jinak 0. Narazí-li pohyb do zdi nebo okraje, je s′ = s a příslušné členy se sečtou — součet přes všechna s′ je vždy 1. Rozdělení (0,8; 0,1; 0,1) (tj. p = 0,2) má i klasický mřížkový svět z učebnice Russella a Norviga.

Příklad — krok doprava podél útesu

Agent stojí na poli vpravo od startu (nad ním je zeď, pod ním útes) a zvolí „doprava“, p = 0,2:

0,8 — další pole vpravo,
0,1 — útes (odměna −10, konec),
0,1 — pole vpravo od startu (uklouzne nahoru do zdi a zůstane na místě),

dohromady 0,8 + 0,1 + 0,1 = 1 (barvy podle vzorce výše: zamýšlený krok a uklouznutí do strany). Očekávaná okamžitá odměna tohoto tahu je 0,8 · 0 + 0,1 · (−10) + 0,1 · 0 = −1: v průměru každý desátý takový krok skončí pádem.

2. Výnos, diskont a strategie

Definice — výnos a strategie

Nechť (S, A, P, R, γ) je MDP a r₁, r₂, … ∈ ℝ jsou odměny, které agent postupně dostane. Výnos z času t ∈ ℕ₀ je diskontovaný součet budoucích odměn

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

(řada konverguje, viz větu níže; po vstupu do koncového stavu jsou všechny další odměny 0).

Strategie (policy) je pravidlo, podle kterého agent volí akci podle současného stavu:

deterministická strategie je funkce π : S → A; agent v čase t volí a_t = π(s_t);
stochastická strategie je funkce π : A × S → [0, 1], (a, s) ↦ π(a | s), taková, že ∑_{a ∈ A} π(a | s) = 1 pro každé s ∈ S; agent volí akci náhodně s P(a_t = a | s_t = s, historie) = π(a | s).

Deterministická strategie je zvláštní případ stochastické s π(a | s) = 1, právě když a = π(s). Pevná strategie π udělá z MDP Markovův řetězec na S s přechodovými pravděpodobnostmi p_ss′ = ∑_{a ∈ A} π(a | s) P(s′ | s, a). Cílem je strategie s co největším očekávaným výnosem (přesně v definici hodnotové funkce níže).

Laicky řečeno

Diskont γ říká, kolik je odměna zítra méně než dnes. S γ = 0,9 má odměna za deset kroků váhu 0,9¹⁰ ≈ 0,35, s γ = 0,5 jen 0,001. Malé γ dělá agenta netrpělivým, γ blízko 1 trpělivým. Strategie je pak prostě tahák: „na tomhle políčku jdi doprava, na tamtom nahoru“.

G_t = r_t+1 + γ · G_t+1

G_t: výnos od teď do konce — číslo, které chce agent mít co největší
r_t+1: odměna hned za příští krok — jediná, kterou dostane bez čekání, proto bez diskontu
γ: diskont — všechno, co přijde později, se zlevní o jeden činitel γ; tím se „později“ převádí na „méně“
G_t+1: výnos od příštího kroku — tatáž veličina o krok dál; rekurze, ze které za chvíli vyroste Bellmanova rovnice

Stačí vytknout γ ze všech členů kromě prvního: r_t+1 + γ (r_t+2 + γ r_t+3 + …).

Věta — s γ < 1 je výnos vždy konečný

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, protože S i A jsou konečné). Pak pro každou strategii, každé t ∈ ℕ₀ a každý průběh procesu řada G_t absolutně konverguje a

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

i kdyby epizoda nikdy neskončila.

Důkaz. Každá odměna je r_t+k+1 = R(s_t+k, a_t+k, s_t+k+1), takže |r_t+k+1| ≤ R_max. Trojúhelníková nerovnost dá |G_t| ≤ ∑_{k ≥ 0} γ^k |r_t+k+1| ≤ R_max ∑_{k ≥ 0} γ^k a geometrická řada s kvocientem 0 ≤ γ < 1 má souč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 ještě mnohem méně: nenulovou odměnu dá jen vstup do cíle nebo útesu, a to nejvýš jednou za epizodu, takže |G| ≤ 10. Proto γ = 1 jde použít jen tam, kde epizoda jistě skončí.

Příklad — výnos nejkratší cesty k velkému cíli

Na pevné podlaze vede nejkratší cesta k cíli +10 přes 6 kroků. Prvních pět kroků dá odměnu 0, šestý (vstup do cíle) +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 pevné podlaze se nic náhodného neděje, takže tohle je přímo hodnota startu — a výpočet hodnotovou iterací v oddílu o strategiích dá skutečně 5,90. Malý cíl +1 by i za 3 kroky dal jen 0,9² · 1 = 0,81.

3. Hodnota a Bellmanovy rovnice

Definice — hodnotová funkce a Bellmanova rovnice optimality

Nechť (S, A, P, R, γ) je MDP s γ ∈ [0, 1), π strategie a E_π značí střední hodnotu při chování podle π. Hodnotová funkce strategie π je funkce V^π : S → ℝ a hodnota akce je funkce Q^π : S × A → ℝ,

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

(díky Markovově vlastnosti nezávisí na t). V^π(s) je tedy očekávaný výnos, když agent začne v s a řídí se π; u Q^π(s, a) první akci a určíme sami a teprve potom se agent řídí π. Optimální hodnoty jsou

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

a strategie π* je optimální, právě když V^π*(s) = V*(s) pro všechna s ∈ S. (U konečného MDP s γ < 1 maxima existují a existuje optimální deterministická strategie.)

Platí (Richard Bellman, 1957):

Bellmanova rovnice pro deterministickou strategii π: pro všechna s ∈ S V^π(s) = ∑_{s′ ∈ S} P(s′ | s, π(s)) [R(s, π(s), s′) + γ V^π(s′)];
Bellmanova rovnice optimality: pro všechna 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á funkce S → ℝ, která tyto rovnice splňuje;
každá deterministická strategie π* s π*(s) ∈ argmax_{a ∈ A} Q*(s, a) pro všechna s ∈ S je optimální.

Laicky řečeno

Hodnota políčka = co z něj nejlépe vytěžím. A to se dá spočítat rekurzivně: z každého tahu dostanu okamžitou odměnu plus (trochu zlevněnou) hodnotu políčka, kam mě tah zavede — zprůměrovanou přes to, kam mě kostka může hodit. Vyberu tah, kde to vyjde nejvíc.

V*(s) = max_a ∑_s′ P(s′ | s, a) [R(s, a, s′) + γ V*(s′)]

V*(s): nejlepší očekávaný výnos z pole s — to, co hledáme; stojí na obou stranách, takže rovnice je podmínka, kterou musí hodnoty splnit všechny najednou
max_a: volba agenta — akci si vybírá sám, a tak bere tu nejlepší; tady se rovnice „optimality“ liší od rovnice pro pevnou strategii π, kde místo maxima stojí π(s)
∑_s′ P(s′ | s, a) […]: průměr přes to, kam agenta svět skutečně hodí — o tom agent nerozhoduje, proto střední hodnota, ne maximum
R(s, a, s′): okamžitá odměna za tenhle přechod (+1, +10, −10 nebo cena kroku)
γ: diskont — budoucnost je o krok dál, proto jeden činitel γ (stejně jako ve vzorci G_t = r_t+1 + γ G_t+1)
V*(s′): nejlepší výnos z místa dopadu — celá budoucnost shrnutá do jednoho čísla, takže se nemusí procházet všechny dlouhé cesty

Výraz za maximem je Q*(s, a): hodnota akce a v poli s, když se potom už hraje nejlépe.

Příklad — Bellmanova rovnice na startu (klouzání 20 %, γ = 0,9)

Hotové optimální hodnoty sousedů startu: pole nad startem V* = 3,325, pole vpravo V* = 2,260, start sám V* = 2,854; útes je koncový (hodnota 0, odměna −10). Dosadíme do pravé strany pro každou akci (barvy podle Bellmanovy rovnice výše):

↑: 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 jsou Q*(start, a). Největší (max_a) je ↑ s 2,854, a to je přesně V*(start) — rovnice platí (rozdíl v poslední číslici je zaokrouhlení). Akce „nahoru“ má cenu i přes 10% šanci, že agent uklouzne doleva, narazí na okraj a zůstane na startu: proto se V*(start) objevuje i vpravo. Akce „dolů“ vede z 80 % do útesu a vyjde hluboko záporná.

4. Hodnotová iterace

Definice — hodnotová iterace

Bellmanův operátor MDP (S, A, P, R, γ) je zobrazení B, které každé funkci V : S → ℝ přiřadí funkci BV : S → ℝ,

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

Hodnotová iterace je algoritmus:

vstup: MDP (S, A, P, R, γ) s γ ∈ [0, 1) a tolerance ε > 0;
výstup: přibližné optimální hodnoty V : S → ℝ a deterministická strategie π : S → A.

Polož V₀(s) = 0 pro všechna s ∈ S a k = 0.
Spočítej V_k+1 = BV_k, tj. V_k+1(s) = max_a ∑_s′ P(s′ | s, a) [R(s, a, s′) + γ V_k(s′)] pro všechna s ∈ S.
Je-li max_{s ∈ S} |V_k+1(s) − V_k(s)| < ε, pokračuj krokem 4; jinak zvyš k o 1 a vrať se ke kroku 2.
Vrať V = V_k+1 a π(s) ∈ argmax_a ∑_s′ P(s′ | s, a) [R(s, a, s′) + γ V(s′)] pro každé s ∈ S.

Pro γ < 1 je B kontrakce v maximové normě: pro všechny U, V : S → ℝ platí max_s |(BU)(s) − (BV)(s)| ≤ γ · max_s |U(s) − V(s)|. Protože BV* = V* (Bellmanova rovnice optimality), plyne odtud max_s |V_k(s) − V*(s)| ≤ γ^k · max_s |V₀(s) − V*(s)|: chyba klesá aspoň jako γ^k a algoritmus pro každé ε > 0 skončí. Koncové stavy mají podle definice MDP V_k = 0 v každém kole, proto je pseudokód níže vůbec nepřepočítává.

Laicky řečeno

V prvním kole znají hodnotu jen políčka hned vedle cílů. V druhém se informace posune o políčko dál, ve třetím o další. Jako když se zpráva šíří od souseda k sousedovi — po pár kolech ví každé políčko, kam se vyplatí jít.

# hodnotová iterace
V = 0 ve všech stavech
opakuj:
    pro každý nekoncový stav s:
        pro každou akci a:
            Q[a] = ∑ přes s′ ( P(s′ | s, a) · (R(s, a, s′) + γ · V(s′)) )
        V_nové(s) = max(Q)
    změna = max přes s |V_nové(s) − V(s)|
    V = V_nové
dokud změna ≥ 10⁻⁶
π(s) = akce s největším Q[a] (spočteným z konečného V)

Příklad — první tři kola (klouzání 20 %, γ = 0,9)

Sledujeme dvě pole v prostředním řádku: A hned vlevo od velkého cíle +10 a B o pole dál, hned vpravo od malého cíle +1. Nad B je zeď, nad A volno, pod oběma obyčejná podlaha.

kolo `k`	`V`_k(A)	nejlepší akce v A	`V`_k(B)	nejlepší akce v B
1	8,000	→	0,800	←
2	8,000	→	5,832	→
3	9,166	→	6,343	→

Kolo 1 (všude V₀ = 0): z A vede krok doprava s pravděpodobností 0,8 do cíle, tedy 0,8 · 10 = 8,000. Z B zatím nic dalekého vidět není, nejlepší je krok doleva k malému cíli: 0,8 · 1 = 0,800.

Kolo 2: z B doprava se dojde do A, které už má hodnotu 8: 0,8 · 0,9 · 8 = 5,76, k tomu 0,1 · 0,9 · 0,8 = 0,072 za uklouznutí nahoru (zeď, zůstane v B s V₁ = 0,8) a 0 za uklouznutí dolů — celkem 5,832 (barvy podle Bellmanovy rovnice v předchozím oddílu; nová hodnota V_k+1 má barvu V*). Nejlepší akce v B se překlopila z ← na →: informace o velkém cíli doputovala o pole dál.

max_s |V_k+1(s) − V_k(s)| ≤ γ^k · max_s |V₁(s) − V₀(s)|

max |V_k+1 − V_k|: největší změna v kole k + 1 — to, co výpočet sleduje a podle čeho se zastaví; v grafu níže zelená (γ = 0,9) a modrá (γ = 0,99) čára
γ^k: každé kolo zmenší rozdíl dvou odhadů aspoň γ-krát (kontrakce); po k kolech tedy γ^k-krát — proto pomalá konvergence pro γ blízko 1
max |V₁ − V₀|: velikost první změny; s V₀ = 0 je to největší očekávaná odměna za jeden krok, u nás nejvýš 10 — odtud čárkovaná mez 10 · γ^k v grafu

Hodnotová iterace na kluzké podlaze (p = 0,2): největší změna hodnoty v každé iteraci γ = 0,9 (50 iterací)γ = 0,99 (77 iterací) 10 · γ^k

S γ = 0,9 se hodnoty ustálí (změna pod 10⁻⁶) po 50 iteracích, s γ = 0,99 po 77. Chyba klesá rychleji, než zaručuje mez γ^k — ta platí vždy, ale u konkrétního světa bývá pesimistická. Čím blíž je γ k jedné, tím dál do budoucnosti se musí informace rozšířit a tím déle výpočet trvá.

5. Co změní diskont, klouzání a cena kroku

Teď to nejzajímavější. Stejný svět, jen jiná nastavení — a optimální strategie vypadá úplně jinak.

Bez klouzání a s klouzáním (γ = 0,9): hodnoty polí, optimální akce a nejpravděpodobnější cesta

Na pevné podlaze vede nejkratší cesta k velkému cíli těsně podél útesu: 6 kroků a hodnota startu 5,90. Když podlaha klouže, okraj útesu je nebezpečný — každý krok tam znamená šanci 10 % spadnout. Optimální strategie proto obejde zdi horem: 10 kroků místo 6, ale do útesu spadne jen 0,7 % epizod. Kdybychom na kluzké podlaze použili riskantní strategii, spadl by agent v 30 % případů a hodnota startu by klesla na 0,64 místo 2,85.

Netrpělivý agent a agent, kterého každý krok stojí

S γ = 0,5 je velký cíl tak daleko, že se nevyplatí — +10 za 10 kroků má dnes váhu jen 10 · 0,5¹⁰ ≈ 0,01. Agent jde opatrně horem k malému cíli. Když naopak každý krok stojí −1, vyplatí se riskovat: agent jde k velkému cíli po okraji útesu a v 27 % epizod spadne. Dlouhá bezpečná cesta by ho stála víc, než je průměrná ztráta pádem.

γ	klouzání	krok	cesta vede	V(start)	simulace	pád	kroků
0,9	0 %	0	k +10	5,90	5,90	0,0 %	6,0
0,9	20 %	0	k +10	2,85	2,84	0,7 %	13,1
0,5	20 %	0	k +1	0,01	0,01	0,0 %	9,5
0,9	20 %	−1	k +10	−2,86	−2,90	26,9 %	6,0
0,5	0 %	−1	k +1	−1,25	−1,25	0,0 %	3,0

Sloupec „simulace“ je kontrola: průměrný výnos z 10 000 epizod podle nalezené strategie, s náhodným klouzáním. Průměrný výnos se od vypočtené hodnoty startu liší nejvýš o pár setin — Bellmanova rovnice opravdu počítá očekávaný výnos.

Ponaučení pro skutečné aplikace: chování agenta neurčuje jen „co je cílem“, ale i drobnosti jako diskont a cena za krok. Kdo navrhuje odměny, navrhuje chování — i to, které nechtěl.

6. Iterace strategie

Definice — iterace strategie

Iterace strategie (Ronald Howard, 1960) je algoritmus:

vstup: MDP (S, A, P, R, γ) s γ ∈ [0, 1) a počáteční deterministická strategie π₀ : S → A;
výstup: optimální deterministická strategie π a její hodnotová funkce V^π = V*.

Polož i = 0.
Vyhodnocení: spočítej V^π_i : S → ℝ jako (jediné) řešení soustavy |S| lineárních rovnic V(s) = ∑_{s′ ∈ S} P(s′ | s, π_i(s)) [R(s, π_i(s), s′) + γ V(s′)], s ∈ S.
Zlepšení: pro každé s ∈ S zvol π_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′)]; je-li π_i(s) mezi maximy, ponech π_i+1(s) = π_i(s).
Je-li π_i+1 = π_i (tj. π_i+1(s) = π_i(s) pro všechna s ∈ S), zastav a vrať π = π_i; jinak zvyš i o 1 a vrať se ke kroku 2.

Že je vrácená strategie optimální a že algoritmus vždy skončí, říká věta o zlepšení strategie níže.

Laicky řečeno

Vezmu nějaký tahák, poctivě spočítám, jak dobře s ním dopadnu z každého políčka, a pak tahák opravím všude, kde by jiný tah vyšel líp. Opakuji. Tahák se zlepšuje každým kolem a po pár kolech se už nezmění.

# iterace strategie
π = „všude nahoru“
opakuj:
    # vyhodnocení: V^π řešením soustavy (u nás opakovaným dosazováním)
    V = 0
    opakuj, dokud se V mění o víc než 10⁻⁹:
        V(s) = ∑ přes s′ ( P(s′ | s, π(s)) · (R + γ · V(s′)) )   pro každé s
    # zlepšení: v každém stavu nejlepší akce podle V^π
    π_nová(s) = argmax přes a  ∑ přes s′ ( P(s′ | s, a) · (R + γ · V(s′)) )
    změněných = počet stavů, kde π_nová(s) ≠ π(s)
    π = π_nová
dokud změněných > 0

Věta — o zlepšení strategie

Nechť (S, A, P, R, γ) je MDP s γ ∈ [0, 1), π : S → A deterministická strategie a π′ : S → A deterministická strategie taková, že π′(s) ∈ argmax_{a ∈ A} Q^π(s, a) pro všechna s ∈ S. Pak

V^π′(s) ≥ V^π(s) pro všechna s ∈ S;
je-li Q^π(s, π(s)) = max_{a ∈ A} Q^π(s, a) pro všechna s ∈ S (zlepšení nemá co změnit, π′ = π), pak V^π splňuje Bellmanovu rovnici optimality, V^π = V* a π je optimální;
jinak existuje s ∈ S s V^π′(s) > V^π(s).

Náčrt důkazu. Z volby π′ je V^π(s) = Q^π(s, π(s)) ≤ Q^π(s, π′(s)) = E[r + γ V^π(s′)]. Do V^π(s′) dosadíme tutéž nerovnost, pak znovu… Po rozvinutí zbude očekávaný výnos strategie, která hraje π′ ve všech krocích, tedy V^π′(s). ∎

Deterministických strategií je konečně mnoho — u nás 4 akce v 19 nekoncových polích, tedy 4¹⁹ ≈ 2,7 · 10¹¹. Žádná se nemůže opakovat (každé kolo hodnotu zlepší, nebo skončí), takže iterace strategie skončí vždy. Ve skutečnosti stačí kol překvapivě málo: u nás 6.

Na kluzké podlaze s γ = 0,9, se strategií „všude nahoru“ na začátku:

kolo	V(start) strategie	kroků vyhodnocení	změněných akcí
1	0,03	66	7
2	0,11	137	7
3	0,16	141	8
4	0,49	151	3
5	2,85	42	1
6	2,85	77	0

Po 6 kolech je strategie stejná jako z hodnotové iterace. Kol je málo, ale každé obsahuje celé vyhodnocení (u nás desítky až stovky průchodů světem). Který z obou postupů je rychlejší, záleží na úloze; v praxi se kombinují.

7. Když pravidla světa neznáme

Všechno výše předpokládá, že známe P a R — umíme se „podívat do pravidel“. To je plánování (dynamické programování). Ve skutečném posilovaném učení je agent hozen do světa, jehož pravidla nezná: musí zkoušet, sbírat zkušenosti a odhadovat hodnoty z nich. Bellmanova rovnice ale zůstává srdcem téměř všech metod — jen se místo přesného průměru přes P použije vzorek z jednoho skutečného kroku. To je Q-learning, téma dalšího dílu.

Stejný rámec popisuje robota, který se učí chodit, řízení zásob ve skladu, doporučovací systém i jazykový model učený z lidských preferencí v dílu o RLHF — tam je stavem dosavadní text, akcí další token a odměnou hodnocení odpovědi.

8. Shrnutí

MDP = stavy, akce, náhodné přechody, odměny a diskont; další stav závisí jen na současném stavu a akci.
Hodnota stavu je očekávaný diskontovaný výnos; optimální hodnoty splňují Bellmanovu rovnici.
Hodnotová iterace opakuje Bellmanovu rovnici; chyba klesá aspoň jako γ^k (u nás 50 iterací pro γ = 0,9).
Klouzání přesune cestu dál od útesu (pád 0,7 % místo 30 %), malé γ vede k malému blízkému cíli, cena za krok k riskování.
Iterace strategie střídá vyhodnocení a zlepšení; u nás 6 kol.
Bez znalosti pravidel světa se hodnoty musí učit ze zkušenosti — to je posilované učení.

Chcete si to osahat? Nechte AI agenta naprogramovat tenhle svět s útesem a interaktivně měnit γ, klouzání a cenu kroku — a sledujte, kdy se strategie „překlopí“ z jedné cesty na jinou.

Máte na to jiný názor? Napište na support@coden-app.com.

Markovovy rozhodovací procesy: stavy, akce, odměny a Bellmanovy rovnice

1. Agent, prostředí, odměna

2. Výnos, diskont a strategie

3. Hodnota a Bellmanovy rovnice

4. Hodnotová iterace

5. Co změní diskont, klouzání a cena kroku

6. Iterace strategie

7. Když pravidla světa neznáme

8. Shrnutí

Agent na vašem počítači, ovládaný z telefonu