論文の概要: Adversarial Learning in Games with Bandit Feedback: Logarithmic Pure-Strategy Maximin Regret

• arxiv url: http://arxiv.org/abs/2602.06348v1
• Date: Fri, 06 Feb 2026 03:26:01 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-09 22:18:26.210603
• Title: Adversarial Learning in Games with Bandit Feedback: Logarithmic Pure-Strategy Maximin Regret
• Title（参考訳）: 帯域フィードバックを持つゲームにおける対数学習:対数的Pure-Strategy Maximin Regret
• Authors: Shinji Ito, Haipeng Luo, Arnab Maiti, Taira Tsuchiya, Yue Wu,
• Abstract要約: ゼロサムゲームを学ぶことは、ゲーム理論と機械学習の基本的な問題である。 ビジットフィードバックによるゼロサムゲームにおける対戦学習について検討し,最大戦略に対する障害を最小限に抑えることを目的とした。 我々は,Tsallis-INFアルゴリズムがゲーム依存パラメータ$c$で$O(c log T)$インスタンス依存後悔を実現することを示す。
• 参考スコア（独自算出の注目度）: 64.73231630190121
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Learning to play zero-sum games is a fundamental problem in game theory and machine learning. While significant progress has been made in minimizing external regret in the self-play settings or with full-information feedback, real-world applications often force learners to play against unknown, arbitrary opponents and restrict learners to bandit feedback where only the payoff of the realized action is observable. In such challenging settings, it is well-known that $Ω(\sqrt{T})$ external regret is unavoidable (where T is the number of rounds). To overcome this barrier, we investigate adversarial learning in zero-sum games under bandit feedback, aiming to minimize the deficit against the maximin pure strategy -- a metric we term Pure-Strategy Maximin Regret. We analyze this problem under two bandit feedback models: uninformed (only the realized reward is revealed) and informed (both the reward and the opponent's action are revealed). For uninformed bandit learning of normal-form games, we show that the Tsallis-INF algorithm achieves $O(c \log T)$ instance-dependent regret with a game-dependent parameter $c$. Crucially, we prove an information-theoretic lower bound showing that the dependence on c is necessary. To overcome this hardness, we turn to the informed setting and introduce Maximin-UCB, which obtains another regret bound of the form $O(c' \log T)$ for a different game-dependent parameter $c'$ that could potentially be much smaller than $c$. Finally, we generalize both results to bilinear games over an arbitrary, large action set, proposing Tsallis-FTRL-SPM and Maximin-LinUCB for the uninformed and informed setting respectively and establishing similar game-dependent logarithmic regret bounds.
• Abstract（参考訳）: ゼロサムゲームを学ぶことは、ゲーム理論と機械学習の基本的な問題である。 自己プレイ設定や完全な情報フィードバックによる外部の後悔を最小限に抑えるために大きな進歩があったが、現実のアプリケーションでは、学習者が未知の、任意の相手に対してプレーすることを強制し、学習者が実際に実現された行動の支払いのみを観察できるようなフィードバックを盗むことを制限していることが多い。 このような困難な設定では、$Ω(\sqrt{T})$外部後悔は避けられない(T はラウンド数である)ことが知られている。 この障壁を克服するために、我々は、極大純粋戦略に対する欠点を最小化することを目的とした、バンドイットフィードバックによるゼロサムゲームにおける敵意学習(Pure-Strategy Maximin Regret)を調査する。 本研究では,この問題を2つの包括的フィードバックモデルで解析する。非インフォームド(実効的な報酬のみを明らかにする)とインフォームド(報酬と相手の行動を明らかにする)である。 正規形式ゲームの非インフォームなバンディット学習では、Tsallis-INFアルゴリズムがゲーム依存パラメータ$c$で$O(c \log T)$インスタンス依存後悔を達成することを示す。 重要なことは、c への依存が不可欠であることを示す情報理論の下界を証明している。 この難しさを克服するために、情報設定に目を向けてMaximin-UCBを導入し、ゲーム依存のパラメータ $c'$ に対して $O(c' \log T)$ という形の別の後悔境界を得る。 最後に、2つの結果を任意の大きなアクション集合上の双線形ゲームに一般化し、それぞれ非形式的および情報的設定に対して Tsallis-FTRL-SPM と Maximin-LinUCB を提案し、同様のゲーム依存対数的後悔境界を確立する。

