17.2. Értékiteráció

Ebben az alfejezetben az optimális eljárásmód kiszámítására mutatunk be egy algoritmust, az úgynevezett értékiterációt (value iteration). Az alapötlet az, hogy kiszámítjuk minden egyes állapot hasznosságát, majd az állapothasznosságokat felhasználjuk az egyes állapotoknál az optimális cselekvés megválasztásához.

17.2.1. Az állapotok hasznossága

Az állapotok hasznosságát az állapotsorozatok hasznosságán keresztül definiáljuk. Nagyjából azt modhatjuk, hogy egy állapot hasznossága a belőle kiinduló állapotsorozatok várható hasznosságával egyenlő. Nyilvánvalóan az állapotsorozatok függnek a végrehajtott eljárásmódtól, így elsőként egy adott π eljárásmódra definiáljuk a hasznosságot, Uπ(s)-t. Jelöljük st-vel az ágens állapotát a π eljárásmód t lépésnyi végrehajtása után, ekkor azt kapjuk, hogy

Felhasználva ezt a definíciót, egy állapot valódi hasznossága az Uπ (s), amit U(s)-sel jelölünk. Ez a a leszámítolt jutalmak várható értéke akkor, amikor az ágens egy optimális eljárásmódot hajt végre. Vegyük észre, hogy az U(s) és az R(s) igen eltérő mennyiségek: az R(s) a „rövid távú” jutalom az s-ben tartózkodásért, míg az U(s) a „hosszú távú” összjutalom s-től kezdve. A 17.3. ábrán láthatók a hasznosságok a 4 × 3-as világban. Látható, hogy a hasznosságok nagyobbak a +1-es kijárathoz közeli állapotoknál, mivel kevesebb lépés szükséges a kijárat eléréséhez.

Az U(s) hasznosságfüggvény lehetővé teszi az ágensnek, hogy a cselekvéseit a 16. fejezetben szereplő maximális várható hasznosság elve alapján válassza meg; azt a cselekvést választja, amelyik maximalizálja a bekövetkező állapot várható hasznosságát:

Fontos

Most azonban, ha egy állapot hasznossága a leszámítolt jutalmak várható értékének összege attól a kiindulóponttól kezdve, akkor közvetlen kapcsolat áll fenn egy állapot hasznossága és a szomszédainak a hasznossága között: egy állapot hasznossága az állapotban tartózkodás közvetlen jutalmának és a következő állapot várható leszámítolt hasznosságának az összege, feltéve, hogy az ágens az optimális cselekvést választja. Azaz egy állapot hasznossága a következő:

17.2. ábra - Az állapotok hasznosságai a 4 × 3-as világban, γ = 1 és a nem végállapotoknál R(s) = –0,04 esetén
Az állapotok hasznosságai a 4 × 3-as világban, γ = 1 és a nem végállapotoknál R(s) = –0,04 esetén

A (17.5) egyenletet Bellman-egyenletnek (Bellman equation) nevezik Richard Bellman tiszteletére (Bellman, 1957). Az állapotok hasznosságai – mint a bekövetkező állapotsorozatok várható hasznossága a (17.3) egyenlet szerint – a Bellman-egyenletek egy rendszerének a megoldásai. Valójában ezek egyértelmű megoldások, ahogyan a következő két alfejezetben megmutatjuk.

Nézzük meg a 4 × 3-as világ Bellman-egyenleteinek egyikét. Az (1, 1) állapothoz tartozó egyenlet:

U(1, 1) = –0,04 + γ max{0,8U(1, 2) + 0,1U(2, 1) + 0,1U(1, 1) (Fel)

0,9U(1, 1) + 0,1U(1, 2) (Balra)

0,9U(1, 1) + 0,1U(2,1) (Le)

0,8U(2, 1) + 0,1U(1, 2) + 0,1U(1, 1)} (Jobbra)

A 17.3. ábrán látható számok behelyettesítésével azt láthatjuk, hogy a Fel a legjobb cselekvés.

17.2.2. Az értékiteráció algoritmus

