One-sentence Summary

Researchers from UC San Diego show that episodic exploration bonuses and neural memory architectures interact in three distinct patterns governed by reward structure rather than density, formalizing sparsity with observation-anchored reward machines to separate structural sparsity from potential sparsity and demonstrating that exploration and memory are complements, not substitutes.

Key Contributions

• An identical episodic exploration bonus produces three distinct interaction patterns with neural memory architectures (amplifying capacity differences, equalizing performance, or yielding no effect) depending on how the environment’s reward structure supervises memory content acquisition.
• Observation-anchored reward machines formalize reward sparsity into structural sparsity (whether the reward directly supervises the required latent memory) and potential sparsity (whether local exploratory actions are mispriced), organizing task regimes by their retention burden rather than by temporal signal density.
• Controlled reward manipulations show that a dense reward neutralizes an exploration bonus only when it directly supervises the necessary latent representation, and that a small avoidable penalty on exploratory actions causes convergence to suboptimal policies, which exploration bonuses resolve by inducing state coverage that memory architectures convert into return.

Introduction

The authors investigate how episodic exploration bonuses interact with neural memory architectures in reinforcement learning, a critical concern for tasks requiring agents to retain information over time. Prior work often treats exploration and memory as separate design choices, leaving unclear how an environment’s reward structure mediates their combined effect on performance. The central contribution is a framework showing that the same exploration signal can amplify, neutralize, or have no effect on architectural capacity differences depending on what the reward inherently supervises. The authors introduce observation-anchored reward machines to characterize this dependency, distinguishing structural sparsity, which governs whether retention is supervised, from potential sparsity, which determines whether an exploratory deficit exists.

Experiment

The evaluation compares six memory architectures and two episodic bonuses across three environments under a single training stack, revealing that the same bonus can amplify, equalize, or have no effect depending on the environment’s memory demands. These divergent outcomes are traced to two sparsity properties: structural sparsity governs whether retention is reward-supervised, while potential sparsity determines whether the agent must actively discover what to remember. Controlled reward manipulations confirm that reward structure rather than density drives bonus efficacy, and penalty variants show that bonuses recover exploration by breaking stagnation rather than outbidding costs.

Success rates on MysteryPath-Grid show that reward structure, not density, governs exploration bonus effectiveness. Architectures with stronger sequence-modeling capacity benefit more from bonuses under sparse rewards, while aligned rewards make bonuses redundant or harmful and penalty rewards cause stagnation that bonuses break rather than outbid. GatedDeltaNet and RetNet achieve the highest success rates with exploration bonuses under sparse reward, substantially outperforming GRU, LSTM, and Mamba-2. Under the penalty reward, all recurrent architectures collapse to near-zero success without a bonus, but E3B and NovelD restore performance, indicating bonuses resolve stagnation rather than simply outweighing the penalty. The aligned reward produces the highest bonus-free success rates across most architectures, and adding a bonus often reduces performance, consistent with the bonus becoming redundant or detrimental. The distractor reward yields near-zero success regardless of architecture or bonus, confirming that an uninformative dense reward cannot substitute for memory-grounded exploration. Memoryless agents fail across all reward conditions, with success rates at or near zero, underscoring that sequence modeling capacity is necessary for any recovery by exploration bonuses.

Exploration bonuses substantially improve success rates over baseline, with the effect depending on both memory architecture and field-of-view conditions. Under restricted views and sparse or penalty rewards, bonuses enable near-perfect performance for several recurrent models, while the memoryless baseline remains at chance. Distractor and penalty manipulations confirm that bonuses primarily break exploratory stagnation rather than simply outbidding negative reward signals. Without a bonus, all architectures except Mamba-2 and GatedDeltaNet remain near chance under the restricted 3×3 sparse condition. E3B and NovelD bonuses lift GRU, LSTM, and GatedDeltaNet to near-ceiling success rates across most 3×3 reward variants. The memoryless architecture fails to exceed 50% success in any configuration, regardless of bonus or field of view. Under the 7×7 sparse setting, GatedDeltaNet achieves 94% success without a bonus, far surpassing other architectures in the same condition. Penalty and distractor rewards preserve the restorative effect of bonuses, indicating that bonuses resolve stagnation rather than simply compensating for negative rewards.

Memory-augmented architectures GRU and LSTM reliably achieve high exact-recall success regardless of bonus or reward density, while GatedDeltaNet shows moderate but noisy recovery that improves with bonuses. In contrast, RetNet, Mamba-2, and memoryless variants completely fail across all conditions, and neither exploration bonus nor dense reward alters the ranking among architectures. GRU and LSTM reach tail-mean success rates around 0.90–0.93 under all bonus and reward-density combinations, with LSTM slightly ahead in the sparse setting. GatedDeltaNet attains a modest 0.31–0.40 success rate, and bonuses provide a small lift in both sparse and dense rewards, though high variance persists. RetNet, Mamba-2, and the memoryless architecture yield near-zero success in every condition, showing no benefit from exploration bonuses or dense rewards.

This evaluation examines how exploration bonuses interact with reward structure and memory architecture across three tasks. On MysteryPath-Grid, bonuses are most effective under sparse rewards for architectures with strong sequence modeling, but become redundant or harmful under aligned rewards, while penalty rewards cause stagnation that bonuses resolve. Under restricted views, bonuses restore near-perfect performance for several recurrent models in sparse and penalty conditions, whereas memoryless agents fail universally. In exact-recall, GRU and LSTM succeed reliably regardless of bonus or reward density, while other architectures fail completely, and neither bonuses nor dense rewards alter the ranking among models.