論文の概要: Optimal No-regret Learning in Repeated First-price Auctions
- arxiv url: http://arxiv.org/abs/2003.09795v6
- Date: Thu, 18 May 2023 03:55:39 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-19 23:11:35.942470
- Title: Optimal No-regret Learning in Repeated First-price Auctions
- Title（参考訳）: 繰り返し第一価格オークションにおける最適ノンレグレット学習
- Authors: Yanjun Han, Zhengyuan Zhou, Tsachy Weissman
- Abstract要約: オンライン学習を反復した初価オークションで研究する。
我々は,ほぼ最適の$widetildeO(sqrtT)$ regret boundを達成するための最初の学習アルゴリズムを開発した。
- 参考スコア（独自算出の注目度）: 44.06737450851219
- 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 a 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.
The feedback in first-price auctions combines the graph feedback across
actions (bids), the cross learning across contexts (private values), and a
partial order over the contexts; we generalize it as the partially ordered
contextual bandits. 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)間のグラフフィードバック、コンテキスト間のクロスラーニング(private value)、コンテキスト上の部分順序を組み合わせ、部分的に順序付けられたコンテキストの包帯として一般化する。
我々は、この枠組みの強みと弱みの両立を立証し、反逆的文脈では不可能でありながら、アクション/コンテキストサイズからほぼ独立している後悔が可能であることを示す。
特に、このフレームワークは、入札者のプライベート値が \emph{iid} である場合、最初の価格のオークションに対して$O(\sqrt{T}\log^{2.5}T)$ regret をもたらす。
上記のフレームワークの限界にもかかわらず、一価オークションの特別報酬関数を更に活用し、反対に生成されたプライベート値が存在する場合でもサンプル効率のよいアルゴリズムを開発する。
我々は,このアルゴリズムに対して$O(\sqrt{T}\log^3 T)$ regret boundを定め,第一価格オークションにおける最適学習保証の完全な評価を提供する。
関連論文リスト
- Randomized Truthful Auctions with Learning Agents [10.39657928150242]
本研究では, エージェントが未学習の学習を用いて, 繰り返しオークションに参加する環境について検討する。
競売者が非回帰入札アルゴリズムを用いて第2価格の競売に参加する場合、勝者が真に競売に収束しないことが示される。
我々は,第2代競売の収益と競売との収益を比べて,エムオークションのコンセプトを定義した。
論文 参考訳（メタデータ） (2024-11-14T15:28:40Z) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。