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

Проблема ресурсов в машинном обучении

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

В теории вероятностей и машинном обучении задача многорукого бандита (иногда называемая задачей K- [ ^1] или N -рукого бандита ^[2] ) — это задача, в которой лицо, принимающее решение, итеративно выбирает один из нескольких фиксированных вариантов (т. е. руки или действия), когда свойства каждого выбора известны лишь частично на момент распределения и могут стать более понятными с течением времени. Фундаментальным аспектом задач бандита является то, что выбор руки не влияет на свойства руки или других рук. ^[3]

Примеры задачи многорукого бандита включают задачу итеративного распределения фиксированного, ограниченного набора ресурсов между конкурирующими (альтернативными) вариантами выбора таким образом, чтобы свести к минимуму сожаление . [ ^{4] [5]} Известная альтернативная установка для задачи многорукого бандита включает задачу «идентификации лучшей руки», где цель состоит в том, чтобы определить лучший выбор к концу конечного числа раундов. ^[6]

Задача о многоруком бандите — это классическая задача обучения с подкреплением , которая иллюстрирует дилемму компромисса между исследованием и эксплуатацией . В отличие от общего RL, выбранные действия в задачах о бандитах не влияют на распределение вознаграждения по рукам. Название происходит от представления игрока за рядом игровых автоматов (иногда называемых «однорукими бандитами»), который должен решить, на каких автоматах играть, сколько раз играть на каждом автомате и в каком порядке играть, и продолжать ли играть на текущем автомате или попробовать другой автомат. ^[7] Задача о многоруком бандите также попадает в широкую категорию стохастического планирования .

В этой задаче каждая машина выдает случайное вознаграждение из распределения вероятностей , специфичного для этой машины, которое заранее неизвестно . Цель игрока — максимизировать сумму вознаграждений, полученных посредством последовательности нажатий рычагов. ^{[4] [5]} Решающий компромисс, с которым сталкивается игрок в каждом испытании, заключается в «эксплуатации» машины, которая имеет самый высокий ожидаемый выигрыш, и «исследовании», чтобы получить больше информации об ожидаемых выигрышах других машин. Компромисс между исследованием и эксплуатацией также встречается в машинном обучении . На практике многорукие бандиты использовались для моделирования таких проблем, как управление исследовательскими проектами в крупной организации, такой как научный фонд или фармацевтическая компания . ^{[4] [5]} В ранних версиях задачи игрок начинает без каких-либо начальных знаний о машинах.

Герберт Роббинс в 1952 году, осознавая важность проблемы, сконструировал конвергентные стратегии отбора популяции в «некоторых аспектах последовательного проектирования экспериментов». ^[8] Теорема, индекс Гиттинса , впервые опубликованная Джоном К. Гиттинсом , дает оптимальную политику для максимизации ожидаемого дисконтированного вознаграждения. ^[9]

Эмпирическая мотивация

Как следует распределить бюджет между этими исследовательскими отделами, чтобы добиться максимальных результатов?

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

• клинические испытания, изучающие эффекты различных экспериментальных методов лечения при минимизации потерь пациентов, ^{[4] [5] [10] [11]}
• адаптивная маршрутизация для минимизации задержек в сети,
• дизайн финансового портфеля ^{[12] [13]}

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

Модель также использовалась для управления динамическим распределением ресурсов по различным проектам, отвечая на вопрос, над каким проектом работать, учитывая неопределенность относительно сложности и выгоды каждой возможности. ^[14]

Первоначально рассматриваемая учеными-союзниками во время Второй мировой войны , она оказалась настолько неразрешимой, что, по словам Питера Уиттла , было предложено отказаться от решения этой проблемы в отношении Германии , чтобы немецкие ученые также могли потратить на нее свое время. ^[15]

Версия проблемы, которую сейчас обычно анализируют, была сформулирована Гербертом Роббинсом в 1952 году.

Модель многорукого бандита

Многорукого бандита (сокращенно: бандит или МАБ) можно рассматривать как набор реальных распределений , каждое из которых связано с наградами, предоставляемыми одним из рычагов. Пусть будут средними значениями, связанными с этими распределениями наград. Игрок итеративно играет одним рычагом за раунд и наблюдает за связанной наградой. Цель состоит в том, чтобы максимизировать сумму собранных наград. Горизонт — это количество раундов, которые осталось сыграть. Задача бандита формально эквивалентна процессу принятия решений Маркова с одним состоянием . Сожаление после раундов определяется как ожидаемая разница между суммой награды, связанной с оптимальной стратегией, и суммой собранных наград: ${\displaystyle B=\{R_{1},\dots ,R_{K}\}}$ ${\displaystyle K\in \mathbb {N} ^{+}}$ ${\displaystyle \mu _{1},\dots ,\mu _{K}}$ ${\displaystyle H}$ ${\displaystyle \rho }$ ${\displaystyle T}$

