Online learning with side information
Online learning with side information
复制标题
在线学习附带辅助信息
DOI：
10.1109/milcom.2017.8170860
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
A. Swami
中科院分区：
文献类型：
--
作者：
Xiao Xu;Sattar Vakili;Qing Zhao;A. Swami
考虑了一个带有侧信息的在线学习问题。将该问题表述为图结构随机多臂强盗（MAB）问题。图中的每个节点表示强盗问题中的一个分支，两个分支之间的一条边表示它们的平均报酬接近。结果表明，这些边信息可以诱导出一个单位间隔图，并且可以利用几个图的性质来实现臂数的次线性遗憾，同时在时间上保持最优对数遗憾。建立了后悔度的下界，提出了在臂数和学习视界两方面都是序最优的分层学习策略。
An online learning problem with side information is considered. The problem is formulated as a graph structured stochastic Multi-Armed Bandit (MAB). Each node in the graph represents an arm in the bandit problem and an edge between two arms indicates closeness in their mean rewards. It is shown that such side information induces a Unit Interval Graph and several graph properties can be leveraged to achieve a sublinear regret in the number of arms while preserving the optimal logarithmic regret in time. A lower bound on regret is established and a hierarchical learning policy that is order optimal in terms of both the number of arms and the learning horizon is developed.