論文の概要: Optimistic Policy Optimization is Provably Efficient in Non-stationary MDPs
- arxiv url: http://arxiv.org/abs/2110.08984v3
- Date: Mon, 23 Dec 2024 15:25:22 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-12-25 15:53:30.237436
- Title: Optimistic Policy Optimization is Provably Efficient in Non-stationary MDPs
- Title(参考訳): 非定常MDPにおける最適政策最適化の有効性
- Authors: Han Zhong, Zhongren Chen, Zhuoran Yang, Zhaoran Wang, Csaba Szepesvári,
- Abstract要約: 非定常線形カーネルマルコフ決定過程(MDP)におけるエピソード強化学習(RL)の研究
線形最適化アンダーライン最適化アルゴリズム(PROPO)を提案する。
PROPOはスライディングウィンドウベースのポリシー評価と周期的リスタートベースのポリシー改善の2つのメカニズムを特徴としている。
- 参考スコア(独自算出の注目度): 113.8752163061151
- License:
- Abstract: We study episodic reinforcement learning (RL) in non-stationary linear kernel Markov decision processes (MDPs). In this setting, both the reward function and the transition kernel are linear with respect to the given feature maps and are allowed to vary over time, as long as their respective parameter variations do not exceed certain variation budgets. We propose the \underline{p}eriodically \underline{r}estarted \underline{o}ptimistic \underline{p}olicy \underline{o}ptimization algorithm (PROPO), which is an optimistic policy optimization algorithm with linear function approximation. PROPO features two mechanisms: sliding-window-based policy evaluation and periodic-restart-based policy improvement, which are tailored for policy optimization in a non-stationary environment. In addition, only utilizing the technique of sliding window, we propose a value-iteration algorithm. We establish dynamic upper bounds for the proposed methods and a minimax lower bound which shows the (near-) optimality of the proposed methods. To our best knowledge, PROPO is the first provably efficient policy optimization algorithm that handles non-stationarity.
- Abstract(参考訳): 非定常線形カーネルマルコフ決定過程(MDP)におけるエピソード強化学習(RL)について検討した。
この設定では、報酬関数と遷移カーネルは、与えられた特徴写像に対して線形であり、それぞれのパラメータの変動が特定の変動予算を超えない限り、時間とともに変化することが許される。
本稿では,線形関数近似を用いた楽観的ポリシー最適化アルゴリズムである,<underline{p}eriodically \underline{r}estarted \underline{o}ptimistic \underline{p}olicy \underline{o}ptimization algorithm (PROPO)を提案する。
PROPOは、スライディングウインドウに基づく政策評価と周期的再起動に基づく政策改善の2つのメカニズムを特徴としている。
また,スライディングウインドウの手法を利用するだけで,値イテレーションアルゴリズムを提案する。
提案手法の動的上界と,提案手法の(ほぼ)最適性を示すミニマックス下界を確立する。
我々の知る限り、PROPOは非定常性を扱う最初の証明可能な効率的なポリシー最適化アルゴリズムである。
関連論文リスト
- Towards Efficient Exact Optimization of Language Model Alignment [93.39181634597877]
嗜好データから直接ポリシーを最適化するために、直接選好最適化(DPO)が提案された。
問題の最適解に基づいて導出されたDPOが,現実の最適解の妥協平均探索近似に繋がることを示す。
本稿では、アライメント目的の効率的な精度最適化(EXO)を提案する。
論文 参考訳(メタデータ) (2024-02-01T18:51:54Z) - Last-Iterate Convergent Policy Gradient Primal-Dual Methods for
Constrained MDPs [107.28031292946774]
無限水平割引マルコフ決定過程(拘束型MDP)の最適ポリシの計算問題について検討する。
我々は, 最適制約付きポリシーに反復的に対応し, 非漸近収束性を持つ2つの単一スケールポリシーに基づく原始双対アルゴリズムを開発した。
我々の知る限り、この研究は制約付きMDPにおける単一時間スケールアルゴリズムの非漸近的な最後の収束結果となる。
論文 参考訳(メタデータ) (2023-06-20T17:27:31Z) - Optimistic Natural Policy Gradient: a Simple Efficient Policy
Optimization Framework for Online RL [23.957148537567146]
本稿では,オンラインRLのための最適化NPGという,シンプルな効率的なポリシー最適化フレームワークを提案する。
$d$次元線形 MDP の場合、Optimistic NPG は計算効率が良く、$tildeO(d2/varepsilon3)$サンプル内で $varepsilon$-Optimal Policy を学ぶ。
論文 参考訳(メタデータ) (2023-05-18T15:19:26Z) - Policy Gradient Algorithms Implicitly Optimize by Continuation [7.351769270728942]
我々は、政策段階的なアルゴリズムの探索は、目の前にある政策の回帰の継続であり、その回帰を最大化するよりも、政策は歴史に依存しているべきだと論じる。
論文 参考訳(メタデータ) (2023-05-11T14:50:20Z) - Proximal Point Imitation Learning [48.50107891696562]
我々は、無限地平線模倣学習のための厳密な効率保証を備えた新しいアルゴリズムを開発した。
我々は、最適化、特に近点法(PPM)と双対平滑化から古典的ツールを活用する。
線形関数とニューラルネットワーク関数の近似の双方に対して、説得力のある経験的性能を実現する。
論文 参考訳(メタデータ) (2022-09-22T12:40:21Z) - Understanding the Effect of Stochasticity in Policy Optimization [86.7574122154668]
最適化手法の優位性は、正確な勾配が用いられるかどうかに大きく依存することを示す。
次に,政策最適化におけるコミット率の概念を紹介する。
第三に、外部のオラクル情報がない場合には、収束を加速するために幾何を利用することと、最適性をほぼ確実に達成することとの間に本質的にトレードオフがあることが示される。
論文 参考訳(メタデータ) (2021-10-29T06:35:44Z) - Near Optimal Policy Optimization via REPS [33.992374484681704]
emphrelative entropy policy search (reps) は多くのシミュレーションと実世界のロボットドメインでポリシー学習に成功した。
勾配に基づく解法を用いる場合、REPSの性能には保証がない。
最適規則化ポリシーに好適な収束を維持するためのパラメータ更新を計算するために,基礎となる決定プロセスへの表現的アクセスを利用する手法を提案する。
論文 参考訳(メタデータ) (2021-03-17T16:22:59Z) - Fast Global Convergence of Natural Policy Gradient Methods with Entropy
Regularization [44.24881971917951]
自然政策勾配法(NPG)は、最も広く使われている政策最適化アルゴリズムの一つである。
我々は,ソフトマックスパラメータ化の下で,エントロピー規則化NPG法に対する収束保証を開発する。
この結果から, エントロピー正則化の役割を浮き彫りにした。
論文 参考訳(メタデータ) (2020-07-13T17:58:41Z) - Proximal Gradient Algorithm with Momentum and Flexible Parameter Restart
for Nonconvex Optimization [73.38702974136102]
アルゴリズムの高速化のために,パラメータ再起動方式が提案されている。
本論文では,非滑らかな問題を解くアルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-02-26T16:06:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。