# Limit-Computable Grains of Truth for Arbitrary Computable Extensive-Form (Un)Known Games

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 4 of its 26 references that are in the map.
- First posted on arXiv 22 Aug 2025.

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

- [Bad Universal Priors and Notions of Optimality](https://mlsanity.com/paper/1510.04931/) (2015)
- [Thompson Sampling is Asymptotically Optimal in General Environments](https://mlsanity.com/paper/1602.07905/) (2016)
- [A Formal Solution to the Grain of Truth Problem](https://mlsanity.com/paper/1609.05058/) (2016)
- [Reflective Oracles: A Foundation for Classical Game Theory](https://mlsanity.com/paper/1508.04145/) (2015)

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

- [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 player acting in an infinite multi-player game learns to predict the other players' strategies if his prior assigns positive probability to their play (or contains a grain of truth). Kalai and Lehrer's classic grain of truth problem is to find a reasonably large class of strategies that contains the Bayes-optimal policies with respect to this class, allowing mutually-consistent beliefs about strategy choice that obey the rules of Bayesian inference. 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 strategies wide enough to contain all computable strategies as well as Bayes-optimal strategies for every reasonable prior over the class. When the "environment" is a known repeated stage game, we show convergence in the sense of [KL93a] and [KL93b]. When the environment is unknown, agents using Thompson sampling converge to play varepsilon-Nash equilibria in arbitrary unknown computable multi-agent environments. Finally, we include an application to self-predictive policies that avoid planning. While these results use computability theory only as a conceptual tool to solve a classic game theory problem, we show that our solution can naturally be computationally approximated arbitrarily closely.