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

Michal Ajdarów, James C. A. Main, Jan Křetínský, Mickaël Randour

Abstract

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.

Introduction

Markov Decision Processes (MDPs) are the standard mathematical framework for modeling decision-making in environments where outcomes are partly random and partly under the control of a decision-maker. One-Counter MDPs (OC-MDPs) extend this by adding a single counter—representing resources like energy, time, or queue length—that can increment, decrement, or stay the same at each step.

Because the counter can theoretically grow to infinity, the state space of an OC-MDP is infinite. This makes finding a winning strategy incredibly difficult. This research focuses on two primary goals: state-reachability (reaching a target state regardless of the counter value) and selective termination (reaching a target state with a counter value of exactly zero). The general problem of synthesizing a strategy for selective termination in unbounded OC-MDPs is tied to major unsolved problems in number theory and its decidability remains an open question. This paper addresses these challenges by introducing "interval strategies," which are both natural to human decision-making and computationally manageable.

Methodology: Interval Strategies and Compression

To bypass the undecidability of the general problem, the authors introduce Interval Strategies. Instead of assigning a unique action to every possible counter value from zero to infinity, an interval strategy partitions the counter values into "chunks" (intervals) and applies the same decision logic within each chunk. Two types are defined:

  • Open-Ended Interval Strategies (OEIS): These use a finite number of intervals, ending with an open-ended interval (e.g., $[1, 10], [11, 100], [101, \infty)$). This mimics a "rich man's strategy"—if resources are above a certain threshold, the player adopts a static, aggressive strategy.
  • Cyclic Interval Strategies (CIS): These utilize a repeating, periodic partition of intervals (e.g., repeating the same decision logic every 5 units).

To analyze these strategies, the authors developed a novel Compressed Markov Chain technique. They take the infinite Markov chain generated by the strategy and compress it by aggregating configurations and transitions. Because the transition probabilities in this compressed chain can be irrational numbers, they are characterized as the least solutions to quadratic systems of equations. This allows the reduction of verification and synthesis (realisability) problems to checking logical formulas in the "theory of the reals."

Key Results and Complexity

The core contribution of this work is proving that both verification and realisability are decidable for interval strategies. The authors established strict upper bounds, showing that all considered problems fall within the PSPACE complexity class.

Summary of complexity results for verification and realisability of interval strategies in OC-MDPs.

As shown in the table above, the complexity varies based on the semantics (Bounded vs. Unbounded) and the strategy type (Open-ended vs. Cyclic). Notably, the research highlights that while deterministic (pure) strategies are often sufficient in standard MDPs, allowing randomization in interval strategies can yield higher success probabilities due to the structural constraints of the intervals. Furthermore, all considered problems were proven to be "square-root-sum-hard," a significant lower bound in numerical computation.

Key Insights

  • Taming Infinity: Grouping counter values into intervals formalizes the intuition that optimal actions rarely change between very large, similar resource values (e.g., 10,000 vs 10,001 units).
  • Exponential Succinctness: Interval strategies can be exponentially more concise than traditional finite-memory representations like Mealy machines.
  • Compression as a Bridge: The mathematical trick of compressing an infinite Markov chain into a finite one by solving quadratic equations is the key to bridging the gap between infinite state spaces and finite computational algorithms.

Limitations and Future Work

While interval strategies are expressive and computationally friendly, they are not always sufficient to play perfectly optimally in unbounded OC-MDPs, though they can approximate the optimal probability. The general OC-MDP synthesis problem without structural constraints remains a major open question. Future work may extend these compression techniques to "ultimately periodic interval partitions," a hybrid strategy that combines unique finite intervals with repeating cyclic patterns.

Summary updated

Abstract

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.
BibTeX
@misc{ajdarow2025taming,
  author = {Michal Ajdarów and James C. A. Main and Jan Křetínský and Mickaël Randour},
  title = {{Taming Infinity One Chunk at a Time: Concisely Represented Strategies in One-Counter MDPs}},
  year = {2025},
  eprint = {2503.00788},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2503.00788},
}
Figure