Gittins index

Gittins index är ett mått på den belöning som kan uppnås genom en given stokastisk process med vissa egenskaper, nämligen: processen har ett slutgiltigt avslutningstillstånd och utvecklas med ett alternativ, vid varje mellanliggande tillstånd, att avsluta. Vid terminering vid ett givet tillstånd är den erhållna belöningen summan av de probabilistiska förväntade belöningarna som är associerade med varje tillstånd från det faktiska avslutande tillståndet till det slutliga terminaltillståndet, inklusive. Indexet är en riktig skalär .

Terminologi

För att illustrera teorin kan vi ta två exempel från en utvecklingssektor, till exempel från elgenererande teknologier: vindkraft och vågkraft. Om vi ​​presenteras för de två teknologierna när de båda föreslås som idéer kan vi inte säga vilken som kommer att vara bättre i det långa loppet eftersom vi ännu inte har några data att basera våra bedömningar på. Det skulle vara lätt att säga att vågkraften skulle vara för problematisk att utveckla då det verkar lättare att sätta upp många vindkraftverk än att göra de långa flytande generatorerna, bogsera ut dem till havs och lägga de kablar som behövs.

Om vi ​​skulle göra en bedömning vid den tidiga utvecklingsfasen skulle vi kunna döma en teknik till att läggas på hyllan och den andra skulle utvecklas och tas i drift. Om vi ​​utvecklar båda teknologierna skulle vi kunna göra en bedömning av var och en genom att jämföra framstegen för varje teknik vid ett visst tidsintervall, till exempel var tredje månad. De beslut vi fattar om investeringar i nästa steg skulle baseras på dessa resultat.

I en artikel 1979 som heter Bandit Processes and Dynamic Allocation Index föreslår John C. Gittins en lösning på problem som detta. Han tar de två grundläggande funktionerna i ett " schemaläggningsproblem " och ett " flerarmad bandit "-problem och visar hur dessa problem kan lösas med hjälp av dynamiska allokeringsindex . Han tar först "Schemaläggningsproblemet" och reducerar det till en maskin som måste utföra jobb och som har en bestämd tidsperiod, till exempel varje timme eller dag, för att avsluta varje jobb i. Maskinen får ett belöningsvärde, baserat på efterbehandling eller inte inom tidsperioden, och ett sannolikhetsvärde för om det kommer att slutföras eller inte för varje jobb beräknas. Problemet är "att bestämma vilket jobb som ska bearbetas härnäst i varje steg för att maximera den totala förväntade belöningen." Han går sedan vidare till "Multi-armed bandit problem" där varje drag på en " en armed bandit " spak tilldelas en belöningsfunktion för ett lyckat drag och en noll belöning för ett misslyckat drag. Sekvensen av framgångar bildar en Bernoulli-process och har en okänd sannolikhet för framgång. Det finns flera "banditer" och fördelningen av framgångsrika drag är beräknad och olika för varje maskin. Gittins säger att problemet här är "att bestämma vilken arm som ska dras härnäst i varje steg för att maximera den totala förväntade belöningen från en oändlig sekvens av drag."

Gittins säger att "Båda problemen som beskrivs ovan involverar en sekvens av beslut, som var och en är baserad på mer information än sina föregångare, och dessa båda problem kan hanteras av dynamiska allokeringsindex."

Definition

Inom tillämpad matematik är "Gittins index" ett verkligt skalärt värde som är associerat med tillståndet för en stokastisk process med en belöningsfunktion och med sannolikhet för uppsägning. Det är ett mått på belöningen som kan uppnås genom att processen utvecklas från det tillståndet och med sannolikheten att den kommer att avslutas i framtiden. "Indexpolicyn" som induceras av Gittins index, som består av att när som helst välja den stokastiska processen med det för närvarande högsta Gittins indexet, är lösningen på några stoppande problem , såsom det med dynamisk allokering, där en beslutsfattare måste maximera den totala belöningen genom att dela ut en begränsad mängd ansträngning till ett antal konkurrerande projekt, som vart och ett ger en stokastisk belöning. Om projekten är oberoende av varandra och endast ett projekt åt gången kan utvecklas, kallas problemet multi-armed bandit (en typ av Stokastiska schemaläggningsproblem ) och Gittins indexpolicy är optimal. Om flera projekt kan utvecklas kallas problemet Restless bandit och Gittins indexpolicy är en känd bra heuristik men ingen optimal lösning finns i allmänhet. I själva verket är detta problem i allmänhet NP-komplett och det är allmänt accepterat att ingen genomförbar lösning kan hittas.

Historia

Frågor om den optimala stopppolicyn i samband med kliniska prövningar har varit öppna från 1940-talet och på 1960-talet analyserade några författare enkla modeller som ledde till optimal indexpolicy, men det var först på 1970-talet som Gittins och hans medarbetare demonstrerade i en Markovian ramverket att den optimala lösningen i det allmänna fallet är en indexpolicy vars "dynamiska allokeringsindex" i princip kan beräknas för varje tillstånd i varje projekt som en funktion av det enskilda projektets dynamik. Parallellt med Gittins Martin Weitzman samma resultat i den ekonomiska litteraturen.

