論文の概要: 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には、すべての決定論的環境や、時間ステップを持つすべてのエピソド環境、あるいは状態の一部として単調に変化する値など、幅広い種類の環境が含まれる。
確率近似を用いた以前の証明と異なり、非常に単純で、大数の強い法則を利用するだけで、新しい帰納的アプローチを導入する。
関連論文リスト
- Provable and Practical: Efficient Exploration in Reinforcement Learning
via Langevin Monte Carlo [98.11820566044216]
我々は、強化学習のためのトンプソンサンプリングに基づくスケーラブルで効果的な探索戦略を提案する。
代わりに、Langevin Monte Carlo を用いて、Q 関数をその後部分布から直接サンプリングする。
提案手法は,Atari57スイートからのいくつかの挑戦的な探索課題において,最先端の深部RLアルゴリズムと比較して,より優れた,あるいは類似した結果が得られる。
論文 参考訳(メタデータ) (2023-05-29T17:11:28Z) - Model-Based Reinforcement Learning with Multinomial Logistic Function
Approximation [12.36108042107798]
マルコフ決定過程におけるモデルに基づく強化学習について検討する。
我々は,多項ロジスティックモデルにより状態遷移が与えられるMPPに対して,証明可能な効率のよいRLアルゴリズムを確立する。
本稿では,提案アルゴリズムが既存の手法より一貫して優れていることを示す。
論文 参考訳(メタデータ) (2022-12-27T16:25:09Z) - Policy Gradient Algorithms with Monte-Carlo Tree Search for Non-Markov
Decision Processes [1.8925617030516926]
本稿では,政策(PG)とモンテカルロ木探索(MCTS)の勾配混合政策を提案する。
2時間スケール近似の結果から収束条件を導出し,これらの条件を満たすアルゴリズムを提案する。
提案手法の有効性は,非マルコフ決定過程に関する数値実験によって検証される。
論文 参考訳(メタデータ) (2022-06-02T12:21:40Z) - Sample-Efficient Reinforcement Learning for POMDPs with Linear Function
Approximations [130.66193083412716]
本稿では,関数近似と部分観測可能性の緊張に対処する。
最適ポリシーと値関数は有限メモリヒルベルト・ベルマン作用素の列によって特徴づけられることを示す。
本稿では、カーネル空間(RKHS)の埋め込みを再現することで、これらの演算子の楽観的な推定値を構成するRLアルゴリズムを提案する。
論文 参考訳(メタデータ) (2022-04-20T21:15:38Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。