Kako znati da li odabrati novi smjer ili se držati provjerenog? I k tome imati, matematički potkrijepljenu, vjerojatnost da li smo odabrali bolje ili lošije. Gittins index.

Gittins index je matematički problem rješavanja teorije redova, čekanja i posluživanja. Neću vas zamarati teškim matematičkim opisima i detaljima. Ako nekoga zanima više u poveznicama može pronaći znanstvene članke i radove o Gittins indeksu.

1979-te godine, John Gittins dobio je zadatak pronaći model optimizacije investicija u nove produkte u tvrtki Unilever. Cilj zadatak je bio izračunati matematičku vjerojatnost odabira između investicije u novi ili postojeći već dokazani lijek. Uvjet je bio da novi lijek mora biti najmanje 90% učinkovit i profitabilan kao postojeći lijek.

Nakon mjeseci rada, nastao je Gittins index [1].

Unilever je koristio ovu matricu za procjenu opravdanosti promjene smjera investicija uspoređujući broj uspjeha i neuspjeha dva različita lijeka. Primjerice, ako je postojeći lijek bio uspješan 9 puta a neuspješan 8 puta, Gittins indeks iznosi 0,56. A novi lijek je bio uspješan 3 puta i neuspješan 3 puta, Gittins indeks iznosi 0,58. Ako ne postoji broj uspjeha i neuspjeha (0:0), Gittins indeks iznosi 0.70. Ukratko bolje bi prošli kada bi išli “na slijepo” tj. bez ikakvih mjerenja nego s postojećim lijekom koji ima indeks 0.56.

Gittins indeks i danas se smatra vrlo pouzdanom metodom za potrebe donošenja odluka da li ostati pri trenutačnom rješenju ili promijeniti smjer prema novom rješenju.

Zašto Gittins indeks umjesto jednostavne usporedbe dvije brojke? 10 uspjeha i 10 neuspjeha, u postotku, jednak je kao i 3 uspjeha i 3 neuspjeha. Oboje iznosi 50%. Naočigled logično. Međutim, prema teoriji vjerojatnosti koja je poznata pod nazivom Multi-armed bandit, svaki sljedeći odabir je stohastičke prirode te je moguće izračunati vjerojatnost svakog sljedećeg odabira.

Gittins indeks je kompleksno za izračunati [5]. Međutim, postoje gotovi kalkulatori za izračun Gittins indeksa [6].

Primjena? U knjizi Algorithms to Live by, autori daju jako puno primjera gdje je moguće primijeniti ovaj matematički problem. Od odabira restorana do odabira ključnih riječi koje je moguće bolje koristiti za on-line oglašavanje. Kao uvod u knjigu priložio sam video “Talks at Google” gdje autori prolaze kroz primjere.

Video materijali

Za one koji žele znati više

[1] Bandit Processes and Dynamic Allocation Indices, J. C. Gittins, Journal of the Royal Statistical Society: Series B (Methodological), 1979, https://rss.onlinelibrary.wiley.com/doi/10.1111/j.2517-6161.1979.tb01068.x

[2] Multi-armed bandit, Wikipedia, https://en.wikipedia.org/wiki/Multi-armed_bandit

[3] Multi-Armed Bandits and the Gittins Index, Bobby Kleinberg, Cornell University, 2017, https://www.cs.cornell.edu/courses/cs6840/2017sp/lecnotes/6840sp17R_Kleinberg.pdf

[4] On the Gittins Index for Multiarmed Bandits, Richard Weber, The Annals of Applied Probability, 1992, https://www.jstor.org/stable/2959678

[5] Practical Calculation of Gittins Indices for Multi-armed Bandits, James Edwards, 2019, https://arxiv.org/abs/1909.05075

[6] Gittins Index, Google Play Store, https://play.google.com/store/apps/details?id=dk.allanlindjensen.gittinsindex&hl=en_AU