論文の概要: 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文献における最初の理論的結果である。
関連論文リスト
- A Few Expert Queries Suffices for Sample-Efficient RL with Resets and
Linear Value Approximation [16.29514743112387]
最適値関数のみを線形化可能な設定において、サンプル効率のよい強化学習(RL)について検討する。
専門的なクエリと探索をブレンドするための統計的・計算学的に効率的なアルゴリズム(Delphi)を提案する。
Delphi には $tildemathcalO(d)$ エキスパートクエリと $texttpoly(d,|mathcalA|,1/varepsilon)$ 探索サンプルの量が必要です。
論文 参考訳(メタデータ) (2022-07-18T01:39:13Z) - Reward-Free RL is No Harder Than Reward-Aware RL in Linear Markov
Decision Processes [61.11090361892306]
Reward-free reinforcement learning (RL) は、エージェントが探索中に報酬関数にアクセスできないような環境を考える。
この分離は線形MDPの設定には存在しないことを示す。
我々は$d$次元線形 MDP における報酬のない RL に対する計算効率の良いアルゴリズムを開発した。
論文 参考訳(メタデータ) (2022-01-26T22:09:59Z) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。