論文の概要: Nearly Minimax Optimal Reinforcement Learning with Linear Function Approximation

• arxiv url: http://arxiv.org/abs/2206.11489v1
• Date: Thu, 23 Jun 2022 06:04:21 GMT
• ステータス: 処理完了
• システム内更新日: 2022-06-24 14:18:35.860186
• Title: Nearly Minimax Optimal Reinforcement Learning with Linear Function Approximation
• Title（参考訳）: 線形関数近似を用いた最短最適強化学習
• Authors: Pihe Hu, Yu Chen, Longbo Huang
• Abstract要約: 本稿では,遷移確率と報酬関数が線形な線形関数近似を用いた強化学習について検討する。 本稿では,新たなアルゴリズムLSVI-UCB$+$を提案し,$H$がエピソード長,$d$が特徴次元,$T$がステップ数である場合に,$widetildeO(HdsqrtT)$ regretboundを実現する。
• 参考スコア（独自算出の注目度）: 25.60689712525918
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study reinforcement learning with linear function approximation where the transition probability and reward functions are linear with respect to a feature mapping $\boldsymbol{\phi}(s,a)$. Specifically, we consider the episodic inhomogeneous linear Markov Decision Process (MDP), and propose a novel computation-efficient algorithm, LSVI-UCB$^+$, which achieves an $\widetilde{O}(Hd\sqrt{T})$ regret bound where $H$ is the episode length, $d$ is the feature dimension, and $T$ is the number of steps. LSVI-UCB$^+$ builds on weighted ridge regression and upper confidence value iteration with a Bernstein-type exploration bonus. Our statistical results are obtained with novel analytical tools, including a new Bernstein self-normalized bound with conservatism on elliptical potentials, and refined analysis of the correction term. To the best of our knowledge, this is the first minimax optimal algorithm for linear MDPs up to logarithmic factors, which closes the $\sqrt{Hd}$ gap between the best known upper bound of $\widetilde{O}(\sqrt{H^3d^3T})$ in \cite{jin2020provably} and lower bound of $\Omega(Hd\sqrt{T})$ for linear MDPs.
• Abstract（参考訳）: 本稿では,遷移確率と報酬関数が線形となる線形関数近似を用いた強化学習について,特徴写像 $\boldsymbol{\phi}(s,a)$ について検討する。 具体的には、エピソード不均一な線形マルコフ決定過程(MDP)を検討し、新しい計算効率のアルゴリズムLSVI-UCB$^+$を提案し、$\widetilde{O}(Hd\sqrt{T})$ regret bound、$H$はエピソード長、$d$は特徴次元、$T$はステップ数である。 lsvi-ucb$^+$ は、重み付きリッジ回帰と、ベルンシュタイン型探索ボーナスによる高信頼値反復に基づいている。 本研究では,新しい解析ツールを用いて,楕円ポテンシャルの保存性を持つベルンシュタイン自己正規化バウンドと補正項の洗練された解析を行った。 我々の知る限り、これは線形 MDP に対する最初の極小極小アルゴリズムであり、これは線型 MDP に対して$\sqrt{Hd}$ の最もよく知られた上限である $\widetilde{O}(\sqrt{H^3d^3T})$ と $\Omega(Hd\sqrt{T})$ とのギャップを埋めるものである。

関連論文リスト

• Provably Efficient Infinite-Horizon Average-Reward Reinforcement Learning with Linear Function Approximation [1.8416014644193066]
  ベルマン最適条件下で線形マルコフ決定過程(MDP)と線形混合MDPを学習するアルゴリズムを提案する。 線形MDPに対する我々のアルゴリズムは、$widetildemathcalO(d3/2mathrmsp(v*)sqrtT)$ over $T$タイムステップの最もよく知られた後悔の上限を達成する。 線形混合 MDP に対して、我々のアルゴリズムは、$widetildemathcalO(dcdotmathrm) の後悔境界に達する。
  論文  参考訳（メタデータ） (2024-09-16T23:13:42Z)
• Improved Algorithm for Adversarial Linear Mixture MDPs with Bandit Feedback and Unknown Transition [71.33787410075577]
  線形関数近似,未知遷移,および逆損失を用いた強化学習について検討した。 我々は高い確率で$widetildeO(dsqrtHS3K + sqrtHSAK)$ regretを実現する新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-03-07T15:03:50Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• Randomized Exploration for Reinforcement Learning with General Value Function Approximation [122.70803181751135]
  本稿では,ランダム化最小二乗値反復(RLSVI)アルゴリズムに着想を得たモデルレス強化学習アルゴリズムを提案する。 提案アルゴリズムは,スカラーノイズを用いたトレーニングデータを簡易に摂動させることにより,探索を促進する。 我々はこの理論を、既知の困難な探査課題にまたがる実証的な評価で補完する。
  論文  参考訳（メタデータ） (2021-06-15T02:23:07Z)
• 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 Reinforcement Learning for Linear Mixture Markov Decision Processes [91.38793800392108]
  本稿では,マルコフ決定過程(MDP)の遷移確率核が線形混合モデルである線形関数近似による強化学習について検討する。 上記の線形混合 MDP に対して$textUCRL-VTR+$ という線形関数近似を用いた計算効率の良い新しいアルゴリズムを提案する。 我々の知る限り、これらは線形関数近似を持つRLのための計算効率が良く、ほぼ最小のアルゴリズムである。
  論文  参考訳（メタデータ） (2020-12-15T18:56:46Z)
• Logarithmic Regret for Reinforcement Learning with Linear Function Approximation [99.59319332864129]
  最近提案された2つの線形MDP仮定で対数的後悔が達成可能であることを示す。 我々の知る限り、これらは線型関数近似を持つRLに対する最初の対数的後悔境界である。
  論文  参考訳（メタデータ） (2020-11-23T17:25:00Z)

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

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