論文の概要: Q-Learning with Fine-Grained Gap-Dependent Regret
- arxiv url: http://arxiv.org/abs/2510.06647v1
- Date: Wed, 08 Oct 2025 05:02:16 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-10-09 16:41:20.304541
- Title: Q-Learning with Fine-Grained Gap-Dependent Regret
- Title（参考訳）: 微細ギャップ依存レグレットを用いたQ-Learning
- Authors: Haochen Zhang, Zhong Zheng, Lingzhou Xue,
- Abstract要約: 既存のモデルフリーアルゴリズムは、最小限の最悪の後悔を実現するが、そのギャップ依存境界はいまだに粗いままであり、最適以下のギャップの構造を完全に捉えることができない。
UCBベースと非UCBベースの両方のアルゴリズムに対して、きめ細かいギャップ依存的後悔境界を確立する。
- 参考スコア（独自算出の注目度）: 13.370933509246568
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study fine-grained gap-dependent regret bounds for model-free reinforcement learning in episodic tabular Markov Decision Processes. Existing model-free algorithms achieve minimax worst-case regret, but their gap-dependent bounds remain coarse and fail to fully capture the structure of suboptimality gaps. We address this limitation by establishing fine-grained gap-dependent regret bounds for both UCB-based and non-UCB-based algorithms. In the UCB-based setting, we develop a novel analytical framework that explicitly separates the analysis of optimal and suboptimal state-action pairs, yielding the first fine-grained regret upper bound for UCB-Hoeffding (Jin et al., 2018). To highlight the generality of this framework, we introduce ULCB-Hoeffding, a new UCB-based algorithm inspired by AMB (Xu et al.,2021) but with a simplified structure, which enjoys fine-grained regret guarantees and empirically outperforms AMB. In the non-UCB-based setting, we revisit the only known algorithm AMB, and identify two key issues in its algorithm design and analysis: improper truncation in the $Q$-updates and violation of the martingale difference condition in its concentration argument. We propose a refined version of AMB that addresses these issues, establishing the first rigorous fine-grained gap-dependent regret for a non-UCB-based method, with experiments demonstrating improved performance over AMB.
- Abstract（参考訳）: 表在性表在性マルコフ決定過程におけるモデルなし強化学習のための微粒なギャップ依存的後悔境界について検討した。
既存のモデルフリーアルゴリズムは、最小限の最悪の後悔を実現するが、そのギャップ依存境界はいまだに粗いままであり、最適以下のギャップの構造を完全に捉えることができない。
UCBベースと非UCBベースの両方のアルゴリズムに対して、きめ細かいギャップ依存の後悔境界を確立することで、この制限に対処する。
提案手法は, UCB-Hoeffding (Jin et al , 2018) において, UCB-Hoeffding において, 最適な状態-作用対と最適状態-作用対を明示的に分離した新たな解析フレームワークを開発するものである。
AMB(Xu et al ,2021)にインスパイアされた新しい UCB ベースのアルゴリズムであるULCB-Hoeffding を導入し,その構造を単純化した。
非UCB ベースの設定では、唯一知られているアルゴリズム AMB を再検討し、アルゴリズムの設計と解析における2つの重要な問題を特定する。
本稿では,これらの問題に対処する AMB の改良版を提案し,AMB よりも優れた性能を示す実験を行った。
関連論文リスト
- UCB algorithms for multi-armed bandits: Precise regret and adaptive inference [6.349503549199403]
upper Confidence Bound (UCB) アルゴリズムは、$K$武器の盗聴問題に対して広く使われているシーケンシャルアルゴリズムのクラスである。
Lai-Robbins の後悔公式が真であることと、その部分最適性ギャップが$sigmasqrtKlog T/T$を超える場合に限ることを示す。
また、その最大後悔は対数係数によって最小後悔から逸脱し、従ってその厳密な最小最適性を負に設定することを示した。
論文 参考訳（メタデータ） (2024-12-09T01:14:02Z) - Gap-Dependent Bounds for Q-Learning using Reference-Advantage Decomposition [4.895986534376972]
有限水平マルコフ決定過程(MDPs)に対するオンラインQ-ラーニングのための2つの重要なアルゴリズムのギャップ依存境界について検討する。
本稿では, UCB-Advantage と Q-EarlySettled-Advantage のギャップ依存的再帰境界を, 対数的に$T$で証明する新しい誤り分解フレームワークを開発する。
また, UCB-Advantage の政策切替コストのギャップ依存境界を確立し, 最悪の MDP でそれを改善する。
論文 参考訳（メタデータ） (2024-10-10T03:19:46Z) - Scale-free Adversarial Reinforcement Learning [17.276918882127728]
本稿では,マルコフ決定過程(MDP)におけるスケールフリー学習の研究を開始する。
We design a generic algorithmic framework underlineScale underlineClipping underlineBound (textttSCB)
我々は,最小限の最適再帰限界を達成し,大規模無敵MABにおける最初の高確率再帰限界を達成した。
論文 参考訳（メタデータ） (2024-03-01T19:21:10Z) - On the Sublinear Regret of GP-UCB [58.25014663727544]
ガウス過程上信頼境界 (GP-UCB) アルゴリズムは, ほぼ最適の後悔率を有することを示す。
私たちの改善は、基盤となるカーネルの滑らかさに比例してカーネルリッジ推定を正規化するという、重要な技術的貢献に依存しています。
論文 参考訳（メタデータ） (2023-07-14T13:56:11Z) - Tight Guarantees for Interactive Decision Making with the
Decision-Estimation Coefficient [51.37720227675476]
我々は、決定推定係数の新たな変種を導入し、それを用いて、3つの面における事前の作業を改善する新しい下界を導出する。
我々は同じ量でスケールした後悔について上界を与え、フォスター等における上界と下界の間のギャップの1つを除いて全てを閉じる。
この結果は、後悔のフレームワークとPACフレームワークの両方に適用され、我々が期待するいくつかの新しい分析とアルゴリズム設計技術を利用して、より広範な利用が期待できる。
論文 参考訳（メタデータ） (2023-01-19T18:24:08Z) - Achieving the Pareto Frontier of Regret Minimization and Best Arm
Identification in Multi-Armed Bandits [91.8283876874947]
本稿では,BoBW-lil'UCB$(gamma)$アルゴリズムの設計と解析を行う。
i) RMとBAIの両方の目的に対して最適なアルゴリズムを同時に実行できないことを示す。
また、BoBW-lil'UCB$(gamma)$は、時間複雑性と後悔の点で競合よりも優れていることを示す。
論文 参考訳（メタデータ） (2021-10-16T17:52:32Z) - Value-Function-based Sequential Minimization for Bi-level Optimization [52.39882976848064]
勾配に基づくBi-Level Optimization (BLO)法は、現代の学習課題に広く応用されている。
機能的制約のあるBLOや悲観的なBLOなど、難解なシナリオでBLOを解くことができる勾配ベースの方法はほとんどない。
上記の問題に対処するために,BVFSM(Bi-level Value-Function-based Sequential Minimization)を提案する。
論文 参考訳（メタデータ） (2021-10-11T03:13:39Z) - A Closer Look at the Worst-case Behavior of Multi-armed Bandit
Algorithms [8.099977107670918]
アッパー信頼境界 (UCB) は楽観的なMABアルゴリズムである。
本稿では,UCBのアームサンプリング動作に関する新しい知見を提供する。
また、UPBの下でのMAB問題のプロセスレベルの特徴付けも提供する。
論文 参考訳（メタデータ） (2021-06-03T20:52:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。