Average Reward Reinforcement Learning for Omega-Regular and Mean-Payoff Objectives

• URL: http://arxiv.org/abs/2505.15693v1
• Date: Wed, 21 May 2025 16:06:51 GMT
• Title: Average Reward Reinforcement Learning for Omega-Regular and Mean-Payoff Objectives
• Authors: Milad Kazemi, Mateo Perez, Fabio Somenzi, Sadegh Soudjani, Ashutosh Trivedi, Alvaro Velasquez,
• Abstract summary: We present the first model-free reinforcement learning framework that translates absolute liveness specifications to average-reward objectives.<n>We also introduce a reward structure for lexicographic multi-objective optimization.<n> Empirical results show our average-reward approach in continuing setting outperforms discount-based methods across benchmarks.
• Score: 9.657038158333139
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Recent advances in reinforcement learning (RL) have renewed focus on the design of reward functions that shape agent behavior. Manually designing reward functions is tedious and error-prone. A principled alternative is to specify behaviors in a formal language that can be automatically translated into rewards. Omega-regular languages are a natural choice for this purpose, given their established role in formal verification and synthesis. However, existing methods using omega-regular specifications typically rely on discounted reward RL in episodic settings, with periodic resets. This setup misaligns with the semantics of omega-regular specifications, which describe properties over infinite behavior traces. In such cases, the average reward criterion and the continuing setting -- where the agent interacts with the environment over a single, uninterrupted lifetime -- are more appropriate. To address the challenges of infinite-horizon, continuing tasks, we focus on absolute liveness specifications -- a subclass of omega-regular languages that cannot be violated by any finite behavior prefix, making them well-suited to the continuing setting. We present the first model-free RL framework that translates absolute liveness specifications to average-reward objectives. Our approach enables learning in communicating MDPs without episodic resetting. We also introduce a reward structure for lexicographic multi-objective optimization, aiming to maximize an external average-reward objective among the policies that also maximize the satisfaction probability of a given omega-regular specification. Our method guarantees convergence in unknown communicating MDPs and supports on-the-fly reductions that do not require full knowledge of the environment, thus enabling model-free RL. Empirical results show our average-reward approach in continuing setting outperforms discount-based methods across benchmarks.

Related papers

• Recursive Reward Aggregation [51.552609126905885]
  We propose an alternative approach for flexible behavior alignment that eliminates the need to modify the reward function.<n>By introducing an algebraic perspective on Markov decision processes (MDPs), we show that the Bellman equations naturally emerge from the generation and aggregation of rewards.<n>Our approach applies to both deterministic and deterministic settings and seamlessly integrates with value-based and actor-critic algorithms.
  arXiv  Detail & Related papers  (2025-07-11T12:37:20Z)
• RewardAnything: Generalizable Principle-Following Reward Models [82.16312590749052]
  Reward models are typically trained on fixed preference datasets.<n>This prevents adaptation to diverse real-world needs-from conciseness in one task to detailed explanations in another.<n>We introduce generalizable, principle-following reward models.<n>We present RewardAnything, a novel RM designed and trained to explicitly follow natural language principles.
  arXiv  Detail & Related papers  (2025-06-04T07:30:16Z)
• Adaptive Reward Design for Reinforcement Learning [2.3031174164121127]
  We propose a suite of reward functions that incentivize an RL agent to complete a task specified by a formula as much as possible.<n>We develop an adaptive reward shaping approach that dynamically updates reward functions during the learning process.
  arXiv  Detail & Related papers  (2024-12-14T18:04:18Z)
• Foundation Policies with Hilbert Representations [54.44869979017766]
  We propose an unsupervised framework to pre-train generalist policies from unlabeled offline data. Our key insight is to learn a structured representation that preserves the temporal structure of the underlying environment. Our experiments show that our unsupervised policies can solve goal-conditioned and general RL tasks in a zero-shot fashion.
  arXiv  Detail & Related papers  (2024-02-23T19:09:10Z)
• Entropy-Regularized Token-Level Policy Optimization for Language Agent Reinforcement [67.1393112206885]
  Large Language Models (LLMs) have shown promise as intelligent agents in interactive decision-making tasks. We introduce Entropy-Regularized Token-level Policy Optimization (ETPO), an entropy-augmented RL method tailored for optimizing LLMs at the token level. We assess the effectiveness of ETPO within a simulated environment that models data science code generation as a series of multi-step interactive tasks.
  arXiv  Detail & Related papers  (2024-02-09T07:45:26Z)
• DeAL: Decoding-time Alignment for Large Language Models [59.63643988872571]
  Large Language Models (LLMs) are nowadays expected to generate content aligned with human preferences. We propose DeAL, a framework that allows the user to customize reward functions and enables Detime Alignment of LLMs. Our experiments show that we can DeAL with fine-grained trade-offs, improve adherence to alignment objectives, and address residual gaps in LLMs.
  arXiv  Detail & Related papers  (2024-02-05T06:12:29Z)
• Reinforcement Learning for Omega-Regular Specifications on Continuous-Time MDP [1.8262547855491456]
  Continuous-time Markov decision processes (CTMDPs) are canonical models to express sequential decision-making under dense-time environments. We present an approach enabling correct translation to scalar reward signals for CTMDPs.
  arXiv  Detail & Related papers  (2023-03-16T17:45:38Z)
• Model-Free Reinforcement Learning for Symbolic Automata-encoded Objectives [0.0]
  Reinforcement learning (RL) is a popular approach for robotic path planning in uncertain environments. Poorly designed rewards can lead to policies that do get maximal rewards but fail to satisfy desired task objectives or are unsafe. We propose using formal specifications in the form of symbolic automata.
  arXiv  Detail & Related papers  (2022-02-04T21:54:36Z)
• Modular Deep Reinforcement Learning for Continuous Motion Planning with Temporal Logic [59.94347858883343]
  This paper investigates the motion planning of autonomous dynamical systems modeled by Markov decision processes (MDP) The novelty is to design an embedded product MDP (EP-MDP) between the LDGBA and the MDP. The proposed LDGBA-based reward shaping and discounting schemes for the model-free reinforcement learning (RL) only depend on the EP-MDP states.
  arXiv  Detail & Related papers  (2021-02-24T01:11:25Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.