論文の概要: Accelerating Value Iteration with Anchoring
- arxiv url: http://arxiv.org/abs/2305.16569v1
- Date: Fri, 26 May 2023 01:32:21 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-29 17:29:42.594107
- Title: Accelerating Value Iteration with Anchoring
- Title（参考訳）: Anchoringによる価値イテレーションの高速化
- Authors: Jongmin Lee, Ernest K. Ryu
- Abstract要約: 価値反復(VI)は現代の強化学習の理論と実践の基礎となっている。
ベルマン整合性演算子と最適性演算子の両方に対して、最初の加速 VI を示す。
- 参考スコア（独自算出の注目度）: 11.425115656134961
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Value Iteration (VI) is foundational to the theory and practice of modern
reinforcement learning, and it is known to converge at a
$\mathcal{O}(\gamma^k)$-rate, where $\gamma$ is the discount factor.
Surprisingly, however, the optimal rate for the VI setup was not known, and
finding a general acceleration mechanism has been an open problem. In this
paper, we present the first accelerated VI for both the Bellman consistency and
optimality operators. Our method, called Anc-VI, is based on an
\emph{anchoring} mechanism (distinct from Nesterov's acceleration), and it
reduces the Bellman error faster than standard VI. In particular, Anc-VI
exhibits a $\mathcal{O}(1/k)$-rate for $\gamma\approx 1$ or even $\gamma=1$,
while standard VI has rate $\mathcal{O}(1)$ for $\gamma\ge 1-1/k$, where $k$ is
the iteration count. We also provide a complexity lower bound matching the
upper bound up to a constant factor of $4$, thereby establishing optimality of
the accelerated rate of Anc-VI. Finally, we show that the anchoring mechanism
provides the same benefit in the approximate VI and Gauss--Seidel VI setups as
well.
- Abstract（参考訳）: 値反復(VI)は現代の強化学習の理論と実践の基礎であり、$\mathcal{O}(\gamma^k)$-rateで収束することが知られている。
しかし、驚くべきことに、vi設定の最適速度は分かっておらず、一般的な加速機構を見つけることはオープンな問題であった。
本稿ではベルマン整合性演算子と最適性演算子の両方に対する最初の加速VIを示す。
我々の手法は Anc-VI と呼ばれ、nesterov の加速度と区別する) \emph{anchoring} 機構に基づいており、標準 VI よりもベルマン誤差を高速に低減する。
特に、Anc-VI は $\mathcal{O}(1/k)$-rate for $\gamma\approx 1$ あるいは $\gamma=1$ であるのに対して、標準 VI は $\mathcal{O}(1)$ for $\gamma\ge 1-1/k$ である。
また,anc-viの加速速度の最適性を確立するために,上限値が4ドルの定数値まで一致するような複雑性を低減できる。
最後に、アンカー機構が近似 VI とガウス-シーデル VI のセットアップにも同様の利点をもたらすことを示す。
関連論文リスト
- Distributed Extra-gradient with Optimal Complexity and Communication
Guarantees [60.571030754252824]
複数のプロセッサ/ワーカー/クライアントがローカルなデュアルベクトルにアクセス可能なマルチGPU設定において、モノトン変分不等式(VI)問題を考察する。
モノトーンVI問題に対するデファクトアルゴリズムであるExtra-gradientは、通信効率が良くないように設計されている。
そこで本稿では,VI の解法に適した非バイアスで適応的な圧縮手法である量子化一般化外部勾配 (Q-GenX) を提案する。
論文 参考訳（メタデータ） (2023-08-17T21:15:04Z) - Accelerated Quasi-Newton Proximal Extragradient: Faster Rate for Smooth
Convex Optimization [26.328847475942894]
我々は,本手法が$Obigl(minfrac1k2, fracsqrtdlog kk2.5bigr)$の収束率を達成できることを証明した。
我々の知る限りでは、この結果はネステロフの加速勾配に対する準ニュートン型法の証明可能な利得を示す最初のものである。
論文 参考訳（メタデータ） (2023-06-03T23:31:27Z) - A note on $L^1$-Convergence of the Empiric Minimizer for unbounded
functions with fast growth [0.0]
V : mathbbRd to mathbbR$ coercive に対して、経験的最小値の$L1$-distance の収束率について検討する。
一般に、高速な成長を持つ非有界函数に対しては、収束率は上述の$a_n n-1/q$で制限され、$q$は潜在確率変数の次元である。
論文 参考訳（メタデータ） (2023-03-08T08:46:13Z) - Solving Constrained Variational Inequalities via an Interior Point
Method [88.39091990656107]
制約付き変分不等式(cVI)問題を解くためのインテリアポイントアプローチを開発する。
本稿では,2種類の問題においてACVIの収束保証を提供する。
この設定における以前の作業とは異なり、ACVIは制約が自明でない場合にcVIを解く手段を提供する。
論文 参考訳（メタデータ） (2022-06-21T17:55:13Z) - Sharper Convergence Guarantees for Asynchronous SGD for Distributed and
Federated Learning [77.22019100456595]
通信周波数の異なる分散計算作業者のトレーニングアルゴリズムを示す。
本研究では,より厳密な収束率を$mathcalO!!(sigma2-2_avg!)とする。
また,不均一性の項は,作業者の平均遅延によっても影響されることを示した。
論文 参考訳（メタデータ） (2022-06-16T17:10:57Z) - Perseus: A Simple and Optimal High-Order Method for Variational
Inequalities [81.32967242727152]
VI は、$langle F(x), x - xstarrangle geq 0$ for all $x in MathcalX$ であるように、mathcalX$ で $xstar を見つける。
そこで本稿では,テキストitが行探索を必要とせず,$O(epsilon-2/(p+1))$で弱解に確実に収束する$pth$-order法を提案する。
論文 参考訳（メタデータ） (2022-05-06T13:29:14Z) - A first-order primal-dual method with adaptivity to local smoothness [64.62056765216386]
凸凹対象 $min_x max_y f(x) + langle Ax, yrangle - g*(y)$, ここで、$f$ は局所リプシッツ勾配を持つ凸関数であり、$g$ は凸かつ非滑らかである。
主勾配ステップと2段ステップを交互に交互に行うCondat-Vuアルゴリズムの適応バージョンを提案する。
論文 参考訳（メタデータ） (2021-10-28T14:19:30Z) - Halpern-Type Accelerated and Splitting Algorithms For Monotone
Inclusions [14.445131747570962]
我々は、最大単調方程式のクラスを解くために、新しいタイプの加速アルゴリズムを開発する。
我々の手法は[32]におけるハルパーン型固定点反復と呼ばれるものに依存しており、近年多くの研究者が利用している。
論文 参考訳（メタデータ） (2021-10-15T15:26:32Z) - f-Divergence Variational Inference [9.172478956440216]
$f$-VIフレームワークは、既存のVIメソッドを統一する。
一般の$f$-変数境界が導出され、限界確率(または証拠)のサンドイッチ推定を提供する。
また、f$-VIに対して、よく知られた座標のアセント変分推論を一般化する平均場近似スキームを提案する。
論文 参考訳（メタデータ） (2020-09-28T06:22:05Z) - Accelerated Zeroth-Order and First-Order Momentum Methods from Mini to
Minimax Optimization [133.53164856723782]
そこで我々は,関数値のみが得られるブラックボックス最小最適化のための新しいアクセラレーションゼロ階運動量 (AccZOM) 法を提案する。
一方,ブラックボックス最小値最適化のためのアクセラレーションゼロ階運動量降下法(Acc-MDA)を提案する。
特に、Acc-MDAは、$tildeO(kappa_y2.5epsilon-3)$の低い勾配の複雑さを、バッチサイズ$O(kappa_y4)$で得ることができる。
論文 参考訳（メタデータ） (2020-08-18T22:19:29Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。