Багаторукий бандит

У теорії ймовірностей та машинному навчанні задача багаторукого бандита (яку іноді називають задачею K- або N-рукого бандита) — це задача розподілу обмеженої множини ресурсів між конкуруючими альтернативами таким чином, щоб максимізувати очікуваний виграш, коли властивості кожного варіанту відомі лише частково на момент ухвалення рішення, і можуть стати краще зрозумілими з плином часу або шляхом розподілу ресурсів для реалізації варіанту. Це класична задача навчання з підкріпленням, яка є прикладом дилеми балансу між експлуатацією та розвідкою. Назва походить від уявного гравця на низці ігрових автоматів (їх часто називають «однорукими бандитами»), який має вирішити, на яких автоматах варто грати, скільки разів варто грати на кожному автоматі та в якому порядку слід грати, і чи продовжувати з поточним автоматом або спробувати інший. Проблема багаторуких бандитів також підпадає під широку категорію ^[en].

Ряд ігрових автоматів у Лас-Вегасі

У цій задачі кожен автомат забезпечує випадкову винагороду відповідно до розподілу ймовірностей, який властивий для цього автомату. Мета гравця — максимізувати суму винагород, яку він отримує відповідно у випадку задіяння обраної послідовності важелів. Принципова проблема, з якою стикається гравець на кожному кроці, полягає в тому, що він має зробити вибір, між «експлуатацією» автомата, який має найвищий очікуваний прибуток, і «розвідкою», щоб отримати більше інформації про очікувані виграші інших автоматів. Питання компромісу між розвідкою та експлуатацією також виникає у машинному навчанні. На практиці багаторукі бандити використовувались для моделювання таких задач, як управління дослідницькими проектами у великій організації, як науковий фонд або фармацевтична компанія. У ранніх формулюваннях задачі гравець починає взаємодію без початкових знань про автомати.

Герберт Роббінс у 1952 році, усвідомлюючи важливість цієї задачі, побудував збіжні стратегії відбору сукупності в «деяких аспектах послідовного планування експериментів». Теорема про індекс Гіттінса, вперше опублікована ^[en], дає оптимальну стратегію максимізації очікуваної винагороди з урахуванням коефіцієнта знецінювання.

Емпірична мотивація

Як потрібно розподілити наявний бюджет між цими дослідницькими інститутами, щоб максимізувати результати?

Проблема багаторукого бандита моделює агента, який одночасно намагається здобути нові знання (що називається «розвідкою») та оптимізувати свої рішення на основі існуючих знань (називається «експлуатацією»). Агент намагається збалансувати ці конкуруючі завдання, щоб максимізувати загальну принесену ними цінність за розглянутий проміжок часу. Існує багато практичних застосувань моделі бандита, наприклад:

• клінічні випробування, які вивчають ефекти різних експериментальних методів лікування для мінімізації втрат серед пацієнтів,
• зусилля по ^[en] для мінімізації затримок у мережі,
• створення фінансового портфеля.

У цих практичних прикладах задача полягає у збалансуванні максимізації винагороди на основі вже набутих знань із спробами нових дій для подальшого збільшення знань. Ця дилема відома як компроміс між експлуатацією та дослідженням в машинному навчанні.

Модель також використовувалася для управління динамічним розподілом ресурсів для різних проектів, відповідаючи на питання, над яким проектом варто працювати, зважаючи на невизначеність щодо складності та вигідності кожної можливості.

Спочатку задача досліджувалась науковцями союзників у Другій світовій війні та виявилася настільки складною, що, за жартівливими словами ^[en], пропонувалося скинути її над Німеччиною, щоб німецькі вчені також могли витрачати на неї свій час.

Варіант задачі, який набув широкого визнання у сучасному формулюванні, був запропонований Гербертом Роббінсом у 1952 році.

Модель багаторукого бандита

