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 polynomial-time value and policy iteration methods for both cases, and provide a polynomial-time linear programming solution for the first case.
Introduction
In traditional Reinforcement Learning (RL) and Markov Decision Processes (MDPs), the set of available actions at any given state is typically assumed to be fixed. However, real-world applications often feature stochastic action availability. For instance, in online advertising, the set of eligible ads for a user query fluctuates based on campaign budgets or frequency capping. Similarly, in recommender systems, the candidate pool of items is often pre-filtered by upstream systems.
Ignoring this stochasticity leads to suboptimal policies, while naively embedding all possible action subsets into the state space results in an exponential blow-up, making the problem computationally intractable. This paper introduces the SAS-MDP framework to address these challenges efficiently.
The SAS-MDP Framework
The authors formalize the SAS-MDP and demonstrate that optimal policies can be compactly represented as Decision Lists (DL). Instead of mapping every possible subset of actions to a specific choice, a DL ranks the base actions. When a state is reached, the agent simply executes the highest-ranked action that is currently available.
A key insight is that the optimal Q-value of an action $k$ at state $s$ is independent of what other actions are currently available. This structural property allows for a compressed representation that bypasses the curse of dimensionality.
Algorithms and Tractability
The paper adapts standard RL and planning algorithms for the SAS setting:
- SAS-Q-Learning: A modified Q-learning update that maximizes only over the realized available actions in the next state. This is proven to converge to the optimal Q-function.
- Model-Based Planning: The authors develop polynomial-time versions of Value Iteration (VI) and Policy Iteration (PI) under the Product Distribution Assumption (PDA), where actions are available independently. They also provide a Linear Programming (LP) formulation that remains tractable despite having factorially many constraints.
Empirical Results
The framework was evaluated on a routing problem using a real-world road network in the San Francisco Bay Area. In this scenario, a critical bridge is available only with probability $p$. An "oblivious" policy that assumes the bridge is always available performs poorly when $p$ is low, as it fails to account for the high cost of the bridge being closed.
As shown in the results, the SAS-optimal policy significantly reduces trip times by naturally incorporating redundancy and alternate routes when the bridge's availability is uncertain.
Conclusion
SAS-MDPs provide a robust foundation for decision-making in environments with fluctuating action sets. By leveraging the structure of Decision Lists, the authors provide polynomial-time algorithms for both planning and learning. Future work includes relaxing the independence assumption between actions using more complex graphical models.
Summary updated