arXiv CS open access

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

2026 · arxiv_cs

arXiv CS · Papers · 2026

deep-learning machine-learning neural-networks

Conceptio Open Archive

Analyze & explore related research in Conceptio

Connect this record directly into your research workflow or AI agent. Explore citations across open repositories, query full text, and export structured proof bundles.

Explore in Search →Connect via MCP / API ↗

Reward Structure Shapes the Interaction Between Episodic Exploration and Neural Memory in Reinforcement Learning Jai Malegaonkar∗† , Rohan Patil∗† , Henrik I. Christensen Department of Computer Science and Engineering, UC San Diego, United States {jmalegaonkar, rpatil, hichristensen}@ucsd.edu

arXiv:2608.05111v1 [cs.LG] 5 Aug 2026

Abstract In partially observable reinforcement learning, agents face a dual bottleneck: they must explore to encounter rewarding states and retain that experience in memory to optimize their policies. Exploration bonuses and memory architectures are traditionally evaluated in isolation, leaving their interaction unmeasured, and standard notions of sparse reward conflate temporal signal density with what the reward actually supervises. We present a controlled study crossing episodic exploration bonuses with diverse neural memory architectures across three environments that vary how the content of memory is acquired. An identical bonus signal yields three distinct interaction patterns: it amplifies architectural capacity differences where memory content must be actively discovered and retained unsupervised; equalizes architectures to a shared ceiling where the content, once sought out, is a single rewardsupervised cue; and is null where the observation stream is purely scheduled. Controlled reward manipulations verify that these patterns track reward structure rather than density: a dense reward neutralizes a bonus only if it directly supervises the required latent memory, and a small avoidable penalty on exploratory actions (leaving the optimum unchanged) induces policy convergence to suboptimal stationary states, which either bonus resolves. We then formalize reward sparsity with observation-anchored reward machines, separating structural sparsity (an automaton reproduces the return without the taskrequired history) from potential sparsity (the one-step reward misprices local exploratory actions); the resulting vocabulary organizes the three regimes by the retention burden each task exposes. Together, these results show exploration and memory are complements, not substitutes: a bonus induces exposure, and only memory converts exposure into return.

Introduction An agent acting under partial observability cannot condition on the true state of the world. It must instead act on a summary of its interaction history (o0 , a0 , . . . , ot ) (Kaelbling, Littman, and Cassandra 1998), which deep reinforcement learning approximates with a recurrent hidden state. Two conditions are necessary for this representation to be useful, and each depends on the other: a policy cannot reliably reach rewarding states without an adequate memory representation, and the recurrent state cannot learn to retain critical ∗ †

These authors contributed equally. Corresponding author.

information without a reachable reward signal to provide gradients. Exploration and memory are nonetheless studied in isolation. Memory benchmarks isolate recurrent capacity by holding the training signal fixed (Morad et al. 2023; Pleines et al. 2025; Smirnov and Gu 2025), whereas exploration studies evaluate bonuses under a fixed architecture (Henaff et al. 2022; Zhang et al. 2021; Yuan et al. 2025). Two questions therefore remain open: does the effect of an episodic bonus depend on the choice of memory architecture, and what property of the task governs that dependence? Standard terminology provides limited insight into the second question, as the conventional notion of “sparse reward” measures signal frequency, conflating temporal density with what the reward actually supervises. We address both questions by crossing episodic bonuses with diverse memory architectures under controlled reward manipulations, and by formalizing reward sparsity in terms of what the reward supervises rather than how often it pays. We contribute the following: • A comprehensive evaluation of episodic bonuses across diverse memory architectures, yielding three distinct interaction patterns. Holding the training stack constant, an identical episodic bonus amplifies the performance spread between architectures where memory content must be actively discovered; equalizes architectures to a shared performance ceiling where critical information is initially observable but temporally distant; and yields a null effect where the observation stream is purely scheduled. • Causal verification that reward structure, not reward density, governs bonus efficacy. Holding the environment, architectures, and hyperparameters fixed, we vary solely the target of the reward signal. A dense reward that directly supervises the required memory renders an exploration bonus redundant and often detrimental, whereas a density-matched reward evaluating task-irrelevant transitions preserves its positive effect. A small, avoidable penalty on exploratory actions—which leaves the theoretical optimum unchanged—further drives every architecture into suboptimal stationary policies, which either bonus escapes independently of its magnitude relative to the penalty.

• A reward-machine formalization of reward sparsity. We equip POMDPs with observation-anchored reward machines (Toro Icarte et al. 2018) to separate two properties the frequency-based notion conflates: structural sparsity, where an automaton reproduces the expected return without retaining the task-required history, leaving the latent memory representation unsupervised; and potential sparsity, where the one-step reward misprices local exploratory actions. Classifying each task under a rewardpreserving abstraction separates the three empirical patterns by the retention burden each exposes. Adjacent work has examined parts of this space: intrinsic rewards underperforming with LSTMs (Yuan et al. 2025), exploration at fixed architecture (Kayal, Pignatelli, and Toni 2025), memory decoupled from credit assignment (Ni et al. 2023), and intrinsic motivation unified at the policy level (Lidayan, Dennis, and Russell 2025). However, none evaluates architecture, bonus, and reward structure simultaneously. Exploration and memory are complementary, not interchangeable: state coverage is ineffective without the representational capacity to retain it, and high-capacity memory requires sufficient coverage to provide a meaningful training signal. The paper proceeds as follows. We review the partially observable setting alongside foundational concepts of exploration bonuses, reward shaping, and reward machines. We then detail the experimental design across architectures, bonuses, environments, and reward variants. We present the three interaction patterns and demonstrate through controlled manipulations that they track reward structure rather than density.We subsequently formalize reward sparsity as an ordered diagnostic and conclude with a discussion of the results and the limitations of the proposed framework.

Background POMDPs and Memory in RL A finite partially observable Markov decision process (POMDP) is a tuple M = ⟨S, A, O, p, ω, r, γ, µ⟩: finite state, action, and observation sets, transition kernel p(s′ | s, a), observation distribution ω(o | s′ ), deterministic reward over traces r : (S × A)∗ × S → R, discount γ ∈ [0, 1), and initial distribution µ. An agent never observes st ; it receives ot ∼ ω(· | st ) and acts on the history ht = (o0 , a0 , . . . , ot ). An optimal policy is therefore a function of a sufficient statistic of ht (Kaelbling, Littman, and Cassandra 1998). Deep RL approximates this statistic with learned recurrent architectures, ranging from LSTMs and GRUs (Hausknecht and Stone 2015; Kapturowski et al. 2019) to state-space and linear-recurrent models (Gu and Dao 2023; Lu et al. 2023). We reserve memory for this recurrent state, distinct from episodic replay buffers (Badia et al. 2020). Prior benchmarks isolate memory capacity by holding the training signal fixed (Morad et al. 2023; Pleines et al. 2025; Smirnov and Gu 2025), leaving the effect of an episodic bonus on the performance gaps between architectures unmeasured.

Exploration Bonuses Intrinsic bonuses augment extrinsic rewards with a novelty signal. Global bonuses score a state against lifelong experi-

ence (Bellemare et al. 2016; Pathak et al. 2017; Burda et al. 2019); episodic bonuses pay within-trajectory novelty and reset every episode (Savinov et al. 2019), driving performance in procedurally generated environments (Henaff et al. 2022; Henaff, Jiang, and Raileanu 2023). We study two episodic bonuses alongside a no-bonus control. E3B pays the elliptical novelty of the current observation from the regularized covariance of features ϕ trained by an inverse-dynamics model: −1 be3b = ϕ(ot )⊤ Ct−1 ϕ(ot ), t X Ct = ϕ(oi ) ϕ(oi )⊤ + λI,

(1)

i≤t

with C reset at episode boundaries (Henaff et al. 2022). NovelD pays the positive difference in lifelong RND novelty w(·) across a transition, gated by an episodic first-visit indicator Nep (Zhang et al. 2021): bnvd = max w(ot+1 ) − α w(ot ), 0 · 1 Nep (ot+1 ) = 1 . t (2) In discrete navigation tasks, E3B’s bonus approximates an episodic position count. The two methods therefore differ primarily in their temporal credit assignment: E3B distributes a graded score at every step, whereas NovelD’s first-visit gate concentrates payment on a sparse subset of transitions. Both evaluate novelty over raw observations ot , whereas the governing quantity under partial observability is a statistic of history, which the recurrent state approximates. Consequently, the exploration bonus and the memory architecture are structurally coupled. Because episodic bonuses functionally modify the reward, the theory of policy invariance applies. Ng, Harada, and Russell (1999) established that a shaping term preserves optimal behavior exactly when it is potential-based: γΦ(s′ )−Φ(s) for some potential Φ over states. Wiewiora (2003) related such shaping to an equivalent initialization of the value function. Neither E3B nor NovelD is potential-based, thus lacking invariance guarantees; these bonuses may alter the optimal policy. Our aligned reward variant tests this dynamic directly, and potential functions provide the formal basis for our definition of potential sparsity.

Reward Machines A reward machine (RM) summarizes the reward-relevant history of a non-Markovian reward in a finite-state automaton over high-level propositions (Toro Icarte et al. 2018, 2022). An RM is a tuple R = ⟨U, u0 , δu , δr ⟩: a finite state set U , an initial state u0 ∈ U , a state-transition function δu : U × 2P → U over a finite proposition set P, and a reward-transition function δr : U × 2P → R.1 A Markov decision process with a reward machine (MDPRM) is M′ = ⟨S, A, p, γ, µ, P, L, RP SA ⟩, equipped with a labelling function L : S × A × S → 2P . Subscripts on R record the labelling domain: RP SA over propositions, states, 1

We write Ū := U ∪ F for the union of non-terminal and terminal states and use Ū where the distinction is immaterial; Toro Icarte et al. (2018) keep the two strictly separate.

Gradient T BP P T <latexit sha1_base64="Uv7uNXvq/RPUK/gzckSUL1qCzgI=">AAAB+XicdVDLSgMxFL1TX7W+Rl26CRbBVZnRWrssdaHLEfqCdiiZTKYNzTxIMoUy1C9x40IRt/6JO//G9CFU0QOBwzn33hyOl3AmlWV9Grm19Y3Nrfx2YWd3b//APDxqyTgVhDZJzGPR8bCknEW0qZjitJMIikOP07Y3upn57TEVksVRQ00S6oZ4ELGAEay01DfNW4F9RiOFHlCj7jiNvlm0S9YcyFohl+VK9Qp9W0VYwumbHz0/JmmobxCOpezaVqLcDAvFCKfTQi+VNMFkhAe0q2mEQyrdbJ58is604qMgFvrpDHN1dSPDoZST0NOTIVZD+dubiX953VQFVTdjUZIqGpHFR0HKkYrRrAbkM0GJ4hNNMBFMZ0VkiAUmSpdVWC3hf9K6KNmVUuW+XKzVl3Xk4QRO4RxsuIYa3IEDTSAwhkd4hhcjM56MV+NtMZozljvH8APG+xdu+5Ln</latexit>

→ <latexit sha1_base64="Hi4LtNeag2YZaCPF1qa8nxQFI2g=">AAAB7XicdVDLSgNBEOyNrxhfUY9eBoPgKexqjDkGvXiMYB6QLKF3MpuMmZ1dZmaFEPIPXjwo4tX/8ebfOHkIUbSgoajqprsrSATXxnU/nczK6tr6RnYzt7W9s7uX3z9o6DhVlNVpLGLVClAzwSWrG24EayWKYRQI1gyG11O/+cCU5rG8M6OE+RH2JQ85RWOlRkdiILCbL3hFdwbiLpHzUrlyQb6tAixQ6+Y/Or2YphGThgrUuu25ifHHqAyngk1ynVSzBOkQ+6xtqcSIaX88u3ZCTqzSI2GsbElDZuryxBgjrUdRYDsjNAP925uKf3nt1IQVf8xlkhom6XxRmApiYjJ9nfS4YtSIkSVIFbe3EjpAhdTYgHLLIfxPGmdFr1ws35YK1atFHFk4gmM4BQ8uoQo3UIM6ULiHR3iGFyd2npxX523emnEWM4fwA877F6kQjzY=</latexit>

Encoder ω CN N/M LP by obs <latexit sha1_base64="qYmu6qtRkpDk8fEOQn1cVKwcIEs=">AAACBnicbVDLSsNAFJ3UV62vqEsRQosgCDVxUV0Wi+BCSwX7gCaUyWTaDp3MhJmJEEq7ceMH+BNuXCji1m9w179x+lho64ELh3Pu5d57/IgSqWx7ZKSWlldW19LrmY3Nre0dc3evJnksEK4iTrlo+FBiShiuKqIobkQCw9CnuO73SmO//oCFJJzdqyTCXgg7jLQJgkpLLfPwiiEeYDF0I0lcN1Mql09vbypDPxlyX7bMnJ23J7AWiTMjuWLWPXkeFZNKy/x2A47iEDOFKJSy6diR8vpQKIIoHmTcWOIIoh7s4KamDIZYev3JGwPrSCuB1eZCF1PWRP090YehlEno684Qqq6c98bif14zVu0Lr09YFCvM0HRRO6aW4tY4EysgAiNFE00gEkTfaqEuFBApnVxGh+DMv7xIamd5p5Av3Dm54iWYIg0OQBYcAwecgyK4BhVQBQg8ghfwBt6NJ+PV+DA+p60pYzazD/7A+PoBrTGbng==</latexit>

ot <latexit sha1_base64="wLcdwgDteqyoSD/AeeMSdH1viWg=">AAAB63icbZC7SgNBFIbPxluMt6hgYzMYBKuwaxEtQ2wsEzAXSJYwO5lNhsxlmZkVwpJXsLFQxNbSt/AJ7Gx8FneTFJr4w8DH/5/DnHOCiDNjXffLya2tb2xu5bcLO7t7+wfFw6OWUbEmtEkUV7oTYEM5k7RpmeW0E2mKRcBpOxjfZHn7nmrDlLyzk4j6Ag8lCxnBNrNU3xb6xZJbdmdCq+AtoFQ9aXyz99pHvV/87A0UiQWVlnBsTNdzI+snWFtGOJ0WerGhESZjPKTdFCUW1PjJbNYpOk+dAQqVTp+0aOb+7kiwMGYigrRSYDsyy1lm/pd1Yxte+wmTUWypJPOPwpgjq1C2OBowTYnlkxQw0SydFZER1pjY9DzZEbzllVehdVn2KuVKwytVazBXHk7hDC7Agyuowi3UoQkERvAAT/DsCOfReXFe56U5Z9FzDH/kvP0Ae2KRlw==</latexit>

<latexit sha1_base64="yg5CXulhQASfGFYw19lbvmtHzso=">AAAB/3icdVDLSgMxFM34rONrVHDjJlgEV2VGa+2y6MaVVLAP6Awlk0nb0EwyJBmh1Bb8FTcuFHHrb7jzb0ynFarogcDhnHu4NydMGFXadT+thcWl5ZXV3Jq9vrG5te3s7NaVSCUmNSyYkM0QKcIoJzVNNSPNRBIUh4w0wv7lxG/cEamo4Ld6kJAgRl1OOxQjbaS2s38txpQnqfZ9m4txV6KIEq7bTt4ruBmgO0dOi6XyGfy28mCGatv58COB09hkMUNKtTw30cEQSU0xIyPbTxVJEO6jLmkZylFMVDDM7h/BI6NEsCOkeVzDTJ1PDFGs1CAOzWSMdE/99ibiX14r1Z1yMMz+RzieLuqkDGoBJ2XAiEqCNRsYgrCk5laIe0girE1l9nwJ/5P6ScErFUo3xXzlYlZHDhyAQ3AMPHAOKuAKVEENYHAPHsEzeLEerCfr1Xqbji5Ys8we+AHr/Quci5aD</latexit>

Recurrent Cell <latexit sha1_base64="C6ZyfFDxWBdPVHyCCkcWO7BAEQ0=">AAACCHicbVC7TsMwFHXKq4RXgJGBiAqJqUoQKowVXRgLog+piSLHuWmtOg/ZDlIVtRsLv8LCAEKsfAIbf4PbZoCWI1k6Pufea9/jp4wKaVnfWmlldW19o7ypb23v7O4Z+wdtkWScQIskLOFdHwtgNIaWpJJBN+WAI59Bxx82pn7nAbigSXwvRym4Ee7HNKQESyV5xvEdkIxziOWkAYw5jj6gAYgJUZfJwJOeUbGq1gzmMrELUkEFmp7x5QQJySI1kTAsRM+2UunmmEtKGIx1JxOQYjLEfegpGuMIhJvPFhmbp0oJzDDh6sTSnKm/O3IcCTGKfFUZYTkQi95U/M/rZTK8cnMap5mEmMwfCjNmysScpmIGlAORbKQIJpyqv5pkgDkmUmWnqxDsxZWXSfu8ateqtduLSv26iKOMjtAJOkM2ukR1dIOaqIUIekTP6BW9aU/ai/aufcxLS1rRc4j+QPv8AXtImko=</latexit>

