論文の概要: On the Convergence of the Monte Carlo Exploring Starts Algorithm for Reinforcement Learning

• arxiv url: http://arxiv.org/abs/2002.03585v2
• Date: Fri, 5 Aug 2022 16:05:42 GMT
• ステータス: 処理完了
• システム内更新日: 2023-01-02 07:10:43.593366
• Title: On the Convergence of the Monte Carlo Exploring Starts Algorithm for Reinforcement Learning
• Title（参考訳）: 強化学習のためのモンテカルロ探索開始アルゴリズムの収束性について
• Authors: Che Wang, Shuhan Yuan, Kai Shao, Keith Ross
• Abstract要約: 強化学習のための単純で自然なアルゴリズムはMonte Carlo Exploring Starts (MCES)である 我々は,元来のより効率的な MCES アルゴリズムを駆使し,最適ポリシーフィードフォワード MDP の収束性をほぼ確実に確立する。 我々は、非常に単純で、大数の強法則のみを利用する、新しい帰納的アプローチを導入する。
• 参考スコア（独自算出の注目度）: 8.19727735624814
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A simple and natural algorithm for reinforcement learning (RL) is Monte Carlo Exploring Starts (MCES), where the Q-function is estimated by averaging the Monte Carlo returns, and the policy is improved by choosing actions that maximize the current estimate of the Q-function. Exploration is performed by "exploring starts", that is, each episode begins with a randomly chosen state and action, and then follows the current policy to the terminal state. In the classic book on RL by Sutton & Barto (2018), it is stated that establishing convergence for the MCES algorithm is one of the most important remaining open theoretical problems in RL. However, the convergence question for MCES turns out to be quite nuanced. Bertsekas & Tsitsiklis (1996) provide a counter-example showing that the MCES algorithm does not necessarily converge. Tsitsiklis (2002) further shows that if the original MCES algorithm is modified so that the Q-function estimates are updated at the same rate for all state-action pairs, and the discount factor is strictly less than one, then the MCES algorithm converges. In this paper we make headway with the original and more efficient MCES algorithm given in Sutton & Barto (1998), establishing almost sure convergence for Optimal Policy Feed-Forward MDPs, which are MDPs whose states are not revisited within any episode when using an optimal policy. Such MDPs include a large class of environments such as all deterministic environments and all episodic environments with a timestep or any monotonically changing values as part of the state. Different from the previous proofs using stochastic approximations, we introduce a novel inductive approach, which is very simple and only makes use of the strong law of large numbers.
• Abstract（参考訳）: 強化学習(RL)のための単純で自然なアルゴリズムはモンテカルロ探索開始(MCES)であり、Q関数を平均化することでQ関数を推定し、Q関数の現在の推定を最大化するアクションを選択することでポリシーを改善する。 探索は「探索開始」によって行われ、各エピソードはランダムに選択された状態と動作から始まり、その後、現在のポリシーを端末状態に従わせる。 Sutton & Barto (2018) による古典的な RL の本で、MCES アルゴリズムの収束を確立することは、RL における最も重要なオープン理論上の問題の1つであることが述べられている。 しかし、MCESの収束問題はかなり曖昧であることが判明した。 Bertsekas & Tsitsiklis (1996) は MCES アルゴリズムが必ずしも収束しないことを示す反例を提供している。 Tsitsiklis (2002) はさらに、元の MCES アルゴリズムが変更され、Q-関数の推定値が全ての状態-作用対に対して同じ速度で更新され、割引係数が1より厳密に小さい場合、MCES アルゴリズムは収束することを示した。 本論文では,1998年にサットン・アンド・バルト(Sutton & Barto)で与えられた,より効率的な MCES アルゴリズムを用いて,最適政策フィードフォワード MDP に対するほぼ確実な収束性を確立する。 このようなmdpには、すべての決定論的環境や、時間ステップを持つすべてのエピソド環境、あるいは状態の一部として単調に変化する値など、幅広い種類の環境が含まれる。 確率近似を用いた以前の証明と異なり、非常に単純で、大数の強い法則を利用するだけで、新しい帰納的アプローチを導入する。

関連論文リスト

• Finite-Sample Analysis of the Monte Carlo Exploring Starts Algorithm for Reinforcement Learning [0.0]
  政策アルゴリズムの収束率に関する新しい結果を示す。 このアルゴリズムは、$tildeO(SAK3log3frac1delta)$ sampled episodesの後に最適なポリシーを返す。
  論文  参考訳（メタデータ） (2024-10-03T21:11:29Z)
