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). We further
demonstrate the applicability of our algorithms in RL in the generative model
setting, resulting in improved sample complexity over prior approaches.
Finally, we show that the standard optimistic algorithms (e.g., UCB) are
sub-optimal by dimension factors. In the neural net setting (with polynomial
activation functions) with noiseless reward, we provide a bandit algorithm with
sample complexity equal to the intrinsic algebraic dimension. Again, we show
that optimistic approaches have worse sample complexity, polynomial in the
extrinsic dimension (which could be exponentially worse in the polynomial
degree).

本文研究非凸奖励的赌博机问题，提出了一种适用于一类具有非凸奖励函数的赌博机算法，通过统一的零阶优化范式达到了多项式设置下的最优速率，并在生成模型的 RL 中实现了算法的应用，从而取得了比之前方法更好的样本复杂度。