A Bellman-egyenletek képezik az alapját az MDF-ek megoldására szolgáló értékiteráció algoritmusnak. Ha n lehetséges állapot van, akkor n Bellman-egyenlet létezik, mindegyik állapotra egy. Az n egyenlet n ismeretlent tartalmaz – az állapotok hasznosságát. Így a hasznosságok megállapításához ezen egyenletek együttesét szeretnénk megoldani. Azonban van egy probléma: az egyenletek nemlineárisak, mivel a „max” operátor nemlineáris operátor. Míg a lineáris egyenletrendszerek hatékonyan megoldhatók lineáris algebrai eszközökkel, a nemlineáris egyenletrendszerek már problematikusabbak. Ekkor iteratív módszerrel próbálkozhatunk. Kezdéskor tetszőleges kezdeti értékeket választunk a hasznosságoknak, kiszámítjuk az egyenletek jobb oldalát, majd behelyettesítjük a bal oldalra – így frissítve az egyes állapotok hasznosságát a szomszédjainak a hasznosságával. Ezt addig ismételjük, ameddig el nem érünk egy egyensúlyi helyzetet. Jelölje Ui(s) az s állapot hasznosságértékét az i-edik iterációban. A Bellman-frissítésnek (Bellman update) nevezett iterációs lépés a következőképpen néz ki:

Ha a Bellman-frissítést végtelen sokszor alkalmazzuk, garantált, hogy egyensúlyi helyzetet érünk el (lásd következő alfejezet), és ekkor a végső hasznosságértékeknek a Bellman-egyenletek megoldását kell adniuk. Valójában ezek egyértelmű megoldások is, és a hozzájuk tartozó eljárásmód optimális (amit a (17.4) egyenlettel nyerhetünk). Az algoritmus, amit ÉRTÉKITERÁCIÓ-nak nevezünk, a 17.4. ábrán látható.

17.4. ábra - Az értékiteráció algoritmus az állapotok hasznosságának kiszámítására. A leállási feltétel a (17.8) egyenletből származik.
Az értékiteráció algoritmus az állapotok hasznosságának kiszámítására. A leállási feltétel a (17.8) egyenletből származik.

17.5. ábra - (a) A grafikonokon kiválasztott állapotok hasznosságainak a fejlődése látható az értékiteráció felhasználásánál. (b) A szükséges értékiterációk száma (k), hogy a hiba garantáltan legfeljebb ε = cRmax legyen, c különböző értékeinél, mint a γ leszámítolási tényező függvénye.
(a) A grafikonokon kiválasztott állapotok hasznosságainak a fejlődése látható az értékiteráció felhasználásánál. (b) A szükséges értékiterációk száma (k), hogy a hiba garantáltan legfeljebb ε = cRmax legyen, c különböző értékeinél, mint a γ leszámítolási tényező függvénye.

Az értékiterációt alkalmazhatjuk a 17.1. (a) ábra 4 × 3-as világára. Nulla kezdeti értékekről indulva, a hasznosságok alakulása a 17.5. (a) ábrán látható. Vegyük észre, ahogy a (4, 3) állapottól különböző távolságra lévő állapotok negatív jutalmakat halmoznak fel egészen addig, amíg egy bizonyos ponton utat találnak a (4, 3)-hoz, amikortól is a hasznosságok elkezdenek növekedni. Az értékiteráció algoritmusára gondolhatunk úgy, mint lokális frissítések általi információterjesztésre az állapottérben.

17.2.3. Az értékiteráció konvergenciája

Azt állítottuk, hogy az értékiteráció végül a Bellman-egyenletek egy egyértelmű megoldásához konvergál. Ebben az alfejezetben kifejtjük, miért is történik ez. Ennek során bevezetünk néhány hasznos matematikai fogalmat, és olyan módszereket kapunk, amelyek megbecsülik a hasznosságfüggvény hibáját , ha az algoritmust hamar állítottuk le; ennek hasznosságát az adja, hogy nem kell végtelen hosszan futtatnunk az algoritmust. Az alfejezet a technikai részleteket is bemutatja.

