論文の概要: Beyond Peak Backlog: Conditional Energy and Temporal Geometry in Capacity-Constrained Delayed Bandit Optimization
- arxiv url: http://arxiv.org/abs/2608.16216v1
- Date: Mon, 17 Aug 2026 07:49:51 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-08-18 19:59:03.581634
- Title: Beyond Peak Backlog: Conditional Energy and Temporal Geometry in Capacity-Constrained Delayed Bandit Optimization
- Title（参考訳）: ピークバックログを超えて:容量制約遅延帯域最適化における条件エネルギーと時間幾何学
- Abstract要約: 本研究では,1点摂動フィルタからレート適応を分離するスケジューラ側条件エネルギーインタフェースを提案する。
同一の遅延多重集合を持つ2つの遅延ベクトル、$d_mathrmtot$、$_max$、キャパシティは、にもかかわらず、累積タイミングが曲率の下で重要であることを示す極端に異なるミニマックス後悔を持つことができる。
- 参考スコア（独自算出の注目度）: 11.872017840435428
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: What is the right delay complexity when a learner can track only $C$ pending feedback items and discarded feedback is permanently lost? Existing one-point bandit convex optimization guarantees in this model pay $\sqrt{Tσ_{\max}}$, where $σ_{\max}$ is the peak backlog, although unlimited tracking admits the sharper $\sqrt{d_{\mathrm{tot}}}$ dependence on total delay. We introduce a scheduler-side conditional-energy interface that separates rate adaptation from the one-point perturbation filtration and handles the dependent importance weights created by randomized admission. Under the same semi-clairvoyant oracle and pathwise hard-capacity contract, this yields an untuned learner whose delay term scales as $O(\sqrt{E_C d_{\mathrm{tot}}})$, with only an explicit restart factor $E_C$; a public constant-factor peak bound removes this factor while $d_{\mathrm{tot}}$ remains unknown. Under strong convexity, the same interface yields the temporal cost $H_A(d)=\sum_t σ_t/(A+t)$. Two delay vectors with identical delay multisets, $d_{\mathrm{tot}}$, $σ_{\max}$, and capacity can nevertheless have polynomially different minimax regret, showing that timing matters under curvature even when aggregate delay summaries agree. Finally, a continuous hard family converts tracking capacity into a zeroth-order query budget and gives a complementary capacity-starvation lower endpoint. The upper bounds require $C\ge \ln T+1$ and do not constitute a complete capacity minimax characterization.
- Abstract（参考訳）: 学習者が保留中のフィードバック項目のみを追跡でき、破棄されたフィードバックが永久に失われる場合、適切な遅延複雑性はどのようなものでしょう?
既存のワンポイントバンディット凸最適化はこのモデルでは$\sqrt{Tσ_{\max}}$、$σ_{\max}$はピークバックログであるが、無制限のトラッキングは、よりシャープな$\sqrt{d_{\mathrm{tot}}}$への依存を許容する。
本研究では,1点摂動フィルタからレート適応を分離するスケジューラ側条件エネルギーインタフェースを導入し,ランダム化入力によって生じる重み付けを処理した。
同じ半クレアボイトオラクルとパスワイズハードキャパシティ契約の下で、これは遅延項が$O(\sqrt{E_C d_{\mathrm{tot}}})$とスケールする未修正の学習者を得る。
強い凸性の下では、同じインターフェースは時間費用$H_A(d)=\sum_t σ_t/(A+t)$となる。
同一の遅延多重集合を持つ2つの遅延ベクトル、$d_{\mathrm{tot}}$, $σ_{\max}$, and capacity は、にもかかわらず多項式的に異なるミニマックス後悔を持つことができ、集合遅延サマリーが一致する場合でも、タイミングが曲率の下で重要であることを示す。
最後に、連続ハードファミリーは、トラッキング能力をゼロ階のクエリ予算に変換し、補完的なキャパシティ飢餓の低いエンドポイントを提供する。
上界は$C\ge \ln T+1$を必要とし、完全なキャパシティのミニマックスキャラクタリゼーションを構成しない。
関連論文リスト
- Constrained Online Learning with Noisy Constraint Values [55.29259818039367]
一般的な実現可能性の下では、我々のLEDGERアルゴリズムは、期待される損失$O(sqrt T)と期待される予算違反$O(sqrtTlog(eT))を達成します。
スレーター条件、フィードバックチャネル間の独立性、絶対的制約値境界は不要である。
論文 参考訳（メタデータ） (2026-09-07T01:38:41Z) - Toward the Optimal Regret-Instability Trade-off in Multi-Armed Bandits [13.075031222564535]
マルチアームのバンディットアルゴリズムは、後悔によって評価されるが、同等の後悔は、独立ラン毎に異なるアロケーションと共存することができる。
我々は、最低ケースの後悔$mathcalR_K,T$と不安定$mathcalS_K,T$のトレードオフを、端末プルカウントの最大の標準偏差として定義し、$K$アームと$T$ラウンドについて検討する。
論文 参考訳（メタデータ） (2026-08-18T14:38:47Z) - From Approachability Residuals to Anytime-Valid Evidence: The Online Convex Geometry of Testing by Betting [0.1624454100511275]
ギャンブリングベースのシーケンシャルテストとブラックウェルのアプローチ性は、支持関数による比例還元によってリンクされる。
正確な経路単位は$$dist(bar r_T,S) =frac1Tsum_t=1Tq_t+fracReg_TTである。
論文 参考訳（メタデータ） (2026-08-10T11:23:30Z) - Asymptotically Optimal Regret for Reinforcement Learning without Horizon Dependence [54.59847568544922]
有限水平時間同質なマルコフ決定過程に対して、$A$状態、$A$アクション、hoighty $H$、および1ドルで有界なトラジェクティブ当たりの合計報酬について、地平自由な後悔について検討する。
失敗確率$$K$はエピソード数で$tilde O(sqrtSAK+S3K)$ hides $mathsfpolyである。
論文 参考訳（メタデータ） (2026-07-22T07:42:19Z) - Capacity-Constrained Online Convex Optimization with Delayed Feedback [58.59385794080679]
容量制約下での遅延オンライン凸最適化(OCO)について検討した。
1次フィードバックの場合、容量$C = (log T)$ sufficesで標準遅延OCOレートを対数係数まで回復できることがわかった。
包帯フィードバックの場合、後悔率は$(1 + _textmax/C)$で変調される。
論文 参考訳（メタデータ） (2026-06-10T06:37:06Z) - A Reduction from Delayed to Immediate Feedback for Online Convex Optimization with Improved Guarantees [58.59385794080679]
本稿では,後悔を遅延非依存の学習項と遅延誘発のドリフト項に分解する連続時間モデルを提案する。
バンディット凸最適化では,最先端の1次数に適合する遅延依存項を用いて,既存の残差境界を大幅に改善する。
論文 参考訳（メタデータ） (2026-02-02T18:17:34Z) - Exploiting Curvature in Online Convex Optimization with Delayed Feedback [6.390468088226495]
曲面損失と遅延フィードバックを用いたオンライン凸最適化問題について検討する。
次数$minsigma_maxln T, sqrtd_mathrmtot$を後悔する規則化リーダの変種を提案する。
次に、exp-concave損失を検討し、適応的な学習率チューニングで遅延を処理するためにOnline Newton Stepアルゴリズムを拡張した。
論文 参考訳（メタデータ） (2025-06-09T09:49:54Z) - Capacity-Constrained Online Learning with Delays: Scheduling Frameworks and Regret Trade-offs [60.7808741738461]
我々は,遅れたフィードバックのために,過去のラウンドを同時に追跡できる回数を制限する,斬新な「透明さ」の下で,難解な遅延を伴うオンライン学習について研究する。
我々のアルゴリズムは、全てのキャパシティレベルにおいてミニマックスの後悔を達成し、性能は最適以下のキャパシティで優雅に低下する。
論文 参考訳（メタデータ） (2025-03-25T17:20:39Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。