В чем проблема многоруких бандитов?

Название Multi-Armed Bandit (MAB) происходит из примера, когда игрок имеет возможность играть на игровых автоматах n, и каждый автомат предоставляет случайную награду из вероятности распределение, характерное для этой машины и неизвестное игроку.

Теперь, чтобы максимизировать свой заработок, он должен решить, на какой машине играть, сколько раз играть на каждой машине и в каком порядке играть на них. В большинстве реальных случаев игрок теряет деньги во время игры, отсюда и название бандиты, а игровые автоматы известны как руки.

Проблема многорукого бандита - это классическая проблема, которая моделирует агента (или планировщика, или центра), который хочет максимизировать свою общую награду, с помощью которой он одновременно желает получить новые знания («исследование») и оптимизировать свои решения на основе существующих знаний. («Эксплуатация»).

Разведка против эксплуатации

Дилемма исследования и эксплуатации возникает в сценарии неполной информации, когда есть параметр, который необходимо изучить для принятия общих решений. Эта дилемма легко изучается в обучении с подкреплением. Из приведенного выше примера в каждый период времени игрок должен делать выбор между следующим:

  1. Вытаскивание руки, которая принесла лучшую на данный момент награду, то есть эксплуатацию.
  2. Изучение другого оружия, которое потенциально может принести лучшую награду в будущем, например исследование.

Ссылаясь на приведенный выше пример, проблема MAB охватывает сценарий, в котором игрок сталкивается с компромиссом между исследованием, оптимистично вытягивая менее исследованные руки в поисках руки с лучшей наградой, и эксплуатацией, вытягивая руку, известную как лучшую, до текущий момент времени с точки зрения получения максимальной награды.

Многорукий бандит в основном делится на три части в зависимости от типа распределения вознаграждения, которое имеет оружие: Стохастический, Соревновательный и Марковский МАБ.

Существует множество различных вариантов в зависимости от наличия дополнительной информации (Контекстные бандиты), конечного количества оружия, доступного в каждый момент времени (Спящие бандиты), бесконечного количества оружия (Многорукие бандиты) и многих других.

Приложения

  1. Краудсорсинг. Краудсорсинг стал мощным средством, доступным для работодателей или заказчиков услуг, для своевременного и экономичного выполнения задач. Целью работодателя является максимальное количество выполненных задач. Доступные рабочие (или служащие, или фрилансеры) действуют в этом случае как оружие, обладая скрытыми качествами, неизвестными работодателю. Таким образом, проблему можно представить как проблему МАБ, когда работодатель может либо изучить руки, чтобы узнать их качества, либо выбрать лучшую руку, определенную до сих пор.
  2. Система рекомендаций по новостям: когда приходит новый пользователь, сайт должен выбрать новостную статью из набора статей, и сайт получает вознаграждение всякий раз, когда пользователь нажимает на статью. Поскольку цель сайта - максимизировать доход, он хочет показывать статьи, которые с наибольшей вероятностью получат клик. Проблема здесь в том, что мы не знаем о вероятности нажатия на статью, а это параметр, который мы хотим узнать. Мы ясно видим дилемму разведки и эксплуатации, возникающую в приведенном выше сценарии, и ее можно смоделировать как проблему MAB.
  3. Клинические испытания: в этом приложении доступны различные экспериментальные методы лечения. Специалист по планированию должен решить, какое лечение использовать, сводя к минимуму потери пациентов. Лечение носит экспериментальный характер, подразумевая, что возможности лечения необходимо изучить, проводя его на пациентах. Вышеупомянутая проблема может быть смоделирована как проблема МАБ с лечением как руками, и эффективность лечения должна быть изучена. Планировщик может либо исследовать руки, чтобы узнать ее процент успеха (эффективность) рук, либо выбрать использование руки с наибольшей вероятностью успеха на данный момент.

Другие применения MAB - адаптивная маршрутизация в сети, дизайн финансового портфеля, интеллектуальные сети и т. Д.