# Simple Agent, Complex Environment: Efficient Reinforcement Learning with Agent States

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

## Key facts

- Cited by 43 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 53 references that are in the map.
- First posted on arXiv 10 Feb 2021.

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

- [Mastering Atari, Go, Chess and Shogi by Planning with a Learned Model](https://mlsanity.com/paper/1911.08265/) (2019)
- [Provably Efficient Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/1907.05388/) (2019)
- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [Maximum a Posteriori Policy Optimisation](https://mlsanity.com/paper/1806.06920/) (2018)
- [Contextual Decision Processes with Low Bellman Rank are PAC-Learnable](https://mlsanity.com/paper/1610.09512/) (2016)
- [(More) Efficient Reinforcement Learning via Posterior Sampling](https://mlsanity.com/paper/1306.0940/) (2013)
- [FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPs](https://mlsanity.com/paper/2006.10814/) (2020)
- [Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes](https://mlsanity.com/paper/2012.08507/) (2020)
- [Learning Near Optimal Policies with Low Inherent Bellman Error](https://mlsanity.com/paper/2003.00153/) (2020)
- [Deep Exploration via Randomized Value Functions](https://mlsanity.com/paper/1703.07608/) (2017)
- [Near-Optimal Representation Learning for Hierarchical Reinforcement Learning](https://mlsanity.com/paper/1810.01257/) (2018)
- [Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizon](https://mlsanity.com/paper/2009.13503/) (2020)
- [V-MPO: On-Policy Maximum a Posteriori Policy Optimization for Discrete and Continuous Control](https://mlsanity.com/paper/1909.12238/) (2019)
- [Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processes](https://mlsanity.com/paper/1910.07072/) (2019)
- [Approximate information state for approximate planning and reinforcement learning in partially observed systems](https://mlsanity.com/paper/2010.08843/) (2020)
- [Learning Unknown Markov Decision Processes: A Thompson Sampling Approach](https://mlsanity.com/paper/1709.04570/) (2017)
- [Learning and Planning in Average-Reward Markov Decision Processes](https://mlsanity.com/paper/2006.16318/) (2020)
- [Near Optimality of Finite Memory Feedback Policies in Partially Observed Markov Decision Processes](https://mlsanity.com/paper/2010.07452/) (2020)
- [Queue-Learning: A Reinforcement Learning Approach for Providing Quality of Service](https://mlsanity.com/paper/2101.04627/) (2021)

## Built on by (most cited first, 30 of 43)

- [A Definition of Continual Reinforcement Learning](https://mlsanity.com/paper/2307.11046/) (2023)
- [Fine-Tuning Language Models with Advantage-Induced Policy Alignment](https://mlsanity.com/paper/2306.02231/) (2023)
- [Continual Learning as Computationally Constrained Reinforcement Learning](https://mlsanity.com/paper/2307.04345/) (2023)
- [Settling the Reward Hypothesis](https://mlsanity.com/paper/2212.10420/) (2022)
- [Toward Efficient Exploration by Large Language Model Agents](https://mlsanity.com/paper/2504.20997/) (2025)
- [Rethinking the Foundations for Continual Reinforcement Learning](https://mlsanity.com/paper/2504.08161/) (2025)
- [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)
- [Reinforcement Learning in Non-Markovian Environments](https://mlsanity.com/paper/2211.01595/) (2022)
- [BOFormer: Learning to Solve Multi-Objective Bayesian Optimization via Non-Markovian RL](https://mlsanity.com/paper/2505.21974/) (2025)
- [On Convergence of Average-Reward Q-Learning in Weakly Communicating Markov Decision Processes](https://mlsanity.com/paper/2408.16262/) (2024)
- [Agent-state based policies in POMDPs: Beyond belief-state MDPs](https://mlsanity.com/paper/2409.15703/) (2024)
- [On the Convergence of Bounded Agents](https://mlsanity.com/paper/2307.11044/) (2023)
- [Q-Learning for Stochastic Control under General Information Structures and Non-Markovian Environments](https://mlsanity.com/paper/2311.00123/) (2023)
- [Mitigating Partial Observability in Sequential Decision Processes via the Lambda Discrepancy](https://mlsanity.com/paper/2407.07333/) (2024)
- [Modeling Others' Minds as Code](https://mlsanity.com/paper/2510.01272/) (2025)
- [On Rate-Distortion Theory in Capacity-Limited Cognition & Reinforcement Learning](https://mlsanity.com/paper/2210.16877/) (2022)
- [Periodic agent-state based Q-learning for POMDPs](https://mlsanity.com/paper/2407.06121/) (2024)
- [A Theoretical Justification for Asymmetric Actor-Critic Algorithms](https://mlsanity.com/paper/2501.19116/) (2025)
- [Approximate information state based convergence analysis of recurrent Q-learning](https://mlsanity.com/paper/2306.05991/) (2023)
- [The Need for a Big World Simulator: A Scientific Challenge for Continual Learning](https://mlsanity.com/paper/2408.02930/) (2024)
- [Planning to the Information Horizon of BAMDPs via Epistemic State Abstraction](https://mlsanity.com/paper/2210.16872/) (2022)
- [Posterior Sampling for Continuing Environments](https://mlsanity.com/paper/2211.15931/) (2022)
- [Bayesian Reinforcement Learning with Limited Cognitive Load](https://mlsanity.com/paper/2305.03263/) (2023)
- [DARA: Few-shot Budget Allocation in Online Advertising via In-Context Decision Making with RL-Finetuned LLMs](https://mlsanity.com/paper/2601.14711/) (2026)
- [Conditions on Preference Relations that Guarantee the Existence of Optimal Policies](https://mlsanity.com/paper/2311.01990/) (2023)
- [On the Interplay Between Sparsity and Training in Deep Reinforcement Learning](https://mlsanity.com/paper/2501.16729/) (2025)
- [Beyond Sliding Windows: Learning to Manage Memory in Non-Markovian Environments](https://mlsanity.com/paper/2512.19154/) (2025)
- [Exploring Incremental Unlearning: Techniques, Challenges, and Future Directions](https://mlsanity.com/paper/2502.16708/) (2025)
- [Memory Allocation in Resource-Constrained Reinforcement Learning](https://mlsanity.com/paper/2506.17263/) (2025)

## Abstract (arXiv)

We design a simple reinforcement learning (RL) agent that implements an optimistic version of Q-learning and establish through regret analysis that this agent can operate with some level of competence in any environment. While we leverage concepts from the literature on provably efficient RL, we consider a general agent-environment interface and provide a novel agent design and analysis. This level of generality positions our results to inform the design of future agents for operation in complex real environments. We establish that, as time progresses, our agent performs competitively relative to policies that require longer times to evaluate. The time it takes to approach asymptotic performance is polynomial in the complexity of the agent's state representation and the time required to evaluate the best policy that the agent can represent. Notably, there is no dependence on the complexity of the environment. The ultimate per-period performance loss of the agent is bounded by a constant multiple of a measure of distortion introduced by the agent's state representation. This work is the first to establish that an algorithm approaches this asymptotic condition within a tractable time frame.