Performance-Driven Environment Abstraction with Multi-Timescale Learning
For RL practitioners dealing with large state spaces, this method offers a principled way to learn compact abstractions that improve sample efficiency and planning speed.
This work proposes a performance-driven environment abstraction method for large MDPs that directly optimizes decision quality by aggregating states and sharing action distributions. The multi-timescale RL framework jointly adapts policy and tree-structured abstraction, achieving substantial state compression, improved sample efficiency, and faster replanning compared to actor-critic baselines.
We study performance-driven environment abstraction for decision-making in large Markov decision processes. Rather than preserving geometric or topological structure, we seek abstractions that directly optimize decision quality. We model abstraction as a controlled approximation obtained by aggregating the state space and enforcing a shared action distribution within each aggregated state. For a fixed partition, we establish a performance guarantee that separates value-function approximation error from the loss introduced by action sharing. Guided by this analysis, we develop a multi-timescale reinforcement learning framework that jointly adapts the policy and a tree-structured environment abstraction. The resulting algorithm refines and coarsens regions of the state space based on Q-value discrepancies, balancing performance against abstraction size and complexity. Empirical results demonstrate substantial state compression, improved sample efficiency, and faster replanning compared to actor-critic baselines.