Many systems, ranging from search engines to smart homes, aim to continually improve the utility they are providing to their users. While clearly a machine learning problem, it is less clear what the interface between user and learning algorithm should look like. Focusing on learning problems that arise in recommendation and search, this talk explores how the interactions between the user and the system can be modeled as an online learning process. In particular, the talk investigates several techniques for eliciting implicit feedback, evaluates their reliability through user studies, and then proposes online learning models and methods that can make use of such feedback. A key finding is that implicit user feedback comes in the form of preferences, and that our online learning methods provide bounded regret for (approximately) rational users.