論文の概要: Stochastic Approximation with Unbounded Markovian Noise: A General-Purpose Theorem

• arxiv url: http://arxiv.org/abs/2410.21704v1
• Date: Tue, 29 Oct 2024 03:40:53 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-10-30 13:38:45.998203
• Title: Stochastic Approximation with Unbounded Markovian Noise: A General-Purpose Theorem
• Title（参考訳）: 非有界マルコフ雑音による確率近似:一般目的理論
• Authors: Shaan Ul Haque, Siva Theja Maguluri,
• Abstract要約: 非有界な状態空間と報酬関数を持つ平均逆強化学習を考える。 近年の研究では、この問題をアクター批判の枠組みで研究している。 線形関数近似を用いた時間差分学習(TD)について検討した。
• 参考スコア（独自算出の注目度）: 7.443139252028032
• License:
• Abstract: Motivated by engineering applications such as resource allocation in networks and inventory systems, we consider average-reward Reinforcement Learning with unbounded state space and reward function. Recent works studied this problem in the actor-critic framework and established finite sample bounds assuming access to a critic with certain error guarantees. We complement their work by studying Temporal Difference (TD) learning with linear function approximation and establishing finite-time bounds with the optimal $\mathcal{O}\left(1/\epsilon^2\right)$ sample complexity. These results are obtained using the following general-purpose theorem for non-linear Stochastic Approximation (SA). Suppose that one constructs a Lyapunov function for a non-linear SA with certain drift condition. Then, our theorem establishes finite-time bounds when this SA is driven by unbounded Markovian noise under suitable conditions. It serves as a black box tool to generalize sample guarantees on SA from i.i.d. or martingale difference case to potentially unbounded Markovian noise. The generality and the mild assumption of the setup enables broad applicability of our theorem. We illustrate its power by studying two more systems: (i) We improve upon the finite-time bounds of $Q$-learning by tightening the error bounds and also allowing for a larger class of behavior policies. (ii) We establish the first ever finite-time bounds for distributed stochastic optimization of high-dimensional smooth strongly convex function using cyclic block coordinate descent.
• Abstract（参考訳）: ネットワークや在庫システムにおける資源配分などの工学的応用によって動機づけられた,非有界な状態空間と報酬関数を持つ平均逆強化学習を考察する。 近年の研究では、アクター批判の枠組みでこの問題を研究し、一定のエラー保証を条件として、批判者へのアクセスを前提とした有限サンプル境界を確立している。 時間差分(TD)学習を線形関数近似を用いて研究し、最適な$\mathcal{O}\left(1/\epsilon^2\right)$サンプル複雑性で有限時間境界を確立することで、それらの研究を補完する。 これらの結果は、非線形確率近似(SA)に対する以下の汎用定理を用いて得られる。 あるドリフト条件の非線型 SA に対して、リアプノフ函数を構成すると仮定する。 そして、この定理は、この SA が適当な条件下で非有界マルコフ雑音によって駆動されるときの有限時間境界を定めている。 ブラックボックスツールとして機能し、SAのサンプル保証をマーチンゲール差分ケースから潜在的に有界なマルコフ雑音に一般化する。 集合の一般性と穏やかな仮定は、我々の定理の広範な適用を可能にする。 さらに2つのシステムを研究することで、そのパワーを説明します。 (i) エラー境界を厳格化し, より大規模な行動ポリシーを実現することにより, 有限時間での$Q$-learningのバウンダリを改善する。 (II)循環ブロック座標を用いた高次元滑らかな凸関数の確率的分散最適化のための最初の有限時間境界を確立する。

関連論文リスト

• Stochastic Approximation with Delayed Updates: Finite-Time Rates under Markovian Sampling [73.5602474095954]
  マルコフサンプリングの遅延更新による近似スキームの非漸近的性能について検討した。 我々の理論的な発見は、幅広いアルゴリズムの遅延の有限時間効果に光を当てた。
  論文  参考訳（メタデータ） (2024-02-19T03:08:02Z)
• The Curse of Memory in Stochastic Approximation: Extended Version [1.534667887016089]
  適応制御の初期から、制御システムコミュニティ内で近似の理論と応用が成長してきた。 近年の結果, (十分小さい) ステップサイズ$alpha>0$のSAの顕著な性能が確認されている。
  論文  参考訳（メタデータ） (2023-09-06T12:22:32Z)
• Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation Constrained Optimization [88.0031283949404]
  多くの実世界の問題は複雑な非機能的制約を持ち、多くのデータポイントを使用する。 提案手法は,従来最もよく知られた結果で既存手法よりも優れた性能を示す。
  論文  参考訳（メタデータ） (2022-12-19T14:48:54Z)
• Optimal variance-reduced stochastic approximation in Banach spaces [114.8734960258221]
  可分バナッハ空間上で定義された収縮作用素の定点を推定する問題について検討する。 演算子欠陥と推定誤差の両方に対して漸近的でない境界を確立する。
  論文  参考訳（メタデータ） (2022-01-21T02:46:57Z)
• Concave Utility Reinforcement Learning with Zero-Constraint Violations [43.29210413964558]
  本稿では,凸制約を伴うCURL(Concave utility reinforcement Learning)の問題点について考察する。 制約違反をゼロにするモデルベース学習アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-09-12T06:13:33Z)
• High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
  アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。 非滑らか凸最適化の既存の方法は、信頼度に依存した複雑性境界を持つ。 そこで我々は,勾配クリッピングを伴う2つの手法に対して,新たなステップサイズルールを提案する。
  論文  参考訳（メタデータ） (2021-06-10T17:54:21Z)
• Optimal oracle inequalities for solving projected fixed-point equations [53.31620399640334]
  ヒルベルト空間の既知の低次元部分空間を探索することにより、確率観測の集合を用いて近似解を計算する手法を検討する。 本稿では,線形関数近似を用いた政策評価問題に対する時間差分学習手法の誤差を正確に評価する方法について述べる。
  論文  参考訳（メタデータ） (2020-12-09T20:19:32Z)
• On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentration [115.1954841020189]
  The inequality and non-asymptotic properties of approximation procedure with Polyak-Ruppert averaging。 一定のステップサイズと無限大となる反復数を持つ平均的反復数に対する中心極限定理(CLT)を証明する。
  論文  参考訳（メタデータ） (2020-04-09T17:54:18Z)
• Stochastic Approximation with Markov Noise: Analysis and applications in reinforcement learning [0.0]
  マルコフ雑音によって駆動される2つの時間スケール近似の収束解析を初めて提示する。 両方の時間スケールにおける差分包摂を限定することで、フレームワークの挙動を分析する。 ポリシ評価アルゴリズムの関数近似における最初の情報的誤差境界を求める。
  論文  参考訳（メタデータ） (2020-04-08T03:59:21Z)
• Finite-Sample Analysis of Stochastic Approximation Using Smooth Convex Envelopes [40.31139355952393]
  一般化エンベロープを用いて滑らかなリャプノフ函数を構築し、そのリャプノフ函数に対してSAの反復体が負のドリフトを持つことを示す。 特に、政治以外のTD学習において、Vトレースアルゴリズムの最初の既知収束率を確立するためにこれを用いる。 また、TD学習を現場で研究し、既存の最先端の成果を$Q$ラーニングで回収する。
  論文  参考訳（メタデータ） (2020-02-03T16:42:01Z)

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

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