論文の概要: Optimal Rates of Convergence for Entropy Regularization in Discounted Markov Decision Processes
- arxiv url: http://arxiv.org/abs/2406.04163v3
- Date: Wed, 07 May 2025 08:19:19 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-05-08 19:07:35.686743
- Title: Optimal Rates of Convergence for Entropy Regularization in Discounted Markov Decision Processes
- Title（参考訳）: 離散マルコフ決定過程におけるエントロピー規則化のための収束の最適速度
- Authors: Johannes Müller, Semih Cayci,
- Abstract要約: マルコフ決定過程におけるエントロピー正則化による誤差について検討する。
この誤差は逆正則化強度で指数関数的に減少することを示す。
私たちは分析をエントロピーを超えた設定に拡張します。
- 参考スコア（独自算出の注目度）: 4.714840786221651
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the error introduced by entropy regularization in infinite-horizon, discrete, discounted Markov decision processes. We show that this error decreases exponentially in the inverse regularization strength both in a weighted KL-divergence and in value with a problem-specific exponent. This is in contrast to previously known estimates, of the order $O(\tau)$, where $\tau$ is the regularization strength. We provide a lower bound matching our upper bound up to a polynomial term, thereby characterizing the exponential convergence rate for entropy regularization. Our proof relies on the observation that the solutions of entropy-regularized Markov decision processes solve a gradient flow of the unregularized reward with respect to a Riemannian metric common in natural policy gradient methods. This correspondence allows us to identify the limit of this gradient flow as the generalized maximum entropy optimal policy, thereby characterizing the implicit bias of this gradient flow, which corresponds to a time-continuous version of the natural policy gradient method. We use our improved error estimates to show that for entropy-regularized natural policy gradient methods, the overall error decays exponentially in the square root of the number of iterations, improving over existing sublinear guarantees. Finally, we extend our analysis to settings beyond the entropy. In particular, we characterize the implicit bias regarding general convex potentials and their resulting generalized natural policy gradients.
- Abstract（参考訳）: 無限水平離散化マルコフ決定過程におけるエントロピー正則化による誤差について検討する。
この誤差は、重み付きKL偏差と問題固有指数の値の両方において、逆正則化強度において指数関数的に減少することを示す。
これは、既に知られている$O(\tau)$の次数である$O(\tau)$とは対照的に、$\tau$は正規化強度である。
多項式項までの上界に一致する下界を与え、エントロピー正則化の指数収束率を特徴づける。
我々の証明は、エントロピー正則化マルコフ決定過程の解が、自然政策勾配法に共通するリーマン計量に対する非正則化報酬の勾配フローを解くという観察に依存している。
この対応により、この勾配流の極限を一般化された最大エントロピー最適ポリシーとして特定することができ、これにより、自然方針勾配法の時間連続バージョンに対応する勾配流の暗黙バイアスを特徴づけることができる。
改良された誤差推定値を用いて、エントロピー規則化された自然方針勾配法では、全体の誤差は繰り返し回数の平方根で指数関数的に減少し、既存のサブ線形保証よりも改善されることを示す。
最後に、分析をエントロピー以外の設定にまで拡張します。
特に、一般凸ポテンシャルに関する暗黙バイアスとその結果として生じる一般化された自然政策勾配を特徴づける。
関連論文リスト
- Entropy annealing for policy mirror descent in continuous time and space [2.8255028200738455]
本研究では,エントロピー正則化が出口時間制御問題に対する政策手法の収束に及ぼす影響について検討する。
本稿では,真の勾配であっても,エントロピー正則化が政策最適化をどのように改善するかを説明する。
論文 参考訳（メタデータ） (2024-05-30T17:02:18Z) - A Unified Theory of Stochastic Proximal Point Methods without Smoothness [52.30944052987393]
近点法はその数値的安定性と不完全なチューニングに対する頑健性からかなりの関心を集めている。
本稿では,近位点法(SPPM)の幅広いバリエーションの包括的解析について述べる。
論文 参考訳（メタデータ） (2024-05-24T21:09:19Z) - A Fisher-Rao gradient flow for entropy-regularised Markov decision
processes in Polish spaces [10.777806006475297]
無限水平エントロピー規則化マルコフ決定過程に対するフィッシャー・ラオ政策勾配流のポーランド状態と行動空間による大域収束について検討する。
勾配流の大域的健全性を確立し,その指数収束性を示す。
論文 参考訳（メタデータ） (2023-10-04T16:41:36Z) - First Order Methods with Markovian Noise: from Acceleration to Variational Inequalities [91.46841922915418]
本稿では,一階変分法の理論解析のための統一的アプローチを提案する。
提案手法は非線形勾配問題とモンテカルロの強い問題の両方をカバーする。
凸法最適化問題の場合、オラクルに強く一致するような境界を与える。
論文 参考訳（メタデータ） (2023-05-25T11:11:31Z) - On the Importance of Gradient Norm in PAC-Bayesian Bounds [92.82627080794491]
対数ソボレフ不等式の縮約性を利用する新しい一般化法を提案する。
我々は、この新たな損失段階的ノルム項が異なるニューラルネットワークに与える影響を実証的に分析する。
論文 参考訳（メタデータ） (2022-10-12T12:49:20Z) - On the Convergence Rates of Policy Gradient Methods [9.74841674275568]
有限状態部分空間における幾何的に割引された支配問題を考える。
試料中の直交勾配のパラリゼーションにより、勾配の一般的な複雑さを解析できることが示される。
論文 参考訳（メタデータ） (2022-01-19T07:03:37Z) - Convergence of policy gradient for entropy regularized MDPs with neural
network approximation in the mean-field regime [0.0]
無限水平連続状態および行動空間,エントロピー規則化マルコフ決定過程(MDPs)に対する政策勾配のグローバル収束性について検討する。
結果は非線形フォッカー-プランク-コルモゴロフ方程式の慎重な解析に依存する。
論文 参考訳（メタデータ） (2022-01-18T20:17:16Z) - Beyond Exact Gradients: Convergence of Stochastic Soft-Max Policy Gradient Methods with Entropy Regularization [20.651913793555163]
古典的エントロピー正規化政策勾配法をソフトマックス政策パラメトリゼーションで再検討する。
提案したアルゴリズムに対して,大域的最適収束結果と$widetildemathcalO(frac1epsilon2)$のサンプル複雑性を確立する。
論文 参考訳（メタデータ） (2021-10-19T17:21:09Z) - Linear Convergence of Entropy-Regularized Natural Policy Gradient with
Linear Function Approximation [30.02577720946978]
線形関数近似を用いたエントロピー規則化NPGの有限時間収束解析を確立した。
エントロピー規則化NPGは関数近似誤差までのエンフィナール収束を示すことを示す。
論文 参考訳（メタデータ） (2021-06-08T04:30:39Z) - Benign Overfitting of Constant-Stepsize SGD for Linear Regression [122.70478935214128]
帰納バイアスは 経験的に過剰フィットを防げる中心的存在です
この研究は、この問題を最も基本的な設定として考慮している: 線形回帰に対する定数ステップサイズ SGD。
我々は、(正規化されていない)SGDで得られるアルゴリズム正則化と、通常の最小二乗よりも多くの顕著な違いを反映する。
論文 参考訳（メタデータ） (2021-03-23T17:15:53Z) - Optimal oracle inequalities for solving projected fixed-point equations [53.31620399640334]
ヒルベルト空間の既知の低次元部分空間を探索することにより、確率観測の集合を用いて近似解を計算する手法を検討する。
本稿では,線形関数近似を用いた政策評価問題に対する時間差分学習手法の誤差を正確に評価する方法について述べる。
論文 参考訳（メタデータ） (2020-12-09T20:19:32Z) - Approximation Schemes for ReLU Regression [80.33702497406632]
我々はReLU回帰の根本的な問題を考察する。
目的は、未知の分布から引き出された2乗損失に対して、最も適したReLUを出力することである。
論文 参考訳（メタデータ） (2020-05-26T16:26:17Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。