English

运筹学学报

• 运筹学 • 上一篇    下一篇

在线学习方法综述: 汤普森抽样和其他方法

何斯迈1,*  金羽佳2  王华2  葛冬冬3   

  1. 1. 上海财经大学信息管理与工程学院, 上海  200433 2. 复旦大学数学科学学院, 上海 200433 3. 上海财经大学交叉科学研究院, 上海 200433
  • 收稿日期:2017-08-30 出版日期:2017-12-15 发布日期:2017-12-15
  • 通讯作者: 何斯迈 simaihe@mail.shufe.edu.cn
  • 基金资助:

    国家自然科学基金(No. 11471205), 上海高校特聘教授(东方学者)岗位计划(No. 2015140002), 上海财经大学创新团队支持计划(Nos. 2014110354, 2016110392)

A survey on online learning methods: Thompson sampling and others

HE Simai1,*  JIN Yujia2  WANG Hua2  GE Dongdong3   

  1. 1. School of Information Management and Engineering, Shanghai University of Finance and Economics, Shanghai 200433, China 2. School of Mathematical Sciences, Fudan University, Shanghai 200433, China 3. Research Institute for Interdisciplinary Sciences, Shanghai University of Finance and Economics, Shanghai 200433, China
  • Received:2017-08-30 Online:2017-12-15 Published:2017-12-15

PDF

717

摘要：

本文尝试对在线学习领域的最新研究成果、相关主要理论和算法进行综述. 在线学习的内容非常广博, 本文希望能够为读者介绍其中一些基本的算法和想法, 从最经典的理论模型和算法设计开始, 对在线学习的发展情况作一个一般性的介绍. 首先, 以经典的在线优化模型------多摇臂赌博机问题为例, 引入了汤普森抽样算法和信心上界算法, 分析、展示了它们的基本思路和最新成果, 并进一步讨论了汤普森抽样算法在更复杂的在线学习问题中的变式和应用. 本文同时对在线凸优化算法做了初步探讨, 它也是解决多摇臂赌博机问题和其他许多在线学习的应用问题时一种强有力的工具.

关键词: 在线学习, 多摇臂赌博机, 汤普森抽样, 信心上界算法, 情境多摇臂赌博机, 在线凸优化

Abstract:

The paper is a survey on the latest research results, major theories and algorithms in the field of online learning. The topic of online learning is a broad one, and we aim at introducing the principles of the basic algorithms and ideas to the readers. We start from the most standard models and algorithm design, and extend all the way to a more general presentation on the latest developments in the area.

To begin with, we take the standard online optimization model, the Multi-Armed Bandit Problem, as an example. Then we discuss Thompson Sampling algorithms and Upper Confidence Bound algorithms, analyzing and presenting the main idea and newest theoretical achievements, with further discussion about the extensions and applications of Thompson Sampling in some more complicated real-world online learning scenarios. Furthermore, the paper gives a brief introduction about online convex optimization, which serves as an effective and well-known framework in solving Multi-Armed Bandit problem and other application problems.

Key words: online learning, multi-armed bandit, Thompson sampling, upper confidence bound, contextual multi-armed bandit, online convex optimization