Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspective

Abstract

In the classical multi-armed bandit problem, instance-dependent algorithms attain improved performance on "easy" problems with a gap between the best and second-best arm. Are similar guarantees possible for contextual bandits? While positive results are known for certain special cases, there is no general theory characterizing when and how instance-dependent regret bounds for contextual bandits can be achieved for rich, general classes of policies. We introduce a family of complexity measures that are both sufficient and necessary to obtain instance-dependent regret bounds. We then introduce new oracle-efficient algorithms which adapt to the gap whenever possible, while also attaining the minimax rate in the worst case. Finally, we provide structural results that tie together a number of complexity measures previously proposed throughout contextual bandits, reinforcement learning, and active learning and elucidate their role in determining the optimal instance-dependent regret. In a large-scale empirical evaluation, we find that our approach often gives superior results for challenging exploration problems. Turning our focus to reinforcement learning with function approximation, we develop new oracle-efficient algorithms for reinforcement learning with rich observations that obtain optimal gap-dependent sample complexity.

References in corpus (28)

• A Contextual-Bandit Approach to Personalized News Article Recommendation
• On the Complexity of Best Arm Identification in Multi-Armed Bandit Models
• Fast learning rates for plug-in classifiers
• Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits
• Provably Efficient Reinforcement Learning with Linear Function Approximation
• Contextual Decision Processes with Low Bellman Rank are PAC-Learnable
• Concentration inequalities and asymptotic results for ratio type empirical processes
• Nonparametric Bandits with Covariates
• Making Contextual Decisions with Low Technical Debt
• Model-Based Reinforcement Learning with Value-Targeted Regression
• On Explore-Then-Commit Strategies
• Online Importance Weight Aware Updates
• Optimism in Reinforcement Learning with Generalized Linear Function Approximation
• Provably efficient RL with Rich Observations via Latent State Decoding
• A Contextual Bandit Bake-off
• Contextual Bandit Learning with Predictable Rewards
• Practical Contextual Bandits with Regression Oracles
• Model-based Reinforcement Learning and the Eluder Dimension
• Active Learning for Cost-Sensitive Classification
• FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPs
• Provably Efficient $Q$-learning with Function Approximation via Distribution Shift Error Checking Oracle
• Exploration in Structured Reinforcement Learning
• Thompson sampling with the online bootstrap
• Learning with Square Loss: Localization through Offset Rademacher Complexity
• Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity
• On Oracle-Efficient PAC RL with Rich Observations
• Kinematic State Abstraction and Provably Efficient Rich-Observation Reinforcement Learning
• Upper Counterfactual Confidence Bounds: a New Optimism Principle for Contextual Bandits

Cited by in corpus (15)

• Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms
• Model-free Representation Learning and Exploration in Low-rank MDPs
• The Power of Exploiter: Provable Multi-Agent RL in Large State Spaces
• Provable Model-based Nonlinear Bandit and Reinforcement Learning: Shelve Optimism, Embrace Virtual Curvature
• Representation Learning for Online and Offline RL in Low-rank MDPs
• Beyond Value-Function Gaps: Improved Instance-Dependent Regret Bounds for Episodic Reinforcement Learning
• Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraints
• Provably Efficient Representation Selection in Low-rank Markov Decision Processes: From Online to Offline RL
• Top-$k$ eXtreme Contextual Bandits with Arm Hierarchy
• Adapting to Misspecification in Contextual Bandits with Offline Regression Oracles
• Regret Minimization in Isotonic, Heavy-Tailed Contextual Bandits via Adaptive Confidence Bands
• A Short Note on the Relationship of Information Gain and Eluder Dimension
• Online Sub-Sampling for Reinforcement Learning with General Function Approximation
• Confidence-Budget Matching for Sequential Budgeted Learning
• Efficient and Optimal Algorithms for Contextual Dueling Bandits under Realizability