Багаторукий бандит: відмінності між версіями

У [[Теорія ймовірностей|теорії ймовірностей]] та [[Машинне навчання|машинному навчанні]] '''задача багаторукого бандита''' (яку іноді називають '''''задачею'' ''K''- <ref name="doi10.1023/A:1013689704352">{{Cite journal|last=Auer|first=P.|last2=Cesa-Bianchi|first2=N.|last3=Fischer|first3=P.|year=2002|title=Finite-time Analysis of the Multiarmed Bandit Problem|journal=Machine Learning|volume=47|issue=2/3|pages=235–256|doi=10.1023/A:1013689704352|doi-access=free}}</ref> або ''N-рукого'' бандита''' <ref>{{Cite journal|last=Katehakis|first=M. N.|last2=Veinott|first2=A. F.|year=1987|title=The Multi-Armed Bandit Problem: Decomposition and Computation|url=https://semanticscholar.org/paper/e4fe28113fed71999a0db30a930e0b42d3ce55f1|journal=Mathematics of Operations Research|volume=12|issue=2|pages=262–268|doi=10.1287/moor.12.2.262}}</ref>) -&nbsp;— це задача розподілу обмеженої множини ресурсів між конкуруючими альтернативами таким чином, щоб максимізувати очікуваний виграш, коли властивості кожного варіанту відомі лише частково на момент прийняття рішення, і можуть стати краще зрозумілими з плином часу або шляхом розподілу ресурсів для реалізації варіанту<ref name="Gittins89">

</ref>. Це класична задача [[Навчаннянавчання з підкріпленням|підкріплення навчання]], яка є прикладом дилеми балансу між дослідженням та розвідкою. Назва походить від уявного [[Азартні ігри|гравця]] на низці [[Слот-машина|ігрових автоматів]] (їх часто називають "«[[wiktionary:one-armed bandit|однорукими бандитами]]"»), який має вирішити, на яких автоматах варто грати, скільки разів варто грати на кожному автоматі та в якому порядку слід грати, і чи продовжувати з поточним автоматом або спробувати інший<ref name="weber">{{Citation|last=Weber|first=Richard|number=4|journal=[[Annals of Applied Probability]]|pages=1024–1033|title=On the Gittins index for multiarmed bandits|volume=2|year=1992|jstor=2959678|doi=10.1214/aoap/1177005588}}</ref>. Проблема багаторуких бандитів також підпадає під широку категорію {{Нп|Стохастичне планування|стохастичного планування||Stochastic scheduling}}.

У цій задачі кожен автомат забезпечує випадкову винагороду відповідно до [[Розподіл імовірностей|розподілу ймовірностей,]], який властивий для цього автомату. Мета гравця -&nbsp;— максимізувати суму винагород, яку він отримує відповідно у випадку задіяння обраної послідовності важелів<ref name="Gittins89">

</ref>. Принципова проблема, з якою стикається гравець на кожному кроці, полягає в тому, що він має зробити вибір, між "«експлуатацією"» автомата, який має найвищий очікуваний прибуток, і "«розвідкою"», щоб отримати більше [[Теорема Баєса|інформації]] про очікувані виграші інших автоматів. Питання компромісу між розвідкою та експлуатацією також виникає у [[Машинне навчання|машинному навчанні]]. На практиці багаторукі бандити використовувались для моделювання таких задач, як управління дослідницькими проектами у великій організації, як науковий фонд або [[Фармацевтична промисловість|фармацевтична компанія]]. У ранніх формулюваннях задачі гравець починає взаємодію без початкових знань про автомати.

[[Герберт Роббінс]] у 1952 році, усвідомлюючи важливість цієї задачі, побудував збіжні стратегії відбору сукупності в "«деяких аспектах послідовного планування експериментів"»<ref>{{Cite journal|last=Robbins|first=H.|year=1952|title=Some aspects of the sequential design of experiments|journal=Bulletin of the American Mathematical Society|volume=58|issue=5|pages=527–535|doi=10.1090/S0002-9904-1952-09620-8|doi-access=free}}</ref>. Теорема про {{Нп|індекс Гіттінса|||Gittins index}}, вперше опублікована {{Нп|Джон Ч. Гіттінс|Джоном КЧ. Гіттінсом||John C. Gittins}}, дає оптимальну стратегію максимізації очікуваної винагороди з урахуванням [[Q-навчання#Коефіцієнт знецінювання|коефіцієнта знецінювання]]<ref>{{Cite journal|last=J. C. Gittins|author-link=John C. Gittins|year=1979|title=Bandit Processes and Dynamic Allocation Indices|journal=Journal of the Royal Statistical Society. Series B (Methodological)|volume=41|issue=2|pages=148–177|doi=10.1111/j.2517-6161.1979.tb01068.x|jstor=2985029}}</ref>.

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

* зусилля по адаптивній{{Нп|Динамічна маршрутизація|динамічній маршрутизації||Dynamic routing}} для мінімізації затримок у мережі,

Спочатку задача досліджувалась науковцями союзників у [[Друга світова війна|Другій світовій війні]] та виявилася настільки складною, що, за жартівливими словами {{Нп|Пітер Уіттл (математик)|Пітера Уіттла||Peter Whittle (mathematician)}}, пропонувалося скинути її над [[Німеччина|Німеччиною,]] щоб німецькі вчені також могли витрачати на неї свій час<ref name="Whittle79">

Багаторукого бандита (коротко: ''бандит'' або БРБ) можна розглядати як сукупність [[Розподіл імовірностей|розподілів]] дійсних чисел <math>B = \{R_1, \dots ,R_K\}</math>, кожен розподіл пов'язаний з винагородами, які отримуються натисканням одного із <math>K \in \mathbb{N}^+</math> важелів. Нехай <math>\mu_1, \dots, \mu_K</math> будуть середніми значеннями, які пов’язаніпов'язані з цими розподілами винагород. Гравець ітеративно грає по одному важелю за раунд і отримує відповідну винагороду. Метою є максимізація суми зібраних винагород. Горизонтом <math>H</math> називається кількість раундів, які залишилось зіграти. Задача про багаторуких бандитів формально еквівалентна процесу [[Марковський процес вирішування|Маркова]] з одним станом. [[Смуток (теорія рішень)|Смуток]] <math>\rho</math> після <math>T</math> раундів визначається як очікувана різниця між сумою винагороди, пов’язаноюпов'язаною з оптимальною стратегією, та сумою отриманих винагород:

де <math>\mu^* = \max_k \{ \mu_k \}</math> -&nbsp;— максимальне середнє значення винагороди, і <math>\widehat{r}_t</math> -&nbsp;— винагорода у раунді ''t''.

Стратегія ''нульового смутку'' -&nbsp;— це стратегія, середній смуток якої за раунд <math>\rho / T</math> прямує до нуля з імовірністю 1, коли кількість зіграних раундів прямує до нескінченності<ref name="Vermorel2005">

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

У статті "«Асимптотично ефективні правила адаптивного розподілу"» Лай і [[Герберт Роббінс|Роббінс]]<ref>{{Cite journal|last=Lai|first=T.L.|last2=Robbins|first2=H.|year=1985|title=Asymptotically efficient adaptive allocation rules|journal=Advances in Applied Mathematics|volume=6|issue=1|pages=4–22|doi=10.1016/0196-8858(85)90002-8}}</ref> (наступні статті Роббінса та його колег відсилають до статі Роббінса 1952 року) побудували збіжний відбір стратегій, що мають найшвидший рівень збіжності (до генеральної сукупності з найвищим середнім значенням) у випадку, коли розподіли винагород є однопараметричним експоненціальним сімейством. Потім у роботі {{Нп|Майкл Катехакіс|Катехакіса||Michael Katehakis}} та [[Герберт Роббінс|Роббінса]]<ref>{{Cite journal|last=Katehakis|first=M.N.|last2=Robbins|first2=H.|year=1995|title=Sequential choice from several populations|journal=Proceedings of the National Academy of Sciences of the United States of America|volume=92|issue=19|pages=8584–5|bibcode=1995PNAS...92.8584K|doi=10.1073/pnas.92.19.8584|pmc=41010|pmid=11607577}}</ref> за спрощеної стратегії було надано доведення у випадку нормальних генеральних сукупностей з відомими дисперсіями. Подальше вагоме просування здійснили Бурнетас і Катехакіс у роботі "«Оптимальні адаптивні політики для задачі послідовного розподілу"»<ref>{{Cite journal|last=Burnetas|first=A.N.|last2=Katehakis|first2=M.N.|year=1996|title=Optimal adaptive policies for sequential allocation problems|journal=Advances in Applied Mathematics|volume=17|issue=2|pages=122–142|doi=10.1006/aama.1996.0007}}</ref>, в якій були побудовані стратегії на основі індексу з рівномірно максимальним коефіцієнтом збіжності за більш загальних умов, що включають випадок, коли розподіли результатів від кожної сукупності залежать від вектору невідомих параметрів. Бурнетас і Катехакіс (1996) також надали явне рішення для важливого випадку, коли розподіли результатів є довільними (тобто непараметричними) дискретними одновимірними розподілами.

Пізніше в "«Оптимальній адаптивній політиці для Марковських процесів прийняття рішень"»<ref>{{Cite journal|last=Burnetas|first=A.N.|last2=Katehakis|first2=M.N.|year=1997|title=Optimal adaptive policies for Markov decision processes|journal=Math. Oper. Res.|volume=22|issue=1|pages=222–255|doi=10.1287/moor.22.1.222}}</ref> Бурнетас і Катехакіс дослідили набагато більшу модель процесів прийняття рішень Маркова з частковою інформацією, коли закон переходу та/або очікувана винагорода за один період можуть залежати від невідомих параметрів. У цій роботі була побудована явна форма для класу адаптивних стратегій, які мають рівномірно максимальну збіжність для загальної очікуваної винагороди з кінцевим горизонтом, за необхідних припущень щодо скінченності простору дій та станів й незводимості правила переходу. Головною особливістю цих стратегій є те, що вибір дій у кожному стані та періоді часу базується на індексах, які є записом правої частини оцінки середньої винагороди у рівняннях оптимальності. Їх назвали оптимістичним підходом у роботах Теварі та Бартлетта<ref>{{Cite journal|last=Tewari|first=A.|last2=Bartlett|first2=P.L.|year=2008|title=Optimistic linear programming gives logarithmic regret for irreducible MDPs|url=http://books.nips.cc/papers/files/nips20/NIPS2007_0673.pdf|journal=Advances in Neural Information Processing Systems|volume=20|citeseerx=10.1.1.69.5482}}</ref>, Ортнера<ref>{{Cite journal|last=Ortner|first=R.|year=2010|title=Online regret bounds for Markov decision processes with deterministic transitions|journal=Theoretical Computer Science|volume=411|issue=29|pages=2684–2695|doi=10.1016/j.tcs.2010.04.005}}</ref> Філіппі, Каппе та Гарів'є<ref>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–122115—122</ref>, а також Хонди та Такемури<ref>{{Cite journal|last=Honda|first=J.|last2=Takemura|first2=A.|year=2011|title=An asymptotically optimal policy for finite support models in the multi-armed bandit problem|journal=Machine Learning|volume=85|issue=3|pages=361–391|arxiv=0905.2776|doi=10.1007/s10994-011-5257-4}}</ref>.

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

* '''Епсилон-перша стратегія''': Після чистої фази розвідки йде фаза чистої експлуатації. Якщо <math>N</math> -&nbsp;— загальна кількість випробувань, то фаза розвідки складається з <math>\epsilon N</math> випробувань і фаза експлуатації -&nbsp;— <math>(1 - \epsilon) N</math> випробувань. Під час фази розвідки випадковим чином вибирається важіль (з рівною ймовірністю); на етапі експлуатації завжди вибирається найкращий важіль.

</ref>. Великі коливання оцінок вартості призводять до високого епсилону (велика розвідка, низька експлуатація); низькі коливання до низького епсилону (низька розвідка, висока експлуатація). Подальші поліпшення можуть бути досягнуті шляхом [[Softmax|вибору дій, зважених на [[Softmax|софтмаксі,]], у випадку дослідницьких дій (Tokic & Palm, 2011)<ref name="TokicPalm2011">

</ref>.

* '''Адаптивна епсилон-жадібна стратегія на основі байєсівських ансамблів (Epsilon-BMC)''': Адаптивна стратегія адаптації епсилону для посилення навчання, подібного до VBDE, з монотонними гарантіями збіжності. У цьому підході параметр епсилон розглядається як очікування постеріорного розподілу, який оцінює жадібного агента (який повністю довіряє отриманій винагороді) та агента, який навчається одноманітно (який не довіряє отриманій винагороді). Докладніше див. Гімельфарб та ін., 2019. <ref name="Gimelfarb2019">

* '''Контекстуальна-епсілон-жадібна стратегія''': Подібна до епсілон-жадібної стратегії, за винятком того, що значення <math>\epsilon</math> обчислюється з урахуванням ситуації при проходженні експерименту, що дозволяє алгоритму брати до уваги контекст. Він базується на динамічному балансуванні розвіки/експлуатації і може адаптивно збалансувати два аспекти, вирішуючи, яка ситуація є найбільш відповідною для розвідки чи експлуатації, що призводить до надзвичайно дослідницької поведінки, коли ситуація не є критичною, і дуже експлуататорської поведінки у критичній ситуації. <ref name="Bouneffouf2012">

== ДивисьДив. також ==

* {{Нп|Індекс Гіттінса|||Gittins index}}&nbsp;-— потужна, загальна стратегія аналізу бандитськихзадач про проблем.ББ

[[Категорія:Послідовні методи]]</nowiki>