論文の概要: Algorithm for Contextual Queueing Bandits with Rate-Optimal Queue Length Regret

• arxiv url: http://arxiv.org/abs/2606.09668v1
• Date: Mon, 08 Jun 2026 15:51:25 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-09 14:42:07.484219
• Title: Algorithm for Contextual Queueing Bandits with Rate-Optimal Queue Length Regret
• Title（参考訳）: レート最適待ち時間レグレットを用いたコンテキスト待ち帯域のアルゴリズム
• Authors: Seoungbin Bae, Dabeen Lee,
• Abstract要約: 待ち時間後悔は、学習者の待ち時間とオラクルの待ち時間の間に期待される差として定義される。 本稿では,この値を$widetildemathcalO(T-1/2)$に改善する。
• 参考スコア（独自算出の注目度）: 1.0098114696565863
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Contextual queueing bandits provide a framework for learning to schedule heterogeneous jobs under unknown context-dependent service rates. Under stochastic contexts, existing algorithms achieve $\widetilde{\mathcal{O}}(T^{-1/4})$ queue length regret, defined as the expected difference between the learner's and oracle's queue lengths at horizon $T$. In this paper, we improve this rate to $\widetilde{\mathcal{O}}(T^{-1/2})$. The key observation is that random exploration is needed only up to a carefully chosen cutoff round, rather than throughout the entire horizon. We propose CQB-$η$-2, a three-phase algorithm: (i) pure random exploration to construct an initial estimator, (ii) $η$-random exploration combined with a UCB rule to continue learning while maintaining negative drift, and (iii) pure UCB after the exploration cutoff. Our proof decomposes the queue length regret at the cutoff round. Before the cutoff, negative drift suppresses queue length differences caused by suboptimal choices. After the cutoff, the first two phases provide sufficient random exploration samples, ensuring that UCB decisions incur small departure-rate gaps. Combining these two bounds yields queue length regret of order $\widetilde{\mathcal{O}}(T^{-1/2})$. We further prove a minimax lower bound of order $Ω(T^{-1/2})$. The proof constructs two hard instances that are statistically indistinguishable up to the final service decision, and uses a queue-specific coupling argument to convert the resulting testing error into queue length regret. Together, our upper and lower bounds characterize the minimax dependence on the horizon $T$ up to logarithmic factors.
• Abstract（参考訳）: コンテキストキューの帯域は、未知のコンテキスト依存のサービスレートの下で異種ジョブをスケジュールする学習フレームワークを提供する。 確率的文脈では、既存のアルゴリズムは$\widetilde{\mathcal{O}}(T^{-1/4})$ queue length regretを達成する。 本稿では,この値を$\widetilde{\mathcal{O}}(T^{-1/2})$に改善する。 鍵となる観測は、ランダムな探査は地平線全体を通してではなく、慎重に選択されたカットオフラウンドまでのみ必要とされることである。 我々は三相アルゴリズムであるCQB-$η$-2を提案する。 (i)初期推定器を構築するための純粋ランダム探索 (ii)$η$-random 探索と UCB 規則を組み合わせて学習を継続し、負のドリフトを維持し、 三 探査遮断後の純粋なUCB。 我々の証明は、カットオフラウンドでの待ち行列長の後悔を分解する。 カットオフ前、負のドリフトは、最適下選択によるキュー長の差を抑制する。 切断後、最初の2つのフェーズでは十分なランダムな探索サンプルが提供され、UTBの決定がわずかな離脱率のギャップを生じさせることが保証された。 これら2つの境界を組み合わせると、順序 $\widetilde{\mathcal{O}}(T^{-1/2})$ のキュー長の後悔が得られる。 さらに、位数$Ω(T^{-1/2})$のミニマックス下界を証明します。 この証明は、最終的なサービス決定まで統計的に区別できない2つのハードインスタンスを構築し、キュー固有の結合引数を使用して、結果のテストエラーをキュー長の後悔に変換する。 上界と下界は、対数的因子までの地平線上の$T$のミニマックス依存性を特徴付ける。

関連論文リスト

