Categorizer Automata for Discounted-Sum Payoffs

• URL: http://arxiv.org/abs/2608.26763v1
• Date: Thu, 27 Aug 2026 07:56:16 GMT
• Title: Categorizer Automata for Discounted-Sum Payoffs
• Abstract summary: 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.<n>We apply categorizer automata to Markov decision processes, where they allow one to synthesize policies that maximize the expected utility of a discounted-sum payoff.<n>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.
• Score: 4.8981980337377555
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• SSTQ:Privacy-Preserving Vector Quantization via Subsampled Stochastic TurboQuant [79.24089819400126]
  Subsampled TurboQuant (SSTQ) is a framework that combines overcomplete equal-width tight frames, coordinate subsampling, and privacy-aware quantization.<n>SSTQ achieves mean squared error scaling while using only $lceil log N il + b$ bits per client, where $N = (d)$ is the frame size.<n>We also derive a surrogate privacy-aware codebook objective that reduces the codebook-dependent MSE scaling from $O(4b)$ to $O(2b)$.
  arXiv  Detail & Related papers  (2026-08-05T17:51:25Z)
• AutoLALA: Automatic Loop Algebraic Locality Analysis for AI and HPC Kernels [6.223124502234209]
  AutoLALA is an open-source tool that analyzes data locality in affine loop programs.<n>It produces closed-form symbolic formulas for reuse distance and data movement complexity.
  arXiv  Detail & Related papers  (2026-04-06T18:12:39Z)
• On the Statistical Query Complexity of Learning Semiautomata: a Random Walk Approach [59.589793281734636]
  We show that Statistical Query hardness can be established when both the alphabet size and input length are in the number of states.<n>Our result is derived solely from the internal state-transition structure of semiautomata.
  arXiv  Detail & Related papers  (2025-10-05T09:35:35Z)
• Learning Quantitative Automata Modulo Theories [17.33092604696224]
  We present QUINTIC, an active learning algorithm, wherein the learner infers a valid automaton through deductive reasoning. Our evaluations utilize theory of rationals in order to learn summation, discounted summation, product, and classification quantitative automata.
  arXiv  Detail & Related papers  (2024-11-15T21:51:14Z)
• Deciding Differential Privacy of Online Algorithms with Multiple Variables [0.41248472494152805]
  This paper generalizes an automaton model called DiP automata to describe such algorithms. Our PSPACE algorithm also computes a value for $mathfrakD$ when the given automaton is differentially private.
  arXiv  Detail & Related papers  (2023-09-12T22:03:01Z)
• Automata Learning from Preference and Equivalence Queries [17.33092604696224]
  We propose a novel variant of the active automata learning problem: actively learn finite automata using preference queries.<n>ReMAP is guaranteed to correctly infer the minimal complexity with query complexity under exact equivalence queries.<n>Our empirical evaluations indicate REMAP scales to large automata is effective at learning correct automata from consistent teachers.
  arXiv  Detail & Related papers  (2023-08-18T04:49:45Z)
• Unified Functional Hashing in Automatic Machine Learning [58.77232199682271]
  We show that large efficiency gains can be obtained by employing a fast unified functional hash. Our hash is "functional" in that it identifies equivalent candidates even if they were represented or coded differently. We show dramatic improvements on multiple AutoML domains, including neural architecture search and algorithm discovery.
  arXiv  Detail & Related papers  (2023-02-10T18:50:37Z)
• Automatically Bounding the Taylor Remainder Series: Tighter Bounds and New Applications [10.824474741383723]
  We present a new algorithm for automatically bounding the Taylor remainder series. Our algorithm can make efficient use of machine learning hardware, and we provide an open source implementation in JAX. In a companion paper we use our new machinery to create the first universal majorization-minimization optimization algorithms.
  arXiv  Detail & Related papers  (2022-12-22T00:43:06Z)
• Faster Privacy Accounting via Evolving Discretization [54.32252900997422]
  We introduce a new algorithm for numerical composition of privacy random variables. Our algorithm achieves a running time and memory usage of $mathrmpolylog(k)$ for the task of self-composing a mechanism.
  arXiv  Detail & Related papers  (2022-07-10T04:25:37Z)
• Linear-Time Gromov Wasserstein Distances using Low Rank Couplings and Costs [45.87981728307819]
  The ability to compare and align related datasets living in heterogeneous spaces plays an increasingly important role in machine learning. The Gromov-Wasserstein (GW) formalism can help tackle this problem.
  arXiv  Detail & Related papers  (2021-06-02T12:50:56Z)
• Induction and Exploitation of Subgoal Automata for Reinforcement Learning [75.55324974788475]
  We present ISA, an approach for learning and exploiting subgoals in episodic reinforcement learning (RL) tasks. ISA interleaves reinforcement learning with the induction of a subgoal automaton, an automaton whose edges are labeled by the task's subgoals. A subgoal automaton also consists of two special states: a state indicating the successful completion of the task, and a state indicating that the task has finished without succeeding.
  arXiv  Detail & Related papers  (2020-09-08T16:42:55Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.