No Regret Reinforcement Learning Algorithms for Online Scheduling with Multi-Stage Tasks

Yongxin Xu, Hengquan Guo, Ziyu Shao, Xin LiuIJCAI 2025 · DOI

Abstract

Online scheduling of multi-stage tasks involves managing complex intra-task dependencies and inter-task competition for limited resources under unknown reward and cost distributions. This paper introduces RM$^2$VI (Robbins-Monro-based Value Iteration for Ratio Maximization), a novel reinforcement learning approach designed to maximize the long-term reward-to-cost ratio. By integrating stochastic approximation with double-optimistic value iteration, RM$^2$VI achieves a sub-linear regret bound of $O(K^{3/4})$. Empirical evaluations in e-commerce and cloud computing simulations demonstrate that RM$^2$VI consistently outperforms existing baselines in both performance and stability.

Introduction

In domains such as cloud computing and digital marketing, scheduling is more than just ordering tasks; it involves managing multi-stage processes where early decisions ripple through to final outcomes. For example, a machine learning pipeline involves data processing, pre-training, and fine-tuning, where resource allocation at one stage dictates the potential accuracy (reward) of the next.

Traditional scheduling algorithms often fail to address two key complexities:

  1. Intra-dependence: Decisions in early stages affect the states and possibilities of subsequent stages.
  2. Inter-dependence: Diverse task types arrive sequentially and compete for a shared resource pool.

Furthermore, system dynamics—such as task arrival patterns and the underlying Markov Decision Process (MDP) transitions—are often unknown, necessitating an online learning approach.

Methodology: The RM$^2$VI Algorithm

The researchers propose Robbins-Monro-based Value Iteration for Ratio Maximization (RM$^2$VI) to tackle these challenges. The algorithm is built on three primary pillars:

  • Stochastic Approximation (Robbins-Monro): Instead of explicitly modeling task arrival distributions, the algorithm tracks the average system performance (the reward-to-cost ratio, $\theta$) and updates this estimate iteratively as tasks complete.
  • Double-Optimistic Value Iteration (DOVI): To handle intra-dependence, the agent employs a "double-optimistic" strategy. It calculates an Upper Confidence Bound (UCB) for rewards and a Lower Confidence Bound (LCB) for costs, encouraging exploration of actions that might yield a higher overall ratio.
  • Cost-Aware Greedy Decisions: At each step, the agent selects actions that maximize a surrogate function: $(Estimated Reward) - \theta \times (Estimated Cost)$. This balances the pursuit of high rewards against resource costs, guided by the current global performance estimate.

Empirical Evaluation

The algorithm was evaluated using two high-fidelity synthetic environments:

  • Sale Promotion Scenario: An e-commerce simulation where users move through stages (interest $\rightarrow$ cart $\rightarrow$ purchase). The platform optimizes discount levels to maximize revenue relative to costs.
  • Cloud Computing Scenario: A server training various ML models. The server must allocate computational epochs across different training stages to maximize model accuracy relative to computational cost.

Key Results and Discussion

Experimental results confirm that RM$^2$VI achieves superior performance and stability compared to standard baselines such as Q-learning with UCB (Q-UCB), CARVI, and Constrained Actor-Critic (CAAC).

Cumulative reward-to-cost ratio in the Sale Promotion scenario.

In the Sale Promotion scenario, RM$^2$VI converged to a higher stable ratio than its competitors. While algorithms like CARVI performed reasonably well, they lacked the ability to adapt to the specific distribution of task types as effectively as RM$^2$VI.

Cumulative reward-to-cost ratio in the Cloud Computing scenario.

In the Cloud Computing scenario, the performance gap was even more pronounced. RM$^2$VI demonstrated significantly better stability than Actor-Critic methods, which often struggle with the non-stationary nature of online scheduling. The algorithm's "no-regret" property was empirically validated, as the per-task error vanished over time, confirming the theoretical $O(K^{3/4})$ regret bound.

Conclusion

RM$^2$VI provides a robust framework for maximizing the reward-to-cost ratio in complex, multi-stage scheduling environments. By decoupling inter-task arrival complexity from intra-task stage transitions, the algorithm offers a scalable solution for real-world resource management. Future research will focus on tightening the regret bounds toward $O(K^{1/2})$ and extending the framework to continuous state and action spaces using Deep RL techniques.

Summary updated

BibTeX
@inproceedings{xu2025no,
  author = {Yongxin Xu and Hengquan Guo and Ziyu Shao and Xin Liu},
  title = {{No Regret Reinforcement Learning Algorithms for Online Scheduling with Multi-Stage Tasks}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.24963/ijcai.2025/753},
}
Figure