An asymptotically optimal heuristic for general nonstationary finite-horizon restless multi-armed, multi-action bandits
An asymptotically optimal heuristic for general nonstationary finite-horizon restless multi-armed, multi-action bandits
复制标题
一般非平稳有限视野不安定多臂多动作老虎机的渐近最优启发式
DOI：
--
复制
发表时间：
2017
影响因子：
1.2
通讯作者：
Guihua Wang
中科院分区：
文献类型：
--
作者：
Gabriel Zayas;Stefanus Jasin;Guihua Wang
摘要针对一类具有离散时间和有限状态的不宁多臂强盗问题，提出了一种渐近最优启发式算法，称为随机分配控制（RAC）。它是用原始随机控制公式的线性规划松弛来构造的。与大多数现有文献相反，我们考虑了一个具有多个动作和在每个时间段可以激活的强盗数量的时间相关（即非平稳）上界的有限视界问题；事实上，我们的分析也可以应用于具有非平稳转移矩阵和非平稳成本函数的情况。渐近设置是通过让强盗数目和其他相关参数增长到无穷大而得到的。我们的主要贡献是RAC在这种一般情况下的渐近最优性不需要索引性或底层马尔可夫链（如单链）或流体近似（如全局稳定吸引子）的通常稳定性条件。此外，我们的多动作设置并不局限于通常的主导动作概念。最后，我们证明RAC对于动态种群也是渐近最优的，其中强盗可以随机到达和离开系统。
Abstract We propose an asymptotically optimal heuristic, which we term randomized assignment control (RAC) for a restless multi-armed bandit problem with discrete-time and finite states. It is constructed using a linear programming relaxation of the original stochastic control formulation. In contrast to most of the existing literature, we consider a finite-horizon problem with multiple actions and time-dependent (i.e. nonstationary) upper bound on the number of bandits that can be activated at each time period; indeed, our analysis can also be applied in the setting with nonstationary transition matrix and nonstationary cost function. The asymptotic setting is obtained by letting the number of bandits and other related parameters grow to infinity. Our main contribution is that the asymptotic optimality of RAC in this general setting does not require indexability properties or the usual stability conditions of the underlying Markov chain (e.g. unichain) or fluid approximation (e.g. global stable attractor). Moreover, our multi-action setting is not restricted to the usual dominant action concept. Finally, we show that RAC is also asymptotically optimal for a dynamic population, where bandits can randomly arrive and depart the system.