Timezone: »
Poster
Joint Online Learning and Decision-making via Dual Mirror Descent
Alfonso Lobos Ruiz · Paul Grigas · Zheng Wen
We consider an online revenue maximization problem over a finite time horizon subject to lower and upper bounds on cost. At each period, an agent receives a context vector sampled i.i.d. from an unknown distribution and needs to make a decision adaptively. The revenue and cost functions depend on the context vector as well as some fixed but possibly unknown parameter vector to be learned. We propose a novel offline benchmark and a new algorithm that mixes an online dual mirror descent scheme with a generic parameter learning process. When the parameter vector is known, we demonstrate an $O(\sqrt{T})$ regret result as well an $O(\sqrt{T})$ bound on the possible constraint violations. When the parameter is not known and must be learned, we demonstrate that the regret and constraint violations are the sums of the previous $O(\sqrt{T})$ terms plus terms that directly depend on the convergence of the learning process.
Author Information
Alfonso Lobos Ruiz (Microsoft)
Paul Grigas (UC Berkeley)
Zheng Wen (DeepMind)
Related Events (a corresponding poster, oral, or spotlight)
-
2021 Spotlight: Joint Online Learning and Decision-making via Dual Mirror Descent »
Wed. Jul 21st 01:25 -- 01:30 PM Room
More from the Same Authors
-
2020 Poster: Budgeted Online Influence Maximization »
Pierre Perrault · Jennifer Healey · Zheng Wen · Michal Valko -
2020 Poster: Influence Diagram Bandits: Variational Thompson Sampling for Structured Bandit Problems »
Tong Yu · Branislav Kveton · Zheng Wen · Ruiyi Zhang · Ole J. Mengshoel -
2020 Poster: Structured Policy Iteration for Linear Quadratic Regulator »
Youngsuk Park · Ryan A. Rossi · Zheng Wen · Gang Wu · Handong Zhao