  We propose a new online learning model for learning with preference feedback.
The model is especially suited for applications like web search and recommender
systems, where preference data is readily available from implicit user feedback
(e.g. clicks). In particular, at each time step a potentially structured object
(e.g. a ranking) is presented to the user in response to a context (e.g.
query), providing him or her with some unobserved amount of utility. As
feedback the algorithm receives an improved object that would have provided
higher utility. We propose a learning algorithm with provable regret bounds for
this online learning setting and demonstrate its effectiveness on a web-search
application. The new learning model also applies to many other interactive
learning problems and admits several interesting extensions.
