Q-Learning Lagrange Policies for Multi-Action Restless Bandits
Q-Learning Lagrange Policies for Multi-Action Restless Bandits
复制标题
针对多动作不安强盗贼的 Q-Learning 拉格朗日策略
DOI：
10.1145/3447548.3467370
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
M. Tambe
中科院分区：
文献类型：
--
作者：
J. Killian;Arpita Biswas;Sanket Shah;M. Tambe
多动作不安多臂老虎机 (RMAB) 是一个强大的受限资源分配框架，其中管理 N 个独立进程。然而，以前的工作仅研究问题动态已知的离线设置。我们解决了这个限制性假设，设计了第一个算法，使用拉格朗日松弛和 Q 学习的组合在线学习多动作 RMAB 的良好策略。我们的第一种方法 MAIQL 将二元操作 RMAB 中 Q 学习 Whittle 索引的方法扩展到多操作设置。我们推导出广义更新规则和收敛证明，并确定在标准假设下，当 t → ∞ 时，MAIQL 收敛到渐近最优多动作 RMAB 策略。然而，MAIQL 依赖于在两个时间尺度上学习 Q 函数和索引，这导致收敛速度慢，并且需要问题结构才能表现良好。因此，我们设计了第二种算法 LPQL，它通过 Q 学习的变体学习最小化拉格朗日界限，从而学习多动作 RMAB 的性能良好且更通用的拉格朗日策略。为了确保快速收敛，我们采用了一种能够在单个时间尺度上进行学习的近似策略，然后保证将近似精度与 LPQL 的返回上限（t → ∞）相关联。最后，我们表明，我们的方法在多种设置中始终优于基线，包括源自真实世界药物依从性数据的方法。
Multi-action restless multi-armed bandits (RMABs) are a powerful framework for constrained resource allocation in which N independent processes are managed. However, previous work only study the offline setting where problem dynamics are known. We address this restrictive assumption, designing the first algorithms for learning good policies for Multi-action RMABs online using combinations of Lagrangian relaxation and Q-learning. Our first approach, MAIQL, extends a method for Q-learning the Whittle index in binary-action RMABs to the multi-action setting. We derive a generalized update rule and convergence proof and establish that, under standard assumptions, MAIQL converges to the asymptotically optimal multi-action RMAB policy as t → ∞. However, MAIQL relies on learning Q-functions and indexes on two timescales which leads to slow convergence and requires problem structure to perform well. Thus, we design a second algorithm, LPQL, which learns the well-performing and more general Lagrange policy for multi-action RMABs by learning to minimize the Lagrange bound through a variant of Q-learning. To ensure fast convergence, we take an approximation strategy that enables learning on a single timescale, then give a guarantee relating the approximation's precision to an upper bound of LPQL's return as t → ∞. Finally, we show that our approaches always outperform baselines across multiple settings, including one derived from real-world medication adherence data.
排队控制和资产管理的可索引性的一般概念
DOI：
10.1214/10-aap705
发表时间：
2011
期刊：
The Annals of Applied Probability
影响因子：
--
作者：
Glazebrook K
通讯作者：
Glazebrook K