Data to 14 Oct 2026

Learning with Good Feature Representations in Bandits and in RL with a Generative Model

arXiv 1911.07676 ↗First posted 18 Nov 2019stat.ML cs.LGcited by 127

Not on the map. Why?

Abstract (arXiv)

The construction by Du et al. (2019) implies that even if a learner is given linear features in mathbb Rd that approximate the rewards in a bandit with a uniform error of ε, then searching for an action that is optimal up to O(ε) requires examining essentially all actions. We use the Kiefer-Wolfowitz theorem to prove a positive result that by checking only a few actions, a learner can always find an action that is suboptimal with an error of at most O(ε √d). Thus, features are useful when the approximation error is small relative to the dimensionality of the features. The idea is applied to stochastic bandits and reinforcement learning with a generative model where the learner has access to d-dimensional linear features that approximate the action-value functions for all policies to an accuracy of ε. For linear bandits, we prove a bound on the regret of order √dn log(k) + ε n √d log(n) with k the number of actions and n the horizon. For RL we show that approximate policy iteration can learn a policy that is optimal up to an additive error of order ε √d/(1 - γ)2 and using d/(ε2(1 - γ)4) samples from a generative model. These bounds are independent of the finer details of the features. We also investigate how the structure of the feature set impacts the tradeoff between sample complexity and estimation error.

Key facts. Cited by 127 papers in the map (data through 14 Oct 2026). First posted on arXiv 18 Nov 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 42; 2022: 22; 2023: 20; 2024: 16; 2025: 7; 2026: 20.

127 papers.

Sort:

By area:

2021Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraintscited by 124
2021Recent Advances in Reinforcement Learning in Financecited by 110
2021Model-free Representation Learning and Exploration in Low-rank MDPscited by 82
2021Adapting to Misspecification in Contextual Banditscited by 81
2021Offline Reinforcement Learning: Fundamental Barriers for Value Function Approximationcited by 71
2021On The Effect of Auxiliary Tasks on Representation Dynamicscited by 57
2021Near-Optimal Offline Reinforcement Learning via Double Variance Reductioncited by 56
2021High-Dimensional Experimental Design and Kernel Banditscited by 56
2021Misspecified Gaussian Process Bandit Optimizationcited by 55
2022Nearly Optimal Algorithms for Linear Contextual Bandits with Adversarial Corruptionscited by 51
2021Near-optimal Representation Learning for Linear Bandits and Linear RLcited by 45
2021A Model Selection Approach for Corruption Robust Reinforcement Learningcited by 45

38 more

2021Bayesian decision-making under misspecified priors with applications to meta-learningcited by 44
2021Sample-Efficient Learning of Stackelberg Equilibria in General-Sum Gamescited by 40
2021An Exponential Lower Bound for Linearly-Realizable MDPs with Constant Suboptimality Gapcited by 40
2022Contextual Bandits with Large Action Spaces: Made Practicalcited by 33
2021Minimax Optimal Fixed-Budget Best Arm Identification in Linear Banditscited by 32
2021Leveraging Good Representations in Linear Contextual Banditscited by 29
2021Which Mutual-Information Representation Learning Objectives are Sufficient for Control?cited by 29
2023Provable and Practical: Efficient Exploration in Reinforcement Learning via Langevin Monte Carlocited by 29
2021Sample-Efficient Reinforcement Learning Is Feasible for Linearly Realizable MDPs with Limited Revisitingcited by 28
2022Bayesian Optimization with Conformal Prediction Setscited by 28
2022Investigating the Properties of Neural Network Representations in Reinforcement Learningcited by 24
2021Efficient Local Planning with Linear Function Approximationcited by 23
2021Distribution-free Contextual Dynamic Pricingcited by 22
2022Differentially Private Reinforcement Learning with Linear Function Approximationcited by 22
2022Efficient Active Learning with Abstentioncited by 22
2022Replicable Banditscited by 22
2021Adapting to Misspecification in Contextual Bandits with Offline Regression Oraclescited by 21
2021When Is Generalizable Reinforcement Learning Tractable?cited by 20
2022Contexts can be Cheap: Solving Stochastic Contextual Bandits with Linear Bandit Algorithmscited by 19
2021On Query-efficient Planning in MDPs under Linear Realizability of the Optimal State-value Functioncited by 18
2021Design of Experiments for Stochastic Contextual Linear Banditscited by 18
2021Reinforcement Learning in Linear MDPs: Constant Regret and Representation Selectioncited by 18
2023Distributionally Robust Model-based Reinforcement Learning with Large State Spacescited by 17
2025Generative Models in Decision Making: A Surveycited by 15
2021Pareto Optimal Model Selection in Linear Banditscited by 14
2021On component interactions in two-stage recommender systemscited by 14
2023Best-of-Three-Worlds Linear Bandit Algorithm with Variance-Adaptive Regret Boundscited by 14
2021Pure Exploration in Kernel and Neural Banditscited by 13
2021Dealing With Misspecification In Fixed-Confidence Linear Top-m Identificationcited by 12
2022Bilinear Exponential Family of MDPs: Frequentist Regret Bound with Tractable Exploration and Planningcited by 12
2023Online Clustering of Bandits with Misspecified User Modelscited by 12
2022A Robust Phased Elimination Algorithm for Corruption-Tolerant Gaussian Process Banditscited by 11
2021Online Markov Decision Processes with Aggregate Bandit Feedbackcited by 10
2021When Are Linear Stochastic Bandits Attackable?cited by 10
2021Linear Bandit Algorithms with Sublinear Time Complexitycited by 9
2023When is Agnostic Reinforcement Learning Statistically Tractable?cited by 9
2024Mean-Field Sampling for Cooperative Multi-Agent Reinforcement Learningcited by 9
2022Differentially Private Linear Bandits with Partial Distributed Feedbackcited by 8

50 most cited of 127 All 127 (JSON)