論文の概要: When Are We Near Nash? Certifying Solutions in General-Sum Games

• arxiv url: http://arxiv.org/abs/2610.29300v1
• Date: Wed, 21 Oct 2026 06:53:56 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-23 00:40:06.263468
• Title: When Are We Near Nash? Certifying Solutions in General-Sum Games
• Title（参考訳）: ナッシュはいつ近づいたか? 汎用ゲームにおける認証ソリューション
• Abstract要約: 2人のプレイヤーゲームでは、重み付き平均戦略のナッシュギャップは、最大化プレイヤーにおいて、重み付き外部後悔と符号付き値補正とで等しくなる。 チェックポイント当たりのコストが端末履歴数に線形であるオンライン証明書を発行する。 証明書は更新を交互に行い、3人以上のプレーヤーとのゲームで音を立てる。
• 参考スコア（独自算出の注目度）: 38.06569764716213
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Heuristic solvers for general-sum extensive-form games produce a stream of iterates, and practice reports the NashGap of the returned profile. We ask what a solver can know about its own iterates from the regret accumulators and the terminal-distribution accumulators its updates already maintain. In two-player games the NashGap of a weighted average strategy equals, at the maximizing player, the weighted external regret plus a signed value correction. Bounding the regret by the running counterfactual-regret accumulator gives an online certificate whose cost per checkpoint is linear in the number of terminal histories. The certificate stays sound under alternating updates and in games with three or more players. The mismatch between what alternation evaluates and what the averages record enters as one signed comparator term, maximized in a single backward pass per player whose comparator weight is nonzero. The bound is read off the regret state, with no best response against the average. Run a portfolio of training-free regret-matching solvers, output the iterate with the smallest certificate, and verify that iterate once. On the benchmark's biased Leduc family a pool of sixteen training-free solvers, seven original and nine recent variants, solves $89\%$ of the $64$ instances at threshold $10^{-5}$ this way, matching the trajectory-minimum union of the solvers. The same protocol solves $92\%$ of the $64$ pre-registered held-out instances and $89\%$ again on a third set of $64$ instances that no earlier stage used. The zero-best-response certificate certifies all $57$ in-sample solves and all $57$ fresh ones, and $58$ of the $59$ held-out ones. Its exact-comparator refinement certifies every solve in the three sets. The certificate states both and attributes its bound. Code is available at https://github.com/lbn187/CertNE.
• Abstract（参考訳）: 汎用的な広義ゲームのためのヒューリスティックな解法は、繰り返しのストリームを生成し、返却されたプロファイルのNashGapを実践する。 我々は、後悔するアキュムレータと、その更新がすでに維持されている端末配信アキュムレータから、解決者が自身のイテレートについて何を知っているのかを尋ねる。 2人のプレイヤーゲームでは、重み付き平均戦略のナッシュギャップは、最大化プレイヤーにおいて、重み付き外部後悔と符号付き値補正とで等しくなる。 チェックポイント当たりのコストが端末履歴数に線形であるオンライン証明書を発行する。 証明書は更新を交互に行い、3人以上のプレーヤーとのゲームで音を立てる。 換算値と平均値レコードとのミスマッチは1つの符号付きコンパレータの項として入力され、コンパレータの重量がゼロでないプレイヤーごとに1つの後方パスで最大化される。 境界は後悔状態から読み出され、平均に対するベストな反応はない。 トレーニングなしの後悔マッチング解決器のポートフォリオを実行し、最小の証明書でイテレートを出力し、一度イテレートしたことを検証します。 ベンチマークのバイアス付きLeducファミリでは、16のトレーニング不要のソルバのプール、7つのオリジナルと9つの最近の変種が、しきい値10^{-5}$の6,4$インスタンスの89\%$をこの方法で解決し、ソルバの軌道最小結合と一致する。 同じプロトコルでは、事前登録された640ドルの保留インスタンスの912\%と、未使用の第3セットの644ドルのインスタンスの89\%を解決している。 0-best-responseの証明書は、インサンプルで57ドル、新品で57ドル、ホールトアウトで59ドルをすべて認証する。 その完全コンパクト化は、3つの集合のすべての解を証明している。 証明書は両方を記述し、その境界を属性とする。 コードはhttps://github.com/lbn187/CertNEで入手できる。

