Exponential Hardness of Reinforcement Learning with Linear Function Approximation

Daniel Kane, Sihan Liu, Shachar Lovett +3

A fundamental question in reinforcement learning theory is: suppose the optimal value functions are linear in given features, can we learn them efficiently? This problem's counterp…