Citeseer/3 Improvements and Generalizations of Stochastic Knapsack and Multi-Armed Bandit Approximation Algorithms (2014) 10.1.1.767.2351

Ссылки сюда (1) →

«3 Improvements and Generalizations of Stochastic Knapsack and Multi-Armed Bandit Approximation Algorithms (2014) 10.1.1.767.2351»^{скачать}

« Проблема многорукого бандита (MAB) представляет собой классический компромисс между разведкой и эксплуатацией.

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

Недавно Gupta получил основанную на линейном программировании 1/484-приближение для MAB-задачи без допущения мартингейла.

Мы улучшили этот алгоритм до 4/27-приближения, с более простым анализом.

Наш алгоритм также обобщается на случай суперпроцессов МАБ с (стохастические) многопериодные действия.

Также мы получили (1/2−ε)-приближение для варианта МАБ, в котором упреждение не допускается. … …»

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.