Gittiny index - Gittins index

The Gittiny index je měřítkem odměny, které lze dosáhnout daným stochastický proces s určitými vlastnostmi, jmenovitě: proces má konečný stav ukončení a vyvíjí se s možností ukončení v každém přechodném stavu. Po ukončení v daném stavu je dosažená odměna součtem pravděpodobnostních očekávaných odměn spojených s každým stavem od skutečného konečného stavu po konečný konečný stav včetně. Index je a nemovitý skalární.

Terminologie

Pro ilustraci teorie si můžeme vzít dva příklady z rozvíjejícího se sektoru, například z technologií na výrobu elektřiny: větrná energie a vlnová energie. Pokud se nám představí tyto dvě technologie, když jsou obě navrženy jako nápady, nemůžeme říci, která bude z dlouhodobého hlediska lepší, protože zatím nemáme žádná data, na nichž bychom mohli vycházet z našich úsudků.^[1] Dalo by se snadno říci, že vlnová síla by byla příliš problematická na to, aby se mohla vyvinout, protože se zdá být jednodušší postavit mnoho větrných turbín, než vyrobit dlouhé plovoucí generátory, vytáhnout je na moře a položit kabely.

Pokud bychom měli v té rané době vývoje zavolat úsudek, mohli bychom odsoudit jednu technologii k uvedení na polici a druhou by bylo možné vyvinout a uvést do provozu. Pokud vyvineme obě technologie, byli bychom schopni provést úsudek u každé z nich porovnáním pokroku každé technologie ve stanoveném časovém intervalu, například každé tři měsíce. Rozhodnutí o investici v další fázi by byla založena na těchto výsledcích.^[1]

V příspěvku z roku 1979 s názvem Banditské procesy a indexy dynamické alokace John C. Gittins navrhuje řešení problémů, jako je tento. Převezme dvě základní funkce „Plánování Problém “a problém„ Víceramenný bandita “^[2] a ukazuje, jak lze tyto problémy vyřešit pomocí Indexy dynamické alokace. Nejprve vezme „problém plánování“ a redukuje jej na stroj, který musí vykonávat úlohy a má stanovené časové období, například každou hodinu nebo den, aby dokončil každou úlohu. Stroj dostane hodnotu odměny na základě dokončení nebo ne v časovém období a pro každou úlohu se vypočítá hodnota pravděpodobnosti, zda bude dokončena nebo ne. Problém je v tom, „rozhodnout se, kterou práci zpracovat dále v každé fázi, aby se maximalizovala celková očekávaná odměna.“^[1] Poté přejde k „problému vícerukých banditů“, kde každý zatáhne za „jeden ozbrojený bandita "páce je přidělena funkce odměny za úspěšný tah a nulová odměna za neúspěšný tah. Posloupnost úspěchů tvoří a Bernoulliho proces a má neznámou pravděpodobnost úspěchu. Existuje několik „banditů“ a distribuce úspěšných tahů se počítá a liší se pro každý stroj. Gittins uvádí, že problém zde je „rozhodnout, kterou paži vytáhnout jako další v každé fázi, aby se maximalizovala celková očekávaná odměna z nekonečné posloupnosti tahů“.^[1]

Gittins říká, že „Oba výše popsané problémy zahrnují posloupnost rozhodnutí, každé z nich je založeno na více informací než jeho předchůdci, a tyto oba problémy lze řešit pomocí dynamických alokačních indexů.“^[2]

Definice

