論文の概要: Online Learning in Unknown Markov Games

• arxiv url: http://arxiv.org/abs/2010.15020v2
• Date: Sat, 6 Feb 2021 05:24:25 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-02 04:54:57.544529
• Title: Online Learning in Unknown Markov Games
• Title（参考訳）: マルコフゲームにおけるオンライン学習
• Authors: Yi Tian, Yuanhao Wang, Tiancheng Yu, Suvrit Sra
• Abstract要約: 未知のマルコフゲームでオンライン学習を学ぶ。 後方視における最良の反応に対するサブ線形後悔の達成は統計的に困難であることを示す。 サブ線形$tildemathcalO(K2/3)$ regretを$K$のエピソード後に達成するアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 55.07327246187741
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study online learning in unknown Markov games, a problem that arises in episodic multi-agent reinforcement learning where the actions of the opponents are unobservable. We show that in this challenging setting, achieving sublinear regret against the best response in hindsight is statistically hard. We then consider a weaker notion of regret by competing with the \emph{minimax value} of the game, and present an algorithm that achieves a sublinear $\tilde{\mathcal{O}}(K^{2/3})$ regret after $K$ episodes. This is the first sublinear regret bound (to our knowledge) for online learning in unknown Markov games. Importantly, our regret bound is independent of the size of the opponents' action spaces. As a result, even when the opponents' actions are fully observable, our regret bound improves upon existing analysis (e.g., (Xie et al., 2020)) by an exponential factor in the number of opponents.
• Abstract（参考訳）: 我々は,未知のマルコフゲームにおいてオンライン学習を研究する。これは,対戦者の行動が観察不能なエピソード多エージェント強化学習において生じる問題である。 この困難な状況下では,後見の最良の反応に対する下位線形後悔の達成は統計的に困難である。 すると、ゲームの \emph{minimax value} と競合して後悔というより弱い概念を考え、K$のエピソードの後、サブ線形$\tilde{\mathcal{O}}(K^{2/3})$後悔を達成するアルゴリズムを提案する。 これは、未知のマルコフゲームでオンライン学習に(我々の知識に)結びつく最初のサブリニアな後悔である。 重要なのは、我々の後悔は相手のアクションスペースの大きさとは無関係である。 その結果、相手の行動が完全に観察可能であったとしても、既存の分析(例えば、Xie et al., 2020)を相手数の指数関数的因子によって改善する。

関連論文リスト

• Learning in Markov Games with Adaptive Adversaries: Policy Regret, Fundamental Barriers, and Efficient Algorithms [24.928268203611047]
  学習者と戦略的相手とのマルコフゲームとしてモデル化された動的に進化する環境における学習について検討する。 これは、学習者が最も安定した政策の順序に従えば達成したであろうリターンと競合することを目的とした、反ファクト的な概念である。
  論文  参考訳（メタデータ） (2024-11-01T16:17:27Z)
• Is Learning in Games Good for the Learners? [14.781100349601587]
  2人のエージェント間の繰り返しのゲームプレイにおいて、報酬と後悔の間のトレードオフを考慮する。 このような平衡は、任意の相手に対する後悔の保証を維持するアルゴリズムのペアによって到達可能であることを示す。 また,ゲーム開始時において,未学習エージェントとの繰り返しプレイを通じて報酬-最適戦略を学習する問題についても検討する。
  論文  参考訳（メタデータ） (2023-05-31T02:10:27Z)
• Online Learning in Stackelberg Games with an Omniscient Follower [83.42564921330896]
  オンライン学習の課題を2人のプレイヤーによる分散協調型Stackelbergゲームで検討する。 各ラウンドで、まずリーダーが行動を起こし、次にリーダーの動きを観察した後に行動を起こすフォロワーが続く。 報酬構造によっては、全能なフォロワーの存在が、サンプルの複雑さを大きく変える可能性があることを示す。
  論文  参考訳（メタデータ） (2023-01-27T03:35:10Z)
• No-Regret Learning in Time-Varying Zero-Sum Games [99.86860277006318]
  固定ゼロサムゲームにおける繰り返しプレイからの学習は、ゲーム理論とオンライン学習における古典的な問題である。 提案手法は,3つの性能基準の下で,良好な保証を同時に享受できる1つのパラメータフリーアルゴリズムである。 本アルゴリズムは,ある特性を満たすブラックボックスベースラーナー群に対するメタアルゴリズムを用いた2層構造に基づく。
  論文  参考訳（メタデータ） (2022-01-30T06:10:04Z)
• 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)
• Learning to Play Sequential Games versus Unknown Opponents [93.8672371143881]
  学習者が最初にプレーするゲームと、選択した行動に反応する相手との連続的なゲームについて考察する。 対戦相手の対戦相手列と対戦する際,学習者に対して新しいアルゴリズムを提案する。 我々の結果には、相手の反応の正則性に依存するアルゴリズムの後悔の保証が含まれている。
  論文  参考訳（メタデータ） (2020-07-10T09:33:05Z)
• Matrix games with bandit feedback [33.637621576707076]
  本研究では,古典的ゼロサム行列ゲームのバージョンを,未知のペイオフ行列と帯域幅フィードバックを用いて検討する。 我々は、トンプソンがこの設定で破滅的に失敗し、既存のアルゴリズムと経験的な比較を行うことを示した。
  論文  参考訳（メタデータ） (2020-06-09T09:36:21Z)
• Provable Self-Play Algorithms for Competitive Reinforcement Learning [48.12602400021397]
  我々はマルコフゲームの設定の下で、競争力強化学習における自己プレイについて研究する。 自己再生アルゴリズムは、ゲームのT$ステップをプレイした後、後悔の$tildemathcalO(sqrtT)$を達成する。 また, 最悪の場合においても, 時間内に実行可能であることを保証し, 若干悪い後悔を招き, エクスプロイトスタイルのアルゴリズムも導入する。
  論文  参考訳（メタデータ） (2020-02-10T18:44:50Z)

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

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