Provable Model-based Nonlinear Bandit and Reinforcement Learning: Shelve Optimism, Embrace Virtual Curvature
arXiv:2102.04168
Abstract
This paper studies model-based bandit and reinforcement learning (RL) with nonlinear function approximations. We propose to study convergence to approximate local maxima because we show that global convergence is statistically intractable even for one-layer neural net bandit with a deterministic reward. For both nonlinear bandit and RL, the paper presents a model-based algorithm, Virtual Ascent with Online Model Learner (ViOlin), which provably converges to a local maximum with sample complexity that only depends on the sequential Rademacher complexity of the model class. Our results imply novel global or local regret bounds on several concrete settings such as linear bandit with finite or sparse model class, and two-layer neural net bandit. A key algorithmic insight is that optimism may lead to over-exploration even for two-layer neural net model class. On the other hand, for convergence to local maxima, it suffices to maximize the virtual return if the model can also reasonably predict the size of the gradient and Hessian of the real return.
Updated Figure 1 and its caption
References in corpus (19)
- Applications of Deep Learning and Reinforcement Learning to Biological Data
- Contextual Decision Processes with Low Bellman Rank are PAC-Learnable
- Efficient Optimal Learning for Contextual Bandits
- Model-Based Reinforcement Learning with Value-Targeted Regression
- Efficient Learning of Generalized Linear and Single Index Models with Isotonic Regression
- Optimism in Reinforcement Learning with Generalized Linear Function Approximation
- Model-based Reinforcement Learning and the Eluder Dimension
- Model-Augmented Actor-Critic: Backpropagating through Paths
- FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPs
- Information Theoretic Regret Bounds for Online Nonlinear Control
- Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspective
- Efficient Regret Minimization in Non-Convex Games
- Bilinear Classes: A Structural Framework for Provable Generalization in RL
- High-Dimensional Sparse Linear Bandits
- Provably Efficient Reinforcement Learning with Aggregated States
- Efficient Planning in Large MDPs with Weak Linear Function Approximation
- Nearly Dimension-Independent Sparse Linear Bandit over Small Action Spaces via Best Subset Selection
- On the Performance of Thompson Sampling on Logistic Bandits
- Bandit Theory meets Compressed Sensing for high dimensional Stochastic Linear Bandit