論文の概要: Optimal No-regret Learning in Repeated First-price Auctions
- arxiv url: http://arxiv.org/abs/2003.09795v7
- Date: Mon, 4 Mar 2024 23:27:02 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-07 04:38:19.931149
- Title: Optimal No-regret Learning in Repeated First-price Auctions
- Title（参考訳）: 繰り返し第一価格オークションにおける最適ノンレグレット学習
- Authors: Yanjun Han, Zhengyuan Zhou, Tsachy Weissman
- Abstract要約: オンライン学習を反復した初価オークションで研究する。
我々は,ほぼ最適の$widetildeO(sqrtT)$ regret boundを達成するための最初の学習アルゴリズムを開発した。
- 参考スコア（独自算出の注目度）: 38.908235632001116
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study online learning in repeated first-price auctions 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 censored feedback: if she wins the bid, then she is not able to
observe the highest bid of the other bidders, which we assume is \textit{iid}
drawn from an unknown distribution. In this paper, we develop the first
learning algorithm that achieves a near-optimal $\widetilde{O}(\sqrt{T})$
regret bound, by exploiting two structural properties of first-price auctions,
i.e. the specific feedback structure and payoff function.
We first formulate the feedback structure in first-price auctions as
partially ordered contextual bandits, a combination of the graph feedback
across actions (bids), the cross learning across contexts (private values), 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. In particular, this framework
leads to an $O(\sqrt{T}\log^{2.5}T)$ regret for first-price auctions when the
bidder's private values are \emph{iid}.
Despite the limitation of the above framework, we further exploit the special
payoff function of first-price auctions to develop a sample-efficient algorithm
even 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価格オークションにおいて学習する。
この目標を達成するために、入札者は検閲されたフィードバックに直面し、もし入札に勝ったら、他の入札者の最も高い入札を見ることができず、それは未知の分布から引き出された「textit{iid}」であると仮定する。
本稿では,1価オークションの2つの構造的性質,すなわち,フィードバック構造とペイオフ関数を活用し,ほぼ最適に近い$\widetilde{o}(\sqrt{t})$ regretboundを実現する最初の学習アルゴリズムを開発した。
まず,最初の価格オークションにおけるフィードバック構造を,部分順序付けされたコンテキストバンディット,アクション間のグラフフィードバックの組み合わせ(bid),コンテキスト間のクロスラーニング(プライベート値),コンテキスト上の部分順序として定式化した。
我々は、この枠組みの強みと弱みの両立を立証し、反逆的文脈では不可能でありながら、アクション/コンテキストサイズからほぼ独立している後悔が可能であることを示す。
特に、このフレームワークは、入札者のプライベート値が \emph{iid} である場合、最初の価格のオークションに対して$O(\sqrt{T}\log^{2.5}T)$ regret をもたらす。
上記のフレームワークの限界にもかかわらず、一価オークションの特別報酬関数を更に活用し、反対に生成されたプライベート値が存在する場合でもサンプル効率のよいアルゴリズムを開発する。
我々は,このアルゴリズムに対して$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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。