Sleeping Reinforcement Learning

Simone Drago, Marco Mussi, Alberto Maria MetelliICML 2025 · OpenReview

TL;DR: This paper introduces Sleeping Reinforcement Learning (SleRL), a framework for environments where the set of available actions changes over time due to external constraints. The authors demonstrate that while Markovian action availability makes learning exponentially difficult, independent availability can be solved as efficiently as standard RL using their novel algorithm, S-UCBVI.

The Challenge of Disappearing Actions

In textbook Reinforcement Learning (RL), an agent typically assumes a fixed, immutable set of actions. If a robot can move North, South, East, and West, it assumes it can always do so. However, in real-world deployments, this is rarely the case. A low-level safety controller might temporarily disable a forward movement to prevent a collision, or a drone might lose certain maneuvers due to environmental factors like high winds or low battery.

Architecture of a Sleeping RL Agent

This scenario is known in the bandit literature as the "Sleeping" problem, but extending it to the full complexity of Markov Decision Processes (MDPs)—where actions affect future states—presents significant new challenges. The complexity of this problem hinges on two main factors:

  1. Information Disclosure: Does the agent learn which actions are available at the start of an episode (per-episode), or only immediately before making a decision (per-stage)?
  2. Availability Dynamics: Is the availability of an action totally random (independent), or does it depend on previous states and actions (Markovian)?

Interaction Protocols: Per-Episode vs. Per-Stage

To formalize these scenarios, the authors define two distinct interaction protocols.

Interaction Protocols for Sleeping RL

In the per-episode setting, the agent is handed a schedule of available actions for the entire episode upfront. In the more challenging and realistic per-stage setting, the agent only discovers its available options at the exact moment it reaches a state.

Algorithmic Solutions

The authors tackle these scenarios by building upon the UCBVI (Upper Confidence Bound Value Iteration) algorithm:

  • AR-UCBVI (Action-Restricted UCBVI): Designed for the per-episode case. It modifies standard optimistic value iteration to only consider actions explicitly known to be available for that specific episode.
  • S-UCBVI (Sleeping UCBVI): The primary algorithmic contribution for the per-stage independent case. Because the agent doesn't know future action availability, it must estimate the probability of each action being "awake." S-UCBVI introduces a novel exploration bonus specifically for uncertainty in action availability, alongside the standard bonus for state transition uncertainty.

Key Insights and The Statistical Barrier

The paper reveals a stark contrast in learning difficulty based on how actions become unavailable:

  • The Exponential Barrier (Markovian Availability): If action availability follows a Markovian process (e.g., using a specific tool forces it into a "cooldown" state for several turns), the problem becomes exceptionally hard. The authors prove a minimax lower bound of $\Omega(\sqrt{T 2^{A/2}})$. This establishes a statistical barrier, showing that in the worst case, learning is exponentially difficult relative to the number of actions ($A$).
  • The Tractability of Independence: Conversely, if actions "sleep" independently at each step, the problem is much more forgiving. The authors prove that an agent only needs to estimate the marginal probability of each action's availability. Under this condition, S-UCBVI achieves a regret bound of $\widetilde{\mathcal{O}}(H\sqrt{SAT})$, matching the complexity of standard RL.

Empirical Validation

To test these theoretical findings, the authors introduced StochasticFrozenLake, a modified OpenAI Gym environment where "holes" in the ice open and close stochastically, effectively disabling movement actions. In these experiments, S-UCBVI consistently reached optimal reward levels, whereas standard UCBVI—which ignores action availability dynamics—settled for suboptimal policies. The performance gap widened as the environment became more unstable.

Future Directions

The most significant limitation identified is the "Markovian Barrier." While worst-case Markovian availability is exponentially hard, real-world systems often exhibit structured availability that isn't purely independent but avoids worst-case extremes. Future work will likely focus on:

  • Structured Availability: Investigating intermediate models (e.g., linear constraints) to find tractable middle grounds.
  • Function Approximation: Extending these discrete-state algorithms to deep RL settings with continuous state spaces.

Reference: Drago, S., Mussi, M., & Metelli, A. M. (2025). Sleeping Reinforcement Learning. Proceedings of the 42nd International Conference on Machine Learning (ICML).

Summary updated

Abstract

In the standard Reinforcement Learning (RL) paradigm, the action space is assumed to be fixed and immutable throughout the learning process. However, in many real-world scenarios, not all actions are available at every decision stage. The available action set may depend on the current environment state, domain-specific constraints, or other (potentially stochastic) factors outside the agent's control. To address these realistic scenarios, we introduce a novel paradigm called *Sleeping Reinforcement Learning*, where the available action set varies during the interaction with the environment. We start with the simpler scenario in which the available action sets are revealed at the beginning of each episode. We show that a modification of UCBVI achieves regret of order $\widetilde{\mathcal{O}}(H\sqrt{SAT})$, where $H$ is the horizon, $S$ and $A$ are the cardinalities of the state and action spaces, respectively, and $T$ is the learning horizon. Next, we address the more challenging and realistic scenario in which the available actions are disclosed only at each decision stage. By leveraging a novel construction, we establish a minimax lower bound of order $\Omega(\sqrt{T 2^{A/2}})$ when the availability of actions is governed by a Markovian process, establishing a statistical barrier of the problem. Focusing on the statistically tractable case where action availability depends only on the current state and stage, we propose a new optimistic algorithm that achieves regret guarantees of order $\widetilde{\mathcal{O}}(H\sqrt{SAT})$, showing that the problem shares the same complexity of standard RL.
BibTeX
@inproceedings{drago2025sleeping,
  author = {Simone Drago and Marco Mussi and Alberto Maria Metelli},
  title = {{Sleeping Reinforcement Learning}},
  booktitle = {International Conference on Machine Learning},
  year = {2025},
  url = {https://openreview.net/forum?id=U7c1DqiPTl},
}
Figure