論文の概要: Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPs

• arxiv url: http://arxiv.org/abs/2205.11507v1
• Date: Mon, 23 May 2022 17:59:18 GMT
• ステータス: 処理完了
• システム内更新日: 2022-05-24 16:31:25.945905
• Title: Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPs
• Title（参考訳）: 線形混合型MDPの高速水平強化学習
• Authors: Dongruo Zhou and Quanquan Gu
• Abstract要約: 線形混合MDPのための計算効率のよい初めての地平線フリーアルゴリズムを提案する。 我々のアルゴリズムは、未知の遷移力学に対する重み付き最小二乗推定器に適応する。 これにより、$sigma_k2$'sが知られているときに、この設定で最もよく知られたアルゴリズムも改善される。
• 参考スコア（独自算出の注目度）: 111.75736569611159
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Recent studies have shown that episodic reinforcement learning (RL) is not more difficult than contextual bandits, even with a long planning horizon and unknown state transitions. However, these results are limited to either tabular Markov decision processes (MDPs) or computationally inefficient algorithms for linear mixture MDPs. In this paper, we propose the first computationally efficient horizon-free algorithm for linear mixture MDPs, which achieves the optimal $\tilde O(d\sqrt{K} +d^2)$ regret up to logarithmic factors. Our algorithm adapts a weighted least square estimator for the unknown transitional dynamic, where the weight is both \emph{variance-aware} and \emph{uncertainty-aware}. When applying our weighted least square estimator to heterogeneous linear bandits, we can obtain an $\tilde O(d\sqrt{\sum_{k=1}^K \sigma_k^2} +d)$ regret in the first $K$ rounds, where $d$ is the dimension of the context and $\sigma_k^2$ is the variance of the reward in the $k$-th round. This also improves upon the best-known algorithms in this setting when $\sigma_k^2$'s are known.
• Abstract（参考訳）: 近年の研究では、長期計画の地平線と未知の状態遷移であっても、エピソード強化学習(RL)は文脈的帯域幅よりも困難ではないことが示されている。 しかし、これらの結果は表型マルコフ決定過程(MDP)または線形混合MDPの計算非効率アルゴリズムに限られる。 本稿では,線形混合mdpに対する最初の計算効率のよいホライズンフリーアルゴリズムを提案し,対数係数に対して最適な$\tilde o(d\sqrt{k} +d^2)$ を達成する。 我々のアルゴリズムは、未知の遷移力学に対する重み付き最小二乗推定器を採用し、重みは \emph{variance-aware} と \emph{uncertainty-aware} の両方である。 重み付き最小二乗推定器を不均質な線形バンドイットに適用すると、最初の$k$ラウンドにおいて$\tilde o(d\sqrt{\sum_{k=1}^k \sigma_k^2} +d)$の後悔を得ることができ、ここで$d$はコンテキストの次元であり$\sigma_k^2$は$k$-thラウンドにおける報酬の分散である。 これはまた、$\sigma_k^2$'sが知られているこの設定における最もよく知られたアルゴリズムも改善する。

関連論文リスト

• Upper and Lower Bounds for Distributionally Robust Off-Dynamics Reinforcement Learning [6.236688509180343]
  政策訓練と展開環境が異なるオフダイナミックス強化学習(RL)について検討する。 We-DRIVE-Uは,平均的最適値$widetildemathcalObig(d H cdot min 1/rho, H/sqrtK big)$を満足するアルゴリズムを提案する。 また、新しいハードインスタンスを構築し、この設定で最初の情報理論の下界を導出する。
  論文  参考訳（メタデータ） (2024-09-30T17:21:15Z)
• 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)
• Best-of-Both-Worlds Algorithms for Linear Contextual Bandits [11.94312915280916]
  両世界のベスト・オブ・ワールドズ・アルゴリズムを$K$武器付き線形文脈包帯に対して検討する。 我々のアルゴリズムは、敵対的体制と敵対的体制の両方において、ほぼ最適の後悔の限界を提供する。
  論文  参考訳（メタデータ） (2023-12-24T08:27:30Z)
• An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue Optimization Problems [76.2042837251496]
  相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。 注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。 本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
  論文  参考訳（メタデータ） (2023-06-30T08:34:29Z)
• Horizon-free Reinforcement Learning in Adversarial Linear Mixture MDPs [72.40181882916089]
  我々のアルゴリズムが $tildeObig((d+log (|mathcalS|2 |mathcalA|))sqrtKbig)$ regret with full-information feedback, where $d$ is the dimension of a known feature mapping is linearly parametrizing the unknown transition kernel of the MDP, $K$ is the number of episodes, $|mathcalS|$ and $|mathcalA|$ is the standardities of the state and action space。
  論文  参考訳（メタデータ） (2023-05-15T05:37:32Z)
• Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiency [90.40062452292091]
  本稿では,不整合雑音を持つ線形帯域に対する計算効率のよい最初のアルゴリズムを提案する。 我々のアルゴリズムは未知のノイズの分散に適応し、$tildeO(d sqrtsum_k = 1K sigma_k2 + d)$ regretを達成する。 また、強化学習において、線形混合マルコフ決定過程(MDP)に対する分散適応アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-02-21T00:17:24Z)
• Variance-Aware Confidence Set: Variance-Dependent Bound for Linear Bandits and Horizon-Free Bound for Linear Mixture MDP [76.94328400919836]
  線形バンドイットと線形混合決定プロセス(mdp)に対する分散認識信頼セットの構築方法を示す。 線形バンドイットに対しては、$d を特徴次元とする$widetildeo(mathrmpoly(d)sqrt1 + sum_i=1ksigma_i2) が成り立つ。 線形混合 MDP に対し、$widetildeO(mathrmpoly(d)sqrtK)$ regret bound を得る。
  論文  参考訳（メタデータ） (2021-01-29T18:57:52Z)
• 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)

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

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