💻 computer science

Robust Restless Multi-Armed Bandit for Data Center Flexibility Services Through Virtual Machine Scheduling

This paper proposes a robust restless multi-armed bandit framework that combines Whittle-index policies with a global upper confidence bound strategy to enable data centers to provide flexible load reduction services to the power grid while effectively handling uncertain resource utilization and quality-of-service constraints.

Original authors: Yifu Ding, Zixi Chen, Thomas Magnanti

Published 2026-05-20

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Yifu Ding, Zixi Chen, Thomas Magnanti

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a massive, high-stakes game of "Musical Chairs" played not with people, but with thousands of computer jobs running inside data centers.

Here is the story of the paper, broken down into simple concepts:

The Big Problem: The Grid is Thirsty

Think of the electrical grid as a giant water pipe. Sometimes, the pipe gets too full (too much demand), and it needs to be drained quickly to avoid bursting. Data centers are like giant factories that guzzle electricity. When the grid is stressed, it asks these factories to "turn down the faucet" for a few minutes.

But there's a catch: The grid operator (the person asking for the water cut) doesn't know exactly what's happening inside the factory. They can't see every single machine or job. They only see the "big picture" (like, "Factory A is using a lot of power right now"). If the factory manager tries to move jobs around to save power, they might accidentally slow down a customer's video call or delay a file upload. This is the "Quality of Service" (QoS) loss. The factory doesn't want to tell the grid operator exactly how they are moving jobs because that's their secret recipe.

The Solution: A Smart "Slot Machine" Game

The authors propose a new way to play this game using a concept called a Restless Multi-Armed Bandit (RMAB).

The Analogy: Imagine you are in a casino with 10 different slot machines (the data centers). You only have enough coins to pull 3 levers (ask 3 data centers to reduce power) at a time.
The Twist: These machines are "restless." Even when you don't pull their lever, they keep changing. A machine that was "hot" (easy to reduce power) might become "cold" (hard to reduce power) just because the jobs inside it changed.
The Goal: You need to figure out which 3 machines to pull right now to get the most power savings without breaking the machines (causing too much delay for customers).

The Challenge: Learning in the Dark

The grid operator doesn't know the rules of the slot machines. They have to learn them while playing.

The Old Way (Thompson-Whittle): This is like a student who tries to memorize the rules of every machine by watching them for a long time. It's smart, but at the very beginning, the student is guessing wildly and making mistakes.
The Problem: If the student guesses wrong early on, they lose a lot of "coins" (money/power) before they figure it out. Also, if the information they get is "noisy" (like a bad radio signal), they get confused easily.

The New Trick: The "Trust-Mixed" Strategy

The authors created a new player called TM-TW (Trust-Mixed Thompson-Whittle). Think of this player as a hybrid driver:

Phase 1: The Cautious Explorer (Early Game): When the driver first starts, they don't trust their complex map (the learned rules) yet. Instead, they rely on a "GPS" that looks at the big picture (Global UCB) and the immediate traffic (Local UCB). They take safe, smart bets based on what they can see right now.
Phase 2: The Gradual Shift: As the driver gets more experience and the map becomes clearer, they slowly stop relying on the GPS and start trusting their own learned map.
Phase 3: The Expert (Late Game): Eventually, the driver relies entirely on their complex, learned map (the Whittle Index), which is the most efficient way to play.

Why is this cool? It combines the safety of a beginner with the efficiency of an expert. It doesn't wait to be perfect before it starts making good moves.

What the Results Show

The authors tested this using real data from Microsoft's Azure cloud (thousands of real computer jobs).

Beating the Competition: Their new "hybrid driver" (TM-TW) consistently earned more "coins" (power savings) than the old "student" (TW) and a simple guesser (ST).
Handling Noise: When the data was messy or "noisy" (like a bad connection), the old methods got confused and made bad choices. The new method stayed calm and kept performing well because it didn't rely only on the messy data; it also looked at the bigger picture.
Beating the "Black Box": They compared their method to a famous AI strategy called EXP4 (which just picks the best performer from a list of experts). Their method learned faster and ended up with better results because it understood the structure of the problem, not just the history of who won.

The Bottom Line

This paper presents a smart, adaptive way for power grids to ask data centers to save energy without needing to know their secret internal recipes. By using a "trust-mixed" learning strategy, the system learns quickly, handles messy data well, and saves more energy than previous methods, all while keeping the data centers' internal operations private.

The authors even shared their code (called RACER) so others can try it out and see the results for themselves.

Technical Summary: Robust Restless Multi-Armed Bandit for Data Center Flexibility Services

