Kasutaja:Litvand/Mitmekäelise bandiidi ülesanne

Mitmekäelise bandiidi ülesanne (ka K-[1] või N-käelise bandiidi ülesanne[2]) on tõenäosusteooria valdkonnas ülesanne, mille puhul tuleb jaotada etteantud piiratud ressursside hulk üksteist välistavate valikute vahel, et maksimeerida oodatavat kasumit, kusjuures valikute omadused on valiku tegemisel ainult osaliselt teada ja neid võib paremini teada saada aja möödudes või valikule ressursse jagades.[3][4]

Ülesanne on nimetatud hüpoteetilise hasartmängija järgi, kelle ees on erinevad mänguautomaadid (mänguautomaate kutsutakse vahel ühekäelisteks bandiitideks) ning kes peab otsustama, milliseid mänguautomaate mängida ning mis järjekorras ja mitu korda neid mängida.[5]

Iga mänguautomaat annab kasumi, mis on juhuslik suurus ning mille tõenäosusjaotus on omane sellele mänguautomaadile. Hasartmängija eesmärk on maksimeerida teenitud kasumi summa.[3][4] Iga kord, kui mängija valib mänguautomaadi, on dilemma selle vahel, kas "ära kasutada" (inglise keeles "exploit") mänguautomaati, millel on kõrgeim oodatav kasum, või valida mõnda teist mänguautomaati, et avastada (inglise keeles "explore") sellelt saadava kasumi jaotuse täpsemat kuju. Dilemma valikute ärakasutamise ja avastamise vahel esineb sarnaselt ka masinõppes. Mitmekäelise bandiidi ülesannet on kasutatud praktikas erinevate probleemide modelleerimiseks. Üks neist on teaduslike projektide haldamine suures ravimifirmas, mille puhul ressursse tuleb jaotada erinevate projektide vahel.[3][4] Ajalooliselt uuriti esimesena sellist mitmekäelise bandiidi ülesande varianti, mille puhul mängija ei tea alguses (s.t. enne ühegi valiku tegemist) midagi mänguautomaatide (ja nende jaotuste) kohta.[6]

Kasutamine praktikas muuda

Mitmekäelise bandiidi ülesanne modelleerib agenti (s.t stiimulõppe õppijat), kes samaaegselt üritab teadmisi juurde saada ("avastamine") ja optimeerida valikuid olemasolevate teadmiste põhjal ("ärakasutamine"). Agent üritab leida kompromissi nende kahe eesmärgi vahel, et maksimeerida kasumi summat antud aja jooksul. Sellisel mudelil on mitmeid rakendusi, näiteks:

  • kliinilise uuringu käigus erinevate ravimite toimete uurimine, samas minimeerides kahju patsientidele;[3][4][7][8]
  • dünaamiline marsruutimine võrguliikluse latentsi minimeerimiseks;
  • väärtpaberite portfelli valimine.[9]

Esimesena üritasid ülesannet lahendada liitlasriikide teadlased Teise maailmasõja ajal. Matemaatiku Peter Whittle'i sõnul osutus aga ülesanne nii raskeks, et liitlasriikide teadlased jutustasid mõtest kirjutada ülesande kirjeldus paberile ja visata see Saksamaa kohal alla, et Saksa teadlased leiaksid kirjelduse ja raisaksid oma aega ülesandele lahendust otsides.[10]

Versiooni ülesandest, mida tänapäeval tavaliselt analüüsitakse, formuleeris Herbert Robbins 1952. aastal.[6]

Mitmekäelise bandiidi mudel muuda

Mitmekäeline bandiit (ehk lihtsalt "bandiit") on vaadeldav kui tõenäosusjaotuste hulk  , kus iga jaotus vastab kasumile, mida saab ühest mänguautomaadist  . Olgu   nende jaotuste keskväärtused. Igal käigul valib mängur ühe mänguautomaadi ja saab teada praeguse kasumi (mänguautomaadi jaotusega juhusliku suuruse ühe väärtuse). Eesmärk on maksimeerida saadud kasumi summa. Horisont   on alles jäänud käikude arv. Kahetsus   pärast   käiku on defineeritud kui tegeliku kasumi summa ja optimaalse strateegiaga saadud kasumi summa vahe ooteväärtus,  , kus   on maksimaalne keskväärtus,  , ning   on saadud kasum käigul t.[11]

Viited muuda

  1. Auer, P.; Cesa-Bianchi, N.; Fischer, P. (2002). "Finite-time Analysis of the Multiarmed Bandit Problem". Machine Learning. 47 (2/3): 235–256. DOI:10.1023/A:1013689704352.
  2. Katehakis, M. N.; Veinott, A. F. (1987). "The Multi-Armed Bandit Problem: Decomposition and Computation". Mathematics of Operations Research. 12 (2): 262–268. DOI:10.1287/moor.12.2.262.
  3. 3,0 3,1 3,2 3,3 Gittins, J. C. (1989). "Multi-armed bandit allocation indices". Wiley-Interscience Series in Systems and Optimization. Chichester: John Wiley & Sons, Ltd. ISBN 0-471-92059-2. {{cite journal}}: viitemall journal nõuab parameetrit |journal= (juhend)
  4. 4,0 4,1 4,2 4,3 Berry, Donald A.; Fristedt, Bert (1985). "Bandit problems: Sequential allocation of experiments". Monographs on Statistics and Applied Probability. London: Chapman & Hall. ISBN 0-412-24810-7. {{cite journal}}: viitemall journal nõuab parameetrit |journal= (juhend)
  5. Weber, Richard (1992). "On the Gittins index for multiarmed bandits". Annals of Applied Probability. 2 (4): 1024–1033. DOI:10.1214/aoap/1177005588. JSTOR 2959678.
  6. 6,0 6,1 Robbins, H. (1952). "Some aspects of the sequential design of experiments". Bulletin of the American Mathematical Society. 58 (5): 527–535. DOI:10.1090/S0002-9904-1952-09620-8.
  7. Press, William H. (2009). "Bandit solutions provide unified ethical models for randomized clinical trials and comparative effectiveness research". Proceedings of the National Academy of Sciences. 106 (52): 22387–22392. Bibcode:2009PNAS..10622387P. DOI:10.1073/pnas.0912378106. PMC 2793317. PMID 20018711.{{cite journal}}: CS1 hooldus: postscript (link)
  8. Katehakis, M. and C. Derman (1986). "Computing Optimal Sequential Allocation Rules in Clinical Trials". IMS Lecture Notes-Monograph Series. 8: 29–39. DOI:10.1214/lnms/1215540286. JSTOR 4355518.{{cite journal}}: CS1 hooldus: postscript (link)
  9. Shen, Weiwei; Wang, Jun; Jiang, Yu-Gang; Zha, Hongyuan (2015). "Portfolio Choices with Orthogonal Bandit Learning". Proceedings of International Joint Conferences on Artificial Intelligence (IJCAI2015).
  10. Whittle, Peter (1979). "Discussion of Dr Gittins' paper". Journal of the Royal Statistical Society. Series B. 41 (2): 165. JSTOR 2985029.
  11. Vermorel, Joannes; Mohri, Mehryar (2005). "Multi-armed bandit algorithms and empirical evaluation" (PDF). In European Conference on Machine Learning. Springer: 437–448. {{cite journal}}: viitemall journal nõuab parameetrit |journal= (juhend)