Citeseer/Bandits with knapsacks (2013) 10.1.1.744.7353 — различия между версиями
StasFomin (обсуждение | вклад) (Новая страница: «{{checked|}} {{citeseerlink|citeseer/Bandits with knapsacks (2013) 10.1.1.744.7353|<html> </html>}} Расширенная версия Citeseer/Bandits_with…») |
StasFomin (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
{{checked|}} | {{checked|}} | ||
{{citeseerlink|citeseer/Bandits with knapsacks (2013) 10.1.1.744.7353|<html> | {{citeseerlink|citeseer/Bandits with knapsacks (2013) 10.1.1.744.7353|<html> | ||
| + | Задачи с «многоруким бандитом» являются доминирующей теоретической моделью компромиссов между разведкой и эксплуатацией в обучении, и они имеют бесчисленное множество применений, начиная от медицинских испытаний, коммуникационных сетей и заканчивая веб-поиском и рекламой. | ||
| + | <p> | ||
| + | Во многих из этих прикладных областей обучающийся может быть ограничен одним или несколькими ограничениями на предложение (или бюджет), в дополнение к обычному ограничению на временной горизонт. | ||
| + | В литературе отсутствует общая модель, охватывающая такого рода проблемы. | ||
| + | <p> | ||
| + | Мы представляем такую модель, называемую «бандиты с ранцами», которая сочетает в себе аспекты стохастического целочисленного программирования и онлайн-обучения. | ||
| + | Отличительной особенностью нашей задачи, по сравнению с существующей литературой по минимизации сожалений, является то, что оптимальная политика для данного латентного распределения может значительно превосходить политику, которая играет «оптимальную фиксированную руку». | ||
| + | Следовательно, достижение «сублинейного сожаления» в задаче «бандит с рюкзаками» значительно сложнее, чем в обычных задачах с бандитами. | ||
| + | <p> | ||
| + | Мы представляем два алгоритма, чье вознаграждение близко к информационно-теоретическому оптимуму: один основан на новой парадигме «сбалансированной разведки», а другой — это первично-дуальный алгоритм, использующий мультипликативные обновления. | ||
| + | Далее мы доказываем, что «сожаление», достигаемое обоими алгоритмами, оптимально до полилогарифмических коэффициентов. | ||
| + | |||
| + | <p> | ||
| + | |||
| + | Мы иллюстрируем общность проблемы, представляя приложения в ряде различных областей, включая электронную торговлю, маршрутизацию и составление расписаний. | ||
| + | |||
| + | В качестве примера конкретного приложения мы рассматриваем проблему динамического ценообразования на размещение с ограниченным предложением и получаем первый алгоритм, чье сожаление по отношению к оптимальной динамической политике является сублинейным по отношению к предложению. | ||
</html>}} | </html>}} | ||
Расширенная версия [[Citeseer/Bandits_with_Knapsacks_—_Dynamic_procurement_for_crowdsourcing_10.1.1.365.1661]] | Расширенная версия [[Citeseer/Bandits_with_Knapsacks_—_Dynamic_procurement_for_crowdsourcing_10.1.1.365.1661]] | ||
| + | |||
{{enddiv}} | {{enddiv}} | ||
[[Категория:CiteSeerArticles]] | [[Категория:CiteSeerArticles]] | ||
Текущая версия на 14:51, 23 ноября 2021
Во многих из этих прикладных областей обучающийся может быть ограничен одним или несколькими ограничениями на предложение (или бюджет), в дополнение к обычному ограничению на временной горизонт. В литературе отсутствует общая модель, охватывающая такого рода проблемы.
Мы представляем такую модель, называемую «бандиты с ранцами», которая сочетает в себе аспекты стохастического целочисленного программирования и онлайн-обучения. Отличительной особенностью нашей задачи, по сравнению с существующей литературой по минимизации сожалений, является то, что оптимальная политика для данного латентного распределения может значительно превосходить политику, которая играет «оптимальную фиксированную руку». Следовательно, достижение «сублинейного сожаления» в задаче «бандит с рюкзаками» значительно сложнее, чем в обычных задачах с бандитами.
Мы представляем два алгоритма, чье вознаграждение близко к информационно-теоретическому оптимуму: один основан на новой парадигме «сбалансированной разведки», а другой — это первично-дуальный алгоритм, использующий мультипликативные обновления. Далее мы доказываем, что «сожаление», достигаемое обоими алгоритмами, оптимально до полилогарифмических коэффициентов.
Мы иллюстрируем общность проблемы, представляя приложения в ряде различных областей, включая электронную торговлю, маршрутизацию и составление расписаний. В качестве примера конкретного приложения мы рассматриваем проблему динамического ценообразования на размещение с ограниченным предложением и получаем первый алгоритм, чье сожаление по отношению к оптимальной динамической политике является сублинейным по отношению к предложению. …»
Расширенная версия Citeseer/Bandits_with_Knapsacks_—_Dynamic_procurement_for_crowdsourcing_10.1.1.365.1661