Model Predictive Control is Almost Optimal for Restless Bandit
We consider the discrete time infinite horizon average reward restless markovian bandit (RMAB) problem. We propose a \emph{model predictive control} based non-stationary policy with a rolling computational horizon $\tau$. At each time-slot, this policy solves a $\tau$ horizon linear program whose first control value is kept as a control for the RMAB. Our solution requires minimal assumptions and quantifies the loss in optimality in terms of $\tau$ and the number of arms, $N$. We show that its sub-optimality gap is $O(1/\sqrt{N})$ in general, and $\exp(-\Omega(N))$ under a local-stability condition. Our proof is based on a framework from dynamic control known as \emph{dissipativity}. Our solution easy to implement and performs very well in practice when compared to the state of the art. Further, both our solution and our proof methodology can easily be generalized to more general constrained MDP settings and should thus, be of great interest to the burgeoning RMAB community.
Code (0)
등록된 구현이 없습니다.
Tasks
Model Predictive ControlSimilar Papers 제목 키워드 기반
Model Predictive Control is almost Optimal for Heterogeneous Restless Multi-armed Bandits
We consider a general infinite horizon Heterogeneous Restless multi-armed Bandit (RMAB). Heterogeneity is a fundamental problem for many real-world systems largely because it resists many concentration arguments. In this…
Multi-Armed BanditsOptimal Adaptive Learning in Uncontrolled Restless Bandit Problems
In this paper we consider the problem of learning the optimal policy for uncontrolled restless bandit problems. In an uncontrolled restless bandit problem, there is a finite set of arms, each of which when pulled yields …
NeurWIN: Neural Whittle Index Network For Restless Bandits Via Deep RL
Whittle index policy is a powerful tool to obtain asymptotically optimal solutions for the notoriously intractable problem of restless bandits. However, finding the Whittle indices remains a difficult problem for many pr…
Deep Reinforcement LearningMARBLE: Multi-Armed Restless Bandits in Latent Markovian Environment
Restless Multi-Armed Bandits (RMABs) are powerful models for decision-making under uncertainty, yet classical formulations typically assume fixed dynamics, an assumption often violated in nonstationary environments. We i…
Multi-Armed BanditsAchieving Exponential Asymptotic Optimality in Average-Reward Restless Bandits without Global Attractor Assumption
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 a nearly optimal state distribution and…