# Taming Infinity one Chunk at a Time: Concisely Represented Strategies in One-Counter MDPs

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 40 references that are in the map.
- First posted on arXiv 2 Mar 2025.

## Builds on (most cited first, 12 of 12)

- [dtControl 2.0: Explainable Strategy Representation via Decision Tree Learning Steered by Experts](https://mlsanity.com/paper/2101.07202/) (2021)
- [Counterexample Explanation by Learning Small Strategies in Markov Decision Processes](https://mlsanity.com/paper/1502.02834/) (2015)
- [Qualitative Controller Synthesis for Consumption Markov Decision Processes](https://mlsanity.com/paper/2005.07227/) (2020)
- [Simple Strategies in Multi-Objective MDPs (Technical Report)](https://mlsanity.com/paper/1910.11024/) (2019)
- [Percentile Queries in Multi-Dimensional Markov Decision Processes](https://mlsanity.com/paper/1410.4801/) (2014)
- [Strategy Representation by Decision Trees in Reactive Synthesis](https://mlsanity.com/paper/1802.00758/) (2018)
- [Algebraically Explainable Controllers: Decision Trees and Support Vector Machines Join Forces](https://mlsanity.com/paper/2208.12804/) (2022)
- [Games Where You Can Play Optimally with Arena-Independent Finite Memory](https://mlsanity.com/paper/2001.03894/) (2020)
- [Arena-Independent Finite-Memory Determinacy in Stochastic Games](https://mlsanity.com/paper/2102.10104/) (2021)
- [Different Strokes in Randomised Strategies: Revisiting Kuhn's Theorem under Finite-Memory Assumptions](https://mlsanity.com/paper/2201.10825/) (2022)
- [Mixing Any Cocktail with Limited Ingredients: On the Structure of Payoff Sets in Multi-Objective POMDPs and its Impact on Randomised Strategies](https://mlsanity.com/paper/2502.18296/) (2025)
- [Positivity-hardness results on Markov decision processes](https://mlsanity.com/paper/2302.13675/) (2023)

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

- [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)

Markov decision processes (MDPs) are a canonical model to reason about decision making within a stochastic environment. We study a fundamental class of infinite MDPs: one-counter MDPs (OC-MDPs). They extend finite MDPs via an associated counter taking natural values, thus inducing an infinite MDP over the set of configurations (current state and counter value). We consider two characteristic objectives: reaching a target state (state-reachability), and reaching a target state with counter value zero (selective termination). The synthesis problem for the latter is not known to be decidable and connected to major open problems in number theory. Furthermore, even seemingly simple strategies (e.g., memoryless ones) in OC-MDPs might be impossible to build in practice (due to the underlying infinite configuration space): we need finite, and preferably small, representations. To overcome these obstacles, we introduce two natural classes of concisely represented strategies based on a (possibly infinite) partition of counter values in intervals. For both classes, and both objectives, we study the verification problem (does a given strategy ensure a high enough probability for the objective?), and two synthesis problems (does there exist such a strategy?): one where the interval partition is fixed as input, and one where it is only parameterized. We develop a generic approach based on a compression of the induced infinite MDP that yields decidability in all cases, with all complexities within PSPACE.