論文の概要: Non-Stationary Bandits with Knapsack Problems with Advice
- arxiv url: http://arxiv.org/abs/2302.04182v1
- Date: Wed, 8 Feb 2023 16:40:43 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-09 15:24:43.155138
- Title: Non-Stationary Bandits with Knapsack Problems with Advice
- Title(参考訳): Knapsack問題のある非定常バンドとアドバイス
- Authors: Lixing Lyu and Wang Chi Cheung
- Abstract要約: 総需要額$Q$のオンライン予測によって、パフォーマンス保証を改善する方法について検討する。
予測なしでは、オンラインアルゴリズムがリニア・イン・T$を後悔することを示している。
提案手法は, 予測の正確性に依存した残差を, 偏見的に組み込んだオンラインアルゴリズムを提案する。
- 参考スコア(独自算出の注目度): 12.081877372552606
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We consider a non-stationary Bandits with Knapsack problem. The outcome
distribution at each time is scaled by a non-stationary quantity that signifies
changing demand volumes. Instead of studying settings with limited
non-stationarity, we investigate how online predictions on the total demand
volume $Q$ allows us to improve our performance guarantees. We show that,
without any prediction, any online algorithm incurs a linear-in-$T$ regret. In
contrast, with online predictions on $Q$, we propose an online algorithm that
judiciously incorporates the predictions, and achieve regret bounds that
depends on the accuracy of the predictions. These bounds are shown to be tight
in settings when prediction accuracy improves across time. Our theoretical
results are corroborated by our numerical findings.
- Abstract(参考訳): Knapsack問題を持つ非定常帯域を考える。
各時点の成果分布は、変化する需要量を示す非定常量によってスケールされる。
限られた非定常性で設定を勉強する代わりに、総需要量$q$のオンライン予測がどのようにパフォーマンス保証を改善するかを調査します。
予測がなければ、オンラインアルゴリズムがリニアイン・$t$の後悔を負うことが分かる。
対照的に,$q$のオンライン予測とは対照的に,予測を巧みに取り入れ,予測の正確性に依存する後悔の限界を達成するオンラインアルゴリズムを提案する。
これらの境界は、予測精度が時間にわたって改善されたときに設定が厳密であることが示される。
我々の理論的結果は数値的な結果と一致している。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。