Багаторукого бандита (коротко: бандит або БРБ) можна розглядати як сукупність розподілів дійсних чисел ${\displaystyle B=\{R_{1},\dots ,R_{K}\}}$, кожен розподіл пов'язаний з винагородами, які отримуються натисканням одного із ${\displaystyle K\in \mathbb {N} ^{+}}$ важелів. Нехай ${\displaystyle \mu _{1},\dots ,\mu _{K}}$ будуть середніми значеннями, які пов'язані з цими розподілами винагород. Гравець ітеративно грає по одному важелю за раунд і отримує відповідну винагороду. Метою є максимізація суми зібраних винагород. Горизонтом ${\displaystyle H}$ називається кількість раундів, які залишилось зіграти. Задача про багаторуких бандитів формально еквівалентна процесу Маркова з одним станом. Смуток ${\displaystyle \rho }$ після ${\displaystyle T}$ раундів визначається як очікувана різниця між сумою винагороди, пов'язаною з оптимальною стратегією, та сумою отриманих винагород:

${\displaystyle \rho =T\mu ^{*}-\sum _{t=1}^{T}{\widehat {r}}_{t}}$ ,

де ${\displaystyle \mu ^{*}=\max _{k}\{\mu _{k}\}}$ — максимальне середнє значення винагороди, і ${\displaystyle {\widehat {r}}_{t}}$ — винагорода у раунді t.

