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

arXiv: https://arxiv.org/abs/1911.07676 · HTML: https://mlsanity.com/paper/1911.07676/

## Key facts

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

## Built on by (most cited first, 30 of 127)

- [Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraints](https://mlsanity.com/paper/2101.02195/) (2021)
- [Recent Advances in Reinforcement Learning in Finance](https://mlsanity.com/paper/2112.04553/) (2021)
- [Model-free Representation Learning and Exploration in Low-rank MDPs](https://mlsanity.com/paper/2102.07035/) (2021)
- [Adapting to Misspecification in Contextual Bandits](https://mlsanity.com/paper/2107.05745/) (2021)
- [Offline Reinforcement Learning: Fundamental Barriers for Value Function Approximation](https://mlsanity.com/paper/2111.10919/) (2021)
- [On The Effect of Auxiliary Tasks on Representation Dynamics](https://mlsanity.com/paper/2102.13089/) (2021)
- [Near-Optimal Offline Reinforcement Learning via Double Variance Reduction](https://mlsanity.com/paper/2102.01748/) (2021)
- [High-Dimensional Experimental Design and Kernel Bandits](https://mlsanity.com/paper/2105.05806/) (2021)
- [Misspecified Gaussian Process Bandit Optimization](https://mlsanity.com/paper/2111.05008/) (2021)
- [Nearly Optimal Algorithms for Linear Contextual Bandits with Adversarial Corruptions](https://mlsanity.com/paper/2205.06811/) (2022)
- [Near-optimal Representation Learning for Linear Bandits and Linear RL](https://mlsanity.com/paper/2102.04132/) (2021)
- [A Model Selection Approach for Corruption Robust Reinforcement Learning](https://mlsanity.com/paper/2110.03580/) (2021)
- [Bayesian decision-making under misspecified priors with applications to meta-learning](https://mlsanity.com/paper/2107.01509/) (2021)
- [Sample-Efficient Learning of Stackelberg Equilibria in General-Sum Games](https://mlsanity.com/paper/2102.11494/) (2021)
- [An Exponential Lower Bound for Linearly-Realizable MDPs with Constant Suboptimality Gap](https://mlsanity.com/paper/2103.12690/) (2021)
- [Contextual Bandits with Large Action Spaces: Made Practical](https://mlsanity.com/paper/2207.05836/) (2022)
- [Minimax Optimal Fixed-Budget Best Arm Identification in Linear Bandits](https://mlsanity.com/paper/2105.13017/) (2021)
- [Leveraging Good Representations in Linear Contextual Bandits](https://mlsanity.com/paper/2104.03781/) (2021)
- [Which Mutual-Information Representation Learning Objectives are Sufficient for Control?](https://mlsanity.com/paper/2106.07278/) (2021)
- [Provable and Practical: Efficient Exploration in Reinforcement Learning via Langevin Monte Carlo](https://mlsanity.com/paper/2305.18246/) (2023)
- [Sample-Efficient Reinforcement Learning Is Feasible for Linearly Realizable MDPs with Limited Revisiting](https://mlsanity.com/paper/2105.08024/) (2021)
- [Bayesian Optimization with Conformal Prediction Sets](https://mlsanity.com/paper/2210.12496/) (2022)
- [Investigating the Properties of Neural Network Representations in Reinforcement Learning](https://mlsanity.com/paper/2203.15955/) (2022)
- [Efficient Local Planning with Linear Function Approximation](https://mlsanity.com/paper/2108.05533/) (2021)
- [Distribution-free Contextual Dynamic Pricing](https://mlsanity.com/paper/2109.07340/) (2021)
- [Differentially Private Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2201.07052/) (2022)
- [Efficient Active Learning with Abstention](https://mlsanity.com/paper/2204.00043/) (2022)
- [Replicable Bandits](https://mlsanity.com/paper/2210.01898/) (2022)
- [Adapting to Misspecification in Contextual Bandits with Offline Regression Oracles](https://mlsanity.com/paper/2102.13240/) (2021)
- [When Is Generalizable Reinforcement Learning Tractable?](https://mlsanity.com/paper/2101.00300/) (2021)

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