stochastic dynamic programming

Angol

Főnév

stochastic dynamic programming (tsz. stochastic dynamic programmings)

(informatika) A sztochasztikus dinamikus programozás olyan matematikai-optimalizációs keretrendszer, amelyben a döntési folyamat több lépésben zajlik, a rendszer állapota pedig mind a múltbeli döntésektől, mind véletlen eseményektől függ. Ezzel ellentétben a determinisztikus dinamikus programozásnál a jövő pontosan előre jelezhető. A stochasztikus esetben viszont valószínűségi átmeneteket és várható értékeket alkalmazunk, így alkalmasunk olyan valós problémák modellezésére, ahol a bizonytalanság kulcsszerepet játszik (például készletszintek, portfóliókezelés, sorban álló rendszerek).

1. A stochasztikus dinamikus programozás alapjai

Állapotok ( $𝒮$ ) A rendszer lehetséges konfigurációinak halmaza. Egy inventory-problémánál ez lehet a raktárkészlet szintje, pénzügyi portfólió esetén pedig a vagyontételek értéke.
Akciók ( $𝒜$ ) Minden időpillanatban elérhető döntések, például mekkora mennyiséget rendelünk, vagy milyen arányban allokáljuk az eszközöket.
Átmeneti valószínűségek ( $P$ )

