論文の概要: Beyond the Bellman Fixed Point: Geometry and Fast Policy Identification in Value Iteration

• arxiv url: http://arxiv.org/abs/2604.17457v2
• Date: Tue, 21 Apr 2026 11:49:02 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-22 14:04:47.923263
• Title: Beyond the Bellman Fixed Point: Geometry and Fast Policy Identification in Value Iteration
• Title（参考訳）: ベルマン固定点を超えて: 値反復における幾何と高速なポリシー同定
• Abstract要約: 本稿では,スイッチングシステム理論のレンズを通して,ディスカウントされたQ-VIを再検討する。 Q-VI は一般に有限時間において$Q*$に到達しないが、有限時間において最適な作用クラスを特定する。
• 参考スコア（独自算出の注目度）: 7.8232617281369805
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Dynamic programming is one of the most fundamental methodologies for solving Markov decision problems. Among its many variants, Q-value iteration (Q-VI) is particularly important due to its conceptual simplicity and its classical contraction-based convergence guarantee. Despite the central role of this contraction property, it does not fully reveal the geometric structure of the Q-VI trajectory. In particular, when one is interested not only in the final limit $Q^*$ but also in when the induced greedy policy becomes effectively optimal, the standard contraction argument provides only a coarse characterization. To formalize this notion, we denote by $\mathcal X^*$ the set of $Q$-functions whose corresponding tie-broken greedy policies are optimal, referred to as the practically optimal solution set (POS). In this paper, we revisit discounted Q-VI through the lens of switching system theory and derive new geometric insights into its behavior. In particular, we show that although Q-VI does not reach $Q^*$ in finite time in general, it identifies the optimal action class in finite time. Furthermore, we prove that the distance from the iterate to a particular subset of $\mathcal X^*$ decays exponentially at a rate governed by the joint spectral radius (JSR) of a restricted switching family. This rate can be strictly faster than the standard $γ$ rate when the restricted JSR is strictly smaller than $γ$, while the convergence of the entire $Q$-function to $Q^*$ can still be dominated by the slower $γ$ mode, where $γ$ denotes the discount factor. These results reveal a two-stage geometric behavior of Q-VI: a fast convergence toward $\mathcal X_1$, followed by a slower convergence toward $Q^*$ in general.
• Abstract（参考訳）: 動的プログラミングはマルコフ決定問題を解くための最も基本的な方法論の1つである。 多くの変種の中で、Q-値反復(Q-VI)は概念的単純さと古典的収縮に基づく収束を保証するため特に重要である。 この収縮特性の中心的な役割にもかかわらず、Q-VI軌道の幾何学的構造を完全には明らかにしていない。 特に、最終極限$Q^*$だけでなく、誘導された欲求ポリシーが効果的に最適になったときにも、標準収縮論証は粗い特徴を与えるだけである。 この概念を定式化するには、$\mathcal X^*$ で、対応する階層的欲求ポリシーが最適である$Q$-函数の集合を、実際最適解集合 (POS) と呼ぶ。 本稿では, スイッチングシステム理論のレンズを通して, Q-VI の割引を再度検討し, その挙動に関する新たな幾何学的洞察を導出する。 特に、Q-VI は一般に有限時間において$Q^*$に到達しないが、有限時間において最適な作用クラスを特定する。 さらに、イテレートから$\mathcal X^*$の特定の部分集合への距離は、制限されたスイッチングファミリーの結合スペクトル半径(JSR)に支配される速度で指数関数的に崩壊することを示す。 制限されたJSRが$γ$よりも厳密に小さい場合、このレートは標準の$γ$よりも厳格に速いが、$Q$関数全体の$Q^*$への収束は、さらに遅い$γ$モードによって支配され、$γ$は割引係数を表す。 これらの結果は、Q-VIの2段階の幾何学的挙動を示す:$\mathcal X_1$への高速収束と、一般に$Q^*$への緩やかな収束である。

関連論文リスト

• Discretization and Statistical Consistency of Functional Flow Matching [0.0]
  有限ランク再構成の強い一貫した列に対して、有限条件速度目標の強い$L2$収束を証明した。 学習フローに対して、集団重ね合わせ経路に直接結合すると、終端ワッサーシュタイン境界が得られる。
  論文  参考訳（メタデータ） (2026-08-05T07:05:47Z)
• Optimal Dimension-Free Sampling for Regularized Classification [56.72526267755301]
  我々は、リプシッツ連続分類損失関数の幅広いクラスに対して、$(1pmvarepsilon)$-relativeエラーを達成する最適サンプリング境界を証明した。 これにはロジスティックやシグモイドの損失、ヒンジの損失、ReLUの損失といった重要な機能が含まれており、顕著で一般的な例である。
  論文  参考訳（メタデータ） (2026-05-22T15:05:33Z)
• Optimistic Training and Convergence of Q-Learning -- Extended Version [0.0]
  近年の研究では,線形関数近似を用いたQ-ラーニングが安定であることが示されている。 一次元の例は、トレーニングの難解なポリシーの下では、PBEに対する解決策がないことを示している。 基底が理想であるような例は、真の Q-函数が基底のスパンであるという意味で示される。
  論文  参考訳（メタデータ） (2026-02-05T19:32:13Z)
• A Polynomial-Time Algorithm for Variational Inequalities under the Minty Condition [77.76727425995186]
  変分不等式(SVIs)の解決は、最適化の中心にある基礎的な問題である。 ほとんどの研究は、その難易度を損なう特定のサブクラスを彫刻することに重点を置いている。
  論文  参考訳（メタデータ） (2025-04-04T13:24:41Z)
