論文の概要: Gaussian Approximation for Asynchronous Q-learning
- arxiv url: http://arxiv.org/abs/2604.07323v1
- Date: Wed, 08 Apr 2026 17:37:15 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-04-09 17:30:51.660752
- Title: Gaussian Approximation for Asynchronous Q-learning
- Title（参考訳）: 非同期Q-ラーニングのためのガウス近似
- Authors: Artemy Rubtsov, Sergey Samsonov, Vladimir Ulyanov, Alexey Naumov,
- Abstract要約: マルティンゲール差分和に対する高次元中心極限定理を証明した。
アルゴリズムの最後の繰り返しに対する高次モーメントのバウンダリを提示する。
- 参考スコア（独自算出の注目度）: 11.260593100797381
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In this paper, we derive rates of convergence in the high-dimensional central limit theorem for Polyak-Ruppert averaged iterates generated by the asynchronous Q-learning algorithm with a polynomial stepsize $k^{-ω},\, ω\in (1/2, 1]$. Assuming that the sequence of state-action-next-state triples $(s_k, a_k, s_{k+1})_{k \geq 0}$ forms a uniformly geometrically ergodic Markov chain, we establish a rate of order up to $n^{-1/6} \log^{4} (nS A)$ over the class of hyper-rectangles, where $n$ is the number of samples used by the algorithm and $S$ and $A$ denote the numbers of states and actions, respectively. To obtain this result, we prove a high-dimensional central limit theorem for sums of martingale differences, which may be of independent interest. Finally, we present bounds for high-order moments for the algorithm's last iterate.
- Abstract（参考訳）: 本稿では,非同期Q-ラーニングアルゴリズムが生成する高次元中心極限定理における収束率を,多項式次数 $k^{-ω},\, ω\in (1/2, 1]$ で導出する。
状態-作用-next-state三重項の列 $(s_k, a_k, s_{k+1})_{k \geq 0}$ が一様幾何学的にエルゴード的マルコフ連鎖を形成すると仮定すると、超矩形クラス上の位数$n^{-1/6} \log^{4} (nS A)$ が成立する。
この結果を得るため、マルティンゲール差分和に対する高次元中心極限定理を証明し、これは独立な興味を持つかもしれない。
最後に,アルゴリズムの最後の繰り返しに対する高次モーメントのバウンダリを提示する。
関連論文リスト
- Hardness of High-Dimensional Linear Classification [58.29089693778071]
我々は、最大半空間離散性問題に対する次元下界の新たな指数関数を確立する。
どちらも計算幾何学と機械学習の基本的問題であり、その正確で近似的な形式である。
論文 参考訳（メタデータ） (2026-03-19T15:53:41Z) - The Picard-Lagrange Framework for Higher-Order Langevin Monte Carlo [15.440889897519483]
一般の$K$th-order Langevinダイナミックスに基づく新しいサンプリングアルゴリズムを導入し,2次法および3次法を超えて拡張する。
滑らかで強い対数凹凸密度を持つ対象に対して、ワッサーシュタイン距離における次元依存収束を証明する。
これはそのようなクエリの複雑さを達成する最初のサンプリングアルゴリズムである。
論文 参考訳（メタデータ） (2025-10-21T03:04:58Z) - A Normal Map-Based Proximal Stochastic Gradient Method: Convergence and Identification Properties [7.281869462071603]
近位勾配法 (PSGD) は複合型問題に対する最先端手法の1つである。
本稿では,ロビンソン写像に基づくPSGDの簡易な変種について述べる。
論文 参考訳（メタデータ） (2023-05-10T01:12:11Z) - Randomized Block-Coordinate Optimistic Gradient Algorithms for Root-Finding Problems [11.15373699918747]
大規模設定における非線形方程式の解を近似する2つの新しいアルゴリズムを開発した。
本稿では,機械学習,統計的学習,ネットワーク最適化などにおける顕著な応用を網羅した大規模有限サム包含のクラスに適用する。
論文 参考訳（メタデータ） (2023-01-08T21:46:27Z) - Average-Case Complexity of Tensor Decomposition for Low-Degree
Polynomials [93.59919600451487]
多くの統計的推論タスクにおいて「統計計算ギャップ」が発生する。
1つの成分が他の成分よりもわずかに大きいランダムオーダー3分解モデルを考える。
テンソルエントリは$ll n3/2$のとき最大成分を正確に推定できるが、$rgg n3/2$のとき失敗する。
論文 参考訳（メタデータ） (2022-11-10T00:40:37Z) - Finite-time High-probability Bounds for Polyak-Ruppert Averaged Iterates
of Linear Stochastic Approximation [22.51165277694864]
本稿では,線形近似 (LSA) アルゴリズムの有限時間解析を行う。
LSAは$d$次元線形系の近似解を計算するために用いられる。
論文 参考訳（メタデータ） (2022-07-10T14:36:04Z) - Statistical Inference of Constrained Stochastic Optimization via Sketched Sequential Quadratic Programming [53.63469275932989]
制約付き非線形最適化問題のオンライン統計的推測を考察する。
これらの問題を解決するために、逐次二次計画法(StoSQP)を適用する。
論文 参考訳（メタデータ） (2022-05-27T00:34:03Z) - Optimal and instance-dependent guarantees for Markovian linear stochastic approximation [47.912511426974376]
標準スキームの最後の繰り返しの2乗誤差に対して、$t_mathrmmix tfracdn$の非漸近境界を示す。
マルコフ雑音による政策評価について,これらの結果のまとめを導出する。
論文 参考訳（メタデータ） (2021-12-23T18:47:50Z) - Complexity of zigzag sampling algorithm for strongly log-concave
distributions [6.336005544376984]
強いログ凹分布に対するジグザグサンプリングアルゴリズムの計算複雑性について検討する。
ジグザグサンプリングアルゴリズムは, 計算コストが$obiglに匹敵するchi-squareの発散において, $varepsilon$ 誤差を達成することを証明した。
論文 参考訳（メタデータ） (2020-12-21T03:10: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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。