論文の概要: 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$と定義されている。
提案手法は,未知品質の予測を入力とし,予測品質や要求到着モデルを知ることなく,要求到着モデル(統計的および敵対的)において漸近的に最適な性能を実現するアルゴリズムである。
提案アルゴリズムの性能は,アルゴリズムが到達したモデルと予測の精度を知っていれば,最も達成可能な性能と一致することを示す。
実験によってアルゴリズムを実証的に検証する。
関連論文リスト
- Online Algorithms with Uncertainty-Quantified Predictions [12.57910560144628]
本稿では,オンラインアルゴリズムの設計における不確実性定量化予測を最適に活用する方法について考察する。
特に,基底真理が一定の範囲に落下する可能性を示す不確実な定量化を付加した予測について考察する。
いずれの場合も、確率論的予測を完全に活用するためには、アルゴリズム設計に対する非自明な修正が必要であることを実証する。
論文 参考訳(メタデータ) (2023-10-17T20:09:41Z) - Zero-Regret Performative Prediction Under Inequality Constraints [5.513958040574729]
本稿では不等式制約下での性能予測について検討する。
我々は,ある程度の精度しか必要としない頑健な原始双対フレームワークを開発する。
次に、位置ファミリに対する適応的原始双対アルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-09-22T04:54:26Z) - Algorithms with Prediction Portfolios [23.703372221079306]
我々は、マッチング、ロードバランシング、非クレアボイラントスケジューリングなど、多くの基本的な問題に対する複数の予測器の使用について検討する。
これらの問題のそれぞれに対して、複数の予測器を利用する新しいアルゴリズムを導入し、その結果のパフォーマンスに限界を証明します。
論文 参考訳(メタデータ) (2022-10-22T12:58:07Z) - What Should I Know? Using Meta-gradient Descent for Predictive Feature
Discovery in a Single Stream of Experience [63.75363908696257]
計算強化学習は、未来の感覚の予測を通じて、エージェントの世界の知覚を構築しようとする。
この一連の作業において、オープンな課題は、エージェントがどの予測が意思決定を最も支援できるかを、無限に多くの予測から決定することである。
本稿では,エージェントが何を予測するかを学習するメタ段階的な降下過程,(2)選択した予測の見積もり,3)将来の報酬を最大化するポリシーを生成する方法を紹介する。
論文 参考訳(メタデータ) (2022-06-13T21:31:06Z) - A Universal Error Measure for Input Predictions Applied to Online Graph
Problems [57.58926849872494]
本稿では,入力予測における誤差の定量化のための新しい尺度を提案する。
この尺度は、予測されていない要求と予測されていない実際の要求によるエラーをキャプチャする。
論文 参考訳(メタデータ) (2022-05-25T15:24:03Z) - 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) - Online Search With Best-Price and Query-Based Predictions [2.3204178451683264]
本稿では,入力に関する誤予測が存在する可能性のある学習増強アルゴリズムについて検討する。
株式市場から得られたデータに関する実験結果を提供する。
論文 参考訳(メタデータ) (2021-12-02T20:18:37Z) - Dense Uncertainty Estimation [62.23555922631451]
本稿では,ニューラルネットワークと不確実性推定手法について検討し,正確な決定論的予測と確実性推定の両方を実現する。
本研究では,アンサンブルに基づく手法と生成モデルに基づく手法の2つの不確実性推定法について検討し,それらの長所と短所を,完全/半端/弱度に制御されたフレームワークを用いて説明する。
論文 参考訳(メタデータ) (2021-10-13T01:23:48Z) - Double Coverage with Machine-Learned Advice [100.23487145400833]
オンラインの基本的な$k$-serverの問題を学習強化環境で研究する。
我々のアルゴリズムは任意の k に対してほぼ最適の一貫性-破壊性トレードオフを達成することを示す。
論文 参考訳(メタデータ) (2021-03-02T11:04:33Z) - Estimation with Uncertainty via Conditional Generative Adversarial
Networks [3.829070379776576]
条件付き生成逆数ネットワーク(cGAN)におけるジェネレータの使い方が異なる予測確率型ニューラルネットワークモデルを提案する。
通常のcGANの入力と出力を反転させることで、モデルを予測モデルとしてうまく利用することができる。
さらに,予測の不確実性を測定するために,回帰問題や分類問題に対するエントロピーと相対エントロピーを導入する。
論文 参考訳(メタデータ) (2020-07-01T08:54:17Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。