Source-linked AI summary
Categorizer Automata for Discounted-Sum Payoffs
Nathalie Bertrand, Pranav Ghorpade, Senthil Rajasekaran, Sasha Rubin, Moshe Vardi
TL;DR
The paper addresses how to classify discounted sums into multiple payoff bins and optimize expected utility when utilities may be discontinuous. It introduces categorizer automata with a state space linear in the number of bins, then applies them to MDP policy synthesis. The resulting algorithms are exact for piecewise-constant utilities and ε-optimal for piecewise-Lipschitz utilities, while the synthesis problem is PSPACE-hard in a restricted case.
Problem
Single-threshold comparisons are insufficient for utilities that distinguish multiple payoff regions or require prescribed payoff accuracy, while discontinuities defeat standard continuous-utility approximations.
Method
The paper constructs categorizer automata that identify which interval contains a discounted sum, compactly encoding dependent boundary comparisons instead of taking their cross-product.
Results
The construction has state space linear in the number of bins; it yields exact pseudo-polynomial synthesis for piecewise-constant utilities, ε-optimal pseudo-polynomial synthesis for piecewise-Lipschitz utilities, and PSPACE-hardness already with three bins and d = 2.
Takeaways & Limitations
Categorizer automata provide a bridge from discounted-sum payoff intervals to automata-theoretic policy synthesis for stochastic models and discontinuous utility functions.
Takeaways & Limitations
The construction requires an integer discount factor; for non-integer factors, approximate categorization cannot recover the discontinuous-utility guarantees without new ideas.
Abstract
from arXiv · showhide
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.
1 Introduction
Discounted-sum payoffs support quantitative reasoning over infinite executions, but single-threshold comparisons are insufficient for richer utility and precision requirements. The paper introduces categorizer automata, whose compact construction supports applications to stochastic decision-making with potentially discontinuous utilities.
- Motivation: Discounted-sum payoffs aggregate infinite reward sequences and underpin numerical objectives in verification and sequential decision-making.Finite-state automata can represent numerical properties of these payoffs for synthesis and verification.
- Prior approach: Comparator automata classify discounted sums against one threshold and have supported synthesis for games, temporal specifications, and multi-agent equilibria.Their applications include satisficing objectives, combined payoff-temporal objectives, and Nash-equilibrium realizability.
- Motivation: Single-threshold comparisons cannot express utilities that distinguish multiple payoff regions or track payoffs to a prescribed accuracy.Such settings may distinguish losses, moderate gains, and large gains.
- Categorizer automata: Categorizer automata partition the real line into disjoint intervals and identify the interval containing an infinite reward sequence’s discounted sum using a Büchi condition.Comparator automata arise as the special case of two intervals, while finer partitions provide more payoff information.
- Construction challenge: A cross-product of one comparator automaton per boundary causes exponential state growth as the number of intervals increases.This becomes especially problematic when finer precision requires more intervals.
- Construction: The paper’s construction uses dependence among boundary comparisons to obtain state space linear in the number of intervals under bounded-integer rewards, rational boundaries, and integer discount factors.The construction avoids the exponential blowup of the comparator cross-product.
- Applications: Categorizer automata compose with finite-state models, including MDPs, and reduce exact or approximate payoff-interval objectives to automata-theoretic objectives.Their MDP application targets expected utility maximization for utilities that may be discontinuous.
- Utility challenge: Continuous-utility truncation and discretization methods do not directly handle discontinuities, where arbitrarily small payoff changes can cause large utility changes.For threshold utilities, the expected utility equals the probability that the discounted sum reaches the threshold.
2 Categorizer Automata
Categorizer automata classify infinite reward sequences by the interval containing their discounted sum, extending comparator automata to multiple bins. For integer discount factors, the paper gives a direct construction with state space linear in the number of bins, avoiding the exponential cross-product blowup.
- Categorizer Automata: A categorizer automaton uses one deterministic transition system with n Büchi conditions, one for each interval of a rational binning.Each condition accepts exactly the reward sequences whose discounted sum lies in its associated interval.
- Relation to Comparator Automata: Comparator automata are the special case of two intervals, whereas categorizer automata classify discounted sums across finitely many intervals.Comparator automata determine whether a discounted sum lies above or below one threshold; categorizer automata distinguish multiple bins.
- Existence: Categorizer automata exist for every rational binning if and only if the discount factor d is an integer.For non-integer d, some rational threshold lacks a comparator automaton, while integer d permits construction through comparator automata.
- Construction That Avoids Exponential Blowup: The comparator cross-product has exponentially many states in the number of bins, making it impractical when the bin count is part of the input.The construction in the paper instead exploits dependencies among endpoint gap values rather than storing all endpoint statuses independently.
- Size: O(nµqB(1 + log_d(µqB))) states and construction time are achieved for integer d, with size linear in n and polynomial in µ and qB.Here qB is the largest denominator of a bin endpoint in lowest terms, so the bound is pseudo-polynomial in the numeric parameters.
- Construction: The construction tracks endpoint statuses compactly, using gap values and endpoint indices once at most one endpoint remains active.Its acceptance conditions then ensure that the run satisfies Fi exactly when the discounted sum belongs to interval Ii.
3 Application: Policy Synthesis for Maximizing Expected Utility in MDPs
The paper applies categorizer automata to synthesize finite-memory MDP policies maximizing expected utility for discounted-sum payoffs, including discontinuous utilities. It gives exact pseudo-polynomial algorithms for piecewise-constant utilities, ε-optimal algorithms for piecewise-Lipschitz utilities, and a PSPACE-hardness result.
- Problem formulation: The synthesis problem maximizes the expected utility of a discounted-sum payoff over policies in a finite MDP.MDPs use bounded integer rewards, rational transition probabilities, and an integer discount factor.
- Problem formulation: Piecewise-Lipschitz utilities may be discontinuous at bin endpoints while remaining Lipschitz within each interval.The piecewise-constant case is the special case L = 0, with one utility value per interval.
- Results: For piecewise-constant utilities, the optimal expected utility is rational and an optimal finite-memory policy is computable in pseudo-polynomial time.The running time is polynomial in |M|, the number of bins, and the numerical values of µM and qB, with additional polynomial dependence on endpoint bit-lengths and utility values.
- Results: For piecewise-Lipschitz utilities, the algorithm computes an ε-accurate value and an ε-optimal finite-memory policy in pseudo-polynomial time.It approximates the utility by a piecewise-constant utility u′ within ε/2 and solves the resulting exact problem.
- Solution approach: The product of an MDP and a categorizer automaton converts each payoff-bin event into a Büchi event and reduces optimization to a weighted sum of Büchi probabilities.The resulting product MDP records both the MDP state and automaton state.
- Complexity: The synthesis problem is PSPACE-hard for piecewise-constant utilities, even with discount factor d = 2 and three bins with integer endpoints.The lower bound already holds for qB = 1.
4 Conclusion
The paper introduces categorizer automata, applies them to expected-utility policy synthesis, and identifies integer discount factors as a limitation with unresolved discontinuous-utility guarantees for non-integer factors.
- Categorizer automata can be constructed in time and space linear in the number of bins rather than exponential.
- The construction supports policy synthesis in MDPs that maximizes expected utility for possibly discontinuous discounted-sum utilities.
- Categorizer automata can translate quantitative discounted-sum payoffs into ω-regular conditions for combining soft preferences with hard LTL requirements.
- The construction requires an integer discount factor, and approximate categorization cannot recover the stated guarantees at utility discontinuities.For continuous utility at endpoints, the approximation introduces only a vanishing utility error.
A.1 Categorizer Automata
The categorizer automaton tracks threshold-specific gap values through bounded and resolved states, with transitions preserving threshold classifications and reachable-state consistency.
- For each threshold, the proof classifies runs as eventually resolved below, eventually resolved above, or active after every prefix.These cases are exhaustive and pairwise disjoint, and their conclusions distinguish discounted sums below, above, or equal to the threshold.
- Active gap values lie on a discrete grid determined by the integer discount factor and reward bound, enabling a finite state-space construction.The update maps the boundary region back to itself through d(D−µ)=D and d(−D+µ)=−D.
- Resolved threshold states remain resolved under subsequent rewards because the bounded reward range preserves the gap beyond the resolution boundary.
- The initialization selects the first relevant threshold or a lower resolved state based on which thresholds initially lie within the bounded gap range.
- The transition function distinguishes active, resolved, and absorbing state classes, with the latter using self-loops.
- Reachable active states satisfy an integer consistency condition, while inconsistent states receive self-loops that do not affect runs from the initial state.
- Transitions for active states reconstruct threshold gaps, update them with the input reward, and select successors according to the set of active thresholds.
A.2 Lower Bound
The lower-bound reduction encodes QSubsetSum in a layered MDP whose three-bin utility rewards exact target achievement, establishing PSPACE-hardness under fixed discount and integer endpoints.
- The layered MDP has one level per number, with agent choices at odd levels and fair probabilistic choices at even levels.
- The construction contains 3N/2+1 states and sends the final level to an absorbing state whose only action has reward zero.
- At odd level i, take yields reward ki d^(i−1) and skip yields zero; at even level i, the single enabled action yields bki d^(i−1).
- The reduction uses discount factor d = 2, three bins, and integer endpoints, and is polynomial in the QSubsetSum instance size.The construction therefore establishes PSPACE-hardness for the synthesis problem.
- The reward scaling by d^(i−1) cancels discounting while increasing binary encoding length by only i−1.
- The three-bin utility is one only for discounted sum T and zero for sums below or above T, so its expected value tests exact target attainment.
- An optimal policy achieves value at least 1 exactly when some policy makes the encoded sum equal T almost surely, which holds exactly for positive QSubsetSum instances.