論文の概要: Queue Length Regret Bounds for Contextual Queueing Bandits

• arxiv url: http://arxiv.org/abs/2601.19300v1
• Date: Tue, 27 Jan 2026 07:40:23 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-01-28 15:26:51.227434
• Title: Queue Length Regret Bounds for Contextual Queueing Bandits
• Title（参考訳）: 待ち行列帯域に対する待ち長レグレクト境界
• Authors: Seoungbin Bae, Garyeong Kang, Dabeen Lee,
• Abstract要約: 我々は、未知のサービスレートを同時に学習しながら、スケジューリングのための新しいコンテキスト対応フレームワークであるコンテキストキュー帯域を導入します。 我々のアルゴリズムであるCQB-$varepsilon$は、$widetildemathcalO(T-1/4)$の残念な上限を達成する。 また,2番目のアルゴリズムであるCQB-Optは,逆選択された文脈の設定も考慮し,その場合の残差上限は$mathcalO(log2 T)$である。
• 参考スコア（独自算出の注目度）: 0.8984888893275712
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We introduce contextual queueing bandits, a new context-aware framework for scheduling while simultaneously learning unknown service rates. Individual jobs carry heterogeneous contextual features, based on which the agent chooses a job and matches it with a server to maximize the departure rate. The service/departure rate is governed by a logistic model of the contextual feature with an unknown server-specific parameter. To evaluate the performance of a policy, we consider queue length regret, defined as the difference in queue length between the policy and the optimal policy. The main challenge in the analysis is that the lists of remaining job features in the queue may differ under our policy versus the optimal policy for a given time step, since they may process jobs in different orders. To address this, we propose the idea of policy-switching queues equipped with a sophisticated coupling argument. This leads to a novel queue length regret decomposition framework, allowing us to understand the short-term effect of choosing a suboptimal job-server pair and its long-term effect on queue state differences. We show that our algorithm, CQB-$\varepsilon$, achieves a regret upper bound of $\widetilde{\mathcal{O}}(T^{-1/4})$. We also consider the setting of adversarially chosen contexts, for which our second algorithm, CQB-Opt, achieves a regret upper bound of $\mathcal{O}(\log^2 T)$. Lastly, we provide experimental results that validate our theoretical findings.
• Abstract（参考訳）: 我々は、未知のサービスレートを同時に学習しながら、スケジューリングのための新しいコンテキスト対応フレームワークであるコンテキストキュー帯域を導入します。 個々のジョブは異種コンテキストの特徴を持ち、エージェントがジョブを選択し、それをサーバとマッチングして出発率を最大化する。 サービス/分割率は、未知のサーバ固有のパラメータを持つコンテキスト機能のロジスティックモデルによって管理されます。 ポリシの性能を評価するために,ポリシと最適ポリシのキュー長の差として定義される待ち行列長の後悔について検討する。 分析の主な課題は、キューに残されているジョブの特徴のリストが、特定の時間ステップに対する最適なポリシーと、異なる順序でジョブを処理する可能性があるため、私たちのポリシーの下で異なる可能性があることです。 そこで本研究では,複雑な結合引数を持つポリシスイッチングキューを提案する。 これにより、新しい待ち時間後悔分解フレームワークが実現され、最適ジョブサーバペアの選択による短期的効果と、待ち時間状態の違いに対する長期的影響が理解できるようになる。 我々は、我々のアルゴリズムであるCQB-$\varepsilon$が、$\widetilde{\mathcal{O}}(T^{-1/4})$の後悔の上限を達成することを示した。 また,2番目のアルゴリズムであるCQB-Opt は,逆選択された文脈の設定も考慮し,この場合の後悔の上限は$\mathcal{O}(\log^2T)$である。 最後に, 理論的結果を検証する実験結果について報告する。

関連論文リスト

• Rethinking Thinking Tokens: LLMs as Improvement Operators [80.12087211785949]
  推論トレーニングは、LLMに長い思考の連鎖(長いCoT)を生み出す動機を与え、自己チェックによるソリューション戦略を探索することを可能にする。 これにより、精度が高くなりますが、コンテキストの長さ、トークン/計算コスト、応答レイテンシが膨らみます。 現在のモデルはメタ認知を活用して、このParetoフロンティアで他の組み合わせを提供できるのでしょうか? i) 多様なドラフトを並列に生成し、(ii) それらを有界なテキストワークスペースに蒸留し、(iii) このワークスペース上に条件付き精製する。
  論文  参考訳（メタデータ） (2025-10-01T17:08:59Z)
