标题： 对 restless Markov 棒球的遗憾界限 显示英文标题

标题： Regret Bounds for Restless Markov Bandits

摘要： 我们考虑非静止马尔可夫老虎机问题，其中每个杠杆的状态根据马尔可夫过程独立于学习者的动作演变。 我们提出一种算法，在$T$步骤后相对于知道所有杠杆分布的最佳策略实现了$\tilde{O}(\sqrt{T})$的遗憾。 除了马尔可夫链是不可约的外，没有对马尔可夫链做出其他假设。 此外，我们证明基于索引的策略对于所考虑的问题来说本质上是次优的。 显示英文摘要

摘要： We consider the restless Markov bandit problem, in which the state of each arm evolves according to a Markov process independently of the learner's actions. We suggest an algorithm that after $T$ steps achieves $\tilde{O}(\sqrt{T})$ regret with respect to the best policy that knows the distributions of all arms. No assumptions on the Markov chains are made except that they are irreducible. In addition, we show that index-based policies are necessarily suboptimal for the considered problem.