論文の概要: Improved Sample Complexity for Reward-free Reinforcement Learning under Low-rank MDPs

• arxiv url: http://arxiv.org/abs/2303.10859v1
• Date: Mon, 20 Mar 2023 04:39:39 GMT
• ステータス: 処理完了
• システム内更新日: 2023-03-21 16:50:01.239855
• Title: Improved Sample Complexity for Reward-free Reinforcement Learning under Low-rank MDPs
• Title（参考訳）: 低ランクMDP下での逆フリー強化学習におけるサンプル複雑性の改善
• Authors: Yuan Cheng, Ruiquan Huang, Jing Yang, Yingbin Liang
• Abstract要約: 本稿では,低ランクMDPモデルによる報酬なし強化学習に焦点を当てた。 我々はまず、低ランクのMDPの下での任意のアルゴリズムに対して、最初の既知のサンプル複雑性の低い境界を提供する。 次に、RAFFLEと呼ばれる新しいモデルベースアルゴリズムを提案し、$epsilon$-optimal Policyを見つけ、$epsilon$-accurate system IDを実現できることを示す。
• 参考スコア（独自算出の注目度）: 43.53286390357673
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In reward-free reinforcement learning (RL), an agent explores the environment first without any reward information, in order to achieve certain learning goals afterwards for any given reward. In this paper we focus on reward-free RL under low-rank MDP models, in which both the representation and linear weight vectors are unknown. Although various algorithms have been proposed for reward-free low-rank MDPs, the corresponding sample complexity is still far from being satisfactory. In this work, we first provide the first known sample complexity lower bound that holds for any algorithm under low-rank MDPs. This lower bound implies it is strictly harder to find a near-optimal policy under low-rank MDPs than under linear MDPs. We then propose a novel model-based algorithm, coined RAFFLE, and show it can both find an $\epsilon$-optimal policy and achieve an $\epsilon$-accurate system identification via reward-free exploration, with a sample complexity significantly improving the previous results. Such a sample complexity matches our lower bound in the dependence on $\epsilon$, as well as on $K$ in the large $d$ regime, where $d$ and $K$ respectively denote the representation dimension and action space cardinality. Finally, we provide a planning algorithm (without further interaction with true environment) for RAFFLE to learn a near-accurate representation, which is the first known representation learning guarantee under the same setting.
• Abstract（参考訳）: 報酬のない強化学習(rl)では、エージェントは報酬情報なしでまず環境を探索し、与えられた報酬に対して特定の学習目標を達成する。 本稿では,表現量と線形重みベクトルが不明な低ランクMDPモデル下での報酬のないRLに着目した。 報酬のない低ランクMPPに対して様々なアルゴリズムが提案されているが、対応するサンプルの複雑さは十分ではない。 本研究において,我々はまず,低ランクmdp下での任意のアルゴリズムに対して保持される,最初の既知のサンプル複雑性下限を提供する。 この下限は、線形 MDP よりも低ランク MDP 下での準最適政策を見つけることが困難であることを意味する。 次に、RAFFLEと呼ばれる新しいモデルベースアルゴリズムを提案し、$\epsilon$-optimal Policyを見つけ、$\epsilon$-accurate system Identificationを報酬のない探索によって達成できることを示し、サンプルの複雑さは以前の結果を大幅に改善した。 このようなサンプル複雑性は、$\epsilon$への依存度の下限と、$d$と$k$がそれぞれ表現次元と作用空間濃度を表す大規模な$d$レジームにおける$k$に一致する。 最後に,ラフレに対して,ほぼ正確な表現を学習するための計画アルゴリズム(真の環境とのさらなる相互作用を伴わない)を提供する。

関連論文リスト

• Near-Optimal Regret in Linear MDPs with Aggregate Bandit Feedback [38.61232011566285]
  本稿では,最近提案されたRLモデルとアグリゲート帯域フィードバック(RL-ABF)について検討する。 本稿では,ABFを線形関数近似に拡張し,ほぼ最適後悔保証を伴う2つの効率的なアルゴリズムを開発する。
  論文  参考訳（メタデータ） (2024-05-13T10:51:01Z)
• 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)
• 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)
• On Reward-Free RL with Kernel and Neural Function Approximations: Single-Agent MDP and Markov Game [140.19656665344917]
  エージェントが事前に特定された報酬関数を使わずに環境を徹底的に探索することを目的とした報酬のないRL問題について検討する。 関数近似の文脈でこの問題に取り組み、強力な関数近似器を活用する。 我々は、カーネルとニューラルファンクション近似器を用いた、証明可能な効率の良い報酬なしRLアルゴリズムを確立した。
  論文  参考訳（メタデータ） (2021-10-19T07:26:33Z)
• Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexity [67.02490430380415]
  モデルに基づくMARLは、Nash平衡値(NE)を求めるために$tilde O(|S||B|(gamma)-3epsilon-2)$のサンプル複雑性を実現する。 また、アルゴリズムが報酬に依存しない場合、そのようなサンプル境界は最小値(対数因子まで)であり、アルゴリズムは報酬知識のない遷移サンプルを問合せする。
  論文  参考訳（メタデータ） (2020-07-15T03:25:24Z)
• Adaptive Reward-Free Exploration [48.98199700043158]
  提案アルゴリズムは1994年からのFiechterのアルゴリズムの変種と見なすことができる。 さらに、報酬のない探索と最高の政治識別の相対的な複雑さについて検討する。
  論文  参考訳（メタデータ） (2020-06-11T09:58:03Z)

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

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