論文の概要: A Few Expert Queries Suffices for Sample-Efficient RL with Resets and Linear Value Approximation

• arxiv url: http://arxiv.org/abs/2207.08342v1
• Date: Mon, 18 Jul 2022 01:39:13 GMT
• ステータス: 処理完了
• システム内更新日: 2022-07-20 01:32:31.459325
• Title: A Few Expert Queries Suffices for Sample-Efficient RL with Resets and Linear Value Approximation
• Title（参考訳）: リセットと線形値近似を用いたサンプル効率rlのためのエキスパートクエリsuffices
• Authors: Philip Amortila, Nan Jiang, Dhruv Madeka, Dean P. Foster
• Abstract要約: 最適値関数のみを線形化可能な設定において、サンプル効率のよい強化学習(RL)について検討する。 専門的なクエリと探索をブレンドするための統計的・計算学的に効率的なアルゴリズム(Delphi)を提案する。 Delphi には $tildemathcalO(d)$ エキスパートクエリと $texttpoly(d,|mathcalA|,1/varepsilon)$ 探索サンプルの量が必要です。
• 参考スコア（独自算出の注目度）: 16.29514743112387
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The current paper studies sample-efficient Reinforcement Learning (RL) in settings where only the optimal value function is assumed to be linearly-realizable. It has recently been understood that, even under this seemingly strong assumption and access to a generative model, worst-case sample complexities can be prohibitively (i.e., exponentially) large. We investigate the setting where the learner additionally has access to interactive demonstrations from an expert policy, and we present a statistically and computationally efficient algorithm (Delphi) for blending exploration with expert queries. In particular, Delphi requires $\tilde{\mathcal{O}}(d)$ expert queries and a $\texttt{poly}(d,H,|\mathcal{A}|,1/\varepsilon)$ amount of exploratory samples to provably recover an $\varepsilon$-suboptimal policy. Compared to pure RL approaches, this corresponds to an exponential improvement in sample complexity with surprisingly-little expert input. Compared to prior imitation learning (IL) approaches, our required number of expert demonstrations is independent of $H$ and logarithmic in $1/\varepsilon$, whereas all prior work required at least linear factors of both in addition to the same dependence on $d$. Towards establishing the minimal amount of expert queries needed, we show that, in the same setting, any learner whose exploration budget is polynomially-bounded (in terms of $d,H,$ and $|\mathcal{A}|$) will require at least $\tilde\Omega(\sqrt{d})$ oracle calls to recover a policy competing with the expert's value function. Under the weaker assumption that the expert's policy is linear, we show that the lower bound increases to $\tilde\Omega(d)$.
• Abstract（参考訳）: 本論文は, 最適値関数のみを線形化可能な設定において, サンプル効率向上学習(RL)について検討する。 この一見強い仮定と生成モデルへのアクセスにもかかわらず、最悪のサンプルの複雑さは禁止的に(指数関数的に)大きいと理解されている。 学習者がエキスパートポリシーからインタラクティブなデモンストレーションにアクセスできるような設定について検討し、専門家クエリと探索をブレンドするための統計的かつ計算的に効率的なアルゴリズム(Delphi)を提案する。 特にdelphiには、$\tilde{\mathcal{o}}(d)$ エキスパートクエリと$\texttt{poly}(d,h,|\mathcal{a}|,1/\varepsilon)$ の探索的なサンプルが要求され、$\varepsilon$-suboptimalポリシーが確実に回収される。 純粋なRLアプローチと比較して、これは驚くほど少ない専門家入力によるサンプル複雑性の指数関数的な改善に対応する。 従来の模倣学習 (IL) のアプローチと比較して,我々の要求する専門家のデモンストレーションの数は$H$と$/\varepsilon$の対数性とは無関係である。 必要最小限のエキスパートクエリの確立に向けて、同じ設定で、探索予算が多項式境界($d,H,$および$|\mathcal{A}|$)を持つ学習者は、少なくとも$\tilde\Omega(\sqrt{d})$ oracleが専門家の値関数と競合するポリシーを回復するために必要であることを示す。 専門家のポリシーが線型であるというより弱い仮定の下で、下界が$\tilde\Omega(d)$に増加することを示す。

関連論文リスト

• Computational-Statistical Gaps for Improper Learning in Sparse Linear Regression [4.396860522241307]
  疎線形回帰の効率的な学習アルゴリズムは, 負のスパイクを持つスパースPCA問題を解くのに有効であることを示す。 我々は,低次および統計的クエリの低い境界を減らしたスパース問題に対して補う。
  論文  参考訳（メタデータ） (2024-02-21T19:55:01Z)
