論文の概要: Logarithmic Regret for Reinforcement Learning with Linear Function
Approximation
- arxiv url: http://arxiv.org/abs/2011.11566v2
- Date: Thu, 18 Feb 2021 16:35:54 GMT
- ステータス: 処理完了
- システム内更新日: 2022-09-22 01:43:35.330014
- Title: Logarithmic Regret for Reinforcement Learning with Linear Function
Approximation
- Title（参考訳）: 線形関数近似を用いた強化学習に対する対数的後悔
- Authors: Jiafan He and Dongruo Zhou and Quanquan Gu
- Abstract要約: 最近提案された2つの線形MDP仮定で対数的後悔が達成可能であることを示す。
我々の知る限り、これらは線型関数近似を持つRLに対する最初の対数的後悔境界である。
- 参考スコア（独自算出の注目度）: 99.59319332864129
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Reinforcement learning (RL) with linear function approximation has received
increasing attention recently. However, existing work has focused on obtaining
$\sqrt{T}$-type regret bound, where $T$ is the number of interactions with the
MDP. In this paper, we show that logarithmic regret is attainable under two
recently proposed linear MDP assumptions provided that there exists a positive
sub-optimality gap for the optimal action-value function. More specifically,
under the linear MDP assumption (Jin et al. 2019), the LSVI-UCB algorithm can
achieve $\tilde{O}(d^{3}H^5/\text{gap}_{\text{min}}\cdot \log(T))$ regret; and
under the linear mixture MDP assumption (Ayoub et al. 2020), the UCRL-VTR
algorithm can achieve $\tilde{O}(d^{2}H^5/\text{gap}_{\text{min}}\cdot
\log^3(T))$ regret, where $d$ is the dimension of feature mapping, $H$ is the
length of episode, $\text{gap}_{\text{min}}$ is the minimal sub-optimality gap,
and $\tilde O$ hides all logarithmic terms except $\log(T)$. To the best of our
knowledge, these are the first logarithmic regret bounds for RL with linear
function approximation. We also establish gap-dependent lower bounds for the
two linear MDP models.
- Abstract（参考訳）: 近年,線形関数近似を用いた強化学習(RL)が注目されている。
しかし、既存の研究は、$\sqrt{T}$-type regret bound を得ることに集中しており、$T$ は MDP との相互作用の数である。
本稿では, 対数的後悔は, 最適作用値関数に正の準最適差があることを仮定して, 最近提案された2つの線形MDP仮定の下で達成可能であることを示す。
More specifically, under the linear MDP assumption (Jin et al. 2019), the LSVI-UCB algorithm can achieve $\tilde{O}(d^{3}H^5/\text{gap}_{\text{min}}\cdot \log(T))$ regret; and under the linear mixture MDP assumption (Ayoub et al. 2020), the UCRL-VTR algorithm can achieve $\tilde{O}(d^{2}H^5/\text{gap}_{\text{min}}\cdot \log^3(T))$ regret, where $d$ is the dimension of feature mapping, $H$ is the length of episode, $\text{gap}_{\text{min}}$ is the minimal sub-optimality gap, and $\tilde O$ hides all logarithmic terms except $\log(T)$.
我々の知る限り、これらは線型関数近似を持つRLに対する最初の対数的後悔境界である。
また, 2 つの線形 mdp モデルのギャップ依存下界を定式化する。
関連論文リスト
- Reinforcement Learning for Infinite-Horizon Average-Reward MDPs with Multinomial Logistic Function Approximation [3.675529589403533]
無限水平平均報酬設定のための2つのアルゴリズムを開発する。
ここでは、$tildemathcalO(d2/5 Mathrmsp(v*)T4/5)$に対して、$mathrmsp(v*)$は関連する最適バイアス関数のスパンである。
論文 参考訳（メタデータ） (2024-06-19T15:29:14Z) - Refined Regret for Adversarial MDPs with Linear Function Approximation [50.00022394876222]
我々は,損失関数が約1,300ドル以上のエピソードに対して任意に変化するような,敵対的決定過程(MDP)の学習を検討する。
本稿では,同じ設定で$tildemathcal O(K2/3)$に対する後悔を改善する2つのアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-01-30T14:37:21Z) - Nearly Minimax Optimal Reinforcement Learning with Linear Function
Approximation [25.60689712525918]
本稿では,遷移確率と報酬関数が線形な線形関数近似を用いた強化学習について検討する。
本稿では,新たなアルゴリズムLSVI-UCB$+$を提案し,$H$がエピソード長,$d$が特徴次元,$T$がステップ数である場合に,$widetildeO(HdsqrtT)$ regretboundを実現する。
論文 参考訳（メタデータ） (2022-06-23T06:04:21Z) - 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) - Near-optimal Representation Learning for Linear Bandits and Linear RL [41.33483293243257]
私たちはまず、次元が$d$の線形バンディットを同時に$M$で演奏する設定を考えます。
これらの包帯は、$k$-次元線型表現を共有するので、$kll d$ と $k ll M$ が成り立つ。
我々は、共有表現を利用して$tildeO(MsqrtdkT + dsqrtkMT )を後悔するサンプル効率のアルゴリズムMTLR-OFULを提案する。
論文 参考訳（メタデータ） (2021-02-08T11:11:53Z) - Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov
Decision Processes [91.38793800392108]
本稿では,マルコフ決定過程(MDP)の遷移確率核が線形混合モデルである線形関数近似による強化学習について検討する。
上記の線形混合 MDP に対して$textUCRL-VTR+$ という線形関数近似を用いた計算効率の良い新しいアルゴリズムを提案する。
我々の知る限り、これらは線形関数近似を持つRLのための計算効率が良く、ほぼ最小のアルゴリズムである。
論文 参考訳（メタデータ） (2020-12-15T18:56:46Z) - $Q$-learning with Logarithmic Regret [60.24952657636464]
楽観的な$Q$は$mathcalOleft(fracSAcdot mathrmpolyleft(Hright)Delta_minlogleft(SATright)right)$ cumulative regret bound, where $S$ is the number of state, $A$ is the number of action, $H$ is the planning horizon, $T$ is the total number of steps, $Delta_min$ is the least sub-Optitimality gap。
論文 参考訳（メタデータ） (2020-06-16T13:01:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。