Online Learning via Offline Greedy: Applications in Market Design and Optimization
Online Learning via Offline Greedy: Applications in Market Design and Optimization
复制标题
通过离线贪婪进行在线学习：在市场设计和优化中的应用
DOI：
10.2139/ssrn.3613756
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Ashwinkumar Badanidiyuru
中科院分区：
文献类型：
--
作者：
Rad Niazadeh;Negin Golrezaei;Joshua R. Wang;Fransisca Susan;Ashwinkumar Badanidiyuru
受时变组合环境中在线决策的启发，我们研究了将离线算法转化为在线算法的问题。我们使用一种对局部误差具有健壮性的贪婪算法来研究适合于恒定因子近似的离线组合问题。对于这类问题，我们提供了一个通用的框架，利用Blackwell可达性将离线的健壮贪婪算法有效地转换为在线的贪婪算法。我们证明了在完全信息条件下，所得到的在线算法具有O(T^{1/2})(近似)遗憾。我们进一步引入了Blackwell可达性的Bandit扩张，我们称之为Bandit Blackwell可达性。我们利用这一概念将贪婪健壮的离线算法转化为强盗设置下的O(T^{2/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(T^{1/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(T^{2/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.