Просмотр исходного текста страницы Citeseer/3 Improvements and Generalizations of Stochastic Knapsack and Multi-Armed Bandit Approximation Algorithms (2014) 10.1.1.767.2351

{{checked|}}
{{citeseerlink|citeseer/3 Improvements and Generalizations of Stochastic Knapsack and Multi-Armed Bandit Approximation Algorithms (2014) 10.1.1.767.2351|<html>

Проблема многорукого бандита (MAB) представляет собой классический компромисс между разведкой и эксплуатацией.  
<p>
Входные данные определяют несколько стохастических плеч, которые развиваются с каждым рывком, и цель состоит в том, чтобы максимизировать ожидаемое вознаграждение после фиксированного бюджета тяги.  Знаменитая работа [GGW89] предполагает «условие на руки», называемое допущением мартингейла.
<p>
Недавно Gupta получил основанную на линейном программировании 1/484-приближение для MAB-задачи без допущения мартингейла.
<p>
Мы улучшили этот алгоритм до 4/27-приближения, с более простым анализом.  
<p>
Наш алгоритм также обобщается на случай суперпроцессов МАБ с (стохастические) многопериодные действия.  
<p>
Также мы получили (1/2−ε)-приближение для варианта МАБ, в котором упреждение не допускается.
…
</html>}}
{{enddiv}}

[[Категория:CiteSeerArticles]]