A Formal Solution to the Grain of Truth Problem

By Jan Leike, Jessica Taylor, Benya Fallenstein. 2016

18 citations recorded by the source corpus.

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 \emph{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 \emph{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 {\epsilon}-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.

Subfields: Reinforcement Learning

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Reinforcement Learning

1. Jan Leike
2. Tom Everitt
3. Shane Legg
4. David Krueger
5. Marcus Hutter
6. Miljan Martic
7. Vishal Maini
8. Gary Lea

Citations in the corpus

• Scalable agent alignment via reward modeling: a research direction (2018, background): “…problem definitions from many authors before us, highlighting tractable and neglected problems in the field of AI safety (Russell et al., 2015; Soares, 2015; Amodei et al., 2016; Taylor et al., 2016; Soares & Fallenstein, 2017; Christiano, 2017; Leike et al., 2017; Ortega et al., 2018; and others).”
• AGI Safety Literature Review (2018, methodology): “Extensions of this framework have been developed for studying goal alignment (Everitt and Hutter, 2018a), multi-agent interaction (Leike, Taylor, et al., 2016), space-time embeddedness (Orseau and Ring, 2012), self-modification (Everitt, Filan, et al., 2016; Orseau and Ring, 2011), observation…”
• Embedded Agency (2019, background): “For details, see Leike (2016).”