論文の概要: Online Resource Allocation with Continuous Random Consumption: Regret under Degeneracy

• arxiv url: http://arxiv.org/abs/2607.02196v1
• Date: Thu, 02 Jul 2026 14:04:21 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-07-03 19:45:08.864073
• Title: Online Resource Allocation with Continuous Random Consumption: Regret under Degeneracy
• Title（参考訳）: 連続的ランダム消費を伴うオンライン資源配分:縮退下でのレグレト
• Authors: Jiawei Zhang,
• Abstract要約: 報酬と消費の双方が継続的に分配される場合のオンラインリソース割り当てについて検討する。 付加的後悔は, 有効受容遮断の近傍に値対サイズ比が有する要求の大きさ重み付けの質量によって支配されることを示す。
• 参考スコア（独自算出の注目度）: 7.379474076344059
• License: http://creativecommons.org/publicdomain/zero/1.0/
• Abstract: We study online resource allocation when both rewards and consumption sizes may be continuously distributed. Requests arrive sequentially and must be accepted or rejected irrevocably under fixed resource capacities. Each request belongs to one of finitely many observable types; conditional on an observable request type, both the reward and the scalar size are random, and the realized size scales a fixed type-specific resource-consumption vector. The model allows the deterministic fluid relaxation to be degenerate. We show that additive regret is governed by the size-weighted mass of requests whose value-to-size ratios lie near the active acceptance cutoffs. We formalize this quantity through an active weighted-mass exponent p. When p > 1, this cutoff mass is thin, and the problem is genuinely hard: every online policy must incur regret of order at least $T^{1/2 - 1/(2p)}$, and this holds for every p > 1. A sample-path marginal policy matches this lower bound up to polylogarithmic factors; and when p = 1, so that the mass grows linearly near the cutoff, it attains $O((\log T)^2)$ regret. For example, if the size and the value-to-size ratio are independent and uniformly distributed, then p = 1; if instead the size and the reward are independent and uniformly distributed, then p = 2. Thus the policy achieves $o(\sqrt{T})$ regret throughout this regularity class without any fluid non-degeneracy assumption, allowing both primal degeneracy and dual non-uniqueness.
• Abstract（参考訳）: 報酬と消費の双方が継続的に分配される場合のオンラインリソース割り当てについて検討する。 要求はシーケンシャルに届き、固定されたリソース容量で不当に受け入れられるか、拒否されなければならない。 各リクエストは、有限個の観測可能なタイプの1つに属し、観測可能な要求タイプでは、報酬とスカラーサイズの両方がランダムであり、実現されたサイズは、固定されたタイプ固有のリソース消費ベクトルをスケールする。 このモデルは、決定論的流体緩和を退化させる。 付加的後悔は, 有効受容遮断の近傍に値対サイズ比が有する要求の大きさ重み付けの質量によって支配されることを示す。 我々はこの量を活性重み付き質量指数 p で定式化する。 p > 1 のとき、このカットオフ質量は薄く、問題は真に難しい: すべてのオンラインポリシーは少なくとも少なくとも$T^{1/2 - 1/(2p)}$を後悔し、これはすべての p > 1. に対して成り立つ。 例えば、サイズと値対サイズ比が独立で均一に分布しているなら、p = 1; 代わりにサイズと報酬が独立で均一に分布しているなら、p = 2 となる。

関連論文リスト

• Self-Normalized Martingales and Uniform Regret Bounds for Linear Regression [65.82017723631897]
  自己正規化マルティンガレのスケール不変上界が可能であることを示す。 通常の正規化ペナルティを含まない自己正規化濃度不等式を導出する。
  論文  参考訳（メタデータ） (2026-05-02T22:39:00Z)
• Regularized Online RLHF with Generalized Bilinear Preferences [68.44113000390544]
  一般的な嗜好を伴う文脈的オンラインRLHFの問題を考える。 一般化された双線形選好モデルを用いて、低ランクなスキュー対称行列による選好を捉える。 グリーディポリシーの双対ギャップは推定誤差の正方形によって有界であることを示す。
  論文  参考訳（メタデータ） (2026-02-26T15:27:53Z)
• The Rate-Distortion-Perception Trade-off: The Role of Private Randomness [53.81648040452621]
  圧縮速度がソースのエントロピーよりも低い場合、プライベートなランダム性は役に立たないことを示す。 圧縮速度がソースのエントロピーよりも低い場合, プライベートなランダム性が有用でないことを示す。
  論文  参考訳（メタデータ） (2024-04-01T13:36:01Z)
• Allocating Divisible Resources on Arms with Unknown and Random Rewards [25.93048671326331]
  我々は、各期間に複数の武器で再生可能資源の1単位を割り当てる意思決定者について検討する。 アームは未知でランダムな報酬であり、その手段は割り当てられたリソースに比例し、分散は割り当てられたリソースのオーダー$b$に比例する。
  論文  参考訳（メタデータ） (2023-06-28T21:59:11Z)
• Policy Evaluation in Distributional LQR [70.63903506291383]
  ランダムリターンの分布を閉形式で表現する。 この分布は有限個の確率変数で近似できることを示す。 近似回帰分布を用いて,リスク・アバースLQRに対するゼロ階ポリシー勾配アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-03-23T20:27:40Z)
• Degeneracy is OK: Logarithmic Regret for Network Revenue Management with Indiscrete Distributions [13.310272407473809]
  我々は、従来のネットワーク収益管理(NRM)問題について、意思決定を受理/退避し、IIDの到着を$T$で検討する。 本モデルでは,O(log2 T)$ regret を実現するオンラインアルゴリズムを開発した。 2階成長の仮定を追加して、$O(log T)$ regretを達成する2番目の結果を得る。
  論文  参考訳（メタデータ） (2022-10-14T17:52:19Z)
• Universal Off-Policy Evaluation [64.02853483874334]
  ユニバーサルオフ政治推定器(UnO)への第一歩を踏み出す 我々は, 平均, 分散, 分位数/中間数, 分位数範囲, cvar, および累積分布全体の推定と同時結合に uno を用いる。
  論文  参考訳（メタデータ） (2021-04-26T18:54:31Z)

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

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