Вступ до Задачі

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

Походження проблеми

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

Проблема

Проблема багаторукого бандита (MAB) відображає складність балансування між дослідженням та експлуатацією:

• Дослідження: випробування різних важелів для отримання інформації про їхні виплати;
• Експлуатація: вибір важеля, який наразі здається найкращим, для максимізації негайної винагороди.

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

Застосування в реальному світі

Хоча спочатку задача MAB була сформульована у сфері азартних ігор, вона зустрічається у багатьох галузях:

• Онлайн-реклама: вибір найкращої реклами для показу на основі взаємодії користувача;
• Клінічні випробування: тестування декількох методів лікування для визначення найефективнішого;
• Системи рекомендацій: надання користувачам найбільш релевантного контенту.