論文の概要: Learning to Bid Optimally and Efficiently in Adversarial First-price Auctions

• arxiv url: http://arxiv.org/abs/2007.04568v1
• Date: Thu, 9 Jul 2020 05:40:39 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-12 04:17:02.652736
• Title: Learning to Bid Optimally and Efficiently in Adversarial First-price Auctions
• Title（参考訳）: 対価第一価格オークションにおける最適かつ効率的な入札の学習
• Authors: Yanjun Han, Zhengyuan Zhou, Aaron Flores, Erik Ordentlich, Tsachy Weissman
• Abstract要約: 我々は,$widetildeO(sqrtT)$ regretを達成する,最初のミニマックス最適オンライン入札アルゴリズムを開発した。 Verizon Mediaから得られた3つの実世界の1価オークションデータセットを用いて,本アルゴリズムを検証した。
• 参考スコア（独自算出の注目度）: 40.30925727499806
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: First-price auctions have very recently swept the online advertising industry, replacing second-price auctions as the predominant auction mechanism on many platforms. This shift has brought forth important challenges for a bidder: how should one bid in a first-price auction, where unlike in second-price auctions, it is no longer optimal to bid one's private value truthfully and hard to know the others' bidding behaviors? In this paper, we take an online learning angle and address the fundamental problem of learning to bid in repeated first-price auctions, where both the bidder's private valuations and other bidders' bids can be arbitrary. We develop the first minimax optimal online bidding algorithm that achieves an $\widetilde{O}(\sqrt{T})$ regret when competing with the set of all Lipschitz bidding policies, a strong oracle that contains a rich set of bidding strategies. This novel algorithm is built on the insight that the presence of a good expert can be leveraged to improve performance, as well as an original hierarchical expert-chaining structure, both of which could be of independent interest in online learning. Further, by exploiting the product structure that exists in the problem, we modify this algorithm--in its vanilla form statistically optimal but computationally infeasible--to a computationally efficient and space efficient algorithm that also retains the same $\widetilde{O}(\sqrt{T})$ minimax optimal regret guarantee. Additionally, through an impossibility result, we highlight that one is unlikely to compete this favorably with a stronger oracle (than the considered Lipschitz bidding policies). Finally, we test our algorithm on three real-world first-price auction datasets obtained from Verizon Media and demonstrate our algorithm's superior performance compared to several existing bidding algorithms.
• Abstract（参考訳）: 第一価オークションはオンライン広告業界を席巻し、多くのプラットフォームで第二価オークションが支配的なオークションメカニズムとなっている。 この変化は、入札者にとって重要な課題を引き起こした: 第1の価格オークションにおいて、第2価格オークションとは異なり、他人の入札行動を知るのが困難で、他人のプライベート価値を競うのがもはや最適ではない、どのように入札すべきなのか? 本稿では,オンライン学習の角度から,入札者の私的評価と他の入札者の入札の両方が任意にできる1次オークションの入札を繰り返すことの学習の基本問題に対処する。 我々は,全てのリプシッツ入札ポリシーの集合と競合するときに,$\widetilde{O}(\sqrt{T})$の後悔を達成する,最初のミニマックス最適オンライン入札アルゴリズムを開発した。 この新しいアルゴリズムは、優れたエキスパートの存在がパフォーマンスを向上させるために活用できるという洞察と、オンライン学習に独立した関心を持つような、オリジナルの階層的なエキスパート連鎖構造に基づいている。 さらに,この問題に存在する積構造を生かして,このアルゴリズムを統計的に最適だが計算不可能であるバニラ形式から,同じ$\widetilde{o}(\sqrt{t})$ minimax の最適後悔保証を保った計算効率と空間効率のよいアルゴリズムに変更する。 さらに、不可能性の結果を通じて、より強力なオラクル(リプシッツ入札ポリシーが考慮されている)と有利に競合する可能性は低いことを強調する。 最後に,verizon mediaから得られた3つの実世界の1価オークションデータセット上でアルゴリズムをテストし,既存の入札アルゴリズムと比較して,アルゴリズムの優れた性能を示す。

関連論文リスト

• Strategically-Robust Learning Algorithms for Bidding in First-Price Auctions [11.988955088595858]
  ゲーム理論と機械学習のインターフェースにおいて,プライスオークションを繰り返し競うことの学習は基本的な問題である。 本稿では,プライスオークションにおける純ストラテジー入札のための新しいコンケーブの定式化を提案し,この問題に対する自然なグラディエント・アセンセント・アルゴリズムの解析に利用した。
  論文  参考訳（メタデータ） (2024-02-12T01:33:33Z)
• 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)
• A Reinforcement Learning Approach in Multi-Phase Second-Price Auction Design [158.0041488194202]
  多相第2価格オークションにおけるリザーブ価格の最適化について検討する。 売り手の視点からは、潜在的に非現実的な入札者の存在下で、環境を効率的に探索する必要がある。 第三に、売り手のステップごとの収益は未知であり、非線形であり、環境から直接観察することさえできない。
  論文  参考訳（メタデータ） (2022-10-19T03:49:05Z)
• No-regret Learning in Repeated First-Price Auctions with Budget Constraints [5.834615090865286]
  定常競争下での最適非予測戦略に対して,RLに基づく入札アルゴリズムを提案する。 提案アルゴリズムは,各ラウンドの最後にすべての入札が明らかになった場合,$widetilde O(sqrt T)$-regretを求める。
  論文  参考訳（メタデータ） (2022-05-29T04:32:05Z)
• Fast Rate Learning in Stochastic First Price Bidding [0.0]
  ファーストプライスのオークションは、プログラム広告におけるビックレーのオークションに基づく伝統的な入札アプローチを大きく置き換えている。 対戦相手の最大入札分布が分かっている場合, 後悔度を著しく低くする方法を示す。 我々のアルゴリズムは、様々な入札分布の文献で提案されている選択肢よりもはるかに高速に収束する。
  論文  参考訳（メタデータ） (2021-07-05T07:48:52Z)
• 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)
• ProportionNet: Balancing Fairness and Revenue for Auction Design with Deep Learning [55.76903822619047]
  本研究では,強力なインセンティブ保証を備えた収益最大化オークションの設計について検討する。 我々は、高い収益と強力なインセンティブ保証を維持しつつ、公平性の懸念に対処するため、深層学習を用いてオークションを近似する手法を拡張した。
  論文  参考訳（メタデータ） (2020-10-13T13:54:21Z)
• Optimal No-regret Learning in Repeated First-price Auctions [38.908235632001116]
  オンライン学習を反復した初価オークションで研究する。 我々は,ほぼ最適の$widetildeO(sqrtT)$ regret boundを達成するための最初の学習アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2020-03-22T03:32:09Z)

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

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