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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Стратегії

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

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

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

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

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

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

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

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

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

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

Див. також

• Індекс Гіттінса — потужна, загальна стратегія аналізу задач про ББ
• Жадібний алгоритм
• Теорія пошуку
• Стохастичне планування