論文の概要: Fast Rate Learning in Stochastic First Price Bidding

• arxiv url: http://arxiv.org/abs/2107.01835v1
• Date: Mon, 5 Jul 2021 07:48:52 GMT
• ステータス: 処理完了
• システム内更新日: 2021-07-06 15:15:20.116483
• Title: Fast Rate Learning in Stochastic First Price Bidding
• Title（参考訳）: 確率的ファースト価格入札における高速学習
• Authors: Juliette Achddou (PSL, DI-ENS, VALDA ), Olivier Capp\'e (LTCI, VALDA ), Aur\'elien Garivier (UMPA-ENSL)
• Abstract要約: ファーストプライスのオークションは、プログラム広告におけるビックレーのオークションに基づく伝統的な入札アプローチを大きく置き換えている。 対戦相手の最大入札分布が分かっている場合, 後悔度を著しく低くする方法を示す。 我々のアルゴリズムは、様々な入札分布の文献で提案されている選択肢よりもはるかに高速に収束する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: First-price auctions have largely replaced traditional bidding approaches based on Vickrey auctions in programmatic advertising. As far as learning is concerned, first-price auctions are more challenging because the optimal bidding strategy does not only depend on the value of the item but also requires some knowledge of the other bids. They have already given rise to several works in sequential learning, many of which consider models for which the value of the buyer or the opponents' maximal bid is chosen in an adversarial manner. Even in the simplest settings, this gives rise to algorithms whose regret grows as $\sqrt{T}$ with respect to the time horizon $T$. Focusing on the case where the buyer plays against a stationary stochastic environment, we show how to achieve significantly lower regret: when the opponents' maximal bid distribution is known we provide an algorithm whose regret can be as low as $\log^2(T)$; in the case where the distribution must be learnt sequentially, a generalization of this algorithm can achieve $T^{1/3+ \epsilon}$ regret, for any $\epsilon>0$. To obtain these results, we introduce two novel ideas that can be of interest in their own right. First, by transposing results obtained in the posted price setting, we provide conditions under which the first-price biding utility is locally quadratic around its optimum. Second, we leverage the observation that, on small sub-intervals, the concentration of the variations of the empirical distribution function may be controlled more accurately than by using the classical Dvoretzky-Kiefer-Wolfowitz inequality. Numerical simulations confirm that our algorithms converge much faster than alternatives proposed in the literature for various bid distributions, including for bids collected on an actual programmatic advertising platform.
• Abstract（参考訳）: ファーストプライスオークションは、プログラム広告におけるビックリーオークションに基づく従来の入札アプローチに取って代わった。 学習に関しては、最適入札戦略はアイテムの価値に依存するだけでなく、他の入札についてある程度の知識を必要とするため、第一価格オークションはより困難である。 彼らはすでにシーケンシャルラーニングにおいていくつかの作品を生み出しており、その多くが、買い手または相手の最大入札の価値が敵対的に選択されるモデルを考える。 最も単純な設定であっても、これは時間の地平線に関して$\sqrt{T}$として後悔するアルゴリズムを生み出す。 静的確率環境に対してバイヤーがプレーする場合には, 相手の最大入札分布が分かっていれば, 後悔度が$\log^2(T)$まで低いアルゴリズムが提供されるので, アルゴリズムの一般化により, 任意の$\epsilon>0$に対して$T^{1/3+ \epsilon}$後悔度を達成できる。 これらの結果を得るために,本研究では,それぞれが興味を持つ新しいアイデアを2つ紹介する。 まず、ポスト価格設定の結果を変換することにより、第1価格入札ユーティリティが最適値付近で局所的に二次的な条件を提供する。 第2に、小さな部分相互作用において、経験分布関数の変動の濃度が古典的なドヴォルネツキー・キーファー・ウルフウィッツの不等式よりも正確に制御できるという観測結果を活用する。 数値シミュレーションにより,本アルゴリズムは,実際のプログラム広告プラットフォームで収集した入札を含む,様々な入札分布の文献で提案されている選択肢よりもはるかに高速に収束することを確認した。

