Partitioning continuous data into discrete bins is a fundamental operation in artificial intelligence. This paper introduces the categorizer automaton, a deterministic automaton that reads an infinite reward sequence and determines which predefined bin contains its discounted sum. The categorizer automaton generalizes comparator automata, which handle only two bins and have already been useful in quantitative synthesis. The main technical contribution is a construction whose state space grows linearly with the number of bins, avoiding the exponential blow‑up of a cross‑product of comparator automata. We then apply categorizer automata to Markov decision processes (MDPs), enabling the synthesis of policies that maximize the expected utility of a discounted‑sum payoff even when the utility function is discontinuous. For piecewise‑constant utilities the algorithm is exact and runs in pseudo‑polynomial time. For piecewise‑Lipschitz utilities—functions whose slope is bounded between finitely many jumps—it also runs in pseudo‑polynomial time and yields a $\varepsilon$‑optimal policy. Moreover, we show that the synthesis problem is PSPACE‑hard already for piecewise‑constant utilities.
Blogger's Review: The linear‑size construction of categorizer automata dramatically reduces the complexity of discretizing discounted sums, offering a practical tool for handling discontinuous utility functions and bridging theory with real‑world applications.