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となる。

関連論文リスト

Achieving Tractable Minimax Optimal Regret in Average Reward MDPs [19.663336027878408]
我々は,$widetildemathrmO(sqrtmathrmsp(h*) S A T)$のミニマックス最適後悔を伴う最初の抽出可能なアルゴリズムを提案する。注目すべきは、我々のアルゴリズムは$mathrmsp(h*)$に関する事前情報を必要としないことである。
論文参考訳（メタデータ） (2024-06-03T11:53:44Z)
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)
Efficient Learning in Non-Stationary Linear Markov Decision Processes [17.296084954104415]
非定常線形(低ランク)マルコフ決定過程(MDP)におけるエピソード強化学習の研究 OPT-WLSVI は最小二乗の重み付け値に基づく楽観的なモデルフリーのアルゴリズムであり、指数重み付けを用いて過去のデータをスムーズに忘れる。我々のアルゴリズムは、各時点で最高のポリシーと競合するときに、$d$$$widetildemathcalO(d5/4H2 Delta1/4 K3/4)$で上限付けられた後悔を実現する。
論文参考訳（メタデータ） (2020-10-24T11:02:45Z)
Learning Infinite-horizon Average-reward MDPs with Linear Function Approximation [44.374427255708135]
線形関数近似を用いた無限水平平均逆設定でマルコフ決定過程を学習するための新しいアルゴリズムを開発した。まず,最適$widetildeO(sqrtT)$ regretの計算非効率アルゴリズムを提案する。次に,逆線形包帯から着想を得て,$widetildeO(sqrtT)$ regretのアルゴリズムを新たに開発した。
論文参考訳（メタデータ） (2020-07-23T08:23:44Z)
Efficient Optimistic Exploration in Linear-Quadratic Regulators via Lagrangian Relaxation [107.06364966905821]
線形2次レギュレータ(LQR)設定における探索・探索ジレンマについて検討した。有限 MDP に対する楽観的アルゴリズムで用いられる拡張値反復アルゴリズムに着想を得て,Oulq の楽観的最適化を緩和することを提案する。我々は、少なくとも$Obig(log (1/epsilon)big)$ Riccati方程式を解くことで、$epsilon$-OptimisticControllerを効率的に計算できることを示した。
論文参考訳（メタデータ） (2020-07-13T16:30:47Z)

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

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