関連論文リスト

• No-Regret Algorithms in non-Truthful Auctions with Budget and ROI Constraints [0.9694940903078658]
  本稿では、ROIと予算制約の対象となる価値を最適化するために、オンラインオートバイディングアルゴリズムを設計する問題について検討する。 我々の主な結果は、最高のリプシッツ関数に関して、ほぼ最適の$tilde O(sqrt T)$の後悔を保証する完全な情報フィードバックを持つアルゴリズムである。
  論文  参考訳（メタデータ） (2024-04-15T14:31:53Z)
• Online Learning in Contextual Second-Price Pay-Per-Click Auctions [47.06746975822902]
  オンライン学習は、クリック単価のオークションで学習し、そこでは、各ラウンドのT$で、学習者がいくつかのコンテキストと広告を受信する。 学習者のゴールは、彼女の後悔を最小限に抑えることであり、それは彼女の総収入と託宣戦略のギャップとして定義される。
  論文  参考訳（メタデータ） (2023-10-08T07:04:22Z)
• Autobidders with Budget and ROI Constraints: Efficiency, Regret, and Pacing Dynamics [53.62091043347035]
  オンライン広告プラットフォームで競合するオートバイディングアルゴリズムのゲームについて検討する。 本稿では,全ての制約を満たすことを保証し,個人の後悔を解消する勾配に基づく学習アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-01-30T21:59:30Z)
• Leveraging the Hints: Adaptive Bidding in Repeated First-Price Auctions [42.002983450368134]
  プライスオークションでの競売の仕方について検討する。 第二価格のオークションとは異なり、個人価値を真に入札することはもはや最適ではない。 1つは1つの点予測が可能であり、もう1つはヒント間隔が利用可能である。
  論文  参考訳（メタデータ） (2022-11-05T19:20:53Z)
• A Reinforcement Learning Approach in Multi-Phase Second-Price Auction Design [158.0041488194202]
  多相第2価格オークションにおけるリザーブ価格の最適化について検討する。 売り手の視点からは、潜在的に非現実的な入札者の存在下で、環境を効率的に探索する必要がある。 第三に、売り手のステップごとの収益は未知であり、非線形であり、環境から直接観察することさえできない。
  論文  参考訳（メタデータ） (2022-10-19T03:49:05Z)
• Efficient Algorithms for Stochastic Repeated Second-price Auctions [0.0]
  我々は,繰り返し競売を行うための効率的な逐次入札戦略を開発する。 この問題に対する最初のパラメトリック下界を提供する。 本稿では,探索時コミット帯域幅アルゴリズムを思い起こさせる,より説明可能な戦略を提案する。
  論文  参考訳（メタデータ） (2020-11-10T12:45:02Z)
• A novel auction system for selecting advertisements in Real-Time bidding [68.8204255655161]
  リアルタイム入札(Real-Time Bidding)は、インターネット広告システムで、近年非常に人気を集めている。 本稿では、経済的な側面だけでなく、広告システムの機能にかかわる他の要因も考慮した、新たなアプローチによる代替ベッティングシステムを提案する。
  論文  参考訳（メタデータ） (2020-10-22T18:36:41Z)
• Learning to Bid Optimally and Efficiently in Adversarial First-price Auctions [40.30925727499806]
  我々は,$widetildeO(sqrtT)$ regretを達成する,最初のミニマックス最適オンライン入札アルゴリズムを開発した。 Verizon Mediaから得られた3つの実世界の1価オークションデータセットを用いて,本アルゴリズムを検証した。
  論文  参考訳（メタデータ） (2020-07-09T05:40:39Z)
• Optimal No-regret Learning in Repeated First-price Auctions [38.908235632001116]
  オンライン学習を反復した初価オークションで研究する。 我々は,ほぼ最適の$widetildeO(sqrtT)$ regret boundを達成するための最初の学習アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2020-03-22T03:32:09Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。