![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/8/82/Las_Vegas_slot_machines.jpg/640px-Las_Vegas_slot_machines.jpg&w=640&q=50)
Багаторукий бандит
З Вікіпедії, безкоштовно encyclopedia
У теорії ймовірностей та машинному навчанні задача багаторукого бандита (яку іноді називають задачею K-[1] або N-рукого бандита[2]) — це задача розподілу обмеженої множини ресурсів між конкуруючими альтернативами таким чином, щоб максимізувати очікуваний виграш, коли властивості кожного варіанту відомі лише частково на момент ухвалення рішення, і можуть стати краще зрозумілими з плином часу або шляхом розподілу ресурсів для реалізації варіанту[3][4]. Це класична задача навчання з підкріпленням, яка є прикладом дилеми балансу між експлуатацією та розвідкою. Назва походить від уявного гравця на низці ігрових автоматів (їх часто називають «однорукими бандитами»), який має вирішити, на яких автоматах варто грати, скільки разів варто грати на кожному автоматі та в якому порядку слід грати, і чи продовжувати з поточним автоматом або спробувати інший[5]. Проблема багаторуких бандитів також підпадає під широку категорію стохастичного планування[en].
![Thumb image](http://upload.wikimedia.org/wikipedia/commons/thumb/8/82/Las_Vegas_slot_machines.jpg/640px-Las_Vegas_slot_machines.jpg)
У цій задачі кожен автомат забезпечує випадкову винагороду відповідно до розподілу ймовірностей, який властивий для цього автомату. Мета гравця — максимізувати суму винагород, яку він отримує відповідно у випадку задіяння обраної послідовності важелів[3][4]. Принципова проблема, з якою стикається гравець на кожному кроці, полягає в тому, що він має зробити вибір, між «експлуатацією» автомата, який має найвищий очікуваний прибуток, і «розвідкою», щоб отримати більше інформації про очікувані виграші інших автоматів. Питання компромісу між розвідкою та експлуатацією також виникає у машинному навчанні. На практиці багаторукі бандити використовувались для моделювання таких задач, як управління дослідницькими проектами у великій організації, як науковий фонд або фармацевтична компанія. У ранніх формулюваннях задачі гравець починає взаємодію без початкових знань про автомати.
Герберт Роббінс у 1952 році, усвідомлюючи важливість цієї задачі, побудував збіжні стратегії відбору сукупності в «деяких аспектах послідовного планування експериментів»[6]. Теорема про індекс Гіттінса, вперше опублікована Джоном Ч. Гіттінсом[en], дає оптимальну стратегію максимізації очікуваної винагороди з урахуванням коефіцієнта знецінювання[7].