Hierarchical Learning Algorithms for Multi-scale Expert Problems
Hierarchical Learning Algorithms for Multi-scale Expert Problems
复制标题
多尺度专家问题的分层学习算法
DOI：
10.1145/3489048.3530967
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Towsley, Don
中科院分区：
文献类型：
--
作者：
Yang, Lin;Chen, Yu-zhen Janice;Hajiesmaili, Mohammad H.;Herbster, Mark;Towsley, Don
本文研究了多尺度专家问题，其中不同专家的报酬在不同的报酬范围内是不同的。对于多尺度专家问题，现有算法的性能与任何专家或最优秀专家的最大奖励范围成正比，并且没有捕捉到专家之间奖励范围的非均匀异质性。在这项工作中，我们提出了一种学习算法，该算法基于专家奖励范围的异构性构建层次树结构，然后根据奖励上界和随时间累积的经验反馈来确定差异化学习率。然后，我们将该算法的遗憾刻画为非均匀报酬范围的函数，并证明了当专家报酬在不同范围内表现出非均匀异质性时，它们的后悔性能优于已有的算法。最后，通过数值实验验证了该算法相对于以往算法的有效性。
In this paper, we study the multi-scale expert problem, where the rewards of different experts vary in different reward ranges. The performance of existing algorithms for the multi-scale expert problem degrades linearly proportional to the maximum reward range of any expert or the best expert and does not capture the non-uniform heterogeneity in the reward ranges among experts. In this work, we propose learning algorithms that construct a hierarchical tree structure based on the heterogeneity of the reward range of experts and then determine differentiated learning rates based on the reward upper bounds and cumulative empirical feedback over time. We then characterize the regret of the proposed algorithms as a function of non-uniform reward ranges and show that their regrets outperform prior algorithms when the rewards of experts exhibit non-uniform heterogeneity in different ranges. Last, our numerical experiments verify our algorithms' efficiency compared to previous algorithms.
在线拍卖和多尺度在线学习
DOI：
10.1145/3033274.3085145
发表时间：
2017
期刊：
Proceedings of the 2017 ACM Conference on Economics and Computation
影响因子：
--
作者：
Sébastien Bubeck;Nikhil R. Devanur;Zhiyi Huang;Rad Niazadeh
通讯作者：
Rad Niazadeh