Стратегія нульового смутку — це стратегія, середній смуток якої за раунд ${\displaystyle \rho /T}$ прямує до нуля з імовірністю 1, коли кількість зіграних раундів прямує до нескінченності. Інтуїтивно зрозуміло, що стратегії нульового смутку гарантовано збігаються до (не обов'язково єдиної) оптимальної стратегії, якщо зіграно достатньо раундів.

Варіації задачі

Загальноприйнятим формулюванням є двійковий багаторукий бандит або багаторукий бандит Бернуллі, який видає винагороду одиниця з ймовірністю ${\displaystyle p}$, а в протилежному випадку винагорода дорівнює нулю.

В іншому формулюванні задачі про багаторукого бандита кожна рука представляє незалежну машину Маркова. Кожного разу, коли грається певна рука, стан цієї машини переходить у новий стан, обраний відповідно до розподілу ймовірностей станів машини Маркова. Тобто, кожного разу винагорода залежить від поточного стану машини. Для узагальнення, яке називають «задачею неспокійного бандита», стани рук, які не обираються гравцем, також можуть еволюціонувати з часом. Також розглядаються системи, в яких кількість варіантів (щодо того, яку руку зіграти) з часом збільшується.

Дослідники-інформатики вивчали багаторуких бандитів при найгірших припущеннях, отримуючи алгоритми, що дозволяють мінімізувати смуток як в кінцевому, так і в нескінченному (асимптотичному) часових горизонтах як у випадку стохастичного, так і у випадку нестохастичного виграшу.

Стратегії

Основним проривом була побудова оптимальної генеральної сукупності стратегій або політик (які мають рівномірно максимальний коефіцієнт збіжності до сукупності з найвищим середнім значенням) у роботі, яка описана далі.

Оптимальні рішення

У статті «Асимптотично ефективні правила адаптивного розподілу» Лай і Роббінс (наступні статті Роббінса та його колег відсилають до статі Роббінса 1952 року) побудували збіжний відбір стратегій, що мають найшвидший рівень збіжності (до генеральної сукупності з найвищим середнім значенням) у випадку, коли розподіли винагород є однопараметричним експоненціальним сімейством. Потім у роботі ^[en] та Роббінса за спрощеної стратегії було надано доведення у випадку нормальних генеральних сукупностей з відомими дисперсіями. Подальше вагоме просування здійснили Бурнетас і Катехакіс у роботі «Оптимальні адаптивні політики для задачі послідовного розподілу», в якій були побудовані стратегії на основі індексу з рівномірно максимальним коефіцієнтом збіжності за більш загальних умов, що включають випадок, коли розподіли результатів від кожної сукупності залежать від вектору невідомих параметрів. Бурнетас і Катехакіс (1996) також надали явне рішення для важливого випадку, коли розподіли результатів є довільними (тобто непараметричними) дискретними одновимірними розподілами.

Пізніше в «Оптимальній адаптивній політиці для Марковських процесів ухвалювання рішень» Бурнетас і Катехакіс дослідили набагато більшу модель процесів ухвалювання рішень Маркова з частковою інформацією, коли закон переходу та/або очікувана винагорода за один період можуть залежати від невідомих параметрів. У цій роботі була побудована явна форма для класу адаптивних стратегій, які мають рівномірно максимальну збіжність для загальної очікуваної винагороди з кінцевим горизонтом, за необхідних припущень щодо скінченності простору дій та станів й незвідності правила переходу. Головною особливістю цих стратегій є те, що вибір дій у кожному стані та періоді часу базується на індексах, які є записом правої частини оцінки середньої винагороди у рівняннях оптимальності. Їх назвали оптимістичним підходом у роботах Теварі та Бартлетта, Ортнера Філіппі, Каппе та Гарів'є, а також Хонди та Такемури.

Коли оптимальні рішення для задач про одноруких бандитів використовуються для оцінки вибору, який роблять тварини, через активність нейронів у мигдалині та смугастому тілі кодується значення, яке виводиться з цих правил, і може використовуватися для декодування, коли тварини роблять вибір між дослідженням та експлуатацією. Більше того, оптимальні стратегії краще прогнозують поведінку тварин при виборі, ніж альтернативні стратегії (описані нижче). Це свідчить про те, що оптимальні рішення для задач багаторуких бандитів є біологічно правдоподібними, незважаючи на вимоги до обчислень.

Наближені розв'язки

Існує багато стратегій, які забезпечують наближене розв'язання ЗББ, і їх можна віднести до чотирьох широких категорій, які докладно описані нижче.

Напіврівномірні стратегії

Напіврівномірні стратегії були найдавнішими (і найпростішими) стратегіями, які дають наближений розв'язок ЗББ. Всі ці стратегії мають спільну жадібну поведінку, коли найкращий важіль (на основі попередніх спостережень) завжди використовується, за винятком випадків, коли вживається (рівномірно) випадкова дія.

• Епсилон-жадібна стратегія: Найкращий важіль вибирається з ймовірністю ${\displaystyle 1-\varepsilon }$, і важіль вибирається випадково з рівною ймовірністю ${\displaystyle \epsilon }$. Типовим значенням параметра може бути ${\displaystyle \varepsilon =0.1}$, але він може сильно відрізнятися в залежності від обставин та цілей.
• Епсилон-перша стратегія: Після чистої фази розвідки йде фаза чистої експлуатації. Якщо ${\displaystyle N}$ — загальна кількість випробувань, то фаза розвідки складається з ${\displaystyle \varepsilon N}$ випробувань і фаза експлуатації — ${\displaystyle (1-\varepsilon )N}$ випробувань. Під час фази розвідки випадковим чином вибирається важіль (з рівною ймовірністю); на етапі експлуатації завжди вибирається найкращий важіль.
• Стратегія епсилон-зменшення: Подібна до епсилон-жадібної стратегії, за винятком того, що значення ${\displaystyle \varepsilon }$ зменшується з проходження експерименту, що призводить до надзвичайно дослідницької поведінки на початку та надзвичайно експлуататорської поведінки на фініші.
• Адаптивна епсилон-жадібна стратегія, заснована на ціннісних відмінностях (VDBE): Подібна до стратегії зменшення епсилону, за винятком того, що епсилон зменшується відповідно до прогресу навчання замість ручного регулювання (Токіч, 2010). Великі коливання оцінок вартості призводять до високого епсилону (велика розвідка, низька експлуатація); низькі коливання до низького епсилону (низька розвідка, висока експлуатація). Подальші поліпшення можуть бути досягнуті шляхом вибору дій, зважених на софтмаксі, у випадку дослідницьких дій (Tokic & Palm, 2011).
• Адаптивна епсилон-жадібна стратегія на основі баєсових ансамблів (Epsilon-BMC): Адаптивна стратегія адаптації епсилону для посилення навчання, подібного до VBDE, з монотонними гарантіями збіжності. У цьому підході параметр епсилон розглядається як очікування постеріорного розподілу, який оцінює жадібного агента (який повністю довіряє отриманій винагороді) та агента, який навчається одноманітно (який не довіряє отриманій винагороді). Докладніше див. Гімельфарб та ін., 2019.
• Контекстуальна-епсілон-жадібна стратегія: Подібна до епсілон-жадібної стратегії, за винятком того, що значення ${\displaystyle \varepsilon }$ обчислюється з урахуванням ситуації при проходженні експерименту, що дозволяє алгоритму брати до уваги контекст. Він базується на динамічному балансуванні розвіки/експлуатації і може адаптивно збалансувати два аспекти, вирішуючи, яка ситуація є найбільш відповідною для розвідки чи експлуатації, що призводить до надзвичайно дослідницької поведінки, коли ситуація не є критичною, і дуже експлуататорської поведінки у критичній ситуації.

Див. також

• Індекс Гіттінса — потужна, загальна стратегія аналізу задач про ББ
• Жадібний алгоритм
• ^[en]
• ^[en]

Примітки

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. (1989), Multi-armed bandit allocation indices, Wiley-Interscience Series in Systems and Optimization., Chichester: John Wiley & Sons, Ltd., ISBN 
4. ; Fristedt, Bert (1985), Bandit problems: Sequential allocation of experiments, Monographs on Statistics and Applied Probability, London: Chapman & Hall, ISBN 
5. Weber, Richard (1992), On the Gittins index for multiarmed bandits, , 2 (4): 1024—1033, doi:10.1214/aoap/1177005588, JSTOR 2959678
6. 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. (1979). Bandit Processes and Dynamic Allocation Indices. Journal of the Royal Statistical Society. Series B (Methodological). 41 (2): 148—177. doi:10.1111/j.2517-6161.1979.tb01068.x. JSTOR 2985029.
8. 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.
9. Press (1986)
10. Brochu, Eric; Hoffman, Matthew W.; de Freitas, Nando (September 2010), Portfolio Allocation for Bayesian Optimization, arXiv:1009.5419, Bibcode:2010arXiv1009.5419B
11. Shen, Weiwei; Wang, Jun; Jiang, Yu-Gang; Zha, Hongyuan (2015), , Proceedings of International Joint Conferences on Artificial Intelligence (IJCAI2015), архів оригіналу за 4 грудня 2021, процитовано 4 грудня 2021
12. Farias, Vivek F; Ritesh, Madan (2011), The irrevocable multiarmed bandit problem, , 59 (2): 383—399, doi:10.1287/opre.1100.0891
13. (1979), Discussion of Dr Gittins' paper, , Series B, 41 (2): 148—177, doi:10.1111/j.2517-6161.1979.tb01069.x
14. Vermorel, Joannes; Mohri, Mehryar (2005), (PDF), In European Conference on Machine Learning, Springer, с. 437—448, архів оригіналу (PDF) за 21 листопада 2008, процитовано 4 грудня 2021
15. (1988), Restless bandits: Activity allocation in a changing world, Journal of Applied Probability, 25A: 287—298, doi:10.2307/3214163, JSTOR 3214163, MR 0974588
16. (1981), Arm-acquiring bandits, Annals of Probability, 9 (2): 284—292, doi:10.1214/aop/1176994469
17. Auer, P.; Cesa-Bianchi, N.; Freund, Y.; Schapire, R. E. (2002). The Nonstochastic Multiarmed Bandit Problem. 32 (1): 48—77. CiteSeerX 10.1.1.130.158. doi:10.1137/S0097539701398375.
18. Lai, T.L.; Robbins, H. (1985). Asymptotically efficient adaptive allocation rules. Advances in Applied Mathematics. 6 (1): 4—22. doi:10.1016/0196-8858(85)90002-8.
19. Katehakis, M.N.; Robbins, H. (1995). Sequential choice from several populations. Proceedings of the National Academy of Sciences of the United States of America. 92 (19): 8584—5. Bibcode:1995PNAS...92.8584K. doi:10.1073/pnas.92.19.8584. PMC 41010. PMID 11607577.
20. Burnetas, A.N.; Katehakis, M.N. (1996). Optimal adaptive policies for sequential allocation problems. Advances in Applied Mathematics. 17 (2): 122—142. doi:10.1006/aama.1996.0007.
21. Burnetas, A.N.; Katehakis, M.N. (1997). Optimal adaptive policies for Markov decision processes. Math. Oper. Res. 22 (1): 222—255. doi:10.1287/moor.22.1.222.
22. Tewari, A.; Bartlett, P.L. (2008). (PDF). Advances in Neural Information Processing Systems. 20. CiteSeerX 10.1.1.69.5482. Архів оригіналу (PDF) за 25 травня 2012. Процитовано 4 грудня 2021.
23. Ortner, R. (2010). Online regret bounds for Markov decision processes with deterministic transitions. Theoretical Computer Science. 411 (29): 2684—2695. doi:10.1016/j.tcs.2010.04.005.
24. Filippi, S. and Cappé, O. and Garivier, A. (2010). «Online regret bounds for Markov decision processes with deterministic transitions», Communication, Control, and Computing (Allerton), 2010 48th Annual Allerton Conference on, pp. 115—122
25. Honda, J.; Takemura, A. (2011). An asymptotically optimal policy for finite support models in the multi-armed bandit problem. Machine Learning. 85 (3): 361—391. arXiv:0905.2776. doi:10.1007/s10994-011-5257-4.
26. Averbeck, B.B. (2015). Theory of choice in bandit, information sampling, and foraging tasks. PLOS Computational Biology. 11 (3): e1004164. Bibcode:2015PLSCB..11E4164A. doi:10.1371/journal.pcbi.1004164. PMC 4376795. PMID 25815510.{{}}: Обслуговування CS1: Сторінки із непозначеним DOI з безкоштовним доступом ()
27. Costa, V.D.; Averbeck, B.B. (2019). Subcortical Substrates of Explore-Exploit Decisions in Primates. Neuron. 103 (3): 533—535. doi:10.1016/j.neuron.2019.05.017. PMC 6687547. PMID 31196672.
28. Sutton, R. S. & Barto, A. G. 1998 Reinforcement learning: an introduction. Cambridge, MA: MIT Press.
29. Tokic, Michel (2010), (PDF), KI 2010: Advances in Artificial Intelligence, Lecture Notes in Computer Science, т. 6359, Springer-Verlag, с. 203—210, doi:10.1007/978-3-642-16111-7_23, ISBN , архів оригіналу (PDF) за 4 грудня 2021, процитовано 4 грудня 2021.
30. Tokic, Michel; Palm, Günther (2011), (PDF), KI 2011: Advances in Artificial Intelligence, Lecture Notes in Computer Science, т. 7006, Springer-Verlag, с. 335—346, ISBN , архів оригіналу (PDF) за 23 листопада 2018, процитовано 4 грудня 2021.
31. Gimelfarb, Michel; Sanner, Scott; Lee, Chi-Guhn (2019), (PDF), Proceedings of the Thirty-Fifth Conference on Uncertainty in Artificial Intelligence, AUAI Press, с. 162, архів оригіналу (PDF) за 1 березня 2021, процитовано 4 грудня 2021.
32. Bouneffouf, D.; Bouzeghoub, A.; Gançarski, A. L. (2012), A Contextual-Bandit Algorithm for Mobile Context-Aware Recommender System, Neural Information Processing, Lecture Notes in Computer Science, т. 7665, с. 324, doi:10.1007/978-3-642-34487-9_40, ISBN