論文の概要: No-Regret Learning in Partially-Informed Auctions
- arxiv url: http://arxiv.org/abs/2202.10606v1
- Date: Tue, 22 Feb 2022 01:15:51 GMT
- ステータス: 処理完了
- システム内更新日: 2022-02-23 17:00:41.921916
- Title: No-Regret Learning in Partially-Informed Auctions
- Title（参考訳）: 部分インフォームドオークションにおける非回帰学習
- Authors: Wenshuo Guo, Michael I. Jordan, Ellen Vitercik
- Abstract要約: 本研究では,一部の情報を用いたオークションの機械学習定式化について検討する。
各ラウンドでは、未知の分布から新しいアイテムが引き出され、プラットフォームは、そのアイテムに関する不完全な「偽」情報とともに価格を発行する。
アイテムの分布が買い手に知られ、マスクがSimHash関数のマッピングである場合、$mathbbRd$ to $0,1ell$、我々のアルゴリズムは、$tilde MathcalO((Tdell)frac12)$を後悔している。
- 参考スコア（独自算出の注目度）: 85.67897346422122
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Auctions with partially-revealed information about items are broadly employed
in real-world applications, but the underlying mechanisms have limited
theoretical support. In this work, we study a machine learning formulation of
these types of mechanisms, presenting algorithms that are no-regret from the
buyer's perspective. Specifically, a buyer who wishes to maximize his utility
interacts repeatedly with a platform over a series of $T$ rounds. In each
round, a new item is drawn from an unknown distribution and the platform
publishes a price together with incomplete, "masked" information about the
item. The buyer then decides whether to purchase the item. We formalize this
problem as an online learning task where the goal is to have low regret with
respect to a myopic oracle that has perfect knowledge of the distribution over
items and the seller's masking function. When the distribution over items is
known to the buyer and the mask is a SimHash function mapping $\mathbb{R}^d$ to
$\{0,1\}^{\ell}$, our algorithm has regret $\tilde
{\mathcal{O}}((Td\ell)^{\frac{1}{2}})$. In a fully agnostic setting when the
mask is an arbitrary function mapping to a set of size $n$, our algorithm has
regret $\tilde {\mathcal{O}}(T^{\frac{3}{4}}n^{\frac{1}{2}})$. Finally, when
the prices are stochastic, the algorithm has regret $\tilde
{\mathcal{O}}((Tn)^{\frac{1}{2}})$.
- Abstract（参考訳）: 商品に関する情報を部分的に明らかにしたオークションは、現実世界のアプリケーションに広く採用されているが、基礎となるメカニズムは理論的な支援に限られている。
本研究では,これらのメカニズムの機械学習による定式化について検討し,買い手の視点からは問題のないアルゴリズムを提示する。
特に,自分のユーティリティを最大化したいバイヤーは,一連の$t$ラウンドを通じてプラットフォームと繰り返し対話します。
各ラウンドでは、未知の分布から新しいアイテムが引き出され、プラットフォームは、そのアイテムに関する不完全な「偽」情報とともに価格を発行する。
購入者は商品を購入するかどうかを決定する。
私たちはこの問題をオンライン学習タスクとして定式化し、アイテムの配布と販売者のマスキング機能に関する完全な知識を持つ明快なオラクルに対して、後悔を少なくすることを目標としている。
アイテムの分布が買い手に知られ、マスクが SimHash 関数 $\mathbb{R}^d$ to $\{0,1\}^{\ell}$ であるとき、我々のアルゴリズムは $\tilde {\mathcal{O}}((Td\ell)^{\frac{1}{2}})$ を後悔している。
マスクが$n$の集合への任意の関数写像であるとき、我々のアルゴリズムは、$\tilde {\mathcal{O}}(T^{\frac{3}{4}}n^{\frac{1}{2}})$を後悔している。
最後に、価格が確率的であれば、アルゴリズムは$\tilde {\mathcal{O}}((Tn)^{\frac{1}{2}})$を後悔する。
関連論文リスト
- On learning Whittle index policy for restless bandits with scalable
regret [1.0152838128195465]
強化学習は、優れたリソース割り当てとスケジューリングポリシーを学ぶための魅力的なアプローチである。
ほとんどのRLアルゴリズムの累積後悔は$tilde O(mathsfS sqrtmathsfA T)$、$mathsfS$は状態空間のサイズである。
本稿では,このような問題に対するモデルベースRLアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-02-07T19:07:02Z) - Near-Optimal Learning of Extensive-Form Games with Imperfect Information [54.55092907312749]
本稿では,2プレイヤーゼロサムゲームにおいて,$widetildemathcalO((XA+YB)/varepsilon2)$プレイのエピソードのみを必要とするアルゴリズムの最初の行を,$varepsilon$-approximate Nash平衡を求める。
これにより$widetildemathcalO((X2A+Y2B)/varepsilon2)$が$widetildemathcalO(maxX,
論文 参考訳（メタデータ） (2022-02-03T18:18:28Z) - On Submodular Contextual Bandits [92.45432756301231]
作用が基底集合の部分集合であり、平均報酬が未知の単調部分モジュラ函数によってモデル化されるような文脈的包帯の問題を考える。
Inverse Gap Weighting 戦略により,提案アルゴリズムは推定関数の局所的最適度を効率よくランダム化することを示す。
論文 参考訳（メタデータ） (2021-12-03T21:42:33Z) - Learning to Bid in Contextual First Price Auctions [6.482311591019749]
我々は、最初の価格オークションに何度も入札する1人の入札者(受講者)について検討する。
2進フィードバックに対して,最大最大推定(MLE)法を用いて,最大$widetildeO(sqrtlog(d) T)$ regretを実現する入札アルゴリズムを提案する。
また、幅広いクラスの入札ポリシーは、少なくとも$Omega(sqrtT)$を後悔しなければなりません。
論文 参考訳（メタデータ） (2021-09-07T16:11:18Z) - Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。
この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
論文 参考訳（メタデータ） (2021-08-19T16:16:48Z) - Contextual Recommendations and Low-Regret Cutting-Plane Algorithms [49.91214213074933]
本稿では、ナビゲーションエンジンやレコメンデーションシステムにおけるルーティングアプリケーションによって動機付けられた、コンテキスト線形帯域の次の変種について考察する。
我々は、真の点$w*$と分離オラクルが返す超平面の間の全距離を、低い「回帰」を持つ新しい切断平面アルゴリズムを設計する。
論文 参考訳（メタデータ） (2021-06-09T05:39:05Z) - Hardness of Learning Halfspaces with Massart Noise [56.98280399449707]
我々は、マッサート(有界)ノイズの存在下でPAC学習のハーフスペースの複雑さを研究します。
情報理論上最適なエラーとSQアルゴリズムで達成できる最高のエラーとの間に指数関数的なギャップがあることを示した。
論文 参考訳（メタデータ） (2020-12-17T16:43:11Z) - Fully Gap-Dependent Bounds for Multinomial Logit Bandit [5.132017939561661]
マルチノミアルロジット (MNL) バンディット問題について検討し、各ステップごとに、販売者は、N$アイテムのプールから最大でK$のサイズを提供する。
i) $widetildeO(sum_i = 1N Delta_i-2)$ time steps with high probability, (ii) $O(sum_i notin S* KDelta_i)というアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-11-19T17:52:12Z) - Optimal Contextual Pricing and Extensions [32.152826900874075]
このアルゴリズムは$Omega(d log T)$ lower bound up to the $d log d$ additive factor。
これらのアルゴリズムは、凸領域のスタイナー固有値を様々なスケールで有界化する新しい手法に基づいている。
論文 参考訳（メタデータ） (2020-03-03T18:46:29Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。