Research map / Bandits and online learning / RL theory and MDPs

Sleeping Reinforcement Learning

ICML 2025 · Bandits and online learning › RL theory and MDPs · approach: Linear function approximation in RL

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Introduces Sleeping RL, where action availability varies over time, and gives regret bounds for per-episode and per-stage action disclosure, including an exponential lower bound for Markovian availability and an optimistic algorithm (S-UCBVI) matching standard RL for independent availability.

Problem

Standard RL assumes a fixed, immutable action set, but in many real settings the available actions depend on state, constraints, or stochastic factors outside the agent's control. The paper asks how to learn when action availability varies and is revealed either per episode or per stage.

Approach

Formalizes Sleeping MDPs with per-episode and per-stage action disclosure and Markovian or independent availability models. It adapts UCBVI into AR-UCBVI for per-episode disclosure and S-UCBVI with an extra availability-estimation bonus for independent per-stage disclosure, and proves an exponential lower bound for Markovian availability via an augmented MDP.

Key results

• AR-UCBVI achieves per-episode disclosure regret of order H sqrt(SAT) (up to log factors), matching standard RL.
• A lower bound of order H sqrt(SA T^{2^{A/2}}) holds for per-stage disclosure with Markovian action availability, showing exponential dependence on A is unavoidable.
• S-UCBVI achieves regret of order H sqrt(SAT) (up to log factors) for per-stage disclosure with independent action availability, matching the standard RL lower bound for large T.

Measured effects reported in the paper

Surprising findings

• With Markovian action availability, per-stage disclosure incurs an exponential-in-A regret lower bound, so the problem is statistically harder than standard RL.

Limitations

• Upper bound for per-stage disclosure only holds for independent availability; Markovian case has exponential dependence on A.
• Minimum horizon T required for the leading term scales exponentially with A in the independent per-stage case.
• Rewards assumed known and deterministic.

Experimental setup

Metrics: cumulative regret

Baselines: UCBVI standard RL lower bound

Builds on: UCBVI Markov decision processes action masking sleeping multi-armed bandits Domingues et al. 2021 lower bound

Closest papers by meaning

• Enabling Realtime Reinforcement Learning at Scale with Staggered Asynchronous Inference (ICLR 2025 · similarity 0.88)
• Taming "data-hungry" reinforcement learning? Stability in continuous state-action spaces (NeurIPS 2024 · similarity 0.87)
• DARLING: Detection Augmented Reinforcement Learning with Non-Stationary Guarantees (NeurIPS 2026 · similarity 0.87)
• Model-based RL as a Minimalist Approach to Horizon-Free and Second-Order Bounds (ICLR 2025 · similarity 0.87)
• Overcoming Slow Decision Frequencies in Continuous Control: Model-Based Sequence Reinforcement Learning for Model-Free Control (ICLR 2025 · similarity 0.87)
• Long-Term Safe Reinforcement Learning with Binary Feedback (AAAI 2024 · similarity 0.87)