Просмотр исходного текста страницы Citeseer/Bandits with knapsacks (2013) 10.1.1.744.7353

{{checked|}}
{{citeseerlink|citeseer/Bandits with knapsacks (2013) 10.1.1.744.7353|<html>
Задачи с «многоруким бандитом» являются доминирующей теоретической моделью компромиссов между разведкой и эксплуатацией в обучении, и они имеют бесчисленное множество применений, начиная от медицинских испытаний, коммуникационных сетей и заканчивая веб-поиском и рекламой. 
<p>
Во многих из этих прикладных областей обучающийся может быть ограничен одним или несколькими ограничениями на предложение (или бюджет), в дополнение к обычному ограничению на временной горизонт. 
В литературе отсутствует общая модель, охватывающая такого рода проблемы. 
<p>
Мы представляем такую модель, называемую «бандиты с ранцами», которая сочетает в себе аспекты стохастического целочисленного программирования и онлайн-обучения. 

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

Далее мы доказываем, что «сожаление», достигаемое обоими алгоритмами, оптимально до полилогарифмических коэффициентов. 

<p>

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

В качестве примера конкретного приложения мы рассматриваем проблему динамического ценообразования на размещение с ограниченным предложением и получаем первый алгоритм, чье сожаление по отношению к оптимальной динамической политике является сублинейным по отношению к предложению.
</html>}}

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

{{enddiv}}

[[Категория:CiteSeerArticles]]