論文の概要: Hitting-Time Bounds for Asynchronous Q-Learning

• arxiv url: http://arxiv.org/abs/2610.13901v1
• Date: Fri, 09 Oct 2026 17:44:10 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-13 04:06:29.703571
• Title: Hitting-Time Bounds for Asynchronous Q-Learning
• Title（参考訳）: 非同期Q-Learningのためのハッティング時間境界
• Abstract要約: 有限マルコフ決定過程の単一軌道からの標準非同期Q-ラーニングの最後の繰り返しについて検討する。 一定のステップサイズを持つゼロ周期Q-ラーニングが $widetildeO(H4/(_minvarepsilon2)+mathfrak h_star)$ transitions を用いて高い確率を達成することを証明した。 経験的状態-アクションカウントルールは、その後のトレーニング実行のための一定のステップサイズを選択し、モデルパラメータの事前の知識なしに同じレートを達成する。
• 参考スコア（独自算出の注目度）: 11.004709593999296
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the last iterate of standard asynchronous Q-learning from a single trajectory of a finite Markov decision process. The trajectory follows a fixed behavior policy whose state--action chain is irreducible and may be periodic. For discount factor $γ$, write $H=(1-γ)^{-1}$, and let $μ_{\min}$ be the minimum stationary state--action probability and $\mathfrak h_\star$ the largest expected hitting time of the reverse state--action chain. We prove that zero-initialized Q-learning with a constant step size achieves sup-norm error at most $\varepsilon$ with high probability using $\widetilde{O}(H^4/(μ_{\min}\varepsilon^2)+\mathfrak h_\star)$ transitions, for $0<\varepsilon\le1$. The statistical term retains the quartic effective-horizon dependence of standard Q-learning, while initialization cost is additive in $\mathfrak h_\star$. For aperiodic behavior chains, a comparison with mixing time yields a transient term $\widetilde{O}(t_{\mathrm{mix}}/μ_{\min})$. An empirical state--action count rule selects a constant step size for a subsequent training run and attains the same rate without prior knowledge of model parameters, target accuracy, or confidence level. The output is the last training iterate, with both stages included in the sample count. The proof uses two deterministic Bellman envelopes to separate statistical error from fixed-policy initialization error and adapts reverse-time hitting-cost compensation from TD learning to state--action propagation. An exploration lower bound holds for arbitrary predictable step sizes. Together with the existing statistical lower bound and its extension to pilot-selected constant steps, it yields matching mean-square rates up to logarithmic factors on the stated large-sample parameter classes.
• Abstract（参考訳）: 有限マルコフ決定過程の単一軌道からの標準非同期Q-ラーニングの最後の繰り返しについて検討する。 この軌道は、状態-作用連鎖が既約であり周期的である固定的な行動方針に従う。 割引係数 $γ$, write $H=(1-γ)^{-1}$, and let $μ_{\min}$ be the minimum stationary state-action probability and $\mathfrak h_\star$ the largest hit time of the reverse state-action chain。 一定のステップサイズを持つゼロ初期化Q-ラーニングは、0<\varepsilon\le1$に対して$\widetilde{O}(H^4/(μ_{\min}\varepsilon^2)+\mathfrak h_\star)$transitionsを用いて、高い確率でsup-norm誤差を最大$\varepsilon$で達成することを証明する。 統計用語は標準的なQ-ラーニングの質的有効-水平依存を保ち、初期化コストは$\mathfrak h_\star$で加算される。 周期的行動連鎖に対して、混合時間との比較は、過渡項 $\widetilde{O}(t_{\mathrm{mix}}/μ_{\min})$ を得る。 経験的状態-行動カウントルールは、その後のトレーニング実行のための一定のステップサイズを選択し、モデルパラメータ、ターゲット精度、あるいは信頼度に関する事前の知識なしで同じレートを達成する。 出力は最後のトレーニングであり、両方のステージがサンプルカウントに含まれている。 この証明は2つの決定論的ベルマンエンベロープを用いて、統計的誤差と固定政治初期化誤差を分離し、TD学習から状態-作用伝播への逆時間打撃コスト補償を適用する。 探索下界は任意の予測可能なステップサイズに対して保持される。 既存の統計的下界と、パイロット選択された定数ステップへの拡張とともに、提案された大サンプルパラメータークラス上の対数係数に一致する平均二乗率を得る。