• Visual Document Understanding and Question Answering: A Multi-Agent Collaboration Framework with Test-Time Scaling [83.78874399606379]
  テスト時間スケーリングを備えたマルチエージェント協調フレームワークであるMACTを提案する。 4つの異なる小規模エージェントから構成され、明確に定義された役割と効果的なコラボレーションがある。 一般および数学的タスクの能力を犠牲にすることなく、より小さなパラメータスケールで優れた性能を示す。
  論文  参考訳（メタデータ） (2025-08-05T12:52:09Z)
• Learning payoffs while routing in skill-based queues [0.4077787659104315]
  我々は,全支払パラメータを適応的に学習し,全支払パラメータを最大化する機械学習アルゴリズムを構築した。 このアルゴリズムは,残差の下限を導出することにより,対数項に最適であることを示す。
  論文  参考訳（メタデータ） (2024-12-13T14:33:50Z)
• Queueing Matching Bandits with Preference Feedback [10.988222071035198]
  我々は、一方のN$キューと他方のK$サーバからなるマルチクラス非対称キューシステムについて検討する。 各ジョブサーバ割り当てのサービスレートは未知であり、機能ベースのMNL(Multi-nomial Logit)関数によってモデル化される。 我々は,UCBとトンプソンサンプリングに基づくアルゴリズムを提案する。このアルゴリズムは,待ち時間の平均値が$O(minN,K/epsilon)$に制限されたシステム安定性を実現する。
  論文  参考訳（メタデータ） (2024-10-14T02:29:06Z)
• Autoregressive Bandits [58.46584210388307]
  本稿では,オンライン学習環境であるAutoregressive Banditsを提案する。 報酬プロセスの軽微な仮定の下では、最適ポリシーを便利に計算できることが示される。 次に、新しい楽観的後悔最小化アルゴリズム、すなわちAutoRegressive Upper Confidence Bound (AR-UCB)を考案し、$widetildemathcalO left( frac(k+1)3/2sqrtnT (1-G)のサブ線形後悔を被る。
  論文  参考訳（メタデータ） (2022-12-12T21:37:36Z)
• Learning to Schedule in Parallel-Server Queues with Stochastic Bilinear Rewards [7.519872646378837]
  本稿では,ジョブサーバの割り当てが不確実なマルチクラス並列サーバシステムにおけるスケジューリングの問題について考察する。 我々の目標は、時間軸上でのジョブサーバ割り当ての累積報酬を最大化することで、後悔を最小限に抑えることです。 提案アルゴリズムは,サブリニア・リセット・バウンドとサブリニア平均保持コストを実現する。
  論文  参考訳（メタデータ） (2021-12-13T00:37:20Z)
• Adversarial Option-Aware Hierarchical Imitation Learning [89.92994158193237]
  提案するOption-GAILは,遠隔地平線でスキルを学ぶための新しい手法である。 Option-GAILの鍵となる考え方は、タスク階層をオプションでモデル化し、生成的敵最適化を通じてポリシーを訓練することである。 実験によると、Option-GAILはさまざまなタスクにおいて、他のタスクよりも一貫してパフォーマンスが向上している。
  論文  参考訳（メタデータ） (2021-06-10T06:42:05Z)
• Dynamic Multi-Robot Task Allocation under Uncertainty and Temporal Constraints [52.58352707495122]
  本稿では,不確実性およびマルチエージェント協調の下での逐次意思決定における重要な計算課題を分離するマルチロボット割当アルゴリズムを提案する。 都市におけるマルチアームコンベヤベルトピック・アンド・プレイスとマルチドローン配送ディスパッチの2つの異なる領域における広範囲なシミュレーション結果について検証を行った。
  論文  参考訳（メタデータ） (2020-05-27T01:10:41Z)
• Learning Algorithms for Minimizing Queue Length Regret [5.8010446129208155]
  パケットはランダムに送信機のキューに到着し、受信機に送信されるのを待ちます。 送信機の目的は、キュー内のパケット数を$T$のタイムスロットで最小化するために、最適なチャネルを素早く識別することである。 順序の最適値O(1)$キュー長の後悔を得られるキュー長ベースのポリシーのセットが存在することを示す。
  論文  参考訳（メタデータ） (2020-05-11T15:50:56Z)

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

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