論文の概要: Near-Optimal Algorithms for Autonomous Exploration and Multi-Goal Stochastic Shortest Path

• arxiv url: http://arxiv.org/abs/2205.10729v1
• Date: Sun, 22 May 2022 03:54:15 GMT
• ステータス: 処理完了
• システム内更新日: 2022-05-24 19:27:31.616153
• Title: Near-Optimal Algorithms for Autonomous Exploration and Multi-Goal Stochastic Shortest Path
• Title（参考訳）: 自律探索とマルチゴール確率的最短経路の近似アルゴリズム
• Authors: Haoyuan Cai, Tengyu Ma, Simon Du
• Abstract要約: 我々はLim & Auer (2012) が提唱する漸進的な自律探査問題を再考する。 この設定では、エージェントは、$L$制御可能な状態に到達するために、最適に近い目標条件の一連のポリシーを学ぶことを目的としている。 既存のものよりも強いサンプル境界を持つ新しいアルゴリズムを導入する。
• 参考スコア（独自算出の注目度）: 26.27529098205787
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We revisit the incremental autonomous exploration problem proposed by Lim & Auer (2012). In this setting, the agent aims to learn a set of near-optimal goal-conditioned policies to reach the $L$-controllable states: states that are incrementally reachable from an initial state $s_0$ within $L$ steps in expectation. We introduce a new algorithm with stronger sample complexity bounds than existing ones. Furthermore, we also prove the first lower bound for the autonomous exploration problem. In particular, the lower bound implies that our proposed algorithm, Value-Aware Autonomous Exploration, is nearly minimax-optimal when the number of $L$-controllable states grows polynomially with respect to $L$. Key in our algorithm design is a connection between autonomous exploration and multi-goal stochastic shortest path, a new problem that naturally generalizes the classical stochastic shortest path problem. This new problem and its connection to autonomous exploration can be of independent interest.
• Abstract（参考訳）: 我々はLim & Auer (2012) による漸進的な自律探査問題を再考する。 この設定において、エージェントは、$l$-controllable状態に到達するための最適に近い目標条件付きポリシーのセットを学習することを目指している: 初期状態から段階的に到達可能な状態は、$l$のステップで$s_0$である。 我々は既存のものよりも強いサンプル複雑性境界を持つ新しいアルゴリズムを導入する。 さらに,自律探査問題に対する最初の下限も証明した。 特に下界は,$L$制御可能な状態の数が$L$に対して多項式的に増加するとき,提案アルゴリズムであるValue-Aware Autonomous Explorationが最小値に近いことを意味する。 アルゴリズム設計における鍵となるのは、自律探索とマルチゴール確率的最短経路の接続であり、これは古典的確率的最短経路問題を自然に一般化する新しい問題である。 この新たな問題と自律探査との関係は、独立した関心事である。

関連論文リスト

• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• Optimal Horizon-Free Reward-Free Exploration for Linear Mixture MDPs [60.40452803295326]
  線形マルコフ決定過程(MDP)を学習するための新たな報酬なしアルゴリズムを提案する。 我々のアルゴリズムの核心は、探索駆動の擬似回帰を用いた不確実性重み付き値目標回帰である。 我々のアルゴリズムは$tilde O(d2varepsilon-2)$ episodesを探索するだけで、$varepsilon$-optimal policyを見つけることができる。
  論文  参考訳（メタデータ） (2023-03-17T17:53:28Z)
• 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)
• Adaptive Multi-Goal Exploration [118.40427257364729]
  我々は、AdaGoalが$epsilon$-optimal goal-conditioned policyを学習する目的を達成するためにどのように使えるかを示す。 AdaGoalは、ゴール条件の深い強化学習のための既存の手法の高レベルなアルゴリズム構造に固定されている。
  論文  参考訳（メタデータ） (2021-11-23T17:59:50Z)
• Improved Sample Complexity for Incremental Autonomous Exploration in MDPs [132.88757893161699]
  我々は $epsilon$-optimal 目標条件付きポリシーのセットを学び、$ L$ ステップ内で段階的に到達可能なすべての状態を達成します。 DisCoは、コストに敏感な最短経路問題に対して$epsilon/c_min$-optimalポリシーを返すことができる最初のアルゴリズムです。
  論文  参考訳（メタデータ） (2020-12-29T14:06:09Z)
• Reward-Free Exploration for Reinforcement Learning [82.3300753751066]
  探索の課題を分離する「逆フリーなRL」フレームワークを提案する。 我々は,$tildemathcalO(S2Amathrmpoly(H)/epsilon2)$の探索を効率的に行うアルゴリズムを提案する。 また、ほぼ一致する$Omega(S2AH2/epsilon2)$ lower boundを与え、この設定でアルゴリズムのほぼ最適性を示す。
  論文  参考訳（メタデータ） (2020-02-07T14:03:38Z)

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

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