論文の概要: Learning Infinite-horizon Average-reward MDPs with Linear Function Approximation

• arxiv url: http://arxiv.org/abs/2007.11849v2
• Date: Mon, 26 Apr 2021 09:12:03 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-07 11:54:37.545256
• Title: Learning Infinite-horizon Average-reward MDPs with Linear Function Approximation
• Title（参考訳）: 線形関数近似を用いた無限水平平均回帰MDPの学習
• Authors: Chen-Yu Wei, Mehdi Jafarnia-Jahromi, Haipeng Luo, Rahul Jain
• Abstract要約: 線形関数近似を用いた無限水平平均逆設定でマルコフ決定過程を学習するための新しいアルゴリズムを開発した。 まず,最適$widetildeO(sqrtT)$ regretの計算非効率アルゴリズムを提案する。 次に,逆線形包帯から着想を得て,$widetildeO(sqrtT)$ regretのアルゴリズムを新たに開発した。
• 参考スコア（独自算出の注目度）: 44.374427255708135
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We develop several new algorithms for learning Markov Decision Processes in an infinite-horizon average-reward setting with linear function approximation. Using the optimism principle and assuming that the MDP has a linear structure, we first propose a computationally inefficient algorithm with optimal $\widetilde{O}(\sqrt{T})$ regret and another computationally efficient variant with $\widetilde{O}(T^{3/4})$ regret, where $T$ is the number of interactions. Next, taking inspiration from adversarial linear bandits, we develop yet another efficient algorithm with $\widetilde{O}(\sqrt{T})$ regret under a different set of assumptions, improving the best existing result by Hao et al. (2020) with $\widetilde{O}(T^{2/3})$ regret. Moreover, we draw a connection between this algorithm and the Natural Policy Gradient algorithm proposed by Kakade (2002), and show that our analysis improves the sample complexity bound recently given by Agarwal et al. (2020).
• Abstract（参考訳）: 線形関数近似を用いた無限水平平均逆設定でマルコフ決定過程を学習するための新しいアルゴリズムを開発した。 最適化原理を用いて、MDPが線形構造を持つことを仮定し、まず、最適な$\widetilde{O}(\sqrt{T})$ regretと$\widetilde{O}(T^{3/4})$ regretを持つ別の計算効率の良い変種を持つ計算非効率なアルゴリズムを提案し、そこで$T$は相互作用の数である。 次に、逆線型包帯からインスピレーションを得て、異なる仮定のセットの下で、$\widetilde{O}(\sqrt{T})$ regret を持つ別の効率的なアルゴリズムを開発し、$\widetilde{O}(T^{2/3})$ regret を用いて Hao et al. (2020) による最高の既存の結果を改善する。 さらに,本アルゴリズムとkakade (2002) が提案した自然政策勾配アルゴリズムとの関係を考察し,最近 agarwal et al. (2020) によって与えられたサンプル複雑性を解析により改善することを示した。

関連論文リスト

• Learning Infinite-Horizon Average-Reward Linear Mixture MDPs of Bounded Span [16.49229317664822]
  本稿では,無限水平平均逆線形混合マルコフ決定過程(MDPs)を学習するための計算抽出可能なアルゴリズムを提案する。 線形混合MDPのアルゴリズムは,$widetildemathcalO(dsqrtmathrmsp(v*)T)$$$T$以上の最小限の後悔上限を実現する。
  論文  参考訳（メタデータ） (2024-10-19T05:45:50Z)
• 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)
• Reinforcement Learning for Infinite-Horizon Average-Reward Linear MDPs via Approximation by Discounted-Reward MDPs [16.49229317664822]
  線形MDPを用いた無限水平平均逆強化学習について検討する。 本稿では,$widetildeO(sqrtT)$の後悔境界が,計算効率のよいアルゴリズムを実現することを提案する。
  論文  参考訳（メタデータ） (2024-05-23T20:58:33Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• Refined Regret for Adversarial MDPs with Linear Function Approximation [50.00022394876222]
  我々は,損失関数が約1,300ドル以上のエピソードに対して任意に変化するような,敵対的決定過程(MDP)の学習を検討する。 本稿では,同じ設定で$tildemathcal O(K2/3)$に対する後悔を改善する2つのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-01-30T14:37:21Z)
• 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 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)

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

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