Real-Time Scheduling via Reinforcement Learning

Robert Glaubius, Terry Tidwell, Christopher D. Gill, William D. SmartUAI 2010

TL;DR

This paper tackles the challenge of real-time scheduling for cyber-physical systems, like mobile robots, where tasks have unpredictable durations and cannot be easily interrupted. They propose a reinforcement learning approach to learn optimal scheduling policies without prior knowledge of task behavior, providing theoretical guarantees on learning efficiency and demonstrating empirically that a purely exploitative strategy often outperforms explicit exploration in this domain.

What Problem Does This Paper Address?

In real-time systems, especially those involving physical actions like robotics, ensuring that tasks complete within their deadlines is crucial. Traditional scheduling methods often assume tasks have predictable execution times and can be paused and resumed. However, in many real-world scenarios, tasks like moving a robotic arm have variable durations and are difficult or impossible to preempt without significant overhead. Furthermore, these systems often need to balance general tasks (like obstacle avoidance) with mission-specific goals (like imaging a room), requiring a dynamic allocation of shared resources. The core problem is learning effective scheduling strategies in such dynamic and uncertain environments, where complete prior knowledge of task behavior is impractical.

Methods

The authors frame the scheduling problem as a Markov Decision Process (MDP). A key challenge is that the state space of this MDP is countably infinite, and costs can be unbounded. To address this, they leverage the structure of the problem, specifically the concept of "utilization states" and the fact that states collinear along the target utilization ray can be aggregated.

Their primary theoretical contribution is a PAC (Probably Approximately Correct) bound on the sample complexity of learning a near-optimal policy. This bound quantifies how many observations are needed to learn a good scheduling policy with high confidence. They achieve this by extending existing reinforcement learning techniques for finite state spaces to their infinite state, unbounded cost domain. The analysis relies on bounding the error in estimating the state-action value function (Q-function) and relating this to the error in the learned policy.

For practical learning, they consider several exploration strategies:

  • Balanced Wandering: A theoretical approach where each action is tried a fixed number of times before exploiting the learned model.
  • e-greedy: A common strategy that takes a random action with a small probability ($\epsilon$) and the best-known action otherwise.
  • Optimistic Interval-Based Exploration: This method uses confidence intervals on estimated values to bias action selection towards actions with higher potential value, even if their current estimated value is lower.

Datasets

The paper does not use traditional "datasets" in the sense of pre-collected data. Instead, they generate task duration distributions and problem instances for simulation. For their experiments, they create two-task problem instances by:

  • Selecting worst-case execution times (W) uniformly at random from [8, 32].
  • Generating normal distributions for task durations with randomly chosen means and variances, then truncating and discretizing them over [1, W].
  • Choosing utilization targets for each task randomly.

They then simulate these instances over 20,000 decision epochs for each exploration strategy.

Key Insights and Ideas

  • Infinite State Space, Finite Complexity: Despite the theoretically infinite state space of the utilization problem, its structure allows for aggregation, leading to a sample complexity that depends on task parameters (like worst-case execution time) rather than the number of states. This is a significant theoretical result for learning in complex real-time systems.
  • Exploitation Dominance: Empirically, a purely exploitative strategy (always choosing the action believed to be best based on current knowledge) often outperforms strategies that explicitly encourage exploration. This is a surprising finding, as exploration is typically considered essential for learning in reinforcement learning.
  • Environment-Induced Exploration: The authors hypothesize that the cost structure of the scheduling problem itself enforces a form of exploration. If a task is consistently ignored, its underutilization leads to increasing costs, eventually making it beneficial to dispatch that task. This "natural exploration" might obviate the need for explicit exploration mechanisms.
  • PAC Bounds for Complex Domains: The paper provides the first PAC bounds for learning in infinite state, unbounded cost MDPs, specifically for the task scheduling domain. This offers theoretical assurance for the learning process.

Key Results

  • Theoretical Guarantee: The paper derives a PAC bound showing that learning a near-optimal policy with high probability requires a number of observations that scales polynomially with parameters like the discount factor, confidence level, and worst-case execution time, but not with the number of states.
  • Empirical Performance: In simulations comparing optimistic interval-based exploration, e-greedy, and balanced wandering, the "Exploit" strategy (which greedily follows the current best policy) consistently performed best, making the fewest mistakes. Even with explicit exploration, the mistake rates were low, suggesting the domain's inherent cost structure drives learning.
  • Balanced Wandering Ineffectiveness: Contrary to theoretical expectations for some domains, balanced wandering did not outperform purely exploitative strategies in their simulations.

Limitations and Future Work

  • Assumptions: The theoretical PAC bounds rely on assumptions like balanced wandering and finite support for task durations. While the empirical results explore other strategies, the tightness of the theoretical bounds might be affected by these assumptions.
  • Generalizability of Exploitation: The finding that pure exploitation works well is specific to this task scheduling domain. The authors pose an open question about whether other MDPs with similar "portability" or cost structures might also exhibit this behavior, suggesting future work in identifying such classes of problems.
  • Regret vs. PAC: The paper focuses on PAC bounds (learning a good policy with high probability) rather than regret bounds (minimizing cumulative loss during learning). While PAC bounds are valuable, regret bounds might offer more direct guarantees on transient real-time performance. Future work could explore regret bounds in this context.
  • Model Representation: The paper notes that for these results to be practical, policies must be represented compactly, which is possible for this scheduling domain but not generally. Future work could explore how to handle more complex policy representations.

Summary updated

BibTeX
@inproceedings{glaubius2010real,
  author = {Robert Glaubius and Terry Tidwell and Christopher D. Gill and William D. Smart},
  title = {{Real-Time Scheduling via Reinforcement Learning}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2010},
}
Figure