Optimal Gradient-based Algorithms for Non-concave Bandit Optimization

Understand

Bandit problems with linear or concave reward have been extensively studied, but relatively few works have studied bandits with non-concave reward.

• This work considers a large family of bandit problems where the unknown underlying reward function is non-concave, including the low-rank generalized linear bandit problems and two-layer neural network with polynomial activation bandit problem.
• For the low-rank generalized linear bandit problem, we provide a minimax-optimal algorithm in the dimension, refuting both conjectures in [LMT21, JWWN19].
• Our algorithms are based on a unified zeroth-order optimization paradigm that applies in great generality and attains optimal rates in several structured polynomial settings (in the dimension).