論文の概要: Variance-Reduced Cascade Q-learning: Algorithms and Sample Complexity

• arxiv url: http://arxiv.org/abs/2408.06544v1
• Date: Tue, 13 Aug 2024 00:34:33 GMT
• ステータス: 処理完了
• システム内更新日: 2024-08-14 18:56:02.678290
• Title: Variance-Reduced Cascade Q-learning: Algorithms and Sample Complexity
• Title（参考訳）: 可変再生カスケードQ-ラーニング:アルゴリズムとサンプル複雑度
• Authors: Mohammad Boveiri, Peyman Mohajerin Esfahani,
• Abstract要約: Variance-Reduced Cascade Q-learning (VRCQ)と呼ばれる新しいモデルなしアルゴリズムを導入し分析する。 VRCQは、既存のモデルフリー近似型アルゴリズムと比較して、$ell_infty$-normにおいて優れた保証を提供する。
• 参考スコア（独自算出の注目度）: 3.4376560669160394
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the problem of estimating the optimal Q-function of $\gamma$-discounted Markov decision processes (MDPs) under the synchronous setting, where independent samples for all state-action pairs are drawn from a generative model at each iteration. We introduce and analyze a novel model-free algorithm called Variance-Reduced Cascade Q-learning (VRCQ). VRCQ comprises two key building blocks: (i) the established direct variance reduction technique and (ii) our proposed variance reduction scheme, Cascade Q-learning. By leveraging these techniques, VRCQ provides superior guarantees in the $\ell_\infty$-norm compared with the existing model-free stochastic approximation-type algorithms. Specifically, we demonstrate that VRCQ is minimax optimal. Additionally, when the action set is a singleton (so that the Q-learning problem reduces to policy evaluation), it achieves non-asymptotic instance optimality while requiring the minimum number of samples theoretically possible. Our theoretical results and their practical implications are supported by numerical experiments.
• Abstract（参考訳）: 同期条件下での$\gamma$-discounted Markov決定過程(MDP)の最適Q-関数を推定する問題について検討する。 本稿では,Variance-Reduced Cascade Q-learning (VRCQ)と呼ばれる新しいモデルフリーアルゴリズムを導入,解析する。 VRCQは2つの重要なビルディングブロックから構成される。 一 確立された直接分散低減技術及び方法 (II)カスケードQ-ラーニング法を提案する。 これらの手法を活用することで、VRCQは既存のモデル自由確率近似型アルゴリズムと比較して$\ell_\infty$-normにおいて優れた保証を提供する。 具体的には,VRCQがミニマックス最適であることを示す。 さらに、アクション集合がシングルトンである場合(Q-ラーニング問題はポリシー評価に還元される)、理論上可能な最小のサンプル数を必要としながら、漸近的でないインスタンス最適性を達成する。 我々の理論的結果とその実践的意味は数値実験によって支えられている。

関連論文リスト

• Q-learning for Quantile MDPs: A Decomposition, Performance, and Convergence Analysis [30.713243690224207]
  マルコフ決定過程(MDPs)において、バリュー・アット・リスク(Value-at-Risk)のような量子リスク尺度は、特定の結果に対するRLエージェントの嗜好をモデル化するための標準指標である。 本稿では,強い収束と性能保証を有するMDPにおける量子化最適化のための新しいQ-ラーニングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-10-31T16:53:20Z)
• Two-Step Q-Learning [0.0]
  そこで本研究では,重要でない2段階のQ-ラーニングアルゴリズムを提案する。 数値実験により、2段階のQ-ラーニングとそのスムーズな変形の優れた性能が示された。
  論文  参考訳（メタデータ） (2024-07-02T15:39:00Z)
• Multi-Timescale Ensemble Q-learning for Markov Decision Process Policy Optimization [21.30645601474163]
  元々のQ-ラーニングは、非常に大きなネットワークにわたるパフォーマンスと複雑性の課題に悩まされている。 従来のQ-ラーニングに適応したモデルフリーアンサンブル強化学習アルゴリズムを提案する。 計算結果から,提案アルゴリズムは平均ポリシエラーを最大55%,実行時複雑性を最大50%削減できることがわかった。
  論文  参考訳（メタデータ） (2024-02-08T08:08:23Z)
• Improving Sample Efficiency of Model-Free Algorithms for Zero-Sum Markov Games [66.2085181793014]
  モデルフリーのステージベースQ-ラーニングアルゴリズムはモデルベースアルゴリズムと同じ$H$依存の最適性を享受できることを示す。 本アルゴリズムは,楽観的値関数と悲観的値関数のペアとして参照値関数を更新するキーとなる新しい設計を特徴とする。
  論文  参考訳（メタデータ） (2023-08-17T08:34:58Z)
• An Optimization-based Deep Equilibrium Model for Hyperspectral Image Deconvolution with Convergence Guarantees [71.57324258813675]
  本稿では,ハイパースペクトル画像のデコンボリューション問題に対処する新しい手法を提案する。 新しい最適化問題を定式化し、学習可能な正規化器をニューラルネットワークの形で活用する。 導出した反復解法は、Deep Equilibriumフレームワーク内の不動点計算問題として表現される。
  論文  参考訳（メタデータ） (2023-06-10T08:25:16Z)
• Sample Complexity of Variance-reduced Distributionally Robust Q-learning [17.96094201655567]
  本稿では,分散性に頑健なQ-ラーニングアルゴリズムと,分散性に欠けるロバストなポリシーを効果的に学習できる分散性のあるQ-ラーニングアルゴリズムを2つ提案する。 一連の数値実験により、分布シフトの処理におけるアルゴリズムの理論的発見と効率性が確認された。
  論文  参考訳（メタデータ） (2023-05-28T19:40:46Z)
• A Data-Driven State Aggregation Approach for Dynamic Discrete Choice Models [7.7347261505610865]
  本稿では,状態の選択と集約のためのデータ駆動型手法を提案する。 提案した2段階のアプローチは,問題次元を減らして次元の呪いを緩和する。 2つの古典的動的離散的選択推定法におけるアルゴリズムの実証的性能を実証する。
  論文  参考訳（メタデータ） (2023-04-11T01:07:24Z)
• Faster One-Sample Stochastic Conditional Gradient Method for Composite Convex Minimization [61.26619639722804]
  滑らかで非滑らかな項の和として形成される凸有限サム目標を最小化するための条件勾配法(CGM)を提案する。 提案手法は, 平均勾配 (SAG) 推定器を備え, 1回に1回のサンプルしか必要としないが, より高度な分散低減技術と同等の高速収束速度を保証できる。
  論文  参考訳（メタデータ） (2022-02-26T19:10:48Z)
• Tightening the Dependence on Horizon in the Sample Complexity of Q-Learning [59.71676469100807]
  この研究は、同期Q-ラーニングのサンプルの複雑さを、任意の$0varepsilon 1$に対して$frac|mathcalS| (1-gamma)4varepsilon2$の順序に絞る。 計算やストレージを余分に必要とせずに、高速なq-learningにマッチするvanilla q-learningの有効性を明らかにした。
  論文  参考訳（メタデータ） (2021-02-12T14:22:05Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• Momentum Q-learning with Finite-Sample Convergence Guarantee [49.38471009162477]
  本稿では,有限サンプル保証を用いたモーメントに基づくQ-ラーニングアルゴリズムのクラスを解析する。 線形関数近似とマルコフサンプリングによるMomentumQの収束保証を確立する。 提案したMomentumQが他のモーメントベースのQ-ラーニングアルゴリズムより優れていることを示す。
  論文  参考訳（メタデータ） (2020-07-30T12:27:03Z)

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

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