Abstract
In many practical uses of reinforcement learning (RL) the set of actions available at a given state is a random variable, with realizations governed by an exogenous stochastic process. Somewhat surprisingly, the foundations for such sequential decision processes have been unaddressed. In this work, we formalize and investigate MDPs with stochastic action sets (SAS-MDPs) to provide these foundations. We show that optimal policies and value functions in this model have a structure that admits a compact representation. From an RL perspective, we show that Q-learning with sampled action sets is sound. In model-based settings, we consider two important special cases: when individual actions are available with independent probabilities; and a sampling-based model for unknown distributions. We develop poly-time value and policy iteration methods for both cases; and in the first, we offer a poly-time linear programming solution.
Introduction
Standard Markov Decision Processes (MDPs) assume a fixed set of actions $A(s)$ for each state $s$. However, in many real-world domains—from inventory management where products go out of stock to online advertising where budgets are exhausted—action availability is volatile. Treating the set of available actions as part of the state leads to an exponential explosion of the state space ($2^{|A|}$ possible subsets), making traditional RL methods computationally intractable. This paper introduces the Stochastic Action Set MDP (SAS-MDP) framework to provide a theoretical foundation and efficient algorithms for these environments.
The SAS-MDP Framework
A SAS-MDP extends the standard MDP by assuming that at each time step, the set of available actions $A_t \subseteq A$ is drawn from a distribution $P(A|s)$. The agent must choose an action $a \in A_t$. To analyze this, the authors distinguish between an Embedded MDP ($M_e$), which includes the action set in the state, and a Compressed MDP ($M_c$), which operates on the original state space by taking expectations over action availability.
A key theoretical innovation is the proof that an optimal policy always exists in the form of a Decision List (DL): a state-specific ordering of actions. When an agent reaches a state, it simply selects the highest-ranked action in its list that is currently available. This structure is possible because the Q-value of an action $a$ at state $s$ is independent of which other actions are currently available.
Algorithms for Planning and Learning
The paper demonstrates that SAS-MDPs admit computationally efficient solutions even with the added complexity of stochasticity:
- SAS-Q-learning: Standard Q-learning can be adapted by updating $Q(s, a)$ only when action $a$ is available and chosen, and maximizing over the realized set of available actions in the next state. This approach is robust as it does not require prior knowledge of the action availability distribution.
- Efficient Planning: Under the Product Distribution Assumption (PDA)—where actions are available independently with probability $\rho(s, a)$—the Bellman update can be computed in $O(m \log m)$ time by simply sorting actions by their Q-values. This reduces an exponential search over subsets to a simple sorting operation.
- Linear Programming: For model-based settings, the authors provide a polynomial-time LP solution that utilizes constraint generation to handle the factorial number of possible action orderings.
Empirical Evaluation
The framework was evaluated using a synthetic routing problem based on the San Francisco Bay Area road network. In this scenario, road segments (actions) have a probability $p$ of being available, simulating traffic closures.
As shown in the results, a standard "oblivious" policy that ignores stochastic availability performs significantly worse than the SAS-optimal policy when availability is low. The SAS-optimal policy gracefully adapts by building in redundancy, whereas the oblivious policy's performance drops sharply. The value gap is most pronounced at low values of $p$, where accounting for stochasticity provides up to a 50% improvement in expected value.
Conclusion
SAS-MDPs provide a robust foundation for RL in environments with volatile action sets. By proving that optimal policies are simple action orderings and providing polynomial-time algorithms, this work enables efficient planning and learning in complex, real-world scenarios. Future work includes relaxing the independence assumption between actions and extending these methods to large-scale function approximation settings like Deep Q-Networks (DQN).
Summary updated