# On the Convergence of Bounded Agents

arXiv: https://arxiv.org/abs/2307.11044 · HTML: https://mlsanity.com/paper/2307.11044/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 58 references that are in the map.
- First posted on arXiv 20 Jul 2023.

## Builds on (most cited first, 14 of 14)

- [Mastering Atari, Go, Chess and Shogi by Planning with a Learned Model](https://mlsanity.com/paper/1911.08265/) (2019)
- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulator](https://mlsanity.com/paper/1801.05039/) (2018)
- [Reward Machines: Exploiting Reward Function Structure in Reinforcement Learning](https://mlsanity.com/paper/2010.03950/) (2020)
- [Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraints](https://mlsanity.com/paper/2101.02195/) (2021)
- [Reinforcement Learning, Bit by Bit](https://mlsanity.com/paper/2103.04047/) (2021)
- [Simple Agent, Complex Environment: Efficient Reinforcement Learning with Agent States](https://mlsanity.com/paper/2102.05261/) (2021)
- [Settling the Reward Hypothesis](https://mlsanity.com/paper/2212.10420/) (2022)
- [The Sample-Complexity of General Reinforcement Learning](https://mlsanity.com/paper/1308.4828/) (2013)
- [Nonparametric General Reinforcement Learning](https://mlsanity.com/paper/1611.08944/) (2016)
- [A Strongly Asymptotically Optimal Agent in General Environments](https://mlsanity.com/paper/1903.01021/) (2019)
- [Thompson Sampling is Asymptotically Optimal in General Environments](https://mlsanity.com/paper/1602.07905/) (2016)
- [Abstractions of General Reinforcement Learning](https://mlsanity.com/paper/2112.13404/) (2021)
- [Performance Guarantees for Homomorphisms Beyond Markov Decision Processes](https://mlsanity.com/paper/1811.03895/) (2018)

## Built on by (most cited first, 7 of 7)

- [Three Dogmas of Reinforcement Learning](https://mlsanity.com/paper/2407.10583/) (2024)
- [Plasticity as the Mirror of Empowerment](https://mlsanity.com/paper/2505.10361/) (2025)
- [Modeling Others' Minds as Code](https://mlsanity.com/paper/2510.01272/) (2025)
- [On the Interplay Between Sparsity and Training in Deep Reinforcement Learning](https://mlsanity.com/paper/2501.16729/) (2025)
- [Meta-Gradient Search Control: A Method for Improving the Efficiency of Dyna-style Planning](https://mlsanity.com/paper/2406.19561/) (2024)
- [Forgetting is Everywhere](https://mlsanity.com/paper/2511.04666/) (2025)
- [Artifacts as Memory Beyond the Agent Boundary](https://mlsanity.com/paper/2604.08756/) (2026)

## Abstract (arXiv)

When has an agent converged? Standard models of the reinforcement learning problem give rise to a straightforward definition of convergence: An agent converges when its behavior or performance in each environment state stops changing. However, as we shift the focus of our learning problem from the environment's state to the agent's state, the concept of an agent's convergence becomes significantly less clear. In this paper, we propose two complementary accounts of agent convergence in a framing of the reinforcement learning problem that centers around bounded agents. The first view says that a bounded agent has converged when the minimal number of states needed to describe the agent's future behavior cannot decrease. The second view says that a bounded agent has converged just when the agent's performance only changes if the agent's internal state changes. We establish basic properties of these two definitions, show that they accommodate typical views of convergence in standard settings, and prove several facts about their nature and relationship. We take these perspectives, definitions, and analysis to bring clarity to a central idea of the field.