関連論文リスト

• Parameter-Free Interval-Dynamic Regret under Heavy-Tailed Noise [55.29259818039367]
  オンライン凸最適化を1ラウンドに1つの偏りのない下位段階と、未知の有限条件の雑音モーメントであるp$th, $1ple2$で検討する。 長さ$n$の固定区間$I$に対して、学習者は最適な全水平静的レートを含む1+log(T/n)$を達成する。
  論文  参考訳（メタデータ） (2026-09-30T21:03:03Z)
• Sharp Statistical Rates for Asynchronous TD Learning with Markovian Data [11.004709593999296]
  最期TDが超ノーム誤差を最大$varepsilon$で高い確率で達成することを証明する。 既知の決定論的報酬を持つ三状態構成は、統計的および混合項に対して一致するミニマックス境界を低くする。
  論文  参考訳（メタデータ） (2026-09-30T03:31:05Z)
• Next-token functional estimation [11.973479596074514]
  実験的な指標を形成する前に,各インデックスの後に長さ$$$のウィンドウを削除する。 我々の推定器は、アウト・ワン・アウトとアドスタント・ベースラインが失敗する多くのシナリオで成功することを示す。
  論文  参考訳（メタデータ） (2026-09-17T00:51:01Z)
• From Approachability Residuals to Anytime-Valid Evidence: The Online Convex Geometry of Testing by Betting [0.1624454100511275]
  ギャンブリングベースのシーケンシャルテストとブラックウェルのアプローチ性は、支持関数による比例還元によってリンクされる。 正確な経路単位は$$dist(bar r_T,S) =frac1Tsum_t=1Tq_t+fracReg_TTである。
  論文  参考訳（メタデータ） (2026-08-10T11:23:30Z)
• Robust Average-Reward Markov Decision Processes: Minimax-Optimal Learning via Plug-in Reductions [51.50375419691955]
  分布的に堅牢なマルコフ決定プロセスは、モデルの不確実性の下でのシーケンシャルな意思決定のための原則化されたフレームワークを提供する。 我々は,平均回帰基準の下で,$varepsilon$-Optimal robust policyを学習するのに必要なサンプル数と十分なサンプル数について検討した。
  論文  参考訳（メタデータ） (2026-08-06T19:49:48Z)
• Asymptotic-Preserving A Posteriori Analysis of Diffusion and Flow-Matching Samplers [0.6768558752130311]
  拡散及びフローマッチングサンプリングは、学習した確率フローODEを、大きなノイズスケールから小さな終端フロア($_min$)まで統合し、スコアが硬く、フローが境界層を発達させる。 特異摂動パラメータとして$_min$を扱い、どの固定ステップサンプリングが解けるかを決定する。
  論文  参考訳（メタデータ） (2026-07-05T04:48:33Z)
• Statistical Inference of Constrained Stochastic Optimization via Sketched Sequential Quadratic Programming [53.63469275932989]
  制約付き非線形最適化問題のオンライン統計的推測を考察する。 これらの問題を解決するために、逐次二次計画法(StoSQP)を適用する。
  論文  参考訳（メタデータ） (2022-05-27T00:34:03Z)
• Tightening the Dependence on Horizon in the Sample Complexity of Q-Learning [59.71676469100807]
  この研究は、同期Q-ラーニングのサンプルの複雑さを、任意の$0varepsilon 1$に対して$frac|mathcalS| (1-gamma)4varepsilon2$の順序に絞る。 計算やストレージを余分に必要とせずに、高速なq-learningにマッチするvanilla q-learningの有効性を明らかにした。
  論文  参考訳（メタデータ） (2021-02-12T14:22:05Z)
• Finite-Time Analysis for Double Q-learning [50.50058000948908]
  二重Q-ラーニングのための非漸近的有限時間解析を初めて提供する。 同期と非同期の二重Q-ラーニングの両方が,グローバル最適化の$epsilon$-accurate近辺に収束することが保証されていることを示す。
  論文  参考訳（メタデータ） (2020-09-29T18:48:21Z)
• 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)

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

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