Az értékiteráció konvergenciájának megmutatásában használt alapfogalom az összehúzás (contraction). Az összehúzás nagyjából egy olyan egyváltozós függvény, ami két különböző bemeneti értékre alkalmazva, két olyan kimeneti értéket ad, amelyek „egymáshoz közelebbiek”, mint az eredeti értékek, legalább egy bizonyos állandó mennyiséggel. Például a „kettővel való osztás” egy összehúzás, mivel bármely két szám elosztása után a különbségük megfeleződik. Vegyük észre, hogy a „kettővel való osztásnak” van egy fix pontja, nevezetesen a nulla, ami a függvény alkalmazásával nem változik. Ebből a példából az összehúzás két fontos tulajdonságát vehetjük észre:

  • Egy összehúzásnak egyetlen fix pontja van: ha két fix pontja lenne, nem kerülnének egymáshoz közel a függvény alkalmazásakor, így nem is volna összehúzás.

  • A függvény tetszőleges argumentumra történő alkalmazásakor a függvényértéknek közelebb kell kerülniük a fix ponthoz (mivel a fix pont nem mozdul el), így egy öszszehúzás ismételt alkalmazása a fix pontot adja határértékben.

Most tegyük fel, hogy a Bellman-frissítést (a (17.6) egyenletet) egy B operátornak tekintjük, aminek egyszeri alkalmazása az összes állapot hasznosságát frissíti. Jelölje Ui az összes állapot i-edik iterációbeli hasznosságának a vektorát. Ekkor a Bellman-frissítési egyenletet felírhatjuk úgy, hogy

Ui+1BUi

Most egy olyan módszerre van szükségünk, amellyel a hasznosságvektorok távolságát mérhetjük. A maximum normát (max norm) fogjuk használni, ami egy vektor hoszszát a legnagyobb komponensének hosszával méri:

Fontos

Ezzel a definícióval, a két vektor közötti „távolság” ||UU′|| az összetartozó elemek közötti különbségek maximuma. Az alfejezet fő eredménye a következő: Legyen Ui és két tetszőleges hasznosságvektor. Ekkor

||BUi – BUi′|| ≤ γ||Ui – Ui′|| (17.7)

Azaz, a Bellman-frissítés egy összehúzás egy γ tényezővel a hasznosságvektorok terében. Így az értékiteráció mindig a Bellman-egyenletek egy egyértelmű megoldásához konvergál.

Nevezetesen, a (17.7) egyenletben lecserélhetjük Ui′ -t a valódi U hasznosságokkal, amire BU = U. Ekkor a következő egyenlőtlenséget kapjuk

||BUi – U|| ≤ γ||Ui – U||

Ezért, ha ||Ui – U||-ra mint az Ui becslés hibájára tekintünk, látjuk, hogy a hiba minden iterációban legalább egy γ tényezővel csökken. Ez azt jelenti, hogy az értékiteráció exponenciálisan gyorsan konvergál. A szükséges iterációk számát egy adott e hibahatár eléréséhez a következőképpen számíthatjuk ki: először, a (17.1) egyenlet szerint, az összes állapot hasznossága korlátos ±Rmax/(1 – γ) értékkel. Ez azt jelenti, hogy a maximális kezdeti hiba ||U0U|| ≤ 2Rmax/(1 – γ). Tegyük fel, hogy N iterációt végzünk ahhoz, hogy a hiba legfeljebb ε értékű legyen. Mivel a hiba minden egyes alkalommal legalább γ -szorosára csökken, annak kell teljesülnie, hogy γN 2 Rmax/(1 – γ) ≤ ε. Ha vesszük a két oldal logaritmusát, az adódik, hogy

számú iteráció elegendő. A 17.5. (b) ábrán látható, hogyan változik γ függvényében az N különböző értékű ε/Rmax hányadosok esetében. A jó hír az, hogy az exponenciális gyorsaságú konvergencia miatt N nem függ túlságosan az ε/Rmax hányadostól. A rossz hír az, hogy N gyorsan nő, ahogy γ közel kerül 1-hez. Így gyors konvergenciát úgy érhetünk el, ha γ -t kicsivé tesszük, de ez valójában az ágensnek rövid távú horizontot biztosít, és az ágens cselekvéseinek hosszú távú hatásait figyelmen kívül hagyhatja.

