stochastic dynamic programming

stochastic dynamic programming (tsz. stochastic dynamic programmings)

1. (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. Állapotok (${\textstyle {\mathcal {S}}}$) 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.

2. Akciók (${\textstyle {\mathcal {A}}}$) 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.

3. Átmeneti valószínűségek (${\textstyle P}$)

   $${\displaystyle P(s'\mid s,a)}$$

   Azt adja meg, hogy ha a jelen állapot ${\textstyle s}$-ben az ${\textstyle a}$ akciót hajtjuk végre, a következő időpontban ${\textstyle 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.

4. Jutalom- vagy költségfüggvény (${\textstyle r}$)

   $${\displaystyle r(s,a,s')}$$

   A rendszer az ${\textstyle s}$ állapotból az ${\textstyle s'}$ állapotba lépve az ${\textstyle a}$ akció következtében kapott (vagy fizetett) jutalom/költség. Gyakran egyszerűsítünk és ${\textstyle r(s,a)}$ vagy akár ${\textstyle r(s)}$ formában dolgozunk.

5. Diszkontfaktor (${\textstyle \gamma }$) Egy ${\textstyle 0\leq \gamma <1}$ valós szám, amely a jövőbeni jutalmak jelenértékét adja. A teljes várható, diszkontált jutalom

   $${\displaystyle \mathbb {E} {\Bigl }}$$

   maximalizálása a cél.

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

$${\displaystyle V^{*}(s)\;=\;\max _{a\in {\mathcal {A}}(s)}\;\sum _{s'\in {\mathcal {S}}}P(s'\mid s,a)\,{\bigl }.}$$

Itt

• ${\textstyle V^{*}(s)}$ az optimális értékfüggvény: a maximális várható, diszkontált jutalom, ha az ${\textstyle 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 ${\textstyle 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 ${\textstyle V_{T-1},V_{T-2},\dots ,V_{0}}$ értékeket.

• Vége horizon (T időlépés) Ilyenkor a Bellman-egyenletet a terminális időpontban ${\textstyle t=T}$ kezdeti feltételekkel indítjuk (${\textstyle V_{T}(s)}$ ismert), majd visszafelé iterálva kapjuk ${\textstyle V_{0}}$-t, ahonnan a döntést meghozzuk.

• Végtelen horizon Ha ${\textstyle T\to \infty }$ és ${\textstyle \gamma <1}$, az értékiteráció konvergál egy fixpontra, ahol

  $${\displaystyle V_{k+1}(s)=\max _{a}\sum _{s'}P(s'\mid s,a){\bigl },}$$

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

1. É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 ${\textstyle V^{*}}$-et.

2. Politikaiteráció

   • Politikaértékelés: adott politika ${\textstyle \pi }$ mellett megoldjuk a lineáris egyenletrendszert

     $${\displaystyle V^{\pi }(s)=\sum _{s'}P(s'\!\mid s,\pi (s)){\bigl }.}$$

   • Politikaváltás: ${\textstyle \pi _{\text{new}}(s)=\arg \max _{a}\sum _{s'}P(s'\mid s,a)}$. 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).

3. Lineáris programozás Közvetlenül megoldhatjuk egy LP-formulációval:

   $${\displaystyle \min \sum _{s}\alpha (s)\,V(s)\quad {\text{s.t.}}\quad V(s)\geq r(s,a)+\gamma \sum _{s'}P(s'\mid s,a)\,V(s')\quad \forall s,a.}$$

   Itt ${\textstyle \alpha (s)}$ súlyozott kiinduló állapot-gyakoriság.

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

• Állapot: ${\textstyle s\in \{0,1,\dots ,S_{\max }\}}$.

• Akció: ${\textstyle a\in \{0,1,\dots ,A_{\max }\}}$.

• Átmenet:

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

  vagy 0, ha kifogy.

• Jutalom:

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

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

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

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

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

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.

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