Fugu-MT 論文翻訳(概要): Provably Efficient Reinforcement Learning for Infinite-Horizon Average-Reward Linear MDPs

論文の概要: Provably Efficient Reinforcement Learning for Infinite-Horizon Average-Reward Linear MDPs

arxiv url: http://arxiv.org/abs/2405.15050v1
Date: Thu, 23 May 2024 20:58:33 GMT
ステータス: 処理完了
システム内更新日: 2024-05-27 19:07:30.299134
Title: Provably Efficient Reinforcement Learning for Infinite-Horizon Average-Reward Linear MDPs
Title（参考訳）: 無限水平平均逆線形MDPの確率的強化学習
Authors: Kihyuk Hong, Yufan Zhang, Ambuj Tewari,
Abstract要約: 我々は、$widetildeO(sqrtT)$ regret を用いて、無限水平平均逆線形マルコフ決定過程(MDP)に対する計算効率のよいアルゴリズムを設計するというオープンな問題を解決した。割引設定を学習するための楽観的な反復型アルゴリズムを実行すると、割引係数$gamma$が適切に調整された場合、$widetildeO(sqrtT)$ regretが得られることを示す。
参考スコア（独自算出の注目度）: 17.690503667311166
License: http://creativecommons.org/licenses/by/4.0/
Abstract: We resolve the open problem of designing a computationally efficient algorithm for infinite-horizon average-reward linear Markov Decision Processes (MDPs) with $\widetilde{O}(\sqrt{T})$ regret. Previous approaches with $\widetilde{O}(\sqrt{T})$ regret either suffer from computational inefficiency or require strong assumptions on dynamics, such as ergodicity. In this paper, we approximate the average-reward setting by the discounted setting and show that running an optimistic value iteration-based algorithm for learning the discounted setting achieves $\widetilde{O}(\sqrt{T})$ regret when the discounting factor $\gamma$ is tuned appropriately. The challenge in the approximation approach is to get a regret bound with a sharp dependency on the effective horizon $1 / (1 - \gamma)$. We use a computationally efficient clipping operator that constrains the span of the optimistic state value function estimate to achieve a sharp regret bound in terms of the effective horizon, which leads to $\widetilde{O}(\sqrt{T})$ regret.
Abstract（参考訳）: 無限水平平均逆線形マルコフ決定過程 (MDPs) に対する計算効率のよいアルゴリズムを設計するオープンな問題を$\widetilde{O}(\sqrt{T})$ regret で解決する。これまでの$\widetilde{O}(\sqrt{T})$ regretのアプローチは、計算の非効率性に悩まされるか、エルゴディディティのような力学の強い仮定を必要とする。本稿では、割引設定による平均回帰設定を近似し、割引設定を学習するための楽観的な値反復ベースのアルゴリズムの実行が、割引係数$\gamma$が適切に調整された場合に、後悔する$\widetilde{O}(\sqrt{T})を達成できることを示す。近似アプローチの課題は、効果的な地平線に鋭い依存を持つ後悔を1 / (1 - \gamma)$ とすることである。我々は、楽観的な状態値関数の推定値の範囲を制限する計算効率の良いクリッピング演算子を用いて、有効地平線の観点からシャープな後悔境界を達成し、$\widetilde{O}(\sqrt{T})$ regretとなる。

関連論文リスト

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)
Infinite-Horizon Reinforcement Learning with Multinomial Logistic Function Approximation [3.2703356989962518]
非線型関数近似を用いたモデルに基づく強化学習について検討する。本研究では,無限水平平均逆法と割引逆法の両方に有効である確率効率のよい値反復型アルゴリズムを開発した。
論文参考訳（メタデータ） (2024-06-19T15:29:14Z)
Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文参考訳（メタデータ） (2024-02-14T07:52:00Z)
Provably Efficient Reinforcement Learning via Surprise Bound [66.15308700413814]
本稿では,一般値関数近似を用いた効率の良い強化学習アルゴリズムを提案する。本アルゴリズムは, 線形設定と疎高次元線形設定の両方に適用した場合に, 合理的な後悔境界を達成できる。
論文参考訳（メタデータ） (2023-02-22T20:21:25Z)
Refined Regret for Adversarial MDPs with Linear Function Approximation [50.00022394876222]
我々は,損失関数が約1,300ドル以上のエピソードに対して任意に変化するような,敵対的決定過程(MDP)の学習を検討する。本稿では,同じ設定で$tildemathcal O(K2/3)$に対する後悔を改善する2つのアルゴリズムを提案する。
論文参考訳（メタデータ） (2023-01-30T14:37:21Z)
Learning Infinite-Horizon Average-Reward Markov Decision Processes with Constraints [39.715977181666766]
本研究では,無限水平平均回帰マルコフ決定過程(MDP)のコスト制約による後悔について検討する。我々のアルゴリズムはエルゴディックMDPに対して$widetildeO(sqrtT)$ regret and constant constraint violationを保証します。これらは、MDPをコスト制約で弱い通信を行うための最初の証明可能なアルゴリズムである。
論文参考訳（メタデータ） (2022-01-31T23:52:34Z)
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)
Learning Infinite-horizon Average-reward MDPs with Linear Function Approximation [44.374427255708135]
線形関数近似を用いた無限水平平均逆設定でマルコフ決定過程を学習するための新しいアルゴリズムを開発した。まず,最適$widetildeO(sqrtT)$ regretの計算非効率アルゴリズムを提案する。次に,逆線形包帯から着想を得て,$widetildeO(sqrtT)$ regretのアルゴリズムを新たに開発した。
論文参考訳（メタデータ） (2020-07-23T08:23:44Z)
Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mapping [99.59319332864129]
本稿では,割引決定(MDP)のための強化学習について検討する。本稿では,特徴写像を利用した新しいアルゴリズムを提案し,$tilde O(dsqrtT/ (1-gamma)2)$ regretを求める。以上の結果から,提案した強化学習アルゴリズムは,最大1-γ-0.5$の係数でほぼ最適であることが示唆された。
論文参考訳（メタデータ） (2020-06-23T17:08:54Z)

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

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