Comments on the Du-Kakade-Wang-Yang Lower Bounds

Du, Kakade, Wang, and Yang [1] recently established intriguing lower bounds on the sample complexity of reinforcement learning with a misspecified representation. Versions of the lower bound apply to model learning, value function learning, and policy learning. The cornerstone of their analysis is a basic problem, embedded in each of their results, of bandit learning with a misspecified linear model. The problem is one of finding a needle in a haystack: an agent must identify among an exponentially large number of actions the only one that generates rewards. This obviously requires exponentially many trials. One might hope that with a suitable choice of features, by using a linearly parameterized approximation to generalize across actions, the agent can efficiently identify the rewarding action.