Robust Restless Multi-Armed Bandit for Data Center Flexibility Services Through Virtual Machine Scheduling
Zixi Chen, Yifu Ding, Thomas Magnanti · 2026
Read Robust Restless Multi-Armed Bandit for Data Center Flexibility Services Through Virtual Machine Scheduling by Zixi Chen, Yifu Ding, Thomas Magnanti (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-19116.txt.
Introduction
Zixi Chen, Yifu Ding, and Thomas Magnanti frame data-centre demand response as a restless bandit problem: the grid requests load cuts without seeing each centre's rescheduling details. Each centre becomes an arm in a Markov decision process, with Whittle-index policies learned by Thompson sampling on virtual-machine data. A mixed strategy adds an upper confidence bound and trust indices to speed learning across state spaces. The mixed algorithm stays robust across state-space sizes, beats pure Thompson-Whittle under noisy context, and outperforms EXP4, with code released.
Catalog record
| CREATOR | Zixi Chen, Yifu Ding, Thomas Magnanti |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 31602 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.19116
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Robust Restless Multi-Armed Bandit for Data Center Flexibility Services Through Virtual Machine Scheduling Zixi Chen, Yifu Ding, Thomas Magnanti Abstract Energy demands from data centers have surged and stressed the grid in recent years. Electric grids require balancing supply and demand every second, motivating demand response (reduction) from large loads, including data centers. This can be achieved by rescheduling jobs on physical machines. Its real-time implementation is uncertain due to fluctuating resource utilization, and rescheduling incurs quality-of-service (QoS) losses that providers are unwilling to disclose. We propose a restless multi-arm bandit (RMAB) framework in which the grid operator requests load reductions without access to detailed job-rescheduling procedures. Using the open-source virtual machine (VM) datasets, we model job arrivals and rescheduling at each data center as a restless arm in a Markov decision process (MDP), and derive Whittle-index-based policies based on the learned transition function via Thompson sampling. To overcome the weakness of an increasingly long learning process due to an enlarged state space, we used a mixed strategy that included a global upper confidence bound (UCB) encoded with trust indices to enhance robustness and accelerate learning. Results show that the proposed mixed-strategy algorithm remains robust across varying state-space sizes and consistently outperforms the pure Thompson-Whittle (TW) algorithm, especially when contextual information is noisy. It also demonstrates superior performance compared to the state-of-the-art EXP4 framework. We provided an open-sourced code for reproducibility. Keywords: Data centers, VM scheduling, RMAB, Thompson learning, Mixed strategies I Introduction This letter proposes a contextual RMAB framework for coordinating flexible, privacy-preserving data center demand responses through VM rescheduling. A VM is a software-defined machine that operates within a physical server as an independent computing unit, characterized by heterogeneous features such as CPU or GPU utilization and memory usage. Within a data center, VM rescheduling can improve both service quality and resource efficiency by reallocating workloads to more suitable configurations. Recent demonstrations using workload power orchestration software show that job rescheduling within a single data center can directly respond to grid power reduction signals [ 1 ] . In our framework, the grid operator does not observe the underlying rescheduling process, but instead has access only to aggregated, batch-level VM information, such as job flexibility tiers and average power consumption. Moreover, grid operators commonly procure flexibility services from multiple data centers to improve cost-effectiveness and operational performance. I-A Related works A restless multi-armed bandit (RMAB) is a sequential decision-making framework used to allocate limited resources across multiple dynamically evolving processes under uncertainty. For instance, ref. [ 2 ] formulates a stochastic deadline scheduling problem as an RMAB, where jobs arrive randomly at a service center and are characterized by stochastic rewards and completion deadlines. A key challenge in RMAB problems is their computational intractability as the state space grows. To address this issue, closed-form, near-optimal index policies have been developed, offering computational tractability together with provable bounds on the performance gap relative to the true optimum [ 3 ] . This involves proving the indexability of RMAB problem and calculating the Whittle index for each arm. The RMAB has been widely applied to model demand responses in electric grids, where load states are only partially observable. Ref. [ 4 ] was among the first to introduce an index-based policy within the RMAB framework for demand responses through thermostatically controlled loads (TCLs). More recently, ref. [ 5 ] proposed an online learning algorithm for RMAB-based building demand responses that estimates the index-based policy under unknown state transition dynamics, assuming access to perfect global and local contextual information. The main contributions of this paper are threefold. First, we developed a contextual RMAB framework that enables flexible and privacy-preserving data center flexibility services using real-world VM datasets. Instead of disclosing detailed job-level features, the grid operator has access to aggregated batch-level features. Second, we proposed a learning-based index policy augmented with complementary UCB strategies that significantly improve performance during the early learning stage, particularly in large state-space settings. Third, the proposed algorithm demonstrates strong robustness across various sensitivity analyses, including changes in problem scale, arm-context noise levels, and policy weights. II Methodology II-A VM (re)scheduling as a Markov decision process Given a set of VMs \mathcal{V}=\{v_{1},v_{2},...,v_{m}\} , each has heterogeneous power consumptions p and QoS costs c per core hour. These VM jobs are deployed on \mathcal{N} data centers, and we could model (re)scheduling of each data center as MDP, defined by a tuple (\mathcal{S},\mathcal{A},P,R,\beta) , where \mathcal{S} is the state space, \mathcal{A} is the action space, P(s^{\prime}\mid s,a) is the transition kernel, R(s,a) is the one-step reward, and \beta\in(0,1] is the discount factor. The grid could take the action a\in\mathcal{A} to request services from each data center. At time t\in\mathcal{T} , without the grid request, each data center executes a batch of N_{j} VM tasks in the cyclic job queue consecutively. If the grid requests the service, the data center responds by looking ahead to the next N_{f}\geq N_{j} jobs and selecting the jobs with the lowest power consumption, using the saved power to meet the grid request. The detailed definitions of MDP is given by, • States (s_{t}) : Position s_{i} in the circular job queue, representing the current batch of N_{j} jobs. • Actions (a_{t}) : The binary decision variable a_{i} indicates whether data center i receives a request from the grid. When a_{i}=0 , data center i executes the default next N_{j} jobs in the queue. The data center is activated if a_{i}=1 or passive if a_{i}=0 . • Rewards (r_{t}) : When a_{i}=0 , the reward is always zero. When a_{i}=1 , the reward is defined as the net benefit from rescheduling, computed as the power savings minus the delay penalty associated with any interactive jobs skipped during reordering. The detailed rescheduling process is illustrated in Appendix, Section V-B . A few underlying assumptions are made: (1) the state space of data centers is finite, implying that the job queue at each data center follows a recurring pattern over time; (2) rescheduling under the same hardware configuration does not alter the power consumption of VM jobs; and (3) the framework models real-time interactions between the grid operator and data centers, where each RMAB learning round corresponds to a grid request. We assume that the duration of each demand response event is shorter than the interval between consecutive requests, such that individual grid requests can be treated as independent. II-B Model formulation II-B 1 RMAB problem At time t\in\mathcal{T} , the grid sends requests to a pre-determined, limited number of data centers N_{t}\leq\mathcal{N} , depending on the grid conditions. The multi-armed bandit problem \mathcal{M} is formulated as, \displaystyle(\mathcal{M})\quad\text{obj.} \displaystyle\max_{\pi}\mathbb{E}_{\pi}\sum^{\infty}_{t=0}\sum^{\mathcal{N}}_{i=1}\{\beta^{t}r_{i,t}a_{i,t}\} (1) \displaystyle\text{s.t.} \displaystyle\sum^{\mathcal{N}}_{i=1}a_{i,t}\leq N_{t} \displaystyle r_{i,t}=R_{i}(a_{i,t},s_{i,t}) The objective is to design a control policy \pi that maximizes the long-term cumulative discounted reward, given the per-round reward r_{i,t} and discount factor \beta . The state transition of each arm depends on whether the corresponding data center is activated. Specifically, P_{i}^{1}(\cdot\mid s) denotes the transition function under activation, while P_{i}^{0}(\cdot\mid s) denotes the transition function when the arm remains passive. In our framework, the reward function R_{i} and transition function are assumed to be unknown; otherwise, the problem reduces to a standard dynamic optimization problem. Lamma 1 (Intractability): In the