論文の概要: Toward the Fundamental Limits of Imitation Learning
- arxiv url: http://arxiv.org/abs/2009.05990v1
- Date: Sun, 13 Sep 2020 12:45:52 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-19 02:34:55.518290
- Title: Toward the Fundamental Limits of Imitation Learning
- Title（参考訳）: 模倣学習の基本限界に向けて
- Authors: Nived Rajaraman, Lin F. Yang, Jiantao Jiao, Kannan Ramachandran
- Abstract要約: シミュレーション学習(IL)は、実演のみを与えられた逐次的な意思決定問題において、専門家の政策の振る舞いを模倣することを目的としている。
まず,学習者が事前に$N$のエキスパートトラジェクトリのデータセットを提供して,MDPと対話できないような設定について検討する。
可能な限り専門家を模倣するポリシーは、専門家が任意のポリシーに従う場合でも、専門家の値と比較すると、$lesssim frac|mathcalS| H2 log (N)N$ suboptimalであることを示す。
- 参考スコア（独自算出の注目度）: 29.87139380803829
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Imitation learning (IL) aims to mimic the behavior of an expert policy in a
sequential decision-making problem given only demonstrations. In this paper, we
focus on understanding the minimax statistical limits of IL in episodic Markov
Decision Processes (MDPs). We first consider the setting where the learner is
provided a dataset of $N$ expert trajectories ahead of time, and cannot
interact with the MDP. Here, we show that the policy which mimics the expert
whenever possible is in expectation $\lesssim \frac{|\mathcal{S}| H^2 \log
(N)}{N}$ suboptimal compared to the value of the expert, even when the expert
follows an arbitrary stochastic policy. Here $\mathcal{S}$ is the state space,
and $H$ is the length of the episode. Furthermore, we establish a suboptimality
lower bound of $\gtrsim |\mathcal{S}| H^2 / N$ which applies even if the expert
is constrained to be deterministic, or if the learner is allowed to actively
query the expert at visited states while interacting with the MDP for $N$
episodes. To our knowledge, this is the first algorithm with suboptimality
having no dependence on the number of actions, under no additional assumptions.
We then propose a novel algorithm based on minimum-distance functionals in the
setting where the transition model is given and the expert is deterministic.
The algorithm is suboptimal by $\lesssim \min \{ H \sqrt{|\mathcal{S}| / N} ,\
|\mathcal{S}| H^{3/2} / N \}$, showing that knowledge of transition improves
the minimax rate by at least a $\sqrt{H}$ factor.
- Abstract（参考訳）: 模倣学習(il)は、デモンストレーションのみを与えられた逐次意思決定問題において、専門家ポリシーの振る舞いを模倣することを目的としている。
本稿では,マルコフ決定過程(MDP)におけるILの最小統計限界を理解することに焦点を当てる。
まず,学習者が事前に$N$のエキスパートトラジェクトリのデータセットを提供して,MDPと対話できないような設定について検討する。
ここでは、専門家を可能な限り模倣するポリシーは、専門家が任意の確率的ポリシーに従う場合でも、専門家の値と比較すると、$\lesssim \frac{|\mathcal{S}| H^2 \log (N)}{N}$ suboptimalであることを示す。
ここで$\mathcal{S}$は状態空間であり、$H$はエピソードの長さである。
さらに、エキスパートが決定論的であることに制約されている場合や、学習者が訪問状態のエキスパートにN$のエピソードでMDPと対話しながら積極的に問い合わせることが許されている場合であっても、サブ最適下限の$\gtrsim |\mathcal{S}| H^2 / N$を確立する。
我々の知る限り、このアルゴリズムは、追加の仮定なしで、アクションの数に依存しない最適でない最初のアルゴリズムである。
次に、遷移モデルが与えられ、専門家が決定論的な設定において、最小距離関数に基づく新しいアルゴリズムを提案する。
このアルゴリズムは、$\lesssim \min \{ H \sqrt{|\mathcal{S}| / N} ,\ |\mathcal{S}| H^{3/2} / N \}$ によって最適化され、遷移の知識が少なくとも$\sqrt{H}$因子によってミニマックス率を改善することを示す。
関連論文リスト
- A Doubly Robust Approach to Sparse Reinforcement Learning [19.68978899041642]
エピソードスパークリニアマルコフ決定過程(SMDP)に対する新しい後悔アルゴリズムを提案する。
提案アルゴリズムは$tildeO(sigma-1_min s_star H sqrtN)$である。
論文 参考訳（メタデータ） (2023-10-23T18:52:17Z) - Horizon-free Reinforcement Learning in Adversarial Linear Mixture MDPs [72.40181882916089]
我々のアルゴリズムが $tildeObig((d+log (|mathcalS|2 |mathcalA|))sqrtKbig)$ regret with full-information feedback, where $d$ is the dimension of a known feature mapping is linearly parametrizing the unknown transition kernel of the MDP, $K$ is the number of episodes, $|mathcalS|$ and $|mathcalA|$ is the standardities of the state and action space。
論文 参考訳（メタデータ） (2023-05-15T05:37:32Z) - Optimism in Face of a Context: Regret Guarantees for Stochastic
Contextual MDP [46.86114958340962]
我々は,最小到達可能性仮定の下での文脈的MDPに対する後悔のアルゴリズムを提案する。
我々のアプローチは、一般関数近似を用いた文脈的MDPに適用された最初の楽観的アプローチである。
論文 参考訳（メタデータ） (2022-07-22T15:00:15Z) - Gap-Dependent Unsupervised Exploration for Reinforcement Learning [40.990467706237396]
タスクに依存しない強化学習のための効率的なアルゴリズムを提案する。
このアルゴリズムは1/epsilon cdot (H3SA / rho + H4 S2 A) の$widetildemathcalOのみを探索する。
情報理論上、この境界は$rho Theta (1/(HS))$と$H>1$に対してほぼ厳密であることを示す。
論文 参考訳（メタデータ） (2021-08-11T20:42:46Z) - Minimax Regret for Stochastic Shortest Path [63.45407095296692]
我々は、エージェントが最小の総予想コストで目標状態に達する必要がある最短パス(SSP)問題を研究します。
この設定に対するminimaxの後悔は、$widetilde O(B_star sqrt|S| |A|K)$であり、$B_star$は任意の状態から最適なポリシーの予想コストに拘束されることを示しています。
本アルゴリズムは, 有限水平MDPにおける強化学習の新たな削減を基礎として, エピソードごとのインタイム動作を行う。
論文 参考訳（メタデータ） (2021-03-24T10:11:49Z) - Provably Breaking the Quadratic Error Compounding Barrier in Imitation
Learning, Optimally [58.463668865380946]
状態空間 $mathcalS$ を用いたエピソードマルコフ決定過程 (MDPs) における模擬学習の統計的限界について検討する。
rajaraman et al (2020) におけるmdアルゴリズムを用いた準最適性に対する上限 $o(|mathcals|h3/2/n)$ を定式化する。
Omega(H3/2/N)$ $mathcalS|geq 3$ であるのに対して、未知の遷移条件はよりシャープレートに悩まされる。
論文 参考訳（メタデータ） (2021-02-25T15:50:19Z) - Learning Near Optimal Policies with Low Inherent Bellman Error [115.16037976819331]
エピソード強化学習における近似線形作用値関数を用いた探索問題について検討する。
我々は,検討した設定に対して最適な統計率を達成するアルゴリズムを用いて,Emphbatch仮定のみを用いて探索を行うことが可能であることを示す。
論文 参考訳（メタデータ） (2020-02-29T02:02:40Z) - Near-optimal Regret Bounds for Stochastic Shortest Path [63.029132134792555]
最短経路 (SSP) は計画と制御においてよく知られた問題であり、エージェントは最小の総コストで目標状態に到達する必要がある。
任意の学習アルゴリズムは、最悪の場合、少なくとも$Omega(B_star sqrt|S| |A|K)$後悔しなければならない。
論文 参考訳（メタデータ） (2020-02-23T09:10:14Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。