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:
kde je stochastický proces, je schopnost (také nazývaná odměna) spojená s diskrétním stavem , je pravděpodobnost, že stochastický proces nekončí, a je uveden operátor podmíněného očekáváníC:
s 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:
kde je funkce hodnoty
se stejným zápisem jako výše. To platí
Restartujte ve stavu formulace
Li 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 , čímž se buduje Markovův rozhodovací proces .
Gittinsův index tohoto státu je nejvyšší celková odměna, jaké lze dosáhnout pokud se člověk vždy může rozhodnout pokračovat nebo restartovat z tohoto stavu .
kde označuje ukončení politiky . To platí
- .
Zobecněný index
Pokud je pravděpodobnost přežití záleží na stavu , zobecnění zavedené Soninem (2008) definuje index Gittins jako maximální diskontovaná celková odměna za šanci na ukončení.
kde
Li je nahrazen v definicích , a , pak to platí
toto pozorování vede Sonin k závěru, že a ne 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
- ^ A b C d Cowan, Robin (červenec 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.
- ^ A b C Gittins, J. C. (1979). "Banditské procesy a indexy dynamické alokace". Journal of the Royal Statistical Society. Řada B (metodická). 41 (2): 148–177. JSTOR 2985029.
- ^ Mitten L (1960). „Analytické řešení problému se sekvencí při testování nejnižších nákladů“. Journal of Industrial Engineering. 11 (1): 17.
- ^ Gittins, J. C .; Jones, D. M. (1979). "Dynamický alokační index pro problém se zlevněnými multiamediálními bandity". Biometrika. 66 (3): 561–565. doi:10.2307/2335176. JSTOR 2335176.
- ^ Weitzman, Martin L. (1979). "Optimální hledání nejlepší alternativy". Econometrica. 47 (3): 641–654. doi:10.2307/1910412. JSTOR 1910412.
- ^ Whittle, Peter (1980). "Víceramenní bandité a index Gittins". Journal of the Royal Statistical Society, Series B. 42 (2): 143–149.
- ^ Varaiya, P .; Walrand, J .; Buyukkoc, C. (květen 1985). "Rozšíření problému s více pásmy s bandity: Zlevněný případ". Transakce IEEE na automatickém ovládání. 30 (5): 426–439. doi:10.1109 / TAC.1985.1103989.
- ^ Chen Y.R., Katehakis M.N. (1986). Msgstr "Lineární programování pro konečný stav víceramenných banditů". Matematika. Oper. Res. 11 (1): 180–183. doi:10,1287 / měsíc 11. 11. 180.
- ^ Kallenberg L.C.M. (1986). „Poznámka k výpočtu indexu Gittins od MN Katehakise a Y.-R. Chena“. Matematika. Oper. Res. 11 (1): 184–186. doi:10,1287 / měsíc 11. 11. 184.
- ^ Katehakis M., Veinott A. (1987). Msgstr "Problém víceramenných banditů: rozklad a výpočet". Matematika. Oper. Res. 12 (2): 262–268. doi:10,1287 / měsíc 12. 2. 262.
- ^ Sonin I (2008). "Zobecněný index Gittins pro Markovův řetězec a jeho rekurzivní výpočet". Statistika a pravděpodobnostní dopisy. 78 (12): 1526–1533. doi:10.1016 / j.spl.2008.01.049.
- ^ Ni, Mora J (2007). „A (2/3) ^ n Rychle se otáčející algoritmus pro Gittinsův index a optimální zastavení Markovova řetězce“. INFORMS Journal o práci na počítači. 19 (4): 596–606. CiteSeerX 10.1.1.77.5127. doi:10.1287 / ijoc.1060.0206.
- ^ Cowan, Wesley; Katehakis, Michael N. (leden 2015). „Víceramenní bandité podléhají obecnému odpisu a závazku“. Pravděpodobnost v technických a informačních vědách. 29 (1): 51–76. doi:10.1017 / S0269964814000217.
- ^ 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)
- ^ Di Gregorio, Lorenzo a Frascolla, Valerio (1. října 2019). Optimalizace předání v heterogenních sítích. Světové fórum 5G. arXiv:1908.09991v2.CS1 maint: více jmen: seznam autorů (odkaz)
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.