論文の概要: A Contraction Framework for Stochastic Operators with Bootstrapping: Application to TD Learning
- arxiv url: http://arxiv.org/abs/2609.29961v1
- Date: Thu, 24 Sep 2026 15:18:29 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-09-25 21:10:10.046199
- Title: A Contraction Framework for Stochastic Operators with Bootstrapping: Application to TD Learning
- Title（参考訳）: ブートストラップ付き確率演算子のための契約フレームワーク:TD学習への応用
- Abstract要約: 反復アルゴリズムでは、サンプル更新とターゲットのリフレッシュをKステップ毎に行う方法を示す。
我々は、i.d.サンプルと任意の目標更新期間$K$に対して有限時間境界を導出する。
また, 凍結対象に対する感度が内部地図の収縮スラックよりも小さい場合, 固定点付近の球に対して, ルート平均二乗に幾何的に収束することを示した。
- 参考スコア（独自算出の注目度）: 21.04448505361607
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Many iterative algorithms rely on bootstrapping. A variable is updated using a second, frozen copy as a target, which is periodically replaced with the updated variable. Majorize-minimize and inexact proximal-point methods share this structure, as does temporal-difference (TD) learning. However, existing convergence guarantees for scenarios that combine sampled updates with targets refreshed only every $K$ steps rely on the specific structure of the update, such as linear approximation or gradient-based inner steps, and on uniformly bounded sampling error. We instead model the sampled update as a stochastic operator on the parameter space, which reduces the analysis to a contraction argument that needs no gradient structure and allows the sampling error to grow with the iterates. Within this framework, we derive a finite-time bound for i.i.d. samples and any target-update period $K$. We show that the iterates converge geometrically in root mean square to a ball around the fixed point, provided the sensitivity to the frozen target is smaller than the contraction slack of the inner map. Existing deterministic frozen-target contraction and stochastic-gradient-type bounds follow as special cases of our framework, and simulations of TD learning reproduce the predicted contraction rate and scaling of the error floor with the step size.
- Abstract（参考訳）: 多くの反復アルゴリズムはブートストラッピングに依存している。
変数は第2の凍結コピーをターゲットとして更新され、定期的に更新された変数に置き換えられる。
大規模最小化と不正確な近点法は、時間差学習(TD)と同様に、この構造を共有する。
しかし、既存の収束保証は、サンプリングされた更新とターゲットを組み合わすシナリオは、リニア近似や勾配ベースの内部ステップ、一様境界のサンプリングエラーといった、更新の特定の構造に依存している。
代わりに、サンプル更新をパラメータ空間上の確率演算子としてモデル化し、勾配構造を必要としない縮退引数まで解析を減らし、繰り返しでサンプリングエラーを増大させる。
このフレームワーク内では、i.d.サンプルと任意の目標更新期間$K$に対して有限時間境界を導出する。
また, 凍結対象に対する感度が内部地図の収縮スラックよりも小さい場合, 固定点付近の球に対して, ルート平均二乗に幾何的に収束することを示した。
既存の決定論的凍結目標収縮と確率的漸進型境界は,本フレームワークの特別な事例であり,TD学習のシミュレーションは,ステップサイズで予測された収縮率と誤差フロアのスケーリングを再現する。
関連論文リスト
- Self-Normalized Inference for Constant-Stepsize Temporal-Difference Learning under Markovian Sampling [9.271408028342496]
定段階時間差学習(TD)は政策評価に魅力的であるが,1つのマルコフ軌道からの推論は連続的依存と段階的依存的定常目標を考慮しなければならない。
我々は、ランダムなTD行列と定常反復誤差によって誘導される乗法成分を共分散が保持する機能中心極限定理を確立する。
FrozenLakeとGarnetの実験では、静止目標被覆、RR目標補正、地平線インデクシング設計の有限サンプル挙動が示されている。
論文 参考訳（メタデータ） (2026-08-11T13:19:28Z) - Stabilizing Extrapolation in Looped Transformers via Learned Stochastic Stopping [56.14767235650558]
共有トランスブロックを繰り返し適用するLooped Transformerは、可変長の計算タスクに自然に適合するアーキテクチャである。
この差分を、列長とループ数の間の単純なアルゴリズムタスクにおける突発的相関に追従する。
私たちの研究は、"停止する時"は単なる推論時間割当ルールではなく、トレーニング設計の選択として扱われるべきであることを示唆しています。
論文 参考訳（メタデータ） (2026-06-29T08:58:09Z) - A Finite-Time Analysis of TD Learning with Linear Function Approximation without Projections or Strong Convexity [11.513419525702924]
線形関数近似を用いた時間差分学習(TD)の有限時間収束特性について検討する。
単純な射影自由多様体は、マルコフノイズの存在下でさえ$widetildemathcalO(frac||theta)$の速度で収束することを示す。
論文 参考訳（メタデータ） (2025-06-01T15:39:00Z) - Stabilizing Temporal Difference Learning via Implicit Stochastic Recursion [2.1301560294088318]
時間差学習は強化学習における基礎的アルゴリズムである
本稿では,TD更新を固定点方程式に変換する暗黙的TDアルゴリズムを提案する。
以上の結果から,暗黙的TDアルゴリズムはより広いステップサイズに適用可能であることが示された。
論文 参考訳（メタデータ） (2025-05-02T15:57:54Z) - Finite time analysis of temporal difference learning with linear
function approximation: Tail averaging and regularisation [44.27439128304058]
そこで本研究では,TD学習アルゴリズムの時間的有限性について検討した。
ステップサイズ選択の下で、テール平均TDのパラメータ誤差に基づいて有限時間境界を導出する。
論文 参考訳（メタデータ） (2022-10-12T04:37:54Z) - Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and
Beyond [63.59034509960994]
シャッフルに基づく変種(ミニバッチと局所ランダムリシャッフル)について検討する。
ポリアック・ロジャシエヴィチ条件を満たす滑らかな函数に対して、これらのシャッフル型不変量(英語版)(shuffling-based variants)がそれらの置換式よりも早く収束することを示す収束境界を得る。
我々は, 同期シャッフル法と呼ばれるアルゴリズムの修正を提案し, ほぼ均一な条件下では, 下界よりも収束速度が速くなった。
論文 参考訳（メタデータ） (2021-10-20T02:25:25Z) - Convergence of Batch Asynchronous Stochastic Approximation With Applications to Reinforcement Learning [1.2966003263488448]
Reinforcement Learning (RL)のいくつかのアプリケーションでは、textitonlyの$theta_t$の1つのコンポーネントは、各$t$で更新される。
本稿では、 textbfBlock Asynchronous SA (BASA) について検討し、各ステップ $t$, textitsome で $theta_t$ のすべてのコンポーネントが更新される必要はない。
BASA の収束に十分な条件を提供し、$theta_t$ to の収束のテキスト化を証明します。
論文 参考訳（メタデータ） (2021-09-08T06:06:28Z) - Balancing Rates and Variance via Adaptive Batch-Size for Stochastic
Optimization Problems [120.21685755278509]
本研究は,ステップサイズの減衰が正確な収束に必要であるという事実と,一定のステップサイズがエラーまでの時間でより速く学習するという事実のバランスをとることを目的とする。
ステップサイズのミニバッチを最初から修正するのではなく,パラメータを適応的に進化させることを提案する。
論文 参考訳（メタデータ） (2020-07-02T16:02:02Z) - Path Sample-Analytic Gradient Estimators for Stochastic Binary Networks [78.76880041670904]
二進的アクティベーションや二進的重みを持つニューラルネットワークでは、勾配降下によるトレーニングは複雑である。
そこで本研究では,サンプリングと解析近似を併用した新しい推定法を提案する。
勾配推定において高い精度を示し、深部畳み込みモデルにおいてより安定かつ優れた訓練を行うことを示す。
論文 参考訳（メタデータ） (2020-06-04T21:51:21Z) - Non-asymptotic Convergence Analysis of Two Time-scale (Natural)
Actor-Critic Algorithms [58.57004511121862]
アクタークリティカル(AC)とナチュラルアクタークリティカル(NAC)のアルゴリズムは、最適なポリシーを見つけるために2つの方法で実行されることが多い。
2つの時間スケールACは、$mathcalO(epsilon-2.5log3(epsilon-1))$で、$epsilon$-accurateの定常点に達するために、全体のサンプルの複雑さを必要とすることを示す。
我々は,動的にマルコフサンプリングが変化するため,アクターのバイアス誤差をバウンドする新しい手法を開発した。
論文 参考訳（メタデータ） (2020-05-07T15:42:31Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。