論文の概要: Efficient Algorithms for Stochastic Repeated Second-price Auctions
- arxiv url: http://arxiv.org/abs/2011.05072v2
- Date: Fri, 26 Feb 2021 08:04:20 GMT
- ステータス: 処理完了
- システム内更新日: 2022-09-27 06:46:42.753763
- Title: Efficient Algorithms for Stochastic Repeated Second-price Auctions
- Title(参考訳): 確率的繰り返し2値オークションの効率的なアルゴリズム
- Authors: Juliette Achddou (VALDA), Olivier Capp\'e (VALDA), Aur\'elien Garivier
(UMPA-ENSL)
- Abstract要約: 我々は,繰り返し競売を行うための効率的な逐次入札戦略を開発する。
この問題に対する最初のパラメトリック下界を提供する。
本稿では,探索時コミット帯域幅アルゴリズムを思い起こさせる,より説明可能な戦略を提案する。
- 参考スコア(独自算出の注目度): 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Developing efficient sequential bidding strategies for repeated auctions is
an important practical challenge in various marketing tasks. In this setting,
the bidding agent obtains information, on both the value of the item at sale
and the behavior of the other bidders, only when she wins the auction. Standard
bandit theory does not apply to this problem due to the presence of
action-dependent censoring. In this work, we consider second-price auctions and
propose novel, efficient UCB-like algorithms for this task. These algorithms
are analyzed in the stochastic setting, assuming regularity of the distribution
of the opponents' bids. We provide regret upper bounds that quantify the
improvement over the baseline algorithm proposed in the literature. The
improvement is particularly significant in cases when the value of the
auctioned item is low, yielding a spectacular reduction in the order of the
worst-case regret. We further provide the first parametric lower bound for this
problem that applies to generic UCB-like strategies. As an alternative, we
propose more explainable strategies which are reminiscent of the Explore Then
Commit bandit algorithm. We provide a critical analysis of this class of
strategies, showing both important advantages and limitations. In particular,
we provide a minimax lower bound and propose a nearly minimax-optimal instance
of this class.
- Abstract(参考訳): 反復オークションにおける効率的な逐次入札戦略の開発は,様々なマーケティングタスクにおいて重要な課題である。
この設定では、入札エージェントは、販売中の商品の価値と他の入札者の行動の両方について、オークションに勝った場合にのみ情報を取得する。
標準バンディット理論は、行動依存的な検閲が存在するため、この問題には適用されない。
そこで本研究では,2次価格オークションを検討し,新しい効率的なucbライクなアルゴリズムを提案する。
これらのアルゴリズムは確率的設定で解析され、相手の入札の分布の規則性を仮定する。
文献に提案されているベースラインアルゴリズムに対する改善を定量化するための後悔の上限を提供する。
この改善は、オークション商品の価値が低い場合に特に重要であり、最悪の場合の後悔の順序が著しく低下する。
さらに,本問題に対する最初のパラメトリック下限を一般の ucb 的な戦略に適用する。
代替として、探索時コミット帯域幅アルゴリズムを連想させる説明可能な戦略を提案する。
このタイプの戦略を批判的に分析し、重要な利点と限界の両方を示します。
特に、ミニマックス下界を提供し、このクラスのほぼ最小最適インスタンスを提案する。
関連論文リスト
- Procurement Auctions via Approximately Optimal Submodular Optimization [53.93943270902349]
競売業者がプライベートコストで戦略的売り手からサービスを取得しようとする競売について検討する。
我々の目標は、取得したサービスの品質と販売者の総コストとの差を最大化する計算効率の良いオークションを設計することである。
論文 参考訳(メタデータ) (2024-11-20T18:06:55Z) - Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedback [58.66941279460248]
人からのフィードバックから学ぶことは、大言語モデル(LLM)のような生成モデルを調整する上で重要な役割を果たす
本稿では,本問題の領域内モデルについて考察する。-文脈的デュエルバンディットと敵対的フィードバックを併用し,真の嗜好ラベルを敵によって反転させることができる。
本稿では,不確実性重み付き最大推定に基づく頑健なコンテキストデュエルバンドイット(アルゴ)を提案する。
論文 参考訳(メタデータ) (2024-04-16T17:59:55Z) - Strategically-Robust Learning Algorithms for Bidding in First-Price Auctions [11.988955088595858]
ゲーム理論と機械学習のインターフェースにおいて,プライスオークションを繰り返し競うことの学習は基本的な問題である。
本稿では,プライスオークションにおける純ストラテジー入札のための新しいコンケーブの定式化を提案し,この問題に対する自然なグラディエント・アセンセント・アルゴリズムの解析に利用した。
論文 参考訳(メタデータ) (2024-02-12T01:33:33Z) - A Reinforcement Learning Approach in Multi-Phase Second-Price Auction
Design [158.0041488194202]
多相第2価格オークションにおけるリザーブ価格の最適化について検討する。
売り手の視点からは、潜在的に非現実的な入札者の存在下で、環境を効率的に探索する必要がある。
第三に、売り手のステップごとの収益は未知であり、非線形であり、環境から直接観察することさえできない。
論文 参考訳(メタデータ) (2022-10-19T03:49:05Z) - Dynamic Budget Throttling in Repeated Second-Price Auctions [11.823210231891517]
スロットリングは人気のある選択であり、広告主の総支出を管理するために、オークションのサブセットだけを選択することで、広告主の総支出を管理する。
本稿では,2次価格の繰り返しオークションにおいて,単一の広告主の動的予算絞りプロセスの理論的パノラマを提供する。
本研究は, 競売におけるスロットリングの理論的研究のギャップを埋めるものであり, この一般的な予算平滑化戦略の能力を明らかにするものである。
論文 参考訳(メタデータ) (2022-07-11T08:12:02Z) - Fast Rate Learning in Stochastic First Price Bidding [0.0]
ファーストプライスのオークションは、プログラム広告におけるビックレーのオークションに基づく伝統的な入札アプローチを大きく置き換えている。
対戦相手の最大入札分布が分かっている場合, 後悔度を著しく低くする方法を示す。
我々のアルゴリズムは、様々な入札分布の文献で提案されている選択肢よりもはるかに高速に収束する。
論文 参考訳(メタデータ) (2021-07-05T07:48:52Z) - Learning over no-Preferred and Preferred Sequence of items for Robust
Recommendation [66.8722561224499]
暗黙のフィードバックよりも大規模なレコメンダーシステム(RS)を訓練するための理論的に確立されたシーケンシャル戦略を提案する。
本稿では、モデルパラメータをモメンタリメソッドまたはグラデーションベースのアプローチで更新するこの戦略の2つのバリエーションを紹介します。
論文 参考訳(メタデータ) (2020-12-12T22:10:15Z) - 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) - Adaptive Discretization for Adversarial Lipschitz Bandits [85.39106976861702]
リプシッツ・バンディット(Lipschitz bandits)は、大規模で構造化された行動空間を研究する多腕バンディットの顕著なバージョンである。
ここでの中心的なテーマは、アクション空間の適応的な離散化であり、より有望な領域で徐々にズームインする'である。
逆バージョンにおける適応的な離散化のための最初のアルゴリズムを提供し、インスタンス依存の後悔境界を導出する。
論文 参考訳(メタデータ) (2020-06-22T16:06:25Z) - Optimal No-regret Learning in Repeated First-price Auctions [38.908235632001116]
オンライン学習を反復した初価オークションで研究する。
我々は,ほぼ最適の$widetildeO(sqrtT)$ regret boundを達成するための最初の学習アルゴリズムを開発した。
論文 参考訳(メタデータ) (2020-03-22T03:32:09Z) - Adversarial Attacks on Linear Contextual Bandits [87.08004581867537]
悪意のあるエージェントは、望ましい行動を実行するためにバンディットアルゴリズムを攻撃するインセンティブを持つ可能性がある。
悪意のあるエージェントは、線形コンテキストのバンドイットアルゴリズムに任意のアーム$T - o(T)$倍を$T$ステップで引き出すように強制することができる。
また,悪意のあるエージェントが単一コンテキストにおける帯域幅アルゴリズムの動作に影響を与えることに関心がある場合についても検討する。
論文 参考訳(メタデータ) (2020-02-10T15:04:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。