論文の概要: RL en Markov Games with Independent Function Approximation: Improved Sample Complexity Bound under the Local Access Model

• arxiv url: http://arxiv.org/abs/2403.11544v1
• Date: Mon, 18 Mar 2024 07:54:11 GMT
• ステータス: 処理完了
• システム内更新日: 2024-03-19 16:16:57.306803
• Title: RL en Markov Games with Independent Function Approximation: Improved Sample Complexity Bound under the Local Access Model
• Title（参考訳）: RL en Markov Games with Independent Function Approximation: Improved Sample Complexity bound under the Local Access Model
• Authors: Junyi Fan, Yuxuan Han, Jialin Zeng, Jian-Feng Cai, Yang Wang, Yang Xiang, Jiheng Zhang,
• Abstract要約: シミュレータへの局所アクセスを伴う粗相関平衡(CCE)を学習するための新しいアルゴリズムLin-Confident-FTRLを導入する。 状態空間のサイズに対数的依存がある限り、Lin-Confident-FTRLは証明可能な最適精度で$O(epsilon-2)$で$epsilon$-CCEを学ぶ。 本分析は,単一エージェントのローカルプランニング文献における仮想ポリシー境界を一般化する。
• 参考スコア（独自算出の注目度）: 15.596599935486534
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Efficiently learning equilibria with large state and action spaces in general-sum Markov games while overcoming the curse of multi-agency is a challenging problem. Recent works have attempted to solve this problem by employing independent linear function classes to approximate the marginal $Q$-value for each agent. However, existing sample complexity bounds under such a framework have a suboptimal dependency on the desired accuracy $\varepsilon$ or the action space. In this work, we introduce a new algorithm, Lin-Confident-FTRL, for learning coarse correlated equilibria (CCE) with local access to the simulator, i.e., one can interact with the underlying environment on the visited states. Up to a logarithmic dependence on the size of the state space, Lin-Confident-FTRL learns $\epsilon$-CCE with a provable optimal accuracy bound $O(\epsilon^{-2})$ and gets rids of the linear dependency on the action space, while scaling polynomially with relevant problem parameters (such as the number of agents and time horizon). Moreover, our analysis of Linear-Confident-FTRL generalizes the virtual policy iteration technique in the single-agent local planning literature, which yields a new computationally efficient algorithm with a tighter sample complexity bound when assuming random access to the simulator.
• Abstract（参考訳）: マルチ緊急の呪いを克服しつつ、一般的なマルコフゲームにおいて、大きな状態と行動空間を持つ平衡を効果的に学習することは難しい問題である。 近年の研究では、各エージェントの限界値Q$-値を近似するために、独立線型関数クラスを用いてこの問題を解決しようとしている。 しかし、そのようなフレームワークの下の既存のサンプルの複雑さ境界は、所望の精度$\varepsilon$またはアクション空間に最適な依存関係を持つ。 本研究では,CCE(Carse correlation equilibria)をシミュレータにローカルアクセスして学習するための新しいアルゴリズムLin-Confident-FTRLを導入する。 状態空間のサイズに対数的依存がある限り、Lin-Confident-FTRLは証明可能な最適精度で$\epsilon$-CCEを学習し、関連する問題パラメータ(エージェントの数や時間水平線など)と多項式的にスケールしながら、アクション空間への線形依存を取り除く。 さらに,Linear-Confident-FTRLの解析は,シミュレータへのランダムアクセスを想定した場合,より厳密なサンプル複雑性を持つ計算効率の高いアルゴリズムを新たに生成する単一エージェントローカルプランニング文献において,仮想ポリシー反復手法を一般化する。

関連論文リスト

• Sample and Oracle Efficient Reinforcement Learning for MDPs with Linearly-Realizable Value Functions [10.225358400539719]
  本稿では,線形作用が特徴写像に一般化される決定法(MDP)の効率的な強化アルゴリズムを提案する。 具体的には、この設定において、最適に近いポリシーを効率的に見つける新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-09-07T14:38:05Z)
• The Power of Resets in Online Reinforcement Learning [73.64852266145387]
  ローカルシミュレータアクセス(あるいはローカルプランニング)を用いたオンライン強化学習を通してシミュレータのパワーを探求する。 カバー性が低いMPPは,Qstar$-realizabilityのみのサンプル効率で学習可能であることを示す。 ローカルシミュレーターアクセス下では, 悪名高いExogenous Block MDP問題が抽出可能であることを示す。
  論文  参考訳（メタデータ） (2024-04-23T18:09:53Z)
