論文の概要: Simultaneous Competitive and Regret Guarantees for TCP Acknowledgment

• arxiv url: http://arxiv.org/abs/2610.13571v1
• Date: Fri, 09 Oct 2026 13:24:38 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-13 04:06:29.59945
• Title: Simultaneous Competitive and Regret Guarantees for TCP Acknowledgment
• Title（参考訳）: TCP認証のための同時競合保証とレギュレット保証
• Abstract要約: TCP認証の競合と後悔の同時保証について検討する。 我々のアルゴリズムは、専門家間のコストを制御し、許容される競争限界と現在のコストとのギャップを利用して、いつ学習を切り替えるかを決定する。
• 参考スコア（独自算出の注目度）: 7.858819231575403
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study simultaneous competitive and regret guarantees for TCP acknowledgment. Each acknowledgment serves all pending packets, and the objective is to minimize the total acknowledgment and waiting costs. It is well known that no deterministic online algorithm achieves a competitive ratio better than $2$. Given $k$ randomized online experts and $0<\varepsilon<1$, we construct a randomized online algorithm whose realized total cost is always at most $(2+\varepsilon)$ times the offline optimal cost $\mathrm{OPT}$ and whose expected regret against the expert with the smallest realized cost is $O(\sqrt{\mathrm{OPT}\log(k+1)}+\log(1/\varepsilon))$. The algorithm requires no advance knowledge of the number of packets or $\mathrm{OPT}$. Our algorithm controls switching costs between experts and uses the gap between the permitted competitive bound and its current cost to determine when to learn. We also prove lower bounds showing that, for $k\ge 2$, this regret bound is asymptotically optimal in $\mathrm{OPT}$, $k$, and $\varepsilon$, and that $\varepsilon>0$ is necessary for sublinear regret.
• Abstract（参考訳）: TCP認証の競合と後悔の同時保証について検討する。 それぞれの承認は、保留中のパケットすべてに役立ち、総承認と待ち時間のコストを最小化することを目的としている。 決定論的オンラインアルゴリズムが2ドル以上の競争率を達成することはよく知られている。 k$のランダム化オンラインエキスパートと$0<\varepsilon<1$のランダム化オンラインアルゴリズムを構築し、その総コストが最大で(2+\varepsilon)$倍のオフライン最適コストが$\mathrm{OPT}$で、最小の実現コストで専門家に対する後悔は$O(\sqrt{\mathrm{OPT}\log(k+1)}+\log(1/\varepsilon)$である。 このアルゴリズムはパケットの数や$\mathrm{OPT}$に関する事前知識を必要としない。 我々のアルゴリズムは、専門家間の切り替えコストを制御し、許容される競争限界と現在のコストとのギャップを利用して、いつ学習するかを決定する。 また、$k\ge 2$ の場合、この後悔境界は $\mathrm{OPT}$, $k$ および $\varepsilon$ において漸近的に最適であり、サブ線形後悔には $\varepsilon>0$ が必要であることを示す下界も証明している。

関連論文リスト

• Learning-Augmented and Randomized Algorithms for Line Aggregation with Delays [7.216833894546792]
  本研究は,オンラインアグリゲーションの学習とランダム化を行間距離で検討する。 for each $in (0,1]$, we propose a deterministic learning-augmented textscBalance algorithm that is $(4/+1/2)$-robust。 また,古典的逆数モデルにおける問題に対する無作為化アルゴリズムを提案し,その逆数に対して$(e+1)$-competitive である。
  論文  参考訳（メタデータ） (2026-07-30T07:47:07Z)
• Fast swap regret minimization and applications to approximate correlated equilibria [20.047624953965965]
  任意の定数$varepsilon>0$に対して、我々のアルゴリズムは$varepsilon T$-swap regretを$T = Mathsfpolylog(n)$ roundsで取得する。 我々のアルゴリズムは$varepsilon$に指数関数的依存を持つが、我々は一致する新しい下界を証明している。
  論文  参考訳（メタデータ） (2023-10-30T15:35:24Z)
• Horizon-free Reinforcement Learning in Adversarial Linear Mixture MDPs [72.40181882916089]
  我々のアルゴリズムが $tildeObig((d+log (|mathcalS|2 |mathcalA|))sqrtKbig)$ regret with full-information feedback, where $d$ is the dimension of a known feature mapping is linearly parametrizing the unknown transition kernel of the MDP, $K$ is the number of episodes, $|mathcalS|$ and $|mathcalA|$ is the standardities of the state and action space。
  論文  参考訳（メタデータ） (2023-05-15T05:37:32Z)
• Private Online Prediction from Experts: Separations and Faster Rates [74.52487417350221]
  専門家によるオンライン予測は機械学習の基本的な問題であり、いくつかの研究がプライバシーの制約の下でこの問題を研究している。 本研究では,非適応的敵に対する最良な既存アルゴリズムの残差を克服する新たなアルゴリズムを提案し,解析する。
  論文  参考訳（メタデータ） (2022-10-24T18:40:19Z)
• Logarithmic Regret from Sublinear Hints [76.87432703516942]
  自然クエリモデルにより,アルゴリズムが$O(log T)$ regretsを$O(sqrtT)$ hintsで得ることを示す。 また、$o(sqrtT)$ hintsは$Omega(sqrtT)$ regretより保証できないことも示しています。
  論文  参考訳（メタデータ） (2021-11-09T16:50:18Z)
• Projection-free Distributed Online Learning with Strongly Convex Losses [37.08975118221237]
  損失関数の強い凸性を利用して、後悔と通信の複雑さを改善する。 本アルゴリズムは多対数因子に縛られた$o(t2/3log t)$ regretを得るのにほぼ最適である。
  論文  参考訳（メタデータ） (2021-03-20T05:38:51Z)
• Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
  我々は,バンディットフィードバックを用いてオンライン学習を学習する。 learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。 我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。 ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
  論文  参考訳（メタデータ） (2021-02-15T08:16:51Z)
• Revisiting Smoothed Online Learning [70.09792747315323]
  オンライン学習者がヒットコストとスイッチングコストの両方に苦しむスムーズなオンライン学習の問題を調査します。 競争比を縛るために、各ラウンドで打つコストが学習者に知られていると仮定し、打つコストと切り換えコストの重み付け合計を単純に最小化する勾配アルゴリズムを調査します。
  論文  参考訳（メタデータ） (2021-02-13T14:15:55Z)

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

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