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

• URL: http://arxiv.org/abs/2508.16245v1
• Date: Fri, 22 Aug 2025 09:24:55 GMT
• Title: Limit-Computable Grains of Truth for Arbitrary Computable Extensive-Form (Un)Known Games
• Authors: Cole Wyeth, Marcus Hutter, Jan Leike, Jessica Taylor,
• Abstract summary: We find a class of strategies wide enough to contain all computable strategies as well as Bayes-optimal strategies for every reasonable prior over the class.<n>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.
• Score: 12.27678841215594
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Decoding Game: On Minimax Optimality of Heuristic Text Generation Strategies [7.641996822987559]
  We propose Decoding Game, a comprehensive theoretical framework which reimagines text generation as a two-player zero-sum game between Strategist and Nature.<n>It is shown that the adversarial Nature imposes an implicit regularization on likelihood, and truncation-normalization methods are first order approximations to the optimal strategy under this regularization.
  arXiv  Detail & Related papers  (2024-10-04T23:18:27Z)
• Is Learning in Games Good for the Learners? [14.781100349601587]
  We consider tradeoffs between reward and regret in repeated gameplay between two agents. We show that any such equilibrium is reachable by a pair of algorithms which maintain their regret guarantees against arbitrary opponents. We also consider the question of learning reward-optimal strategies via repeated play with a no-regret agent when game is initially unknown.
  arXiv  Detail & Related papers  (2023-05-31T02:10:27Z)
• ApproxED: Approximate exploitability descent via learned best responses [61.17702187957206]
  We study the problem of finding an approximate Nash equilibrium of games with continuous action sets. We propose two new methods that minimize an approximation of exploitability with respect to the strategy profile.
  arXiv  Detail & Related papers  (2023-01-20T23:55:30Z)
• Finding mixed-strategy equilibria of continuous-action games without gradients using randomized policy networks [83.28949556413717]
  We study the problem of computing an approximate Nash equilibrium of continuous-action game without access to gradients. We model players' strategies using artificial neural networks. This paper is the first to solve general continuous-action games with unrestricted mixed strategies and without any gradient information.
  arXiv  Detail & Related papers  (2022-11-29T05:16:41Z)
• Learning Correlated Equilibria in Mean-Field Games [62.14589406821103]
  We develop the concepts of Mean-Field correlated and coarse-correlated equilibria. We show that they can be efficiently learnt in emphall games, without requiring any additional assumption on the structure of the game.
  arXiv  Detail & Related papers  (2022-08-22T08:31:46Z)
• Near-Optimal No-Regret Learning for General Convex Games [121.50979258049135]
  We show that regret can be obtained for general convex and compact strategy sets. Our dynamics are on an instantiation of optimistic follow-the-regularized-bounds over an appropriately emphlifted space. Even in those special cases where prior results apply, our algorithm improves over the state-of-the-art regret.
  arXiv  Detail & Related papers  (2022-06-17T12:58:58Z)
• Strategizing against Learners in Bayesian Games [74.46970859427907]
  We study repeated two-player games where one of the players, the learner, employs a no-regret learning strategy. We consider general Bayesian games, where the payoffs of both the payoffs of both the learner and the learner could depend on the type.
  arXiv  Detail & Related papers  (2022-05-17T18:10:25Z)
• On the Impossibility of Convergence of Mixed Strategies with No Regret Learning [10.515544361834241]
  We study convergence properties of the mixed strategies that result from a general class of optimal no regret learning strategies. We consider the class of strategies whose information set at each step is the empirical average of the opponent's realized play.
  arXiv  Detail & Related papers  (2020-12-03T18:02:40Z)
• Complexity and Algorithms for Exploiting Quantal Opponents in Large Two-Player Games [16.43565579998679]
  Solution concepts of traditional game theory assume entirely rational players; therefore, their ability to exploit subrational opponents is limited. This paper aims to analyze and propose scalable algorithms for computing effective and robust strategies against a quantal opponent in normal-form and extensive-form games.
  arXiv  Detail & Related papers  (2020-09-30T09:14:56Z)
• Efficient exploration of zero-sum stochastic games [83.28949556413717]
  We investigate the increasingly important and common game-solving setting where we do not have an explicit description of the game but only oracle access to it through gameplay. During a limited-duration learning phase, the algorithm can control the actions of both players in order to try to learn the game and how to play it well. Our motivation is to quickly learn strategies that have low exploitability in situations where evaluating the payoffs of a queried strategy profile is costly.
  arXiv  Detail & Related papers  (2020-02-24T20:30:38Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.