論文の概要: Regret Minimization with Adaptive Opponents in Repeated Games

• arxiv url: http://arxiv.org/abs/2606.06486v1
• Date: Thu, 04 Jun 2026 17:59:08 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-05 22:39:45.034653
• Title: Regret Minimization with Adaptive Opponents in Repeated Games
• Title（参考訳）: 繰り返しゲームにおけるアダプティブ・ポンポンによるレギュレット最小化
• Authors: Mingyang Liu, Asuman Ozdaglar, Tiancheng Yu, Kaiqing Zhang,
• Abstract要約: 我々は,エフィンジンジックの蓄積ユーティリティとエフィンジンジックの差を測るゲーム計量を導入する。 この設定での既存の後悔の概念と比較すると、我々は繰り返しプレイするゲームにネイティブです。 残念な概念を最小化することは、Stag-Huntのようなゲームにおいて、より高いユーティリティを持つより協調的な解決につながることを示す。
• 参考スコア（独自算出の注目度）: 26.91475329780589
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this paper, we study regret minimization in repeated games with \emph{adaptive} opponents who can respond based on histories of play. The standard metric of \emph{external regret} in online learning is known to fail to capture such adaptivity. To account for players' counterfactual reasoning, we introduce {\tt Repeated Policy Regret (RP-Regret)}, a game-theoretic metric that measures the difference between the \emph{realized} and the \emph{best-in-hindsight} accumulated utility when all players can \emph{respond} to the history of play. Compared to existing regret notions in this setting, ours is native to repeated game playing, enabling stronger comparators and opponents with fewer constraints, while maintaining the possibility of finding better equilibria when all players minimize it. We first identify necessary conditions for obtaining {\tt RP-Regret} sublinear in time, on the variation of the player's comparator strategies in the regret definition and on the memories of both the comparator and opponents' strategies. We then study additional conditions and provable algorithms to minimize {\tt RP-Regret}, which is by definition \emph{non-convex} in the strategy space. To address this challenge, we propose three algorithms: (i) one based on an optimization oracle, as assumed in some prior work in online non-convex learning; (ii) one that minimizes a convex and \emph{linearized} surrogate of {\tt RP-Regret} at each iteration; (iii) one that directly minimizes {\tt RP-Regret} when opponents change strategies slowly. Furthermore, when all players can run algorithms to minimize the {\tt RP-Regret} (or its linearized variant), certain subgame perfect equilibria of the repeated game can be learned. We also provide experiments showing that minimizing our regret notions can lead to more cooperative solutions with higher utility in games such as Stag-Hunt.
• Abstract（参考訳）: 本稿では,プレイ履歴に基づいて応答可能な<emph{adaptive>対戦相手との繰り返しゲームにおける後悔の最小化について検討する。 オンライン学習における'emph{external regret}'の標準的な測定基準は、そのような適応性を捉えるのに失敗することが知られている。 プレイヤーの反ファクト的推論を考慮し,ゲーム理論において,すべてのプレイヤーがプレイの歴史に適応できる場合に,蓄積されたユーティリティである「emph{realized}」と「emph{best-in-hindsight}」の差を計測する「itt Repeated Policy Regret」(RP-Regret)を導入する。 この設定における既存の後悔の概念と比較すると、我々の考え方は繰り返しのゲームプレイに固有のものであり、より強いコンパレータや対戦相手を少ない制約で可能にしつつ、全てのプレイヤーが最小限にした場合により良い均衡を見出す可能性を維持している。 まず, プレイヤーの反則的戦略の相違, コンパレータと対戦相手の戦略の記憶の相違について, 時間内でのRP-Regretのサブリニア獲得に必要な条件を同定する。 次に、戦略空間における定義 \emph{non-convex} である {\tt RP-Regret} を最小化する追加条件と証明可能なアルゴリズムについて検討する。 この課題に対処するため,我々は3つのアルゴリズムを提案する。 一 オンライン非凸学習における先行研究にいうように、最適化託宣に基づくもの (ii)各反復におけるtt RP-Regret の凸と \emph{linearized} の代理を最小化するもの 三 相手が戦略をゆっくり変更するとき、直接RP-Regretを最小化するもの。 さらに、全てのプレイヤーがアルゴリズムを実行して {\tt RP-Regret}(またはその線形化変種)を最小化できる場合、繰り返しゲームのある種のサブゲーム完全平衡が学習される。 また、残念な概念を最小化することで、Stag-Huntのようなゲームにおいて、より高いユーティリティを持つより協力的なソリューションが生まれることを示す実験も提供します。

関連論文リスト

• 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)
• Is Learning in Games Good for the Learners? [14.781100349601587]
  2人のエージェント間の繰り返しのゲームプレイにおいて、報酬と後悔の間のトレードオフを考慮する。 このような平衡は、任意の相手に対する後悔の保証を維持するアルゴリズムのペアによって到達可能であることを示す。 また,ゲーム開始時において,未学習エージェントとの繰り返しプレイを通じて報酬-最適戦略を学習する問題についても検討する。
  論文  参考訳（メタデータ） (2023-05-31T02:10:27Z)
