Unichain and Aperiodicity are Sufficient for Asymptotic Optimality of Average-Reward Restless Bandits
arXiv:2402.05689v4 Announce Type: replace Abstract: We consider the infinite-horizon, average-reward restless bandit problem in discrete time. We propose a new class of policies that are designed to drive a progressively larger subset of arms toward the optimal distribution. We show that our policies are asymptotically optimal with an $O(1/\sqrt{N})$ optimality gap for an $N$-armed problem, assuming only a unichain and aperiodicity assumption. Our approach departs from most existing work that focuses on index or priority policies, which rely on the Global Attractor Property (GAP) to guarantee — Yige Hong, Qiaomin Xie, Yudong Chen, Weina Wang
View PDF
Abstract:We consider the infinite-horizon, average-reward restless bandit problem in discrete time. We propose a new class of policies that are designed to drive a progressively larger subset of arms toward the optimal distribution. We show that our policies are asymptotically optimal with an $O(1/\sqrt{N})$ optimality gap for an $N$-armed problem, assuming only a unichain and aperiodicity assumption. Our approach departs from most existing work that focuses on index or priority policies, which rely on the Global Attractor Property (GAP) to guarantee convergence to the optimum, or a recently developed simulation-based policy, which requires a Synchronization Assumption (SA).
Comments: 68 pages, 17 figures
Subjects:
Machine Learning (cs.LG); Optimization and Control (math.OC); Probability (math.PR)
MSC classes: 90C40 (Primary) 90B15, 60J10, 93E20 (Secondary)
ACM classes: G.3; I.6
Cite as: arXiv:2402.05689 [cs.LG]
(or arXiv:2402.05689v4 [cs.LG] for this version)
https://doi.org/10.48550/arXiv.2402.05689
arXiv-issued DOI via DataCite
Related DOI:
https://doi.org/10.1287/moor.2024.0678
DOI(s) linking to related resources
Submission history
From: Yige Hong [view email] [v1] Thu, 8 Feb 2024 14:07:20 UTC (4,081 KB) [v2] Thu, 13 Jun 2024 17:43:45 UTC (1,265 KB) [v3] Thu, 3 Oct 2024 17:37:33 UTC (2,830 KB) [v4] Mon, 30 Mar 2026 02:35:52 UTC (2,522 KB)
Sign in to highlight and annotate this article
Conversation starters
Daily AI Digest
Get the top 5 AI stories delivered to your inbox every morning.
Knowledge Map
Connected Articles — Knowledge Graph
This article is connected to other articles through shared AI topics and tags.
Discussion
Sign in to join the discussion
No comments yet — be the first to share your thoughts!