mlsanityData to 14 Oct 2026

Bi-Level Online Provisioning and Scheduling with Switching Costs and Cross-Level Constraints

arXiv 2601.18936 ↗First posted 26 Jan 2026cs.LGcited by 0

Not on the map. Why?

Abstract (arXiv)

We study a bi-level online provisioning and scheduling problem motivated by network resource allocation, where provisioning decisions are made at a slow time scale while queue-/state-dependent scheduling is performed at a fast time scale. We model this two-time-scale interaction using an upper-level online convex optimization (OCO) problem and a lower-level constrained Markov decision process (CMDP). Existing OCO typically assumes stateless decisions and thus cannot capture MDP network dynamics such as queue evolution. Meanwhile, CMDP algorithms typically assume a fixed constraint threshold, whereas in provisioning-and-scheduling systems, the threshold varies with online budget decisions. To address these gaps, we study bi-level OCO-CMDP learning under switching costs (budget reprovisioning/system reconfiguration) and cross-level constraints that couple budgets to scheduling decisions. Our new algorithm solves this learning problem via several non-trivial developments, including a carefully designed dual feedback that returns the budget multiplier as sensitivity information for the upper-level update and a lower level that solves a budget-adaptive safe exploration problem via an extended occupancy-measure linear program. We establish near-optimal regret and high-probability satisfaction of the cross-level constraints.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 7 of its 21 references that are in the map. First posted on arXiv 26 Jan 2026.

Builds on

7 of 21 references.

References · 7

  1. 2019Introduction to Online Convex Optimizationcited by 803
  2. 2017Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learningcited by 176
  3. 2021DOPE: Doubly Optimistic and Pessimistic Exploration for Safe Reinforcement Learningcited by 35
  4. 2018Online Optimization with Predictions and Switching Costs: Fast Algorithms and the Fundamental Limitcited by 27
  5. 2023A Near-Optimal Algorithm for Safe Reinforcement Learning Under Instantaneous Hard Constraintscited by 17
  6. 2025Provably Efficient RL for Linear MDPs under Instantaneous Safety Constraints in Non-Convex Feature Spacescited by 7
  7. 2023Near-Optimal Adversarial Reinforcement Learning with Switching Costscited by 4

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2026A Constrained RL Approach for Cost-Efficient Delivery of Latency-Sensitive Applications
  2. 2024Exponentially Weighted Algorithm for Online Network Resource Allocation with Long-Term Constraints
  3. 2025Offline Diffusion Policy for Multi-User Delay-Constrained Scheduling
  4. 2025Reinforcement Learning for Dynamic Resource Allocation in Optical Networks: Hype or Hope?
  5. 2025A Hybrid Reinforcement Learning Framework for Hard Latency Constrained Resource Scheduling
  6. 2025Generalizing Beyond Suboptimality: Offline Reinforcement Learning Learns Effective Scheduling through Random Solutions
  7. 2025Demonstration of effective UCB-based routing in skill-based queues on real-world data
  8. 2025Optimal Batched Scheduling of Stochastic Processing Networks Using Atomic Action Decomposition ↗