基于布尔反馈的赌博机在线学习理论与方法

With the rapid development of information technology and the continued popularity of Internet, various types of data are increasing dramatically, and the era of Big Data has arrived. The velocity property of big data makes online learning an indispensable tool for big data analytics. Online decision making under incomplete observations is referred to as bandit online learning, which has been widely used to solve problems with weak feedbacks, including network routing, recommender system and online advertising. However, existing studies of bandit online learning mainly focus on real-valued feedbacks, and lack theoretical guarantees when applied to Boolean feedbacks, such as purchase or not, click or not, like or dislike, which are frequently encountered in real-world systems. To address this limitation, we will first investigate the generation process of binary feedbacks, develop stochastic observation theory, and propose online algorithms for parameter estimation. Based on Boolean feedbacks, we will develop bandit online learning theory for single-function estimation, and propose approximation algorithms to support continuous decision spaces. Furthermore, we will develop bandit online learning theory for multi-function estimation, and propose randomized decision algorithms to handle large-scale settings. In this project, it is expected to publish 4-6 high-quality papers, apply for 1-2 patents, and supervise 2-4 graduate students.

随着信息技术的飞速发展和互联网的不断普及，各种类型的数据资源与日俱增，大数据时代已经到来。大数据高速增长的特点使在线学习成为大数据分析必不可少的技术。其中，观测不完备情况下的在线决策被称为赌博机在线学习，广泛用于解决网络路由、推荐系统、广告投放等存在弱反馈的问题。然而，现有的赌博机在线学习主要关注数值反馈，在处理实际应用中更常见的是否购买、是否点击、是否喜欢等布尔反馈时缺乏理论保证。为解决该不足，本项目将研究布尔反馈的产生机制，形成针对布尔反馈的随机观测理论，提出在线参数更新算法；在此基础上，利用布尔反馈，建立针对单函数估计的赌博机在线学习理论，提出近似优化算法，支持连续决策空间；并进一步发展针对多函数估计的赌博机在线学习理论，提出随机决策算法，支持大规模函数估计。本项目研究可望产生高水平论文4-6篇，申请专利1-2项，培养2-4名研究生。

赌博机在线学习是处理大数据的重要技术手段，被广泛用于网络路由、推荐系统、广告投放等存在弱反馈的应用场景。然而，现有的赌博机在线学习主要关注数值反馈，在处理实际应用中常见的布尔反馈、噪声反馈时缺乏理论保证。针对布尔反馈，本项目提出利用逻辑模型对随机观测进行建模，采用在线牛顿法更新参数，从理论上分析了参数估计的置信区域，进而依据乐观面对不确定性的原则选择最优的决策，自动在探索和利用之间折中，取得了最优的遗憾上界。在此基础上，本项目进一步考虑了广义线性模型和重尾分布，允许更多类型的反馈并能处理未知噪声，利用多目标赌博机建模多函数在线估计问题，提出能最小化帕累托遗憾的在线算法。此外，本项目还研究了随机和近似优化技术，提出了一系列高效的离线学习算法，并将快速优化应用到在线学习问题中，保证算法实时性并且不影响效果。最后，针对动态环境中存在的模型漂移，提出了能处理特征变化的在线学习算法，能最小化自适应遗憾和动态遗憾的在线学习算法。围绕上述成果，在重要国际会议和期刊上发表论文18篇，其中CCF-A类论文15篇，申请国家发明专利1项，培养研究生5名。