論文の概要: Offline Reinforcement Learning via Linear-Programming with Error-Bound Induced Constraints

• arxiv url: http://arxiv.org/abs/2212.13861v3
• Date: Mon, 09 Dec 2024 20:39:58 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-12-11 14:34:27.332504
• Title: Offline Reinforcement Learning via Linear-Programming with Error-Bound Induced Constraints
• Title（参考訳）: 誤差境界制約付き線形プログラミングによるオフライン強化学習
• Authors: Asuman Ozdaglar, Sarath Pattathil, Jiawei Zhang, Kaiqing Zhang,
• Abstract要約: オフライン強化学習(RL)は、事前に収集されたデータセットを使用して、マルコフ決定プロセス(MDP)の最適ポリシーを見つけることを目的としている。 本研究では,オフラインRLにおけるマルコフ決定過程の線形プログラミング (LP) の再検討を行う。
• 参考スコア（独自算出の注目度）: 26.008426384903764
• License:
• Abstract: Offline reinforcement learning (RL) aims to find an optimal policy for Markov decision processes (MDPs) using a pre-collected dataset. In this work, we revisit the linear programming (LP) reformulation of Markov decision processes for offline RL, with the goal of developing algorithms with optimal $O(1/\sqrt{n})$ sample complexity, where $n$ is the sample size, under partial data coverage and general function approximation, and with favorable computational tractability. To this end, we derive new \emph{error bounds} for both the dual and primal-dual formulations of the LP, and incorporate them properly as \emph{constraints} in the LP reformulation. We then show that under a completeness-type assumption, $O(1/\sqrt{n})$ sample complexity can be achieved under standard single-policy coverage assumption, when one properly \emph{relaxes} the occupancy validity constraint in the LP. This framework can readily handle both infinite-horizon discounted and average-reward MDPs, in both general function approximation and tabular cases. The instantiation to the tabular case achieves either state-of-the-art or the first sample complexities of offline RL in these settings. To further remove any completeness-type assumption, we then introduce a proper \emph{lower-bound constraint} in the LP, and a variant of the standard single-policy coverage assumption. Such an algorithm leads to a $O(1/\sqrt{n})$ sample complexity with dependence on the \emph{value-function gap}, with only realizability assumptions. Our properly constrained LP framework advances the existing results in several aspects, in relaxing certain assumptions and achieving the optimal $O(1/\sqrt{n})$ sample complexity, with simple analyses. We hope our results bring new insights into the use of LP formulations and the equivalent primal-dual minimax optimization for offline RL, through the error-bound induced constraints.
• Abstract（参考訳）: オフライン強化学習(RL)は、事前に収集したデータセットを使用してマルコフ決定プロセス(MDP)の最適ポリシーを見つけることを目的としている。 本稿では,オフラインRLにおけるマルコフ決定過程の線形プログラミング (LP) の再構成を,最適な$O(1/\sqrt{n})$サンプル複雑性を持つアルゴリズムを開発することを目的として再検討する。 この目的のために、LPの双対および原始双対の定式化のための新しい 'emph{error bounds} を導出し、LP再構成において 'emph{constraints} として適切に組み込む。 次に、完全性型仮定の下で、$O(1/\sqrt{n})$サンプル複雑性は、LPの占有率の制約を適切に満たすとき、標準的な単一政治カバレッジの仮定の下で達成できることを示す。 このフレームワークは、一般関数近似と表型ケースの両方において、無限水平割引と平均逆 MDP の両方を容易に扱うことができる。 表のケースへのインスタンス化は、これらの設定におけるオフラインRLの最先端または最初のサンプル複雑度を達成する。 完全性型仮定をさらに除去するために、LP に固有な \emph{lower-bound constraint} を導入する。 そのようなアルゴリズムは、実現可能性の仮定だけで、 \emph{value-function gap} に依存した$O(1/\sqrt{n})$サンプル複雑性をもたらす。 我々の適切に制約されたLPフレームワークは、いくつかの面で既存の結果を前進させ、いくつかの仮定を緩和し、単純な解析で最適な$O(1/\sqrt{n})$サンプル複雑性を達成する。 我々は,LPの定式化とオフラインRLの最小二乗最小最適化に関する新たな知見を,エラーバウンド誘導制約を通じて得られることを期待する。

関連論文リスト

• Span-Agnostic Optimal Sample Complexity and Oracle Inequalities for Average-Reward RL [6.996002801232415]
  生成モデルを用いてマルコフ決定過程(MDP)において,$varepsilon$-optimal Policyを求める際のサンプル複雑性について検討した。 我々は,知識を必要とせず,最適なスパンベース複雑性に適合するアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2025-02-16T19:10:55Z)
• Nearly Optimal Sample Complexity of Offline KL-Regularized Contextual Bandits under Single-Policy Concentrability [49.96531901205305]
  我々は,オフラインの文脈的包帯に対する単一政治中心性の下でのサンプル複雑性を$tildeO(epsilon-1)$とするemphfirstアルゴリズムを提案する。 我々の証明は、KL正則化の強い凸性と、真の報酬と悲観的推定子のギャップの条件的非負性を利用する。 我々は,このアルゴリズムを文脈的デュエル帯域に拡張し,ほぼ最適なサンプル複雑性を実現する。
  論文  参考訳（メタデータ） (2025-02-09T22:14:45Z)
• A Primal-Dual Algorithm for Offline Constrained Reinforcement Learning with Linear MDPs [18.449996575976993]
  無限水平割引設定における線形 MDP を用いたオフライン RL の原始双対アルゴリズムを提案する。 本アルゴリズムは, 部分的データカバレッジを仮定した$O(epsilon-2)$のサンプル複雑性を実現するアルゴリズムとして, この設定において, 計算効率のよい最初のアルゴリズムである。 我々はアルゴリズムをオフラインの制約付きRL設定で動作させ、追加の報酬信号に制約を課すように拡張する。
  論文  参考訳（メタデータ） (2024-02-07T00:33:11Z)
• Offline Primal-Dual Reinforcement Learning for Linear MDPs [16.782625445546273]
  オフライン強化学習(RL)は、他のポリシによって収集されたトランジションの固定データセットから、ほぼ最適なポリシを学ぶことを目的としている。 本稿では,RLの線形プログラミング定式化に基づく原始双対最適化手法を提案する。
  論文  参考訳（メタデータ） (2023-05-22T11:45:23Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• Near-Optimal Sample Complexity Bounds for Constrained MDPs [25.509556551558834]
  減算CMDPにおける準最適政策を学習するために,サンプルの複雑さを極小値と下位値で表す。 CMDPの学習は,少ない制約違反を許す場合と同等に容易であるが,制約違反を要求しない場合には本質的に困難であることを示す。
  論文  参考訳（メタデータ） (2022-06-13T15:58:14Z)
• 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)
• 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)
• 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)

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

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