Technical Summary: Distance-Guided Reinforcement Learning in Large Discrete Action Spaces

Problem Statement

Reinforcement Learning (RL) has achieved success in continuous and small-scale discrete domains but struggles with the "curse of cardinality" in large-scale decision-making problems such as logistics, scheduling, and recommender systems. These applications often involve action spaces with cardinalities up to $10^{20}$, containing high-dimensional discrete components, categorical variables, or hybrid discrete-continuous parameters.

Existing approaches face three primary bottlenecks:

1. Gradient Variance: Standard policy gradients suffer from variance explosion as the probability mass $\pi(a|s)$ vanishes in large action spaces.
2. Computational Tractability: Methods relying on exhaustive enumeration or pre-computed lookup tables (e.g., Wolpertinger) become intractable as dimensionality increases.
3. Structural Rigidity: Approaches like Dynamic Neighborhood Construction (DNC) rely on regular grid structures (e.g., numerical adjacency) and fail in irregularly spaced or sparse feasible regions. Furthermore, hybrid action spaces often require hierarchical sequencing, which introduces commitment bottlenecks and destabilizes training.

Methodology: Distance-Guided RL (DGRL)

The authors propose Distance-Guided Reinforcement Learning (DGRL), an off-policy actor-critic algorithm designed to scale to action spaces with up to $10^{20}$ candidates. DGRL operates in a continuous relaxation of the discrete action space and utilizes a volumetric projection loop composed of two synergistic components:

1. Sampled Dynamic Neighborhoods (SDN)

SDN addresses the exploration challenge in high-dimensional discrete spaces by performing stochastic volumetric exploration around a continuous "proto-action" $\hat{a}$ generated by the actor.

• Mechanism: Instead of relying on rigid grid lines or pre-computed nearest-neighbor tables, SDN constructs a dynamic neighborhood $B(\hat{a})$ bounded by a Chebyshev ($L_\infty$) radius $L$.
• Independent Coordinate Sampling: To avoid the combinatorial explosion of enumerating all integer points in the hypercube, SDN samples each dimension independently. It interprets $\hat{a}$ as the mode of a sampling distribution and draws $K$ candidate actions. The probability of sampling a candidate decreases with its distance from $\hat{a}$.
• Dimensional Invariance: By using the $L_\infty$ metric, the search volume remains stable as dimensionality $N \to \infty$. This ensures that sampling probabilities do not vanish, unlike Euclidean ($L_2$) metrics where the required radius grows with $\sqrt{N}$.
• Complexity: This approach reduces search complexity from exponential $O((2L)^N)$ to linear $O(N \cdot K)$, enabling scalability to dimensions where $N > 100$.

2. Distance-Based Updates (DBU)

DBU addresses the gradient variance and instability issues by transforming policy optimization into a stable regression task.

• Target Construction: The algorithm perturbs the proto-action $\hat{a}$ to generate $M$ auxiliary candidates. It evaluates these candidates using the critic to obtain Q-values and constructs a target action $\bar{a}$ as a softmax-weighted average of these candidates. This acts as a denoising filter, mitigating critic overestimation and smoothing the loss landscape.
• Regression Loss: The actor is updated by minimizing the distance between the proto-action $\hat{a}$ and the target $\bar{a}$ (e.g., using Huber loss).
• Variance Independence: Theoretically, the gradient variance of DBU is independent of the action space cardinality $|A|$. The update depends only on the geometry of the relaxed action space and the fixed number of sampled candidates $M$, decoupling gradient noise from the size of the action space.

Unified Treatment of Hybrid Spaces

DGRL handles hybrid action spaces $A \subset \mathbb{Z}^N \times \mathbb{R}^M$ by outputting a joint proto-action $(\hat{a}_d, \hat{a}_c)$. Both SDN and DBU operate on the full vector simultaneously. This allows for joint optimization where discrete and continuous components inform each other through shared representation layers, avoiding the "regret floor" typical of hierarchical methods where high-level choices constrain low-level optimization.

Key Contributions

1. Algorithmic Framework: Introduction of DGRL, which combines SDN and DBU to enable efficient RL in spaces with up to $10^{20}$ actions.
2. Theoretical Guarantees:
   • Proof that Chebyshev-based sampling maintains a stable search volume as dimensionality increases (Proposition 4.1).
   • Proof that DBU's gradient variance is independent of action cardinality $|A|$ (Theorem 4.2).
   • Establishment of local value improvement guarantees in structured tasks under Lipschitz continuity assumptions (Proposition 4.5).
3. Scalability: Demonstration that DGRL scales linearly with dimensionality $N$ rather than exponentially with cardinality $|A|$, and generalizes naturally to irregularly structured and hybrid action spaces.

Experimental Results

The authors evaluated DGRL across twelve variations of four environments: 2D Mazes, Job Shop Scheduling, Joint Inventory Replenishment, and Recommender Systems. These included both structured (regular) and irregularly structured topologies, with action spaces ranging from $5^4$ to $343^{10}$.

• Performance: DGRL outperformed state-of-the-art benchmarks (including Wolpertinger, DNC, Cacla, and LAR) by up to 66% in discrete environments and 129% in hybrid environments.
• Robustness: Unlike DNC, which collapsed in high-dimensional irregular spaces, DGRL maintained stability and performance. It also showed significantly lower variance and faster convergence compared to DDPG-based baselines.
• Computational Efficiency: DGRL exhibited near-constant step times relative to action space size, whereas methods relying on lookup tables (Wolpertinger, LAR) became computationally prohibitive, and DNC's step times degraded with dimensionality.
• Ablation Studies: Results confirmed that both SDN (for volumetric exploration) and DBU (for stable regression updates) are essential; removing either component led to performance degradation or instability.

Significance and Claims

The paper claims that DGRL provides a foundational approach for metric-aware RL, suggesting that leveraging problem structure and distance-guided sampling can replace categorical representations in large-scale decision-making.

The authors assert that DGRL successfully bridges the scalability gap in RL by:

1. Decoupling gradient variance from action space cardinality.
2. Enabling volumetric exploration that is robust to irregular action space structures.
3. Facilitating joint optimization in hybrid spaces without the instability of hierarchical decomposition.

The work is presented as a solution to the "curse of cardinality," offering a computationally tractable alternative to exhaustive search and a more stable alternative to policy gradient methods in massive discrete and hybrid action spaces.