Breaking the Grid: Distance-Guided Reinforcement Learning in Large Discrete Action Spaces
Organizations: Technical University of Munich · University of Twente
Abstract
Reinforcement Learning (RL) is increasingly applied to large-scale decision-making problems like logistics, scheduling, and recommender systems, but existing algorithms struggle with the curse of dimensionality in such large discrete action spaces. We propose Distance-Guided Reinforcement Learning (DGRL), combining Sampled Dynamic Neighborhoods and Distance-Based Updates to enable efficient RL in problems with up to actions. Unlike prior methods, DGRL performs stochastic volumetric exploration and transforms policy optimization into a stable regression task, decoupling gradient variance from action space cardinality. On structured tasks, DGRL provably guarantees local value improvement. DGRL naturally handles action spaces without regular semantic structure and hybrid continuous-discrete action spaces. We demonstrate performance improvements of up to 66% against state-of-the-art benchmarks across regularly and irregularly structured environments, while simultaneously improving convergence speed and computational complexity.
Figures & tables
| DGRL | DNC (SA) | Cacla | Wolp. | LAR | |
|---|---|---|---|---|---|
| 3.3 | 12.8 | 0.1 | 1.1 | 0.2 | |
| 3.4 | 19.4 | 0.1 | - | - | |
| 3.4 | 33.6 | 0.1 | - | - | |
| 3.2 | 80.2 | 0.1 | - | - |
Appendix figures & tables13 assets
Supplementary material from the paper’s appendix.
Appendix
| Feature | Wolpertinger | DNC (SA) | DGRL (SDN + DBU) |
|---|---|---|---|
| Search Strategy | Local ( -NN) | Local (SA) | Local (Sampling) |
| Metric Space | Euclidean | Grid-based | Any ( preferred) |
| Gradient Logic | DDPG | Policy Gradient | Dist. Regression |
| Complexity | (preparation) | (parallel) | |
| Sampling budget | (similar to ) | ||
| Hybrid Support | No | No | Joint Optimization |
| Chosen values | ||||||
| Hyperparameters | Set of values | Maze, (S) | Maze, (I) | Maze, (S) | Maze, (I) | |
| Overall | Actor nodes/layer | |||||
| Critic nodes/layer | ||||||
| Actor lr | ||||||
| Critic lr | ||||||
| DGRL | Max distance | |||||
| Chosen values | ||||||
| Hyperparameters | Set of values | Job Shop | Inventory | Rcm., | Rcm., | |
| Overall | Actor nodes/layer | |||||
| Critic nodes/layer | ||||||
| Actor lr | ||||||
| Critic lr | ||||||
| DGRL | Max distance | |||||
| Chosen values | ||||||
| Hyperparameters | Set of values | Maze, (S) | Maze, , (S) | Rcm., | Rcm., | |
| Overall | Actor nodes/layer | |||||
| Critic nodes/layer | ||||||
| Actor lr | ||||||
| Critic lr | ||||||
| DGRL | Max distance | |||||
| Algorithm | Hyperparameters tuned | Full grid | Evaluated |
|---|---|---|---|
| DGRL | Standard deviations , | 16 | 16 |
| DNC (SA/greedy) | SA search steps, cooling, acceptance cooling, | 64 | 24 |
| Wolpertinger | , | 12 | 12 |
| LAR/HyAR | buffer size, VAR lr , | 24 | 12 |
| Maze, , structured | Maze, , irregularly structured | |||||
|---|---|---|---|---|---|---|
| Modification | DGRL | DNC (SA) | Cacla | DGRL | DNC (SA) | Cacla |
| None (baseline) | 9.58 | 9.57 | -4.95 | 9.50 | 9.50 | -4.95 |
| More actuators ( ) | 8.28 | -4.45 | -4.95 | -4.95 | -4.95 | -4.95 |
| More actuators ( ) | -4.48 | -4.95 | -4.95 | -4.95 | -4.95 | -4.95 |
| More actuators ( ) | -4.95 | -4.95 | -4.95 | -4.95 | -4.95 | -4.95 |
| More actuators ( ) | -4.95 | -4.95 | -4.95 | -4.95 | -4.95 | -4.95 |
| Algorithm | Mean | Median | Std. | vs. DNC (%) | vs. Cacla (%) | Num Seeds |
| Maze, , structured, discrete | ||||||
| DGRL (SDN, DBU) | 9.67 | 9.67 | 0.01 | 0 | 14390 | 10 |
| DNC (SA), A2C | 9.74 | 9.75 | 0.03 | 0 | 14507 | 10 |
| DNC (greedy), A2C | 9.35 | 9.36 | 0.17 | -3 | 13927 | 10 |
| Wolpertinger, DDPG | 8.24 | 8.91 | 1.29 | -8 | 13248 | 10 |
| Wolpertinger, DBU | 8.31 | 8.63 | 1.13 | -11 | 12822 | 10 |
| Algorithm | Mean | Median | Std. | vs. DNC (%) | vs. Cacla (%) | Num Seeds |
| Recommender, , discrete | ||||||
| DGRL (SDN, DBU) | 2009.88 | 2006.62 | 42.18 | 31 | 60 | 10 |
| DNC (SA), A2C | 1534.94 | 1524.49 | 265.15 | 0 | 21 | 10 |
| DNC (greedy), A2C | 1587.59 | 1637.68 | 273.37 | 7 | 30 | 10 |
| Wolpertinger, DDPG | 460.38 | 444.65 | 29.42 | -70 | -64 | 10 |
| Cacla, A2C | 1370.89 | 1253.92 | 320.12 | -17 | 0 | 10 |
| Algorithm | Mean | Median | Std. | vs. H-DNC (%) | vs. H-Cacla (%) | Num Seeds |
| Maze, , hybrid | ||||||
| DGRL (SDN, DBU) | 9.71 | 9.71 | 0.01 | 0 | 0 | 10 |
| Hybrid DNC, H-A2C | 9.78 | 9.79 | 0.02 | 0 | 1 | 10 |
| Hybrid Cacla, DDPG | 9.57 | 9.66 | 0.17 | -1 | 0 | 10 |
| HyAR, A2C | 0.27 | 0.25 | 0.23 | -97 | -97 | 10 |
| Maze, , hybrid | ||||||
Reinforcement Learning
Reinforcement learning studies how agents learn sequential decisions from rewards and interaction, balancing exploration, performance, safety, and adaptation.
See all 1,835 papersFLAG: Flow Policy MaxEnt-RL by Latent Augmented Guidance
When to Stop Reusing: Dynamic Gradient Gating for Sample-Efficient RLVR
lm\_head weight change, while intermediate layers remain stable. Empirically, we verify that DWD emerges consistently across diverse LLMs and tasks. Theoretically, we prove that (i) harmful gradients concentrate at the lm\_head while intermediate layers are structurally attenuated, and (ii) the lm\_head gradient norm lower-bounds the policy divergence. These results establish the lm\_head gradient norm as a principled, real-time signal of catastrophic policy shift. Guided by this insight, we propose Dynamic Gradient Gating (DGG), a lightweight intervention that monitors the lm\_head gradient norm in real time and intercepts harmful gradients before they corrupt the optimizer. DGG consistently matches or exceeds the standard single-use baseline, achieving up to sample efficiency and wall-clock speedup across math, ALFWorld, WebShop, and search-augmented QA tasks.