論文の概要: Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal
Algorithm Escaping the Curse of Horizon
- arxiv url: http://arxiv.org/abs/2009.13503v2
- Date: Wed, 30 Jun 2021 07:06:10 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-13 21:15:27.781050
- Title: Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal
Algorithm Escaping the Curse of Horizon
- Title（参考訳）: 強化学習はバンドよりも困難か?
地平線の呪いを逃れる近似最適アルゴリズム
- Authors: Zihan Zhang, Xiangyang Ji, Simon S. Du
- Abstract要約: エピソード強化学習は文脈的包帯を一般化する。
長期計画の地平線と未知の状態依存的な遷移は、サンプルの複雑さに若干の困難をもたらす。
MVPは$left(sqrtSAK + S2Aright)$ regretを楽しみ、$Omegaleft(sqrtSAK + S2Aright)$ lower bound of emphcontextual bandits to logarithmic termsに近づいている。
- 参考スコア（独自算出の注目度）: 88.75843804630772
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Episodic reinforcement learning and contextual bandits are two widely studied
sequential decision-making problems. Episodic reinforcement learning
generalizes contextual bandits and is often perceived to be more difficult due
to long planning horizon and unknown state-dependent transitions. The current
paper shows that the long planning horizon and the unknown state-dependent
transitions (at most) pose little additional difficulty on sample complexity.
We consider the episodic reinforcement learning with $S$ states, $A$ actions,
planning horizon $H$, total reward bounded by $1$, and the agent plays for $K$
episodes. We propose a new algorithm, \textbf{M}onotonic \textbf{V}alue
\textbf{P}ropagation (MVP), which relies on a new Bernstein-type bonus.
Compared to existing bonus constructions, the new bonus is tighter since it is
based on a well-designed monotonic value function. In particular, the
\emph{constants} in the bonus should be subtly setting to ensure optimism and
monotonicity.
We show MVP enjoys an $O\left(\left(\sqrt{SAK} + S^2A\right) \poly\log
\left(SAHK\right)\right)$ regret, approaching the
$\Omega\left(\sqrt{SAK}\right)$ lower bound of \emph{contextual bandits} up to
logarithmic terms. Notably, this result 1) \emph{exponentially} improves the
state-of-the-art polynomial-time algorithms by Dann et al. [2019] and Zanette
et al. [2019] in terms of the dependency on $H$, and 2) \emph{exponentially}
improves the running time in [Wang et al. 2020] and significantly improves the
dependency on $S$, $A$ and $K$ in sample complexity.
- Abstract（参考訳）: エピソディック強化学習と文脈的バンディットは、一連の意思決定問題として広く研究されている。
エピソディック強化学習は、文脈的包帯を一般化し、長い計画の地平線と未知の状態依存の遷移のために、しばしば困難であるとみなされる。
現在の論文は、長い計画の地平線と未知の状態依存の遷移(多くは)が、サンプルの複雑さにわずかな困難をもたらすことを示している。
我々は、$S$状態、$A$アクション、プランニング水平線$H$、合計報酬$1$制限付き、エージェントが$K$エピソードをプレイする、という叙事的な強化学習について検討する。
我々は,新しいベルンシュタイン型ボーナスに依存する新しいアルゴリズム, \textbf{M}onotonic \textbf{V}alue \textbf{P}ropagation (MVP)を提案する。
既存のボーナス構造と比較すると、よく設計された単調値関数に基づいているため、新しいボーナスはより厳密である。
特に、ボーナスの \emph{constants} は、楽観性と単調性を保証するために微妙に設定されるべきである。
MVP は $O\left(\left(\sqrt{SAK} + S^2A\right) \poly\log \left(SAHK\right)\right)$ regret を楽しみ、$Omega\left(\sqrt{SAK}\right)$ lower bound of \emph{contextual bandits} を対数項に近づく。
特にこの結果は
1) \emph{exponentially}はdannらによる最先端多項式時間アルゴリズムを改善する。
Zanette et al. [2019] and Zanette et al.
[2019]$H$および$H$への依存性の観点で
2) \emph{exponentially}は[Wang et al. 2020]の実行時間を改善し、サンプル複雑性における$S$、$A$、$K$への依存性を大幅に改善します。
関連論文リスト
- Horizon-free Reinforcement Learning in Adversarial Linear Mixture MDPs [72.40181882916089]
我々のアルゴリズムが $tildeObig((d+log (|mathcalS|2 |mathcalA|))sqrtKbig)$ regret with full-information feedback, where $d$ is the dimension of a known feature mapping is linearly parametrizing the unknown transition kernel of the MDP, $K$ is the number of episodes, $|mathcalS|$ and $|mathcalA|$ is the standardities of the state and action space。
論文 参考訳（メタデータ） (2023-05-15T05:37:32Z) - Uncoupled Learning Dynamics with $O(\log T)$ Swap Regret in Multiplayer
Games [121.50979258049135]
我々は、すべてのプレイヤーが、時空不変の学習速度で我々のダイナミクスに従うとき、時間$T$までの時空二階パス長は、$O(log T)$で有界であることを示す。
提案する学習力学は, 直観的正規化学習と, 自己一致障壁を併用した新しい学習手法である。
論文 参考訳（メタデータ） (2022-04-25T03:20:16Z) - Horizon-Free Reinforcement Learning in Polynomial Time: the Power of
Stationary Policies [88.75843804630772]
我々は既存の境界に対して,$Oleft(mathrmpoly(S,A,log K)sqrtKright)を後悔するアルゴリズムを設計する。
この結果は、定常政策の近似力、安定性、および濃度特性を確立する新しい構造補題の列に依存している。
論文 参考訳（メタデータ） (2022-03-24T08:14:12Z) - Nearly Horizon-Free Offline Reinforcement Learning [97.36751930393245]
S$状態、$A$アクション、計画的地平$H$で、エピソードな時間同質なMarkov決定プロセスに関するオフライン強化学習を再考する。
経験的MDPを用いた評価と計画のための,約$H$自由なサンプル複雑性境界の最初の集合を得る。
論文 参考訳（メタデータ） (2021-03-25T18:52:17Z) - Nearly Minimax Optimal Reward-free Reinforcement Learning [88.75843804630772]
本稿では、特にバッチ強化学習に適した報酬不要強化学習フレームワークと、複数の報酬関数に対するポリシーを必要とするシナリオについて検討する。
textbfStaged textbfSampling + textbfTruncated textbfPlanning (algoname) という新しい効率的なアルゴリズムを提供しています。
論文 参考訳（メタデータ） (2020-10-12T17:51:19Z) - Improved Optimistic Algorithms for Logistic Bandits [16.140301473601454]
そこで本稿では,報酬関数の非線形性について,より詳細な検証に基づく新しい楽観的アルゴリズムを提案する。
我々は、$tildemathcalO(sqrtT)$ regretを楽しんでおり、$kappa$に依存しないが、第2の順序の項には依存しないことを示す。
論文 参考訳（メタデータ） (2020-02-18T12:52:32Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。