${\displaystyle \rho =T\mu ^{*}-\sum _{t=1}^{T}{\widehat {r}}_{t}}$,

где — максимальное среднее вознаграждение , а — вознаграждение в раунде t . ${\displaystyle \mu ^{*}}$ ${\displaystyle \mu ^{*}=\max _{k}\{\mu _{k}\}}$ ${\displaystyle {\widehat {r}}_{t}}$

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

Вариации

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

Другая формулировка многорукого бандита подразумевает, что каждая рука представляет собой независимую марковскую машину. Каждый раз, когда разыгрывается конкретная рука, состояние этой машины переходит в новое, выбранное в соответствии с вероятностями эволюции марковских состояний. Существует вознаграждение, зависящее от текущего состояния машины. В обобщении, называемом «проблемой беспокойного бандита», состояния неразыгранных рук также могут со временем меняться. ^[17] Также обсуждались системы, в которых количество выборов (какой рукой играть) со временем увеличивается. ^[18]

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

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

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

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

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

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

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

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

Например, используя правило принятия решения , мы могли бы использовать , где находится машина № 1 (вы можете использовать другую переменную соответственно), а — это сумма за каждую попытку потянуть рычаг, где , определить как сумму каждой попытки , (...) по мере необходимости, и оттуда вы можете получить отношение, сумму или среднее значение как количественную вероятность и выборку вашей формулировки для каждого слота. ${\displaystyle m_{1}}$ ${\displaystyle m}$ ${\displaystyle 1}$ ${\displaystyle \int \sum m_{1},m_{2},(...)=M}$ ${\displaystyle M}$ ${\displaystyle m_{1}+m_{2}}$

Вы также можете сделать где равно каждому уникальному слоту машины, это сумма каждый раз, когда рычаг срабатывает, это сумма , будет общей доступной суммой в вашем распоряжении, является относительной к где уменьшается как сумма каждого выигрыша или проигрыша от (скажем, у вас есть 100$, которые определяются как и будут выигрыш равен проигрышу, оттуда вы получаете свои результаты либо положительные, либо отрицательные, чтобы добавить для с вашим собственным конкретным правилом) и как максимум, который вы готовы потратить. Можно выразить эту конструкцию, используя комбинацию нескольких алгебраических формул, как упоминалось выше, где вы можете ограничить с помощью для или во времени и так далее. ${\displaystyle \int \sum _{k\propto _{i}}^{N}-(n_{j})}$ ${\displaystyle m1+m2}$ ${\displaystyle x,y}$ ${\displaystyle N}$ ${\displaystyle (m1_{x},_{y})+(m2_{x},_{y})(...)}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle N}$ ${\displaystyle N=n(n_{a},b),(n1_{a},b),(n2_{a},b)}$ ${\displaystyle n_{j}}$ ${\displaystyle a,b}$ ${\displaystyle n}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle N}$ ${\displaystyle i}$ ${\displaystyle T}$

Стратегии бандитов

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

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

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

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

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

Когда оптимальные решения задач многорукого бандита ^[31] используются для получения значения выбора животных, активность нейронов в миндалевидном теле и вентральном стриатуме кодирует значения, полученные из этих политик, и может использоваться для декодирования, когда животные делают исследовательский выбор против эксплуататорского выбора. Более того, оптимальные политики лучше предсказывают поведение выбора животных, чем альтернативные стратегии (описанные ниже). Это говорит о том, что оптимальные решения задач многорукого бандита биологически правдоподобны, несмотря на то, что они требуют вычислительных затрат. ^[32]

Приблизительные решения

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

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

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

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

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

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

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

Стратегии ценообразования

Стратегии ценообразования устанавливают цену для каждого рычага. Например, как показано в алгоритме POKER ^[16], цена может быть суммой ожидаемого вознаграждения плюс оценка дополнительных будущих вознаграждений, которые будут получены благодаря дополнительным знаниям. Рычаг с самой высокой ценой всегда тянется.

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

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

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

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

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

• Алгоритм LinUCB (верхняя граница достоверности) : авторы предполагают линейную зависимость между ожидаемым вознаграждением за действие и его контекстом и моделируют пространство представления с использованием набора линейных предикторов. ^{[40] [41]}
• Алгоритм LinRel (линейное ассоциативное обучение с подкреплением) : похож на LinUCB, но использует сингулярное разложение вместо гребневой регрессии для получения оценки достоверности. ^{[42] [43]}

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

