# Stochastic Q-learning for Large Discrete Action Spaces

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods.
- Builds on 37 of its 60 references that are in the map.
- First posted on arXiv 16 May 2024.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

## Builds on (most cited first, 30 of 37)

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Continuous control with deep reinforcement learning](https://mlsanity.com/paper/1509.02971/) (2015)
- [Playing Atari with Deep Reinforcement Learning](https://mlsanity.com/paper/1312.5602/) (2013)
- [Asynchronous Methods for Deep Reinforcement Learning](https://mlsanity.com/paper/1602.01783/) (2016)
- [Deep Reinforcement Learning with Double Q-learning](https://mlsanity.com/paper/1509.06461/) (2015)
- [OpenAI Gym](https://mlsanity.com/paper/1606.01540/) (2016)
- [QT-Opt: Scalable Deep Reinforcement Learning for Vision-Based Robotic Manipulation](https://mlsanity.com/paper/1806.10293/) (2018)
- [Reinforcement Learning for Combinatorial Optimization: A Survey](https://mlsanity.com/paper/2003.03600/) (2020)
- [FACMAC: Factored Multi-Agent Centralised Policy Gradients](https://mlsanity.com/paper/2003.06709/) (2020)
- [Applications of Deep Reinforcement Learning in Communications and Networking: A Survey](https://mlsanity.com/paper/1810.07862/) (2018)
- [Deep Reinforcement Learning in Large Discrete Action Spaces](https://mlsanity.com/paper/1512.07679/) (2015)
- [Maxmin Q-learning: Controlling the Estimation Bias of Q-learning](https://mlsanity.com/paper/2002.06487/) (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)
- [Discretizing Continuous Action Space for On-Policy Optimization](https://mlsanity.com/paper/1901.10500/) (2019)
- [Reinforcement Learning with Combinatorial Actions: An Application to Vehicle Routing](https://mlsanity.com/paper/2010.12001/) (2020)
- [Generating Adjacency-Constrained Subgoals in Hierarchical Reinforcement Learning](https://mlsanity.com/paper/2006.11485/) (2020)
- [DeepPool: Distributed Model-free Algorithm for Ride-sharing using Deep Reinforcement Learning](https://mlsanity.com/paper/1903.03882/) (2019)
- [Discrete Sequential Prediction of Continuous Actions for Deep RL](https://mlsanity.com/paper/1705.05035/) (2017)
- [Is Bang-Bang Control All You Need? Solving Continuous Control with Bernoulli Policies](https://mlsanity.com/paper/2111.02552/) (2021)
- [Deep Reinforcement Learning for Vision-Based Robotic Grasping: A Simulated Comparative Evaluation of Off-Policy Methods](https://mlsanity.com/paper/1802.10264/) (2018)
- [Q-Learning in enormous action spaces via amortized approximate maximization](https://mlsanity.com/paper/2001.08116/) (2020)
- [Growing Action Spaces](https://mlsanity.com/paper/1906.12266/) (2019)
- [The Natural Language of Actions](https://mlsanity.com/paper/1902.01119/) (2019)
- [Solving Continuous Control via Q-learning](https://mlsanity.com/paper/2210.12566/) (2022)
- [Randomized Greedy Learning for Non-monotone Stochastic Submodular Maximization Under Full-bandit Feedback](https://mlsanity.com/paper/2302.01324/) (2023)
- [Hybrid Multi-agent Deep Reinforcement Learning for Autonomous Mobility on Demand Systems](https://mlsanity.com/paper/2212.07313/) (2022)
- [Combinatorial Stochastic-Greedy Bandit](https://mlsanity.com/paper/2312.08057/) (2023)

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

- [Efficient Reinforcement Learning with Large Language Model Priors](https://mlsanity.com/paper/2410.07927/) (2024)
- [Every Call is Precious: Global Optimization of Black-Box Functions with Unknown Lipschitz Constants](https://mlsanity.com/paper/2502.04290/) (2025)
- [ACING: Actor-Critic for Instruction Learning in Black-Box LLMs](https://mlsanity.com/paper/2411.12736/) (2024)
- [Language Model Distillation: A Temporal Difference Imitation Learning Perspective](https://mlsanity.com/paper/2505.20335/) (2025)
- [ECPv2: Fast, Efficient, and Scalable Global Optimization of Lipschitz Functions](https://mlsanity.com/paper/2511.16575/) (2025)

## Abstract (arXiv)

In complex environments with large discrete action spaces, effective decision-making is critical in reinforcement learning (RL). Despite the widespread use of value-based RL approaches like Q-learning, they come with a computational burden, necessitating the maximization of a value function over all actions in each iteration. This burden becomes particularly challenging when addressing large-scale problems and using deep neural networks as function approximators. In this paper, we present stochastic value-based RL approaches which, in each iteration, as opposed to optimizing over the entire set of n actions, only consider a variable stochastic set of a sublinear number of actions, possibly as small as O(log(n)). The presented stochastic value-based RL methods include, among others, Stochastic Q-learning, StochDQN, and StochDDQN, all of which integrate this stochastic approach for both value-function updates and action selection. The theoretical convergence of Stochastic Q-learning is established, while an analysis of stochastic maximization is provided. Moreover, through empirical validation, we illustrate that the various proposed approaches outperform the baseline methods across diverse environments, including different control problems, achieving near-optimal average returns in significantly reduced time.