論文の概要: Online Learning under Budget and ROI Constraints via Weak Adaptivity
- arxiv url: http://arxiv.org/abs/2302.01203v3
- Date: Sat, 2 Mar 2024 17:26:22 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-05 21:12:34.530715
- Title: Online Learning under Budget and ROI Constraints via Weak Adaptivity
- Title(参考訳): 弱適応性による予算・ROI制約下のオンライン学習
- Authors: Matteo Castiglioni, Andrea Celli, Christian Kroer
- Abstract要約: 制約付きオンライン学習問題に対する既存の原始双対アルゴリズムは、2つの基本的な仮定に依存している。
このような仮定は、標準の原始双対テンプレートを弱適応的後悔最小化器で与えることによって、どのように回避できるのかを示す。
上記の2つの前提が満たされていない場合に保証される、世界の最高の保証を証明します。
- 参考スコア(独自算出の注目度): 57.097119428915796
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study online learning problems in which a decision maker has to make a
sequence of costly decisions, with the goal of maximizing their expected reward
while adhering to budget and return-on-investment (ROI) constraints. Existing
primal-dual algorithms designed for constrained online learning problems under
adversarial inputs rely on two fundamental assumptions. First, the decision
maker must know beforehand the value of parameters related to the degree of
strict feasibility of the problem (i.e. Slater parameters). Second, a strictly
feasible solution to the offline optimization problem must exist at each round.
Both requirements are unrealistic for practical applications such as bidding in
online ad auctions. In this paper, we show how such assumptions can be
circumvented by endowing standard primal-dual templates with weakly adaptive
regret minimizers. This results in a ``dual-balancing'' framework which ensures
that dual variables stay sufficiently small, even in the absence of knowledge
about Slater's parameter. We prove the first best-of-both-worlds no-regret
guarantees which hold in absence of the two aforementioned assumptions, under
stochastic and adversarial inputs. Finally, we show how to instantiate the
framework to optimally bid in various mechanisms of practical relevance, such
as first- and second-price auctions.
- Abstract(参考訳): 我々は、予算と投資リターン(roi)の制約に固執しながら、期待する報酬を最大化することを目的として、意思決定者が一連のコストのかかる意思決定をしなければならないオンライン学習問題を研究する。
敵対的入力下でのオンライン学習問題を制約するために設計された既存の原始的アルゴリズムは、2つの基本的な仮定に依存している。
まず、意思決定者は、問題の厳密な実現可能性(すなわちスレーターパラメータ)の度合いに関連するパラメータの値を事前に知る必要がある。
第二に、オフライン最適化問題に対する厳密な解決法が各ラウンドに存在する必要がある。
どちらの要件も、オンライン広告オークションの入札のような実用的な応用には非現実的である。
本稿では,弱適応型後悔最小値を持つ標準原始的テンプレートを内挿することで,このような仮定を回避できることを示す。
これにより `dual-balancing'' フレームワークが作成され、スレーターのパラメータに関する知識がなくても、双対変数が十分に小さく保たれることが保証される。
我々は、前述した2つの仮定の欠如を確率的かつ逆の入力の下で保持する、初めて両世界の最高のノンレグレット保証を証明する。
最後に、第1および第2価格オークションのような実用的妥当性の様々なメカニズムを最適に入札するためのフレームワークのインスタンス化方法を示す。
関連論文リスト
- Efficient Methods for Non-stationary Online Learning [67.3300478545554]
本稿では, 動的後悔と適応的後悔を最適化する効率的な手法を提案し, ラウンド当たりの投影回数を$mathcalO(log T)$から$ $1$まで削減した。
本手法は,パラメータフリーオンライン学習において開発された還元機構を基礎として,非定常オンライン手法に非自明なツイストを必要とする。
論文 参考訳(メタデータ) (2023-09-16T07:30:12Z) - Model-based Constrained MDP for Budget Allocation in Sequential
Incentive Marketing [28.395877073390434]
逐次インセンティブマーケティングは、オンラインビジネスにとって顧客を獲得し、忠誠心を高め、売上を伸ばすための重要なアプローチである。
予算制約下でのリターンを最大化するインセンティブを効果的に割り当てる方法については、文献ではあまり研究されていない。
本稿では,2項探索とモデルベース計画を組み合わせた効率的な学習アルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-03-02T08:10:45Z) - Direct Heterogeneous Causal Learning for Resource Allocation Problems in
Marketing [20.9377115817821]
マーケティングは、ユーザのエンゲージメントを高め、プラットフォーム収益を改善するための重要なメカニズムである。
マーケティングにおける意思決定問題は資源配分問題として定式化され、数十年にわたって研究されてきた。
既存の作業は通常、解法を2つの完全に分離された段階、すなわち機械学習(ML)と操作研究(OR)に分割する。
論文 参考訳(メタデータ) (2022-11-28T19:27:34Z) - A Unifying Framework for Online Optimization with Long-Term Constraints [62.35194099438855]
我々は,意思決定者が長期的制約の対象となる一連の意思決定をしなければならないオンライン学習問題について検討する。
目標は、全報酬を最大化し、同時に、$T$ラウンド全体で小さな累積違反を達成することである。
本稿では,この一般クラス問題に対して,未知のモデルに基づいて報酬と制約が選択された場合と,各ラウンドで敵が選択した場合の双方において,最良世界型アルゴリズムを提示する。
論文 参考訳(メタデータ) (2022-09-15T16:59:19Z) - Online Learning with Knapsacks: the Best of Both Worlds [54.28273783164608]
オンライン学習の課題として,意思決定者が,リソース制約の有限セットに違反することなく,期待する報酬を最大化したい,という課題を提起する。
当社のフレームワークは,意思決定者がそのエビデンスを柔軟かつコスト論的に扱えるようにします。
論文 参考訳(メタデータ) (2022-02-28T12:10:48Z) - Online Allocation with Two-sided Resource Constraints [44.5635910908944]
我々は,要求が順次到着する,リソース制約の低いオンラインアロケーション問題を考える。
提案手法では, リクエスト全体を知るオフライン問題に対して, 1-O (fracepsilonalpha-epsilon)$-competitive ratioを求めるアルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-12-28T02:21:06Z) - Online Optimization and Learning in Uncertain Dynamical Environments
with Performance Guarantees [2.729854122688235]
未知かつ不確実な動的環境におけるオンライン最適化と学習問題を解決するための新しいフレームワークを提案する。
このフレームワークは、オンラインの決定を定量的に堅牢にしながら、不確実な動的環境を同時に学ぶことができます。
論文 参考訳(メタデータ) (2021-02-18T01:49:06Z) - An Online Method for A Class of Distributionally Robust Optimization
with Non-Convex Objectives [54.29001037565384]
本稿では,オンライン分散ロバスト最適化(DRO)のクラスを解決するための実用的なオンライン手法を提案する。
本研究は,ネットワークの堅牢性向上のための機械学習における重要な応用を実証する。
論文 参考訳(メタデータ) (2020-06-17T20:19:25Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。