• Learning RL-Policies for Joint Beamforming Without Exploration: A Batch Constrained Off-Policy Approach [1.0080317855851213]
  本稿では,ネットワークにおけるパラメータキャンセル最適化の問題点について考察する。 探索と学習のために実世界でアルゴリズムをデプロイすることは、探索せずにデータによって達成できることを示す。
  論文  参考訳（メタデータ） (2023-10-12T18:36:36Z)
• Breaking the Curse of Multiagency: Provably Efficient Decentralized Multi-Agent RL with Function Approximation [44.051717720483595]
  本稿では,マルチ緊急近似の呪いを確実に解決するMARLアルゴリズムの1行について述べる。 より弱いバージョンのCCEを学習する代わりに、このアルゴリズムは一般的な関数近似の下で幅広い問題に適用される。 我々のアルゴリズムは常にMarkov CCEを出力し、最適レートは$widetildemathcalO(epsilon-2)$で$epsilon$-optimal Solutionを見つける。
  論文  参考訳（メタデータ） (2023-02-13T18:59:25Z)
• Near-optimal Policy Identification in Active Reinforcement Learning [84.27592560211909]
  AE-LSVI はカーネル化された最小二乗値 RL (LSVI) アルゴリズムの新しい変種であり、楽観主義と悲観主義を組み合わせて活発な探索を行う。 AE-LSVIは初期状態に対するロバスト性が必要な場合、様々な環境で他のアルゴリズムよりも優れていることを示す。
  論文  参考訳（メタデータ） (2022-12-19T14:46:57Z)
• On the Convergence of Heterogeneous Federated Learning with Arbitrary Adaptive Online Model Pruning [15.300983585090794]
  任意適応型オンラインモデルプルーニングを用いた異種FLアルゴリズムの一元化フレームワークを提案する。 特に、ある十分な条件下では、これらのアルゴリズムは一般的なスムーズなコスト関数に対して標準FLの定常点に収束する。 コンバージェンスに影響を与える2つの要因として,プルーニング誘導雑音と最小カバレッジ指数を照らす。
  論文  参考訳（メタデータ） (2022-01-27T20:43:38Z)
• Settling the Horizon-Dependence of Sample Complexity in Reinforcement Learning [82.31436758872715]
  我々は,環境相互作用の$O(1)$のエピソードのみを用いて,同一のPAC保証を実現するアルゴリズムを開発した。 値関数と有限水平マルコフ決定過程の接続を確立する。
  論文  参考訳（メタデータ） (2021-11-01T00:21:24Z)
• Online Sub-Sampling for Reinforcement Learning with General Function Approximation [111.01990889581243]
  本稿では,RLアルゴリズムによって収集されたデータポイントの情報取得量を測定する,効率的なオンラインサブサンプリングフレームワークを確立する。 複雑性バウンド関数クラスを持つ値ベースのメソッドの場合、$proptooperatornamepolylog(K)$ timesに対してのみポリシーを更新する必要がある。 少なくとも$Omega(K)$倍のポリシーを更新する既存のアプローチとは対照的に、当社のアプローチはポリシーの解決における最適化コールの数を劇的に削減します。
  論文  参考訳（メタデータ） (2021-06-14T07:36:25Z)
• Sample-Efficient Reinforcement Learning Is Feasible for Linearly Realizable MDPs with Limited Revisiting [60.98700344526674]
  線形関数表現のような低複雑度モデルがサンプル効率のよい強化学習を可能にする上で重要な役割を果たしている。 本稿では,オンライン/探索的な方法でサンプルを描画するが,制御不能な方法で以前の状態をバックトラックし,再訪することができる新しいサンプリングプロトコルについて検討する。 この設定に合わせたアルゴリズムを開発し、特徴次元、地平線、逆の準最適ギャップと実際にスケールするサンプル複雑性を実現するが、状態/作用空間のサイズではない。
  論文  参考訳（メタデータ） (2021-05-17T17:22:07Z)
• Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexity [67.02490430380415]
  モデルに基づくMARLは、Nash平衡値(NE)を求めるために$tilde O(|S||B|(gamma)-3epsilon-2)$のサンプル複雑性を実現する。 また、アルゴリズムが報酬に依存しない場合、そのようなサンプル境界は最小値(対数因子まで)であり、アルゴリズムは報酬知識のない遷移サンプルを問合せする。
  論文  参考訳（メタデータ） (2020-07-15T03:25:24Z)

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

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