論文の概要: Reward-Free RL is No Harder Than Reward-Aware RL in Linear Markov Decision Processes

• arxiv url: http://arxiv.org/abs/2201.11206v1
• Date: Wed, 26 Jan 2022 22:09:59 GMT
• ステータス: 処理完了
• システム内更新日: 2022-01-28 14:05:59.243059
• Title: Reward-Free RL is No Harder Than Reward-Aware RL in Linear Markov Decision Processes
• Title（参考訳）: 線形マルコフ決定過程におけるReward-free RLはReward-Aware RLより困難ではない
• Authors: Andrew Wagenmaker, Yifang Chen, Max Simchowitz, Simon S. Du, Kevin Jamieson
• Abstract要約: Reward-free reinforcement learning (RL) は、エージェントが探索中に報酬関数にアクセスできないような環境を考える。 この分離は線形MDPの設定には存在しないことを示す。 我々は$d$次元線形 MDP における報酬のない RL に対する計算効率の良いアルゴリズムを開発した。
• 参考スコア（独自算出の注目度）: 61.11090361892306
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Reward-free reinforcement learning (RL) considers the setting where the agent does not have access to a reward function during exploration, but must propose a near-optimal policy for an arbitrary reward function revealed only after exploring. In the the tabular setting, it is well known that this is a more difficult problem than PAC RL -- where the agent has access to the reward function during exploration -- with optimal sample complexities in the two settings differing by a factor of $|\mathcal{S}|$, the size of the state space. We show that this separation does not exist in the setting of linear MDPs. We first develop a computationally efficient algorithm for reward-free RL in a $d$-dimensional linear MDP with sample complexity scaling as $\mathcal{O}(d^2/\epsilon^2)$. We then show a matching lower bound of $\Omega(d^2/\epsilon^2)$ on PAC RL. To our knowledge, our approach is the first computationally efficient algorithm to achieve optimal $d$ dependence in linear MDPs, even in the single-reward PAC setting. Our algorithm relies on a novel procedure which efficiently traverses a linear MDP, collecting samples in any given "feature direction", and enjoys a sample complexity scaling optimally in the (linear MDP equivalent of the) maximal state visitation probability. We show that this exploration procedure can also be applied to solve the problem of obtaining "well-conditioned" covariates in linear MDPs.
• Abstract（参考訳）: Reward-free reinforcement learning (RL) は、エージェントが探索中に報酬関数にアクセスできないような設定を考えるが、探索後にのみ現れる任意の報酬関数に対して、ほぼ最適なポリシーを提案する必要がある。 表の設定では、これはPAC RLよりも難しい問題であり、エージェントが探索中に報酬関数にアクセスでき、状態空間のサイズである$|\mathcal{S}|$で異なる2つの設定における最適なサンプル複雑度を持つことが知られている。 この分離は線形MDPの設定には存在しないことを示す。 まず,$d$ 次元線形 MDP における報酬のない RL の計算効率を$\mathcal{O}(d^2/\epsilon^2)$ とした。 次に、PAC RL 上で $\Omega(d^2/\epsilon^2)$ の一致する下界を示す。 我々の知る限り、本手法は一方向pac設定においても線形mdpにおける最適な$d$依存性を達成する最初の計算効率の高いアルゴリズムである。 このアルゴリズムは、線形mdpを効率的に横断し、任意の「特徴方向」でサンプルを収集し、(線形mdpと同等の)最大状態訪問確率で最適にスケールするサンプル複雑性を享受する、新しい手順に依存している。 線形MDPにおける「良条件」な共変量を得るためにも,この探索手法が適用可能であることを示す。

関連論文リスト

• Provable and Practical: Efficient Exploration in Reinforcement Learning via Langevin Monte Carlo [104.9535542833054]
  我々は、強化学習のためのトンプソンサンプリングに基づくスケーラブルで効果的な探索戦略を提案する。 代わりに、Langevin Monte Carlo を用いて、Q 関数をその後部分布から直接サンプリングする。 提案手法は,Atari57スイートからのいくつかの挑戦的な探索課題において,最先端の深部RLアルゴリズムと比較して,より優れた,あるいは類似した結果が得られる。
  論文  参考訳（メタデータ） (2023-05-29T17:11:28Z)
• Improved Sample Complexity for Reward-free Reinforcement Learning under Low-rank MDPs [43.53286390357673]
  本稿では,低ランクMDPモデルによる報酬なし強化学習に焦点を当てた。 我々はまず、低ランクのMDPの下での任意のアルゴリズムに対して、最初の既知のサンプル複雑性の低い境界を提供する。 次に、RAFFLEと呼ばれる新しいモデルベースアルゴリズムを提案し、$epsilon$-optimal Policyを見つけ、$epsilon$-accurate system IDを実現できることを示す。
  論文  参考訳（メタデータ） (2023-03-20T04:39:39Z)
• 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)
• Provably Efficient Offline Reinforcement Learning with Trajectory-Wise Reward [66.81579829897392]
  我々はPessimistic vAlue iteRaTionとrEward Decomposition (PARTED)という新しいオフライン強化学習アルゴリズムを提案する。 PartEDは、最小2乗ベースの報酬再分配を通じて、ステップごとのプロキシ報酬に軌道を分解し、学習したプロキシ報酬に基づいて悲観的な値を実行する。 私たちの知る限りでは、PartEDは、トラジェクティブな報酬を持つ一般のMDPにおいて、証明可能な効率のよい最初のオフラインRLアルゴリズムである。
  論文  参考訳（メタデータ） (2022-06-13T19:11:22Z)
• 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)
• On Reward-Free Reinforcement Learning with Linear Function Approximation [144.4210285338698]
  Reward-free reinforcement learning (RL) は、バッチRL設定と多くの報酬関数がある設定の両方に適したフレームワークである。 本研究では,線形関数近似を用いた報酬のないRLに対して,正と負の両方の結果を与える。
  論文  参考訳（メタデータ） (2020-06-19T17:59:36Z)

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

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