Optimal Gradient-based Algorithms for Non-concave Bandit Optimization

Abstract

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).

References in corpus (21)

• Neural Tangent Kernel: Convergence and Generalization in Neural Networks
• Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Data
• The Noisy Power Method: A Meta Algorithm with Applications
• What Can ResNet Learn Efficiently, Going Beyond Kernels?
• Randomized Block Krylov Methods for Stronger and Faster Approximate Singular Value Decomposition
• Convergence of Adversarial Training in Overparametrized Neural Networks
• Few-Shot Learning via Learning the Representation, Provably
• Linear Programming for Large-Scale Markov Decision Problems
• Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms
• An optimal algorithm for bandit convex optimization
• Bilinear Classes: A Structural Framework for Provable Generalization in RL
• Neural Contextual Bandits with Deep Representation and Shallow Exploration
• Shape Matters: Understanding the Implicit Bias of the Noise Covariance
• High-Dimensional Sparse Linear Bandits
• Stochastic Linear Bandits with Hidden Low Rank Structure
• When Does Non-Orthogonal Tensor Decomposition Have No Spurious Local Minima?
• Minimax rate of convergence and the performance of ERM in phase recovery
• Label Noise SGD Provably Prefers Flat Global Minimizers
• Structured Stochastic Linear Bandits
• Provable Model-based Nonlinear Bandit and Reinforcement Learning: Shelve Optimism, Embrace Virtual Curvature
• Bandit Phase Retrieval

Cited by in corpus (1)

• Going Beyond Linear RL: Sample Efficient Neural Function Approximation