Statistical limits and conditional complexity in real-world reinforcement learning: a tutorial survey

Full abstract

Read the full abstract

Reinforcement learning (RL) has achieved remarkable success in controlled environments, demonstrating superhuman performance in domains such as game playing and simulated robotics. However, its transition to real-world applications remains constrained by fundamental statistical challenges that limit scalability, reliability, and safety. This study systematically examines four such challenges: sample inefficiency, in which millions of interactions may be required even for simple tasks; nonstationarity, arising from evolving environmental dynamics and agent-induced distribution shifts; partial observability, which violates the Markov assumption and inflates estimation variance; and the curse of dimensionality, which causes exploration demands to grow rapidly in high-dimensional spaces. Known theoretical lower bounds from the literature are reviewed to characterize the fundamental limits of these challenges, and a survey of contemporary mitigation strategies is presented, including model-based methods, robust Markov decision process formulations, memory-augmented architectures, and hierarchical abstractions. In addition to these core statistical challenges, this study briefly discusses related deployment-oriented topics—including safe RL, explainable RL, multi-agent coordination, and curriculum learning—that interact with, but remain distinct from, the four primary statistical limits. This study is intended as a tutorial synthesis rather than a source of new theoretical results. Its main contribution is organizational and interpretive: It unifies existing lower bounds, representative complexity arguments, and practical mitigation strategies around the structural assumptions that make real-world RL easier or harder.