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

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

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

Формулировка проблемы многорукого бандита

Классическая проблема многорукого бандита (MAB) определяется K руками, каждая с неизвестным распределением вознаграждения. На каждом временном шаге t агент выбирает руку a_t ∈ {1, 2, ..., K} и получает вознаграждение r_t, взятое из распределения выбранной руки. Цель — максимизировать кумулятивное вознаграждение за T раундов или, что эквивалентно, минимизировать сожаление, которое представляет собой разницу между кумулятивным вознаграждением оптимальной руки и кумулятивным вознаграждением выбранных рук.

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

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

Контекстные многорукие бандиты

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

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

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

Практические применения многоруких бандитов

Клинические испытания

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

Рекомендательные системы

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

Обнаружение аномалий

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

Другие применения

Дополнительные применения включают оптимизацию портфеля в финансах, A/B тестирование в веб-разработке, распределение ресурсов в облачных вычислениях и образовательные технологии для адаптивного обучения. Гибкость фреймворка бандитов делает его применимым к любому сценарию, требующему последовательного принятия решений в условиях неопределенности с ограниченной обратной связью.

Алгоритмы и подходы для бандитов

Стохастические бандиты

Стохастические бандиты предполагают, что вознаграждения каждой руки извлекаются независимо из фиксированного распределения. Ключевые алгоритмы включают ε-жадный, который выбирает лучшую руку с вероятностью 1-ε и случайную руку с вероятностью ε; алгоритмы Верхней Доверительной Границы (UCB), которые выбирают руки на основе оптимистичных оценок их потенциала; и Томпсоновское сэмплирование, которое использует байесовские апостериорные распределения для балансирования исследования и использования.

Аверсивные бандиты

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

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

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

Алгоритмы контекстных бандитов

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

Текущие тенденции и будущие перспективы

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

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

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

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

Заключение

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

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

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