論文の概要: Fast Rates for Maximum Entropy Exploration

• arxiv url: http://arxiv.org/abs/2303.08059v1
• Date: Tue, 14 Mar 2023 16:51:14 GMT
• ステータス: 翻訳完了
• システム内更新日: 2023-03-15 14:08:35.991661
• Title: Fast Rates for Maximum Entropy Exploration
• Title（参考訳）: 最大エントロピー探査のための高速速度
• Authors: Daniil Tiapkin, Denis Belomestny, Daniele Calandriello, Eric Moulines, Remi Munos, Alexey Naumov, Pierre Perrault, Yunhao Tang, Michal Valko, Pierre Menard
• Abstract要約: エージェントが未知の環境で動作しなければならない強化学習環境について考察する。 本研究では,UCBVアルゴリズムの最大探索問題について検討する。
• 参考スコア（独自算出の注目度）: 52.946307632704645
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the reinforcement learning (RL) setting, in which the agent has to act in unknown environment driven by a Markov Decision Process (MDP) with sparse or even reward free signals. In this situation, exploration becomes the main challenge. In this work, we study the maximum entropy exploration problem of two different types. The first type is visitation entropy maximization that was previously considered by Hazan et al. (2019) in the discounted setting. For this type of exploration, we propose an algorithm based on a game theoretic representation that has $\widetilde{\mathcal{O}}(H^3 S^2 A / \varepsilon^2)$ sample complexity thus improving the $\varepsilon$-dependence of Hazan et al. (2019), where $S$ is a number of states, $A$ is a number of actions, $H$ is an episode length, and $\varepsilon$ is a desired accuracy. The second type of entropy we study is the trajectory entropy. This objective function is closely related to the entropy-regularized MDPs, and we propose a simple modification of the UCBVI algorithm that has a sample complexity of order $\widetilde{\mathcal{O}}(1/\varepsilon)$ ignoring dependence in $S, A, H$. Interestingly enough, it is the first theoretical result in RL literature establishing that the exploration problem for the regularized MDPs can be statistically strictly easier (in terms of sample complexity) than for the ordinary MDPs.
• Abstract（参考訳）: 本稿では,マークフ決定プロセス(MDP)によって駆動される未知の環境でエージェントが動作しなければならない強化学習(RL)について考察する。 この状況では、探索が主な課題となる。 本研究では,2種類のエントロピー探索問題について検討する。 最初のタイプは、割引設定で以前Hazanらによって検討された訪問エントロピー最大化(2019)である。 このタイプの探索では、$\widetilde{\mathcal{O}}(H^3 S^2 A / \varepsilon^2)$サンプルの複雑さにより$\varepsilon$-dependence of Hazan et al. (2019) が向上するゲーム理論表現に基づくアルゴリズムを提案し、$S$は多数の状態であり、$A$はアクションの数であり、$H$はエピソード長であり、$\varepsilon$は望ましい精度である。 我々が研究している2つ目のエントロピーは軌道エントロピーである。 この目的関数はエントロピー規則化された MDP と密接に関連しており、より単純な UCBVI アルゴリズムの修正を提案し、このアルゴリズムは$S, A, H$ の依存を無視するオーダー $\widetilde{\mathcal{O}}(1/\varepsilon)$ のサンプル複雑性を持つ。 興味深いことに、正規化されたMDPの探索問題は通常のMDPよりも統計的に(サンプルの複雑さの観点から)簡単であることが証明されたRL文献における最初の理論的結果である。

関連論文リスト

• 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)
• Sublinear quantum algorithms for estimating von Neumann entropy [18.30551855632791]
  我々は、確率分布のシャノンエントロピーと混合量子状態のフォン・ノイマンエントロピーの乗法係数$gamma>1$における推定値を得る問題を研究する。 我々は古典的確率分布と混合量子状態の両方を扱える量子純粋クエリーアクセスモデルに取り組んでおり、文献の中では最も一般的な入力モデルである。
  論文  参考訳（メタデータ） (2021-11-22T12:00:45Z)
• Reward-Free Model-Based Reinforcement Learning with Linear Function Approximation [92.99933928528797]
  エピソードマルコフ決定過程(MDP)に対する線形関数近似を用いたモデルに基づく無報酬強化学習について検討する。 計画段階では、特定の報酬関数が与えられ、探索フェーズから収集したサンプルを使用して良い政策を学ぶ。 任意の報酬関数に対して$epsilon$-optimal Policyを得るには,最大$tilde O(H4d(H + d)epsilon-2)$ episodesをサンプリングする必要がある。
  論文  参考訳（メタデータ） (2021-10-12T23:03:58Z)
• 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)
• Improved Sample Complexity for Incremental Autonomous Exploration in MDPs [132.88757893161699]
  我々は $epsilon$-optimal 目標条件付きポリシーのセットを学び、$ L$ ステップ内で段階的に到達可能なすべての状態を達成します。 DisCoは、コストに敏感な最短経路問題に対して$epsilon/c_min$-optimalポリシーを返すことができる最初のアルゴリズムです。
  論文  参考訳（メタデータ） (2020-12-29T14:06:09Z)
• Adaptive Reward-Free Exploration [48.98199700043158]
  提案アルゴリズムは1994年からのFiechterのアルゴリズムの変種と見なすことができる。 さらに、報酬のない探索と最高の政治識別の相対的な複雑さについて検討する。
  論文  参考訳（メタデータ） (2020-06-11T09:58:03Z)
• Reward-Free Exploration for Reinforcement Learning [82.3300753751066]
  探索の課題を分離する「逆フリーなRL」フレームワークを提案する。 我々は,$tildemathcalO(S2Amathrmpoly(H)/epsilon2)$の探索を効率的に行うアルゴリズムを提案する。 また、ほぼ一致する$Omega(S2AH2/epsilon2)$ lower boundを与え、この設定でアルゴリズムのほぼ最適性を示す。
  論文  参考訳（メタデータ） (2020-02-07T14:03:38Z)

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

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