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.
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:
- 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)?
- 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.
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