V aplikované matematice je „index Gittins“ a nemovitý skalární hodnota spojená se stavem a stochastický proces s funkcí odměny as pravděpodobností ukončení. Jde o míru odměny, které lze dosáhnout procesem vyvíjejícím se od tohoto stavu, s pravděpodobností, že bude v budoucnu ukončen. „Indexová politika“ vyvolaná indexem Gittins, spočívající v výběru kdykoli stochastického procesu s aktuálně nejvyšším indexem Gittins, je řešením některých zastavení problémů jako je dynamická alokace, kdy rozhodující osoba musí maximalizovat celkovou odměnu tím, že rozdělí omezené množství úsilí na řadu konkurenčních projektů, z nichž každý vrací stochastickou odměnu. Pokud jsou projekty na sobě nezávislé a může se vyvíjet pouze jeden projekt najednou, nazývá se problém mnohoruký bandita (jeden typ Stochastické plánování problémy) a politika indexu Gittins je optimální. Pokud se může vyvinout více projektů, problém se nazývá Neklidný bandita a politika indexu Gittins je známá dobrá heuristika, ale obecně neexistuje optimální řešení. Ve skutečnosti tento problém obecně je NP-kompletní a je všeobecně přijímáno, že nelze najít žádné proveditelné řešení.

Dějiny

Otázky ohledně optimálních politik zastavení v kontextu klinických studií byly otevřené od 40. let 20. století a v 60. letech několik autorů analyzovalo jednoduché modely vedoucí k optimálním indexovým politikám,^[3] ale to bylo až v 70. letech Gittiny a jeho spolupracovníci v markovianském rámci prokázali, že optimálním řešením obecného případu je indexová politika, jejíž „index dynamické alokace“ je v zásadě vypočítatelný pro každý stav každého projektu jako funkce dynamiky jediného projektu.^[2][4] Souběžně s Gittiny Martin Weitzman stanovil stejný výsledek v ekonomické literatuře.^[5]

Brzy po seminární práci Gittins, Peter Whittle^[6]prokázal, že index se jeví jako a Lagrangeův multiplikátor od a dynamické programování formulace problému zvaného proces odchodu do důchodu a předpokládal, že stejný index by byl dobrou heuristikou v obecnějším pojmenovaném nastavení Neklidný bandita. Otázka, jak vlastně vypočítat index pro Markovovy řetězy byl poprvé osloven Varaiyou a jeho spolupracovníky^[7] s algoritmem, který počítá indexy od největšího nejprve po nejmenší a podle Chen a Katehakis ^[8] kdo ukázal ten standard LP lze použít k výpočtu indexu stavu bez nutnosti jeho výpočtu pro všechny státy s vyššími hodnotami indexu. LCM Kallenberg ^[9] poskytl parametrickou implementaci LP k výpočtu indexů pro všechny stavy Markovova řetězce. Dále Katehakis a Veinott^[10] prokázal, že index je očekávanou odměnou a Markovův rozhodovací proces postavena na Markovově řetězci a známá jako Restartujte ve státě a lze jej přesně vypočítat řešením tohoto problému pomocí iterace politiky algoritmus, nebo přibližně s hodnotová iterace algoritmus. Výhodou tohoto přístupu je výpočet indexu pro jeden konkrétní stav, aniž by bylo nutné počítat všechny větší indexy, a je platný za obecnějších podmínek stavového prostoru. Rychlejší algoritmus pro výpočet všech indexů získal v roce 2004 Sonin^[11] v důsledku jeho eliminační algoritmus pro optimální zastavení řetězce Markov. V tomto algoritmu může pravděpodobnost ukončení procesu záviset spíše na aktuálním stavu než na pevném faktoru. Rychlejší algoritmus navrhl v roce 2007 Niño-Mora ^[12] využitím struktury parametrického simplexu ke snížení výpočetního úsilí pivotních kroků a dosažení stejné složitosti jako Gaussova eliminace algoritmus. Cowan, W. a Katehakis (2014),^[13] poskytnout řešení problému s potenciálně nemarkovskými, nespočetnými procesy odměňování stavového prostoru v rámci, ve kterém buď diskontní faktory mohou být nejednotné a mohou se časem měnit, nebo nemusí být období aktivace každého bandity pevná nebo uniformní, místo toho je možná stochastická doba aktivace, než je povolena změna na jiného banditu. Řešení je založeno na zobecněných indexech restartu ve stavu.

Matematická definice

Dynamický alokační index