• Learning Thresholds with Latent Values and Censored Feedback [18.129896050051432]
  未知の報酬$g(gamma, v)$が提案されたしきい値$gamma$と潜伏値$v$に依存する問題を示し、そのしきい値が未知の潜伏値よりも低い場合のみ$$を達成できる。 この問題は、オンラインオークションにおける予約価格の最適化、クラウドソーシングにおけるオンラインタスクの割り当て、雇用におけるリクルートバーの設定など、現実的なシナリオにおける幅広い応用がある。
  論文  参考訳（メタデータ） (2023-12-07T19:30:08Z)
• Demonstration-Regularized RL [39.96273388393764]
  専門的な実証から,次数$widetildeO(mathrmPoly(S,A,H)/(varepsilon2 NmathrmE)$および$widetildeO(mathrmPoly(d,H)/(varepsilon2 NmathrmE)$の線形マルコフ決定過程における最適ポリシを同定した。 実演規則化手法が人間のフィードバックからの強化学習に有効であることを示す。
  論文  参考訳（メタデータ） (2023-10-26T10:54:47Z)
• Fast Rates for Maximum Entropy Exploration [52.946307632704645]
  エージェントが未知の環境下で活動し、報酬が得られない場合、強化学習(RL)における探索の課題に対処する。 本研究では,最大エントロピー探索問題を2つの異なるタイプで検討する。 訪問エントロピーには、$widetildemathcalO(H3S2A/varepsilon2)$ sample complexity を持つゲーム理論アルゴリズムを提案する。 軌道エントロピーに対しては,次数$widetildemathcalO(mathrmpoly(S,)の複雑さのサンプルを持つ単純なアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-03-14T16:51:14Z)
• Overcoming the Long Horizon Barrier for Sample-Efficient Reinforcement Learning with Latent Low-Rank Structure [9.759209713196718]
  我々は、対応する最適$Q*$関数が低ランクであるMDPのクラスを考える。 より強い低階構造仮定の下では、生成モデル(LR-MCPI)と低階経験値イテレーション(LR-EVI)が、ランクに対して$tildeOleft((|S|+|A|)mathrmpoly(d,H)/epsilon2right)$の所望のサンプル複雑性を実現することが示されている。
  論文  参考訳（メタデータ） (2022-06-07T20:39:51Z)
• Agnostic Reinforcement Learning with Low-Rank MDPs and Rich Observations [79.66404989555566]
  我々は、リッチな観測空間を持つより現実的な非依存的RLの設定と、近似的ポリシーを含まないような固定されたポリシーのクラス$Pi$を考える。 我々は,MDPの階数$d$の誤差が有界な設定のためのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-06-22T03:20:40Z)
• Online Sub-Sampling for Reinforcement Learning with General Function Approximation [111.01990889581243]
  本稿では,RLアルゴリズムによって収集されたデータポイントの情報取得量を測定する,効率的なオンラインサブサンプリングフレームワークを確立する。 複雑性バウンド関数クラスを持つ値ベースのメソッドの場合、$proptooperatornamepolylog(K)$ timesに対してのみポリシーを更新する必要がある。 少なくとも$Omega(K)$倍のポリシーを更新する既存のアプローチとは対照的に、当社のアプローチはポリシーの解決における最適化コールの数を劇的に削減します。
  論文  参考訳（メタデータ） (2021-06-14T07:36:25Z)
• On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spaces [208.67848059021915]
  強化学習のコアにおける探索・探索トレードオフについて検討する。 特に、関数クラス $mathcalF$ の複雑さが関数の複雑さを特徴づけていることを証明する。 私たちの後悔の限界はエピソードの数とは無関係です。
  論文  参考訳（メタデータ） (2020-11-09T18:32:22Z)
• Linear-Sample Learning of Low-Rank Distributions [56.59844655107251]
  ktimes k$, rank-r$, matrices to normalized $L_1$ distance requires $Omega(frackrepsilon2)$ sample。 我々は、$cal O(frackrepsilon2log2fracepsilon)$ sample, a number linear in the high dimension, and almost linear in the matrices, usually low, rank proofs.というアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-09-30T19:10:32Z)
• 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)
• Sample Efficient Reinforcement Learning via Low-Rank Matrix Estimation [30.137884459159107]
  連続状態と行動空間を用いた強化学習において,Q$関数を効率よく学習する方法を考える。 我々は、$epsilon$-Schmidt $Q$-functionと$widetildeO(frac1epsilonmax(d1, d_2)+2)$のサンプル複雑性を求める単純な反復学習アルゴリズムを開発する。
  論文  参考訳（メタデータ） (2020-06-11T00:55:35Z)

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

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