CRII:RI: Adaptive and Practical Algorithms for Personalization

智能个性化系统，如新闻、广告、搜索、在线购物和临床试验等，在日常生活中发挥着越来越重要的作用，在给我们带来巨大便利的同时，也提高了社会生产力。为这些系统开发算法解决方案的主要挑战在于，用户只提供对推荐选项的反馈，而不提供其他选项的反馈。在实践中使用了许多简单的启发式方法，最近也有一些更严格的方法取得了一些进展，基于“背景强盗”模型，指的是与通过杠杆拉动序列获得的回报总和最大化的目标进行类比，其中对过去业绩的编码提供了背景。但在实用性和性能保障方面仍有很大提升空间。本项目致力于为这类系统开发更实用和适应性更强的上下文盗贼算法。这个项目的成功需要开发新的算法技术和数学工具，从统计、优化、机器学习及其组合中以创新的方式，这推动了在线决策领域的理论和实践。通过课程开发和学生辅导，将教育纳入该项目。外联活动包括与其他大学以及工业界的合作，以及在顶级会议上组织相关讲习班。具体地说，该项目的目标是设计一类实用的上下文盗贼算法，这些算法不仅具有信息论上的最坏情况保证，而且当问题表现出某种容易程度时，还可以获得更好的性能。首先，该项目系统地研究了不同类型的“易用性”测量，并为每种测量开发和分析了具体的算法。其次，该项目进一步考虑是否有可能有一个对所有问题实例都是最优的单一算法，其中最优性是指合理的算法类别中的最佳性能。最后，该项目实现了所有开发的算法，并在基准数据集上进行了经验评估，目标是发布易于使用和公开可用的软件。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

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.