関連論文リスト

• Instance-Dependent Regret Bounds for Learning Two-Player Zero-Sum Games with Bandit Feedback [60.610120215789976]
  純粋な戦略 ナッシュ均衡が存在するとき、$c$ は 0 となり、最適のインスタンス依存後悔境界となることを示す。 また,本アルゴリズムは最終段階の収束性も享受し,ほぼ最適サンプルを用いて純粋な戦略ナッシュ均衡を同定することができる。
  論文  参考訳（メタデータ） (2025-02-24T20:20:06Z)
• Provably Efficient Generalized Lagrangian Policy Optimization for Safe Multi-Agent Reinforcement Learning [105.7510838453122]
  制約付きマルコフゲームを用いたオンライン安全なマルチエージェント強化学習について検討する。 我々は,このラグランジアン問題を解くための高信頼強化学習アルゴリズムを開発した。 提案アルゴリズムは,オンラインミラー降下によるミニマックス決定主元変数と,投影勾配ステップによる双対変数を更新する。
  論文  参考訳（メタデータ） (2023-05-31T22:09:24Z)
• Is Learning in Games Good for the Learners? [14.781100349601587]
  2人のエージェント間の繰り返しのゲームプレイにおいて、報酬と後悔の間のトレードオフを考慮する。 このような平衡は、任意の相手に対する後悔の保証を維持するアルゴリズムのペアによって到達可能であることを示す。 また,ゲーム開始時において,未学習エージェントとの繰り返しプレイを通じて報酬-最適戦略を学習する問題についても検討する。
  論文  参考訳（メタデータ） (2023-05-31T02:10:27Z)
• No-regret learning for repeated non-cooperative games with lossy bandits [5.437709019435926]
  本研究では,長期的後悔の損失を最小限に抑えるために,プレイヤーの非同期オンライン学習戦略について検討する。 この論文は、損失帯域付きオンライングラディエントDescent(OGD-lb)と呼ばれる、新しい非回帰学習アルゴリズムを提供する。
  論文  参考訳（メタデータ） (2022-05-14T05:02:56Z)
• Complete Policy Regret Bounds for Tallying Bandits [51.039677652803675]
  政策後悔は、適応的な敵に対してオンライン学習アルゴリズムのパフォーマンスを測定するという、よく確立された概念である。 我々は,不完全な政策後悔を効果的に最小化できる敵の制限について検討する。 我々は、$tildemathcalO(mKsqrtT)$の完全なポリシーを後悔するアルゴリズムを提供し、$tildemathcalO$表記は対数要素だけを隠す。
  論文  参考訳（メタデータ） (2022-04-24T03:10:27Z)
• Generalized Bandit Regret Minimizer Framework in Imperfect Information Extensive-Form Game [9.933208900617174]
  我々は,IIEGのダイナミクスを知らない対話型バンディットフィードバック設定の問題点を考察する。 NEを学習するには、後悔最小化器は、全フィードバック損失勾配$ellt$ by $v(zt)$を推定し、後悔を最小化する。 モデルフリーであり、$O(sqrtX B/T+sqrtY C/T)$から$O()$までの最良の収束率を大幅に向上させる。
  論文  参考訳（メタデータ） (2022-03-11T13:45:42Z)
• The Best of Both Worlds: Reinforcement Learning with Logarithmic Regret and Policy Switches [84.54669549718075]
  漸進的強化学習(RL)における後悔の最小化問題について検討する。 一般関数クラスと一般モデルクラスで学ぶことに集中する。 対数的後悔境界は$O(log T)$スイッチングコストのアルゴリズムによって実現可能であることを示す。
  論文  参考訳（メタデータ） (2022-03-03T02:55:55Z)
• Online Learning in Unknown Markov Games [55.07327246187741]
  未知のマルコフゲームでオンライン学習を学ぶ。 後方視における最良の反応に対するサブ線形後悔の達成は統計的に困難であることを示す。 サブ線形$tildemathcalO(K2/3)$ regretを$K$のエピソード後に達成するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-10-28T14:52:15Z)

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

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