We study a general Markov game with metric switching costs: in each round, the player adaptively chooses one of several Markov chains to advance with the objective of minimizing the expected cost for at least $k$ chains to reach their target states. If the player decides to play a different chain, an additional switching cost is incurred. The special case in which there is no switching cost was solved optimally by Dumitriu, Tetali, and Winkler [DTW03] by a variant of the celebrated Gittins Index for the classical multi-armed bandit (MAB) problem with Markovian rewards [Gittins 74, Gittins79]. However, for multi-armed bandit (MAB) with nontrivial switching cost, even if the switching cost is a constant, the classic paper by Banks and Sundaram [BS94] showed that no index strategy can be optimal. In this paper, we complement their result and show there is a simple index strategy that achieves a constant approximation factor if the switching cost is constant and $k=1$. To the best of our knowledge, this is the first index strategy that achieves a constant approximation factor for a general MAB variant with switching costs. For the general metric, we propose a more involved constant-factor approximation algorithm, via a nontrivial reduction to the stochastic $k$-TSP problem, in which a Markov chain is approximated by a random variable. Our analysis makes extensive use of various interesting properties of the Gittins index.
翻译:我们研究了一个通用的Markov游戏,其成本为标准转换成本:在每一回合中,玩家都适应性地选择了几个Markov 链条中的一个来推进Markov 奖赏[Gittins 74, Gittins79]。然而,如果玩家决定玩一个不同的链,就会产生额外的转换成本。如果玩家决定玩一个不同的链条,那么,就会产生额外的转换成本。没有转换成本的特殊案例,Dumitriu、Tetali和Winkler[DTW03]以一个备效的Gittins指数变量解决了。对于古典多臂匪盗(MAB)的奖赏问题[Gittins 74, Gittins79]。然而,对于多臂匪队(MAB)以非三重转换成本到达目标状态的预期成本。即使开关成本是固定不变的,银行和Sundarram[BS94]的经典论文表明,没有哪个指数战略是最佳的。在本文中,我们有一个简单的指数战略,如果转换成本不变和美元。 。对于我们的知识来说,这是通过一个不固定的变式的变式的变式战略,我们总的变式的变式的变式的变式的变式的变式的变式的GLF 。