<latexit sha1_base64="J7nvKawoyee4UYgI7jTIzwx76FI=">AAAB/XicbVDLTsMwENzwLOUVHjcuFhUSp5IgVDgWeuFYJPqQ2qhyXKe16jiR7SCVqOVXuHAAIa78Bzf+BjftAVpGWmk0s2vvjh9zprTjfFtLyyura+u5jfzm1vbOrr23X1dRIgmtkYhHsuljRTkTtKaZ5rQZS4pDn9OGP6hM/MYDlYpF4l4PY+qFuCdYwAjWRurYh9dER3Lcjhk6QxXJNCPjescuOEUnA1ok7owUYIZqx/5qdyOShFRowrFSLdeJtZdiaZ7jdJRvJ4rGmAxwj7YMFTikykuz7UfoxChdFETSlNAoU39PpDhUahj6pjPEuq/mvYn4n9dKdHDlpUzEiaaCTD8KEo50hCZRoC6TlGg+NAST7HRE+lhiok1geROCO3/yIqmfF91SsXR3USjfzOLIwREcwym4cAlluIUq1IDAIzzDK7xZT9aL9W59TFuXrNnMAfyB9fkDwTWUyw==</latexit>

Actor ω/Critic V

hides cell ht

Advantage At <latexit sha1_base64="NpFKWqVBe/7uhwXAlF7lUmJiOkA=">AAAB9HicbVBNT8JAEJ3iF+IX6tFLIzHxRFpj0CPoxSMm8pFAQ7bbBTZst3V3SkIa/BtePGiMV3+MN/+NC/Sg4EsmeXlvZnfm+bHgGh3n28qtrW9sbuW3Czu7e/sHxcOjpo4SRVmDRiJSbZ9oJrhkDeQoWDtWjIS+YC1/dDvzW2OmNI/kA05i5oVkIHmfU4JG8mrBmEgkA/ZU62GvWHLKzhz2KnEzUoIM9V7xqxtENAmZRCqI1h3XidFLiUJOBZsWuolmMaEj837HUElCpr10vvTUPjNKYPcjZUqiPVd/T6Qk1HoS+qYzJDjUy95M/M/rJNi/9lIu4wSZpIuP+omwMbJnCdgBV4yimBhCqOJmV5sOiSIUTU4FE4K7fPIqaV6U3Uq5cn9Zqt5kceThBE7hHFy4gircQR0aQOERnuEV3qyx9WK9Wx+L1pyVzRzDH1ifP83LkiQ=</latexit>

N o input

no gradient <latexit sha1_base64="ThTM/C7PPd2J6RxCIoP8IFbpHMo=">AAACD3icbVC7SgNBFJ31GeMrammzGBSrsCsSLUNsLBQimAdklzA7mU2GzM4sM3eFsGS/wMZfsbFQxNbWzr9x8ig08cDA4Zx7uHNPEHOmwXG+raXlldW19dxGfnNre2e3sLff0DJRhNaJ5FK1AqwpZ4LWgQGnrVhRHAWcNoPB1dhvPlClmRT3MIypH+GeYCEjGIzUKZxUpUh0RgWRXaoyL9bM8/Ihx5Dd3tQyabKZ7ECnUHRKzgT2InFnpIhmqHUKX15XkiSiAgjHWrddJwY/xQoY4XSU9xJNY0wGuEfbhgocUe2nk3tG9rFRunYolXkC7In6O5HiSOthFJjJCENfz3tj8T+vnUB46adMxAmYi6eLwoTbIO1xOXaXKUqADw3BRDHzV5v0scIETIV5U4I7f/IiaZyV3HKpfHderFRndeTQITpCp8hFF6iCrlEN1RFBj+gZvaI368l6sd6tj+nokjXLHKA/sD5/AGJFnYc=</latexit>

Bonus encoder ω

f lat M LP over ot

GAE <latexit sha1_base64="fR3eku0iZSkNyZUCEay1bu56TPo=">AAAB6nicbVDLSgNBEOyNrxhfUY9eBoPgKeyKRI9RET1GNA9IljA7mSRDZmeXmV4hLPkELx4U8eoXefNvnCR70GhBQ1HVTXdXEEth0HW/nNzS8srqWn69sLG5tb1T3N1rmCjRjNdZJCPdCqjhUiheR4GSt2LNaRhI3gxGV1O/+ci1EZF6wHHM/ZAOlOgLRtFK9zcX191iyS27M5C/xMtICTLUusXPTi9iScgVMkmNaXtujH5KNQom+aTQSQyPKRvRAW9bqmjIjZ/OTp2QI6v0SD/SthSSmfpzIqWhMeMwsJ0hxaFZ9Kbif147wf65nwoVJ8gVmy/qJ5JgRKZ/k57QnKEcW0KZFvZWwoZUU4Y2nYINwVt8+S9pnJS9Srlyd1qqXmZx5OEADuEYPDiDKtxCDerAYABP8AKvjnSenTfnfd6ac7KZffgF5+MbtUeNcA==</latexit>

bt <latexit sha1_base64="scFVwHnuzNATwtZ4ZgVnunTmAgA=">AAAB63icbVBNS8NAEJ3Ur1q/qh69LBbBU0lEqseiF48V7Ae0oWy2m3bp7ibsToQS+he8eFDEq3/Im//GpM1Bqw8GHu/NMDMviKWw6LpfTmltfWNzq7xd2dnd2z+oHh51bJQYxtsskpHpBdRyKTRvo0DJe7HhVAWSd4Ppbe53H7mxItIPOIu5r+hYi1AwirkUDLEyrNbcursA+Uu8gtSgQGtY/RyMIpYorpFJam3fc2P0U2pQMMnnlUFieUzZlI55P6OaKm79dHHrnJxlyoiEkclKI1moPydSqqydqSDrVBQndtXLxf+8foLhtZ8KHSfINVsuChNJMCL542QkDGcoZxmhzIjsVsIm1FCGWTx5CN7qy39J56LuNeqN+8ta86aIowwncArn4MEVNOEOWtAGBhN4ghd4dZTz7Lw578vWklPMHMMvOB/fiI+N7A==</latexit>

rt + ω bt <latexit sha1_base64="skUrfl81aPJ8m83x28q4JoBFOb8=">AAAB+XicbVDLSsNAFJ34rPUVdelmsAiCUBKR6rLoxmUF+4A2hMlk0g6dTMLMTaGE9kvcuFDErX/izr9x2mahrQcGDufcw71zglRwDY7zba2tb2xubZd2yrt7+weH9tFxSyeZoqxJE5GoTkA0E1yyJnAQrJMqRuJAsHYwvJ/57RFTmifyCcYp82LSlzzilICRfNtWPkwve8IkQjINfPDtilN15sCrxC1IBRVo+PZXL0xoFjMJVBCtu66TgpcTBZwKNin3Ms1SQoekz7qGShIz7eXzyyf43CghjhJlngQ8V38nchJrPY4DMxkTGOhlbyb+53UziG69nMs0AybpYlGUCQwJntWAQ64YBTE2hFDFza2YDogiFExZZVOCu/zlVdK6qrq1au3xulK/K+oooVN0hi6Qi25QHT2gBmoiikboGb2iNyu3Xqx362MxumYVmRP0B9bnD6xmk7Q=</latexit>

Figure 1: Architectural separation of bonus and memory in the forward pass. The bonus encoder ϕ processes only the instantaneous observation ot , bypassing the recurrent hidden state ht . Because the bonus augments the reward prior to advantage estimation, its gradient updates the recurrent cell without the memory conditioning on the exploration signal. and actions; RP OA over propositions, observations, and actions. The framework extends to POMDPs by anchoring labels to observations, with L : O × A × O → 2P advancing the machine along a trace. Writing xt for the RM state at step t (x0 = u0 , xt = δu (xt−1 , L(ot−1 , at−1 , ot ))), an RM is perfect for M w.r.t. L (Toro Icarte et al. 2019, 2023) iff Pr ot+1 , rt | o0 , a0 , . . . , ot , at = Pr ot+1 , rt | ot , xt , at . (3) Augmenting the observation with a perfect RM state renders the environment Markovian over O × U . This transformation strictly isolates tasks where the native reward supervises memory-advancing transitions from those where it does not.

Experimental Setup Common Design. Every experiment crosses six architectures (GRU, LSTM, RetNet, GatedDeltaNet, Mamba-2, Memoryless) with a no-bonus control (none) and the episodic bonuses E3B (Eq. 1) and NovelD (Eq. 2), evaluated as a complete matrix across all three environments. This lineup spans standard gated RNNs (GRU, LSTM), retention and linear-attention models (RetNet, GatedDeltaNet), a statespace model (Mamba-2), and a memoryless control. We run online recurrent PPO with truncated backpropagation through time. Bonus and memory: coupled, but separate. The exploration bonus is strictly unconditioned on the agent’s memory (Figure 1). The bonus encoder ϕ is a separate flat MLP that observes only the instantaneous observation ot , isolating it from the recurrent hidden state ht . The bonus signal augments the reward before advantage estimation (rt + λbt ), ensuring its gradient backpropagates through time into the recurrent cell alongside the task reward. Consequently, the bonus and memory are coupled during gradient updates but strictly separated in the forward pass. Any observed architecture-dependent effect therefore reflects variations in representational capacity given a shared training signal, rather than variations in the signal received. The bonus supplies advantage on transitions where the extrinsic reward is flat; determining whether this alters the underlying latent encoding is beyond the scope of this study. Environments. Three environments vary how the content of memory is acquired (full specifications in the appendix):

• MysteryPath-Grid (Pleines et al. 2025): An invisible path must be actively discovered via probing. Off-path steps reset the agent’s position but not the path itself; therefore, state coverage yields zero expected return unless the path is retained in memory across resets within the episode. • MiniGrid-MemoryS13 (Chevalier-Boisvert et al. 2023): A cue object near the start must be retained to solve a temporally distant binary T-junction (chance floor 0.50). We utilize the restrictive 3×3 view, which forces the agent to actively seek the cue, as the discriminative setting (the default 7 × 7 view makes the cue trivial to observe). • TinyReproduce (modified POPGym Autoencode (Morad et al. 2023)): A 10-symbol sequence is dictated on a fixed, unalterable schedule, and must subsequently be reproduced in reverse. Two exactly return-matched variants differ strictly in timing: Dense pays +1/k per correct token, while Sparse pays the same total at the end of the episode; both terminate on the first incorrect token. Reward Variants. On the two gridworlds, we manipulate the target of the reward signal while holding the environment, architectures, and hyperparameters fixed (calibration details in the appendix): Sparse pays +1 solely upon success. Penalty introduces an avoidable cost to exploratory moves (−1/Tmax per off-path step in MysteryPath; a permove cost in MemoryS13), leaving the theoretical optimal policy unchanged. Aligned (MysteryPath only) densely pays +0.1 for memory-advancing forward progress, serving as a negative control for the bonus. Distractor (both gridworlds) is density-matched to the aligned reward but fundamentally uninformative, paying ε = 0.1/Tmax solely for re-entering known tiles; the discounted criterion ε/(1 − γ) < 1 leaves the optimal policy unchanged. Evaluation & Budgets. The primary metric is deterministic-policy success rate over 20 evaluation episodes per checkpoint, reported as the tail mean over the final 20% of checkpoints. MysteryPath (Tmax =128, γ=0.995) and MemoryS13 (Tmax =845, γ=0.999) run for 20M steps; TinyReproduce (γ=0.99) runs for 10M. Every cell is evaluated across n=10 seeds, reported as mean ± std, with all significance claims supported by 95% unpaired seed-bootstrap intervals; learning curves with seed bands are in the appendix. (Agarwal et al. 2021). A single hyperparameter configuration is shared across all architectures (environment-specific overrides are applied identically to all cells), and all experimental runs utilize a bonus coefficient of λ=0.03 derived from a unified sweep. Full registry and calibration details are provided in the appendix.

Results To evaluate the interaction between representational capacity and exploration, we crossed diverse memory architectures with episodic exploration bonuses across three distinct POMDP environments. We find that exploration bonuses do not affect memory architectures uniformly; rather, the interaction yields three distinct empirical patterns tracking the un-

Table 1: MysteryPath-Grid: deterministic-policy success rate. Values denote the tail mean over the final 20% of evaluation checkpoints (mean ± std, n=10 seeds). Bold text denotes frozen cells (.00 success rate). E3B and NovelD bonuses are crossed with diverse memory architectures across four controlled reward manipulations. Sparse Cell

none

e3b

Penalty nvld

none

e3b

Aligned nvld

none

e3b

Distractor nvld

none

e3b

nvld

GRU .14±.01 .18±.02 .18±.02 .00±.00 .17±.01 .13±.01 .31±.03 .18±.02 .26±.02 .03±.05 .18±.02 .18±.01 LSTM .14±.01 .17±.02 .19±.02 .00±.00 .17±.02 .13±.01 .26±.02 .18±.02 .26±.02 .06±.06 .18±.02 .19±.02 RetNet .16±.03 .56±.05 .53±.03 .00±.00 .55±.02 .57±.04 .75±.05 .61±.05 .78±.04 .07±.06 .55±.03 .53±.05 GatedDeltaNet .17±.02 .63±.04 .59±.06 .00±.00 .58±.07 .59±.06 .67±.10 .65±.08 .82±.04 .02±.06 .62±.05 .57±.05 Mamba-2 .20±.02 .34±.04 .30±.03 .00±.00 .31±.04 .25±.03 .44±.03 .31±.03 .44±.05 .02±.05 .34±.05 .29±.03 Memoryless .06±.01 .00±.00 .04±.01 .00±.00 .00±.00 .01±.00 .05±.01 .01±.01 .05±.01 .01±.02 .00±.00 .04±.01

derlying reward structure of the environment. Furthermore, controlled manipulations of the reward structure verify that these patterns are governed by what the reward supervises, not merely its temporal density. Gains reported below represent within-cell changes in mean success against the respective no-bonus control, supported by 95% unpaired seedbootstrap intervals.

Exploration Does Not Help Memory Uniformly On MysteryPath-Grid, all memory architectures exhibit poor baseline performance without an exploration bonus (0.14– 0.20; the memoryless control sits at 0.06). The introduction of E3B does not provide a uniform performance increase (Table 1). Instead, the within-cell gains selectively order the architectures: standard gated RNNs exhibit negligible improvements (LSTM +0.03 [+0.02, +0.05], GRU +0.04 [+0.03, +0.06]), whereas linear-attention and retention models demonstrate substantial performance increases (RetNet +0.40 [+0.37, +0.44], GatedDeltaNet +0.46 [+0.44, +0.49]), with an intermediate gain for the state-space model Mamba-2 (+0.14). These three cells maintain disjoint seed distributions with and without the bonus, whereas GRU and LSTM distributions overlap heavily. We designate this the amplification pattern: the exploration signal disproportionately amplifies the underlying sequencemodeling capacity of the architecture. A coefficient sweep confirms this is a structural phenomenon rather than a hyperparameter artifact: across an order of magnitude of λ, GRU’s performance remains low and fails to scale (0.175 → 0.133) while RetNet’s scales monotonically (0.300 → 0.475). Conversely, the memoryless control actively declines under E3B (0.062 → 0.002) with disjoint distributions, demonstrating empirically that state coverage without recurrent representational capacity strictly degrades performance. On MiniGrid-MemoryS13 (3 × 3), critical information is initially observable and the architectural responses invert (Table 2). Without a bonus, GRU, LSTM, and RetNet average 0.49–0.50, making them statistically indistinguishable from chance at a binary junction. Under E3B, every seed in these three cells reaches at least 0.68, generating significant within-cell improvements (+0.42, +0.48, and +0.42, respectively); NovelD produces comparable gains (+0.36, +0.44, and +0.30). Conversely, models that independently converge above chance without a bonus demon-