• Queue Length Regret Bounds for Contextual Queueing Bandits [0.8984888893275712]
  我々は、未知のサービスレートを同時に学習しながら、スケジューリングのための新しいコンテキスト対応フレームワークであるコンテキストキュー帯域を導入します。 我々のアルゴリズムであるCQB-$varepsilon$は、$widetildemathcalO(T-1/4)$の残念な上限を達成する。 また,2番目のアルゴリズムであるCQB-Optは,逆選択された文脈の設定も考慮し,その場合の残差上限は$mathcalO(log2 T)$である。
  論文  参考訳（メタデータ） (2026-01-27T07:40:23Z)
• Tail Distribution of Regret in Optimistic Reinforcement Learning [3.9962751777898955]
  累積的後悔$R_K$ over $K$ エピソードのテール分布を,期待値や単一高確率量子化ではなく,特徴付ける。 提案したアルゴリズムは、期待される後悔と、その後悔がガウス以下の尾を示す範囲のバランスをとるチューニングパラメータ$$に依存する。
  論文  参考訳（メタデータ） (2025-11-23T02:23:09Z)
• Lateral Tree-of-Thoughts Surpasses ToT by Incorporating Logically-Consistent, Low-Utility Candidates [0.0]
  Lateral Tree-of-Thoughts (LToT) は、ユーティリティを論理的一貫性から分離し、低ユーティリティだが一貫した候補を無駄ではなく資産として扱うドロップインコントローラである。 LToTは、横方向の小さなプローブを非常に広い横方向のセットに広げるキャップ付き連続半減レースである、横方向レーシングと短絡(LR--SC)を介して横方向を探索する。
  論文  参考訳（メタデータ） (2025-10-01T22:23:58Z)
• From Continual Learning to SGD and Back: Better Rates for Continual Linear Models [50.11453013647086]
  以前見られたタスクの損失を、$k$の繰り返しの後、忘れること、すなわち、分析する。 実現可能な最小二乗の設定において、新しい最上界を創出する。 我々は、タスクを繰り返しないランダム化だけで、十分に長いタスクシーケンスで破滅的な事態を防げることを初めて証明した。
  論文  参考訳（メタデータ） (2025-04-06T18:39:45Z)
• p-Mean Regret for Stochastic Bandits [52.828710025519996]
  単純で統一された UCB ベースのアルゴリズムを導入し、新しい$p$-mean の後悔境界を実現する。 我々の枠組みは、特別な場合として、平均的な累積的後悔とナッシュ後悔の両方を包含する。
  論文  参考訳（メタデータ） (2024-12-14T08:38:26Z)
• Contextual Bandits for Unbounded Context Distributions [20.923880900127774]
  非パラメトリックな文脈的包帯は、シーケンシャルな意思決定問題の重要なモデルである。 UCB探査と近接する2つの手法を提案する。 本手法は, 限界条件が弱い場合に, 最小限の後悔を達成できることを示す。 2つ目の方法は、$tildeOleft(T1-frac(alpha+1)betaalpha+(d+2)beta+T1-betaright)$の期待された後悔を達成する。
  論文  参考訳（メタデータ） (2024-08-19T02:30:37Z)
• Communication-Constrained Bandits under Additive Gaussian Noise [111.06688156723018]
  クライアントが学習者にコミュニケーション制約のあるフィードバックを提供する分散マルチアームバンディットについて検討する。 我々は、この下限を小さな加法係数にマッチさせるマルチフェーズ帯域幅アルゴリズム、$mathtUEtext-UCB++$を提案する。
  論文  参考訳（メタデータ） (2023-04-25T09:31:20Z)
• Fast Rates for the Regret of Offline Reinforcement Learning [69.23654172273085]
  無限水平割引決定プロセス(MDP)における固定行動ポリシーによって生成されたオフラインデータからの強化学習の後悔について検討する。 最適品質関数 $Q*$ に対する任意の推定が与えられたとき、定義するポリシーの後悔は、$Q*$-estimate の点収束率の指数によって与えられる速度で収束することを示す。
  論文  参考訳（メタデータ） (2021-01-31T16:17:56Z)

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

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