{"ID":2879383,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2508.16245","arxiv_id":"2508.16245","title":"Limit-Computable Grains of Truth for Arbitrary Computable Extensive-Form (Un)Known Games","abstract":"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.","short_abstract":"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-op...","url_abs":"https://arxiv.org/abs/2508.16245","url_pdf":"https://arxiv.org/pdf/2508.16245v1","authors":"[\"Cole Wyeth\",\"Marcus Hutter\",\"Jan Leike\",\"Jessica Taylor\"]","published":"2025-08-22T09:24:55Z","proceeding":"cs.GT","tasks":"[\"cs.GT\",\"cs.LG\",\"cs.MA\",\"econ.TH\"]","methods":"[]","has_code":false}