strate marginal or zero improvement, with Mamba-2’s interval spanning zero (−0.10 [−0.26, +0.06]). We designate this the equalization pattern: the bonus dictates whether low-capacity cells learn the task at all, effectively pulling them to the performance ceiling rather than further benefiting already-competent models. On TinyReproduce, environment dynamics are purely scheduled and no sequence information can be actively sought. Consequently, no bonus produces a substantive within-cell effect (Table 3). GRU and LSTM converge on the task independently and remain unaffected; GatedDeltaNet plateaus at 0.30–0.40 regardless of the applied bonus. RetNet, Mamba-2, and the Memoryless control fail to learn exact reverse recall, aligning with known copying gaps documented for state-space and linear-attention models (Jelassi et al. 2024). All measured bonus effects lie strictly within ±0.08. The single interval excluding zero is LSTM under E3B on the sparse variant (+0.018 [+0.001, +0.034]), representing a statistically negligible fraction of its baseline performance. This constitutes the null pattern.

Reward Structure vs. Reward Density To isolate whether these interactions are driven by reward density or structural task dependencies, we manipulated what the reward explicitly supervises while holding frequency and hyperparameters fixed. The aligned reward on MysteryPath densely pays +0.1 for memory-advancing forward progress. Under this structure, RetNet and GatedDeltaNet reach 0.75 and 0.67 natively (Table 1). However, adding E3B degrades performance for four of the five memory architectures: GRU drops by −0.13, LSTM by −0.08, RetNet by −0.14, and Mamba-2 by −0.13 (all four intervals excluding zero), whereas GatedDeltaNet is essentially unchanged (0.67 → 0.65). Because E3B provides a dense novelty signal at every step, it functionally interferes with the dense extrinsic supervision. NovelD, constrained by its first-visit gating mechanism, interferes far less: its effects are neutral for LSTM, RetNet, and Mamba-2, mildly negative for GRU (0.31 → 0.26), and positive for GatedDeltaNet (0.67 → 0.82). Conversely, the distractor reward matches the aligned variant’s density but exclusively pays for uninformative state visitations (re-entering known tiles). This useless density induces policy convergence to suboptimal states, collapsing

Table 2: MiniGrid-MemoryS13: deterministic-policy success rate. Values denote the tail mean over the final 20% of evaluation checkpoints (mean ± std, n=10 seeds). E3B and NovelD bonuses are crossed with memory architectures across restricted (3 × 3) and default (7 × 7) fields of view, alongside penalty and distractor reward manipulations. 3 × 3 Sparse Cell

none

e3b

3 × 3 Penalty nvld

none

e3b

3 × 3 Distractor

nvld

none

e3b

7 × 7 Sparse

nvld

none

e3b

nvld

GRU .50±.01 .92±.09 .86±.19 .50±.01 .95±.05 .94±.10 .50±.02 .87±.09 .96±.04 .69±.19 .96±.10 .97±.08 LSTM .50±.02 .98±.02 .94±.10 .50±.01 .94±.06 .98±.02 .50±.01 .99±.02 .99±.02 .76±.22 .96±.07 .98±.03 RetNet .49±.02 .91±.11 .79±.19 .49±.01 .86±.12 .86±.11 .50±.01 .86±.15 .73±.21 .67±.17 .96±.06 .96±.05 GatedDeltaNet .76±.17 .97±.04 .98±.03 .68±.17 .96±.07 .97±.05 .73±.22 .98±.03 .99±.02 .94±.12 .93±.15 .99±.02 Mamba-2 .86±.14 .76±.23 .91±.06 .79±.24 .84±.19 .85±.12 .74±.21 .73±.31 .81±.21 .87±.15 .93±.11 .96±.03 Memoryless .35±.24 .50±.01 .50±.01 .50±.01 .48±.02 .50±.01 .50±.01 .49±.01 .50±.01 .50±.01 .48±.02 .50±.01

Table 3: TinyReproduce (k=10, reverse): exact-recall success rate. Values denote the tail mean over the final 20% of evaluation checkpoints (mean ± std, n=10 seeds). E3B and NovelD bonuses are crossed with memory architectures across sparse and dense reward variants. Sparse

Dense

Cell

none

e3b

nvld

none

e3b

nvld

GRU LSTM RetNet GatedDeltaNet Mamba-2 Memoryless

.90±.02 .91±.02 .00±.00 .33±.08 .01±.01 .00±.00

.90±.02 .93±.02 .00±.00 .31±.10 .01±.01 .00±.00

.90±.01 .92±.02 .00±.00 .40±.15 .01±.01 .00±.00

.91±.02 .91±.02 .00±.00 .35±.09 .01±.01 .00±.00

.90±.02 .92±.01 .00±.00 .32±.11 .01±.01 .00±.00

.90±.02 .91±.03 .00±.00 .39±.07 .01±.01 .00±.00

every memory architecture’s no-bonus baseline to between 0.02 and 0.07. Despite this dense signal, E3B successfully restores RetNet and GatedDeltaNet to their sparse-reward performance levels (0.55 and 0.62, compared to 0.56 and 0.63 on sparse). This dissociation shows that, in these tasks, a dense extrinsic reward neutralizes an exploration bonus only when it directly supervises the memory the task requires; matching its density with an uninformative signal confers no such effect.

Pricing Exploration Can Hinder Optimization The penalty reward variant on MysteryPath imposes a −1/Tmax cost per off-path step. Because falls are avoidable, the theoretical mathematical optimum is identical to the sparse reward. Despite this equivalence, the penalty induces policy convergence to a 0.00 success rate across all architectures (Table 1). Trajectory data confirms a stationary, suboptimal policy: over the final 80% of training, median falls per episode reach 0.00, episode lengths sit exactly at Tmax =128, and the critic’s loss approaches 0.00. The policies remain highly stochastic (exhibiting high policy entropy) but exclusively within verified-safe, zero-cost states. Both E3B and NovelD resolve this exploratory stagnation, restoring RetNet and GatedDeltaNet to their sparse-reward performance levels (0.55–0.60). This recovery occurs independently of the specific bonus magnitude: E3B delivers 2.6× the per-step penalty, while NovelD delivers only 0.3×, yet both recover GatedDeltaNet equally (0.58–0.59). This optimization failure is strictly dependent on the environmental state space; the matched penalty on MemoryS13 does not cause a collapse (Table 2) because no equivalent absorbing

zero-cost state exists.

Reward Sparsity & Reward Machines Conventional definitions of reward sparsity rely strictly on the frequency of non-zero payments, measuring temporal density rather than structural dependencies. This temporal metric fails to explain our empirical results: the base rewards in MysteryPath, MemoryS13, and TinyReproduce are identically sparse by frequency, yet an identical episodic bonus amplifies, equalizes, or nullifies architecture differences across them. We therefore formalize two distinct notions of sparsity using observation-anchored reward machines. Structural sparsity evaluates whether the reward can be reproduced by an automaton that omits the history required to solve the task. Potential sparsity evaluates whether the immediate one-step reward optimally ranks local actions. While Toro Icarte et al. (2023) defines perfect reward machines for POMDPs, no corresponding formulation equips a POMDP with an arbitrary (not necessarily perfect) reward machine. Definition 1 (POMDPRM). A POMDP with a simple reward machine (POMDPRM) is a tuple T = ⟨S, A, O, p, ω, γ, µ, P, L, RP OA ⟩ where S, A, O, p, ω, γ, µ are as in a POMDP, P is a finite set of propositional symbols, L : O × A × O → 2P is a labelling function, and RP OA = ⟨U, u0 , δu , δr ⟩ is an RM with finite U , δu : U ×2P → U and δr : U ×2P → R. The reward process of T is given by x0 = u0 , xt+1 = δ x , L(o , a , o ) , u t t t t+1 and r̃t = δr xt , L(ot , at , ot+1 ) . Definition 2 (Encoding). Given a POMDP M = ⟨S, A, O, p, ω, r, γ, µ⟩,

• MDPRM ⟨S, A, p, γ, µ, P, L, RP SA ⟩, where RP SA = ⟨U, u0 , δu , δr ⟩, encodes M ⇐⇒ on all reachable tra- jectories under every policy, rt = δr xt , L(st , at , st+1 ) for all t, where xt is the RM state at t; • POMDPRM ⟨S, A, O, p, ω, γ, µ, P, L, RP OA ⟩, where RP OA = ⟨U, u0 , δu , δr ⟩, encodes M ⇐⇒ for every observation-history policy π, hX hX i i Eπ γ t rt = Eπ γ t r̃t . t≥0

t≥0

The RM of a POMDPRM is not strictly required to be perfect: the expected machine reward on an observed transition is defined as the conditional expectation of the environment reward given the observation. While encoders are not guaranteed to exist globally (the appendix demonstrates a threestate POMDP requiring an unbounded number of machine states), they exist and are computable provided the observation stream induces only finitely many posteriors over the hidden state. Definition 3 (Structural sparsity). Given a POMDP M = ⟨S, A, O, p, ω, r, γ, µ⟩, r is structurally sparse if no POMDPRM encodes M, or if there exists a POMDPRM ⟨S, A, O, p, ω, γ, µ, P, L, RP OA ⟩ which encodes M such that RP OA is not perfect w.r.t. L (Eq. 3). r is structurally dense if at least one POMDPRM encodes M and, for all POMDPRMs ⟨S, A, O, p, ω, γ, µ, P, L, RP OA ⟩ which encode M, RP OA is perfect w.r.t. L. Structural density indicates that every automaton consistent with the return inherently encodes the memory required by the task. Conversely, structural sparsity indicates that an automaton can reproduce the return without achieving perfection. MysteryPath and MemoryS13 are both structurally sparse, but via distinct mechanisms. In MysteryPath, the one-state machine (Figure 2a) encodes the return while entirely ignoring the path; the reward signal never supervises the memory required to solve the task. In MemoryS13, the corresponding machine (Figure 2b) tracks the cue and encodes the return, yet fails perfection on raw observations due to visual aliasing (e.g., corridor cells share identical views, rendering next-observation predictions dependent on unobserved positions). Here, dynamics aliasing—rather than the reward structure itself—prevents perfection. Conversely, TinyReproduce is structurally dense in its dictation abstraction: the play observation remains constant following both correct and incorrect tokens, forcing every encoder to carry the fully dictated sequence (Figure 2c). Formal proofs are provided in the appendix, including the analysis of a rewardpreserving, structurally dense abstraction of MemoryS13 that strictly removes dynamics aliasing. The second notion of sparsity applies to arbitrary encoders; perfection is not assumed prior to Theorem 1. Definition 4 (Greedy RM policy). Given a POMDPRM ⟨S, A, O, p, ω, γ, µ, P, L, RP OA ⟩ and a fixed full-support reference policy π0 (a | o, u) = 1/|A|, the greedy RM policy π is uniquely given by X π(· | o, u) = arg max Prπ0 (o′ | o, u, a) δr (u, σ), a

o′ ∈O

where σ = L(o, a, o′ ) and tie-breaking among maximizing actions is uniformly random. Here, Prπ0 (o′ | o, u, a) denotes the next-observation distribution along trajectories generated by π0 ; it coincides with the canonical kernel of Eq. 3 under perfect machines. Fixing π0 strictly defines π. Definition 5 (Potential sparsity). Suppose POMDPRM T = ⟨S, A, O, p, ω, γ, µ, P, L, RP OA ⟩ encodes the POMDP ⟨S, A, O, p, ω, r, γ, µ⟩, where RP OA = ⟨U, u0 , δu , δr ⟩. Let P t γ r J(π) := Eπ denote the expected return in M. t t≥0 For ϕ : U × O → R define the shaped one-step value X q ϕ (o, u, a) = Prπ0 (o′ | o, u, a)r̂(u, o, o′ , a) o′ ∈O

where r̂(u, o, o′ , a) = δr u, L(o,a, o′ ) + γ ϕ(u′ , o′ ) − ϕ(u, o), u′ = δu u, L(o, a, o′ ) , and let π ϕ = arg maxa q ϕ (o, u, a). If there exists a ϕ such that J(π) < J(π ϕ ) where π is greedy RM policy for T , then r is potentially sparse w.r.t. T ; else r is potentially dense w.r.t. T . The correction term γ ϕ(u′ , o′ ) − ϕ(u, o) maintains the potential-based form of Ng, Harada, and Russell (1999), defined over the state-observation pairs (u, o) rather than machine edges. The shaped table serves strictly to select onestep policies, whose true returns J are subsequently evaluated. Because a coarse automaton cannot register a misranking that its state space fails to represent, potential sparsity is exclusively evaluated in settings where the reward is structurally dense and all encoders are perfect. Theorem 1 (Dense rewards need no lookahead). For a POMDP M = ⟨S, A, O, p, ω, r, γ, µ⟩, if r is structurally dense, POMDPRM T = ⟨S, A, O, p, ω, γ, µ, P, L, RP OA ⟩ encodes M (hence is perfect, by Definition 3), and r is potentially dense w.r.t. T , then the greedy RM policy over T is optimal for M among all observation-history policies. Perfection collapses the POMDP to a finite MDP over the pairs (o, u). In this formulation, shaping with the optimal value function converts the one-step reward into the optimal advantage; thus, potential density implies the unshaped greedy policy is already optimal. Theorem 1 strictly characterizes the induced planning problem rather than the convergence dynamics of actor-critic optimization. Notably, the two reward variants of TinyReproduce diverge on potential sparsity with respect to the sequence machine (appendix).

Discussion We evaluated six memory architectures and two episodic bonuses under a single training stack across three environments. The identical bonus yielded three distinct outcomes: amplification on MysteryPath, equalization on MemoryS13, and a null effect on TinyReproduce. Structural Determinants of Interaction Patterns. These divergence patterns isolate the post-exploration retention burden. The two sparsity properties separate them sequentially: structural sparsity applies first, while potential sparsity applies only when the reward is structurally dense. In MysteryPath, the bonus induces state coverage, but this yields zero

⟨pl1 , 0⟩

⟨o/w, 0⟩ ⟨tok0 , 0⟩

u0 ⟨cueA , 0⟩

⟨o/w, 0⟩

⟨goal, +1⟩

⟨matchA , +1⟩ ⟨matchB , 0⟩

(a) MysteryPath

⟨cueB , 0⟩

⟨matchi , 0.5⟩

⟨matchB , +1⟩

⟨tok0 , 0⟩

0 ⟨tok1 , 0⟩

⟨pl1 , 0⟩

⟨tok0 , 0⟩

⟨pl0 , 0⟩

[0]

⟨p l1 ⟨pl0 , +1⟩ ,0

⟩

u0 ⟨o/w, 0⟩

⟨tok1 , 0⟩

⟨pl1 , 0⟩

[1] ⟨pl1 , 0⟩

⟩

,0 pl 0 ⟨pl1 ,⟨ +1⟩

⟨pl0 , 0⟩

⟨matchA , 0⟩

(b) MiniGrid-MemoryS13

⟨pl0 , 0⟩

Figure 2: Reward machines for the three environments. Transitions are labeled ⟨φ, c⟩, where φ denotes the label condition and c denotes the reward. The symbol o/w matches any remaining label, and uf indicates the terminal state. (a) The MysteryPath machine, featuring a single non-terminal state and issuing +1 upon reaching the visible goal. (b) The MemoryS13 machine, which stores the initially observed cue. The transition matchA yields +1 from uA and 0 from uB , while a cue-blind transition earns 0.5. (c) The TinyReproduce machine, which stores the dictated sequence. During replay, correctness is verified against stored targets, with +1 issued solely upon full sequence completion. return unless the high-dimensional path is retained. Structural sparsity (Definition 3) formalizes this lack of memory supervision: the abstraction admits a one-state machine that reproduces the return while omitting the path. Since retention is never reward-supervised, the bonus strictly multiplies the sequence-modeling capacity a cell already possesses (amplification). Conversely, the MemoryS13 cue abstraction is structurally dense but potentially sparse (Definition 5): the agent must actively discover the cue, but the subsequent retention burden is only a single reward-supervised bit. The bonus supplies the missing local advantage to seek the cue; since standard cells easily carry one bit, the bonus determines whether convergence occurs rather than how well (equalization). TinyReproduce’s dictation abstraction is structurally dense and potentially dense: every encoder must carry the full sequence, and the observation stream is action-independent. Theorem 1 accounts for this null effect; joint density implies the unshaped greedy policy is already optimal, leaving no exploratory deficit to correct. Reward Manipulations and Exploratory Stagnation. Controlled variants confirm that reward structure, rather than density, drives bonus efficacy. The aligned reward (which directly supervises the required memory) renders the bonus redundant or detrimental, whereas the density-matched, uninformative distractor reward preserves its full restorative effect. Separately, the penalty variant isolates an optimization failure: a return-matched cost on exploratory actions drives architectures into stationary policies confined to zerocost states. Either exploration bonus overcomes this suboptimal convergence regardless of its relative magnitude to the penalty (E3B pays 2.6× the per-step cost and NovelD only 0.3×, yet both recover GatedDeltaNet equally). This indicates that recovery involves breaking stagnation rather than outbidding the penalty. Reward sparsity determines where a bonus is effective, whereas reward pricing determines whether exploration occurs at all. Limitations. The formal results cover the regimes unevenly. Theorem 1 accounts for the null pattern, whereas the amplify/equalize distinction rests on empirical retentionburden analysis. Additionally, every classification applies

