論文の概要: Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity

• arxiv url: http://arxiv.org/abs/2002.07125v1
• Date: Mon, 17 Feb 2020 18:41:49 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-31 11:40:41.287235
• Title: Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity
• Title（参考訳）: 決定論的システムにおける関数近似を用いた非依存q-learning:近似誤差とサンプル複雑性の厳密な境界
• Authors: Simon S. Du, Jason D. Lee, Gaurav Mahajan, Ruosong Wang
• Abstract要約: 本稿では,決定論的システムにおける関数近似を用いたQ$学習の問題について検討する。 もし$delta = Oleft(rho/sqrtdim_Eright)$なら、$Oleft(dim_Eright)$を使って最適なポリシーを見つけることができる。
• 参考スコア（独自算出の注目度）: 94.37110094442136
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The current paper studies the problem of agnostic $Q$-learning with function approximation in deterministic systems where the optimal $Q$-function is approximable by a function in the class $\mathcal{F}$ with approximation error $\delta \ge 0$. We propose a novel recursion-based algorithm and show that if $\delta = O\left(\rho/\sqrt{\dim_E}\right)$, then one can find the optimal policy using $O\left(\dim_E\right)$ trajectories, where $\rho$ is the gap between the optimal $Q$-value of the best actions and that of the second-best actions and $\dim_E$ is the Eluder dimension of $\mathcal{F}$. Our result has two implications: 1) In conjunction with the lower bound in [Du et al., ICLR 2020], our upper bound suggests that the condition $\delta = \widetilde{\Theta}\left(\rho/\sqrt{\mathrm{dim}_E}\right)$ is necessary and sufficient for algorithms with polynomial sample complexity. 2) In conjunction with the lower bound in [Wen and Van Roy, NIPS 2013], our upper bound suggests that the sample complexity $\widetilde{\Theta}\left(\mathrm{dim}_E\right)$ is tight even in the agnostic setting. Therefore, we settle the open problem on agnostic $Q$-learning proposed in [Wen and Van Roy, NIPS 2013]. We further extend our algorithm to the stochastic reward setting and obtain similar results.
• Abstract（参考訳）: 本稿では, 最適q$-関数が近似誤差$\delta \ge 0$ を持つクラス$\mathcal{f}$ の関数によって近似される決定論的システムにおいて, 関数近似を伴う非依存な $q$-learning の問題を研究する。 我々は、新しい再帰に基づくアルゴリズムを提案し、もし$\delta = o\left(\rho/\sqrt{\dim_e}\right)$であれば、$o\left(\dim_e\right)$ trajectories を使って最適なポリシーを見つけることができることを示した。 1) [du et al., iclr 2020] の下限とともに、条件 $\delta = \widetilde{\theta}\left(\rho/\sqrt{\mathrm{dim}_e}\right)$ が多項式サンプル複雑性を持つアルゴリズムにとって必要かつ十分であることを示唆している。 2) [Wen and Van Roy, NIPS 2013] の下位境界と合わせて, 我々の上限は, サンプル複雑性 $\widetilde{\Theta}\left(\mathrm{dim}_E\right)$ が無知条件においてもきついことを示唆している。 そこで,本研究では,[Wen and Van Roy, NIPS 2013] で提案された非依存的な$Q$-learningに関するオープンな問題を解決した。 さらに,アルゴリズムを確率的報酬設定に拡張し,同様の結果を得る。

関連論文リスト

• Misspecified $Q$-Learning with Sparse Linear Function Approximation: Tight Bounds on Approximation Error [25.777423855881878]
  我々は、$Oleft(Hepsilonright)$-optimal Policyを得ることができることを示す新しい除去アルゴリズムを示す。 我々は上界を$widetildeOmegaleft(Hepsilonright)$-optimality lower boundで補い、この問題の完全な図面を与える。
  論文  参考訳（メタデータ） (2024-07-18T15:58:04Z)
• Comparisons Are All You Need for Optimizing Smooth Functions [12.097567715078252]
  微分自由法を用いてスムーズな関数を最適化するためには,エンファラリソンがすべて必要であることを示す。 さらに,サドル点をエスケープし,エプシロン$秒の定常点に到達するためのアルゴリズムも提供する。
  論文  参考訳（メタデータ） (2024-05-19T05:39:46Z)
• Nearly Horizon-Free Offline Reinforcement Learning [97.36751930393245]
  S$状態、$A$アクション、計画的地平$H$で、エピソードな時間同質なMarkov決定プロセスに関するオフライン強化学習を再考する。 経験的MDPを用いた評価と計画のための,約$H$自由なサンプル複雑性境界の最初の集合を得る。
  論文  参考訳（メタデータ） (2021-03-25T18:52:17Z)
• Infinite-Horizon Offline Reinforcement Learning with Linear Function Approximation: Curse of Dimensionality and Algorithm [46.36534144138337]
  本稿では,オフライン強化学習におけるポリシー評価のサンプル複雑さについて検討する。 低分布シフトの仮定の下では、最大$oleft(maxleft fracleftvert thetapirightvert _24varepsilon4logfracddelta,frac1varepsilon2left(d+logfrac1deltaright)right right)$サンプルを必要とするアルゴリズムがあることを示す。
  論文  参考訳（メタデータ） (2021-03-17T18:18:57Z)
• Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$ Geometry [69.24618367447101]
  対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。 損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
  論文  参考訳（メタデータ） (2021-03-02T06:53:44Z)
• Active Local Learning [22.823171570933397]
  クエリポイント$x$とラベルなしのトレーニングセット$S$へのアクティブアクセスを与えられた場合、H$でほぼ最適な$hの予測$h(x)$を出力します。 特にラベルクエリの数は$H$の複雑さとは無関係でなければならないし、関数$h$は$x$とは無関係に明確に定義されるべきである。 これはまた、すぐに距離推定のアルゴリズムを示唆している: ほぼ最適の$hを実際に学習するのに必要となる多くのラベルから$opt(H)$を推定する。
  論文  参考訳（メタデータ） (2020-08-31T05:39:35Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)
• $Q$-learning with Logarithmic Regret [60.24952657636464]
  楽観的な$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。
  論文  参考訳（メタデータ） (2020-06-16T13:01:33Z)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。 十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
  論文  参考訳（メタデータ） (2020-06-06T13:34:41Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。