論文の概要: Trajectory Data Suffices for Statistically Efficient Learning in Offline RL with Linear $q^π$-Realizability and Concentrability
- arxiv url: http://arxiv.org/abs/2405.16809v1
- Date: Mon, 27 May 2024 03:59:13 GMT
- ステータス: 処理完了
- システム内更新日: 2024-05-28 19:06:16.181884
- Title: Trajectory Data Suffices for Statistically Efficient Learning in Offline RL with Linear $q^π$-Realizability and Concentrability
- Title（参考訳）: 線形$q^π$-Realizabilityと集中度を持つオフラインRLにおける統計的に効率的な学習のための軌道データ
- Authors: Volodymyr Tkachuk, Gellért Weisz, Csaba Szepesvári,
- Abstract要約: H$-horizon Markov decision process(MDPs)におけるオフライン強化学習(RL)
トラジェクトリデータでは、$textpoly(d,H,C_textconc)/epsilon2$のデータセットは、$epsilon$-optimal Policyを導出するのに十分であることを示す。
- 参考スコア（独自算出の注目度）: 34.51093353030245
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider offline reinforcement learning (RL) in $H$-horizon Markov decision processes (MDPs) under the linear $q^\pi$-realizability assumption, where the action-value function of every policy is linear with respect to a given $d$-dimensional feature function. The hope in this setting is that learning a good policy will be possible without requiring a sample size that scales with the number of states in the MDP. Foster et al. [2021] have shown this to be impossible even under $\textit{concentrability}$, a data coverage assumption where a coefficient $C_\text{conc}$ bounds the extent to which the state-action distribution of any policy can veer off the data distribution. However, the data in this previous work was in the form of a sequence of individual transitions. This leaves open the question of whether the negative result mentioned could be overcome if the data was composed of sequences of full trajectories. In this work we answer this question positively by proving that with trajectory data, a dataset of size $\text{poly}(d,H,C_\text{conc})/\epsilon^2$ is sufficient for deriving an $\epsilon$-optimal policy, regardless of the size of the state space. The main tool that makes this result possible is due to Weisz et al. [2023], who demonstrate that linear MDPs can be used to approximate linearly $q^\pi$-realizable MDPs. The connection to trajectory data is that the linear MDP approximation relies on "skipping" over certain states. The associated estimation problems are thus easy when working with trajectory data, while they remain nontrivial when working with individual transitions. The question of computational efficiency under our assumptions remains open.
- Abstract（参考訳）: 線形$q^\pi$-realizability(英語版)仮定の下では、任意のポリシーのアクション値関数が与えられた$d$次元特徴関数に対して線形となるような、オフライン強化学習 (RL) を$H$-horizon Markov決定プロセス (MDPs) で考える。
この設定では、MDP内の状態の数に合わせてスケールするサンプルサイズを必要とせずに、優れた政策を学ぶことができると期待されている。
Foster et al [2021]は、$\textit{concentrability}$の下では、係数$C_\text{conc}$が任意のポリシーの状態-作用分布がデータ分布を逸脱できる範囲に制限される、データカバレッジの仮定でさえ、これを不可能であることを示した。
しかし、この前の研究で得られたデータは、個々の遷移のシーケンスの形式であった。
このことは、データが完全な軌跡の列で構成されていた場合、上述した負の結果が克服できるかどうかという疑問を解き放つ。
この研究では、軌跡データを用いて、状態空間のサイズに関わらず、$\epsilon$-optimal Policyを導出するのに十分なサイズのデータセット $\text{poly}(d,H,C_\text{conc})/\epsilon^2$ が十分であることを証明することによって、この質問に答える。
この結果を可能にする主なツールはWeisz et al [2023] によるものであり、線形 MDP が線形に$q^\pi$-realizable MDP を近似するために使用できることを示すものである。
軌道データとのつながりは、線形MDP近似が特定の状態の「スキップ」に依存することである。
関連する推定問題は、軌跡データを扱う際には容易であるが、個々の遷移を扱う際には非自明なままである。
我々の仮定による計算効率の問題はまだ未解決である。
関連論文リスト
- Online RL in Linearly $q^\pi$-Realizable MDPs Is as Easy as in Linear
MDPs If You Learn What to Ignore [0.0]
エピソードマルコフ決定過程(MDP)におけるオンライン強化学習の検討
2つのクラスの違いは、線形に$qpi$-realizable MDPにおける状態の存在であることを示す。
線形$qpi$-realizable MDPのための新しい(計算非効率な)学習アルゴリズムを導出する。
論文 参考訳（メタデータ） (2023-10-11T18:50:25Z) - On Instance-Dependent Bounds for Offline Reinforcement Learning with
Linear Function Approximation [80.86358123230757]
本稿では,Bootstrapped and Constrained Pessimistic Value Iteration (BCP-VI) というアルゴリズムを提案する。
部分的なデータカバレッジの仮定の下で、BCP-VI は最適な Q-値関数に正のギャップがあるときに、オフライン RL に対して $tildemathcalO(frac1K)$ の高速レートを得る。
これらは、アダプティブデータからの線形関数近似を持つオフラインRLに対してそれぞれ、最初の$tildemathcalO(frac1K)$boundと絶対零部分最適境界である。
論文 参考訳（メタデータ） (2022-11-23T18:50:44Z) - Provably Efficient Offline Reinforcement Learning with Trajectory-Wise
Reward [66.81579829897392]
我々はPessimistic vAlue iteRaTionとrEward Decomposition (PARTED)という新しいオフライン強化学習アルゴリズムを提案する。
PartEDは、最小2乗ベースの報酬再分配を通じて、ステップごとのプロキシ報酬に軌道を分解し、学習したプロキシ報酬に基づいて悲観的な値を実行する。
私たちの知る限りでは、PartEDは、トラジェクティブな報酬を持つ一般のMDPにおいて、証明可能な効率のよい最初のオフラインRLアルゴリズムである。
論文 参考訳（メタデータ） (2022-06-13T19:11:22Z) - Pessimism in the Face of Confounders: Provably Efficient Offline Reinforcement Learning in Partially Observable Markov Decision Processes [99.26864533035454]
半可観測マルコフ決定過程におけるオフライン強化学習(RL)について検討する。
本稿では,UnderlineProxy変数 underlinePessimistic UnderlinePolicy UnderlineOptimization (textttP3O)アルゴリズムを提案する。
textttP3Oは、確立されたデータセットを持つPOMDPのための証明可能な最初のオフラインRLアルゴリズムである。
論文 参考訳（メタデータ） (2022-05-26T19:13:55Z) - Settling the Sample Complexity of Model-Based Offline Reinforcement
Learning [50.5790774201146]
オフライン強化学習(RL)は、事前収集されたデータを用いて、さらなる探索を行わずに学習する。
事前のアルゴリズムや分析は、最適なサンプルの複雑さに悩まされるか、サンプルの最適性に到達するために高いバーンインコストがかかるかのいずれかである。
モデルベース(あるいは"プラグイン")アプローチは,バーンインコストを伴わずに,最小限のサンプル複雑性を実現することを実証する。
論文 参考訳（メタデータ） (2022-04-11T17:26:19Z) - Reward-Free RL is No Harder Than Reward-Aware RL in Linear Markov
Decision Processes [61.11090361892306]
Reward-free reinforcement learning (RL) は、エージェントが探索中に報酬関数にアクセスできないような環境を考える。
この分離は線形MDPの設定には存在しないことを示す。
我々は$d$次元線形 MDP における報酬のない RL に対する計算効率の良いアルゴリズムを開発した。
論文 参考訳（メタデータ） (2022-01-26T22:09:59Z) - Towards Instance-Optimal Offline Reinforcement Learning with Pessimism [34.54294677335518]
我々は、未知マルコフ決定過程(MDP)における報酬最大化ポリシーの学習を目標とするオフライン強化学習(オフラインRL)問題について検討する。
本研究では、適応悲観的値反復法(APVI)アルゴリズムを分析し、[Oleft(sum_h=1Hsum_s_h,a_hdpistar_h(s_h,a_h)sqrtfracmathrmmathrmVar_]とほぼ一致する準最適上限を導出する。
論文 参考訳（メタデータ） (2021-10-17T01:21:52Z) - Reward-Free Model-Based Reinforcement Learning with Linear Function
Approximation [92.99933928528797]
エピソードマルコフ決定過程(MDP)に対する線形関数近似を用いたモデルに基づく無報酬強化学習について検討する。
計画段階では、特定の報酬関数が与えられ、探索フェーズから収集したサンプルを使用して良い政策を学ぶ。
任意の報酬関数に対して$epsilon$-optimal Policyを得るには,最大$tilde O(H4d(H + d)epsilon-2)$ episodesをサンプリングする必要がある。
論文 参考訳（メタデータ） (2021-10-12T23:03:58Z) - On Query-efficient Planning in MDPs under Linear Realizability of the
Optimal State-value Function [14.205660708980988]
固定水平マルコフ決定過程(MDP)における局所的計画の問題点を生成モデルを用いて考察する。
最近の下界は、最適ポリシーの作用値関数が線形に実現可能である場合の関連する問題は指数的なクエリ数を必要とすることを証明している。
本研究では,アクションセットが小さい場合,ポリ$(H, d)$学習が(状態値関数の実現可能性を持つ)可能であることを確かめる。
論文 参考訳（メタデータ） (2021-02-03T13:23:15Z) - Online Robust Regression via SGD on the l1 loss [19.087335681007477]
ストリーミング方式でデータにアクセス可能なオンライン環境において、ロバストな線形回帰問題を考察する。
この研究で、$ell_O( 1 / (1 - eta)2 n )$損失の降下は、汚染された測定値に依存しない$tildeO( 1 / (1 - eta)2 n )$レートで真のパラメータベクトルに収束することを示した。
論文 参考訳（メタデータ） (2020-07-01T11:38:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。