論文の概要: A Parameter-Free Best-of-Both-Worlds Policy for Queueing Bandits

• arxiv url: http://arxiv.org/abs/2611.02431v1
• Date: Mon, 02 Nov 2026 02:54:20 GMT
• ステータス: 情報取得中
• システム内更新日: 2026-11-03 19:34:15.004381
• Title: A Parameter-Free Best-of-Both-Worlds Policy for Queueing Bandits
• Title（参考訳）: 帯域待ちのためのパラメータフリーBest-of-Both-Worldsポリシー
• Abstract要約: 我々は,帯域幅フィードバックの下で,1つのキューに対してK$チャネルを提供するオンラインチャネルスケジューリングについて検討した。 本稿では,キューが空になった時を探索するベスト・オブ・ワールド・ポリシーを提案する。 難解な敵によって決定される任意の到着やサービスに対して、我々のポリシーは、高い確率で$tildemathcalO(sqrtK L_T)$ worst-case queue length regretを達成します。
• 参考スコア（独自算出の注目度）: 4.262693522975888
• License:
• Abstract: We study online channel scheduling for a single queue served by $K$ channels under bandit feedback. We propose a simple best-of-both-worlds policy that explores when the queue is empty. During busy periods, it selects the empirical best channel while the prescribed conditions hold and, if any condition is violated, switches to a robust bandit policy to clear the queue. For arbitrary arrivals and services determined by an oblivious adversary, our policy achieves $\tilde{\mathcal{O}}(\sqrt{K L_T})$ worst-case queue length regret with high probability, where $L_T$ is the longest busy-period length. This result improves the previous $T^{3/4}$ dependence and matches the worst-case lower bound up to logarithmic factors. Under bounded i.i.d. stochastic models with a unique best stabilizing channel, we show that the cumulative queue length regret converges to a finite problem-dependent constant, and further establish the logarithmic expected worst-case queue length regret bound.
• Abstract（参考訳）: 我々は,帯域幅フィードバックの下で,1つのキューに対してK$チャネルを提供するオンラインチャネルスケジューリングについて検討した。 本稿では,キューが空になった時を探索する,シンプルなベスト・オブ・ザ・ワールドズ・ポリシーを提案する。 忙しい期間に、所定の条件が保たれている間に経験的最良のチャンネルを選択し、条件が破られた場合、待ち行列をクリアするために堅牢なバンディットポリシーに切り替える。 不可解な敵によって決定される任意の到着とサービスに対して、我々のポリシーは、高い確率で最悪のキュー長を後悔する$\tilde{\mathcal{O}}(\sqrt{K L_T})を達成します。 この結果は、以前の$T^{3/4}$依存を改善し、最悪の場合の対数係数に一致する。 最適な安定化チャネルを持つ有界確率モデルの下では、累積待ち行列長後悔は有限問題依存定数に収束し、さらに対数的に予測される最悪の待ち行列長後悔境界を確立する。

関連論文リスト

• Learning While Scheduling Jobs under Context-Dependent Service Rates: An Anytime Rate-Optimal Algorithm [1.0098114696565863]
  我々は、学習者が未知のサービスレートを学習しながらジョブをスケジュールするコンテキスト待ち行列の帯域について研究する。 WISE(Widest Interval Selection with Elimination)を提案する。
  論文  参考訳（メタデータ） (2026-10-05T09:02:51Z)
• Constrained Online Learning with Noisy Constraint Values [55.29259818039367]
  一般的な実現可能性の下では、我々のLEDGERアルゴリズムは、期待される損失$O(sqrt T)と期待される予算違反$O(sqrtTlog(eT))を達成します。 スレーター条件、フィードバックチャネル間の独立性、絶対的制約値境界は不要である。
  論文  参考訳（メタデータ） (2026-09-07T01:38:41Z)
• Algorithm for Contextual Queueing Bandits with Rate-Optimal Queue Length Regret [1.0098114696565863]
  待ち時間後悔は、学習者の待ち時間とオラクルの待ち時間の間に期待される差として定義される。 本稿では,この値を$widetildemathcalO(T-1/2)$に改善する。
  論文  参考訳（メタデータ） (2026-06-08T15:51:25Z)
• 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)
• Finite-Time Information-Theoretic Bounds in Queueing Control [54.11376591632282]
  本稿では, 待ち行列の待ち行列を, 待ち行列と待ち行列の双方で処理するネットワーク上のスケジューリング問題において, 待ち行列の総長を求める新しいポリシーを導出する。 これらの結果は「ドリフトオンリー」な手法の基本的な制限を明らかにし、待ち行列制御における原則的、非漸近的最適性への道を示す。
  論文  参考訳（メタデータ） (2025-06-23T04:14:40Z)
• Continuous K-Max Bandits [54.21533414838677]
  我々は、連続的な結果分布と弱い値-インデックスフィードバックを持つ、$K$-Maxのマルチアームバンディット問題について検討する。 この設定は、レコメンデーションシステム、分散コンピューティング、サーバスケジューリングなどにおいて重要なアプリケーションをキャプチャします。 我々の重要な貢献は、適応的な離散化とバイアス補正された信頼境界を組み合わせた計算効率の良いアルゴリズムDCK-UCBである。
  論文  参考訳（メタデータ） (2025-02-19T06:37:37Z)
• Minimizing Queue Length Regret for Arbitrarily Varying Channels [9.091372562683311]
  任意に変化する無線チャネルをN$で備えた単一送受信機対のオンラインチャネルスケジューリング問題を考える。 チャネルの送信速度は非定常的であり、不可避な敵によって制御される可能性がある。 本稿では,この設定における待ち行列長の最小化のために,弱適応型マルチアーマッド帯域幅(MAB)アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-01-23T10:54:22Z)
• Non-stationary Delayed Online Convex Optimization: From Full-information to Bandit Setting [71.82716109461967]
  遅延勾配が利用できる全情報ケースに対して Mild-OGD というアルゴリズムを提案する。 ミルド-OGDのダイナミックな後悔は、順番の仮定の下で$O(sqrtbardT(P_T+1))$で自動的に束縛されることを示す。 Mild-OGDのバンディット版も開発し,損失値の遅れのみを考慮に入れた,より困難なケースについて検討した。
  論文  参考訳（メタデータ） (2023-05-20T07:54:07Z)
• Fast Rates for the Regret of Offline Reinforcement Learning [69.23654172273085]
  無限水平割引決定プロセス(MDP)における固定行動ポリシーによって生成されたオフラインデータからの強化学習の後悔について検討する。 最適品質関数 $Q*$ に対する任意の推定が与えられたとき、定義するポリシーの後悔は、$Q*$-estimate の点収束率の指数によって与えられる速度で収束することを示す。
  論文  参考訳（メタデータ） (2021-01-31T16:17:56Z)
• Stochastic Bandits with Linear Constraints [69.757694218456]
  制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。 楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-17T22:32:19Z)
• Learning Algorithms for Minimizing Queue Length Regret [5.8010446129208155]
  パケットはランダムに送信機のキューに到着し、受信機に送信されるのを待ちます。 送信機の目的は、キュー内のパケット数を$T$のタイムスロットで最小化するために、最適なチャネルを素早く識別することである。 順序の最適値O(1)$キュー長の後悔を得られるキュー長ベースのポリシーのセットが存在することを示す。
  論文  参考訳（メタデータ） (2020-05-11T15:50:56Z)

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

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