Многорукий бандит - Multi-armed bandit

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

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

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

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

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

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

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

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

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

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

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

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

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

Многорукий бандит (сокращенно: бандит или МАБ) можно рассматривать как набор реальных распределений , каждое из которых связано с наградами, доставляемыми одним из рычагов. Позвольте быть средними значениями, связанными с этими распределениями вознаграждения. Игрок итеративно использует один рычаг за раунд и наблюдает за соответствующей наградой. Цель состоит в том, чтобы максимизировать сумму собранных наград. Горизонт - это количество оставшихся раундов. Проблема бандита формально эквивалентна однозначному марковскому процессу принятия решений . Сожалеют после раундов определяются как ожидаемая разница между суммой вознаграждения , связанной с оптимальной стратегией и суммами собранных наград: ${\ Displaystyle B = \ {R_ {1}, \ dots, R_ {K} \}}$${\ Displaystyle К \ ин \ 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 \ му ^ {*} = \ макс _ {к} \ {\ му _ {к} \}}$${\ displaystyle {\ widehat {r}} _ {t}}$

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

Вариации

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

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

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

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

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

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

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

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

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

• UCBC (исторические верхние границы достоверности с кластерами): алгоритм адаптирует UCB для новых настроек, так что он может включать как кластеризацию, так и историческую информацию. Алгоритм включает исторические наблюдения за счет использования как при вычислении наблюдаемых средних вознаграждений, так и члена неопределенности. Алгоритм включает информацию о кластеризации, играя на двух уровнях: сначала выбирая кластер, используя UCB-подобную стратегию на каждом временном шаге, а затем выбирая руку в кластере, снова используя UCB-подобную стратегию.

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

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

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

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

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

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

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

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

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

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

Стратегии с этическими ограничениями

• Выборка Томпсона с ограничениями поведения (BCTS) : в этой статье авторы подробно описывают новый онлайн-агент, который изучает набор поведенческих ограничений путем наблюдения и использует эти усвоенные ограничения в качестве руководства при принятии решений в онлайн-среде, при этом оставаясь реактивным на вознаграждение за обратную связь. Чтобы определить этого агента, было решено принять новое расширение классической контекстной настройки многорукого бандита и предоставить новый алгоритм под названием Behavior Constrained Thompson Sampling (BCTS), который позволяет онлайн-обучение при соблюдении экзогенных ограничений. Агент изучает ограниченную политику, которая реализует наблюдаемые поведенческие ограничения, продемонстрированные агентом учителя, а затем использует эту ограниченную политику для управления онлайн-исследованием и эксплуатацией на основе вознаграждения.

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

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

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

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

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

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

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

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

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

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

• Контекстные бандиты или контекстные бандиты с ограниченным контекстом : авторы рассматривают новую формулировку модели многорукого бандита, которая называется контекстным бандитом с ограниченным контекстом, в которой учащийся может получить доступ только к ограниченному количеству функций на каждой итерации. Эта новая формулировка мотивирована различными онлайн-проблемами, возникающими при клинических испытаниях, рекомендательных системах и моделировании внимания. Здесь они адаптируют стандартный алгоритм многорукого бандита, известный как выборка Томпсона, чтобы воспользоваться настройкой ограниченного контекста, и предлагают два новых алгоритма, называемых выборкой Томпсона с ограниченным контекстом (TSRC) и выборкой Томпсона с ограниченным контекстом (WTSRC). ), для работы в стационарных и нестационарных средах соответственно.

На практике обычно существует стоимость, связанная с ресурсом, потребляемым каждым действием, а общая стоимость ограничивается бюджетом во многих приложениях, таких как краудсорсинг и клинические испытания. Ограниченный контекстный бандит (CCB) - это такая модель, которая учитывает как временные, так и бюджетные ограничения в условиях многорукого бандита. A. Badanidiyuru et al. впервые изучил контекстуальных бандитов с ограничениями бюджета, также называемых Находчивыми контекстными бандитами, и показал, что сожаление достижимо. Однако их работа сосредоточена на конечном наборе политик, а алгоритм вычислительно неэффективен. ${\ displaystyle O ({\ sqrt {T}})}$

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

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

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

Состязательный бандит

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

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

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

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

Exp3

