論文の概要: From Generative to Episodic: Sample-Efficient Replicable Reinforcement Learning

• arxiv url: http://arxiv.org/abs/2507.11926v1
• Date: Wed, 16 Jul 2025 05:43:46 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-07-17 19:00:11.239296
• Title: From Generative to Episodic: Sample-Efficient Replicable Reinforcement Learning
• Title（参考訳）: ジェネレーティブからエピソディクスへ:有効に再現可能な強化学習
• Authors: Max Hopkins, Sihan Liu, Christopher Ye, Yuichi Yoshida,
• Abstract要約: 固定されたi.d.ソースからデータを取得するバッチ設定では、データ効率のよいレプリカブルアルゴリズムの設計が多かれ少なかれ理解されている。 探索は複製可能な学習にとって重要な障壁ではないことを、私たちは示しています! 我々の主な成果は、$tildeO(S2A)$サンプル上の複製可能なRLアルゴリズムであり、生成的設定とエピソード設定のギャップを埋めるものである。
• 参考スコア（独自算出の注目度）: 18.59097820898079
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The epidemic failure of replicability across empirical science and machine learning has recently motivated the formal study of replicable learning algorithms [Impagliazzo et al. (2022)]. In batch settings where data comes from a fixed i.i.d. source (e.g., hypothesis testing, supervised learning), the design of data-efficient replicable algorithms is now more or less understood. In contrast, there remain significant gaps in our knowledge for control settings like reinforcement learning where an agent must interact directly with a shifting environment. Karbasi et. al show that with access to a generative model of an environment with $S$ states and $A$ actions (the RL 'batch setting'), replicably learning a near-optimal policy costs only $\tilde{O}(S^2A^2)$ samples. On the other hand, the best upper bound without a generative model jumps to $\tilde{O}(S^7 A^7)$ [Eaton et al. (2024)] due to the substantial difficulty of environment exploration. This gap raises a key question in the broader theory of replicability: Is replicable exploration inherently more expensive than batch learning? Is sample-efficient replicable RL even possible? In this work, we (nearly) resolve this problem (for low-horizon tabular MDPs): exploration is not a significant barrier to replicable learning! Our main result is a replicable RL algorithm on $\tilde{O}(S^2A)$ samples, bridging the gap between the generative and episodic settings. We complement this with a matching $\tilde{\Omega}(S^2A)$ lower bound in the generative setting (under the common parallel sampling assumption) and an unconditional lower bound in the episodic setting of $\tilde{\Omega}(S^2)$ showcasing the near-optimality of our algorithm with respect to the state space $S$.
• Abstract（参考訳）: 実証科学と機械学習による複製能力の崩壊は、最近、レプリカブル学習アルゴリズム(Impagliazzo et al (2022))の正式な研究を動機付けている。 固定されたi.d.ソース(仮説テスト、教師あり学習など)からデータがやってくるバッチ設定では、データ効率のよい複製可能なアルゴリズムの設計が多かれ少なかれ理解されるようになった。 対照的に、エージェントが移動環境と直接対話しなければならない強化学習のような制御設定に関する知識には、大きなギャップが残っている。 Karbasiなど。 alは、$S$状態と$A$アクション(RL 'バッチ設定')を持つ環境の生成モデルにアクセスすると、ほぼ最適ポリシーを複製して学習するのは、$\tilde{O}(S^2A^2)$サンプルのみであることを示している。 一方, 生成モデルを持たない最高の上界は, 環境探査の困難さから$\tilde{O}(S^7 A^7)$ [Eaton et al (2024)] にジャンプする。 レプリカブルな探索は本質的に、バッチ学習よりも高価か? サンプル効率のよいレプリカRLは可能か? この作業では、(低水平の表型MDPに対して)この問題を(ほぼ)解決します。 我々の主な成果は、$\tilde{O}(S^2A)$サンプル上の複製可能なRLアルゴリズムであり、生成的設定とエピソード設定のギャップを埋めるものである。 これに一致する$\tilde{\Omega}(S^2A)$ lower bound in the generative set (under the common parallel sample assumption) and a unconditional lower bound in the episodic set of $\tilde{\Omega}(S^2)$

関連論文リスト

• Inverse Entropic Optimal Transport Solves Semi-supervised Learning via Data Likelihood Maximization [65.8915778873691]
  条件分布は機械学習の中心的な問題です ペアデータとペアデータの両方を統合する新しいパラダイムを提案する。 提案手法は任意の誤差で理論上真の条件分布を復元可能であることを示す。
  論文  参考訳（メタデータ） (2024-10-03T16:12:59Z)
