論文の概要: Learning in Strategic Queuing with Geometric Recharge: From Bandits to Systems

• arxiv url: http://arxiv.org/abs/2610.19179v1
• Date: Tue, 13 Oct 2026 20:45:13 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-15 21:06:15.805309
• Title: Learning in Strategic Queuing with Geometric Recharge: From Bandits to Systems
• Title（参考訳）: 幾何学的チャージによる戦略的キューイングの学習:バンドからシステムへ
• Abstract要約: 待ち行列が利己的で、未学習の学習アルゴリズムを用いて未知のサービスレートでサーバを選択するミオピックエージェントであるキューシステムにおいて、パケットルーティングについて検討する。 高確率非回帰学習においてシステムを安定させる最小のオーバープロビジョン係数が$frac11-_max$であることを示す。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study packet routing in queuing systems where queues act as selfish, myopic agents that use no-regret learning algorithms to select servers with unknown service rates. To model the small buffers used in data centers, we assume that each server has a single-packet buffer. Even such a tiny buffer already captures the features of buffering: routers can exploit multiple servers while accepted packets remain in service, but packets can occupy servers for multiple rounds, complicating future service and learning. We first analyze a single queue routing packets to $m$ buffered servers with service rates $μ_1, \dots, μ_m$. This setting is equivalent to an instance of the recharging bandits problem with geometric recharge. We prove that any no-regret learner achieves a long-run average throughput of at least the Hamacher sum of the server rates, and that this bound is tight. Consequently, a single no-regret queue is stable if and only if its arrival rate is below the Hamacher sum of the server rates. Moreover, comparing against an optimal policy, we show that any no-regret learner is at least $0.77$-competitive, which is also tight. We then study multi-queue systems where $n$ queues with arrival rates $λ_1, \dots, λ_n$, each at most $λ_{\max}$, compete for service from $m$ buffered servers. We show that the smallest overprovisioning factor that guarantees the system to be stable under high-probability no-regret learning is $\frac{1}{1-λ_{\max}}$. Equivalently, in terms of the total arrival and service rates, the condition $\sum_{i=1}^n λ_i < (1-λ_{\max})\sum_{j=1}^m μ_j$ is sufficient, and sometimes necessary, for stability under no-regret learning. In particular, for $λ_{\max} = 1/2$, this improves the upper bound of Abel et al. (EC 2026) from $3$ to $2$, matching their lower bound and resolving their open question.
• Abstract（参考訳）: 待ち行列が利己的で、未学習の学習アルゴリズムを用いて未知のサービスレートでサーバを選択するミオピックエージェントであるキューシステムにおいて、パケットルーティングについて検討する。 データセンターで使用される小さなバッファをモデル化するために、各サーバが単一パケットバッファを持っていると仮定する。 ルータは複数のサーバを利用でき、受信したパケットはサービス内に留まるが、パケットは複数のラウンドでサーバを占有し、将来のサービスと学習を複雑にする。 まず、サービスレートが$μ_1, \dots, μ_m$で、単一のキュールーティングパケットを$m$バッファされたサーバにルーティングする。 この設定は、幾何充電を伴う充電バンディット問題の例と同値である。 我々は,非学習者がサーバレートの少なくともハマー和の長時間平均スループットを達成し,この境界がきついことを証明した。 したがって、単一のno-regretキューが安定であることと、その到着率がサーバレートのHaacher和以下であることは同値である。 さらに, 最適政策と比較すると, 未学習者は少なくとも0.77$-競争的であり, これも厳密であることを示す。 次に、到着率$λ_1, \dots, λ_n$のキューが、最大$λ_{\max}$でそれぞれ$m$バッファされたサーバのサービスと競合するマルチキューシステムについて検討する。 高確率非回帰学習において系が安定であることを保証する最小のオーバープロビジョン係数が$\frac{1}{1-λ_{\max}}$であることを示す。 同様に、総到着率とサービス率の面では、条件 $\sum_{i=1}^n λ_i < (1-λ_{\max})\sum_{j=1}^m μ_j$ が十分であり、時には非回帰学習の下での安定性のために必要である。 特に、$λ_{\max} = 1/2$ の場合、これは Abel et al (EC 2026) の上界を 3$ から 2$ に改善し、下界と整合して開問題を解決する。

関連論文リスト

