Efficient Policy Iteration and Value Iteration via State Space Clustering

This paper presents a novel state-space clustering technique specifically designed for Reinforcement Learning (RL) problems with discrete state and action spaces. Building on this clustering methodology, we propose a Hierarchical Reinforcement Learning (HRL) framework to improve the efficiency of policy iteration (PI) and value iteration (VI) algorithms. Our approach partitions the state space into well-defined, homogeneous clusters and identifies representative prototype states for each cluster. Transitioning between clusters is facilitated through macro-actions, which are derived using the Depth First Search (DFS) algorithm. By focusing value function updates exclusively on these prototype states during PI and VI operations, the proposed method substantially reduces computational overhead without compromising performance. Experimental evaluations demonstrate that the proposed technique generates highly cohesive clusters, enhances policy learning quality, and accelerates the convergence of the PI and VI algorithms.