Theoretical Barriers in Bellman-Based Reinforcement Learning
This work highlights a theoretical barrier for researchers and practitioners in reinforcement learning, showing that common approaches can be fundamentally flawed, which is incremental as it builds on known issues but formalizes them with new counterexamples.
The paper identifies a fundamental limitation in Bellman-based reinforcement learning algorithms that rely on generalization from sampled states, constructing counterexamples where these methods fail to exploit simple structures and neglect critical information, leading to inefficiencies, and extends this negative result to Hindsight Experience Rereachability approaches.
Reinforcement Learning algorithms designed for high-dimensional spaces often enforce the Bellman equation on a sampled subset of states, relying on generalization to propagate knowledge across the state space. In this paper, we identify and formalize a fundamental limitation of this common approach. Specifically, we construct counterexample problems with a simple structure that this approach fails to exploit. Our findings reveal that such algorithms can neglect critical information about the problems, leading to inefficiencies. Furthermore, we extend this negative result to another approach from the literature: Hindsight Experience Replay learning state-to-state reachability.