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

Understand

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.