Klasická definice Gittins et al. je:

${displaystyle u (i) = sup _ {au> 0} {frac {leftlangle sum _ {t = 0} ^ {au -1} eta ^ {t} R [Z (t)] ightangle _ {Z (0) = i}} {součet levého úhlu _ {t = 0} ^ {au -1} eta ^ {t} ightangle _ {Z (0) = i}}}}$

kde ${displaystyle Z (cdot)}$ je stochastický proces, ${displaystyle R (i)}$ je schopnost (také nazývaná odměna) spojená s diskrétním stavem ${displaystyle i}$,${displaystyle eta <1}$ je pravděpodobnost, že stochastický proces nekončí, a ${displaystyle langle cdot angle _ {c}}$ je uveden operátor podmíněného očekáváníC:

${displaystyle langle Xangle _ {c} doteq sum _ {xin chi} xP {X = x | c}}$

s ${displaystyle chi}$ být doména zX.

Formulace procesu odchodu do důchodu

Formulace dynamického programování z hlediska procesu odchodu do důchodu, kterou uvádí Whittle, je:

${displaystyle w (i) = inf {k: v (i, k) = k}}$

kde ${displaystyle v (i, k)}$ je funkce hodnoty

${displaystyle v (i, k) = sup _ {au> 0} součet levého úhlu _ {t = 0} ^ {au -1} eta ^ {t} R [Z (t)] + eta ^ {t} kightangle _ {Z (0) = i}}$

se stejným zápisem jako výše. To platí

${displaystyle u (i) = (1- eta) w (i).}$

Restartujte ve stavu formulace

Li ${displaystyle Z (cdot)}$ je markovský řetězec s odměnami, interpretace Katehakis a Veinott (1987) spojuje s každým stavem akci restartu z jednoho libovolného stavu ${displaystyle i}$, čímž se buduje Markovův rozhodovací proces ${displaystyle M_ {i}}$.

Gittinsův index tohoto státu ${displaystyle i}$ je nejvyšší celková odměna, jaké lze dosáhnout ${displaystyle M_ {i}}$ pokud se člověk vždy může rozhodnout pokračovat nebo restartovat z tohoto stavu ${displaystyle i}$.

${displaystyle h (i) = sup _ {pi} součet levého úhlu _ {t = 0} ^ {au -1} eta ^ {t} R [Z ^ {pi} (t)] ightangle _ {Z (0) = já}}$

kde ${displaystyle pi}$ označuje ukončení politiky ${displaystyle M_ {i}}$. To platí

${displaystyle h (i) = w (i)}$.

Zobecněný index

Pokud je pravděpodobnost přežití ${displaystyle eta (i)}$ záleží na stavu ${displaystyle i}$, zobecnění zavedené Soninem (2008) definuje index Gittins ${displaystyle alpha (i)}$ jako maximální diskontovaná celková odměna za šanci na ukončení.

${displaystyle alpha (i) = sup _ {au> 0} {frac {R ^ {au} (i)} {Q ^ {au} (i)}}}$

kde

${displaystyle R ^ {au} (i) = součet levého úhlu _ {t = 0} ^ {au -1} R [Z (t)] pravý úhel _ {Z (0) = i}}$

${displaystyle Q ^ {au} (i) = levý úhel 1-prod _ {t = 0} ^ {au -1} eta [Z (t)] ightangle _ {Z (0) = i}}$

Li ${displaystyle eta ^ {t}}$ je nahrazen ${displaystyle prod _ {j = 0} ^ {t-1} eta [Z (j)]}$ v definicích ${displaystyle u (i)}$, ${displaystyle w (i)}$ a ${displaystyle h (i)}$, pak to platí

${displaystyle alfa (i) = h (i) = w (i)}$

${displaystyle alpha (i) eq ku (i), forall k}$

toto pozorování vede Sonin k závěru, že ${displaystyle alpha (i)}$ a ne ${displaystyle u (i)}$ je „skutečný význam“ indexu Gittins.

