論文の概要: Efficient Learning for Entropy-regularized Markov Decision Processes via Multilevel Monte Carlo

• arxiv url: http://arxiv.org/abs/2503.21224v1
• Date: Thu, 27 Mar 2025 07:35:23 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-03-28 12:53:53.591878
• Title: Efficient Learning for Entropy-regularized Markov Decision Processes via Multilevel Monte Carlo
• Title（参考訳）: 多レベルモンテカルロによるエントロピー規則化マルコフ決定過程の効率的な学習
• Authors: Matthieu Meunier, Christoph Reisinger, Yufei Zhang,
• Abstract要約: 本稿では,固定点反復とベルマン作用素の一般近似を融合したマルチレベルモンテカルロアルゴリズムを提案する。 本稿では,Bellman演算子に対する偏平MC推定値を用いることで,準ポリノミカル標本の複雑さが生じることを示す。 特に、これらのアルゴリズムは状態空間や作用空間の次元や濃度に依存しない。
• 参考スコア（独自算出の注目度）: 3.439970905480239
• License:
• Abstract: Designing efficient learning algorithms with complexity guarantees for Markov decision processes (MDPs) with large or continuous state and action spaces remains a fundamental challenge. We address this challenge for entropy-regularized MDPs with Polish state and action spaces, assuming access to a generative model of the environment. We propose a novel family of multilevel Monte Carlo (MLMC) algorithms that integrate fixed-point iteration with MLMC techniques and a generic stochastic approximation of the Bellman operator. We quantify the precise impact of the chosen approximate Bellman operator on the accuracy of the resulting MLMC estimator. Leveraging this error analysis, we show that using a biased plain MC estimate for the Bellman operator results in quasi-polynomial sample complexity, whereas an unbiased randomized multilevel approximation of the Bellman operator achieves polynomial sample complexity in expectation. Notably, these complexity bounds are independent of the dimensions or cardinalities of the state and action spaces, distinguishing our approach from existing algorithms whose complexities scale with the sizes of these spaces. We validate these theoretical performance guarantees through numerical experiments.
• Abstract（参考訳）: マルコフ決定プロセス(MDP)の複雑性を保証するような効率的な学習アルゴリズムを、大規模または連続的な状態と行動空間で設計することは、依然として根本的な課題である。 本研究では,環境生成モデルへのアクセスを前提として,ポーランド状態と行動空間を有するエントロピー規則型MDPの課題に対処する。 本稿では,固定点反復をMLMC手法と統合したマルチレベルモンテカルロアルゴリズムと,ベルマン作用素の一般確率近似を提案する。 得られたMLMC推定器の精度に対するベルマン演算子の正確な影響を定量化する。 この誤差分析を応用して、ベルマン作用素に対して偏りのある平面MC推定を用いることで準ポリーノミカル標本の複雑さが生じるのに対し、ベルマン作用素の偏りのないランダム化多重レベル近似は予想される多項式サンプルの複雑さを達成する。 特に、これらの複雑性境界は状態空間と作用空間の次元や基数とは独立であり、これらの空間のサイズにスケールする既存のアルゴリズムと我々のアプローチを区別する。 我々はこれらの理論的性能保証を数値実験により検証する。

関連論文リスト

• Overcoming the Curse of Dimensionality in Reinforcement Learning Through Approximate Factorization [15.898378661128334]
  強化学習(RL)アルゴリズムは次元性の呪いに苦しむことが知られている。 本稿では,元のマルコフ決定過程(MDP)を,より小さく,独立に進化するMDPに大まかに分解することで,次元性の呪いを克服することを提案する。 提案手法は,両アルゴリズムに改良された複雑性保証を提供する。
  論文  参考訳（メタデータ） (2024-11-12T07:08:00Z)
• Sample-Efficient Multi-Agent RL: An Optimization Perspective [103.35353196535544]
  一般関数近似に基づく汎用マルコフゲーム(MG)のためのマルチエージェント強化学習(MARL)について検討した。 汎用MGに対するマルチエージェントデカップリング係数(MADC)と呼ばれる新しい複雑性尺度を導入する。 我々のアルゴリズムは既存の研究に匹敵するサブリニアな後悔を与えることを示す。
  論文  参考訳（メタデータ） (2023-10-10T01:39:04Z)
• Provably Efficient UCB-type Algorithms For Learning Predictive State Representations [55.00359893021461]
  逐次決定問題は、予測状態表現(PSR)によってモデル化された低ランク構造が認められる場合、統計的に学習可能である 本稿では,推定モデルと実モデル間の全変動距離を上限とする新しいボーナス項を特徴とする,PSRに対する最初のUCB型アプローチを提案する。 PSRに対する既存のアプローチとは対照的に、UCB型アルゴリズムは計算的トラクタビリティ、最優先の準最適ポリシー、モデルの精度が保証される。
  論文  参考訳（メタデータ） (2023-07-01T18:35:21Z)
• Quantum algorithms for multivariate Monte Carlo estimation [0.0]
  多次元確率変数によって出力が記述されるモンテカルロ過程の予測結果を推定する問題を考える。 結果の精度に関して,クエリの複雑性を2次的に高速化する量子アルゴリズムを設計する。 我々はアルゴリズムのいくつかの応用、特に機械学習の分野について述べる。
  論文  参考訳（メタデータ） (2021-07-07T18:00:18Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• Sample-Efficient Reinforcement Learning of Undercomplete POMDPs [91.40308354344505]
  この研究は、これらの硬度障壁が、部分観測可能決定過程(POMDP)の豊かで興味深いサブクラスに対する効率的な強化学習を妨げないことを示している。 提案手法は, 観測回数が潜伏状態の数よりも大きく, 探索が学習に不可欠であり, 先行研究と区別できるような, エピソード有限不完全POMDPに対するサンプル効率アルゴリズムOOM-UCBを提案する。
  論文  参考訳（メタデータ） (2020-06-22T17:58:54Z)
• Partial Policy Iteration for L1-Robust Markov Decision Processes [13.555107578858307]
  本稿では、ロバストなMDPの共通クラスを解くための新しい効率的なアルゴリズムについて述べる。 我々は、ロバストなMDPのための部分ポリシーイテレーション、新しい、効率的で柔軟な、一般的なポリシーイテレーションスキームを提案する。 実験結果から,提案手法は最先端手法よりも桁違いに高速であることが示唆された。
  論文  参考訳（メタデータ） (2020-06-16T19:50:14Z)
• Planning in Markov Decision Processes with Gap-Dependent Sample Complexity [48.98199700043158]
  マルコフ決定過程における計画のための新しいトラジェクトリに基づくモンテカルロ木探索アルゴリズム MDP-GapE を提案する。 我々は, MDP-GapE に要求される生成モデルに対する呼び出し回数の上限を証明し, 確率の高い準最適動作を同定する。
  論文  参考訳（メタデータ） (2020-06-10T15:05:51Z)
• Theoretical Convergence of Multi-Step Model-Agnostic Meta-Learning [63.64636047748605]
  一般的なマルチステップMAMLアルゴリズムに対して収束保証を提供するための新しい理論フレームワークを開発する。 特に,本研究の結果は,収束を保証するためには,内部段階のステップを逆比例して$N$の内段ステップを選択する必要があることを示唆している。
  論文  参考訳（メタデータ） (2020-02-18T19:17:54Z)

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

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