論文の概要: Minimax Optimal Q Learning with Nearest Neighbors

• arxiv url: http://arxiv.org/abs/2308.01490v2
• Date: Mon, 17 Jun 2024 05:41:41 GMT
• ステータス: 処理完了
• システム内更新日: 2024-06-19 12:40:28.099126
• Title: Minimax Optimal Q Learning with Nearest Neighbors
• Title（参考訳）: 最近近傍における最小Q学習
• Authors: Puning Zhao, Lifeng Lai,
• Abstract要約: オフライン設定用とオンライン設定用という,近接した2つの学習方法を提案する。 これら2つの手法のサンプル複雑度は、オフラインおよびオンラインメソッドそれぞれ$tildeO(frac1epsilond+2 (1-gamma)d+2)$と$tildeO(frac1epsilond+2 (1-gamma)d+3)$である。
• 参考スコア（独自算出の注目度）: 32.19733226959755
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Analyzing the Markov decision process (MDP) with continuous state spaces is generally challenging. A recent interesting work \cite{shah2018q} solves MDP with bounded continuous state space by a nearest neighbor $Q$ learning approach, which has a sample complexity of $\tilde{O}(\frac{1}{\epsilon^{d+3}(1-\gamma)^{d+7}})$ for $\epsilon$-accurate $Q$ function estimation with discount factor $\gamma$. In this paper, we propose two new nearest neighbor $Q$ learning methods, one for the offline setting and the other for the online setting. We show that the sample complexities of these two methods are $\tilde{O}(\frac{1}{\epsilon^{d+2}(1-\gamma)^{d+2}})$ and $\tilde{O}(\frac{1}{\epsilon^{d+2}(1-\gamma)^{d+3}})$ for offline and online methods respectively, which significantly improve over existing results and have minimax optimal dependence over $\epsilon$. We achieve such improvement by utilizing the samples more efficiently. In particular, the method in \cite{shah2018q} clears up all samples after each iteration, thus these samples are somewhat wasted. On the other hand, our offline method does not remove any samples, and our online method only removes samples with time earlier than $\beta t$ at time $t$ with $\beta$ being a tunable parameter, thus our methods significantly reduce the loss of information. Apart from the sample complexity, our methods also have additional advantages of better computational complexity, as well as suitability to unbounded state spaces.
• Abstract（参考訳）: マルコフ決定プロセス(MDP)を連続状態空間で解析することは一般的に困難である。 最近の興味深い研究 \cite{shah2018q} は、隣接する$Q$学習アプローチによって境界付き連続状態空間を持つ MDP を解き、サンプル複雑性は $\tilde{O}(\frac{1}{\epsilon^{d+3}(1-\gamma)^{d+7}})$ for $\epsilon$-accurate $Q$ function Estimation with discount factor $\gamma$ である。 本稿では,オフライン設定用とオンライン設定用という,近接した2つの学習方法を提案する。 これら2つの方法のサンプル複雑度は$\tilde{O}(\frac{1}{\epsilon^{d+2}(1-\gamma)^{d+2}})$と$\tilde{O}(\frac{1}{\epsilon^{d+2}(1-\gamma)^{d+3}})$である。 試料をより効率的に利用し, 改良を図っている。 特に、 \cite{shah2018q} のメソッドは反復後にすべてのサンプルをクリアするので、これらのサンプルは幾らか無駄になる。 一方、オフラインメソッドはサンプルを削除せず、オンラインメソッドは、$\beta t$ at time $t$と$\beta$が調整可能なパラメータである時間でのみ、サンプルを削除します。 サンプルの複雑さを別にすれば、我々の手法は計算の複雑さを向上し、非有界な状態空間に適しているという利点もある。

関連論文リスト

• 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)
• Truncated Variance Reduced Value Iteration [23.282578280033622]
  我々は、割引マルコフ決定プロセスにおいて、$epsilon$-optimal Policyを計算するための高速なランダム化アルゴリズムを提供する。 この結果から,モデルフリー法とモデルベース法とでは,サンプル・複雑さのギャップを埋めることができた。
  論文  参考訳（メタデータ） (2024-05-21T17:28:06Z)
• Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
  本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。 我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。 我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
  論文  参考訳（メタデータ） (2024-05-10T09:58:47Z)
• 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)
• Near Sample-Optimal Reduction-based Policy Learning for Average Reward MDP [58.13930707612128]
  この研究は、平均報酬マルコフ決定過程(AMDP)における$varepsilon$-Optimal Policyを得る際のサンプルの複雑さを考察する。 我々は、状態-作用対当たりの$widetilde O(H varepsilon-3 ln frac1delta)$サンプルを証明し、$H := sp(h*)$は任意の最適ポリシーのバイアスのスパンであり、$varepsilon$は精度、$delta$は失敗確率である。
  論文  参考訳（メタデータ） (2022-12-01T15:57:58Z)
• Reward-Mixing MDPs with a Few Latent Contexts are Learnable [75.17357040707347]
  報酬混合マルコフ決定過程(RMMDP)におけるエピソード強化学習の検討 我々のゴールは、そのようなモデルにおける時間段階の累積報酬をほぼ最大化する、ほぼ最適に近いポリシーを学ぶことである。
  論文  参考訳（メタデータ） (2022-10-05T22:52:00Z)
• Settling the Sample Complexity of Model-Based Offline Reinforcement Learning [50.5790774201146]
  オフライン強化学習(RL)は、事前収集されたデータを用いて、さらなる探索を行わずに学習する。 事前のアルゴリズムや分析は、最適なサンプルの複雑さに悩まされるか、サンプルの最適性に到達するために高いバーンインコストがかかるかのいずれかである。 モデルベース(あるいは"プラグイン")アプローチは,バーンインコストを伴わずに,最小限のサンプル複雑性を実現することを実証する。
  論文  参考訳（メタデータ） (2022-04-11T17:26:19Z)
• Nearly Horizon-Free Offline Reinforcement Learning [97.36751930393245]
  S$状態、$A$アクション、計画的地平$H$で、エピソードな時間同質なMarkov決定プロセスに関するオフライン強化学習を再考する。 経験的MDPを用いた評価と計画のための,約$H$自由なサンプル複雑性境界の最初の集合を得る。
  論文  参考訳（メタデータ） (2021-03-25T18:52:17Z)
• 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)

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

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