論文の概要: Gap-Dependent Bounds for Q-Learning using Reference-Advantage Decomposition

• arxiv url: http://arxiv.org/abs/2410.07574v1
• Date: Thu, 10 Oct 2024 03:19:46 GMT
• ステータス: 処理完了
• システム内更新日: 2024-10-31 16:16:17.219043
• Title: Gap-Dependent Bounds for Q-Learning using Reference-Advantage Decomposition
• Title（参考訳）: 参照アドバンテージ分解を用いたQ-Learningのためのギャップ依存境界
• Authors: Zhong Zheng, Haochen Zhang, Lingzhou Xue,
• Abstract要約: 有限水平マルコフ決定過程(MDPs)に対するオンラインQ-ラーニングのための2つの重要なアルゴリズムのギャップ依存境界について検討する。 本稿では, UCB-Advantage と Q-EarlySettled-Advantage のギャップ依存的再帰境界を, 対数的に$T$で証明する新しい誤り分解フレームワークを開発する。 また, UCB-Advantage の政策切替コストのギャップ依存境界を確立し, 最悪の MDP でそれを改善する。
• 参考スコア（独自算出の注目度）: 4.895986534376972
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the gap-dependent bounds of two important algorithms for on-policy Q-learning for finite-horizon episodic tabular Markov Decision Processes (MDPs): UCB-Advantage (Zhang et al. 2020) and Q-EarlySettled-Advantage (Li et al. 2021). UCB-Advantage and Q-EarlySettled-Advantage improve upon the results based on Hoeffding-type bonuses and achieve the almost optimal $\sqrt{T}$-type regret bound in the worst-case scenario, where $T$ is the total number of steps. However, the benign structures of the MDPs such as a strictly positive suboptimality gap can significantly improve the regret. While gap-dependent regret bounds have been obtained for Q-learning with Hoeffding-type bonuses, it remains an open question to establish gap-dependent regret bounds for Q-learning using variance estimators in their bonuses and reference-advantage decomposition for variance reduction. We develop a novel error decomposition framework to prove gap-dependent regret bounds of UCB-Advantage and Q-EarlySettled-Advantage that are logarithmic in $T$ and improve upon existing ones for Q-learning algorithms. Moreover, we establish the gap-dependent bound for the policy switching cost of UCB-Advantage and improve that under the worst-case MDPs. To our knowledge, this paper presents the first gap-dependent regret analysis for Q-learning using variance estimators and reference-advantage decomposition and also provides the first gap-dependent analysis on policy switching cost for Q-learning.
• Abstract（参考訳）: 有限水平表層型マルコフ決定過程(MDPs): UCB-Advantage (Zhang et al 2020)とQ-EarlySettled-Advantage (Li et al 2021)の2つの重要なQ-ラーニングアルゴリズムのギャップ依存境界について検討した。 UCB-AdvantageとQ-EarlySettled-Advantageは、Hoeffding型のボーナスに基づいて結果を改善し、最悪のシナリオでは、$T$がステップの総数であるようなほぼ最適な$\sqrt{T}$-typeの後悔を達成します。 しかし, 厳密な正の準最適ギャップなどのMDPの良質な構造は, 後悔を著しく改善する可能性がある。 Hoeffding型ボーナスを用いたQラーニングにおいて、ギャップ依存の後悔境界が得られたが、分散推定器を用いたQラーニングにおけるギャップ依存の後悔境界と、分散低減のための参照アドバンテージ分解を確立することは、未解決の問題である。 本稿では, UCB-Advantage と Q-EarlySettled-Advantage のギャップ依存的再帰境界を$T$で対数的に証明し, 既存のQ-ラーニングアルゴリズムの改良を目的とした新しい誤り分解フレームワークを開発した。 さらに, UCB-Advantage の政策切替コストのギャップ依存境界を確立し, 最悪の MDP でそれを改善する。 本稿では,分散推定器と参照アドバンテージ分解を用いたQ-ラーニングにおける最初のギャップ依存的後悔分析と,Q-ラーニングにおけるポリシー切替コストに関する最初のギャップ依存的分析を提案する。

関連論文リスト

• Regularized Q-learning through Robust Averaging [3.4354636842203026]
  本稿では,既存のQラーニング手法の弱点を原則的に解決する,2RA Qラーニングと呼ばれる新しいQラーニング変種を提案する。 そのような弱点の1つは、制御できない、しばしばパフォーマンスが低下する、基礎となる推定バイアスである。 2RA Q-learningは最適ポリシーに収束し、理論平均二乗誤差を解析する。
  論文  参考訳（メタデータ） (2024-05-03T15:57:26Z)
