Research map / Reinforcement learning / Visual and representation RL
Exploring Large Action Sets with Hyperspherical Embeddings using von Mises-Fisher Sampling
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 von Mises-Fisher exploration (vMF-exp), which samples a state vector from a vMF distribution on the hypersphere and returns its nearest action embedding, and proves it asymptotically matches Boltzmann exploration's action probabilities while scaling to millions of actions.
Problem
Exploring large action sets in RL where actions are unit-norm hyperspherical embeddings: Boltzmann exploration is accurate but needs softmax over all actions (unscalable), while truncated versions restrict exploration radius.
Approach
Sample a state embedding from a von Mises-Fisher distribution centred on the state vector and select its nearest neighbour among action embeddings; this induces Voronoi-cell sampling probabilities that asymptotically equal Boltzmann probabilities with cost independent of the number of actions.
Key results
- Proves that the ratio of B-exp to vMF-exp exploration probabilities tends to 1 as the number of actions n grows (uniform hypersphere assumption).
- Monte Carlo results (8 million repetitions) show B-exp and the approximation P0 are indistinguishable over the tested n, and vMF-exp matches B-exp for small d.
- vMF-exp was deployed on Deezer's 'Mixes Inspired By' recommender with a positive worldwide online A/B test and few-millisecond sampling latency.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| replace B-exp with vMF-exp for action exploration | RL with hyperspherical action embeddings · Uniform hyperspherical action embeddings as the action set grows | exploration probability: lim_{n→+∞} P_B-exp(a) / P_vMF-exp(a) = 1 | No clear effect |
| use vMF-exp instead of B-exp | RL with large action sets · Action sets with millions of candidates | scalability | Helped |
| use vMF-exp instead of B-exp with the same κ and d | RL with high-dimensional hyperspherical embeddings · High-dimensional embeddings with positive similarity between V and A | probability of exploring action a | Hurt |
| use vMF-exp instead of B-exp with the same κ and d | RL with high-dimensional hyperspherical embeddings · High-dimensional embeddings with A opposite to V | probability of exploring action a | Helped |
Surprising findings
- For large dimension d, vMF-exp explores similar actions less and dissimilar actions more than B-exp with the same kappa, so it diverges from B-exp in high dimensions.
Limitations
- Theoretical guarantees hold only for i.i.d. uniform hypersphere embeddings; clustered real embeddings not covered.
- Assumes exact nearest-neighbour retrieval; ANN errors not analysed.
- Second-order term may matter for large kappa and is left to future work.
Experimental setup
Datasets: GloVe word embeddings (one million vectors)
Benchmarks: Monte Carlo simulations of exploration probabilities GloVe one-million-vector dataset Deezer online A/B test
Metrics: sampling probability of an action scalability latency A/B test engagement
Baselines: Boltzmann exploration truncated Boltzmann exploration epsilon-greedy uniform random exploration
Builds on: Boltzmann exploration Wolpertinger architecture von Mises-Fisher distribution
Closest papers by meaning
- Learning Action Representations for Reinforcement Learning (ICML 2019 · similarity 0.86)
- MaxInfoRL: Boosting exploration in reinforcement learning through information gain maximization (ICLR 2025 · similarity 0.85)
- Towards Principled Representation Learning from Videos for Reinforcement Learning (ICLR 2024 · similarity 0.84)
- Efficient Off-Policy Learning for High-Dimensional Action Spaces (ICLR 2025 · similarity 0.84)
- Action abstractions for amortized sampling (ICLR 2025 · similarity 0.84)
- XLand-100B: A Large-Scale Multi-Task Dataset for In-Context Reinforcement Learning (ICLR 2025 · similarity 0.84)
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.