Learning to Score: Tuning Cluster Schedulers through Reinforcement Learning

This paper proposes a reinforcement learning approach that automatically tunes cluster scheduler scoring weights using percentage improvement rewards, frame-stacking, and limited domain information to significantly improve end-to-end job performance across diverse workloads and cluster setups.

The Gist

Imagine you are the manager of a massive, chaotic warehouse (a computer cluster) filled with thousands of workers (nodes) and a constant stream of packages (jobs) arriving every second. Your goal is to get every package to the right worker as fast as possible.

In the old days, the manager used a rulebook (the scheduler) to decide who gets which package. This rulebook had a list of criteria: "Is the worker near the package?" "Does the worker have the right tools?" "Is the worker already busy?"

The Problem:
The rulebook gave every single criterion the exact same importance. It was like saying, "Distance is just as important as whether the worker has a forklift."

• Sometimes, you need to prioritize speed (distance).
• Sometimes, you need to prioritize having the right tools (capabilities).
• But the old rulebook couldn't change its mind. It was "one-size-fits-all," which meant packages often got stuck, or workers were underutilized.

To fix this manually, you'd need a super-expert to sit down and tweak the importance of each rule. But the warehouse is too big, and the rules change too fast. It's like trying to tune a radio while driving a race car at 200 mph.

The Solution: A Smart AI Coach (Reinforcement Learning)
This paper introduces a new way to manage the warehouse using an AI Coach that learns by doing. Instead of a static rulebook, the AI learns to adjust the "volume knobs" (weights) for each rule in real-time.

Here is how the AI coach works, using some creative analogies:

1. The "Taste Test" Reward System

Usually, AI learns by trying to get a high score. But in a warehouse, a "high score" is hard to define because every day is different.

• The Paper's Trick: The AI doesn't just look for a "good" score; it looks for improvement.
• The Analogy: Imagine the AI is a chef trying to perfect a soup. Instead of just saying "Is this soup good?", the AI asks, "Is this soup better than the bland soup we made yesterday?"
• If the AI changes the recipe (tunes the weights) and the soup tastes 10% better, it gets a "reward." If it makes it worse, it gets no reward. This encourages the AI to keep experimenting to find that perfect flavor, rather than settling for "okay."

2. Remembering the Past (Frame Stacking)

The AI needs to remember what it tried before so it doesn't make the same mistake twice.

• The Analogy: Think of the AI as a detective looking at a crime scene. If it only looks at the room right now, it might miss clues. But if it stacks up photos of the room from the last 10 minutes (Frame Stacking), it can see the pattern of movement.
• In the warehouse, the AI looks at the last few attempts at assigning packages. This "stack of memories" helps it understand the flow of traffic and make smarter decisions for the next package.

3. Not Cheating (Limiting Domain Information)

This is a very clever part of the paper. If you train an AI too specifically on one type of warehouse, it might "cheat" by memorizing the layout rather than learning the principles of logistics.

• The Analogy: Imagine training a driver only on a specific track with a specific curve. They might memorize "turn left at the red barn." But if you put them on a new track with no red barn, they crash.
• The Paper's Fix: The researchers deliberately hid some details from the AI during training. They didn't let the AI know the exact number of workers or the specific brand of forklifts. They only gave it general descriptions like "busy zone" or "quiet zone."
• The Result: Because the AI couldn't memorize the specific track, it was forced to learn the general principles of driving. Now, when it enters a completely new warehouse with different workers and tools, it can still drive perfectly. It didn't memorize the map; it learned how to drive.

The Results: A Winning Strategy

The researchers tested this AI Coach in a simulated "Serverless" warehouse (where apps run like temporary functions).

• Vs. The Old Rulebook: The AI improved performance by 33%. That's like getting 33% more packages delivered in the same amount of time.
• Vs. Other Smart Methods: It beat other advanced optimization methods by 12%.

Why This Matters

This isn't just about computer code; it's about adaptability.

• Old Way: You need a human expert to manually tweak the settings every time the workload changes.
• New Way: The AI learns the "vibe" of the current workload. If the warehouse is full of heavy, slow jobs, the AI turns up the volume on "capacity" rules. If it's full of tiny, urgent jobs, it turns up the volume on "speed" rules.

In a nutshell:
This paper teaches a computer how to be a better manager by letting it play a game of "What if?" It rewards the computer for getting better, helps it remember its mistakes, and forces it to learn general rules instead of memorizing specific tricks. The result is a system that is faster, smarter, and ready for anything the future throws at it.

Technical Summary

Here is a detailed technical summary of the paper "Learning to Score: Tuning Cluster Schedulers through Reinforcement Learning."

1. Problem Statement

Modern cluster orchestration systems (e.g., Kubernetes, Borg) typically use a two-step process for job scheduling: filtering (selecting feasible nodes based on hard constraints) and scoring (ranking feasible nodes based on soft constraints).

