# A Formal Solution to the Grain of Truth Problem

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Sep 2016.

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

- [Scalable agent alignment via reward modeling: a research direction](https://mlsanity.com/paper/1811.07871/) (2018)
- [QKSA: Quantum Knowledge Seeking Agent](https://mlsanity.com/paper/2107.01429/) (2021)
- [Limit-Computable Grains of Truth for Arbitrary Computable Extensive-Form (Un)Known Games](https://mlsanity.com/paper/2508.16245/) (2025)
- [Formalizing Embeddedness Failures in Universal Artificial Intelligence](https://mlsanity.com/paper/2505.17882/) (2025)
- [A Model-Free Universal AI](https://mlsanity.com/paper/2602.23242/) (2026)
- [On the Computational Tractability of Robust Bandits](https://mlsanity.com/paper/2610.08740/) (2026)

## Abstract (arXiv)

A Bayesian agent acting in a multi-agent environment learns to predict the other agents' policies if its prior assigns positive probability to them (in other words, its prior contains a grain of truth). Finding a reasonably large class of policies that contains the Bayes-optimal policies with respect to this class is known as the grain of truth problem. Only small classes are known to have a grain of truth and the literature contains several related impossibility results. In this paper we present a formal and general solution to the full grain of truth problem: we construct a class of policies that contains all computable policies as well as Bayes-optimal policies for every lower semicomputable prior over the class. When the environment is unknown, Bayes-optimal agents may fail to act optimally even asymptotically. However, agents based on Thompson sampling converge to play ε-Nash equilibria in arbitrary unknown computable multi-agent environments. While these results are purely theoretical, we show that they can be computationally approximated arbitrarily closely.