strictly to reward-preserving abstractions. The diagnostic requires reasoning over encoding machines, which may not exist globally or scale to high-dimensional inputs. Empirically, this study is bounded to discrete-action domains, a single onpolicy algorithm, and observation-based episodic bonuses. Because the forward pass strictly separates the bonus and memory, we measure behavioral outcomes rather than latent encoding alterations. Evaluating these dependencies under global bonuses, off-policy learners, and continuous environments remains for future work.

Conclusion The interaction between episodic exploration bonuses and neural memory architectures is task-dependent: an identical exploration signal amplifies capacity differences, equalizes performance, or yields a null effect according to the environment’s reward structure. Controlled manipulations confirm that a dense reward neutralizes an exploration bonus only when it directly supervises the necessary latent representation, and that pricing exploratory actions can halt optimization even where the theoretical optimum is unchanged. Observation-anchored reward machines organize these regimes by what the reward supervises rather than how often it pays. Structural sparsity (an automaton reproduces the return while omitting the required memory) determines whether retention is supervised, dictating how severely architectural capacity gates the gain. Where the reward is structurally dense, potential sparsity (the one-step reward misprices local exploratory actions) determines whether an exploratory deficit exists. Practitioners must therefore evaluate what the reward inherently supervises and whether the architecture can retain the information the bonus exposes. An exploration bonus induces necessary state coverage, but only adequate representational capacity can convert that coverage into optimal expected return.

References Agarwal, R.; Schwarzer, M.; Castro, P. S.; Courville, A.; and Bellemare, M. G. 2021. Deep Reinforcement Learning at the Edge of the Statistical Precipice. In Advances in Neural Information Processing Systems (NeurIPS). Badia, A. P.; Sprechmann, P.; Vitvitskyi, A.; Guo, D.; Piot, B.; Kapturowski, S.; Tieleman, O.; Arjovsky, M.; Pritzel, A.; Bolt, A.; and Blundell, C. 2020. Never Give Up: Learning Directed Exploration Strategies. In International Conference on Learning Representations (ICLR). Bellemare, M. G.; Srinivasan, S.; Ostrovski, G.; Schaul, T.; Saxton, D.; and Munos, R. 2016. Unifying Count-Based Exploration and Intrinsic Motivation. In Advances in Neural Information Processing Systems (NeurIPS). Burda, Y.; Edwards, H.; Storkey, A.; and Klimov, O. 2019. Exploration by Random Network Distillation. In International Conference on Learning Representations (ICLR). Chevalier-Boisvert, M.; Dai, B.; Towers, M.; de Lazcano, R.; Willems, L.; Lahlou, S.; Pal, S.; Castro, P. S.; and Terry, J. 2023. Minigrid & Miniworld: Modular & Customizable Reinforcement Learning Environments for Goal-Oriented Tasks. In Advances in Neural Information Processing Systems (NeurIPS), Datasets and Benchmarks Track. Gu, A.; and Dao, T. 2023. Mamba: Linear-Time Sequence Modeling with Selective State Spaces. arXiv preprint arXiv:2312.00752. Hausknecht, M.; and Stone, P. 2015. Deep Recurrent QLearning for Partially Observable MDPs. In AAAI Fall Symposium Series. Henaff, M.; Jiang, M.; and Raileanu, R. 2023. A Study of Global and Episodic Bonuses for Exploration in Contextual MDPs. In Proceedings of the 40th International Conference on Machine Learning (ICML). Henaff, M.; Raileanu, R.; Jiang, M.; and Rocktäschel, T. 2022. Exploration via Elliptical Episodic Bonuses. In Advances in Neural Information Processing Systems (NeurIPS). Jelassi, S.; Brandfonbrener, D.; Kakade, S. M.; and Malach, E. 2024. Repeat After Me: Transformers are Better than State Space Models at Copying. In International Conference on Machine Learning (ICML). Kaelbling, L. P.; Littman, M. L.; and Cassandra, A. R. 1998. Planning and Acting in Partially Observable Stochastic Domains. Artificial Intelligence, 101(1–2): 99–134. Kapturowski, S.; Ostrovski, G.; Quan, J.; Munos, R.; and Dabney, W. 2019. Recurrent Experience Replay in Distributed Reinforcement Learning. In International Conference on Learning Representations (ICLR). Kayal, A.; Pignatelli, E.; and Toni, L. 2025. The Impact of Intrinsic Rewards on Exploration in Reinforcement Learning. Neural Computing and Applications. ArXiv:2501.11533. Lidayan, A.; Dennis, M.; and Russell, S. 2025. BAMDP Shaping: A Unified Theoretical Framework for Intrinsic Motivation and Reward Shaping. In International Conference on Learning Representations (ICLR). ArXiv:2409.05358.

Lu, C.; Schroecker, Y.; Gu, A.; Parisotto, E.; Foerster, J.; Singh, S.; and Behbahani, F. 2023. Structured State Space Models for In-Context Reinforcement Learning. In Advances in Neural Information Processing Systems (NeurIPS). Morad, S.; Kortvelesy, R.; Bettini, M.; Liwicki, S.; and Prorok, A. 2023. POPGym: Benchmarking Partially Observable Reinforcement Learning. In International Conference on Learning Representations (ICLR). Ng, A. Y.; Harada, D.; and Russell, S. 1999. Policy Invariance Under Reward Transformations: Theory and Application to Reward Shaping. In Proceedings of the 16th International Conference on Machine Learning (ICML), 278–287. Ni, T.; Ma, M.; Eysenbach, B.; and Bacon, P.-L. 2023. When Do Transformers Shine in RL? Decoupling Memory from Credit Assignment. In Advances in Neural Information Processing Systems (NeurIPS). Pathak, D.; Agrawal, P.; Efros, A. A.; and Darrell, T. 2017. Curiosity-Driven Exploration by Self-Supervised Prediction. In Proceedings of the 34th International Conference on Machine Learning (ICML). Pleines, M.; Pallasch, M.; Zimmer, F.; and Preuss, M. 2025. Memory Gym: Towards Endless Tasks to Benchmark Memory Capabilities of Agents. Journal of Machine Learning Research, 26(6): 1–40. Savinov, N.; Raichuk, A.; Marinier, R.; Vincent, D.; Pollefeys, M.; Lillicrap, T.; and Gelly, S. 2019. Episodic Curiosity through Reachability. In International Conference on Learning Representations (ICLR). Smirnov, I.; and Gu, S. 2025. RLBenchNet: The Right Network for the Right Reinforcement Learning Task. arXiv:2505.15040. Toro Icarte, R.; Klassen, T. Q.; Valenzano, R.; Castro, M. P.; Waldie, E.; and McIlraith, S. A. 2023. Learning Reward Machines: A Study in Partially Observable Reinforcement Learning. Artificial Intelligence. Toro Icarte, R.; Klassen, T. Q.; Valenzano, R.; and McIlraith, S. A. 2018. Using Reward Machines for High-Level Task Specification and Decomposition in Reinforcement Learning. In Proceedings of the 35th International Conference on Machine Learning (ICML), 2107–2116. Toro Icarte, R.; Klassen, T. Q.; Valenzano, R.; and McIlraith, S. A. 2022. Reward Machines: Exploiting Reward Function Structure in Reinforcement Learning. Journal of Artificial Intelligence Research (JAIR), 73: 173–208. Toro Icarte, R.; Waldie, E.; Klassen, T. Q.; Valenzano, R.; Castro, M. P.; and McIlraith, S. A. 2019. Learning Reward Machines for Partially Observable Reinforcement Learning. In Advances in Neural Information Processing Systems (NeurIPS), volume 32. Wiewiora, E. 2003. Potential-Based Shaping and Q-Value Initialization Are Equivalent. Journal of Artificial Intelligence Research (JAIR), 19: 205–208. Yuan, M.; Castanyer, R. C.; Li, B.; Jin, X.; Berseth, G.; and Zeng, W. 2025. RLeXplore: Accelerating Research in Intrinsically-Motivated Reinforcement Learning. Transactions on Machine Learning Research (TMLR). ArXiv:2405.19548.

Zhang, T.; Xu, H.; Wang, X.; Wu, Y.; Keutzer, K.; Gonzalez, J. E.; and Tian, Y. 2021. NovelD: A Simple yet Effective Exploration Criterion. In Advances in Neural Information Processing Systems (NeurIPS).

Environment Details Overview. We use three environments that vary how memory content is acquired while keeping the training stack identical. Table 4 summarizes the observation spaces, action spaces, horizons, and training budgets. MysteryPath-Grid (Pleines et al. 2025). A continuous, invisible path connects a fixed origin to a goal. The agent observes its own position and the visible goal, but the path itself remains hidden. Stepping off the path results in a fall, resetting the agent to the origin without altering the path’s layout. Because the path is procedurally generated each episode, memory content must be discovered within each episode through trial and error. An optimal agent retraces known safe steps and systematically probes unknown edges. Consequently, exploration incurs the cost of falls, and this exploration yields no benefit unless the verified path is retained in memory across resets. The action space consists of the four cardinal directions. Because falls are entirely avoidable, the penalty reward variant is strictly return-matched to the sparse baseline. MiniGrid-MemoryS13 (Chevalier-Boisvert et al. 2023). The agent spawns near a cue object (e.g., a key or a ball), must observe it, traverse a corridor, and select the matching object at a distant T-junction. Here, memory content exists from the start; the agent must merely find and retain it. Observations are one-hot encoded MiniGrid tensors. To appropriately handle categorical channels (object type, color, state) rather than continuous pixel intensities, a wrapper expands the raw (N, N, 3) grid into a (N, N, 20) binary format. We evaluate both the default 7 × 7 view and a restricted 3 × 3 view. The restricted view forces the agent to actively seek the cue, introducing a mild exploration challenge, and thus serves as our primary discriminative setting. The S13 reward wrapper. MiniGrid’s default reward applies horizon discounting, which confounds task success with completion speed and is not strictly sparse. To ensure a fair comparison against MysteryPath using matched rewards and metrics, our wrapper provides three modes: • native: The default reward of 1 − 0.9 t/Tmax for reaching the correct object, and 0 otherwise. This is retained for baseline reference only. • matched sparse: +1 for finding the matching object, and 0 otherwise. This flat-sparse variant provides a direct match to MysteryPath’s sparse reward. • matched penalty: Identical to the matched sparse mode, but subtracts p for every non-nop action. This introduces an unconditional per-move cost absent from the native discount (which applies only upon success and cannot induce a policy freeze). MiniGrid’s done action (index 6) is cost-free, acting as a zero-cost sanctuary. We set p = 1/Tmax = 1/845, serving as the horizon-normalized equivalent of MysteryPath’s −1/128 off-path penalty. Regardless of the reward mode, the wrapper computes info["is_success"] based purely on environment geometry (agent_pos == success_pos). This guaran-

tees that the reported success rate is a clean, binary metric that remains identical across all reward variants. TinyReproduce (modified POPGym Autoencode, Morad et al. 2023). A sequence of k tokens from an alphabet of v symbols is dictated on a strict schedule, and the agent must reproduce it in reverse order. Observations are formatted as [ ⊮watch , ⊮play , onehot(v) ], with a discrete action space over the v symbols. For k=10 and v=4, the episode spans 2k − 1 = 19 steps. The environment begins by revealing the first token, followed by k−1 additional watch steps, and concludes with k reproduction steps. The task fundamentally forces memory retention without any exploration demands, serving as a pure null-regime baseline. TinyReproduce instrumentation and the rm_state interface. The environment exposes its ground-truth rewardmachine state at every step, enabling empirical verification of our structural classification: • info["phase"] ∈ {watch, play}. • info["rm_state"]: During the watch phase, this contains the prefix revealed so far (tuple(seq[:shown])). During the play phase, it contains the remaining sequence to be emitted, in emission order. This is the exact minimal sufficient statistic of the history, making it the perfect RM state. • info["n_correct"] and info["is_correct"] track step-wise accuracy, while info["success"] and info["is_success"] indicate if the agent successfully reproduced all k tokens.

Hyperparameter Registry All runs are managed by a single declarative registry. A shared set of hyperparameters (Table 5) serves as the baseline across all experiments. The per-environment tables strictly detail deviations from this baseline. We do not use architecture-specific hyperparameters anywhere in the suite.

Reward-Variant Calibration Distractor: the discounted criterion. The distractor rewards the agent with ε every time it revisits a tile. If a policy ignores the main task to farmP these revisits, the theoretical maximum it can earn is ε t≥0 γ t = ε/(1 − γ). For the optimal policy to remain unchanged, this farmed total must stay strictly below the +1 success payout. Evaluating the configurations: on MysteryPath, ε/(1 − γ) = (0.1/128)/0.005 ≈ 0.156 < 1. On MemoryS13, it is (0.1/845)/0.001 ≈ 0.118 < 1. In both scenarios, the margin of safety is approximately 6–8×. This guarantees that farming revisits can never become the optimal strategy, even prior to factoring in the constraint that a tile must first be visited before it can pay out again. Penalty: return-matching. Because the per-step penalty is −1/Tmax , the maximum cumulative penalty an agent can accrue over a full episode is −1. Since falls (MysteryPath) and moves beyond the free done action (MemoryS13) are entirely avoidable, the optimal trajectory for the sparse variant yields the exact same return under the penalty variant. The

Table 4: Environment specifications. “Flat dim” is the flattened observation size provided to the encoder. MysteryPath uses a Nature-DQN convolutional encoder; the MiniGrid one-hot tensors and the TinyReproduce vectors are processed by an MLP encoder. Every configuration in the suite evaluates n=10 seeds. Environment

Observation

Flat dim

Actions

Tmax

Budget

MysteryPath-Grid MemoryS13 (3 × 3) MemoryS13 (7 × 7) TinyReproduce (k=10)

84 × 84 × 3 3 × 3 × 20 7 × 7 × 20 R6

21,168 180 980 6

4 7 7 4

128 845 845 19

20M 20M 20M 10M

Table 5: Shared defaults (all environments) and per-architecture kwargs. Entries listed in the per-environment tables override these baseline settings. Optimization learning rate epochs per update clip range entropy coef value coef max grad norm target KL encoder dim encoder hidden

Rollout / PPO 1 × 10 4 0.2 0.008 1.0 0.5 0.05 128 256

−4

parallel envs steps per env discount γ GAE λ TBPTT chunk chunks per batch bonus coef λint eval every eval episodes

16 512 0.995 0.95 64 32 0.03 10 rollouts 20

Architecture kwargs GRU, LSTM, Memoryless GatedDeltaNet

(defaults) assoc. size 64

theoretical optimum is therefore mathematically unchanged; only the optimization landscape shifts, successfully isolating the exploration pricing dynamic.

Bonus-Coefficient Sweep We use a coefficient of λint = 0.03 across all reported runs for both E3B and NovelD, regardless of the environment or reward variant. This value was established via the sweep in Table 9. To maintain consistency, NovelD and the nonMysteryPath environments inherit this value. Table 10 compares our chosen value against coefficients utilized in prior literature. Bracketing λ from above. While Table 9 confirms λ = 0.03 as the strongest tested value, we ran an upper bracket test at λ = 0.1 (a 3.3× increase) on the two cells most responsive to the bonus (Table 11). Both architectures completely collapsed, confirming that λ = 0.03 represents a true interior optimum rather than an unexplored edge.

Learning Curves and Training Diagnostics The learning dynamics across all environments and architectures illustrate the three patterns directly, bypassing reliance on final tail means alone. Curves represent the deterministic evaluation success rate (20 episodes per evaluation, taken every 10 rollouts), with the shaded band representing a 95% seed-bootstrap confidence interval on the mean. The freeze is a sampling failure, not a value-estimation failure. The timing of the first success rules out the possi-

RetNet Mamba-2

4 heads 4 heads, dstate 64, expand 2

