Research map / Reinforcement learning / Policy gradient and actor-critic
Stochastic Q-learning for 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 stochastic maximization (StochMax/StochArgmax over sublinear random action subsets plus memory) and plugs it into Q-learning, Double Q-learning, Sarsa, DQN and DDQN, proving Stochastic Q-learning convergence and showing wall-time speedups on large discrete action spaces.
Problem
Value-based RL with large discrete action spaces requires a max/argmax over all n actions at every action selection and update, costing O(n) per step, which is impractical for large n and deep Q-networks.
Approach
Replace exact max/argmax with a stochastic maximum over a random subset of about ceil(log n) actions plus a small memory of recently exploited actions, giving logarithmic per-step cost while still converging (for memoryless updates) to a well-defined Q* under the sampling distribution.
Key results
- On InvertedPendulum-v4 with 1000 actions, stochastic methods took about 0.003 s per step versus 0.18 s for non-stochastic, roughly 60x faster.
- On HalfCheetah-v4 with 4096 actions, one (D)DQN step takes 0.6 s (about 17 hours for 100k steps) while Stoch(D)DQN needs about 2 hours.
- Stochastic Q-learning outperforms the compared tabular methods on FrozenLake-v1 in cumulative reward; StochDDQN nearly reaches optimal return on InvertedPendulum-v4 while DDQN struggles.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace exact maximization with stochastic maximization | Stoch(D)DQN vs. (D)DQN · InvertedPendulum-v4, 1000 actions | time per step: 0.18 seconds -> around 0.003 seconds per step; 60 times faster | Helped |
| Replace exact maximization with stochastic maximization | Stoch(D)DQN vs. (D)DQN · HalfCheetah-v4, 4096 actions, 100,000 steps | runtime: around 17 hours -> around 2 hours | Helped |
| Replace exact maximization with stochastic maximization | Stochastic Q-learning · FrozenLake-v1 | cumulative rewards | Helped |
| Replace exact maximization with stochastic maximization | Stochastic Q-learning, Stochastic Double Q-learning, and Stochastic Sarsa · CliffWalking-v0 | steps to reach optimal policy | No clear effect |
| Replace exact maximization with stochastic maximization | Stochastic Q-learning, Stochastic Double Q-learning, and Stochastic Sarsa · Generated MDP, 256 actions | steps to reach optimal policy | No clear effect |
| Replace exact maximization with stochastic maximization | StochDQN vs. DQN · InvertedPendulum-v4 | steps to optimal average return | Helped |
| Replace exact maximization with stochastic maximization | StochDDQN vs. DDQN · InvertedPendulum-v4 | average return | Helped |
| Use stochastic maximization in DQN variants | StochDQN and StochDDQN · InvertedPendulum-v4 | average return | Helped |
| Use stochastic maximization in DQN variants | StochDQN and StochDDQN · HalfCheetah-v4, 4096 actions | average return | No clear effect |
| Use stochastic maximization in DQN variants | DQN methods · HalfCheetah-v4, 4096 actions | average return | Helped |
Surprising findings
- DDQN underperforms on InvertedPendulum-v4 while StochDDQN nearly reaches optimal return, which the authors attribute to stochasticity.
- Stochastic variants sometimes yield higher reward than their exact counterparts, not only lower wall time.
Limitations
- Memoryless convergence result holds for a sampling distribution that changes the target Q*; exact optimality only recovered as sample size grows to all actions.
- Stochastic maximization is not guaranteed to find the exact maximizer; the lower bound on success probability is only about ceil(log n)/n.
- Experiments are limited to small discrete tasks and discretized MuJoCo control, with no comparison against other large-action methods.
Experimental setup
Datasets: CliffWalking-v0 FrozenLake-v1 InvertedPendulum-v4 HalfCheetah-v4
Benchmarks: CliffWalking-v0 FrozenLake-v1 InvertedPendulum-v4 HalfCheetah-v4
Metrics: average return wall time per step omega ratio (stochmax/max) beta estimation error
Baselines: Q-learning Double Q-learning Sarsa DQN DDQN DDPG A2C PPO
Builds on: Q-learning Double Q-learning DQN Double DQN Sarsa
Closest papers by meaning
- The Effective Horizon Explains Deep RL Performance in Stochastic Environments (ICLR 2024 · similarity 0.89)
- Actor-Free Continuous Control via Structurally Maximizable Q-Functions (NeurIPS 2025 · similarity 0.88)
- Long-Horizon Q-Learning: Accurate Value Learning via n-Step Inequalities (NeurIPS 2026 · similarity 0.88)
- Enhancing Value Function Estimation through First-Order State-Action Dynamics in Offline Reinforcement Learning (ICML 2024 · similarity 0.88)
- Q-SFT: Q-Learning for Language Models via Supervised Fine-Tuning (ICLR 2025 · similarity 0.88)
- Inverting the Bellman Equation: From $Q$-Values to World Models (NeurIPS 2026 · similarity 0.88)
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.