Exploring Large Action Sets with Hyperspherical Embeddings using von Mises-Fisher Sampling

Response to reviewer eaK7

Thank you for your insightful review. # Code Availability The code for reproducing the Monte Carlo simulations described in Section 4.3 was provided as a zip file in the Supplementary Material of our submission. Please let me know if you're having trouble accessing it, as in that case we may figure out with the Area Chairs an alternative way to share the code. The code randomly samples $N$ embeddings of dimension $d$, as well as a state vector $V$ and an action vector $A$ such that $<V,A>$ has the desired value. It then computes the probability of selecting action $A$ using both Boltzmann exploration and von Mises-Fisher exploration. The sampling has to be performed repeatedly (at least several times $N$, which is 1 million in Figure 2 and annex F of our paper) for the observed probability to be significant. The current code samples embeddings from a uniform spherical distribution, which is the one for which we derived theoretical guarantees that our method asymptotically behaves as Boltzmann exploration (Section 4 of the paper, with proofs spanning Appendices A to D). In the future we want to add the possibility to sample embeddings from other distributions, to assess both empirically and theoretically if a similar relationship can be found. # Additional Reproducible Experiments on a Public Dataset In response to the recurring and understandable concern expressed by reviewers that the online experiments presented in the papers can not be independently reproduced, we have performed additional experiments on a large scale public dataset of embeddings comparing the behavior of our method with the popular (but inefficient) Boltzmann sampling. We have thus submitted a revised version of our paper that includes an additional appendix (appendix H) thoroughly describing the experiments performed as well as their result. We will include the code for these experiments in our final submission. Due to the absence, to our knowledge, of large scale public datasets of embeddings for recommendations, we used instead the Glove-25 dataset [1] made of 1 million embeddings of dimension 25 representing word tokens, trained with Word2Vec on 2 billion tweets. The experiments show that, on this real-world dataset, **our method verifies the good properties described in Section 2 of our paper**. Moreover, the mathematical propositions derived in Section 4 of our paper under the simplifying assumption of uniform spherical distribution still help to anticipate most of the behavior of our method as well as Boltzmann sampling on this real-world dataset. This is especially interesting as in our opinion, **the theoretical analysis as well as the proofs provided are the main contribution** of our submission. The code for this additional experiments will be made public along the paper. # Online Experiments We understand that the manner in which results are reported in Section 5.1 aren't quantitatively informative of the performances of our method in its goal of fostering exploration in a very large discrete action space, and that it contrasts with how results on public benchmarks are usually reported. The reason we believe that Section 5 can still be valuable to the reader is two-fold: - It gives a concrete real-world example of an environment where the action space is made of millions of discrete actions represented by hyperspherical embeddings. - It shows that designing a dedicated exploration method for this problem, as opposed to using more common naive methods, does bring improvement, even though we unfortunately cannot precisely quantify it for confidentiality reasons. As such, these experiments were included to illustrate that the problem of very large action sets exploration is worth working on as it remains understudied despite its concrete applications. [1] Jeffrey Pennington, Richard Socher, and Christopher D. Manning. 2014. GloVe: Global Vectors for Word Representation. In Empirical Methods in Natural Language Processing (EMNLP). 1532– 1543.

Response to reviewer oFjd (Part 1/2)

Thank you for your feedback and for your questions. We especially appreciate that you value our theoretical results, as we believe they constitute the most significant contribution of our paper. We also understand that empirical evaluation and reproducibility are essential to produce qualitative research. # Simulations on Synthetic Data Simulations on synthetic data have already been performed and are described in Section 4.3 of the paper. The corresponding code has been provided as a zip file in the supplementary material of the submission. The code randomly samples $N$ embeddings of dimension $d$, as well as a state vector $V$ and an action vector $A$ such that $<V,A>$ has the desired value. It then computes the probability of selecting action $A$ using both Boltzmann exploration and von Mises-Fisher exploration. The sampling has to be performed repeatedly (at least several times $N$, which is 1 million in Figure 2 and annex F of our paper) for the observed probability to be significant. # Experiments on a Public Dataset of Embeddings In order to improve the evaluation performed in the paper, we have performed additional experiments on a large scale public dataset of embeddings comparing the behavior of our method with the popular (but inefficient) Boltzmann sampling. We have thus submitted a revised version of our paper that includes an additional appendix (appendix H) thoroughly describing the experiments performed as well as their result. We will include the code for these experiments in our final submission. Due to the absence, to our knowledge, of large scale public datasets of embeddings for recommendation, we used instead the Glove-25 dataset [3] made of 1 million embeddings of dimension 25 representing word tokens, trained with Word2Vec on 2 billion tweets. The experiments show that, on this real-world dataset, **our method verifies the good properties described in Section 2 of our paper**. Moreover, the mathematical propositions derived in Section 4 of our paper under the simplifying assumption of uniform spherical distribution stills helps to anticipate most of the behavior of our method as well as Boltzmann sampling on this real-world dataset. This is especially interesting as in our opinion, **the theoretical analysis as well as the proofs provided are the main contribution of our submission**. [3] Jeffrey Pennington, Richard Socher, and Christopher D. Manning. 2014. GloVe: Global Vectors for Word Representation. In Empirical Methods in Natural Language Processing (EMNLP). 1532– 1543.

Response to reviewer Reviewer rKBK (Part 1/2)

