論文の概要: Gap-Dependent Bounds for Nearly Minimax Optimal Reinforcement Learning with Linear Function Approximation

• arxiv url: http://arxiv.org/abs/2602.20297v1
• Date: Mon, 23 Feb 2026 19:25:46 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-25 17:34:53.500664
• Title: Gap-Dependent Bounds for Nearly Minimax Optimal Reinforcement Learning with Linear Function Approximation
• Title（参考訳）: 線形関数近似を用いた極小最小強化学習のためのギャップ依存境界
• Authors: Haochen Zhang, Zhong Zheng, Lingzhou Xue,
• Abstract要約: ほぼ最小のアルゴリズムLSVI-UCB++に対して、最初のギャップ依存の後悔境界を提供する。 我々の分析では、以前のギャップ依存の結果と比較して、$d$と$H$の両方の依存性が改善されている。
• 参考スコア（独自算出の注目度）: 13.370933509246568
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study gap-dependent performance guarantees for nearly minimax-optimal algorithms in reinforcement learning with linear function approximation. While prior works have established gap-dependent regret bounds in this setting, existing analyses do not apply to algorithms that achieve the nearly minimax-optimal worst-case regret bound $\tilde{O}(d\sqrt{H^3K})$, where $d$ is the feature dimension, $H$ is the horizon length, and $K$ is the number of episodes. We bridge this gap by providing the first gap-dependent regret bound for the nearly minimax-optimal algorithm LSVI-UCB++ (He et al., 2023). Our analysis yields improved dependencies on both $d$ and $H$ compared to previous gap-dependent results. Moreover, leveraging the low policy-switching property of LSVI-UCB++, we introduce a concurrent variant that enables efficient parallel exploration across multiple agents and establish the first gap-dependent sample complexity upper bound for online multi-agent RL with linear function approximation, achieving linear speedup with respect to the number of agents.
• Abstract（参考訳）: 線形関数近似を用いた強化学習において,極小最適化アルゴリズムのギャップ依存性能保証について検討した。 これまでの研究では、この設定においてギャップ依存の後悔境界が確立されているが、既存の分析は、最小極最適最悪の後悔境界である$\tilde{O}(d\sqrt{H^3K})$を達成するアルゴリズムには適用されない。 ほぼ最小のアルゴリズム LSVI-UCB++ (He et al , 2023) に対して、このギャップに依存した最初のリフレッシュバウンドを提供することで、このギャップを埋める。 我々の分析では、以前のギャップ依存の結果と比較して、$d$と$H$の両方の依存性が改善されている。 さらに、LSVI-UCB++の低ポリシ切替特性を活用し、複数のエージェントを効率的に並列探索し、線形関数近似によるオンラインマルチエージェントRLに対する最初のギャップ依存サンプル複雑性上限を確立し、エージェント数に対する線形スピードアップを実現する並列変種を導入する。

関連論文リスト

• Solving the Offline and Online Min-Max Problem of Non-smooth Submodular-Concave Functions: A Zeroth-Order Approach [1.220074067604011]
  我々は、ミニミザーに関して非滑らかで、サブモジュラーであり、最大値に関して凹凸であるような目的関数の問題を考察する。 この問題に適用したゼロ階法の性能について検討する。
  論文  参考訳（メタデータ） (2026-01-29T04:04:27Z)
• Closing the Approximation Gap of Partial AUC Optimization: A Tale of Two Formulations [121.39938773554523]
  ROC曲線の下の領域(AUC)は、クラス不均衡と決定制約の両方を持つ実世界のシナリオにおける重要な評価指標である。 PAUC最適化の近似ギャップを埋めるために,2つの簡単なインスタンス単位のミニマックス修正を提案する。 得られたアルゴリズムは、サンプルサイズと典型的な一方方向と双方向のPAUCに対して$O(-2/3)$の収束率の線形パーイテレーション計算複雑性を享受する。
  論文  参考訳（メタデータ） (2025-12-01T02:52:33Z)
• Span-Agnostic Optimal Sample Complexity and Oracle Inequalities for Average-Reward RL [6.996002801232415]
  生成モデルを用いてマルコフ決定過程(MDP)において,$varepsilon$-optimal Policyを求める際のサンプル複雑性について検討した。 我々は,知識を必要とせず,最適なスパンベース複雑性に適合するアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2025-02-16T19:10:55Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• Refined Sample Complexity for Markov Games with Independent Linear Function Approximation [49.5660193419984]
  マルコフゲーム(MG)はマルチエージェント強化学習(MARL)の重要なモデルである 本稿では、WangらによるAVLPRフレームワークを改良し(2023年)、最適部分ギャップの悲観的推定を設計する。 マルチエージェントの呪いに取り組み、最適な$O(T-1/2)収束率を達成し、同時に$textpoly(A_max)$依存性を避ける最初のアルゴリズムを与える。
  論文  参考訳（メタデータ） (2024-02-11T01:51:15Z)
• Offline Primal-Dual Reinforcement Learning for Linear MDPs [16.782625445546273]
  オフライン強化学習(RL)は、他のポリシによって収集されたトランジションの固定データセットから、ほぼ最適なポリシを学ぶことを目的としている。 本稿では,RLの線形プログラミング定式化に基づく原始双対最適化手法を提案する。
  論文  参考訳（メタデータ） (2023-05-22T11:45:23Z)
• Provably Efficient Reinforcement Learning via Surprise Bound [66.15308700413814]
  本稿では,一般値関数近似を用いた効率の良い強化学習アルゴリズムを提案する。 本アルゴリズムは, 線形設定と疎高次元線形設定の両方に適用した場合に, 合理的な後悔境界を達成できる。
  論文  参考訳（メタデータ） (2023-02-22T20:21: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)

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

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