Sample Efficient Reinforcement Learning In Continuous State Spaces: A Perspective Beyond Linearity
This addresses a foundational gap in RL theory for practitioners working with complex nonlinear environments like gaming benchmarks.
The paper tackles the discrepancy between theoretical reinforcement learning (RL) requiring linear structures for sample efficiency and empirical success in nonlinear continuous state spaces, by introducing the Effective Planning Window (EPW) condition that enables sample efficient RL without linearity assumptions, with applications to Atari games.
Reinforcement learning (RL) is empirically successful in complex nonlinear Markov decision processes (MDPs) with continuous state spaces. By contrast, the majority of theoretical RL literature requires the MDP to satisfy some form of linear structure, in order to guarantee sample efficient RL. Such efforts typically assume the transition dynamics or value function of the MDP are described by linear functions of the state features. To resolve this discrepancy between theory and practice, we introduce the Effective Planning Window (EPW) condition, a structural condition on MDPs that makes no linearity assumptions. We demonstrate that the EPW condition permits sample efficient RL, by providing an algorithm which provably solves MDPs satisfying this condition. Our algorithm requires minimal assumptions on the policy class, which can include multi-layer neural networks with nonlinear activation functions. Notably, the EPW condition is directly motivated by popular gaming benchmarks, and we show that many classic Atari games satisfy this condition. We additionally show the necessity of conditions like EPW, by demonstrating that simple MDPs with slight nonlinearities cannot be solved sample efficiently.