論文の概要: Online Resource Allocation: Bandits feedback and Advice on Time-varying
Demands
- arxiv url: http://arxiv.org/abs/2302.04182v2
- Date: Mon, 12 Jun 2023 10:52:47 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-14 01:23:25.066624
- Title: Online Resource Allocation: Bandits feedback and Advice on Time-varying
Demands
- Title(参考訳): オンラインリソース割り当て: 時間変動要求に対するフィードバックとアドバイスを包括する
- Authors: Lixing Lyu and Wang Chi Cheung
- Abstract要約: 我々は、帯域幅のフィードバックと時間変化の要求を伴う一般的なオンラインリソース割り当てモデルについて検討する。
最近のOnline Algorithms with Adviceフレームワークに触発され、オンラインアドバイスがポリシー設計にどのように役立つかを探る。
提案アルゴリズムは,文学における他のアルゴリズムと比較して,理論的性能と有望な数値結果の両方を有することを示した。
- 参考スコア(独自算出の注目度): 12.081877372552606
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We consider a general online resource allocation model with bandit feedback
and time-varying demands. While online resource allocation has been well
studied in the literature, most existing works make the strong assumption that
the demand arrival process is stationary. In practical applications, such as
online advertisement and revenue management, however, this process may be
exogenous and non-stationary, like the constantly changing internet traffic.
Motivated by the recent Online Algorithms with Advice framework [Mitazenmacher
and Vassilvitskii, \emph{Commun. ACM} 2022], we explore how online advice can
inform policy design. We establish an impossibility result that any algorithm
perform poorly in terms of regret without any advice in our setting. In
contrast, we design an robust online algorithm that leverages the online
predictions on the total demand volumes. Empowered with online advice, our
proposed algorithm is shown to have both theoretical performance and promising
numerical results compared with other algorithms in literature. We also provide
two explicit examples for the time-varying demand scenarios and derive
corresponding theoretical performance guarantees. Finally, we adapt our model
to a network revenue management problem, and numerically demonstrate that our
algorithm can still performs competitively compared to existing baselines.
- Abstract(参考訳): 我々は,包帯フィードバックと時間変動要求を伴う一般的なオンラインリソース割り当てモデルを検討する。
オンラインリソース割り当ては文献でよく研究されているが、既存の作品の多くは需要の到着プロセスが静止していると強く仮定している。
しかし、オンライン広告や収益管理のような実践的なアプリケーションでは、このプロセスはインターネットトラフィックが絶えず変化するように、外生的にも非定常的かもしれない。
最近の Online Algorithms with Advice framework [Mitazenmacher と Vassilvitskii, \emph{Commun] に触発された。
ACM} 2022] オンラインアドバイスが政策設計にどのように役立つかを探る。
我々は,どのアルゴリズムも,我々の設定において何の助言も受けずに,後悔の観点からは不十分な結果を生んでいる。
対照的に,総需要量のオンライン予測を活用できるロバストなオンラインアルゴリズムを設計した。
提案アルゴリズムは,オンラインアドバイスを応用し,理論的性能と有望な数値的結果の両方を文献上の他のアルゴリズムと比較した。
また,時間変動需要シナリオに対する2つの明示的な例を示し,それに対応する理論性能保証を導出する。
最後に、ネットワーク収益管理問題にモデルを適応させ、既存のベースラインと比較してアルゴリズムが競合的に動作可能であることを数値的に示す。
関連論文リスト
- Online Optimization for Network Resource Allocation and Comparison with
Reinforcement Learning Techniques [0.6466206145151128]
本稿では、ジョブ転送におけるオンラインネットワークリソース割り当て問題に取り組む。
本稿では指数重み付け手法に基づくランダム化オンラインアルゴリズムを提案する。
提案アルゴリズムは,その経験からアルゴリズムが適応し,学習していることを示す。
論文 参考訳(メタデータ) (2023-11-16T17:08:27Z) - Rethinking and Benchmarking Predict-then-Optimize Paradigm for
Combinatorial Optimization Problems [62.25108152764568]
多くのWebアプリケーションは、エネルギーコストを考慮したスケジューリング、Web広告の予算配分、ソーシャルネットワークでのグラフマッチングなど、最適化問題の解決に頼っている。
統一システムにおける予測と意思決定の性能について考察する。
我々は、現在のアプローチを包括的に分類し、既存の実験シナリオを統合する。
論文 参考訳(メタデータ) (2023-11-13T13:19:34Z) - Efficient Methods for Non-stationary Online Learning [67.3300478545554]
本稿では, 動的後悔と適応的後悔を最適化する効率的な手法を提案し, ラウンド当たりの投影回数を$mathcalO(log T)$から$ $1$まで削減した。
本手法は,パラメータフリーオンライン学習において開発された還元機構を基礎として,非定常オンライン手法に非自明なツイストを必要とする。
論文 参考訳(メタデータ) (2023-09-16T07:30:12Z) - Online Network Source Optimization with Graph-Kernel MAB [62.6067511147939]
大規模ネットワークにおける最適なソース配置をオンラインで学習するためのグラフカーネルマルチアームバンディットアルゴリズムであるGrab-UCBを提案する。
適応グラフ辞書モデルを用いて,ネットワークプロセスを記述する。
我々は、ネットワークパラメータに依存する性能保証を導出し、シーケンシャルな意思決定戦略の学習曲線にさらに影響を及ぼす。
論文 参考訳(メタデータ) (2023-07-07T15:03:42Z) - Online Caching with no Regret: Optimistic Learning via Recommendations [15.877673959068458]
ファイル要求の予測を含むFTRL(Follow-the-Regularized-Leader)フレームワークを構築した。
フレームワークを拡張して、多くが利用可能な場合に最適な要求予測器を学習し、利用します。
提案した楽観的な学習キャッシュポリシが,完全予測のためのサブゼロ性能損失(regret)を達成できることを実証する。
論文 参考訳(メタデータ) (2022-04-20T09:29:47Z) - Non-Clairvoyant Scheduling with Predictions Revisited [77.86290991564829]
非論理的スケジューリングでは、優先度不明な処理条件でジョブをスケジューリングするためのオンライン戦略を見つけることが課題である。
我々はこのよく研究された問題を、アルゴリズム設計に(信頼できない)予測を統合する、最近人気の高い学習強化された設定で再検討する。
これらの予測には所望の特性があり, 高い性能保証を有するアルゴリズムと同様に, 自然な誤差測定が可能であることを示す。
論文 参考訳(メタデータ) (2022-02-21T13:18:11Z) - Single-Leg Revenue Management with Advice [27.21119630468227]
我々は、アルゴリズムとアドバイスのフレームワークのレンズを通して、シングルレグの収益管理の問題に目を向ける。
すべてのアドバイスに対する一貫性(アドバイスが正確であればパフォーマンス)と競争性(アドバイスが不正確であればパフォーマンス)のトレードオフを特徴付ける。
また、シングルレッグ収益管理において最も広く展開されている技術である保護レベル政策のクラスについても検討する。
論文 参考訳(メタデータ) (2022-02-18T00:32:11Z) - An Online Learning Approach to Optimizing Time-Varying Costs of AoI [26.661352924641285]
通信ネットワーク上でのソースのタイムリーな監視を必要とするシステムについて検討する。
単一のソース監視問題に対して、後見の最良の固定ポリシーと比較して、サブ線形後悔を実現するアルゴリズムを設計する。
複数ソーススケジューリング問題に対して、Follow-the-Perturbed-Whittle-Leaderと呼ばれる新しいオンライン学習アルゴリズムを設計する。
論文 参考訳(メタデータ) (2021-05-27T18:10:56Z) - Better than the Best: Gradient-based Improper Reinforcement Learning for
Network Scheduling [60.48359567964899]
パケット遅延を最小限に抑えるため,制約付き待ち行列ネットワークにおけるスケジューリングの問題を考える。
我々は、利用可能な原子ポリシーよりも優れたスケジューラを生成するポリシー勾配に基づく強化学習アルゴリズムを使用する。
論文 参考訳(メタデータ) (2021-05-01T10:18:34Z) - Computation Resource Allocation Solution in Recommender Systems [19.456109814747048]
限られた計算資源と応答時間でビジネス目標を最大化する計算資源割当ソリューション(CRAS)を提案します。
本手法の有効性はtaobao.comの実データに基づく広範囲な実験により検証された。
論文 参考訳(メタデータ) (2021-03-03T08:41:43Z) - Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online
Algorithms [85.97516436641533]
機械学習予測を取り入れたオンラインアルゴリズムの性能向上の課題について検討する。
目標は、一貫性と堅牢性の両方を備えたアルゴリズムを設計することだ。
機械学習予測を用いた競合解析のための非自明な下界の最初のセットを提供する。
論文 参考訳(メタデータ) (2020-10-22T04:51:01Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。