No-Regret Learning in Partially-Informed Auctions
  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}})$.
