Breaking the Grid: Distance-Guided Reinforcement Learning in Large Discrete Action Spaces

About

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 $10^{20}$ 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 generalizes to 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.

Heiko Hoppe, Fabian Akkerman, Wouter van Heeswijk, Maximilian Schiffer · 2026

Related benchmarks

Task	Dataset	Result
Reinforcement Learning	Maze 17^10 structured discrete	Mean Score9.61	9
Reinforcement Learning	Maze 5^4 unstructured discrete	Mean Performance9.57	7
Reinforcement Learning	Maze 5^4 structured discrete	Mean Score9.67	7
Reinforcement Learning	Recommender discrete	Mean Score2009.88	6
Reinforcement Learning	Maze 17^10 unstructured discrete	Mean Score9.25	4
Reinforcement Learning	Recommender 343^10 discrete	Mean Return1937.61	4
Reinforcement Learning	Joint Replenishment 67^20	Mean Return-3810.73	4
Reinforcement Learning	Job Shop Scheduling 10^10	Mean Completion Time4027.51	4
Reinforcement Learning	Maze 17^10 hybrid	Mean Score9.72	3
Reinforcement Learning	Recommender hybrid 343	Mean Score1579.64	3