Short Abstract: Du et al. (2019) implies that even if a learner is given linear features in \(R^d\) that approximate the rewards in a bandit with a uniform error of \(\varepsilon\), then searching for an action that is optimal up to \(O(\varepsilon)\) requires examining essentially all actions. This paper uses 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(\varepsilon \sqrt{d})\). Thus, features are useful when the approximation error is small relative to the dimensionality of the features.

Main reference: Lattimore T, Szepesvari C, Weisz G. Learning with good feature representations in bandits and in rl with a generative model.