Learning with Good Feature Representations in Bandits and in RL with a
  Generative Model
  The construction by Du et al. (2019) implies that even if a learner is given
linear features in $\mathbb R^d$ that approximate the rewards in a bandit with
a uniform error of $\epsilon$, then searching for an action that is optimal up
to $O(\epsilon)$ 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(\epsilon \sqrt{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 $\epsilon$. For linear bandits, we prove a bound on the regret of
order $\sqrt{dn \log(k)} + \epsilon n \sqrt{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 $\epsilon
\sqrt{d}/(1 - \gamma)^2$ and using $d/(\epsilon^2(1 - \gamma)^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.
