Technical Summary: Reward Structure Shapes the Interaction Between Episodic Exploration and Neural Memory in Reinforcement Learning

Problem Statement

In partially observable reinforcement learning (POMDPs), agents face a dual bottleneck: they must explore to encounter rewarding states and retain that experience in memory to optimize their policies. While exploration bonuses (intrinsic rewards) and neural memory architectures (recurrent states) are traditionally evaluated in isolation, their interaction remains unmeasured. Furthermore, standard notions of "sparse reward" conflate temporal signal density with the structural nature of what the reward actually supervises. This paper addresses two open questions: (1) Does the efficacy of an episodic exploration bonus depend on the choice of memory architecture? and (2) What property of the task governs this dependence?

Methodology

The authors conduct a controlled study crossing episodic exploration bonuses with diverse neural memory architectures across three environments that vary in how memory content is acquired.

Experimental Design

• Architectures: Six models were evaluated: standard gated RNNs (GRU, LSTM), retention and linear-attention models (RetNet, GatedDeltaNet), a state-space model (Mamba-2), and a memoryless control.
• Exploration Bonuses: Two episodic bonuses were tested against a no-bonus control:
  • E3B: Pays the elliptical novelty of the current observation based on a regularized covariance of features trained by an inverse-dynamics model.
  • NovelD: Pays the positive difference in lifelong RND novelty across a transition, gated by an episodic first-visit indicator.
• Environments:
  1. MysteryPath-Grid: An invisible path must be actively discovered via probing. Off-path steps reset the agent but not the path; memory is required to retain the path across resets.
  2. MiniGrid-MemoryS13: A cue object near the start must be retained to solve a temporally distant binary T-junction. The restricted 3×3 view forces active seeking of the cue.
  3. TinyReproduce: A 10-symbol sequence is dictated on a fixed schedule and must be reproduced in reverse. No active exploration is possible; the task is purely a memory retention test.
• Reward Manipulations: To isolate reward structure from density, the authors introduced variants:
  • Aligned (MysteryPath only): Densely pays for memory-advancing forward progress.
  • Penalty: Introduces a small, avoidable cost for exploratory actions (e.g., off-path steps), leaving the theoretical optimum unchanged.
  • Distractor: Matches the density of the aligned reward but pays only for re-entering known tiles (uninformative).

Theoretical Framework

The paper formalizes reward sparsity using observation-anchored reward machines (RMs) to separate two properties often conflated by frequency-based metrics:

1. Structural Sparsity: An automaton can reproduce the expected return without retaining the task-required history (i.e., the reward does not supervise the necessary memory).
2. Potential Sparsity: The one-step reward misprices local exploratory actions (i.e., the greedy policy is suboptimal without lookahead).

Key Results

The study identifies three distinct interaction patterns between exploration bonuses and memory architectures, determined by the reward structure rather than temporal density:

1. The Amplification Pattern (MysteryPath-Grid)

• Context: The reward is structurally sparse. The agent must actively discover and retain a high-dimensional path, but the reward signal (upon success) does not directly supervise the intermediate memory steps required to find it.
• Result: The exploration bonus disproportionately amplifies the performance spread between architectures. High-capacity models (RetNet, GatedDeltaNet) show substantial gains (e.g., +0.40 to +0.46), while standard RNNs (GRU, LSTM) show negligible improvement. The memoryless control degrades.
• Mechanism: The bonus induces state coverage, but only architectures with sufficient representational capacity can convert that exposure into a retained policy.

2. The Equalization Pattern (MiniGrid-MemoryS13)

• Context: The reward is structurally dense but potentially sparse. The agent must discover a cue (exploration), but once found, the retention burden is a single reward-supervised bit.
• Result: The bonus equalizes architectures to a shared performance ceiling. Low-capacity models (GRU, LSTM, RetNet) that fail without a bonus (stuck at chance, 0.50) are lifted to high success rates (0.90+). Models that already succeed without a bonus (GatedDeltaNet, Mamba-2) show marginal or zero improvement.
• Mechanism: The bonus supplies the missing local advantage to seek the cue; since standard cells can easily retain a single bit once found, the bonus determines whether convergence occurs, not how well.

3. The Null Pattern (TinyReproduce)

• Context: The reward is structurally dense and potentially dense. The observation stream is purely scheduled, and the task requires carrying the full sequence.
• Result: The bonus yields a null effect. No architecture shows substantive within-cell improvement.
• Mechanism: The observation stream is action-independent; the optimal policy is already greedy. The bonus cannot reorder policies because the extrinsic reward already perfectly ranks them.

Causal Verification of Reward Structure

• Reward Density vs. Structure: A dense reward that directly supervises the required memory (Aligned variant) renders the exploration bonus redundant or even detrimental. Conversely, a density-matched but uninformative reward (Distractor) preserves the bonus's positive effect.
• Exploration Pricing: Introducing a small, avoidable penalty on exploratory actions causes all architectures to converge to suboptimal stationary states (policy freeze) with 0% success, despite the theoretical optimum being unchanged. Both E3B and NovelD resolve this stagnation, proving that the bonus breaks the freeze by encouraging exploration rather than simply outbidding the penalty.

Significance and Claims

The paper claims that exploration and memory are complements, not substitutes. An exploration bonus induces necessary state coverage, but only adequate representational capacity can convert that coverage into optimal expected return.

• Formalization: The authors provide a formal vocabulary (Structural vs. Potential Sparsity via Reward Machines) to organize these regimes based on the "retention burden" a task exposes, rather than just reward frequency.
• Practical Implication: Practitioners must evaluate what the reward inherently supervises. If the reward is structurally sparse, architectural capacity gates the gain from exploration. If the reward is structurally dense but potentially sparse, exploration bonuses can enable convergence for lower-capacity models. If the reward is both dense, bonuses offer no benefit.
• Limitations: The study is bounded to discrete-action domains, a single on-policy algorithm (PPO), and observation-based episodic bonuses. The formal results regarding encoding machines assume finite posteriors and may not scale to high-dimensional continuous inputs without further abstraction.

The authors conclude that the interaction between episodic exploration bonuses and neural memory is task-dependent, governed by the reward structure's supervision of the latent memory required for the task.