LGFeb 1, 2023
Bandit Convex Optimisation Revisited: FTRL Achieves $\tilde{O}(t^{1/2})$ Regret
arXiv:2302.00358v2h-index: 47
Originality Incremental advance
AI Analysis
This improves regret bounds for bandit convex optimization, a problem in online learning with partial feedback.
The paper tackles bandit convex optimization by converting a kernel estimator into a bandit estimator and applying it with FTRL, achieving $ ilde{O}(t^{1/2})$ regret against adversarial convex loss functions.
We show that a kernel estimator using multiple function evaluations can be easily converted into a sampling-based bandit estimator with expectation equal to the original kernel estimate. Plugging such a bandit estimator into the standard FTRL algorithm yields a bandit convex optimisation algorithm that achieves $\tilde{O}(t^{1/2})$ regret against adversarial time-varying convex loss functions.