# Planning and Learning with Stochastic Action Sets

arXiv: https://arxiv.org/abs/1805.02363 · HTML: https://mlsanity.com/paper/1805.02363/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 May 2018.

## Built on by (most cited first, 9 of 9)

- [Dynamic Planning in Open-Ended Dialogue using Reinforcement Learning](https://mlsanity.com/paper/2208.02294/) (2022)
- [Statistical Guarantees for Lifelong Reinforcement Learning using PAC-Bayes Theory](https://mlsanity.com/paper/2411.00401/) (2024)
- [On the Hardness of Reinforcement Learning with Transition Look-Ahead](https://mlsanity.com/paper/2510.19372/) (2025)
- [From monoliths to modules: Decomposing transducers for efficient world modelling](https://mlsanity.com/paper/2512.02193/) (2025)
- [Offline Reinforcement Learning for Mixture-of-Expert Dialogue Management](https://mlsanity.com/paper/2302.10850/) (2023)
- [Action Pick-up in Dynamic Action Space Reinforcement Learning](https://mlsanity.com/paper/2304.00873/) (2023)
- [A Bibliometric Analysis and Review on Reinforcement Learning for Transportation Applications](https://mlsanity.com/paper/2210.14524/) (2022)
- [Efficient Learning of High Level Plans from Play](https://mlsanity.com/paper/2303.09628/) (2023)
- [Reinforcement Learning Framework for Server Placement and Workload Allocation in Multi-Access Edge Computing](https://mlsanity.com/paper/2203.07998/) (2022)

## Abstract (arXiv)

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.