  We study online learning in contextual pay-per-click auctions where at each
of the $T$ rounds, the learner receives some context along with a set of ads
and needs to make an estimate on their click-through rate (CTR) in order to run
a second-price pay-per-click auction. The learner's goal is to minimize her
regret, defined as the gap between her total revenue and that of an oracle
strategy that always makes perfect CTR predictions. We first show that
$\sqrt{T}$-regret is obtainable via a computationally inefficient algorithm and
that it is unavoidable since our algorithm is no easier than the classical
multi-armed bandit problem. A by-product of our results is a $\sqrt{T}$-regret
bound for the simpler non-contextual setting, improving upon a recent work of
[Feng et al., 2023] by removing the inverse CTR dependency that could be
arbitrarily large. Then, borrowing ideas from recent advances on efficient
contextual bandit algorithms, we develop two practically efficient contextual
auction algorithms: the first one uses the exponential weight scheme with
optimistic square errors and maintains the same $\sqrt{T}$-regret bound, while
the second one reduces the problem to online regression via a simple
epsilon-greedy strategy, albeit with a worse regret bound. Finally, we conduct
experiments on a synthetic dataset to showcase the effectiveness and superior
performance of our algorithms.
