将随机博弈重构为上下文阈值带，实现更快收敛与更高收益。
From Restless to Contextual: A Thresholding Bandit Reformulation For Finite-horizon Improvement
- 把复杂状态转移简化为单标量奖励，降低学习难度。
- 在异构多状态环境中实现次线性损失，收敛速度更快。
- 适合大规模动态环境中的高效决策任务。
本文针对现有在线随机博弈（RB）算法在有限时域内表现不佳的问题，指出其根源在于学习完整马尔可夫决策过程（MDP）所需的过高样本复杂度。我们提出将在线RB重新建模为预算约束的上下文阈值带问题，通过将长期状态转移编码为标量奖励来简化学习过程。我们证明了简化有限时域设定下最优策略的首个非渐近最优性。在异构代理、多状态场景下提出一种实用学习策略，证明其具有次线性遗憾，实现比现有方法更快的收敛。在大规模异构环境中实证验证，显著优于当前最优算法，带来更高的累计收益。代码已开源（github）。本工作为有限时域随机博弈中实现高效、低样本学习提供了新路径。
原文摘要 · Abstract (English)
This paper addresses the poor finite-horizon performance of existing online \emph{restless bandit} (RB) algorithms, which stems from the prohibitive sample complexity of learning a full \emph{Markov decision process} (MDP) for each agent. We argue that superior finite-horizon performance requires \emph{rapid convergence} to a \emph{high-quality} policy. Thus motivated, we introduce a reformulation of online RBs as a \emph{budgeted thresholding contextual bandit}, which simplifies the learning problem by encoding long-term state transitions into a scalar reward. We prove the first non-asymptotic optimality of an oracle policy for a simplified finite-horizon setting. We propose a practical learning policy under a heterogeneous-agent, multi-state setting, and show that it achieves a sublinear regret, achieving \emph{faster convergence} than existing methods. This directly translates to higher cumulative reward, as empirically validated by significant gains over state-of-the-art algorithms in large-scale heterogeneous environments. The code is provided in \href{https://github.com/jamie01713/EGT}{github}. Our work provides a new pathway for achieving practical, sample-efficient learning in finite-horizon RBs.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。