Online tanulás nemstacionárius Markov döntési folyamatokban
Neu Gergely
Számítástudományi és Információelméleti Tanszék Budapesti Muszaki ˝ és Gazdaságtudományi Egyetem
PhD értekezés tézisei
Témavezet˝o: Dr. Györfi László
Küls˝o témavezet˝ok: Dr. György András Dr. Szepesvári Csaba
Budapest 2013
1. Bevezetés A doktori értekezésben bemutatott munka a szekvenciális gépi tanulás elméletének két modelljét általánosítja. Ezek az online tanulás (online learning, [12, 10]) és a meger˝osítéses tanulás (reinforcement learning, [35, 8, 38, 34]) modelljei, melyek jellegzetességeit alább foglaljuk össze. Online tanulás: Az online tanulási probléma legegyszerubb ˝ változatában a döntéshozó minden t = 1, 2, . . . , T lépésben választ egy at ∈ A akciót, ahol A egy véges döntéshalmazt jelöl. Ezen döntés következtében a döntéshozó r t (at ) jutalomban részesül, valamint megismeri az egyéb akciókért járó r t (a) jutalmakat is. A tanulóalgoritmus feladata a jutalP mak Tt=1 r t (at ) összegének a maximalizálása. Bár a fenti probléma a klasszikus statisztika eszközeivel könnyen kezelhet˝o, amennyiben a jutalmak független, azonos eloszlású (independent and identically distributed, i.i.d.) valószínuségi ˝ változók, ez a feltevés a gyakorlatban nem mindig állja meg a helyét. Ezzel szemben az online tanulás területének eredményei kiterjednek id˝oben dinamikusan változó jutalomfüggvények esetére is: A kiindulási feltevés, hogy a jutalomfüggvények (r t )Tt=1 , r t : A → [0, 1] sorozatát egy küls˝o mechanizmus (a környezet) választja a döntéseinkt˝ol függetlenül. A jutalmakat generáló környezetr˝ol semmilyen statisztikai feltevést nem teszünk, így a jutalmak (r t )Tt=1 sorozatát el˝ore rögzített—de ismeretlen—sorozatként is kezelhetjük. A statisztikai feltevések elveP tése után természetesen le kell tennünk a Tt=1 r t (at ) összeg aszimptotikus maximalizálásáról, be kell érnünk egy kevésbé nagyratör˝o célkituzéssel. ˝ Az online tanulás algoritmusainak célja, hogy megközelít˝oleg annyi jutalmat gyujtsenek ˝ össze, mint amennyi a legjobb fix akció választásával elérhet˝o. A tanulási folyamat során „elveszített” jutalmak összegét regretnek (kb. „megbánás”) nevezzük, és formálisan a következ˝o képlettel definiáljuk:
LT = max
T X
a∈A t =1
r t (a) −
T X
r t (at ).
t =1
Fontos megjegyezni, hogy a fenti kifejezésben szerepl˝o maximum csak a teljes jutalomsorozat ismeretében, azaz csak a döntési folyamat utolsó lépése után számítható ki. Bár a regret minimalizálása intuitíven nagyon nehéz feladatnak tunik, ˝ mára jól ismertek optimális megoldások abban az esetben is, amikor a tanuló minden lépése után csak a saját r t (at ) jutalmáról értesül (a teljes r t jutalomfüggvény helyett). A probléma ezen változata bandita-probléma néven ismert. Az utóbbi években számos algoritmus született az online tanulási probléma különféle változatainak a megoldására, például speciálisan strukturált A döntéshalmazok vagy a döntéshozó részére hiányosan eljuttatott visszajelzések esetére. Az online tanulás modelljének azonban van egy komoly hiányossága: nem ad megnyugtató választ arra a kérdésre, hogy milyen garanciák adhatók olyan esetekben, amelyekben a környezet reagálhat a döntéshozó döntéseire—azaz a formalizmus nem engedi, hogy az r t jutalomfüggvény függjön a megel˝oz˝o a1 , . . . , at −1 sorozattól. A disszertációban bemutatott modell lehet˝oséget nyújt az ilyen esetek megfelel˝o kezelésére. 2
Meger˝ osítéses tanulás: A meger˝osítéses tanulás alapproblémájának minden t = 1, 2, . . . , T lépésében a döntéshozó (vagy ágens) megfigyeli a környezet xt állapotát, kiválaszt egy at akciót a véges A akciótérb˝ol, majd ennek következtében r (xt , at ) jutalomban részesül. Ezt követ˝oen a környezet következ˝o id˝opontbeli xt +1 állapota a P (·|xt , at ) eloszlás szerint módosul. Feltesszük, hogy az állapotok a véges X állapottér elemei, a r : X × A → [0, 1] jutalomfüggvény és a P : X × X × A → [0, 1] átmeneti függvény rögzített, ám ismeretlen függP vények. Az ágens célja a jutalmak Tt=1 r (xt , at ) összegének maximalizálása az (X, A, P, r ) négyes által leírt Markov döntési folyamatban (Markov decision process, MDP). A megoldásokat gyakran szokás a stacionárius politikák (röviden: politika, policy) körében keresni: egy π : X → A politika olyan viselkedést ír le, amely az x ∈ X állapotban a π(x) ∈ A akciót választja. Egy π politika értékét az általa T lépés alatt összegyujtött ˝ jutalmak összegének várható értéke adja meg: " # T X π 0 0 RT = E r (xt , π(xt )) , t =1
ahol x0t +1 ∼ P (·|x0t , π(x0t )). Az ágens várható összjutalmát a következ˝oképp jelöljük: "
T X
RbT = E
# r (xt , at ) ,
t =1
A fenti jelölések felhasználásával bevezethetjük a regret fogalmát: b T = max R π − RbT . L T π
A regret a tanulási folyamat során „elveszett” jutalmakat, azaz azt az árat adja meg, amit az ágens azért fizet, mert nem ismeri a jutalom- és átmeneti függvényeket a tanulási folyamat elején. Így ez a mennyiség jó mér˝oszáma a tanulóalgoritmusunk teljesítményének. Az MDP formalizmus f˝o korlátja, hogy nem képes modellezni az r és a P függvények esetleges id˝obeli változásait, azaz csak id˝oben változatlan struktúrájú döntési folyamatokat képes leírni. A disszertációban olyan modellt mutatunk be, amely képes ezen hiányosság kiküszöbölésére, valamint olyan algoritmusokat dolgozunk ki, melyek a meger˝osítéses tanulás irodalmában szokásos sztochasztikus feltevéseknél gyengébb feltételek mellett képesek garantáltan jól teljesíteni. Ebben a disszertációban olyan komplex meger˝osítéses tanulási feladatokat vizsgálunk, amelyekben nem feltétlenül teljesül, hogy az állapotok id˝obeli fejl˝odése leírható Markov-modellel. A bevezetett formalizmus a meger˝osítéses tanulás és az online tanulás fogalmain alapszik: a fent említett komplex feladatokat olyan Markov döntési feladatokként kezeljük, amelyekben a jutalomfüggvény az id˝o el˝orehaladtával változhat. Célunk olyan tanulóalgoritmusok konstruálása, amelyek jó teljesítménye elméletileg garantálható. Algoritmusaink teljesítményét az online tanulás irodalmából ismert ún. worst-case regret segítségével mérjük. A fent vázolt formalizmus
3
at
/01*2'
;<='
;<='
;<='
!"#$%&'()*"+,-.'
xt rt
;<='
314"#5'67*-8%*'
yt 9*-%*2#%::15' ()*"+,-.' ;<='
1. ábra. A döntéshozó és a környezet interakciója. A t -edik id˝opontban a t az ágens akciója, x t a markovi környezet állapota, y t az autonóm környezet állapota; q −1 az id˝obeli egylépéses eltolás operátora. számos olyan gyakorlati probléma modellezésére alkalmas, amelyben a környezet nehezen modellezhet˝o, komplex része csak a döntéshozó által kapott jutalmakat befolyásolja. Az összefoglaló hátralev˝o szakaszaiban bemutatjuk a modellünk különféle változatait és rámutatunk, ezek a változatok hogyan kapcsolódnak a fent vázolt tanulási paradigmákhoz. A 3. szakaszban megfogalmazzuk a disszertáció f˝o téziseit. A 4. szakaszban bemutatjuk az irodalomban fellelhet˝o legfontosabb egyéb kapcsolódó eredményeket. Végül az 5. szakaszban röviden bemutatunk néhány gyakorlati problémát, amelyekben a formalizmusunk alkalmazható.
2. A tanulási modell A döntéshozó és a környezet interakcióját az 1. ábra szemlélteti. A környezet két különálló részre bontható: egy markovi tulajdonságú és egy autonóm részre, amelyr˝ol semmilyen statisztikai feltételezést nem teszünk. Az ágens minden diszkrét t id˝opontban megfigyeli a markovi környezet xt állapotát, valamint a feladat jellegét˝ol függ˝oen információt kaphat az autonóm környezet el˝oz˝o y t −1 állapotáról. A döntéshozó ezen megfigyelések alapján dönt a következ˝o at akciójáról, amit elküld a környezetnek. A környezet ezután átlép a következ˝o állapotába: a markovi környezet xt +1 állapotát a P (·|xt , at ) eloszlás, az autonóm környezet y t +1 állapotát pedig egy tetsz˝oleges, ám az akcióktól és a markovi környezet állapotaitól független folyamat generálja. Az állapotátmenet után az ágens a környezet teljes állapotától és a saját választott akciójától függ˝o 4
nagyságú r (xt , y t , at ) jutalmat kap. Az ágens célja a kapott jutalmak összegének maximalizálása. Gyakorlati feladatok modellezésekor a környezet akciók által kauzálisan befolyásolt részét Markov-modellel közelítjük, a fennmaradó részb˝ol áll össze az autonóm dinamika, melyre nem alkotunk explicit modellt. Számos operációkutatási és irányításelméleti probléma rendelkezik a fent vázolt struktúrával. Példaként tekinthetünk olyan gyártási és er˝oforrás-allokációs problémákat, amelyekben a f˝o nehézséget az költségek modellezése jelenti, különféle számítástudományi problémákat (kszerver probléma, virtuálismemória-kezelési feladatok), valamint összetett weboptimalizálási problémákat (hirdetésallokáció késedelmes visszajelzéssel). Konkrét példákért ld. a 5. szakaszt. A továbbiakban a markovi környezet xt állapotára egyszeruen ˝ „az állapotként” hivatkozunk, a jutalmak y t -t˝ol való függését pedig a t id˝ot˝ol való függésként kezeljük, bevezetve az r t (·, ·) = r (·, y t , cd ot ) jelölést. A döntéshozó célja tehát az ¯ # " ¯ T X ¯ b RT = E r t (xt , at )¯ P , ¯ t =1 várható összjutalom maximalizálása, ahol az E [ ·| P ] jelöléssel hangsúlyoztuk, hogy az (xt )Tt=1 állapotsorozatot a P átmeneti függvény generálta. A π : X → A formában megadott kontrollereket stacionárius, determinisztikus politikáknak nevezzük, ahol X a Markov-modell állapottere és A az akciótér. Egy tetsz˝oleges π politika teljesítményét a ¯ " # ¯ T X π 0 0 ¯ RT = E r t (xt , π(xt ))¯ P, π , ¯ t =1 várható összjutalommal mérjük, ahol a (x0t )Tt=1 állapotsorozatot a π politika futtatása generálta a P átmeneti függvénnyel leírt MDP-ben. A tanulóalgoritmus célja, hogy közel annyi jutalmat gyujtsön ˝ össze, mint ha a legjobb (a teljes jutalomsorozat ismeretében) rögzített stacionárius politikát követte volna a tanulási folyamat elejét˝ol kezdve. Formálisan tehát a cél az alább definiált teljes várható regret minimalizálása: b T = max R π − RbT . L T π
(1)
Mivel feltesszük, hogy a döntéshozó képtelen az autonóm környezet viselkedésének modellezésére, olyan fels˝o korlátokat kell adnunk a regretre, amelyek minden (y t ) (illetve (r t )) sorozatra érvényesek. Ennek megfelel˝oen az alacsony regret garantálása robusztus irányítási garanciát jelent. Ezen megközelítés potenciális el˝onye, hogy a kapott eredmények általánosabban alkalmazhatók és algoritmusaink robusztusabbak lesznek, mint a tradicionálisabb, klasszikus statisztikán alapuló módszerek alkalmazása esetén. Megjegyezzük, hogy bár a robusztus irányítási garanciák gyakran túl konzervatívak a gyakorlati alkalmazhatósághoz, a felügyelt tanulás esetére vonatkozó eredmények alapján [11, 27, 36] az online tanulási technikák el tudják kerülni a túlzott pesszimizmus csapdáját az er˝os worst-case garanciák meg˝orzése mellett.
5
3. Új eredmények Az el˝oz˝oekben leírt problémát számos különféle, a Markov-modell struktúráját és a döntéshozónak juttatott visszajelzéseket illet˝o feltevés mellett vizsgáltuk. Az új eredményeink bemutatása el˝ott az alábbi listában informálisan ismertetjük a feltevéseinket. 1. Körmentes epizodikus környezeteknek nevezzük az olyan epizodikus markovi környezeteket, amelyekben az átmenetek csak „el˝ore” lehetségesek. Az epizodikus MDP-k olyan tanulási feladatok modellezésére alkalmasak, amelyben az ágensnek hasonló, de komplex, több állapotátmenetb˝ol álló feladatok sorozatát kell újra és újra megoldania. Az ágens minden epizódban a rögzített x 0 kezd˝oállapotból indul, az epizód végét az x L végállapot elérése jelenti. Feltesszük, hogy az X állapottér minden további állapota epizódonként legfeljebb egyszer elérhet˝o, azaz az átmeneti struktúra nem tartalmazhat köröket. Az r t : X × A → [0, 1] jutalomfüggvény a t = 1, 2, . . . , T epizódon belül változatlan, azonban epizódonként tetsz˝olegesen változhat. A döntéshozó a t -edik epizód minden l = 0, 1, . . . , L − 1 ) ) lépésében megfigyeli a markovi környezet x(t állapotát, és döntést hoz az a(t akcióról. A l l döntéshozó várható összjutalma T epizód után ¯ # " ¯ T L−1 X X ) (t ) ¯ r t (x(t RbT = E , a ) ¯P , l l ¯ t =1 l =0 a π politika összjutalma pedig ¯ # ¯ ¯ R Tπ = E r t (x0l , a0l )¯ P, π , ¯ t =1 l =0 "
T L−1 X X
ahol a E [ ·| P, π] jelöléssel hangsúlyoztuk, hogy az (x0l , a0l )L−1 trajektóriát a P átmeneti mol =0 dell és a π politika generálta. A legkisebb állapotlátogatási valószínuség ˝ ¯ £ ¤ α = min min P ∃l : x0l = x ¯ P, π . x∈X π∈AX
(a) Teljes visszajelzés ismert átmeneti függvénnyel: Feltesszük, hogy a P átmeneti függvény teljesen ismert az els˝o epizód kezdete el˝ott, és hogy a döntéshozó minden t epizód végén teljes egészében megismeri az r t jutalomfüggvényt. (b) Bandita-visszajelzés ismert átmeneti függvénnyel: Feltesszük, hogy a P átmeneti függvény teljesen ismert az els˝o epizód kezdete el˝ott, de a döntéshozó csak a saját trajektóriája mentén ismeri meg a jutalmakat. Más szóval az ágensnek adott visszajelzés a t -edik epizód után ³
´L−1 ) (t ) (t ) xl(t ) , a(t , r (x , a ) . t l l l l =0
(c) Teljes visszajelzés ismeretlen átmeneti függvénnyel: Feltesszük, hogy a P átmeneti függvény ismeretlen az els˝o epizód kezdete el˝ott, de a döntéshozó minden t epizód 6
végén teljes egészében megismeri az r t jutalomfüggvényt. Az állapottér rétegszerkezetér˝ol és az akciótérr˝ol szintén feltesszük, hogy ismertek. Az ágens tehát minden t epizód végén a megfigyeli a következ˝o visszajelzést: µ³ ´L−1 ¶ (t ) (t ) , rt . xl , al l =0
2. Unichain környezetnek nevezzük az olyan folytatódó (nem-epizodikus) markovi környezeteket, amelyekben minden politika indukál egy stacionárius eloszlást. A döntéshozó minden t = 1, 2, . . . , T id˝opontban megfigyeli az xt állapotot és kiválasztja az at akciót, az r t : X × A → [0, 1] jutalomfüggvény minden lépés után korlátozás nélkül változhat. Tetsz˝oleges π : X → A politikához definiáljuk a P π átmeneti mátrixot, melynek elemei P π (x|y) = P (x|y, π(y))
(∀x, y ∈ X).
Feltesszük, hogy minden π politikához tartozik pontosan egy µπ eloszlás az állapottér felett, amelyre minden x ∈ X esetén teljesül, hogy µπ (x) =
X y∈X
µπ (y)P π (x|y).
A µπ eloszlást a π politikához tartozó stacionárius eloszlásnak nevezzük. A legkisebb stacionárius látogatási valószínuség ˝ α0 = min min µπ (x). x∈X π∈AX
Feltesszük, hogy minden π politikához tartozik egy véges τπ keverési id˝o, amely jellemzi a stacionárius eloszlás megközelítésének a sebességét, valamint hogy a döntéshozó ismer egy τ ≥ supπ τπ fels˝o korlátot a leglassabban kever˝o politika keverési idejére. A döntéshozó várható összjutalma T lépés után ¯ # " ¯ T X ¯ RbT = E r t (xt , at )¯ P , ¯ t =1 a π politika összjutalma pedig R Tπ
" =E
T X t =1
¯ ¯
¯ r t (x0t , a0t )¯ P, π ¯
# ,
ahol az (x0t , a0t ) trajektóriát a P átmeneti modell és a π politika generálta. (a) Teljes visszajelzés ismert átmeneti függvénnyel: Feltesszük, hogy a P átmeneti függvény teljesen ismert az els˝o lépés el˝ott, és hogy a döntéshozó minden t lépés után teljes egészében megismeri az r t jutalomfüggvényt.
7
(b) Bandita-visszajelzés ismert átmeneti függvénnyel: Feltesszük, hogy a P átmeneti függvény teljesen ismert az els˝o lépés el˝ott, de a döntéshozó csak a saját állapotakció párjában ismeri meg a jutalmat. Más szóval, a döntéshozónak adott visszajelzés a t -edik lépés után (r t (xt , at ), xt +1 ) . 3. Online tanulás váltási költségekkel: Ez a probléma az általános online tanulási probléma egy speciális változata, amelyben a döntéshozó csak valamilyen K > 0 költség ellenében változtathat akciót lépések között. Ezt a problémát tekinthetjük az általános modellünk speciális esetének is, mivel könnyen felépíthetünk egy online MDP-t, amellyel modellezhet˝o az összes olyan online tanulási probléma, amelyben drága az akciók közötti váltás. Az (X, A, P, (r t )Tt=1 ) online MDP a következ˝oképp specifikálható: A környezet xt +1 állapota megegyezik a döntéshozó el˝oz˝o at akciójával. Másképpen, X = A és a P átmeneti függvényre teljesül, hogy minden x, y, z ∈ A hármasra P (y|x, y) = 1, valamint P (z|x, y) = 0 amennyiben z 6= y. A r t : X × A → [0, 1] jutalomfüggvényt az eredeti g t : A → [0, 1] jutalomfüggvény és a K váltási költség segítségével a r t (x, a) = g t (a) − K I{a6=x} képlettel definiáljuk az összes (x, a) ∈ A2 párra. A probléma két változatát vizsgáljuk. (a) Online predikció szakért˝ okkel: Feltesszük, hogy az A akciótér aránylag kicsi és a környezet szabadon rendelhet jutalmakat mindegyik akcióhoz. Ilyen esetekben az akciókra gyakran hivatkozunk „szakért˝okként” (experts). (b) Online kombinatorikus optimalizálás: Feltesszük, hogy minden akció reprezentálható egy d -dimenziós bináris vektorral, és a környezet a fenti d komponenshez rendelhet jutalmakat. Formálisan, a döntéshozó akciótere A ⊆ {0, 1}d , a környezet pedig minden t id˝opontban kiválasztja a jutalmak g t ∈ Rd vektorát. Az a ∈ A akcióért járó jutalmat a g t (a) = a > g t bels˝o szorzat adja meg. 4. Az online veszteséges forráskódolás problémája a 3. pontban vázolt problémaosztály egy példánya, amelyben a döntéshozó feladata a z 1 , z 2 , . . . , z T forrásszimbólumok sorozatának kódolt továbbítása egy zajmentes csatornán, majd a továbbítottak alapján a zˆ1 , zˆ2 , . . . , zˆT reprodukciós szimbólumok sorozatának el˝oállítása. A (z)Tt=1 forrásszimbólumokhoz (y)Tt=1 ˆ Tt=1 recsatornaszimbólumokat rendel˝o f kódoló és a (y)Tt=1 csatornaszimbólumokhoz (z) konstrukciós szimbólumokat rendel˝o g dekódoló rendezett ( f , g ) párját kódolási sémának nevezzük. Feltesszük, hogy a döntéshozónak rendelkezésére áll kódolási sémák egy rögzített F halmaza. A döntéshozó célja, hogy minden t = 1, 2, . . . , T id˝opontban úgy válassza meg a (ft , gt ) ∈ F kódolási sémáját, hogy az eredményként el˝oálló (ˆz)Tt=1 sorozat és a forrássorozat közötti kumulált torzítás a lehet˝o legkisebb legyen: bT = D
T X
d t (z t , zˆt ) → min,
t =1
8
ahol d egy adott torzítási metrika. A forrásszimbólumok sorozatáról semmilyen statisztikai feltevést nem teszünk. Egy fix ( f , g ) ∈ F kódolási séma össztorzítását D T ( f , g )-vel jelölve, a tanulóalgoritmus célja felírható a µ ¶ 1 £ ¤ b RT = E D T − min D T ( f , g ) , ( f ,g )∈F T várható normalizált torzítás-redundancia minimalizálásaként, amely egyenértéku ˝ a teljes várható regret minimalizálásával egy olyan online tanulási problémában, amelyben a jutalmakat a negatív torzítások adják. A szokásos tanulási problémán felül a dinamikus kódolási sémánknak biztosítania kell, hogy a vev˝o a megfelel˝o gt dekódert alkalmazza a t edik csatornaszimbólum dekódolására. Feltesszük, hogy a gt dekóder identitásának közlése kizárólag a kódolt forrásszimbólumok továbbítására használt csatornán lehetséges. Ezen körülmény miatt költségessé válik a kódolási sémák közötti váltás, így a redundancia minimalizálásához a 3. pontban leírt problémát kell megoldanunk. A disszertációban bemutatott, az egyes fent vázolt problémákra vonatkozó új eredményeket az alábbiakban foglaljuk össze.
1. Tézis. Hatékony algoritmusokat dolgoztam ki az online tanulási probléma megoldására ismert körmentes epizodikus környezetek esetén. Teljesítménygaranciákat bizonyítottam az 1a. és 1b. pontokban leírt tanulási problémákra. A bebizonyított korlátok függése az epizódok számától optimális. [C2, S1]
A körmentes epizodikus környezetekhez kidolgozott algoritmusaink azon a megfigyelésen alapulnak, hogy a regret minimalizálásának globális feladata felbontható több egyszeru ˝ párhuzamos döntési feladatra. A döntéshozó feladata így a regret minimalizálása ezekben a részfeladatokban a (πt )Tt=1 politikasorozat megválasztásával. A dekompozícióhoz a qt akcióértékel˝o- és a vt értékel˝ofüggvények bevezetésével juthatunk el, mely függvények az ún. Bellman–egyenletek (ld. pl. Puterman [35]) egyedi megoldásaként állnak el˝o: X qt (x, a) = r t (x, a) + P (x 0 |x, a)vt (x 0 ), (x, a) ∈ X × A, x0
vt (x) =
X
πt (a|x)qt (x, a),
a
x ∈ X \ {x L },
(2)
valamint vt (x L ) = 0. A fenti jelöléssel megmutatható, hogy a teljes várható regret könnyen kor£ ¤ P látozható, amennyiben minden x ∈ X esetén képesek vagyunk a Tt=1 E qt (x, π∗T (x)) − vt (x) összegek korlátozására. A fenti összeg adott x esetén megfelel egy olyan online tanulási probléma regretjének, amelyben a jutalmak sorozata (qt (x, ·))Tt=1 . Célunk tehát az így el˝oálló döntési feladatok megoldása minden állapotban. Erre a megfigyelésre építve számos online tanulási algoritmust dolgoztunk ki, amelyek mind különféle (állapotfogalom nélküli) online tanulási algoritmus állapotonkénti futtatásán alapulnak. Legfontosabb eredményünk a 1b. pontban vázolt 9
problémára vonatkozik, amelyben az ágens csak a saját megkapott jutalmait képes megfigyelni (szemben a teljes információs esettel, ahol képes megfigyelni a teljes jutalomfüggvényt). A fenti esetre konstruált algoritmusunk minden t = 1, 2, . . . , T − 1 epizód után kiszámítja a qt függvény egy torzítatlan qˆ t becslését, majd a politikáját ¢ ¡ P exp η ts=1 qˆ s (x, a) γ ¢+ ¡ Pt πt +1 (a|x) = (1 − γ) P (3) 0 0 | A| ˆ s (x , a ) x 0 ,a 0 exp η s=1 q alakban választja minden (x, a) állapot-akció párban, ahol η > 0 és γ ∈ (0, 1) az algoritmus választható paraméterei. A következ˝o tétel garanciát ad az algoritmus teljesítményére. 1.1. Tétel ([C2, S1]). Optimális paraméterbeállítások mellett az algoritmusunk teljes várható regretje a következ˝oképp korlátozható: s b T ≤ (L(L + 1)) L
T |A| ln |A|(e − 1) . α
2. Tézis. Hatékony algoritmust dolgoztam ki az online tanulási probléma megoldására ismert unichain környezet esetén. Teljesítménygaranciákat bizonyítottam a 2a. és2b. pontokban leírt tanulási problémákra. A bebizonyított korlátok függése a lépések számától (logaritmikus tényez˝okt˝ol eltekintve) optimális. [C3, J2]
Az általános tanulási probléma ezen változatát illet˝o eredményeink Even-Dar et al. [16] munkájára támaszkodnak: o˝ k adtak meg els˝oként az el˝oz˝o tézisben prezentálthoz hasonló dekompozíciót unichain környezet esetére. Ezen dekompozícióra alapozva kidolgoztak egy algoritmust teljes visszajelzést feltételezve (ld. 2a. pont). A π politika r t jutalomfüggvényre vonatkozó staciP onárius átlagjutalmát a ρ πt = x,a µπ (x)π(a|x)r t (x, a) képlettel definiálva a regret felbontható a következ˝oképpen: Ã ! Ã " #! " # T T T T X X X X π∗T π∗T π∗T π π t t bT = R − L ρ + ρ −E ρ +E ρ − RbT , (4) T
t =1
t
t =1
t
t =1
t
t =1
t
ahol (πt )Tt=1 a tanulóalgoritmus által választott politikák sorozata. A fenti összeg els˝o tagja egy konstanssal korlátozható, a harmadik tag pedig egyszeruen ˝ kezelhet˝o, amennyiben biztosítani tudjuk, hogy a választott politikák lassan változnak az id˝oben, azaz hogy kπt (·|x) − πt +1 (·|x)k1 = p O(1/ T ). A középs˝o tag korlátozásához a (2) egyenlettel analóg módon definiálhatjuk az akcióértékel˝o- és az értékel˝ofüggvényeket. Az el˝oz˝o tézishez hasonlóan bevezetve minden x állapotra a (qt (x, ·))Tt=1 jutalomsorozattal rendelkez˝o online tanulási részfeladatokat, a középs˝o tag a részproblémák regretjeinek korlátozásával kezelhet˝o. A disszertációban kiterjesztjük Even-Dar et al. [16] eredményeit bandita-visszajelzések esetére, valamint kijavítjuk a bizonyításaik apróbb hibáit. Az el˝oz˝o tézisben leírtakhoz hasonlóan 10
bevezetjük az akcióértékel˝o függvény qˆ t torzítatlan becsléseit, amelyek segítségével a (3) képlettel számoljuk a politikáinkat. Unichain környezet esetén azonban további er˝ofeszítéseket kell π tennünk annak érdekében, hogy a becsléseink jól reprezentálják a politikáink ρ t t átlagjutalmait. Ennek érdekében a t id˝opontban kiszámolt πt +1 politikát csak N > 1 lépésnyi késéssel kezdjük el használni, azaz a t id˝opontban a πt −N politikát követjük. Ezen trükk segítségével csökkenthet˝o a qˆ t becsléseink varianciája is, ami nagyon fontos a politikák lassú változásának biztosításához. Algoritmusunk teljesítményére a következ˝o garanciát bizonyítjuk be: 2.1. Tétel ([J2]). Optimális paraméterbeállítások mellett az algoritmusunk teljes várható regretje a következ˝oképp korlátozható: s b T = O τ3/2 T |A| ln T ln |A| . L α0 3. Tézis. Hatékony algoritmust dolgoztam ki az online tanulási probléma megoldására ismeretlen körmentes epizodikus környezetek esetén. Teljesítménygaranciákat bizonyítottam az 1c. pontban leírt tanulási problémára. A bebizonyított korlátok függése az epizódok számától optimális. [C5] Ismeretlen P átmeneti függvény esetén nem lehetséges torzítatlan becslést adni a qt függvényekre. Amennyibe feltesszük, hogy a döntéshozó a t -edik epizód után teljes egészében megfigyeli r t függvényt, nincs szükség ilyen becslésre és az egyedüli feladat a P függvény tanulása a regret minimalizálása közben. Ezen probléma megoldásához Jaksch et al. [24] nyomán olyan Pt konfidenciahalmazokat konstruálunk, amelyek nagy valószínuséggel ˝ tartalmazzák a valódi átmeneti függvényt. Kombinálva ezt az ötletet a Follow-the-Perturbed-Leader (FPL, [29]) predikciós algoritmussal, minden t id˝opontban minden (x, a) állapot-akció párhoz választunk egy-egy exponenciális eloszlású Zt (x, a) valószínuségi ˝ változót, majd együttesen kiválasztjuk az átmeneti függvényünket és a politikánkat a ¯ " # ´¯ L−1 X³ ¯ (πt , Pt ) = arg max E R t −1 (xl , al ) + Zt (xl , al ) ¯ P˜ , π ¯ l =0 π∈AX ,P˜ ∈P t
P −1 optimalizálási feladat megoldásával. A fenti képletben R t −1 = ts=1 r t a korábban megfigyelt L−1 jutalomfüggvények összege és a (xl , al )l =0 trajektóriát a π politika és a P˜ átmeneti függvény generálja. Más szóval, az átmeneti függvényünket optimista módon választjuk úgy, hogy a modellben maximális legyen az elérhet˝o perturbált összjutalom, majd ebben a modellben követjük az optimális politikát. Az algoritmus teljesítményére az alábbi garanciát bizonyítjuk: 3.1. Tétel ([C5]). Optimális paraméterbeállítások mellett az algoritmusunk teljes várható regretje a következ˝oképp korlátozható: ³ p ´ ˜ L|X ||A| T . bT = O L 11
4. Tézis. Hatékony algoritmust dolgoztam ki az online tanulási feladat megoldására akcióváltási költségek esetén. Teljesítménygaranciákat bizonyítottam a 3a. és 3b. pontokban leírt tanulási problémákra. A 3a. pont problémájára adott korlátok a probléma minden paraméterében optimálisak. A 3b. pont problémájára megadtuk az els˝o hatékony algoritmust. [S3, S4]
Erre a problémára javasolt algoritmusunk a Follow-the-Perturbed-Leader (FPL, ld. [22, 28, 29]) predikciós algoritmus módosított változata, amelyben a jutalmakat szimmetrikus véletlen sétákkal perturbáljuk. Az alábbiakban a 3b. pont alatt leírt problémaváltozatra (ahol A ⊆ {0, 1}d ) mutatjuk be az algoritmusunkat. Minden t = 1, 2, . . . , T id˝opontra és i = 1, 2, . . . , d komponensre Xi ,t ∼ N(0, η2 ) független normális eloszlású valószínuségi ˝ változókat választva definiáljuk a Zt = Pt opontbeli perturbációkat, ahol η > 0 az algoritmus szabadon választható paras=1 Xs a t id˝ P métere. Ezen felül legyen G t = s=1 g s a t id˝opontig megfigyelt jutalomvektorok összege. A döntéshozó minden t = 1, 2, . . . , T id˝opontban a perturbált összjutalmakat maximalizáló akciót választja: at = arg max a > (G t −1 + Zt ) . a∈A
A fentiekb˝ol világosan látszik, hogy az algoritmus hatékonyan implementálható amennyiben az A halmazon hatékonyan megoldható a statikus optimalizálás feladata. Feltéve, hogy minden a ∈ A akció vektoros reprezentációjában pontosan m darab 1-es szerepel, jól ismert technikákp kal megmutatható, hogy az algoritmus regretje O(m d T ln d ), megfelelve az FPL-re adott legjobb korlátoknak. Érdekesebb eredmény, hogy a d párhuzamos véletlen séta tulajdonságainak analizálásával (d -t˝ol csak logaritmikusan függ˝o módon) korlátozható az akcióváltások várható száma: 4.1. Tétel ([S3, S4]). Optimális paraméterbeállítások mellett az algoritmusunk akcióváltásainak várható száma a következ˝oképp korlátozható: " # ³ T p ´ X E I{at +1 6=at } = O m(ln d )5/2 T . t =1
5. Tézis. Hatékony algoritmust dolgoztam ki az online veszteséges forráskódolás problémájának megoldására. Teljesítménygaranciákat bizonyítottam a 4. pontban leírt tanulási problémára. A bebizonyított korlátok a függése a továbbított szimbólumok számától (logaritmikus tényez˝okt˝ol eltekintve) optimális. [C4, S2]
Algoritmusunk azon a megfigyelésen alapul, hogy az online veszteséges forráskódolás problémája olyan online tanulási problémaként fogható fel, melyben az akcióváltások költségesek.
12
Ezek a költségek természetes következményei annak, hogy a kódolási séma minden megváltozásakor értesíteni kell a vev˝ot az új dekódoló identitásáról. Az ilyen jellegu ˝ problémák hatékonyan kezelhet˝ok az el˝oz˝o tézisben bemutatott technikával, vagy a Shrinking Dartboard (SD, Geulen et al. [17]) algoritmus alkalmazásával. Ennek megfelel˝oen kidolgozunk és analizálunk egy algoritmust, mely az SD egy módosított változatának segítségével választja ki a használandó kódolási sémákat. Megmutatjuk, hogy ez az algoritmus egyszerre garantálja, hogy a teljes várható redundancia kicsi, miközben a dekóderek lecserélésének a száma szintén alacsony. Eredményeinket a következ˝o tétel foglalja össze: 5.1. Tétel ([C4, S2]). Optimális paraméterbeállítások mellett az algoritmusunk normalizált torzítás-redundanciája a következ˝oképp korlátozható: µ ¶ ln(T |F|) RT = O . p T
4. Kapcsolódó eredmények Mint korábban említettük, a munkánk szorosan kapcsolódik a meger˝osítéses tanulás területéhez. A terület legtöbb elméleti eredménye, a mi eredményeinkhez hasonlóan, véges állapotú MDP-kkel kapcsolatos. Bár létezik példa végtelen állapotú MDP-kkel kapcsolatos elméleti eredményre, ezek mind valamilyen egyéb er˝os feltevést tesznek az MDP szerkezetére (pl. [26, 37, 1]). Az MDP-kben való online tanulással kapcsolatos eredményeinket az 1. táblázat foglalja össze, az irodalomban fellelhet˝o legfontosabb egyéb eredményekkel együtt. Els˝oként Even-Dar et al. [15, 16] vizsgálta az online tanulási problémát nemstacionárius MDP-k esetén. Munkájukban feltették, hogy a Markov-modell unichain és a jutalomfüggvények teljesen megfigyelhet˝ok (ld. 2a. pont). MDP-E nevu ˝ algoritmusuk online tanulási algoritmusok p ˜ (τ2 T ). Mint korábban állapotonkénti futtatásán alapul, a regretjér˝ol bebizonyítják, hogy O már említettük, eredményeink egy részének bebizonyítására felhasználtuk a globális döntési probléma kisebb részfeladatokra bontására vonatkozó ötletüket. Yu et al. [43] ugyanerre a tanulási problémára dolgozott ki egy FPL-alapú algoritmust. Bár a módszerük számításigénye ˜ (T 3/4+² ). Ugyanezen cikkben jelent˝osen alacsonyabb, az elért regret távol van az optimálistól, O bemutattak bandita-visszajelzés esetére is egy algoritmust, melynek regretje o(T ). Yu és Mannor [41, 42] a problémánk azon változatát vizsgálják, amelyben az átmeneti valószínuségek ˝ is tetsz˝olegesen változhatnak a lépések között. Ez a változat jelent˝osen bonyolultabb az általunk vizsgált eseteknél, ennek megfelel˝oen nem tudtak szublineáris korlátot bizonyítani a regretre (azaz tanulóalgoritmusuk nem konzisztens). Jaksch et al. [24] azt az esetet vizsgálta, amelyben a tanulási folyamat elején a P átmeneti mátrix ismeretlen, a jutalmak pedig független, azonos eloszlású valószínuségi ˝ változók. Az átmeneti függvényre tett feltevéseik a unichain feltevésnél gyengébbek: felteszik, hogy létezik egy véges D > 0 konstans, amelyre teljesül, hogy bármely állapotból bármely más állapot elérhet˝o legfeljebb D lépésben (várható értékben). A Markov-láncok elméletében szokásos elnevezéssel
13
r t megfigyelve
r t (xt , at ) megfigyelve • 1. Tézis [C2, S1] – körmentes epizodikus környezet ³ p ´ b T = O L 2 T |A|/α – L
P ismert
• Even-Dar et al. [16] – unichain környezet ³ p ´ b T = O τ2 T log |A| – L
• 2. Tézis [C3, J2] – unichain környezet ³ ´ p b T = O τ3/2 T |A|/α0 – L
• Jaksch et al. [24]
P ismeretlen
– i.i.d. jutalmak – irreducibilis környezet ³ ´ p ˜ D|X| T |A| bT = O – L
Nyitott kérdés
• 3. Tézis [C5] – körmentes epizodikus környezet p ¢ ¡ b T = O L||X| | A| T – L
1. táblázat. Fels˝o korlátok a regretre a döntéshozónak eljuttatott visszajelzésekre tett különféle feltevések mellett. A saját eredményeket félkövér szedés jelzi. A jutalmakról statisztikai feltevést nem teszünk fel, amennyiben ezt külön nem jelezzük. az ilyen MDP-ket irreducibilisnek nevezzük D átmér˝ovel. Jaksch et al. [24] célja a (1) egyenlet szerinti regret minimalizálása, UCRL-2 nevu ˝ algoritmusuk garantálja, hogy ez a mennyiség p minden lehetséges D átmér˝oju ˝ MDP és jutalomeloszlás esetén legfeljebb O(D|X| |A|T ). Az 1. Tézisben bemutatott eredményeink tekinthet˝ok a determinisztikus online legrövidebb út problémákra vonatkozó eredmények sztochasztikus kiterjesztéseiként is. Ezen a területen György et al. [20] megközelítése áll legközelebb az alapelveinkhez és az algoritmusunkhoz: Auer et al. [3] bandita-algoritmusát implementálják dinamikus programozás segítségével az összes út felett, miközben az egyes élek jutalmait egyenként becslik. Bár ez a megközelítés vonzó lehet a mi problémánk esetén is, közvetlen alkalmazása problematikus: az MDP-struktúra véletlen átmenetei miatt Auer et al. [3] algoritmusa nem számítható ki a fent említett dinamikus programozási eljárással. A közelmúltban Arora et al. [2] adott algoritmust determinisztikus MDP-k esetére, változó jutalmakat és bandita-visszajelzést feltételezve. Ortner [33] eredményeire alapozva megállapítják, hogy az általuk vizsgált környezetben minden politika periodikus viselkedést indukál, így az op14
timális politika megtalálása ekvivalens az átmeneti gráf egy „optimális körének” megtalálásával. Bár az optimális kör egyértelmuen ˝ értelmezett stacionárius jutalmak esetén, Arora et al. megmutatja, hogy ez tetsz˝oleges jutalomsorozatok esetén nem teljesül, azaz a regret minimalizálása az optimális politikával szemben nem értelmezhet˝o cél. Jobb célkituzés ˝ tehát az olyan metapolitikákkal való versengés, amelyek képesek bármely stacionárius politikát bármely kezd˝oállapotból futtatni. Arora et al. algoritmusának regretje O(T 3/4 ) a fenti meta-politikák halmaza ellen. Mi vizsgáltuk els˝oként az online kombinatorikus optimalizálás problémáját váltási költségek mellett. Bár Geulen et al. [17] eredményei alkalmazhatók erre a problémára, algoritmusuk csak néhány speciális akciótér esetén alkalmazható hatékonyan (példákért ld. pl. [30, 13]). A mi megközelítésünk ezzel szemben minden olyan döntéshalmaz esetén hatékonyan implementálható, amelyhez létezik hatékony statikus optimalizálási eljárás. Ennek az alacsony számításigénynek azonban némileg gyengébb teljesítmény az ára: egyszeru ˝ számításokkal megmutatp ható, hogy Geulen et al. algoritmusa garantálja, hogy az akcióváltások száma O( mT ln d ). A tanuláselmélet egyik legérdekesebb nyitott kérdése, hogy a hasonló teljesítmény-számításigény dilemmák valóban szükségszeruek-e, ˝ vagy pedig a tanulási problémák jellegéb˝ol következ˝oen elkerülhetetlenek. Az online veszteséges forráskódolás problémáját tetsz˝oleges forrássorozatok esetére Linder és Lugosi [31] vizsgálta els˝oként, akik megmutatták, hogy létezik olyan randomizált kódolási séma, amelynek normalizált torzítása legfeljebb O(T −1/5 ln T )-vel nagyobb, mint a legjobb utólag kiválasztott skalárkvantálónak. Kódolási sémájukat Weissman és Merhav [40] fejlesztette tovább, akik azt az általánosabb esetet vizsgálták, amelyben F kódolási sémák egy véges referenciaosztálya. Bebizonyították, hogy algoritmusuk normalizált torzítás-redundanciája O(T −1/3 ln2/3 |F|). A skalárkvantálók végtelen referenciaosztályának esetére a teljesítménykorlátjuk O(T −1/3 ln T ). Bár Weissman és Merhav [40] eredményeit többen továbbfejlesztették, a mi munkánkat megel˝oz˝oen senkinek nem sikerült leszorítani a korlátok T -t˝ol való függését az optimális szintre.
5. Alkalmazások Ebben a szakaszban röviden leírunk néhány gyakorlati problémát, amelyek modellezhet˝ok a formalizmusunkkal. A bemutatott példák közös tulajdonsága, hogy a környezet állapottere egy X irányított állapottér és egy Y autonóm állapottér szorzataként írható le. A környezet irányított © ª állapota az X, A, P Markov-modellel írható le, míg az autonóm környezet állapotainak (y t )Tt=1 sorozatáról semmilyen statisztikai feltevést nem tudunk tenni. Feltehet˝o továbbá, hogy az irányított és az autonóm környezet nem léphet egymással közvetlen interakcióba, azaz a (xt )Tt=1 sztochasztikus átmeneteit nem befolyásolhatja a (y t )Tt=1 sorozat, és fordított irányú hatások sem léphetnek fel.
15
5.1. Leltárkezelés Tekintsünk egy leltárkezelési problémát, melyben a célunk a bevételek maximalizálása. Ebben az optimális irányítási feladatban az irányított rendszer állapota xt , az at akció a rendelt eszközök mennyiségének felel meg. Az eszközeink mennyiségét szintén befolyásolja a kereslet, amelyet sztochasztikusnak tekinthetünk. Ezen felül a bevételeinkre közvetlen hatással van az eszközök vételi és eladási ára. Feltesszük, hogy a döntések meghozatalakor ezek az árak nem ismertek pontosan. Mivel az árak számos, gyakran megfigyelhetetlen y t tényez˝ot˝ol függhetnek, id˝obeli változásuk nehezen modellezhet˝o. Feltehet˝o továbbá, hogy a beszerzéseink hatása az árak jöv˝obeli alakulására elhanyagolható. Mivel az y t tényez˝ok nem megfigyelhet˝ok, a probléma a 1b. és 2b. pontokban leírt modellel kezelhet˝o.
5.2. Hibrid gépjármu ˝ motorjának irányítása A hibrid hajtások fogyasztásának optimalizálásához fontos, hogy a hajtást vezérl˝o logika a megfelel˝o id˝opontokban váltson a bels˝o égésu ˝ és a villamos hajtás között (ld. pl. Balluchi et al. [5]). A megfelel˝o hajtás kiválasztását a vezet˝o szándékaitól az útviszonyokig számos tényez˝o befolyásolja: például lejtmenetben tölthet˝ok a villamos hajtás akkumulátorai, normál útviszonyok között a bels˝o égésu ˝ motor segítségével hatékonyabban érhet˝ok el nagyobb sebességek. Feltesszük, hogy a motor részleges xt állapota megfigyelhet˝o, és diszkrét id˝opontokban dönthetünk a hajtások közötti váltásról. A váltás sztochasztikus dinamikai modelljét ismertnek tesszük fel. A hibrid hajtás állapotának más y t részeit nem feltétlenül tudjuk megfigyelni. Feltesszük, hogy a fent említett és egyéb küls˝o hatások csak erre az állapotváltozóra vannak hatással, és az xt állapotot nem befolyásolják. Ennek megfelel˝oen y t -t egy autonóm folyamat állapotának tekintjük, amely befolyásolja a hatékony üzemelésért járó jutalmakat. Mivel y t nem teljesen megfigyelhet˝o, a problémát a 1b. és2b. pontokban leírt modellekkel kezelhetjük.
5.3. Energiatárolás széler˝ om˝ uvekhez A magyar villamosenergia-rendszer átvételi mechanizmusának szabályozása a széler˝omuvek ˝ számára is el˝oírja, hogy termelési menetrendet adjanak le 15 perces id˝obontásban, egy hónapra el˝ore. Amennyiben a termelés eltér az el˝ore jelzett˝ol, a termel˝onek az eltérést˝ol függ˝o mértéku ˝ szabályozási pótdíjat kell fizetnie. Amint Hartmann és Dán [23] kifejti, a menetrend betartásának egy lehetséges módja az el˝ore jelzett energiamennyiség feletti energia eltárolása, valamint a tárolt energia rendszerbe táplálása alacsony szélteljesítmény esetén. Ebben a feladatban feltesszük, hogy a tároló xt állapota leírható egy (esetleg ismeretlen) Markov-modellel, valamint hogy a y t szélsebesség id˝obeli fejl˝odése nem modellezhet˝o sztochasztikus módszerekkel. Mivel a menetrendek jóval a döntési id˝opontok el˝ott elérhet˝oek, a hatásukat kezelhetjük a Markovmodell részeként. Ilyen módon az autonóm környezet állapota kizárólag a jutalmakat (negatív pótdíjakat) befolyásolja, tehát a probléma modellezhet˝o nemstacionárius Markov döntési folyamatként. Mivel y t megfigyelhet˝o, a probléma kezelhet˝o a 1a., 2a. és 1c. pontokban leírt modellekkel. 16
5.4. Adaptív útvonaltervezés számítógéphálózatokban Tekintsük a szekvenciális routing problémáját egy számítógéphálózatban, ahol a cél T csomag eljuttatása az x 0 forráscsomópontból az x L célcsomópontba minimális késleltetéssel (ld. pl. György és Ottucsák [21]). Az egyes összeköttetéseken fellép˝o késleltetéseket különféle küls˝o események, például egyes csomópontok meghibásodásai befolyásolhatják. Az y t állapot ezen küls˝o ) csomópontban kiválaszthatjuk a hálóhatások leírására szolgál. Feltesszük, hogy minden x(t l (t ) ˝ randomizált algoritmus szerint továbbítja zati réteg egy al ∈ A interfészét, amely egy egyszeru (t ) a csomagot a xl +1 csomópontba. A fenti feltételek mellett a feladat felírható körmentes epizodikus problémaként, amely problémát a 1. pontban tárgyaltuk. Amennyiben a késleltetéseket csak az egyes csomagok által megtett út mentén tudjuk megfigyelni és az interfészek által alkalmazott algoritmus ismert, a probléma a 1b. pont szerint modellezhet˝o. Amennyiben az összes késleltetést megismerjük az egyes csomagok elküldése után, a 1c. pont esetére kidolgozott algoritmusaink akkor is garantálhatóan jól teljesítenek, ha a hálózati réteg sztochasztikus muködése ˝ ismeretlen.
5.5. Log-optimális portfólióstratégiák tranzakciós költségekkel Tekintsük a szekvenciális befektetési stratégiák konstruálásának problémáját, amelyben a befektet˝o minden diszkrét id˝opontban szétosztja a t˝okéjét d részvény között (ld. pl. Györfi és Walk [19]). Formálisan, a befektet˝o feladata a at ∈ [0, 1]d portfólióvektor kiválasztása minden t id˝oP pontban, biztosítva, hogy di=1 (at )i = 1. A at vektor i -edik komponense adja meg a befektet˝o Nt t˝okéjének az i részvénybe a t id˝opontban fektetett hányadát. A piac viselkedését a piacvektorok s 1 , s 2 , . . . , s T ∈ [0, ∞)d sorozata adja meg, ahol az s t vektor i -edik komponense adja meg az i -edik részvény árát a t id˝opontban. Hasznos az y t ∈ [0, ∞)d hozamvektorok definiálása, (s t )i melynek komponensei (y t )i = (s t −1 onek a t )i minden t > 1 esetén. Feltesszük, hogy a befektet˝ id˝opontban eladott, illetve vásárolt részvények után ct tranzakciós költséget kell fizetnie, mely költség függ az vásárolt/eladott részvények árától. A befektet˝o célja a NT t˝okéje maximalizálása, illetve másképpen a T1 log NT növekedési ráta (hozamszint) maximalizálása. A fenti maximalizálási feladat felírható online tanulási feladatként egy nemstacionárius Markov döntési folyamatban, amelyben az t id˝opontbeli állapotot az el˝oz˝o at −1 portfólióvektor határozza meg, az at akcióért járó jutalmat az xt = at −1 állapotban pedig a µ ¶ ¡ ¢ Nt − ct r (xt , y t , at ) = log + log a> t yt Nt képlet adja meg. Mivel a ct tranzakciós költség összefüggése a at −1 , at portfóliókkal és a Nt t˝okével jól ismert, és az y t hozamvektorok hatása a jutalmakra szintén közvetlenül számítható, feltehetjük, hogy a döntéshozó teljes visszajelzésben részesül. A portfóliók és árak diszkretizálása után közvetlenül alkalmazhatjuk a 2a. ponthoz kidolgozott algoritmusainkat. A probléma megközelíthet˝oen modellezhet˝o a 3a. pontban leírt modellel is, amennyiben feltesszük, hogy c t ≤ ¡ ¢ αNt teljesül valamilyen α ∈ (0, 1) esetére: A g t (a) = log a > y t jutalmakkal és a K = − log(1 − α)
17
váltási költséggel leírt online tanulási problémán futtatott tanulóalgoritmus regretjét kontrollálva nagyvonalú fels˝o korlátot kaphatunk a szekvenciális befektetési stratégia regretjére.
Publikációk [J1] Neu, G. and Szepesvári, Cs. (2009). Training parsers by inverse reinforcement learning. Machine Learning Journal, 77(2):303–337. [J2] Neu, G., György, A., Szepesvári, Cs., and Antos, A. (2013b). Online Markov decision processes under bandit feedback. Accepted for publication at the IEEE Transactions on Automatic Control. [C1] Neu, G. and Szepesvári, Cs. (2007). Apprenticeship learning using inverse reinforcement learning and gradient methods. In Conference on Uncertainty in Artificial Intelligence (UAI), pages 295–302. [C2] Neu, G., György, A., and Szepesvári, Cs. (2010a). The online loop-free stochastic shortestpath problem. In Proceedings of the Twenty-Third Conference on Computational Learning Theory, pages 231–243. [C3] Neu, G., György, A., Szepesvári, Cs., and Antos, A. (2010b). Online Markov decision processes under bandit feedback. In Advances in Neural Information Processing Systems 23. [C4] György, A. and Neu, G. (2011). Near-optimal rates for limited-delay universal lossy source coding. In Proceedings of the IEEE International Symposium on Information Theory (ISIT), pages 2344–2348. [C5] Neu, G., György, A., and Szepesvári, Cs. (2012). The adversarial stochastic shortest path problem with unknown transition probabilities. In Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics, volume 22 of JMLR Workshop and Conference Proceedings, pages 805–813, La Palma, Canary Islands. [S1] Neu, G., György, A., and Szepesvári, Cs. (2013a). The online loop-free stochastic shortestpath problem. In preparation. [S2] György, A. and Neu, G. (2013). Near-optimal rates for limited-delay universal lossy source coding. Submitted to the IEEE Transactions on Information Theory. [S3] Devroye, L., Lugosi, G., and Neu, G. (2013). Prediction by random-walk perturbation. Submitted to the Twenty-Sixth Conference on Learning Theory. [S4] Devroye, L., Lugosi, G., and Neu, G. (2013). Prediction by random-walk perturbation. Submitted to the IEEE Transactions on Information Theory.
18
Hivatkozások [1] Abbasi-Yadkori, Y. and Szepesvári, Cs. (2011). Regret bounds for the adaptive control of linear quadratic systems. In Proceedings of the Twenty-Fourth Conference on Computational Learning Theory. [2] Arora, R., Dekel, O., and Tewari, A. (2012). Deterministic MDPs with adversarial rewards and bandit feedback. CoRR, abs/1210.4843. [3] Auer, P., Cesa-Bianchi, N., Freund, Y., and Schapire, R. (1995). Gambling in a rigged casino: The adversarial multi-armed bandit problem. In Proceedings of the 36th Annual Symposium on the Foundations of Computer Science, pages 322–331. IEEE press. [4] Awerbuch, B. and Kleinberg, R. D. (2004). Adaptive routing with end-to-end feedback: distributed learning and geometric approaches. In Proceedings of the 36th ACM Symposium on Theory of Computing, pages 45–53. [5] Balluchi, A., Benvenuti, L., Di Benedetto, M. D., Pinello, C., and Sangiovanni-Vincentelli, A. L. (2000). Automotive engine control and hybrid systems: challenges and opportunities. In Proceedings of the IEEE, pages 888–912. [6] Bartlett, P. L., Dani, V., Hayes, T. P., Kakade, S., Rakhlin, A., and Tewari, A. (2008). Highprobability regret bounds for bandit online linear optimization. In Servedio, R. A. and Zhang, T., editors, 21st Annual Conference on Learning Theory (COLT 2008), pages 335– 342. Omnipress. [7] Bartlett, P. L. and Tewari, A. (2009). REGAL: A regularization based algorithm for reinforcement learning in weakly communicating MDPs. In Proceedings of the 25th Annual Conference on Uncertainty in Artificial Intelligence. [8] Bertsekas, D. P. and Tsitsiklis, J. N. (1996). Neuro-Dynamic Programming. Athena Scientific, Belmont, MA. [9] Brafman, R. I. and Tennenholtz, M. (2002). R-MAX - a general polynomial time algorithm for near-optimal reinforcement learning. Journal of Machine Learning Research, 3:213– 231. [10] Bubeck, S. and Cesa-Bianchi, N. (2012). Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems. Now Publishers Inc. [11] Cesa-Bianchi, N., Conconi, A., and Gentile, C. (2004). On the generalization ability of online learning algorithms. IEEE Transactions on Information Theory, 50:2050–2057. [12] Cesa-Bianchi, N. and Lugosi, G. (2006). Prediction, Learning, and Games. Cambridge University Press, New York, NY, USA. 19
[13] Cesa-Bianchi, N. and Lugosi, G. (2012). Combinatorial bandits. Journal of Computer and System Sciences, 78:1404–1422. [14] Dani, V., Hayes, T. P., and Kakade, S. (2008). The price of bandit information for online optimization. In Platt, J. C., Koller, D., Singer, Y., and Roweis, S. T., editors, Advances in Neural Information Processing Systems 20, pages 345–352. MIT Press. [15] Even-Dar, E., Kakade, S. M., and Mansour, Y. (2005). Experts in a Markov decision process. In Saul, L. K., Weiss, Y., and Bottou, L., editors, Advances in Neural Information Processing Systems 17, pages 401–408. [16] Even-Dar, E., Kakade, S. M., and Mansour, Y. (2009). Online Markov decision processes. Mathematics of Operations Research, 34(3):726–736. [17] Geulen, S., Voecking, B., and Winkler, M. (2010). Regret minimization for online buffering problems using the weighted majority algorithm. In Proceedings of the Twenty-Third Conference on Computational Learning Theory. [18] Györfi, L., Ottucsák, Gy., and Urbán, A. (2008). Empirical log-optimal portfolio selections: a survey. Machine Learning Summer School 2007, MLSS 2007 (invited lecture). [19] Györfi, L. and Walk, H. (2012). Empirical portfolio selection strategies with proportional transaction costs. IEEE Transactions on Information Theory, 58(10):6320–6331. [20] György, A., Linder, T., Lugosi, G., and Ottucsák, Gy. (2007). The on-line shortest path problem under partial monitoring. Journal of Machine Learning Research, 8:2369–2403. [21] György, A. and Ottucsák, Gy. (2006). Adaptive routing using expert advice. Computer Journal, 49(2):180–189. [22] Hannan, J. (1957). Approximation to Bayes risk in repeated play. Contributions to the theory of games, 3:97–139. [23] Hartmann, B. and Dán, A. (2012). Cooperation of a grid-connected wind farm and an energy storage unit demonstration of a simulation tool. IEEE Transactions on Sustainable Energy, 3(1):49–56. [24] Jaksch, T., Ortner, R., and Auer, P. (2010). Near-optimal regret bounds for reinforcement learning. J. Mach. Learn. Res., 99:1563–1600. [25] Kakade, S. (2003). On the sample complexity of reinforcement learning. PhD thesis, Gatsby Computational Neuroscience Unit, University College London. [26] Kakade, S., Kearns, M. J., and Langford, J. (2003). Exploration in metric state spaces. In ICML2003, pages 306–312.
20
[27] Kakade, S., Sridharan, K., and Tewari, A. (2009). On the complexity of linear prediction: Risk bounds, margin bounds, and regularization. In NIPS-22, pages 793–800. [28] Kalai, A. and Vempala, S. (2003). Efficient algorithms for the online decision problem. In Schölkopf, B. and Warmuth, M., editors, Proceedings of the 16th Annual Conference on Learning Theory and the 7th Kernel Workshop, COLT-Kernel 2003, pages 26–40, New York, USA. Springer. [29] Kalai, A. and Vempala, S. (2005). Efficient algorithms for online decision problems. J. Comput. Syst. Sci., 71:291–307. [30] Koolen, W., Warmuth, M., and Kivinen, J. (2010). Hedging structured concepts. In Proceedings of the 23rd Annual Conference on Learning Theory (COLT), pages 93–105. [31] Linder, T. and Lugosi, G. (2001). A zero-delay sequential scheme for lossy coding of individual sequences. IEEE Transactions on Information Theory, 47:2533–2538. [32] McMahan, H. B. and Blum, A. (2004). Online geometric optimization in the bandit setting against an adaptive adversary. In Proceedings of the Eighteenth Conference on Computational Learning Theory, pages 109–123. [33] Ortner, R. (2008). Online regret bounds for Markov decision processes with deterministic transitions. In Proceedings of the 19th International Conference on Algorithmic Learning Theory, ALT 2008. [34] Powell, W. B. (2007). Approximate Dynamic Programming: Solving the curses of dimensionality. John Wiley and Sons, New York. [35] Puterman, M. L. (1994). Markov Decision Processes: Discrete Stochastic Dynamic Programming. Wiley-Interscience. [36] Rakhlin, A., Sridharan, K., and Tewari, A. (2011). Online learning: Stochastic and constrained adversaries. In NIPS-24. [37] Strehl, A. L. and Littman, M. L. (2008). Online linear regression and its application to model-based reinforcement learning. In NIPS20, pages 1417–1424. [38] Sutton, R. and Barto, A. (1998). Reinforcement Learning: An Introduction. MIP Press. [39] Szepesvári, Cs. (2010). Algorithms for Reinforcement Learning. Synthesis Lectures on Artificial Intelligence and Machine Learning. Morgan & Claypool Publishers. [40] Weissman, T. and Merhav, N. (2002). On limited-delay lossy coding and filtering of individual sequences. IEEE Transactions on Information Theory, 48:721–733.
21
[41] Yu, J. Y. and Mannor, S. (2009a). Arbitrarily modulated Markov decision processes. In Joint 48th IEEE Conference on Decision and Control and 28th Chinese Control Conference, pages 2946–2953. IEEE Press. [42] Yu, J. Y. and Mannor, S. (2009b). Online learning in Markov decision processes with arbitrarily changing rewards and transitions. In GameNets’09: Proceedings of the First ICST international conference on Game Theory for Networks, pages 314–322, Piscataway, NJ, USA. IEEE Press. [43] Yu, J. Y., Mannor, S., and Shimkin, N. (2009). Markov decision processes with arbitrary reward processes. Mathematics of Operations Research, 34(3):737–757.
22