Thank you for your review and your questions. # Novelty of the Approach It is right that the approach builds on already existing methods of approximate nearest neighbors (ANN), however the method itself is novel as to the best of our knowledge such approach has never been proposed to perform exploration in very large discrete action spaces. More importantly, in the paper, **we prove the mathematical tie between Boltzmann exploration and von Mises-Fisher exploration** in a specific setting, and provide a non trivial proof for it (Appendices A to D). Although the problem of efficiently sampling from a softmax (i.e a Boltzmann distribution) when the number of choices is large is a notoriously difficult problem, to our knowledge this is the first time that an approach using a **continuous probability distribution**, for which sampling elements can be performed in constant time with, is proposed, with mathematically proven asymptotic properties. # Embedding Distribution Assumptions Here we would like to stress out that the uniform spherical assumption is only required to guarantee the theoretical results of Section 4. However, the method can still be employed, with scalability, **regardless of the distribution of the set of action embeddings**. To further highlight this point and to assess whether the theoretical findings apply to distributions other than the spherical uniform, we have performed some additional **experiments on a large public dataset of real-world embeddings** that we have included in the revised version of the paper (see below for details). # Motivations for von Mises-Fisher Exploration We apologize if the motivations for using von Mises-Fisher exploration were not clearly stated in the paper. We summarize below the arguments for using it in a setting where there is a very large action space, and refer to sections in the paper that develop those arguments: - Sampling from discrete distributions has a time complexity that grows linearly with the number of actions. This is problematic when there is a real-time constraint and the number of actions exceeds millions (Section 2.2). - By contrast, sampling from a continuous vector distribution has a constant time complexity with regard to the number of actions, and ANN methods have sublinear complexity, hence the two can be combined to perform **real-time sampling of discrete actions**, even when the number of actions exceeds millions (Section 3.2) - Of all continuous vector distributions, the von Mises-Fisher distribution has a probability density function that is proportional to the exponential of the dot product between the action vector and the state vector, just like the probability mass function of a Boltzmann distribution (Section 3.1). In fact, we mathematically show in the paper that if the number of actions is very large and the embeddings are uniformly distributed, Boltzmann exploration and von Mises-Fisher exploration become the same method, with the latter being scalable.

Response to Reviewer mgSr

Thank you for your review. It is correct that no section is explicitly named "related work" in our submission, however we listed the limitations of the (few) existing solutions to perform exploration in very large discrete action sets with millions of elements in Section 2.2 of our submission, and cited the paper [4] in Section 2.3 when introducing the von Mises-Fisher (vMF) distribution. We appreciate that you took the time to share several publications leveraging the vMF distribution in a RL context. However, to our understanding, these papers do not tackle the problem of exploration when actions space is discrete and very large. Below, we provide a brief summary, in our own words, of each of these publications. [1] This paper introduces an unsupervised pretraining objective for RL where the agent is allowed to interact with the environment without being informed of the reward obtained, and seeks to satisfy 2 objectives: - exploring the most "diverse" set of states, mathematically characterized by representing each state $s$ by a vector $\phi(s)$ and ensuring that the distribution of states visited by the policy has maximal entropy. - ensuring that given a task, defined by a vector $w$, the set of states explored is relevant to this task. A state $s$ is considered relevant to the task if $<w,\phi(s)>$ is high, which is equivalent to saying that $s$ has a high log-likelihood of being sampled from vMF$(w, 1)$. The paper does not deal with the problem of sampling actions when the action set is very large; indeed, on line 8 of Algorithm 1, it is stated that they use $\epsilon$-greedy to sample actions during the data collection phase, and we have explained in Section 2.2 of our paper why it is not possible when the action set is very large (millions of actions), whereas their experiments are run on the suite of Atari games where __the maximum number of actions is 18__. [2] This papers studies the problem of helping an agent navigate in an environment that is either a 2D or 3D flow with unknown dynamics. During episodes, the agent is pushed forward by a constant velocity vector, and the goal at each time step is to decide the orientation of the agent. Thus, the problem is modeled as a POMPD where, unlike our setting, __the action space is continuous__ and gives the orientation for the agent. Performances of Q-learning, A2C and PPO are compared. For A2C and PPO, action is sampled from a vMF distribution centered on a vector predicted by a neural-network actor, which makes more sense than the more common Gaussian distribution because the action to be selected represents a direction instead of a position, but this paper does not deal with the problem of sampling from large discrete action spaces. [3] This papers studies how to imitate expert behavior when successive states of expert trajectories are available, but actual actions taken are unknown. Their method represents states in a latent space, and the parameters of the function representing states are learned by performing gradient ascent on an expected cumulated reward. To compute this gradient, the distribution of the shift between two subsequent states is assumed to be a vMF centered on the current sub-goal representation (defined in the paper). Here __vMF is not used to sample actions__; it is said in Section 3.1 that when running the agent in an environment to augment dataset, the action to be performed at each time step is selected __greedily__. This is possible because the experiments are run on a suite of 5 environments related to the Doom game for which the maximum number of available actions is 7, contrasting with our settings where actions range in millions. [4] This paper deals with the issue of using the gradients of an ensemble of critics when improving a policy. As the critics may highly disagree on the value of taking an action given a state, their respective gradients may also disagree about the direction towards which a parameter update should be made. The authors propose to assign during training a value of gradient uncertainty to each transition of the replay buffer, and sample transitions based on the level of certainty on the gradient's direction. This certainty is computed by taking, for each transition, the set of gradient vectors of the ensemble of critics, and fitting a vMF distribution using the same method we refer to in our online experiments of Section 5.1. The concentration parameter $kappa$ of the distribution is then used as certainty. The experiments that they describe are performed on Mujoco robotic control environments, where __action spaces are continuous__ and multi-dimensional, and so they do not deal with sampling from large discrete action spaces. All of the above articles share the common property of dealing with data where direction matters more than position, and so does our contribution, but none of them tackles the problem of sampling from extremely large discrete action sets, which is an active problem.