Markov decision process

Markov decision process (tsz. Markov decision processes)

1. (informatika, mesterséges intelligencia) Markov-döntési folyamat

A Markov Decision Process (MDP) egy matematikai modell, amelyet az optimális döntéshozatal leírására használnak olyan rendszerekben, ahol a következő állapot a jelenlegi állapottól és a meghozott döntéstől (akciótól) függ, és ez a változás bizonytalan („statisztikus”). Az MDP-k alkalmazási területei közé tartozik a robotika, az automatikus vezérlés, a pénzügyi döntések, a játékelmélet és a mesterséges intelligencia egyaránt.

Egy MDP-t négyes számpárként szokás definiálni:

$${\displaystyle ({\mathcal {S}},{\mathcal {A}},P,R,\gamma ),}$$

ahol

1. Állapotok (${\textstyle {\mathcal {S}}}$) A rendszer lehetséges „helyzeteinek” halmaza. Például egy robot pozíciói egy rácson, vagy egy befektetési portfólió különböző állapotai.

2. Akciók (${\textstyle {\mathcal {A}}}$) Minden állapotban elérhető döntések („lépések”) halmaza. Ez lehet diszkrét (pl. „fel”, „le”, „balra”, „jobbra”) vagy folytonos (pl. kormánykerék elfordításának mértéke).

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

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

   Az a valószínűség, hogy az aktuális állapot ${\textstyle s\in {\mathcal {S}}}$ és az ott választott akció ${\textstyle a\in {\mathcal {A}}}$ hatására a következő időlépésben ${\textstyle s'\in {\mathcal {S}}}$ állapotba kerülünk.

4. Jutalmak (${\textstyle R}$)

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

   Az a valós érték, amit a döntéshozó az ${\textstyle s}$ állapotban ${\textstyle a}$ akció végrehajtása és ${\textstyle s'}$ állapotba jutás közben kap. Gyakran egyszerűsít az ${\textstyle R(s,a)}$ vagy akár ${\textstyle R(s)}$ formára, ha a jutalom csak a jelenlegi állapottól és/vagy akciótól függ.

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

   $${\displaystyle G_{t}=\sum _{k=0}^{\infty }\gamma ^{k}\,R_{t+k+1}.}$$

   Ha ${\textstyle \gamma }$ közelebb van 1-hez, a hosszú távú jutalmak is erősen számítanak; ha közelebb 0-hoz, a stratégia inkább rövidtávra fókuszál.

A politika egy leképezés, ami megadja, hogyan választunk akciót minden állapotban.

• Determinista politika: ${\textstyle \pi (s)=a}$.
• Vegyes (stochastic) politika: ${\textstyle \pi (a\mid s)=P(a\mid s)}$, azaz adott állapotban az akciókat valószínűségi eloszlás szerint választjuk.

Az optimális politika megtalálásához először definiáljuk az értékfüggvényeket:

1. State-value function

   $${\displaystyle V^{\pi }(s)=\mathbb {E} _{\pi }{\Bigl }.}$$

   Megadja az ${\textstyle s}$ állapotból indulva a politika követése esetén várt (diszkontált) összjutalmat.

2. Action-value function

   $${\displaystyle Q^{\pi }(s,a)=\mathbb {E} _{\pi }{\Bigl }.}$$

   Megadja, ha az ${\textstyle s}$ állapotban ${\textstyle a}$ akciót választunk, majd utána a politikát követjük, milyen várt jutalomra számíthatunk.

Az értékfüggvényekre teljesülnek a Bellman-rekurziók, amelyek az MDP optimális megoldásának alapját képezik:

1. Bellman-egyenlet politikára

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

2. Bellman-egyenlet optimális értékfüggvényre

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

   Ennek hasonló párja ${\textstyle Q^{*}(s,a)}$-ra:

   $${\displaystyle Q^{*}(s,a)=\sum _{s'}P(s'\!\mid s,a){\bigl }.}$$

Az optimális politika ${\textstyle \pi ^{*}}$ pedig:

$${\displaystyle \pi ^{*}(s)=\arg \max _{a}Q^{*}(s,a).}$$

• Lépés: minden állapotra ismételten alkalmazzuk a Bellman-optimális frissítést:

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

• Konvergencia: ${\textstyle V_{k}}$ konvergens ${\textstyle V^{*}}$-hez, ezután ${\textstyle \pi ^{*}(s)=\arg \max _{a}\!\sum _{s'}}$.

1. Politikaértékelés: egy aktuális ${\textstyle \pi }$ esetén oldjuk meg lineáris egyenletrendszerrel a Bellman-egyenleteket ${\textstyle V^{\pi }}$-re.
2. Politikaváltás: új, javított politikát építünk: ${\textstyle \pi _{\text{new}}(s)=\arg \max _{a}\sum _{s'}P(s'\!\mid s,a)}$.
3. Ismétlés, amíg a politika nem változik.

Ha nem ismerjük ${\textstyle P}$-t és ${\textstyle R}$-et explicit módon, élő interakció során tanulhatunk:

• Q‐learning:

  $${\displaystyle Q(s,a)\leftarrow Q(s,a)+\alpha {\bigl }.}$$

• SARSA (on‐policy tanulás):

  $${\displaystyle Q(s,a)\leftarrow Q(s,a)+\alpha {\bigl }.}$$

• Egy ${\textstyle 4\times 4}$ rácson a kezdőpont bal felső, a cél jobb alsó sarok.
• Akciók: fel, le, balra, jobbra.
• Kimeneti jutalom: minden lépés −1, cél elérésekor +10.
• Diszkontfaktor: ${\textstyle \gamma =0.9}$.

Érték‐ vagy politikaiterációval kiszámíthatjuk a cellánkénti ${\textstyle V^{*}}$ értékeket, majd ebből a legjobb útvonalat (policy) követve a legrövidebb, legkevesebb büntetőpontot eredményező útba jutunk a célhoz.

1. Robotika és vezérlés – Autonóm járművek útvonaltervezése, manipulátorok mozgásának optimalizálása.
2. Játékok és szimuláció – Sakk- és Go‐játszók, bármilyen szimulált környezetben való stratégiatanulás.
3. Pénzügyi döntések – Portfólió‐rebalance, opcióárazás, kockázatkezelés.
4. ellátási lánc – Készletszint‐kezelés, rendelési döntések dinamikus kereslet mellett.

Kiterjesztések

• Partially Observable MDP (POMDP): részlegesen megfigyelhető állapotok, belső meggyőződés (belief state) használatával.
• Hierarchikus MDP: több szintű feladatokra komponálható döntési folyamatok.
• Multi‐agent MDP (Markov Game): több döntéshozó, játék‐elméleti kiterjesztés.

A Markov Decision Process keretet ad a sorozatos döntések optimalizálásához bizonytalan környezetben. Megadja, hogyan lehet formálisan meghatározni az állapotokat, akciókat, átmeneti valószínűségeket és jutalmakat, majd Bellman-egyenletek és iteratív algoritmusok (érték‐, politikaiteráció) segítségével kiszámítani a legjobb stratégiát. Modell‐mentes módszerekkel, mint a Q‐learning, pedig akkor is tanulhatunk jó politikát, ha a környezet paraméterei ismeretlenek. Az MDP-k és azok kiterjesztései alapvető eszközei a mesterséges intelligencia, automatizálás és optimalizáció modern alkalmazásainak.

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