論文の概要: Optimal Spend Rate Estimation and Pacing for Ad Campaigns with Budgets
- arxiv url: http://arxiv.org/abs/2202.05881v1
- Date: Fri, 4 Feb 2022 20:18:00 GMT
- ステータス: 処理完了
- システム内更新日: 2022-02-20 16:30:27.818931
- Title: Optimal Spend Rate Estimation and Pacing for Ad Campaigns with Budgets
- Title（参考訳）: 予算付き広告キャンペーンにおける最適散布率推定とペイシング
- Authors: Bhuvesh Kumar, Jamie Morgenstern, and Okke Schrijvers
- Abstract要約: 本稿では、時間によって異なる印象と競争の2つのモデルについて考察する。
本稿では,支出計画の正確性と,その結果のエンドツーエンドの予算管理システムの双方について,最初の学習理論的保証を示す。
- 参考スコア（独自算出の注目度）: 6.870572485624023
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: Online ad platforms offer budget management tools for advertisers that aim to
maximize the number of conversions given a budget constraint. As the volume of
impressions, conversion rates and prices vary over time, these budget
management systems learn a spend plan (to find the optimal distribution of
budget over time) and run a pacing algorithm which follows the spend plan.
This paper considers two models for impressions and competition that varies
with time: a) an episodic model which exhibits stationarity in each episode,
but each episode can be arbitrarily different from the next, and b) a model
where the distributions of prices and values change slowly over time. We
present the first learning theoretic guarantees on both the accuracy of spend
plans and the resulting end-to-end budget management system. We present four
main results: 1) for the episodic setting we give sample complexity bounds for
the spend rate prediction problem: given $n$ samples from each episode, with
high probability we have $|\widehat{\rho}_e - \rho_e| \leq
\tilde{O}(\frac{1}{n^{1/3}})$ where $\rho_e$ is the optimal spend rate for the
episode, $\widehat{\rho}_e$ is the estimate from our algorithm, 2) we extend
the algorithm of Balseiro and Gur (2017) to operate on varying, approximate
spend rates and show that the resulting combined system of optimal spend rate
estimation and online pacing algorithm for episodic settings has regret that
vanishes in number of historic samples $n$ and the number of rounds $T$, 3) for
non-episodic but slowly-changing distributions we show that the same approach
approximates the optimal bidding strategy up to a factor dependent on the
rate-of-change of the distributions and 4) we provide experiments showing that
our algorithm outperforms both static spend plans and non-pacing across a wide
variety of settings.
- Abstract（参考訳）: オンライン広告プラットフォームは、予算制約によってコンバージョン数を最大化しようとする広告主に予算管理ツールを提供する。
インプレッションの量、変換率、価格が時間とともに変化するにつれて、これらの予算管理システムは支出計画(予算の最適配分を見つけるために)を学び、支出計画に従うペーシングアルゴリズムを実行する。
本稿では、時間によって異なる印象と競争の2つのモデルについて考察する。
a)各エピソードに定常性を示すが,各エピソードは次のエピソードと任意に異なることができるエピソディクスモデル,及び
b)価格と価値の分布が時間とともにゆっくりと変化するモデル
本稿では,支出計画の正確性と,その結果のエンドツーエンドの予算管理システムの両方について,最初の学習理論的保証を示す。
主な結果が4つあります
1) エピソディック設定では、各エピソードから与えられた$n$ のサンプルを高い確率で与えると、$|\widehat{\rho}_e - \rho_e| \leq \tilde{o}(\frac{1}{n^{1/3}})$ ここで$\rho_e$ はエピソードの最適な支出率、$\widehat{\rho}_e$ はアルゴリズムからの見積もりである。
2)BalseiroとGur(2017)のアルゴリズムを拡張して、様々な近似的な支出率で運用し、その結果得られた最適支出率推定とエピソード設定のためのオンラインペイシングアルゴリズムの組み合わせが、歴史的なサンプル数$n$とラウンド数$T$の減少を後悔していることを示す。
3)非等方的だが緩やかに変化する分布に対して、同じアプローチが最適入札戦略を、分布の変化率に依存する要因まで近似することを示す。
4)我々のアルゴリズムが,様々な設定で静的支出計画と非ペーシングの両方を上回っていることを示す実験を行った。
関連論文リスト
- Stochastic Multi-round Submodular Optimization with Budget [7.902059578326225]
我々は、アイテムの部分集合上で定義された単調部分モジュラー目的関数の和を、複数のラウンドで適応的に最大化することを目指している。
目的関数はイベントの実現にも依存しており、全てのラウンドで選択できるアイテムの総数は、限られた予算で制限されている。
論文 参考訳（メタデータ） (2024-04-21T18:24:43Z) - Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。
SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
論文 参考訳（メタデータ） (2023-12-13T11:08:25Z) - Rate-Optimal Policy Optimization for Linear Markov Decision Processes [65.5958446762678]
最安値の$widetilde O (sqrt K)$ regret, $K$はエピソード数を表す。
我々の研究は、バンディットフィードバックのある設定において最適な収束率(w.r.t.$K$)を確立する最初のものである。
現在、最適なレート保証を持つアルゴリズムは知られていない。
論文 参考訳（メタデータ） (2023-08-28T15:16:09Z) - Stochastic Approximation Approaches to Group Distributionally Robust Optimization and Beyond [89.72693227960274]
本稿では,グループ分散ロバスト最適化 (GDRO) を,$m$以上の異なる分布をうまく処理するモデルを学習する目的で検討する。
各ラウンドのサンプル数を$m$から1に抑えるため、GDROを2人でプレイするゲームとして、一方のプレイヤーが実行し、他方のプレイヤーが非公開のマルチアームバンディットのオンラインアルゴリズムを実行する。
第2のシナリオでは、最大リスクではなく、平均的最上位k$リスクを最適化し、分散の影響を軽減することを提案する。
論文 参考訳（メタデータ） (2023-02-18T09:24:15Z) - Robust Budget Pacing with a Single Sample [9.826939499674676]
ほぼ最適の$tilde O(sqrtT)$-regretを達成するのに、分布毎に1つのサンプルだけで十分であることを示す。
ほぼ最適の$tilde O(sqrtT)$-regretを達成するのに、分布毎に1つのサンプルだけで十分であることを示す。
論文 参考訳（メタデータ） (2023-02-03T21:23:09Z) - Human-in-the-loop: Provably Efficient Preference-based Reinforcement
Learning with General Function Approximation [107.54516740713969]
本研究は,RL(Human-in-the-loop reinforcement learning)を軌道的嗜好で検討する。
各ステップで数値的な報酬を受ける代わりに、エージェントは人間の監督者から軌道上のペアよりも優先される。
一般関数近似を用いたPbRLの楽観的モデルベースアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-05-23T09:03:24Z) - REX: Revisiting Budgeted Training with an Improved Schedule [14.618325490983052]
本稿では,Reflectred Exponential(REX)スケジュールと呼ばれる新しいプロファイルとサンプリングレートの組み合わせを提案する。
REXは、いくつかの最先端の学習率スケジュールのパフォーマンスを一致または超えながら、低予算で線形スケジュールを上回ります。
論文 参考訳（メタデータ） (2021-07-09T04:17:35Z) - Online Stochastic Optimization with Wasserstein Based Non-stationarity [12.91020811577007]
有限期間の地平線上の複数の予算制約を持つ一般的なオンライン最適化問題を検討する。
意思決定者の目標は、予算制約の対象となる累積報酬を最大化することである。
この定式化は、オンラインリニアプログラミングやネットワーク収益管理を含む幅広いアプリケーションを取り込む。
論文 参考訳（メタデータ） (2020-12-13T04:47:37Z) - Minimax Regret for Stochastic Shortest Path with Adversarial Costs and
Known Transition [37.6975819766632]
我々は、敵対コストと既知の移行で最短経路問題を研究します。
ミニマックスの後悔は,全情報設定と盗聴フィードバック設定に対して$widetildeO(sqrtDTstar K)$および$widetildeO(sqrtDTstar SA K)$であることを示す。
論文 参考訳（メタデータ） (2020-12-07T20:55:28Z) - Private Stochastic Non-Convex Optimization: Adaptive Algorithms and
Tighter Generalization Bounds [72.63031036770425]
有界非次元最適化のための差分プライベート(DP)アルゴリズムを提案する。
標準勾配法に対する経験的優位性について,2つの一般的なディープラーニング手法を実証する。
論文 参考訳（メタデータ） (2020-06-24T06:01:24Z) - Stochastic Shortest Path with Adversarially Changing Costs [57.90236104782219]
最短経路 (SSP) は計画と制御においてよく知られた問題である。
また, 時間とともにコストの逆変化を考慮に入れた逆SSPモデルを提案する。
我々は、この自然な逆SSPの設定を最初に検討し、それに対するサブ線形後悔を得る。
論文 参考訳（メタデータ） (2020-06-20T12:10:35Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。