Dynamic Programming with State Abstraction for Reinforcement Learning

Abstract

Reinforcement learning (RL) relies heavily on dynamic programming (DP) to find optimal policies. However, the curse of dimensionality significantly limits its applicability in environments with large or continuous state spaces. Traditional DP methods become computationally intractable, often requiring exponential time and memory with respect to the number of states. This paper proposes a novel approach that combines dynamic programming with state abstraction. The core idea is to allow the algorithm to automatically learn to group similar states together, effectively reducing the size of the state space without compromising the accuracy of the DP solution. The algorithm iteratively identifies states based on their similarity, creating abstract states, and then applies DP on these smaller state sets. We demonstrate that this approach offers a significant improvement in computational efficiency and scalability compared to standard DP, particularly in environments where state space exploration is a major bottleneck. The key elements of this method include a similarity metric for state comparison, a clustering algorithm to group similar states, and an efficient DP solver applied to the abstracted state sets. The theoretical framework presented here provides a foundation for designing more scalable and robust RL algorithms.