論文の概要: Provably Breaking the Quadratic Error Compounding Barrier in Imitation
Learning, Optimally
- arxiv url: http://arxiv.org/abs/2102.12948v1
- Date: Thu, 25 Feb 2021 15:50:19 GMT
- ステータス: 処理完了
- システム内更新日: 2021-02-26 14:00:22.246671
- Title: Provably Breaking the Quadratic Error Compounding Barrier in Imitation
Learning, Optimally
- Title（参考訳）: 模倣学習における二次誤差複合障壁を最適に破る
- Authors: Nived Rajaraman, Yanjun Han, Lin F. Yang, Kannan Ramchandran, Jiantao
Jiao
- Abstract要約: 状態空間 $mathcalS$ を用いたエピソードマルコフ決定過程 (MDPs) における模擬学習の統計的限界について検討する。
rajaraman et al (2020) におけるmdアルゴリズムを用いた準最適性に対する上限 $o(|mathcals|h3/2/n)$ を定式化する。
Omega(H3/2/N)$ $mathcalS|geq 3$ であるのに対して、未知の遷移条件はよりシャープレートに悩まされる。
- 参考スコア（独自算出の注目度）: 58.463668865380946
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the statistical limits of Imitation Learning (IL) in episodic Markov
Decision Processes (MDPs) with a state space $\mathcal{S}$. We focus on the
known-transition setting where the learner is provided a dataset of $N$
length-$H$ trajectories from a deterministic expert policy and knows the MDP
transition. We establish an upper bound $O(|\mathcal{S}|H^{3/2}/N)$ for the
suboptimality using the Mimic-MD algorithm in Rajaraman et al (2020) which we
prove to be computationally efficient. In contrast, we show the minimax
suboptimality grows as $\Omega( H^{3/2}/N)$ when $|\mathcal{S}|\geq 3$ while
the unknown-transition setting suffers from a larger sharp rate
$\Theta(|\mathcal{S}|H^2/N)$ (Rajaraman et al (2020)). The lower bound is
established by proving a two-way reduction between IL and the value estimation
problem of the unknown expert policy under any given reward function, as well
as building connections with linear functional estimation with subsampled
observations. We further show that under the additional assumption that the
expert is optimal for the true reward function, there exists an efficient
algorithm, which we term as Mimic-Mixture, that provably achieves suboptimality
$O(1/N)$ for arbitrary 3-state MDPs with rewards only at the terminal layer. In
contrast, no algorithm can achieve suboptimality $O(\sqrt{H}/N)$ with high
probability if the expert is not constrained to be optimal. Our work formally
establishes the benefit of the expert optimal assumption in the known
transition setting, while Rajaraman et al (2020) showed it does not help when
transitions are unknown.
- Abstract（参考訳）: 我々は、状態空間 $\mathcal{S}$ を持つ韻律マルコフ決定過程 (MDPs) における模擬学習 (IL) の統計的限界について研究する。
我々は,学習者が決定論的専門家政策からN$長-H$トラジェクトリのデータセットを提供し,MDP遷移を知るような既知の移行設定に焦点を当てる。
上界の $O(|\mathcal{S}|H^{3/2}/N)$ を、Rajaraman et al (2020) の Mimic-MD アルゴリズムを用いて最適化し、計算効率を証明した。
対照的に、minimax suboptimality は $\Omega(H^{3/2}/N)$ が $|\mathcal{S}|\geq 3$ であるのに対して、未知の遷移条件はより大きいシャープレート $\Theta(|\mathcal{S}|H^2/N)$ (Rajaraman et al (2020) ) である。
下界は、任意の報酬関数の下で、ILと未知の専門家ポリシーの値推定問題との双方向の低減を証明し、サブサンプル観測による線形関数推定との接続を構築することにより確立される。
さらに、エキスパートが真の報酬関数に最適であるという仮定が加わり、終端層にのみ報酬を持つ任意の3状態のMDPに対して、その準最適性(O(1/N)$)を確実に達成する効率的なアルゴリズムが存在することを示す。
対照的に、専門家が最適に制約されない場合、アルゴリズムは高い確率で準最適$O(\sqrt{H}/N)$を達成できない。
我々の研究は、既知の遷移設定において、専門家の最適仮定の利点を正式に確立する一方、Rajaraman et al (2020) は遷移が不明な場合に役に立たないことを示した。
関連論文リスト
- Randomized Exploration for Reinforcement Learning with Multinomial Logistic Function Approximation [8.274693573069442]
多項ロジスティック(MNL)関数近似を用いた強化学習について検討した。
頻繁な後悔の保証を有するランダムな探索を伴う確率的効率のアルゴリズムを提案する。
数値実験により提案アルゴリズムの優れた性能を示す。
論文 参考訳（メタデータ） (2024-05-30T15:39:19Z) - Improved Algorithm for Adversarial Linear Mixture MDPs with Bandit
Feedback and Unknown Transition [71.33787410075577]
線形関数近似,未知遷移,および逆損失を用いた強化学習について検討した。
我々は高い確率で$widetildeO(dsqrtHS3K + sqrtHSAK)$ regretを実現する新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-03-07T15:03:50Z) - Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳（メタデータ） (2024-02-14T07:52:00Z) - Optimism in Face of a Context: Regret Guarantees for Stochastic
Contextual MDP [46.86114958340962]
我々は,最小到達可能性仮定の下での文脈的MDPに対する後悔のアルゴリズムを提案する。
我々のアプローチは、一般関数近似を用いた文脈的MDPに適用された最初の楽観的アプローチである。
論文 参考訳（メタデータ） (2022-07-22T15:00:15Z) - Nearly Minimax Optimal Reinforcement Learning with Linear Function
Approximation [25.60689712525918]
本稿では,遷移確率と報酬関数が線形な線形関数近似を用いた強化学習について検討する。
本稿では,新たなアルゴリズムLSVI-UCB$+$を提案し,$H$がエピソード長,$d$が特徴次元,$T$がステップ数である場合に,$widetildeO(HdsqrtT)$ regretboundを実現する。
論文 参考訳（メタデータ） (2022-06-23T06:04:21Z) - Computationally Efficient Horizon-Free Reinforcement Learning for Linear
Mixture MDPs [111.75736569611159]
線形混合MDPのための計算効率のよい初めての地平線フリーアルゴリズムを提案する。
我々のアルゴリズムは、未知の遷移力学に対する重み付き最小二乗推定器に適応する。
これにより、$sigma_k2$'sが知られているときに、この設定で最もよく知られたアルゴリズムも改善される。
論文 参考訳（メタデータ） (2022-05-23T17:59:18Z) - Nearly Optimal Regret for Learning Adversarial MDPs with Linear Function
Approximation [92.3161051419884]
我々は、敵対的な報酬と完全な情報フィードバックで有限正方体エピソディックマルコフ決定プロセスのための強化学習を研究します。
我々は、$tildeO(dHsqrtT)$ regretを達成できることを示し、$H$はエピソードの長さである。
また、対数因子までの$tildeOmega(dHsqrtT)$の値が一致することを証明する。
論文 参考訳（メタデータ） (2021-02-17T18:54:08Z) - Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov
Decision Processes [91.38793800392108]
本稿では,マルコフ決定過程(MDP)の遷移確率核が線形混合モデルである線形関数近似による強化学習について検討する。
上記の線形混合 MDP に対して$textUCRL-VTR+$ という線形関数近似を用いた計算効率の良い新しいアルゴリズムを提案する。
我々の知る限り、これらは線形関数近似を持つRLのための計算効率が良く、ほぼ最小のアルゴリズムである。
論文 参考訳（メタデータ） (2020-12-15T18:56:46Z) - Toward the Fundamental Limits of Imitation Learning [29.87139380803829]
シミュレーション学習(IL)は、実演のみを与えられた逐次的な意思決定問題において、専門家の政策の振る舞いを模倣することを目的としている。
まず,学習者が事前に$N$のエキスパートトラジェクトリのデータセットを提供して,MDPと対話できないような設定について検討する。
可能な限り専門家を模倣するポリシーは、専門家が任意のポリシーに従う場合でも、専門家の値と比較すると、$lesssim frac|mathcalS| H2 log (N)N$ suboptimalであることを示す。
論文 参考訳（メタデータ） (2020-09-13T12:45:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。