Timezone: »
Poster
The Symmetry between Arms and Knapsacks: A Primal-Dual Approach for Bandits with Knapsacks
Xiaocheng Li · Chunlin Sun · Yinyu Ye
In this paper, we study the bandits with knapsacks (BwK) problem and develop a primal-dual based algorithm that achieves a problem-dependent logarithmic regret bound. The BwK problem extends the multi-arm bandit (MAB) problem to model the resource consumption, and the existing BwK literature has been mainly focused on deriving asymptotically optimal distribution-free regret bounds. We first study the primal and dual linear programs underlying the BwK problem. From this primal-dual perspective, we discover symmetry between arms and knapsacks, and then propose a new notion of suboptimality measure for the BwK problem. The suboptimality measure highlights the important role of knapsacks in determining algorithm regret and inspires the design of our two-phase algorithm. In the first phase, the algorithm identifies the optimal arms and the binding knapsacks, and in the second phase, it exhausts the binding knapsacks via playing the optimal arms through an adaptive procedure. Our regret upper bound involves the proposed suboptimality measure and it has a logarithmic dependence on length of horizon $T$ and a polynomial dependence on $m$ (the numbers of arms) and $d$ (the number of knapsacks). To the best of our knowledge, this is the first problem-dependent logarithmic regret bound for solving the general BwK problem.
Author Information
Xiaocheng Li (Imperial College London)
Chunlin Sun (Stanford University)
Yinyu Ye (Standord)
Related Events (a corresponding poster, oral, or spotlight)
-
2021 Oral: The Symmetry between Arms and Knapsacks: A Primal-Dual Approach for Bandits with Knapsacks »
Thu. Jul 22nd 12:00 -- 12:20 AM Room
More from the Same Authors
-
2023 Poster: Maximum Optimality Margin: A Unified Approach for Contextual Linear Programming and Inverse Linear Programming »
Chunlin Sun · Shang Liu · Xiaocheng Li -
2023 Poster: Solving Linear Program with Fast Online Learning Algorithms »
Wenzhi Gao · Dongdong Ge · Chunlin Sun · Yinyu Ye -
2017 Poster: Strong NP-Hardness for Sparse Optimization with Concave Penalty Functions »
Yichen Chen · Dongdong Ge · Mengdi Wang · Zizhuo Wang · Yinyu Ye · Hao Yin -
2017 Talk: Strong NP-Hardness for Sparse Optimization with Concave Penalty Functions »
Yichen Chen · Dongdong Ge · Mengdi Wang · Zizhuo Wang · Yinyu Ye · Hao Yin