# Categorizer Automata for Discounted-Sum Payoffs

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 7 of its 20 references that are in the map.
- First posted on arXiv 27 Aug 2026.

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

- [Risk-sensitive Markov Decision Process and Learning under General Utility Functions](https://mlsanity.com/paper/2311.13589/) (2023)
- [Percentile Queries in Multi-Dimensional Markov Decision Processes](https://mlsanity.com/paper/1410.4801/) (2014)
- [Comparator automata in quantitative verification](https://mlsanity.com/paper/1812.06569/) (2018)
- [Exact and Approximate Determinization of Discounted-Sum Automata](https://mlsanity.com/paper/1401.3957/) (2014)
- [The Odds of Staying on Budget](https://mlsanity.com/paper/1409.8228/) (2014)
- [Synthesis from Satisficing and Temporal Goals](https://mlsanity.com/paper/2205.10464/) (2022)
- [Multi-Agent Systems with Quantitative Satisficing Goals](https://mlsanity.com/paper/2305.00953/) (2023)

## Abstract (arXiv)

Categorizing continuous data into discrete bins is a fundamental operation in artificial intelligence. We introduce the categorizer automaton, a deterministic automaton that reads an infinite sequence of rewards and identifies which of finitely many bins contains its discounted sum. Categorizer automata generalize comparator automata, the special case of two bins, which have already proven useful in quantitative synthesis. Our main technical contribution is the construction of a categorizer automaton whose state space is linear in the number of bins, rather than exponential as obtained by a cross-product of comparator automata. We then apply categorizer automata to Markov decision processes, where they allow one to synthesize policies that maximize the expected utility of a discounted-sum payoff for utility functions that may be discontinuous. For piecewise-constant utility functions, the resulting algorithm is exact and runs in pseudo-polynomial time. For piecewise-Lipschitz utility functions, a class that includes any utility with bounded slope between finitely many jumps, it again runs in pseudo-polynomial time and yields an varepsilon-optimal policy. We also show that the synthesis problem considered is PSPACE-hard already for piecewise-constant utilities.