論文の概要: Provably Efficient Reinforcement Learning with Linear Function
Approximation Under Adaptivity Constraints
- arxiv url: http://arxiv.org/abs/2101.02195v1
- Date: Wed, 6 Jan 2021 18:56:07 GMT
- ステータス: 処理完了
- システム内更新日: 2021-04-11 00:10:53.244106
- Title: Provably Efficient Reinforcement Learning with Linear Function
Approximation Under Adaptivity Constraints
- Title（参考訳）: 適応性制約下における線形関数近似による効率的強化学習
- Authors: Tianhao Wang and Dongruo Zhou and Quanquan Gu
- Abstract要約: 一般的な限定的適応モデルとして,バッチ学習モデルとレアポリシースイッチモデルがある。
提案したLSVI-UCB-Batchアルゴリズムは,$tilde O(sqrtd3H3T + dHT/B)$ regretを実現する。
まれなポリシスイッチモデルでは,提案されたLSVI-UCB-RareSwitchアルゴリズムは,$tilde O(sqrtd3H3T[1+T/(dH)]dH/B)$の後悔を享受する。
- 参考スコア（独自算出の注目度）: 94.76881135901753
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study reinforcement learning (RL) with linear function approximation under
the adaptivity constraint. We consider two popular limited adaptivity models:
batch learning model and rare policy switch model, and propose two efficient
online RL algorithms for linear Markov decision processes. In specific, for the
batch learning model, our proposed LSVI-UCB-Batch algorithm achieves an $\tilde
O(\sqrt{d^3H^3T} + dHT/B)$ regret, where $d$ is the dimension of the feature
mapping, $H$ is the episode length, $T$ is the number of interactions and $B$
is the number of batches. Our result suggests that it suffices to use only
$\sqrt{T/dH}$ batches to obtain $\tilde O(\sqrt{d^3H^3T})$ regret. For the rare
policy switch model, our proposed LSVI-UCB-RareSwitch algorithm enjoys an
$\tilde O(\sqrt{d^3H^3T[1+T/(dH)]^{dH/B}})$ regret, which implies that $dH\log
T$ policy switches suffice to obtain the $\tilde O(\sqrt{d^3H^3T})$ regret. Our
algorithms achieve the same regret as the LSVI-UCB algorithm (Jin et al.,
2019), yet with a substantially smaller amount of adaptivity.
- Abstract（参考訳）: 適応性制約の下で線形関数近似を用いた強化学習(RL)について検討した。
バッチ学習モデルとレアポリシースイッチモデルという2つの一般的な限定適応モデルを検討し,線形マルコフ決定プロセスに対する2つの効率的なオンラインrlアルゴリズムを提案する。
具体的には、バッチ学習モデルに対して、提案したLSVI-UCB-Batchアルゴリズムは、$\tilde O(\sqrt{d^3H^3T} + dHT/B)$ regret, where $d$ is the dimension of the feature mapping, $H$ is the episode length, $T$ is the number of interaction and $B$ is the number of batches。
その結果、$\sqrt{t/dh}$バッチのみを使用して$\tilde o(\sqrt{d^3h^3t})$ regretを得ることができた。
希少なポリシースイッチモデルでは、LSVI-UCB-RareSwitchアルゴリズムは、$\tilde O(\sqrt{d^3H^3T[1+T/(dH)]^{dH/B}})を後悔し、$dH\log T$ポリシースイッチは$\tilde O(\sqrt{d^3H^3T})を後悔する。
我々のアルゴリズムはLSVI-UCBアルゴリズム(Jin et al., 2019)と同じ残念な結果を得るが、適応性はかなり小さい。
関連論文リスト
- 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) - On the Interplay Between Misspecification and Sub-optimality Gap in
Linear Contextual Bandits [76.2262680277608]
本研究では,線形関数クラスによって期待される報酬関数を近似できるような,不特定条件下での線形文脈帯域について検討する。
このアルゴリズムは, 対数的因子に比例した設定において, ギャップ依存の残差が$tilde O (d2/Delta)$と同じであることを示す。
論文 参考訳（メタデータ） (2023-03-16T15:24:29Z) - Near-Optimal Regret Bounds for Multi-batch Reinforcement Learning [54.806166861456035]
本研究では,有限水平マルコフ決定過程(MDP)によってモデル化されたエピソディック強化学習(RL)問題をバッチ数に制約を加えて検討する。
我々は,$tildeO(sqrtSAH3Kln (1/delta))$tildeO(cdot)をほぼ最適に後悔するアルゴリズムを設計し,$(S,A,H,K)$の対数項を$K$で隠蔽する。
技術的貢献は2つある: 1) 探索のためのほぼ最適設計スキーム
論文 参考訳（メタデータ） (2022-10-15T09:22:22Z) - Nearly Minimax Optimal Reinforcement Learning with Linear Function
Approximation [25.60689712525918]
本稿では,遷移確率と報酬関数が線形な線形関数近似を用いた強化学習について検討する。
本稿では,新たなアルゴリズムLSVI-UCB$+$を提案し,$H$がエピソード長,$d$が特徴次元,$T$がステップ数である場合に,$widetildeO(HdsqrtT)$ regretboundを実現する。
論文 参考訳（メタデータ） (2022-06-23T06:04:21Z) - Randomized Exploration for Reinforcement Learning with General Value
Function Approximation [122.70803181751135]
本稿では,ランダム化最小二乗値反復(RLSVI)アルゴリズムに着想を得たモデルレス強化学習アルゴリズムを提案する。
提案アルゴリズムは,スカラーノイズを用いたトレーニングデータを簡易に摂動させることにより,探索を促進する。
我々はこの理論を、既知の困難な探査課題にまたがる実証的な評価で補完する。
論文 参考訳（メタデータ） (2021-06-15T02:23:07Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。