A Lyapunov-Based Methodology for Constrained Optimization with Bandit Feedback
A Lyapunov-Based Methodology for Constrained Optimization with Bandit Feedback
复制标题
DOI：
10.1609/aaai.v36i4.20285
复制
发表时间：
2021-06
期刊：
影响因子：
--
通讯作者：
Semih Cayci;Yilin Zheng;A. Eryilmaz
中科院分区：
文献类型：
--
作者：
Semih Cayci;Yilin Zheng;A. Eryilmaz
在包括在线广告、合同租用和无线调度在内的各种应用中，控制器受到对可用资源的严格预算约束(每一操作以随机数量消耗)，以及可能对决策施加重要操作限制的随机可行性约束。在这项工作中，我们考虑了一个一般模型来解决这类问题，其中每个行动从未知的联合分布中返回随机的报酬、成本和惩罚，决策者的目标是在预算约束B和时间平均惩罚的随机约束下最大化总回报。提出了一种新的基于Lyapunov优化方法的低复杂度算法Lyon，并证明了当B足够大时，对于K个ARM，它实现了KBlog(B)的后悔和零约束违反的平方根。Lyon算法较低的计算代价和较好的性能边界表明，基于Lyapunov的算法设计方法可以有效地解决带约束的土匪优化问题。
In a wide variety of applications including online advertising, contractual hiring, and wireless scheduling, the controller is constrained by a stringent budget constraint on the available resources, which are consumed in a random amount by each action, and a stochastic feasibility constraint that may impose important operational limitations on decision-making. In this work, we consider a general model to address such problems, where each action returns a random reward, cost, and penalty from an unknown joint distribution, and the decision-maker aims to maximize the total reward under a budget constraint B on the total cost and a stochastic constraint on the time-average penalty. We propose a novel low-complexity algorithm based on Lyapunov optimization methodology, named LyOn, and prove that for K arms it achieves square root of KBlog(B) regret and zero constraint-violation when B is sufficiently large. The low computational cost and sharp performance bounds of LyOn suggest that Lyapunov-based algorithm design methodology can be effective in solving constrained bandit optimization problems.