Exploring Large Action Sets with Hyperspherical Embeddings using von Mises-Fisher Sampling
Authors: Walid Bendada
Guillaume Salha-Galvan
Romain Hennequin
Théo Bontempelli
Thomas Bouabça
Tristan Cazenave
Venue: ICML 2025 poster (2025)
Keywords: Efficient Sampling
Probability Theory
Large-Scale
Embeddings
Real-World Application
Reinforcement Learning
Primary area: probabilistic_methods->monte_carlo_and_sampling_methods
TL;DR: When action sets are too large, it is not possible to sample from a softmax distribution in real-time ; we propose a new scalable approach to sample actions represented by embeddings and mathematically prove its ties to Boltzmann exploration.

Abstract: This paper introduces von Mises-Fisher exploration (vMF-exp), a scalable method for exploring large action sets in reinforcement learning problems where hyperspherical embedding vectors represent these actions. vMF-exp involves initially sampling a state embedding representation using a von Mises-Fisher distribution, then exploring this representation's nearest neighbors, which scales to virtually unlimited numbers of candidate actions.
We show that, under theoretical assumptions, vMF-exp asymptotically maintains the same probability of exploring each action as Boltzmann Exploration (B-exp), a popular alternative that, nonetheless, suffers from scalability issues as it requires computing softmax values for each action.
Consequently, vMF-exp serves as a scalable alternative to B-exp for exploring large action sets with hyperspherical embeddings. 
Experiments on simulated data, real-world public data, and the successful large-scale deployment of vMF-exp on the recommender system of a global music streaming service empirically validate the key properties of the proposed method.

