跳转至

文章背景与核心概要

将连续数据分类到离散的区间（bins）中是人工智能中的一项基础操作。本文引入了“分类自动机”（categorizer automata）这一概念，这是一种确定性自动机，旨在读取无限的奖励序列，并识别出其折扣和（discounted sum）落在有限个区间中的哪一个。这些自动机推广了比较器自动机（仅有两个区间的特殊情况），并提供了一种高度高效的状态空间表示，其大小关于区间数量呈线性增长，而非指数级增长。

通过将分类自动机应用于马尔可夫决策过程（MDP），本文作者实现了策略的综合（synthesis），能够最大化连续和不连续效用函数下折扣和收益的期望效用：对于分段常数效用（Piecewise-Constant Utilities），该方法产生了一个在伪多项式时间内运行的精确算法（尽管被证明是 PSPACE-hard 的）；对于分段 Lipschitz 效用（Piecewise-Lipschitz Utilities），它在伪多项式时间内产生成本在有界斜率和有限次跳跃约束下的 \(\varepsilon\)-最优策略。

Categorizer Automata for Discounted-Sum Payoffs

Executive Summary

Categorizing continuous data into discrete bins is a fundamental operation in artificial intelligence. This paper introduces categorizer automata—deterministic automata designed to read an infinite sequence of rewards and identify which of finitely many bins contains its discounted sum. These automata generalize comparator automata (the special case of two bins) and offer a highly efficient state space representation that is linear, rather than exponential, in the number of bins.

By applying categorizer automata to Markov decision processes (MDPs), the authors enable the synthesis of policies that maximize the expected utility of a discounted-sum payoff for both continuous and discontinuous utility functions: * Piecewise-Constant Utilities: Yields an exact algorithm running in pseudo-polynomial time (though shown to be PSPACE-hard). * Piecewise-Lipschitz Utilities: Yields an \(\varepsilon\)-optimal policy running in pseudo-polynomial time for utilities with bounded slope between finitely many jumps.

Paper Metadata

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.

Access & Resources