Az előző bekezdés hibakorlátja ad bizonyos tájékozódást az algoritmus futási idejét befolyásoló tényezőkről, de gyakran túlságosan óvatos módszert jelent annak eldöntésére, hogy mikor álljon le az iteráció. Az utóbbi célra felhasználhatunk egy korlátot, ami a hibát az egyes iterációkban a Bellman-frissítés nagyságához kapcsolja. Az összehúzási tulajdonságból ((17.7) egyenlet) meg lehet mutatni, hogy ha a frissítés kicsi (azaz egyetlen állapot hasznossága sem változik nagyon), akkor a hiba a valódi hasznosságfüggvényhez képest szintén kicsi. Pontosabban,

ha ||Ui+1Ui|| < ε(1 – γ)/ γ, akkor ||Ui+1U|| < ε (17.8)

Ez a leállási feltétel szerepel az ÉRTÉKITERÁCIÓ algoritmusában a 17.4. ábrán.

Fontos

Eddig az értékiteráció algoritmusa által visszaadott hasznosságfüggvény hibáját elemeztük. Az ágenst azonban igazán az érdekli, hogyan fog boldogulni, ha egy ilyen döntésfüggvény alapján hoz döntéseket. Tegyük fel, hogy az értékiteráció i-edik iterációja után az ágens a valódi U hasznosságra egy Ui becslést kap, és az Ui-n alapuló egylépéses előrenézés felhasználásával (ahogy a (17.4) egyenletben) megkapja a π i MVH-eljárásmódot. Vajon a kiadódó viselkedés megközelítőleg lesz-e olyan jó, mint az optimális viselkedés? Ez döntő kérdés minden valós ágens számára, és bizonyítható, hogy a válasz igen. Jelölje azt a hasznosságot, ami a π i végrehajtásakor adódik s-ből kiindulva. Ekkor az az eljárásmód vesztesége (policy loss) annak a maximális értéke, amit az ágens veszíthet π i-t végrehajtva az optimális π * eljárásmód helyett. A π i eljárásmód veszteségét az Ui-beli hibához a következő egyenlőtlenség kapcsolja:

A gyakorlatban sokszor előfordul, hogy π i jóval hamarabb optimálissá válik, mielőtt Ui konvergált volna. A 17.6. ábrán látható, ahogy a 4 × 3-as környezetben a maximális Ui-beli hiba és az eljárásmód vesztesége az értékiteráció folyamatának előrehaladtával nullához közelít, γ = 0,9 értéknél. A π i eljárásmód már i = 4-nél optimális, pedig az Ui-beli maximális hiba még 0,46.

17.6. ábra - A hasznosságbecslés maximális hibája ||UiU|| és az eljárásmód vesztesége A hasznosságbecslés maximális hibája ||Ui – U|| és az eljárásmód vesztesége az optimális eljárásmódhoz viszonyítva az értékiteráció iterációszámának függvényében az optimális eljárásmódhoz viszonyítva az értékiteráció iterációszámának függvényében
A hasznosságbecslés maximális hibája ||Ui – U|| és az eljárásmód vesztesége az optimális eljárásmódhoz viszonyítva az értékiteráció iterációszámának függvényében

Most már minden rendelkezésünkre áll, hogy az értékiterációt a gyakorlatban is felhasználjuk. Tudjuk, hogy a helyes hasznosságokhoz konvergál, a hasznosság becslésének hibájára korlátokat tudunk adni, ha véges számú iteráció után leállunk, és korlátokat tudunk adni az eljárásmód veszteségére, ami a becsült hasznosságértékekhez tartozó MVH-eljárásmód végrehajtása miatt lép fel. A végső megjegyzés, hogy az összes eredmény feltétele ebben az alfejezetben a γ < 1-gyel való leszámítolás. Ha γ = 1 és a környezet tartalmaz végállapotokat, akkor bizonyos technikai feltételek teljesülése esetén konvergenciaeredmények és hibakorlátok hasonló halmaza származtatható.