Exploring Large Action Sets with Hyperspherical Embeddings using von Mises-Fisher Sampling
Walid Bendada 12 Guillaume Salha-Galvan
Romain Hennequin Tristan Cazenave"
Théo Bontempelli' Thomas Bouabça
Abstract
2002; Slivkins et al., 2019; Sutton & Barto, 2018; Tang et al., 2017). However, as the set of actions to explore grows larger, the exploration process becomes increasingly challenging. Indeed, large action sets can lead to higher computational costs, longer learning times, and the risk of inadequate ex- ploration and suboptimal policy development (Amin et al., 2021; Chen al., 2021; Dulac-Arold et al., 2015; Lillicrap et al., 2016; Sutton & Barto, 2018; Tomasi et al., 2023).
This paper introduces von Mises-Fisher explo- ration (vMF-exp), scalable method for explor- ing large action sets in reinforcement learning problems where hyperspherical embedding vec- tors represent these actions. vMF-exp involves initially sampling a state embedding representa- tion using von Mises-Fisher distribution, then exploring this representation's 's nearest neighbors, which scales to virtually unlimited numbers of candidate actions. We show that, under theoretical assumptions, vMF-exp asymptotically maintains the same probability of exploring each action as Boltzmann Exploration (B-exp), a popular alter- native that, nonetheless, suffers from scalability issues it requires computing softmax values for each action. Consequently, vMF-exp serves as scalable alternative to B-exp for exploring large action sets with hyperspherical embeddings. Experiments on simulated data, real-world public data, and the successful large-scale deployment of vMF-exp on the recommender system of a global music streaming service empirically validate the key properties of the proposed method.
As an illustration, consider a recommender system on a music streaming service like Apple Music or Spotify, curat- ing playlists of songs "inspired by" an initial selection to help users discover music (Bendada al., 2023a). In prac- tice, these services often generate such playlists all at once, using efficient nearest neighbor search systems (Johnson et al., 2019; Li et al., 2019) to retrieve songs most similar to the initial one, in a song embedding vector space learned using collaborative filtering or content-based methods (Ben- dada et al., 2023a;b; Bontempelli et al., 2022; Jacobson et al., 2016; Schedl al., 2018; Zamani et al., 2019). AI- ternatively, one could formalize this task as an RL prob- lem (Tomasi et al., 2023), where the recommender system (i.e., the agent) would adaptively select the next song to recommend (i.e., the next action) based on user feedback on previously recommended songs (i.e., the rewards, such as likes or skips). Using an RL approach instead of generating the playlist once would have the advantage of dynamically learning from user feedback to identify the best recommen- dations (Afsar al., 2022: Tomasi et al., 2023). However, music streaming services offer access to large catalogs with several millions of songs (Bendada et al., 2020; Jacobson et al., 2016; Schedl et al., 2018). Therefore, the agent would need to consider millions of possible actions for exploration, increasing the complexity of this task.
1. Introduction
Exploration is a fundamental component of the reinforce- ment learning (RL) paradigm (Amin et al., 2021; McFar- lane, 2018; Sutton & Barto, 2018). It allows RL agents to gather valuable information about their environment and identify optimal actions that maximize rewards (Amin et al., 2021; Chiappa et al., 2023; Dulac-Amold et al., 2015; Jin et al., 2020; Ladosz et al., 2022; McFarlane, 2018; Reynolds,
In particular, Boltzmann Exploration (B-exp) (Cesa-Bianchi et al., 2017; Sutton & Barto, 2018), one of the prevalent exploration strategies to sample actions based embed- ding similarities, would become practically intractable as it would require computing softmax values over millions of elements (see Section 2). Furthermore, in large action sets, many actions are often irrelevant; in our example, most songs would constitute poor recommendations (Tomasi
'Deezer Research, Paris, France. LLAMSADE. Université Paris Dauphine, PSL, Paris, France." 'SPEIT, Shanghai Jiao Tong University, Shanghai, China. Correspondence to: Walid Bendada <bendadaw @ goai..com>.
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Exploring Large Action Sets with Hyperspherical Embeddings using von Miscs-Fisher Sampling
al., 2023). Therefore, random exploration methods like e- greedy (Dann et al., 2022; Sutton & Barto, 2018), although more efficient than B B-exp, would also be unsuitable for pro- duction use. Since these methods ignore song similarities, each song, including inappropriate ones, would have an equal chance of being selected for exploration. This could result in negative user feedback and a poor perception of the service (Tomasi al., 2023). Lastly, deterministic explo- ration strategies would also be ineffective. Systems serving millions of users often rely on batch RL (Lange et al., 2012) since updating models after every trajectory is impractical. Batch RL, unlike on-policy learning, requires exploring ac- tions non-deterministically given a state, and deterministic exploration would result in redundant trajectories and slow convergence (Bendada et al., 2020).
of actions represented by hyperspherical embedding vectors. vMF-exp involves initially sampling state embedding vector on the unit hypersphere using von Mises-Fisher distribution (Fisher, 1953), then explor- ing the approximate nearest neighbors of this repre- sentation. This strategy effectively scales to large sets with millions of candidate actions to explore.
We provide comprehensive mathematical analysis of the behavior of vMF-exp, demonstrating that it ex- hibits desirable properties for effective exploration in large-scale RL problems. Notably, vMF-exp does not restrict exploration to a specific neighborhood and ef- fectively preserves order while leveraging information from embedding vectors to assess action relevance.
In summary, exploration remains challenging in RL prob- lems characterized by large action sets and where account- ing for embedding similarities is crucial, like our recom- mendation example. Overall, although a growing body of scientific research has been dedicated to adapting RL models for recommendation (see, e.g., the survey by Afsar et al. (2022)), evidence of RL adoption in commercial rec- ommender systems exists but remains limited (Chen al., 2019; 2021; 2022; Tomasi et al., 2023). The few existing solutions typically settle for a workaround by using trun- cated version of B-exp (TB-exp). In TB-exp, a small subset of candidate actions is first selected, c.g., using approximate nearest neighbor search (a framework sometimes referred to as the Wolpertinger architecture (Dulac-Arnold et al., 2015)). Softmax values candidates only (Chen et al., 2019; 2021; 2022). YouTube, for instance, employs this technique for video recommen- dation (Chen et al., 2019). TB-exp allows for exploration in the close embedding neighborhood of a given state; how- ever, restricts the number of candidate actions based on technical considerations rather than optimal convergence properties. Although exploring beyond this restricted neigh- borhood might be beneficial, finding the best way to do in large-scale settings remains open research question.
We also show that, under some theoretical assumptions, vMF-exp asymptotically maintains the same proba- bility of exploring each action as the popular B-exp method while overcoming its scalability issues. This positions vMF-exp as scalable alternative to B-exp.
The primary objective of this paper is the introduction and mathematical analysis of the theoretical properties of vMF-exp. Nonetheless, a complement to this analysis, we also report empirical validations of the method, including experiments on simulated data, on real-world publicly available data, and a discussion of the recent and successful deployment of vMF-exp on a global music streaming service to recommend music to millions of users daily. These experiments validate the key properties of the proposed method and its potential.
then computed among those
We publicly release a Python implementation of vMF-exp on GitHub to enable reproducibility of our experiments and to encourage future use of the method: https: https://github. /ttp///ggttt..t/te wttitttb..oooooeeeee deneee/ vMF-exploration
The remainder of this paper is organized as follows. Sec- tion 2 formalizes the problem. Section 3 introduces vMF. exp, Section 4 details our theoretical analysis, Section 5 discusses our experiments, and Section 6 concludes.
In this paper', we propose to address this important question with a focus on its theoretical foundations. Our work ex- amines the specific setting where actions are represented by embedding vectors with unit Euclidean norm, i.c. vectors lying on a unit hypersphere. As detailed in Section 2, this setting aligns with many real-world applications. Specifi- cally, our contributions in this paper are as follows:
2. Preliminaries
We begin this section by formally introducing the problem addressed in this paper, followed by an explanation of the limitations of existing and popular RL exploration strategies.
We present von Mises-Fisher exploration (vMF-exp), a scalable sampling method for exploring large sets
2.1. Problem Formulation
Notation Throughout this paper, we consider an RL agent sequentially selecting actions within a set of E N* actions:
Parrt of the content published in this ICML 2025 conference paper were previously presented at two non-avchival workshops: ICML. 2024 ARLET (Bendada et al., 2024) and ICLR 2025 FPI (Bendada et al., 2025).
In = (1, 2.....n).
(1)
2

---

Exploring Large Action Sets with Hyperspherical Embeddings using von Mises-Fisher Sampling
Each action i E In is represented by a distinct low- dimensional vectorial representation X; E Rd, i.e., by embedding vector simply an embedding", for some fixed dimension d E N with d' 2 2 and d << n. Addition- ally, we assume all vectors have a unit Euclidean norm, i... ||xxi|22 = 1, Vi E In They form a set of embeddings noted Xx = {Xi) E (S*-1)", where Sd-1 is the d-dimensional unit hypersphere (Fisher, 1953):
Alternatively, it may rely on an exploration strategy select another In element. Formally, an exploration strategy P is policy function (Sutton & Barto, 2018) that, given V, selects each action i E In with a probability P(i V) E [0, 1].
Objective Our goal in this paper is to develop a suitable exploration strategy for our specific setting, where hyper- spherical embedding vectors represent actions, and the num- ber of actions can reach millions. Precisely, we aim to obtain exploration scheme meeting the following properties:
sa1 = fz E R ||ا|| = }
Scalability (P1): we consider an exploration scalable if the time required to sample actions given a vector V is at most the time needed for the ANN engine to retrieve the nearest neighbor, which is typically achieved in a sublinear time complexity with respect to n. Scalability is a mandatory requirement for exploring large action sets with millions of elements.
We also assume the availability of an approximate nearest neighbor (ANN) (Johnson et al., 2019; et al., 2019) search engine. Using this engine, for any vector V E 8d-1, the nearest neighbor of V among X, in terms of inner prod- uct similarity (equal to the cosine similarity, for unit vec- tors (Tan et al., 2016)), called Xtz. can be retrieved in a sublinear time complexity with respect to n. Although ANN engines are parameterized based on a trade-off between effi- ciency and accuracy, we make the simplifying assumption that x is the actual nearest neighbor of V. which we later discuss in Section 4.3. Formally:
Unrestricted radius (P2): Radius(P | V) is the num- ber of actions with a non-zero probability of being explored given a state V. While exploring actions too far from V might be suboptimal (c.g., resulting in poor recommendations) it is crucial that exploration is not restricted to a specific radius by construction. Such a restriction could prevent the agent from exploring relevant actions that lie beyond this radius. An un- restricted radius ensures that the exploration strategy remains flexible and capable of adapting various con- texts, allowing for the exploration of relevant actions regardless of their embedding position.
V = arg max X,).)
SE
Returning to the illustrative example of Section 1, Xr would represent embeddings associated with each song of the cat- alog In of the music streaming service. In this case, n would be on the order of several millions (Bendada et al., 2020; Briand et al., 2021; Jacobson et al., 2016). The RL agent would be the recommender system sequentially rec- ommending these songs to users. Normalizing embeddings is common practice in both academic and industrial rec- ommender systems (Afchar et al., 2023; Bontempelli et al., 2022; Kim et al., 2023; Schedl et al., 2018) to mitigate popularity biases, as vector norms often encode popularity information on items (Afchar et al., 2023; Chen et al., 2023). Normalizing embeddings also prevents inner products from being unbounded, avoiding overflow and underflow numeri- cal instabilities (LeCun et al., 2015).
Order preservation (P3): order is preserved when the probability of selecting the action i given the state V is a strictly increasing function of (V, Xt). More formally, order preservation requires that, Vi,j) E I2,
(V, X.) (V, - P(i V) > PÚ VV. (4)
P3 ensures that the exploration strategy properly lever- ages the information captured in the embedding vectors to assess the relevance of an action given state.
At time 1, the agent considers a state vector V. E Sd-1, noted V for brevity. It selects the next action in In, whose relevance is evaluated by a reward provided by the envi- ronment. In our example, the agent would recommend the next song to continue the playlist, based on the previous song whose embedding V acts as the current state. In this case, the reward might be based on user feedback, such as liking or skipping the song (Bontempelli et al., 2022). The agent may select i i.e., exploit it (Sutton& & Barto, 2018).
2.2. Limitations of Existing Exploration Strategies
Finding an strategy that simultaneously meets the three prop- erties P1, P2 and P3 is essential for effective exploration in RL problems with large action sets and embedding repre- sentations. Nonetheless, existing exploration methods fail to achieve this, which motivates our work this paper.
Random and E-greedy Exploration The most straight- forward example of an action exploration strategy would be the random (uniform) policy, where:
At this stage, we do not make assumptions regarding the specific methods used to learn these embedding vectors, nor the in- terpretation proximity between vectors the embedding space.
1
Vi E In. Prano (i) VV
(5)
3

---

Exploring Large Action Sets with Hyperspherical Embeddings using von Mises-Fisher Sampling
A popular variant is the e-greedy strategy (Sutton & Barto, 2018). With a probability e E [o, 1), the agent would choose the next action uniformly at random. With a probability 1 1- E, it would exploit the most relevant action based on its knowledge. Random and E-greedy exploration strate- gies are scalable (P1), as elements of Z, can be uniformly sampled in (1) time (Cormen et al., 2022). Additionally, they verify P2. Indeed, Radius(PPand) V) = n since every action can be selected. However, these strategies ignore embeddings at the sampling phase and do not achieve order preservation (P3). This is a significant limitation, reinforced by the fact that these policies have a maximal radius. As explained in Section 1, in large action sets, many actions are often irrelevant, e.g., most songs from the musical cata- log would constitute poor recommendations given an initial state (Tomasi et al., 2023). Exploring each action/song with equal probability, including inappropriate ones, could re- sult in negative user feedback and a poor perception of the service (Tomasi et al., 2023).
usually around hundreds or thousands, is first retrieved us- ing the ANN search engine, leading candidate action set Im (V). The sampling step is subsequently performed only within Im (V). More formally, for all i E Im (V):
en((V.X.)
PTB-exp.m (i V, Kn; x)) ΣjEI eXiV
TB-exp performs action selection in time that depends on m instead of n, and has been successfully deployed in pro- duction environments involving millions of actions (Chen et al., 2019; 2021; 2022). While it still satisfies P3, TB- exp also meets P1 for small values of m. However, it no longer satisfies P2. This method restricts the radius, i.e., the number of candidate actions, based on technical consid- erations rather than exploration efficiency. This restriction can potentially hinder model convergence by neglecting the exploration of relevant actions beyond this fixed radius. This highlights the difficulty of designing a method that simultaneously satisfies P1, P2, and P3 -3-iieelly, one with properties akin to B B-exp but with greater scalability.
Boltzmann Exploration To overcome the limitations of random exploration, actions can be sampled based on their embedding similarity with V. typically measured using dot products. The prevalent approach in RL is Boltzmann Explo- ration (B-exp) (Amin et al., 2021; eesa-Bianchh et al., 2017; Chen et al., 2021; Sutton & Barto, 2018), which employs the Boltzmann distribution for action sampling:
3. From Boltzmann to vMF Exploration
In this section, we present our proposed solution for explor- ing large action sets with hyperspherical embeddings.
3.1. von Mises-Fisher Exploration
(A(ViX))
Vie E In. P... ex (i V, Nn K)
Σー= (X())))))
(6)
The inability of B-exp to scale arises from its need to com- pute all n sampling probabilities explicitly. In this paper, we propose von Mises-Fisher Exploration (vMF-exp), an alter- native strategy that overcomes this constraint. Specifically, given an initial state vector V, vMF-exp consists in:
where the hyperparameter E R+ controls the entropy of the distribution. B-exp samples actions according to strictly increasing function of their inner product similarity with V for k > 0, guarantecing order preservation (P3). By carefully tuning K, one can ensure that irrelevant actions are practically never selected while maintaining a nenozero probability of recommending actions with less than maximal similarity, thereby indirectly controlling the radius of the policy (P2). Unfortunately, B-exp does not satisfy P1, i.e., it is not scalable to large action sets. Indeed, evaluating Equation (6) requires explicitly computing the probability of sampling each individual action before actually sampling from them, which is prohibitively expensive for large values of n (Chen et al., 2021). Note that, while we focus on B-exp, these concerns would remain valid for any other sampling distribution requiring explicitly computing similarities and probabilities for each of the n actions (Amin et al., 2021).
Firstly, sampling an hyperspherical vector V on the unit hypersphere gd-1, according to a von Mises- Fisher distribution (Fisher, 1953) centered on V.
Secondly, selecting V'ss nearest neighbor action in the embedding space for exploration.
In directional statistics, the vMF distribution (Fisher, 1953) is a continuous vector probability distribution defined on the unit hypersphere sd-1, It has recently been used in RL to assess the uncertainty of gradient directions (Zhu et al., 2024). For all V e Sd-1, its probability density function (PDF) is defined as follows:
fvMr(V Kx, V. = Ca(M))
(8)
Truncated Boltzmann Exploration Due to these scal- ability concerns, previous work sometimes settled for a workaround consisting in sampling actions from a Trun- cated version of B-exp (Chen et al., 2021), which we refer to as TB-exp. A small number m & n of candidate actions,
with:
Ca(k)) Jvess en(M)) di =
(9)
(2xr) 4 و
(

---

Exploring Large Action Sets with Hyperspherical Embeddings using von Miscs-Fisher Sampling
V
V
X1
0
8 2
25
8
A
A
< <.AA>
8
X2
2.0
X3
X10
X4
X9
Xs
1.0
X8
0.5
X
X6
(a)
(b)
(c)
Figure 1. (a) Probability density function (PDF) a 3-dimensional vMF distribution. (b) vMF-exp explores the action a represented by the
embedding vector A when the sampled vector V lies in A's Voronoi cell, shown in red in 3D. (c) Same (b) in 2-dimensional setting.
and where A E R+ The function _ designates the mod- ified Bessel function of the first kind (Baricz, 2010) at order d/2 1. Figure ((a) illustrates the PDF of a vMF distribu- tion on the 3-dimensional unit sphere. For any V Sd-11 (V K. d.)) is proportional to e*(V,V) which is remi- niscent of the B-exp sampling probability of Equation (6). The hyperparameter x controls the entropy of the distribu- tion. In particular, for 0, the vMF distribution boils down to the uniform distribution on Sd-1
Thus, vMF-exp's 's sampling probabilities can be written as:
Vi E In: PoMP-eup(t (i V. k.)
J SNME(V Kr Vd), (12)
which is always strictly positive. Therefore, vMF-exp satis- fies the unrestricted radius property (P2). Similar to B-exp, adjusting x ensures that actions with low similarity have negligible sampling probabilities in practice.
3.2. Properties
P3 esp (i | V, T,,'n, xe) increases due to two factors: the average fyMP(V (V K. V, d) value for V E Svamnoi (X; Xx,,, correlated to (X,, V) and contributing to order preservation, and the surface area of Sviromos (X, X,),, which measures X;'s 's dissimilarity to other X,, elements. Actions in low- density subspace of g have larger Voronoi cells and may be selected more often than those near V but in high- density regions. Thus, vMF-exp favors actions similar to V and dissimilar to others, with order preservation being dependent on X,," 's distribution. Scction focuses on a setting where B-exp and vMF-exp asymptotically share similar probabilities. Consequently, vMF-exp, like B-exp, will verify order preservation (P3). In conclusion, in this setting, vMF-exp will verify P1, P2, and P3 simultancously.
P1 vMF-exp only requires sampling d-dimensional vec- tor instead of handling a discrete distribution with pa- rameters, allowing V to be sampled in constant time with respect to n. Therefore, vMF-exp is scalable exploration strategy. Efficient sampling algorithms for vMF distribu- tions have been well-studied (Kang& & Oh, 2024; Pinzón & Jung, 2023) (see Appendix for practical details). As shown in the following sections, we successfully explored sets of millions of actions without scalability issues, using the Python vMF sampler from Pinzón & Jung (2023) for simulations in Section 4 and a custom implementation for the recommendation application in Section 5.
The probability of sampling i E In given V for explo- ration is the probability that X, is the nearest neighbor of V. within Xn. i.e., that V lies in Svanoos(X (X; | Xx).. the Voronoï cell of X, in the Voronoi tessellation of 8d-1 defined by Xn (Du et al.. 1999; 2010) (see Figures 1(b). 1(c)). We have:
P2
4. Theoretical Comparison: vMFF-epp vs B-exp
We now provide a mathematical comparison of vMF-exp and B-exp. We focus on the theoretical setting presented in Section 4.1. We show that, in this setting, vMFF-xp maintains the same probability of exploring each action as B-exp, while overcoming its scalability issues. As noted above, this implies that vMF-exp verifies P1, P2, and P3 simultaneously and, therefore, acts as a scalable alternative (1I) to the popular but unscalable B-exp for exploring large action sets with hyperspherical embeddings.
Svorooor (Xil kn) = (V E sd-1 Vj E In, (V,X.) 2 (V, X,)),
(10)
and:
U Svoronor Kn)) = sd-1
5

---

Exploring Large Action Sets with Hyperspherical Embeddings using von Mises-Fisher Sampling
4.1. Setting and Assumptions
with A(84-1) denoting the surface area of the hypersphere S The following two propositions describe the rate which this asymptotic behavior is reached by B-exp and vMF-exp, respectively, as grows.
We focus on the setting where embeddings are independent and identically distributed (i.i.d.) and follow uniform distribution on the unit hypersphere, i.c.
Proposition 4.2. In the setting of Section 4.1, we have:
Xn ~ 1(8
(13)
PB-eppa (a n. V. Pu(a n. d. v,
For convenience in our proofs, we consider the action set to be the union of In. the set of actions, and another ac- tion a with known embedding A E sd-1, The resulting entire action set L and embedding set Xx+1 are defined as In+1= = I, U {a} and Xa+1 = X, U {A}. In this sec- tion, we are interested the probability of each exploration scheme, B-exp and vMF-exp, to sample a among all actions of I given state embedding vector V Sá-1, These probabilities are defined respectively as:
(18)
+ ol nyn
Proposition 4.3. In the setting of Section 4.1, we have: PaMr-cap(a n. I,.dd v)) = Po(a m, d, In,d
V,K)
(0())
if = 2, (19)
if > 2.
PB ea m, V.)
In essence, when n is large, the probability of sampling a can be approximated by the PDF of the vMF distribution evaluated at A multiplied by the average surface area of A's Voronoi cell, for both methods. As n grows, this Voronoi cell shrinks until SMM becomes nearly constant across its entire surface. Figure 2(f) illustrates this interpretation.
E X, ( Pa-expla| | V, Vi (14)
and:
expF-epp(a (a n. d. V,K)
PuMPooppa| V V, m)).
The rate at which the two exploration methods reach their asymptotic behavior differs. Specifically, the shrinking rate of the Voronoi cell depends on the dimension of the hyper- sphere, explaining why the second term in Equation (19) depends on d. This dependency does not occur with B-exp. Consequently, for large values of d, one may require a higher number of actions n before the asymptotic behavior of Equa- tion (16) is observed. For this reason, it is useful to obtain a more precise approximation of PoMt-exp(a (a n, d, V, k) when increases, which we provide in the next section.
E X, (((S--1)
(15)
4.2. Results
We now present and discuss our main theoretical results. For brevity, we report all intermediary lemmas and math- ematical proof' in the Appendices A, B, C and D of this paper. Our first and most general result links the asymptotic behavior of B-exp and vMF-exp as the action set grows
Proposition 4.1. In the setting of Section 4. I, we have:
4.3. Discussion
lim ex n, d, V, R)) +00 PeMsF-epp(a (a n, d, V,))
High Dimension Building on the above discussion, Proposition 4.4 provides a more precise expression for Pa | n, V,K) when d increases (approximately d 2 20 in our experiments). This expression derived by examining the first two terms of the Taylor expan- sion (Abramowitz & Stegun, 1948) of fyMF near A, rather than relying solely on the zero-order term. The second term becomes increasingly significant as d grows. Despite its apparent complexity, the expression has a straightforward interpretation: the negative sign before (V, A) indicates that, when A is similar to V. it is sampled less often than with B-exp for the same λ and d. Conversely, when A is on the opposite side of the hypersphere, the term positively contributes to Pa n, V, R).. In summary, for larger d vMF-exp is expected to explore more extensively than B-exp with the same k.
=
(16)
Proposition 4.1 states that, for large values of n, the probabil- ity of sampling the action a for exploration is asymptotically the same using either B-exp or vMIF-exp. This result follows from the respective asymptotic characterizations of PB-exp and P exp detailed below. Importantly, it implies that, for large values of n, vMF-exp shares the same properties as B-exp (P2, P3). including order preservation. However, as noted in Section 3, vMF-exp offers greater scalability since its implementation only requires sampling a vector of fixed size d, an operation independent of n (P1).
Next, we present common approximate analytical expres- sion for both methods, denoted Po and defined as follows:
Proposition 4.4. Let B: : (2), 22) + fo (1-t)===1 dt denote the Beta function, and T + So fe dt
Pa(a| | d. V.R)= [A
A | V, ((
(17)
6

---

Exploring Large Action Sets with Hyperspherical Embeddings using von Mises-Fisher Sampling
K= 1.0, <V.A2=0.5, d-4
K 1.0, <V.A>=0.5, d-8
K 1.0, <V..A==0.5, d-16
175
Pala)
1.75
Pola)
1775
Pola)
150
(a(a)
3.59
Py(a)
1.0
Pr(a)
Pa expla)
Po Po-cup
Pa expla
1.25
Puwe- upla)
P.ee (a)
1.25
Puw- amla)
1.00
3 2.00
2
1.00
0.75
0.75
0.75
0.50
0.30
0.25
0.23
0.25
0.00
0.00
0.00
02
0.4
0.5
0.6
1.0
0.5
(a)
(b)
(c)
1e-5
k= 1.0, <V,5==0.5, d=32
1e-5
== 1.0, <V,5>=0.5, d=64
Pola)
1.6
Pola)
Pl(a)
Pyla)
Pa- ap)
160
1.2
Puer- lap)
Puer- eppla
50
1.0
0.4
0
0.2
0.2
0.0
0.0
(d)
(e)
(l)
Figure 2. (a) to (e): Validation of the key properties discussed in Sections 4.2 and 4.3 using Monte Carlo simulations, as further elaborated
in Section 4.3. (f) Illustration of the 3-dimensional Voronoi cell of vector A, for action numbers n E {50, 100, 1000].
denote the Gamma function (Abramowitz & Stegun, 1948).
Validation of Theoretical Properties via Monte Carlo Simulations Using the efficient Python sampler of Pinzón & Jung (2023), we repeatedly sampled vectors Xn ~ u($d-1) ) and V ~ vMF(V, x)), for various values of d, k, and (V, Figure 2 reports, for 1.0, (V, = 0.5 and growing values of d, the PaM (a) sampling probability depending on the number of actions as well as P (a) with similar parameters and our approximations (a and (a). We repeated all experiments 8 million times and re- ported 95% confidence intervals. The results are consistent with our key theoretical findings in this paper.
In the setting of Section 4.1 with d 2 3, we have:
PaM n. V, x) = Pi (a n, V,K)
(20)
+ 0
with:
(a n.) = Pola| | n, K)))
[uMP(A V, V.H)A(S++))((VVA)IV
2
Firstly, in line with Proposition 4.2, PB-cop(a) and Po(a) are indistinguishable for this range of n values. Secondly, for small d values (Figures 2(a), 2(b), 2(c)), PoM is also tightly aligned with ex (a) and Pa(a), consistently with Proposition 4. and 4.3. Note that the y-axis is on a le-5 scale; hence, probabilities are extremely close. Thirdly, when d > 16 (Figures 2(d), 2(e)). (u) becomes more distinguishable from Pa(a) and constitutes better approx- imation of PcMP-exp (a) than Po(a). as per Proposition 4.4. Lastly, since (V > 0, Proposition 4.4 predicts that Pn exp (a) 2 eaMF (a) for large d, which our experiments confirm. We provide comparable simulations with other (d, (V, A)) combinations in Appendix G. All simulations are reproducible using our source code (see Section 5).
(d - 1)B( 31 x
x
(21)
The case = In 2 dimensions, Voronoi cells are ares of a circle and are delimited by the perpendicular bisectors of two neighboring points, as shown in Figure 1(c). Inter- estingly, in this specific case, (v n, d = 2, V. k) can be computed using geometric arguments. A comprehen- sive mathematical analysis is provided in Appendix B. This analysis confirms that, when d = 2, vMF-exp approaches its asymptotic behavior faster than B-exp, as indicated by the O nz) term in Proposition 4.3.
7

---

Exploring Large Action Sets with Hyperspherical Embeddings using von Miscs-Fisher Sampling
Mixes inspired by..
Discover new tracks sim similar to your favourites
Under The Gun by Flectric
Pastoral Christian Löftler
I'm Real (feat. Rule) by Jejeeniferr Lopez
Samiie Sani
Think
Day's by Hamnlr Minactian
Memory Box by Peter Cat Recording Co.
by Aretha Fraanklnn
Madan
Otan Hunu by Silm Young
The Number the Beast by Iron Maiden
by Saitt Kelta
Figure 3. Interface of the "Mixes Inspired By" recommender system on the music streaming service Deezer. This system presents a personalized shortlist of songs liked by the user. Clicking on song generates playlist "inspired by" this song. As detailed in Section 5 and Appendix vMF-exp has been employed for months on the production environment of this service to generate playlists, exploring songs from a catalog containing millions of candidates.
Link with Thompson Sampling One might notice inter- esting similarities between vMF-exp and bandit arm explo- ration with the Thompson Sampling method (Chapelle & Li, 20. We refer the interested reader to our Appendix E for detailed comparison of the two approaches.
vectors. Nonetheless, as an opening to our work and a com- plement to this mathematical analysis, we describe in this section several empirical validations of vMF-exp, further detailed in Appendices G, H. and I. Taken together. these experiments validate the claimed scalability and theoretical properties of the proposed method, as well as its potential and impact for real-world applications. Specifically:
Limitations and Future Work While we believe our study provides valuable insights into vMF-exp, several limi- tations must be acknowledged. Our theoretical guarantees currently restricted to the distributions described in Sec- tion 4.1. Although vMF-exp can be applied in practice with hyperspherical embeddings from any other distributions, we have not yet extended our guarantees to such cases?.
To begin with, recall that, explained in Sec- tion 4.3, a more comprehensive outline of the Monte Carlo simulations discussed in that section is provided in Appendix G. The additional results presented in this appendix are consistent with those shown in Figure of Section 4.3, To ensure the reproducibility of these experiments and to encourage future use of the vMF- exp method, have released Python implementa- tion of vMF-exp GitHub with this paper: https: / / //qitt githuu..... com/ deezer VMF-exploration
For instance, studying vMF-exp in clustered embedding settings, as is sometimes the case with music recommen- dation embeddings (where clusters can, e.g., summarize music genres (Salha-Galvan et al., 2022)), could be insight- ful. We believe that future research should benefit from the approach we proposed in this paper to derive the full (non-trivial) demonstration for the uniform distribution case.
To go further, we recognize that some readers may wish explore our topic through reproducible experiments on real-world data. Therefore, in Appendix H, we em- pirically validate the main properties of vMF-exp using a large-scale, publicly available dataset of one mil- lion Glo word embedding vectors (Pennington et al., 2014). We demonstrate that vMF-exp simultaneously satisfies P1, P2, and P3 on this GloVe dataset. Further- more, this study Glo Ve vectors shows the accuracy of our approximations of PB-exp (a) and PoMF-cxp(o) (a) from Propositions 4.2, 4.3, and 4.4, despite the fact that GloVe vectors do not strictly meet the i.i.d. and uniform assumptions of our thcoretical study. This additional study fully reproducible using the code provided in the GitHub repository mentioned above.
Our future work will also investigate the second-order term from Proposition 4.4, which may be significant for large K, as well the impact of ANN errors. Although our analysis assumes exact neighbor retrieval, this assumption may break down for extremely large action sets (Johnson et al., 2019), potentially causing minor exploration perturbations.
5. vMF-exp in the Real World
As explained in Section 1, the primary objective of this paper was to introduce vMF-exp and provide rigorous mathe- matical analysis of its theoretical properties for exploring large action sets represented by hyperspherical embedding
The final appendix of this paper, Appendix I, show- cases real-world application of vMF-exp. We present its successful large-scale deployment in the private
Nonetheless, results from Section 5 will tend to confirm the practical usefulness of our propositions real-world embedding vectors that do not strictly satisfy assumptions from Section 4.1.
8

---

Exploring Large Action Sets with Hyperspherical Embeddings using von Miscs-Fisher Sampling
production system of the global music streaming ser- vice Deezer (Bendada et al., 2023a). On this service, vMF-exp has been employed for months to recom- mend playlists of songs inspired by an initial selection to millions of users (see Figure 3), exploring a cata- log of millions of candidate songs. This application, validated by a positive worldwide online A/B test, con- firms the practical relevance of our work. As vMF-exp was successfully deployed in production, achieving sampling latency of just few milliseconds, it also confirms the scalability of the method.
2023.
Afsar, M. M., Crump, T., and Far, B. Reinforcement learn ing based recommender systems: A survey. ACM Com- puting Surveys, 55(7):1-38, 2022.
Amin, S., Gomrokchi, M., Satija, H., van Hoof, H., and Pre- cup, D. A survey of exploration methods in reinforcement learning. arXiv preprint (XXx:2209.001555 2021.
Aumüller, M., Bernhardsson, E., and Faithfull, A. Ann- benchmarks: A benchmarking tool for approximate near- est neighbor algorithms. In Proceedings of the 10th In- ternational Conference on Similarity Search and Applica- tions, pp. 49. Springer, 2017.
6. Conclusion
This paper introduced vMF-exp, a scalable method for ex- ploring large action sets in RL problems where hyperspher- ical embedding vectors represent these actions. vMF-exp scales effectively to large sets with millions of actions, ex- hibits desirable properties, and, under theoretical assump- tions, even asymptotically preserves the same exploration probabilities as B-cxp, a prevalent RL exploration method that suffers from scalability limitations. This establishes vMF-exp as a scalable and practical alternative B-exp. While the primary focus of this paper is on the theoretical foundations of vMF-exp, extensive experiments lated data, real-world public data, and the successful deploy- ment of vMF-exp on a music streaming service validated the scalability and practical relevance of the proposed method.
Banerjee, A., Dhillon, I. S., Ghosh, J., Sra, S., and Ridge- way, G. Clustering the unit hypersphere using von mises-fisher distributions. Journal of Machine Learning Research, 6(9), 2005.
Banerjee, S. and Roy, A. Linear Algebra and Matrix Analy- sis for Statistics. CRC Press, 2014.
Baricz, Á. Generalized Bessel Functions of the First Kind. Springer, 2010.
simu-
Bendada, W., Salha, G., and Bontempelli, T. Carousel personalization in music streaming apps with contextual bandits. In Proceedings of the 14th ACM Conference on Recommender Systems, pp. 420-425-55 2020.
Impact Statement
Bendada, W., Bontempelli, T., Morlon, M., Chapus, B., Cador, T., Bouabça, T., and Salha- Galvan, G. Track mix generation on music streaming services using transform- ers. In Proceedings of the 17th ACM Conference on Recommender Systems, pp. 112-115, 2023a.
This paper introduces scalable method for exploring large action sets in reinforcement learning problems, with appli- cations including recommender systems. While our work is primarily methodological and theoretical, its integration into real-world systems, such as personalized music recom- mender systems, can influence user experience, engagement, and exposure information. We highlight the potential for both positive outcomes (e.g., improved personalization and efficiency) and risks such as over- peter-eesonliiiiionn or bias am- plification if used without appropriate fairness and diversity constraints. We encourage careful deployment and further study when applying this method to sensitive domains in- volving social or behavioral data.
Bendada, W., Salha-Galvan, G., Bouabça, T., and Cazenave, T. A scalable framework for automatic playlist continua- tion on music streaming services. In Proceedings of the 46th International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 464-47 474, 2023b.
Bendada, W., Salha-Galvan, G., Hennequin, R., Bontem- pelli, T., Bouabça, T., and Cazenave, T. vmf-exp: von mnsess-fisher exploration of large action sets with hyper- spherical embeddings. In ICML. 2024 Workshop on Align- ing Reinforcement Learning Experimentalists and Theo- rists, 2024.
References
Abramowitz, M. and Stegun, I. A. Handbook of Mathemati- cal Functions with Formulas, Graphs, and Mathematical Tables, volume 55. US Government Printing Office, 1948.
Bendada, W., Salha-Galvan G., Hennequin, R., Bontem- pelli, T., Bouabça, T., and Cazenave, T. von mises-fisher sampling of glove vectors. In ICLR 2025 Workshop on Frontiers in Probabilistic Inference: Learning meets Sam- pling, 2025.
Afchar, D., Hemnequin, R., and Guigue, V. Of spiky svds and music recommendation. In Proceedings of the 17th ACM Conference on Recommender Systems, pp. 926 932,

---

Exploring Large Action Sets with Hyperspherical Embeddings using von Miscs-Fisher Sampling
Billingsley, P. Convergence of Probability Measures. John Wiley & Sons, 2013.
Coolidge, J. L. The story of the binomial theorem. The
American Mathematical Monthly, 56(3):147-157, 1949.
Bontempelli, T., Chapus, B., Rigaud, F., Morlon, M., Lorant, M., and music by moods on deezer. In Proceedings of the 16th ACM Conference Recommender Systems, pp. 452-455, 2022.
Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C.
G. Flow moods: Recommending
Introduction to Algorithms. MIT Press, 2022.
Dann, C., Mansour, Y., Mohri, M., Sekhari, A., and Srid- haran, K. Guarantees for epsilon-greedy reinforcement learning with function approximation. In Proceedings of the 39th International Conference on Machine Learning, pp. 4666 4689. PMLR, 2022.
Boytsov, I.. and Naidan, B. Engineering efficient and ef- fective non-metric space library. In Proceedings of the 6th International Conference on Similarity Search and Applications, pp- 280-293. Springer, 2013.
Douze, M., Guzhva, A., Deng, C., Johnson, J., Szilvasy, G., Mazaré, et al. The faiss library. arXiv preprint arXiv:2401.0828/ 2024.
Briand, L.,, Salha-Galvan, G., Bendada, W., Morlon, M., and Tran, V.-A. semi-pene cemi-personalized system for user cold start recommendation on music streaming apps. In Proceed- ings of the 27th ACM SIGKDD conference on knowledge discovery & data mining, pp. 2601 -2099, 2021.
Du, Q.. Faber, V., and Gunzburger, M. Centroidal voronoi tessellations: Applications and algorithms. SIAM Review, 41(4):637-676, 1999.
Du, Q., Gunzburger, M., and Ju, L. Advances in studies and applications of centroidal voronoi tessellations. Numeri- cal Mathematics: Theory, Methods and Applications. 3 (2):119-143) 2010.
Briand, L., Bontempelli, T., Bendada, W., Morlon, M.,
Rigaud, F., Chapus, B., Bouabça, T., and
G. Let's get it started: Fostering the discoverability of new releases on deezer. In European Conference on In- formation Retrieval, pp. 286-28 291. Springer, 2024.
Dulac-Arold, G., Evans, R., van Hasselt, H., Sunehag, P., Lillicrap. T., Hunt, J., Mann, T., Weber, T., Degris, T., and Coppin, B. Deep reinforcement learning in large discrete action spaces. arXiv preprint arXiv: 1512.0779, 2015.
Cesa-Bianchi, N., Gentile, C.. Lugosi, G., and Neu, G. Boltzmann exploration done right. Advances in Neural Information Processing Systems, 30, 2017.
Fischer, H. A History of the Central Limit Theorem: from Classical to Modern Probability Theory. Springer, 2011.
Chapelle, O. and Li, L. An empirical evaluation of thompson sampling. Advances in Neural Information Processing Systems, 24, 2011.
Fisher, R. A. Dispersion on sphere. Proceedings of the
Royal Society of London. Series Mathematical and Physical Sciences, 217(1130):995-005, 1953.
Chen, J., Wu, J., Wu, J., Cao, X., Zhou, S., and He, X. Adap-T: Adaptively modulating embedding magnitude for recommendation. In Proceedings of the ACM Web Conference 2023, pp. 1085-1096, 2023.
Gentle, J. E. Springer, 2009.
Computational Statistics, volume 308.
Chen, M., Beutel, A., Covington, P., Jain, S., Belletti, F,, and Chi, E. H. Top-k off-policy correction for rein- force recommender system. In Proceedings of the 12th ACM International Conference on Web Search and Data Mining, pp. 456 464, 2019.
Gnedenko, B. Sur la distribution limite du terme maximum d' unu serie alcatoire. Annals of Mathematics, pp. 423- 453, 1943.
Guo, R., Sun, P., Lindgren, E.,, Geng, Q., Simeha, D., Chern, F,, and Kumar, S. Accelerating large-scale inference with anisotropic vector quantization. In Proceedings of the 37th International Conference on Machine Learning, pp. 3887-3896, 2020.
Chen, M.. Chang, B., Xu, C., and Chi, E. H. User response models to improve reinforce recommender system. In Proceedings of the 14th ACM International Conference on Web Search and Data Mining, pp. 121-129, 2021.
Iwasaki, M. and Miyazaki, D. Optimization of indexing based on k-nearest neighbor graph for proximity search, arXiv preprint arXiv: / 181000735, 2018
Chen, M., Xu, C., Gatto, V., Jain, D., Kumar, A., and Chi, E. Off-policy actor-critic for recommender systems. In Pro- ceedings of the 16th ACM Conference on Recommender Systems, pp. 338-349 2022.
Jacobson, K., Murali, V., Newett, E., Whitman, B., and Yon, R. Music Personalization at Spotify, pp. 373-373, 2016.
Chiappa, A. S., Marin Vargas, A., Huang, A., and Mathis, A. Latent exploration for reinforcement learning. Advances in Neural Information Processing Systems, 36, 2023.
Jacod, J. and Protter, P. Probability Essentials. Springer
Science & Business Media, 2004.
10

---

Exploring Large Action Sets with Hyperspherical Embeddings using von Miscs-Fisher Sampling
Jin, C., Krishnamurthy, A., Simchowitz, M., and Yu, T. Reward-free exploration for reinforcement learning. In Proceedings of the 37th International Conference on Ma- chine Learning, pp.
Mikolov, T., Sutskever, I., Chen, K., Corrado, G. S., and Dean, J. Distributed representations of words and phrases and their compositionaliiy. Advances in Neural Informa- tion Processing Systems, 26, 2013.
PMLR, 2020.
Johnson, J., Douze, M., and Jégou, H. Billion-scale similar- ity search with gpus. IEEE Transactions on Big Data, 7 (3):535-544) 547, 2019.
Oehlert, G. W. A note on the delta method. The American Statistician, 46(1):27-29, 1992.
Pennington, J., Socher, R., and Manning, C. D. Glove: Global vectors for word representation. In Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing, pp. 1532-1543, 2014.
Kang, S. and Oh, H.-S. Novel sampling method for the von mises-fisher distribution. Statistics and Computing, 34 (3):106, 2024.
Kim, D., Park, J., and Kim, D. Test-time embedding normal- ization for popularity bias mitigation. In Proceedings of the 32nd ACM International Conference Information 2023.
Pinzón, C. and Jung, K. Fast python sampler for the von mises fisher distribution. HAL Id: hal-04004568, 2023.
Reynolds. Reinforcement learning with exploration. Ph.D.. Thesis, University of Birmingham, 2002.
and Knowledge Management, pp.
Konda, V. and Tsitsiklis, J. Actor-critic algorithms. Ad- vances in Neural Information Processing Systems, 12, 1999.
Malha-Galvar G., Lutzeyer, J. F., Dasoulas, G., Hennequin, R., and Vazirgiannis, M. Modularity aawrre graph autoen- coders for joint community detection and link prediction. Neural Networks, 153:474 495, 2022.
Koren, Y. and Bell, R. Advances Collaborative Filtering. Recommender Systems Handbook, pp. 77-118, 2015.
Schedl, M., Zamani, H., Chen, C.-W., Deldjoo, Y., and Elahi, M. Current challenges and visions in music recommender systems research. International Journal of Multimedia Information Retrieval, 7:95-116, 2018.
Ladosz, P., Weng, L., Kim, M., and Oh, H. Exploration in deep reinforcement learning: survey. Information Fusion, 85:1-22, 2022.
Simhadri, H. V., Aumüller, M., Ingber, A., Douze, M., Williams, G., Manohar, M. D., Baranchuk, D., Lib- erty, E., Liu, F,, Landrum, B., et al. Results of the big Neurips' competition. arXiv preprint arXiv:2409. 17424, 2024.
Lange, S., Gabel, T., and Riedmiller, M. Batch reinforce- ment learning. In Reinforcement Learning: State-Of-The Art, pp. 45-73. Springer, 2012.
LeCun, Y., Bengio, Y., and Hinton, G. Deep learning, Na- ture, 521(7553):436 444, 2015.
Slivkins, A. al. Introduction to multi- bandits. Foun- dations and Trends in Machine Learning, 12(1-2):1 2019.
Li, W. Zhang, Y., Sun, Y., Wang, W. Li, L., Zhang, W., and Lin, X. Approximate nearest neighbor search on high dimensional data experiments, analyses, and im- provement. IEEE Transactions on Knowledge and Data Engineering. 32(8):1475-1488 2019.
Sra, S. A short note on parameter approximation for von mises-fisher distributions: And a fast implementation of is(x). Computational Statistics, 27:177 190, 2012.
Lillicrap, T. P., Hunt, J. J., Pritzel, A., Heess, N., Erez, T., Tassa, Y., Silver, D., and Wierstra, D. Continuous control with deep reinforcement learning. In Proceedings of the 4th International Conference on Learning Representation, 2016.
Sutton, R. S. and Barto, A. G. Reinforcement Learning: An Introduction. MIT Press, 2018
Tan, P.-N., Steinbach, M., and Kumar, V. Introduction to Data Mining. Pearson Education India, 2016.
Tang, H., Houthooft, R., Foote, D., Stooke, A., Xi Chen, O., Duan, Y. Schulman, J., DeTurck, F., and Abbeel, P. exploration: A study of count-basee exploration for deep reinforeement learning. Advances in Neural Information Processing Systems, 30, 2017.
Malkov, Y. A. and Yashunin, D. A. Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence, 42(4))824- 836, 2018
Tomasi, F., Cauteruccio. J., Kanoria, S., Ciosek, K., Rinaldi, M., and Dai, Z. Automatic music playlist generation via simulation- based reinforcement learning. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 4957, 2023.
Mardia, K. V. and Jupp, P. E. Directional Statistics. John Wiley & Sons, 2009.
McFarlane, R. A survey of exploration strategies in rein- forcement learning. McGill University, 3:17-18, 2018.

---

Exploring Large Action Sets with Hyperspherical Embeddings using von Mises-Fisher Sampling
Zamani, H., Schedl, M., Lamere, P., and Chen, C.-W. An analysis of approaches taken in the recsys chal- lenge 2018 for automatic music playlist continuation. ACM Transactions on Intelligent Systems and Technology (TIST), 10(5):1-21, 2019.
Zhu, Y., Liu, J., Wei, W., Fu, Q., Hu, Y., Fang, Z., An, B., Hao, J., Lv, T., and Fan, C. vmffr: von mises- fisher experience resampling based on uncertainty of gradient directions for policy improvement of actor-critic algo- rithms. In Proceedings of the 23rd International Confer- ence on Autonomous Agents and Multiagent Systems, pp.
2621 2623, 2024.
12

---

Exploring Large Action Sets with Hyperspherical Embeddings using von Miscs-Fisher Sampling
Appendix
This appendix supplements the article "Exploring Large Action Sets with Hyperspherical Embeddings using von Mises-Fisher Sampling" and is organized as follows:
Appendices A, B, C, and D provide detailed proofs and discussions for all theoretical results presented in the paper.
Appendix explores the connection between vMF-exp and Thompson Sampling.
Appendix F explains practical methods for sampling from the vMF distribution.
Appendix G presents the complete results of our Monte Carlo simulations.
Appendix details an additional experimental study using a large-scale, publicly available Glo dataset.
Appendix highlights the successful large-scale deployment vMF-exp in the private production system of the global music streaming service Deezer for large-scale music recommendation.
A. Asymptotic Behavior of Boltzmann Exploration (Proof of Proposition 4.2)
We begin with the proof of Proposition 4.2 claiming that, in the setting of Section 4.1, we have:
PB-exp (a n, d, V, fvMr(A (A V, V,R)A(S*
to 1 nvn
(22)
denoted (o (a,,,,d
with SAMF the probability density function (PDF) of the Mises-Fisher (vMF) (Fisher, 1953) distribution:
AA E 8d-11 1 (A v,K)) Ca(M))=<VVA))
(23)
where A(S is the surface area of 1 the d-dimensional unit hypersphere, and Ca(K) the normalizing constant.
Proof. By definition,
(V((VAA)
Pa-exp(a n,d, V,K) = x, ((((--1))
en(ViA + Ei= en(V.x))
cH(ViA)
pa(Vid) E ((
(24)
(V, Diml
n
n
n
(V,A)) E X
Dm
We use D,, to denote the denominator of the expression inside the above expectation. Dn is the empirical average of independent and identically distributed (i..d.) random variables (plus a constant). Therefore, by applying the Central Limit Theorem (CLT) (Fischer, 2011), we know that as n grows will be asymptotically distributed according to a Normal distribution with the following expectation:
(eN(V.A)
en(V.X)))
E x [Dn] = E x.-U((0-1)
(25)
(N(VAA)
[oR(V.x3))
+ E XxU(SS-1)
n
Moreover, we have:
E Xxulis1 1) [en(V.))
- - A(Sa-I) d.X
(v
(26)
A(8d-1)Cd(k))
13

---

Exploring Large Action Sets with Hyperspherical Embeddings using von Mises-Fisher Sampling
using the fact that (1s is the normalizing constant of vMF distribution, ensuring that its PDF (Equation (23)) sums when integrated the unit hypersphere.
Let us define = Var X~u((s-1) [c*(v Although we do not need an explicit expression for o, we know it is finite.
Additionally, let g : x + be the inverse function. The CLT ensures that:
V Dn ((s(k)
(0,
(27)
where 2, denotes convergence in distribution (Jacod & Protter, 2004). Moreover, since is differentiable function on R we use the Delta method (Ochlert, 1992) to infer that:
Vilg(Da) g( A(S )1 2., ((SS-CCC )..)
(28)
Replacing 9 and g' by their respective values, we obtain:
Vn 1 Ca(())A(8-))) Dn
(29)
Furthermore, recall that a sequence E1, .2... of random variables converges distribution to a random variable Z, then for all bounded continuous function @, lim E [z,) [ø(Z)] (Jacod & Protter, 2004). Since for every the random n
variable 7m vnl (((s))A(S)-1)) has bounded values, we can simply chose the identity function for ø to conclude that:
lim E ~ 1) Vni 1 D, C2(+)-((Sd-1)) =0, +00
(30)
which is equivalent to:
1 Ca(K))A(8*1)) 1+++) +
E xs(s 1)
(31)
D
Finally, by multiplying Equation (31) by en(V.a)
we obtain Equation (22), concluding the proof.
14

---

Exploring Large Action Sets with Hyperspherical Embeddings using von Miscs-Fisher Sampling
B. Asymptotic Behavior of vMF Exploration in d dimensions (Proof of Proposition 4.3, Part] 1)
We now prove Proposition 4.3 when d = 2. In 2 dimensions, the vMF distribution takes the special form of the von Mises (vM) distribution (Mardia & Jupp, 2009) which, instead of describing the distribution of the dot product between V and V, describes the distribution of their angle 0. The PDF of a von Mises distribution is defined as follows:
40 E [- fo R) e" cos(()
(32)
(x)
Let us define On as the angle between V and A. In this section, we prove that:
ex coa(())) (l((()) n
1 0
P PiMF-esp(4 (A n, = x))
(33)
Proof. By definition,
exM (A n. 22 = E N. X.- PP( E Svonuoil (A kntz))1:
(34)
where Svirnoai (X; =v) (V, x,) 2 (V,x,) Let us call Vn = {Yr the result of the permutation of the indices of Xn such that the (signed) angles 3; between A and Y; are sorted in increasing order. Since the {X:} are i..d. and uniformly distributed on the cirele, then the angles between A and the {X,} are i.i.d. and uniformly distributed on [0, 2m]. Therefore, the set { is the set of the order statisties of n i.i.d. random variables uniformly distributed on [0, 2n).
Consequently, the set { 2z is the set of the order statistics of i.i.d. random variables uniformly distributed on [o, 1]. which known to follow Beta distributions (Gentle, 2009) defined as follows:
B1
V1 sis n,
Beta(i, n + 1-i).
(35)
2x
As consequence, we have:
E [3]] 2T
(36)
2Tn
E [8m]
(37)
2m
Var [31] = Var [8n] = (n 1)2 + 2)
(38)
Moreover, for given values of Y,, we can see from Figure 4 that, in 2 dimensions, Voronoi cells ares of the circle and delimited by perpendicular bisectors of two neighboring points. Specifically, the Voronoi cell of is delimited by the perpendicular bisector of A and Yı on side, and the perpendicular bisector of A and Y, the other side. By denoting 0 the (signed) angle between V and V, we have:
PP V E Svornoo (A) xx+1)) IP(0 100
B. 2m
- 1110 0 k1,
00
(39)
Not
Sm 15) do.
0=00
2n
Therefore:
No 1 A Engas
PoMP-cxp(A n, d 2,x) B Bn
fvr(0)
k)) d0
(40)
To get an asymptotic expression of the probability that lies between the considered bounds, we can first notice that as n grows, Br will approach 0 and Bn will approach 2v. This means that the integral we need to compute will have very narrow
15

---

Exploring Large Action Sets with Hyperspherical Embeddings using von Miscs-Fisher Sampling
B1
Y1
0
+
A
6
X2
B
$3
10
Y
9
Y
8
Yy
Y
Figure 4, For vMF-exp explores the action A when V lies its Voronoï cell, shown in red.
bounds centered Og. and leverage the Taylor series expansion (Abramowizz & Stegun, 1948) of f.m around On and obtain:
fv m²) = frm(fu [x) + Ro),),
(41)
(1) (0olx) (0
where (0) = E
0,)* is the zero order remainder term of the Taylor series expansion of fvM near 0g.
1
We can now estimate the portion of the integral of Equation (40) corresponding to each term of the expansion separately, and show that when n becomes large:
the zero-order term gives probability of selecting A that the same as the asymptotic behavior of B-exp: e com()g)
10+ 41
E 91,8m
10000 Eugar fvM(00 x)
(lo(k) +0(,))
the expectation of the remainder term is bounded by 1 7
term: S,
-= سج Ro do = 0
16

---

Exploring Large Action Sets with Hyperspherical Embeddings using von Miscs-Fisher Sampling
B.1. Zero-Order Estimate
Let us study the zero-order approximation of [v x) near 0o:
Aot 4
Bn 2T
E 91,9n
fu k) do
= E BL.8n
fva( x)(00 +
- -00 +
0=00- 2mg2
3n B
E D1.0n
[vM( 1T)(T
2
Bn 11
- ffu 16) E B1,0n
2n
Bi
A1
(1 - E 91,9n
+ E BL.8..
(In(k)
2TT
2T
n +
(42)
210(k)
n + 1
21((k) n+1
(n 1n+1)lo0M
(=coss(8)
C cos(8))
nlo(k)
n(n + (x)
+ 00
nlo(k)
n
This proves that, asymptotically, the contribution the zero-order term of fvM to the probability of selecting is equal to the probability of selecting A using B-exp with the same x value.
To understand how fast vMF-exp reaches its asymptotic behavior, now need study Ro (0), the remainder of the Taylor series expansion of fvM around 0g.
B.2. Bounding of the Remainder Term
We start by computing the first derivative of fym:
[sin(0) cos(0)
AO [0, 2m), 15 x)]=
(43)
(rc)
which is bounded on 2m] by M =
xe" [o(x)-
According to the
inequality (Abramowitz & Stegun, 1948).
this in turn bounds the remainder term as follows:
A [0, 2m,, (R) S M| 0ul-
(44)
We note that tighter bound could be found by studying the second derivative, will not be necessary purpose of this proof.
17

---

Exploring Large Action Sets with Hyperspherical Embeddings using von Miscs-Fisher Sampling
In partieular, this inequality holds for every 0 100
9m-2n
0o )
and
0o+ 41
80+
Ro(0))
M Pol d0
8= 90 8 22
Euger
10+
go
M(0 0o) d0 +
M(O 0) do
0=
-0=00 2
(45)
M0 do
M0
0==
10=2m
M 31 (3n 27)²
The above inequality holds when considering the expected values over uniformly distributed X,:
Bo+
Ro(()) do I E 8,,8, [8]] + 9.,3, [(Sn -2xr)²
E 9r.
A= 2m
8
Var B1,8, [311 + (E
81,8, [311)² + Var M, 1(3, 2T)] + (E BI,8, 13, 2T))²²
M
8
M.
2 4
2 x 4m²
(46)
+
8 (n 1)2 2)
(n + 1)2
MT²
(n + 1) + 2)
0 n2
Since Binn S0=00t Ba 2m Ro( d0
S Birh poot eng2
[o(0))
we have shown:
Ro(0) d0 = 0 1
E 0r
(47)
n1
In summary, when combining the asymptotic behavior of the zero-order term and the remainder term, conclude that when d = 2 we have:
e cos(Oo)
PaME (A ni, 2,
+ O
(48)
nTo(k)
This proves Proposition 4.3 when 2. Note that, comparing the asymptotic expressions for PreeppA n, = 2, x) and PyMF-esp(A (A n, 2, k)), also gives us a proof for Proposition 4.1 when
18

---

Exploring Large Action Sets with Hyperspherical Embeddings using von Miscs-Fisher Sampling
C. Asymptotic Behavior of vMF Exploration in d > dimensions (Proofs of Proposition 4.3, Part
2, and of Proposition 4.4)
We now prove Proposition 4.3 when d >> 2, starting with series of intermediary lemmas. We subsequently justify the approximate expression of Proposition 4.4.
C.1. Intermediary Lemmas
We introduce series of lemmas regarding the properties of the Voronoi cell of A when Xn ~ ~d-1 We recall that, for given set of embedding vectors Xn, we use the notation Xn+1 = Xn U (A).
Lemma C.1. Let d N, d 2 AE A and n E N As before, let A(8d-1) denote the surface area of S Then:
A(S
E X. ~usu 1) A(Suvonor(A Xn+1))
(49)
+
Proof. To compute this expectation, one can notice that:
E (S--1))-1) A(S (A Xn+1)) E ((41~(((d-1)
A A(Svrnmaa (Xx+1 (x+1)) Xn+1 A]
(50)
Indeed, considering that A is known is equivalent to considering A as random vector Xn+1 ~ U(S with the constraint Xn+1 = A. We will now show that the right part of Equation (50) is actually independent of the value of A.
Consider any point A' E Sd-11 One can always define a (not necessarily unique) rotation RA.A' such that RA (A) = A'. Since rotations preserve inner products, they also preserve areas of Voronoi cells, which means that for given of vectors Xa+1, have:
A V (xx+1 Xx+1)) A Sirconal ( RA, (Xa+1)))
(51)
Moreover, the image the rotation of random vector uniformly distributed on the hypersphere is also uniformly distributed, which means that:
Xn+1 ~ u((a-1) + (A,,(() ~ (((
(52)
Therefore:
A A(Serrmmil Xn+1 Xn+1)) Xx+1 = A)
E (
E X, (x11-1((86-)) A(Svoronor [A, (X (X++1)
Xx+1 = A)
E (A (Ni (1) A ASrooooo (RR.A((Nnna (A44()))))) (X A']
(53)
= E (((())))) A A(Svooooaa A' (A' (A,)(())))))
= E x 1) A(Svoronor(A (A' {n))
This result proves that E x. --L Xx++))]] is independent of A. Then, use this information along with Equation (50) to obtain:
E xx A(Svoronor Xn+1)) x (((--11) A(Svornor (Xn+1 Zn+1).
(54)
Since Σ (SS (X: (n-1)) A(S (Du et al., 1999; 2010) and the X, are i.i.d., we derive:
X (((--11) A(S (a (X,-1 X 11n A(S
(55)
Combining Equations (50) with Equation (55) leads Equation (49), concluding the proof.
19

---

Exploring Large Action Sets with Hyperspherical Embeddings using von Miscs-Fisher Sampling
A
N(A n)
0
Figure 5. The Voronoi cell of A, Svinna (A X,41). along with the average normal vector of the cell ((4 n.) On expectation. (4 n) and are collincar.
Lemma C.2. Le A S and n E N Then:
YE E E.RE X. -(((
vav = AA.
(56)
V 1)xx+1)
Proof. We want to prove that the average normal vector of the Voronoï cell of A and A are collinear, as illustrated in Figure 5. To do so, we will show that this average normal vector is invariant to any rotation around A. For every 0 E [0, 2nr). we define RA as the rotation around of the angle 8. As discussed in the proof of Lemma C.I, Nr ~ U(($-1)) + (x,)(K ~ U (SS-11) Moreover, (A. = A. Let us denote:
[/
N(A n) = E X, ((s+-)))
VESumar V Xa+1)
var
(57)
the expected normal vector the Voronoï cell of A. Its image by the rotation RA, verifies:
RA.((N(A) n)) RAo x, x [ VESmoua(A12 I vdrl)
Vav
E x.-1(((0-1)) VESS Ra.(()at)))
(58)
/ E (1 VeSumm (A ((x44)))))
N(A n).
This proves that ((A n)) and A are collinear.
Lemma C.3. With the same hypotheses as Lemma C.2:
A(S
A
E x., 1, max .xi)
(59)
n +
20

---

Exploring Large Action Sets with Hyperspherical Embeddings using von Miscs-Fisher Sampling
Proof. À is defined follows:
/ (AS varj
AA = E X (((-)(
[/ (El varl. .11 .1)
(AY, A) = (E Xx (
A E X((e((s--1) VESSmar (AI (V. AV
(60)
VESmman (X (V. Xn+1) dv Xn+1 = =A]
À X 1)
A E X (X max(V, X:) dV Xn+1 = A
Moreover, as done in the proof of Lemma C.1, we can leverage the invariance by any rotation of the above expression to infer that the conditional expectation is actually independent of A:
// VES Xa+1)
À = E X
max(V, (o)((VX,)))) x.)
(61)
Since, in the above equation, X,+1 has the same distribution every element of X,+1, similar expression for À can be found using each X element. By summing them together, we obtain:
(n + 1)A
Σ 3=1
E X X ((s4-1)))11)
[/ (X,
max(V, X2) d
n+1
Σ
max (V, X,) d.)
E x,11)((((4-1))
VXSSmmn(X (X,1))+1)
j=1
(62)
Vega-1 max(V, ]V]
=
E X, x,11-11((5
A(Sa-1) max; (V, dv] A(Sd-1)
E X VESaLi
A(( E X EE Vruess 1 v,[max(V, xitl].
which proves the lemma
The last two lemmas are useful to describe the distribution of (V, X,) when V is fixed, Xn+1 ~ U(S0-1), and n is large.
Lemma C.4. Let B : (21, + f01 10--7 1)22-1 (1 dt denote the Beta function. Let d 2 3, V E Sa-1 and X be a random vector with X 1() Let Fradiat be the cumulative distribution function (CDF) of (V. X). The Taylor series expansion of Frudiat near is:
2²11
(d - B) 2-1) (1 - 1) d=1 +0((1 - 1) =z 1)
F Fradiat()) =1
(63)
21

---

Exploring Large Action Sets with Hyperspherical Embeddings using von Miscs-Fisher Sampling
Proof. The distribution of (V, has been studied in directional statisties (Mardia & Jupp, 2009). Its PDF is known to be:
(1 12) -
(tadia(t))
B d-1)
(1 -1+1 d=
B( d-1
(1 - t)=² " -1 (1 (1-t)
(64)
B 2
2 (11 1) 11
(1-1) =
(1-1)
B d=1
2
2
I (1 +
1 t
B
2
x=
The last line above was obtained using Newton's generalized binomial theorem for real exponent (Coolidge, 1949). It involves the term ( - with (-); the Pochhammer symbol used to designate falling factorial (Abramowitz & Stegun, 1948). We have obtained an expression of fradial involving an infinite weighted sum of powers of (1 t) with
exponents greater or equal to since 2 3. Therefore, by uniqueness of the Taylor polynomial, we derive that the Taylor
series expansion of fradial near is:
Sradial (1) 2 -1 (1 +
+ o((1 - 1) --11)
(65)
B d-1 2
Since by definition Fridial is the primitive of frndia on [-1, 1] and that (1) can integrate the above equation get:
2 2 2 (1 1)
Fradial (1) =1
o(11 1) 1)=²")
d-
B 3
d-1
2
(66)
2² (1 t) 4-1
= (d- 1) d11
+[((1
- t) #
Since this is exactly the Equation (63), this completes the proof.
Lemma C.5. Let d 3, V ga-1 and let Frudiat be defined as in Lemma C.4. For E N", let Xn ~ ((( be of i..dd random vectors uniformly distributed Sd-1, and let F,, be the CDF of max, (V, Xi). Then, for [-
lim Fa bn) c(-(1+)a) 5) 4
(67)
2 where y = I-I Og = ((d-1)B()
2 with B the Beta function, and by = d-I Ug.
2
Proof. The proof relies on the Fisher- hiipee-Tipeett Gnedenko couple of sequences o, and b, such that the left term of Equation (67) converges, then its limit should be the CDF of Generalized Extreme Value distribution (GEV) with shape parameter 7 which is the right term of Equation (67). Theorem 5 of Gnedenko (1943) provides a necessary and sufficient convergence condition for random variable with maximal value Tmax and CDF F, provided that < 0:
Tipeett-Gnedenko theorem (Gnedenko, 1943) which states that if there exists a
1 - F( Zmax vut)
(
lim 0-
for all u > 0.
(68)
F( xmax - 1)
22

---

Exploring Large Action Sets with Hyperspherical Embeddings using von Miscs-Fisher Sampling
Recall that Lemma C.4 gives us the Taylor expansion of Fradial near Fradial (t) K(1 -t =² + +o((1 =t)²²) Knowing that Tmax = 1, we obtain that, Vu >> 0:
with
K
1)
1 - Fradial (1 u tt
1 K(ut) (-(1-K(ut) + -
lim (-0+
lim 2-0+
radial (1 t)
1 - (1 K(t) +
K(ul) ' + +0((1)²²'
lim 1-00
(69)
((t) 4-1 + (((()) 2 ))
d-11
which guarantees convergence and in the same time gives the value of y 2
To find suitable sequences an and ba, we can use the fact that (t) = Frodial (t)" and study the behavior of In (t) near
I = 1:
In (1) In (Fradial (
n In (Frodial (t))
(70)
nlIn (1 K(1 - +) + o((11 - ()) as -- =n1K((1- 1) +(111 1) }) as 1 1
By defining on = ->(K))7, 1- (Kn) and doing the change of variable
E-by
we see that:
an
t = 0, + bn = 1 - (1 + ru) (Kn)².
(71)
Since for every lim (1 + (nn)7 0 (recall that y < 0), the term o( x) o( ) as n + +oo. this means that:
1 is equivalent to
In (a bn)) -nk ((1+ + (2) + (1)) as n -> +00.
(72)
=1 + 7u)) o(1) as n
We can now consider the exponential of the above expression get our asymptotic maximum distribution:
Pa + ba) = - lim ++0
(73)
which concludes the proof.
Corollary C.6. With I; 2: 10 e- dt the Gamma function (Abramowitz & Stegun, 1948), we have:
d-1 E x(-- ma X,) = (d- 1)B(1
((d+1)
21
(74)
n
71
Proof. According to the Portmanteau theorem (Billingsley, 2013), Lemma C.5 is equivalent to:
max,(V, (V,,)))))))))) bn D, GEV(?),
(75)
On
where GEV(?) a generalized extreme value distribution with shape parameter ? (Gnedenko, 1943). Recall that if a sequence Z,, Z2,... ... of random variables converges in distribution random variable Z, then for all bounded continuous
23

---

Exploring Large Action Sets with Hyperspherical Embeddings using von Miscs-Fisher Sampling
function 6. lim E (+(2,)) = [)).
Since max, (V.X.)
is bounded for every n, we can consider the identity
+=++0 function for e and obtain:
max; (V,X) bn E [GEV(>)] T(1 7) -1
lim E x x 1)
(76)
On
Replacing 7, an and bn by their respective expressions, implies that:
max; (V, .X)) - -1 (Kn) 2
E ((
d -
lim
17
(Kn)
d
(77)
E (((--11))
maxi(V Xi)
- -1 K
lim
0.
a-1
Since K 2
=
(d-1))B(
2 1-1
this is equivalent to writing:
(d (d-1)B
d-1
d
E Nr xx-0((50 (Vax(V - -1+ 2
= o
d
nd-11
(78)
+ E x(-d(1--11 [m, Xz) = - r d
(d-
1)B -
+ o
d - 1
nd-1
We have thus obtained Equation (74), concluding the proof of the corollary.
C.2. Proof of Proposition 4.3
We now return Proposition 4.3. In this section consider the of vMF-exp when d> 2 and X; embeddings uniformly distributed on gá-1, Under those assumptions:
PeM (a n, V, = SMM V1x))((4+1))
+ 0
(79)
n
Proof. Similarly to the 2 dimensional case, the definition of PaM n, d, V, vK is:
P. A n, d, V, k)) = E Xx-U(5=-1) |P(V E Sveromoi (A Xn+1) vMF(K,
(80)
which can be written using the PDF of the vMF distribution:
Us (SAnnc(A)(Xtt))
PaMr exp (A n, n, d, v.). = IE x. -(
fiMr(V V.K)dv
(81)
As done in the 2D case, we study the Taylor expansion of fyMP near A:
vV E SAamoussA 1x+1), (i kc V) = Ca(())a(VV))
= VV
(x(V, V i A))²
(82)
= SvMP(A VR
= fAME(A V1 KVV - - R
24

---

Exploring Large Action Sets with Hyperspherical Embeddings using von Miscs-Fisher Sampling
V
A
<,A>
O
Figure 6. For d = 3: vMF-exp explores the action A when V lies in its Voronoï coll, shown in red.
with (V) = = (<(VV-AI AWy, Leveraging the linearity property of both integration and expectation (Jacod & Protter, 2004), can study Pa (A n, d, V, by assessing separately the contribution of the different terms of the expansion of fYMF in:
PaMRes((A n, n,d. V,K)
(83)
SAMP(A [VAVV,)))) (1 + <VV VV +)+ + R()))
E x(--((1-11 VeSSmmnt (A Xu+1)
However, contrary to the 2D case where Svorooo (A) x is always defined as the arc between 2 angles on the circle, for d > 2 the shape of Svaromoi Xn+1) is highly dependent of the layout of the elements of Xr that share frontier with A. Figure 6 provides an illustration of the complexity and diversity of the shapes of Voronoï cells for uniformly sampled points on the 3D sphere.
As a consequence, expliciting the bounds of integration, as we did in the 2D case, can be somewhat tedious. Instead, we will leverage the geometrical properties of the problem hand estimate PoMP-cup(A (A n, d, V, K)). We start with the zero-order term.
C.2.1. ZERO-ORDER TERM
Since the zero-order term is constant, its integral over Svaromo (A Xn+1) can be expressed as:
SveSimndAAA [A A V,K)dv SMMr(A V, (() (A Xx+1));
(84)
where A(Svoronor (A| Xx+1)) is the value of the surface area of Svoronor (A Xx+1). To assess the expected value of the above equation for uniformly distributed Xn, we use Lemma C.1 and obtain:
[ (A forr (A V. R) (.Rdd di
fvMr( (A) V, (V)
E (()--1
(85)
n 1
fAMr(AA A V, A(
+ 0
n2
25

---

Exploring Large Action Sets with Hyperspherical Embeddings using von Miscs-Fisher Sampling
C.2.2. FIRST-ORDER TERM
We want estimate the value of:
E x.-U(s(r)) [vresnmmm (E SOME(A VV A)dU
(86)
(V, x VESMOnnrA (
(V, AVAA)484)))
fMMr(A] [OLA|VV,, KWKD
var
n
Using Lemmas C.2 and C.3 well as Corollary C.6, the left term inside the parentheses is:
// (AStmme(AAAA))))
(V. ((((())))))
var
AV A(S0-1)
E (K..U(S--1) max((VXX))
(87)
n n+1
(V,4) 115
r( ((#))
(d- (d-1) 1) الع
1
+ o n
n+1
2
Re-injecting this expression into Equation (86) gives the following expression for the contribution of the first-order term the probability of sampling A:
SNMP( (A V
V,K)s((VV - A)
E Xr ((
V (AI (1)xa+1))
(88)
di,
A(S
(d- 1. - T(d+1)
-fMPP(A V2K)
n+1 A(V
+ +o
2
n n
C.2.3. REMAINDER TERM
As done in the 2D proof, we leverage the Taylor-Lagrange inequality (Abramowitz & Stegun, 1948). The second derivative
of the function (xx) = Ca(n))*² is f(x))(2 n² fxr), which bounded on x E [-1,1] (1.1bby by M (x)ee This
implies that:
M(V, V- A)2
(V)
2
M M All2
(89)
(according the Cauchy-Schwarz inequality (Jacod & Protter, 2004))
2
= M(1 (V,
This inequality holds for every V &verrmoi Xx+1) when X, -((SS-1)), which means that:
(S4-1)
SAMP(A (()))
VESmmun (A1
S Smrr(A V,R) X. (S
M(1 (V, A)) av
A(S
fAMr(A V,K) n +
M(1 (Ssdree(Sdd
max(V, Xx) d
(90)
VESA-1
= fAMP[A| V, K. A(S
d-1
d=1 (d 1)B(
d
1
+ o
+1
2
n1
n
2
0
1+ 1-11
26

---

Exploring Large Action Sets with Hyperspherical Embeddings using von Mises-Fisher Sampling
We used Lemmas C.2 and C.3 to go from line 2 to 3, and Corollary C.6 to go from line to 4. In essence, have bounded the contribution of (V) to the probability of sampling A follows:
E X xama (S (ESS f.M (A (. dV 0
(91)
Finally, adding up Equations (85), (89), and (91), we conclude the proof of Proposition 4.3 for d 2 3 and (via the first-order term) simultancously justify the approximate probability (a n, V, k) introduced in Proposition 4.4.
27

---

Exploring Large Action Sets with Hyperspherical Embeddings using von Miscs-Fisher Sampling
D. Similar Asymptotic Behavior of B-exp and vMF-exp for Large Action Sets (Proof of Proposition 4.1)
Finally, Propositions 4.2 and 4.3 allow to derive Proposition 4.1, i.e., that in the setting of Section 4.1, we have:
lim ex n. d, V,K) +-+ PoMP-cxp (a n, d, V, =1
(92)
Proof. Acording to Proposition 4.2, we have:
ex n, v.). SMMP A V, ((K))
+ 0 nvn
(93)
Moreover, according to Proposition 4.3, we have:
P ep n. v.) SAME(A (A] (1K))(((=1))
(0 0
if if 2, ifd2
(94)
Therefore:
lim Pa n, d, V,x) +00 PeMI-eap (a n, d, V,K.)
lim ex (a n1 d, V,
t PoM (a n, V,
(AMr(A V.K)A(S*
(95)
fAME(A V, (x)))
1.
E. Link with Thompson Sampling
At first glance, one might draw some similarities between vMF-exp and Thompson Sampling (TS) with Gaussian prior for contextual bandits (Chapelle & Li, 201 Admittedly, vMF-exp shares a common spirit with TS, where action selection is preceded by sampling individual weights according to a Normal distribution centered on an observed context/state vector. However, -MF-exp also presents two major differences:
Firstly, in vMF-exp, vector sampling is performed according to a vMF hyperspherical distribution, centered on the state embedding vector V. This choice of distribution ensures that vectors with the same inner product with the state vector have the same probability of being sampled, as illustrated in Figure ((a). This aligns better with the similarity used to retrieve nearest neighbors and, emphasized in this paper, leads to probabilities of exploring actions asymptotically comparable to Boltzmann Exploration (with better scalability) under the theoretical assumptions of Section 4.1.
Secondly, vMF-exp is not designed to maximize the expected reward of a policy in an RL or contextual bandit environment and does not impose any parameter update strategy. Instead, serves as an action selection tool for any scenario where policy updates cannot be performed regularly (as in the batch RL setting commonly found industrial applications), yet broad exploration must still be guaranteed between consecutive updates.
28

---

Exploring Large Action Sets with Hyperspherical Embeddings using von Mises-Fisher Sampling
F. Sampling from the von Mises- Distribution
F.I Radial-tangent decomposition
Given a vector V sd-1 and a concentration x E 1R+, the algorithm described in (Pinzón & Jung, 2023) sample from vMF(V, x) by leveraging the radial-tanged -tagent decomposition of the elements of Sd-1, For any V E Sd-1, let us call T= (V, V). Then have:
= iv + /1 -1-22
(96)
where the vector Vo has a unit norm and is orthogonal to V.
E2. vMF distribution
If. xM)(K, then
is scalar valued random variable.
Vo is random vector uniformly distributed on the (d-2) dimensional sub-sphere that is centered at and perpendicular to V. For instance, for 3, this would mean a circle centered around V.
and Vo are independent.
Since the reciprocal is also true, & and Vo can thus be separately sampled obtain V.
F.3. Sampling i (V, V)
The PDF f known (Fisher, 1953) and follows:
(k/2) -1 EH (1 - 12) ب=ه
Frntial (1; d)
-² T 1g-1(n)
(97)
This PDF can be used to sample through rejection sampling (Gentle, 2009).
E44 Sampling Vo
Vo can be obtained by following the steps of algorithm 1.
Algorithm Sample Vo
1 Sample vector U uniformly from 5d-1,
2 - Compute projection of U on V: W (U, VVV: U-W
3 Subtract projection and normalize: Vo [1-
4 retuuurn Vo
Note that a simple way to sample U uniformly on Sd is to sample standard Gaussians independently (one for each dimension) and then normalize the resulting vector (Gentle, 2009).
F.S. Wrapping up
The vector V can now be computed by summing the right term of equation 97. Overall, we see that sampling V from vMF(V, k) data-independent, hence the scalability the approach.
29

---

Exploring Large Action Sets with Hyperspherical Embeddings using von Mises-Fisher Sampling
G. Additional Monte Carlo Simulations
1r-b
= 1.0, <V dm4
10-3
= 1.0, <V.A>=0.5, dm8
10-3
x=1.0, <V.A>=0.5, d=16
Ps(a)
Po(a)
135
Po(a)
252
Pr(a)
expla)
1.53
P:(a]
epp(a)
Pa espla)
Ar(a]
125
Powe .oupāā
Pwe - oxp(
Pwe- evpla)
100
1.00
5.75
0.75
1.7
0.30
0.25
02
6.4
0.6
0.2
3.5
32
3.4
0.5
3.0
1.5
02
3A
3.6
0.0
(b)
(c)
2--5
x= 1.0, <V.A>> -0.5, d=32
1--6
x= 1.0, <VV.2==0.3, d-64
1--5
K= 1.0. <V,A>> =0.5, d d-128
1.6
Pola)
Pyla)
1.6
Pota)
Psta)
P:la)
P:(a)
1.4
Po. cap
Ps ca)
Ps oula)
12
1.2
Fer (xp
PAr cxp(aa
Par (a)
2.0
1.0
2 0.0
3.5
58
0.5
5.2
52
0.
9.0
50
0.9
34c
14c
(d)
(e)
(I)
10.5
K= 1.0, <VVAA> 0.9, d=4
le-5
K- 2.0, <V,A>-D. 0.9, d-4
1e-5
K-2.0, <V.A>-0. 0.9, d-8
Pola)
Pola)
Po(a)
Pj(a)
Pi(a)
(((a)
2.0
Pa-wup())
Pa Pa-a
Per sup(a)
Puwr cag(a)
Powr esgla)
2.5
02
0.4
3.4
3.8
1.5
3.2
0.4
0.6
0.8
1.0
52
3.4
0.5
0.8
1.0
0
los
0
Jes
(h)
7--5
1.0, <VV,A> m.9, d=8
10-5
2.D, <V,A> =D.5, d=8
1e-5
2.0, <V. As =0 d=32
Pola)
Psla)
Po(a)
Pyla)
20
Prla)
(((a)
cpp(
Po (ap
Po (op)))
2.0
Pew Pap--
Par espla)
Puer mp)
3.5
3.0
3.5
0.5
0.4 3.5
0.4
3.8
0.5
16C
1nc
16t
(k)
(l)
Figure 7. We report complete results for the Monte Carlo simulations presented and discussed in Section 4.3, involving more combinations of d, K. and A). We recall that (a) and (a(a) are indistinguishable for this range of values. We emphasize that the y-axis on a le-5 scale; hence, all probabilitics are extremely close.
30

---

Exploring Large Action Sets with Hyperspherical Embeddings using von Miscs-Fisher Sampling
H. Additional Experiments on a Real-World Dataset of Glo Ve Word Embedding Vectors
While our main contributions in this work are theoretical, we aimed in the main paper to validate our key findings with Monte Carlo simulations, which involved synthetic data. Understanding that some readers may wish to further explore our topic through reproducible experiments on real-world data, we present an additional study in this Appendix H. This study experimentally validates the main properties of vMF-exp large-scale, publicly available real-workle dataset.
H.1. Experimental setting
We present vMF-exp experiments on real-world, publicly available data. Specifically, we compare the behaviors of B-exp and vMF-exp the Glo Ve-25 dataset of 1 million Glo Ve word embedding vectors with dimension d = 25 (Pennington et al., 2014). Each vector, learned using word2vec (Mikolov et al., 2013) from 2 billion tweets, represents a word token. We subtract the set's ss average from each vector and divide them by their norms. We obtain vector set, denoted G, with all vectors lying on the unit hypersphere, making GloVe-25 a relevant large-scale dataset for our study.
Our experiments follow the protocol outlined in Section 4.3 of the main paper. In this section, we compared the empirical probabilities PB exp(() and exMFeepp(0 (a) of sampling an action represented by a vector given a state vector V, for varying action numbers n and inner products (V, A). While we relied on Monte Carlo simulations with uniformly drawn vectors Xn ~ (S*-1)), in this Appendix H, vectors are sampled from G, with V and A also drawn from G such that AV matches the pre-selected values. Our goal is to empirically compare epla)p and expFee)(()) while verifying the claims that P1, P2. and P3 simultaneously hold for vMF-exp.
Finally, in our Sections 4.2 and 4.3, we provided analytical approximations of PB-esp(a) and PeM (a) in the presence of independent and identically distributed (i.i.d.) uniform embedding vectors. We will assess the usefulness of these approximations on these GloVe vectors, which do not strictly satisfy these strong assumptions.
Finally, regarding these experiments Veo we note that:
The Vl dataset is available for download at:
In our experiments, we use the Python vMF sampler from Pinzón & Jung (2023) to efficiently explore large action sets.
All results are reproducible using our source code:
com http:///.....eeeee////eeeeplaaaa
H.2. Results and Discussion
On P1 We now discuss our results. We first focus on P1. While B-exp requires computing (V, X,) and softmax values for all vectors X; Xn, vMF-exp only involves sampling d-dimensional vector (in constant time with respect to n)) and finding its approximate nearest neighbor (ANN) in Xz.
Table compares the performance of four popular ANN algorithms on GloVe-25. Following standard ANN literature (Simhadri et al., 2024), our performance metric is the maximum throughput, measured in queries per second (QPS), for which the average recall of the exact top-10 10 neighbors exceeds 90%. We also report the throughput of exhaustive search, as an indicator of B-exp's inefficiency.
Table 1 shows that exhaustive search yields throughput 2 orders of magnitude lower than ANN methods. This confirms the significantly better scalability (P1) of vMF-exp compared to B-exp.
Table 1. Performance of popular ANN algorithms Vlo extracted from the benchmark of Aumüller et al. (2017). Following Simhadri et al. (2024), our performance metric is the maximum throughput, measured in Queries Per Second (QPS), for which the average recall of the exact top-10 neighbors exceeds 90%. The evaluated algorithms include 2018), one from the Faiss library (Douze et al., 2024) and the other from NMSLIB (Boytsov & Naidan, 2013), as well as ScaNN (Guo al., 2020) and NGT-QG (Iwasaki & Miyazaki, 2018). Exhaustive search 2 to 3 orders of magnitude slower than ANN methods.
implementations of HNSW (Malkov & Yashunin,
Algorithm
Exhaustive Search
HNSW (Faiss)
HNSW (NMSLIB)
ScaNN
NGT-QG
Maximum Throughput
34
6197
14080
23436
22733
in Queries Per Second (QPS)
31

---

Exploring Large Action Sets with Hyperspherical Embeddings using von Miscs-Fisher Sampling
On P2 and P3 Figure compares B-oopp (a) and PxMF-csp(1) (a) for increasing values of and (V, A). Figure 8(a) highlights the properties that make B-exp popular in RL: the ability to sample actions with unrestricted radius (P2) and the ordering of sampling probabilities based on action similarity to V (P3).
Importantly, Figure 8(b) confirms that vMF-exp also satisfies both properties. In our tests, A always has positive sampling probability, which strictly increases with (V, A). Thus, vMF-exp also satisfies P2 and P3 on 2--2e-
On Theoretical Approximations Finally, Figure shows that, although GloVe vectors are not i.id. and uniform, the analytical approximations of the main paper for (B-esp(a) and PMM--pp (a) often remain accurate, particularly for B-exp. Also, vMF-exp closely matches B-exp's 's probabilities for low absolute values of A).
However, as (V, A)| increases, the gap between PxMF-ep (a) and ap)) grows more rapidly than predicted by approxi- mations, highlighting the limitations of the i.idd. and uniform assumptions and opening the way for future research more general expressions.
Conclusion This additional study confirmed the key theoretical and scalability properties of vMF-exp on a scale-scaleaaa and publicly available real-world dataset. Our results highlight its potential as a practical solution for exploring large action sets when hyperspherical embedding vectors represent these actions.
Glove-25, vMF-exp k=1 <V,A> [-0.9.0.9]
Glove-25, B-exp k=1, <V.A> E (.0.90099]
x10-
x10-+
1.2
0.9
7
5
0.0
0.8
Paer cela
Pe oxp(a)
0.3
4
0.6
0.0
0.3
2
0.0
20000 30000
40000 50000 60000 70000 80000 90000 100000
20000 30000 40000 50000 60000 90000 100000
b
Figure& 8. We report the empirical probabilities (a) and PoMPesy (a) of sampling action represented by a GloVe embedding vector A, using B-exp and vMF-exp. respectively, given state vector V. with 20000 S S 100000 and (V, A) E (0.9. 0.3, 0.0, -0.3, 0.9]. and with 25 and = Sampling is repeated 30 million times and averaged to obtain precise estimates. For both methods, the probability of sampling a for exploration is strictly positive (P2) and is strictly increasing function of the inner product similarity (V, (P3). Results remain consistent when is modified.
32

---

Exploring Large Action Sets with Hyperspherical Embeddings using von Mises-Fisher Sampling
1.0, <V.A==0.0:
Glove-25
X10m
K 1.0, <V.A>=0.3:
Glove-25
k 1.0, <V.A>=-0.3
Glove-25
Pola)
Pola)
Pola)
Pyla]
Pila)
P1(a)
Ps cpll)
Pe expla)
Pa - emp (a)
PIM
(a)
PuMF cxpla)
PuM cxp
0.6
P1a)
0.4
0.4
20000
40200
60000
20000
100000
(a)
(b)
(c)
K 1.0, <V.A==0.9:
Glove-25
K10>>
K= 1.0, -.AA==0099:
Glove-25
2.5
Pola)
Po(a)
Pl(a)
Pi(a)
Pe- Pe-expla)
Pa (ap)
Pure eap (a)
Puer (a)
3.5
0.5
(d)
(e)
Figure 9. We compare (a) and PaM (a) on GloVe-25 to the analytical approximations Po(a) and (i(a) stated in Propositions 4.1 to 4.4 of the main paper under the assumption of i.i.d. and uniformly distributed vectors. Our confirm the usefulness of these approximations on GloVe-25. The ycllow curve (Po(a)) is indistinguishable from the red curve ( (spesp(a) (a)), indicating that Proposition 4.2 holds across all configurations. Furthermore, PaM (a) (blue) remains close Pe ex (a) (red) for low absolute values of (V, A) (Figures 9a). 9b),, and 9())), anticipated by Propositions 4.1 and 4.3. In Figures 9b) and 9()). the small difference between PMM (a) and (a) aligns with the alternative expression P1 (a) (green) derived in Proposition 4.4. However. as (V,A)) increases (Figures 9(d) and 9())), the difference between vMF-exp and B-exp grows more rapidly than predicted by Proposition 4.4, highlighting the limitations of the i.idd. and uniform assumptions.
33

---

Exploring Large Action Sets with Hyperspherical Embeddings using von Miscs-Fisher Sampling
I. Application to Large-Scale Music Recommendation
Our analysis of vMF-exp in this paper was intentionally general, as the method can be applied to various problem settings. In this Appendix I. showcase a real-world application of vMF-exp.
L.I. Experimental Setting
We consider the "Mixes inspired by" feature of the global music streaming service Deezer'. This recommender system is deployed at scale and available on the homepage of this service (Bendada et al., 2023a). As shown in Figure 10, displays personalized shortlist of songs, selected from those previously liked by each user. A click on a song generates a playlist of 40 songs "inspired by" the initial one, with the aim of helping users discover music within catalog including several millions of recommendable songs.
Mixes inspired by...
Discover new tracks similar to your favourites
Under The Gun
Pastoral
I'm Real (feat. Ja Rule) by Jennifer Lopez
by
Loffler
Sirvelo Suni
Think
Day's by Hamrlet Minessian
Memory Box by Peter Cat Recording Co.
by Aretha Frenklin
Madan
Otan Hunu by Slim Young
The Number of the Beast by Iron Maiden
by Swiff Kelta
Figure 10. Interface of "Mixes inspired by" recommender system on the music streaming service Deezer.
To generate playlists, Deezer leverages collaborative filtering model (Koren & Bell, 2015). This model learns unit norm song embedding representations of dimension d 128 by factorizing mutual information matrix based song co-occurrences in various listening contexts, using singular value decomposition (SVD) (Banerjee & Roy, 2014; Briand et al., 2021; 2024). Inner product proximity in the resulting embedding space aims to reflect user preferences. When user selects an initial song, the model retrieves its embedding, then (approximately) identifies its neighbors in the embedding space using the efficient Faiss library (Johnson et al., 2019) for ANN. Currently, Deezer generates the entire playlist at once in production.
The service considering RL approaches to, instead, recommend songs one by one while adapting to user feedback on previous songs of the playlist (likes, skips, etc.). However, explained in Section 1, adopting such approaches would require exploring millions of possible actions/songs, significantly increasing the complexity of this task.
In this Appendix I, we continue generating "Mixes inspired by" playlists all at once, but take step towards RL by comparing three methods for exploring large action sets of millions of songs:
vMFF-exp: we use the embedding of the user's selected song as the initial state V. We sample a random state embedding V according to the vMF distribution, using the estimator of Banerjee al. (2005) tune (see Equation (4) of Sra (2012)). Finally, recommend the 40 nearest neighbors of V in the embedding space according to the ANN engine.
TB-exp: comparing vMF-exp to full B B-exp is practically intractable this scale. We compare vMF-exp TB- exp with similar K. We first retrieve the 500 nearest neighbors of the initial song in the embedding space, according to the ANN engine. Then, we generate the playlist by sampling 40 songs from these 500 using a truncated Boltzmann distribution.
Reference: we also compare vMF-exp to a baseline that retrieves the 500 nearest neighbors of the initial song using ANN, then shuffles them randomly to generate playlist of 40 songs.
In early 2024, we conducted an industrial-scat scale online A/B test on the music streaming service Deezer compare these exploration strategies in real conditions. The test involved millions of users worldwide, randomly split and unaware of the test.
'https: // www. deezer. wwt.eee.coomoooommmmmmmmooooe com/en/
34

---

Exploring Large Action Sets with Hyperspherical Embeddings using von Miscs-Fisher Sampling
1.2. Results and Discussion
Firstly, it is important highlight that we were able successfully deploy vMF-exp in Deezer's production environment, achieving sampling latency of just a few milliseconds, comparable to the other methods. This industrial deployment service used by millions of users daily basis confirms the claimed scalability of vMF-exp and its practical relevance for large-scale applications.
Using vMF-exp or TB-exp for exploration improved the daily number of recommended songs "liked" by users through "Mixes inspired by" (liking a song adds it to their list of favorites), compared to the reference bascline. For confidentiality, we do not report exact numbers of likes users in each cohort, but present relative rates with respect to the reference. On average, users exposed vMF-exp or TB-exp added 1 11% more recommended songs their playlists than the reference cohort. These differences observed between vMF-exp and TB-exp, showing that vMF-exp is competitive with TB-exp.
statistically signifieant the 1% level (p-value < 0.01). No apparent differences were
In addition, vMF-exp. which does not suffer from the restricted radius of TB-exp, recommended more diverse playlists. We measured the average Jaccard similarity (Tan et al., 2016) of playlists generated from the same initial selection, to assess how similar the songs sampled from the same state embedding were, for each method. Results reveal that TB-exp had an average Jaccard similarity 35% higher (less diverse playlists) than vMF-exp, statistically significant difference the 1% substantial exploration, without compromising performance.
level (p-value < 0.01). Therefore, vMFF-epp allowed for
At the time of writing, Deezer continues use vMF-exp for "Mixes inspired by" recommendations. Playlists are still generated at once, but our work equips this service with an effective strategy to explore their large and embedded action set of millions of songs. This opens interesting avenues for further investigation of RL for recommendation. In the near future, Deezer will launch tests involving actor-critic RL models (Konda & Tsitsiklis, 1999; Sutton & Barto, 2018) to explore and generate songs sequentially based on user feedback.
35


Reviews:
[{"review_id": "m1OUsta3tV", "reviewer": "Reviewer_gBBS", "summary": "This paper proposes a method called vMF-exp: a method for exploration in tasks with large action spaces. One such task is recommender systems, where there are millions of categories to choose from. The paper discusses 3 important properties in order to have good exploration: 1. scalability to sample actions from a large search space; 2) high radius to have some probability of sampling every action; 3) order preservation where the probability of selection of an action depends on some similarity metric. The paper then discusses the problems with existing methods like $\\epsilon$-greedy, Boltzmann exploration, and Truncated Boltzmann exploration~(TB-exp). A method called vMF-Exploration is proposed which satisfies these properties. A/B testing is conducted where the vMF-exp performs similarly to the TB-exp on a music recommendation platform.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Point 2**\n\nWe begin with Point 2, which we understand to be the reviewer’s primary concern. \n\nThis point appears to stem from a misunderstanding, as our paper does, in fact, include extensive experiments on a publicly available real-world dataset.\n\nSpecifically, Section 5 and Appendix H present an in-depth experimental validation of the scalability and theoretical properties of vMF-exp, using a large-scale dataset of publicly available GloVe word embeddings. These experiments reinforce the conclusions of the paper. In particular, they demonstrate that actions consistently receive a positive sampling probability (Property P2 – unrestricted radius), which, by design, TB-exp fails to achieve. Moreover, the experiments validate the practical relevance of Properties 4.1 to 4.4 derived in our theoretical analysis when applied to real-world data.\n\nWe have made our source code publicly available to ensure full reproducibility.\n\nWe hope this clarification will help address the reviewer's reservations regarding the evaluation of the method.\n\n*P.S.* We plan to add a figure to the A/B test discussion to clearly illustrate that, in this A/B test setting as well, all actions receive a positive sampling probability under vMF-exp; unlike TB-exp, where probabilities are set to zero beyond the top-500 radius. We hope this additional plot will reinforce the message of the A/B test, which not only demonstrates the practical value of vMF-exp through its successful deployment at scale for music recommendation to millions of users, but also highlights its ability to support broader exploration without compromising performance.\n\n**Point 1**\n\nWhile two other reviewers found the paper to be *\"extremely well written\"* and *\"well written and easy to follow,\"*  we understand the reviewer's comment and would like to clarify the motivation behind the structure and focus of the paper, which may help contextualize our presentation choices. \n\nAs stated in the paper, the primary objective of this work is to introduce vMF-exp and provide a rigorous mathematical analysis of its exploration behavior over large action sets. In this sense, the paper is positioned primarily as a theoretical contribution, one that could have been presented as a purely theoretical article. The experimental results were intended as a complement to the theoretical findings, offering empirical insights and illustrating the applicability of vMF-exp beyond mathematical results. This motivation guided our decision to place these experiments in the appendix in order to preserve focus in the main text.\n\nThat said, we appreciate the reviewer's suggestion. We will consider creating a summary table to better articulate the key differences among methods and improve accessibility. Moreover, in a future arXiv version of the article, where space constraints are not an issue, we will consider moving both experiments on GloVe public data and the A/B test into the main body of the paper.\n\n**Point 3**\n\nThe mentioned paper deals with correcting importance sampling estimators of bandit algorithms when the action set is extremely large. To reduce variance, they make the explicit assumption that most actions are irrelevant, assigning them a non-learnable minimal reward and stabilizing the computation of the expected reward for a learnable policy. \n\nHowever, they explicitly state that they do not provide a solution to identify the subset of relevant actions to explore, and instead resort to \"a greedy heuristic,\" namely top-$p$ sampling with $p = 20$, followed by softmax, i.e., TB-exp with $m = 20$. Our exploration method could be combined with their training approach for a potentially stronger algorithm (in our case, the set of relevant actions can vary depending on $x$, which constitutes a meaningful improvement over the fixed-size greedy top-$p$ selection). \n\nIt is interesting to note that, as a future direction, they mention developing methods to *\"further help in incorporating prior knowledge about the reward function\"*... which is precisely what vMF-exp sampling is about.", "claims_and_evidence": "The paper motivates the importance of efficient exploration for the application of recommender systems. However, the proposed method vMF performs similarly to the known truncated Boltzmann exploration. It is unclear is the proposed method helped with exploration in the action space. \n\nIt is unclear if the proposed method is helping with exploration in web-scale recommender systems. As discussed in the paper, TB-exp suffers from exploration issues because of the fixed radius while sampling exploratory action (P2), it would be interesting to see what fraction of actions were sampled outside this radius and how often that was a good action.", "methods_and_evaluation_criteria": "The paper does not compare with any open-source datasets used to test the claim over recommender systems. Another concern is that only A/B testing results are reported and there are no analysis on where the gains are coming from.", "theoretical_claims": "I checked Proposition 4.1-4.3.", "experimental_designs_or_analyses": "I checked Appendix I where the paper discusses the experiments and results of A/B testing.", "relation_to_broader_scientific_literature": "Exploration is challenging in web-scale recommendation systems due to large action spaces. Moreover, A/B testing is hard as the random exploratory actions can be irrelevant. Any method that improves this exploration is applicable for retrieval in web-scale recommendation systems.", "essential_references_not_discussed": "NA", "other_strengths_and_weaknesses": "1. The paper is not well-written. The paper talks about importance of exploration in recommendation systems, but all the results of A/B testing are pushed to the Appendix. The main experiments should be in the main paper. The discussion on properties P1-P3 and the existing methods is verbose and having a simple table will help articulate this better.\n\n2. Another concern is that the A/B testing results are not convincing. The paper would benefit from experiments on a public dataset.\n\n3. How does vMF-exp compare to algorithms for eXtreme Multi-Label Classification (XC) like [1]? \n\n[1] Lopez et al., Learning from eXtreme Bandit Feedback, 2020", "other_comments_or_suggestions": "NA", "questions_for_authors": "NA", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "xr0QV8mSI7", "reviewer": "Reviewer_sVYv", "summary": "This paper addresses the challenge of exploration in reinforcement learning (RL) when the action space is extremely large, as in real-world recommendation systems like music streaming platforms. Traditional exploration strategies such as Boltzmann exploration and epsilon-greedy become inefficient or intractable in these settings, especially when millions of actions are involved and many are irrelevant. A common workaround, truncated Boltzmann exploration (TB-exp), limits exploration to a small subset of actions, but this may hinder optimal performance.\n\nThe authors propose a new method, von Mises-Fisher exploration (vMF-exp), designed for large-scale RL tasks where actions are represented by embedding vectors on a unit hypersphere. vMF-exp samples a direction using a von Mises-Fisher distribution and explores actions in that direction, allowing scalable and informative exploration. The paper provides a theoretical analysis showing that vMF-exp retains key properties of Boltzmann exploration in certain regimes while being computationally efficient. Empirical results, including real-world deployment on a music streaming platform, support the method’s effectiveness. A public Python implementation is also provided.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**On the uniform distribution**\n\nThe reviewer highlights an important point. We agree that the assumption of a uniform distribution over the hypersphere is strong and may not hold in practical settings. However, we would like to emphasize that the vMF-exp method itself remains fully applicable regardless of the distribution of action embeddings. Most of its key properties, such as scalability and unrestricted radius, do not rely on the uniformity assumption. Uniformity is used solely to derive the asymptotic equivalence with B-exp and to obtain the analytical approximations presented in Propositions 4.1 to 4.4. \n\nInterestingly, our experiments on the publicly available GloVe word embedding dataset (Appendix H) suggest that, although these real-world vectors are clearly not uniformly distributed, the analytical approximations from Propositions 4.1 and 4.4 remain accurate in most cases. Moreover, the A/B testing conducted on the music streaming service (Appendix I) further showcases the practical effectiveness of vMF-exp in an industrial-scale, real-world scenario where, again, the action embeddings are not sampled uniformly. \n\nTaken together, these results highlight the robustness and practical relevance of vMF-exp beyond the idealized uniform setting of our theoretical study.\n\n\n**On the potential over-sampling of isolated actions with large Voronoi cells**\n\nThe reviewer raises an interesting question. In practice, a large Voronoi cell simply implies that a given action is more likely to be sampled than an equally undesirable action with a smaller Voronoi cell, but *not necessarily* that it would be sampled disproportionately overall. When Property P3 holds, the sampling probabilities remain aligned with action relevance. That is, undesirable actions, even those with large Voronoi cells, will still receive lower sampling probabilities than more desirable ones. Therefore, the ranking of actions by relevance is preserved, and the method does not favor undesirable actions in an uncontrolled manner. \n\nThat said, the reviewer's comment opens up interesting avenues for additional research related to exploration in the\npresence of outliers. We detail below a proposal for a future research agenda tackling the specific problem of outliers management in the context of a the scalable sampling method proposed in this submission:\n* *Prevalence of isolated points in real-world datasets of embeddings:* the first step would be to determine if real-world embeddings actually exhibit isolated points with larger Voronoi cell overly attracting nearest neighbor search. Theoretical approaches using tools from statistical theory, such as Mardia's multivariate kurtosis, and empirical approaches based on Monte Carlo estimation of the surface of Voronoi cells can both be considered for this task. \n* *Impact of oversampling isolated actions on model training and reward*: in case that isolated points frequently occur, a follow-up research question would be to determine the impact on observed rewards and model training, which wouldn't necessarily be negative. Indeed, actions embedded close to one another are likely to provide a similar reward, thus carrying redundant information when selected. A method undersampling those actions in favor of isolated ones could thus provide more diverse batches for training, potentially accelerating convergence of bandit and reinforcement learning approaches, all the while introducing diversity in the selected actions which in the case of a recommender system can provide a more interesting experience.\n* *Correcting for oversampling of isolated points*: while the von Mises-Fisher distribution samples vectors isotropically around its mean direction, other distributions from the directional statistics literature can be considered. One interesting candidate could be the Fisher–Bingham distribution, whose probability density function is given by:\n$$f(\\tilde{V} | {V}, {\\Sigma}) = \\frac{\\exp ( - \\frac{1}{2} \\tilde{V}^\\top {\\Sigma} \\tilde{V} + \\tilde{V}^{\\top}\\Sigma V ) }{C({\\mu}, {\\Sigma} )} $$\nwhere $\\Sigma$ is a full rank, square concentration matrix, that can be fitted from embeddings in the neighborhood of the context vector $V$ to account for anisotropy, thus favoring denser areas around $V$ containing more embeddings.", "claims_and_evidence": "Claims and supported by mathematical statements and experiments.", "methods_and_evaluation_criteria": "They seem to make sense.", "theoretical_claims": "I did not check the correctness of the proofs.", "experimental_designs_or_analyses": "I didn't check in detail.", "relation_to_broader_scientific_literature": "The works builds on the broader research effort of designing scalable exploration strategies in large action spaces.", "essential_references_not_discussed": "NA", "other_strengths_and_weaknesses": "Main weakness: While vMF-exp offers a more scalable alternative to B-exp, its theoretical justification relies on a regime where action embeddings are sampled uniformly at random from the hypersphere—a setting that is unlikely to reflect the structure of real-world datasets. Moreover, vMF-exp tends to assign higher sampling probability to isolated actions (i.e., those with large Voronoi cells), which may not be desirable. For example, in a music recommendation context, this could lead to disproportionately sampling songs from niche genres unrelated to a user’s preferences. This behavior raises concerns about the method’s practical suitability, and as a result, I remain unconvinced that vMF-exp is the right scalable solution for exploration in large action spaces. With that said, experimental results still look promising.", "other_comments_or_suggestions": "Paper is well written and easy to follow.", "questions_for_authors": "Can you address the weakness that I pointed out.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "1I4IhHM0Y1", "reviewer": "Reviewer_xRgZ", "summary": "Summary: The authors propose to improve exploration for very large actions spaces (e.g., millions of samples). This work attempts to overcome the main limitation of Boltzmann exploration for high dimensional actions spaces which requires calculating cosine similarities between the reference sample and all other samples. The proposed exploration method using von Mises-Fisher sampling improves upon this by setting probabilities for exploration depending on whether a candidate sample is near the current sample according to a voronoi cell in a hypersphere. Thus the calculation for the exploration probabilities can be kept constant with regards to the number of actions.\n\n\n### Update after rebuttal\n\nI appreciate the authors responses. I think this is a very well written paper with clear desiderata that are needed for sampling in very large action spaces. Even though the experimental section is limited in its thoroughness, I think the authors rather convincingly show that their method is effective. I will keep my score of accept.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**On the possible distribution of embeddings**\n\nRegarding your concern, vMF sampling is applicable to a wide range of embedding distributions and is not restricted to the uniform distribution on the sphere, which we assumed in part of the theoretical analysis in Section 4. vMF sampling operates by identifying approximate nearest neighbors based on inner products in a d-dimensional hypersphere. Equivalently, it can be understood as finding nearest neighbors using cosine similarity in a d-dimensional Euclidean space. Unlike Euclidean distance, cosine similarity is inherently bounded between -1 and 1, making our approach robust even when embeddings are far apart in Euclidean terms.\nTo assess the behavior of our method for both low and high inner product similarity values, we provide in Figure 9 (Appendix H) an analysis of vMF sampling on the real-world dataset of GloVe-25 embeddings, considering cases where the action to be sampled has a similarity of -0.9 and +0.9 with the context vector. These plots demonstrate that while vMF exploration behaves differently from Boltzmann exploration, it still satisfies properties P1, P2, and P3 outlined in Section 2, reinforcing its practical applicability.\n\n\n**On the particular case of discrete features**\n\nYou also raise an interesting question regarding the behavior of vMF sampling when features are discrete. This is particularly relevant in the context of embedding quantization, which reduces memory usage and accelerates similarity computations by decreasing the number of bitwise comparisons. In this scenario, it is again important to highlight that cosine similarities remain bounded between -1 and 1, ensuring that approximate nearest neighbor search remains feasible.\nA potential challenge in highly quantized embeddings is that the set of possible inner product similarities becomes discrete, potentially leading to ambiguity when multiple points have identical similarities to the context vector. However, this issue arises even in Boltzmann exploration, as it also depends on computing inner product similarities before sampling actions. Moreover, even when embeddings are discrete, sampling from a vMF distribution around a discrete state embedding $V$ produces a new state vector $\\tilde{V}$ with continuous features, mitigating the aforementioned issue.\n\n\n**On additional applications beyond music recommendation**\n\nIt is worth noting that although the submission has recurrently referred to the example of music recommendation, other recommendation scenarios involving very large catalogs can be considered. To illustrate this, we refer to the paper [1] mentioned by Reviewer gBBS. In this paper, which deals with the task of extreme classification, a dataset of Amazon products with 670,000 different labels is considered for evaluation. More generally, extreme classification is an active area of research that involves different sorts of applications, and for which a benchmark can be found at http://manikvarma.org/downloads/XC/XMLRepository.html\n\n[1] Lopez et al., Learning from eXtreme Bandit Feedback, 2020", "claims_and_evidence": "The paper is extremely well written. The authors propose a set of conditions that need to be met for efficient exploration in high-dimensional spaces and explain how their method fulfills all these conditions in comparison to other methods. Furthermore, an exhaustive analysis is performed of the exploration behaviour when using von Mises-Fisher sampling.", "methods_and_evaluation_criteria": "The authors clearly identify issues with current Boltzmann exploration, which is its inefficiency when dealing with millions of samples. However, the authors go further by proposing a set of desiderate that an exploration algorithm should have for their intended purpose: Scalability, Unrestricted radius, Order preservation. I believe these criteria are sensible for the problem contstraints.\n\nThe authors scrutinise random, boltzmann and von mises-fisher exploration under these criteria and show that their proposed method fulfills all of these criteria.", "theoretical_claims": "I did not check every claim in detail, although most justifications follow logically  if one is familiar with the discussed methods. In any case, the authors show in Figure 2, that their proposed method holds the properties that were derived for their proposed method.", "experimental_designs_or_analyses": "I think the authors do a commendable effort on studying the effectiveness of their method and on whether it improves upon Boltzmann exploration. While concrete benchmarks results are not available, given the theoretical guarantees and the synthetic analysis it is likely that the proposed method will perform better. \n\nThe authors also provide a meta analysis of a field study performed on a large streaming service.", "relation_to_broader_scientific_literature": "I think this is an interesting problem to address from a technical perspective. However, the problem is quite constrained to the proposed issue of music recommendations. I wonder how well the von Mises-Fisher sampling would work when embeddings are not as \"close\" in euclidean space. \n\nI would like to see the authors address more limitations regarding the type of embeddings that can be used with their proposed methods.", "essential_references_not_discussed": "None", "other_strengths_and_weaknesses": "None", "other_comments_or_suggestions": "None", "questions_for_authors": "- How well would the method work for embeddings composed of discrete features? As I understand it, von Mises-Fisher sampling relies on neighbourhoods between samples to be reasonably close to each other. What happens when features are distant in euclidean space.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "djn2Hp0YuX", "reviewer": "Reviewer_Rb4B", "summary": "The paper considers exploration in large action spaces where simple baselines like epsilon-greedy are impractical. The authors motivate that prior SoTA on this problem uses approximate nearest neighbor search to inform a truncated version of Boltzmann exploration, which does not have a clean theoretical characterization. By contrast, the authors propose Von Mises Fisher  exploration to directly sample the action embedded in a unit sphere, with exploration asymptotically matching that of Boltzmann exploration. This is combined with experimental evidence to support the theory along with a theoretical comparison to boltzmann exploration.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**On the interpretation of the algorithm**\n\nThe interpretation of our algorithm as a way of accounting for the uncertainty in the query embedding is extremely interesting and will be further investigated in subsequent work. Indeed, the operation of sampling $\\tilde{V}$ from a directional distribution, such as von Mises-Fisher, around the initial state vector $V$ can be understood as the embedding equivalent of reformulating a query in information retrieval tasks. With our method, the extent to which the query embedding can be reformulated is entirely controlled by the parameter $\\kappa$, which can either remain constant across the hypersphere (as in our offline experiments in Section 4.3 and Appendix H) or depend on additional information, such as the local density of embeddings (as in the real-world A/B test detailed in Appendix I).\n\nAs the need for reformulation generally arises when the intent behind the query is ambiguous, this could explain why our method benefits recommender systems based on vector searches. Since users do not explicitly formulate their needs, the system must infer them from past user actions, leaving plenty of room for uncertainty. To investigate this hypothesis, in future experiments, we will consider calibrating the concentration parameter $\\kappa$ of the von Mises-Fisher distribution to an independent estimate of the uncertainty of the current query embedding. The impact of such an approach on the observed reward should provide valuable insights into the relevance of this interpretation.\n\n\n**On the uniform distribution assumption**\n\nThis aspect was also noted by Reviewer sVYv, and overall, we agree that the assumption of a uniform distribution over the hypersphere is strong and may not hold in practical settings. However, we emphasize that the vMF-exp method itself remains fully applicable regardless of the distribution of action embeddings. Most of its key properties, such as scalability and unrestricted radius, do not rely on the uniformity assumption. Uniformity is used solely to derive the asymptotic equivalence with B-exp and to obtain the analytical approximations presented in Propositions 4.1 to 4.4. Furthermore, the non-trivial proof detailed from Appendices A to D provides a useful foundation for future attempts at deriving a more general result akin to Propositions 4.1 to 4.4 under relaxed assumptions.\n\nInterestingly, our experiments on the publicly available GloVe word embedding dataset (Appendix H) suggest that, although these real-world vectors are clearly not uniformly distributed, the analytical approximations from Propositions 4.1 and 4.4 remain accurate in most cases. Moreover, the A/B testing conducted on the music streaming service (Appendix I) further showcases the practical effectiveness of vMF-exp in an industrial-scale, real-world scenario where, again, the action embeddings are not sampled uniformly.\n\nTaken together, these results highlight the robustness and practical relevance of vMF-exp beyond the idealized uniform setting of our theoretical study.\n\n**On the case of heavily imbalanced samples**\n\nIt is true that, under a heavily imbalanced distribution of action embeddings, actions associated with larger Voronoi cells may \"attract the nearest neighbor search to them.\" However, we emphasize that the sampling density of the vMF distribution is still modulated by the inner product similarity between the state and action embeddings. In other words, even if an action has a large Voronoi cell, a very low similarity with the current state will significantly reduce its sampling probability. This mitigates the risk of over-sampling irrelevant actions solely due to geometric imbalance.\n\nRegarding how much more frequently such an action might be sampled compared to vanilla Boltzmann exploration, the answer is inherently distribution-dependent. The reviewer’s comment highlights an interesting direction for future theoretical investigation into the different behaviors of B-exp and vMF-exp under heavily imbalanced embedding distributions. We will consider discussing this aspect explicitly in the limitations and future work section of the paper.\n\nThe outline of this future research agenda should be as follows:\n\n- Assess the extent to which real-world distributions exhibit outliers with large Voronoi cells.\n- Evaluate the impact of over-sampling isolated vectors (and under-sampling potentially redundant actions) on the training of models in a batch-learning setting.\n- Consider alternative distributions from directional statistics that allow for anisotropic sampling, such as the Fisher-Bingham distribution, to balance the oversampling of isolated points.\n\nMore details about this research agenda can be found in our response to Reviewer sVYv.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "I believe the assumption of uniformity in the distribution of the action embeddings makes the result less interesting. On the other hand, with a heavily imbalanced sample of the action embeddings, a very low probability embedding could nevertheless end up being sampled much more significantly with the proposed strategy due to a large voronoi cell attracting the nearest neighbor search to it, which would nevertheless not get sampled in vanilla Boltzmann exploration. \n\nHaving said that, I believe the authors allude to something like this in the limitations and future work section.", "experimental_designs_or_analyses": "The authors explore the performance for non iid embeddings like the Glove Vectors in the appendix and a real world deployment where they claim it showed benefits, though the baseline is unclear. While the authors compare with Boltzmann exploration, given the motivation in the introduction it would be interesting to also compare to the truncated boltzmann distribution (similar to the wolpertinger policy) which seems to be missing.", "relation_to_broader_scientific_literature": "The authors introduce a new and simple exploration strategy that involves sampling a unit embedding from the vonmises fisher distribution and then running a cheap ann search as the exploration mechanism. This is in contrast to prior work that proposed truncated Boltzmann exploration for similar problems (TB-exp with several references listed in the paper)", "essential_references_not_discussed": "n/a", "other_strengths_and_weaknesses": "Strengths: Simple exploration strategy that's intuitively easy to appreciate and simple to implement. Proof of evidence of deployment with clear benefits recognized in a production setting is impressive.\n\nWeaknesses: The justification for why this is a good idea makes a uniformity assumption on the embeddings which doesn't seem very accurate, and more importantly, the proposed reasoning for why this helps does not appear to hold when violating this assumption. It is plausible that the scheme is still a good idea for other reasons, but I am not sure the current theory indicates anything of that sort.", "other_comments_or_suggestions": "n/a", "questions_for_authors": "Have you considered interpreting the algorithm as accounting for uncertainty in the query embedding?  I wonder if that might give an alternate potential justification for why this could be a good idea, especially when the catalogue embeddings are not uniformly distributed on the hyper-sphere.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_flag": "Flag this paper for an ethics review."}}]

Author rebuttal:

Meta-review: This paper proposes a new method, vMF-exp, for exploration in settings with very large action spaces, such as recommendation systems. The approach uses the von Mises-Fisher distribution to sample exploratory actions based on embeddings, aiming for better computational efficiency than prior methods. A notable strength mentioned by reviewers is its reported deployment and positive results in a real-world music recommendation system. Some also found the paper's explanation of desired exploration properties helpful.

However, reviewers identified several weaknesses. The theoretical explanation relies on an assumption about action embeddings being uniformly distributed, which may not be realistic. Some reviewers found the experimental results unconvincing because the A/B test performance was similar to an existing method (TB-exp), and the paper lacked clear evidence or analysis showing improved exploration. Concerns were also raised that the method might sample isolated or irrelevant actions too often. Issues with writing clarity and the lack of experiments on public datasets were also mentioned.

Overall, the assessment was mixed but leaned cautiously towards acceptance. The method addresses an important practical problem with an interesting approach, even though its justification and testing have limitations.
Decision: Accept (poster)