論文の概要: Perturbing Best Responses in Zero-Sum Games

• arxiv url: http://arxiv.org/abs/2511.12523v1
• Date: Sun, 16 Nov 2025 09:30:15 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-18 14:36:24.293465
• Title: Perturbing Best Responses in Zero-Sum Games
• Title（参考訳）: ゼロサムゲームにおけるベストレスポンスの摂動
• Authors: Adam Dziwoki, Rostislav Horcik,
• Abstract要約: このようなオラクルを用いることで、両方のアルゴリズムの繰り返し回数を減らすことが示される。 実用性摂動は計算的に要求されているが、純粋な戦略がより内部構造を持つゲームにおいて、有効性を効率的に摂動できることを示す。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This paper investigates the impact of perturbations on the best-response-based algorithms approximating Nash equilibria in zero-sum games, namely Double Oracle and Fictitious Play. More precisely, we assume that the oracle computing the best responses perturbs the utilities before selecting the best response. We show that using such an oracle reduces the number of iterations for both algorithms. For some cases, suitable perturbations ensure the expected number of iterations is logarithmic. Although the utility perturbation is computationally demanding as it requires iterating through all pure strategies, we demonstrate that one can efficiently perturb the utilities in games where pure strategies have further inner structure.
• Abstract（参考訳）: 本稿では,ゼロサムゲーム,すなわちDouble OracleとFictitious Playにおいて,摂動がNash平衡を近似する最良の応答型アルゴリズムに与える影響について検討する。 より正確には、ベストレスポンスを計算したオラクルが、ベストレスポンスを選択する前にユーティリティを乱すと仮定する。 このようなオラクルを用いることで、両方のアルゴリズムの繰り返し回数を減らすことが示される。 場合によっては、適切な摂動は、期待される反復回数が対数であることを保証します。 実用性摂動は、全ての純粋な戦略を反復する必要があるため、計算的に要求されているが、純粋な戦略がより内部構造を持つゲームにおいて、有効性を効率的に摂動できることを実証する。

関連論文リスト

• Distributed Online Bandit Nonconvex Optimization with One-Point Residual Feedback via Dynamic Regret [10.700891331004799]
  本稿では,非損失関数を用いた分散オンライン帯域最適化問題について検討する。 プレイヤーは敵を選択し、そのプレイヤーに任意の非線形損失関数を割り当てる。 予想されるアルゴリズムの後悔は、2点偏差を用いた既存のアルゴリズムに匹敵する。
  論文  参考訳（メタデータ） (2024-09-24T02:37:33Z)
• A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
  そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。 提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
  論文  参考訳（メタデータ） (2024-09-07T06:37:23Z)
• Online Learning and Solving Infinite Games with an ERM Oracle [20.1330044382824]
  本稿では,ERMオーラクルコールのみに依存するオンラインバイナリ分類設定のためのアルゴリズムを提案する。 我々は、実現可能な設定における有限の後悔と、不可知的な設定におけるサブリニアに成長する後悔が示される。 我々のアルゴリズムは二値ゲームと実値ゲームの両方に適用でき、大きなゲームを解く実践において、二重オラクルと多重オラクルのアルゴリズムを広く活用するための正当性を提供すると見なすことができる。
  論文  参考訳（メタデータ） (2023-07-04T12:51:21Z)
• Efficient Policy Space Response Oracles [61.71849698253696]
  ポリシー空間応答 Oracle 法 (PSRO) は、2プレイヤーゼロサムゲームにおけるナッシュ均衡の一般解を提供する。 我々の開発の中心は、制限なし(URR)ゲームにおけるミニマックス最適化の導入である。 壁面時間, 10倍のデータ効率, および既存のPSRO法と同様のエクスプロイザビリティを, Kuhn と Leduc Poker のゲームで50倍高速化したことを報告した。
  論文  参考訳（メタデータ） (2022-01-28T17:54:45Z)
• Efficient and Optimal Algorithms for Contextual Dueling Bandits under Realizability [59.81339109121384]
  我々は,学習者が文脈情報を用いて2つの決定を下す連続的な決定設定であるK$コンテキストデュエルバンディット問題について検討するが,一方の判断が他方よりも優れていることを示唆する強調基準に基づくフィードバックのみを観察する。 提案手法は, 最善応答後悔という新たな概念に対して, 最善応答後悔に対する最適後悔率を実現するアルゴリズムである。
  論文  参考訳（メタデータ） (2021-11-24T07:14:57Z)
• Efficient Pure Exploration for Combinatorial Bandits with Semi-Bandit Feedback [51.21673420940346]
  コンビナーシャルバンディットはマルチアームバンディットを一般化し、エージェントが腕のセットを選択し、選択したセットに含まれる各腕の騒々しい報酬を観察します。 我々は, 最善の腕を一定の信頼度で識別する純粋爆発問題と, 応答集合の構造が動作集合の1つと異なるような, より一般的な設定に注目する。 有限多面体に対するプロジェクションフリーオンライン学習アルゴリズムに基づいて、凸的に最適であり、競争力のある経験的性能を持つ最初の計算効率の良いアルゴリズムである。
  論文  参考訳（メタデータ） (2021-01-21T10:35:09Z)
• New Oracle-Efficient Algorithms for Private Synthetic Data Release [52.33506193761153]
  微分プライベートな合成データを構築するための3つの新しいアルゴリズムを提案する。 アルゴリズムは最悪の場合でも差分プライバシーを満たす。 現状の手法である高次元行列機構 citeMcKennaMHM18 と比較すると,我々のアルゴリズムは大規模作業負荷の精度が向上する。
  論文  参考訳（メタデータ） (2020-07-10T15:46:05Z)
• Follow the Perturbed Leader: Optimism and Fast Parallel Algorithms for Smooth Minimax Games [33.9383996530254]
  オンライン学習の問題点とそのミニマックスゲームへの応用について考察する。 オンライン学習の問題に対して、Follow Perturbed Leaderは、最も優れたレスポンスを計算する、広く摂動されたオラクル設定である。
  論文  参考訳（メタデータ） (2020-06-13T02:55:41Z)
• Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oracles [112.89548995091182]
  我々は、文脈的帯域幅からオンライン回帰への、初めての普遍的で最適な削減を提供する。 我々のアルゴリズムは、実現可能性以上の分布仮定は必要とせず、コンテキストが逆選択された場合でも機能する。
  論文  参考訳（メタデータ） (2020-02-12T11:33:46Z)

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

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