論文の概要: 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における「良条件」な共変量を得るためにも,この探索手法が適用可能であることを示す。
関連論文リスト
- Near-Optimal Deployment Efficiency in Reward-Free Reinforcement Learning
with Linear Function Approximation [16.871660060209674]
本研究では, 線形関数近似を用いた展開効率向上強化学習(RL)の課題を, 遠近自由探索条件下で検討する。
我々は,最大$widetildeO(fracd2H5epsilon2)$ trajectoriesを$H$デプロイメント内で収集し,$epsilon$-Optimal Policyを任意の(おそらくはデータに依存した)報酬関数の選択に対して識別するアルゴリズムを提案する。
論文 参考訳(メタデータ) (2022-10-03T03:48:26Z) - Provably Efficient Offline Reinforcement Learning with Trajectory-Wise
Reward [65.09383385484007]
我々はPessimistic vAlue iteRaTionとrEward Decomposition (PARTED)という新しいオフライン強化学習アルゴリズムを提案する。
PartEDは、最小2乗ベースの報酬再分配を通じて、ステップごとのプロキシ報酬に軌道を分解し、学習したプロキシ報酬に基づいて悲観的な値を実行する。
私たちの知る限りでは、PartEDは、トラジェクティブな報酬を持つ一般のMDPにおいて、証明可能な効率のよい最初のオフラインRLアルゴリズムである。
論文 参考訳(メタデータ) (2022-06-13T19:11:22Z) - Human-in-the-loop: Provably Efficient Preference-based Reinforcement
Learning with General Function Approximation [107.54516740713969]
本研究は,RL(Human-in-the-loop reinforcement learning)を軌道的嗜好で検討する。
各ステップで数値的な報酬を受ける代わりに、エージェントは人間の監督者から軌道上のペアよりも優先される。
一般関数近似を用いたPbRLの楽観的モデルベースアルゴリズムを提案する。
論文 参考訳(メタデータ) (2022-05-23T09:03:24Z) - Sample-Efficient Reinforcement Learning for POMDPs with Linear Function
Approximations [130.66193083412716]
本稿では,関数近似と部分観測可能性の緊張に対処する。
最適ポリシーと値関数は有限メモリヒルベルト・ベルマン作用素の列によって特徴づけられることを示す。
本稿では、カーネル空間(RKHS)の埋め込みを再現することで、これらの演算子の楽観的な推定値を構成するRLアルゴリズムを提案する。
論文 参考訳(メタデータ) (2022-04-20T21:15:38Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。