• Алгоритм UCBogram : Нелинейные функции вознаграждения оцениваются с использованием кусочно-постоянной оценки, называемой регрессограммой в непараметрической регрессии . Затем UCB применяется к каждой постоянной части. Последовательные уточнения разбиения контекстного пространства планируются или выбираются адаптивно. ^{[44] [45] [46]}
• Обобщенные линейные алгоритмы : распределение вознаграждения следует обобщенной линейной модели, расширенной для линейных бандитов. ^{[47] [48] [49] [50]}
• Алгоритм KernelUCB : нелинейная версия linearUCB с ядром, с эффективной реализацией и анализом за конечное время. ^[51]
• Алгоритм «Бандитский лес» : случайный лес строится и анализируется относительно построенного случайного леса, зная совместное распределение контекстов и вознаграждений. ^[52]
• Алгоритм на основе Oracle : алгоритм сводит контекстную задачу о бандите к серии задач контролируемого обучения и не полагается на типичное предположение о реализуемости функции вознаграждения. ^[53]

Ограниченный контекстуальный бандит

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

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

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

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

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

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

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

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

Приблизительные решения

Эксп3^[57]

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

Алгоритм

 Параметры: Реальные ${\displaystyle \gamma \in (0,1]}$  Инициализация: для ${\displaystyle \omega _{i}(1)=1}$ ${\displaystyle i=1,...,K}$  Для каждого t = 1, 2, ..., T 1. Набор 2. Вытягиваем случайным образом в соответствии с вероятностями 3. Получаем награду 4. За набор:      ${\displaystyle p_{i}(t)=(1-\gamma ){\frac {\omega _{i}(t)}{\sum _{j=1}^{K}\omega _{j}(t)}}+{\frac {\gamma }{K}}}$        ${\displaystyle i=1,...,K}$ ${\displaystyle i_{t}}$ ${\displaystyle p_{1}(t),...,p_{K}(t)}$ ${\displaystyle x_{i_{t}}(t)\in [0,1]}$ ${\displaystyle j=1,...,K}$ ${\displaystyle {\hat {x}}_{j}(t)={\begin{cases}x_{j}(t)/p_{j}(t)&{\text{if }}j=i_{t}\\0,&{\text{otherwise}}\end{cases}}}$       ${\displaystyle \omega _{j}(t+1)=\omega _{j}(t)\exp(\gamma {\hat {x}}_{j}(t)/K)}$

Объяснение

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

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

(Внешнее) сожаление алгоритма Exp3 составляет максимум ${\displaystyle O({\sqrt {KTlog(K)}})}$

Алгоритм следования возмущенному лидеру (FPL)

Алгоритм

 Параметры: Реальные ${\displaystyle \eta }$  Инициализация:  ${\displaystyle \forall i:R_{i}(1)=0}$  Для каждого t = 1,2,...,T 1. Для каждого плеча сгенерировать случайный шум из экспоненциального распределения 2. Вытянуть плечо : ${\displaystyle \forall i:Z_{i}(t)\sim Exp(\eta )}$ ${\displaystyle I(t)}$ ${\displaystyle I(t)=arg\max _{i}\{R_{i}(t)+Z_{i}(t)\}}$ Добавьте шум к каждому плечу и вытяните то, у которого значение больше. 3. Обновить значение: ${\displaystyle R_{I(t)}(t+1)=R_{I(t)}(t)+x_{I(t)}(t)}$ Остальное осталось прежним.

Объяснение

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

Exp3 против FPL

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

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

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

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

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

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

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

