Fugu-MT 論文翻訳(概要): A Lower Bound for the Sample Complexity of Inverse Reinforcement Learning

論文の概要: A Lower Bound for the Sample Complexity of Inverse Reinforcement Learning

arxiv url: http://arxiv.org/abs/2103.04446v1
Date: Sun, 7 Mar 2021 20:29:10 GMT
ステータス: 処理完了
システム内更新日: 2021-03-09 15:56:56.994354
Title: A Lower Bound for the Sample Complexity of Inverse Reinforcement Learning
Title（参考訳）: 逆強化学習のサンプル複雑性のための下界
Authors: Abi Komanduru, Jean Honorio
Abstract要約: 逆強化学習(IRL)は、与えられたマルコフ決定過程(MDP)に対して望ましい最適ポリシーを生成する報酬関数を求めるタスクである。本稿では, 有限状態, 有限作用IRL問題のサンプル複雑性に対する情報理論の下界について述べる。
参考スコア（独自算出の注目度）: 26.384010313580596
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: Inverse reinforcement learning (IRL) is the task of finding a reward function that generates a desired optimal policy for a given Markov Decision Process (MDP). This paper develops an information-theoretic lower bound for the sample complexity of the finite state, finite action IRL problem. A geometric construction of $\beta$-strict separable IRL problems using spherical codes is considered. Properties of the ensemble size as well as the Kullback-Leibler divergence between the generated trajectories are derived. The resulting ensemble is then used along with Fano's inequality to derive a sample complexity lower bound of $O(n \log n)$, where $n$ is the number of states in the MDP.
Abstract（参考訳）: 逆強化学習(IRL)は、与えられたマルコフ決定プロセス(MDP)に対して望ましい最適ポリシーを生成する報酬関数を求めるタスクである。本稿では, 有限状態, 有限作用IRL問題のサンプル複雑性に対する情報理論の下界について述べる。球面符号を用いた $\beta$-strict separable IRL 問題の幾何学的構成を考える。生成した軌跡間のkullback-leibler発散と同様にアンサンブルサイズの性質を導出する。結果として得られるアンサンブルはファノの不等式とともに、mdp 内の状態数である $n$ で$o(n \log n)$ 以下のサンプル複雑性を導出するために用いられる。

関連論文リスト

Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
論文参考訳（メタデータ） (2024-05-10T09:58:47Z)
Settling the Sample Complexity of Online Reinforcement Learning [92.02082223856479]
バーンインコストを発生させることなく、最小限の最適後悔を実現する方法を示す。最適値/コストや一定の分散といった問題依存量の影響を明らかにするために、我々の理論を拡張します。
論文参考訳（メタデータ） (2023-07-25T15:42:11Z)
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)
Improved Sample Complexity Bounds for Distributionally Robust Reinforcement Learning [3.222802562733787]
トレーニング環境とテスト環境のパラメータミスマッチに対して頑健な制御ポリシーを学習することの問題点を考察する。本研究では,4つの異なる発散によって特定される不確実性集合に対して,ロバスト位相値学習(RPVL)アルゴリズムを提案する。提案アルゴリズムは,既存の結果より一様によいサンプル複雑性を$tildemathcalO(|mathcalSmathcalA| H5)$とする。
論文参考訳（メタデータ） (2023-03-05T21:47:08Z)
Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learning [52.76230802067506]
漸進的強化学習における後悔を最小限に抑えるために,新しいモデルフリーアルゴリズムを提案する。提案アルゴリズムは、2つのQ-ラーニングシーケンスの助けを借りて、初期設定された参照更新ルールを用いる。初期の分散還元法の設計原理は、他のRL設定とは独立した関心を持つかもしれない。
論文参考訳（メタデータ） (2021-10-09T21:13:48Z)
Towards Tight Bounds on the Sample Complexity of Average-reward MDPs [39.01663172393174]
生成モデルにアクセス可能な無限水平平均回帰マルコフ決定過程の最適方針を求める。状態-作用対あたりのサンプルを$widetildeO(t_mathrmmix epsilon-3)$ (oblivious) で解決するアルゴリズムを提案する。
論文参考訳（メタデータ） (2021-06-13T17:18:11Z)
Sample-Efficient Reinforcement Learning for Linearly-Parameterized MDPs with a Generative Model [3.749193647980305]
本稿では,一連の状態対応機能を有するマルコフ決定プロセス(MDP)について考察する。モデルに基づくアプローチ(resp.$Q-learning)が、高い確率で$varepsilon$-Optimalポリシーを確実に学習することを示す。
論文参考訳（メタデータ） (2021-05-28T17:49:39Z)
Tightening the Dependence on Horizon in the Sample Complexity of Q-Learning [59.71676469100807]
この研究は、同期Q-ラーニングのサンプルの複雑さを、任意の$0varepsilon 1$に対して$frac|mathcalS| (1-gamma)4varepsilon2$の順序に絞る。計算やストレージを余分に必要とせずに、高速なq-learningにマッチするvanilla q-learningの有効性を明らかにした。
論文参考訳（メタデータ） (2021-02-12T14:22:05Z)
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)

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