関連論文リスト

• The Certification Exponent: Instance-Optimal Sequential Certification of Policy Improvement from History Dependent Logs [3.744103474408833]
  指数$Kstar$は、ログ化された法則から、ターゲットが改善しない同じログ化された作用確率を持つ法則への最小のKL分岐であることを示す。 サウンド証明器は、$log(1/)/Kstar$期待のエピソードで停止せず、任意の$で、0Kstarinfty$でプラグインのKelly認証器が$to0$でこのレートを達成する。
  論文  参考訳（メタデータ） (2026-10-17T00:25:45Z)
• Terminal-Register Certification for Finite-Measurement Learning of Multiscale Quantum States [1.9599274203282304]
  逆2次元多スケールエンタングルメント再正規化アンサッツ(MERA)による純粋一次元状態の学習について検討する。 理想的な逐次および終端測定スケジュールが一致した因果操作の下で同じ完全ビット列分布を提供することを確認した。 雑音認識定理は、有限ショット証明書に個別の摂動総変量実装予算を導入する。
  論文  参考訳（メタデータ） (2026-09-27T13:41:20Z)
• Certified Inference and Training for Deep Equilibrium Networks: A Continuation Framework with Polynomial Complexity Guarantees [0.0]
  我々は、Deep equilibrium Network(DEQ)における推論とトレーニングのための認定された継続フレームワークを開発する。 推論のために、入力ホモトピーは供給された開始根から平衡を選択し、丸いトラッカーが定量的条件下でそれに従う。 訓練のために、プログラム可能な休眠可能な双線形ランクワンチャネルは、出力保存された残留整列修復を提供する。
  論文  参考訳（メタデータ） (2026-09-15T01:15:58Z)
• CAST: Game Solvers as Turn-Level Teachers for LLM Agents [78.2379284312811]
  大きな言語モデル(LLM)を訓練して、長距離ゲームで動作させることは、ジェネラリストの意思決定に向けた有望なステップである。 デンサープロセスの信号はこのターンレベルの信用を欠く可能性があるが、既存の情報源は安価で正確な情報を維持することは難しい。 本稿では,ゲームソルバの状態値の変化をデザイナの利点に変換し,ターンレベルの信号としてRLVRに注入するCASTを提案する。
  論文  参考訳（メタデータ） (2026-07-28T05:39:01Z)
• Interval Certifications for Multilayered Perceptrons via Lattice Traversal [10.268619734362547]
  本研究では, 対向ロバスト性問題を格子問題に還元できることを示す。 我々は形式的検証器を開発し、音の最大性と完全最小性が保証される。 新たなParallelepipedoNNシステムを用いて,実験的検討を行った。
  論文  参考訳（メタデータ） (2026-04-09T11:25:43Z)
• Instance-Dependent Regret Bounds for Learning Two-Player Zero-Sum Games with Bandit Feedback [60.610120215789976]
  純粋な戦略 ナッシュ均衡が存在するとき、$c$ は 0 となり、最適のインスタンス依存後悔境界となることを示す。 また,本アルゴリズムは最終段階の収束性も享受し,ほぼ最適サンプルを用いて純粋な戦略ナッシュ均衡を同定することができる。
  論文  参考訳（メタデータ） (2025-02-24T20:20:06Z)
• Corrupted Learning Dynamics in Games [62.73758165845971]
  すべてのプレイヤーが楽観的な追従型リーダー(OFTRL)に従うと、平衡は$O(log T)$の速さで計算できる。 本稿では,各プレイヤーが所定のアルゴリズムによって提案される戦略から逸脱する程度に依存する速度で,適応的に平衡を求める学習ダイナミクスを提案する。
  論文  参考訳（メタデータ） (2024-12-10T02:23:44Z)
• Computational Lower Bounds for Regret Minimization in Normal-Form Games [68.66209476382213]
  乗算重み更新などの既存の学習アルゴリズムが最適に近いことを示す。 結果はKothari と Mehta が提案したアルゴリズムの枠組みで得られた。
  論文  参考訳（メタデータ） (2024-11-04T00:39:52Z)

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

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