Abstract
State abstraction is of central importance in reinforcement learning and Markov Decision Processes. This paper studies the case of variable resolution state abstraction for continuous-state, deterministic dynamic control problems in which near-optimal policies are required. We describe variable resolution policy and value function representations based on Kuhn triangulations embedded in a kd-tree. We then consider top-down approaches to choosing which cells to split in order to generate improved policies. By introducing two new non-local measures, influence and variance, we derive a splitting criterion that allows one cell to efficiently take into account its impact on other cells when deciding whether to split. We evaluate the performance of a variety of splitting criteria on many benchmark problems, paying careful attention to their number-of-cells versus closeness-to-optimality tradeoff curves.
Introduction
Solving continuous optimal control problems often involves the "curse of dimensionality." To find an optimal policy for tasks like balancing a pole or driving a car, researchers typically discretize the continuous state space into a grid. However, uniform grids are notoriously inefficient; they allocate the same computational resources to "easy" regions as they do to critical decision boundaries where precision is paramount. This paper proposes a method for variable resolution discretization, automatically refining the grid only where it most benefits the final policy.
Methodology: Variable Resolution Discretization
The core of the proposed approach lies in how the state space is represented and refined.
Discretization and Interpolation
The state space is partitioned using a kd-tree, where each leaf node represents a hyper-rectangular cell. To maintain continuity and manage computational complexity, the authors employ Kuhn triangulations within these cells. This allows for linear interpolation of values (barycentric interpolation), ensuring that the approximated value function remains tractable.
Splitting Criteria: Influence and Variance
The primary innovation is the move from local splitting heuristics to a global, non-local criterion. The authors introduce two key measures:
- Variance ($\sigma$): Quantifies the uncertainty or approximation error of the value function within a specific cell.
- Influence ($I$): A non-local measure that calculates the degree to which a state contributes to the value of other critical states—specifically those where the current policy is in "disagreement" or flux.
By combining these into a single heuristic ($Stdev\_Inf$), the algorithm prioritizes splitting cells that exhibit both high uncertainty and significant influence on the regions where the optimal policy is being determined.
Experimental Evaluation
The method was tested on several standard Reinforcement Learning benchmarks.
Datasets
- Car-on-the-Hill: A 2D problem requiring a car to gain momentum to reach a goal at the top of a steep hill.
- Cart-Pole: A 4D problem involving balancing a pole on a cart within a constrained region.
- Acrobot: A 4D, two-link underactuated robot arm task.
Key Results
- Efficiency: In the "Car-on-the-Hill" task, the variable resolution approach achieved near-optimal performance using four times fewer states than a uniform grid.
- Scalability: In 4D tasks (Cart-Pole and Acrobot), local splitting criteria often failed by over-refining irrelevant areas. The $Stdev\_Inf$ criterion successfully focused on critical regions like the balance point, significantly outperforming both uniform grids and local heuristics.
- Parsimony: The resulting kd-trees are significantly smaller, leading to controllers that require less memory and offer faster evaluation times.
Discussion and Future Work
The research highlights that "Policy Disagreement" serves as an effective compass for refinement. By using "Influence" as a form of credit assignment, importance can be propagated backward through time to precursors of difficult decisions.
While the "top-down" splitting approach is highly effective, the authors suggest that a "bottom-up" pruning or merging mechanism would further enhance robustness. Additionally, while this work focuses on deterministic systems, extending these global influence measures to stochastic environments remains a significant area for future research.
Summary updated