論文の概要: Bandit Sequential Posted Pricing via Half-Concavity
- arxiv url: http://arxiv.org/abs/2312.12794v1
- Date: Wed, 20 Dec 2023 06:34:15 GMT
- ステータス: 処理完了
- システム内更新日: 2023-12-21 16:40:08.576347
- Title: Bandit Sequential Posted Pricing via Half-Concavity
- Title（参考訳）: banditシーケンシャルな価格設定はハーフコンベビティ経由
- Authors: Sahil Singla, Yifan Wang
- Abstract要約: バンディット学習モデルにおいて,逐次ポスト価格について検討した。
各ラウンドで、売り手は$n$の買い手に対して$n$の価格を投稿する。
我々の主な成果は、単一項目のシーケンシャルなポスト価格に対して、ほぼ最適の後悔境界を得る。
- 参考スコア（独自算出の注目度）: 14.618166373146643
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Sequential posted pricing auctions are popular because of their simplicity in
practice and their tractability in theory. A usual assumption in their study is
that the Bayesian prior distributions of the buyers are known to the seller,
while in reality these priors can only be accessed from historical data. To
overcome this assumption, we study sequential posted pricing in the bandit
learning model, where the seller interacts with $n$ buyers over $T$ rounds: In
each round the seller posts $n$ prices for the $n$ buyers and the first buyer
with a valuation higher than the price takes the item. The only feedback that
the seller receives in each round is the revenue.
Our main results obtain nearly-optimal regret bounds for single-item
sequential posted pricing in the bandit learning model. In particular, we
achieve an $\tilde{O}(\mathsf{poly}(n)\sqrt{T})$ regret for buyers with
(Myerson's) regular distributions and an
$\tilde{O}(\mathsf{poly}(n)T^{{2}/{3}})$ regret for buyers with general
distributions, both of which are tight in the number of rounds $T$. Our result
for regular distributions was previously not known even for the single-buyer
setting and relies on a new half-concavity property of the revenue function in
the value space. For $n$ sequential buyers, our technique is to run a
generalized single-buyer algorithm for all the buyers and to carefully bound
the regret from the sub-optimal pricing of the suffix buyers.
- Abstract（参考訳）: 列挙された価格オークションは、実践の単純さと理論のトラクタビリティによって人気がある。
彼らの研究における通常の仮定は、購入者のベイズ以前の分布は販売者に知られているが、実際にはこれらの事前分布は歴史的データからのみアクセスできるというものである。
この仮定を克服するために、バンディット学習モデルにおいて、売り手が$T$のラウンドで$n$の買い手と相互作用する連続的な価格について調査する: 各ラウンドでは、売り手は$n$の買い手に対して$n$の価格を投稿し、最初の買い手は、その商品を受け取った価格よりも高い価格で評価する。
販売者が各ラウンドで受け取る唯一のフィードバックは収益である。
本研究の主な成果は,帯域学習モデルにおける単一項目の逐次投稿価格に対して,ほぼ最適な後悔境界を求めることである。
特に、(myersonの)正規分布を持つ買い手に対して$\tilde{o}(\mathsf{poly}(n)\sqrt{t})$を、一般分布を持つ買い手に対して$\tilde{o}(\mathsf{poly}(n)t^{{2}/{3}})$を、どちらも$t$のラウンド数でタイトである。
正規分布に対する結果は,従来シングルバイヤー設定においても知られておらず,価値空間における収益関数の新たな半透明性に依存している。
シーケンシャルバイヤー$n$の場合、我々の技術は、すべてのバイヤーに対して一般化されたシングルバイヤーアルゴリズムを実行し、サフィックスバイヤーのサブ最適価格からの後悔を慎重に拘束することである。
関連論文リスト
- No-Regret Algorithms in non-Truthful Auctions with Budget and ROI Constraints [0.9694940903078658]
本稿では、ROIと予算制約の対象となる価値を最適化するために、オンラインオートバイディングアルゴリズムを設計する問題について検討する。
我々の主な結果は、最高のリプシッツ関数に関して、ほぼ最適の$tilde O(sqrt T)$の後悔を保証する完全な情報フィードバックを持つアルゴリズムである。
論文 参考訳（メタデータ） (2024-04-15T14:31:53Z) - An Online Learning Theory of Brokerage [3.8059763597999012]
オンライン学習の観点からトレーダー間のブローカーについて検討する。
既に研究されている他の二国間貿易問題とは異なり、指定された買い手や売り手の役割が存在しない場合に焦点を当てる。
第1の場合、最適率は$sqrtT$に低下し、第2の場合、問題は解けなくなる。
論文 参考訳（メタデータ） (2023-10-18T17:01:32Z) - Online Learning in Contextual Second-Price Pay-Per-Click Auctions [47.06746975822902]
オンライン学習は、クリック単価のオークションで学習し、そこでは、各ラウンドのT$で、学習者がいくつかのコンテキストと広告を受信する。
学習者のゴールは、彼女の後悔を最小限に抑えることであり、それは彼女の総収入と託宣戦略のギャップとして定義される。
論文 参考訳（メタデータ） (2023-10-08T07:04:22Z) - Repeated Bilateral Trade Against a Smoothed Adversary [5.939280057673226]
我々は、アダプティブ$sigma$-smooth敵が売り手と買い手のバリュエーションを生成する二国間取引について検討する。
本研究では、異なるフィードバックモデルの下での固定価格機構に対する後悔状態の完全な特徴付けを行う。
論文 参考訳（メタデータ） (2023-02-21T16:30:10Z) - Leveraging Reviews: Learning to Price with Buyer and Seller Uncertainty [30.60994780724878]
我々は、販売者が有限種類の購入者と相互作用するオンライン環境で価格問題を研究する。
我々は、売り手が高い収入を得るために使用できる非レグレットアルゴリズムを提供する。
論文 参考訳（メタデータ） (2023-02-20T00:15:45Z) - A Reinforcement Learning Approach in Multi-Phase Second-Price Auction
Design [158.0041488194202]
多相第2価格オークションにおけるリザーブ価格の最適化について検討する。
売り手の視点からは、潜在的に非現実的な入札者の存在下で、環境を効率的に探索する必要がある。
第三に、売り手のステップごとの収益は未知であり、非線形であり、環境から直接観察することさえできない。
論文 参考訳（メタデータ） (2022-10-19T03:49:05Z) - Double Auctions with Two-sided Bandit Feedback [11.334374665364214]
ダブルオークションは、複数の買い手と売り手の間の商品の分散移動を可能にする。
信頼関係に基づく入札を行い、参加者の間には「平均価格」が効率的な価格発見をもたらすことを示す。
本論文は,両面の市場において,両面から学習が必要な不確実な嗜好を持つ分散学習アルゴリズムを初めて提供するものである。
論文 参考訳（メタデータ） (2022-08-13T01:03:34Z) - No-Regret Learning in Partially-Informed Auctions [85.67897346422122]
本研究では,一部の情報を用いたオークションの機械学習定式化について検討する。
各ラウンドでは、未知の分布から新しいアイテムが引き出され、プラットフォームは、そのアイテムに関する不完全な「偽」情報とともに価格を発行する。
アイテムの分布が買い手に知られ、マスクがSimHash関数のマッピングである場合、$mathbbRd$ to $0,1ell$、我々のアルゴリズムは、$tilde MathcalO((Tdell)frac12)$を後悔している。
論文 参考訳（メタデータ） (2022-02-22T01:15:51Z) - Top $K$ Ranking for Multi-Armed Bandit with Noisy Evaluations [102.32996053572144]
我々は,各ラウンドの開始時に,学習者が各アームの真の報酬について,ノイズのない独立した評価を受けるマルチアームバンディット・セッティングを考える。
評価の方法によって異なるアルゴリズムアプローチと理論的保証を導出する。
論文 参考訳（メタデータ） (2021-12-13T09:48:54Z) - Robust Learning of Optimal Auctions [84.13356290199603]
本研究では、入札者の評価値のサンプルを逆向きに破損させたり、逆向きに歪んだ分布から引き出すことができる場合に、サンプルから収益-最適マルチバイダオークションを学習する問題について検討する。
我々は,コルモゴロフ-スミルノフ距離における元の分布に対して$alpha$-closeの「全ての真の分布」に対して,収入がほぼ同時に最適であるメカニズムを学習できる新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-07-13T17:37:21Z) - Stochastic Bandits with Linear Constraints [69.757694218456]
制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。
楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-17T22:32:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。