${\displaystyle \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 ^[61] и Sliding-Window UCB. ^[62] Похожий подход, основанный на алгоритме выборки Томпсона, — это f-Discounted-Sliding-Window Thompson Sampling (f-dsw TS) ^[63], предложенный Кавенаги и др. Алгоритм f-dsw TS использует коэффициент дисконтирования в истории вознаграждения и скользящее окно, связанное с рукой, для противопоставления дрейфа концепций в нестационарных средах. Другая работа Буртини и др. представляет подход выборки Томпсона с весовыми наименьшими квадратами (WLS-TS), который оказывается полезным как в известных, так и в неизвестных нестационарных случаях. ^[64]

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

За последние годы было предложено много вариантов этой задачи.

Бандит-дуэлянт

Вариант дуэли бандитов был введен Юэ и др. (2012) ^[65] для моделирования компромисса между разведкой и эксплуатацией для относительной обратной связи. В этом варианте игроку разрешено одновременно тянуть два рычага, но он получает только бинарную обратную связь, сообщающую, какой рычаг обеспечил лучшую награду. Сложность этой проблемы заключается в том, что у игрока нет возможности напрямую наблюдать награду за свои действия. Самые ранние алгоритмы для этой проблемы — InterleaveFiltering, ^[65] Beat-The-Mean. ^[66] Относительная обратная связь дуэли бандитов также может приводить к парадоксам голосования . Решение — взять победителя Кондорсе в качестве эталона. ^[67]

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

Коллаборативный бандит

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

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

Проблема комбинаторного многорукого бандита (CMAB) ^{[76] [77] [78]} возникает, когда вместо одной дискретной переменной для выбора агенту необходимо выбрать значения для набора переменных. Если предположить, что каждая переменная дискретна, то число возможных выборов на итерацию экспоненциально зависит от числа переменных. В литературе было изучено несколько настроек CMAB, от настроек, где переменные являются бинарными ^[77], до более общих настроек, где каждая переменная может принимать произвольный набор значений. ^[78]

Смотрите также

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

Ссылки

1. Auer, P.; Cesa-Bianchi, N.; Fischer, P. (2002). «Конечный анализ задачи о многоруком бандите». Machine Learning . 47 (2/3): 235–256. doi : 10.1023/A:1013689704352 .
2. Katehakis, Michael N.; Veinott, Jr., Arthur F. (1987). «Проблема многорукого бандита: декомпозиция и вычисления». Математика исследования операций . 12 (2): 262–268. doi :10.1287/moor.12.2.262. S2CID  656323.
3. Бубек, Себастьен (2012). «Анализ сожалений стохастических и нестохастических задач многорукого бандита». Основы и тенденции в машинном обучении . 5 : 1–122. doi :10.1561/2200000024.
4. Gittins, JC (1989), Индексы распределения многорукого бандита , Wiley-Interscience Series in Systems and Optimization., Чичестер: John Wiley & Sons, Ltd., ISBN 978-0-471-92059-5
5. Берри, Дональд А .; Фристедт, Берт (1985), Проблемы бандитов: Последовательное распределение экспериментов , Монографии по статистике и прикладной теории вероятностей, Лондон: Chapman & Hall, ISBN 978-0-412-24810-8
6. Соаре, Марта; Лазарик, Алессандро; Мунос, Реми (2014). «Лучшая идентификация руки у линейных бандитов». arXiv : 1409.6110 [cs.LG].
7. Вебер, Ричард (1992), «Об индексе Гиттинса для многоруких бандитов», Annals of Applied Probability , 2 (4): 1024–1033, doi : 10.1214/aoap/1177005588 , JSTOR  2959678
8. Роббинс, Х. (1952). «Некоторые аспекты последовательного планирования экспериментов». Бюллетень Американского математического общества . 58 (5): 527–535. doi : 10.1090/S0002-9904-1952-09620-8 .
9. JC Gittins (1979). «Бандитские процессы и динамические индексы распределения». Журнал Королевского статистического общества. Серия B (методологическая) . 41 (2): 148–177. doi :10.1111/j.2517-6161.1979.tb01068.x. JSTOR  2985029. S2CID  17724147.
10. Пресс, Уильям Х. (2009), «Решения Bandit предоставляют унифицированные этические модели для рандомизированных клинических испытаний и сравнительных исследований эффективности», Труды Национальной академии наук , 106 (52): 22387–22392, Bibcode : 2009PNAS..10622387P, doi : 10.1073/pnas.0912378106 , PMC 2793317 , PMID  20018711. 
11. Пресса (1986)
12. Брошу, Эрик; Хоффман, Мэтью В.; де Фрейтас, Нандо (сентябрь 2010 г.). «Распределение портфеля для байесовской оптимизации». arXiv : 1009.5419 [cs.LG].
13. Шэнь, Вэйвэй; Ван, Цзюнь; Цзян, Юй-Ган; Чжа, Хунъюань (2015), «Выбор портфеля с ортогональным бандитским обучением», Труды международных совместных конференций по искусственному интеллекту (IJCAI2015) , заархивировано из оригинала 2021-12-04 , извлечено 2016-03-20
14. Фариас, Вивек Ф.; Ритеш, Мадан (2011), «Необратимая проблема многорукого бандита», Operations Research , 59 (2): 383–399, CiteSeerX 10.1.1.380.6983 , doi :10.1287/opre.1100.0891 
15. Уиттл, Питер (1979), «Обсуждение статьи доктора Гиттинса», Журнал Королевского статистического общества , серия B, 41 (2): 148–177, doi : 10.1111/j.2517-6161.1979.tb01069.x
16. Vermorel, Joannes; Mohri, Mehryar (2005), Алгоритмы многорукого бандита и эмпирическая оценка (PDF) , на Европейской конференции по машинному обучению, Springer, стр. 437–448
17. Уиттл, Питер (1988), «Беспокойные бандиты: распределение активности в меняющемся мире», Журнал прикладной вероятности , 25A : 287–298, doi : 10.2307/3214163, JSTOR  3214163, MR  0974588, S2CID  202109695
18. Уиттл, Питер (1981), «Бандиты, приобретающие оружие», Annals of Probability , 9 (2): 284–292, doi : 10.1214/aop/1176994469
19. Auer, P.; Cesa-Bianchi, N.; Freund, Y.; Schapire, RE (2002). «Нестохастическая задача многорукого бандита». SIAM J. Comput. 32 (1): 48–77. CiteSeerX 10.1.1.130.158 . doi :10.1137/S0097539701398375. S2CID  13209702.  
20. Орельен Гаривье; Эмили Кауфманн (2016). «Оптимальная идентификация лучшей руки с фиксированной уверенностью». arXiv : 1602.04589 [math.ST].
21. Лай, Т. Л.; Роббинс, Х. (1985). «Асимптотически эффективные адаптивные правила распределения». Успехи в прикладной математике . 6 (1): 4–22. doi : 10.1016/0196-8858(85)90002-8 .
22. Katehakis, MN; Robbins, H. (1995). «Последовательный выбор из нескольких популяций». Труды Национальной академии наук Соединенных Штатов Америки . 92 (19): 8584–5. Bibcode : 1995PNAS ...92.8584K. doi : 10.1073/pnas.92.19.8584 . PMC 41010. PMID  11607577. 
23. Бернетас, AN; Катехакис, MN (1996). «Оптимальные адаптивные политики для задач последовательного распределения». Успехи в прикладной математике . 17 (2): 122–142. doi : 10.1006/aama.1996.0007 .
24. Бернетас, Апостолос Н.; Катехакис, Майкл Н. (1997). «Оптимальные адаптивные политики для марковских процессов принятия решений». Математика исследования операций . 22 (1): 222–255. doi :10.1287/moor.22.1.222.
25. Тевари, А.; Бартлетт, ПЛ (2008). «Оптимистическое линейное программирование дает логарифмическое сожаление для неприводимых MDP» (PDF) . Достижения в области нейронных систем обработки информации . 20 . CiteSeerX 10.1.1.69.5482 . Архивировано из оригинала (PDF) 2012-05-25 . Получено 2012-10-12 . 
26. Ортнер, Р. (2010). «Онлайн-границы сожалений для марковских процессов принятия решений с детерминированными переходами». Теоретическая информатика . 411 (29): 2684–2695. doi : 10.1016/j.tcs.2010.04.005 .
27. Филиппи, С. и Каппе, О. и Гаривье, А. (2010). «Онлайн-границы сожалений для марковских процессов принятия решений с детерминированными переходами», Communication, Control, and Computing (Allerton), 48-я ежегодная конференция Allerton по , стр. 115–122
28. Honda, J.; Takemura, A. (2011). «Асимптотически оптимальная политика для моделей с конечной поддержкой в ​​задаче о многоруком бандите». Machine Learning . 85 (3): 361–391. arXiv : 0905.2776 . doi :10.1007/s10994-011-5257-4. S2CID  821462.
29. Пиларски, Себастьян; Пиларский, Славомир; Варро, Даниэль (февраль 2021 г.). «Оптимальная политика для бандитов Бернулли: расчеты и алгоритмы». Транзакции IEEE по искусственному интеллекту . 2 (1): 2–17. дои : 10.1109/TAI.2021.3074122 . ISSN  2691-4581. S2CID  235475602.
30. Пиларски, Себастьян; Пиларски, Славомир; Варро, Даниэль (2021). «Бандиты Бернулли с отложенным вознаграждением: оптимальная политика и предсказательный метаалгоритм PARDI». Труды IEEE по искусственному интеллекту . 3 (2): 152–163. doi : 10.1109/TAI.2021.3117743 . ISSN  2691-4581. S2CID  247682940.
31. Авербек, BB (2015). «Теория выбора в задачах бандита, выборки информации и добычи пропитания». PLOS Computational Biology . 11 (3): e1004164. Bibcode : 2015PLSCB..11E4164A. doi : 10.1371/journal.pcbi.1004164 . PMC 4376795. PMID  25815510 . 
32. Коста, VD; Авербек, BB (2019). «Подкорковые субстраты решений «исследовать-использовать» у приматов». Neuron . 103 (3): 533–535. doi :10.1016/j.neuron.2019.05.017. PMC 6687547 . PMID  31196672. 
33. Саттон, Р. С. и Барто, А. Г. 1998 Обучение с подкреплением: введение. Кембридж, Массачусетс: MIT Press.
34. Tokic, Michel (2010), «Адаптивное ε-жадное исследование в обучении с подкреплением на основе различий в значениях» (PDF) , KI 2010: Достижения в области искусственного интеллекта , Lecture Notes in Computer Science, т. 6359, Springer-Verlag, стр. 203–210, CiteSeerX 10.1.1.458.464 , doi :10.1007/978-3-642-16111-7_23, ISBN  978-3-642-16110-0.
35. Tokic, Michel; Palm, Günther (2011), «Исследование на основе разницы значений: адаптивное управление между Epsilon-Greedy и Softmax» (PDF) , KI 2011: Достижения в области искусственного интеллекта , Lecture Notes in Computer Science, т. 7006, Springer-Verlag, стр. 335–346, ISBN 978-3-642-24455-1.
36. Гимельфарб, Мишель; Саннер, Скотт; Ли, Чи-Гун (2019), «ε-BMC: байесовский ансамблевый подход к эпсилон-жадному исследованию в обучении с подкреплением без моделей» (PDF) , Труды тридцать пятой конференции по неопределенности в искусственном интеллекте , AUAI Press, стр. 162.
37. Скотт, SL (2010), «Современный байесовский взгляд на многорукого бандита», Прикладные стохастические модели в бизнесе и промышленности , 26 (2): 639–658, doi :10.1002/asmb.874, S2CID  573750
38. Оливье Шапель; Лихонг Ли (2011), «Эмпирическая оценка выборки Томпсона», Достижения в области нейронных систем обработки информации , 24 , Curran Associates: 2249–2257
39. Лэнгфорд, Джон; Чжан, Тонг (2008), «Алгоритм жадности эпохи для контекстных многоруких бандитов», Достижения в области нейронных систем обработки информации , т. 20, Curran Associates, Inc., стр. 817–824
40. Лихонг Ли; Вэй Чу; Джон Лэнгфорд; Роберт Э. Шапир (2010), «Контекстно-бандитский подход к персонализированным рекомендациям новостных статей», Труды 19-й международной конференции по Всемирной паутине , стр. 661–670, arXiv : 1003.0146 , doi : 10.1145/1772690.1772758, ISBN 9781605587998, S2CID  207178795
41. Вэй Чу; Лихонг Ли; Лев Рейзин; Роберт Э. Шапир (2011), «Контекстные бандиты с линейными функциями выплат» (PDF) , Труды 14-й Международной конференции по искусственному интеллекту и статистике (AISTATS) : 208–214
42. Auer, P. (2000). «Использование верхних доверительных границ для онлайн-обучения». Труды 41-го ежегодного симпозиума по основам компьютерной науки . IEEE Comput. Soc. стр. 270–279. doi :10.1109/sfcs.2000.892116. ISBN 978-0769508504. S2CID  28713091.
43. Хонг, Цунг-Пей; Сонг, Вэй-Пин; Чиу, Чу-Тиен (ноябрь 2011 г.). «Эволюционная кластеризация составных атрибутов». Международная конференция по технологиям и приложениям искусственного интеллекта 2011 г. IEEE. стр. 305–308. doi :10.1109/taai.2011.59. ISBN 9781457721748. S2CID  14125100.
44. Риголле, Филипп; Зееви, Ассаф (2010), Непараметрические бандиты с ковариатами , Конференция по теории обучения, COLT 2010, arXiv : 1003.1630 , Bibcode : 2010arXiv1003.1630R
45. Сливкинс, Александрс (2011), Контекстные бандиты с информацией о сходстве. (PDF) , Конференция по теории обучения, COLT 2011
46. Перше, Вианней; Риголле, Филипп (2013), «Проблема многорукого бандита с ковариатами», Annals of Statistics , 41 (2): 693–721, arXiv : 1110.6084 , doi : 10.1214/13-aos1101, S2CID  14258665
47. Сара Филиппи; Оливье Каппе; Орельен Гаривье; Чаба Шепешвари (2010), «Параметрические бандиты: обобщенный линейный случай», Достижения в области нейронных систем обработки информации , 23 , Curran Associates: 586–594
48. Лихун Ли; Юй Лу; Дэнъюн Чжоу (2017), «Доказуемо оптимальные алгоритмы для обобщенных линейных контекстных бандитов», Труды 34-й Международной конференции по машинному обучению (ICML) : 2071–2080, arXiv : 1703.00048 , Bibcode : 2017arXiv170300048L
49. Кванг-Сун Джун; Анируддха Бхаргава; Роберт Д. Новак; Ребекка Уиллетт (2017), «Масштабируемые обобщенные линейные бандиты: онлайн-вычисления и хеширование», Достижения в области нейронных систем обработки информации , 30 , Curran Associates: 99–109, arXiv : 1706.00136 , Bibcode : 2017arXiv170600136J
50. Бранислав Кветон; Манзил Захир; Чаба Шепешвари; Лихонг Ли; Мохаммад Гавамзаде; Крейг Бутилье (2020), «Рандомизированное исследование в обобщенных линейных бандитах», Труды 23-й Международной конференции по искусственному интеллекту и статистике (AISTATS) , arXiv : 1906.08947 , Bibcode : 2019arXiv190608947K
51. Михал Валько; Натан Корда; Реми Муньос; Илиас Флаунас; Нелло Кристианини (2013), Конечновременной анализ контекстных бандитов с ядром , 29-я конференция по неопределенности в искусственном интеллекте (UAI 2013) и (JFPDA 2013)., arXiv : 1309.6869 , Bibcode :2013arXiv1309.6869V
52. Феро, Рафаэль; Аллезиардо, Робин; Урвой, Танги; Клеро, Фабрис (2016). «Случайный лес для контекстной проблемы бандита». Aistats : 93–101. Архивировано из оригинала 2016-08-10 . Получено 2016-06-10 .
53. Алех Агарвал; Дэниел Дж. Хсу; Сатьен Кейл; Джон Лэнгфорд; Лихонг Ли; Роберт Э. Шапир (2014), «Укрощение монстра: быстрый и простой алгоритм для контекстных бандитов», Труды 31-й Международной конференции по машинному обучению (ICML) : 1638–1646, arXiv : 1402.0555 , Bibcode : 2014arXiv1402.0555A
54. Баданидиюру, А.; Лэнгфорд, Дж.; Сливкинс, А. (2014), «Находчивые контекстные бандиты» (PDF) , Труды конференции по теории обучения (COLT)^{[ постоянная мертвая ссылка ]}
55. Wu, Huasen; Srikant, R.; Liu, Xin; Jiang, Chong (2015), «Алгоритмы с логарифмическим или сублинейным сожалением для ограниченных контекстных бандитов», 29-я ежегодная конференция по нейронным системам обработки информации (NIPS) , 28 , Curran Associates: 433–441, arXiv : 1504.06937 , Bibcode : 2015arXiv150406937W
56. Буртини, Джузеппе; Лоеппки, Джейсон; Лоуренс, Рамон (2015). «Обзор дизайна онлайн-экспериментов со стохастическим многоруким бандитом». arXiv : 1510.00757 [stat.ML].
57. Seldin, Y., Szepesvári, C., Auer, P. и Abbasi-Yadkori, Y., 2012, декабрь. Оценка и анализ производительности алгоритма EXP3 в стохастических средах. В EWRL (стр. 103–116).
58. Хаттер, М. и Поланд, Дж., 2005. Адаптивное онлайн-прогнозирование путем следования за возмущенным лидером. Журнал исследований машинного обучения, 6 (апрель), стр. 639–660.
59. Агравал, Раджив. Задача о континуум-вооруженном бандите. SIAM J. of Control and Optimization. 1995.
60. Бесбес, О.; Гур, И.; Зееви, А. Стохастическая задача многорукого бандита с нестационарными вознаграждениями. В Трудах Достижений в области нейронных систем обработки информации, Монреаль, Квебек, Канада, 8–13 декабря 2014 г.; стр. 199–207<https://proceedings.neurips.cc/paper/2014/file/903ce9225fca3e988c2af215d4e544d3-Paper.pdf>
61. UCB со скидкой, Левенте Кочиш, Чаба Сепешвари, 2006 г.
62. Гаривье, Орельен; Мулин, Эрик (2008). «О политиках с верхней границей уверенности для нестационарных задач бандитов». arXiv : 0805.3415 [math.ST].
63. Кавенаги, Эмануэле; Соттокорнола, Габриэле; Стелла, Фабио; Занкер, Маркус (2021). «Нестационарный многорукий бандит: эмпирическая оценка нового концептуального алгоритма, учитывающего дрейф». Энтропия . 23 (3): 380. Bibcode : 2021Entrp..23..380C. doi : 10.3390/e23030380 . PMC 8004723. PMID  33807028 . 
64. Улучшение экспериментов в области интернет-маркетинга с помощью дрейфующих многоруких бандитов, Джузеппе Буртини, Джейсон Леппки, Рамон Лоуренс, 2015 г. <http://www.scitepress.org/DigitalLibrary/PublicationsDetail.aspx?ID=Dx2xXEB0PJE=&t=1>
65. Юэ, Йисонг; Бродер, Йозеф; Кляйнберг, Роберт; Йоахимс, Торстен (2012), «Проблема дуэли бандитов с К-руками», Журнал компьютерных и системных наук , 78 (5): 1538–1556, CiteSeerX 10.1.1.162.2764 , doi : 10.1016/j.jcss.2011.12.028 
66. Юэ, Йисонг; Йоахимс, Торстен (2011), «Победить подлого бандита», Труды ICML'11
67. Урвой, Танги; Клеро, Фабрис; Феро, Рафаэль; Нааман, Сами (2013), «Generic Exploration and K-armed Voting Bandits» (PDF) , Труды 30-й Международной конференции по машинному обучению (ICML-13) , заархивировано из оригинала (PDF) 2016-10-02 , извлечено 2016-04-29
68. Зоги, Масрур; Уайтсон, Шимон; Муньос, Реми; Рийке, Маартен Д. (2014), «Относительная верхняя граница достоверности для задачи о поединке с вооруженным $K$ бандитом» (PDF) , Труды 31-й Международной конференции по машинному обучению (ICML-14) , архивировано из оригинала (PDF) 26.03.2016 , извлечено 27.04.2016
69. Gajane, Pratik; Urvoy, Tanguy; Clérot, Fabrice (2015), "A Relative Exponential Weighing Algorithm for Adversarial Utility-based Dueling Bandits" (PDF) , Труды 32-й Международной конференции по машинному обучению (ICML-15) , заархивировано из оригинала (PDF) 2015-09-08 , извлечено 2016-04-29
70. Зоги, Масрур; Карнин, Зохар С.; Уайтсон, Шимон; Рийке, Маартен Д. (2015), «Copeland Dueling Bandits», Достижения в области нейронных систем обработки информации, NIPS'15 , arXiv : 1506.00312 , Bibcode : 2015arXiv150600312Z
71. Комияма, Дзюнпей; Хонда, Дзюнья; Касима, Хисаши; Накагава, Хироши (2015), «Нижняя граница сожаления и оптимальный алгоритм в задаче о дуэли бандитов» (PDF) , Труды 28-й конференции по теории обучения , архивировано из оригинала (PDF) 2016-06-17 , извлечено 2016-04-27
72. Ву, Хуасэн; Лю, Синь (2016), «Двойная выборка Томпсона для дуэли бандитов», 30-я ежегодная конференция по нейронным системам обработки информации (NIPS) , arXiv : 1604.07101 , Bibcode : 2016arXiv160407101W
73. Чеза-Бьянки, Николо; Джентиле, Клаудио; Заппелла, Джованни (2013), Банда бандитов , Достижения в области нейронных систем обработки информации 26, NIPS 2013, arXiv : 1306.0811
74. Джентиле, Клаудио; Ли, Шуай; Заппелла, Джованни (2014), «Онлайн-кластеризация бандитов», 31-я Международная конференция по машинному обучению, Журнал исследований машинного обучения (ICML 2014) , arXiv : 1401.8257 , Bibcode : 2014arXiv1401.8257G
75. Ли, Шуай; Александрос, Карацоглу; Джентиле, Клаудио (2016), «Бандиты совместной фильтрации», 39-я Международная конференция ACM SIGIR по поиску информации (SIGIR 2016) , arXiv : 1502.03473 , Bibcode : 2015arXiv150203473L
76. Гай, Й.; Кришнамачари, Б.; Джейн, Р. (2010), «Изучение многопользовательских распределений каналов в сетях когнитивного радио: комбинаторная формулировка многорукого бандита», Симпозиум IEEE 2010 года по новым рубежам в динамическом спектре (PDF) , стр. 1–9^{[ мертвая ссылка ]}
77. Chen, Wei; Wang, Yajun; Yuan, Yang (2013), «Комбинаторный многорукий бандит: общая структура и приложения», Труды 30-й Международной конференции по машинному обучению (ICML 2013) (PDF) , стр. 151–159, архивировано из оригинала (PDF) 2016-11-19 , извлечено 2019-06-14
78. Santiago Ontañón (2017), «Комбинаторные многорукие бандиты для стратегических игр в реальном времени», Журнал исследований искусственного интеллекта , 58 : 665–702, arXiv : 1710.04805 , Bibcode : 2017arXiv171004805O, doi : 10.1613/jair.5398, S2CID  8517525

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

• Гуха, С.; Мунагала, К.; Ши, П. (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», Приближенное динамическое программирование: Решение проклятий размерности , Нью-Йорк: John Wiley and Sons, 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, архивировано из оригинала 2013-12-11.

• Аллесиардо, Робин (2014), «Комитет по нейронным сетям для решения проблемы контекстного бандита», Neural Information Processing – 21st International Conference, ICONIP 2014, Малайзия, 03-06 ноября 2014 г., Труды , Lecture Notes in Computer Science, т. 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.
• Katehakis, M. ; C. Derman (1986), "Вычисление оптимальных последовательных правил распределения в клинических испытаниях", Адаптивные статистические процедуры и смежные темы , Конспект лекций Института математической статистики - Серия монографий, т. 8, стр. 29–39, doi : 10.1214/lnms/1215540286 , ISBN 978-0-940600-09-6, JSTOR  4355518.
• Katehakis, Michael N. ; Veinott, Jr., Arthur F. (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 с открытым исходным кодом , облегчающий моделирование и оценку как контекстно-независимых, так и контекстных политик многорукого бандита.
• bandit.sourceforge.net Проект Bandit, реализация стратегий Bandit с открытым исходным кодом.
• Banditlib, реализация бандитских стратегий с открытым исходным кодом на C++.
• Лесли Пак Кельблинг и Майкл Л. Литтман (1996). Эксплуатация против исследования: случай одного государства.
• Учебник: Введение в Bandits: Алгоритмы и теория. Часть 1. Часть 2.
• Задача Фейнмана о ресторане — классический пример (с известным ответом) компромисса между эксплуатацией и исследованием.
• Алгоритмы Bandit против AB-тестирования.
• С. Бубек и Н. Чеза-Бьянки. Обзор бандитов.
• Обзор контекстных многоруких бандитов, обзор/руководство по контекстным бандитам.
• Запись в блоге о стратегиях многорукого бандита с кодом Python.
• Анимированные интерактивные графики, иллюстрирующие стратегии балансировки разведки/эксплуатации с использованием эпсилон-жадного алгоритма, выборки Томпсона и верхней доверительной границы.