論文の概要: Achieving the Asymptotically Optimal Sample Complexity of Offline Reinforcement Learning: A DRO-Based Approach

• arxiv url: http://arxiv.org/abs/2305.13289v4
• Date: Sat, 28 Sep 2024 22:56:24 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-10-01 21:59:28.029884
• Title: Achieving the Asymptotically Optimal Sample Complexity of Offline Reinforcement Learning: A DRO-Based Approach
• Title（参考訳）: オフライン強化学習における漸近的最適サンプル複雑さの達成:DROに基づくアプローチ
• Authors: Yue Wang, Jinjun Xiong, Shaofeng Zou,
• Abstract要約: オフライン強化学習は、アクティブな探索なしに、事前に収集されたデータセットから学習することを目的としている。 既存のアプローチでは、不確実性に対する悲観的なスタンスを採用し、探索されていない状態-作用対の報酬を、保守的に値関数を推定する。 分散ロバスト最適化(DRO)に基づくアプローチはこれらの課題にも対処でき、漸近的に最小限の最適化であることを示す。
• 参考スコア（独自算出の注目度）: 36.88301225561535
• License:
• 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 {asymptotically minimax optimal}. Specifically, we directly model the uncertainty in the transition kernel and construct an uncertainty set of statistically plausible transition kernels. We then show that the policy that optimizes the worst-case performance over this uncertainty set has a near-optimal performance in the underlying problem. We first design a metric-based distribution-based 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 value-function-based 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 asymptotically matches with the minimax lower bound for offline reinforcement learning, and thus is asymptotically minimax optimal.
• Abstract（参考訳）: オフライン強化学習は、積極的に探索することなく、事前に収集したデータセットから学習することを目的としている。 この問題は、データ可用性や分散シフトの制限など、重大な課題に直面している。 既存のアプローチでは、不確実性に対する悲観的なスタンスを採用し、探索されていない状態-作用対の報酬を、保守的に値関数を推定する。 本稿では,分散ロバスト最適化(DRO)に基づくアプローチがこれらの課題に対処できることを示す。 具体的には、遷移カーネルにおける不確実性を直接モデル化し、統計的に妥当な遷移カーネルの不確実性セットを構築する。 そして、この不確実性集合に対して最悪の性能を最適化するポリシーは、基礎となる問題においてほぼ最適であることを示す。 まず、この集合に真の遷移核が存在する確率の高い分布に基づく不確実性集合を設計する。 サンプル複雑性を$\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)

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

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。