論文の概要: Variance-Aware Non-Stationary Bandits:All-Budget Regret Bounds and Adaptation Costs
- arxiv url: http://arxiv.org/abs/2610.26116v1
- Date: Mon, 19 Oct 2026 10:10:27 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-24 02:16:50.937898
- Title: Variance-Aware Non-Stationary Bandits:All-Budget Regret Bounds and Adaptation Costs
- Title（参考訳）: 変動を考慮した非定常帯域:全予算レグレト境界と適応コスト
- Abstract要約: 低報酬分散は推定コストを低減させるが、観測されていないまま改善される可能性のある腕の監視を排除しない。
我々は,2つのコストが,有界,非定常なマルチ武器帯における供給されるばらつきと変動予算にどのように依存するかを特徴付ける。
- 参考スコア（独自算出の注目度）: 1.469272550839244
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Low reward variance reduces estimation cost, but does not eliminate monitoring of arms that may improve while unobserved. We refine the variance--variation tradeoff and characterize how both costs depend on supplied variance and variation budgets in bounded, non-stationary multi-armed bandits. Let $A$ be the number of arms, $T$ the horizon, $B$ a bound on consecutive mean variation excluding the initial vector, and $Q$ a bound on the sum of the largest per-round reward variances. For every admissible pair $Q,B$, the minimax expected dynamic regret is, within a single logarithmic factor, \[ \min\{T,\;A+\sqrt{AQ}+(AQBT)^{1/3} +\sqrt{AT}\min\{B,\sqrt B\}\}. \] The deterministic boundary $Q=0$ is characterized without logarithms. For small positive budgets, a safe calibration phase identifies a common interval containing all future means of surviving arms. Clipping observations to a wider interval reduces the cost of restarting a prior hybrid static-regret algorithm; an original-mean analytical reference controls its residuals without charging the variation of clipped means. Balancing clipping bias and monitoring closes the small-budget noisy regime. Fixed oblivious constructions give the matching lower bound. We also quantify adaptation costs: on a disclosed deterministic one-improvement family, a stationary-regret budget has a matching worst-case change-regret frontier, including a finite improvement pulse. This implies an $Ω((T/A)^{1/4})$ loss when one policy competes with all supplied-budget deterministic oracle rates. The budget-free low-noise scheduling problem remains separate.
- Abstract（参考訳）: 低報酬分散は推定コストを低減させるが、観測されていないまま改善される可能性のある腕の監視を排除しない。
我々は、ばらつきのトレードオフを洗練させ、両コストが、有界、非定常な多武装バンディットにおける供給されたばらつきとばらつきの予算にどのように依存するかを特徴付ける。
A$ を腕の数、T$ 地平線、B$ を初期ベクトルを除く連続平均変動、Q$ をラウンド当たりの最大の報酬分散の和とする。
任意の許容可能なペア $Q,B$ に対して、ミニマックス予想される動的後悔は、単一の対数係数 \[ \min\{T,\;A+\sqrt{AQ}+(AQBT)^{1/3} +\sqrt{AT}\min\{B,\sqrt B\}\}\} の中で与えられる。
\] 決定論的境界$Q=0$は対数なしで特徴づけられる。
小さな正の予算では、安全なキャリブレーションフェーズは、生き残った武器の全ての将来の手段を含む共通の間隔を識別する。
より広い間隔で観測を行うと、以前のハイブリッドな静的回帰アルゴリズムを再起動するコストが削減される。
クリッピングバイアスとモニタリングのバランスをとることで、低予算のノイズが解消される。
固定された曖昧な構成は、一致した下界を与える。
また, 適応コストの定量化も行なっている: 決定論的一改良ファミリーでは, 定常回帰予算は, 有限改良パルスを含む最悪の変化最前線を有する。
これは、1つのポリシーが全ての供給された予算決定論的なオラクルレートと競合するとき、$Ω((T/A)^{1/4})$損失を意味する。
予算のない低ノイズスケジューリング問題はまだ分離されていない。
関連論文リスト
- Parameter-Free Interval-Dynamic Regret under Heavy-Tailed Noise [55.29259818039367]
オンライン凸最適化を1ラウンドに1つの偏りのない下位段階と、未知の有限条件の雑音モーメントであるp$th, $1ple2$で検討する。
長さ$n$の固定区間$I$に対して、学習者は最適な全水平静的レートを含む1+log(T/n)$を達成する。
論文 参考訳（メタデータ） (2026-09-30T21:03:03Z) - Constrained Online Learning with Noisy Constraint Values [55.29259818039367]
一般的な実現可能性の下では、我々のLEDGERアルゴリズムは、期待される損失$O(sqrt T)と期待される予算違反$O(sqrtTlog(eT))を達成します。
スレーター条件、フィードバックチャネル間の独立性、絶対的制約値境界は不要である。
論文 参考訳（メタデータ） (2026-09-07T01:38:41Z) - Breaking the Total Variance Barrier: Sharp Sample Complexity for Linear Heteroscedastic Bandits with Fixed Action Set [93.03556214432615]
本稿では,学習過程を通じて動作セットをプレフィックスするヘテロセシダスティックノイズによる線形帯域問題を再検討する。
本稿では,情報ゲインを最大化するアクションを積極的に探求する,大規模アクション集合のための分散適応アルゴリズムのtexttVAEEを提案する。
音素平均依存率が避けられないことを示す固定作用集合に対して、ほぼ一致する下界を確立する。
論文 参考訳（メタデータ） (2026-07-26T14:24:34Z) - Online Covariance Estimation in Averaged SGD: Improved Batch-Mean Rates and Minimax Optimality via Trajectory Regression [12.805268849262243]
我々はPolyak-Ruppert averaged gradient descent (SGD)のオンライン共分散行列推定について検討した。
この構造は、このボトルネックがSGDドリフトからヘッセンの情報をサブ線形に蓄積していることを明らかにする。
論文 参考訳（メタデータ） (2026-04-12T20:49:33Z) - Variance-Dependent Regret Bounds for Non-stationary Linear Bandits [52.872628573907434]
報酬分布の分散と$B_K$の分散を利用するアルゴリズムを提案する。
Restarted Weighted$textOFUL+$とRestarted$textSAVE+$の2つの新しいアルゴリズムを紹介します。
特に、V_K$が$K$よりはるかに小さい場合、我々のアルゴリズムは、異なる設定下での非定常線形バンドレットの最先端結果よりも優れている。
論文 参考訳（メタデータ） (2024-03-15T23:36:55Z) - Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement
Learning: Adaptivity and Computational Efficiency [90.40062452292091]
本稿では,不整合雑音を持つ線形帯域に対する計算効率のよい最初のアルゴリズムを提案する。
我々のアルゴリズムは未知のノイズの分散に適応し、$tildeO(d sqrtsum_k = 1K sigma_k2 + d)$ regretを達成する。
また、強化学習において、線形混合マルコフ決定過程(MDP)に対する分散適応アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-02-21T00:17:24Z) - Adversarially Robust Multi-Armed Bandit Algorithm with
Variance-Dependent Regret Bounds [34.37963000493442]
本稿では,マルチアーム・バンディット(MAB)問題について考察し,両対向的条件下でほぼ最適に機能する,新たなベスト・オブ・ボス・ワールド(BOBW)アルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-06-14T12:58:46Z) - Stochastic Linear Bandits Robust to Adversarial Attacks [117.665995707568]
我々はロバスト位相除去アルゴリズムの2つの変種を提供し、その1つは$C$を知っており、もう1つはそうでない。
いずれの変種も、倒壊しない場合には、それぞれ$C = 0$ となり、それぞれ追加の加法項が生じる。
文脈的設定では、単純な欲求的アルゴリズムは、明示的な探索を行わず、C$を知らないにもかかわらず、ほぼ最適加法的後悔項で証明可能な堅牢性を示す。
論文 参考訳（メタデータ） (2020-07-07T09:00:57Z) - Budget-Constrained Bandits over General Cost and Reward Distributions [32.63624728528415]
我々は,各アームがランダムなコストを発生させ,その見返りにランダムな報酬を与える,予算制約付きバンディット問題を考える。
ある$gamma > 0$ に対して位数 $(2+gamma)$ のモーメントが存在するならば、$O(log B)$ regret は予算 $B>0$ に対して達成可能である。
論文 参考訳（メタデータ） (2020-02-29T23:50:08Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。