Бандиты с рюкзаками

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