論文の概要: Achieving the Minimax Optimal Sample Complexity of Offline Reinforcement
Learning: A DRO-Based Approach
- arxiv url: http://arxiv.org/abs/2305.13289v3
- Date: Sun, 3 Dec 2023 23:00:11 GMT
- ステータス: 処理完了
- システム内更新日: 2023-12-05 23:31:48.357944
- Title: Achieving the Minimax Optimal Sample Complexity of Offline Reinforcement
Learning: A DRO-Based Approach
- Title（参考訳）: オフライン強化学習におけるミニマックス最適サンプル複雑さの達成:DROに基づくアプローチ
- Authors: Yue Wang, Jinjun Xiong, Shaofeng Zou
- Abstract要約: オフライン強化学習は、アクティブな探索なしに、事前に収集されたデータセットから学習することを目的としている。
既存のアプローチでは、探索されていない状態-作用対の報酬を罰することで不確実性に対する悲観的なスタンスを採用している。
分布的にロバストな最適化手法はこれらの課題にも対処でき、最小限の最適化であることを示す。
- 参考スコア（独自算出の注目度）: 41.45280954901834
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Offline reinforcement learning aims to learn from pre-collected datasets
without active exploration. This problem faces significant challenges,
including limited data availability and distributional shifts. Existing
approaches adopt a pessimistic stance towards uncertainty by penalizing rewards
of under-explored state-action pairs to estimate value functions
conservatively. In this paper, we show that the distributionally robust
optimization (DRO) based approach can also address these challenges and is
minimax optimal. Specifically, we directly model the uncertainty in the
transition kernel and construct an uncertainty set of statistically plausible
transition kernels. We then find the policy that optimizes the worst-case
performance over this uncertainty set. We first design a metric-based
Hoeffding-style uncertainty set such that with high probability the true
transition kernel is in this set. We prove that to achieve a sub-optimality gap
of $\epsilon$, the sample complexity is
$\mathcal{O}(S^2C^{\pi^*}\epsilon^{-2}(1-\gamma)^{-4})$, where $\gamma$ is the
discount factor, $S$ is the number of states, and $C^{\pi^*}$ is the
single-policy clipped concentrability coefficient which quantifies the
distribution shift. To achieve the optimal sample complexity, we further
propose a less conservative Bernstein-style uncertainty set, which, however,
does not necessarily include the true transition kernel. We show that an
improved sample complexity of
$\mathcal{O}(SC^{\pi^*}\epsilon^{-2}(1-\gamma)^{-3})$ can be obtained, which
matches with the minimax lower bound for offline reinforcement learning, and
thus is minimax optimal.
- Abstract（参考訳）: オフライン強化学習は、アクティブな探索なしに事前に収集されたデータセットから学ぶことを目的としている。
この問題は、データ可用性や分散シフトの制限など、重大な課題に直面している。
既存のアプローチでは、不確実性に対する悲観的なスタンスを採用し、探索されていない状態-作用対の報酬を、保守的に値関数を推定する。
本稿では,分散ロバスト最適化(DRO)に基づく手法により,これらの課題にも対処できることを示す。
具体的には、遷移核における不確かさを直接モデル化し、統計的に妥当な遷移核の不確実性集合を構成する。
そして、この不確実性セットに対して最悪のパフォーマンスを最適化するポリシーを見つけます。
まず、高い確率で真の遷移カーネルがこの集合に含まれるような計量ベースのHoeffding型不確実性集合を設計する。
サンプル複雑性を$\mathcal{O}(S^2C^{\pi^*}\epsilon^{-2}(1-\gamma)^{-4})$とすると、$\gamma$は割引係数であり、$S$は状態数であり、$C^{\pi^*}$は分布シフトを定量化する単極クリッピング集中係数である。
最適なサンプル複雑性を達成するため、より保守的なベルンシュタイン型不確実性集合も提案するが、必ずしも真の遷移核を含まない。
オフライン強化学習における最小値の最小値と一致する$\mathcal{O}(SC^{\pi^*}\epsilon^{-2}(1-\gamma)^{-3})$の改善されたサンプル複雑性が得られた。
関連論文リスト
- Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳（メタデータ） (2024-02-14T07:52:00Z) - Breaking the Heavy-Tailed Noise Barrier in Stochastic Optimization Problems [56.86067111855056]
構造密度の重み付き雑音によるクリップ最適化問題を考察する。
勾配が有限の順序モーメントを持つとき、$mathcalO(K-(alpha - 1)/alpha)$よりも高速な収束率が得られることを示す。
得られた推定値が無視可能なバイアスと制御可能な分散を持つことを示す。
論文 参考訳（メタデータ） (2023-11-07T17:39:17Z) - Improved Sample Complexity Bounds for Distributionally Robust
Reinforcement Learning [3.222802562733787]
トレーニング環境とテスト環境のパラメータミスマッチに対して頑健な制御ポリシーを学習することの問題点を考察する。
本研究では,4つの異なる発散によって特定される不確実性集合に対して,ロバスト位相値学習(RPVL)アルゴリズムを提案する。
提案アルゴリズムは,既存の結果より一様によいサンプル複雑性を$tildemathcalO(|mathcalSmathcalA| H5)$とする。
論文 参考訳（メタデータ） (2023-03-05T21:47:08Z) - Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation
Constrained Optimization [88.0031283949404]
多くの実世界の問題は複雑な非機能的制約を持ち、多くのデータポイントを使用する。
提案手法は,従来最もよく知られた結果で既存手法よりも優れた性能を示す。
論文 参考訳（メタデータ） (2022-12-19T14:48:54Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Sharper Rates and Flexible Framework for Nonconvex SGD with Client and
Data Sampling [64.31011847952006]
我々は、平均$n$スムーズでおそらくは非カラー関数のほぼ定常点を求める問題を再考する。
我々は$smallsfcolorgreen$を一般化し、事実上あらゆるサンプリングメカニズムで確実に動作するようにします。
我々は、スムーズな非カラー状態における最適境界の最も一般的な、最も正確な解析を提供する。
論文 参考訳（メタデータ） (2022-06-05T21:32:33Z) - Stochastic regularized majorization-minimization with weakly convex and
multi-convex surrogates [0.0]
提案アルゴリズムの最初の最適性ギャップは,非テンソル依存データ設定下での様々な手法の期待損失率で減衰することを示す。
非テンション依存データ設定の下で, 各種手法の収束点を求める。
論文 参考訳（メタデータ） (2022-01-05T15:17:35Z) - Distributed Sparse Regression via Penalization [5.990069843501885]
エージェントのネットワーク上の線形回帰を、(集中ノードを持たない)無向グラフとしてモデル化する。
推定問題は、局所的なLASSO損失関数の和とコンセンサス制約の2次ペナルティの最小化として定式化される。
本稿では, ペナル化問題に適用した近似勾配アルゴリズムが, 集中的な統計的誤差の順序の許容値まで線形に収束することを示す。
論文 参考訳（メタデータ） (2021-11-12T01:51:50Z) - Non-convex Distributionally Robust Optimization: Non-asymptotic Analysis [16.499651513178012]
分散ロバスト最適化(DRO)は、分散シフトに対してロバストなモデルを学ぶために広く使われている手法である。
目的関数はおそらく非滑らかであり,正規化勾配降下を有するにもかかわらず,非漸近収束を保証する。
論文 参考訳（メタデータ） (2021-10-24T14:56:38Z) - Breaking the Sample Size Barrier in Model-Based Reinforcement Learning
with a Generative Model [50.38446482252857]
本稿では、生成モデル(シミュレータ)へのアクセスを想定して、強化学習のサンプル効率について検討する。
最初に$gamma$-discounted infinite-horizon Markov decision process (MDPs) with state space $mathcalS$ and action space $mathcalA$を考える。
対象の精度を考慮すれば,モデルに基づく計画アルゴリズムが最小限のサンプルの複雑さを実現するのに十分であることを示す。
論文 参考訳（メタデータ） (2020-05-26T17:53:18Z) - Stochastic Proximal Gradient Algorithm with Minibatches. Application to
Large Scale Learning Models [2.384873896423002]
非滑らかな成分を持つ汎用合成対象関数に対する勾配アルゴリズムのミニバッチ変種を開発し解析する。
我々は、最小バッチサイズ$N$に対して、$mathcalO(frac1Nepsilon)$$epsilon-$subityが最適解に期待される二次距離で達成されるような、定数および変数のステップサイズ反復ポリシーの複雑さを提供する。
論文 参考訳（メタデータ） (2020-03-30T10:43:56Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。