論文の概要: Online Bidding Algorithms for Return-on-Spend Constrained Advertisers
- arxiv url: http://arxiv.org/abs/2208.13713v3
- Date: Mon, 3 Jul 2023 05:20:52 GMT
- ステータス: 処理完了
- システム内更新日: 2023-07-04 15:49:40.992116
- Title: Online Bidding Algorithms for Return-on-Spend Constrained Advertisers
- Title（参考訳）: 広告主のオンライン入札アルゴリズム
- Authors: Zhe Feng, Swati Padmanabhan, Di Wang
- Abstract要約: この研究は、人気が高まっている制約の下で、単一の価値を最大化する広告主のための効率的なオンラインアルゴリズムを探索する。
我々は,指定したRoS制約を常に尊重しながら,期待のほぼ最適に後悔する簡単なオンラインアルゴリズムに貢献する。
- 参考スコア（独自算出の注目度）: 10.500109788348732
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Online advertising has recently grown into a highly competitive and complex
multi-billion-dollar industry, with advertisers bidding for ad slots at large
scales and high frequencies. This has resulted in a growing need for efficient
"auto-bidding" algorithms that determine the bids for incoming queries to
maximize advertisers' targets subject to their specified constraints. This work
explores efficient online algorithms for a single value-maximizing advertiser
under an increasingly popular constraint: Return-on-Spend (RoS). We quantify
efficiency in terms of regret relative to the optimal algorithm, which knows
all queries a priori.
We contribute a simple online algorithm that achieves near-optimal regret in
expectation while always respecting the specified RoS constraint when the input
sequence of queries are i.i.d. samples from some distribution. We also
integrate our results with the previous work of Balseiro, Lu, and Mirrokni
[BLM20] to achieve near-optimal regret while respecting both RoS and fixed
budget constraints.
Our algorithm follows the primal-dual framework and uses online mirror
descent (OMD) for the dual updates. However, we need to use a non-canonical
setup of OMD, and therefore the classic low-regret guarantee of OMD, which is
for the adversarial setting in online learning, no longer holds. Nonetheless,
in our case and more generally where low-regret dynamics are applied in
algorithm design, the gradients encountered by OMD can be far from adversarial
but influenced by our algorithmic choices. We exploit this key insight to show
our OMD setup achieves low regret in the realm of our algorithm.
- Abstract（参考訳）: オンライン広告は競争の激しい数十億ドル規模の業界へと成長し、広告主は大規模かつ高頻度の広告スロットを入札している。
これにより、特定の制約に基づいて広告主のターゲットを最大化するために、入ってくるクエリの入札を決定する効率的な「自動入札」アルゴリズムの必要性が高まっている。
本研究は,価値を最大化する広告主に対して,ros(return-on-spend)という制約下で効率的なオンラインアルゴリズムを提案する。
全てのクエリを事前に知っている最適アルゴリズムに対して、後悔の観点から効率を定量化する。
我々は,ある分布から入力されたクエリのシーケンスがサンプルである場合に,常に指定されたRoS制約を尊重しながら,期待のほぼ最適に後悔する簡単なオンラインアルゴリズムに寄与する。
また,これまでのbalseiro,lu,mirrokni [blm20] の成果と統合して,ros と固定予算の制約を尊重しながら,ほぼ最適の後悔を実現した。
本アルゴリズムは原始双対フレームワークに従い,オンラインミラー降下(omd)を用いてデュアルアップデートを行う。
しかし、OMDの非標準設定を用いる必要があるため、オンライン学習における逆境設定であるOMDの古典的な低レベル保証はもはや保持されない。
しかしながら,アルゴリズム設計において低相対性ダイナミクスが適用される場合,OMDが直面する勾配は逆数とは程遠いが,アルゴリズム選択の影響を受けやすい。
我々は、この重要な洞察を利用して、omd設定がアルゴリズムの領域において低い後悔を達成していることを示す。
関連論文リスト
- Procurement Auctions via Approximately Optimal Submodular Optimization [53.93943270902349]
競売業者がプライベートコストで戦略的売り手からサービスを取得しようとする競売について検討する。
我々の目標は、取得したサービスの品質と販売者の総コストとの差を最大化する計算効率の良いオークションを設計することである。
論文 参考訳（メタデータ） (2024-11-20T18:06:55Z) - Online Budgeted Matching with General Bids [40.142341503145275]
我々は,オンライン予算マッチング(OBM)の問題に一般入札で対処する。
まず、決定論的オンラインアルゴリズムの競合比を1-kappaの上限とする。
そこで我々はMetaAdと呼ばれる新しいメタアルゴリズムを提案し、最初に証明可能な競合比で異なるアルゴリズムに還元する。
論文 参考訳（メタデータ） (2024-11-06T19:02:42Z) - Selling Joint Ads: A Regret Minimization Perspective [7.288063443108292]
オンライン小売によるモチベーションにより、一品(広告スロットなど)を2つの非排除購入者(商店、ブランド等)に販売する問題を考える。
この問題は、例えば、マーチャントとブランドが商品を宣伝するために競売に協力して入札する状況と、表示されている広告の恩恵を捉えている。
メカニズムは2つの入札を収集し、どちらを割り当てるか、どの支払いを行うかを決定する。
論文 参考訳（メタデータ） (2024-09-12T07:59:10Z) - No-Regret Algorithms in non-Truthful Auctions with Budget and ROI Constraints [0.9694940903078658]
本稿では、ROIと予算制約の対象となる価値を最適化するために、オンラインオートバイディングアルゴリズムを設計する問題について検討する。
我々の主な結果は、最高のリプシッツ関数に関して、ほぼ最適の$tilde O(sqrt T)$の後悔を保証する完全な情報フィードバックを持つアルゴリズムである。
論文 参考訳（メタデータ） (2024-04-15T14:31:53Z) - Autobidders with Budget and ROI Constraints: Efficiency, Regret, and Pacing Dynamics [53.62091043347035]
オンライン広告プラットフォームで競合するオートバイディングアルゴリズムのゲームについて検討する。
本稿では,全ての制約を満たすことを保証し,個人の後悔を解消する勾配に基づく学習アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-01-30T21:59:30Z) - Safe Online Bid Optimization with Return-On-Investment and Budget
Constraints subject to Uncertainty [87.81197574939355]
最適化問題と学習問題の両方について検討する。
我々は、潜在的に線形な数の制約違反を犠牲にして、サブ線形後悔を保証するアルゴリズム、すなわちGCBを提供する。
より興味深いことに、我々はGCB_safe(psi,phi)というアルゴリズムを提供し、サブ線形擬似回帰と安全性w.h.p.の両方を、耐性 psi と phi を受け入れるコストで保証する。
論文 参考訳（メタデータ） (2022-01-18T17:24:20Z) - Double Coverage with Machine-Learned Advice [100.23487145400833]
オンラインの基本的な$k$-serverの問題を学習強化環境で研究する。
我々のアルゴリズムは任意の k に対してほぼ最適の一貫性-破壊性トレードオフを達成することを示す。
論文 参考訳（メタデータ） (2021-03-02T11:04:33Z) - Online Apprenticeship Learning [58.45089581278177]
見習い学習(AL)では、コスト関数にアクセスせずにマルコフ決定プロセス(MDP)が与えられます。
目標は、事前に定義されたコスト関数のセットで専門家のパフォーマンスに一致するポリシーを見つけることです。
ミラー下降型ノンレグレットアルゴリズムを2つ組み合わせることで,OAL問題を効果的に解くことができることを示す。
論文 参考訳（メタデータ） (2021-02-13T12:57:51Z) - The Best of Many Worlds: Dual Mirror Descent for Online Allocation
Problems [7.433931244705934]
本稿では,意思決定者に対して未知の入力モデルを用いて,各要求に対する報酬とリソース消費を生成するデータ駆動型設定について考察する。
様々な入力モデルにおいて,どの入力に直面するかを知ることなく,優れた性能が得られるアルゴリズムの一般クラスを設計する。
我々のアルゴリズムはラグランジアン双対空間で動作し、オンラインミラー降下を用いて更新される各リソースに対して双対乗算器を保持する。
論文 参考訳（メタデータ） (2020-11-18T18:39:17Z) - Experimental Design for Regret Minimization in Linear Bandits [19.8309784360219]
オンライン・リニア・バンドレットにおける後悔を最小限に抑える設計に基づく新しいアルゴリズムを提案する。
我々は、現在最先端の有限時間後悔保証を提供し、このアルゴリズムが帯域幅と半帯域幅の両方のフィードバックシステムに適用可能であることを示す。
論文 参考訳（メタデータ） (2020-11-01T17:59:19Z) - Sub-linear Regret Bounds for Bayesian Optimisation in Unknown Search
Spaces [63.22864716473051]
本稿では,反復により探索空間を拡大(およびシフト)する新しいBOアルゴリズムを提案する。
理論的には、どちらのアルゴリズムにおいても、累積的後悔は線形以下の速度で増大する。
論文 参考訳（メタデータ） (2020-09-05T14:24:40Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。