論文の概要: Optimal No-regret Learning in Repeated First-price Auctions
- arxiv url: http://arxiv.org/abs/2003.09795v5
- Date: Fri, 15 Jul 2022 03:07:22 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-21 05:33:35.408498
- Title: Optimal No-regret Learning in Repeated First-price Auctions
- Title（参考訳）: 繰り返し第一価格オークションにおける最適ノンレグレット学習
- Authors: Yanjun Han, Zhengyuan Zhou, Tsachy Weissman
- Abstract要約: オンライン学習を,検閲されたフィードバックで繰り返し最初の価格オークションで研究する。
プライスオークションの構造的特性を活かして,O(sqrtTlog2.5 T)$ regret boundを達成した最初の学習アルゴリズムを開発した。
- 参考スコア（独自算出の注目度）: 44.06737450851219
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study online learning in repeated first-price auctions with censored
feedback, where a bidder, only observing the winning bid at the end of each
auction, learns to adaptively bid in order to maximize her cumulative payoff.
To achieve this goal, the bidder faces a challenging dilemma: if she wins the
bid--the only way to achieve positive payoffs--then she is not able to observe
the highest bid of the other bidders, which we assume is iid drawn from an
unknown distribution. This dilemma, despite being reminiscent of the
exploration-exploitation trade-off in contextual bandits, cannot directly be
addressed by the existing UCB or Thompson sampling algorithms.
In this paper, by exploiting the structural properties of first-price
auctions, we develop the first learning algorithm that achieves
$O(\sqrt{T}\log^{2.5} T)$ regret bound, which is minimax optimal up to $\log$
factors, when the bidder's private values are stochastically generated. We do
so by providing an algorithm on a general class of problems, called the
partially ordered contextual bandits, which combine the graph feedback across
actions, the cross learning across contexts, and a partial order over the
contexts. We establish both strengths and weaknesses of this framework, by
showing a curious separation that a regret nearly independent of the
action/context sizes is possible under stochastic contexts, but is impossible
under adversarial contexts. Despite the limitation of this general framework,
we further exploit the structure of first-price auctions and develop a learning
algorithm that operates sample-efficiently (and computationally efficiently) in
the presence of adversarially generated private values. We establish an
$O(\sqrt{T}\log^3 T)$ regret bound for this algorithm, hence providing a
complete characterization of optimal learning guarantees for first-price
auctions.
- Abstract（参考訳）: オンライン学習は,各競売の終了時のみの入札者が,その累積支払額を最大化するために適応入札を学習する,検閲されたフィードバックで,繰り返し第1価格オークションにおいて学習する。
この目標を達成するために、入札者は挑戦的なジレンマに直面している:もし彼女が入札に勝利すれば、正の報酬を得る唯一の方法は、他の入札者の最も高い入札を観察できない。
このジレンマは、コンテキストバンディットにおける探索・探索のトレードオフを思い起こさせるが、既存のucbやトンプソンサンプリングアルゴリズムでは直接対処できない。
本稿では,1価オークションの構造的性質を生かして,入札者のプライベート値が確率的に生成される場合,最大$\log$ まで最適となる$o(\sqrt{t}\log^{2.5} t)$ regretboundを実現する最初の学習アルゴリズムを開発した。
私たちは、アクション間のグラフフィードバック、コンテキスト間のクロスラーニング、コンテキスト上の部分順序を組み合わせた、部分順序付きコンテキストバンディットと呼ばれる一般的な問題のクラスにアルゴリズムを提供することによって、それを実現する。
我々は、この枠組みの強みと弱みの両立を立証し、反逆的文脈では不可能でありながら、アクション/コンテキストサイズからほぼ独立している後悔が可能であることを示す。
この汎用フレームワークの限界にもかかわらず, 初値オークションの構造をさらに活用し, 反対に生成されたプライベート値の存在下で, サンプル効率 (かつ計算効率) で操作する学習アルゴリズムを開発する。
我々は,このアルゴリズムに対して$O(\sqrt{T}\log^3 T)$ regret boundを定め,第一価格オークションにおける最適学習保証の完全な評価を提供する。
関連論文リスト
- Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedback [58.66941279460248]
人からのフィードバックから学ぶことは、大言語モデル(LLM)のような生成モデルを調整する上で重要な役割を果たす
本稿では,本問題の領域内モデルについて考察する。-文脈的デュエルバンディットと敵対的フィードバックを併用し,真の嗜好ラベルを敵によって反転させることができる。
本稿では,不確実性重み付き最大推定に基づく頑健なコンテキストデュエルバンドイット(アルゴ)を提案する。
論文 参考訳（メタデータ） (2024-04-16T17:59:55Z) - Online Learning in Contextual Second-Price Pay-Per-Click Auctions [47.06746975822902]
オンライン学習は、クリック単価のオークションで学習し、そこでは、各ラウンドのT$で、学習者がいくつかのコンテキストと広告を受信する。
学習者のゴールは、彼女の後悔を最小限に抑えることであり、それは彼女の総収入と託宣戦略のギャップとして定義される。
論文 参考訳（メタデータ） (2023-10-08T07:04:22Z) - Learning in Repeated Multi-Unit Pay-As-Bid Auctions [3.6294895527930504]
複数単位のペイ・アズ・バイドオークションの入札方法を学ぶことの問題点を考察する。
バイド・バイド・オークションの入札方法を学ぶという問題は、アクション・スペースの性質によって困難である。
時間動的計画法を用いて,オフライン問題に対する最適解が得られることを示す。
論文 参考訳（メタデータ） (2023-07-27T20:49:28Z) - 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) - ProportionNet: Balancing Fairness and Revenue for Auction Design with
Deep Learning [55.76903822619047]
本研究では,強力なインセンティブ保証を備えた収益最大化オークションの設計について検討する。
我々は、高い収益と強力なインセンティブ保証を維持しつつ、公平性の懸念に対処するため、深層学習を用いてオークションを近似する手法を拡張した。
論文 参考訳（メタデータ） (2020-10-13T13:54:21Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。