論文の概要: Near-Optimal $\sqrt{K}$-Regret for Online Learning in Uninformed Markov Games

• arxiv url: http://arxiv.org/abs/2611.01649v1
• Date: Sun, 01 Nov 2026 06:56:08 GMT
• ステータス: 情報取得中
• システム内更新日: 2026-11-03 19:24:39.361085
• Title: Near-Optimal $\sqrt{K}$-Regret for Online Learning in Uninformed Markov Games
• Title（参考訳）: マルコフゲームにおけるオンライン学習のための準最適$\sqrt{K}$-regret
• Abstract要約: オンライン学習を2人プレイのマルコフゲームで学習する。 相手は各エピソードで任意の未知のポリシーに従うことができ、学習者は相手の行動を観察しない。 我々は,相手のポリシーに対して,$widetildeO(H3/2SsqrtAK)$ empirical Nash-value regretを実現するアルゴリズムを開発した。
• 参考スコア（独自算出の注目度）: 54.274028560515454
• License:
• Abstract: We study online learning in two-player uninformed Markov games, where the opponent may follow an arbitrary, unknown policy in each episode and the learner does not observe the opponent's actions. [TWYS21] showed that achieving sublinear external regret requires an exponential dependence on the episode length $H$. Motivated by this limitation, they studied the weaker notion of Nash-value regret and obtained an $\widetilde{O}(K^{2/3})$ regret bound, where $K$ is the number of episodes. More recently, [LLZR26] introduced a stronger notion called empirical Nash-value regret and achieved an $\widetilde{O}(\sqrt{K})$ bound when the opponent's non-stationarity is moderate, including the case where the opponent follows a fixed policy. However, whether the $\sqrt{K}$ rate is achievable in the worst case remained open. In this paper, we resolve this open question by developing an algorithm that achieves $\widetilde{O}(H^{3/2}S\sqrt{AK})$ empirical Nash-value regret against arbitrary opponent policies, where $S$ is the number of states and $A$ is the number of learner's actions. Specifically, our algorithm combines global and local planning by maintaining a collection of candidate predictions of future losses, each associated with a policy. Global planning learns which candidates to favor across episodes, while local planning combines their policies differently at each state to make decisions. A key ingredient is to coordinate these two components to control the discrepancy between local loss estimates and the total loss of the executed policy, using only the learner's observed trajectories.
• Abstract（参考訳）: 対戦相手は各エピソードにおいて任意の未知のポリシーに従うことができ、学習者は相手の行動を観察しない。 [TWYS21] は, サブリニアな外部後悔を達成するにはエピソードの長さに指数関数的依存を必要とすることを示した。 この制限によって、彼らはナッシュ値の後悔というより弱い概念を研究し、$\widetilde{O}(K^{2/3})$ regret bound、ここで$K$はエピソードの数である。 より最近では [LLZR26] は経験的ナッシュ値後悔という強い概念を導入し、相手の非定常性が適度であれば$\widetilde{O}(\sqrt{K})$boundを達成した。 しかし、最悪の場合、$\sqrt{K}$レートが達成可能であるかどうかは未解決のままである。 本稿では,このオープンな問題を,$\widetilde{O}(H^{3/2}S\sqrt{AK})$ empirical Nash-value regret against any opponent policy, where $S$ is the number of state and $A$ is the number of learner's action。 具体的には,このアルゴリズムは,将来的な損失予測の集合を,それぞれがポリシーに関連付けることによって,グローバルな計画とローカルな計画を組み合わせる。 グローバルプランニングはエピソードを通じてどの候補者を好むかを学ぶが、地域プランニングは各州で異なる政策を組み合わせて意思決定を行う。 鍵となる要素は、これらの2つのコンポーネントを調整し、学習者の観察された軌跡のみを用いて、局所的な損失推定と実行されたポリシーの総損失との相違を制御することである。

関連論文リスト

• Fast Last-Iterate Convergence in Zero-Sum Markov Games with Bandit Feedback [14.692647465985916]
  未知の2プレイヤーゼロサム割引マルコフゲームにおけるラストイテレート収束を帯域フィードバックで検討した。 適応正規化TD学習(ARTD)を開発し、現在のポリシーに縛られた$widetildemathcalO(t-1/4)$ duality gapを実現する。 我々は、ログバリアの正規化を価値推定の進捗に適応させ、学習を通してポリシーと価値のエラーを制御します。
  論文  参考訳（メタデータ） (2026-10-05T08:20:13Z)
• Polylogarithmic Nash Regret in Matrix Games with Bandit Feedback [14.692647465985916]
  バンド利得フィードバックによる未知有限行列ゲームにおけるナッシュの後悔について検討し、相手の動作を観察した。 我々は、インスタンス依存の$mathcalO(log2 T)$ナッシュ後悔を実現するOPB(Optimistic Payoff Balancing)を開発する。
  論文  参考訳（メタデータ） (2026-09-28T10:13:59Z)
• Online Learning for Uninformed Markov Games: Empirical Nash-Value Regret and Non-Stationarity Adaptation [54.274028560515454]
  対戦相手の行動や方針が守られない2人プレイヤのマルコフゲームにおいて,オンライン学習を学習する。 経験的ナッシュバリュー後悔は,ナッシュバリュー後悔よりも強く,新たな後悔の概念である。 我々は,このアルゴリズムを,相手の潜在的非定常性に応じて適切な$で適応的に再起動する方法を示す。
  論文  参考訳（メタデータ） (2026-02-06T21:25:54Z)
• 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)
• Complete Policy Regret Bounds for Tallying Bandits [51.039677652803675]
  政策後悔は、適応的な敵に対してオンライン学習アルゴリズムのパフォーマンスを測定するという、よく確立された概念である。 我々は,不完全な政策後悔を効果的に最小化できる敵の制限について検討する。 我々は、$tildemathcalO(mKsqrtT)$の完全なポリシーを後悔するアルゴリズムを提供し、$tildemathcalO$表記は対数要素だけを隠す。
  論文  参考訳（メタデータ） (2022-04-24T03:10:27Z)
• Minimax Regret for Stochastic Shortest Path [63.45407095296692]
  我々は、エージェントが最小の総予想コストで目標状態に達する必要がある最短パス(SSP)問題を研究します。 この設定に対するminimaxの後悔は、$widetilde O(B_star sqrt|S| |A|K)$であり、$B_star$は任意の状態から最適なポリシーの予想コストに拘束されることを示しています。 本アルゴリズムは, 有限水平MDPにおける強化学習の新たな削減を基礎として, エピソードごとのインタイム動作を行う。
  論文  参考訳（メタデータ） (2021-03-24T10:11:49Z)

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

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