論文の概要: Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free
Reinforcement Learning
- arxiv url: http://arxiv.org/abs/2110.04645v1
- Date: Sat, 9 Oct 2021 21:13:48 GMT
- ステータス: 処理完了
- システム内更新日: 2021-10-12 16:42:43.041986
- Title: Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free
Reinforcement Learning
- Title（参考訳）: 適応型モデルフリー強化学習におけるサンプル複雑性障壁の破却
- Authors: Gen Li, Laixi Shi, Yuxin Chen, Yuantao Gu, Yuejie Chi
- Abstract要約: 漸進的強化学習における後悔を最小限に抑えるために,新しいモデルフリーアルゴリズムを提案する。
提案アルゴリズムは、2つのQ-ラーニングシーケンスの助けを借りて、初期設定された参照更新ルールを用いる。
初期の分散還元法の設計原理は、他のRL設定とは独立した関心を持つかもしれない。
- 参考スコア（独自算出の注目度）: 52.76230802067506
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Achieving sample efficiency in online episodic reinforcement learning (RL)
requires optimally balancing exploration and exploitation. When it comes to a
finite-horizon episodic Markov decision process with $S$ states, $A$ actions
and horizon length $H$, substantial progress has been achieved towards
characterizing the minimax-optimal regret, which scales on the order of
$\sqrt{H^2SAT}$ (modulo log factors) with $T$ the total number of samples.
While several competing solution paradigms have been proposed to minimize
regret, they are either memory-inefficient, or fall short of optimality unless
the sample size exceeds an enormous threshold (e.g., $S^6A^4
\,\mathrm{poly}(H)$ for existing model-free methods).
To overcome such a large sample size barrier to efficient RL, we design a
novel model-free algorithm, with space complexity $O(SAH)$, that achieves
near-optimal regret as soon as the sample size exceeds the order of
$SA\,\mathrm{poly}(H)$. In terms of this sample size requirement (also referred
to the initial burn-in cost),
our method improves -- by at least a factor of $S^5A^3$ -- upon any prior
memory-efficient algorithm that is asymptotically regret-optimal. Leveraging
the recently introduced variance reduction strategy (also called {\em
reference-advantage decomposition}), the proposed algorithm employs an {\em
early-settled} reference update rule, with the aid of two Q-learning sequences
with upper and lower confidence bounds. The design principle of our
early-settled variance reduction method might be of independent interest to
other RL settings that involve intricate exploration-exploitation trade-offs.
- Abstract（参考訳）: オンラインエピソジック強化学習(rl)におけるサンプル効率の達成には、探索と搾取の最適バランスが必要である。
s$ 状態、$a$ アクション、地平線の長さ $h$ を持つ有限ホリゾンのエピソディックマルコフ決定プロセスに関しては、サンプル総数 $t$ で$\sqrt{h^2sat}$ (modulo log factor) の順にスケールするminimax-optimal regret を特徴付けるためにかなりの進歩があった。
いくつかの競合する解パラダイムは後悔を最小限に抑えるために提案されているが、それらはメモリ非効率であるか、サンプルサイズが巨大なしきい値(例えば、既存のモデルフリーメソッドでは$S^6A^4 \,\mathrm{poly}(H)$)を超えない限り、最適性に欠ける。
このような大きなサンプルサイズ障壁を克服して効率的なRLを実現するために、サンプルサイズが$SA\,\mathrm{poly}(H)$を超えると、ほぼ最適に後悔する空間複雑性$O(SAH)$で新しいモデルフリーアルゴリズムを設計する。
このサンプルサイズ要件(初期バーンインコストとも呼ばれる)に関して、我々の手法は、漸近的に後悔と最適化される以前のメモリ効率アルゴリズムに対して、少なくとも$S^5A^3$の係数で改善する。
提案アルゴリズムは,最近導入された分散低減戦略(「vs-reference-advantage decomposition」とも呼ばれる)を活用し,上位と下位の信頼境界を持つ2つのQ-ラーニングシーケンスの助けを借りて,初期セットされた参照更新ルールを採用する。
初期の分散還元法の設計原理は、複雑な探査・探査のトレードオフを含む他のRL設定と独立して関心を持つかもしれない。
関連論文リスト
- Bridging Distributional and Risk-sensitive Reinforcement Learning with
Provable Regret Bounds [23.46659319363579]
2つの異なるスキームを通して楽観性を実装する2つの新しいDRLアルゴリズムを提案する。
どちらも$tildemathcalO(fracexp(|beta|H)-1|beta|HHsqrtHS2AT)$ regret upper bound, ここで$S$は状態の数である。
これは、DRLとRSRLを、サンプルの複雑さの観点から橋渡しするDRLを初めて後悔する分析である。
論文 参考訳（メタデータ） (2022-10-25T14:30:48Z) - Human-in-the-loop: Provably Efficient Preference-based Reinforcement
Learning with General Function Approximation [107.54516740713969]
本研究は,RL(Human-in-the-loop reinforcement learning)を軌道的嗜好で検討する。
各ステップで数値的な報酬を受ける代わりに、エージェントは人間の監督者から軌道上のペアよりも優先される。
一般関数近似を用いたPbRLの楽観的モデルベースアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-05-23T09:03:24Z) - Settling the Sample Complexity of Model-Based Offline Reinforcement
Learning [51.47633778534544]
オフライン強化学習(RL)は、事前収集されたデータを用いて、さらなる探索を行わずに学習する。
事前のアルゴリズムや分析は、最適なサンプルの複雑さに悩まされるか、サンプルの最適性に到達するために高いバーンインコストがかかるかのいずれかである。
モデルベース(あるいは"プラグイン")アプローチは,バーンインコストを伴わずに,最小限のサンプル複雑性を実現することを実証する。
論文 参考訳（メタデータ） (2022-04-11T17:26:19Z) - Reward-Free RL is No Harder Than Reward-Aware RL in Linear Markov
Decision Processes [61.11090361892306]
Reward-free reinforcement learning (RL) は、エージェントが探索中に報酬関数にアクセスできないような環境を考える。
この分離は線形MDPの設定には存在しないことを示す。
我々は$d$次元線形 MDP における報酬のない RL に対する計算効率の良いアルゴリズムを開発した。
論文 参考訳（メタデータ） (2022-01-26T22:09:59Z) - Is Plug-in Solver Sample-Efficient for Feature-based Reinforcement
Learning? [30.065091907118827]
本研究は,マルコフ決定過程(MDP)における$epsilon$-optimal Policyの発見の複雑さについて考察する。
実験モデルを構築し,任意のプラグインソルバを用いて実験モデルを計画するプラグインソルバ手法を用いてこの問題を解決する。
プラグインアプローチはサンプル効率も向上し,強化学習のためのモデルベースアルゴリズムを設計するための柔軟なアプローチを提供する。
論文 参考訳（メタデータ） (2020-10-12T13:13:01Z) - Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal
Sample Complexity [67.02490430380415]
モデルに基づくMARLは、Nash平衡値(NE)を求めるために$tilde O(|S||B|(gamma)-3epsilon-2)$のサンプル複雑性を実現する。
また、アルゴリズムが報酬に依存しない場合、そのようなサンプル境界は最小値(対数因子まで)であり、アルゴリズムは報酬知識のない遷移サンプルを問合せする。
論文 参考訳（メタデータ） (2020-07-15T03:25:24Z) - A Model-free Learning Algorithm for Infinite-horizon Average-reward MDPs
with Near-optimal Regret [44.374427255708135]
無限水平平均逆マルコフ決定過程(MDP)のモデルフリーアルゴリズムである探索強化Q-ラーニング(EE-QL)を提案する。
EE-QLは、最適平均報酬のオンライン集中近似が利用可能であると仮定する。
これは、エルゴード的な仮定なしに$O(sqrt T)$後悔を達成する最初のモデル自由学習アルゴリズムであり、対数的因子を除いて、下位境界の$T$と一致する。
論文 参考訳（メタデータ） (2020-06-08T05:09:32Z) - Breaking the Sample Size Barrier in Model-Based Reinforcement Learning
with a Generative Model [50.38446482252857]
本稿では、生成モデル(シミュレータ)へのアクセスを想定して、強化学習のサンプル効率について検討する。
最初に$gamma$-discounted infinite-horizon Markov decision process (MDPs) with state space $mathcalS$ and action space $mathcalA$を考える。
対象の精度を考慮すれば,モデルに基づく計画アルゴリズムが最小限のサンプルの複雑さを実現するのに十分であることを示す。
論文 参考訳（メタデータ） (2020-05-26T17:53:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。