Research map / Reinforcement learning / Visual and representation RL
Dynamic Neighborhood Construction for Structured Large Discrete Action Spaces
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes Dynamic Neighborhood Construction (DNC), an actor-critic pipeline that maps continuous actor outputs to discrete structured actions by simulated-annealing search over perturbed neighborhoods scored by the critic, scaling to action spaces up to 10^73.
Problem
Reinforcement learning with structured large discrete action spaces (SLDAS) whose size grows to billions or beyond, where enumerating or storing all actions (as in kNN, MinMax, LAR) is infeasible.
Approach
Convert the actor's continuous output into a discrete base action by rounding, then generate perturbed discrete neighbors dynamically and select among them with a simulated-annealing search guided by critic Q-values, without enumerating or storing the action space.
Key results
- DNC scales to structured action spaces of up to 10^73 actions, where kNN and LAR fail due to memory and VAC fails already at about 2^12 actions.
- In the inventory environment only DNC learns a performant policy; VAC, kNN and LAR run out of memory, while MinMax and DNC w/o SA converge to less performant policies.
- In the maze and job-shop environments DNC matches or outperforms state-of-the-art benchmarks, with DNC outperforming DNC w/o SA and MinMax in job-shop scheduling.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use DNC instead of MinMax | DNC actor-critic pipeline · Maze | test return | No clear effect |
| Use neighborhood-based action selection instead of MinMax | Maze with teleporting tile · Maze with teleporting tile | test return | Helped |
| Add simulated annealing to DNC (ablation) | DNC · Joint inventory replenishment | test return | Helped |
| Add simulated annealing to DNC (ablation) | DNC · Job-shop scheduling | test return | Helped |
| Evaluate multiple neighbors instead of using only the nearest-neighbor mapping (ablation) | DNC w/o SA · Job-shop scheduling | test return | Helped |
| Use DNC instead of MinMax | DNC actor-critic pipeline · Very large structured action spaces | learning performant policies | Helped |
| Use DNC rather than methods requiring an enumerable action space | DNC actor-critic pipeline · Action spaces up to 10^73 actions | scalability: 10^73 | Helped |
| Use DNC instead of kNN | DNC actor-critic pipeline · Action spaces with |A| > 10^9 | learning performant policies | Helped |
Surprising findings
- In the simple maze environment DNC does not outperform MinMax, and the authors note the benefit of considering neighbors is limited there.
Limitations
- Neighborhood exploration is not exhaustive, so potentially better neighbors may be missed; the policy gradient is only approximate because the composed mapping is not differentiable.
- Performance gains are limited in simple environments with smooth Q-value distributions.
- Infeasible actions and constraints are not handled.
Experimental setup
Datasets: maze environment joint inventory replenishment environment job-shop scheduling environment
Benchmarks: maze maze with teleporting tile joint inventory replenishment job-shop scheduling
Metrics: expected test return step time memory usage
Baselines: VAC MinMax kNN mapping LAR DNC w/o SA MILP
Builds on: actor-critic simulated annealing MinMax mapping k-nearest neighbor action mapping learned action representation
Closest papers by meaning
- BraVE: Offline Reinforcement Learning for Discrete Combinatorial Action Spaces (NeurIPS 2025 · similarity 0.87)
- Achieving Sample and Computational Efficient Reinforcement Learning by Action Space Reduction via Grouping (ICLR 2024 · similarity 0.86)
- Multiagent Gumbel MuZero: Efficient Planning in Combinatorial Action Spaces (AAAI 2024 · similarity 0.85)
- Flow Matching for Offline Reinforcement Learning with Discrete Actions (NeurIPS 2026 · similarity 0.85)
- In-Context Reinforcement Learning for Variable Action Spaces (ICML 2024 · similarity 0.85)
- Scalable Decision-Making in Stochastic Environments through Learned Temporal Abstraction (ICLR 2025 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.