5 papers
Lyapunov-Based Sample Complexity Analysis for Weakly-Coupled MDPs
Tianhao Wu, Matthew Zurek, Weina Wang +1
We study the sample complexity of learning in average-reward weakly-coupled Markov decision processes (WCMDPs) and Restless Bandits (RBs) under a generative model. Naive reduction…
Optimality of a Threshold Policy for a Queueing System with One Fast Server and Two Identical Slow Servers
Weina Wang, Taha Ameen, Yudong Chen +3
This paper studies the optimal control problem of a queueing system with three servers: one fast server and two identical slow servers. The two-server version of this problem, with…
Unichain and Aperiodicity are Sufficient for Asymptotic Optimality of Average-Reward Restless Bandits
Yige Hong, Qiaomin Xie, Yudong Chen +1
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 subs…
Projection-based Lyapunov method for fully heterogeneous weakly-coupled MDPs
Xiangcheng Zhang, Yige Hong, Weina Wang
Heterogeneity poses a fundamental challenge for many real-world large-scale decision-making problems but remains largely understudied. In this paper, we study the fully heterogeneo…
Achieving Exponential Asymptotic Optimality in Average-Reward Restless Bandits without Global Attractor Assumption
Yige Hong, Qiaomin Xie, Yudong Chen +1
We consider the infinite-horizon average-reward restless bandit problem. We propose a novel \emph{two-set policy} that maintains two dynamic subsets of arms: one subset of arms has…