論文の概要: 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設定がアルゴリズムの領域において低い後悔を達成していることを示す。
関連論文リスト
- Online Learning in Contextual Second-Price Pay-Per-Click Auctions [47.06746975822902]
オンライン学習は、クリック単価のオークションで学習し、そこでは、各ラウンドのT$で、学習者がいくつかのコンテキストと広告を受信する。
学習者のゴールは、彼女の後悔を最小限に抑えることであり、それは彼女の総収入と託宣戦略のギャップとして定義される。
論文 参考訳(メタデータ) (2023-10-08T07:04:22Z) - Constrained Online Two-stage Stochastic Optimization: Near Optimal
Algorithms via Adversarial Learning [1.994307489466967]
有限地平線上の長期制約付きオンライン2段階最適化をT$周期で検討する。
対戦型学習アルゴリズムからオンライン二段階問題のオンラインアルゴリズムを開発する。
論文 参考訳(メタデータ) (2023-02-02T10:33:09Z) - Autobidders with Budget and ROI Constraints: Efficiency, Regret, and
Pacing Dynamics [77.67037372500495]
オンライン広告プラットフォームで競合するオートバイディングアルゴリズムのゲームについて検討する。
本稿では,全ての制約を満たすことを保証し,個人の後悔を解消する勾配に基づく学習アルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-01-30T21:59:30Z) - A Metaheuristic Algorithm for Large Maximum Weight Independent Set
Problems [58.348679046591265]
ノード重み付きグラフが与えられたとき、ノード重みが最大となる独立した(相互に非隣接な)ノードの集合を見つける。
このアプリケーションで放送されるグラフの中には、数十万のノードと数億のエッジを持つ大きなものもあります。
我々は,不規則なランダム化適応検索フレームワークにおいてメタヒューリスティックな新しい局所探索アルゴリズムを開発した。
論文 参考訳(メタデータ) (2022-03-28T21:34:16Z) - 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) - Efficient Algorithms for Stochastic Repeated Second-price Auctions [0.0]
我々は,繰り返し競売を行うための効率的な逐次入札戦略を開発する。
この問題に対する最初のパラメトリック下界を提供する。
本稿では,探索時コミット帯域幅アルゴリズムを思い起こさせる,より説明可能な戦略を提案する。
論文 参考訳(メタデータ) (2020-11-10T12:45:02Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。