Finite-time Analysis of Kullback-Leibler Upper Confidence Bounds for Optimal Adaptive Allocation with Multiple Plays and Markovian Rewards
Finite-time Analysis of Kullback-Leibler Upper Confidence Bounds for Optimal Adaptive Allocation with Multiple Plays and Markovian Rewards
复制标题
多重游戏和马尔可夫奖励最优自适应分配的 Kullback-Leibler 置信上限有限时间分析
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Vrettos Moulos
中科院分区：
文献类型：
--
作者：
Vrettos Moulos
研究了经典随机多臂强盗问题的一个推广，该问题涉及马尔可夫报酬和多重对策。为了解决这个问题，我们考虑一个指数为基础的自适应分配规则，在每个阶段结合样本均值的计算，和置信上限，使用Kullback-Leibler发散率，马尔可夫武器的固定预期回报。对于单参数指数族马尔科夫链产生的奖励，我们为这种自适应分配规则产生的后悔提供了有限时间上界，揭示了后悔对时间范围的对数依赖性，并且是渐进最优的。对于我们的分析，我们设计了几个浓度的马尔可夫链的结果，包括马尔可夫链的最大不等式，这可能是在自己的权利感兴趣。作为我们的分析的副产品，我们还建立，渐近最优的，有限时间的情况下，多个播放的保证，和IID奖励从一个参数的指数家庭的概率密度。
We study an extension of the classic stochastic multi-armed bandit problem which involves Markovian rewards and multiple plays. In order to tackle this problem we consider an index based adaptive allocation rule which at each stage combines calculations of sample means, and of upper confidence bounds, using the Kullback-Leibler divergence rate, for the stationary expected reward of Markovian arms. For rewards generated from a one-parameter exponential family of Markov chains, we provide a finite-time upper bound for the regret incurred from this adaptive allocation rule, which reveals the logarithmic dependence of the regret on the time horizon, and which is asymptotically optimal. For our analysis we devise several concentration results for Markov chains, including a maximal inequality for Markov chains, that may be of interest in their own right. As a byproduct of our analysis we also establish, asymptotically optimal, finite-time guarantees for the case of multiple plays, and IID rewards drawn from a one-parameter exponential family of probability densities.
有限状态马尔可夫链的Hoeffding不等式及其在马尔可夫强盗中的应用
DOI：
10.1109/isit44484.2020.9173931
发表时间：
2020
期刊：
2020 IEEE International Symposium on Information Theory (ISIT
影响因子：
--
作者：
Moulos, Vrettos
通讯作者：
Moulos, Vrettos