• Online Learning under Budget and ROI Constraints via Weak Adaptivity [57.097119428915796]
  制約付きオンライン学習問題に対する既存の原始双対アルゴリズムは、2つの基本的な仮定に依存している。 このような仮定は、標準の原始双対テンプレートを弱適応的後悔最小化器で与えることによって、どのように回避できるのかを示す。 上記の2つの前提が満たされていない場合に保証される、世界の最高の保証を証明します。
  論文  参考訳（メタデータ） (2023-02-02T16:30:33Z)
• Direct Heterogeneous Causal Learning for Resource Allocation Problems in Marketing [20.9377115817821]
  マーケティングは、ユーザのエンゲージメントを高め、プラットフォーム収益を改善するための重要なメカニズムである。 マーケティングにおける意思決定問題は資源配分問題として定式化され、数十年にわたって研究されてきた。 既存の作業は通常、解法を2つの完全に分離された段階、すなわち機械学習(ML)と操作研究(OR)に分割する。
  論文  参考訳（メタデータ） (2022-11-28T19:27:34Z)
• Optimizing Two-way Partial AUC with an End-to-end Framework [154.47590401735323]
  ROC曲線のエリア(AUC)は、機械学習にとって重要な指標である。 最近の研究は、TPAUCが既存のPartial AUCメトリクスと本質的に矛盾していることを示している。 本論文では,この新指標を最適化するための最初の試行について述べる。
  論文  参考訳（メタデータ） (2022-06-23T12:21:30Z)
• Online Learning with Knapsacks: the Best of Both Worlds [54.28273783164608]
  オンライン学習の課題として,意思決定者が,リソース制約の有限セットに違反することなく,期待する報酬を最大化したい,という課題を提起する。 当社のフレームワークは,意思決定者がそのエビデンスを柔軟かつコスト論的に扱えるようにします。
  論文  参考訳（メタデータ） (2022-02-28T12:10:48Z)
• Can Q-Learning be Improved with Advice? [27.24260290748049]
  本稿では,マルコフ決定過程(MDP)のオンライン学習において,後悔に対する最悪の下限を回避できるかどうかを論じる。 最適$Q$-値関数の予測が蒸留と呼ばれる合理的に弱い条件を満たす場合、状態-作用対の集合を、その予測が極端に不正確な状態-作用対の集合に置き換えることで、後悔境界を改善することができることを示す。 私たちの研究は、キャッシュやスケジューリングといった単純なオンライン問題に重点を置いていた予測を伴うアルゴリズムに関する最近の研究を、強化学習のより複雑で一般的な問題へと拡張しています。
  論文  参考訳（メタデータ） (2021-10-25T15:44:20Z)
• Learning with Multiclass AUC: Theory and Algorithms [141.63211412386283]
  ROC曲線 (AUC) の下の領域は、不均衡学習やレコメンダシステムといった問題に対するよく知られたランキング基準である。 本稿では,マルチクラスAUCメトリクスを最適化することで,多クラススコアリング関数を学習する問題について検討する。
  論文  参考訳（メタデータ） (2021-07-28T05:18:10Z)
• Cross Learning in Deep Q-Networks [82.20059754270302]
  本稿では、値に基づく強化学習手法において、よく知られた過大評価問題を緩和することを目的とした、新しいクロスQ-ラーニングアルゴリズムを提案する。 本アルゴリズムは,並列モデルの集合を維持し,ランダムに選択されたネットワークに基づいてQ値を算出することによって,二重Q-ラーニングに基づいて構築する。
  論文  参考訳（メタデータ） (2020-09-29T04:58:17Z)
• Upper Confidence Primal-Dual Reinforcement Learning for CMDP with Adversarial Loss [145.54544979467872]
  マルコフ決定過程(CMDP)に対するオンライン学習の検討 本稿では,遷移モデルから標本化した軌跡のみを必要とする,新しいEmphupper confidence primal-dualアルゴリズムを提案する。 我々の分析では、ラグランジュ乗算過程の新たな高確率ドリフト解析を、高信頼強化学習の記念後悔解析に組み入れている。
  論文  参考訳（メタデータ） (2020-03-02T05:02:23Z)

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

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