論文の概要: Horizon-Free Regret for Linear Markov Decision Processes

• arxiv url: http://arxiv.org/abs/2403.10738v1
• Date: Fri, 15 Mar 2024 23:50:58 GMT
• ステータス: 処理完了
• システム内更新日: 2024-03-19 22:04:53.145067
• Title: Horizon-Free Regret for Linear Markov Decision Processes
• Title（参考訳）: 線形マルコフ決定過程に対する水平自由回帰法
• Authors: Zihan Zhang, Jason D. Lee, Yuxin Chen, Simon S. Du,
• Abstract要約: 最近の一連の研究は、強化学習における残念な境界が(ほぼ)計画的地平から独立していることを示している。 我々は、人気のある線形マルコフ決定過程(MDP)設定に対して、最初の地平面自由境界を与える。 遷移モデルを明示的に推定し、不均一な値関数を計算する先行研究とは対照的に、直接値関数と信頼集合を推定する。
• 参考スコア（独自算出の注目度）: 92.02082223856479
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A recent line of works showed regret bounds in reinforcement learning (RL) can be (nearly) independent of planning horizon, a.k.a.~the horizon-free bounds. However, these regret bounds only apply to settings where a polynomial dependency on the size of transition model is allowed, such as tabular Markov Decision Process (MDP) and linear mixture MDP. We give the first horizon-free bound for the popular linear MDP setting where the size of the transition model can be exponentially large or even uncountable. In contrast to prior works which explicitly estimate the transition model and compute the inhomogeneous value functions at different time steps, we directly estimate the value functions and confidence sets. We obtain the horizon-free bound by: (1) maintaining multiple weighted least square estimators for the value functions; and (2) a structural lemma which shows the maximal total variation of the inhomogeneous value functions is bounded by a polynomial factor of the feature dimension.
• Abstract（参考訳）: 最近の一連の研究は、強化学習(RL)が(ほぼ)計画的地平線、すなわち地平線のない地平線から独立していることを示した。 しかしながら、これらの後悔の限界は、テーブル状マルコフ決定プロセス(MDP)や線形混合MDPのような遷移モデルのサイズに対する多項式依存が許容される設定にのみ適用される。 遷移モデルのサイズが指数関数的に大きくなり、あるいは非可算となるような、一般的な線形 MDP 設定に対して、最初の地平面自由境界を与える。 遷移モデルを明示的に推定し、異なる時間ステップで不均一な値関数を計算する先行研究とは対照的に、値関数と信頼セットを直接推定する。 1)値関数に対する多重重み付き最小二乗推定器の維持,(2)不均一値関数の最大総変動を示す構造的補題は特徴次元の多項式係数で有界である。

関連論文リスト

• Model-based RL as a Minimalist Approach to Horizon-Free and Second-Order Bounds [59.875550175217874]
  本稿では,オンラインとオフラインのRL設定において,モデルベース強化学習方式が強い後悔とサンプル境界を実現することを示す。 我々のアルゴリズムは単純で、かなり標準的であり、実際にRLの文献で広く研究されている。
  論文  参考訳（メタデータ） (2024-08-16T19:52:53Z)
• Double Duality: Variational Primal-Dual Policy Optimization for Constrained Reinforcement Learning [132.7040981721302]
  本研究では,訪問尺度の凸関数を最小化することを目的として,制約付き凸決定プロセス(MDP)について検討する。 制約付き凸MDPの設計アルゴリズムは、大きな状態空間を扱うなど、いくつかの課題に直面している。
  論文  参考訳（メタデータ） (2024-02-16T16:35:18Z)
• 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)
• Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processes [80.89852729380425]
  そこで本研究では,最小限の最小残差である$tilde O(dsqrtH3K)$を計算効率よく実現したアルゴリズムを提案する。 我々の研究は線形 MDP を用いた最適 RL に対する完全な答えを提供する。
  論文  参考訳（メタデータ） (2022-12-12T18:58:59Z)
• Provably Efficient Model-Free Constrained RL with Linear Function Approximation [4.060731229044571]
  我々は,大規模システムにおいても,サブリニア後悔とサブリニア制約違反を実現するための,最初のモデルフリーシミュレータフリーアルゴリズムを開発した。 本結果は,標準LSVI-UCBアルゴリズムの新たな適応により達成される。
  論文  参考訳（メタデータ） (2022-06-23T17:54:31Z)
• Deep Learning Approximation of Diffeomorphisms via Linear-Control Systems [91.3755431537592]
  我々は、制御に線形に依存する$dot x = sum_i=1lF_i(x)u_i$という形の制御系を考える。 対応するフローを用いて、コンパクトな点のアンサンブル上の微分同相写像の作用を近似する。
  論文  参考訳（メタデータ） (2021-10-24T08:57:46Z)
• Lifting the Convex Conjugate in Lagrangian Relaxations: A Tractable Approach for Continuous Markov Random Fields [53.31927549039624]
  断片的な離散化は既存の離散化問題と矛盾しないことを示す。 この理論を2つの画像のマッチング問題に適用する。
  論文  参考訳（メタデータ） (2021-07-13T12:31:06Z)
• Polynomial Time Reinforcement Learning in Correlated FMDPs with Linear Value Functions [25.621280373733605]
  因子マルコフ決定過程(FMDP)を用いた強化学習のための最初のアルゴリズムを提案する。 様々な要因の遷移が独立したものではないと仮定する。 従来の作業とは対照的に、さまざまな要因の遷移が独立したものであるとは考えません。
  論文  参考訳（メタデータ） (2021-07-12T04:13:18Z)
• Characterizing the SLOPE Trade-off: A Variational Perspective and the Donoho-Tanner Limit [29.344264789740894]
  sorted l1 regularizationは高次元統計的推定問題の解法として多くの方法に取り入れられている。 本手法は,FDP(False discovery proportion)と真正比( true positive proportion, TPP)の最適SLOPEトレードオフを特徴付けることにより,変数選択をいかに改善するかを示す。
  論文  参考訳（メタデータ） (2021-05-27T16:56:42Z)

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

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