稳健的重尾线性赌博机算法

马兰霁弘 赵 鹏 周志华

（计算机软件新技术国家重点实验室（南京大学）南京 210023）

许多现实世界的应用可以被建模为面对不确定因素时的序列决策问题，其基本挑战是探索（exploration）和利用（exploitation）之间的权衡困境.多臂赌博机[1]是一种系统化模拟这类问题的模型，在该模型中，学习者每轮从摇臂池中选择1 个摇臂，随后从环境中收到选择的摇臂所对应的奖赏.学习者的目标是尽可能最大化所获得的累积奖赏，因此学习者必须在收集更多关于奖赏分布的数据（探索）和选择到目前为止最有可能取得最高奖赏的摇臂（利用）之间取得平衡.

随机线性赌博机是多臂赌博机在实际应用中的一个自然和重要的变体，已经引起了相当大的关注.其通常假设每个摇臂都具有其对应的d维特征，这些特征通常被称为“上下文信息”（contextual information），学习者需要根据上下文和所获得的历史奖赏信息来选择下一个摇臂.在第t轮中用xt表示所选摇臂的特征信息，该摇臂所能获得的奖赏可参数化为其上下文信息的线性函数，额外加上满足一定性质的噪声 ηt.其形式化为

其中θ ∈Rd是未知的回归系数，ηt是服从亚高斯分布的噪声.尽管该模型非常简单，但是它已被广泛应用于许多现实场景，如临床试验[2]和个性化推荐[3].

在现实世界的应用中，在线数据通常是从开放动态的环境中收集的，导致数据的不规范性经常出现，而这些不规范性又进一步限制了标准模型式（1）及其相应算法的使用.在……