bility that the agent reaches the goal but fails to propagate its value backward. Across every no-bonus seed in the penalty arm, the goal is never reached during the 20M steps. The +1 reward is never observed, leaving nothing to propagate. Upon introducing a bonus, the agent hits the goal within the first few thousand steps. The rescue is not arithmetic. The bonus does not simply overpower the penalty. While E3B delivers 2.6× the penalty scale, NovelD only delivers 0.3×, meaning the penalty heavily outweighs the NovelD bonus (Table 14). Nevertheless, NovelD successfully rescues the freeze (Table 12), proving the rescue relies on more than the net positive sign of the per-step reward.

Statistical Analysis of the Architecture–Bonus Interaction This section quantifies the Architecture×Bonus interaction claims (amplification, equalization, and null). The primary metric is the per-seed tail-mean success rate over the final 20% of training. We exclude the memoryless control to avoid artificially inflating the between-architecture spread statistic. Factorial analysis. Table 15 details a two-way ANOVA for each environment. Due to highly heterogeneous cell variances and bounded, occasionally bimodal outcomes (Fig. 7), we pair each interaction F with a permutation p-value. Permuting bonus labels within each architecture (2×104 resamples) preserves the architecture main effect while nullifying

Table 6: MysteryPath-Grid. No hyperparameter overrides; the shared baseline from Table 5 applies completely. Environment id Horizon Tmax Discount γ Budget / seeds Architectures Training signals HP overrides

MysteryPath-Grid-v0 128 0.995 20M steps, n = 10 GRU, LSTM, RetNet, GatedDeltaNet, Mamba-2, Memoryless none, E3B, NovelD (shared)

Reward variants Sparse Penalty Aligned Distractor

+1 on success +1 on success, −0.008 (−1/Tmax ) per off-path step +0.1 per step of forward progress along the confirmed path +ε per revisited tile, ε = 0.1/Tmax ≈ 7.8 × 10−4

Table 7: MiniGrid-MemoryS13. The delayed cross-corridor reward necessitates a longer credit assignment horizon than the shared baseline provides. We tuned these four overrides specifically for this environment and applied them uniformly to all architectures. Environment id Horizon Tmax Budget / seeds Architectures Training signals

MiniGrid-MemoryS13-v0 845 (5 · 132 ) 20M steps, n = 10 GRU, LSTM, RetNet, GatedDeltaNet, Mamba-2, Memoryless none, E3B, NovelD

HP overrides (all cells) discount γ 0.999 GAE λ 0.98 TBPTT chunk 32 learning rate 3 × 10−4 Reward variants Sparse 3 × 3 Sparse 7 × 7 Penalty 3 × 3 Distractor 3 × 3

flat +1 on the matching object, 3 × 3 egocentric view as above, default 7 × 7 view flat +1, −1/Tmax ≈ −1.2 × 10−3 per movement action flat +1, +ε per revisited cell, ε = 0.1/Tmax ≈ 1.2 × 10−4

Table 8: TinyReproduce. We use a single learning rate across all architectures. Because the shared 10−4 rate caused several cells to floor near ≈0.00, the entire suite runs at 10−3 without any architecture-specific exceptions. The learning rate is the sole override; the discount factor relies on the shared γ = 0.995 baseline. Environment id Sequence Horizon Tmax Budget / seeds Architectures Training signals

TinyReproduce-v0 k = 10 symbols, alphabet v = 4, reverse order 2k − 1 = 19 10M steps, n = 10 GRU, LSTM, RetNet, GatedDeltaNet, Mamba-2, Memoryless none, E3B, NovelD

HP overrides All cells

learning rate 10−3 (only override; γ = 0.995 shared)

