論文の概要: Online Learning for Uninformed Markov Games: Empirical Nash-Value Regret and Non-Stationarity Adaptation

• arxiv url: http://arxiv.org/abs/2602.07205v1
• Date: Fri, 06 Feb 2026 21:25:54 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-10 20:26:24.503998
• Title: Online Learning for Uninformed Markov Games: Empirical Nash-Value Regret and Non-Stationarity Adaptation
• Title（参考訳）: マルコフゲームのためのオンライン学習:経験的ナッシュバリューレグレットと非定常適応
• Authors: Junyan Liu, Haipeng Luo, Zihan Zhang, Lillian J. Ratliff,
• Abstract要約: 対戦相手の行動や方針が守られない2人プレイヤのマルコフゲームにおいて,オンライン学習を学習する。 経験的ナッシュバリュー後悔は,ナッシュバリュー後悔よりも強く,新たな後悔の概念である。 我々は,このアルゴリズムを,相手の潜在的非定常性に応じて適切な$で適応的に再起動する方法を示す。
• 参考スコア（独自算出の注目度）: 54.274028560515454
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study online learning in two-player uninformed Markov games, where the opponent's actions and policies are unobserved. In this setting, Tian et al. (2021) show that achieving no-external-regret is impossible without incurring an exponential dependence on the episode length $H$. They then turn to the weaker notion of Nash-value regret and propose a V-learning algorithm with regret $O(K^{2/3})$ after $K$ episodes. However, their algorithm and guarantee do not adapt to the difficulty of the problem: even in the case where the opponent follows a fixed policy and thus $O(\sqrt{K})$ external regret is well-known to be achievable, their result is still the worse rate $O(K^{2/3})$ on a weaker metric. In this work, we fully address both limitations. First, we introduce empirical Nash-value regret, a new regret notion that is strictly stronger than Nash-value regret and naturally reduces to external regret when the opponent follows a fixed policy. Moreover, under this new metric, we propose a parameter-free algorithm that achieves an $O(\min \{\sqrt{K} + (CK)^{1/3},\sqrt{LK}\})$ regret bound, where $C$ quantifies the variance of the opponent's policies and $L$ denotes the number of policy switches (both at most $O(K)$). Therefore, our results not only recover the two extremes -- $O(\sqrt{K})$ external regret when the opponent is fixed and $O(K^{2/3})$ Nash-value regret in the worst case -- but also smoothly interpolate between these extremes by automatically adapting to the opponent's non-stationarity. We achieve so by first providing a new analysis of the epoch-based V-learning algorithm by Mao et al. (2022), establishing an $O(ηC + \sqrt{K/η})$ regret bound, where $η$ is the epoch incremental factor. Next, we show how to adaptively restart this algorithm with an appropriate $η$ in response to the potential non-stationarity of the opponent, eventually achieving our final results.
• Abstract（参考訳）: 対戦相手の行動や方針が守られない2人プレイヤのマルコフゲームにおいて,オンライン学習を学習する。 この設定では、Tian et al (2021) は、エピソードの長さに指数関数的な依存を伴わずに、外部回帰を達成することは不可能であることを示した。 すると、より弱いナッシュ値の後悔の概念に目を向け、後悔する$O(K^{2/3})$の後に$K$のV学習アルゴリズムを提案する。 しかし、それらのアルゴリズムと保証は問題の難しさに適応しない:例えば、相手が固定されたポリシーに従えば、$O(\sqrt{K})$外部後悔は達成可能であることはよく知られているが、それでもより弱い計量上では$O(K^{2/3})$よりも悪いレートである。 この作業では、両方の制限に完全に対処します。 まず,経験的ナッシュ・バリュー・後悔を導入する。これはナッシュ・バリュー・後悔よりも強く,相手が一定の方針に従えば自然に外部の後悔に還元される新しい後悔概念である。 さらに、この新たな計量の下では、$O(\min \{\sqrt{K} + (CK)^{1/3},\sqrt{LK}\})$ regret bound, ここで、$C$は相手のポリシーの分散を定量化し、$L$はポリシースイッチの数を表す(両方とも$O(K)$である)。 したがって、この結果は、相手が固定されたときの外部後悔$O(\sqrt{K})と、最悪の場合のナッシュ値後悔$O(K^{2/3})という2つの極小を回復するだけでなく、相手の非定常性に自動的に適応することで、これらの極小をスムーズに補間する。 まず Mao et al (2022) によるエポックベースのV-ラーニングアルゴリズムの新しい解析を行い、O(ηC + \sqrt{K/η})$ regret bound, ここで$η$はエポックインクリメンタルファクタである。 次に,提案アルゴリズムを適切な$η$で適応的に再起動する方法を示す。

関連論文リスト

• Convergence of Regret Matching in Potential Games and Constrained Optimization [85.55969013318627]
  RM$+$の交互収束は、$O_epsilon (1/epsilon4)$の後に$Epsilon$-KKT点に収束し、それが音で高速な一階数であることを示す。 我々の下界は、ポテンシャルゲームにおける粗相関平衡への収束が、ナッシュ平衡への収束よりも指数関数的に速いことを示している。
  論文  参考訳（メタデータ） (2025-10-20T00:45:47Z)
• Instance-Dependent Regret Bounds for Learning Two-Player Zero-Sum Games with Bandit Feedback [60.610120215789976]
  純粋な戦略 ナッシュ均衡が存在するとき、$c$ は 0 となり、最適のインスタンス依存後悔境界となることを示す。 また,本アルゴリズムは最終段階の収束性も享受し,ほぼ最適サンプルを用いて純粋な戦略ナッシュ均衡を同定することができる。
  論文  参考訳（メタデータ） (2025-02-24T20:20:06Z)
• Near-optimal Regret Using Policy Optimization in Online MDPs with Aggregate Bandit Feedback [49.84060509296641]
  オンライン有限水平マルコフ決定過程を逆向きに変化した損失と総括的帯域幅フィードバック(フルバンド幅)を用いて研究する。 この種のフィードバックの下では、エージェントは、軌跡内の各中間段階における個々の損失よりも、軌跡全体に生じる総損失のみを観察する。 この設定のための最初のポリシー最適化アルゴリズムを紹介します。
  論文  参考訳（メタデータ） (2025-02-06T12:03:24Z)
• p-Mean Regret for Stochastic Bandits [52.828710025519996]
  単純で統一された UCB ベースのアルゴリズムを導入し、新しい$p$-mean の後悔境界を実現する。 我々の枠組みは、特別な場合として、平均的な累積的後悔とナッシュ後悔の両方を包含する。
  論文  参考訳（メタデータ） (2024-12-14T08:38:26Z)
• 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)
• Achieving Better Regret against Strategic Adversaries [15.51709428653595]
  本研究では,学習者が相手の行動について余分な知識を持つオンライン学習問題について検討する。 我々は,正規化リーダ(AFTRL)とProd-Best Response(Prod-BR)の2つの新しいオンライン学習アルゴリズムを提案する。 AFTRLは、外部の後悔に対して$O(1)$、または$O(1)$、遠回りの後悔に対して$O(1)$を達成する。
  論文  参考訳（メタデータ） (2023-02-13T19:34:36Z)
• The Best of Both Worlds: Reinforcement Learning with Logarithmic Regret and Policy Switches [84.54669549718075]
  漸進的強化学習(RL)における後悔の最小化問題について検討する。 一般関数クラスと一般モデルクラスで学ぶことに集中する。 対数的後悔境界は$O(log T)$スイッチングコストのアルゴリズムによって実現可能であることを示す。
  論文  参考訳（メタデータ） (2022-03-03T02:55:55Z)

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

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