将连续数据划分到离散区间是人工智能中的基础操作。本文提出 分类自动机（categorizer automaton），一种确定性自动机，能够读取无限序列的奖励并判断其折扣和落入哪一个预定义的区间（bin）。分类自动机是比较自动机（comparator automaton）的推广，后者只处理两区间的情况，已在定量合成中得到应用。本文的核心技术是构造一种状态数仅与区间数量线性相关的分类自动机，避免了通过比较自动机的笛卡尔积导致的指数级状态爆炸。随后，我们将分类自动机应用于马尔可夫决策过程（MDP），利用它可以合成在折扣和收益的期望效用上最优的策略，即使效用函数存在不连续点。对于分段常数效用函数，算法是精确的且运行时间为伪多项式。对于分段 Lipschitz 效用函数（即在有限个跳点之间斜率有界的函数），同样在伪多项式时间内得到 $\varepsilon$-最优策略。我们还证明，即使效用函数是分段常数的，合成问题已经是 PSPACE‑hard。
博主点评：分类自动机的线性状态构造显著降低了离散化折扣和的复杂度，为处理不连续效用函数提供了实用工具，理论与实践价值并重。