論文の概要: Nearly Minimax Optimal Regret for Learning Infinite-horizon
Average-reward MDPs with Linear Function Approximation
- arxiv url: http://arxiv.org/abs/2102.07301v1
- Date: Mon, 15 Feb 2021 02:08:39 GMT
- ステータス: 処理完了
- システム内更新日: 2021-02-16 15:56:22.617188
- Title: Nearly Minimax Optimal Regret for Learning Infinite-horizon
Average-reward MDPs with Linear Function Approximation
- Title（参考訳）: 線形関数近似を用いた無限ホリゾン平均回帰mdp学習のための最短最適後悔
- Authors: Yue Wu and Dongruo Zhou and Quanquan Gu
- Abstract要約: 本論文では, 線形関数近似を用いた UCRL2 アルゴリズムの拡張として見ることのできる新しいアルゴリズム UCRL2-VTR を提案する。
Bernstein 型ボーナス付き UCRL2-VTR は $tildeO(dsqrtDT)$ の後悔を達成でき、$d$ は特徴写像の次元である。
また、一致した下界$tildeOmega(dsqrtDT)$を証明し、提案したUCRL2-VTRが対数係数の最小値であることを示す。
- 参考スコア（独自算出の注目度）: 95.80683238546499
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study reinforcement learning in an infinite-horizon average-reward setting
with linear function approximation, where the transition probability function
of the underlying Markov Decision Process (MDP) admits a linear form over a
feature mapping of the current state, action, and next state. We propose a new
algorithm UCRL2-VTR, which can be seen as an extension of the UCRL2 algorithm
with linear function approximation. We show that UCRL2-VTR with Bernstein-type
bonus can achieve a regret of $\tilde{O}(d\sqrt{DT})$, where $d$ is the
dimension of the feature mapping, $T$ is the horizon, and $\sqrt{D}$ is the
diameter of the MDP. We also prove a matching lower bound
$\tilde{\Omega}(d\sqrt{DT})$, which suggests that the proposed UCRL2-VTR is
minimax optimal up to logarithmic factors. To the best of our knowledge, our
algorithm is the first nearly minimax optimal RL algorithm with function
approximation in the infinite-horizon average-reward setting.
- Abstract（参考訳）: 本研究では,マルコフ決定過程(MDP)の遷移確率関数が,現在の状態,動作,次の状態の特徴写像上の線形形式を認める線形関数近似を用いた無限水平平均報酬設定による強化学習について検討する。
本論文では, 線形関数近似を用いた UCRL2 アルゴリズムの拡張として見ることのできる新しいアルゴリズム UCRL2-VTR を提案する。
ベルンシュタイン型ボーナスを持つ UCRL2-VTR は $\tilde{O}(d\sqrt{DT})$ の後悔を達成できることを示した。ここで $d$ は特徴写像の次元、$T$ は地平線、$\sqrt{D}$ は MDP の直径である。
提案された UCRL2-VTR が対数因子までの最小最大値であることを示唆する、マッチングする低い有界 $\tilde{\Omega}(d\sqrt{DT})$ も証明する。
我々の知る限りでは、我々のアルゴリズムは無限ホライゾン平均回帰設定で関数近似を持つ最初の最小最大最適rlアルゴリズムである。
関連論文リスト
- 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) - Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision
Processes [80.89852729380425]
そこで本研究では,最小限の最小残差である$tilde O(dsqrtH3K)$を計算効率よく実現したアルゴリズムを提案する。
我々の研究は線形 MDP を用いた最適 RL に対する完全な答えを提供する。
論文 参考訳（メタデータ） (2022-12-12T18:58:59Z) - 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 Reinforcement Learning for Linear Mixture Markov
Decision Processes [91.38793800392108]
本稿では,マルコフ決定過程(MDP)の遷移確率核が線形混合モデルである線形関数近似による強化学習について検討する。
上記の線形混合 MDP に対して$textUCRL-VTR+$ という線形関数近似を用いた計算効率の良い新しいアルゴリズムを提案する。
我々の知る限り、これらは線形関数近似を持つRLのための計算効率が良く、ほぼ最小のアルゴリズムである。
論文 参考訳（メタデータ） (2020-12-15T18:56:46Z) - Logarithmic Regret for Reinforcement Learning with Linear Function
Approximation [99.59319332864129]
最近提案された2つの線形MDP仮定で対数的後悔が達成可能であることを示す。
我々の知る限り、これらは線型関数近似を持つRLに対する最初の対数的後悔境界である。
論文 参考訳（メタデータ） (2020-11-23T17:25:00Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。