Adaptive Task Scheduling for Edge-Intelligent Systems: An Online Sleeping Restless Bandits Framework

In edge-intelligent systems, efficient resource management and task scheduling are critical but challenging due to the dynamic and heterogeneous nature of edge nodes (e.g., IoT devices, drones). We model this dynamic resource allocation challenge as an online sleeping Restless Multi-Armed Bandits (RMAB) problem, where each edge node (arm) operates as a Markov decision process. Unlike prior RMAB frameworks assuming perpetual availability, our setting captures the stochastic availability of edge nodes across rounds. The system controller (learner) is unaware of the transition functions, reward distributions, and node availability a priori. The goal is to maximize expected cumulative rewards through adaptive node selection. To explore this target problem, we first derive an asymptotically optimal sleeping-index policy (SIP) as the oracle based on the fluid process transformation. Then we propose OSILA (Online Sleeping Index-aware Learning Algorithm), featuring a Minimum Exploration Guarantee (MEG) mechanism for efficient exploration. This is coupled with a modified Linear Programming-based exploitation mechanism to construct an online sleeping index, effectively handling dynamic node availability. To the best of our knowledge, this work is the first to provide the theoretical analysis (which achieves O˜(KT2/3logT) regret where K is the number of arms and T is the time horizon) to the online sleeping RMAB problem. Empirical results validate both theoretical guarantees and practical effectiveness in dynamic edge computing environments.