Teorie řazení

V teorii front se index Gittins používá k určení optimálního rozvržení úloh, např. Ve frontě M / G / 1. Průměrnou dobu dokončení úloh podle plánu indexu Gittins lze určit pomocí přístupu SOAP.^[14] Všimněte si, že dynamika fronty je skutečně markovská a stochasticita je způsobena procesy příjezdu a služby. To je v rozporu s většinou prací ve výukové literatuře, kde je stochasticita výslovně vysvětlena jako pojem hluk.

Frakční problémy

Zatímco konvenční gittinové indexy indukují politiku pro optimalizaci narůstání odměny, společné nastavení problému spočívá v optimalizaci poměru narostlých odměn. Jedná se například o případy, kdy systémy maximalizují šířku pásma skládající se z dat v čase nebo minimalizují spotřebu energie skládající se z energie v čase.

Tato třída problémů se liší od optimalizace polomarkovského procesu odměňování, protože ten druhý by mohl vybírat státy s nepřiměřeným časem pobytu jen pro získání vyšší odměny. Místo toho odpovídá třídě problému lineární a frakční optimalizace odměn Markov.

Škodlivým aspektem takových optimalizací poměru je však to, že jakmile je dosažený poměr v určitém stavu vysoký, může optimalizace vybrat stavy vedoucí k nízkému poměru, protože mají vysokou pravděpodobnost ukončení, takže je pravděpodobné, že proces skončí dříve poměr výrazně klesá. Nastavení problému, aby se zabránilo takovým předčasným ukončením, spočívá v definování optimalizace jako maximalizace budoucího poměru, který vidí každý stát. Předpokládá se, že pro tento problém existuje indexace, kterou lze vypočítat jako jednoduchou variaci na stávající algoritmy restartu ve stavu nebo eliminaci stavu a vyhodnotit, aby fungovala dobře v praxi.^[15]

Poznámky

Reference

• Scully, Ziv a Harchol-Balter, Mor a Scheller-Wolf, Alan (2018). „SOAP: Jedna čistá analýza všech politik plánování podle věku“. Sborník ACM o měření a analýze výpočetních systémů. ACM. 2 (1): 16. doi:10.1145/3179419. S2CID  216145213.CS1 maint: více jmen: seznam autorů (odkaz)
• Berry, Donald A. a Fristedt, Bert (1985). Problémy banditů: Postupné přidělování experimentů. Monografie o statistice a aplikované pravděpodobnosti. London: Chapman & Hall. ISBN  978-0-412-24810-8.CS1 maint: více jmen: seznam autorů (odkaz)
• Gittins, J.C. (1989). Indexy přidělení vícebojů banditům. Série Wiley-Interscience v systémech a optimalizaci. předmluva od Peter Whittle. Chichester: John Wiley & Sons, Ltd. ISBN  978-0-471-92059-5.
• Weber, R.R. (Listopad 1992). "Na indexu Gittins pro bandy s více pásmy". Annals of Applied Probability. 2 (4): 1024–1033. doi:10.1214 / aoap / 1177005588. JSTOR  2959678.
• Katehakis, M. a A. F. Veinott, Jr. (1987). Msgstr "Problém víceramenných banditů: rozklad a výpočet". Matematika operačního výzkumu. 12 (2): 262–268. doi:10,1287 / měsíc 12. 2. 262. JSTOR  3689689.CS1 maint: více jmen: seznam autorů (odkaz)
• Cowan, W. a M.N. Katehakis (2014). „Víceramenní bandité pod všeobecným odpisem a závazkem“. Pravděpodobnost v technických a informačních vědách. 29: 51–76. doi:10.1017 / S0269964814000217.

externí odkazy

• [1] Matlab / Octave implementace algoritmů výpočtu indexu
• Cowan, Robin (1991). „Želvy a zajíci: volba mezi technologiemi neznámých zásluh“. Ekonomický deník. 101 (407): 801–814. doi:10.2307/2233856. JSTOR  2233856.