Lyapunov-Driven Optimistic Learning for Online Scheduling with Multi-Stage Tasks

We study online scheduling in a shared-resource system where tasks of different types arrive sequentially and compete for limited resources. Each task is modeled as an $H$-stage episodic Markov decision process, which captures the sequential resource-allocation decisions made within the task. At the system level, the learner must coordinate resource sharing across tasks to maximize the long-term ratio of cumulative reward to cumulative cost over $K$ tasks, without knowledge of the task distribution. The key challenges are coupled intra-task Markovian dynamics and inter-task ratio maximization, further complicated by unknown models and large or continuous state spaces. To address these challenges, we propose Contextual Optimistic Lyapunov Decomposition (COLD), a Lyapunov-driven optimistic learning algorithm. COLD converts the long-term ratio objective into a queue-adjusted per-task surrogate, thereby decoupling reward-cost optimization from statistical value estimation. It uses double-optimistic least-squares value iteration to estimate reward and cost values under linear function approximation, and a softmax policy to smooth the greedy update with only a controlled approximation error. We prove a regret bound of $\tilde{\mathcal{O}}(\sqrt{Md^3H^3T})$, where $M$ is the number of task types, $d$ is the feature dimension, $H$ is the episode horizon, and $T=KH$ is the number of interaction steps. The $\sqrt{T}$ dependence is order-optimal up to logarithmic factors, and the bound scales with the feature dimension rather than the size of the state space. Experiments on synthetic environments and an empirical KuaiRand-based MDP demonstrate the effectiveness of the proposed method.