論文の概要: Improved Sample Complexity for Incremental Autonomous Exploration in
MDPs
- arxiv url: http://arxiv.org/abs/2012.14755v1
- Date: Tue, 29 Dec 2020 14:06:09 GMT
- ステータス: 処理完了
- システム内更新日: 2021-04-18 20:46:41.347987
- Title: Improved Sample Complexity for Incremental Autonomous Exploration in
MDPs
- Title（参考訳）: MDPにおけるインクリメンタル自律探査のためのサンプル複雑さの改善
- Authors: Jean Tarbouriech, Matteo Pirotta, Michal Valko, Alessandro Lazaric
- Abstract要約: 我々は $epsilon$-optimal 目標条件付きポリシーのセットを学び、$ L$ ステップ内で段階的に到達可能なすべての状態を達成します。
DisCoは、コストに敏感な最短経路問題に対して$epsilon/c_min$-optimalポリシーを返すことができる最初のアルゴリズムです。
- 参考スコア（独自算出の注目度）: 132.88757893161699
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We investigate the exploration of an unknown environment when no reward
function is provided. Building on the incremental exploration setting
introduced by Lim and Auer [1], we define the objective of learning the set of
$\epsilon$-optimal goal-conditioned policies attaining all states that are
incrementally reachable within $L$ steps (in expectation) from a reference
state $s_0$. In this paper, we introduce a novel model-based approach that
interleaves discovering new states from $s_0$ and improving the accuracy of a
model estimate that is used to compute goal-conditioned policies to reach newly
discovered states. The resulting algorithm, DisCo, achieves a sample complexity
scaling as $\tilde{O}(L^5 S_{L+\epsilon} \Gamma_{L+\epsilon} A \epsilon^{-2})$,
where $A$ is the number of actions, $S_{L+\epsilon}$ is the number of states
that are incrementally reachable from $s_0$ in $L+\epsilon$ steps, and
$\Gamma_{L+\epsilon}$ is the branching factor of the dynamics over such states.
This improves over the algorithm proposed in [1] in both $\epsilon$ and $L$ at
the cost of an extra $\Gamma_{L+\epsilon}$ factor, which is small in most
environments of interest. Furthermore, DisCo is the first algorithm that can
return an $\epsilon/c_{\min}$-optimal policy for any cost-sensitive
shortest-path problem defined on the $L$-reachable states with minimum cost
$c_{\min}$. Finally, we report preliminary empirical results confirming our
theoretical findings.
- Abstract（参考訳）: 報酬関数が提供されない未知環境の探索について検討する。
lim と auer [1] によって導入されたインクリメンタルな探索設定に基づいて、参照状態 $s_0$ から$l$ ステップ以内に到達可能なすべての状態を達成するために、$\epsilon$-optimal goal-conditioned policies のセットを学習する目的を定義します。
本稿では、新しい状態の発見を$s_0$からインターリーブし、ゴール条件付きポリシーを計算して新たに発見された状態に到達させるモデル推定の精度を向上させる新しいモデルベースアプローチを提案する。
結果のアルゴリズムであるDisCoはサンプル複雑性のスケールを$\tilde{O}(L^5 S_{L+\epsilon} \Gamma_{L+\epsilon} A \epsilon^{-2})$, where $A$ is the number of action, $S_{L+\epsilon}$は $s_0$ in $L+\epsilon$ steps, $\Gamma_{L+\epsilon}$はそのような状態上の力学の分岐因子である。
これは$\epsilon$と$l$の両方で[1]で提案されているアルゴリズムよりも改善され、ほとんどの関心のある環境では小さい$\gamma_{l+\epsilon}$ factorのコストがかかる。
さらに、DisCo は$\epsilon/c_{\min}$-optimal policy を$L$-reachable state で最小コスト$c_{\min}$ で定義した任意のコスト感受性のショートパス問題に対して返すことができる最初のアルゴリズムである。
最後に,我々の理論的知見を裏付ける予備実験結果について報告する。
関連論文リスト
- Finding good policies in average-reward Markov Decision Processes without prior knowledge [19.89784209009327]
平均回帰決定(MDP)における$varepsilon$-Optimal Policyの同定を再考する。
直径推定法を用いて,$(varepsilon,delta)$-PAC-PACポリシー識別のための最初のアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-05-27T12:24:14Z) - Layered State Discovery for Incremental Autonomous Exploration [106.37656068276901]
Layered Autonomous Exploration (LAE) は、$tildemathcalO(LSrightarrow_LAln12(Srightarrow_LAln12(Srightarrow_LAln12(Srightarrow_LAln12(Srightar row_LAln12)Srightarrow_LAln12(Srightarrow_LAln12)Srightarrow_LAln12(Srightarrow_LAln12)のサンプル複雑性を達成するAXの新しいアルゴリズムである。
論文 参考訳（メタデータ） (2023-02-07T22:58:12Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Gap-Dependent Unsupervised Exploration for Reinforcement Learning [40.990467706237396]
タスクに依存しない強化学習のための効率的なアルゴリズムを提案する。
このアルゴリズムは1/epsilon cdot (H3SA / rho + H4 S2 A) の$widetildemathcalOのみを探索する。
情報理論上、この境界は$rho Theta (1/(HS))$と$H>1$に対してほぼ厳密であることを示す。
論文 参考訳（メタデータ） (2021-08-11T20:42:46Z) - Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$
Geometry [69.24618367447101]
対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。
損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
論文 参考訳（メタデータ） (2021-03-02T06:53:44Z) - Sample Efficient Reinforcement Learning via Low-Rank Matrix Estimation [30.137884459159107]
連続状態と行動空間を用いた強化学習において,Q$関数を効率よく学習する方法を考える。
我々は、$epsilon$-Schmidt $Q$-functionと$widetildeO(frac1epsilonmax(d1, d_2)+2)$のサンプル複雑性を求める単純な反復学習アルゴリズムを開発する。
論文 参考訳（メタデータ） (2020-06-11T00:55:35Z) - 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) - Agnostic Q-learning with Function Approximation in Deterministic
Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
本稿では,決定論的システムにおける関数近似を用いたQ$学習の問題について検討する。
もし$delta = Oleft(rho/sqrtdim_Eright)$なら、$Oleft(dim_Eright)$を使って最適なポリシーを見つけることができる。
論文 参考訳（メタデータ） (2020-02-17T18:41:49Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。