論文の概要: Online Packet Scheduling with Deadlines and Learning
- arxiv url: http://arxiv.org/abs/2606.00835v1
- Date: Sat, 30 May 2026 18:20:33 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-06-03 00:57:58.925868
- Title: Online Packet Scheduling with Deadlines and Learning
- Title（参考訳）: デッドラインと学習によるオンラインパケットスケジューリング
- Abstract要約: QoS(Quality-of-Service)の保証を行うネットワークルータは、各クロックサイクルにおいて、送信する情報のパケットの有効期限を決定する必要がある。
我々は,この問題を部分フィードバックの下で,デッドライン付きオンラインパケットスケジューリング(OPSD)問題とみなす。
我々は、異なるスラックネスの下で証明可能な$-regret保証を持つアルゴリズムを提供する。
- 参考スコア（独自算出の注目度）: 30.323408304797365
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Network routers that enforce Quality-of-Service (QoS) guarantees must decide, at every clock cycle, which expiring packet of information to transmit, even when the value of the packet is unknown until it is processed. We frame this problem as the Online Packet Scheduling with Deadlines (OPSD) problem under Partial Feedback: packets arrive at every clock cycle, with different deadlines, but the weights are only observed after execution. Under a stochastic assumption on the unknown weights, we explore different variants of the OPSD problem with bandit feedback. We establish a connection between our setting and the sleeping bandits problem, and set our learning goal to $α$-regret minimization. We provide algorithms with provable $α$-regret guarantees under different spans of slackness, distinguishing systems allowing for randomization and systems that do not. In every scenario, our algorithms achieve an $α$-regret upper bound of $\widetilde{\mathcal{O}}\left(\sqrt{KT}\right)$, matching the lower bound for the standard bandit setting. In the practically relevant case of $2$-bounded deadline instances, where the deadline is set at most one clock cycle away from the arrival, our deterministic algorithm achieves the provably tightest possible competitive ratio. Remarkably, when the number of distinct packet types $K\ge 2$ is finite, it is possible to break the well-established $Φ= \frac{1+\sqrt{5}}{2}$ competitive ratio barrier and attain a tighter competitive ratio $θ_K$ ranging in $[\sqrt{2}, Φ)$.
- Abstract（参考訳）: QoS(Quality-of-Service)を保証しているネットワークルータは、処理されるまでパケットの値が不明である場合でも、送信する情報のパケットを有効化するクロックサイクル毎に決定しなければならない。
我々はこの問題を,部分的フィードバックの下でのオンラインパケットスケジューリング(OPSD)問題として,各クロックサイクルにパケットが到着し,期限が異なるが,重みは実行後にのみ観測される。
未知の重みに関する確率論的仮定の下で、帯域フィードバックを伴うOPSD問題の異なる変種を探索する。
睡眠障害と睡眠障害の関連性を確立し,学習目標を$α$-regret最小化に設定する。
我々は、スラックスの異なる範囲で証明可能な$α$-regretを保証するアルゴリズムを提供し、ランダム化が可能なシステムを区別し、そうでないシステムを区別する。
すべてのシナリオにおいて、我々のアルゴリズムは、標準バンディット設定の下位境界と一致する$\widetilde{\mathcal{O}}\left(\sqrt{KT}\right)$の$α$-regret上限を達成する。
デッドラインが到着から1サイクル以上離れている2ドルのデッドラインの場合、決定論的アルゴリズムは、最も厳しい競合率を達成する。
注目すべきは、異なるパケット型である$K\ge 2$の数が有限であるとき、よく確立された$= \frac{1+\sqrt{5}}{2}$の競合比障壁を破り、$[\sqrt{2}, )$の厳しい競合比$θ_K$を得ることができることである。
関連論文リスト
- Online Learning with Probing for Sequential User-Centric Selection [8.45399786458738]
そこで,学習者がまず武器のサブセットを探索して資源や報酬の副次情報を取得し,その後に$K$プレイを$M$アームに割り当てる。
既知の分布を持つオフライン設定に対しては、定数係数近似により $zeta = (e-1)/ (2e-1)$ が保証される。
未知の分布を持つオンライン・セッティングについては、OLPA(Bandit algorithm)を紹介します。
論文 参考訳（メタデータ） (2025-07-27T03:32:51Z) - Learning-Augmented Algorithms for MTS with Bandit Access to Multiple Predictors [0.0]
我々は、$O(text2/3)$の後悔をいかに達成するかを示し、Dekel et al の構成に基づいて、厳密な下限を証明する。
これは、メモリ境界の敵に対する学習に関連している。
論文 参考訳（メタデータ） (2025-06-05T18:00:37Z) - Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
我々は,帯域幅フィードバックを用いたマルチクラスPAC学習について検討し,入力を$K$ラベルの1つに分類し,予測されたラベルが正しいか否かに制限する。
我々の主な貢献は、問題の無知な$(varepsilon,delta)$PACバージョンのための新しい学習アルゴリズムを設計することである。
論文 参考訳（メタデータ） (2024-06-18T08:54:04Z) - Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。
SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
論文 参考訳（メタデータ） (2023-12-13T11:08:25Z) - Context-lumpable stochastic bandits [49.024050919419366]
我々は、$S$コンテキストと$K$アクションによる文脈的盗賊問題を考える。
我々は,最大$widetilde O(r (S +K )/epsilon2)$サンプルを用いて,$epsilon$-optimal Policyを出力するアルゴリズムを提案する。
後悔の設定では、T$までの累積後悔を$widetilde O(sqrtr3(S+K)T)$で束縛するアルゴリズムを与える。
論文 参考訳（メタデータ） (2023-06-22T17:20:30Z) - First- and Second-Order Bounds for Adversarial Linear Contextual Bandits [22.367921675238318]
我々は,K$の腕に付随する損失関数を制限なく時間とともに変化させることができる,逆線形文脈帯域設定を考える。
V_T$ または $L_T*$ は$T$ よりもかなり小さい可能性があるため、環境が比較的良心的であれば、最悪の場合の後悔よりも改善される。
論文 参考訳（メタデータ） (2023-05-01T14:00:15Z) - Probably Anytime-Safe Stochastic Combinatorial Semi-Bandits [81.60136088841948]
本稿では,時間軸における後悔を最小限に抑えるアルゴリズムを提案する。
提案アルゴリズムは,レコメンデーションシステムや交通機関などの分野に適用可能である。
論文 参考訳（メタデータ） (2023-01-31T03:49:00Z) - Corralling a Larger Band of Bandits: A Case Study on Switching Regret
for Linear Bandits [99.86860277006318]
本稿では,一組の逆アルゴリズムを組み合わせ,学習することの問題点について考察する。
Agarwal et al. の CORRAL はこの目標を、$widetildeO(sqrtd S T)$ の残酷なオーバーヘッドで達成している。
この問題に触発されて、後悔のオーバーヘッドが百万ドルにしか依存しない大規模バンディットアルゴリズムのバンドを囲む新しいレシピを提案する。
論文 参考訳（メタデータ） (2022-02-12T21:55:44Z) - Stochastic Bandits with Linear Constraints [69.757694218456]
制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。
楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-17T22:32:19Z) - Contextual Blocking Bandits [35.235375147227124]
我々は,多腕バンディット問題の新たな変種について検討し,各ステップごとに,腕の平均報酬を決定する独立したサンプルコンテキストをプレイヤーが観察する。
アームを再生することで(すべてのコンテキストにわたって)将来の時間ステップの固定および既知の回数をブロックする。
我々は、$mathcalO(log T)$-regret w.r.t.$alpha$regret戦略を$Tタイムステップで保証し、$Omega(log(T)$low boundと一致する UCB ベースのフル情報アルゴリズムの変種を提案する。
論文 参考訳（メタデータ） (2020-03-06T20:34:42Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。