← Back to all news
arXiv AI By Nathalie Bertrand, Pranav Ghorpade, Senthil Rajasekaran, Sasha Rubin, Moshe Vardi

Categorizer Automata for Discounted-Sum Payoffs

Read the original on arXiv AI →

The paper introduces the categorizer automaton, a deterministic automaton that processes an infinite sequence of rewards and determines which of a finite set of bins contains the discounted sum. Unlike previous approaches that combine multiple comparator automata and yield exponential state spaces, the authors construct a categorizer automaton with a state space linear in the number of bins. They apply this construction to Markov decision processes, enabling synthesis of policies that maximize expected utility for discounted-sum payoffs, including cases with discontinuous or piecewise‑Lipschitz utility functions, achieving pseudo‑polynomial time algorithms and proving PSPACE‑hardness for the synthesis problem even with piecewise‑constant utilities.

Machine-generated by The Flow from the publisher's headline and feed description — not written or checked by a human. The full article lives at arXiv AI.

Related stories

arXiv Machine Learning
2d ago

Policy Iteration Is Not Strongly Polynomial for Deterministic Markov Decision Processes: The Price of Algorithmic Anarchy

The paper presents an exponential lower bound on the number of iterations required by Howard's policy iteration algorithm for deterministic discounted Markov decision processes with at most two actions per state, when the discount factor is part of the input. This result shows that Howard's method cannot be strongly polynomial in this setting and establishes an exponential gap compared to the simplex method with Dantzig's pivoting rule, which remains strongly polynomial. Even with rewards limited to logarithmic bit length, a stretched‑exponential lower bound is achieved, highlighting a fundamental difference between decentralized, simultaneous improvements and Dantzig's coordinated single‑action selection.

By Han Zhong, Yinyu Ye
reinforcement-learning
More like this →
arXiv Machine Learning
Jul 1

End-to-End Efficient RL for Linear Bellman Complete MDPs with Deterministic Transitions

arXiv:2603. 23461v2 Announce Type: replace Abstract: We study reinforcement learning (RL) with linear function approximation in Markov Decision Processes (MDPs) satisfying \emph{linear Bellman completeness} -- a fundamental setting where the Bellman backup of any linear value function remains linear.

By Zakaria Mhammedi, Alexander Rakhlin, Nneka Okolo
reinforcement-learning
More like this →
Hugging Face Trending Papers
Aug 18

Adaptive Policy Portfolios for Robust Markov Decision Processes

The paper investigates adaptive policy portfolios for Robust Markov Decision Processes (RMDPs), proposing finite sets of memoryless randomized policies generated offline and selected online. It introduces robust regret as a metric for portfolio quality, comparing each portfolio member’s performance to the optimal policy for each plausible environment. The authors provide complexity-theoretic results showing that certifying and synthesizing such portfolios is highly intractable, and they present an offline construction method that can be specialized at runtime.

reinforcement-learning
More like this →