Improvements and Generalizations of Stochastic Knapsack and Markovian Bandits Approximation Algorithms
研究了有限时域下马尔可夫链奖励的多臂匪徒问题，当不允许抢占时给出紧的1/2-ε近似，允许抢占时给出1/12近似，改进了现有三个模型的结果。
We study the multi-armed bandit problem with arms which are Markov chains with rewards. In the finite-horizon setting, the celebrated Gittins indices do not apply, and the exact solution is intractable. We provide approximation algorithms for the general model of Markov decision processes with nonunit transition times. When preemption isn’t allowed, we provide a (1/2 − ε)-approximation, along with an example showing this is tight. When preemption is allowed, we provide a 1/12-approximation, which improves to a 4/27-approximation when transition times are unity. Our model captures the Markovian Bandits model of Gupta et al., the Stochastic Knapsack model of Dean et al., and the Budgeted Learning model of Guha and Munagala. Our algorithms improve existing results in all three areas. In our analysis, we encounter and overcome to our knowledge a new obstacle: an algorithm that provably exists via analytical arguments, but cannot be found in polynomial time.