ARMS: Automatic Reward Shaping for Sparse-Reward Multi-Agent Reinforcement Learning

Elie Abboud [email protected], Oren Gal [email protected] · 2026

Read ARMS: Automatic Reward Shaping for Sparse-Reward Multi-Agent Reinforcement Learning by Elie Abboud [email protected], Oren Gal [email protected] (2026) 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-2605-23562.txt.

Introduction

Abboud and Gal tackle sparse rewards in multi-agent reinforcement learning, where simultaneous learning makes the environment shift under each agent and reward design delicate. Their ARMS framework learns dense shaping signals from sparse rewards through trajectory ranking, reformulating policy invariance via conditional best-response reasoning. When its conditions hold, shaping preserves each agent's best-response set under fixed opponents, and thus the Nash equilibria. Tests in a partially observable pathfinding domain show better sampling efficiency, unseen-environment transfer, and a failure mode that extra exploration calms.

Catalog record

CREATORElie Abboud [email protected], Oren Gal [email protected]
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE56574
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.23562

Browse the full library · About the Tower of Babel

Full text

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

ARMS: Automatic Reward Shaping for Sparse-Reward Multi-Agent Reinforcement Learning Elie Abboud [email protected], Oren Gal [email protected] Abstract Sparse rewards are a major bottleneck in multi-agent reinforcement learning (MARL), where simultaneous learning induces non-stationarity and makes reward design especially delicate. Reward shaping can accelerate learning, but in the multi-agent setting it must preserve the strategic structure of the problem rather than merely improve short-term optimization. We propose A utomatic R eward-shaping in M ulti-agent S ystems ( ARMS ), a self-supervised reward shaping framework for MARL that learns dense shaping signals from sparse environmental rewards through trajectory ranking. Since single-agent trajectory-ranking guarantees do not directly transfer to MARL, we reformulate policy invariance through conditional best-response reasoning, and show that if certain conditions hold, then using shaping rewards preserves each agent’s best-response set under fixed opponent policies, and consequently preserve the set of Nash equilibria. Guided by this perspective, ARMS alternates between policy learning and reward learning while sharing shaping parameters across agents for effciency. Experiments in a partially observable multi-agent pathfinding domain show that ARMS improves sampling efficiency under increasing reward sparsity and agent count, generalizes to unseen environments, and reveals a MARL-specific failure mode in which limited exploration and coupled policy–reward dynamics induce oscillatory behavior. Increasing exploration mitigates this effect and stabilizes learning. To the best of our knowledge, ARMS is the first automatic reward shaping framework for MARL whose design is motivated by a game-theoretic equilibrium-preservation result. † † The authors used LLMs as an assistive tool for language editing, LateX troubleshooting and code generation. The authors carefully reviewed and tested the output. 1 Introduction Multi-Agent Reinforcement Learning (MARL) has seen substantial progress, which is evident from the increasing number of papers and surveys in the field in recent years ( 21 ; 17 ; 14 ; 5 ; 23 ; 26 ; 15 ) . A central challenge in this setting is learning effectively from sparse rewards. Sparse rewards are significantly more problematic in MARL due to non-stationarity and co-adaptation between agents, an element not present in single agent reinforcement learning (SARL). A common way to address sparse rewards is reward shaping , namely augmenting the training signal with additional rewards that guide learning toward desirable behavior, or replacing the reward completely. Existing reward shaping methods are typically developed for single-agent settings, and extending them to MARL is non-trivial because the shaping signal must remain meaningful under coupled learning dynamics without altering the underlying strategic structure of the problem. In particular, reward shaping is risky because it may alter the set of optimal policies in SARL, or, in the multi-agent setting, the set of Nash equilibria ( 12 ) . For this reason, reward shaping methods that preserve Nash equilibria are especially attractive. In reinforcement learning (RL), sparse reward functions are often easier to specify than dense ones, but they provide weak supervision and can substantially slow learning. Reward shaping aims to transform this sparse feedback into a denser training signal without changing the underlying solution of the problem. In MARL, this is especially delicate because multiple agents learn and act simultaneously in a shared environment, continually adapting their policies to one another as learning progresses. This gives rise to the inherent MARL challenge of non-stationarity ( 2 , Section 5.4.1) , under which the environment appears non-stationary from the perspective of each individual agent. Moreover, unlike SARL where the relevant solution is an optimal policy, in MARL the relevant solution is defined through mutual best responses and Nash equilibria: no agent can increase its expected return 1 1 1 The return is the cumulative reward obtained in a reinforcement learning problem. by unilaterally altering its policy. Designing such an informative dense reward is challenging even in single-agent settings ( 1 ; 22 ) . In multi-agent environments, this challenge becomes even harder, since the reward should encourage coordinated behavior between agents while preserving the set of Nash equilibria of the underlying problem ( 15 ) . This is precisely why reward shaping is both appealing and riskier in MARL: it has the potential to accelerate learning, but should not induce a shaping signal which changes the agents’ objectives across all agents . Traditionally, reward shaping refers to the hand-design of an additional reward signal by an expert, using domain knowledge or intuition to guide learning toward optimal policies. See 13 and 10 for more information. However, a more recent framework, called Self-Supervised Online Reward Shaping (SORS) ( 11 ) , which removes the need for hand-designing reward was developed for SARL. The main idea is to use a parameterized method to infer a dense reward function by ranking trajectories based on the environment’s sparse reward. Roughly speaking, the paper proposes a framework for training a parameterized reward function and shows theoretically that any two reward functions which similarly rank every pair of trajectories also induce the same set of optimal policies - which is the main motivation for inferring a reward function based on trajectory ranking. In this paper, we propose A utomatic R eward-shaping in M ulti-agent S ystems ( ARMS ), a framework for automatic reward shaping in MARL (Algorithm 1 , Section 5 ). ARMS is built around a multi-agent view of trajectory-based reward learning, in which policy invariance is formulated through conditional best-response reasoning rather than global optimality (Section 4 ). The framework alternates between reinforcement learning and reward-learning steps, using sparse environmental rewards to supervise trajectory ranking. We further examine how multi-agent non-stationarity affects reward learning and training stability (Section 6.4 and Section 6.3 ). To the best of our knowledge, ARMS is the first automatic reward shaping framework for MARL whose design is motivated by a game-theoretic equilibrium-preservation result. While trajectory-ranking approaches are effective in single-agent reinforcement learning, they do not directly extend to multi-agent settings due to three fundamental challenges. First, in MARL, trajectory quality depends on the joint policy of all agents, making it impossible to evaluate or rank trajectories independently of other agents’ behaviors. Second, the learning process is inherently non-stationary, as agents simultaneously update their policies, causing the distribution of trajectories (and their induced rankings) to shift over time. Third, unlike the single-agent case, MARL lacks a global notion of optimality: there is no universally optimal policy or trajectory ordering, but rather a set of interdependent best-response solutions. As a result, the theoretical guarantees underlying SORS, which rely on consistent global trajectory rankings, no longer hold in this setting. These challenges necessitate a fundamentally different formulation of policy invariance for trajectory-based reward shaping in MARL. Our contributions are threefold: 1. A multi-agent formulation of policy invariance for trajectory-based reward shaping. The standard trajectory-ranking guarantees from the single-agent setting do not directly apply in MARL due to joint policy dependence and the absence of a global optimality notion. To address this, we reformulate policy invariance through conditional best-response reasoning, proving that total-order-equivalent shaping rewards preserve each agent’s best-response set under fixed opponent policies, and consequently preserve the set of Nash equilibria. Section 4 presents this result. 2. ARMS: a self-supervised reward shaping framework for MARL. We propose ARMS, an online reward learning method for MARL that leverages trajectory ranking while accounting for the non-stationary and coupled nature of multi-agent

Read the complete text