論文の概要: A Self-Play Posterior Sampling Algorithm for Zero-Sum Markov Games

• arxiv url: http://arxiv.org/abs/2210.01907v1
• Date: Tue, 4 Oct 2022 21:08:26 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-06 13:34:58.781798
• Title: A Self-Play Posterior Sampling Algorithm for Zero-Sum Markov Games
• Title（参考訳）: ゼロサムマルコフゲームのためのセルフプレイ後続サンプリングアルゴリズム
• Authors: Wei Xiong, Han Zhong, Chengshuai Shi, Cong Shen, Tong Zhang
• Abstract要約: 本研究は,多くの包帯および強化学習環境において祝われる,後方サンプリングの異なるアプローチに焦点を当てる。 エピソディックな2プレーヤゼロサムMGに対して,一般関数近似を用いた新しい後方サンプリングアルゴリズムを開発した。 我々の知る限りでは、このアルゴリズムはMGに対して、頻繁な後悔の保証を持つ最初の効率の良い後部サンプリングアルゴリズムである。
• 参考スコア（独自算出の注目度）: 28.227468574464094
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Existing studies on provably efficient algorithms for Markov games (MGs) almost exclusively build on the "optimism in the face of uncertainty" (OFU) principle. This work focuses on a different approach of posterior sampling, which is celebrated in many bandits and reinforcement learning settings but remains under-explored for MGs. Specifically, for episodic two-player zero-sum MGs, a novel posterior sampling algorithm is developed with general function approximation. Theoretical analysis demonstrates that the posterior sampling algorithm admits a $\sqrt{T}$-regret bound for problems with a low multi-agent decoupling coefficient, which is a new complexity measure for MGs, where $T$ denotes the number of episodes. When specialized to linear MGs, the obtained regret bound matches the state-of-the-art results. To the best of our knowledge, this is the first provably efficient posterior sampling algorithm for MGs with frequentist regret guarantees, which enriches the toolbox for MGs and promotes the broad applicability of posterior sampling.
• Abstract（参考訳）: マルコフゲーム(MG)の証明可能な効率的なアルゴリズムに関する研究は、ほぼ独占的に「不確実性に直面した最適化」(OFU)原理に基づいている。 本研究は,多くのバンドイットや強化学習設定で祝われる後方サンプリングの異なるアプローチに焦点をあてるが,MGには未探索のままである。 具体的には, 2-player 0-sum MG に対して, 一般関数近似を用いた新しい後方サンプリングアルゴリズムを開発した。 理論的解析により、後方サンプリングアルゴリズムは、mgsの新しい複雑性尺度である低マルチエージェントデカップリング係数の問題に対して、$\sqrt{t}$-regretバインドを認め、$t$はエピソード数を表す。 線形MGに特化すると、得られた後悔境界は最先端の結果と一致する。 我々の知る限り、このアルゴリズムはMGのためのツールボックスを充実させ、後方サンプリングの幅広い適用性を促進する、頻繁な後悔の保証を持つMGに対する最初の証明可能な効率の良い後方サンプリングアルゴリズムである。

関連論文リスト

• More Efficient Randomized Exploration for Reinforcement Learning via Approximate Sampling [41.21199687865359]
  最近提案されたFeel-Good Thompson Sampling (FGTS) アプローチを用いて,様々な近似サンプリング手法を組み込んだアルゴリズムフレームワークを提案する。 我々の後悔分析は、既存のランダム化アルゴリズムを超越した次元性への後悔の最もよく知られた依存性をもたらす。 我々のアルゴリズムは、RLの深い文献から得られる他の強いベースラインに匹敵する、あるいは同等の性能を達成する。
  論文  参考訳（メタデータ） (2024-06-18T03:32:10Z)
• Provably Efficient Information-Directed Sampling Algorithms for Multi-Agent Reinforcement Learning [50.92957910121088]
  本研究は,情報指向サンプリング(IDS)の原理に基づくマルチエージェント強化学習(MARL)のための新しいアルゴリズムの設計と解析を行う。 エピソディックな2プレーヤゼロサムMGに対して、ナッシュ平衡を学習するための3つのサンプル効率アルゴリズムを提案する。 我々は、Reg-MAIDSをマルチプレイヤー汎用MGに拡張し、ナッシュ平衡または粗相関平衡をサンプル効率良く学習できることを証明する。
  論文  参考訳（メタデータ） (2024-04-30T06:48:56Z)
• Posterior Sampling for Competitive RL: Function Approximation and Partial Observation [96.73342437947014]
  我々は,ゼロサムマルコフゲーム(MG)に焦点をあてる。 そこで本研究では,両プレイヤーがナッシュ平衡を学習するためのモデルベース自己再生後サンプリング手法を提案する。 本稿では,潜在的な部分観測可能性を持つ逆MG学習のためのモデルに基づく後部サンプリング手法を提案する。
  論文  参考訳（メタデータ） (2023-10-30T17:59:26Z)
• Quantized Compressed Sensing with Score-Based Generative Models [6.066320781596792]
  我々は、SGM(QCS-SGM)を用いた量子化圧縮センシングと呼ばれる教師なしのデータ駆動方式を提案する。 提案したQCS-SGMは、分布内および分布外の両方において、既存の最先端アルゴリズムよりも大幅に優れている。 後部サンプリング法として、QCS-SGMは、再構成結果の信頼区間や不確実性推定を得るために容易に使用できる。
  論文  参考訳（メタデータ） (2022-11-02T15:19:07Z)
• SNIPS: Solving Noisy Inverse Problems Stochastically [25.567566997688044]
  本稿では,線形逆問題の後部分布からサンプルを抽出するSNIPSアルゴリズムを提案する。 我々の解はランゲヴィン力学とニュートン法からのアイデアを取り入れ、事前訓練された最小二乗誤差(MMSE)を利用する。 得られたサンプルは、与えられた測定値と鋭く、詳細で一致しており、それらの多様性は、解決される逆問題に固有の不確実性を明らかにする。
  論文  参考訳（メタデータ） (2021-05-31T13:33:21Z)
• Plug-And-Play Learned Gaussian-mixture Approximate Message Passing [71.74028918819046]
  そこで本研究では,従来のi.i.d.ソースに適した圧縮圧縮センシング(CS)リカバリアルゴリズムを提案する。 我々のアルゴリズムは、Borgerdingの学習AMP(LAMP)に基づいて構築されるが、アルゴリズムに普遍的な復調関数を採用することにより、それを大幅に改善する。 数値評価により,L-GM-AMPアルゴリズムは事前の知識を必要とせず,最先端の性能を実現する。
  論文  参考訳（メタデータ） (2020-11-18T16:40:45Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• On Thompson Sampling with Langevin Algorithms [106.78254564840844]
  多武装バンディット問題に対するトンプソンサンプリングは理論と実践の両方において良好な性能を享受する。 計算上のかなりの制限に悩まされており、反復ごとに後続分布からのサンプルを必要とする。 本稿では,この問題に対処するために,トンプソンサンプリングに適した2つのマルコフ連鎖モンテカルロ法を提案する。
  論文  参考訳（メタデータ） (2020-02-23T22:35:29Z)
• Thompson Sampling Algorithms for Mean-Variance Bandits [97.43678751629189]
  我々は平均分散MABのためのトンプソンサンプリング型アルゴリズムを開発した。 我々はまた、ガウシアンとベルヌーイの盗賊に対する包括的後悔の分析も提供する。 我々のアルゴリズムは、全てのリスク許容度に対して既存のLCBベースのアルゴリズムを著しく上回っている。
  論文  参考訳（メタデータ） (2020-02-01T15:33:50Z)

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

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