論文の概要: Online Resource Allocation with Average Budget Constraints
- arxiv url: http://arxiv.org/abs/2402.11425v5
- Date: Fri, 26 Sep 2025 03:06:32 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-09-29 20:57:53.802763
- Title: Online Resource Allocation with Average Budget Constraints
- Title（参考訳）: 平均予算制約によるオンライン資源配分
- Authors: Ruicheng Ao, Hongyu Chen, David Simchi-Levi, Feng Zhu,
- Abstract要約: 平均予算制約によるオンライン資源配分の問題点を考察する。
簡単なポリシーがOmega(sqrtT)$ regretを達成していることを示す。
予算安全バッファを組み込んだ新しいポリシーを提案する。
- 参考スコア（独自算出の注目度）: 17.47923923731483
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the problem of online resource allocation with average budget constraints. At each time point the decision maker makes an irrevocable decision of whether to accept or reject a request before the next request arrives with the goal to maximize the cumulative rewards. In contrast to existing literature requiring the total resource consumption is below a certain level, we require the average resource consumption per accepted request does not exceed a given threshold. This problem can be casted as an online knapsack problem with exogenous random budget replenishment, and can find applications in various fields such as online anomaly detection, sequential advertising, and per-capita public service providers. We start with general arrival distributions and show that a simple policy achieves a $O(\sqrt{T})$ regret. We complement the result by showing that such a regret growing rate is in general not improvable. We then shift our focus to discrete arrival distributions. We find that many existing re-solving heuristics in the online resource allocation literature, albeit achieve bounded loss in canonical settings, may incur a $\Omega(\sqrt{T})$ or even a $\Omega(T)$ regret. With the observation that canonical policies tend to be too optimistic and over accept arrivals, we propose a novel policy that incorporates budget safety buffers. It turns out that a little more safety can greatly enhance efficiency -- small additional logarithmic buffers suffice to reduce the regret from $\Omega(\sqrt{T})$ or even $\Omega(T)$ to $O(\ln^2 T)$. From a practical perspective, we extend the policy to the scenario with continuous arrival distributions, time-dependent information structures, as well as unknown $T$. We conduct both synthetic experiments and empirical applications on a time series data of New York City taxi passengers to validate the performance of our proposed policies.
- Abstract（参考訳）: 平均予算制約によるオンライン資源配分の問題点を考察する。
各時点において、意思決定者は、次の要求が到着する前に要求を受諾するか拒否するかを、累積報酬を最大化するために、取り消し不可能な決定を下す。
既存の文献では、リソースの総消費量が一定の水準以下であるのに対し、受理された要求あたりの平均リソース消費量は所定の閾値を超えない必要がある。
この問題は、外因性ランダムな予算補充を伴うオンラインknapsack問題とみなすことができ、オンライン異常検出、シーケンシャル広告、および一人当たりの公共サービスプロバイダなど、さまざまな分野のアプリケーションを見つけることができる。
まず、一般的な到着分布から始め、単純なポリシーが$O(\sqrt{T})$後悔を達成することを示す。
このような残念な成長速度が一般的には実現不可能であることを示すことで、その結果を補完する。
次に、個別の到着分布に焦点を移します。
オンラインリソース割り当て文献における多くの既存の再解決ヒューリスティックは、標準設定における有界損失を達成したとしても、$\Omega(\sqrt{T})$あるいは$\Omega(T)$後悔を招きかねない。
標準政策は楽観的すぎる傾向にあり、到着を過度に受け入れる傾向にあることから、予算安全バッファーを組み込んだ新しい政策を提案する。
小さな対数バッファは、後悔を$\Omega(\sqrt{T})$または$\Omega(T)$から$O(\ln^2T)$に減らすのに十分である。
実用の観点からは、ポリシーを連続到着分布、時間依存情報構造、未知の$T$のシナリオに拡張する。
ニューヨーク市のタクシー乗客の時系列データに合成実験と経験的応用の両方を施し,提案手法の有効性を検証した。
関連論文リスト
- Quantile-Optimal Policy Learning under Unmeasured Confounding [55.72891849926314]
ここでは,報酬分布が (0, 1) で最大$alpha$-quantileを持つポリシーを見つけることを目標とする量子最適政策学習について検討する。
このような問題は、(i)報酬分布の関数としての量子目標の非線形性、(ii)未観測の共起問題、(iii)オフラインデータセットのカバー不足という3つの大きな課題に悩まされている。
論文 参考訳（メタデータ） (2025-06-08T13:37:38Z) - Distributionally Robust Policy Learning under Concept Drifts [33.44768994272614]
本稿では、より曖昧な問題、つまり、コンセプトドリフトの下でのロバストな政策学習について研究する。
まず、与えられた政策の最悪の平均報酬を評価するための2倍のロバスト推定器を提供する。
次に、所定のポリシークラス内で推定されたポリシー値を最大化するポリシーを出力する学習アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-12-18T19:53:56Z) - Oracle-Efficient Reinforcement Learning for Max Value Ensembles [7.404901768256101]
大または無限の状態空間における強化学習(RL)は、理論上、実験的に困難である。
この作業では、$textitmax-following Policy$と競合することを目指しています。
我々の主な成果は、構成ポリシーのみにアクセスすると、最大フォローポリシーと競合する効率的なアルゴリズムである。
論文 参考訳（メタデータ） (2024-05-27T01:08:23Z) - Online Policy Learning and Inference by Matrix Completion [12.527541242185404]
行列完備帯域(MCB)として問題を定式化する。
我々は、$epsilon$-greedy banditとオンライン勾配降下について検討する。
より早く崩壊する探索は、より少ない後悔をもたらすが、最適なポリシーをより正確に学習する。
論文 参考訳（メタデータ） (2024-04-26T13:19:27Z) - Thompson Exploration with Best Challenger Rule in Best Arm
Identification [66.33448474838342]
本稿では,バンドイットフレームワークにおける固定信頼度最良腕識別問題について検討する。
我々は、トンプソンサンプリングと、ベストチャレンジャールールとして知られる計算効率の良いアプローチを組み合わせた新しいポリシーを提案する。
論文 参考訳（メタデータ） (2023-10-01T01:37:02Z) - Estimating Optimal Policy Value in General Linear Contextual Bandits [50.008542459050155]
多くのバンドイット問題において、政策によって達成可能な最大報酬は、前もって不明であることが多い。
我々は,最適政策が学習される前に,サブ線形データ構造における最適政策値を推定する問題を考察する。
V*$で問題依存上界を推定する,より実用的で効率的なアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-02-19T01:09:24Z) - Probably Anytime-Safe Stochastic Combinatorial Semi-Bandits [81.60136088841948]
本稿では,時間軸における後悔を最小限に抑えるアルゴリズムを提案する。
提案アルゴリズムは,レコメンデーションシステムや交通機関などの分野に適用可能である。
論文 参考訳（メタデータ） (2023-01-31T03:49:00Z) - Anytime-valid off-policy inference for contextual bandits [34.721189269616175]
コンテキストバンディットアルゴリズムは、観測されたコンテキストを$X_t$からアクションにマッピングする。
データの収集に使われたロギングポリシーと異なる仮説的ポリシーの特性を推定することは、しばしば関心がある。
我々は、過去の作業で不要な条件を緩和するOPE推論のための包括的なフレームワークを提案する。
論文 参考訳（メタデータ） (2022-10-19T17:57:53Z) - A Simple and Optimal Policy Design with Safety against Heavy-Tailed Risk for Stochastic Bandits [27.058087400790555]
マルチアームバンディット問題について検討し,期待された後悔に対する最悪のケース最適性と,後悔の分布に対する軽微なリスクの両方を享受する新しいポリシーを設計する。
経営的な観点から、我々の新しい政策設計は、より良い尾の分布をもたらし、祝福された政策よりも好まれることがわかった。
論文 参考訳（メタデータ） (2022-06-07T02:10:30Z) - Doubly Robust Distributionally Robust Off-Policy Evaluation and Learning [59.02006924867438]
オフ政治評価と学習(OPE/L)は、オフラインの観察データを使用してより良い意思決定を行う。
近年の研究では、分散ロバストなOPE/L (DROPE/L) が提案されているが、この提案は逆正則重み付けに依存している。
KL分散不確実性集合を用いたDROPE/Lの最初のDRアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-02-19T20:00:44Z) - Optimal Off-Policy Evaluation from Multiple Logging Policies [77.62012545592233]
我々は,複数のロギングポリシからオフ政治評価を行い,それぞれが一定のサイズ,すなわち階層化サンプリングのデータセットを生成する。
複数ロガーのOPE推定器は,任意のインスタンス,すなわち効率のよいインスタンスに対して最小分散である。
論文 参考訳（メタデータ） (2020-10-21T13:43:48Z) - Stochastic Bandits with Linear Constraints [69.757694218456]
制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。
楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-17T22:32:19Z) - Differentiable Bandit Exploration [38.81737411000074]
我々は、$mathcalP$からサンプルを使って未知のディストリビューション$mathcalP$についてそのようなポリシーを学ぶ。
我々のアプローチはメタラーニングの形式であり、その形式について強い仮定をすることなく$mathcalP$のプロパティを利用する。
論文 参考訳（メタデータ） (2020-02-17T05:07:35Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。