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.

研究在线学习在上下文广告竞拍中的应用，通过算法获得最小化收入损失的目标，针对点击率进行估计，提出了两种有效的上下文拍卖算法，并通过实验验证了其有效性和超凡性能。