Abstract | ||
---|---|---|
A Bayesian agent acting in a multi-agent environment learns to predict the other agentsu0027 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 e-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. |
Year | Venue | DocType |
---|---|---|
2016 | UAI | Journal |
Volume | Citations | PageRank |
abs/1609.05058 | 2 | 0.37 |
References | Authors | |
10 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Jan Leike | 1 | 150 | 15.49 |
Jessica Taylor | 2 | 3 | 0.71 |
Benya Fallenstein | 3 | 2 | 0.37 |