論文の概要: Gap-Dependent Bounds for Two-Player Markov Games

• arxiv url: http://arxiv.org/abs/2107.00685v1
• Date: Thu, 1 Jul 2021 18:25:07 GMT
• ステータス: 処理完了
• システム内更新日: 2021-07-05 13:02:06.603425
• Title: Gap-Dependent Bounds for Two-Player Markov Games
• Title（参考訳）: 2プレーヤマルコフゲームにおけるギャップ依存境界
• Authors: Zehao Dou, Zhuoran Yang, Zhaoran Wang, Simon S.Du
• Abstract要約: 2-TBSGによる2プレイヤーターン型マルコフゲームにおけるナッシュラーニングアルゴリズムの実行時の累積的後悔の分析 この境界は対数項のみの理論的な下界と一致する。 我々は、無限の地平線でディスカウントされたゲーム設定に結論を拡張し、同様のギャップ依存対数後悔境界を提案する。
• 参考スコア（独自算出の注目度）: 122.20541282562363
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: As one of the most popular methods in the field of reinforcement learning, Q-learning has received increasing attention. Recently, there have been more theoretical works on the regret bound of algorithms that belong to the Q-learning class in different settings. In this paper, we analyze the cumulative regret when conducting Nash Q-learning algorithm on 2-player turn-based stochastic Markov games (2-TBSG), and propose the very first gap dependent logarithmic upper bounds in the episodic tabular setting. This bound matches the theoretical lower bound only up to a logarithmic term. Furthermore, we extend the conclusion to the discounted game setting with infinite horizon and propose a similar gap dependent logarithmic regret bound. Also, under the linear MDP assumption, we obtain another logarithmic regret for 2-TBSG, in both centralized and independent settings.
• Abstract（参考訳）: 強化学習の分野における最も一般的な方法の1つとして,q-learningが注目されている。 近年、異なる設定でQラーニングクラスに属するアルゴリズムの残念な境界について、より理論的研究がなされている。 本稿では,2-player turn-based stochastic markov games (2-tbsg) 上でnash q-learningアルゴリズムを実行する際の累積的後悔を分析し,エピソディック表環境における最初のギャップ依存対数上限を提案する。 この境界は対数項のみの理論的な下界と一致する。 さらに,この結論を無限地平線による割引ゲームに拡張し,同様のギャップ依存の対数的後悔境界を提案する。 また, 線形 MDP 仮定の下では, 2-TBSG に対して, 集中的, 独立的な設定で別の対数的後悔が生じる。

関連論文リスト

• Double Successive Over-Relaxation Q-Learning with an Extension to Deep Reinforcement Learning [0.0]
  逐次的過剰緩和(SOR)Q-ラーニングは、収束をスピードアップする緩和因子を導入し、2つの大きな制限がある。 サンプルベースでモデルなしのダブルSORQ学習アルゴリズムを提案する。 提案アルゴリズムは深部RLを用いて大規模問題に拡張される。
  論文  参考訳（メタデータ） (2024-09-10T09:23:03Z)
• Online Learning and Solving Infinite Games with an ERM Oracle [20.1330044382824]
  本稿では,ERMオーラクルコールのみに依存するオンラインバイナリ分類設定のためのアルゴリズムを提案する。 我々は、実現可能な設定における有限の後悔と、不可知的な設定におけるサブリニアに成長する後悔が示される。 我々のアルゴリズムは二値ゲームと実値ゲームの両方に適用でき、大きなゲームを解く実践において、二重オラクルと多重オラクルのアルゴリズムを広く活用するための正当性を提供すると見なすことができる。
  論文  参考訳（メタデータ） (2023-07-04T12:51:21Z)
• On the Convergence of No-Regret Learning Dynamics in Time-Varying Games [89.96815099996132]
  時間変化ゲームにおける楽観的勾配降下(OGD)の収束を特徴付ける。 我々のフレームワークは、ゼロサムゲームにおけるOGDの平衡ギャップに対して鋭い収束境界をもたらす。 また,静的ゲームにおける動的後悔の保証に関する新たな洞察も提供する。
  論文  参考訳（メタデータ） (2023-01-26T17:25:45Z)
• Decentralized model-free reinforcement learning in stochastic games with average-reward objective [1.9852463786440127]
  本アルゴリズムは,次数$T3/4$のサブ線形高確率後悔と次数$T2/3$のサブ線形高確率後悔を実現する。 本アルゴリズムは,従来の手法に比べて計算量が少なく,メモリスペースも少ない。
  論文  参考訳（メタデータ） (2023-01-13T15:59:53Z)
• Learning Two-Player Mixture Markov Games: Kernel Function Approximation and Correlated Equilibrium [157.0902680672422]
  非線形関数近似を用いた2プレイヤーゼロサムマルコフゲームにおけるナッシュ平衡の学習について検討する。 双対性ギャップを最小化してナッシュ均衡を求める新しいオンライン学習アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-08-10T14:21:54Z)
• The Best of Both Worlds: Reinforcement Learning with Logarithmic Regret and Policy Switches [84.54669549718075]
  漸進的強化学習(RL)における後悔の最小化問題について検討する。 一般関数クラスと一般モデルクラスで学ぶことに集中する。 対数的後悔境界は$O(log T)$スイッチングコストのアルゴリズムによって実現可能であることを示す。
  論文  参考訳（メタデータ） (2022-03-03T02:55:55Z)
• Damped Online Newton Step for Portfolio Selection [96.0297968061824]
  古典的なオンラインポートフォリオ選択の問題を再考し、各ラウンドで学習者がポートフォリオの集合上の分布を選択し、その富を割り当てる。 この問題に対する対数的後悔を達成する既存のアルゴリズムは、ラウンドの総数とスケールする時間と空間の複雑さがある。 対数的後悔を伴う最初の実用的オンラインポートフォリオ選択アルゴリズムを提示し、その時間と空間の複雑さは水平線上で対数的にのみ依存する。
  論文  参考訳（メタデータ） (2022-02-15T17:01:55Z)
• Near-Optimal No-Regret Learning for Correlated Equilibria in Multi-Player General-Sum Games [104.74734408204749]
  マルチプレイヤーの汎用正規形式ゲームにおいて,OMWU(Optimistic Multiplicative Weights Update)を用いているエージェントが全員,O(textrmpolylog(T))$(T$)$(T$)$(OMWU)$(OMWU)$(OMWU)$(OMWU)$(OMWU)$)であることを示す。 外部の後悔から内部の後悔へと結果を拡張し、後悔を交換することで、近似した平衡に収束する非結合学習ダイナミクスを確立する。
  論文  参考訳（メタデータ） (2021-11-11T01:19:53Z)
• Near-Linear Time Algorithm with Near-Logarithmic Regret Per Switch for Mixable/Exp-Concave Losses [0.0]
  動的環境における対数的静的後悔を伴う混合損失関数のオンライン最適化について検討する。 文献では,スイッチ1回あたりのほぼ対数的後悔を1時間あたりのポリノミカルな複雑さで達成できることが確認できた。
  論文  参考訳（メタデータ） (2021-09-28T15:06:31Z)

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

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