論文の概要: Sharp Gap-Dependent Variance-Aware Regret Bounds for Tabular MDPs

• arxiv url: http://arxiv.org/abs/2506.06521v1
• Date: Fri, 06 Jun 2025 20:33:57 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-10 16:33:10.307946
• Title: Sharp Gap-Dependent Variance-Aware Regret Bounds for Tabular MDPs
• Title（参考訳）: 球状MDPに対するシャープギャップ依存性可変型レギュレット境界
• Authors: Shulun Chen, Runlong Zhou, Zihan Zhang, Maryam Fazel, Simon S. Du,
• Abstract要約: 我々は,モノトニック値 Omega (MVP) アルゴリズムが,差分を考慮した差分依存残差境界を$tildeOleft(left(sum_Delta_h(s,a)>0 fracH2 log K land MathttVar_maxtextc$。
• 参考スコア（独自算出の注目度）: 54.28273395444243
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the gap-dependent regret bounds for episodic MDPs. We show that the Monotonic Value Propagation (MVP) algorithm achieves a variance-aware gap-dependent regret bound of $$\tilde{O}\left(\left(\sum_{\Delta_h(s,a)>0} \frac{H^2 \log K \land \mathtt{Var}_{\max}^{\text{c}}}{\Delta_h(s,a)} +\sum_{\Delta_h(s,a)=0}\frac{ H^2 \land \mathtt{Var}_{\max}^{\text{c}}}{\Delta_{\mathrm{min}}} + SAH^4 (S \lor H) \right) \log K\right),$$ where $H$ is the planning horizon, $S$ is the number of states, $A$ is the number of actions, and $K$ is the number of episodes. Here, $\Delta_h(s,a) =V_h^* (a) - Q_h^* (s, a)$ represents the suboptimality gap and $\Delta_{\mathrm{min}} := \min_{\Delta_h (s,a) > 0} \Delta_h(s,a)$. The term $\mathtt{Var}_{\max}^{\text{c}}$ denotes the maximum conditional total variance, calculated as the maximum over all $(\pi, h, s)$ tuples of the expected total variance under policy $\pi$ conditioned on trajectories visiting state $s$ at step $h$. $\mathtt{Var}_{\max}^{\text{c}}$ characterizes the maximum randomness encountered when learning any $(h, s)$ pair. Our result stems from a novel analysis of the weighted sum of the suboptimality gap and can be potentially adapted for other algorithms. To complement the study, we establish a lower bound of $$\Omega \left( \sum_{\Delta_h(s,a)>0} \frac{H^2 \land \mathtt{Var}_{\max}^{\text{c}}}{\Delta_h(s,a)}\cdot \log K\right),$$ demonstrating the necessity of dependence on $\mathtt{Var}_{\max}^{\text{c}}$ even when the maximum unconditional total variance (without conditioning on $(h, s)$) approaches zero.
• Abstract（参考訳）: エピソードMDPにおけるギャップ依存的後悔境界について考察する。 MVP(Monotonic Value Propagation)アルゴリズムは、$$$\tilde{O}\left(\left(\sum_{\Delta_h(s,a)>0} \frac{H^2 \log K \land \matht{Var}_{\max}^{\text{c}}}{\Delta_h(s,a)} +\sum_{\Delta_h(s,a)=0}\frac{H^2 \land \matht{Var}_{\max}^{\text{c}}}{\Delta_{\mathrm{min}}} + SAH^4 (S \lor H) \right) \log K\right) の分散-認識ギャップ依存性のリフレクション境界を達成する。 ここで、$\Delta_h(s,a) = V_h^* (a) - Q_h^* (s,a)$は準最適ギャップを表し、$\Delta_{\mathrm{min}} := \min_{\Delta_h (s,a) > 0} \Delta_h(s,a)$である。 $\mathtt{Var}_{\max}^{\text{c}}$は、すべての$(\pi, h, s)$の最大値として計算された最大条件付き全分散を表す。 $\mathtt{Var}_{\max}^{\text{c}}$は、任意の$(h, s)$ペアを学ぶときに発生する最大のランダム性を特徴付ける。 この結果は,重み付けされた準最適差の和の新たな解析から得られたものであり,他のアルゴリズムにも適用できる可能性が示唆された。 この研究を補完するために、$$\Omega \left( \sum_{\Delta_h(s,a)>0} \frac{H^2 \land \matht{Var}_{\max}^{\text{c}}}{\Delta_h(s,a)}\cdot \log K\right),$$$\matht{Var}_{\max}^{\text{c}}$ は、($(h, s)$ の条件なしで)最大無条件の完全分散が 0 に近づくときでさえ、従属の必要性を示す。

関連論文リスト

• On the $O(\frac{\sqrt{d}}{K^{1/4}})$ Convergence Rate of AdamW Measured by $\ell_1$ Norm [54.28350823319057]
  本稿では、$ell_$ノルムで測定されたAdamWの収束率$frac1Ksum_k=1KEleft[|nabla f(xk)|_1right]leq O(fracsqrtdCK1/4)を確立する。
  論文  参考訳（メタデータ） (2025-05-17T05:02:52Z)
• Variance-Dependent Regret Lower Bounds for Contextual Bandits [65.93854043353328]
  これは従来の$tildeO(dsqrtK)$ regret bound to $tildeO(dsqrtsum_k=1Ksigma_k2)$で改善されている。
  論文  参考訳（メタデータ） (2025-03-15T07:09:36Z)
• Efficient Continual Finite-Sum Minimization [52.5238287567572]
  連続有限サム最小化(continuous finite-sum minimization)と呼ばれる有限サム最小化の鍵となるツイストを提案する。 我々のアプローチは$mathcalO(n/epsilon)$ FOs that $mathrmStochasticGradientDescent$で大幅に改善されます。 また、$mathcalOleft(n/epsilonalpharight)$ complexity gradient for $alpha 1/4$という自然な一階法は存在しないことを証明し、この方法の第一階法がほぼ密であることを示す。
  論文  参考訳（メタデータ） (2024-06-07T08:26:31Z)
• Partially Unitary Learning [0.0]
  ヒルベルト空間の最適写像 $IN$ of $left|psirightrangle$ と $OUT$ of $left|phirightrangle$ が提示される。 この最適化問題の大域的な最大値を求める反復アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2024-05-16T17:13:55Z)
• Perturbation Analysis of Randomized SVD and its Applications to Statistics [8.731676546744353]
  RSVD(英: RSVD)は、大規模データ行列の切り詰められたSVDを計算するための計算効率のよいアルゴリズムのクラスである。 本稿では、$ell$ と $ell_2,infty$ の正則特異ベクトル $widehatmathbfU$ と $widehatmathbfM$ の上限を導出する。 理論結果を、$widehatmathbfM$ が観測されていない信号行列 $mathbfM$ の加法摂動であるような設定に適用する。
  論文  参考訳（メタデータ） (2022-03-19T07:26:45Z)
• Spiked Covariance Estimation from Modulo-Reduced Measurements [14.569322713960494]
  我々は、ほとんどの方向において$bfu$と$nu=mathrmpoly(k)$に対して、$n=mathrmpoly(k)$測定を用いて、高い精度で$bfu$を推定するアルゴリズムを開発し、分析する。 数値実験により,非漸近的条件下でも良好な性能が得られた。
  論文  参考訳（メタデータ） (2021-10-04T02:10:47Z)
• The planted matching problem: Sharp threshold and infinite-order phase transition [25.41713098167692]
  ランダムに重み付けされた$ntimes n$ bipartite graphに隠された完全マッチング$M*$を再構築する問題について検討する。 任意の小さな定数 $epsilon>0$ に対して $sqrtd B(mathcalP,mathcalQ) ge 1+epsilon$ が成り立つ場合、任意の推定値の再構築誤差は $0$ から有界であることが示される。
  論文  参考訳（メタデータ） (2021-03-17T00:59:33Z)
• $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)
• Robust Interference Management for SISO Systems with Multiple Over-the-Air Computations [16.52374405363812]
  複素数値を共有するMAC上での総和のオーバー・ザ・エア計算について考察する。 適切なTx-Rxスケーリング因子を見つけることは、$s_n$の計算における低エラーとそれによって引き起こされる干渉との間にバランスをとる。
  論文  参考訳（メタデータ） (2020-04-21T11:15:26Z)
• On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions [62.01594253618911]
  有限和の有限ノイズ構造を利用して、大域オラクルモデルの下での一致する$O(n2)$-upper境界を導出する。 同様のアプローチを踏襲したSVRGの新規な適応法を提案し、これはオラクルと互換性があり、$tildeO(n2+nsqrtL/mu)log (1/epsilon)$と$O(nsqrtL/epsilon)$, for $mu>0$と$mu=0$の複雑さ境界を実現する。
  論文  参考訳（メタデータ） (2020-02-09T03:39:46Z)

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

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