論文の概要: Toward the Optimal Regret-Instability Trade-off in Multi-Armed Bandits

• arxiv url: http://arxiv.org/abs/2608.17841v1
• Date: Tue, 18 Aug 2026 14:38:47 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-08-19 21:40:53.368371
• Title: Toward the Optimal Regret-Instability Trade-off in Multi-Armed Bandits
• Title（参考訳）: マルチアーマッドバンドにおける最適回帰不安定トレードオフに向けて
• Authors: Kaifei Wang, Yinyu Ye, Han Zhong,
• Abstract要約: マルチアームのバンディットアルゴリズムは、後悔によって評価されるが、同等の後悔は、独立ラン毎に異なるアロケーションと共存することができる。 我々は、最低ケースの後悔$mathcalR_K,T$と不安定$mathcalS_K,T$のトレードオフを、端末プルカウントの最大の標準偏差として定義し、$K$アームと$T$ラウンドについて検討する。
• 参考スコア（独自算出の注目度）: 13.075031222564535
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Multi-armed bandit algorithms are evaluated by regret, yet comparable regret can coexist with different allocations across independent runs. We study the trade-off between worst-case regret $\mathcal{R}_{K,T}$ and instability $\mathcal S_{K,T}$, defined as the largest standard deviation of a terminal pull count, for $K$ arms and $T$ rounds. We prove the finite-time lower bound $\mathcal R_{K,T}\mathcal S_{K,T}\ge C T^{3/2}$, where $C$ is independent of $K$ and $T$, under a finite-time regret condition and without the regularity assumptions imposed in the prior asymptotic analysis. We also introduce Stabilized Lower-Envelope UCB (\textup{\textsc{SLE-UCB}}), a new tunable algorithm combining a running lower-envelope index with a decreasing pull-count stabilizer. \textup{\textsc{SLE-UCB}} satisfies $\mathcal R_{K,T}\mathcal S_{K,T}=O(T^{3/2}\log K)$, with an implicit constant independent of $K$ and $T$, matching the lower bound exactly in $T$ and within a logarithmic factor in $K$. To prove the instability bound, we develop a new offline top-prefix representation that removes path dependence from online decisions. Together with single-reward perturbations and the Efron--Stein inequality, this representation controls pull-count variance. Thus, regret and instability depend reciprocally on $K$, while their product has no polynomial dependence on $K$. These results resolve the open question raised in the literature concerning the sharp arm-dependent regret--instability frontier.
• Abstract（参考訳）: マルチアームのバンディットアルゴリズムは、後悔によって評価されるが、同等の後悔は、独立ラン毎に異なるアロケーションと共存することができる。 我々は、最悪の場合の後悔$\mathcal{R}_{K,T}$と不安定$\mathcal S_{K,T}$のトレードオフを、端末プルカウントの最大の標準偏差として定義し、$K$アームと$T$ラウンドについて検討する。 有限時間下界 $\mathcal R_{K,T}\mathcal S_{K,T}\ge C T^{3/2}$ を証明する。 また、動作中の低エンベロープ指数とプル数安定化器を併用した新しいチューナブルアルゴリズムである安定化低エンベロープ UCB (\textup{\textsc{SLE-UCB}}) を導入する。 \textup{\textsc{SLE-UCB}} は $\mathcal R_{K,T}\mathcal S_{K,T}=O(T^{3/2}\log K)$ を満たす。 不安定性を証明するために,オンライン決定から経路依存を除去するオフライントッププレフィックス表現を開発した。 単逆摂動とEfron-Steinの不等式とともに、この表現はプル数分散を制御する。 したがって、後悔と不安定性は$K$に相互に依存するが、それらの積は$K$に多項式依存を持たない。 これらの結果は、鋭い腕依存の後悔-不安定なフロンティアに関する文献で提起されたオープンな疑問を解決する。

関連論文リスト

