論文の概要: Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov
Decision Processes
- arxiv url: http://arxiv.org/abs/2012.08507v2
- Date: Thu, 7 Jan 2021 18:57:11 GMT
- ステータス: 処理完了
- システム内更新日: 2021-05-07 05:30:43.352573
- Title: Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov
Decision Processes
- Title（参考訳）: 線形混合マルコフ決定過程に対する最短最適強化学習
- Authors: Dongruo Zhou and Quanquan Gu and Csaba Szepesvari
- Abstract要約: 本稿では,マルコフ決定過程(MDP)の遷移確率核が線形混合モデルである線形関数近似による強化学習について検討する。
上記の線形混合 MDP に対して$textUCRL-VTR+$ という線形関数近似を用いた計算効率の良い新しいアルゴリズムを提案する。
我々の知る限り、これらは線形関数近似を持つRLのための計算効率が良く、ほぼ最小のアルゴリズムである。
- 参考スコア（独自算出の注目度）: 91.38793800392108
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study reinforcement learning (RL) with linear function approximation where
the underlying transition probability kernel of the Markov decision process
(MDP) is a linear mixture model (Jia et al., 2020; Ayoub et al., 2020; Zhou et
al., 2020) and the learning agent has access to either an integration or a
sampling oracle of the individual basis kernels. We propose a new
Bernstein-type concentration inequality for self-normalized martingales for
linear bandit problems with bounded noise. Based on the new inequality, we
propose a new, computationally efficient algorithm with linear function
approximation named $\text{UCRL-VTR}^{+}$ for the aforementioned linear mixture
MDPs in the episodic undiscounted setting. We show that $\text{UCRL-VTR}^{+}$
attains an $\tilde O(dH\sqrt{T})$ regret where $d$ is the dimension of feature
mapping, $H$ is the length of the episode and $T$ is the number of interactions
with the MDP. We also prove a matching lower bound $\Omega(dH\sqrt{T})$ for
this setting, which shows that $\text{UCRL-VTR}^{+}$ is minimax optimal up to
logarithmic factors. In addition, we propose the $\text{UCLK}^{+}$ algorithm
for the same family of MDPs under discounting and show that it attains an
$\tilde O(d\sqrt{T}/(1-\gamma)^{1.5})$ regret, where $\gamma\in [0,1)$ is the
discount factor. Our upper bound matches the lower bound
$\Omega(d\sqrt{T}/(1-\gamma)^{1.5})$ proved by Zhou et al. (2020) up to
logarithmic factors, suggesting that $\text{UCLK}^{+}$ is nearly minimax
optimal. To the best of our knowledge, these are the first computationally
efficient, nearly minimax optimal algorithms for RL with linear function
approximation.
- Abstract（参考訳）: 我々は,マルコフ決定過程(mdp)の根底となる遷移確率核が線形混合モデル(jia et al., 2020; ayoub et al., 2020; zhou et al., 2020)である線形関数近似による強化学習(rl)について検討し,学習エージェントが個々の基底核の統合あるいはサンプリング神託にアクセス可能であることを検証した。
有界雑音を伴う線形バンディット問題に対する自己正規化マーティンゲールに対するベルンシュタイン型濃度不等式を提案する。
この新しい不等式に基づき、エピソディックな未説明設定の線形混合mdpに対して $\text{ucrl-vtr}^{+}$ という線形関数近似を用いた計算効率の高い新しいアルゴリズムを提案する。
$\text{UCRL-VTR}^{+}$ は $\tilde O(dH\sqrt{T})$ regret となるが、$d$ は特徴写像の次元、$H$ はエピソードの長さ、$T$ は MDP との相互作用の数である。
この設定に対して、一致する下限の$\Omega(dH\sqrt{T})$を証明し、$\text{UCRL-VTR}^{+}$が対数因子まで最小値であることを示す。
さらに,同じmdp群に対して,割引下で$\text{uclk}^{+}$アルゴリズムを提案し,$\gamma\in [0,1)$がディスカウント係数である場合,$\tilde o(d\sqrt{t}/(1-\gamma)^{1.5})$ regret が得られることを示す。
我々の上界は、Zhouらによって証明された下界$\Omega(d\sqrt{T}/(1-\gamma)^{1.5})$と一致する。
(2020) 対数因子からすると、$\text{uclk}^{+}$ はほぼミニマックス最適である。
我々の知る限り、これらは線形関数近似を持つRLのための計算効率が良く、ほぼ最小のアルゴリズムである。
関連論文リスト
- 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) - Sharper Model-free Reinforcement Learning for Average-reward Markov
Decision Processes [21.77276136591518]
我々はマルコフ決定過程(MDPs)のための証明可能なモデルフリー強化学習(RL)アルゴリズムを開発した。
シミュレータ設定では,$widetildeO left(fracSAmathrmsp(h*)epsilon2+fracS2Amathrmsp(h*)epsilon2right)$サンプルを用いて,$epsilon$-optimal Policyを求める。
論文 参考訳（メタデータ） (2023-06-28T17:43:19Z) - Nearly Minimax Optimal Reinforcement Learning with Linear Function
Approximation [25.60689712525918]
本稿では,遷移確率と報酬関数が線形な線形関数近似を用いた強化学習について検討する。
本稿では,新たなアルゴリズムLSVI-UCB$+$を提案し,$H$がエピソード長,$d$が特徴次元,$T$がステップ数である場合に,$widetildeO(HdsqrtT)$ regretboundを実現する。
論文 参考訳（メタデータ） (2022-06-23T06:04:21Z) - Locally Differentially Private Reinforcement Learning for Linear Mixture
Markov Decision Processes [78.27542864367821]
強化学習(RL)アルゴリズムは、ユーザのプライベートで機密性の高いデータに依存するパーソナライズされたサービスを提供するために使用することができる。
ユーザのプライバシを保護するために、プライバシ保護RLアルゴリズムが要求されている。
線形混合MDPと呼ばれるマルコフ決定過程(MDP)のクラスを学習するための新しい$(varepsilon, delta)$-LDPアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-10-19T17:44:09Z) - 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) - Logarithmic Regret for Reinforcement Learning with Linear Function
Approximation [99.59319332864129]
最近提案された2つの線形MDP仮定で対数的後悔が達成可能であることを示す。
我々の知る限り、これらは線型関数近似を持つRLに対する最初の対数的後悔境界である。
論文 参考訳（メタデータ） (2020-11-23T17:25:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。