Adaptive Discretization for Continuous Decision Making

92 concepts64 papers1 proposal

Continuous spaces are ubiquitous in real-world decision-making, from tuning robotic joints and setting financial prices to optimizing medical dosages. Traditional tabular reinforcement learning and multi-armed bandit algorithms, however, rely on discrete states and actions.

The simplest way to bridge this gap is static discretization: slicing the continuous space into a uniform grid of size $\epsilon$. But uniform grids suffer from a severe flaw. As noted by Scott Davies in Multidimensional Triangulation and Interpolation for Reinforcement Learning, uniform structures allocate the exact same resolution to all regions regardless of their importance. This creates a dual failure: it wastes massive computational and memory resources on suboptimal or unreachable regions, while simultaneously under-sampling critical areas where the value function changes rapidly. This exponential growth in complexity with respect to dimensionality is the classic "curse of dimensionality."

As Remi Munos argues in A Study of Reinforcement Learning in the Continuous Case by the Means of Viscosity Solutions, static approaches are fundamentally inefficient. To make continuous control practical, algorithms must dynamically allocate resolution only to areas where the value function or policy shifts most rapidly. This insight motivates adaptive discretization.


The Core Mechanism: Just-in-Time Refinement

Adaptive discretization algorithms solve the curse of dimensionality by starting with a completely coarse representation—often a single partition representing the entire space—and refining it "just in time."

Static Uniform Grid (Inefficient)      Adaptive Grid (Efficient)
+---+---+---+---+                      +-------+-------+
|   |   |   |   |                      |       |   |   |
+---+---+---+---+                      |       +---+---+
|   |   |   |   |   ==============>    |       | * |   |
+---+---+---+---+                      +-------+---+---+
|   |   |   |   |                      |       |       |
+---+---+---+---+                      |       |       |
+---+---+---+---+                      +-------+-------+
(* Target Region)

How does an algorithm know when and where to split a region? The literature highlights three primary triggers for refinement:

  1. Visit Frequency (Experience-Driven): In Adaptive Discretization for Episodic Reinforcement Learning in Metric Spaces, Sean R. Sinclair et al. propose a mechanism that splits a specific region of the state-action space into a finer partition only after that region has been visited a threshold number of times. This ensures that the resolution of the discretization increases in proportion to the agent's experience.
  2. Value and Reward Inconsistency (Performance-Driven): Hiroshi Ishiguro et al. in State Space Construction by Attention Control demonstrate a system that refines its internal world model by splitting existing states when the same action leads to inconsistent rewards. Similarly, Craig Boutilier et al. utilize a process of abductive refinement to grow and merge partitions based on the underlying structure of the domain, ensuring that computational effort scales with the complexity of the value function.
  3. Variance and Demand Transitions: In contextual settings like dynamic pricing, the authors of Contextual Dynamic Pricing with Heterogeneous Buyers show that partitioning a continuous action space based on observed variance and potential rewards allows algorithms to focus discretization efforts near critical demand transitions, managing exploration and exploitation smoothly.

Data Structures for Dynamic Partitioning

To maintain these adaptive maps efficiently without incurring massive overhead, algorithms leverage hierarchical data structures.

For instance, a $kd$-tree structure is frequently employed to adaptively partition continuous spaces. This hierarchical representation allows for selective refinement of regions based on local criteria, enabling a more efficient allocation of computational resources compared to uniform grid-based approaches.

In reinforcement learning, Anders Jonsson et al. employ statistical tests to dynamically partition a state space into a decision tree (the U-Tree algorithm). Splits are only created when a feature significantly improves the prediction of future rewards, avoiding unnecessary complexity in the state representation.

Hierarchical Partitioning (kd-tree / Decision Tree)
         [ Root Space ]
          /          \
    [Region A]     [Region B]
                    /      \
              [B-Sub1]   [B-Sub2] *High-reward focus

This concept extends to the action space via neural network architectures. Kavosh Asadi introduces Deep Radial-Basis Value Functions, which use a neural network to generate state-conditioned action centroids. This functions as a form of adaptive action-space discretization, dynamically allocating representational capacity to the most relevant regions of the action space based on the current state, bypassing fixed grids entirely.


Why It Works: Instance-Dependent Zooming

The core intuition behind why adaptive discretization works so well lies in its instance-dependent nature. In worst-case theoretical analyses, continuous spaces require exploring every corner. But real-world problems possess inherent structure: optimal policies typically trace a narrow, localized path through the state-action space.

By focusing refinement exclusively on near-optimal regions, the complexity of the learning process scales with the density of the optimal policy's path rather than the total volume of the environment.

As Akshay Krishnamurthy et al. demonstrate in Contextual Bandits with Continuous Actions: Smoothing, Zooming, and Adapting, this "zooming" behavior allows learning algorithms to automatically focus on regions containing optimal actions. This localization enables faster learning rates than worst-case theoretical bounds when optimal actions are concentrated in a small portion of the space.

When rewards are noisy or heavy-tailed, Guanghui Wang et al. show that combining this adaptive zooming with robust mean estimators prevents outliers from destabilizing the refined partitions.

Ultimately, as Lihong Li demonstrates in Lazy Approximation for Solving Continuous Finite-Horizon MDPs, using adaptive partitions to represent value functions results in much more compact models than uniform grids. Complexity is only added where rewards or transitions change, leading to a massive reduction in memory requirements and faster processing times while maintaining high accuracy in continuous environments.

Key Foundational Work

Adaptive Range Coding (1990) — contributed 2 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_adaptive_discretization_b742e4ed,
  title = {adaptive discretization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/adaptive-discretization/rdr_b742e4edf399494ea89ab78a0819078f},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_adaptive_discretization_b742e4ed_v1,
  title = {adaptive discretization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/adaptive-discretization/rdr_b742e4edf399494ea89ab78a0819078f/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake