論文の概要: $Q$-learning with Logarithmic Regret
- arxiv url: http://arxiv.org/abs/2006.09118v2
- Date: Tue, 23 Feb 2021 11:44:44 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-20 20:13:37.575294
- Title: $Q$-learning with Logarithmic Regret
- Title（参考訳）: 対数的後悔を伴うq$-learning
- Authors: Kunhe Yang, Lin F. Yang, Simon S. Du
- Abstract要約: 楽観的な$Q$は$mathcalOleft(fracSAcdot mathrmpolyleft(Hright)Delta_minlogleft(SATright)right)$ cumulative regret bound, where $S$ is the number of state, $A$ is the number of action, $H$ is the planning horizon, $T$ is the total number of steps, $Delta_min$ is the least sub-Optitimality gap。
- 参考スコア（独自算出の注目度）: 60.24952657636464
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper presents the first non-asymptotic result showing that a model-free
algorithm can achieve a logarithmic cumulative regret for episodic tabular
reinforcement learning if there exists a strictly positive sub-optimality gap
in the optimal $Q$-function. We prove that the optimistic $Q$-learning studied
in [Jin et al. 2018] enjoys a ${\mathcal{O}}\left(\frac{SA\cdot
\mathrm{poly}\left(H\right)}{\Delta_{\min}}\log\left(SAT\right)\right)$
cumulative regret bound, where $S$ is the number of states, $A$ is the number
of actions, $H$ is the planning horizon, $T$ is the total number of steps, and
$\Delta_{\min}$ is the minimum sub-optimality gap. This bound matches the
information theoretical lower bound in terms of $S,A,T$ up to a
$\log\left(SA\right)$ factor. We further extend our analysis to the discounted
setting and obtain a similar logarithmic cumulative regret bound.
- Abstract（参考訳）: 本稿では,モデルのないアルゴリズムが,最適$Q$関数に正の正の準最適差がある場合,表層表層強化学習における対数的累積後悔を達成できることを示す最初の非漸近的結果を示す。
jin et al. 2018] で研究された楽観的な $q$-learning は${\mathcal{o}}\left(\frac{sa\cdot \mathrm{poly}\left(h\right)}{\delta_{\min}}\log\left(sat\right)\right)$ cumulative regretbound であり、ここで$s$ は州の数、$a$ はアクションの数、$h$ は計画の地平線、$t$ はステップの総数、$\delta_{\min}$ は最小のサブ最適化ギャップである。
この境界は、$s,a,t$ から $\log\left(sa\right)$ factor までの情報理論的下限に一致する。
さらに,本分析を割引設定に拡張し,同様の対数累積後悔値を求める。
関連論文リスト
- 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) - Optimal SQ Lower Bounds for Learning Halfspaces with Massart Noise [9.378684220920562]
マスアートノイズの存在下でハーフスペースを学習するための、最も厳密な統計クエリ(SQ)の下界。
任意の $eta in [0,1/2]$ に対して、$eta$ よりも誤り分類誤差の少ない全ての SQ アルゴリズムは、スーパーポリノミカルな精度のクエリを必要とすることを示す。
論文 参考訳（メタデータ） (2022-01-24T17:33:19Z) - Improved No-Regret Algorithms for Stochastic Shortest Path with Linear
MDP [31.62899359543925]
線形MDPを用いた最短経路問題(SSP)に対する2つの新しい非回帰アルゴリズムを提案する。
我々の最初のアルゴリズムは計算効率が高く、後悔すべき$widetildeOleft(sqrtd3B_star2T_star Kright)$を達成している。
第2のアルゴリズムは計算的に非効率であるが、$T_starに依存しない$widetildeO(d3.5B_starsqrtK)$の最初の「水平な」後悔を実現する。
論文 参考訳（メタデータ） (2021-12-18T06:47:31Z) - Logarithmic Regret from Sublinear Hints [76.87432703516942]
自然クエリモデルにより,アルゴリズムが$O(log T)$ regretsを$O(sqrtT)$ hintsで得ることを示す。
また、$o(sqrtT)$ hintsは$Omega(sqrtT)$ regretより保証できないことも示しています。
論文 参考訳（メタデータ） (2021-11-09T16:50:18Z) - Nearly Horizon-Free Offline Reinforcement Learning [97.36751930393245]
S$状態、$A$アクション、計画的地平$H$で、エピソードな時間同質なMarkov決定プロセスに関するオフライン強化学習を再考する。
経験的MDPを用いた評価と計画のための,約$H$自由なサンプル複雑性境界の最初の集合を得る。
論文 参考訳（メタデータ） (2021-03-25T18:52:17Z) - Logarithmic Regret for Reinforcement Learning with Linear Function
Approximation [99.59319332864129]
最近提案された2つの線形MDP仮定で対数的後悔が達成可能であることを示す。
我々の知る限り、これらは線型関数近似を持つRLに対する最初の対数的後悔境界である。
論文 参考訳（メタデータ） (2020-11-23T17:25:00Z) - Agnostic Q-learning with Function Approximation in Deterministic
Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
本稿では,決定論的システムにおける関数近似を用いたQ$学習の問題について検討する。
もし$delta = Oleft(rho/sqrtdim_Eright)$なら、$Oleft(dim_Eright)$を使って最適なポリシーを見つけることができる。
論文 参考訳（メタデータ） (2020-02-17T18:41:49Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。