Cascading Decomposition and State Abstractions for Reinforcement Learning

Problem decomposition and state abstractions applied in the hierarchical problem solving often requires manual construction of a hierarchy structure in advance. This work is to provide some automatic algorithms for dimension reduction in problem solving. We propose cascading decomposition algorithm based on the spectral analysis on a normalized graph Laplacian to decompose the problem into several sub-problems and conduct parameter relevance analysis on each sub-problem to perform dynamic state abstraction. In each decomposed sub-problem, only parameters in the projected state space related to its sub-goal are reserved, and identical sub-problems are integrated into one through feature comparison. The whole problem is transformed into a combination of projected sub-problems, and problem solving in the abstracted space is more efficient. The paper demonstrates the performance improvement on reinforcement learning based on the proposed state space decomposition and abstraction methods using a capture-the-flag scenario.