• On the Convergence of Single-Timescale Actor-Critic [49.19842488693726]
  本研究では,有限状態空間を持つ無限水平割引決定過程(MD)に対して,単時間アクタークリティカル(AC)アルゴリズムのグローバル収束を解析する。 我々は,アクタと批評家の両方のステップサイズが (O(k-Pfrac12) として崩壊し,従来の (O(k-Pfrac12) ) レートから (非最適) の Markov フレームワーク最適化で一般的に使用される (O(k-Pfrac12) ) レートから$k$ になることを示した。
  論文  参考訳（メタデータ） (2024-10-11T14:46:29Z)
• Revisiting the Last-Iterate Convergence of Stochastic Gradient Methods [25.831462008050387]
  グラディエント・Descent(SGD)アルゴリズムは、実際の性能が良く、理論的な理解が欠如していることから、人々の関心を喚起している。 有限収束がより広い合成最適化や非ユークリッドノルムに証明可能な拡張が可能かどうかはまだ不明である。
  論文  参考訳（メタデータ） (2023-12-13T21:41:06Z)
• Sharpened Lazy Incremental Quasi-Newton Method [15.632456816019944]
  SLIQN法(シャープエントラジインクリメンタル準ニュートン法)について紹介する。 明示的な超線型収束率と優れた経験的性能を、定価$O(d2)$コストで達成する。 実験では,他の準ニュートン変種よりもSLIQNの方が優れていることを示した。
  論文  参考訳（メタデータ） (2023-05-26T22:06:24Z)
• A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization [53.044526424637866]
  本稿では、2つの異なる対象の一般円錐最適化を最小化する近似二階定常点(SOSP)について検討する。 特に、近似SOSPを見つけるためのNewton-CGベースの拡張共役法を提案する。
  論文  参考訳（メタデータ） (2023-01-10T20:43:29Z)
• Min-Max Optimization Made Simple: Approximating the Proximal Point Method via Contraction Maps [77.8999425439444]
  本稿では,凸/凹凸 min-max 問題に対して,ほぼ最適収束率を許容する一階法を提案する。 我々の研究は、近点法の更新規則を精度良く近似できるという事実に基づいている。
  論文  参考訳（メタデータ） (2023-01-10T12:18:47Z)
• Convergence rate of the (1+1)-evolution strategy on locally strongly convex functions with lipschitz continuous gradient [10.31411804947731]
  進化戦略 (ES) はブラックボックス連続最適化のためのアルゴリズムの有望なクラスの一つである。 本研究では,局所$L$-強凸関数上の (1+1)-ES の線型収束率の上界と下界を$U$-Lipschitz連続勾配で導出した。
  論文  参考訳（メタデータ） (2022-09-26T07:16:50Z)
• Finite-Time Error Bounds for Greedy-GQ [20.51105692499517]
  We show that Greedy-GQ algorithm converges fast-time error。 我々の分析は、ステップサイズを選択するために、より高速な収束ステップサイズを提供する。
  論文  参考訳（メタデータ） (2022-09-06T15:04:57Z)
• Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
  滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。 漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
  論文  参考訳（メタデータ） (2022-06-17T06:10:20Z)
• A globally convergent fast iterative shrinkage-thresholding algorithm with a new momentum factor for single and multi-objective convex optimization [0.0]
  提案手法はまた,任意の$(a,b)$に対して,大域収束率$O(1/k2)$を持つことを示す。 様々な$(a,b)$で数値結果を報告し、これらの選択のいくつかが古典的な運動量因子よりも良い結果をもたらすことを示す。
  論文  参考訳（メタデータ） (2022-05-11T04:26:00Z)
• Simulated annealing from continuum to discretization: a convergence analysis via the Eyring--Kramers law [10.406659081400354]
  連続時間アニーリング$(X_t;, t ge 0)$とその離散化$(x_k;, k =0,1, ldots)$の収束率について検討する。 我々は、テール確率 $mathbbP(f(X_t) > min f +delta)$ (resp. $mathP(f(x_k) > min f +delta)$) が時間内に崩壊することを証明する(累積ステップサイズでは、resp. $mathP(f(x_k) > min f +delta)$)。
  論文  参考訳（メタデータ） (2021-02-03T23:45:39Z)
• Fast Rates for the Regret of Offline Reinforcement Learning [69.23654172273085]
  無限水平割引決定プロセス(MDP)における固定行動ポリシーによって生成されたオフラインデータからの強化学習の後悔について検討する。 最適品質関数 $Q*$ に対する任意の推定が与えられたとき、定義するポリシーの後悔は、$Q*$-estimate の点収束率の指数によって与えられる速度で収束することを示す。
  論文  参考訳（メタデータ） (2021-01-31T16:17:56Z)
• Finite-Time Analysis for Double Q-learning [50.50058000948908]
  二重Q-ラーニングのための非漸近的有限時間解析を初めて提供する。 同期と非同期の二重Q-ラーニングの両方が,グローバル最適化の$epsilon$-accurate近辺に収束することが保証されていることを示す。
  論文  参考訳（メタデータ） (2020-09-29T18:48:21Z)
• A Simple Convergence Proof of Adam and Adagrad [74.24716715922759]
  我々はAdam Adagradと$O(d(N)/st)$アルゴリズムの収束の証明を示す。 Adamはデフォルトパラメータで使用する場合と同じ収束$O(d(N)/st)$で収束する。
  論文  参考訳（メタデータ） (2020-03-05T01:56:17Z)

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

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