Citeseer/Bandits with knapsacks (2013) 10.1.1.744.7353
Во многих из этих прикладных областей обучающийся может быть ограничен одним или несколькими ограничениями на предложение (или бюджет), в дополнение к обычному ограничению на временной горизонт. В литературе отсутствует общая модель, охватывающая такого рода проблемы.
Мы представляем такую модель, называемую «бандиты с ранцами», которая сочетает в себе аспекты стохастического целочисленного программирования и онлайн-обучения. Отличительной особенностью нашей задачи, по сравнению с существующей литературой по минимизации сожалений, является то, что оптимальная политика для данного латентного распределения может значительно превосходить политику, которая играет «оптимальную фиксированную руку». Следовательно, достижение «сублинейного сожаления» в задаче «бандит с рюкзаками» значительно сложнее, чем в обычных задачах с бандитами.
Мы представляем два алгоритма, чье вознаграждение близко к информационно-теоретическому оптимуму: один основан на новой парадигме «сбалансированной разведки», а другой — это первично-дуальный алгоритм, использующий мультипликативные обновления. Далее мы доказываем, что «сожаление», достигаемое обоими алгоритмами, оптимально до полилогарифмических коэффициентов.
Мы иллюстрируем общность проблемы, представляя приложения в ряде различных областей, включая электронную торговлю, маршрутизацию и составление расписаний. В качестве примера конкретного приложения мы рассматриваем проблему динамического ценообразования на размещение с ограниченным предложением и получаем первый алгоритм, чье сожаление по отношению к оптимальной динамической политике является сублинейным по отношению к предложению. …»
Расширенная версия Citeseer/Bandits_with_Knapsacks_—_Dynamic_procurement_for_crowdsourcing_10.1.1.365.1661
[ Хронологический вид ]Комментарии
Войдите, чтобы комментировать.