• On the Convergence of No-Regret Learning Dynamics in Time-Varying Games [89.96815099996132]
  時間変化ゲームにおける楽観的勾配降下(OGD)の収束を特徴付ける。 我々のフレームワークは、ゼロサムゲームにおけるOGDの平衡ギャップに対して鋭い収束境界をもたらす。 また,静的ゲームにおける動的後悔の保証に関する新たな洞察も提供する。
  論文  参考訳（メタデータ） (2023-01-26T17:25:45Z)
• Near-Optimal No-Regret Learning for General Convex Games [121.50979258049135]
  一般凸およびコンパクト戦略集合に対して後悔が得られることを示す。 我々の力学は、適度にエンハンリフトされた空間上の楽観的な従順化バウンドのインスタンス化にある。 先行結果が適用される特殊な場合であっても、我々のアルゴリズムは最先端の後悔よりも改善される。
  論文  参考訳（メタデータ） (2022-06-17T12:58:58Z)
• Complete Policy Regret Bounds for Tallying Bandits [51.039677652803675]
  政策後悔は、適応的な敵に対してオンライン学習アルゴリズムのパフォーマンスを測定するという、よく確立された概念である。 我々は,不完全な政策後悔を効果的に最小化できる敵の制限について検討する。 我々は、$tildemathcalO(mKsqrtT)$の完全なポリシーを後悔するアルゴリズムを提供し、$tildemathcalO$表記は対数要素だけを隠す。
  論文  参考訳（メタデータ） (2022-04-24T03:10:27Z)
• Online Multiobjective Minimax Optimization and Applications [14.699969822572308]
  本稿では,適応的な対戦相手が新しいゲームを導入する,シンプルだが汎用的なオンライン学習フレームワークを提案する。 学習者のゴールは、累積ベクトル値損失の最大座標を最小化することである。 対戦相手がまず行動を発表しなければならない設定と競合する簡単なアルゴリズムを提供する。 最適なアルゴリズムと境界を回復して、外部の後悔、内部の後悔、適応的な後悔、多集団の後悔、その後の後悔、睡眠専門家の設定における後悔の概念を最小化できます。
  論文  参考訳（メタデータ） (2021-08-09T06:52:08Z)
• Model-Free Online Learning in Unknown Sequential Decision Making Problems and Games [114.90723492840499]
  大規模な2人プレイのゼロサム情報ゲームでは、反事実後悔最小化(cfr)の現代的な拡張がnash均衡を計算するための実用的な技術である。 私たちは、戦略空間がエージェントに知られていないオンライン学習設定を形式化します。 エージェントが逆の環境に直面しても、その設定に高い確率で$O(T3/4)$後悔を達成する効率的なアルゴリズムを提供します。
  論文  参考訳（メタデータ） (2021-03-08T04:03:24Z)

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

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