# Qualitative Controller Synthesis for Consumption Markov Decision Processes

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

## Key facts

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

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

- [Density Constrained Reinforcement Learning](https://mlsanity.com/paper/2106.12764/) (2021)
- [Shielding in Resource-Constrained Goal POMDPs](https://mlsanity.com/paper/2211.15349/) (2022)
- [Threshold UCT: Cost-Constrained Monte Carlo Tree Search with Pareto Curves](https://mlsanity.com/paper/2412.13962/) (2024)
- [Solving Truly Massive Budgeted Monotonic POMDPs with Oracle-Guided Meta-Reinforcement Learning](https://mlsanity.com/paper/2408.07192/) (2024)
- [Taming Infinity one Chunk at a Time: Concisely Represented Strategies in One-Counter MDPs](https://mlsanity.com/paper/2503.00788/) (2025)
- [Polynomial-Time Algorithms for Multi-Agent Minimal-Capacity Planning](https://mlsanity.com/paper/2105.01225/) (2021)
- [Efficient Strategy Synthesis for MDPs with Resource Constraints](https://mlsanity.com/paper/2105.02099/) (2021)
- [Capacity-Aware Planning and Scheduling in Budget-Constrained Multi-Agent MDPs: A Meta-RL Approach](https://mlsanity.com/paper/2410.21249/) (2024)
- [Simplicity Lies in the Eye of the Beholder: A Strategic Perspective on Controllers in Reactive Synthesis](https://mlsanity.com/paper/2509.04129/) (2025)

## Abstract (arXiv)

Consumption Markov Decision Processes (CMDPs) are probabilistic decision-making models of resource-constrained systems. In a CMDP, the controller possesses a certain amount of a critical resource, such as electric power. Each action of the controller can consume some amount of the resource. Resource replenishment is only possible in special reload states, in which the resource level can be reloaded up to the full capacity of the system. The task of the controller is to prevent resource exhaustion, i.e. ensure that the available amount of the resource stays non-negative, while ensuring an additional linear-time property. We study the complexity of strategy synthesis in consumption MDPs with almost-sure B"uchi objectives. We show that the problem can be solved in polynomial time. We implement our algorithm and show that it can efficiently solve CMDPs modelling real-world scenarios.