Introduction
When applying reinforcement learning (RL) to real-world, continuous problems such as robotics, researchers typically discretize the environment into a grid of states and a sequence of time steps. This creates a "Goldilocks" dilemma:
- Too coarse: The agent cannot perceive enough detail to learn an optimal policy, leading to "waves" or errors in the value function.
- Too fine: The agent is overwhelmed by data, requiring massive amounts of memory and taking excessively long to converge.
Furthermore, space and time discretization are mathematically linked. Refining the spatial grid without adjusting the time sampling rate (or vice versa) can break the mathematical consistency of the Bellman equation. This paper introduces a method for automatically adjusting both the spatial grid and the time-step size in RL for continuous deterministic systems, allowing the algorithm to decide where and when it needs more detail.
Dual-Adaptive Approach
The paper proposes a dual-adaptive approach for deterministic systems with infinite horizon discounted costs:
- Adaptive Grid Refinement: The state space is partitioned using a triangulation (simplices). The algorithm uses a local a-posteriori error estimate, monitoring the difference between the current value function and the value predicted by the Bellman equation. If this error exceeds a specific tolerance in a simplex, that part of the grid is subdivided.
- Adaptive Time Refinement: A new criterion is introduced for the time step ($h$). The algorithm compares the value update calculated at a full time step ($h$) against an update calculated using a half-step ($h/2$). If the half-step yields a significantly lower cost that isn't just a result of spatial discretization error, the time step is halved for that region.
These two schemes are coupled. The grid refinement follows numerical methods used for the Bellman equation, while the time refinement borrows logic from adaptive step-size control in ordinary differential equations (ODEs).
Experimental Setup
Instead of standard RL benchmarks, the approach is evaluated on a synthetic 2D deterministic control problem:
- System: A linear system with a stationary point at $(0.375, 0.375)$ and boundaries that reflect the agent.
- Goal: Steer the agent along a specific L-shaped trajectory in the state space.
- Cost Function: Based on the distance from the agent's current state to the target L-shaped path.
Key Insights and Results
The Importance of the $k/h$ Ratio
For deterministic problems, the ratio of spatial discretization ($k$) to time discretization ($h$) must remain roughly constant ($k/h = C$) to maintain consistency. Choosing the right constant is critical for convergence.
Visualizing "Waves"
The paper illustrates that using a time step that is too large relative to the grid creates "waves" in the value function. These represent a fundamental failure of the agent to understand the cost landscape.
Efficiency through Sparsity
By only refining the grid where the cost function varies significantly (such as near the target trajectory), the agent avoids wasting memory on less complex parts of the state space. Visual results show the grid successfully "clustering" around the L-shaped target trajectory.
Performance Gains
The adaptive approach achieved the same level of accuracy as a fixed-grid approach but was roughly 100 times faster in terms of learning time. Additionally, the Kaczmarz-update method proved more stable than the Kronecker-update for these adaptive grids, particularly with continuous value functions.
Limitations and Future Work
- Dimensionality: While triangulation works well for 2D or 3D problems, it becomes computationally difficult in high-dimensional spaces. Future work may explore rectangular grids.
- Stiff Systems: The current method struggles with "stiff" systems (where some variables change much faster than others) and discontinuous cost functions (like dry friction).
- Coarsening: The paper focuses on refining the grid. A "coarsening" mechanism to merge cells where detail is no longer needed would be valuable for long-term learning.
- Heuristics: The success of the algorithm depends on manual choices for tolerance values, which could ideally be automated in future self-tuning versions.
Summary updated