論文の概要: Best of Many in Both Worlds: Online Resource Allocation with Predictions
under Unknown Arrival Model
- arxiv url: http://arxiv.org/abs/2402.13530v1
- Date: Wed, 21 Feb 2024 04:57:32 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-22 16:55:59.289225
- Title: Best of Many in Both Worlds: Online Resource Allocation with Predictions
under Unknown Arrival Model
- Title（参考訳）: 両世界の多くの人々のベスト:未知の領域モデルに基づく予測付きオンラインリソース割り当て
- Authors: Lin An, Andrew A. Li, Benjamin Moseley, and Gabriel Visotsky
- Abstract要約: オンライン資源配分問題は,収益管理とオンライン意思決定において最も一般的なモデルの一つである。
我々は、各リソースのシャドウ価格を予測として捉え、将来の要求に対する予測によって得ることができる。
我々の主な貢献は、未知品質の予測を入力とし、両方の要求到着モデルの下で最適な性能を達成するアルゴリズムである。
- 参考スコア（独自算出の注目度）: 16.466711636334587
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Online decision-makers today can often obtain predictions on future
variables, such as arrivals, demands, inventories, and so on. These predictions
can be generated from simple forecasting algorithms for univariate time-series,
all the way to state-of-the-art machine learning models that leverage multiple
time-series and additional feature information. However, the prediction quality
is often unknown to decisions-makers a priori, hence blindly following the
predictions can be harmful. In this paper, we address this problem by giving
algorithms that take predictions as inputs and perform robustly against the
unknown prediction quality.
We consider the online resource allocation problem, one of the most generic
models in revenue management and online decision-making. In this problem, a
decision maker has a limited amount of resources, and requests arrive
sequentially. For each request, the decision-maker needs to decide on an
action, which generates a certain amount of rewards and consumes a certain
amount of resources, without knowing the future requests. The decision-maker's
objective is to maximize the total rewards subject to resource constraints. We
take the shadow price of each resource as prediction, which can be obtained by
predictions on future requests. Prediction quality is naturally defined to be
the $\ell_1$ distance between the prediction and the actual shadow price. Our
main contribution is an algorithm which takes the prediction of unknown quality
as an input, and achieves asymptotically optimal performance under both
requests arrival models (stochastic and adversarial) without knowing the
prediction quality and the requests arrival model beforehand. We show our
algorithm's performance matches the best achievable performance of any
algorithm had the arrival models and the accuracy of the predictions been
known. We empirically validate our algorithm with experiments.
- Abstract（参考訳）: 今日のオンライン意思決定者は、到着、要求、在庫など、将来の変数の予測を得られることが多い。
これらの予測は、単変量時系列の単純な予測アルゴリズムから、複数の時系列と追加の機能情報を活用する最先端の機械学習モデルまで、すべて生成することができる。
しかし、予測品質は意思決定者や意思決定者にとってしばしば不明であり、予測に盲目的に従うことは有害である。
本稿では,予測を入力とし,未知の予測品質に対して頑健に動作するアルゴリズムを提供することにより,この問題に対処する。
オンライン資源配分問題は,収益管理とオンライン意思決定において最も一般的なモデルの一つである。
この問題では、意思決定者は限られた量のリソースを持ち、リクエストは順次到着する。
各要求に対して、意思決定者は、将来の要求を知ることなく、一定の量の報酬を生成し、一定の量のリソースを消費するアクションを決定する必要がある。
意思決定者の目標は、リソース制約の対象となる全報酬を最大化することである。
我々は,各リソースのシャドー価格を予測として捉え,将来の要求の予測によって得ることができる。
予測品質は、予測と実際のシャドウ価格の間の距離$\ell_1$と定義されている。
提案手法は,未知品質の予測を入力とし,予測品質や要求到着モデルを知ることなく,要求到着モデル(統計的および敵対的)において漸近的に最適な性能を実現するアルゴリズムである。
提案アルゴリズムの性能は,アルゴリズムが到達したモデルと予測の精度を知っていれば,最も達成可能な性能と一致することを示す。
実験によってアルゴリズムを実証的に検証する。
関連論文リスト
- Next Best View For Point-Cloud Model Acquisition: Bayesian Approximation and Uncertainty Analysis [2.07180164747172]
この研究は、Next-Best-View(PC-NBV)にポイントネットベースのニューラルネットワークを適用する。
モデルアーキテクチャにドロップアウト層を組み込むことで、予測に関連する不確実性推定の計算を可能にする。
本研究の目的は,次の視点を正確に予測することで,ネットワークの精度を向上させることである。
論文 参考訳（メタデータ） (2024-11-04T01:32:09Z) - Towards Human-AI Complementarity with Prediction Sets [14.071862670474832]
予測セットに基づく意思決定支援システムは、人間の専門家が分類タスクを解くのに役立つことが証明されている。
共形予測を用いて構築された予測集合は、一般に平均精度の点で準最適であることを示す。
我々は,多種多様な専門家モデルと非最適スコアに対して,同等あるいはより優れた性能を提供する予測セットを見つけることが保証される,欲求的アルゴリズムを導入する。
論文 参考訳（メタデータ） (2024-05-27T18:00:00Z) - Algorithms with Prediction Portfolios [23.703372221079306]
我々は、マッチング、ロードバランシング、非クレアボイラントスケジューリングなど、多くの基本的な問題に対する複数の予測器の使用について検討する。
これらの問題のそれぞれに対して、複数の予測器を利用する新しいアルゴリズムを導入し、その結果のパフォーマンスに限界を証明します。
論文 参考訳（メタデータ） (2022-10-22T12:58:07Z) - Paging with Succinct Predictions [25.959849403994202]
予測情報を最小限に抑えるという新たな視点から学習増強型ページングについて検討する。
学習強化アルゴリズムの3つの望ましい特性をすべて満たす2つの設定のアルゴリズムを開発する。
論文 参考訳（メタデータ） (2022-10-06T09:26:34Z) - Uncertainty estimation of pedestrian future trajectory using Bayesian
approximation [137.00426219455116]
動的トラフィックシナリオでは、決定論的予測に基づく計画は信頼できない。
著者らは、決定論的アプローチが捉えられない近似を用いて予測中の不確実性を定量化する。
将来の状態の不確実性に対する降雨重量と長期予測の影響について検討した。
論文 参考訳（メタデータ） (2022-05-04T04:23:38Z) - Non-Clairvoyant Scheduling with Predictions Revisited [77.86290991564829]
非論理的スケジューリングでは、優先度不明な処理条件でジョブをスケジューリングするためのオンライン戦略を見つけることが課題である。
我々はこのよく研究された問題を、アルゴリズム設計に(信頼できない)予測を統合する、最近人気の高い学習強化された設定で再検討する。
これらの予測には所望の特性があり, 高い性能保証を有するアルゴリズムと同様に, 自然な誤差測定が可能であることを示す。
論文 参考訳（メタデータ） (2022-02-21T13:18:11Z) - Robustification of Online Graph Exploration Methods [59.50307752165016]
我々は、古典的で有名なオンライングラフ探索問題の学習強化版について研究する。
本稿では,予測をよく知られたNearest Neighbor(NN)アルゴリズムに自然に統合するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-12-10T10:02:31Z) - Dense Uncertainty Estimation [62.23555922631451]
本稿では,ニューラルネットワークと不確実性推定手法について検討し,正確な決定論的予測と確実性推定の両方を実現する。
本研究では,アンサンブルに基づく手法と生成モデルに基づく手法の2つの不確実性推定法について検討し,それらの長所と短所を,完全/半端/弱度に制御されたフレームワークを用いて説明する。
論文 参考訳（メタデータ） (2021-10-13T01:23:48Z) - Learning to Predict Trustworthiness with Steep Slope Loss [69.40817968905495]
本研究では,現実の大規模データセットにおける信頼性の予測問題について検討する。
我々は、先行技術損失関数で訓練された信頼性予測器が、正しい予測と誤った予測の両方を信頼に値するものとみなす傾向があることを観察する。
そこで我々は,2つのスライド状の曲線による不正確な予測から,特徴w.r.t.正しい予測を分離する,新たな急勾配損失を提案する。
論文 参考訳（メタデータ） (2021-09-30T19:19:09Z) - Private Prediction Sets [72.75711776601973]
機械学習システムは、個人のプライバシーの確実な定量化と保護を必要とする。
これら2つのデシラタを共同で扱う枠組みを提案する。
本手法を大規模コンピュータビジョンデータセット上で評価する。
論文 参考訳（メタデータ） (2021-02-11T18:59:11Z) - Bayes DistNet -- A Robust Neural Network for Algorithm Runtime
Distribution Predictions [1.8275108630751844]
ランダム化アルゴリズムは制約満足度問題 (CSP) やブール満足度問題 (SAT) の多くの最先端の解法で用いられている。
従来の最先端の手法は、入力インスタンスが従う固定パラメトリック分布を直接予測しようとする。
この新モデルは,低観測環境下での堅牢な予測性能と,検閲された観測処理を実現する。
論文 参考訳（メタデータ） (2020-12-14T01:15:39Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。