論文の概要: Randomized Exploration is Near-Optimal for Tabular MDP
- arxiv url: http://arxiv.org/abs/2102.09703v1
- Date: Fri, 19 Feb 2021 01:42:50 GMT
- ステータス: 処理完了
- システム内更新日: 2021-02-22 13:25:09.368573
- Title: Randomized Exploration is Near-Optimal for Tabular MDP
- Title（参考訳）: ランダム化探索はタブラルMDPに最適に近い
- Authors: Zhihan Xiong, Ruoqi Shen, Simon S. Du
- Abstract要約: 強化学習におけるThompson Sampling(TS)ライクアルゴリズムにおけるランダム化値関数を用いた探索について検討する。
1)1つのランダムシードを各エピソードで使用し、2)ベルンシュタイン型のノイズの大きさを算出すると、最悪の$widetildeOleft(HsqrtSATright)$リコールがエピソード時間非均質決定プロセスにバインドされることを示します。
- 参考スコア（独自算出の注目度）: 45.16374124699648
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study exploration using randomized value functions in Thompson Sampling
(TS)-like algorithms in reinforcement learning. This type of algorithms enjoys
appealing empirical performance. We show that when we use 1) a single random
seed in each episode, and 2) a Bernstein-type magnitude of noise, we obtain a
worst-case $\widetilde{O}\left(H\sqrt{SAT}\right)$ regret bound for episodic
time-inhomogeneous Markov Decision Process where $S$ is the size of state
space, $A$ is the size of action space, $H$ is the planning horizon and $T$ is
the number of interactions. This bound polynomially improves all existing
bounds for TS-like algorithms based on randomized value functions, and for the
first time, matches the $\Omega\left(H\sqrt{SAT}\right)$ lower bound up to
logarithmic factors. Our result highlights that randomized exploration can be
near-optimal, which was previously only achieved by optimistic algorithms.
- Abstract（参考訳）: 強化学習におけるThompson Sampling(TS)ライクアルゴリズムにおけるランダム化値関数を用いた探索について検討する。
この種のアルゴリズムは、経験的なパフォーマンスをアピールする。
1)各エピソードで1つのランダムシードを使用するとき、2)ベルンシュタインタイプのノイズの大きさは、最悪の場合 $\widetilde{O}\left(H\sqrt{SAT}\right)$ を、$S$ が状態空間のサイズ、$A$ がアクションスペースの大きさ、$H$ が計画地平線、$T$ が相互作用の数である、典型的時間非均質マルコフ決定プロセスにバインドして得ることを示しています。
この有界多項式により、ランダム化された値関数に基づくTSライクアルゴリズムの既存のすべての境界が改善され、初めて $\Omega\left(H\sqrt{SAT}\right)$ が対数係数まで下がる。
その結果,ランダム化探索はほぼ最適であり,従来は楽観的なアルゴリズムによってのみ実現されていた。
関連論文リスト
- Achieving Tractable Minimax Optimal Regret in Average Reward MDPs [19.663336027878408]
我々は,$widetildemathrmO(sqrtmathrmsp(h*) S A T)$のミニマックス最適後悔を伴う最初の抽出可能なアルゴリズムを提案する。
注目すべきは、我々のアルゴリズムは$mathrmsp(h*)$に関する事前情報を必要としないことである。
論文 参考訳（メタデータ） (2024-06-03T11:53:44Z) - Randomized Exploration for Reinforcement Learning with Multinomial Logistic Function Approximation [8.274693573069442]
多項ロジスティック(MNL)関数近似を用いた強化学習について検討した。
頻繁な後悔の保証を有するランダムな探索を伴う確率的効率のアルゴリズムを提案する。
数値実験により提案アルゴリズムの優れた性能を示す。
論文 参考訳（メタデータ） (2024-05-30T15:39:19Z) - Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳（メタデータ） (2024-02-14T07:52:00Z) - Near-Optimal Bounds for Learning Gaussian Halfspaces with Random
Classification Noise [50.64137465792738]
この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。
我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
論文 参考訳（メタデータ） (2023-07-13T18:59:28Z) - 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 Optimal Policy Optimization with Stable at Any Time Guarantee [53.155554415415445]
citetshani 2020optimisticのポリシーベースのメソッドは、$tildeO(sqrtSAH3K + sqrtAH4K)$である。$S$は状態の数、$A$はアクションの数、$H$は地平線、$K$はエピソードの数、$sqrtSH$は情報理論の下限の$tildeOmega(sqrtSAH)と比べてギャップがある。
論文 参考訳（メタデータ） (2021-12-21T01:54:17Z) - Randomized Exploration for Reinforcement Learning with General Value
Function Approximation [122.70803181751135]
本稿では,ランダム化最小二乗値反復(RLSVI)アルゴリズムに着想を得たモデルレス強化学習アルゴリズムを提案する。
提案アルゴリズムは,スカラーノイズを用いたトレーニングデータを簡易に摂動させることにより,探索を促進する。
我々はこの理論を、既知の困難な探査課題にまたがる実証的な評価で補完する。
論文 参考訳（メタデータ） (2021-06-15T02:23:07Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。