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

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

В теории вероятностей и обучении задача многорукого бандита (иногда называемая К- машинном или 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 ^{*}$ — максимальное среднее вознаграждение, $\mu ^{*}=\max _{k}\{\mu _{k}\}$, и ${\widehat {r}}_{t}$ это награда в раунде t .

Стратегия «нулевого сожаления» — это стратегия, среднее количество сожалений в которой за раунд $\rho /T$ стремится к нулю с вероятностью 1, когда количество сыгранных раундов стремится к бесконечности. Интуитивно понятно, что стратегии «нулевого сожаления» гарантированно приведут к (не обязательно уникальной) оптимальной стратегии, если сыграно достаточное количество раундов.

Вариации

Распространенной формулировкой является бинарный многорукий бандит или многорукий бандит Бернулли, который с вероятностью выдает награду в размере одного $p$, а в противном случае награда равна нулю.

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

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

Лучшая идентификация руки

Важным вариантом классической задачи минимизации сожалений у многоруких бандитов является задача Best Arm Identification (BAI). , также известный как чистое исследование . Эта проблема имеет решающее значение в различных приложениях, включая клинические испытания, адаптивную маршрутизацию, системы рекомендаций и A/B-тестирование.

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

1. Правило выборки : $(a_{t})_{t\geq 1}$ представляет собой последовательность действий на каждом временном шаге
2. Правило остановки : $\tau$ это (случайное) время остановки, которое подсказывает, когда прекратить сбор образцов.
3. Правило принятия решения : ${\hat {a}}_{\tau }$ это предположение о лучшей руке, основанное на данных, собранных на данный момент $\tau$

В BAI есть две преобладающие настройки:

Фиксированная настройка уверенности: задан уровень уверенности. $\delta \in (0,1)$, цель состоит в том, чтобы определить руку с самой высокой ожидаемой наградой. $a^{\star }\in \arg \max _{k}\mu _{k}$ с наименьшим количеством попыток и с вероятностью ошибки $\mathbb {P} ({\hat {a}}_{\tau }\neq a^{\star })\leq \delta$.

Настройка фиксированного бюджета: с учетом временного горизонта. $T\geq 1$, цель состоит в том, чтобы определить руку с самой высокой ожидаемой наградой. $a^{\star }\in \arg \max _{k}\mu _{k}$ минимизация вероятности ошибки $\delta$.

Бандитские стратегии

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

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

Дополнительная информация: индекс Гиттинса.

В статье «Асимптотически эффективные правила адаптивного распределения» Лай и Роббинс (следуя статьям Роббинса и его коллег, восходящих к Роббинсу в 1952 году) построил политику конвергентного отбора населения, которая обладает самой быстрой скоростью сходимости (к совокупности с самым высоким средним значением) для случая, когда распределения вознаграждения населения являются одним -параметрическое экспоненциальное семейство. Затем в Катехакисе и Роббинсе упрощения политики и основное доказательство были даны для случая нормальных популяций с известными дисперсиями. Следующий заметный прогресс был достигнут Бурнетасом и Катехакисом в статье «Оптимальные адаптивные политики для задач последовательного распределения». где были построены политики на основе индексов с равномерно максимальной скоростью сходимости при более общих условиях, которые включают случай, когда распределения результатов для каждой совокупности зависят от вектора неизвестных параметров. Бурнетас и Катехакис (1996) также предоставили явное решение важного случая, когда распределения результатов следуют произвольным (т.е. непараметрическим) дискретным одномерным распределениям.

Позже в разделе «Оптимальные адаптивные политики для марковских процессов принятия решений». Бурнетас и Катехакис изучили гораздо более широкую модель марковских процессов принятия решений в условиях частичной информации, где закон перехода и/или ожидаемые вознаграждения за один период могут зависеть от неизвестных параметров. В этой работе авторы построили явную форму для класса адаптивных политик со свойствами равномерно максимальной скорости сходимости для общего ожидаемого вознаграждения на конечном горизонте при достаточных предположениях о конечных пространствах состояний-действий и неприводимости закона перехода. Основная особенность этой политики заключается в том, что выбор действий в каждом состоянии и периоде времени основан на индексах, которые представляют собой инфляции правой части расчетного уравнения оптимальности среднего вознаграждения. Эти инфляции недавно были названы оптимистическим подходом в работе Тевари и Бартлетта. Ортнер Филиппи, Каппе и Гаривье, и Хонда и Такемура.

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

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

Примерные решения

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

Полуравномерные стратегии

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

• Эпсилон-жадная стратегия : Лучший рычаг выбирается по пропорции $1-\epsilon$ испытаний, а рычаг выбирается случайным образом (с равномерной вероятностью) для доли $\epsilon$. Типичное значение параметра может быть $\epsilon =0.1$, но это может сильно варьироваться в зависимости от обстоятельств и пристрастий.
• Эпсилон-первая стратегия : За фазой чистой разведки следует фаза чистой эксплуатации. Для $N$ Всего испытаний, этап разведки занимает $\epsilon N$ испытания и этап эксплуатации $(1-\epsilon )N$ испытания. На этапе исследования рычаг выбирается случайным образом (с равномерной вероятностью); на этапе эксплуатации всегда выбирается лучший рычаг.
• Стратегия уменьшения Эпсилона : Аналогично эпсилон-жадной стратегии, за исключением того, что значение $\epsilon$ уменьшается по мере продвижения эксперимента, что приводит к очень исследовательскому поведению в начале и к очень эксплуататорскому поведению в конце.
• Адаптивная эпсилон-жадная стратегия, основанная на разнице значений (VDBE) : аналогична стратегии уменьшения эпсилона, за исключением того, что эпсилон уменьшается на основе прогресса обучения, а не ручной настройки (Tokic, 2010). Высокие колебания оценок стоимости приводят к высокому эпсилону (высокая разведка, низкая эксплуатация); низкие колебания до низкого эпсилона (низкая разведка, высокая эксплуатация). Дальнейших улучшений можно достичь за счет выбора действия с softmax -взвешенным значением в случае исследовательских действий (Tokic & Palm, 2011).
• Адаптивная эпсилон-жадная стратегия, основанная на байесовских ансамблях (Epsilon-BMC) : адаптивная эпсилон-жадная стратегия для обучения с подкреплением, аналогичная VBDE, с гарантиями монотонной сходимости. В этой структуре параметр эпсилон рассматривается как ожидание апостериорного распределения, взвешивающего жадного агента (который полностью доверяет полученному вознаграждению) и однородного обучающего агента (который не доверяет полученному вознаграждению). Этот апостериор аппроксимируется с использованием подходящего бета-распределения в предположении нормальности наблюдаемых вознаграждений. Чтобы устранить возможный риск слишком быстрого уменьшения эпсилона, неопределенность в дисперсии полученного вознаграждения также моделируется и обновляется с использованием модели нормальной гаммы. (Гимельфарб и др., 2019).

Стратегии сопоставления вероятностей

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

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

Ценовые стратегии

Стратегии ценообразования устанавливают цену для каждого рычага. Например, как показано на примере алгоритма ПОКЕР: цена может представлять собой сумму ожидаемого вознаграждения плюс оценку дополнительных будущих вознаграждений, которые можно получить благодаря дополнительным знаниям. Рычаг самой высокой цены всегда нажат.

Контекстный бандит

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

Примерные решения для контекстного бандита

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

Онлайн линейные бандиты

• LinUCB (Upper Confidence Bound) Алгоритм : авторы предполагают линейную зависимость между ожидаемым вознаграждением за действие и его контекстом и моделируют пространство представления с помощью набора линейных предикторов.
• Алгоритм LinRel (линейное ассоциативное обучение с подкреплением) : похож на LinUCB, но использует разложение по сингулярным значениям , а не регрессию Риджа . для получения оценки достоверности

Онлайн нелинейные бандиты

• Алгоритм UCBogram : Нелинейные функции вознаграждения оцениваются с использованием кусочно-постоянного средства оценки, называемого регрессограммой в непараметрической регрессии . Затем UCB применяется к каждому постоянному куску. Последовательные уточнения разделения контекстного пространства планируются или выбираются адаптивно.
• Обобщенные линейные алгоритмы . Распределение вознаграждения следует обобщенной линейной модели, расширенной для линейных бандитов.
• Алгоритм KernelUCB : нелинейная версия с ядром LineUCB, с эффективной реализацией и анализом за конечное время.
• Алгоритм Bandit Forest : случайный лес строится и анализируется относительно построенного случайного леса с учетом совместного распределения контекстов и вознаграждений.
• Алгоритм на основе Oracle : Алгоритм сводит проблему контекстуального бандита к серии контролируемых задач обучения и не полагается на типичное предположение о реализуемости функции вознаграждения.

Сдержанный контекстный бандит

На практике обычно существует стоимость, связанная с ресурсом, потребляемым каждым действием, а общая стоимость ограничена бюджетом во многих приложениях, таких как краудсорсинг и клинические испытания. Ограниченный контекстный бандит (CCB) — это такая модель, которая учитывает как временные, так и бюджетные ограничения в условиях многорукого бандита. А. Баданидиюру и др. впервые изучил контекстных бандитов с ограниченным бюджетом, также называемых «находчивыми контекстными бандитами», и показал, что $O({\sqrt {T}})$ сожаление достижимо. Однако их работа сосредоточена на конечном наборе политик, а алгоритм вычислительно неэффективен.

Структура UCB-ALP для ограниченных контекстных бандитов

Простой алгоритм с логарифмическим сожалением предлагается в:

• Алгоритм UCB-ALP : Структура UCB-ALP показана на рисунке справа. UCB-ALP — это простой алгоритм, который сочетает в себе метод UCB с алгоритмом адаптивного линейного программирования (ALP) и может быть легко внедрен в практические системы. Это первая работа, показывающая, как добиться логарифмического сожаления у ограниченных контекстуальных бандитов. Хотя посвящен частному случаю с единственным бюджетным ограничением и фиксированной стоимостью, результаты проливают свет на разработку и анализ алгоритмов для более общих задач CCB.

Враждебный бандит

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

Пример: повторяющаяся дилемма заключенного.

Примером враждебных бандитов, который часто рассматривают, является повторяющаяся дилемма заключенного . В этом примере у каждого противника есть две руки, которые нужно тянуть. Они могут либо Отрицать, либо Сознаться. Стандартные алгоритмы стохастического бандита не очень хорошо работают с этими итерациями. Например, если противник сотрудничает в первых 100 раундах, отказывается в следующих 200, затем сотрудничает в следующих 300 и т. д., тогда такие алгоритмы, как UCB, не смогут очень быстро реагировать на эти изменения. Это происходит потому, что после определенного момента неоптимальные вооружения редко используются, чтобы ограничить разведку и сосредоточиться на эксплуатации. Когда среда меняется, алгоритм не может адаптироваться или даже не обнаруживает изменений.

Примерные решения

Опыт 3

EXP3 — популярный алгоритм для враждебных многоруких бандитов, предложенный и проанализированный в этой ситуации Auer et al. [2002б]. В последнее время возрос интерес к эффективности этого алгоритма в стохастической ситуации из-за его новых приложений к стохастическим многоруким бандитам с дополнительной информацией [Seldin et al., 2011] и к многоруким бандитам в смешанной стохастической ситуации. состязательный режим [Bubeck and Slivkins, 2012]. В статье представлены эмпирическая оценка и улучшенный анализ производительности алгоритма EXP3 в стохастической среде, а также модификация алгоритма EXP3, способная достигать «логарифмического» сожаления в стохастической среде.

Алгоритм

 Parameters: Real $\gamma \in (0,1]$
 
 Initialisation: $\omega _{i}(1)=1$ for $i=1,...,K$
 
 For each t = 1, 2, ..., T
  1. Set $p_{i}(t)=(1-\gamma ){\frac {\omega _{i}(t)}{\sum _{j=1}^{K}\omega _{j}(t)}}+{\frac {\gamma }{K}}$       $i=1,...,K$
  2. Draw $i_{t}$ randomly according to the probabilities $p_{1}(t),...,p_{K}(t)$
  3. Receive reward $x_{i_{t}}(t)\in [0,1]$
  4. For $j=1,...,K$ set:
      ${\hat {x}}_{j}(t)={\begin{cases}x_{j}(t)/p_{j}(t)&{\text{if }}j=i_{t}\\0,&{\text{otherwise}}\end{cases}}$
 
      $\omega _{j}(t+1)=\omega _{j}(t)\exp(\gamma {\hat {x}}_{j}(t)/K)$

Объяснение

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

Анализ сожалений

(Внешнее) сожаление алгоритма Exp3 не более чем $O({\sqrt {KTlog(K)}})$

Следуйте алгоритму возмущенного лидера (FPL).

Алгоритм

 Parameters: Real $\eta$
 
 Initialisation: $\forall i:R_{i}(1)=0$
 
 For each t = 1,2,...,T
  1. For each arm generate a random noise from an exponential distribution $\forall i:Z_{i}(t)\sim Exp(\eta )$
  2. Pull arm $I(t)$: $I(t)=arg\max _{i}\{R_{i}(t)+Z_{i}(t)\}$
     Add noise to each arm and pull the one with the highest value
  3. Update value: $R_{I(t)}(t+1)=R_{I(t)}(t)+x_{I(t)}(t)$
     The rest remains the same

Объяснение

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

Exp3 против FPL

Опыт 3	ФПЛ
Сохраняет вес для каждой руки для расчета вероятности вытягивания.	Не нужно знать вероятность вытягивания на руку
Имеет эффективные теоретические гарантии	Стандартный FPL не имеет хороших теоретических гарантий.
Может быть вычислительно дорогостоящим (расчет экспоненциальных членов)	В вычислительном отношении довольно эффективен

Бандит с бесконечными руками

В исходной спецификации и в приведенных выше вариантах задача о бандитах задается дискретным и конечным числом рук, часто обозначаемым переменной $K$. В случае с бесконечным вооружением, предложенном Агравалом (1995), «руки» являются непрерывной переменной в $K$ размеры.

Нестационарный бандит

Эта концепция относится к проблеме многорукого бандита в нестационарной обстановке (т. е. при наличии дрейфа концепций ). В нестационарной ситуации предполагается, что ожидаемое вознаграждение за руку $k$ может меняться на каждом временном шаге $t\in {\mathcal {T}}$: $\mu _{t-1}^{k}\neq \mu _{t}^{k}$. Таким образом, $\mu _{t}^{k}$ больше не представляет всю последовательность ожидаемых (стационарных) вознаграждений за руку $k$. Вместо, $\mu ^{k}$ обозначает последовательность ожидаемых наград для руки $k$, определяемый как $\mu ^{k}=\{\mu _{t}^{k}\}_{t=1}^{T}$.

Динамический оракул представляет собой оптимальную политику для сравнения с другими политиками в нестационарной среде. Динамический оракул оптимизирует ожидаемое вознаграждение на каждом этапе. $t\in {\mathcal {T}}$ всегда выбирая лучшую руку с ожидаемой наградой в размере $\mu _{t}^{*}$. Таким образом, совокупное ожидаемое вознаграждение ${\mathcal {D}}(T)$ для динамического оракула на последнем временном шаге $T$ определяется как:

${\mathcal {D}}(T)=\sum _{t=1}^{T}{\mu _{t}^{*}}$

Отсюда и сожаление $\rho ^{\pi }(T)$ для политики $\pi$ рассчитывается как разница между ${\mathcal {D}}(T)$ и совокупное ожидаемое вознаграждение на этапе $T$ для политики $\pi$:

$\rho ^{\pi }(T)=\sum _{t=1}^{T}{\mu _{t}^{*}}-\mathbb {E} _{\pi }^{\mu }\left[\sum _{t=1}^{T}{r_{t}}\right]={\mathcal {D}}(T)-\mathbb {E} _{\pi }^{\mu }\left[\sum _{t=1}^{T}{r_{t}}\right]$

Гаривье и Мулин получили некоторые из первых результатов в отношении задач о бандитах, в которых основная модель может меняться во время игры. Для решения этого случая был представлен ряд алгоритмов, в том числе Discounted UCB. и UCB с раздвижным окном. Аналогичным подходом, основанным на алгоритме выборки Томпсона, является выборка Томпсона со скользящим окном со скидкой (f-dsw TS). предложенный Кавенаги и др. Алгоритм f-dsw TS использует коэффициент дисконтирования в истории вознаграждений и скользящее окно, связанное с рукой, чтобы противопоставить дрейф концепции в нестационарных средах. Другая работа Буртини и др. представляет метод взвешенной выборки Томпсона по методу наименьших квадратов (WLS-TS), который оказывается полезным как в известных, так и в неизвестных нестационарных случаях.

Другие варианты

В последние годы было предложено множество вариантов проблемы.

Дуэльный бандит

Вариант дуэльного бандита был предложен Юэ и др. (2012) смоделировать компромисс между разведкой и эксплуатацией для получения относительной обратной связи. В этом варианте игроку разрешается нажать на два рычага одновременно, но он получает только двоичную обратную связь, сообщающую, какой рычаг принес наилучшую награду. Сложность этой проблемы связана с тем, что игрок не имеет возможности непосредственно наблюдать за вознаграждением за свои действия. Самыми ранними алгоритмами решения этой проблемы являются InterleaveFiltering. Победи среднее. Относительная обратная связь сражающихся бандитов также может привести к парадоксам голосования . Решение состоит в том, чтобы взять победителя Кондорсе . за образец

Совсем недавно исследователи обобщили алгоритмы от традиционных MAB до дуэльных бандитов: относительные верхние доверительные границы (RUCB), Относительное экспоненциальное взвешивание (REX3), Доверительные границы Коупленда (CCB), Относительное минимальное эмпирическое расхождение (RMED), и двойная выборка Томпсона (DTS).

Совместный бандит

Подходы с использованием нескольких бандитов, которые сотрудничают и делятся знаниями, чтобы лучше оптимизировать свою работу, начались в 2013 году с «Банды бандитов». алгоритм, основанный на графе сходства между различными бандитскими задачами для обмена знаниями. Необходимость в графе подобия была устранена в 2014 году благодаря работе над алгоритмом CLUB. После этой работы несколько других исследователей создали алгоритмы для одновременного изучения нескольких моделей с помощью бандитской обратной связи. Например, COFIBA была представлена ​​Ли, Карацоглу и Джентиле (SIGIR 2016), где классическая совместная фильтрация и методы фильтрации на основе контента пытаются изучить статическую модель рекомендаций с учетом обучающих данных.

Комбинаторный бандит

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

См. также

• Индекс Гиттинса – мощная общая стратегия анализа бандитских проблем.
• Жадный алгоритм
• Оптимальная остановка
• Теория поиска
• Стохастическое планирование

Дальнейшее чтение

• Гуха, С.; Мунагала, К.; Ши, П. (2010), «Алгоритмы аппроксимации проблем беспокойных бандитов», Журнал ACM , 58 : 1–50, arXiv : 0711.3861 , doi : 10.1145/1870103.1870106 , S2CID   1654066
• Даяник, С.; Пауэлл, В.; Ямазаки, К. (2008), «Индексная политика для проблем дисконтированных бандитов с ограничениями доступности», Advances in Applied Probability , 40 (2): 377–400, doi : 10.1239/aap/1214950209 .
• Пауэлл, Уоррен Б. (2007), «Глава 10», Приблизительное динамическое программирование: решение проклятий размерности , Нью-Йорк: Джон Уайли и сыновья, ISBN  978-0-470-17155-4 .
• Роббинс, Х. (1952), «Некоторые аспекты последовательного планирования экспериментов», Бюллетень Американского математического общества , 58 (5): 527–535, doi : 10.1090/S0002-9904-1952-09620-8 .
• Саттон, Ричард; Барто, Эндрю (1998), Обучение с подкреплением , MIT Press, ISBN  978-0-262-19398-6 , заархивировано из оригинала 11 декабря 2013 г.

• Аллесиардо, Робин (2014), «Комитет по нейронным сетям для решения проблемы контекстуального бандита», Нейронная обработка информации – 21-я международная конференция, ICONIP 2014, Малайзия, 3–06 ноября 2014 г., Материалы , конспекты лекций по информатике, том. 8834, Springer, стр. 374–381, arXiv : 1409.8191 , doi : 10.1007/978-3-319-12637-1_47 , ISBN  978-3-319-12636-4 , S2CID   14155718 .

• Вебер, Ричард (1992), «Об индексе Гиттинса для многоруких бандитов», Annals of Applied Probability , 2 (4): 1024–1033, doi : 10.1214/aoap/1177005588 , JSTOR   2959678 .
• Катехакис, М .; К. Дерман (1986), «Вычисление оптимальных правил последовательного распределения в клинических испытаниях», Адаптивные статистические процедуры и смежные темы , Конспект лекций Института математической статистики - Серия монографий, том. 8, стр. 29–39, doi : 10.1214/lnms/1215540286 , ISBN.  978-0-940600-09-6 , JSTOR   4355518 .
• Катехакис, Майкл Н .; Вейнотт-младший, Артур Ф. (1987), «Проблема многорукого бандита: декомпозиция и вычисление», Mathematics of Operations Research , 12 (2): 262–268, doi : 10.1287/moor.12.2.262 , JSTOR   3689689 , S2CID   656323

Внешние ссылки

• MABWiser , реализация бандитских стратегий с открытым исходным кодом на Python, которая поддерживает контекстно-свободные, параметрические и непараметрические контекстные политики со встроенными возможностями распараллеливания и моделирования.
• PyMaBandits , с открытым исходным кодом на Python и Matlab. реализация бандитских стратегий
• Контекстный , с открытым исходным кодом пакет R упрощающий моделирование и оценку как контекстно-свободных, так и контекстно-зависимых политик Multi-Armed Bandit.
• bandit.sourceforge.net Проект Bandit , реализация бандитских стратегий с открытым исходным кодом.
• Banditlib , с открытым исходным кодом на C++. реализация бандитских стратегий
• Лесли Пак Кельблинг и Майкл Л. Литтман (1996). Эксплуатация против разведки: случай единого государства .
• Учебное пособие: Введение в бандитов: алгоритмы и теория. Часть1 . Часть2 .
• Проблема ресторана Фейнмана — классический пример (с известным ответом) компромисса между эксплуатацией и разведкой.
• Бандитские алгоритмы против AB-тестирования .
• С. Бубек и Н. Чеза-Бьянки. Обзор бандитов .
• Обзор контекстных многоруких бандитов , опрос/учебник для контекстных бандитов.
• Сообщение в блоге о стратегиях многоруких бандитов с кодом Python .
• Анимированные интерактивные графики, иллюстрирующие стратегии исследования/эксплуатации Эпсилон-жадной выборки, выборки Томпсона и верхней доверительной границы.