論文の概要: Capacity-Constrained Online Learning with Delays: Scheduling Frameworks and Regret Trade-offs

• arxiv url: http://arxiv.org/abs/2503.19856v1
• Date: Tue, 25 Mar 2025 17:20:39 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-03-26 16:52:07.896309
• Title: Capacity-Constrained Online Learning with Delays: Scheduling Frameworks and Regret Trade-offs
• Title（参考訳）: 遅延を伴う容量制約付きオンライン学習:スケジューリングフレームワークとレグレトトレードオフ
• Authors: Alexander Ryabchenko, Idan Attias, Daniel M. Roy,
• Abstract要約: 我々は,遅延フィードバックのために,過去のラウンドを同時に追跡できる回数を制限する新しい「透明度」の下で,目立った損失の遅延を伴ってオンライン学習を研究する。 我々のアルゴリズムは、全てのキャパシティレベルにおいて、最適以下のキャパシティの優雅な性能で、最小最適後悔を実現する。
• 参考スコア（独自算出の注目度）: 60.7808741738461
• License:
• Abstract: We study online learning with oblivious losses and delays under a novel ``capacity constraint'' that limits how many past rounds can be tracked simultaneously for delayed feedback. Under ``clairvoyance'' (i.e., delay durations are revealed upfront each round) and/or ``preemptibility'' (i.e., we have ability to stop tracking previously chosen round feedback), we establish matching upper and lower bounds (up to logarithmic terms) on achievable regret, characterizing the ``optimal capacity'' needed to match the minimax rates of classical delayed online learning, which implicitly assume unlimited capacity. Our algorithms achieve minimax-optimal regret across all capacity levels, with performance gracefully degrading under suboptimal capacity. For $K$ actions and total delay $D$ over $T$ rounds, under clairvoyance and assuming capacity $C = \Omega(\log(T))$, we achieve regret $\widetilde{\Theta}(\sqrt{TK + DK/C + D\log(K)})$ for bandits and $\widetilde{\Theta}(\sqrt{(D+T)\log(K)})$ for full-information feedback. When replacing clairvoyance with preemptibility, we require a known maximum delay bound $d_{\max}$, adding $\smash{\widetilde{O}(d_{\max})}$ to the regret. For fixed delays $d$ (i.e., $D=Td$), the minimax regret is $\Theta\bigl(\sqrt{TK(1+d/C)+Td\log(K)}\bigr)$ and the optimal capacity is $\Theta(\min\{K/\log(K),d\}\bigr)$ in the bandit setting, while in the full-information setting, the minimax regret is $\Theta\bigl(\sqrt{T(d+1)\log(K)}\bigr)$ and the optimal capacity is $\Theta(1)$. For round-dependent and fixed delays, our upper bounds are achieved using novel scheduling policies, based on Pareto-distributed proxy delays and batching techniques. Crucially, our work unifies delayed bandits, label-efficient learning, and online scheduling frameworks, demonstrating that robust online learning under delayed feedback is possible with surprisingly modest tracking capacity.
• Abstract（参考訳）: 我々は、遅延フィードバックのために、過去のラウンドを同時に追跡できる回数を制限する新しい「容量制約」の下で、目立たない損失と遅延を伴ってオンライン学習を研究する。 例えば、'clairvoyance'(各ラウンドの遅延期間)と'/または'preemptibility'(事前に選択されたラウンドフィードバックを追跡するのをやめる能力)の下で、私たちは、古典的な遅延オンライン学習のミニマックスレートに合わせるのに必要な'\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\ \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\の「。 提案アルゴリズムは,全キャパシティレベルの最小最適後悔を達成し,性能を最適以下のキャパシティで優雅に劣化させる。 K$アクションと総遅延$D$ overT$ラウンドの場合、透視とキャパシティを仮定して$C = \Omega(\log(T))$の場合、後悔の$\widetilde{\Theta}(\sqrt{TK + DK/C + D\log(K)})$ for bandits and $\widetilde{\Theta}(\sqrt{(D+T)\log(K)})$ for full-information feedback。 clairvoyanceをプリエンプティビティに置き換えるには、既知の最大遅延を$d_{\max}$に制限し、後悔に対して$\smash{\widetilde{O}(d_{\max})}$を追加する必要がある。 固定遅延$d$(つまり$D=Td$)の場合、ミニマックス後悔は$\Theta\bigl(\sqrt{TK(1+d/C)+Td\log(K)}\bigr)$、最適容量は$\Theta(\min\{K/\log(K),d\}\bigr)$、全情報設定では$\Theta\bigl(\sqrt{T(d+1)\log(K)}\bigr)$、最適容量は$\Theta(1)$である。 ラウンド依存および固定遅延に対しては、パレート分散プロキシ遅延とバッチ化技術に基づいて、新しいスケジューリングポリシーを用いて上限値が達成される。 重要なことに、当社の作業は遅延帯域幅、ラベル効率のよい学習、オンラインスケジューリングフレームワークを統一し、遅延フィードバックの下で堅牢なオンライン学習が可能であることを実証しています。