Reward variants (exactly return-matched; differ only in timing) Dense +1/k at each correctly reproduced token Sparse lump sum (#correct)/k at episode end

none

MysteryPath-Grid: success rate vs.\ env steps (n = 10, mean ± 95\% CI)

GRU

1.0

LSTM

RetNet

GatedDelta

E3B

Mamba-2

NovelD

Memoryless

sparse

0.8 0.6 0.4 0.2 0.0 0

1.0

penalty

0.8 0.6 0.4 0.2 0.0

aligned (dense)

1.0 0.8 0.6 0.4 0.2 0.0

distractor (dense)

1.0 0.8 0.6 0.4 0.2 n=9

0.0

steps (M)

Figure 3: MysteryPath-Grid across all four reward variants (rows) × six architectures (columns), n=10, showing the mean with a 95% seed-bootstrap CI. Amplification is evident in the sparse row: the bonus separates RetNet, GatedDeltaNet, and Mamba-2 from a floored no-bonus baseline, while GRU and LSTM show minimal movement. The penalty row highlights the freeze: without a bonus, every architecture flatlines at zero, but bonuses successfully restore learning. the bonus effect. The permutation values offer a robust, nonparametric confirmation. Table 9: Bonus-coefficient sweep on MysteryPath (E3B) showing mean final success. The response scales monotonically with λ for architectures that successfully convert the bonus into task success. It remains flat for GRU across an entire order of magnitude, indicating that GRU’s lack of response is not a tuning failure. Cell GRU RetNet GatedDeltaNet

λ=0.003

λ=0.01

λ=0.03

0.175 0.300 0.225

0.120 0.370 0.280

0.133 0.475 0.292

Note: n represents hyperparameter combinations, not seeds. Each λ is evaluated across the same six (learning rate, chunk length) pairings drawn from {10−4 , 2.5 × 10−4 } × {32, 64, 128}, ensuring λ is not confounded by them (λ=0.01 covers 5 of the 6). Because this sweep utilized learning rates and chunk lengths differing from the final registry, it serves strictly to confirm tuning and a monotonic response, rather than acting as a matched-HP ablation. The final-registry results (Table 1 of the main text) outperform these sweep values due to an optimized configuration. We pull the success metric directly from eval/mean_reward, which maps perfectly to the success rate on sparse MysteryPath.

Effect sizes. With n=10, the gridworld interactions are overwhelmingly significant; thus, we focus on effect sizes using seed-level bootstrap intervals (104 resamples). These intervals properly capture the confirmatory null by measuring the absence of an effect. Amplification and equalization as dispersion shifts. Let Vcond represent the variance across the five architecture means. Amplification predicts Vbonus /Vnone > 1, equalization predicts <1, and the null predicts =1. Per-cell effect sizes. Table 17 outlines the probability of improvement Pr(Ybonus > Ynone ) (Agarwal et al. 2021) across all seed pairings. On MemoryS13, Mamba-2 (0.48 under E3B) and GatedDeltaNet (0.85) show minimal improvement because they already clear the cue-blind optimum without a bonus. Equalization closes the spread from below: the bonus lifts the stuck cells and does practically nothing for those already succeeding. On TinyReproduce, the per-cell values scatter around 0.5, indicating a genuine null result. A scale-free reading of MemoryS13. Because the seed distribution on MemoryS13 is bimodal, a binary summary

none

MiniGrid-MemoryS13: success rate vs.\ env steps (n = 10, mean ± 95\% CI)

GRU

sparse 3 × 3

1.0

LSTM

RetNet

GatedDelta

E3B

Mamba-2

NovelD

Memoryless

0.8 0.6 0.4 0.2 0.0 0

penalty 3 × 3

1.0 0.8 0.6 0.4 0.2 0.0

distractor 3 × 3

1.0 0.8 0.6 0.4 0.2 n=9

0.0

sparse 7 × 7

1.0 0.8 0.6 0.4 0.2 0.0

steps (M)

Figure 4: MiniGrid-MemoryS13 across four reward variants (rows) × six architectures (columns), n=10, showing the mean with a 95% seed-bootstrap CI. Equalization is visible in the sparse 3 × 3 row: GRU, LSTM, and RetNet are stuck at the cue-blind 0.50 mark without a bonus, but reach the ceiling with one. GatedDeltaNet and Mamba-2 gain proportionally less. The wide confidence bands without a bonus reflect the bimodal “seed lottery” discussed in Section .

TinyReproduce: success rate vs.\ env steps (n = 10, mean ± 95\% CI) GRU

sparse

1.00

LSTM

RetNet

none

GatedDelta

E3B

Mamba-2

NovelD

Memoryless

0.75 0.50 0.25 0.00

1.00

dense

0.75 0.50 0.25 0.00

steps (M)

Figure 5: TinyReproduce across both reward variants (rows) × six architectures (columns), n=10, showing the mean with a 95% seed-bootstrap CI. The null pattern is consistent: all three signals overlap perfectly in every panel. The only observed differences are architectural (GRU and LSTM solve the task; RetNet and Mamba-2 do not), and adding a bonus does not alter the outcome.

Table 10: Published intrinsic-reward coefficients. Direct comparisons are difficult due to differing bonus scaling techniques. Notably, only E3B and our implementation normalize the bonus via a running standard deviation prior to applying the scale. Method

Environment

Coef.

Norm.

Swept over

E3B (Henaff et al. 2022) E3B E3B NovelD (Zhang et al. 2021) NovelD

MiniHack VizDoom Habitat MiniGrid NetHack

1.0 3 × 10−6 0.1 0.1 100

yes no — no no

10−4 –10 3 × 10−7 –10−4 10−4 –1.0 {0.01, 0.05, 0.1} —

Ours

MysteryPath, S13, Tiny

0.03

yes

{0.003, 0.01, 0.03}

E3B does not report MiniGrid experiments; MiniHack provides the closest comparison and, similar to our setup, applies the coefficient to a running-std-normalized bonus. NovelD’s coefficient applies to an unnormalized RND-difference bonus, complicating direct comparison.

Table 11: Upper bracket test on λ. Evaluated using the sparse MysteryPath variant with E3B, measuring success at 5M steps. The λ=0.03 column reports mean ± std over the n=10 reported seeds, while λ=0.1 tracks a single seed per cell. Increasing the coefficient by 3.3× completely destroys performance. λ=0.1 (n=1)

RetNet GatedDeltaNet

0.223 ± 0.074 0.227 ± 0.058

0.00 0.02

These bracket runs utilize a single seed and terminate at 5M steps, and are not intended to replace a full sweep arm. However, the performance collapse is a full order of magnitude larger than the seed variance at λ=0.03, proving the drop is not an artifact of limited run time. Viewed alongside Table 9, the reported coefficient is bracketed on both sides.

falls / episode

λ=0.03 (n=10)

GRU/E3B GRU/none GRU/NovelD

Gat/E3B Gat/none Gat/NovelD

15 10 5 0

130 120

episode length

Cell

MysteryPath penalty arm: the freeze and its rescue (median over seeds)

110 100 90 80

success rate

Table 12: MysteryPath penalty arm: falls per episode and terminal success (mean ± std over seeds). Without a bonus, the agent drives falls to zero, runs out the clock, and never reaches the goal. The bonus arms trade falls for task success, proving the freeze is a policy that stops paying the exploration cost, not one that forgot how to learn. Arch

Bonus

Falls / episode

Success

GRU GRU GRU

none E3B NovelD

0.0 ± 0.0 14.0 ± 0.7 6.1 ± 0.6

0.00 ± 0.00 0.22 ± 0.08 0.16 ± 0.09

GatedDeltaNet GatedDeltaNet GatedDeltaNet

none E3B NovelD

0.0 ± 0.0 7.0 ± 0.8 6.7 ± 0.6

0.00 ± 0.00 0.63 ± 0.17 0.66 ± 0.10

0.7 0.6 0.5 0.4 0.3 0.2 0.1 0.0 0.0

2.5

5.0

7.5

10.0

env steps (M)

12.5

15.0

17.5

20.0

Figure 6: The penalty-variant freeze on MysteryPath (median across seeds). Without a bonus, falls per episode drop to zero, episode length is pinned at Tmax =128, and the success rate remains at zero. The agent abandons the task to avoid penalties. Policy entropy does not collapse, indicating a sampling failure rather than premature convergence. The agent mixes within the safe region but never observes the sparse +1 reward. Both bonuses successfully break this freeze.

mo r

a mb

ted Ga

none

E3B

mo r Me

mb a Ma

Re tN

ted Ga

Re tN

ted

0.0

0.2

mo r

0.2

mb a

0.2

ted

0.4

0.6

mo r

0.6

mb a

0.6

0.8

S13 / sparse 7x7

1.0

0.8

mo r Me

a mb Ma

Re tN

mo r Me

ted Ga

Re tN

S13 / distractor

1.0

0.0

Re tN

0.0

0.2

Re tN

0.2

ted

0.4

0.6

0.8

final success

0.8

S13 / sparse 3x3

MPG / distractor

1.0

0.8

1.0

final success

MPG / aligned

1.0

MPG / sparse

1.0

NovelD

Figure 7: Per-seed tail-mean success for every cell in the suite. The bimodal nature of MemoryS13 necessitates the scalefree summary in Section . Seeds either land at the cue-blind 0.50 mark or hit the ceiling; a mean midway between the two misrepresents actual runs. Table 13: The first environment step where any evaluation episode reached the goal (MysteryPath penalty arm, per seed). “Never” indicates the goal was not reached during the 20M-step run. The no-bonus policy simply never acquires the data required to begin learning. Arch

Bonus

First success (env steps, per seed)

GRU GRU GRU

none E3B NovelD

never, never, never 2,774 409 409 3,481 337 9,376

GatedDeltaNet GatedDeltaNet GatedDeltaNet

none E3B NovelD

never, never, never 1,984 445 445 2,105 4,703 5,569

provides a more faithful picture. We count a seed as successful if its tail mean exceeds 0.6. The three failing cells learn on every seed (E3B) or most seeds (NovelD) once a bonus is introduced. The two successful cells mostly maintain their performance. This captures the equalization pattern without relying on the numerical scale. A caution on the raw scale. MemoryS13 compression is sensitive to the choice of scale (e.g., a logit transform yields an E3B dispersion ratio near 1.0). Including the memoryless control eliminates compression because the control stays flat while memory cells hit the ceiling. Thus, the equalization claim applies to the raw success-rate scale among memory architectures, supported by Table 18. Amplification on MysteryPath holds regardless of scale. Table 19 makes this dependence explicit on the standard-

Table 14: The delivered per-step intrinsic reward λ · b compared to the per-step penalty 1/Tmax , averaged over training. The logged bonus is the raw, pre-coefficient value; the delivered quantity is λ times that (λ = 0.03). The final column shows the ratio of this bonus to the penalty magnitude. Environment / variant

Bonus

raw b

λb

vs. penalty

MPG / sparse MPG / sparse MPG / penalty MPG / penalty

E3B NovelD E3B NovelD

0.689 0.067 0.678 0.075

0.0207 0.0020 0.0203 0.0023

2.6× 0.3× 2.6× 0.3×

S13 / sparse 3 × 3 S13 / sparse 3 × 3 S13 / penalty 3 × 3 S13 / penalty 3 × 3

E3B NovelD E3B NovelD

0.648 0.016 0.647 0.017

0.0194 0.0005 0.0194 0.0005

2.5× 0.1× 2.5× 0.1×

Tiny / sparse Tiny / sparse Tiny / dense Tiny / dense

E3B NovelD E3B NovelD

0.498 0.000 0.472 0.000

0.0149 0.0000 0.0142 0.0000

— — — —

In TinyReproduce, NovelD’s delivered bonus is numerically zero. Its episodic first-visit gate never triggers because the play-phase observation is a single constant view. Here, the null result for NovelD is structurally guaranteed, serving as an independent confirmation of redundancy.

Table 15: Two-way ANOVA (Architecture × Bonus) on per-seed tail means across the five memory architectures (n=10 per cell, df = 4, 1, 4, 90). Both gridworlds demonstrate a massive, statistically significant interaction under both bonuses. TinyReproduce shows no interaction, perfectly confirming the null effect. F Environment

Effect

(pparam )

[pperm ]

E3B

NovelD −49

MysteryPath (sparse)

Architecture Bonus Arch. × Bonus

271.4 (2.6×10 ) 1300.1 (2.8×10−55 ) 226.4 [0.0002]

274.6 (1.6×10−49 ) 1356.7 (4.6×10−56 ) 234.7 [0.0002]

MemoryS13 (3 × 3)

Architecture Bonus Arch. × Bonus

7.6 (2.4×10−5 ) 162.7 (7.0×10−22 ) 22.1 [0.00005]

17.9 (7.7×10−11 ) 137.3 (8.4×10−20 ) 8.0 [0.021]

Tiny (sparse)

Architecture Bonus Arch. × Bonus

2308.1 (9.4×10−90 ) 0.01 (0.93) 0.35 [0.61]

1414.2 (2.6×10−80 ) 2.6 (0.11) 1.7 [0.23]

Tiny (dense)

Architecture Bonus Arch. × Bonus

1984.0 (7.9×10−87 ) 0.42 (0.52) 0.73 [0.58]

2751.1 (3.7×10−93 ) 0.6 (0.43) 1.2 [0.29]

Permutation p-values are reported exclusively for the interaction term. The TinyReproduce architecture main effect is enormous, while both bonus terms are indistinguishable from zero: the cells perform differently, but the bonus does not affect them.

Table 16: Between-architecture variance of cell means, no bonus vs. bonus, with seed-level bootstrap 95% CIs on the ratio. The bonus increases dispersion on MysteryPath roughly fifty-fold, shrinks it on MemoryS13 by four-fold, and leaves it untouched on TinyReproduce. E3B

NovelD

Environment

Vnone

Ve3b

Ratio [95% CI]

Vnvld

Ratio [95% CI]

MysteryPath (sparse) MemoryS13 (3 × 3) TinyReproduce (sparse) TinyReproduce (dense)

0.0007 0.0300 0.2046 0.2070

0.0440 0.0080 0.2099 0.2086

63.2 [42.1, 101.6] 0.27 [0.06, 0.84] 1.03 [0.99, 1.06] 1.01 [0.98, 1.04]

0.0363 0.0057 0.2059 0.2037

52.1 [34.6, 83.8] 0.19 [0.06, 0.59] 1.01 [0.98, 1.04] 0.98 [0.95, 1.02]

Variance is calculated across the five memory architectures’ cell means (ddof=1). The TinyReproduce intervals rule out a dispersion shift of more than ±6%, confirming a precisely measured absence of an effect.

deviation scale. MysteryPath widens under both bonuses across sparse and distractor variants. MemoryS13’s compression is significant among the five memory cells (−0.075 and −0.090) but vanishes when the memoryless control is added (−0.003). The aligned variant acts as an internal control for amplification. The core amplification claim states a bonus widens the gap between memory architectures only when the reward is structurally sparse. The aligned variant tests this while holding the environment constant. Changing only the reward from sparse to dense-aligned causes amplification to vanish entirely (∆SEP plummets from +0.164 to +0.010). Conversely, the distractor variant (dense but structurally sparse) behaves like the sparse variant (+0.169). Reward structure, not the environment itself, dictates the pattern. Reward structure as a core factor, holding the environment constant. We run a comprehensive three-way factorial—Architecture × Bonus × Reward structure—within MysteryPath to isolate reward structure from environmental confounds.

On the aligned variant, E3B is actively harmful. On the aligned variant, E3B drops average success from 0.486 to 0.386 across all five memory architectures. When there is no misranking to correct (potentially dense reward), exploration pressure pulls the policy away from a well-shaped objective. NovelD, pushing only 0.3× the per-step penalty scale, increases average success slightly to 0.512. E3B’s larger magnitude (2.6×) aggressively disrupts the well-shaped dense objective. Sample efficiency: the bonus does more than raise the ceiling. Table 22 tracks the environment steps required to first sustain an absolute success threshold (mean of five consecutive evaluations). On MysteryPath, the bonus changes the outcome from never to reliably sustaining success. On MemoryS13, GatedDeltaNet accelerates from 12.6M steps to 0.7M (NovelD), an 18× speed-up. Mamba-2’s 0.48 probability of improvement under E3B masks the fact that it hits final performance a full order of magnitude faster. Equalization eliminates a search problem all cells struggle with. On TinyReproduce, the null pattern holds on the time axis as well.

Table 17: Probability of improvement under each bonus vs. no bonus, per cell (E3B / NovelD). Values near 1 mean the bonus helps on essentially every seed pairing; values near 0.5 indicate no effect. Cell

MysteryPath

MemoryS13 (3 × 3)

Tiny (sparse)

Tiny (dense)

GRU LSTM RetNet GatedDeltaNet Mamba-2

0.95 / 0.97 0.98 / 1.00 1.00 / 1.00 1.00 / 1.00 1.00 / 1.00

1.00 / 1.00 1.00 / 1.00 1.00 / 1.00 0.85 / 0.90 0.48 / 0.55

0.47 / 0.56 0.73 / 0.68 0.40 / 0.45 0.38 / 0.61 0.45 / 0.44

0.37 / 0.35 0.70 / 0.56 0.55 / 0.55 0.41 / 0.54 0.64 / 0.54

Table 18: MemoryS13 (3 × 3 sparse): number of seeds out of ten successfully learning the task (tail mean > 0.6). This summary is immune to monotonic rescaling of the success rate. Cell

none

E3B

NovelD

GRU LSTM RetNet GatedDeltaNet Mamba-2

0/10 0/10 0/10 8/10 9/10

10/10 10/10 10/10 10/10 7/10

8/10 10/10 8/10 10/10 10/10

The memoryless control as a falsification test. A policy lacking recurrent state cannot retain exploration findings. A coverage-based bonus should not help it. On MysteryPath sparse, E3B crushes the memoryless control from 0.062 to 0.002 (PoI = 0.00). NovelD yields 0.02. On MemoryS13, the bonus boosts the memoryless control to the cue-blind chance rate of 0.5, preventing collapse below chance but failing to help acquire the cue. MysteryPath serves as the definitive falsification test. Robust aggregation. Table 24 displays the interquartile mean (IQM) using a stratified bootstrap (Agarwal et al. 2021), resistant to bimodal outlier seeds. Amplification on MysteryPath and equalization on MemoryS13 hold up perfectly, with non-overlapping confidence intervals. TinyReproduce intervals overlap significantly, confirming the null. Raw per-seed data. Table 25 presents complete, sorted per-seed tail means. The bimodal split of MemoryS13 is evident: GRU runs without a bonus range from .48 to .52, while GRU runs with E3B stretch from .75 to 1.00.

Does the Bonus Change What Memory Encodes? A logical mechanistic assumption is that the episodic bonus works by upgrading the recurrent state: pushing exploration provides a richer training signal, making the task-relevant latent more decodable, leading to better behavior. This section tests that hypothesis. It fails. This negative mechanistic result contextualizes the positive behavioral results. Pre-registration. We established six predictions (P1–P6) prior to fitting probes. Table 28 grades the outcomes.

Protocol. For each cell, we replay a fixed set of 200 evaluation episodes on the final checkpoint, recording the recurrent state ht . We fit a logistic probe on ht to predict a task-relevant latent, tuning ℓ2 strength on a validation split. Data is split by episode (70/15/15) to prevent leakage. For MysteryPath, the latent is “is this adjacent, tested tile on-path?”. For MemoryS13, it is cue identity. Scope: 3 architectures × {none, E3B} × 3 (env, reward) slices, testing 2 seeds per cell. Three controls, one of which fails informatively. We ran a shuffled-label null, an observation-only probe ψ(ot ), and a randomly initialized cell. On MysteryPath, ψ(ot ) scores 0.58 because the environment visually flags tested tiles. The memory-specific value is ht relative to this baseline. On MemoryS13, an untrained cell decodes cue identity at 0.94–1.00 due to classic reservoir behavior, rendering P4 untestable. Result: the bonus does not improve encoding. The critical disconnect. On MysteryPath sparse, GatedDeltaNet’s success jumps from 0.17 to 0.62 with E3B (Table 25), but path decodability barely moves (+0.016). The bonus does not turn the recurrent state into a better encoder. The complementary disconnect on MemoryS13. Without a bonus, GRU and LSTM decode cue identity at 0.928 and 0.876 but fail the task on every seed (Table 18). Forming the memory is not the bottleneck; using it is. The penalty arm corroborates this: the frozen agent never reaches the goal (Table 13), proving the failure lies in sampling, not encoding. The bonus provides behavioral coverage, not representational quality. Limitations. Two seeds per cell yields directional estimates. The MysteryPath obs-only control inflates the baseline. The MemoryS13 probe is saturated. Linear probes establish only a lower bound on decodability. However, the central disconnect remains: massive behavioral shifts occur alongside near-zero representational ones.

Summary Tables Why we left out Transformers. We limited the lineup to architectures maintaining a fixed-size recurrent state updated online. A growing attention context fundamentally alters the training stack. Given attention’s copying advantage (Jelassi et al. 2024), Transformers would likely dominate TinyReproduce. Evaluating them fairly remains future work.

Table 19: Architecture separation index (SEP). ∆SEP compares the bonus arm against none, with a 95% CI. A positive value means the bonus widens the performance gap; a negative value means it compresses it. SEP(none)

SEP(e3b)

SEP(nvld)

∆SEP(e3b) 95% CI

0.024 0.196 0.016 0.155 0.116 0.104

0.188 0.206 0.184 0.080 0.095 0.014

0.170 0.245 0.167 0.068 0.106 0.010

+0.164 [+0.153, +0.175] +0.010 [−0.009, +0.030] +0.169 [+0.146, +0.178] −0.075 [−0.128, −0.013] −0.021 [−0.085, +0.059] −0.090 [−0.127, −0.035]

6 cells incl. Memoryless MPG / sparse 0.043 MPG / aligned 0.241 MPG / distractor 0.020 S13 / sparse 3 × 3 0.173 S13 / distractor 0.112 S13 / sparse 7 × 7 0.142

0.221 0.235 0.218 0.170 0.170 0.175

0.196 0.281 0.192 0.159 0.177 0.176

+0.178 [+0.170, +0.188] −0.007 [−0.024, +0.011] +0.198 [+0.180, +0.207] −0.003 [−0.049, +0.041] +0.058 [+0.016, +0.108] +0.033 [+0.003, +0.055]

Env / reward 5 memory cells MPG / sparse MPG / aligned MPG / distractor S13 / sparse 3 × 3 S13 / distractor S13 / sparse 7 × 7

On the MPG aligned row, the bonus stops widening the spread (+0.010, interval crosses zero). Amplification turns off exactly where the reward is no longer structurally sparse. MemoryS13 · sparseV3

0.9

obs_only random_init none e3b_idm

0.6 0.5 0.4

probe AUC

0.8 0.7

MysteryPath · aligned

1.0 0.9

0.9

0.8

0.7 0.6 0.5

GRU

LSTM

aN dDelt Gate

0.4

MysteryPath · sparse

1.0

probe AUC

1.0

0.7 0.6 0.5

GRU

dD Gate

e eltaN

LSTM

0.4

GRU

a dDelt

Gate

Net

LSTM

Figure 8: Probe AUC by architecture, grouped by training signal. Dashed lines mark obs-only and random-init controls. MemoryS13 random-init is saturated.

Additional Notes for the Careful Reader Table 20: Three-way ANOVA within MysteryPath: 5 architectures × 2 bonuses × 4 reward variants × 10 seeds. The significant three-way term confirms the architecture×bonus interaction is heavily influenced by reward structure. SS

ω2

Architecture (A) Bonus (B) Reward structure (C) A×B A×C B×C A×B×C

5.732 3.975 3.962 1.920 0.893 3.274 0.553

4 1 3 4 12 3 12

842.9 2338.3 776.8 282.4 43.8 641.9 27.1

0.274 0.190 0.189 0.091 0.042 0.156 0.025

residual

0.612

360

Effect

Reward structure drives as much variance as the bonus (0.189 vs. 0.190), and the bonus×reward term (0.156) heavily outweighs the architecture×bonus term (0.091). The reward given matters as much as the bonus itself.

Why does sparse TinyReproduce show a null result despite potential sparsity? The observation stream operates on a fixed schedule. Intrinsic and extrinsic returns rank policies identically, leaving the bonus with no power to reorder them (redundancy supersedes sparsity). Why do some architectures perform above chance on MemoryS13 without a bonus? GatedDeltaNet and Mamba-2 escape the cue-blind optimum in most seeds via entropy-driven exploration. The bimodal seed distribution (Fig. 7) suggests this relies on lucky early trajectories. The bonus removes this lottery for failing cells but does little for those already succeeding. Is the TinyReproduce failure for RetNet/Mamba-2 a tuning issue? The failure persists across tested learning rates (10−4 and 10−3 ) and mirrors documented copying gaps (Jelassi et al. 2024). The null bonus effect held across all configurations.

Table 21: Breaking down the architecture×bonus interaction within MysteryPath. The interaction is massive in the three structurally sparse variants, but plummets in the dense variant. Reward variant

Classification

F (A×B)

sparse penalty distractor aligned

struct. sparse struct. sparse struct. sparse struct. dense

226.4 249.9 76.4 5.2

partial ω 2 0.900 0.909 0.751 0.144

Dispersion ratio 63.2 undefined† 136.5 1.1

†

In the penalty variant, no-bonus dispersion is functionally zero due to the freeze, making the ratio undefined. The aligned interaction’s partial ω 2 of 0.144 is substantially lower than the 0.75–0.91 seen elsewhere.

Table 22: Environment steps (millions) to first sustain the threshold (median over successful seeds). (k/n) indicates successful seeds. Thresholds are set well above the no-bonus plateau: 0.30 (MysteryPath), 0.75 (MemoryS13), and 0.50 (TinyReproduce). Slice

Arch

none

E3B

NovelD

MPG sparse θ=0.30

GRU LSTM RetNet GatedDeltaNet Mamba-2

never (0/10) never (0/10) 19.4 (1/10) never (0/10) 17.6 (8/10)

16.8 (1/10) never (0/10) 4.7 (10/10) 5.8 (10/10) 11.6 (10/10)

15.6 (2/10) 14.2 (3/10) 5.7 (10/10) 4.4 (10/10) 10.1 (10/10)

S13 sparse θ=0.75

GRU LSTM RetNet GatedDeltaNet Mamba-2

never (0/10) never (0/10) never (0/10) 12.6 (8/10) 5.3 (9/10)

6.7 (10/10) 7.9 (10/10) 4.3 (10/10) 1.5 (10/10) 1.3 (10/10)

5.1 (9/10) 3.2 (10/10) 1.6 (10/10) 0.7 (10/10) 0.4 (10/10)

Tiny sparse θ=0.50

GRU LSTM RetNet GatedDeltaNet Mamba-2

2.2 (10/10) 1.5 (10/10) never 9.5 (2/10) never

2.1 (10/10) 1.4 (10/10) never 6.9 (1/10) never

2.0 (10/10) 1.5 (10/10) never 6.9 (3/10) never

Tiny dense θ=0.50

GRU LSTM RetNet GatedDeltaNet Mamba-2

1.8 (10/10) 1.2 (10/10) never 8.5 (1/10) never

1.9 (10/10) 1.2 (10/10) never 9.2 (3/10) never

1.9 (10/10) 1.4 (10/10) never 7.7 (2/10) never

Table 23: Memoryless control (mean ± std over n=10 seeds) and probability of improvement (PoI). On sparse MysteryPath, the bonus actively degrades the memoryless policy. Slice MPG / sparse MPG / penalty MPG / distractor S13 / sparse 3 × 3 Tiny / sparse Tiny / dense

none

E3B

PoI

NovelD

PoI

0.062 ± 0.010 0.000 ± 0.000 0.010 ± 0.022 0.352 ± 0.243 0.000 ± 0.000 0.000 ± 0.000

0.002 ± 0.003 0.001 ± 0.001 0.001 ± 0.001 0.498 ± 0.011 0.000 ± 0.001 0.000 ± 0.000

0.00 0.75 0.64 0.54 0.55 0.50

0.041 ± 0.008 0.014 ± 0.004 0.038 ± 0.007 0.503 ± 0.008 0.000 ± 0.000 0.000 ± 0.000

0.02 1.00 0.82 0.65 0.50 0.50

Table 24: Interquartile mean (IQM) across all five memory architectures (50 runs per entry) with 95% stratified-bootstrap CIs. All three patterns remain solid under this robust aggregate. Slice MPG / sparse MPG / aligned S13 / sparse 3 × 3 Tiny / sparse Tiny / dense

none

E3B

NovelD

0.154 [0.149, 0.160] 0.459 [0.441, 0.478] 0.546 [0.520, 0.581] 0.402 [0.382, 0.419] 0.411 [0.390, 0.428]

0.358 [0.345, 0.371] 0.354 [0.344, 0.367] 0.963 [0.941, 0.974] 0.397 [0.376, 0.421] 0.399 [0.375, 0.424]

0.336 [0.328, 0.344] 0.489 [0.475, 0.502] 0.953 [0.919, 0.969] 0.432 [0.403, 0.468] 0.421 [0.406, 0.440]

Table 25: Sorted per-seed tail-mean success (n=10). Arch

Bonus

Per-seed tail-mean success (sorted)

MPG / sparse GRU GRU GRU LSTM LSTM LSTM RetNet RetNet RetNet GatedDeltaNet GatedDeltaNet GatedDeltaNet Mamba-2 Mamba-2 Mamba-2 Memoryless Memoryless Memoryless

none e3b nvld none e3b nvld none e3b nvld none e3b nvld none e3b nvld none e3b nvld

.12, .12, .13, .13, .14, .14, .14, .15, .15, .16 .14, .17, .17, .18, .19, .19, .19, .19, .20, .21 .15, .17, .17, .19, .19, .19, .19, .19, .20, .21 .13, .13, .14, .14, .14, .14, .14, .15, .15, .15 .15, .15, .16, .17, .17, .17, .18, .18, .19, .21 .17, .17, .18, .18, .19, .20, .20, .20, .21, .22 .12, .13, .13, .15, .16, .16, .16, .17, .17, .23 .48, .49, .53, .55, .55, .57, .57, .60, .62, .65 .50, .51, .51, .51, .52, .54, .55, .55, .56, .60 .14, .14, .15, .16, .16, .17, .18, .18, .18, .19 .57, .59, .59, .61, .62, .62, .63, .64, .66, .71 .49, .53, .54, .57, .58, .61, .62, .63, .65, .66 .15, .18, .20, .20, .20, .21, .22, .22, .22, .23 .26, .28, .31, .35, .35, .36, .36, .36, .38, .41 .24, .29, .29, .30, .30, .31, .31, .32, .32, .33 .05, .05, .06, .06, .06, .06, .06, .07, .07, .08 .00, .00, .00, .00, .00, .00, .00, .00, .00, .01 .03, .03, .03, .04, .04, .04, .04, .04, .05, .05

S13 / sparse 3 × 3 GRU none GRU e3b GRU nvld LSTM none LSTM e3b LSTM nvld RetNet none RetNet e3b RetNet nvld GatedDeltaNet none GatedDeltaNet e3b GatedDeltaNet nvld Mamba-2 none Mamba-2 e3b Mamba-2 nvld Memoryless none Memoryless e3b Memoryless nvld

.48, .49, .49, .50, .50, .50, .51, .51, .51, .52 .75, .81, .87, .92, .95, .96, .98, .98, 1.00, 1.00 .52, .54, .74, .92, .94, .98, .98, .98, .98, 1.00 .48, .48, .49, .49, .50, .50, .51, .51, .52, .53 .95, .96, .96, .98, .98, .99, 1.00, 1.00, 1.00, 1.00 .69, .90, .95, .95, .98, .99, .99, 1.00, 1.00, 1.00 .44, .48, .49, .49, .49, .49, .50, .50, .50, .51 .68, .76, .91, .94, .94, .95, .98, .98, .99, 1.00 .53, .56, .62, .63, .73, .92, .94, .97, .98, .99 .52, .52, .62, .71, .75, .77, .77, .92, .99, .99 .88, .96, .97, .98, .98, .99, .99, 1.00, 1.00, 1.00 .92, .94, .99, .99, .99, .99, .99, 1.00, 1.00, 1.00 .55, .63, .85, .90, .92, .92, .93, .94, .96, .96 .38, .48, .51, .65, .79, .94, .94, .95, .97, .97 .80, .80, .88, .91, .91, .93, .94, .95, .96, .99 .00, .00, .00, .49, .50, .50, .50, .51, .51, .51 .48, .49, .49, .49, .49, .50, .50, .51, .51, .51 .49, .50, .50, .50, .50, .50, .51, .51, .51, .51

Table 26: Control check. The shuffled-label null passes. The other two controls fail informatively on one environment each. Control

MysteryPath

MemoryS13

Verdict

shuffled label obs-only ψ(ot ) random-init cell

0.48–0.51 0.58 0.55–0.60

≈0.50 0.53 0.94–1.00

pass MPG fails S13 fails

Of 36 shuffled-label fits, only three stray from 0.5 by more than 0.08; all are below chance, pointing to small-sample noise rather than leakage.

Table 27: Impact of E3B on decodability (∆AUC) with 95% CIs. No cell shows the expected increase; three show a significant decrease. Variant

Arch

∆AUC

95% CI

MPG / sparse MPG / sparse MPG / sparse

GRU LSTM GatedDeltaNet

−0.031 −0.051 +0.016

[−0.034, −0.028] [−0.062, −0.040] [−0.001, +0.033]

MPG / aligned MPG / aligned MPG / aligned

GRU LSTM GatedDeltaNet

+0.003 +0.001 −0.020

[−0.004, +0.009] [−0.009, +0.011] [−0.027, −0.014]

S13 / sparse S13 / sparse S13 / sparse

GRU LSTM GatedDeltaNet

+0.048 +0.086 +0.000

[−0.031, +0.126] [−0.001, +0.172] [+0.000, +0.001]

Table 28: Pre-registered predictions vs. actual outcomes. Two misses, two hits, one split, two untestable. ID

Prediction

Outcome

MPG/sparse: bonus increases path decodability Increase is larger for GDN than GRU/LSTM

Miss. Decreased for GRU/LSTM, flat for GDN. Hit on ordering only. GDN > GRU > LSTM, but no actual increase. Hit. All effects ≈0 or negative.

MPG/aligned: bonus does not increase decodability S13: bonus increases cue decodability

Obs-only control sits at chance

Probe AUC correlates with success

Not evaluable. Probe saturated by reservoir dynamics. Split. Hit on S13 (0.53); missed on MPG (0.58). Not trustworthy. Correlation is an artifact of between-environment differences.

F4: cue decodability vs retention distance 1.0

F3: does the bonus move behavior and representation together?

0.9

0.10

LSTM/Mem/spar

0.05

GRU/Mem/spar Gate/Mys/spar

0.00

GRU/Mys/alig LSTM/Mys/alig

Gate/Mem/spar

0.8

GRU/none GRU/e3b_idm GatedDeltaNet/none GatedDeltaNet/e3b_idm LSTM/none LSTM/e3b_idm

0.7 0.6 0.5 4

Gate/Mys/alig GRU/Mys/spar

0.05

probe AUC

probe AUC gain from bonus

0.15

6 8 steps since cue last seen

LSTM/Mys/spar

0.1

0.0

0.1 0.2 0.3 success gain from bonus

0.4

0.5

Figure 9: Success gain vs. decodability gain under E3B. The largest behavioral gains occur with near-zero decodability gain.

Table 29: Evaluated architectures by memory mechanism class. Architecture

Mechanism

Known characteristics

GRU LSTM RetNet GatedDeltaNet Mamba-2 Memoryless

gated recurrence gated recurrence retention (decay) gated linear attention selective SSM none (control)

robust; limited capacity robust; limited capacity high capacity; copying gap high capacity high capacity; copying gap lower bound

Figure 10: MemoryS13 probe AUC vs. steps since cue was visible. Decodability remains high during traverse for all cells. Retention is not the separator.

Does the memoryless decline under E3B directly support the theory? It aligns perfectly: E3B redirects the policy toward novel states, but without memory, the agent cannot convert this into return and loses its baseline unbiased-wandering return. The theory describes what a bonus can change, not the optimization dynamics of an incapable policy.

Compute and Reproducibility Runs operated as single-GPU jobs across a heterogeneous cluster. Code, per-seed tail means, evaluation curves, and analysis scripts will be released upon publication.

Formal Results and Proofs Encoders Need Not Exist in General Encoding is demanding even in expectation. The following construction shows that a Markovian reward over three states

Table 30: Measured compute. Median wall-clock time across finished runs; GPU-hours = median time × number of runs. The 1,800 runs match the released per-seed records. Arm

Budget

Runs

Median

MPG sparse / penalty / aligned MPG distractor S13 sparse 3×3 / 7×7 / penalty S13 distractor TinyReproduce dense / sparse

20M 20M 20M 20M 10M

540 180 540 180 360

13.6 h 11.9 h 8.5 h 7.4 h 3.9 h

Reported matrix

1,800

some j ≤ k − 1, the guess rewards at xk and xj co0 1 incide; but the returns of πk+1 , πk+1 pin the former to 0 1 1 − σ (k+1)λ , σ (k+1)λ while those of πj+1 , πj+1 pin the latter to 1 − σ (j+1)λ , σ (j+1)λ , and σ is strictly GPU-h increasing, a contradiction. 7,344 For any k + 1 > |U | the trace exhibits k distinct machine 2,142 states, so by the pigeonhole principle no finite RM encodes 4,590 the reward at unbounded horizon. If the maximum horizon is 1,332 H and the RM encodes the reward, the states x0 , . . . , xH−2 1,404 are pairwise distinct, so |U | ≥ H − 1. 16,812

Total project cost (including pilots and calibrations) was roughly 21,200 GPU-hours.

can require more machine states than any finite automaton has. Proposition 1. There is a POMDP M with |S| = 3, |O| = 3, |A| = 3 and a Markovian reward, such that (i) in unbounded horizon, no finite RM over observations matches its expected return for all observation-history policies; and (ii) under any horizon H, every RM over observations that does so has at least H − 1 states. Proof. Let M have states S = {s0 , s1 , sd }, actions A = {c, g0 , g1 }, and observations O = {o0 , o1 , o⊥ }. The start state is s0 or s1 with equal probability. Action c keeps the state fixed, while g0 and g1 move to the absorbing state sd . In state sz the observation equals oz with probability q and the other symbol with probability 1 − q, for a fixed 21 < q < 1, and sd always shows o⊥ . The reward of guess gi is 1 if the state was si and 0 otherwise, and all other rewards are 0. In plain terms, a hidden coin, noisy peeks, and a guess that ends the episode. By construction the reward is Markovian. For any policy whose first k − 1 steps choose action c, 1 k q Pr(s1 | o0 = · · · = ok−1 = o1 ) = 1 k 21 = σ(kλ), k q + 2 2 (1 − q) x

q e ′ where σ(x) := 1+e x and λ := ln 1−q > 0. Since σ (x) = σ(x)(1 − σ(x)) > 0, each additional matching peek makes the bettor strictly more confident, without bound in k. Suppose a POMDPRM T with RP OA = ⟨U, u0 , δu , δr ⟩ encodes M. Consider the two policies πk0 and πk1 that take c for the first k − 1 steps and then take g0 and g1 respectively, and consider the trace on which all observations of the first k − 1 steps equal o1 . Let x0 , x1 , x2 , . . . be the machine states along that trace, with x0 = u0 by definition. For k = 1 the expected returns of π10 and π11 are 1 − σ(λ) and σ(λ), so matching them forces δr x0 , L(o1 , g0 , o⊥ ) = 1 − σ(λ) and δr x0 , L(o1 , g1 , o⊥ ) = σ(λ). We claim that x0 , .. . , xk−1 are pairwise distinct with δr xk−1 , L(o1 , gi , o⊥ ) equal to 1 − σ(kλ) for i = 0 and σ(kλ) for i = 1, by induction on k. Suppose it holds up to k. First, δr xj , L(o1 , c, o1 ) = 0 for 0 ≤ j ≤ k − 1, as otherwise the expected returns of πj0 , πj1 would not match. Now xk = δu xk−1 , L(o1 , c, o1 ) . If xk = xj for

The Belief Filter Is a Perfect Encoder The impossibility above disappears when the observations leave only finitely many posteriors over the hidden pair. In that case an encoding machine exists, is computable, and is perfect. Proposition 2 (Belief filter). Let M be a POMDP with γ ∈ (0, 1) such that some MDPRM ⟨S, A, p, γ, µ, P ′ , L′ , RP ′ SA ⟩, with RP ′ SA = ⟨U ′ , u′0 , δu′ , δr′ ⟩, encodes M, and suppose the set of posteriors over Z := S × U ′ reachable at positive probability is finite. Then the belief filter over Z, whose reward on each transition is the average of the latent reward given the observable past, is an explicitly computable POMDPRM that encodes M and is perfect w.r.t. its labelling. Proof. Write zt := (st , ut ) for the pair of the hidden state and the latent machine state, where ut+1 = δu′ ut , L′ (st , at , st+1 ) . The MDPRM hypothesis makeszt a Markov chain and makes rt = δr′ ut , L′ (st , at , st+1 ) a fixed function of (zt , at , st+1 ) on every trajectory. The machine tracks the Bayes posterior over this pair. For an observable history h of positive probability, let bh (z) be the posterior probability of zt = z given h. This posterior does not depend on the policy that produced h, because the probability of any latent path together with Qh factors into environment terms times the policy terms j πj (aj | hj ), the policy terms depend on h alone, and they cancel between the numerator and the denominator of the conditional. By the same cancellation, the predicted probability of the next observation, Pr(ot+1 = o′ | ht , at ), is a fixed function N (bht , at , o′ ) of the current posterior, obtained by propagating bht through p and ω; and one step of Bayes updating carries bh to a posterior F (bh , a, o′ ) that again depends only on (bh , a, o′ ), obtained by propagating bh through p and the latent machine update, weighting by ω(o′ | s′ ), and renormalizing by N . Consequently every reachable posterior arises from a first-step posterior (the same formula with µ b of in place of b) by iterating F , and by hypothesis the set B reachable posteriors is finite. The machine is the filter itself. Choose P so that some injection code : O × A × O → 2P exists. The states are b and a sink ⊥ for updates of the initial ι, the posteriors in B, probability zero, which loops with reward 0; the transitions apply F ; and the reward on a transition is the posterior mean of the latent reward, δr b, L(o, a, o′ )

| s, a)ω(o′ | s′ ) δr′ u, L′ (s, a, s′ ) Proposition 3 (Encoding does not imply perfection; the = MysteryPath abstraction is structurally sparse). There is a N (b, a, o′ ) POMDP M (a one-cell abstraction of MysteryPath) and a with µ in place of b out of ι. Every table is computable in exact POMDPRM T encoding M whose RM has a single nonarithmetic by forward closure from the first-step posteriors, terminal state, reproduces the reward step by step, and is b is finite. not perfect w.r.t. its labelling; moreover no POMDPRM with terminating because B a single non-terminal state that encodes M is perfect. By The machine encodes. By induction on the update rule, Definition 3 of the main text, r is structurally sparse. on every history of positive probability the machine state equals the posterior, x = b , so its reward is r̃ = E r | t h t t t Proof. A hidden trap side z ∈ {L, R} is drawn uniformly. ht , at , ot+1 . Taking total expectations over the countably The states are (start, z) with observation oS , (fallen, z) with many triples (ht , at , ot+1 ) gives Eπ [r̃t ] = Eπ [rt ] for every t observation oF , done1 with observation oG , and done2 with and policy; all rewards are bounded by the largest entry of δr′ , observation o⊥ , and the actions are {aL , aR }. From either so both discounted sums converge absolutely and the returns start-type or fallen-type state with hidden z, action az leads agree. to (fallen, z) with reward 0, and action az̄ leads to done1 The machine is perfect. Given ht and a, the joint distriwith reward +1. done1 moves to done2 under any action, bution of (ot+1 , rt ) is obtained by propagating bht one step done2 is absorbing, and all rewards from the done states are through p, ω, and the latent reward table, so it is a fixed 0. function of (bht , a) = (xt , a). This is Eq. (3) of the main The machine T has one non-terminal state u, with P = text. {G}, L(o, a, o′ ) = {G} iff o′ = oG , δu ≡ u, δr (u, {G}) = 1, and δr (u, ∅) = 0. The environment gives +1 exactly on The Reference Kernel of the Greedy RM Policy transitions into done1 , whose arrival observation is oG , and oG occurs at no other time, so r̃t = 1[ot+1 = oG ] = rt on Remark 1 (The reference kernel, and a caution about coarse every trajectory and T encodes. machines). Definitions 4 and 5 of the main text apply to any Now let T ′ be any encoder with a single non-terminal POMDPRM T encoding M, perfect or P not. Fix the uniform π0 t state. Its RM state xt is constant, so perfection would force reference policy π0 and let d(o, u) = t≥0 γ Pr (ot = Pr(ot+1 , rt | ht , at ) to depend on ht only through ot . The o, xt = u) be the discounted occupancy of the pair (o, u). For histories h = (oS , aL , oF ) and h′ = (oS , aR , oF ) both pairs with d(o, u) > 0, let Prπ0 (o′ | o, u, a) be the weighted ′ have positive probability under the uniform policy and share average of the history conditionals Pr(ot+1 = o | ht , a) (ot , xt , at ) = (oF , u, aL ). But h reveals z = L, so aL falls over all times t and histories ht with (ot , xt ) = (o, u), each again with probability 1, while h′ reveals z = R, so aL weighted by γ t Prπ0 (ht )/d(o, u); for d(o, u) = 0 let the reaches the goal with probability 1. The conditional distrikernel be uniform. The history conditional does not depend butions differ, so no single-state machine is perfect. on the policy, by the cancellation argument of the belieffilter proof applied to the plain POMDP, so the kernel is well Classification of the MemoryS13 Cue Abstraction defined and depends only on the reference policy and γ. ′ The raw environment is not structurally dense. The cue maWhen T is perfect, Pr(ot+1 = o | ht , a) is constant across chine of Figure 2(b) of the main text encodes the raw environthe histories in each (o, u) cell (sum Eq. (3) of the main text ment as well, yet on the raw views it is not perfect, because over reward values), so the kernel equals that common value. inside a corridor whose cells share a view the next obserIt is then independent of the reference policy, the discounting, vation depends on the unobserved position, and by Definiand t, and coincides with the canonical Pr(ot+1 | ot , xt , at ). tion 3 one non-perfect encoder makes the reward structurally Since the full-support π0 reaches every pair that any policy sparse. That failure belongs to the dynamics, since the reward reaches, positive occupancy coincides with reachability. never distinguishes corridor positions. The abstraction below A caution accompanies the generality. A machine too removes exactly this view-aliasing and nothing else, and the coarse cannot register a misranking its state does not repdensity claim is about the abstraction. Here the two-history resent. On the one-state MysteryPath machine of Proposirecipe runs in reverse. Any machine that tries to forget the tion 3, both actions induce the same successor distribution cue and still match the returns of policies that differ only in from every pair, so every ϕ-greedy policy ties everywhere the final pick is caught, since matching pins its remaining and r comes out potentially dense w.r.t. it, even though this discounted reward at the shared state to two different values reward undervalues exactly the probing actions. Potential at once. density w.r.t. a non-perfect encoder therefore certifies nothing, and the classification only reads it where the reward is Lemma 1 (Density certificate for the cue abstraction). Let structurally dense, where every encoder is perfect and the Mcue be the cue abstraction of MiniGrid-MemoryS13. A kernel is canonical. hidden cue c ∈ {A, B} is uniform; the locations are start B (oS ), cue room (oA C or oC , revealing c), junction (oJ ), and Classification of the MysteryPath Abstraction end (oE , then absorbing o⊥ ). At the start, peek moves to the cue room and every other action to the junction; every action The recipe from the main text asks for one machine that forgets and still encodes. The one-state goal machine is that leaves the cue room for the junction; at the junction picki moves to the end with reward 1[i = c] while other actions witness, and the two histories “went left, fell” and “went self-loop with reward 0; all other rewards are 0. Then every right, fell” show it is not perfect. P

