# Dynamic Neighborhood Construction for Structured Large Discrete Action Spaces

arXiv: https://arxiv.org/abs/2305.19891 · HTML: https://mlsanity.com/paper/2305.19891/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 52 references that are in the map.
- First posted on arXiv 31 May 2023.

## Builds on (most cited first, 24 of 24)

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Playing Atari with Deep Reinforcement Learning](https://mlsanity.com/paper/1312.5602/) (2013)
- [FACMAC: Factored Multi-Agent Centralised Policy Gradients](https://mlsanity.com/paper/2003.06709/) (2020)
- [Deep Reinforcement Learning in Large Discrete Action Spaces](https://mlsanity.com/paper/1512.07679/) (2015)
- [Learning to Dispatch for Job Shop Scheduling via Deep Reinforcement Learning](https://mlsanity.com/paper/2010.12367/) (2020)
- [Action Branching Architectures for Deep Reinforcement Learning](https://mlsanity.com/paper/1711.08946/) (2017)
- [Deep Reinforcement Learning with a Natural Language Action Space](https://mlsanity.com/paper/1511.04636/) (2015)
- [Learning Collaborative Policies to Solve NP-hard Routing Problems](https://mlsanity.com/paper/2110.13987/) (2021)
- [Learn What Not to Learn: Action Elimination with Deep Reinforcement Learning](https://mlsanity.com/paper/1809.02121/) (2018)
- [Learning Action Representations for Reinforcement Learning](https://mlsanity.com/paper/1902.00183/) (2019)
- [Generating Adjacency-Constrained Subgoals in Hierarchical Reinforcement Learning](https://mlsanity.com/paper/2006.11485/) (2020)
- [Learning To Navigate The Synthetically Accessible Chemical Space Using Reinforcement Learning](https://mlsanity.com/paper/2004.12485/) (2020)
- [Continuous-Discrete Reinforcement Learning for Hybrid Control in Robotics](https://mlsanity.com/paper/2001.00449/) (2020)
- [Leveraging Factored Action Spaces for Efficient Offline Reinforcement Learning in Healthcare](https://mlsanity.com/paper/2305.01738/) (2023)
- [Dynamics-aware Embeddings](https://mlsanity.com/paper/1908.09357/) (2019)
- [The Natural Language of Actions](https://mlsanity.com/paper/1902.01119/) (2019)
- [Generalization to New Actions in Reinforcement Learning](https://mlsanity.com/paper/2011.01928/) (2020)
- [Hybrid Multi-agent Deep Reinforcement Learning for Autonomous Mobility on Demand Systems](https://mlsanity.com/paper/2212.07313/) (2022)
- [Lifelong Learning with a Changing Action Set](https://mlsanity.com/paper/1906.01770/) (2019)
- [Learning to Factor Policies and Action-Value Functions: Factored Action Space Representations for Deep Reinforcement learning](https://mlsanity.com/paper/1705.07269/) (2017)
- [Reinforcement Learning in Factored Action Spaces using Tensor Decompositions](https://mlsanity.com/paper/2110.14538/) (2021)
- [Jointly-Learned State-Action Embedding for Efficient Reinforcement Learning](https://mlsanity.com/paper/2010.04444/) (2020)
- [A Deep Reinforcement Learning Approach for Traffic Signal Control Optimization](https://mlsanity.com/paper/2107.06115/) (2021)

## Built on by (most cited first, 4 of 4)

- [Global Rewards in Multi-Agent Deep Reinforcement Learning for Autonomous Mobility on Demand Systems](https://mlsanity.com/paper/2312.08884/) (2023)
- [Combinatorial Optimization Augmented Machine Learning](https://mlsanity.com/paper/2601.10583/) (2026)
- [Language Model Distillation: A Temporal Difference Imitation Learning Perspective](https://mlsanity.com/paper/2505.20335/) (2025)
- [Breaking the Grid: Distance-Guided Reinforcement Learning in Large Discrete Action Spaces](https://mlsanity.com/paper/2602.08616/) (2026)

## Abstract (arXiv)

Large discrete action spaces (LDAS) remain a central challenge in reinforcement learning. Existing solution approaches can handle unstructured LDAS with up to a few million actions. However, many real-world applications in logistics, production, and transportation systems have combinatorial action spaces, whose size grows well beyond millions of actions, even on small instances. Fortunately, such action spaces exhibit structure, e.g., equally spaced discrete resource units. With this work, we focus on handling structured LDAS (SLDAS) with sizes that cannot be handled by current benchmarks: we propose Dynamic Neighborhood Construction (DNC), a novel exploitation paradigm for SLDAS. We present a scalable neighborhood exploration heuristic that utilizes this paradigm and efficiently explores the discrete neighborhood around the continuous proxy action in structured action spaces with up to 1073 actions. We demonstrate the performance of our method by benchmarking it against three state-of-the-art approaches designed for large discrete action spaces across two distinct environments. Our results show that DNC matches or outperforms state-of-the-art approaches while being computationally more efficient. Furthermore, our method scales to action spaces that so far remained computationally intractable for existing methodologies.