Optimal Gradient-based Algorithms for Non-concave Bandit Optimization
Optimal Gradient-based Algorithms for Non-concave Bandit Optimization
复制标题
DOI：
--
复制
发表时间：
2021-07
期刊：
影响因子：
--
通讯作者：
Baihe Huang;Kaixuan Huang;S. Kakade;Jason D. Lee;Qi Lei;Runzhe Wang;Jiaqi Yang
中科院分区：
文献类型：
--
作者：
Baihe Huang;Kaixuan Huang;S. Kakade;Jason D. Lee;Qi Lei;Runzhe Wang;Jiaqi Yang
具有线性或凹报酬的强盗问题已经得到了广泛的研究，但相对较少的工作，研究非凹报酬的强盗。本文考虑一类报酬函数为非凹函数的bandit问题，包括低秩广义线性bandit问题和具有多项式激活的双层神经网络bandit问题.对于低秩广义线性强盗问题，我们提供了维度上的极小极大最优算法，反驳了[LMT 21，JWWN 19]中的两个猜想。我们的算法是基于一个统一的零阶优化范式，适用于在很大的普遍性，并在几个结构化的多项式设置（在维度）达到最佳速率。我们进一步证明了我们的算法在生成模型设置中的RL中的适用性，从而提高了先前方法的样本复杂性。最后，我们证明了标准的乐观算法（例如，UCB）是次优的尺寸因素。在神经网络设置（多项式激活函数）与无噪声奖励，我们提供了一个强盗算法的样本复杂度等于内在代数维数。再次，我们表明，乐观的方法有更差的样本复杂性，多项式的外维数（这可能是指数更差的多项式次数）。
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).