  We address online learning in complex auction settings, such as sponsored
search auctions, where the value of the bidder is unknown to her, evolving in
an arbitrary manner and observed only if the bidder wins an allocation. We
leverage the structure of the utility of the bidder and the partial feedback
that bidders typically receive in auctions, in order to provide algorithms with
regret rates against the best fixed bid in hindsight, that are exponentially
faster in convergence in terms of dependence on the action space, than what
would have been derived by applying a generic bandit algorithm and almost
equivalent to what would have been achieved in the full information setting.
Our results are enabled by analyzing a new online learning setting with
outcome-based feedback, which generalizes learning with feedback graphs. We
provide an online learning algorithm for this setting, of independent interest,
with regret that grows only logarithmically with the number of actions and
linearly only in the number of potential outcomes (the latter being very small
in most auction settings). Last but not least, we show that our algorithm
outperforms the bandit approach experimentally and that this performance is
robust to dropping some of our theoretical assumptions or introducing noise in
the feedback that the bidder receives.
