Citeseer/Bandits with knapsacks (2013) 10.1.1.744.7353

Материал из DISCOPAL
Версия от 14:51, 23 ноября 2021; StasFomin (обсуждение | вклад)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

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

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

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

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

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

Расширенная версия Citeseer/Bandits_with_Knapsacks_—_Dynamic_procurement_for_crowdsourcing_10.1.1.365.1661

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.