• Settling the Sample Complexity of Online Reinforcement Learning [92.02082223856479]
  バーンインコストを発生させることなく、最小限の最適後悔を実現する方法を示す。 最適値/コストや一定の分散といった問題依存量の影響を明らかにするために、我々の理論を拡張します。
  論文  参考訳（メタデータ） (2023-07-25T15:42:11Z)
• Fast Rates for Maximum Entropy Exploration [52.946307632704645]
  エージェントが未知の環境下で活動し、報酬が得られない場合、強化学習(RL)における探索の課題に対処する。 本研究では,最大エントロピー探索問題を2つの異なるタイプで検討する。 訪問エントロピーには、$widetildemathcalO(H3S2A/varepsilon2)$ sample complexity を持つゲーム理論アルゴリズムを提案する。 軌道エントロピーに対しては,次数$widetildemathcalO(mathrmpoly(S,)の複雑さのサンプルを持つ単純なアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-03-14T16:51:14Z)
• Robust Empirical Risk Minimization with Tolerance [24.434720137937756]
  我々は、(ロバストな)$textitempirical risk minimization$(RERM)の基本パラダイムについて研究する。 自然寛容なRERMは、$mathbbRd$を超える$gamma$-tolerantな学習VCクラスに十分であることを示す。
  論文  参考訳（メタデータ） (2022-10-02T21:26:15Z)
• Minimax-Optimal Multi-Agent RL in Zero-Sum Markov Games With a Generative Model [50.38446482252857]
  2人プレイのゼロサムマルコフゲームは多エージェント強化学習においておそらく最も基本的な設定である。 我々は,$$ widetildeObiggを用いて,$varepsilon$-approximate Markov NEポリシーを学習する学習アルゴリズムを開発した。 我々は、分散型量の役割を明確にするFTRLに対する洗練された後悔境界を導出する。
  論文  参考訳（メタデータ） (2022-08-22T17:24:55Z)
• A Few Expert Queries Suffices for Sample-Efficient RL with Resets and Linear Value Approximation [16.29514743112387]
  最適値関数のみを線形化可能な設定において、サンプル効率のよい強化学習(RL)について検討する。 専門的なクエリと探索をブレンドするための統計的・計算学的に効率的なアルゴリズム(Delphi)を提案する。 Delphi には $tildemathcalO(d)$ エキスパートクエリと $texttpoly(d,|mathcalA|,1/varepsilon)$ 探索サンプルの量が必要です。
  論文  参考訳（メタデータ） (2022-07-18T01:39:13Z)
• Overcoming the Long Horizon Barrier for Sample-Efficient Reinforcement Learning with Latent Low-Rank Structure [9.759209713196718]
  我々は、対応する最適$Q*$関数が低ランクであるMDPのクラスを考える。 より強い低階構造仮定の下では、生成モデル(LR-MCPI)と低階経験値イテレーション(LR-EVI)が、ランクに対して$tildeOleft((|S|+|A|)mathrmpoly(d,H)/epsilon2right)$の所望のサンプル複雑性を実現することが示されている。
  論文  参考訳（メタデータ） (2022-06-07T20:39:51Z)
• Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learning [52.76230802067506]
  漸進的強化学習における後悔を最小限に抑えるために,新しいモデルフリーアルゴリズムを提案する。 提案アルゴリズムは、2つのQ-ラーニングシーケンスの助けを借りて、初期設定された参照更新ルールを用いる。 初期の分散還元法の設計原理は、他のRL設定とは独立した関心を持つかもしれない。
  論文  参考訳（メタデータ） (2021-10-09T21:13:48Z)
• 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)
• A Provably Efficient Sample Collection Strategy for Reinforcement Learning [123.69175280309226]
  オンライン強化学習(RL)における課題の1つは、エージェントがその振る舞いを最適化するために、環境の探索とサンプルの活用をトレードオフする必要があることである。 1) 生成モデル(環境のスパースシミュレータなど)にアクセス可能な状態のサンプル数を規定する「対象別」アルゴリズム,2) 所定のサンプルをできるだけ早く生成する「対象別」サンプル収集。
  論文  参考訳（メタデータ） (2020-07-13T15:17:35Z)

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

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