論文の概要: Regret and Sample Complexity of Online Q-Learning via Concentration of Stochastic Approximation with Time-Inhomogeneous Markov Chains

• arxiv url: http://arxiv.org/abs/2602.16274v1
• Date: Wed, 18 Feb 2026 08:47:07 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-19 15:58:30.552658
• Title: Regret and Sample Complexity of Online Q-Learning via Concentration of Stochastic Approximation with Time-Inhomogeneous Markov Chains
• Title（参考訳）: 時間不均質マルコフ鎖を用いた確率近似の集中によるオンラインQ-Learningの回帰とサンプル複雑度
• Authors: Rahul Singh, Siddharth Chandak, Eric Moulines, Vivek S. Borkar, Nicholas Bambos,
• Abstract要約: 無限水平割引マルコフ決定過程における古典的オンラインQ-ラーニングに対する最初の高い確率的後悔を示す。 十分な大きなギャップでは、後悔はサブリニアであり、小さなギャップでは劣化し、線形成長に近づく。
• 参考スコア（独自算出の注目度）: 23.565936864449636
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We present the first high-probability regret bound for classical online Q-learning in infinite-horizon discounted Markov decision processes, without relying on optimism or bonus terms. We first analyze Boltzmann Q-learning with decaying temperature and show that its regret depends critically on the suboptimality gap of the MDP: for sufficiently large gaps, the regret is sublinear, while for small gaps it deteriorates and can approach linear growth. To address this limitation, we study a Smoothed $ε_n$-Greedy exploration scheme that combines $ε_n$-greedy and Boltzmann exploration, for which we prove a gap-robust regret bound of near-$\tilde{O}(N^{9/10})$. To analyze these algorithms, we develop a high-probability concentration bound for contractive Markovian stochastic approximation with iterate- and time-dependent transition dynamics. This bound may be of independent interest as the contraction factor in our bound is governed by the mixing time and is allowed to converge to one asymptotically.
• Abstract（参考訳）: 無限水平割引マルコフ決定過程において,古典的オンラインQ-ラーニングにおいて,楽観的・ボーナス的条件に頼らずに,最初の高い確率的後悔を示す。 まず,Boltzmann Q-learningを劣化温度で解析し,その後悔はMDPの最適限界に大きく依存することを示した。 この制限に対処するために、Smoothed $ε_n$-Greedy 探索スキームと Boltzmann 探索を組み合わせた Smoothed $ε_n$-Greedy 探索スキームについて検討する。 これらのアルゴリズムを解析するために,契約型マルコフ確率近似とイテレートおよび時間依存性の遷移力学との高確率集中法を開発した。 この境界は、我々の境界の収縮係数が混合時間によって支配され、漸近的に1つに収束することが許されるので、独立した関心を持つかもしれない。

関連論文リスト

• Achieving $\varepsilon^{-2}$ Dependence for Average-Reward Q-Learning with a New Contraction Principle [13.418969441591882]
  平均回帰マルコフ決定過程に対する同期および非同期Q-ラーニングの収束率を示す。 分析の核となるのは、インスタンス依存半ノルムの構成であり、マルコフ決定過程の遅延変換の後、ベルマン作用素がこの半ノルムの下で一段階の縮約となることを示す。
  論文  参考訳（メタデータ） (2026-01-29T05:54:31Z)
• From stability of Langevin diffusion to convergence of proximal MCMC for non-log-concave sampling [21.958353508957988]
  我々は、Untime Langevin (ULA) を用いた非後方からの離散分布のサンプリング問題を考える。 我々は ULA の頑健さを、ポテンシャルが無限大の凸であるという仮定に証明する。
  論文  参考訳（メタデータ） (2025-05-20T10:29:57Z)
• Stochastic Approximation with Delayed Updates: Finite-Time Rates under Markovian Sampling [73.5602474095954]
  マルコフサンプリングの遅延更新による近似スキームの非漸近的性能について検討した。 我々の理論的な発見は、幅広いアルゴリズムの遅延の有限時間効果に光を当てた。
  論文  参考訳（メタデータ） (2024-02-19T03:08:02Z)
• Differentiable Annealed Importance Sampling and the Perils of Gradient Noise [68.44523807580438]
  Annealed importance sample (AIS) と関連するアルゴリズムは、限界推定のための非常に効果的なツールである。 差別性は、目的として限界確率を最適化する可能性を認めるため、望ましい性質である。 我々はメトロポリス・ハスティングスのステップを放棄して微分可能アルゴリズムを提案し、ミニバッチ計算をさらに解き放つ。
  論文  参考訳（メタデータ） (2021-07-21T17:10:14Z)
• High-probability Bounds for Non-Convex Stochastic Optimization with Heavy Tails [55.561406656549686]
  我々は、勾配推定が末尾を持つ可能性のある一階アルゴリズムを用いたヒルベルト非最適化を考える。 本研究では, 勾配, 運動量, 正規化勾配勾配の収束を高確率臨界点に収束させることと, 円滑な損失に対する最もよく知られた繰り返しを示す。
  論文  参考訳（メタデータ） (2021-06-28T00:17:01Z)
• Upper Confidence Primal-Dual Reinforcement Learning for CMDP with Adversarial Loss [145.54544979467872]
  マルコフ決定過程(CMDP)に対するオンライン学習の検討 本稿では,遷移モデルから標本化した軌跡のみを必要とする,新しいEmphupper confidence primal-dualアルゴリズムを提案する。 我々の分析では、ラグランジュ乗算過程の新たな高確率ドリフト解析を、高信頼強化学習の記念後悔解析に組み入れている。
  論文  参考訳（メタデータ） (2020-03-02T05:02:23Z)

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

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