Strax efter Gittins banbrytande uppsats visade Peter Whittle att indexet uppstår som en Lagrange-multiplikator från en dynamisk programmeringsformulering av problemet som kallas retirement process och förmodade att samma index skulle vara en bra heuristik i en mer allmän uppsättning som heter Restless bandit . Frågan om hur man faktiskt beräknar index för Markov-kedjor togs först upp av Varaiya och hans medarbetare med en algoritm som beräknar indexen från de största först ner till de minsta och av Chen och Katehakis som visade att standard LP kunde användas för att beräkna indexet för ett tillstånd utan att kräva dess beräkning för alla tillstånd med högre indexvärden. LCM Kallenberg tillhandahöll en parametrisk LP-implementering för att beräkna indexen för alla tillstånd i en Markov-kedja. Vidare visade Katehakis och Veinott att indexet är den förväntade belöningen av en Markov-beslutsprocess konstruerad över Markov-kedjan och känd som Restart in State och kan beräknas exakt genom att lösa det problemet med policy iteration- algoritmen, eller ungefär med värde-iterationen algoritm. Detta tillvägagångssätt har också fördelen av att beräkna indexet för ett specifikt tillstånd utan att behöva beräkna alla de större indexen och det är giltigt under mer allmänna tillståndsutrymmesförhållanden. En snabbare algoritm för beräkning av alla index erhölls 2004 av Sonin som en konsekvens av hans elimineringsalgoritm för optimalt stopp av en Markov-kedja. I denna algoritm kan avslutningssannolikheten för processen bero på det aktuella tillståndet snarare än att vara en fast faktor. En snabbare algoritm föreslogs 2007 av Niño-Mora genom att utnyttja strukturen i ett parametriskt simplex för att minska beräkningsansträngningen för pivotstegen och därigenom uppnå samma komplexitet som den Gaussiska elimineringsalgoritmen . Cowan, W. och Katehakis (2014), tillhandahåller en lösning på problemet, med potentiellt icke-markovska, oräkneliga statliga belöningsprocesser, under ramar där antingen rabattfaktorerna kan vara olikformiga och variera över tiden, eller Aktiveringsperioderna för varje bandit kan inte vara fasta eller enhetliga, utan i stället för en eventuellt stokastisk aktiveringstid innan en byte till en annan bandit tillåts. Lösningen är baserad på generaliserade omstart-i-tillstånd-index.

Matematisk definition

Dynamiskt allokeringsindex

Den klassiska definitionen av Gittins et al. är:

$\nu (i)=\sup _{\tau >0}{\frac {\left\langle \sum _{t=0}^{\tau -1}\beta ^{t}R[Z(t)]\ höger\rangle _{Z(0)=i}}{\left\langle \sum _{t=0}^{\tau -1}\beta ^{t}\right\rangle _{Z(0)= i}}}$

där $Z(\cdot )$ är en stokastisk process, $R(i)$ är verktyget (även kallat belöning) som är associerat med det diskreta tillståndet $i$ , $\beta <1$ är sannolikheten att den stokastiska processen inte avslutas, och $\langle \cdot \rangle _{c}$ är den villkorliga förväntansoperatorn given c :

$\langle X\rangle _{c}\doteq \sum _{x\in \chi }xP\{X=x|c\}$

där $\chi$ är domänen för X .

Formulering av pensionsprocessen

Den dynamiska programmeringsformuleringen i termer av pensioneringsprocessen, som ges av Whittle, är:

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

där $v(i,k)$ är värdefunktionen

$v(i,k)=\sup _{ \tau >0}\left\langle \sum _{t=0}^{\tau -1}\beta ^{t}R[Z(t)]+\beta ^{t}k\right\rangle _ {Z(0)=i}$

med samma notation som ovan. Det håller det

$\nu (i)=(1-\beta )w(i).$

Omstart-in-state formulering

Om $Z(\cdot )$ är en Markov-kedja med belöningar, associerar tolkningen av Katehakis och Veinott (1987) till varje tillstånd åtgärden att starta om från ett godtyckligt tillstånd $i$ , och därmed konstruera en Markov-beslutsprocess $M_{i}$ .

Gittins Index för det tillståndet $i$ är den högsta totala belöningen som kan uppnås på $M_{i}$ om man alltid kan välja att fortsätta eller starta om från det tillståndet $i$ .

$h(i)=\sup _{\pi }\left\langle \ summa _{t=0}^{\tau -1}\beta ^{t}R[Z^{\pi }(t)]\right\rangle _{Z(0)=i}$

där $\pi$ indikerar en policy över $M_{i}$ . Det håller det

$h(i)=w(i)$ .

Generaliserat index

