論文の概要: Regularization and Variance-Weighted Regression Achieves Minimax
Optimality in Linear MDPs: Theory and Practice
- arxiv url: http://arxiv.org/abs/2305.13185v1
- Date: Mon, 22 May 2023 16:13:05 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-23 14:38:29.365738
- Title: Regularization and Variance-Weighted Regression Achieves Minimax
Optimality in Linear MDPs: Theory and Practice
- Title（参考訳）: 正則化と分散重み付け回帰は線形mdpにおける最小最適性を達成する:理論と実践
- Authors: Toshinori Kitamura, Tadashi Kozuno, Yunhao Tang, Nino Vieillard,
Michal Valko, Wenhao Yang, Jincheng Mei, Pierre M\'enard, Mohammad Gheshlaghi
Azar, R\'emi Munos, Olivier Pietquin, Matthieu Geist, Csaba Szepesv\'ari,
Wataru Kumagai, Yutaka Matsuo
- Abstract要約: ミラー降下値反復(MDVI)は、KL(Kulback-Leibler)とRL(Entropy-regularized reinforcement learning)の抽象化である。
MDVIを線形関数近似を用いて研究し,$varepsilon$-optimal policyを同定するために必要なサンプル複雑性について検討した。
我々は,無限水平線形MDPに対して,最小限のサンプル複雑性を実現する最初の理論的アルゴリズムである分散重み付き最小二乗法MDVIを提案する。
- 参考スコア（独自算出の注目度）: 79.48432795639403
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Mirror descent value iteration (MDVI), an abstraction of Kullback-Leibler
(KL) and entropy-regularized reinforcement learning (RL), has served as the
basis for recent high-performing practical RL algorithms. However, despite the
use of function approximation in practice, the theoretical understanding of
MDVI has been limited to tabular Markov decision processes (MDPs). We study
MDVI with linear function approximation through its sample complexity required
to identify an $\varepsilon$-optimal policy with probability $1-\delta$ under
the settings of an infinite-horizon linear MDP, generative model, and G-optimal
design. We demonstrate that least-squares regression weighted by the variance
of an estimated optimal value function of the next state is crucial to
achieving minimax optimality. Based on this observation, we present
Variance-Weighted Least-Squares MDVI (VWLS-MDVI), the first theoretical
algorithm that achieves nearly minimax optimal sample complexity for
infinite-horizon linear MDPs. Furthermore, we propose a practical VWLS
algorithm for value-based deep RL, Deep Variance Weighting (DVW). Our
experiments demonstrate that DVW improves the performance of popular
value-based deep RL algorithms on a set of MinAtar benchmarks.
- Abstract（参考訳）: Kullback-Leibler (KL) と entropy-regularized reinforcement learning (RL) の抽象化である Mirror descend value iteration (MDVI) は、近年の高性能実用的なRLアルゴリズムの基礎となっている。
しかし、実際には関数近似を用いているにもかかわらず、MDVIの理論的理解は表形式的マルコフ決定過程(MDP)に限られている。
無限水平線形MDP, 生成モデル, G-最適設計の条件の下で, MDVIを1-\delta$の確率で$\varepsilon$-optimal Policyを同定するために必要となる, サンプル複雑性による線形関数近似を用いて検討した。
推定された次状態の最適値関数の分散によって重み付けられた最小二乗回帰が極小最適性を達成するために重要であることを示す。
この観測に基づいて, 無限水平線形MDPに対して, ほぼ最小値のサンプル複雑性を実現する理論アルゴリズムとして, VWLS-MDVI (Variance-Weighted Least-Squares MDVI) を提案する。
さらに,価値に基づく深度RL(Deep Variance Weighting, DVW)のための実用的なVWLSアルゴリズムを提案する。
実験により,DVWは,一組のMinAtarベンチマークにおいて,一般的な値ベースディープRLアルゴリズムの性能を向上することを示した。
関連論文リスト
- Provably Efficient CVaR RL in Low-rank MDPs [58.58570425202862]
リスクに敏感な強化学習(RL)について検討する。
本稿では, CVaR RLにおける探索, 搾取, 表現学習の相互作用のバランスをとるための, 新たなアッパー信頼境界(UCB)ボーナス駆動アルゴリズムを提案する。
提案アルゴリズムは,各エピソードの長さが$H$,アクション空間が$A$,表現の次元が$d$であるような,エプシロン$最適CVaRのサンプル複雑性を実現する。
論文 参考訳（メタデータ） (2023-11-20T17:44:40Z) - Value-Biased Maximum Likelihood Estimation for Model-based Reinforcement
Learning in Discounted Linear MDPs [16.006893624836554]
本稿では,VBMLE (Value-Biased Maximum Likelihood Estimation) のレンズによる線形MDPの解法を提案する。
VBMLEは、各時間ステップで1つの最適化問題だけを解決する必要があるため、計算的により効率的である。
後悔する解析では、線形MDPにおけるMLEの一般収束結果が、新しいスーパーマーチンゲール構造を通して提供される。
論文 参考訳（メタデータ） (2023-10-17T18:27:27Z) - Provably Efficient Algorithm for Nonstationary Low-Rank MDPs [48.92657638730582]
我々は,非定常RLを,遷移カーネルと報酬の両方が時間とともに変化するような,エピソードな低ランクMDPで調査する最初の試みを行っている。
本稿では,パラメータ依存型ポリシ最適化アルゴリズムである Portal を提案し,パラメータフリー版である Ada-Portal の Portal をさらに改良する。
両アルゴリズムとも,非定常性が著しく大きくない限り, Portal と Ada-PortAL はサンプリング効率が良く,サンプリング複雑性を伴う平均的動的準最適ギャップを任意に小さく得ることを示す。
論文 参考訳（メタデータ） (2023-08-10T09:52:44Z) - Maximize to Explore: One Objective Function Fusing Estimation, Planning,
and Exploration [87.53543137162488]
我々はtextttMEX というオンライン強化学習(オンラインRL)フレームワークを提案する。
textttMEXは、自動的に探索エクスプロイトのバランスをとりながら、見積もりと計画コンポーネントを統合する。
様々な MuJoCo 環境では,ベースラインを安定的なマージンで上回り,十分な報酬を得られる。
論文 参考訳（メタデータ） (2023-05-29T17:25:26Z) - Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision
Processes [80.89852729380425]
そこで本研究では,最小限の最小残差である$tilde O(dsqrtH3K)$を計算効率よく実現したアルゴリズムを提案する。
我々の研究は線形 MDP を用いた最適 RL に対する完全な答えを提供する。
論文 参考訳（メタデータ） (2022-12-12T18:58:59Z) - Sparse high-dimensional linear regression with a partitioned empirical
Bayes ECM algorithm [62.997667081978825]
疎高次元線形回帰に対する計算効率が高く強力なベイズ的手法を提案する。
パラメータに関する最小の事前仮定は、プラグイン経験的ベイズ推定(英語版)を用いて用いられる。
提案手法はRパッケージプローブに実装されている。
論文 参考訳（メタデータ） (2022-09-16T19:15:50Z) - Nearly Minimax Optimal Offline Reinforcement Learning with Linear
Function Approximation: Single-Agent MDP and Markov Game [34.69723238900705]
オフライン強化学習(RL)は、環境とのさらなる相互作用を伴わずに、事前コンパイルされたデータセットを使用して最適な戦略を学ぶことを目的としている。
オフライン単一エージェントMDPと2プレーヤゼロサムマルコフゲーム(MG)のための2つの新しいアルゴリズムを提案する。
我々の知る限り、これらは線形関数近似を用いたオフライン単エージェントMDPとMGのための計算効率が良く、最小に近い最適化アルゴリズムである。
論文 参考訳（メタデータ） (2022-05-31T02:50:17Z) - KL-Entropy-Regularized RL with a Generative Model is Minimax Optimal [70.15267479220691]
モデル強化学習のサンプル複雑性を,生成的分散自由モデルを用いて検討・解析する。
我々の分析は、$varepsilon$が十分小さい場合、$varepsilon$-optimal Policyを見つけるのが、ほぼ最小の最適化であることを示している。
論文 参考訳（メタデータ） (2022-05-27T19:39:24Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。