論文の概要: Limit-Computable Grains of Truth for Arbitrary Computable Extensive-Form (Un)Known Games

• arxiv url: http://arxiv.org/abs/2508.16245v1
• Date: Fri, 22 Aug 2025 09:24:55 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-08-25 16:42:36.338578
• Title: Limit-Computable Grains of Truth for Arbitrary Computable Extensive-Form (Un)Known Games
• Title（参考訳）: 任意計算可能指数型(Un)Knownゲームにおける真理の極限計算可能格子
• Authors: Cole Wyeth, Marcus Hutter, Jan Leike, Jessica Taylor,
• Abstract要約: 計算可能なすべての戦略を含むのに十分広い戦略のクラスと、そのクラスに対する妥当なすべての事前のベイズ最適化戦略を見出す。 これらの結果は、古典ゲーム理論の問題を解決するための概念的ツールとしてのみ計算可能性理論を用いるが、我々は自然に計算的に近似できることを示した。
• 参考スコア（独自算出の注目度）: 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.
• Abstract（参考訳）: 無限のマルチプレイヤーゲームでプレーするベイズ奏者は、前者が自分のプレーに肯定的な確率(または真実の粒を含む)を割り当てた場合、他のプレイヤーの戦略を予測することを学ぶ。 カライとレーラーの古典的な真理問題(英語版)は、このクラスに関してベイズ最適化政策を含む、合理的に大きな戦略クラスを見つけることであり、ベイズ推論の規則に従う戦略選択に関する相互に一貫性のある信念を可能にする。 小さなクラスのみが真実の粒を持っていることが知られており、文献にはいくつかの関連性のない結果が含まれている。 本稿では,全真理問題に対する形式的かつ一般的な解について述べる: 計算可能なすべての戦略を包含できるような,広い範囲の戦略と,クラス上の妥当なすべての事前のベイズ最適化戦略を構築する。 環境」が既知のステージゲームである場合、[KL93a]と[KL93b]の意味で収束を示す。 環境が未知の場合、トンプソンサンプリングを用いたエージェントは、任意の未知の計算可能なマルチエージェント環境において$\varepsilon$-Nash平衡を再生するために収束する。 最後に、計画を避けた自己予測ポリシーへのアプリケーションを含めます。 これらの結果は、古典ゲーム理論の問題を解決するための概念的ツールとしてのみ計算可能性理論を用いるが、我々は自然に計算的に近似できることを示した。

関連論文リスト

• Decoding Game: On Minimax Optimality of Heuristic Text Generation Strategies [7.641996822987559]
  我々は,テキスト生成をストラテジストとネイチャーの2プレイヤーゼロサムゲームとして再定義する,包括的な理論的枠組みであるデコードゲームを提案する。 逆数自然は可能性に対して暗黙の正則化を課し、トラルニケーション正規化法は、この正則化の下での最適戦略の第一次近似である。
  論文  参考訳（メタデータ） (2024-10-04T23:18:27Z)
• Is Learning in Games Good for the Learners? [14.781100349601587]
  2人のエージェント間の繰り返しのゲームプレイにおいて、報酬と後悔の間のトレードオフを考慮する。 このような平衡は、任意の相手に対する後悔の保証を維持するアルゴリズムのペアによって到達可能であることを示す。 また,ゲーム開始時において,未学習エージェントとの繰り返しプレイを通じて報酬-最適戦略を学習する問題についても検討する。
  論文  参考訳（メタデータ） (2023-05-31T02:10:27Z)
• ApproxED: Approximate exploitability descent via learned best responses [61.17702187957206]
  連続的なアクションセットを持つゲームの近似的ナッシュ均衡を求める問題について検討する。 本稿では,戦略プロファイルに対するエクスプロイラビリティの近似を最小化する2つの新しい手法を提案する。
  論文  参考訳（メタデータ） (2023-01-20T23:55:30Z)
• Finding mixed-strategy equilibria of continuous-action games without gradients using randomized policy networks [83.28949556413717]
  グラデーションへのアクセスを伴わない連続アクションゲームのナッシュ平衡を近似的に計算する問題について検討する。 ニューラルネットワークを用いてプレイヤーの戦略をモデル化する。 本論文は、制約のない混合戦略と勾配情報のない一般的な連続アクションゲームを解決する最初の方法である。
  論文  参考訳（メタデータ） (2022-11-29T05:16:41Z)
• Strategizing against Learners in Bayesian Games [74.46970859427907]
  プレイヤーの1人である学習者が無学習の学習戦略を採用する2人プレイヤゲームについて検討した。 一般のベイズゲームでは,学習者と学習者の双方の報酬の支払いが,そのタイプに依存する可能性がある。
  論文  参考訳（メタデータ） (2022-05-17T18:10:25Z)
• On the Impossibility of Convergence of Mixed Strategies with No Regret Learning [10.515544361834241]
  最適無後悔学習戦略の一般クラスから得られる混合戦略の収束特性について検討する。 各ステップに設定された情報を相手の実演の実証平均とする戦略のクラスを考察する。
  論文  参考訳（メタデータ） (2020-12-03T18:02:40Z)
• Efficient exploration of zero-sum stochastic games [83.28949556413717]
  ゲームプレイを通じて,ゲームの記述を明示せず,託宣のみにアクセス可能な,重要で一般的なゲーム解決環境について検討する。 限られたデュレーション学習フェーズにおいて、アルゴリズムは両方のプレイヤーのアクションを制御し、ゲームを学習し、それをうまくプレイする方法を学習する。 私たちのモチベーションは、クエリされた戦略プロファイルの支払いを評価するのにコストがかかる状況において、利用可能性の低い戦略を迅速に学習することにあります。
  論文  参考訳（メタデータ） (2020-02-24T20:30:38Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。