論文の概要: Finite-Sample Analysis of the Monte Carlo Exploring Starts Algorithm for Reinforcement Learning

• arxiv url: http://arxiv.org/abs/2410.02994v1
• Date: Thu, 3 Oct 2024 21:11:29 GMT
• ステータス: 処理完了
• システム内更新日: 2024-11-03 04:35:40.331367
• Title: Finite-Sample Analysis of the Monte Carlo Exploring Starts Algorithm for Reinforcement Learning
• Title（参考訳）: 強化学習のためのモンテカルロ探索開始アルゴリズムの有限サンプル解析
• Authors: Suei-Wen Chen, Keith Ross, Pierre Youssef,
• Abstract要約: 政策アルゴリズムの収束率に関する新しい結果を示す。 このアルゴリズムは、$tildeO(SAK3log3frac1delta)$ sampled episodesの後に最適なポリシーを返す。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Monte Carlo Exploring Starts (MCES), which aims to learn the optimal policy using only sample returns, is a simple and natural algorithm in reinforcement learning which has been shown to converge under various conditions. However, the convergence rate analysis for MCES-style algorithms in the form of sample complexity has received very little attention. In this paper we develop a finite sample bound for a modified MCES algorithm which solves the stochastic shortest path problem. To this end, we prove a novel result on the convergence rate of the policy iteration algorithm. This result implies that with probability at least $1-\delta$, the algorithm returns an optimal policy after $\tilde{O}(SAK^3\log^3\frac{1}{\delta})$ sampled episodes, where $S$ and $A$ denote the number of states and actions respectively, $K$ is a proxy for episode length, and $\tilde{O}$ hides logarithmic factors and constants depending on the rewards of the environment that are assumed to be known.
• Abstract（参考訳）: モンテカルロ探索開始点(Monte Carlo Exploring Starts, MCES)は、様々な条件下で収束することが示されている強化学習における単純で自然なアルゴリズムである。 しかし, MCES型アルゴリズムの収束速度解析は, ほとんど注目されていない。 本稿では,確率的最短経路問題を解く改良型MCESアルゴリズムに限定した有限サンプルを開発する。 この目的のために、ポリシー反復アルゴリズムの収束率に関する新しい結果を示す。 この結果は、少なくとも1-\delta$の確率で、アルゴリズムは、$\tilde{O}(SAK^3\log^3\frac{1}{\delta})$サンプルエピソードの後、最適なポリシーを返し、$S$と$A$はそれぞれ、エピソードの長さのプロキシであり、$\tilde{O}$は、既知の環境の報酬に応じて対数係数と定数を隠すことを意味する。

関連論文リスト

• Provable Policy Gradient Methods for Average-Reward Markov Potential Games [15.136494705127564]
  無限水平平均報酬基準の下でマルコフポテンシャルゲームを研究する。 我々は、独立政策勾配と独立自然政策勾配に基づくアルゴリズムが、平均報酬基準に対するナッシュ均衡にグローバルに収束することを証明した。
  論文  参考訳（メタデータ） (2024-03-09T00:20:33Z)
• A Doubly Robust Approach to Sparse Reinforcement Learning [19.68978899041642]
  エピソードスパークリニアマルコフ決定過程(SMDP)に対する新しい後悔アルゴリズムを提案する。 提案アルゴリズムは$tildeO(sigma-1_min s_star H sqrtN)$である。
  論文  参考訳（メタデータ） (2023-10-23T18:52:17Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。 本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
  論文  参考訳（メタデータ） (2023-07-24T14:37:22Z)
• Reaching Goals is Hard: Settling the Sample Complexity of the Stochastic Shortest Path [106.37656068276902]
  本稿では,最短経路(SSP)問題において,$epsilon$-optimal Policyを学習する際のサンプル複雑性について検討する。 学習者が生成モデルにアクセスできる場合、複雑性境界を導出する。 我々は、$S$状態、$A$アクション、最小コスト$c_min$、およびすべての状態に対する最適ポリシーの最大期待コストを持つ最悪のSSPインスタンスが存在することを示す。
  論文  参考訳（メタデータ） (2022-10-10T18:34:32Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• Randomized Exploration for Reinforcement Learning with General Value Function Approximation [122.70803181751135]
  本稿では,ランダム化最小二乗値反復(RLSVI)アルゴリズムに着想を得たモデルレス強化学習アルゴリズムを提案する。 提案アルゴリズムは,スカラーノイズを用いたトレーニングデータを簡易に摂動させることにより,探索を促進する。 我々はこの理論を、既知の困難な探査課題にまたがる実証的な評価で補完する。
  論文  参考訳（メタデータ） (2021-06-15T02:23:07Z)
• Improved Sample Complexity for Incremental Autonomous Exploration in MDPs [132.88757893161699]
  我々は $epsilon$-optimal 目標条件付きポリシーのセットを学び、$ L$ ステップ内で段階的に到達可能なすべての状態を達成します。 DisCoは、コストに敏感な最短経路問題に対して$epsilon/c_min$-optimalポリシーを返すことができる最初のアルゴリズムです。
  論文  参考訳（メタデータ） (2020-12-29T14:06:09Z)
• On the Convergence of Reinforcement Learning with Monte Carlo Exploring Starts [5.137144629366217]
  基本的なシミュレーションに基づく強化学習アルゴリズムはモンテカルロ探索州 (MCES) 法である。 最短経路問題としても知られる未計算コストの場合のこのアルゴリズムの収束性について検討する。 副作用として、近似によく用いられるスーパーマリンゲール収束定理のバージョンの証明も提供する。
  論文  参考訳（メタデータ） (2020-07-21T16:19:09Z)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。 十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
  論文  参考訳（メタデータ） (2020-06-06T13:34:41Z)

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

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