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

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