論文の概要: Achieving $\varepsilon^{-2}$ Dependence for Average-Reward Q-Learning with a New Contraction Principle

• arxiv url: http://arxiv.org/abs/2601.21301v1
• Date: Thu, 29 Jan 2026 05:54:31 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-01-30 16:22:49.606372
• Title: Achieving $\varepsilon^{-2}$ Dependence for Average-Reward Q-Learning with a New Contraction Principle
• Title（参考訳）: $\varepsilon^{-2}$ Dependence for Average-Reward Q-Learning with a new Contraction Principle
• Authors: Zijun Chen, Zaiwei Chen, Nian Si, Shengbo Wang,
• Abstract要約: 平均回帰マルコフ決定過程に対する同期および非同期Q-ラーニングの収束率を示す。 分析の核となるのは、インスタンス依存半ノルムの構成であり、マルコフ決定過程の遅延変換の後、ベルマン作用素がこの半ノルムの下で一段階の縮約となることを示す。
• 参考スコア（独自算出の注目度）: 13.418969441591882
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We present the convergence rates of synchronous and asynchronous Q-learning for average-reward Markov decision processes, where the absence of contraction poses a fundamental challenge. Existing non-asymptotic results overcome this challenge by either imposing strong assumptions to enforce seminorm contraction or relying on discounted or episodic Markov decision processes as successive approximations, which either require unknown parameters or result in suboptimal sample complexity. In this work, under a reachability assumption, we establish optimal $\widetilde{O}(\varepsilon^{-2})$ sample complexity guarantees (up to logarithmic factors) for a simple variant of synchronous and asynchronous Q-learning that samples from the lazified dynamics, where the system remains in the current state with some fixed probability. At the core of our analysis is the construction of an instance-dependent seminorm and showing that, after a lazy transformation of the Markov decision process, the Bellman operator becomes one-step contractive under this seminorm.
• Abstract（参考訳）: 本稿では, 平均回帰マルコフ決定過程における同期および非同期Q-ラーニングの収束率について述べる。 既存の非漸近的な結果は、半ノルムの収縮を強制する強い仮定を課すか、あるいは非最適サンプルの複雑さをもたらす未知のパラメータを必要とする連続した近似として、半ノルム決定過程やエピソディックなマルコフ決定過程に依存するかによって、この課題を克服する。 この研究は、到達可能性の仮定の下で、最適$\widetilde{O}(\varepsilon^{-2})$サンプル複雑性を保証する(対数的因子まで)。 分析の核となるのは、インスタンス依存半ノルムの構成であり、マルコフ決定過程の遅延変換の後、ベルマン作用素がこの半ノルムの下で一段階の縮約となることを示す。

関連論文リスト

• Average-reward reinforcement learning in semi-Markov decision processes via relative value iteration [7.465862205471524]
  RVI Q-learningアルゴリズムは、平均回帰最適性方程式に対する解のコンパクトで連結な部分集合にほぼ確実に収束することを示す。 SAフレームワークをフル活用するために、最適な報酬率を推定するための新しい単調性条件を導入する。
  論文  参考訳（メタデータ） (2025-12-05T23:49:07Z)
• Finite-Sample Analysis of Policy Evaluation for Robust Average Reward Reinforcement Learning [50.81240969750462]
  我々は、ロバスト平均マルコフ決定過程(PMD)における政策評価の第1次有限サンプル解析を提案する。 頑健なベルマン作用素は、慎重に構築された半ノルムの下で収縮し、制御バイアスを持つフレームワークを開発することを示す。 本手法は,ロバストな政策評価とロバストな平均報酬推定のために,$tildemathcalO(epsilon-2)$のオーダー最適サンプル複雑性を実現する。
  論文  参考訳（メタデータ） (2025-02-24T03:55:09Z)
• Sample Complexity of Linear Quadratic Regulator Without Initial Stability [7.245261469258501]
  ReINFORCEにインスパイアされ、未知のダイナミクスを持つ線形二次レギュレータ(LQR)問題に対して、新しいリリーディングホライゾンアルゴリズムを導入する。 従来の手法とは異なり、本アルゴリズムはサンプルの複雑さの順序を同じに保ちながら、2点勾配推定に依存することを回避している。
  論文  参考訳（メタデータ） (2025-02-20T02:44:25Z)
• Sample Complexity of Variance-reduced Distributionally Robust Q-learning [17.96094201655567]
  本稿では,分散性に頑健なQ-ラーニングアルゴリズムと,分散性に欠けるロバストなポリシーを効果的に学習できる分散性のあるQ-ラーニングアルゴリズムを2つ提案する。 一連の数値実験により、分布シフトの処理におけるアルゴリズムの理論的発見と効率性が確認された。
  論文  参考訳（メタデータ） (2023-05-28T19:40:46Z)
• PAPAL: A Provable PArticle-based Primal-Dual ALgorithm for Mixed Nash Equilibrium [58.26573117273626]
  2プレイヤゼロサム連続ゲームにおける非AL平衡非漸近目的関数について考察する。 連続分布戦略のための粒子ベースアルゴリズムに関する新しい知見を述べる。
  論文  参考訳（メタデータ） (2023-03-02T05:08:15Z)
• Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity [49.66890309455787]
  本稿では,SGDA と SCO の最終的な収束保証として,期待されるコヒーレンシティ条件を導入し,その利点を説明する。 定常的なステップサイズを用いた場合、両手法の線形収束性を解の近傍に証明する。 我々の収束保証は任意のサンプリングパラダイムの下で保たれ、ミニバッチの複雑さに関する洞察を与える。
  論文  参考訳（メタデータ） (2021-06-30T18:32:46Z)
• On the Convergence of Stochastic Extragradient for Bilinear Games with Restarted Iteration Averaging [96.13485146617322]
  本稿では, ステップサイズが一定であるSEG法の解析を行い, 良好な収束をもたらす手法のバリエーションを示す。 平均化で拡張した場合、SEGはナッシュ平衡に確実に収束し、スケジュールされた再起動手順を組み込むことで、その速度が確実に加速されることを証明した。
  論文  参考訳（メタデータ） (2021-06-30T17:51:36Z)
• Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reduction [63.41789556777387]
  非同期Q-ラーニングはマルコフ決定過程(MDP)の最適行動値関数(またはQ-関数)を学習することを目的としている。 Q-関数の入出力$varepsilon$-正確な推定に必要なサンプルの数は、少なくとも$frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$の順である。
  論文  参考訳（メタデータ） (2020-06-04T17:51:00Z)

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

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