A Computationally Efficient Algorithm for Infinite-Horizon Average-Reward Linear MDPs

Kihyuk Hong, Ambuj Tewari · 2025

Read A Computationally Efficient Algorithm for Infinite-Horizon Average-Reward Linear MDPs by Kihyuk Hong, Ambuj Tewari (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-11997.txt.

Description

Kihyuk Hong and Ambuj Tewari present a 2025 algorithm for reinforcement learning where the goal is steady average reward over an endless run. In linear Markov decision processes, a prior method improved statistics by clipping the value function, but that step needed the lowest value across the whole state space, which can be endless. Their version clips only over states the algorithm has actually visited.

The change keeps the same regret promise as the earlier work while cutting the computing cost loose from the size of the state space. The authors frame the result as the first method for this setting that is both statistically and computationally sound at scale. Very large state spaces no longer block the approach.

Catalog record

CREATORKihyuk Hong, Ambuj Tewari
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE43 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-11997

Browse the full library · About the Tower of Babel