EVAL: EigenVector-based Average-reward Learning

Jacob Adamczyk, Volodymyr Makarenko, Stas Tiomkin, Rahul V. Kulkarni · 2025

Read EVAL: EigenVector-based Average-reward Learning by Jacob Adamczyk, Volodymyr Makarenko, Stas Tiomkin, Rahul V. Kulkarni (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-2501-09770.txt.

Introduction

Jacob Adamczyk, Volodymyr Makarenko, Stas Tiomkin, and Rahul Kulkarni extend a fresh way to train agents on long-run average reward in a 2025 paper. Most training chases rewards that fade with time, or a plain average with no frills. A spiced form that adds a spread bonus can make agents bolder and tougher, and recent math solved it in a neat linear way for small cases.

Their work carries that frame to big cases with neural nets in place of tables. The shift also shows new links between the unlike reward aims. Paired with a step-wise plan updater, the method solves the plain average form too. On classic control tests it held steadier and settled faster than rivals.

Catalog record

CREATORJacob Adamczyk, Volodymyr Makarenko, Stas Tiomkin, Rahul V. Kulkarni
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE53 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-09770

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

EVAL: EigenVector-based Average-reward Learning Jacob Adamczyk, Volodymyr Makarenko, Stas Tiomkin, Rahul V. Kulkarni Abstract In reinforcement learning, two objective functions have been developed extensively in the literature: discounted and averaged rewards. The generalization to an entropy-regularized setting has led to improved robustness and exploration for both of these objectives. Recently, the entropy-regularized average-reward problem was addressed using tools from large deviation theory in the tabular setting. This method has the advantage of linearity, providing access to both the optimal policy and average reward-rate through properties of a single matrix. In this paper, we extend that framework to more general settings by developing approaches based on function approximation by neural networks. This formulation reveals new theoretical insights into the relationship between different objectives used in RL. Additionally, we combine our algorithm with a posterior policy iteration scheme, showing how our approach can also solve the average-reward RL problem without entropy-regularization. Using classic control benchmarks, we experimentally find that our method compares favorably with other algorithms in terms of stability and rate of convergence. Introduction To solve the central problem of reinforcement learning, an agent continuously and autonomously interacts with its surroundings to maximize a long-term reward signal. The standard method of solving reinforcement learning (RL) tasks involves a discounted objective function: the agent seeks to maximize an infinite discounted sum of rewards, as expected under a chosen control policy. This geometrically discounted sum ensures a convergent objective function, making it a convenient representation of the problem to be solved. The discounted RL literature is vast in both theoretical ( Sutton and Barto 2018 ; Kakade 2003 ; Bertsekas 2012 ) and algorithmic ( Schulman et al. 2016 ; Andrychowicz et al. 2021 ) studies and has demonstrated great success in real-world problems of interest ( Mnih et al. 2015 ; Schulman et al. 2015 ; Schulman et al. 2017 ; Hessel et al. 2018 ; Haarnoja et al. 2018b ) . However, in many RL problems, this use of discounting is simply a useful proxy for the solving the true objective function: maximization of total episode reward. As a result, the actual choice of the discount factor, \gamma , is unphysical, not grounded in any corresponding physical timescale. As such, it is treated as a hyperparameter which is often tuned over for best performance (or set to some fixed value, e.g. \gamma=0.99 , for simplicity). There is a precedent in past work for rejecting the discounted framework ( Naik et al. 2019 ) , for example the Heaven and Hell MDP ( Schwartz 1993 ) , suggesting that in many tasks the use of discounting is not only unphysical, but can lead to disastrous outcomes. Thus in long-term (“continuing”) decision-making settings, another objective is needed. An alternative approach to ensuring convergence of rewards across infinitely-long trajectories is to instead use the average-reward objective function ( Mahadevan 1996 ) . Despite offering a principled alternative to the long-term optimization problem, the average reward framework has not been historically popular in the RL literature, perhaps due to the lack of successful algorithms in this setting. However, recent work has developed new algorithms and theory ( Zhang and Ross 2021 ; Ma et al. 2021 ; Saxena et al. 2023b ; Arriojas et al. 2023b ; Wan, Naik, and Sutton 2021 ; Naik et al. 2024 ) specifically for the average-reward objective. This prior work has focused on the tabular setting or on using policy-gradient techniques to develop new algorithms. Although these methods have proven useful in their respective domains, there remain gaps in the field that can be addressed with new approaches. One such gap in the field of average-reward algorithms is the lack of entropy-regularized objectives, which have become a cornerstone of state-of-the-art algorithms in discounted RL ( Haarnoja et al. 2017a ; Haarnoja et al. 2018b ; Schulman et al. 2017 ; Schulman et al. 2015 ) . Formally, entropy-regularization involves including an “information” cost for deviating from a pre-specified (e.g. prior, guide, or behavioral) policy. This entropy cost is weighted with an inverse temperature parameter, \beta . This entropy-based regularization, in combination with treating the rewards as negative energies, reveals a close connection to statistical mechanics ( Arriojas et al. 2023b ; Rose, Mair, and Garrahan 2021 ) . Furthermore, including an entropy regularization term in the RL objective leads to more robust solutions (non-greedy optimal policies) and has theoretically been shown to be more adaptable to changes in reward and transition dynamics ( Eysenbach and Levine 2022 ) . Preventing the optimal policy from collapsing to a deterministic function can ensure additional exploration occurs during training and deployment, often leading to faster learning ( Ahmed et al. 2019 ) . Figure 1: Performance of discounted soft Q-Learning (SQL) as a function of discount factor compared with solution using the proposed average-reward method (EVAL). Note that the average-reward solution (blue line) recovers the discounted solution as \gamma~\to~1 . For the discounted objective, computational cost grows as (1~-~\gamma)~^{-1} and choosing a low discount factor to reduce computational cost can result in lower rewards. The boundary of low reward, low complexity and high reward, high complexity is demarcated by the discount factor derived from the spectral gap of the associated tilted matrix (cf. “Preliminaries”). Insets: state-occupation distributions following the SQL optimal policies at \gamma=0.87,0.93 . Green dot denotes initial position of agent, and star denotes the goal. The agent can move in any of the cardinal directions. Since we use entropy-regularization, the optimal policy is stochastic, thus yielding a variance in the return (plotted with a shaded interval for each method). Inverse temperature \beta=15 . In this paper, we introduce a novel algorithm for average-reward RL with entropy regularization: EigenVector-based Average-reward Learning (EVAL). Figure 1 illustrates a simple experiment highlighting one benefit of the EVAL approach to entropy-regularized RL compared to the discounted approach ( Haarnoja et al. 2017b ) . When the RL problem is posed in the discounted framework, a discount factor \gamma is a required input parameter. However, there is often no principled approach for choosing the value of \gamma corresponding to the specific problem being addressed. Thus, the experimenter must treat \gamma as a hyperparameter. This reduces the choice of \gamma to a trade-off between large values to capture long-term rewards and small values to capture computational efficiency which typically scales polynomially with the horizon, (1-\gamma)^{-1} ( Kakade 2003 ) . The horizon introduces a natural timescale to the problem, but this timescale may not be well-aligned with the timescale corresponding to the optimal dynamics: the mixing time of the induced Markov chain. For the discounted approach to accurately estimate the optimal policy, the discounting timescale (horizon) must be larger than the mixing time. However, estimating the mixing time for the optimal dynamics can be challenging in the general case, even when the transition dynamics are known. Therefore, an arbitrary “sufficiently large” choice of \gamma is often made without knowledge of the relevant problem-dependent timescale. This can be problematic from a computational standpoint as evidenced by recent work ( Jiang et al. 2015 ; Schulman et al. 2017 ; Andrychowicz et al. 2021 ) . The approach outlined in this work for average-reward RL (EVAL) has the added

Read the complete text