CRII:RI: Adaptive and Practical Algorithms for Personalization

University Of Southern California, Los Angeles CA

Investigators

Abstract

Intelligent personalization systems, such as those in news, advertising, search, online shopping, and clinical trials, are playing an increasingly important role in daily lives, bringing to us tremendous convenience as well as increasing the productivity of society. The main challenge in developing algorithmic solutions for these systems lies in the fact that only feedback for the recommended options, but not the other ones, is provided by the users. Many simple heuristics have been used in practice, and there are also some recent advances on more rigorous approaches based on the "contextual bandit" model, referring to an analogy with the objective to maximize the sum of rewards earned through a sequence of lever pulls where an encoding of past performance provides context. However, there is still great room for improvement in terms of both practicality and performance guarantees. This project seeks to develop more practical and adaptive contextual bandit algorithms for such systems. The success of this project requires developing new algorithmic techniques as well as mathematical tools from statistics, optimization, machine learning, and their combinations in an innovative way, which advances the theory and practice of the field of online decision making. Education is integrated into the project through curriculum development and student mentoring. Outreach activities include collaborations with other universities as well as with industry, and also organizing related workshops at top conferences. Specifically, the project aims at designing a family of practical contextual bandit algorithms which not only enjoy some information-theoretic worst-case guarantees but can also achieve much better performance when the problem exhibits some kind of "easiness". First, the project systematically studies different kinds of "easiness" measurements and develops and analyzes specific algorithms for each of these measurements. Second, the project further considers the question of whether it is possible to have a single algorithm that is optimal against all problem instances, where optimality is in terms of the best performance among a reasonable class of algorithms. Finally, the project implements all the developed algorithms and conducts empirical evaluation on benchmark datasets, with the goal of releasing easy-to-use and publicly available software. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.