Алгоритм

 Parameters: Real ${\displaystyle \gamma \in (0,1]}$
 
 Initialisation: ${\displaystyle \omega _{i}(1)=1}$ for ${\displaystyle i=1,...,K}$
 
 For each t = 1, 2, ..., T
  1. Set ${\displaystyle p_{i}(t)=(1-\gamma ){\frac {\omega _{i}(t)}{\sum _{j=1}^{K}\omega _{j}(t)}}+{\frac {\gamma }{K}}}$       ${\displaystyle i=1,...,K}$
  2. Draw ${\displaystyle i_{t}}$ randomly according to the probabilities ${\displaystyle p_{1}(t),...,p_{K}(t)}$
  3. Receive reward ${\displaystyle x_{i_{t}}(t)\in [0,1]}$
  4. For ${\displaystyle j=1,...,K}$ set:
      ${\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- \ гамма)}$

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

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

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

Алгоритм

 Parameters: Real ${\displaystyle \eta }$
 
 Initialisation: ${\displaystyle \forall i:R_{i}(1)=0}$
 
 For each t = 1,2,...,T
  1. For each arm generate a random noise from an exponential distribution ${\displaystyle \forall i:Z_{i}(t)\sim Exp(\eta )}$
  2. Pull arm ${\displaystyle I(t)}$: ${\displaystyle 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: ${\displaystyle R_{I(t)}(t+1)=R_{I(t)}(t)+x_{I(t)}(t)}$
     The rest remains the same

Объяснение

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

Exp3 против FPL

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

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

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

Гаривье и Мулен получили некоторые из первых результатов в отношении проблем с бандитами, в которых лежащая в основе модель может изменяться во время игры. Для этого случая был представлен ряд алгоритмов, в том числе UCB со скидкой и UCB со скользящим окном.

Другая работа Буртини и др. вводит метод взвешенной выборки Томпсона методом наименьших квадратов (WLS-TS), который оказывается полезным как в известных, так и в неизвестных нестационарных случаях. В известном нестационарном случае авторы предлагают альтернативное решение, вариант UCB под названием «Скорректированная верхняя граница уверенности» (A-UCB), который предполагает стохастическую модель и предоставляет верхние границы сожаления.

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

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

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

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

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

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

Бандиты с совместной фильтрацией (например, COFIBA) были представлены Ли, Карацоглу и Джентиле (SIGIR, 2016), где методы классической совместной фильтрации и контентной фильтрации пытаются изучить статическую модель рекомендаций с учетом обучающих данных. Эти подходы далеки от идеала в высокодинамичных областях рекомендаций, таких как рекомендации по новостям и вычислительная реклама, где набор элементов и пользователей очень изменчив. В этой работе они исследуют метод адаптивной кластеризации для рекомендаций по контенту, основанный на стратегиях разведки и эксплуатации в контекстных настройках многорукого бандита. Их алгоритм (COFIBA, произносится как «Coffee Bar») учитывает эффекты сотрудничества, возникающие из-за взаимодействия пользователей с элементами, путем динамической группировки пользователей на основе рассматриваемых элементов и, в то же время, группировки элементов. на основе подобия кластеризации, наведенной над пользователями. Таким образом, полученный алгоритм использует преимущества шаблонов предпочтений в данных способом, подобным методам совместной фильтрации. Они обеспечивают эмпирический анализ реальных наборов данных среднего размера, демонстрируя масштабируемость и повышенную эффективность прогнозирования (измеряемую по показателю кликабельности) по сравнению с современными методами кластеризации бандитов. Они также предоставляют анализ сожаления в рамках стандартной настройки линейного стохастического шума.

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

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

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

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

использованная литература

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

У Схолии есть тематический профиль Многорукий бандит .

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

• Аллезиардо, Робин (2014 г.), «Комитет по нейронным сетям для решения проблемы контекстного бандита», Обработка нейронной информации - 21-я международная конференция, ICONIP 2014, Малайзия, 3–6 ноября 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), "Об индексе Gittins для multiarmed бандитов", Анналы прикладной вероятности , 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 .
• Катехакис, М .; AF Veinott, младший (1987), "многорукая проблема Бандита: разложение и вычисление" , Математика исследования операций , 12 (2): 262-268, DOI : 10.1287 / moor.12.2.262 , JSTOR  3689689 , S2CID  656323 .

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

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