• The Power of Resets in Online Reinforcement Learning [73.64852266145387]
  ローカルシミュレータアクセス(あるいはローカルプランニング)を用いたオンライン強化学習を通してシミュレータのパワーを探求する。 カバー性が低いMPPは,Qstar$-realizabilityのみのサンプル効率で学習可能であることを示す。 ローカルシミュレーターアクセス下では, 悪名高いExogenous Block MDP問題が抽出可能であることを示す。
  論文  参考訳（メタデータ） (2024-04-23T18:09:53Z)
• Provable and Practical: Efficient Exploration in Reinforcement Learning via Langevin Monte Carlo [104.9535542833054]
  我々は、強化学習のためのトンプソンサンプリングに基づくスケーラブルで効果的な探索戦略を提案する。 代わりに、Langevin Monte Carlo を用いて、Q 関数をその後部分布から直接サンプリングする。 提案手法は,Atari57スイートからのいくつかの挑戦的な探索課題において,最先端の深部RLアルゴリズムと比較して,より優れた,あるいは類似した結果が得られる。
  論文  参考訳（メタデータ） (2023-05-29T17:11:28Z)
• Model-Based Reinforcement Learning with Multinomial Logistic Function Approximation [10.159501412046508]
  マルコフ決定過程(MDP)におけるモデルベース強化学習(RL)について検討する。 我々は,多項ロジスティックモデルにより状態遷移が与えられるMPPに対して,証明可能な効率のよいRLアルゴリズムを確立する。 我々の知る限りでは、証明可能な保証付き多項ロジスティック関数近似を用いたモデルベースRLアルゴリズムとしてはこれが初めてである。
  論文  参考訳（メタデータ） (2022-12-27T16:25:09Z)
• Policy Gradient Algorithms with Monte Carlo Tree Learning for Non-Markov Decision Processes [3.9311044240639568]
  政策勾配 (PG) は、勾配上昇を用いたパラメータ化政策モデルを最適化する強化学習 (RL) アプローチである。 PGは非マルコフ環境でもうまく機能するが、高原やピークネスの問題に遭遇することがある。 本稿では、まず、オンラインRLのためのMCTSの適応であるモンテカルロ木学習(MCTL)を紹介し、その強みを活用するためにPGとMCTLの政策アプローチについて検討する。
  論文  参考訳（メタデータ） (2022-06-02T12:21:40Z)
• Near Instance-Optimal PAC Reinforcement Learning for Deterministic MDPs [24.256960622176305]
  エピソードマルコフ決定過程におけるPAC RLのサンプル複雑性について, 上界と下界の整合性について検討した。 私たちの境界は、決定論的リターンギャップ(deterministic return gap)と呼ばれる状態-作用ペアに対して、新たな最適ギャップ(sub-optimality gap)を特徴とする。 彼らの設計と分析は、最小フローや最大カットといったグラフ理論の概念を含む新しいアイデアを採用している。
  論文  参考訳（メタデータ） (2022-03-17T11:19:41Z)
• Reinforcement Learning in Reward-Mixing MDPs [74.41782017817808]
  報酬混合マルコフ決定過程(MDP)におけるエピソード強化学習 cdot S2 A2)$ episodes, where$H$ is time-horizon and $S, A$ are the number of state and actions。 epsilon$-optimal policy after $tildeO(poly(H,epsilon-1) cdot S2 A2)$ episodes, $H$ is time-horizon and $S, A$ are the number of state and actions。
  論文  参考訳（メタデータ） (2021-10-07T18:55:49Z)
• RL for Latent MDPs: Regret Guarantees and a Lower Bound [74.41782017817808]
  後期マルコフ決定過程(LMDP)における強化学習における後悔問題の検討 LMDPにおいて、M$可能なMDPのセットからMDPをランダムに描画するが、選択したMDPの同一性はエージェントに明らかにしない。 鍵となるリンクは、MDPシステムの力学の分離の概念であることを示す。
  論文  参考訳（メタデータ） (2021-02-09T16:49:58Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• On the Convergence of Reinforcement Learning with Monte Carlo Exploring Starts [5.137144629366217]
  基本的なシミュレーションに基づく強化学習アルゴリズムはモンテカルロ探索州 (MCES) 法である。 最短経路問題としても知られる未計算コストの場合のこのアルゴリズムの収束性について検討する。 副作用として、近似によく用いられるスーパーマリンゲール収束定理のバージョンの証明も提供する。
  論文  参考訳（メタデータ） (2020-07-21T16:19:09Z)
• Discovering Reinforcement Learning Algorithms [53.72358280495428]
  強化学習アルゴリズムは、いくつかのルールの1つに従ってエージェントのパラメータを更新する。 本稿では,更新ルール全体を検出するメタラーニング手法を提案する。 これには、一連の環境と対話することで、"何を予測するか"(例えば、値関数)と"どのように学習するか"の両方が含まれている。
  論文  参考訳（メタデータ） (2020-07-17T07:38:39Z)

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

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