Citeseer/3 Improvements and Generalizations of Stochastic Knapsack and Multi-Armed Bandit Approximation Algorithms (2014) 10.1.1.767.2351 — различия между версиями
StasFomin (обсуждение | вклад) (Новая страница: «{{checked|}} {{citeseerlink|citeseer/3 Improvements and Generalizations of Stochastic Knapsack and Multi-Armed Bandit Approximation Algorithms (2014) 10.1.1.767.2…») |
StasFomin (обсуждение | вклад) |
||
| Строка 2: | Строка 2: | ||
{{citeseerlink|citeseer/3 Improvements and Generalizations of Stochastic Knapsack and Multi-Armed Bandit Approximation Algorithms (2014) 10.1.1.767.2351|<html> | {{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>}} | </html>}} | ||
{{enddiv}} | {{enddiv}} | ||
[[Категория:CiteSeerArticles]] | [[Категория:CiteSeerArticles]] | ||
Текущая версия на 09:53, 23 ноября 2021
«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−ε)-приближение для варианта МАБ, в котором упреждение не допускается. … …»