Om sannolikheten för överlevnad $\beta (i)$ beror på tillståndet $i$ , definierar en generalisering introducerad av Sonin (2008) Gittins index $\alpha (i)$ som den maximala rabatterade totala belöningen per chans till uppsägning.

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

var

$R^{\tau }(i)=\left\langle \sum _{t=0 }^{\tau -1}R[Z(t)]\right\rangle _{Z(0)=i}$

$Q^{\tau }(i)=\left\langle 1-\prod _{t=0}^{\tau -1}\beta [Z(t)]\ höger\rangle _{Z(0)=i}$

Om $\beta ^{t}$ ersätts med $\prod _{j=0}^{t-1}\beta [Z (j)]$ i definitionerna av $\nu (i)$ , $w(i)$ och $h(i)$ , sedan det håller det

$\alpha (i)=h(i)=w(i)$

$\ alfa (i)\neq k\nu (i),\forall k$

denna observation får Sonin att dra slutsatsen att $\alpha (i)$ och inte $\nu (i)$ är den "sanna betydelsen" av Gittins index.

Köteori

I köteorin används Gittins index för att bestämma den optimala schemaläggningen av jobb, t.ex. i en M/G/1-kö. Den genomsnittliga slutförandetiden för jobb under ett Gittins indexschema kan bestämmas med SOAP-metoden. Observera att dynamiken i kön i sig är markovisk och stokasticitet beror på ankomst- och serviceprocesserna. Detta i motsats till de flesta verk i lärandelitteraturen, där stokasticitet uttryckligen redovisas genom en brusterm.

Bråkproblem

Medan konventionella Gittins-index framkallar en policy för att optimera ackumuleringen av en belöning, består en vanlig problemställning av att optimera förhållandet mellan ackumulerade belöningar. Detta är till exempel ett fall för system att maximera bandbredden, bestående av data över tid, eller minimera strömförbrukningen, bestående av energi över tiden.

Denna klass av problem skiljer sig från optimeringen av en semi-Markov belöningsprocess, eftersom den senare kan välja stater med en oproportionerlig vistelsetid bara för att få en högre belöning. Istället motsvarar det klassen av linjär-fraktionell markov-belöningsoptimeringsproblem.

En skadlig aspekt av sådana kvotoptimeringar är emellertid att, när väl det uppnådda förhållandet i något tillstånd är högt, kan optimeringen välja tillstånd som leder till ett lågt förhållande eftersom de har en hög sannolikhet för avslutning, så att processen sannolikt avslutas innan förhållandet sjunker avsevärt. En probleminställning för att förhindra sådana tidiga uppsägningar består av att definiera optimeringen som maximering av det framtida förhållandet som varje stat ser. En indexering förmodas existera för detta problem, vara beräkningsbar som enkel variation på befintliga omstart-i-tillstånd eller tillståndselimineringsalgoritmer och utvärderas för att fungera bra i praktiken.

Anteckningar

•   Scully, Ziv och Harchol-Balter, Mor och Scheller-Wolf, Alan (2018). "SOAP: En ren analys av alla åldersbaserade schemaläggningspolicyer". Proceedings of the ACM on Measurement and Analysis of Computing Systems . ACM. 2 (1): 16. doi : 10.1145/3179419 . S2CID 216145213 . {{ citera tidskrift }} : CS1 underhåll: flera namn: lista över författare ( länk )
•   Berry, Donald A. och Fristedt, Bert (1985). Banditproblem: Sekventiell tilldelning av experiment . Monografier om statistik och tillämpad sannolikhet. London: Chapman & Hall. ISBN 978-0-412-24810-8 . {{ citera bok }} : CS1 underhåll: flera namn: lista över författare ( länk )
•   Gittins, JC (1989). Multi-armed bandit allokeringsindex . Wiley-Interscience-serien i system och optimering. förord ​​av Peter Whittle . Chichester: John Wiley & Sons, Ltd. ISBN 978-0-471-92059-5 .
•   Weber, RR (november 1992). "På Gittins index för flerarmade banditer". Annals of Applied Probability . 2 (4): 1024–1033. doi : 10.1214/aoap/1177005588 . JSTOR 2959678 .
•   Katehakis, M. och AF Veinott, Jr. (1987). "Det flerarmade banditproblemet: nedbrytning och beräkning". Operationsforskningens matematik . 12 (2): 262–268. doi : 10.1287/moor.12.2.262 . JSTOR 3689689 . {{ citera tidskrift }} : CS1 underhåll: flera namn: lista över författare ( länk )
• Cowan, W. och MN Katehakis (2014). "Multiarmade banditer under allmän avskrivning och engagemang". Sannolikhet inom ingenjörs- och informationsvetenskap . 29 : 51–76. doi : 10.1017/S0269964814000217 .

externa länkar

• [1] Matlab/Octave-implementering av indexberäkningsalgoritmerna
•   Cowan, Robin (1991). "Sköldpaddor och harar: val bland tekniker av okända förtjänster". The Economic Journal . 101 (407): 801–814. doi : 10.2307/2233856 . JSTOR 2233856 .