(s,u)∈Z

s′ ∈S b(s, u) p(s

′

POMDPRM that encodes Mcue is perfect w.r.t. its labelling, so the abstraction’s reward is structurally dense. The threestate cue machine of Figure 2(b) of the main text is such an encoder, and it does not reproduce the reward step by step. Proof. Fix any encoder T . For a positive-probability history h ending at the junction, let κ(h) ∈ {A, B, ∅} record B whether h contains oA C , contains oC , or contains neither, and let x(h) be the machine state after reading the labels of h. We first show that x(h) determines κ(h). After a pick the future is deterministic, so the machine’s discounted reward from the pick onward is a function of the state at the pick and of which pick was played; write Gi (x) for this quantity when picki is played from state x, and Ψ(x) := GA (x) − GB (x). Compare the two deterministic policies that produce h along its prefix, act identically at every other history, and at h play pickA and pickB respectively. Away from h they generate identical trajectories and label streams, so both return differences are supported on the event that h occurs. On that event the environment returns differ by γ |h| Pr(h) Pr(c=A | h) − Pr(c=B | h) while the machine returns differ by γ |h| Pr(h) Ψ(x(h)), the shared prefix cancelling. Encoding equates the two returns for both policies, so Ψ x(h) = Pr(c=A | h) − Pr(c=B | h), which equals 1, −1, or 0 according as κ(h) is A, B, or ∅. Since Ψ is a function of the state alone, two junction histories with different classes cannot share a machine state. Perfection follows cell by cell. In a cell {ot = o, xt = u} with o = oS the only history is the empty one; with o = oX C every history has revealed c = X; with o = oJ all histories share κ by the previous paragraph, and given κ the pick reward is Bernoulli with mean Pr(c = i | κ) while everything else is deterministic; with o ∈ {oE , o⊥ } the process is deterministic with reward 0. In every case the conditional distribution of (ot+1 , rt ) is constant across the histories in the cell, which is Eq. (3) of the main text. Finally, the cue machine encodes Mcue , since its reward on every transition is the average environment reward given the history and the tower property gives equal expected returns for every policy; it does not reproduce the reward step by step, since from its no-cue state a pick is rewarded a fixed 21 while the environment gives 0 or 1. Computation (potential sparsity of the cue abstraction). Take the cue machine, with rewards 1 and 0 for matching and mismatching picks from uA , uB and 21 for either pick from u0 . At (oS , u0 ) all one-step machine rewards are 0, so the greedy policy mixes uniformly over the four actions, peeking with probability 41 and reaching the junction cueblind with probability 43 ; at (oJ , u0 ) it picks uniformly; at (oJ , uX ) it plays pickX ; at the cue room all actions give 0 and lead to the junction. Hence J(π) = 34 · γ · 12 + 14 · γ 2 = 38 γ + 41 γ 2 . ⋆

With ϕ = V ⋆ as in the proof of Theorem 1, J(π V ) = J ⋆ = γ 2 for γ > 12 , since peek, go, pick correctly then beats

guessing immediately, worth γ · 21 , and ⋆

J(π V ) − J(π) = 38 γ (2γ − 1) > 0, so the abstraction’s reward is potentially sparse w.r.t. the cue machine.

Classification of the TinyReproduce Abstraction TinyReproduce invites a shortcut. A mistake ends the episode, so one might hope a machine could simply reward surviving play steps and forget the tokens. The shortcut is not available, because episode end is a consequence of correctness, not an input the machine can read. The labelling function sees only (ot , at , ot+1 ), the play observation is one constant view, and the final step shows that same view whether the token was right or wrong. Two dictations that agree on the tokens queried so far but disagree on the current target give, under the same played token, identical (o, a, o′ ) and hence identical labels with different rewards. The only way to reward a token correctly is to already know it, and knowing every token at its query means carrying the dictated sequence through the play phase, as the sequence machine of Figure 2(c) of the main text does. The lemma shows every encoder is forced into this shape. Lemma 2 (Density certificate for the dictation abstraction). Consider the dictation abstraction of TinyReproduce matching the implementation. A sequence s ∈ Σk (k ≥ 2) drawn uniformly is shown token by token at times 0, . . . , k−1 (the observation at time j is sj , and watch-phase actions do not affect the state), then queried in reverse. The observation at every later step is one constant oplay ; an incorrect token moves the process to an absorbing state, completion does too, and the absorbing state also shows oplay , so no observation distinguishes a right token, a wrong token, or the end of the episode. The dense variant gives +1/k on each correct token; the sparse variant gives τ /k on the transition into the absorbing state, where τ is the number of correct tokens. Then, in the dense variant, and in the sparse variant whenever γ > (k − 1)/k, every POMDPRM that encodes M resolves the dictated sequence, in that its state at the end of the watch phase determines s, and is perfect w.r.t. its labelling. Hence the abstraction’s reward is structurally dense in both variants. Proof. Since the play and absorbing observations coincide, every label from time k on is ℓa = L(oplay , a, oplay ), a function of the action alone; and since those observations carry no information, a deterministic policy’s actions from time k on form a fixed word w ∈ Σω determined by the dictation it watched. Conversely, every map s 7→ w(s), combined with any watch behavior α, is a deterministic policy, and every dictation has positive probability. Fix an encoder P T . For a machine state ξ and a word w, let G(ξ, w) = j≥0 γ j δr (ξj , ℓwj ) with ξ0 = ξ and ξj+1 = δu (ξj , ℓwj ), the machine’s discounted reward from time k on, and let E(s, w) be the environment’s. Writing ρ(s, w) for the number of initial positions at which w matches P the queried reversal of s, the dense variant gives E = k1 j<ρ γ j , and the sparse variant gives E = γ ρ ρ/k on failure (ρ < k) and γ k−1

on completion. In both variants E is strictly increasing in ρ for fixed s, in the sparse variant exactly when γ > (k − 1)/k, the same monotonicity as Proposition 4. Call the full-success value F ; every partial run is worth strictly less than F . Step 1 (pinning). Fix a watch behavior α and let x(s) be the machine state at time k under dictation s, a deterministic function of s. Applying Definition 2 of the main text to the policy (α, w(·)) and to the same policy with the word changed at a single dictation, then subtracting, gives G x(s), w − G x(s), w′ = E(s, w) − E(s, w′ ) (⋆) for all s, w, and w′ . Suppose x(s) = x(s′′ ) with s ̸= s′′ . By (⋆) the function w 7→ E(s, w) − E(s′′ , w) is constant. Evaluating it at the all-correct words ws and ws′′ and subtracting gives E(s′′ , ws ) + E(s, ws′′ ) = 2F . But playing the correct word for one dictation under the other fails at their first disagreement, so both terms are strictly below F , a contradiction. Hence x(·) is one-to-one for every watch behavior. Step 2 (perfection). The same subtraction applied to continuations pins every later state. For a machine state ξ reached at a play time by some (dictation, action-prefix) pair, (⋆) gives that any two pairs reaching ξ have tail-reward functions differing by a constant. A dead pair’s tail is identically 0 while an alive pair’s tail takes at least two values (all-correct earns the full remainder, wrong-now earns 0 or the current partial amount), so dead and alive pairs never share a state. Now take two alive pairs at positions i and i′′ . In the sparse variant, evaluating the constant difference at “wrong now” gives (i − i′′ )/k and at “correct once, then wrong” gives γ (i+1 − i′′ −1)/k, and equating the two forces i = i′′ . In the dense variant, “wrong now” earns 0 for both pairs, so the constant is 0 and the outright; evaluating at “all P tails are equalP correct” gives k1 j<k−i γ j = k1 j<k−i′′ γ j , which again forces i = i′′ . With equal positions the constant is 0 in both variants, so the tail-reward functions are identical, and this forces identical remaining targets, since playing the correct word of one pair under the other would otherwise make the two tails differ. Every reachable play-phase cell (oplay , ξ, a) therefore contains pairs sharing aliveness, position, and remaining targets, and the distribution of (ot+1 , rt ) on it is fixed, with next observation oplay and the deterministic reward the variant assigns. Watch-phase cells are constant as well, since the tokens of a uniform s are independent and uniform. Every cell satisfies Eq. (3) of the main text, so the machine is perfect; since T was arbitrary, the reward is structurally dense. Remark 2 (Greedy behavior and the gate order). W.r.t. the sequence machine (states are the remaining targets and the position), the dense variant is potentially dense. The one-step reward is k1 for the correct token and 0 otherwise at every position, so the greedy RM policy is optimal and Theorem 1 predicts the null outcome directly. The sparse variant is potentially sparse. At position i ≥ 1 the one-step reward is i/k for a wrong token and 0 for the correct one, so the greedy policy fails on purpose, and ϕ = V ⋆ repairs it. Dense and potentially sparse would alone predict a helpful bonus; the observed null is given by Proposition 4, whose gate is read first.

Bonus Redundancy on the Scheduled Stream Proposition 4 (Bonus redundancy). In the dictation abstraction of TinyReproduce, let bt = gt (o0 , . . . , ot ) ≥ 0 be any per-step intrinsic bonus that is a function of the observation prefix. In the dense variant, and in the sparse variant whenever γ > (k − 1)/k, for every λ ≥ 0 the optimal policy sets of r + λb and of r coincide, and all optimal policies of r have identical intrinsic return. Proof. Fix the dictated sequence s and a policy, and let τ be the (random) number of correct tokens. The within-episode observation stream is a deterministic function of (s, τ ), since dictation is scheduled, the reproduction observation is the constant oplay , and the episode ends at the first error or at completion. Moreover, for the same s, the stream under τ is an exact prefix of the stream under any τ ′ > τ , because the two runs coincide through the step at which the token at position τ is played and the shorter run simply ends. Since each bt is a nonnegative function of the prefix o0:t , the cumulative discounted bonus under τ ′ equals that under τ plus nonnegative terms, so the intrinsic return is nondecreasing in τ for each fixed s. The extrinsic return is strictly increasing in τ for each fixed s. In the dense variant each additional correct token adds a positive discounted term. In the sparse variant the terminal reward is γ t(τ ) τ /k with t(τ ) increasing by one per additional token, and γ t(τ )+1 (τ +1)/k > γ t(τ ) τ /k for all τ < k exactly when γ(τ + 1) > τ , which holds for all τ ≤ k − 1 iff γ > (k − 1)/k. Now compare any two policies. A policy that fails to achieve τ = k with positive probability is, on that event, strictly worse extrinsically and weakly worse intrinsically than the policy that corrects the corresponding tokens and agrees elsewhere. So for every λ ≥ 0 the optimal policies of r + λb and of r coincide, and all optimal policies of r have identical intrinsic return. Remark. The hypothesis bt = gt (o0:t ) covers E3B exactly, since its features and covariance are computed from the observations received so far. NovelD scores the arrival observation ot+1 , so the comparison acquires a single boundary term at the divergence step; the conclusion then holds up to λ times one first-visit bonus term, consistent with the at-most-±0.08 effects observed. The statement concerns the objective, not optimization dynamics, as does Theorem 1. With k = 10, the sparse-variant hypothesis requires γ > 0.9; the experimental discount γ = 0.99 (Table 8) satisfies it, so the proposition covers the runs reported in Table 3 of the main text.

Proof of Theorem 1 For a POMDP M = ⟨S, A, O, p, ω, r, γ, µ⟩, if r is structurally dense, POMDPRM T = ⟨S, A, O, p, ω, γ, µ, P, L, RP OA ⟩ encodes M (hence is perfect, by Definition 3), and r is potentially dense w.r.t. T , then the greedy RM policy over T is optimal for M among all observation-history policies.

Proof. Structural density makes T perfect, so by Remark 1 the kernel of Definition 4 equals the canonical P̄ (o′ | o, u, a) := Pr(ot+1 =o′ | ot =o, xt =u, at =a), which does not depend on the policy or on t on reachable pairs. Since xt+1 is a deterministic function of (xt , ot , at , ot+1 ), the pair process is a finite MDP Y on Y = O × U with reward R̄(y, a, y ′ ) := δr (u, σ), discount γ, and initial distribution induced by (µ, ω, u0 ). Let V ⋆ , Q⋆ , J ⋆ be its optimal value function, action-value function, and optimal return, which exist and satisfy the Bellman optimality equations because Y is finite and γ < 1. First, supπ J(π) = J ⋆ . The machine state is a deterministic function of the observation history, so every observationhistory policy induces P a policy for Y with the same machine return Ṽ (π) := Eπ [ t γ t r̃t ], and conversely; and in a finite discounted MDP, history-dependent policies do not outperform stationary ones, so supπ Ṽ (π) = J ⋆ . By Definition 2 of the main text, Ṽ (π) = J(π) for every π, and the claim follows. No step-by-step equality between r̃t and rt is used or available, since encoding is an equality of expected returns, and expected returns are all that optimal behavior depends on. Second, take ϕ := V ⋆ , a function on U × O as Definition 5 requires. At every pair (y, a), X P̄ (o′ | y, a) R̄(y, a, y ′ ) + γV ⋆ (y ′ ) − V ⋆ (y) o′

= Q⋆ (y, a) − V ⋆ (y), ⋆

so π V is uniform over arg maxa Q⋆ (y, ·), and any randomization over the optimal-action set of a finite MDP is optimal, ⋆ hence J(π V ) = J ⋆ . Third, suppose the greedy RM policy π had J(π) < J ⋆ . ⋆ Then J(π) < J(π V ), and ϕ = V ⋆ would witness potential sparsity w.r.t. T , contradicting the hypothesis. Hence J(π) = J ⋆ = supπ′ J(π ′ ), and the greedy RM policy is optimal for M. What happened. Perfection collapses the POMDP to a finite MDP over the pairs (observation, machine state). In that MDP, shaping with the optimal value function converts the one-step reward into the optimal advantage, so myopic greed becomes optimal. A potentially dense reward is one for which no such correction can help, which is only possible when myopic greed was optimal already.

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

Analyze & explore related research in Conceptio

Related documents