# Nonparametric General Reinforcement Learning

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Nov 2016.

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

- [A Definition of Continual Reinforcement Learning](https://mlsanity.com/paper/2307.11046/) (2023)
- [Settling the Reward Hypothesis](https://mlsanity.com/paper/2212.10420/) (2022)
- [Three Dogmas of Reinforcement Learning](https://mlsanity.com/paper/2407.10583/) (2024)
- [Illusory Attacks: Information-Theoretic Detectability Matters in Adversarial Attacks](https://mlsanity.com/paper/2207.10170/) (2022)
- [BOFormer: Learning to Solve Multi-Objective Bayesian Optimization via Non-Markovian RL](https://mlsanity.com/paper/2505.21974/) (2025)
- [On the Convergence of Bounded Agents](https://mlsanity.com/paper/2307.11044/) (2023)
- [Modeling Others' Minds as Code](https://mlsanity.com/paper/2510.01272/) (2025)
- [Non-Markovian Reinforcement Learning using Fractional Dynamics](https://mlsanity.com/paper/2107.13790/) (2021)
- [Self-Improvement as Coherence Optimization: A Theoretical Account](https://mlsanity.com/paper/2601.13566/) (2026)
- [A Model-Free Universal AI](https://mlsanity.com/paper/2602.23242/) (2026)

## Abstract (arXiv)

Reinforcement learning (RL) problems are often phrased in terms of Markov decision processes (MDPs). In this thesis we go beyond MDPs and consider RL in environments that are non-Markovian, non-ergodic and only partially observable. Our focus is not on practical algorithms, but rather on the fundamental underlying problems: How do we balance exploration and exploitation? How do we explore optimally? When is an agent optimal? We follow the nonparametric realizable paradigm. We establish negative results on Bayesian RL agents, in particular AIXI. We show that unlucky or adversarial choices of the prior cause the agent to misbehave drastically. Therefore Legg-Hutter intelligence and balanced Pareto optimality, which depend crucially on the choice of the prior, are entirely subjective. Moreover, in the class of all computable environments every policy is Pareto optimal. This undermines all existing optimality properties for AIXI. However, there are Bayesian approaches to general RL that satisfy objective optimality guarantees: We prove that Thompson sampling is asymptotically optimal in stochastic environments in the sense that its value converges to the value of the optimal policy. We connect asymptotic optimality to regret given a recoverability assumption on the environment that allows the agent to recover from mistakes. Hence Thompson sampling achieves sublinear regret in these environments. Our results culminate in a formal solution to the grain of truth problem: A Bayesian agent acting in a multi-agent environment learns to predict the other agents' policies if its prior assigns positive probability to them (the prior contains a grain of truth). We construct a large but limit computable class containing a grain of truth and show that agents based on Thompson sampling over this class converge to play Nash equilibria in arbitrary unknown computable multi-agent environments.