論文の概要: Polylogarithmic Nash Regret in Matrix Games with Bandit Feedback

• arxiv url: http://arxiv.org/abs/2609.34812v1
• Date: Mon, 28 Sep 2026 10:13:59 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-03 02:38:10.676203
• Title: Polylogarithmic Nash Regret in Matrix Games with Bandit Feedback
• Title（参考訳）: 帯域フィードバックを持つマトリックスゲームにおける多言語ナッシュレグレット
• Abstract要約: バンド利得フィードバックによる未知有限行列ゲームにおけるナッシュの後悔について検討し、相手の動作を観察した。 我々は、インスタンス依存の$mathcalO(log2 T)$ナッシュ後悔を実現するOPB(Optimistic Payoff Balancing)を開発する。
• 参考スコア（独自算出の注目度）: 14.692647465985916
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study Nash regret minimization in unknown finite matrix games with bandit payoff feedback and observed opponent actions. We develop Optimistic Payoff Balancing (OPB), which achieves instance-dependent $\mathcal{O}(\log^2 T)$ Nash regret against arbitrary adaptive opponents, including games with nonunique equilibria. This resolves the open problem posed by Maiti et al. (2025), extending their polylogarithmic guarantee under bandit feedback from $2\times2$ games to arbitrary finite dimensions. To handle nonunique equilibria, we construct a reference strategy that leaves room for local adjustments. We order independent payoff differences by estimation accuracy and scale these adjustments by uncertainty, allowing the learner to exploit the opponent's imbalance to offset estimation costs. Our result thus shows that observing opponent actions suffices for polylogarithmic Nash regret in general finite matrix games.
• Abstract（参考訳）: バンド利得フィードバックによる未知有限行列ゲームにおけるナッシュ後悔の最小化について検討し、対戦動作を観察した。 我々は、インスタンス依存の$\mathcal{O}(\log^2 T)$ Nash regretを達成できるOptimistic Payoff Balancing (OPB)を開発した。 これにより、Maiti et al (2025) が提起したオープンな問題は解決され、そのポリ対数保証は、2 の双対 2 のゲームから任意の有限次元へのバンドイットフィードバックの下で拡張される。 非特異均衡を扱うために、局所的な調整の余地を残した参照戦略を構築する。 我々は、推定精度で独立したペイオフ差分を発注し、不確実性によってこれらの調整をスケールし、学習者が相手の不均衡を利用して推定コストを相殺できるようにする。 以上の結果から, 一般有限行列ゲームにおいて, 対向行動の観察が多対数的ナッシュに十分であることを示す。

関連論文リスト

• Asymmetric Nash Seeking via Best Response Maps: Global Linear Convergence and Robustness to Inexact Reaction Models [0.0]
  ナッシュ均衡(Nash equilibria)は、マルチエージェントの意思決定と制御における相互作用をモデル化するための原則的なフレームワークを提供する。 この手紙は、非対称情報 2-プレーヤ制約付きゲームのクラスを分離可能な集合で研究する。
  論文  参考訳（メタデータ） (2026-03-17T18:45:56Z)
• Online Learning for Uninformed Markov Games: Empirical Nash-Value Regret and Non-Stationarity Adaptation [54.274028560515454]
  対戦相手の行動や方針が守られない2人プレイヤのマルコフゲームにおいて,オンライン学習を学習する。 経験的ナッシュバリュー後悔は,ナッシュバリュー後悔よりも強く,新たな後悔の概念である。 我々は,このアルゴリズムを,相手の潜在的非定常性に応じて適切な$で適応的に再起動する方法を示す。
  論文  参考訳（メタデータ） (2026-02-06T21:25:54Z)
• Adversarial Learning in Games with Bandit Feedback: Logarithmic Pure-Strategy Maximin Regret [64.73231630190121]
  ゼロサムゲームを学ぶことは、ゲーム理論と機械学習の基本的な問題である。 ビジットフィードバックによるゼロサムゲームにおける対戦学習について検討し,最大戦略に対する障害を最小限に抑えることを目的とした。 我々は,Tsallis-INFアルゴリズムがゲーム依存パラメータ$c$で$O(c log T)$インスタンス依存後悔を実現することを示す。
  論文  参考訳（メタデータ） (2026-02-06T03:26:01Z)
• Instance-Dependent Regret Bounds for Learning Two-Player Zero-Sum Games with Bandit Feedback [60.610120215789976]
  純粋な戦略 ナッシュ均衡が存在するとき、$c$ は 0 となり、最適のインスタンス依存後悔境界となることを示す。 また,本アルゴリズムは最終段階の収束性も享受し,ほぼ最適サンプルを用いて純粋な戦略ナッシュ均衡を同定することができる。
  論文  参考訳（メタデータ） (2025-02-24T20:20:06Z)
• On the Limitations and Possibilities of Nash Regret Minimization in Zero-Sum Matrix Games under Noisy Feedback [21.332966440675758]
  ナッシュ後悔(Nash regret)とは、プレイヤーの合計報酬と、タイムホライズによってスケールされたゲームのナッシュ平衡値との差である。 我々は,行プレーヤが行列全体のノイズフィードバックを受信した場合でも,標準アルゴリズムがNashを後悔していることを示す。 一般的な$n times m$行列ゲームに対して、インスタンス依存の$textpolylog(T)$ Nash regretを達成するアルゴリズムを提示する。
  論文  参考訳（メタデータ） (2023-06-22T22:45:48Z)
• Is Learning in Games Good for the Learners? [14.781100349601587]
  2人のエージェント間の繰り返しのゲームプレイにおいて、報酬と後悔の間のトレードオフを考慮する。 このような平衡は、任意の相手に対する後悔の保証を維持するアルゴリズムのペアによって到達可能であることを示す。 また,ゲーム開始時において,未学習エージェントとの繰り返しプレイを通じて報酬-最適戦略を学習する問題についても検討する。
  論文  参考訳（メタデータ） (2023-05-31T02:10:27Z)
• Abstracting Imperfect Information Away from Two-Player Zero-Sum Games [85.27865680662973]
  Nayyar et al. (2013) は、プレイヤーがプレイ中にポリシーを公に発表することで、不完全な情報を共通のペイオフゲームから抽象化できることを示した。 この研究は、ある正規化された平衡が上記の非対応問題を持たないことを示している。 これらの正規化された平衡はナッシュ平衡に任意に近づくことができるので、この結果は2つのプレイヤーゼロサムゲームを解くための新たな視点への扉を開く。
  論文  参考訳（メタデータ） (2023-01-22T16:54:06Z)

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

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