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.
arXiv commentUpdated Figure 1 and its caption
References in corpus (40)
- Trust Region Policy Optimization
- Empirical Evaluation of Rectified Activations in Convolutional Network
- Dota 2 with Large Scale Deep Reinforcement Learning
- Applications of Deep Learning and Reinforcement Learning to Biological Data
- Learning Latent Dynamics for Planning from Pixels
- Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits
- MOPO: Model-based Offline Policy Optimization
- Provably Efficient Reinforcement Learning with Linear Function Approximation
- Input Convex Neural Networks
- Contextual Decision Processes with Low Bellman Rank are PAC-Learnable
- Provably Optimal Algorithms for Generalized Linear Contextual Bandits
- Algorithmic Framework for Model-based Deep Reinforcement Learning with Theoretical Guarantees
- Finite-Time Analysis of Kernelised Contextual Bandits
- Efficient Optimal Learning for Contextual Bandits
- Gradient Descent Converges to Minimizers
- Model-Based Reinforcement Learning with Value-Targeted Regression
- Learning Near Optimal Policies with Low Inherent Bellman Error
- Efficient Learning of Generalized Linear and Single Index Models with Isotonic Regression
- Model-based RL in Contextual Decision Processes: PAC bounds and Exponential Improvements over Model-free Approaches
- Neural Contextual Bandits with UCB-based Exploration
- Optimism in Reinforcement Learning with Generalized Linear Function Approximation
- Provably efficient RL with Rich Observations via Latent State Decoding
- Practical Contextual Bandits with Regression Oracles
- 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
- Provably Efficient -learning with Function Approximation via Distribution Shift Error Checking Oracle
- Information Theoretic Regret Bounds for Online Nonlinear Control
- An Information-Theoretic Analysis for Thompson Sampling with Many Actions
- 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
- Improved Optimistic Algorithms for Logistic Bandits
- On Oracle-Efficient PAC RL with Rich Observations
- High-Dimensional Sparse Linear Bandits
- Provably Efficient Reinforcement Learning with Aggregated States
- Efficient Planning in Large MDPs with Weak Linear Function Approximation
- On the Performance of Thompson Sampling on Logistic Bandits
- Nearly Dimension-Independent Sparse Linear Bandit over Small Action Spaces via Best Subset Selection
- Bandit Theory meets Compressed Sensing for high dimensional Stochastic Linear Bandit