Overcoming the Curse of Dimensionality in Reinforcement Learning Through Approximate Factorization

In recent years, reinforcement learning (RL) (Sutton and Barto, 2018) has become a popular framework for solving sequential decision-making problems in unknown environments, with applications across different domains such as robotics (Kober et al., 2013), transportation (Haydari and Yılmaz, 2020), power systems (Chen et al., 2022), and financial markets (Charpentier et al., 2021). Despite significant progress, the curse of dimensionality remains a major bottleneck in RL tasks (Sutton and Barto, 2018). Specifically, the sample complexity grows geometrically with the dimensionality of the state-action space of the environment, posing challenges for large-scale applications. For example, in robotic control, even adding one more degree of freedom to a single robot can significantly increase the complexity of the control problem (Spong et al., 2020). To overcome the curse of dimensionality in sample complexity, a common approach is incorporating function approximation to approximate either the value function or the policy using a prespecified function class (e.g., neural networks) (Sutton and Barto, 2018). While this approach works in certain applications, these methods heavily rely on the design of the function approximation class, tailored parameter tuning, and other empirical insights. Moreover, they often lack theoretical guarantees. To the best of our knowledge, most existing results are limited to basic settings with linear function approximation (Tsitsiklis and Van Roy, 1996; Bhandari et al., 2018; Srikant and Ying, 2019; Chen et al., 2023).