Online Learning via Offline Greedy Algorithms: Applications in Market Design and Optimization
Online Learning via Offline Greedy Algorithms: Applications in Market Design and Optimization
复制标题
通过离线贪婪算法进行在线学习：在市场设计和优化中的应用
DOI：
10.1145/3465456.3467571
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Ashwinkumar Badanidiyuru
中科院分区：
文献类型：
--
作者：
Rad Niazadeh;Negin Golrezaei;Joshua R. Wang;Fransisca Susan;Ashwinkumar Badanidiyuru
受时变组合环境中在线决策的推动，我们研究了将离线算法转换为在线算法的问题。我们专注于离线组合问题，这些问题可以使用对局部误差具有鲁棒性的贪婪算法进行常数因子近似。对于此类问题，我们提供了一个通用框架，可以使用 Blackwell 的可接近性将离线鲁棒贪婪算法有效地转换为在线算法。我们表明，所得到的在线算法在完整信息设置下具有 O(T1/2)（近似）遗憾。我们进一步引入 Blackwell 可达性的 bandit 扩展，我们称之为 Bandit Blackwell 可达性。我们利用这个概念将贪婪的鲁棒离线算法转化为强盗设置中的 O(T2/3)（近似）遗憾。为了展示我们框架的灵活性，我们将线下到线上的转型应用于收入管理、市场设计和在线优化交叉点的几个问题，包括在线平台中的产品排名优化、拍卖中的底价优化和子模块最大化。我们表明，当我们的转换应用于这些应用程序时，会导致新的遗憾界限或改进当前已知的界限。
Motivated by online decision-making in time-varying combinatorial environments, we study the problem of transforming offline algorithms to their online counterparts. We focus on offline combinatorial problems that are amenable to a constant factor approximation using a greedy algorithm that is robust to local errors. For such problems, we provide a general framework that efficiently transforms offline robust greedy algorithms to online ones using Blackwell approachability. We show that the resulting online algorithms have O(T1/2) (approximate) regret under the full information setting. We further introduce a bandit extension of Blackwell approachability that we call Bandit Blackwell approachability. We leverage this notion to transform greedy robust offline algorithms into a O(T2/3) (approximate) regret in the bandit setting. Demonstrating the flexibility of our framework, we apply our offline-to-online transformation to several problems at the intersection of revenue management, market design, and online optimization, including product ranking optimization in online platforms, reserve price optimization in auctions, and submodular maximization. We show that our transformation, when applied to these applications, leads to new regret bounds or improves the current known bounds.
登录
查看更多内容
DOI：
--
发表时间：
2018
期刊：
31st Annual Conference on Learning Theory (COLT
影响因子：
--
作者：
Roughgarden, Tim;Wang, Joshua R.
通讯作者：
Wang, Joshua R.
DOI：
--
发表时间：
2019-10
期刊：
--
影响因子：
--
作者：
Mingrui Zhang;Zebang Shen;Aryan Mokhtari;Hamed Hassani;Amin Karbasi
通讯作者：
Mingrui Zhang;Zebang Shen;Aryan Mokhtari;Hamed Hassani;Amin Karbasi
DOI：
--
发表时间：
2020
期刊：
International Conference on Artificial Intelligence and Statistics
影响因子：
--
作者：
Chen, Lin;Zhang, Mingrui;Hassani, Hamed;Karbasi, Amin
通讯作者：
Karbasi, Amin
动态激励感知学习：关联拍卖中的稳健定价
影响因子：
2.7
作者：
Negin Golrezaei, Adel Javanmard
通讯作者：
Negin Golrezaei, Adel Javanmard