論文の概要: Minimax Optimal $Q$ Learning with Nearest Neighbors
- arxiv url: http://arxiv.org/abs/2308.01490v1
- Date: Thu, 3 Aug 2023 01:08:53 GMT
- ステータス: 処理完了
- システム内更新日: 2023-08-04 15:37:54.263634
- Title: Minimax Optimal $Q$ Learning with Nearest Neighbors
- Title(参考訳): minimax optimal $q$ learning with nearest neighbors (特集 ミニマックス)
- Authors: Puning Zhao, Lifeng Lai
- Abstract要約: 推定$Q$関数の収束率は$tildeO(T-1/(d+3))$であり、$tildeOmega(T-1/(d+2))$よりも遅い。
本稿では,収束率のギャップを埋める2つの新しいQ$学習法を提案し,そのうちの1つはオフラインで,もう1つはオンラインである。
- 参考スコア(独自算出の注目度): 56.29748742084386
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: $Q$ learning is a popular model free reinforcement learning method. Most of
existing works focus on analyzing $Q$ learning for finite state and action
spaces. If the state space is continuous, then the original $Q$ learning method
can not be directly used. A modification of the original $Q$ learning method
was proposed in (Shah and Xie, 2018), which estimates $Q$ values with nearest
neighbors. Such modification makes $Q$ learning suitable for continuous state
space. (Shah and Xie, 2018) shows that the convergence rate of estimated $Q$
function is $\tilde{O}(T^{-1/(d+3)})$, which is slower than the minimax lower
bound $\tilde{\Omega}(T^{-1/(d+2)})$, indicating that this method is not
efficient. This paper proposes two new $Q$ learning methods to bridge the gap
of convergence rates in (Shah and Xie, 2018), with one of them being offline,
while the other is online. Despite that we still use nearest neighbor approach
to estimate $Q$ function, the algorithms are crucially different from (Shah and
Xie, 2018). In particular, we replace the kernel nearest neighbor in
discretized region with a direct nearest neighbor approach. Consequently, our
approach significantly improves the convergence rate. Moreover, the time
complexity is also significantly improved in high dimensional state spaces. Our
analysis shows that both offline and online methods are minimax rate optimal.
- Abstract(参考訳): q$ learningは人気のあるモデルフリーの強化学習方法だ。
既存の作業の多くは、有限状態およびアクション空間に対する$Q$学習の分析に重点を置いている。
状態空間が連続であれば、元の$Q$学習メソッドを直接使用することはできない。
元の$q$学習法の修正が (shah and xie, 2018) で提案され、これは$q$の値が近辺の値と推定される。
このような修正により、連続状態空間に適した学習が$Q$になる。
(Shah and Xie, 2018) は、推定$Q$関数の収束速度が $\tilde{O}(T^{-1/(d+3)})$ であることを示し、これはミニマックス下界$\tilde{\Omega}(T^{-1/(d+2)})$ よりも遅く、この方法が効率的でないことを示している。
本稿では,収束率のギャップを埋める2つの新しいQ$学習法(Shah and Xie, 2018)を提案し,そのうちの1つはオフラインであり,もう1つはオンラインである。
Q$関数を推定するために、近傍のアプローチは依然として使われているが、アルゴリズムは(Shah and Xie, 2018)非常に異なる。
特に、離散化された領域におけるカーネル近傍のアプローチを、直接近接したアプローチで置き換える。
したがって,本手法は収束率を大幅に向上させる。
さらに、高次元状態空間においても時間複雑性が著しく改善される。
分析の結果,オフラインとオンラインの両方の手法が最適であることがわかった。
関連論文リスト
- Policy Gradient Optimal Correlation Search for Variance Reduction in
Monte Carlo simulation and Maximum Optimal Transport [0.0]
我々は、ある微分方程式の解として$f(X_T)$を推定し、$f$がテスト関数であるときに、分散還元のための新しいアルゴリズムを提案する。
新しい推定器は$(f(XT) + f(X2_T))/2$であり、ここでは$X1$と$X2$は$X2$と同じ限界法則を持つが、分散を減らすために経路的に相関している。
論文 参考訳(メタデータ) (2023-07-24T11:37:02Z) - 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-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) - TURF: A Two-factor, Universal, Robust, Fast Distribution Learning
Algorithm [64.13217062232874]
最も強力で成功したモダリティの1つは、全ての分布を$ell$距離に近似し、基本的に最も近い$t$-piece次数-$d_$の少なくとも1倍大きい。
本稿では,この数値をほぼ最適に推定する手法を提案する。
論文 参考訳(メタデータ) (2022-02-15T03:49:28Z) - Learning Stochastic Shortest Path with Linear Function Approximation [74.08819218747341]
線形関数近似を用いた強化学習における最短経路 (SSP) 問題について検討し, 遷移カーネルを未知モデルの線形混合として表現する。
本稿では,線形混合SSPを学習するための新しいアルゴリズムを提案し,このアルゴリズムにより,$tilde O(d B_star1.5sqrtK/c_min)$ regretを実現する。
論文 参考訳(メタデータ) (2021-10-25T08:34:00Z) - Saddle Point Optimization with Approximate Minimization Oracle [8.680676599607125]
サドル点最適化に対する主要なアプローチである$min_xmax_y f(x, y)$は、GAN(Generative Adversarial Network)によって一般化される勾配に基づくアプローチである。
対照的に、最小化問題を解くオラクルのみに依存する代替手法を解析する。
我々のアプローチでは、近似解 $x'$ と $y'$ to $min_x'f(x', y)$ を与えられた点 $(x, y)$ に配置し、これらの近似解 $(x', y)$ に更新する。
論文 参考訳(メタデータ) (2021-03-29T23:03:24Z) - $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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。