Loading AI tools
З Вікіпедії, вільної енциклопедії
У теорії ймовірностей та машинному навчанні задача багаторукого бандита (яку іноді називають задачею K-[1] або N-рукого бандита[2]) — це задача розподілу обмеженої множини ресурсів між конкуруючими альтернативами таким чином, щоб максимізувати очікуваний виграш, коли властивості кожного варіанту відомі лише частково на момент ухвалення рішення, і можуть стати краще зрозумілими з плином часу або шляхом розподілу ресурсів для реалізації варіанту[3][4]. Це класична задача навчання з підкріпленням, яка є прикладом дилеми балансу між експлуатацією та розвідкою. Назва походить від уявного гравця на низці ігрових автоматів (їх часто називають «однорукими бандитами»), який має вирішити, на яких автоматах варто грати, скільки разів варто грати на кожному автоматі та в якому порядку слід грати, і чи продовжувати з поточним автоматом або спробувати інший[5]. Проблема багаторуких бандитів також підпадає під широку категорію стохастичного планування[en].
У цій задачі кожен автомат забезпечує випадкову винагороду відповідно до розподілу ймовірностей, який властивий для цього автомату. Мета гравця — максимізувати суму винагород, яку він отримує відповідно у випадку задіяння обраної послідовності важелів[3][4]. Принципова проблема, з якою стикається гравець на кожному кроці, полягає в тому, що він має зробити вибір, між «експлуатацією» автомата, який має найвищий очікуваний прибуток, і «розвідкою», щоб отримати більше інформації про очікувані виграші інших автоматів. Питання компромісу між розвідкою та експлуатацією також виникає у машинному навчанні. На практиці багаторукі бандити використовувались для моделювання таких задач, як управління дослідницькими проектами у великій організації, як науковий фонд або фармацевтична компанія. У ранніх формулюваннях задачі гравець починає взаємодію без початкових знань про автомати.
Герберт Роббінс у 1952 році, усвідомлюючи важливість цієї задачі, побудував збіжні стратегії відбору сукупності в «деяких аспектах послідовного планування експериментів»[6]. Теорема про індекс Гіттінса, вперше опублікована Джоном Ч. Гіттінсом[en], дає оптимальну стратегію максимізації очікуваної винагороди з урахуванням коефіцієнта знецінювання[7].
Проблема багаторукого бандита моделює агента, який одночасно намагається здобути нові знання (що називається «розвідкою») та оптимізувати свої рішення на основі існуючих знань (називається «експлуатацією»). Агент намагається збалансувати ці конкуруючі завдання, щоб максимізувати загальну принесену ними цінність за розглянутий проміжок часу. Існує багато практичних застосувань моделі бандита, наприклад:
У цих практичних прикладах задача полягає у збалансуванні максимізації винагороди на основі вже набутих знань із спробами нових дій для подальшого збільшення знань. Ця дилема відома як компроміс між експлуатацією та дослідженням в машинному навчанні.
Модель також використовувалася для управління динамічним розподілом ресурсів для різних проектів, відповідаючи на питання, над яким проектом варто працювати, зважаючи на невизначеність щодо складності та вигідності кожної можливості[12].
Спочатку задача досліджувалась науковцями союзників у Другій світовій війні та виявилася настільки складною, що, за жартівливими словами Пітера Уіттла[en], пропонувалося скинути її над Німеччиною, щоб німецькі вчені також могли витрачати на неї свій час[13].
Варіант задачі, який набув широкого визнання у сучасному формулюванні, був запропонований Гербертом Роббінсом у 1952 році.
Багаторукого бандита (коротко: бандит або БРБ) можна розглядати як сукупність розподілів дійсних чисел , кожен розподіл пов'язаний з винагородами, які отримуються натисканням одного із важелів. Нехай будуть середніми значеннями, які пов'язані з цими розподілами винагород. Гравець ітеративно грає по одному важелю за раунд і отримує відповідну винагороду. Метою є максимізація суми зібраних винагород. Горизонтом називається кількість раундів, які залишилось зіграти. Задача про багаторуких бандитів формально еквівалентна процесу Маркова з одним станом. Смуток після раундів визначається як очікувана різниця між сумою винагороди, пов'язаною з оптимальною стратегією, та сумою отриманих винагород:
,
де — максимальне середнє значення винагороди, і — винагорода у раунді t.
Стратегія нульового смутку — це стратегія, середній смуток якої за раунд прямує до нуля з імовірністю 1, коли кількість зіграних раундів прямує до нескінченності[14]. Інтуїтивно зрозуміло, що стратегії нульового смутку гарантовано збігаються до (не обов'язково єдиної) оптимальної стратегії, якщо зіграно достатньо раундів.
Загальноприйнятим формулюванням є двійковий багаторукий бандит або багаторукий бандит Бернуллі, який видає винагороду одиниця з ймовірністю , а в протилежному випадку винагорода дорівнює нулю.
В іншому формулюванні задачі про багаторукого бандита кожна рука представляє незалежну машину Маркова. Кожного разу, коли грається певна рука, стан цієї машини переходить у новий стан, обраний відповідно до розподілу ймовірностей станів машини Маркова. Тобто, кожного разу винагорода залежить від поточного стану машини. Для узагальнення, яке називають «задачею неспокійного бандита», стани рук, які не обираються гравцем, також можуть еволюціонувати з часом[15]. Також розглядаються системи, в яких кількість варіантів (щодо того, яку руку зіграти) з часом збільшується[16].
Дослідники-інформатики вивчали багаторуких бандитів при найгірших припущеннях, отримуючи алгоритми, що дозволяють мінімізувати смуток як в кінцевому, так і в нескінченному (асимптотичному) часових горизонтах як у випадку стохастичного[1], так і у випадку нестохастичного[17] виграшу.
Основним проривом була побудова оптимальної генеральної сукупності стратегій або політик (які мають рівномірно максимальний коефіцієнт збіжності до сукупності з найвищим середнім значенням) у роботі, яка описана далі.
У статті «Асимптотично ефективні правила адаптивного розподілу» Лай і Роббінс[18] (наступні статті Роббінса та його колег відсилають до статі Роббінса 1952 року) побудували збіжний відбір стратегій, що мають найшвидший рівень збіжності (до генеральної сукупності з найвищим середнім значенням) у випадку, коли розподіли винагород є однопараметричним експоненціальним сімейством. Потім у роботі Катехакіса[en] та Роббінса[19] за спрощеної стратегії було надано доведення у випадку нормальних генеральних сукупностей з відомими дисперсіями. Подальше вагоме просування здійснили Бурнетас і Катехакіс у роботі «Оптимальні адаптивні політики для задачі послідовного розподілу»[20], в якій були побудовані стратегії на основі індексу з рівномірно максимальним коефіцієнтом збіжності за більш загальних умов, що включають випадок, коли розподіли результатів від кожної сукупності залежать від вектору невідомих параметрів. Бурнетас і Катехакіс (1996) також надали явне рішення для важливого випадку, коли розподіли результатів є довільними (тобто непараметричними) дискретними одновимірними розподілами.
Пізніше в «Оптимальній адаптивній політиці для Марковських процесів ухвалювання рішень»[21] Бурнетас і Катехакіс дослідили набагато більшу модель процесів ухвалювання рішень Маркова з частковою інформацією, коли закон переходу та/або очікувана винагорода за один період можуть залежати від невідомих параметрів. У цій роботі була побудована явна форма для класу адаптивних стратегій, які мають рівномірно максимальну збіжність для загальної очікуваної винагороди з кінцевим горизонтом, за необхідних припущень щодо скінченності простору дій та станів й незвідності правила переходу. Головною особливістю цих стратегій є те, що вибір дій у кожному стані та періоді часу базується на індексах, які є записом правої частини оцінки середньої винагороди у рівняннях оптимальності. Їх назвали оптимістичним підходом у роботах Теварі та Бартлетта[22], Ортнера[23] Філіппі, Каппе та Гарів'є[24], а також Хонди та Такемури[25].
Коли оптимальні рішення для задач про одноруких бандитів[26] використовуються для оцінки вибору, який роблять тварини, через активність нейронів у мигдалині та смугастому тілі кодується значення, яке виводиться з цих правил, і може використовуватися для декодування, коли тварини роблять вибір між дослідженням та експлуатацією. Більше того, оптимальні стратегії краще прогнозують поведінку тварин при виборі, ніж альтернативні стратегії (описані нижче). Це свідчить про те, що оптимальні рішення для задач багаторуких бандитів є біологічно правдоподібними, незважаючи на вимоги до обчислень[27].
Існує багато стратегій, які забезпечують наближене розв'язання ЗББ, і їх можна віднести до чотирьох широких категорій, які докладно описані нижче.
Напіврівномірні стратегії були найдавнішими (і найпростішими) стратегіями, які дають наближений розв'язок ЗББ. Всі ці стратегії мають спільну жадібну поведінку, коли найкращий важіль (на основі попередніх спостережень) завжди використовується, за винятком випадків, коли вживається (рівномірно) випадкова дія.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.