論文の概要: Online Resource Allocation with Convex-set Machine-Learned Advice
- arxiv url: http://arxiv.org/abs/2306.12282v1
- Date: Wed, 21 Jun 2023 14:09:33 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-22 13:08:33.916687
- Title: Online Resource Allocation with Convex-set Machine-Learned Advice
- Title（参考訳）: Convex-set Machine-Learned Advice を用いたオンラインリソース割り当て
- Authors: Negin Golrezaei and Patrick Jaillet and Zijie Zhou
- Abstract要約: 本稿では、一貫した比とロバストな比のバランスをとる最適オンラインリソース割り当てアルゴリズムのパラメータ化クラスを導入する。
具体的には、C-リート最適設定において、ロバスト比が少なくともCであることを保証するとともに、一貫した比を最大化する。
- 参考スコア（独自算出の注目度）: 27.662388663465006
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Decision-makers often have access to a machine-learned prediction about
demand, referred to as advice, which can potentially be utilized in online
decision-making processes for resource allocation. However, exploiting such
advice poses challenges due to its potential inaccuracy. To address this issue,
we propose a framework that enhances online resource allocation decisions with
potentially unreliable machine-learned (ML) advice. We assume here that this
advice is represented by a general convex uncertainty set for the demand
vector.
We introduce a parameterized class of Pareto optimal online resource
allocation algorithms that strike a balance between consistent and robust
ratios. The consistent ratio measures the algorithm's performance (compared to
the optimal hindsight solution) when the ML advice is accurate, while the
robust ratio captures performance under an adversarial demand process when the
advice is inaccurate. Specifically, in a C-Pareto optimal setting, we maximize
the robust ratio while ensuring that the consistent ratio is at least C. Our
proposed C-Pareto optimal algorithm is an adaptive protection level algorithm,
which extends the classical fixed protection level algorithm introduced in
Littlewood (2005) and Ball and Queyranne (2009). Solving a complex non-convex
continuous optimization problem characterizes the adaptive protection level
algorithm. To complement our algorithms, we present a simple method for
computing the maximum achievable consistent ratio, which serves as an estimate
for the maximum value of the ML advice. Additionally, we present numerical
studies to evaluate the performance of our algorithm in comparison to benchmark
algorithms. The results demonstrate that by adjusting the parameter C, our
algorithms effectively strike a balance between worst-case and average
performance, outperforming the benchmark algorithms.
- Abstract（参考訳）: 意思決定者は、しばしば、アドバイスと呼ばれる、需要に関する機械学習による予測にアクセスでき、リソース割り当てのオンライン意思決定プロセスで利用することができる。
しかし、そのようなアドバイスを利用すると、その潜在的な不正確さが問題となる。
この問題に対処するために,信頼性の低いマシン学習(ML)アドバイスを用いて,オンラインリソース割り当て決定を強化するフレームワークを提案する。
ここで、このアドバイスは需要ベクトルに対する一般凸不確実性によって表現されると仮定する。
本稿では、一貫した比とロバストな比のバランスをとるPareto最適オンラインリソース割り当てアルゴリズムのパラメータ化クラスを導入する。
整合比は、MLアドバイスが正確であるときにアルゴリズムのパフォーマンス(最適の後見解と比較)を計測し、ロバスト比は、アドバイスが不正確であるときに敵の要求プロセスの下でパフォーマンスをキャプチャする。
提案したC-Pareto最適化アルゴリズムは,Littlewood (2005) と Ball and Queyranne (2009) で導入された古典的固定保護レベルアルゴリズムを拡張した適応保護レベルアルゴリズムである。
複雑な非凸連続最適化問題の解法は適応的保護レベルアルゴリズムを特徴付ける。
アルゴリズムを補完するため,MLアドバイスの最大値に対する推定値である最大達成可能な一貫した比率を計算するための簡単な方法を提案する。
さらに,ベンチマークアルゴリズムと比較して,アルゴリズムの性能を評価するための数値的研究を行った。
その結果、パラメータCを調整することで、アルゴリズムは最悪のケースと平均性能のバランスを保ち、ベンチマークアルゴリズムより優れていることが示された。
関連論文リスト
- Overcoming Brittleness in Pareto-Optimal Learning-Augmented Algorithms [6.131022957085439]
本稿では,ユーザ特定プロファイルを用いて,アルゴリズムの性能のスムーズさを強制する新しいフレームワークを提案する。
我々は、この新しいアプローチを、よく研究されたオンライン問題、すなわち片道取引問題に適用する。
論文 参考訳（メタデータ） (2024-08-07T23:15:21Z) - Deterministic Trajectory Optimization through Probabilistic Optimal Control [3.2771631221674333]
離散時間決定論的有限水平非線形最適制御問題に対する2つの新しいアルゴリズムを提案する。
どちらのアルゴリズムも確率論的最適制御として知られる新しい理論パラダイムにインスパイアされている。
このアルゴリズムの適用により、決定論的最適ポリシーに収束する確率的ポリシーの定点が得られることを示す。
論文 参考訳（メタデータ） (2024-07-18T09:17:47Z) - Likelihood Ratio Confidence Sets for Sequential Decision Making [51.66638486226482]
確率に基づく推論の原理を再検討し、確率比を用いて妥当な信頼シーケンスを構築することを提案する。
本手法は, 精度の高い問題に特に適している。
提案手法は,オンライン凸最適化への接続に光を当てることにより,推定器の最適シーケンスを確実に選択する方法を示す。
論文 参考訳（メタデータ） (2023-11-08T00:10:21Z) - Exploring the Algorithm-Dependent Generalization of AUPRC Optimization
with List Stability [107.65337427333064]
AUPRC(Area Under the Precision-Recall Curve)の最適化は、機械学習にとって重要な問題である。
本研究では, AUPRC最適化の単依存一般化における最初の試行について述べる。
3つの画像検索データセットの実験は、我々のフレームワークの有効性と健全性に言及する。
論文 参考訳（メタデータ） (2022-09-27T09:06:37Z) - Selection of the Most Probable Best [2.1095005405219815]
予測値ランキングと選択(R&S)問題では,すべてのk解のシミュレーション出力が,分布によって不確実性をモデル化可能な共通パラメータに依存する。
我々は、最も確率の高い最適解 (MPB) を、分布に関して最適である確率が最も大きい解と定義する。
最適化条件における未知の手段をその推定値に置き換えるアルゴリズムを考案し,シミュレーション予算が増加するにつれて,アルゴリズムのサンプリング比が条件を満たすことを証明した。
論文 参考訳（メタデータ） (2022-07-15T15:27:27Z) - On the Optimality of Batch Policy Optimization Algorithms [106.89498352537682]
バッチポリシー最適化は、環境と対話する前に既存のデータをポリシー構築に活用することを検討する。
信頼調整インデックスアルゴリズムは楽観的,悲観的,中立的いずれであってもミニマックス最適であることを示す。
最適値予測の本来の難易度を考慮した新しい重み付き最小値基準を提案する。
論文 参考訳（メタデータ） (2021-04-06T05:23:20Z) - Soft-Robust Algorithms for Batch Reinforcement Learning [36.78967245470449]
強化学習では、限られたデータによる堅牢な意思決定問題は、通常パーセンタイル基準によって計算される。
平均性能を最適化し無視することが難しいため、パーセンタイル基準は理論的ではないことを示す。
パーセンタイル基準を最適化するアルゴリズムを2つ提案し,解析する。
論文 参考訳（メタデータ） (2020-11-30T01:36:16Z) - Bilevel Optimization: Convergence Analysis and Enhanced Design [63.64636047748605]
バイレベル最適化は多くの機械学習問題に対するツールである。
Stoc-BiO という新しい確率効率勾配推定器を提案する。
論文 参考訳（メタデータ） (2020-10-15T18:09:48Z) - Adaptive Sampling for Best Policy Identification in Markov Decision
Processes [79.4957965474334]
本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。
最先端アルゴリズムの利点を論じ、解説する。
論文 参考訳（メタデータ） (2020-09-28T15:22:24Z) - Stochastic Optimization Forests [60.523606291705214]
標準的なランダムな森林アルゴリズムのように予測精度を向上させるために分割するのではなく、分割を選択した木を栽培し、下流の意思決定品質を直接最適化することで、森林決定政策の訓練方法を示す。
概略分割基準は、各候補分割に対して正確に最適化された森林アルゴリズムに近い性能を保ちながら、100倍のランニング時間を短縮できることを示す。
論文 参考訳（メタデータ） (2020-08-17T16:56:06Z) - Boosting Algorithms for Estimating Optimal Individualized Treatment
Rules [4.898659895355356]
最適な個別化処理規則を推定するための非パラメトリックアルゴリズムを提案する。
提案アルゴリズムは機械学習文学において最も強力なアルゴリズムの1つであるXGBoostアルゴリズムに基づいている。
論文 参考訳（メタデータ） (2020-01-31T22:26:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。