$P (s^{'} ∣ s, a)$

Azt adja meg, hogy ha a jelen állapot $s$ -ben az $a$ akciót hajtjuk végre, a következő időpontban $s^{'}$ állapotba kerülünk–e mekkora valószínűséggel. Mivel a rendszer stochasztikus, e valószínűségek jellemzik a bizonytalanságot.
Jutalom- vagy költségfüggvény ( $r$ )

$r (s, a, s^{'})$

A rendszer az $s$ állapotból az $s^{'}$ állapotba lépve az $a$ akció következtében kapott (vagy fizetett) jutalom/költség. Gyakran egyszerűsítünk és $r (s, a)$ vagy akár $r (s)$ formában dolgozunk.
Diszkontfaktor ( $γ$ ) Egy $0 \leq γ < 1$ valós szám, amely a jövőbeni jutalmak jelenértékét adja. A teljes várható, diszkontált jutalom

$𝔼 [\sum_{t = 0}^{\infty} γ^{t} r_{t}]$

maximalizálása a cél.

2. A Bellman-egyenlet és visszafelé kalkuláció

A stochasztikus dinamikus programozás központi eszköze a Bellman-egyenlet, amely rekurzívan összekapcsolja az egyes állapotok optimális értékét:

$V^{*} (s) = max_{a \in 𝒜 (s)} \sum_{s^{'} \in 𝒮} P (s^{'} ∣ s, a) [r (s, a, s^{'}) + γ V^{*} (s^{'})] .$

Itt

$V^{*} (s)$ az optimális értékfüggvény: a maximális várható, diszkontált jutalom, ha az $s$ állapotból indulunk és optimális döntéseket hozunk.
A maximálás azokon az akciókon fut, amelyek az adott állapotban engedélyezettek.

A dinamikus programozás során visszafelé („backward induction”) lépünk a lehetséges időpillanatokon: ha végponti feltételként megadtuk $V_{T} (s)$ értékeit (például terminális költség vagy jutalom a leállásnál), onnan lépünk vissza a korábbi állapotokra, és számítjuk ki sorban a $V_{T - 1}, V_{T - 2}, \dots, V_{0}$ értékeket.

3. Véges és végtelen horizon

Vége horizon (T időlépés) Ilyenkor a Bellman-egyenletet a terminális időpontban $t = T$ kezdeti feltételekkel indítjuk ( $V_{T} (s)$ ismert), majd visszafelé iterálva kapjuk $V_{0}$ -t, ahonnan a döntést meghozzuk.
Végtelen horizon Ha $T \to \infty$ és $γ < 1$ , az értékiteráció konvergál egy fixpontra, ahol

$V_{k + 1} (s) = max_{a} \sum_{s^{'}} P (s^{'} ∣ s, a) [r (s, a, s^{'}) + γ V_{k} (s^{'})],$

és $V_{k} \to V^{*}$ .

4. Számítási módszerek

Értékiteráció Egyszerű, de gyakran lassú: minden állapotra minden akciót és átmenetet végig kell számolni minden iterációban. Konvergencia: monotón növekvő (vagy csökkenő) sorozatként éri el az optimális $V^{*}$ -et.
Politikaiteráció
- Politikaértékelés: adott politika $π$ mellett megoldjuk a lineáris egyenletrendszert
  
  $V^{π} (s) = \sum_{s^{'}} P (s^{'} ∣ s, π (s)) [r (s, π (s), s^{'}) + γ V^{π} (s^{'})] .$
- Politikaváltás: $π_{new} (s) = \arg {max}_{a} \sum_{s^{'}} P (s^{'} ∣ s, a) [r + γ V^{π} (s^{'})]$ . A két lépést ismételjük, amíg a politika nem változik (jellemzően kevesebb iteráció szükséges, de egy-egy iteráció drágább).
Lineáris programozás Közvetlenül megoldhatjuk egy LP-formulációval:

$min \sum_{s} α (s) V (s) s.t. V (s) \geq r (s, a) + γ \sum_{s^{'}} P (s^{'} ∣ s, a) V (s^{'}) \forall s, a .$

Itt $α (s)$ súlyozott kiinduló állapot-gyakoriság.

5. Gyakorlat: készletgazdálkodás

Legyen $s_{t}$ a raktárkészlet szintje nap elején, $a_{t}$ a rendelési mennyiség. A kereslet $D_{t}$ stochasztikus, ismert eloszlással. A modell:

Állapot: $s \in {0, 1, \dots, S_{max}}$ .
Akció: $a \in {0, 1, \dots, A_{max}}$ .
Átmenet:

$s_{t + 1} = min {s_{t} + a_{t} - D_{t + 1}, S_{max}},$

vagy 0, ha kifogy.
Jutalom:

$r (s, a, s^{'}) = \underset{bevételek}{\underset{⏟}{p min (s + a, D)}} - \underset{beszerzés költsége}{\underset{⏟}{c a}} - \underset{tárolási költség}{\underset{⏟}{h max (0, s + a - D)}} - \underset{hiány költség}{\underset{⏟}{π max (0, D - s - a)}} .$

A visszafelé kalkulációval az egyes készlet- és rendelési döntésekhez tartozó optimális várható haszon kiszámítható.

6. Kihívások és „átok”

A stochasztikus dinamikus programozás fő nehézsége a dimenziókátka:

Állapottér nagysága gyorsan nő a változók számával.
Akciótér is hasonlóan növeli a komplexitást. Ez korlátozza a módszer közvetlen alkalmazhatóságát nagy rendszerekre.

Megoldási irányok

Approximate Dynamic Programming (ADP) – Funkcióillesztés (pl. lineáris/bázisfüggvényes, neurális hálózatokkal).
Monte Carlo Tree Search (MCTS) – Kérdezgetés-szimuláció (pl. Go-játék).
Reinforcement Learning – Q-learning, SARSA, Deep Q-Network (DQN) – modellmentes megközelítések.
Hierarchikus felbontás – A nagy feladatot több, kisebb DP-problémára bontjuk.

7. Alkalmazási példák

Energiagazdálkodás – Akkumulátor töltési–kisütési stratégia, ha a villamosenergia-ár stochasztikus.
Portfólióoptimalizálás – Részvény–kötvény allokáció időben változó piaci környezetben.
Robotikai mozgástervezés – Bizonytalan környezetben a legjobb irányítást keressük (POMDP kiterjesztés).
Epidemiamodellezés – Vakcina-elosztás dinamikus sztochasztikus fertőzésmodell mellett.

8. Összefoglalás

A stochasztikus dinamikus programozás gazdag elméleti hátteret és univerzális keretet nyújt olyan problémákhoz, ahol a döntések sorozata és a bizonytalanság kölcsönhatása kulcsfontosságú. A Bellman-egyenlet adják a módszer magját, és visszafelé kalkuláció vagy iteratív eljárások alkalmazhatóak a véges vagy végtelen horizonú esetekre. A dimenziókátka miatt azonban gyakran approximate és hierarchikus módszerekkel egészítjük ki, illetve a reinforcement learning modern eszköztárával oldjuk meg a nagy állapot- és akcióterű feladatokat. A keretrendszer sikerrel alkalmazható logisztikától a pénzügyön át a robotikáig, és ma is aktív kutatási terület a hatékonyabb közelítések és skálázható algoritmusok fejlesztése.

További információk

stochastic dynamic programming - Szótár.net (en-hu)
stochastic dynamic programming - Sztaki (en-hu)
stochastic dynamic programming - Merriam–Webster
stochastic dynamic programming - Cambridge
stochastic dynamic programming - WordNet
stochastic dynamic programming - Яндекс (en-ru)
stochastic dynamic programming - Google (en-hu)
stochastic dynamic programming - Wikidata
stochastic dynamic programming - Wikipédia (angol)