Citeseer/Bandits with Knapsacks — Dynamic procurement for crowdsourcing 10.1.1.365.1661 — различия между версиями
StasFomin (обсуждение | вклад) (Новая страница: «{{checked|}} {{citeseerlink|citeseer/Bandits with Knapsacks — Dynamic procurement for crowdsourcing 10.1.1.365.1661|<html> </html>}} {{enddiv}} Катег…») |
StasFomin (обсуждение | вклад) |
||
| (не показана одна промежуточная версия этого же участника) | |||
| Строка 1: | Строка 1: | ||
{{checked|}} | {{checked|}} | ||
| − | {{citeseerlink|citeseer/Bandits with Knapsacks — Dynamic procurement for crowdsourcing 10.1.1.365.1661| | + | {{citeseerlink|citeseer/Bandits with Knapsacks — Dynamic procurement for crowdsourcing 10.1.1.365.1661| |
| + | В базовой версии динамической «задачи закупок» алгоритм имеет бюджет B, который он должен потратить, и сталкивается с n агентами (потенциальными продавцами), которые прибывают последовательно. | ||
| + | Алгоритм предлагает каждому прибывшему продавцу цену «бери или вали»; стоимость продавца для товара является независимой выборкой из | ||
| + | некоторого фиксированного (но неизвестного) распределения. | ||
| − | + | Цель — максимизировать количество купленных товаров. | |
| + | |||
| + | Эта проблема особенно актуальна для развивающейся области краудсорсинга, где агенты соответствуют (относительно недорогим) работникам на краудсорсинговой платформе, такой как Amazon Mechanical Turk, а покупаемые/продаваемые «предметы» соответствуют простым заданиям («микрозадачам»), которые могут быть выполнены этими работниками. | ||
| + | |||
| + | Алгоритм соответствует «клиенту»: субъекту, который подает задания и получает выгоду от их выполнения. | ||
| + | |||
| + | Базовая формулировка допускает различные обобщения, например, на несколько типов заданий. | ||
| + | |||
| + | Мы также | ||
| + | * рассматриваем альтернативную модель, в которой заказчик публикует предложения для всей толпы. | ||
| + | * Моделируем динамические проблемы закупок как проблемы многорукого бандита с бюджетным ограничением. | ||
| + | * определяем «бандиты с ранцами»: широкий класс задач многорукого бандита с ограничениями на использование ресурсов в стиле ранца, который включает в себя динамические закупки и множество других приложений. | ||
| + | |||
| + | Отличительной особенностью нашей задачи, по сравнению с существующей литературой по минимизации сожалений, является то, что оптимальная политика для данного латентного распределения может значительно превосходить политику, которая играет «оптимальную фиксированную руку». | ||
| + | |||
| + | Следовательно, достижение сублинейного сожаления в задаче «бандит с рюкзаками» значительно сложнее, чем в обычных задачах с бандитами. | ||
| + | |||
| + | Наш основной результат — алгоритм для версии бандита с рюкзаками с конечным числом возможных действий. | ||
| + | |||
| + | Это первично-дуальный алгоритм с мультипликативными обновлениями; сожаление этого алгоритма близко к информационно-теоретическому оптимуму. | ||
| + | Мы выводим следствия для динамических закупок, использующих равномерную дискретизацию цен. | ||
| + | }} | ||
{{enddiv}} | {{enddiv}} | ||
[[Категория:CiteSeerArticles]] | [[Категория:CiteSeerArticles]] | ||
Текущая версия на 14:58, 23 ноября 2021
В базовой версии динамической «задачи закупок» алгоритм имеет бюджет B, который он должен потратить, и сталкивается с n агентами (потенциальными продавцами), которые прибывают последовательно.
Алгоритм предлагает каждому прибывшему продавцу цену «бери или вали»; стоимость продавца для товара является независимой выборкой из некоторого фиксированного (но неизвестного) распределения.
Цель — максимизировать количество купленных товаров.
Эта проблема особенно актуальна для развивающейся области краудсорсинга, где агенты соответствуют (относительно недорогим) работникам на краудсорсинговой платформе, такой как Amazon Mechanical Turk, а покупаемые/продаваемые «предметы» соответствуют простым заданиям («микрозадачам»), которые могут быть выполнены этими работниками.
Алгоритм соответствует «клиенту»: субъекту, который подает задания и получает выгоду от их выполнения.
Базовая формулировка допускает различные обобщения, например, на несколько типов заданий.
Мы также
- рассматриваем альтернативную модель, в которой заказчик публикует предложения для всей толпы.
- Моделируем динамические проблемы закупок как проблемы многорукого бандита с бюджетным ограничением.
- определяем «бандиты с ранцами»: широкий класс задач многорукого бандита с ограничениями на использование ресурсов в стиле ранца, который включает в себя динамические закупки и множество других приложений.
Отличительной особенностью нашей задачи, по сравнению с существующей литературой по минимизации сожалений, является то, что оптимальная политика для данного латентного распределения может значительно превосходить политику, которая играет «оптимальную фиксированную руку».
Следовательно, достижение сублинейного сожаления в задаче «бандит с рюкзаками» значительно сложнее, чем в обычных задачах с бандитами.
Наш основной результат — алгоритм для версии бандита с рюкзаками с конечным числом возможных действий.
Это первично-дуальный алгоритм с мультипликативными обновлениями; сожаление этого алгоритма близко к информационно-теоретическому оптимуму. Мы выводим следствия для динамических закупок, использующих равномерную дискретизацию цен.
…»