論文の概要: Baird Counterexample Is Solved: with an example of How to Debug a Two-time-scale Algorithm

• arxiv url: http://arxiv.org/abs/2308.09732v1
• Date: Fri, 18 Aug 2023 00:46:42 GMT
• ステータス: 処理完了
• システム内更新日: 2023-08-22 20:09:34.746846
• Title: Baird Counterexample Is Solved: with an example of How to Debug a Two-time-scale Algorithm
• Title（参考訳）: Baird Counterexampleは解決された: 2時間スケールのアルゴリズムをデバッグする方法の例
• Authors: Hengshuai Yao
• Abstract要約: Baird反例は1995年にLeemon Bairdによって提案され、この例で時間差分(TD(0))アルゴリズムが分岐することを示すために最初に使われた。 勾配性TDアルゴリズムは、Baird反例におけるTDの分散問題を解いた。 しかし、この例におけるそれらの収束は依然として非常に遅く、遅くなる性質はよく理解されていない。
• 参考スコア（独自算出の注目度）: 6.429314569034207
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Baird counterexample was proposed by Leemon Baird in 1995, first used to show that the Temporal Difference (TD(0)) algorithm diverges on this example. Since then, it is often used to test and compare off-policy learning algorithms. Gradient TD algorithms solved the divergence issue of TD on Baird counterexample. However, their convergence on this example is still very slow, and the nature of the slowness is not well understood, e.g., see (Sutton and Barto 2018). This note is to understand in particular, why TDC is slow on this example, and provide debugging analysis to understand this behavior. Our debugging technique can be used to study the convergence behavior of two-time-scale stochastic approximation algorithms. We also provide empirical results of the recent Impression GTD algorithm on this example, showing the convergence is very fast, in fact, in a linear rate. We conclude that Baird counterexample is solved, by an algorithm with convergence guarantee to the TD solution in general and a fast convergence rate.
• Abstract（参考訳）: Baird反例は1995年にLeemon Bairdによって提案され、この例で時間差分(TD(0))アルゴリズムが分岐することを示すために最初に使われた。 それ以来、政治以外の学習アルゴリズムのテストや比較にしばしば使用される。 勾配TDアルゴリズムは、Baird反例におけるTDの分散問題を解いた。 しかし、この例におけるそれらの収束は依然として非常に遅く、例えば Sutton と Barto 2018 など、遅くなる性質はよく理解されていない。 特に、この例ではなぜTDCが遅いのかを理解し、この振る舞いを理解するためにデバッグ分析を提供する。 このデバッギング技術は,2時間スケール確率近似アルゴリズムの収束挙動の研究に利用できる。 この例では,最近の印象gtdアルゴリズムの実験結果も提供し,収束が非常に高速であることを示した。 我々は,一般のTD解に対する収束保証と高速収束率のアルゴリズムを用いて,Baird反例を解くことを結論付けた。

関連論文リスト

• Convergent plug-and-play with proximal denoiser and unconstrained regularization parameter [12.006511319607473]
  本稿では,Plug-Play(PGD)アルゴリズムの収束性について述べる。 最近の研究は、証明(DRS)による収束を探求している。 まず、新しい収束証明を提供する。 正規化にいかなる制限も課さないDSS。 第2に、画像復元の精度を高めるPGDの緩和版について検討する。
  論文  参考訳（メタデータ） (2023-11-02T13:18:39Z)
• Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Function [99.31457740916815]
  信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。 TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
  論文  参考訳（メタデータ） (2023-10-18T10:29:58Z)
• Block-coordinate Frank-Wolfe algorithm and convergence analysis for semi-relaxed optimal transport problem [20.661025590877774]
  凸半緩和最適輸送(OT)問題に対する高速ブロックコーディネートFrank-Wolfe (BCFW) アルゴリズムを提案する。 数値実験により,提案アルゴリズムはカラー転送に有効であり,最先端のアルゴリズムを超越することを示した。
  論文  参考訳（メタデータ） (2022-05-27T05:54:45Z)
• Nesterov Accelerated Shuffling Gradient Method for Convex Optimization [15.908060383231371]
  このアルゴリズムは,統一シャッフル方式を用いて,$mathcalO (1/T)$の改善率を示す。 我々の収束解析は有界領域や有界勾配条件に関する仮定を必要としない。 数値シミュレーションはアルゴリズムの効率を実証する。
  論文  参考訳（メタデータ） (2022-02-07T21:23:17Z)
• Variance-Reduced Off-Policy TDC Learning: Non-Asymptotic Convergence Analysis [27.679514676804057]
  オフ・ポリシー・セッティングにおける2つの時間スケールTDCアルゴリズムの分散化手法を開発した。 実験により,提案した分散還元型TDCは,従来のTDCと分散還元型TDよりも収束誤差が小さいことを示した。
  論文  参考訳（メタデータ） (2020-10-26T01:33:05Z)
• Learning to solve TV regularized problems with unrolled algorithms [18.241062505073234]
  トータル・バージョニング(Total Variation、TV)は、一方向定値信号を促進する一般的な正規化戦略である。 そこで我々は,2つのアプローチを開発し,そのメリットと限界を記述し,反復的な手順よりも実際に改善できる体制について議論する。
  論文  参考訳（メタデータ） (2020-10-19T14:19:02Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。 本研究の結果は, 同時一次および二重側収束の形で表される。
  論文  参考訳（メタデータ） (2020-08-23T20:36:49Z)
• On the Almost Sure Convergence of Stochastic Gradient Descent in Non-Convex Problems [75.58134963501094]
  本稿では,勾配降下(SGD)の軌跡を解析する。 我々はSGDが厳格なステップサイズポリシーのために1ドルでサドルポイント/マニフォールドを避けることを示す。
  論文  参考訳（メタデータ） (2020-06-19T14:11:26Z)
• Learning to Accelerate Heuristic Searching for Large-Scale Maximum Weighted b-Matching Problems in Online Advertising [51.97494906131859]
  バイパルタイトbマッチングはアルゴリズム設計の基本であり、経済市場や労働市場などに広く適用されている。 既存の正確で近似的なアルゴリズムは、通常そのような設定で失敗する。 我々は、以前の事例から学んだ知識を活用して、新しい問題インスタンスを解決するtextttNeuSearcherを提案する。
  論文  参考訳（メタデータ） (2020-05-09T02:48:23Z)
• 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)
• Lagrangian Decomposition for Neural Network Verification [148.0448557991349]
  ニューラルネットワーク検証の基本的なコンポーネントは、出力が取ることのできる値のバウンダリの計算である。 ラグランジアン分解に基づく新しい手法を提案する。 ランニングタイムのごく一部で、既成の解法に匹敵するバウンダリが得られることを示す。
  論文  参考訳（メタデータ） (2020-02-24T17:55:10Z)

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

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