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

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.