論文の概要: Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processes

• arxiv url: http://arxiv.org/abs/2212.06132v3
• Date: Sat, 4 Nov 2023 01:56:36 GMT
• ステータス: 処理完了
• システム内更新日: 2023-11-08 01:31:40.080749
• Title: Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processes
• Title（参考訳）: 線形マルコフ決定過程に対する最短最適強化学習
• Authors: Jiafan He and Heyang Zhao and Dongruo Zhou and Quanquan Gu
• Abstract要約: そこで本研究では,最小限の最小残差である$tilde O(dsqrtH3K)$を計算効率よく実現したアルゴリズムを提案する。 我々の研究は線形 MDP を用いた最適 RL に対する完全な答えを提供する。
• 参考スコア（独自算出の注目度）: 80.89852729380425
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study reinforcement learning (RL) with linear function approximation. For episodic time-inhomogeneous linear Markov decision processes (linear MDPs) whose transition probability can be parameterized as a linear function of a given feature mapping, we propose the first computationally efficient algorithm that achieves the nearly minimax optimal regret $\tilde O(d\sqrt{H^3K})$, where $d$ is the dimension of the feature mapping, $H$ is the planning horizon, and $K$ is the number of episodes. Our algorithm is based on a weighted linear regression scheme with a carefully designed weight, which depends on a new variance estimator that (1) directly estimates the variance of the optimal value function, (2) monotonically decreases with respect to the number of episodes to ensure a better estimation accuracy, and (3) uses a rare-switching policy to update the value function estimator to control the complexity of the estimated value function class. Our work provides a complete answer to optimal RL with linear MDPs, and the developed algorithm and theoretical tools may be of independent interest.
• Abstract（参考訳）: 線形関数近似による強化学習(rl)について検討した。 任意の特徴写像の線形関数として遷移確率をパラメータ化できるエピソドック時間不均質線形マルコフ決定過程(線形mdp)に対して、ほぼミニマックスの最適後悔である$\tilde o(d\sqrt{h^3k})$ を達成する最初の計算効率の高いアルゴリズムを提案し、ここで$d$ は特徴写像の次元、$h$ は計画の地平線、$k$ はエピソード数である。 本アルゴリズムは,(1)最適値関数の分散を直接推定し,(2)エピソード数に対して単調に減少して推定精度が向上し,(3)推定値関数クラスの複雑性を制御するために,値関数推定器の更新にレアスイッチングポリシを用いる新しい分散推定器に依存する,注意深く設計された重み付き線形回帰スキームに基づいている。 本研究は,線形mdpを用いた最適rlに対する完全な回答を提供するとともに,開発したアルゴリズムと理論的ツールが独立した興味を持つかもしれない。

関連論文リスト

• A Nearly Optimal and Low-Switching Algorithm for Reinforcement Learning with General Function Approximation [66.26739783789387]
  我々は、強化学習のための新しいアルゴリズム、MQL-UCBを用いたモノトニックQ-Learningを提案する。 MQL-UCBは、$tildeO(dsqrtHK)$の最小限の後悔を実現する。 本研究は,非線形関数近似を用いたサンプル効率およびデプロイメント効率のよいQ-ラーニングの設計に重点を置いている。
  論文  参考訳（メタデータ） (2023-11-26T08:31:57Z)
• Pessimistic Nonlinear Least-Squares Value Iteration for Offline Reinforcement Learning [53.97335841137496]
  非線形関数近似を用いたオフラインRLにおけるPNLSVI(Pessimistic Least-Square Value Iteration)と呼ばれるオラクル効率のアルゴリズムを提案する。 本アルゴリズムは,関数クラスの複雑性に強く依存する後悔境界を享受し,線形関数近似に特化して最小限のインスタンス依存後悔を実現する。
  論文  参考訳（メタデータ） (2023-10-02T17:42:01Z)
• VO$Q$L: Towards Optimal Regret in Model-free RL with Nonlinear Function Approximation [43.193807443491814]
  一般関数近似とスパース報酬による時間的不均一なエピソード強化学習(RL)について検討した。 我々は,Q$-learningをベースとした新しいアルゴリズム,Variance-weighted Optimistic $Q$-Learning (VO$Q$L) を設計し,その後悔次元を完全性に限定し,回帰関数クラスに対する有界エルダーを設計する。
  論文  参考訳（メタデータ） (2022-12-12T17:37:00Z)
• Human-in-the-loop: Provably Efficient Preference-based Reinforcement Learning with General Function Approximation [107.54516740713969]
  本研究は,RL(Human-in-the-loop reinforcement learning)を軌道的嗜好で検討する。 各ステップで数値的な報酬を受ける代わりに、エージェントは人間の監督者から軌道上のペアよりも優先される。 一般関数近似を用いたPbRLの楽観的モデルベースアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-05-23T09:03:24Z)
• Nearly Optimal Regret for Learning Adversarial MDPs with Linear Function Approximation [92.3161051419884]
  我々は、敵対的な報酬と完全な情報フィードバックで有限正方体エピソディックマルコフ決定プロセスのための強化学習を研究します。 我々は、$tildeO(dHsqrtT)$ regretを達成できることを示し、$H$はエピソードの長さである。 また、対数因子までの$tildeOmega(dHsqrtT)$の値が一致することを証明する。
  論文  参考訳（メタデータ） (2021-02-17T18:54:08Z)
• Nearly Minimax Optimal Regret for Learning Infinite-horizon Average-reward MDPs with Linear Function Approximation [95.80683238546499]
  本論文では, 線形関数近似を用いた UCRL2 アルゴリズムの拡張として見ることのできる新しいアルゴリズム UCRL2-VTR を提案する。 Bernstein 型ボーナス付き UCRL2-VTR は $tildeO(dsqrtDT)$ の後悔を達成でき、$d$ は特徴写像の次元である。 また、一致した下界$tildeOmega(dsqrtDT)$を証明し、提案したUCRL2-VTRが対数係数の最小値であることを示す。
  論文  参考訳（メタデータ） (2021-02-15T02:08:39Z)
• On Query-efficient Planning in MDPs under Linear Realizability of the Optimal State-value Function [14.205660708980988]
  固定水平マルコフ決定過程(MDP)における局所的計画の問題点を生成モデルを用いて考察する。 最近の下界は、最適ポリシーの作用値関数が線形に実現可能である場合の関連する問題は指数的なクエリ数を必要とすることを証明している。 本研究では,アクションセットが小さい場合,ポリ$(H, d)$学習が(状態値関数の実現可能性を持つ)可能であることを確かめる。
  論文  参考訳（メタデータ） (2021-02-03T13:23:15Z)

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

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