Problem Statement
The paper addresses the challenge of coordinating demand response (DR) from data centers to balance electric grid supply and demand. While rescheduling Virtual Machine (VM) jobs within data centers offers a mechanism for load reduction, real-time implementation is hindered by two factors: (1) the uncertainty of fluctuating resource utilization, and (2) the reluctance of providers to disclose detailed job-rescheduling procedures due to privacy concerns. Consequently, grid operators lack access to granular, job-level data, possessing only aggregated, batch-level information (e.g., average power consumption and flexibility tiers). The core problem is formulated as a sequential decision-making task under uncertainty where the grid operator must select a limited subset of data centers to activate for load reduction without observing their internal state transitions or detailed rescheduling logic.

Methodology
The authors propose a Contextual Restless Multi-Armed Bandit (RMAB) framework to model this interaction.

MDP Formulation: Each data center is modeled as an "arm" in a Markov Decision Process (MDP). The state represents the position in a cyclic job queue, and the action is a binary decision to activate (request load reduction) or remain passive. The reward is the net benefit of rescheduling (power savings minus Quality-of-Service penalties).
The Indexability Challenge: Solving the joint optimization of $N$ data centers is computationally intractable due to the exponential growth of the joint state space ( $|S|^N$ ). To address this, the authors utilize Whittle index policies, which decompose the problem into independent single-arm sub-problems under a passivity subsidy.
Learning under Uncertainty: Since the reward and transition functions are unknown, the framework employs Thompson Sampling to learn the underlying dynamics.
- Thompson-Whittle (TW): The algorithm samples from posterior distributions of the reward and transition functions (modeled via Gaussian and Dirichlet-Categorical priors, respectively) to compute Whittle indices.
- Trust-Mixed Thompson-Whittle (TM-TW): Recognizing that TW suffers from volatility and slow learning in early stages due to noisy transition models in large state spaces, the authors introduce a mixed strategy. This approach blends the learned Whittle score with a greedy, uncertainty-aware score derived from Global and Local Upper Confidence Bounds (UCB). A trust coefficient ( $\tau_t$ ) linearly decays over time, shifting the policy from a greedy exploration phase (relying on observable rewards) to a pure Whittle exploitation phase as the model becomes reliable.

Key Contributions

Privacy-Preserving Framework: The paper develops a contextual RMAB framework that enables flexible demand response using real-world VM datasets while respecting privacy. The grid operator utilizes only aggregated batch-level features rather than detailed job-level data.
Enhanced Learning Policy: The authors propose the TM-TW algorithm, which augments the standard Thompson-Whittle index policy with complementary UCB strategies. This hybrid approach significantly improves performance during the early learning stage, particularly in settings with large state spaces.
Robustness Validation: The study demonstrates that the proposed algorithm maintains robustness across varying state-space sizes and noisy contextual information, outperforming both pure Thompson-Whittle and state-of-the-art EXP4 frameworks.

Results
Using the Microsoft Azure VM dataset, the authors conducted extensive simulations with varying numbers of data centers (3 to 10) and activation budgets.

Performance: The TM-TW strategy consistently achieved the highest cumulative rewards, outperforming the pure TW algorithm by 0.19% to 2.14% across different configurations and significantly outperforming the Contextual Bandit (ST) baseline.
Comparison with EXP4: In ablation studies, TM-TW achieved 95.82% of the theoretical Oracle Whittle benchmark, whereas the EXP4 framework (which treats policies as black-box experts) reached only 79.40%. TM-TW demonstrated superior stability, whereas EXP4 plateaued earlier.
Sensitivity Analysis:
- State Space Size: As the number of VM jobs increased (expanding the state space), TM-TW maintained a performance advantage over TW and ST, though computation time for index-based policies increased quadratically.
- Noise Robustness: When state observations were contaminated with Gaussian noise (up to 40% error probability), TM-TW demonstrated the strongest robustness. Notably, under noise levels exceeding 0.15, TM-TW even surpassed the Oracle Whittle policy (which relies on perfect state knowledge but suffers from corrupted index lookups), attributed to the greedy UCB component's ability to mitigate corrupted contextual information.

Significance and Claims
The paper claims that the proposed TM-TW algorithm offers a practical solution for coordinating data center flexibility services where detailed internal data is unavailable. By combining the long-horizon optimality of Whittle indices with the short-term reliability of UCB exploration, the method overcomes the "curse of dimensionality" and the "cold start" problem inherent in learning-based RMABs. The authors note that while the algorithm shows strong empirical performance and robustness, further theoretical regret analysis is required to fully understand its guarantees, which they identify as future work. The code for the framework (RACER) is provided as open-source to ensure reproducibility.