Citeseer/3 Improvements and Generalizations of Stochastic Knapsack and Multi-Armed Bandit Approximation Algorithms (2014) 10.1.1.767.2351
«3 Improvements and Generalizations of Stochastic Knapsack and Multi-Armed Bandit Approximation Algorithms (2014) 10.1.1.767.2351»скачать
Входные данные определяют несколько стохастических плеч, которые развиваются с каждым рывком, и цель состоит в том, чтобы максимизировать ожидаемое вознаграждение после фиксированного бюджета тяги. Знаменитая работа [GGW89] предполагает «условие на руки», называемое допущением мартингейла.
Недавно Gupta получил основанную на линейном программировании 1/484-приближение для MAB-задачи без допущения мартингейла.
Мы улучшили этот алгоритм до 4/27-приближения, с более простым анализом.
Наш алгоритм также обобщается на случай суперпроцессов МАБ с (стохастические) многопериодные действия.
Также мы получили (1/2−ε)-приближение для варианта МАБ, в котором упреждение не допускается. … …»
[ Хронологический вид ]Комментарии
Войдите, чтобы комментировать.