• The Core Issue: Current schedulers rely on a set of scoring functions (e.g., resource balance, locality, capability) that are usually weighted equally or manually tuned by experts.
• The Challenge: A "one-size-fits-all" weighting strategy fails to account for the specific characteristics of diverse workloads (e.g., batch processing vs. real-time services) and heterogeneous cluster configurations (e.g., cloud CPUs vs. edge devices).
• Limitations of Existing Solutions:
  • Manual Tuning: Requires deep expert knowledge and is time-consuming.
  • Black-box Optimization (Random Search, Bayesian Optimization, TPE): These methods struggle with the high dimensionality of the problem, the computational cost of evaluating new configurations, and poor generalization to unseen cluster/workload scenarios.

2. Methodology

The authors propose a Reinforcement Learning (RL) framework to automate the tuning of scoring function weights. The approach treats weight tuning as a multi-step parameter optimization problem.

A. RL Formulation

• Agent: An RL agent that interacts with a simulated FaaS (Function as a Service) environment.
• State Space:
  • Static: Cluster topology, hardware types, and workload characteristics.
  • Dynamic: Encodings of past action-reward pairs (explored weights and their outcomes).
• Action Space: The weights assigned to each scoring function (e.g., $w_1, w_2, ..., w_k$).
• Reward Function: A novel Percentage Improvement Reward. Instead of rewarding absolute metric values, the agent is rewarded based on the percentage improvement of the current configuration over a baseline (default weights) within an optimization episode. This encourages exploration of the parameter space.

B. Key Technical Innovations

1. Percentage Improvement Reward: Defined as $r_i = \frac{\max(r_1...r_n) - r_0}{r_0}$ (where $n$ is the number of samples). This normalizes rewards across different experiments and focuses on the rate of improvement rather than absolute scores.
2. Frame Stacking & Recurrent Policies: To handle the multi-step nature of tuning, the authors use frame stacking (presenting a history of action-reward pairs as input) or Recurrent Neural Networks (RNNs/LSTMs) within the policy network. This allows the agent to "remember" previous attempts and learn from the trajectory of the optimization.
3. Limiting Domain Information: To prevent overfitting to specific training environments, the authors intentionally limit the static domain information provided to the agent (e.g., using coarse descriptions of workloads/clusters rather than exact specifications). This forces the agent to learn a generalizable policy for exploration and exploitation rather than memorizing specific configurations.
4. Algorithms: The implementation leverages Soft Actor-Critic (SAC) with entropy regularization for robust exploration and Recurrent PPO for handling partially observable environments.

3. Experimental Setup

• Simulation Environment: Used faas-sim, a high-fidelity simulator for FaaS platforms that models network topology delays (Internet vs. Urban topologies) and heterogeneous hardware execution times.
• Scoring Functions: The system utilized 8 scoring functions (e.g., MostAllocated, LeastAllocated, ImageLocality, Capability, ResourceBalance).
• Workloads: Random combinations of functions (e.g., ResNet50 training/inference, MobileNet, Speech Inference) with Poisson-distributed arrival rates.
• Cluster Configurations: Tested on 8 distinct heterogeneous setups ranging from Cloud (CPU/GPU) to Edge (Raspberry Pi, NVIDIA Nano, Coral DevBoard) and Hybrid configurations.
• Baselines:
  • Fixed: Default equal weights (Kubernetes style).
  • Random Search (RS): Random sampling.
  • Bayesian Optimization (BO): Gaussian Process-based.
  • Tree-Structured Parzen Estimator (TPE): Non-parametric sequential optimization.

4. Key Results

The proposed RL approach was evaluated against baselines in two scenarios: Similar Configurations (training and testing on similar setups) and Novel Configurations (generalization to unseen setups).

• Performance Gain (Similar Configs):
  • +33% improvement over Fixed weights.
  • +20% improvement over the best-performing baseline (TPE/BO).
  • The RL agent successfully learned to assign low weights to irrelevant functions (e.g., locality in certain contexts) and high weights to critical ones (e.g., capability).
• Performance Gain (Novel/Unseen Configs):
  • +20% improvement over Fixed weights.
  • +6% improvement over the best-performing baseline.
  • This demonstrates the model's ability to generalize to unseen hardware distributions and workload types without retraining.
• Efficiency: The RL approach converged faster and found better local optima compared to traditional black-box methods, which often struggled with the high dimensionality and computational cost.

5. Significance and Contributions

• Automation of Scheduler Tuning: Moves away from manual, expert-driven weight tuning to an automated, data-driven RL approach.
• Generalization: Proves that RL agents can learn robust policies that transfer across diverse cluster topologies and workload types, a common failure point for traditional optimization methods.
• Engineering Practicality: The approach is "plug-and-play" for existing schedulers. It does not require replacing the entire scheduling logic; it simply tunes the weights of existing scoring functions, minimizing infrastructure changes.
• Novel Reward Mechanism: The introduction of the "Percentage Improvement Reward" effectively addresses the multi-step optimization challenge, preventing the agent from getting stuck in local minima.

Conclusion

The paper demonstrates that Reinforcement Learning is a superior method for tuning cluster scheduler scoring functions compared to static heuristics and traditional black-box optimization. By learning to dynamically adjust weights based on workload and cluster characteristics, the proposed method significantly improves end-to-end job performance (up to 33%) and maintains robustness in unseen environments.