論文の概要: On the Limitations and Possibilities of Nash Regret Minimization in Zero-Sum Matrix Games under Noisy Feedback

• arxiv url: http://arxiv.org/abs/2306.13233v3
• Date: Sat, 24 May 2025 01:53:41 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-27 16:58:41.22305
• Title: On the Limitations and Possibilities of Nash Regret Minimization in Zero-Sum Matrix Games under Noisy Feedback
• Title（参考訳）: 雑音フィードバック下でのゼロサム行列ゲームにおけるナッシュレギュレット最小化の限界と可能性について
• Authors: Arnab Maiti, Kevin Jamieson, Lillian J. Ratliff,
• Abstract要約: ナッシュ後悔(Nash regret)とは、プレイヤーの合計報酬と、タイムホライズによってスケールされたゲームのナッシュ平衡値との差である。 我々は,行プレーヤが行列全体のノイズフィードバックを受信した場合でも,標準アルゴリズムがNashを後悔していることを示す。 一般的な$n times m$行列ゲームに対して、インスタンス依存の$textpolylog(T)$ Nash regretを達成するアルゴリズムを提示する。
• 参考スコア（独自算出の注目度）: 21.332966440675758
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper studies a variant of two-player zero-sum matrix games, where, at each timestep, the row player selects row $i$, the column player selects column $j$, and the row player receives a noisy reward with expected value $A_{i,j}$, along with noisy feedback on the input matrix $A$. The row player's goal is to maximize their total reward against an adversarial column player. Nash regret, defined as the difference between the player's total reward and the game's Nash equilibrium value scaled by the time horizon $T$, is often used to evaluate algorithmic performance in zero-sum games. We begin by studying the limitations of existing algorithms for minimizing Nash regret. We show that standard algorithm--including Hedge, FTRL, and OMD--as well as the strategy of playing the Nash equilibrium of the empirical matrix--all incur $\Omega(\sqrt{T})$ Nash regret, even when the row player receives noisy feedback on the entire matrix $A$. Furthermore, we show that UCB for matrix games, a natural adaptation of the well-known bandit algorithm, also suffers $\Omega(\sqrt{T})$ Nash regret under bandit feedback. Notably, these lower bounds hold even in the simplest case of $2 \times 2$ matrix games, where the instance-dependent matrix parameters are constant. We next ask whether instance-dependent $\text{polylog}(T)$ Nash regret is achievable against adversarial opponents. We answer this affirmatively. In the full-information setting, we present the first algorithm for general $n \times m$ matrix games that achieves instance-dependent $\text{polylog}(T)$ Nash regret. In the bandit feedback setting, we design an algorithm with similar guarantees for the special case of $2 \times 2$ game--the same regime in which existing algorithms provably suffer $\Omega(\sqrt{T})$ regret despite the simplicity of the instance. Finally, we validate our theoretical results with empirical evidence.
• Abstract（参考訳）: 本稿では,各タイミングで行プレーヤが行$i$を選択し,列プレーヤが列$j$を選択し,行プレーヤが期待値$A_{i,j}$と,入力マトリクス$A$のノイズフィードバックを受信する。 行プレーヤのゴールは、敵列プレーヤに対する全報酬を最大化することである。 プレイヤーの総報酬とゲームのナッシュ平衡値の差として定義されるナッシュ後悔は、ゼロサムゲームにおけるアルゴリズムのパフォーマンスを評価するためにしばしば用いられる。 まず、Nashの後悔を最小化するための既存のアルゴリズムの限界について研究する。 Hedge, FTRL, OMDを含む標準的なアルゴリズムと, 経験的行列のナッシュ平衡を再生する戦略が, たとえ行プレーヤが行列全体のノイズフィードバックを受けたとしても, すべて$\Omega(\sqrt{T})$ナッシュ後悔することを示している。 さらに、よく知られたバンディットアルゴリズムの自然な適応である行列ゲームに対する UCB もまた、バンディットフィードバックの下では$\Omega(\sqrt{T})$ Nash regret を被っていることを示す。 特に、これらの下界は、インスタンス依存行列パラメータが定数である2$ 2$行列ゲームにおいて最も単純な場合においても成り立つ。 次に、インスタンス依存の $\text{polylog}(T)$ Nash regret が敵対する相手に対して達成可能であるかどうか尋ねる。 私たちはこれを肯定的に答える。 全情報設定では、インスタンス依存の $\text{polylog}(T)$ Nash regret を達成する一般$n \times m$Matrix ゲームに対する最初のアルゴリズムを示す。 バンディットフィードバック設定では、既存のアルゴリズムがインスタンスの単純さに拘わらず、確実に$\Omega(\sqrt{T})$の後悔を被るのと同じ条件で、2ドルの特別なケースに対して同様の保証を持つアルゴリズムを設計する。 最後に, 実証実験による理論結果の検証を行った。

