論文の概要: Finite-Time Information-Theoretic Bounds in Queueing Control
- arxiv url: http://arxiv.org/abs/2506.18278v1
- Date: Mon, 23 Jun 2025 04:14:40 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-06-26 21:00:42.447848
- Title: Finite-Time Information-Theoretic Bounds in Queueing Control
- Title（参考訳）: 待ち行列制御における有限時間情報理論境界
- Authors: Yujie Liu, Vincent Y. F. Tan, Yunbei Xu,
- Abstract要約: 本稿では, 待ち行列の待ち行列を, 待ち行列と待ち行列の双方で処理するネットワーク上のスケジューリング問題において, 待ち行列の総長を求める新しいポリシーを導出する。
これらの結果は「ドリフトオンリー」な手法の基本的な制限を明らかにし、待ち行列制御における原則的、非漸近的最適性への道を示す。
- 参考スコア（独自算出の注目度）: 54.11376591632282
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We establish the first finite-time information-theoretic lower bounds-and derive new policies that achieve them-for the total queue length in scheduling problems over stochastic processing networks with both adversarial and stochastic arrivals. Prior analyses of MaxWeight guarantee only stability and asymptotic optimality in heavy traffic; we prove that, at finite horizons, MaxWeight can incur strictly larger backlog by problem-dependent factors which we identify. Our main innovations are 1) a minimax framework that pinpoints the precise problem parameters governing any policy's finite-time performance; 2) an information-theoretic lower bound on total queue length; 3) fundamental limitation of MaxWeight that it is suboptimal in finite time; and 4) a new scheduling rule that minimizes the full Lyapunov drift-including its second-order term-thereby matching the lower bound under certain conditions, up to universal constants. These findings reveal a fundamental limitation on "drift-only" methods and points the way toward principled, non-asymptotic optimality in queueing control.
- Abstract（参考訳）: 我々は、最初の有限時間情報理論の下界を確立し、それを実現するための新しいポリシーを導出する。
重交通における安定性と漸近的最適性のみを保証し、有限地平線において、マックスウェイトが特定する問題依存因子によって厳密に大きなバックログを創出できることを証明した。
私たちの主なイノベーションは
1) 政策の有限時間性能を規定する正確な問題パラメータをピンポイントするミニマックスフレームワーク
2 総待ち時間における情報理論の下限
3) MaxWeight の基本的制限は、有限時間において最適以下であること、そして
4) 完全なリアプノフドリフトを最小化する新しいスケジューリング規則。
これらの結果は「ドリフトオンリー」な手法の基本的な限界を明らかにし、待ち行列制御における原則的、非漸近的最適性への道を示す。
関連論文リスト
- Beyond Primal-Dual Methods in Bandits with Stochastic and Adversarial Constraints [29.514323697659613]
我々は,学習者が任意の長期制約を満たすことなく報酬を最大化することを目的とした,knapsacks問題によるバンディットの一般化に対処する。
私たちのゴールは、双方の制約の下で機能するベスト・オブ・ザ・ワールドのアルゴリズムを設計することです。
論文 参考訳（メタデータ） (2024-05-25T08:09:36Z) - Online Non-convex Optimization with Long-term Non-convex Constraints [2.033434950296318]
Follow-the-Perturbed-Leader型アルゴリズムを提案する。
提案アルゴリズムは,長期(極値)制約のある河川汚染源同定問題に対処するために適用された。
論文 参考訳（メタデータ） (2023-11-04T15:08:36Z) - Pessimistic Minimax Value Iteration: Provably Efficient Equilibrium
Learning from Offline Datasets [101.5329678997916]
両プレイヤーゼロサムマルコフゲーム(MG)をオフライン環境で研究する。
目標は、事前収集されたデータセットに基づいて、近似的なナッシュ均衡(NE)ポリシーペアを見つけることである。
論文 参考訳（メタデータ） (2022-02-15T15:39:30Z) - Faster Algorithm and Sharper Analysis for Constrained Markov Decision
Process [56.55075925645864]
制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。
新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。
これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
論文 参考訳（メタデータ） (2021-10-20T02:57:21Z) - Finite Sample Analysis of Minimax Offline Reinforcement Learning:
Completeness, Fast Rates and First-Order Efficiency [83.02999769628593]
強化学習におけるオフ・ポリティィ・アセスメント(OPE)の理論的特徴について述べる。
ミニマックス法により、重みと品質関数の高速収束を実現することができることを示す。
非タブラル環境における1次効率を持つ最初の有限サンプル結果を示す。
論文 参考訳（メタデータ） (2021-02-05T03:20:39Z) - An Asymptotically Optimal Primal-Dual Incremental Algorithm for
Contextual Linear Bandits [129.1029690825929]
複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。
非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
論文 参考訳（メタデータ） (2020-10-23T09:12:47Z) - On Lower Bounds for Standard and Robust Gaussian Process Bandit
Optimization [55.937424268654645]
有界ノルムを持つ関数のブラックボックス最適化問題に対するアルゴリズム非依存な下界を考える。
本稿では, 単純さ, 汎用性, エラー確率への依存性の向上など, 後悔の下位境界を導出するための新しい証明手法を提案する。
論文 参考訳（メタデータ） (2020-08-20T03:48:14Z) - Simulating extremal temporal correlations [0.0]
単一の量子系上の逐次測定から生じる相関は、ポリトープを形成する。
これはアロー・オブ・タイム(AoT)の制約によって定義されます。
本稿では,AoTポリトープの極端点をシミュレートするために必要な資源について論じる。
論文 参考訳（メタデータ） (2020-04-30T15:07:17Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。