Citeseer/Bandits with Knapsacks — Dynamic procurement for crowdsourcing 10.1.1.365.1661 — различия между версиями

«Bandits with Knapsacks — Dynamic procurement for crowdsourcing 10.1.1.365.1661»^{скачать}

В базовой версии динамической «задачи закупок» алгоритм имеет бюджет B, который он должен потратить, и сталкивается с n агентами (потенциальными продавцами), которые прибывают последовательно.

Алгоритм предлагает каждому прибывшему продавцу цену «бери или вали»; стоимость продавца для товара является независимой выборкой из некоторого фиксированного (но неизвестного) распределения.

Цель — максимизировать количество купленных товаров.

Эта проблема особенно актуальна для развивающейся области краудсорсинга, где агенты соответствуют (относительно недорогим) работникам на краудсорсинговой платформе, такой как Amazon Mechanical Turk, а покупаемые/продаваемые «предметы» соответствуют простым заданиям («микрозадачам»), которые могут быть выполнены этими работниками.

Алгоритм соответствует «клиенту»: субъекту, который подает задания и получает выгоду от их выполнения.

Базовая формулировка допускает различные обобщения, например, на несколько типов заданий.

Мы также

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

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

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

Наш основной результат — алгоритм для версии бандита с рюкзаками с конечным числом возможных действий.

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