Paper deep dive
Categorizer Automata for Discounted-Sum Payoffs
Nathalie Bertrand, Pranav Ghorpade, Senthil Rajasekaran, Sasha Rubin, Moshe Vardi
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 90%
Last extracted: 8/28/2026, 4:10:58 AM
Summary
This paper introduces the categorizer automaton, a deterministic automaton that categorizes the discounted sum of an infinite reward sequence into one of finitely many discrete bins. It generalizes comparator automata (which handle two bins) and provides a construction with state space linear in the number of bins, avoiding the exponential blowup of cross-product methods. The authors apply this to Markov Decision Processes (MDPs) to synthesize policies maximizing expected utility for discontinuous utility functions, achieving exact solutions for piecewise-constant utilities and epsilon-optimal solutions for piecewise-Lipschitz utilities in pseudo-polynomial time. The problem is shown to be PSPACE-hard.
Entities (7)
Relation Signals (6)
Categorizer Automaton → generalizes → Comparator Automaton
confidence 95% · Categorizer automata generalize comparator automata, the special case of two bins
Categorizer Automaton → appliedto → Markov Decision Process
confidence 92% · We then apply categorizer automata to Markov decision processes, where they allow one to synthesize policies
Categorizer Automaton → hasstatecomplexity → Linear in number of bins
confidence 90% · Our main technical contribution is the construction of a categorizer automaton whose state space is linear in the number of bins
Synthesis Problem → ishardness → PSPACE-hard
confidence 90% · We also show that the synthesis problem considered is PSPACE-hard already for piecewise-constant utilities.
Categorizer Automaton → enablessynthesisfor → Piecewise-Constant Utility
confidence 88% · For piecewise-constant utility functions, the resulting algorithm is exact and runs in pseudo-polynomial time.
Categorizer Automaton → enablessynthesisfor → Piecewise-Lipschitz Utility
confidence 85% · For piecewise-Lipschitz utility functions... it again runs in pseudo-polynomial time and yields an ε-optimal policy.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract: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.
Tags
Links
- Source: https://arxiv.org/abs/2608.26763v1
- Canonical: https://arxiv.org/abs/2608.26763v1
Trouble viewing inline? Open PDF directly →
Full Text
65,749 characters extracted from source content.
Expand or collapse full text
Categorizer Automata for Discounted-Sum Payoffs Nathalie Bertrand Pranav Ghorpade Senthil Rajasekaran Sasha Rubin Moshe Vardi Abstract 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 ε -optimal policy. We also show that the synthesis problem considered is PSPACE-hard already for piecewise-constant utilities. 1Univ Rennes, Inria, CNRS, IRISA, France 2University of Sydney, Australia 3Université Libre de Bruxelles, Belgium 4 Rice University, USA 1 Introduction The fields of verification and sequential decision-making often involve assigning a numerical payoff to an infinite-length execution of a system. One of the most popular ways to reason about such executions is through the discounted-sum payoff (de Alfaro, Henzinger, and Majumdar 2003; Puterman 1994), which aggregates an infinite sequence of rewards along an execution through a discounted sum. For a discount factor d>1d>1, the discounted-sum payoff of an infinite reward sequence r0r1…r_0r_1… is d(r0r1…):=∑i=0∞d−iri DS_d(r_0r_1…):= _i=0^∞d^-ir_i. Representing numerical properties of discounted-sum payoffs with finite-state automata allows synthesis and verification problems involving such properties to be handled using efficient automata-theoretic techniques. A notable example is the development of the comparator automaton (Bansal, Chaudhuri, and Vardi 2018; Bansal, Chaudhuri, and Vardi 2022). A comparator automaton reads an infinite reward sequence w and accepts it iff d(w)⋈t DS_d(w) t, for a fixed rational threshold t and a comparison relation ⋈ such as >> or ≤. Comparator automata have since been used for synthesis for satisficing (synthesize a “good enough” policy rather than an optimal one (Simon 1956)) objectives in two-player discounted-sum games (Bansal, Chatterjee, and Vardi 2021), synthesis that combines discounted-sum payoffs with temporal specifications (Bansal et al. 2022), and Nash-equilibrium realizability under discounted-sum payoffs in deterministic multi-agent systems (Rajasekaran, Bansal, and Vardi 2023). In many settings, however, comparing the payoff with a single threshold does not provide enough information. For example, a decision maker may assign different utilities to losses, moderate gains, and large gains, or may wish to simultaneously track the payoff up to a prescribed accuracy. In this paper, we introduce the categorizer automaton, a generalization of comparator automaton. Instead of reasoning about a single threshold like the comparator automaton, the categorizer automaton simultaneously considers several thresholds that divide the real line ℝR into a series of disjoint intervals I1,…,InI_1,…,I_n. The problem then becomes categorizing an infinite reward sequence by the interval that its discounted sum lies in, as opposed to comparing its discounted sum to a single threshold. That is, a categorizer automaton A reads an infinite reward sequence and identifies the unique interval containing its discounted sum. It does this based on which states repeat infinitely often along the run, a property that is captured by the automata-theoretic Büchi condition. The comparator automaton is the special case of n=2n=2 intervals. A single boundary point splits the real line in two, and the automaton computes one bit about the payoff: whether d(w) DS_d(w) lies above or below the threshold. The use of finer partitions reveals more information about the payoff. In particular, because the discounted-sum payoff is bounded when the rewards are bounded, for every precision ε>0 >0 the bounded range of possible discounted sums can be divided into finitely many intervals of length at most ε (with the rest of ℝR covered by two unbounded intervals) so that the resulting categorizer automaton identifies an interval of width at most ε containing d(w) DS_d(w). A natural way to build a categorizer automaton is to take one comparator automaton per boundary point and construct their cross-product. This works, but the state space grows exponentially with the number n of intervals. This is prohibitively large when n is part of the input, as in the approximation regime above, where reaching precision ε forces a number of intervals that grows as ε shrinks. Our main technical contribution is a construction of the categorizer automaton that has a state space that is linear in the number n of intervals. As in the comparator automata setting, we assume that rewards are bounded integers, the boundary points are rational, and the discount factor d is an integer. Under these assumptions, for every finite partition of ℝR into intervals, our construction yields a categorizer automaton whose state space is linear in n and polynomial in the numeric value of the largest reward and the largest denominator among the boundary points when written in lowest terms. The main idea behind this construction is that the per-boundary comparisons are highly dependent on one another, rather than independent as a cross-product construction via comparator automata would suggest. Exploiting this dependence is what allows one to avoid the exponential blowup. Applications A categorizer automaton can be composed with an arbitrary finite-state model whose executions generate bounded reward sequences, including transition systems, games, Markov decision processes (MDPs), and stochastic games. In the resulting composition, the interval containing the discounted-sum payoff is represented by a Büchi condition. Thus, via categorizer automata, objectives depending on the exact payoff interval, an approximate payoff value, or both, can be reduced to automata-theoretic objectives. We apply categorizer automata to MDPs, where they allow one to synthesize policies that maximize the expected utility of a discounted-sum payoff under utility functions that may be discontinuous. Utility functions provide a standard way to express how a decision maker values different outcomes, allowing the model to reflect attitudes toward risk rather than only the payoff (Mas-Colell et al. 1995). Abrupt changes in utility (discontinuities) arise naturally when meeting a target or crossing a safety threshold. Using categorizer automata together with existing automata-theoretic techniques (Courcoubetis and Yannakakis 1998; Etessami et al. 2008), we obtain, for integer discount factors, an exact algorithm for piecewise-constant utilities with finitely many rational discontinuities. The algorithm computes the optimal expected utility and synthesizes a finite-memory policy attaining it. For utilities that are Lipschitz continuous on each of finitely many intervals but may be discontinuous at their boundaries, we build on the piecewise-constant result to compute the optimal value up to an additive error of ε and synthesize an ε -optimal policy. Both algorithms run in pseudo-polynomial time: their running times are polynomial in certain numerical parameter values, but not in the lengths of their binary encodings. This dependence is unlikely to be avoidable, as we also show that the synthesis problem is PSPACE-hard even for piecewise-constant utilities. We remark that the previous applications of comparator automata discussed above have focused on non-probabilistic models. Our application to MDPs extends the literature to stochastic settings. Related Work The classical discounted-sum payoff objective maximizes the expectation ℳθ[d]E^θ_M[ DS_d] over policies θ in an MDP ℳM. This corresponds to the linear utility u(x)=xu(x)=x and can be solved using the Bellman equations (Puterman 1994). In general, for a nonlinear utility u, the objective ℳθ[u(d)]E^θ_M[u( DS_d)] no longer admits Bellman-style equations on the original state space of the MDP (Kadota, Kurano, and Yasuda 1998). Existing algorithmic approaches typically exploit special structure in the utility, as for exponential utility (Bäuerle and Rieder 2014), or augment the state space with accumulated reward and apply discretizations or finite-horizon approximations (Wu and Xu 2023). Such approximations naturally apply to continuous utilities: truncating the discounted sum changes the payoff by a vanishing amount, and uniform continuity over the bounded payoff range then bounds the resulting change in the utility. This argument fails for discontinuous utilities. Near a discontinuity, an arbitrarily small change in the payoff can produce a large change in utility. The simplest example is a threshold utility, defined by u(x)=0u(x)=0 for x<vx<v and u(x)=1u(x)=1 for x≥vx≥ v, whose expected value is precisely the probability that the discounted-sum payoff is at least v. Threshold utilities have been studied by White (1993) and Wu and Lin (1999), who characterize Bellman-style equations on an extended, possibly infinite, state space and investigate the conditions under which optimal policies exist. From an algorithmic perspective, they have been studied in the finite-horizon setting (Xu and Mannor 2011). For the infinite-horizon setting, Randour, Raskin, and Sankur (2015) study percentile queries through an ε -gap formulation, which permits instances sufficiently close to the payoff threshold to remain unresolved. Thus, prior algorithms either restrict the horizon or relax the threshold comparison, whereas, for integer discount factors, our algorithm solves the exact problem. 2 Categorizer Automata This section introduces categorizer automata for discounted-sum payoffs (Definition 1), characterizes when categorizer automata exist (Proposition 1) and for the cases when they exist, establishes a size bound (Theorem 1). 2.1 Preliminaries Words Given a finite alphabet Σ of symbols, a word (resp. finite word) w is an infinite (resp. finite) sequence of symbols. We denote the length of a finite word as |w||w|, and refer to the unique finite word of length 00 as ε . For a word (resp. finite word) w and index 1≤i1≤ i (resp. 1≤i≤|w|1≤ i≤|w|) we denote: w[i]w[i] as the i-th symbol of w, w[1..i]w[1..i] as the length i prefix of w and w[i..]w[i..] as the suffix starting at position i. For a finite word w and a finite (resp. infinite) word w′w , we denote w⋅w′w· w as the finite (resp. infinite) word formed by concatenating w and w′w . We write Σω ^ω (resp. Σ∗ ^*) for the set of all words (resp. finite words). Transition System A (deterministic) transition system is a tuple =(Q,Σ,qinit,δ)T=(Q, ,q_init,δ), where Q is a finite set of states, Σ is a finite alphabet, qinit∈Qq_init∈ Q is the initial state, and δ:Q×Σ→Qδ:Q× → Q is a transition function. The run of T on a word w∈Σωw∈ ^ω is the sequence of states ρ=ρ[1]ρ[2]⋯ρ=ρ[1]ρ[2]·s with ρ[1]=qinitρ[1]=q_init and ρ[k+1]=δ(ρ[k],w[k])ρ[k+1]=δ(ρ[k],w[k]) for all k≥1k≥ 1. We denote (ρ)Inf(ρ) for the set of states that occur infinitely often in ρ. Given transition systems i=(Qi,Σ,qiniti,δi)T_i=(Q_i, ,q_init^i, _i), for 1≤i≤n1≤ i≤ n, over the same alphabet Σ , their cross-product is the transition system whose states are tuples (q1,…,qn)∈Q1×⋯×Qn(q_1,…,q_n)∈ Q_1×·s× Q_n, whose initial state is (qinit1,…,qinitn)(q_init^1,…,q_init^n), and whose transition on a symbol σ maps (q1,…,qn)(q_1,…,q_n) to (δ1(q1,σ),…,δn(qn,σ))( _1(q_1,σ),…, _n(q_n,σ)). Büchi Acceptance A Büchi acceptance condition is defined by a set F⊆QF Q of states. A run ρ satisfies the Büchi acceptance condition F if (ρ)∩F≠∅Inf(ρ)∩ F≠ , i.e. if at least one state of F occurs infinitely often in the run ρ. A (deterministic) Büchi automaton is a pair =(,F)A=(T,F) of a transition system and a Büchi acceptance. Its language, called the language recognized by A, is the set of words w∈Σωw∈ ^ω whose run on T satisfies F. A language (set of words) is ω-regular if it is recognized by some (possibly nondeterministic) Büchi automaton. Deterministic Büchi automata are effectively closed under intersection: given deterministic Büchi automata with states Q1Q_1, Q2Q_2 recognizing languages L1,L2L_1,L_2, one can construct a deterministic Büchi automaton with 2|Q1||Q2|2|Q_1||Q_2| states recognizing L1∩L2L_1∩ L_2 (Baier and Katoen 2008). 2.2 Discounted-sum and Categorizer Automaton Discounted-Sum Given an integer alphabet bound μ≥1μ≥ 1, we denote Σμ _μ as the finite alphabet consisting of all the integers from −μ-μ to +μ+μ. For discount factor d>1d>1, the discounted sum of a word w∈Σμωw∈ _μ^ω (resp. w∈Σμ∗w∈ _μ^*) is d(w)=∑i=1∞w[i]/di−1 DS_d(w)= _i=1^∞w[i]/d^i-1 (resp. d(w)=∑i=1|w|w[i]/di−1 DS_d(w)= _i=1^|w|w[i]/d^i-1). Binning of ℝR A binning of ℝR is a finite partition B=I1,…,InB=\I_1,…,I_n\ of ℝR into n≥2n≥ 2 nonempty, disjoint intervals, indexed so that every element of IiI_i is smaller than every element of Ii+1I_i+1. The endpoints of B are the finite infimum and supremum of its intervals: the singleton t\t\ has the one endpoint t, whereas [t,t′)[t,t ), [t,t′][t,t ], (t,t′)(t,t ), and (t,t′](t,t ] each have the two endpoints t and t′t . The outer intervals I1I_1 and InI_n are unbounded and so have one endpoint each. Writing t1<⋯<tmt_1<…<t_m for the endpoints of B in increasing order, we have m≤n−1m≤ n-1, and each IiI_i is either the singleton tj\t_j\ or an interval with endpoints tjt_j and tj+1t_j+1, for some 0≤j≤m0≤ j≤ m, where t0=−∞t_0=-∞ and tm+1=+∞t_m+1=+∞. A binning is rational if all its endpoints are rational. Definition 1 (Categorizer automaton). Let μ≥1μ≥ 1 be an integer alphabet bound, let d>1d>1 be a rational discount factor, and let B=I1,…,InB=\I_1,…,I_n\ be a rational binning of ℝR. A categorizer automaton for (μ,d,B)(μ,d,B) is a tuple =(,F1,…,Fn),A=(T,F_1,…,F_n), where =(Q,Σμ,qinit,δ)T=(Q, _μ,q_init,δ) is a deterministic transition system and each Fi⊆QF_i Q is a Büchi acceptance condition, such that, for every word w∈Σμωw∈ _μ^ω and every 1≤i≤n1≤ i≤ n, it holds that d(w)∈Ii DS_d(w)∈ I_i if and only if the run of T on w satisfies FiF_i. In other words, a categorizer automaton for (μ,d,B)(μ,d,B) is one transition system equipped with n Büchi conditions, one per interval of B such that for each i, the language of the Büchi automaton (,Fi)(T,F_i) is w∈Σμω∣d(w)∈Ii\w∈ _μ^ω DS_d(w)∈ I_i\. Relation to Comparator Automata Categorizer automata generalize comparator automata (Bansal, Chaudhuri, and Vardi 2022). Given an integer alphabet bound μ, a rational discount factor d>1d>1, a rational threshold t, and a relation ⋈∈<,>,≤,≥,=,≠ ∈\<,>,≤,≥,=,≠\, a comparator automaton is a deterministic Büchi automaton that recognizes w∈Σμω∣d(w)⋈t.\w∈ _μ^ω DS_d(w) t\. Bansal, Chaudhuri, and Vardi (2022) show that, for every relation ⋈ , such automata exist for every rational threshold t if and only if d is an integer. We now use this result to characterize when categorizer automata exist for every rational binning. To see that the integrality of d is necessary, suppose that d is not an integer. The preceding result gives a rational threshold t for which no comparator automaton recognizes w∈Σμω∣d(w)<t\w∈ _μ^ω DS_d(w)<t\. A categorizer automaton (,F1,F2)(T,F_1,F_2) for the rational binning Bt=(−∞,t),[t,+∞)B_t=\(-∞,t),[t,+∞)\ would make (,F1)(T,F_1) precisely such a comparator automaton, yielding a contradiction. Conversely, suppose that d is an integer, and fix a rational binning B=I1,…,InB=\I_1,…,I_n\. We construct a categorizer automaton for (μ,d,B)(μ,d,B) using comparator automata. For each i, first construct a deterministic Büchi automaton i=(i,Gi)A_i=(T_i,G_i) that recognizes the language Li=w∈Σμω∣d(w)∈Ii.L_i=\w∈ _μ^ω DS_d(w)∈ I_i\. Such an automaton can be constructed from comparator automata: depending on the form of IiI_i, the language LiL_i is either a comparator language or the intersection of two comparator languages. Taking the cross-product of 1,…,nT_1,…,T_n and letting FiF_i consist of the product states whose iith components belong to GiG_i yields a categorizer automaton for (μ,d,B)(μ,d,B). Hence, we obtain the following proposition. Proposition 1 (Existence of categorizer automata). Let μ≥1μ≥ 1 be an integer, and let d>1d>1 be rational. Categorizer automata for (μ,d,B)(μ,d,B) exist for every rational binning B if and only if d is an integer. For non-integer d, the situation is more complex: it is an open problem to characterize the individual rational thresholds that admit comparator automata. For integer d, although the cross-product argument above establishes the existence of a categorizer automaton, it produces one whose size is exponential in the number of bins. In the next section we present a construction that avoids this blowup. 2.3 Construction That Avoids Exponential Blowup In this section, we present a direct construction of a categorizer automaton whose size is linear in the number of bins. Throughout, qBq_B denotes the largest denominator, in lowest terms, of endpoints of B. Theorem 1. Let μ≥1μ≥ 1 be an integer alphabet bound, let d>1d>1 be an integer discount factor, and let B=I1,…,InB=\I_1,…,I_n\ be a rational binning. There exists a categorizer automaton for (μ,d,B)(μ,d,B) with (nμqB(1+logd(μqB)))O(nμ q_B(1+ _d(μ q_B))) many states and it can be constructed in (nμqB(1+logd(μqB)))O(nμ q_B(1+ _d(μ q_B))) time. The bound is linear in the number of bins and polynomial in the numerical values of μ and qBq_B (thus, it is pseudo-polynomial in μ and qBq_B). The remainder of this section proves Theorem 1 by an explicit construction. To that end, fix μ, d, and B as in Theorem 1. Let t1<⋯<tmt_1<…<t_m be the endpoints of B, set t0=−∞t_0=-∞ and tm+1=+∞t_m+1=+∞, and write each finite endpoint in lowest terms as tj=pj/qjt_j=p_j/q_j with qj>0q_j>0 so that qB=max1≤j≤mqjq_B= _1≤ j≤ mq_j. Define D=d(μ⋯)=(μd)/(d−1),D= DS_d(μ·s)=(μ d)/(d-1), so that d(w)∈[−D,D] DS_d(w)∈[-D,D] for every w∈Σμωw∈ _μ^ω. High-Level Idea After every finite word u, the states of the categorizer automaton track a gap value for each endpoint. Intuitively, the gap value of an endpoint records the discounted sum that a continuation of u must have for the complete word to have a discounted sum exactly equal to that endpoint. Since every continuation has a discounted sum in [−D,D][-D,D], a gap value outside this interval determines on which side of the endpoint every continuation must lie. If the gap value lies below −D-D (resp. above D), then, for every continuation w, the discounted sum of u⋅wu· w lies above (resp. below) the endpoint. Otherwise, different continuations can still place the discounted sum below, at, or above the endpoint. Tracking how these gap values evolve therefore allows the automaton to locate the discounted sum relative to every endpoint and, consequently, to locate the bin that contains it. Storing the tuple of all gap values explicitly would produce a state space exponential in the number of endpoints. The key observation behind our construction is that these values are not independent: all gap values can be recovered from the gap value of one endpoint and the length |u||u|. Their pairwise separations also grow exponentially with |u||u|. Consequently, after only logarithmically many symbols, at most one endpoint has a gap value in [−D,D][-D,D]. From that point onward, its gap value and index suffice to determine the position of the discounted sum relative to every endpoint. The construction therefore encodes all gap values compactly by using one gap value, its endpoint index, and, during the short initial phase, the length |u||u|. This encoding gives a construction whose size is linear in the number of bins. Gap Values Gap values are a standard tool for tracking a discounted sum relative to a single threshold (Boker and Henzinger 2014; Bansal, Chaudhuri, and Vardi 2022). For a finite word u∈Σμ∗u∈ _μ^* and an endpoint tjt_j, the gap value of tjt_j after u is defined by the recurrence gj(ε)=tj,gj(u⋅a)=d⋅(gj(u)−a)for a∈Σμ.g_j( )=t_j, g_j(u· a)=d· (g_j(u)-a ) a∈ _μ. (1) An induction on |u||u| gives the closed form gj(u)=d|u|(tj−d(u)).g_j(u)=d^\,|u| (t_j- DS_d(u) ). (2) Since d(u⋅w)=d(u)+d−|u|d(w) DS_d(u· w)= DS_d(u)+d^-|u| DS_d(w) for every w∈Σμωw∈ _μ^ω, the gap value is the discounted sum a continuation of u must have in order to reach tjt_j: for ⋈∈<,=,> ∈\<,=,>\ we have d(u⋅w)⋈tj DS_d(u· w) t_j iff d(w)⋈gj(u) DS_d(w) g_j(u). In particular, if gj(u)<−Dg_j(u)<-D (resp. gj(u)>Dg_j(u)>D) then d(u⋅w)>tj DS_d(u· w)>t_j (resp. <tj<t_j) for every continuation w; we then say tjt_j is resolved to ⊥ (resp. to ⊤ ) after u. Otherwise, i.e. if gj(u)∈[−D,D]g_j(u)∈[-D,D], we say tjt_j is active after u. The following two propositions follow from the definition of gap values and are proved in the supplementary material. Proposition 2. Let 1≤j≤m1≤ j≤ m and let w∈Σμωw∈ _μ^ω. Then d(w)>tj DS_d(w)>t_j iff tjt_j is resolved to ⊥ after some prefix of w; d(w)<tj DS_d(w)<t_j iff tjt_j is resolved to ⊤ after some prefix of w; and d(w)=tj DS_d(w)=t_j iff tjt_j is active after every prefix of w. For indices 1≤j≤m1≤ j≤ m let Gj=x/qj∣x∈ℤ∩[−D,D].G_j=\x/q_j x \∩[-D,D]. In the following proposition, P1 bounds the gaps of active endpoints, and P2 justifies the use of the term “resolved”. Proposition 3. Let u∈Σμ∗u∈ _μ^* and let 1≤j≤m1≤ j≤ m. Then: P1 if tjt_j is active after u then gj(u)∈Gjg_j(u)∈ G_j; P2 if tjt_j is resolved to ⊥ (resp. ⊤ ) after u then tjt_j is resolved to ⊥ (resp. ⊤ ) after u⋅au· a, for all a∈Σμa∈ _μ. We now describe how these facts can be used to construct a categorizer automata. The Shared Structure of Gap Values By Prop. 2 and Prop. 3, it suffices for the transition system of the categorizer automaton for (μ,d,B)(μ,d,B) to track, after every finite word, the status of every endpoint: its gap value (from the finite set GjG_j) if active, and the value ⊥,⊤ , it resolved to otherwise. However, storing the status of every endpoint explicitly requires ∏j(|Gj|+2) _j(|G_j|+2) states, which is still exponential in n. The next lemma shows that the statuses of m endpoints are not independent, which gives the ingredients for a transition system to track all of them simultaneously without incurring an exponential blowup. Lemma 1. Let u∈Σμ∗u∈ _μ^* and let K0=⌊logd(2DqB2)⌋K_0= _d(2Dq_B^2) . Then: P1 gi(u)−gj(u)=d|u|(ti−tj)g_i(u)-g_j(u)=d^\,|u|(t_i-t_j) for all 1≤i,j≤m1≤ i,j≤ m; P2 if |u|>K0|u|>K_0 then at most one endpoint is active after u; P3 there exist ℓ,r ,r with 0≤ℓ≤r≤m0≤ ≤ r≤ m such that the endpoints t1,…,tℓt_1,…,t_ are resolved to ⊥ after u, the endpoints tℓ+1,…,trt_ +1,…,t_r are active after u, and the endpoints tr+1,…,tmt_r+1,…,t_m are resolved to ⊤ after u. Proof. P1 follows from Eq. 2. For P2, let ti,tjt_i,t_j be the endpoints active after u i.e. gi(u),gj(u)∈[−D,D]g_i(u),g_j(u)∈[-D,D]. It follows that |gi(u)−gj(u)|≤2D|g_i(u)-g_j(u)|≤ 2D. Moreover, note that |ti−tj|=|piqj−pjqi|/qiqj≥1/qiqj≥1/qB2|t_i-t_j|=|p_iq_j-p_jq_i|/q_iq_j≥ 1/q_iq_j≥ 1/q_B^2. Substituting these two inequalities in P1 of the lemma, we get d|u|/qB2≤2Dd^\,|u|/q_B^2≤ 2D. Rearranging and taking the logarithm gives |u|≤K0|u|≤ K_0. For P3, since t1<⋯<tmt_1<…<t_m, by Eq. 2, g1(u)<g2(u)<⋯<gm(u)g_1(u)<g_2(u)<…<g_m(u), hence if tit_i is resolved to ⊥ i.e. gi(u)<−Dg_i(u)<-D then tjt_j for all j<ij<i is also resolved to ⊥ . Similarly for ⊤ . ∎ The Construction Formally, the categorizer automaton for (μ,d,B)(μ,d,B) is =(,F1,…,Fn)A=(T,F_1,…,F_n). We encode the status of every endpoint compactly, using a representation according to the number of endpoints active after u. Informally, after reading a finite word u, the state of transition system T records the status of every endpoint, using an encoding that depends on how many endpoints remain active after u. Accordingly, the state of T takes one of three forms: (a) if two or more endpoints are active, the state is a triple (j,gj(u),k)(j,g_j(u),k), where j is the index of smallest active endpoint and k=|u|k=|u|. This triple encodes the status of every endpoint: by P1 of Lemma 1, the gap value of every tit_i can be recovered, which in turn determines the resolved endpoints and their status; (b) If exactly one endpoint is active, the state is a pair (j,gj(u))(j,g_j(u)), where j is the index of that endpoint. By P3 of Lemma 1, t1,…,tj−1t_1,…,t_j-1 are resolved to ⊥ and tj+1,…,tmt_j+1,…,t_m to ⊤ ; (c) If no endpoint is active, the state is an integer ℓ , where t1,…,tℓt_1,…,t_ are resolved to ⊥ and tℓ+1,…,tmt_ +1,…,t_m to ⊤ . Transition System Formally, =(Q,Σμ,qinit,δ)T=(Q, _μ,q_init,δ), where Q=Qa⊎Qb⊎QcQ=Q_a Q_b Q_c is the union of the states of forms (a), (b), and (c), respectively, with Qa Q_a =(j,g,k)| 1≤j≤m,g∈Gj, 0≤k≤K0, = \\,(j,g,k)\; |\;1≤ j≤ m,\ g∈ G_j,\ 0≤ k≤ K_0\, \, Qb Q_b =(j,g)| 1≤j≤m,g∈Gj,Qc=0,…,m. = \\,(j,g)\; |\;1≤ j≤ m,\ g∈ G_j\, \, Q_c=\0,…,m\. We now describe the initial state qinitq_init and transition function δ (the formal definition is given in the supplementary material). The initial state qinit∈Qq_init∈ Q is determined by the status of the initial gap values, which by (1) coincide with the endpoints. On input a∈Σμa∈ _μ, the transition under δ can be viewed as follows. First, decode the current state into the status of every endpoint. Second, update these statuses: resolved endpoints are left unchanged (P2 of Prop. 3), whereas active endpoints are updated using their new gap values, computed as gj′=d(gj−a)g_j =d(g_j-a), as in (1). Finally, re-encode the resulting status as a state of Q, choosing the form according to the number of endpoints that remain active. Acceptance Conditions Along every run ρ of T, resolved endpoints stay resolved (P2 of Prop. 3) and eventually all but at most one of the endpoints become resolved. Hence, for a run ρ of T, there exist x≥0x≥ 0 such that either (i) for all y>xy>x we have ρ[y]=(j,g)ρ[y]=(j,g) for some 1≤j≤m1≤ j≤ m and g∈Gjg∈ G_j, or (i) for all y>xy>x we have ρ[y]=jρ[y]=j for some 0≤j≤m0≤ j≤ m. By Prop. 2, it follows that the run ρ of T on w∈Σμωw∈ _μ^ω visits (j,g)∣g∈Gj⊆Qb\(j,g) g∈ G_j\ Q_b infinitely often iff d(w)=tj DS_d(w)=t_j, and visits the state j∈Qcj∈ Q_c infinitely often iff d(w)∈(tj,tj+1) DS_d(w)∈(t_j,t_j+1). Thus Fi=(j,g)∈Qb|tj∈Ii∪j∈Qc|(tj,tj+1)⊆Ii,F_i=\(j,g)∈ Q_b\ |\ t_j∈ I_i\∪\j∈ Q_c\ |\ (t_j,t_j+1) I_i\, ensures that the run of T on w satisfies FiF_i iff d(w)∈Ii DS_d(w)∈ I_i. Size We bound |Q|=|Qa|+|Qb|+|Qc||Q|=|Q_a|+|Q_b|+|Q_c|. Since |Gj|=2⌊Dqj⌋+1≤2⌊DqB⌋+1|G_j|=2 D\ q_j +1≤ 2 D\ q_B +1 for every j, and m≤n−1m≤ n-1: |Qa|≤n(2⌊DqB⌋+1)(K0+1), |Q_a|≤ n\,(2 D\ q_B +1)\,(K_0+1), |Qb|≤n(2⌊DqB⌋+1), and |Qc|≤n. |Q_b|≤ n\,(2 D\ q_B +1), and |Q_c|≤ n. Thus |Q|=(nDqB(1+K0)).|Q|=O(nDq_B(1+K_0)). Since d≥2d≥ 2, D=(μd)/(d−1)≤2μD=(μ d)/(d-1)≤ 2μ and hence D=(μ)D=O(μ). Moreover, K0=(1+logd(μqB)).K_0=O(1+ _d(μ\ q_B)). Substituting these bounds gives |Q|=(nμqB(1+logd(μqB))).|Q|=O(nμ q_B(1+ _d(μ q_B))). This proves Theorem 1: the above bound gives the size while the correctness follows from the discussion above. 3 Application: Policy Synthesis for Maximizing Expected Utility in MDPs In this section we develop the application of categorizer automata to the problem of maximizing expected utility in Markov decision process (MDP) with discounted-sum payoffs. We provide pseudo-polynomial time algorithms and a PSPACE-hard lower bound for the synthesis problem under a broad class of utility functions. 3.1 Preliminaries We follow the standard terminology of (Puterman 1994; Baier and Katoen 2008). MDP A (discounted reward) Markov decision process (MDP) is a tuple ℳ=(S,,sinit,P,r,d)M=(S,Act,s_init,P,r,d), where S is a finite set of states, Act is a finite set of actions, sinit∈Ss_init∈ S is the initial state, P:S×S→[0,1]∩ℚP:S×Act× S→[0,1] is a transition function, r:S×→ℤr:S×Act is a reward function, and d>1d>1 is an integer discount factor. For every state s and action a we require ∑s′∈SP(s,a,s′)∈0,1 _s ∈ SP(s,a,s )∈\0,1\. When this sum equals 11, we say that a is enabled at s, and assume that at least one action is enabled at every state. We denote μℳ _M as the reward bound maxs∈S,a∈|r(s,a)| _s∈ S,\,a |r(s,a)| of MDP ℳM. Let Dℳ=μℳd/(d−1)D_M= _Md/(d-1). We write |ℳ||M| for the size of the representation of ℳM: states, actions, and nonzero transitions are counted explicitly, while transition probabilities, rewards, and the discount factor are encoded in binary. Plays and Policies A play is an infinite sequence π=s0a0s1a1⋯π=s_0\,a_0\,s_1\,a_1·s with s0=sinits_0=s_init and P(sk,ak,sk+1)>0P(s_k,a_k,s_k+1)>0 for every k≥0k≥ 0. A history is a finite prefix of a play ending in a state. Writing HℳH_M for the set of all histories, a policy is a function θ:Hℳ×→[0,1]θ:H_M×Act→[0,1] such that ∑a∈θ(h,a)=1 _a θ(h,a)=1 for every history h, and θ(h,a)=0θ(h,a)=0 whenever a is not enabled at the last state of history h. A policy is finite-memory if it can be implemented by a finite-state machine (Baier and Katoen 2008, Def. 10.97). We write Θℳ _M for the set of all policies. A policy θ induces the standard probability measure Prℳθ ^θ_M on the set of plays, equipped with the σ-algebra generated by the cylinder sets of histories. Discounted-Sum Payoff and Expected Utility Every play π determines the reward word r(s0,a0)r(s1,a1)⋯∈Σμℳωr(s_0,a_0)\,r(s_1,a_1)…∈ _ _M^ω. We denote d(π) DS_d(π) as the discounted sum of its reward word and refer to it as the discounted-sum payoff of π. The map π↦d(π)π DS_d(π) is measurable, so d DS_d is a random variable under Prℳθ ^θ_M for every policy θ. A utility function u:ℝ→ℝu:R assigns a utility value to each discounted-sum payoff. We make the standard technical assumptions that u is Borel measurable and bounded on [−Dℳ,Dℳ][-D_M,D_M]. Since every discounted-sum payoff generated by ℳM lies in [−Dℳ,Dℳ][-D_M,D_M], u(d)u( DS_d) is a bounded random variable under Prℳθ _M^θ for every policy θ. We denote Vuθ(ℳ)V_u^θ(M) as the expectation ℳθ[u(d)]E_M^θ [u( DS_d) ], and refer to it as the expected utility of θ. We denote Vu∗(ℳ)V_u^*(M) as the supremum of Vuθ(ℳ)V_u^θ(M), over all policies θ∈Θℳθ∈ _M. A policy θ is called optimal if Vuθ(ℳ)=Vu∗(ℳ)V_u^θ(M)=V_u^*(M), and ε -optimal if Vuθ(ℳ)≥Vu∗(ℳ)−εV_u^θ(M)≥ V_u^*(M)- . Büchi Events Let Z⊆SZ S be a set of states. We denote Büchi(Z) B\"uchi(Z) to be the event consisting of the plays that visit Z infinitely often. 3.2 Problem Statement and Overview In this subsection, we formalize the synthesis problem, state the results, and give high level ideas used to establish them. Piecewise-Lipschitz functions Given a rational binning B=I1,…,InB=\I_1,…,I_n\, a function u:ℝ→ℝu is piecewise-Lipschitz on B with Lipschitz constant L≥0L≥ 0 if |u(x)−u(y)|≤L|x−y||u(x)-u(y)|≤ L\,|x-y| for every i and all x,y∈Iix,y∈ I_i. In other words, within each interval, a small change in the payoff cannot cause a disproportionately large change in its utility. However, since no such restriction is imposed across different intervals, u may be discontinuous at their endpoints. The special case L=0L=0 is the piecewise-constant one, in which u takes a single value ui∈ℚu_i on each IiI_i. Synthesis Problem Instance A synthesis problem instance consists of an MDP ℳM, a rational binning B=I1,…,InB=\I_1,…,I_n\, and a utility u that is piecewise-Lipschitz on B with a given constant L≥0L≥ 0. For L=0L=0 the utility is piecewise-constant and we assume it is given explicitly, as the list of its values u1,…,un∈ℚu_1,…,u_n on the intervals of B. For L>0L>0 the problem instance additionally specifies a rational precision ε>0 >0, and the utility is presented by an evaluation oracle u u: on rational inputs x and η>0η>0 it returns a rational u^(x,η) u(x,η) with |u^(x,η)−u(x)|≤η| u(x,η)-u(x)|≤η, in time and with output length polynomial in the bit-length of x and in the numerical value 1/η1/η. Here and for the rest of the section, the bit-length of a rational number is the sum of the bit-lengths of its numerator and denominator when written in lowest terms. For L=0L=0, the task is to compute Vu∗(ℳ)V_u^*(M) exactly together with an optimal policy. For L>0L>0, the task is to compute an ε -accurate value and an ε -optimal policy. Recall that μℳ _M is the reward bound of MDP ℳM and qBq_B is the largest denominator, in lowest terms, of endpoints of B. Theorem 2 (Piecewise-constant utility). For every synthesis problem instance with L=0L=0, the optimal expected utility Vu∗(ℳ)V_u^*(M) is rational. Moreover, Vu∗(ℳ)V_u^*(M) and an optimal finite-memory policy attaining it, can be computed in time polynomial in |ℳ||M|, the number n of bins, and the numerical values μℳ _M and qBq_B. Theorem 3 (Piecewise-Lipschitz utility). For every synthesis problem instance with L>0L>0, an ε -optimal finite-memory policy and a rational number V V satisfying |V^−Vu∗(ℳ)|≤ε| V-V_u^*(M)|≤ can be computed in time polynomial in |ℳ||M|, the number n of bins, and the numerical values μℳ _M, qBq_B, ⌈L⌉ L , and ⌈1/ε⌉ 1/ . For both theorems, the running time additionally depends polynomially on the maximum bit-length of the bin endpoints and, as applicable, the values u1,…,unu_1,…,u_n, L, and ε . High-Level Idea We now give a high-level overview of the proofs of the two theorems. The full details are presented in the following subsections. Let S and d be the states and discount factor of MDP ℳM. For a piecewise-constant utility u, the expected utility for a policy θ decomposes as Vuθ(ℳ)=∑i=1nuiPrℳθ[d∈Ii].V_u^θ(M)= _i=1^nu_i\, _M^θ[ DS_d∈ I_i]. (3) Taking the product of ℳM with the categorizer automaton =(,F1,…,Fn)A=(T,F_1,…,F_n) for (μℳ,d,B)( _M,d,B) turns each event d∈Ii DS_d∈ I_i into a Büchi event Büchi(S×Fi) B\"uchi(S× F_i). The problem therefore becomes the optimization of a weighted sum of Büchi probabilities in a finite MDP, which can be solved using the techniques of Courcoubetis and Yannakakis (1998). For a piecewise-Lipschitz utility, we refine the given binning and use the evaluation oracle to construct a piecewise-constant utility u′u satisfying |u(x)−u′(x)|≤ε/2|u(x)-u (x)|≤ /2 for x∈[−Dℳ,Dℳ]x∈[-D_M,D_M]. An optimal value and policy for u′u are then ε -optimal for u. Lower Bound The algorithms of Theorems 2 and 3 are pseudo-polynomial: their running times depend on the numerical values of μℳ _M and qBq_B, rather than only on their bit-lengths. We complement these upper bounds with a hardness result that already holds for three bins and qB=1q_B=1. The QSubsetSum problem asks, given natural numbers k1,…,kN,Tk_1,…,k_N,T, with N even, whether ∃x1∈0,1∀x2∈0,1⋯∃xN−1∈0,1∀xN∈0,1:∑i=1Nxiki=T∃ x_1∈\0,1\\,∀ x_2∈\0,1\·s∃ x_N-1∈\0,1\\,∀ x_N∈\0,1\: _i=1^Nx_ik_i=T. The problem is PSPACE-complete (Travers 2006, Lem. 4) and, as observed by Haase and Kiefer (2015, §5), can be represented by a layered MDP with one level per number: the agent chooses whether to take reward kik_i at odd level i, while a fair coin makes the choice at even level i. The agent has a policy under which the total reward equals T almost surely exactly when the QSubsetSum instance is positive. Lemma 2. Deciding whether Vu∗(ℳ)≥1V_u^*(M)≥ 1 for a piecewise-constant utility u is PSPACE-hard, already for discount factor d=2d=2 and a binning B with three bins and integer endpoints, i.e. qB=1q_B=1. Proof sketch. Following the discount-balancing construction of Randour, Raskin, and Sankur (2015), in the layered MDP above set d=2d=2 and multiply each reward at level i by di−1d^i-1. The discounted-sum payoff of any play is then exactly the total reward in the original MDP. Finally, take B=(−∞,T),T,(T,+∞)B=\(-∞,T),\T\,(T,+∞)\ and assign utility 11 to T\T\ and utility 00 to the other two bins. Thus, Vu∗(ℳ)=1V_u^*(M)=1 exactly when the QSubsetSum instance is positive. Full details are provided in the supplementary material. ∎ We remark that this strongly suggests that there is no algorithm constructing categorizer automata for (μ,d,B)(μ,d,B) that runs in polynomial time in the bit-length of alphabet bound μ. 3.3 Proof of Theorem 2 In this subsection we prove Thm. 2. Fix an instance consisting of an MDP ℳ=(S,,sinit,P,r,d)M=(S,Act,s_init,P,r,d), a rational binning B=I1,…,InB=\I_1,…,I_n\, and a piecewise-constant utility u on B with value uiu_i on bin IiI_i. Let =(,F1,…,Fn)A=(T,F_1,…,F_n) be the categorizer automaton for (μℳ,d,B)( _M,d,B), with =(Q,Σμℳ,qinit,δ)T=(Q, _ _M,q_init,δ). Product with Categorizer Automaton The product ℳ⊗M is an MDP that records the current states of both the MDP ℳM and the categorizer automaton A. It has state space S×QS× Q, action set Act, initial state (sinit,qinit)(s_init,q_init), and transition probability P⊗((s,q),a,(s′,q′))=P(s,a,s′)P ((s,q),a,(s ,q ))=P(s,a,s ) if q′=δ(q,r(s,a))q =δ(q,r(s,a)), and 00 otherwise. Because the categorizer automaton A is deterministic, every play π=s0a0s1a1⋯π=s_0a_0s_1a_1·s of ℳM has a unique corresponding play π⊗=(s0,q0)a0(s1,q1)a1…π =(s_0,q_0)a_0(s_1,q_1)a_1… of ℳ⊗M , where q0=qinitq_0=q_init and qk+1=δ(qk,r(sk,ak))q_k+1=δ(q_k,r(s_k,a_k)) for every k≥0k≥ 0. Conversely, the projection of every play of ℳ⊗M on its S-component yields a unique play of ℳM. The same correspondence holds between finite histories of ℳM and ℳ⊗M and extends to their policies: given a policy θ on ℳM, define the policy θ⊗θ on ℳ⊗M by θ⊗(h⊗,a)=θ(h,a)θ (h ,a)=θ(h,a) for every pair of corresponding histories h and h⊗h . Conversely, every policy on the product determines a policy on ℳM. Corresponding histories use the same actions and transition probabilities, and hence corresponding measurable events have the same probability. Reduction By construction, a play π of ℳM satisfies d(π)∈Ii DS_d(π)∈ I_i iff the corresponding play π⊗π of ℳ⊗M visits S×FiS× F_i infinitely often. With (3) this gives, for corresponding θ and θ⊗θ , the expected utility Vuθ(ℳ)V_u^θ(M) is equal to the weighted sum ∑i=1nuiPrℳ⊗θ⊗[Büchi(S×Fi)] _i=1^nu_i _M ^θ [ B\"uchi(S× F_i) ] of Büchi probabilities. When all uiu_i are nonnegative, maximizing the right-hand side can be done using the following straightforward consequence of (Courcoubetis and Yannakakis 1998). Proposition 4. For a finite MDP N with state space Z, sets Z1,…,Zk⊆Z_1,…,Z_k Z, and weights v1,…,vk∈ℚ≥0v_1,…,v_k _≥ 0, the optimal value supθ∈Θ∑i=1kvi⋅Prθ[Büchi(Zi)] _θ∈ _N\; _i=1^kv_i· ^θ_N[ B\"uchi(Z_i)] is rational. Moreover, this value and a finite-memory policy attaining it can be computed in time polynomial in |||N|, k and the maximum bit-length of the weights. Indeed, in the corresponding theorem in (Courcoubetis and Yannakakis 1998, Thm. 5.1, § 7) the events Büchi(Zi) B\"uchi(Z_i) are given by automata that must first be composed with the MDP N, and the running time is polynomial in the size of that product. Here, each event is already a Büchi condition on the states of N, so the composition step is not needed and the rest of their proof applies. If some utility values are negative, we shift all values by a common constant before applying Prop. 4. Let c=max0,−miniuic= \0,- _iu_i\ and define u¯(x)=u(x)+c u(x)=u(x)+c. Then u¯ u is piecewise-constant on B, with value u¯i=ui+c≥0 u_i=u_i+c≥ 0 on IiI_i. By taking expectations, for every policy θ, Vu¯θ(ℳ)=Vuθ(ℳ)+cV_ u^θ(M)=V_u^θ(M)+c. Consequently, u and u¯ u have the same optimal policies, and Vu¯∗(ℳ)=Vu∗(ℳ)+cV_ u^*(M)=V_u^*(M)+c. Applying Prop. 4 to ℳ⊗M , with Büchi sets S×F1,…,S×FnS× F_1,…,S× F_n and nonnegative rational weights u¯1,…,u¯n u_1,…, u_n, computes Vu¯∗(ℳ)V_ u^*(M) and an optimal finite-memory policy θ⊗θ on the product. Subtracting c from the computed value gives Vu∗(ℳ)V_u^*(M). Transferring the policy θ⊗θ to θ of ℳM yields an optimal finite-memory policy for u: its memory maintains the current state of A together with the memory used by θ⊗θ . The size of ℳ⊗M is polynomial in |ℳ||M| and |||A|. Thm. 1 and Prop. 4 therefore give the complexity bound of Thm. 2. 3.4 Proof of Theorem 3 In this subsection, we prove Thm. 3. Fix an instance consisting of an MDP ℳ=(S,,sinit,P,r,d)M=(S,Act,s_init,P,r,d), a rational binning B=I1,…,InB=\I_1,…,I_n\, a rational precision ε>0 >0, and a piecewise-Lipschitz utility u on B with Lipschitz constant L>0L>0, represented by an evaluation oracle u u . Piecewise-Constant Approximation Let L^=⌈L⌉ L= L , E=⌈1/ε⌉E= 1/ , τ=1/(4L^E)τ=1/(4 LE), and W=⌈Dℳ/τ⌉+1W= D_M/τ +1. Thus, L≤L^L≤ L, 1/E≤ε1/E≤ , and [−Dℳ,Dℳ]⊆[−Wτ,Wτ][-D_M,D_M] [-Wτ,Wτ]. Construct a binning B′=J1,…,JrB =\J_1,…,J_r\, using the endpoints of B and the grid points kτkτ, for k∈−W,…,Wk∈\-W,…,W\, such that every bin intersecting [−Dℳ,Dℳ][-D_M,D_M] has length at most τ and every bin JiJ_i is contained in a bin of B. For every bin JiJ_i intersecting [−Dℳ,Dℳ][-D_M,D_M], choose a rational point zi∈Ji∩[−Dℳ,Dℳ]z_i∈ J_i∩[-D_M,D_M] whose bit-length is polynomial in the bit-lengths of the endpoints of JiJ_i. Query the evaluation oracle at ziz_i with precision η=1/(4E)η=1/(4E), and let ui′=u^(zi,η)u _i= u(z_i,η). Define u′(x)=ui′u (x)=u _i for every x∈Jix∈ J_i. On bins disjoint from [−Dℳ,Dℳ][-D_M,D_M], define u′u to be 00. The resulting utility u′u is piecewise-constant on B′B and satisfies |u(x)−u′(x)|≤ε/2|u(x)-u (x)|≤ /2 for every x∈[−Dℳ,Dℳ]x∈[-D_M,D_M]. Indeed, let JiJ_i be the bin containing x. Since x,zi∈Jix,z_i∈ J_i, JiJ_i has length at most τ, and JiJ_i is contained in a bin of B, the Lipschitz condition gives |u(x)−u(zi)|≤Lτ|u(x)-u(z_i)|≤ Lτ. The oracle guarantee gives |u(zi)−ui′|≤η|u(z_i)-u _i|≤η. Therefore, |u(x)−u′(x)|≤|u(x)−u(zi)|+|u(zi)−ui′|≤Lτ+η≤1/(2E)≤ε/2.|u(x)-u (x)|≤|u(x)-u(z_i)|+|u(z_i)-u _i|≤ Lτ+η≤ 1/(2E)≤ /2. Reduction and Complexity Taking expectations, for every policy θ of ℳM, Vu′θ(ℳ)−ε/2≤Vuθ(ℳ)≤Vu′θ(ℳ)+ε/2.V_u ^θ(M)- /2≤ V_u^θ(M)≤ V_u ^θ(M)+ /2. Thus, the optimal value Vu′∗(ℳ)V_u ^*(M) satisfies |Vu∗(ℳ)−Vu′∗(ℳ)|≤ε/2|V_u^*(M)-V_u ^*(M)|≤ /2, and an optimal policy θ∗θ^* for u′u is ε -optimal for u (since Vu∗(ℳ)≤Vu′θ∗(ℳ)+ε/2≤Vuθ∗(ℳ)+εV_u^*(M)≤ V_u ^θ^*(M)+ /2≤ V_u^θ^*(M)+ ). Thm. 2 computes Vu′∗(ℳ)V_u ^*(M) and such a policy θ∗θ^*. Since d≥2d≥ 2, we have Dℳ≤2μℳD_M≤ 2 _M, and hence W=(μℳL^E)W=O( _M LE). Therefore, the number r of bins of B′B is on the order of n+(μℳL^E)n+O( _M LE). Moreover, since every new endpoint is of the form k/(4L^E)k/(4 LE), the largest denominator qB′q_B is at most maxqB,4L^E \q_B,4 LE\. Constructing u′u requires r oracle calls, each with precision η=1/(4E)η=1/(4E). By the choice of the query points and the oracle assumption, the total running time of these calls and the bit-lengths of their outputs are polynomial in r, the bit-lengths of the endpoints of B′B , and the numerical value E. Together with the bounds on r and qB′q_B above, Thm. 2 gives the running-time bound claimed in Thm. 3. 4 Conclusion We introduced categorizer automata and showed how to construct them in time and space linear (rather than exponential) in the number of bins. We then applied this construction to obtain algorithms for synthesizing policies that maximize the expected utility of the payoff for a broad class of (possibly) discontinuous utilities. We view this as one instance of a broader use of categorizer automata. A natural next step is to synthesize policies in MDPs that optimize soft quantitative preferences, expressed through discounted-sum payoffs, subject to hard qualitative requirements, expressed by LTL specifications. These two objectives are typically handled using different algorithmic techniques, see (Puterman 1994) and (Baier and Katoen 2008). A categorizer automaton bridges the mismatch by translating the quantitative payoff into ω-regular conditions. Finally, our construction of categorizer automata, like the comparator automata before it, requires the discount factor to be an integer. One potential route to non-integer discount factors is an approximate categorizer automaton, in the spirit of Randour, Raskin, and Sankur (2015), that is required to identify the correct bin only when the payoff is at a distance greater than ε from every endpoint. This relaxation introduces only a vanishing utility error when the utility is continuous at the endpoints. At a discontinuity, however, it cannot recover the guarantees of Theorems 2 and 3, and new ideas are needed. References Baier and Katoen (2008) Baier, C.; and Katoen, J. 2008. Principles of model checking. MIT Press. Bansal, Chatterjee, and Vardi (2021) Bansal, S.; Chatterjee, K.; and Vardi, M. Y. 2021. On Satisficing in Quantitative Games. In Groote, J. F.; and Larsen, K. G., eds., Tools and Algorithms for the Construction and Analysis of Systems TACAS 2021, Lecture Notes in Computer Science, 20–37. Springer. Bansal, Chaudhuri, and Vardi (2018) Bansal, S.; Chaudhuri, S.; and Vardi, M. Y. 2018. Comparator Automata in Quantitative Verification. In FoSSaCS, volume 10803 of Lecture Notes in Computer Science, 420–437. Springer. Bansal, Chaudhuri, and Vardi (2022) Bansal, S.; Chaudhuri, S.; and Vardi, M. Y. 2022. Comparator automata in quantitative verification. Logical Methods in Computer Science, 18. Bansal et al. (2022) Bansal, S.; Kavraki, L.; Vardi, M.; and Wells, A. 2022. Synthesis from Satisficing and Temporal Goals. Proceedings of the AAAI Conference on Artificial Intelligence, 36: 9679–9686. Boker and Henzinger (2014) Boker, U.; and Henzinger, T. A. 2014. Exact and Approximate Determinization of Discounted-Sum Automata. Log. Methods Comput. Sci., 10(1). Bäuerle and Rieder (2014) Bäuerle, N.; and Rieder, U. 2014. More Risk-Sensitive Markov Decision Processes. Mathematics of Operations Research, 39(1): 105–120. Courcoubetis and Yannakakis (1998) Courcoubetis, C.; and Yannakakis, M. 1998. Markov decision processes and regular events. IEEE Trans. Autom. Control., 43(10): 1399–1418. de Alfaro, Henzinger, and Majumdar (2003) de Alfaro, L.; Henzinger, T. A.; and Majumdar, R. 2003. Discounting the Future in Systems Theory. In ICALP, volume 2719 of Lecture Notes in Computer Science, 1022–1037. Springer. Etessami et al. (2008) Etessami, K.; Kwiatkowska, M.; Vardi, M. Y.; and Yannakakis, M. 2008. Multi-Objective Model Checking of Markov Decision Processes. Logical Methods in Computer Science, Volume 4, Issue 4: 8. Haase and Kiefer (2015) Haase, C.; and Kiefer, S. 2015. The Odds of Staying on Budget. In ICALP (2), volume 9135 of Lecture Notes in Computer Science, 234–246. Springer. Kadota, Kurano, and Yasuda (1998) Kadota, Y.; Kurano, M.; and Yasuda, M. 1998. On the General Utility of Discounted Markov Decision Processes. International Transactions in Operational Research, 5(1): 27–34. Mas-Colell et al. (1995) Mas-Colell, A.; Whinston, M. D.; Green, J. R.; et al. 1995. Microeconomic theory, volume 1. Oxford university press New York. Puterman (1994) Puterman, M. L. 1994. Markov Decision Processes: Discrete Stochastic Dynamic Programming. Wiley Series in Probability and Statistics. Wiley. Rajasekaran, Bansal, and Vardi (2023) Rajasekaran, S.; Bansal, S.; and Vardi, M. Y. 2023. Multi-Agent Systems with Quantitative Satisficing Goals. In IJCAI, 280–288. ijcai.org. Randour, Raskin, and Sankur (2015) Randour, M.; Raskin, J.-F.; and Sankur, O. 2015. Percentile Queries in Multi-dimensional Markov Decision Processes. In Kroening, D.; and Păsăreanu, C. S., eds., Computer Aided Verification, 123–139. Cham: Springer International Publishing. ISBN 978-3-319-21690-4. Simon (1956) Simon, H. A. 1956. Rational choice and the structure of the environment. Psychological Review, 63(2): 129–138. Travers (2006) Travers, S. D. 2006. The complexity of membership problems for circuits over sets of integers. Theor. Comput. Sci., 369(1-3): 211–229. White (1993) White, D. J. 1993. Minimizing a Threshold Probability in Discounted Markov Decision Processes. Journal of Mathematical Analysis and Applications, 173(2): 634–646. Wu and Lin (1999) Wu, C.; and Lin, Y. 1999. Minimizing Risk Models in Markov Decision Processes with Policies Depending on Target Values. Journal of Mathematical Analysis and Applications, 231(1): 47–67. Wu and Xu (2023) Wu, Z.; and Xu, R. 2023. Risk-sensitive Markov Decision Process and Learning under General Utility Functions. CoRR, abs/2311.13589. Xu and Mannor (2011) Xu, H.; and Mannor, S. 2011. Probabilistic goal Markov decision processes. In Proceedings of the Twenty-Second international joint conference on Artificial Intelligence - Volume Volume Three, IJCAI’11, 2046–2052. Barcelona, Catalonia, Spain: AAAI Press. ISBN 978-1-57735-515-1. Appendix A Supplementary Material A.1 Categorizer Automata Proof of Proposition 2. Fix j and w, and abbreviate gk=gj(w[1..k])g^k=g_j(w[1..k]) and σk=d(w[k+1..])∈[−D,D]σ^k= DS_d(w[k+1..])∈[-D,D]. Since d(w)=d(w[1..k])+d−kσk DS_d(w)= DS_d(w[1..k])+d^-kσ^k, the closed form (2) gives tj−d(w)=d−k(gk−σk)for every k≥0.t_j- DS_d(w)\;=\;d^-k(g^k-σ^k) every k≥ 0. (4) If gk<−Dg^k<-D for some k, then gk−σk<0g^k-σ^k<0 because σk≥−Dσ^k≥-D, so d(w)>tj DS_d(w)>t_j by (4); symmetrically, gk>Dg^k>D for some k implies d(w)<tj DS_d(w)<t_j. If gk∈[−D,D]g^k∈[-D,D] for all k, then |gk−σk|≤2D|g^k-σ^k|≤ 2D, so |tj−d(w)|≤2Dd−k|t_j- DS_d(w)|≤ 2D\,d^-k for all k, and the right-hand side tends to 00 as k tends to infinity because d>1d>1; hence d(w)=tj DS_d(w)=t_j. The three hypotheses above say that tjt_j is resolved to ⊥ after some prefix of w, resolved to ⊤ after some prefix of w, and active after every prefix of w, respectively. They are exhaustive, since gk∉[−D,D]g^k∉[-D,D] means gk<−Dg^k<-D or gk>Dg^k>D, and pairwise disjoint: the third excludes the other two by definition, and the first two exclude each other because their conclusions d(w)>tj DS_d(w)>t_j and d(w)<tj DS_d(w)<t_j do. Since the three conclusions are likewise exhaustive and pairwise disjoint, each implication is in fact an equivalence. ∎ Proof of Proposition 3. P1. We claim that gj(u)∈1qjℤg_j(u)∈ 1q_jZ for every u∈Σμ∗u∈ _μ^*. Indeed, by (2), gj(u)=d|u|pjqj−∑i=1|u|u[i]d|u|−i+1,g_j(u)\;=\; d^|u|p_jq_j- _i=1^|u|u[i]\,d^|u|-i+1, where the sum is an integer because d is an integer and |u|−i+1≥1|u|-i+1≥ 1 for 1≤i≤|u|1≤ i≤|u|. If tjt_j is active after u then moreover gj(u)∈[−D,D]g_j(u)∈[-D,D], so gj(u)∈Gjg_j(u)∈ G_j. P2. Since D−μ=μ/(d−1)D-μ=μ/(d-1), the bound D is the gap update at the integer bound μ: d(D−μ)=Dandd(−D+μ)=−D.d\,(D-μ)=D d\,(-D+μ)=-D. (5) Let a∈Σμa∈ _μ, so −μ≤a≤μ-μ≤ a≤μ. If tjt_j is resolved to ⊥ after u, i.e. gj(u)<−Dg_j(u)<-D, then gj(u)−a<−D+μg_j(u)-a<-D+μ, and multiplying by d>0d>0 and using (5) gives gj(u⋅a)=d(gj(u)−a)<d(−D+μ)=−D,g_j(u· a)\;=\;d\,(g_j(u)-a)\;<\;d\,(-D+μ)\;=\;-D, so tjt_j is resolved to ⊥ after u⋅au· a. Symmetrically, if gj(u)>Dg_j(u)>D then gj(u)−a>D−μg_j(u)-a>D-μ and gj(u⋅a)>d(D−μ)=Dg_j(u· a)>d\,(D-μ)=D, so tjt_j remains resolved to ⊤ . ∎ Formal Definition of qinitq_init Recall that by (1) we have gi(ε)=tig_i( )=t_i. Let Ainit=i∣ti∈[−D,D]A_init=\i t_i∈[-D,D]\ and ℓinit=maxi∣ti<−D, _init= \i t_i<-D\, where we use the convention max∅=0 =0. Accordingly, qinit=(j,tj,0),j=minAinitif |Ainit|≥2,(j,tj)if Ainit=j,ℓinitif Ainit=∅.q_init= cases(j,t_j,0),\ j= A_init&if |A_init|≥ 2,\\ (j,t_j)&if A_init=\j\,\\ _init&if A_init= . cases Formal Definition of δ Let s∈Qs∈ Q be a state and let r∈Σμr∈ _μ be an input symbol. The transition δ(s,r)δ(s,r) is defined as follows: • ∈s∈ Q_a Let s=(j,g,k)s=(j,g,k). We call s consistent if g−dktj∈ℤg-d^kt_j . If s is not consistent, set δ(s,r)=sδ(s,r)=s. Every state in QaQ_a reachable from qinitq_init is consistent: if it is reached after a word u of length k, then by (2), g−dktj=−dkd(u)∈ℤ.g-d^kt_j=-d^k DS_d(u) . Hence, the self-loops added above do not affect any run from qinitq_init. Suppose now that s is consistent. First reconstruct g^h=g+dk(th−tj) g_h=g+d^k(t_h-t_j) for 1≤h≤m1≤ h≤ m, as in P1 of Lemma 1, and then apply update (1) to obtain g^h′=d(g^h−r) g _h=d( g_h-r). Let A′=i∣g^i′∈[−D,D],ℓ′=maxi∣g^i′<−D.A =\i g_i ∈[-D,D]\, = \i g_i <-D\. The successor s′=δ(s,r)s =δ(s,r) is determined by |A′||A |: – if |A′|≥2|A |≥ 2, then s′=(j′,g^j′,k+1)s =(j , g_j ,k+1) with j′=minA′j = A ; – if A′=hA =\h\, then s′=(h,g^h′)s =(h, g_h ); – if A′=∅A = , then s′=ℓ′s = . • ∈s∈ Q_b Let s=(j,g)s=(j,g), let g′=d(g−r)g =d\,(g-r) as in (1), and set δ(s,r)=(j,g′)if g′∈[−D,D],jif g′<−D,j−1if g′>D.δ(s,r)= cases(j,g )&if g ∈[-D,D],\\ j&if g <-D,\\ j-1&if g >D. cases • ∈s∈ Q_c δ(s,r)=sδ(s,r)=s. A.2 Lower Bound Proof of Lemma 2. We give the details of the reduction from QSubsetSum described in the proof sketch. Fix an instance k1,…,kN,Tk_1,…,k_N,T, where N is even. We construct the MDP ℳM shown in Figure 1 and set its discount factor to d=2d=2. For every odd i, the MDP has one state cic_i, while for every even i, it has two states ci0c_i^0 and ci1c_i^1. It also has an absorbing state ssinks_sink, and its initial state is c1c_1. Thus, ℳM has 3N/2+13N/2+1 states. At an odd-level state cic_i, the actions take and skip are enabled. Under either action, the next state is ci+10c_i+1^0 or ci+11c_i+1^1, each with probability 1/21/2. The rewards of these actions are r(ci,)=kidi−1andr(ci,)=0.r(c_i, take)=k_id^i-1 r(c_i, skip)=0. At an even-level state cibc_i^b, where b∈0,1b∈\0,1\, exactly one action is enabled, and its reward is bkidi−1b\,k_id^i-1. For i<Ni<N, this action leads with probability one to ci+1c_i+1; from level N, it leads to ssinks_sink. The only action enabled at ssinks_sink has reward 00 and returns to ssinks_sink. For a play π, let xi(π)∈0,1x_i(π)∈\0,1\ indicate whether kik_i is taken. At an odd level, this is determined by whether the policy chooses take or skip. At an even level, it is determined by whether the play enters ci1c_i^1 or ci0c_i^0. The reward associated with level i is collected at step i−1i-1. Therefore, d(π)=∑i=1Nxi(π)kidi−1di−1=∑i=1Nxi(π)ki. DS_d(π)= _i=1^N x_i(π)k_id^i-1d^i-1= _i=1^Nx_i(π)k_i. Thus, the scaling by di−1d^i-1 exactly cancels the discounting. The rewards may be exponentially large in value, but multiplying kik_i by 2i−12^i-1 increases its binary encoding length by only i−1i-1. Hence, ℳM can be constructed in time polynomial in the size of the QSubsetSum instance. Consider the three-bin binning B=(−∞,T),T,(T,+∞)B=\(-∞,T),\T\,(T,+∞)\ 11 1 Binning B=(−∞,T−1],(T−1,T+1),[T+1,+∞)B=\(-∞,T-1],(T-1,T+1),[T+1,+∞)\ also works as the discounted-sum payoff is always an integer. and the piecewise-constant utility u that is 11 on T\T\ and 00 on the other two bins. All endpoints are integers, so qB=1q_B=1. Viewing each xix_i as a random variable on plays, for every policy θ we have Vuθ(ℳ)=Prℳθ[∑i=1Nxiki=T].V_u^θ(M)= _M^θ [ _i=1^Nx_ik_i=T ]. Since u takes values in 0,1\0,1\, we have Vu∗(ℳ)≤1V_u^*(M)≤ 1. Moreover, only the first N steps affect the payoff, so an optimal policy exists. It follows that Vu∗(ℳ)≥1V_u^*(M)≥ 1 exactly when some policy makes the sum equal to T almost surely. By (Haase and Kiefer 2015) such a policy exists exactly when the QSubsetSum instance is positive. The reduction is polynomial and uses the fixed discount factor d=2d=2, three bins, and integer endpoints. The claimed PSPACE-hardness follows. ∎ c1c_1c21c_2^1c20c_2^0c3c_3⋯·sssinks_sink:k1 take k_1:0 skip 012 1212 12k2dk_2d00:k3d2 take k_3d^2:0 skip 000level 11level 22level 33sink Figure 1: The layered MDP ℳM used in the lower bound. At odd levels, edge labels give the action and its reward. At even levels and at ssinks_sink, only one action is enabled, so only its reward is shown. Filled dots denote fair probabilistic branching. The repeated levels after level 33 are omitted.