関連論文リスト

• Instance-Dependent Regret Bounds for Learning Two-Player Zero-Sum Games with Bandit Feedback [60.610120215789976]
  純粋な戦略 ナッシュ均衡が存在するとき、$c$ は 0 となり、最適のインスタンス依存後悔境界となることを示す。 また,本アルゴリズムは最終段階の収束性も享受し,ほぼ最適サンプルを用いて純粋な戦略ナッシュ均衡を同定することができる。
  論文  参考訳（メタデータ） (2025-02-24T20:20:06Z)
• Best of Both Worlds: Regret Minimization versus Minimax Play [57.68976579579758]
  この結果から,悪用可能な相手からOmega(T)$を得ることができながら,少なくともO(1)$損失のリスクを保証できることが分かる。
  論文  参考訳（メタデータ） (2025-02-17T11:04:01Z)
• Blackwell's Approachability with Approximation Algorithms [15.266876140036052]
  プレイヤーと相手のベクター値の繰り返しゲームを考える。 プレイヤーのセットのみに近似アルゴリズムが組み込まれている場合、よりシンプルで効率的なアルゴリズムが提供される。
  論文  参考訳（メタデータ） (2025-02-06T09:54:00Z)
• Context-lumpable stochastic bandits [49.024050919419366]
  我々は、$S$コンテキストと$K$アクションによる文脈的盗賊問題を考える。 我々は,最大$widetilde O(r (S +K )/epsilon2)$サンプルを用いて,$epsilon$-optimal Policyを出力するアルゴリズムを提案する。 後悔の設定では、T$までの累積後悔を$widetilde O(sqrtr3(S+K)T)$で束縛するアルゴリズムを与える。
  論文  参考訳（メタデータ） (2023-06-22T17:20:30Z)
• Near-Optimal Learning of Extensive-Form Games with Imperfect Information [54.55092907312749]
  本稿では,2プレイヤーゼロサムゲームにおいて,$widetildemathcalO((XA+YB)/varepsilon2)$プレイのエピソードのみを必要とするアルゴリズムの最初の行を,$varepsilon$-approximate Nash平衡を求める。 これにより$widetildemathcalO((X2A+Y2B)/varepsilon2)$が$widetildemathcalO(maxX,
  論文  参考訳（メタデータ） (2022-02-03T18:18:28Z)
• Doubly Optimal No-Regret Online Learning in Strongly Monotone Games with Bandit Feedback [29.553652241608997]
  本研究では,テキストモオと強いモノトーンゲームの研究を行い,その学習方法について検討した。 我々はまず,新しい帯域学習アルゴリズムを構築し,$tildeTheta(nsqrtT)$の単一エージェント最適後悔を実現することを示す。 そこで我々は,このオープンな問題を解決し,広範にわたるバンディットゲーム理論学習に寄与した。
  論文  参考訳（メタデータ） (2021-12-06T08:27:54Z)
• Almost Optimal Algorithms for Two-player Markov Games with Linear Function Approximation [92.99933928528797]
  同時動作による2プレイヤーゼロサムマルコフゲームの強化学習について検討した。 我々は,「不確かさの最適性」に基づくアルゴリズムナッシュ-UCRL-VTRを提案する。 我々は、Nash-UCRL-VTR が $tildeO(dHsqrtT)$ regret を確実に達成できることを示し、$d$ は線型関数次元である。
  論文  参考訳（メタデータ） (2021-02-15T09:09:16Z)
• Impact of Representation Learning in Linear Bandits [83.17684841392754]
  本研究では,表現学習が帯域幅問題の効率性を向上させる方法について検討する。 我々は,$widetildeO(TsqrtkN + sqrtdkNT)$ regretを達成する新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-10-13T16:35:30Z)
• Near-Optimal Reinforcement Learning with Self-Play [50.29853537456737]
  我々は,直接の監督なしに自己対決で最適な政策を学習するセルフプレイアルゴリズムに焦点をあてる。 本稿では,サンプル複雑性を$tildemathcalO(SAB)$,サンプル複雑性を$tildemathcalO(S(A+B)$とする新しいemphNash Vラーニングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-22T05:00:13Z)
• Improved Sleeping Bandits with Stochastic Actions Sets and Adversarial Rewards [59.559028338399855]
  我々は,行動セットと敵意の報酬を伴って睡眠中の盗賊の問題を考察する。 本稿では,EXP3にインスパイアされた新しい計算効率のよいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-04-14T00:41:26Z)
• Regret Minimization in Stochastic Contextual Dueling Bandits [40.17224226373741]
  我々は、コンテキスト設定において、$K$武装デュエルバンディットの問題を考察する。 提案手法は, それぞれ, 後悔の保証を施した2つのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-02-20T06:36:19Z)

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

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