論文の概要: Stochastic Bandits for Multi-platform Budget Optimization in Online
Advertising
- arxiv url: http://arxiv.org/abs/2103.10246v1
- Date: Tue, 16 Mar 2021 22:10:28 GMT
- ステータス: 処理完了
- システム内更新日: 2021-03-19 13:52:01.561951
- Title: Stochastic Bandits for Multi-platform Budget Optimization in Online
Advertising
- Title（参考訳）: オンライン広告におけるマルチプラットフォーム予算最適化のための確率帯域
- Authors: Vashist Avadhanula, Riccardo Colini-Baldeschi, Stefano Leonardi,
Karthik Abinav Sankararaman, Okke Schrijvers
- Abstract要約: 我々は、複数のプラットフォームでキャンペーンのために広告主の与えられた予算を最適に費やしたいオンライン広告システムの問題を研究します。
当社は、複数の広告プラットフォームを持つ大規模なインターネットオンライン広告会社の実世界のデータセットを使用して、アルゴリズムが一般的なベンチマークを上回っていることを示す。
- 参考スコア（独自算出の注目度）: 8.8896707993459
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the problem of an online advertising system that wants to optimally
spend an advertiser's given budget for a campaign across multiple platforms,
without knowing the value for showing an ad to the users on those platforms. We
model this challenging practical application as a Stochastic Bandits with
Knapsacks problem over $T$ rounds of bidding with the set of arms given by the
set of distinct bidding $m$-tuples, where $m$ is the number of platforms. We
modify the algorithm proposed in Badanidiyuru \emph{et al.,} to extend it to
the case of multiple platforms to obtain an algorithm for both the discrete and
continuous bid-spaces. Namely, for discrete bid spaces we give an algorithm
with regret $O\left(OPT \sqrt {\frac{mn}{B} }+ \sqrt{mn OPT}\right)$, where
$OPT$ is the performance of the optimal algorithm that knows the distributions.
For continuous bid spaces the regret of our algorithm is
$\tilde{O}\left(m^{1/3} \cdot \min\left\{ B^{2/3}, (m T)^{2/3} \right\}
\right)$. When restricted to this special-case, this bound improves over
Sankararaman and Slivkins in the regime $OPT \ll T$, as is the case in the
particular application at hand. Second, we show an $ \Omega\left (\sqrt {m OPT}
\right)$ lower bound for the discrete case and an $\Omega\left( m^{1/3}
B^{2/3}\right)$ lower bound for the continuous setting, almost matching the
upper bounds. Finally, we use a real-world data set from a large internet
online advertising company with multiple ad platforms and show that our
algorithms outperform common benchmarks and satisfy the required properties
warranted in the real-world application.
- Abstract（参考訳）: 我々は,複数のプラットフォームにまたがる広告キャンペーンにおいて,広告主の予算を最適に利用しようとするオンライン広告システムの問題について,それらのプラットフォーム上でユーザに対して広告を表示する価値を知らずに検討する。
この挑戦的な実践的応用を、knapsacks問題のある確率的バンディットとしてモデル化し、$m$-tuplesという異なる入札のセットによって与えられたアームセットを$t$の入札問題に当てはめ、$m$をプラットフォーム数とする。
我々は、badanidiyuru \emph{et al.,} で提案するアルゴリズムを複数のプラットフォームに拡張し、離散入札空間と連続入札空間の両方のアルゴリズムを得る。
すなわち、離散入札空間に対して、後悔するアルゴリズムに$o\left(opt \sqrt {\frac{mn}{b} }+ \sqrt{mn opt}\right)$を与え、ここで$opt$は分布を知る最適なアルゴリズムの性能である。
連続入札空間に対しては、我々のアルゴリズムの後悔は$\tilde{O}\left(m^{1/3} \cdot \min\left\{ B^{2/3}, (m T)^{2/3} \right\right)$である。
この特別なケースに制限された場合、このバウンダリは、手元にある特定のアプリケーションの場合と同様に、体制$OPT \ll T$のサンカラマンとスリブキンスよりも改善される。
第二に、離散ケースに対する$ \Omega\left (\sqrt {m OPT} \right)$下界と連続設定に対する$ \Omega\left(m^{1/3} B^{2/3}\right)$下界を示し、上界とほぼ一致する。
最後に、複数の広告プラットフォームを持つ巨大インターネットオンライン広告会社の実世界のデータセットを使用し、我々のアルゴリズムが一般的なベンチマークを上回り、現実世界のアプリケーションで保証される要求された特性を満たすことを示す。
関連論文リスト
- Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。
SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
論文 参考訳（メタデータ） (2023-12-13T11:08:25Z) - Projection-free Online Exp-concave Optimization [21.30065439295409]
LOOをベースとしたONSスタイルのアルゴリズムを提案する。これは全体$O(T)$コールを使用して,$widetildeO(n2/3T2/3)$でバウンドされた最悪のケースを保証します。
我々のアルゴリズムは、重要かつ確実な低次元データシナリオにおいて最も興味深い。
論文 参考訳（メタデータ） (2023-02-09T18:58:05Z) - Combinatorial Bandits without Total Order for Arms [52.93972547896022]
セット依存報酬分布を捕捉し、武器の合計順序を仮定しない報酬モデルを提案する。
我々は、新しい後悔分析を開発し、$Oleft(frack2 n log Tepsilonright)$ gap-dependent regret boundと$Oleft(k2sqrtn T log Tright)$ gap-dependent regret boundを示す。
論文 参考訳（メタデータ） (2021-03-03T23:08:59Z) - An Algorithm for Stochastic and Adversarial Bandits with Switching Costs [10.549307055348596]
そこで本研究では,マルチアームバンディットのスイッチングコストを考慮したアルゴリズムを提案し,そのアルゴリズムがアームを切り替える度に$lambda$を支払う。
私たちのアルゴリズムは、Zimmert and Seldin(2021)のTsallis-INFアルゴリズムの適応に基づいています。
論文 参考訳（メタデータ） (2021-02-19T11:03:51Z) - Top-$k$ eXtreme Contextual Bandits with Arm Hierarchy [71.17938026619068]
我々は、腕の総数が膨大であることができるトップ$ k$極端な文脈的包帯問題を研究します。
まず,Inverse Gap Weighting戦略を用いて,非極端に実現可能な設定のアルゴリズムを提案する。
我々のアルゴリズムは、$O(ksqrt(A-k+1)T log (|mathcalF|T))$である。
論文 参考訳（メタデータ） (2021-02-15T19:10:52Z) - Fine-Grained Gap-Dependent Bounds for Tabular MDPs via Adaptive
Multi-Step Bootstrap [84.66885506098724]
本稿では,アダプティブ・マルチステップ・ブートストラップ (AMB) を用いた表層有限水平マルコフ決定過程 (MDP) のモデルフリーアルゴリズムを提案する。
AMBは,部分最適ギャップの逆の和でのみスケールする,ギャップ依存的後悔境界を達成できることを示す。
また、AMB は $frac|Z_mul|Delta_min$ regret という追加の $frac|Z_mul|Delta_min$ を被っていることも示しています。
論文 参考訳（メタデータ） (2021-02-09T07:46:34Z) - Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits
with Linear Payoff Functions [53.77572276969548]
我々は、C$2$UCBアルゴリズムが分割マトロイド制約に対して最適な後悔結合$tildeO(dsqrtkT + dk)$を有することを示した。
一般的な制約に対して,C$2$UCBアルゴリズムで腕の報酬推定値を変更するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-20T04:29:18Z) - Fully Gap-Dependent Bounds for Multinomial Logit Bandit [5.132017939561661]
マルチノミアルロジット (MNL) バンディット問題について検討し、各ステップごとに、販売者は、N$アイテムのプールから最大でK$のサイズを提供する。
i) $widetildeO(sum_i = 1N Delta_i-2)$ time steps with high probability, (ii) $O(sum_i notin S* KDelta_i)というアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-11-19T17:52:12Z) - Adversarial Dueling Bandits [85.14061196945599]
本稿では,反逆デュエルバンドにおける後悔の問題を紹介する。
学習者は、繰り返し一対のアイテムを選択し、このペアに対する相対的な二項利得フィードバックのみを観察しなければならない。
我々の主な成果は、EmphBorda-winnerの1組の$K$アイテムと比較して、T$ラウンド後悔するアルゴリズムです。
論文 参考訳（メタデータ） (2020-10-27T19:09:08Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。