• Asymptotically Optimal Regret for Reinforcement Learning without Horizon Dependence [54.59847568544922]
  有限水平時間同質なマルコフ決定過程に対して、$A$状態、$A$アクション、hoighty $H$、および1ドルで有界なトラジェクティブ当たりの合計報酬について、地平自由な後悔について検討する。 失敗確率$$K$はエピソード数で$tilde O(sqrtSAK+S3K)$ hides $mathsfpolyである。
  論文  参考訳（メタデータ） (2026-07-22T07:42:19Z)
• Solving Stochastic Fixed-Point Equations with High Probability [22.376855234542813]
  オラクルの不動点方程式 $mathbfT(mathbfx) = mathbfx$ をノルム空間上で研究する。 本稿では,2次スムーズなバナッハ空間に対する分散還元段階Halpern法であるVR-GHALを紹介する。
  論文  参考訳（メタデータ） (2026-07-10T04:59:20Z)
• Monge-Kantorovich Fitting With Sobolev Budgets [6.748324975906262]
  我々は、$rho$が$mtext-d$集合の近くに集中しているとき、これをノイズのあるデータを持つ多様体学習問題と解釈できることを示した。 Monge-Kantorovich $p$-cost $mathbbW_pp(rho, nu)$を介して$rho$を近似する際の$nu$のパフォーマンスを定量化し、$mathrmsupp nu$を$f : mathbbRmでカバーできるようにすることで複雑さを制限します。
  論文  参考訳（メタデータ） (2024-09-25T01:30:16Z)
• Restless Linear Bandits [5.00389879175348]
  未知の$mathbbRd$-valued stationary $varphi$-mixing sequence of parameters $(theta_t,t in mathbbN)$ が存在すると仮定される。 指数混合率が$theta_t$の場合、LinMix-UCBと呼ばれる楽観的なアルゴリズムが提案される。
  論文  参考訳（メタデータ） (2024-05-17T14:37:39Z)
• LC-Tsallis-INF: Generalized Best-of-Both-Worlds Linear Contextual Bandits [38.41164102066483]
  本研究では,両逆境における上界を後悔するEmphBest-of-Both-Worlds (BoBW) アルゴリズムを開発した。 提案アルゴリズムは限界条件下で$Oleft(log(T)1+beta2+betaTfrac12+betaright)$ regretを達成していることを示す。
  論文  参考訳（メタデータ） (2024-03-05T18:59:47Z)
• Horizon-Free and Variance-Dependent Reinforcement Learning for Latent Markov Decision Processes [62.90204655228324]
  我々は,後期マルコフ決定過程(LMDP)における強化学習(RL)の文脈を考慮した後悔の最小化について検討した。 我々は,モデル最適化と値最適化の両手法でインスタンス化できる,新しいモデルベースアルゴリズムフレームワークを設計する。
  論文  参考訳（メタデータ） (2022-10-20T21:32:01Z)
• Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits with Linear Payoff Functions [53.77572276969548]
  我々は、C$2$UCBアルゴリズムが分割マトロイド制約に対して最適な後悔結合$tildeO(dsqrtkT + dk)$を有することを示した。 一般的な制約に対して,C$2$UCBアルゴリズムで腕の報酬推定値を変更するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-20T04:29:18Z)
• Taking a hint: How to leverage loss predictors in contextual bandits? [63.546913998407405]
  我々は,損失予測の助けを借りて,文脈的包帯における学習を研究する。 最適な後悔は$mathcalO(minsqrtT, sqrtmathcalETfrac13)$である。
  論文  参考訳（メタデータ） (2020-03-04T07:36:38Z)
• Naive Exploration is Optimal for Online LQR [49.681825576239355]
  最適後悔尺度は$widetildeTheta(sqrtd_mathbfu2 d_mathbfx T)$で、$T$は時間ステップの数、$d_mathbfu$は入力空間の次元、$d_mathbfx$はシステム状態の次元である。 我々の下界は、かつての$mathrmpoly(logT)$-regretアルゴリズムの可能性を排除する。
  論文  参考訳（メタデータ） (2020-01-27T03:44:54Z)

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

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