Citeseer/Bandits with Knapsacks — Dynamic procurement for crowdsourcing 10.1.1.365.1661
В базовой версии динамической «задачи закупок» алгоритм имеет бюджет B, который он должен потратить, и сталкивается с n агентами (потенциальными продавцами), которые прибывают последовательно.
Алгоритм предлагает каждому прибывшему продавцу цену «бери или вали»; стоимость продавца для товара является независимой выборкой из некоторого фиксированного (но неизвестного) распределения.
Цель — максимизировать количество купленных товаров.
Эта проблема особенно актуальна для развивающейся области краудсорсинга, где агенты соответствуют (относительно недорогим) работникам на краудсорсинговой платформе, такой как Amazon Mechanical Turk, а покупаемые/продаваемые «предметы» соответствуют простым заданиям («микрозадачам»), которые могут быть выполнены этими работниками.
Алгоритм соответствует «клиенту»: субъекту, который подает задания и получает выгоду от их выполнения.
Базовая формулировка допускает различные обобщения, например, на несколько типов заданий.
Мы также
- рассматриваем альтернативную модель, в которой заказчик публикует предложения для всей толпы.
- Моделируем динамические проблемы закупок как проблемы многорукого бандита с бюджетным ограничением.
- определяем «бандиты с ранцами»: широкий класс задач многорукого бандита с ограничениями на использование ресурсов в стиле ранца, который включает в себя динамические закупки и множество других приложений.
Отличительной особенностью нашей задачи, по сравнению с существующей литературой по минимизации сожалений, является то, что оптимальная политика для данного латентного распределения может значительно превосходить политику, которая играет «оптимальную фиксированную руку».
Следовательно, достижение сублинейного сожаления в задаче «бандит с рюкзаками» значительно сложнее, чем в обычных задачах с бандитами.
Наш основной результат — алгоритм для версии бандита с рюкзаками с конечным числом возможных действий.
Это первично-дуальный алгоритм с мультипликативными обновлениями; сожаление этого алгоритма близко к информационно-теоретическому оптимуму. Мы выводим следствия для динамических закупок, использующих равномерную дискретизацию цен.
…»
[ Хронологический вид ]Комментарии
Войдите, чтобы комментировать.