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 papers