• Lower Bounds for PIR with Preprocessing from Blackbox Cryptography [57.20693707878285]
  プリプロセッシングによるシングルサーバプライベート情報検索(PIR)の限界について検討する。 本研究は,プリプロセッシングを伴うシングルサーバPIRに対して,計算の低いバウンダリを提示する。
  論文  参考訳（メタデータ） (2026-07-07T16:12:48Z)
• Online Packet Scheduling with Deadlines and Learning [30.323408304797365]
  QoS(Quality-of-Service)の保証を行うネットワークルータは、各クロックサイクルにおいて、送信する情報のパケットの有効期限を決定する必要がある。 我々は,この問題を部分フィードバックの下で,デッドライン付きオンラインパケットスケジューリング(OPSD)問題とみなす。 我々は、異なるスラックネスの下で証明可能な$-regret保証を持つアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2026-05-30T18:20:33Z)
• Proving the Limited Scalability of Centralized Distributed Optimization via a New Lower Bound Construction [57.93371273485736]
  我々は、すべての労働者が同一の分布にアクセスする均質な(すなわちd.d.)場合であっても、すべての労働者が非バイアス付き境界 LDeltaepsilon2,$$$$$ のポリ対数的により良いポリ対数を求める集中型分散学習環境を考える。
  論文  参考訳（メタデータ） (2025-06-30T13:27:39Z)
• Analyzing homogenous and heterogeneous multi-server queues via neural networks [0.0]
  我々は,シングルステイトンマルチサーバシステムにおいて,顧客数の定常分布を予測するために,機械学習アプローチを用いる。 システム内の顧客数の定常分布を、$GI/GI_i/2$キューで予測するのは私たちだけです。
  論文  参考訳（メタデータ） (2025-04-01T12:30:18Z)
• Learning in Strategic Queuing Systems with Small Buffers [3.400375586755149]
  ラウンド間の移動効果を持つゲームにおける学習結果を検討する。 ネットワークにおいて重要な例としてルータがあり、単純な学習アルゴリズムを使って、パケットを所望の目的地に届ける最良の方法を見つける。 モデルをよりリアルにし、より高いトラフィック率を可能にする、2つの重要な変更を持つシステムについて検討する。
  論文  参考訳（メタデータ） (2025-02-13T02:23:23Z)
• Queueing Matching Bandits with Preference Feedback [10.988222071035198]
  我々は、一方のN$キューと他方のK$サーバからなるマルチクラス非対称キューシステムについて検討する。 各ジョブサーバ割り当てのサービスレートは未知であり、機能ベースのMNL(Multi-nomial Logit)関数によってモデル化される。 我々は,UCBとトンプソンサンプリングに基づくアルゴリズムを提案する。このアルゴリズムは,待ち時間の平均値が$O(minN,K/epsilon)$に制限されたシステム安定性を実現する。
  論文  参考訳（メタデータ） (2024-10-14T02:29:06Z)
• Federated Combinatorial Multi-Agent Multi-Armed Bandits [79.1700188160944]
  本稿では,Banditを用いたオンライン最適化に適したフェデレーション学習フレームワークを提案する。 この設定では、エージェントのアームサブセットは、個々のアーム情報にアクセスせずにこれらのサブセットに対するノイズの多い報酬を観察し、特定の間隔で協力して情報を共有することができる。
  論文  参考訳（メタデータ） (2024-05-09T17:40:09Z)
• Optimal Algorithms for Latent Bandits with Cluster Structure [50.44722775727619]
  本稿では,複数のユーザが存在するクラスタ構造を持つ潜伏包帯問題と関連するマルチアーム包帯問題とを考察する。 本稿では,潜伏クラスタ構造を利用して$widetildeO(sqrt(mathsfM+mathsfN)mathsfTの最小限の後悔を提供するLATTICEを提案する。
  論文  参考訳（メタデータ） (2023-01-17T17:49:04Z)
• A Simple and Provably Efficient Algorithm for Asynchronous Federated Contextual Linear Bandits [77.09836892653176]
  我々は,M$エージェントが相互に協力して,中央サーバの助けを借りて,グローバルなコンテキスト線形バンドイット問題を解決するためのフェデレーション付きコンテキスト線形バンドイットについて検討した。 すべてのエージェントが独立して動作し、ひとつのエージェントとサーバ間の通信が他のエージェントの通信をトリガーしない非同期設定を考える。 texttFedLinUCBの後悔は$tildeO(dsqrtsum_m=1M T_m)$で、通信の複雑さは$tildeO(dM)であることを示す。
  論文  参考訳（メタデータ） (2022-07-07T06:16:19Z)

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

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