論文の概要: Finite-Time Analysis of Discounted Exponential-Utility Reinforcement Learning
- arxiv url: http://arxiv.org/abs/2608.01917v1
- Date: Mon, 03 Aug 2026 08:50:07 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-08-04 15:07:25.417123
- Title: Finite-Time Analysis of Discounted Exponential-Utility Reinforcement Learning
- Title（参考訳）: 分散指数-ユーティリティ強化学習の有限時間解析
- Abstract要約: モデルなし割引指数効用強化学習における最初の有限時間保証を提供する。
これらの結果は、モデルなし割引指数効用強化学習における最初の有限時間保証を提供する。
- 参考スコア（独自算出の注目度）: 9.748884794669346
- License: http://creativecommons.org/licenses/by-sa/4.0/
- Abstract: Discounted exponential utility provides a principled criterion for risk-sensitive sequential decision-making, but its nonlinear structure complicates reinforcement learning. A recent work \citep{thoppe2026reinforcement} addressed this difficulty by introducing a Bellman-compatible surrogate and two model-free fixed-point algorithms for optimizing it over stationary policies. However, their main convergence results are asymptotic. In this work, we establish finite-time rates of $\tilde{O} (1/\sqrt{n})$ for the aforementioned two algorithms under asynchronous Markovian sampling, where $n$ is the iteration index and $\tilde{O}$ hides logarithmic expressions. Importantly, we employ parameter-free choices for the stepsize parameter to derive these rate results. For the algorithmically simpler one-timescale method, the main challenge is that its update equation is not directly aligned with the contraction geometry of its underlying power-law operator. We overcome this mismatch by exploiting the boundedness, monotonicity, and homogeneity of the operator to obtain a local pseudo-contraction property for the relative-error dynamics. We then use a Moreau-envelope-based Lyapunov function and Polyak--Ruppert averaging to obtain the stated convergence rate with parameter-free stepsizes. For the two-timescale method, the main challenge is to control a tracking error on the faster timescale. These results provide the first finite-time guarantees for model-free discounted exponential-utility reinforcement learning.
- Abstract（参考訳）: 分散指数的ユーティリティは、リスクに敏感なシーケンシャルな意思決定のための原則的基準を提供するが、その非線形構造は強化学習を複雑にする。
最近の研究 "citep{thoppe2026reinforcement}" では、ベルマン互換のサロゲートと2つのモデルフリーな固定点アルゴリズムを導入して、定常ポリシーを最適化することでこの問題に対処している。
しかし、それらの主な収束結果は漸近的である。
本研究では, 非同期マルコフサンプリング法において, 上記の2つのアルゴリズムに対して, $\tilde{O} (1/\sqrt{n})$の有限時間レートを定め, $n$は反復指数, $\tilde{O}$は対数表現を隠蔽する。
重要なことに、これらのレートを導出するために、段差パラメータにパラメータフリーの選択を用いる。
アルゴリズム的に単純化されたワンタイムスケール法では、その更新方程式が根底にあるパワーロー作用素の収縮幾何学と直接一致していないことが主な課題である。
このミスマッチを演算子の有界性, 単調性, 均一性を利用して克服し, 相対誤差力学の局所的擬似抽出特性を得る。
次に、モローエンベロープに基づくリアプノフ関数とポリアック-ルパート平均化を用いて、パラメータフリーなステップサイズで表現された収束率を得る。
2時間スケールの手法では、より高速な時間スケールでトラッキングエラーを制御することが主な課題である。
これらの結果は、モデルなし割引指数効用強化学習における最初の有限時間保証を提供する。
関連論文リスト
- Reinforcement Learning for Exponential Utility: Algorithms and Convergence in Discounted MDPs [2.574071344130061]
マルコフ決定過程における指数効用最適化のための強化学習(RL)は、原則的値ベースアルゴリズムを欠いている。
2つのQ値型拡張を導出し、関連する作用素が$L_infty$とsup-log/Thompsonメトリクスの縮約であることを示す。
我々は、時間スケールの分離により、ほぼ全周収束を確立し、有限時間収束率を与えるとともに、サブ線形パワーロー演算子によって制御される1時間スケールのアルゴリズムを提供する。
論文 参考訳（メタデータ） (2026-05-08T17:41:48Z) - Bridging Constraints and Stochasticity: A Fully First-Order Method for Stochastic Bilevel Optimization with Linear Constraints [3.567855687957749]
この研究は、一階法のみを用いた線形制約付き双レベル最適化に対する最初の有限時間収束保証を提供する。
線形制約、雑音、有限時間解析を両レベル最適化において同時に扱うという前例のない課題に対処する。
論文 参考訳（メタデータ） (2025-11-13T00:59:20Z) - A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。
提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
論文 参考訳（メタデータ） (2024-09-07T06:37:23Z) - Fast Nonlinear Two-Time-Scale Stochastic Approximation: Achieving $O(1/k)$ Finite-Sample Complexity [2.5382095320488665]
本稿では,2つの結合非線形作用素の根を探すために,2時間スケールのモノトン近似の新しい変種を開発することを提案する。
私たちのキーとなるアイデアは、古典的なRuppert-Polyak平均化技術を活用して、それらのサンプルを通して演算子を動的に推定することです。
これらの平均ステップの見積値は、望まれる解を見つけるために、2時間スケールの近似更新で使用される。
論文 参考訳（メタデータ） (2024-01-23T13:44:15Z) - Extra-Newton: A First Approach to Noise-Adaptive Accelerated
Second-Order Methods [57.050204432302195]
本研究では,2次スムーズな凸関数を最小化するための普遍的かつ適応的な2次法を提案する。
我々のアルゴリズムは、オラクルフィードバックが分散$sigma2$であるときに$O(sigma / sqrtT)$収束を達成し、決定論的オラクルで$O(1 / T3)$に収束を改善する。
論文 参考訳（メタデータ） (2022-11-03T14:12:51Z) - Explicit Second-Order Min-Max Optimization: Practical Algorithms and Complexity Analysis [71.05708939639537]
本研究では,非制約問題に対するグローバルなサドル点を求めるために,不正確なNewton型手法をいくつか提案し,解析する。
提案手法は,Sur分解の必要回数の$O(log(1/eps)$因子をシェービングすることで,既存のライン検索に基づくmin-max最適化を改善する。
論文 参考訳（メタデータ） (2022-10-23T21:24:37Z) - Gradient-Free Methods for Deterministic and Stochastic Nonsmooth
Nonconvex Optimization [94.19177623349947]
非滑らかな非最適化問題は、機械学習とビジネス製造に現れる。
2つのコア課題は、有限収束を保証する効率的な方法の開発を妨げる。
GFMとSGFMの2相版も提案され, 改良された大規模評価結果が得られた。
論文 参考訳（メタデータ） (2022-09-12T06:53:24Z) - Finite-Time Error Bounds for Greedy-GQ [20.51105692499517]
We show that Greedy-GQ algorithm converges fast-time error。
我々の分析は、ステップサイズを選択するために、より高速な収束ステップサイズを提供する。
論文 参考訳（メタデータ） (2022-09-06T15:04:57Z) - High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。
非滑らか凸最適化の既存の方法は、信頼度に依存した複雑性境界を持つ。
そこで我々は,勾配クリッピングを伴う2つの手法に対して,新たなステップサイズルールを提案する。
論文 参考訳（メタデータ） (2021-06-10T17:54:21Z) - Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth
Nonlinear TD Learning [145.54544979467872]
本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。
本研究の結果は, 同時一次および二重側収束の形で表される。
論文 参考訳（メタデータ） (2020-08-23T20:36:49Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。