Abstract: The problem of state abstraction is of central importance in optimal control, reinforcement learning and Markov decision processes. This paper studies the case of variable resolution state abstraction for continuous time and space, deterministic dynamic control problems in which near-optimal policies are required. We begin by defining a class of variable resolution policy and value function representations based on Kuhn triangulations embedded in a kd-trie. We then consider top-down approaches to choosing which cells to split in order to generate improved policies. The core of this paper is the introduction and evaluation of a wide variety of possible splitting criteria. We begin with local approaches based on value function and policy properties that use only features of individual cells in making split choices. Later, by introducing two new non-local measures, influence and variance, we derive splitting criteria that allow one cell to efficiently take into account its impact on other cells when deciding whether to split. Influence is an efficiently-calculable measure of the extent to which changes in some state effect the value function of some other states. Variance is an efficiently-calculable measure of how risky is some state in a Markov chain: a low variance state is one in which we would be very surprised if, during any one execution, the long-term reward attained from that state differed substantially from its expected value, given by the value function.
Introduction
Solving optimal control problems in continuous state spaces typically involves the Hamilton-Jacobi-Bellman (HJB) equation. A primary obstacle in this domain is the "curse of dimensionality," where the computational resources required for uniform discretization grow exponentially with the number of state variables. Traditional methods often waste memory refining regions of the state space that have little impact on the final control policy. This paper proposes a variable-resolution approach that adaptively refines the discretization grid only where it is most beneficial for policy performance.
Discretization Framework
The proposed method utilizes a kd-trie data structure to manage the hierarchical partitioning of the state space. Within each cell of this trie, the state space is further subdivided using Kuhn triangulations. This specific triangulation method is chosen for its computational efficiency, allowing for linear interpolation in $O(d \ln d)$ time, where $d$ is the dimensionality of the space.
By embedding these triangulations within a top-down refinement framework, the system can selectively split cells to increase resolution in critical areas while maintaining a coarse representation elsewhere.
Splitting Criteria: Local vs. Global
The central contribution of this work is the evaluation of different heuristics for deciding which cells to split.
Local and Policy-Based Criteria
Local criteria focus on the properties of individual cells, such as the gradient or non-linearity of the value function. While intuitive, these methods often fail in high-dimensional spaces because they may over-refine "singularities" (discontinuities in the value function) that do not actually affect the optimal action. Policy disagreement criteria attempt to mitigate this by splitting where the discrete policy differs from the continuous gradient-based policy.
The Global Heuristic ($Stdev\_Inf$)
To overcome the limitations of local methods, the authors introduce a novel global heuristic that combines two non-local measures:
- Influence ($I$): A measure of how much a change in a local reward affects the value function of other states, acting as a "shadow price" for discretization error.
- Variance ($\sigma^2$): A measure of the error or uncertainty introduced by the interpolation process itself.
By targeting cells with high $Stdev\_Inf$ (the product of standard deviation and influence), the algorithm focuses refinement on areas that are both poorly approximated and highly relevant to the global policy performance.
Experimental Results
The $Stdev\_Inf$ criterion was evaluated against uniform grids and local refinement methods on several 4D control benchmarks, including the Cart-Pole and Acrobot systems.
Key findings include:
- Efficiency: The global heuristic achieved significantly higher cumulative reinforcement with far fewer states than uniform or local methods.
- Policy Focus: In the "Car on the Hill" 2D task, the global heuristic successfully ignored value function discontinuities that were irrelevant to the optimal policy, leading to a more parsimonious grid.
- Scalability: While local methods sometimes performed worse than uniform grids in 4D due to irrelevant refinement, the global heuristic consistently identified critical switching boundaries.
Conclusion
This research demonstrates that global awareness is essential for efficient state abstraction in continuous optimal control. By combining influence and variance, the $Stdev\_Inf$ criterion provides a robust mechanism for building adaptive grids that prioritize policy quality over mere value function approximation. Future work may extend these concepts to stochastic systems and explore bottom-up pruning techniques to further optimize memory usage.
Summary updated