関連論文リスト

• Improved Regret for Bandit Convex Optimization with Delayed Feedback [50.46856739179311]
  遅延フィードバックを伴うバンド凸最適化(BCO)。 我々は,新しいアルゴリズムを開発し,一般にO(sqrtnT3/4+sqrtdT)$の後悔境界を満足していることを証明する。 提案アルゴリズムは,強い凸関数に対して$O((nT)2/3log/3T+dlog T)$に制限された後悔を改善することができることを示す。
  論文  参考訳（メタデータ） (2024-02-14T13:08:26Z)
• Near-Optimal Regret Bounds for Multi-batch Reinforcement Learning [54.806166861456035]
  本研究では,有限水平マルコフ決定過程(MDP)によってモデル化されたエピソディック強化学習(RL)問題をバッチ数に制約を加えて検討する。 我々は,$tildeO(sqrtSAH3Kln (1/delta))$tildeO(cdot)をほぼ最適に後悔するアルゴリズムを設計し,$(S,A,H,K)$の対数項を$K$で隠蔽する。 技術的貢献は2つある: 1) 探索のためのほぼ最適設計スキーム
  論文  参考訳（メタデータ） (2022-10-15T09:22:22Z)
• A Best-of-Both-Worlds Algorithm for Bandits with Delayed Feedback [25.68113242132723]
  本稿では,Zimmert と Seldin [2020] のアルゴリズムを,フィードバックの遅れによる逆方向の多重武装バンディットに対して修正したチューニングを行う。 我々は,時間的遅れのある設定において,ほぼ最適の相反的後悔の保証を同時に達成する。 また,任意の遅延の場合に対するアルゴリズムの拡張も提案する。
  論文  参考訳（メタデータ） (2022-06-29T20:49:45Z)
• Complete Policy Regret Bounds for Tallying Bandits [51.039677652803675]
  政策後悔は、適応的な敵に対してオンライン学習アルゴリズムのパフォーマンスを測定するという、よく確立された概念である。 我々は,不完全な政策後悔を効果的に最小化できる敵の制限について検討する。 我々は、$tildemathcalO(mKsqrtT)$の完全なポリシーを後悔するアルゴリズムを提供し、$tildemathcalO$表記は対数要素だけを隠す。
  論文  参考訳（メタデータ） (2022-04-24T03:10:27Z)
• Scale-Free Adversarial Multi-Armed Bandit with Arbitrary Feedback Delays [21.94728545221709]
  制限のないフィードバック遅延を伴うMAB(Scale-Free Adversarial Multi Armed Bandit)問題を考える。 textttSFBankerは$mathcal O(sqrtK(D+T)L)cdot rm polylog(T, L)$ total regret, where $T$ is the total number of steps, $D$ is the total feedback delay。
  論文  参考訳（メタデータ） (2021-10-26T04:06:51Z)
• Almost Optimal Batch-Regret Tradeoff for Batch Linear Contextual Bandits [45.43968161616453]
  バッチ線形文脈帯域に対する最適バッチ-regretトレードオフについて検討する。 時間的地平線が成長するにつれて2相表現を特徴とする後悔の保証を証明します。 また, 動的上界に依存した新しい行列不等式濃度を証明した。
  論文  参考訳（メタデータ） (2021-10-15T12:32:33Z)
• Minimax Regret for Stochastic Shortest Path [63.45407095296692]
  我々は、エージェントが最小の総予想コストで目標状態に達する必要がある最短パス(SSP)問題を研究します。 この設定に対するminimaxの後悔は、$widetilde O(B_star sqrt|S| |A|K)$であり、$B_star$は任意の状態から最適なポリシーの予想コストに拘束されることを示しています。 本アルゴリズムは, 有限水平MDPにおける強化学習の新たな削減を基礎として, エピソードごとのインタイム動作を行う。
  論文  参考訳（メタデータ） (2021-03-24T10:11:49Z)
• Online Convex Optimization with Continuous Switching Constraint [78.25064451417082]
  連続的なスイッチング制約を伴うオンライン凸最適化の問題を紹介する。 強い凸関数の場合、後悔境界は$O(log T)$ for $S=Omega(log T)$、$O(minT/exp(S)+S,T)$ for $S=O(log T)$に改善できることを示す。
  論文  参考訳（メタデータ） (2021-03-21T11:43:35Z)
• Adapting to Delays and Data in Adversarial Multi-Armed Bandits [7.310043452300736]
  決定時に利用可能な情報のみを用いてステップサイズを調整するExp3アルゴリズムの変種を分析する。 我々は、観測された(最悪の場合ではなく)遅延や損失のシーケンスに適応する後悔の保証を得る。
  論文  参考訳（メタデータ） (2020-10-12T20:53:52Z)

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

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