Online Auctions and Multi-scale Online Learning
Online Auctions and Multi-scale Online Learning
复制标题
在线拍卖和多尺度在线学习
DOI：
10.1145/3033274.3085145
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Rad Niazadeh
中科院分区：
文献类型：
--
作者：
Sébastien Bubeck;Nikhil R. Devanur;Zhiyi Huang;Rad Niazadeh
我们考虑在线拍卖和定价中的收入最大化。一个卖家在每一个时期向一个新的买家或一组新的买家出售一件相同的物品。对于在线发布的定价问题，我们显示遗憾的界限，规模与最佳的固定价格，而不是价值观的范围。我们还显示了遗憾的界限，几乎是无标度的，并匹配离线样本的复杂性，当比较的基准，需要一个下限的市场份额。这些结果是通过将专家和多臂强盗问题的经典学习推广到多尺度版本而得到的。在这个版本中，每个动作的奖励都在不同的范围内，而后悔w.r.t.给定的动作以其自身的范围而不是最大范围缩放。
We consider revenue maximization in online auctions and pricing. A seller sells an identical item in each period to a new buyer, or a new set of buyers. For the online posted pricing problem, we show regret bounds that scale with the best fixed price, rather than the range of the values. We also show regret bounds that are almost scale free, and match the offline sample complexity, when comparing to a benchmark that requires a lower bound on the market share. These results are obtained by generalizing the classical learning from experts and multi-armed bandit problems to their multi-scale versions. In this version, the reward of each action is in a different range, and the regret w.r.t. a given action scales with its own range, rather than the maximum range.