Nicolò Cesa-Bianchi
email: nicolo.cesa-bianchi@unimi.it

Claudio Gentile
email: cla.gentile@gmail.com

Gábor Lugosi
email: gabor.lugosi@gmail.com

Gergely Neu
email: gergely.neu@gmail.com

Boltzmann Exploration Done Right

Boltzmann exploration is a classic strategy for sequential decision-making under uncertainty, and is one of the most standard tools in Reinforcement Learning (RL). Despite its widespread use, there is virtually no theoretical understanding about the limitations or the actual benefits of this exploration scheme. Does it drive exploration in a meaningful way? Is it prone to misidentifying the optimal actions or spending too much time exploring the suboptimal ones? What is the right tuning for the learning rate? In this paper, we address several of these questions for the classic setup of stochastic multi-armed bandits. One of our main results is showing that the Boltzmann exploration strategy with any monotone learning-rate sequence will induce suboptimal behavior. As a remedy, we offer a simple non-monotone schedule that guarantees near-optimal performance, albeit only when given prior access to key problem parameters that are typically not available in practical situations (like the time horizon T and the suboptimality gap ∆). More importantly, we propose a novel variant that uses different learning rates for different arms, and achieves a distribution-dependent regret bound of order K log 2 T ∆ and a distributionindependent bound of order √ KT log K without requiring such prior knowledge. To demonstrate the flexibility of our technique, we also propose a variant that guarantees the same performance bounds even if the rewards are heavy-tailed.

Introduction

Exponential weighting strategies are fundamental tools in a variety of areas, including Machine Learning, Optimization, Theoretical Computer Science, and Decision Theory [START_REF] Arora | The multiplicative weights update method: A meta-algorithm and applications[END_REF]. Within Reinforcement Learning [START_REF] Sutton | Reinforcement Learning: An Introduction[END_REF][START_REF] Cs | Algorithms for Reinforcement Learning[END_REF], exponential weighting schemes are broadly used for balancing exploration and exploitation, and are equivalently referred to as Boltzmann, Gibbs, or softmax exploration policies [START_REF] Sutton | Integrated architectures for learning, planning, and reacting based on approximating dynamic programming[END_REF][START_REF] Kaelbling | Reinforcement learning: A survey[END_REF][START_REF] Sutton | Policy gradient methods for reinforcement learning with function approximation[END_REF][START_REF] Perkins | A convergent form of approximate policy iteration[END_REF]. In the most common version of Boltzmann exploration, the probability of choosing an arm is proportional to an exponential function of the empirical mean of the reward of that arm. Despite the popularity of this policy, very little is known about its theoretical performance, even in the simplest reinforcement learning setting of stochastic bandit problems.

The variant of Boltzmann exploration we focus on in this paper is defined by p t,i ∝ e ηt µt,i ,

where p t,i is the probability of choosing arm i in round t, µ t,i is the empirical average of the rewards obtained from arm i up until round t, and η t > 0 is the learning rate. This variant is broadly used in reinforcement learning [START_REF] Sutton | Reinforcement Learning: An Introduction[END_REF][START_REF] Cs | Algorithms for Reinforcement Learning[END_REF][START_REF] Kaelbling | Reinforcement learning: A survey[END_REF][START_REF] Vermorel | Multi-armed bandit algorithms and empirical evaluation[END_REF][START_REF] Kuleshov | Algorithms for multi-armed bandit problems[END_REF][START_REF] Osband | Generalization and exploration via randomized value functions[END_REF]. In the multiarmed bandit literature, exponentialweights algorithms are also widespread, but they typically use importance-weighted estimators for the rewards -see, e.g., [START_REF] Auer | Gambling in a rigged casino: The adversarial multi-armed bandit problem[END_REF][START_REF] Auer | The nonstochastic multiarmed bandit problem[END_REF] (for the nonstochastic setting), [START_REF] Cesa-Bianchi | Finite-time regret bounds for the multiarmed bandit problem[END_REF] (for the stochastic setting), and [START_REF] Seldin | One practical algorithm for both stochastic and adversarial bandits[END_REF] (for both stochastic and nonstochastic regimes). The theoretical behavior of these algorithms is generally well understood. For example, in the stochastic bandit setting Seldin and Slivkins [START_REF] Seldin | One practical algorithm for both stochastic and adversarial bandits[END_REF] show a regret bound of order K log 2 T

∆

, where ∆ is the suboptimality gap (i.e., the smallest difference between the mean reward of the optimal arm and the mean reward of any other arm).

In this paper, we aim to achieve a better theoretical understanding of the basic variant of the Boltzmann exploration policy that relies on the empirical mean rewards. We first show that any monotone learning-rate schedule will inevitably force the policy to either spend too much time drawing suboptimal arms or completely fail to identify the optimal arm. Then, we show that a specific non-monotone schedule of the learning rates can lead to regret bound of order K log T ∆ 2 . However, the learning schedule has to rely on full knowledge of the gap ∆ and the number of rounds T . Moreover, our negative result helps us to identify a crucial shortcoming of the Boltzmann exploration policy: it does not reason about the uncertainty of the empirical reward estimates. To alleviate this issue, we propose a variant that takes this uncertainty into account by using separate learning rates for each arm, where the learning rates account for the uncertainty of each reward estimate. We show that the resulting algorithm guarantees a distribution-dependent regret bound of order K log 2 T ∆ , and a distribution-independent bound of order

√ KT log K.
Our algorithm and analysis is based on the so-called Gumbel-softmax trick that connects the exponential-weights distribution with the maximum of independent random variables from the Gumbel distribution.

The stochastic multi-armed bandit problem

Consider the setting of stochastic multi-armed bandits: each arm i ∈ [K] def = {1, 2, . . . , K} yields a reward with distribution ν i , mean µ i , with the optimal mean reward being µ * = max i µ i . Without loss of generality, we will assume that the optimal arm is unique and has index 1. The gap of arm i is defined as ∆ i = µ * -µ i . We consider a repeated game between the learner and the environment, where in each round t = 1, 2, . . . , the following steps are repeated:

1. The learner chooses an arm

I t ∈ [K],
2. the environment draws a reward X t,It ∼ ν It independently of the past, 3. the learner receives and observes the reward X t,It .

The performance of the learner is measured in terms of the pseudo-regret defined as

R T = µ * T - T t=1 E [X t,It ] = µ * T -E T t=1 µ It = E T t=1 ∆ It = K i=1 ∆ i E [N T,i ] , (2)
where we defined N t,i = t s=1 I {Is=i} , that is, the number of times that arm i has been chosen until the end of round t. We aim at constructing algorithms that guarantee that the regret grows sublinearly.

We will consider the above problem under various assumptions of the distribution of the rewards. For most of our results, we will assume that each ν i is σ-subgaussian with a known parameter σ > 0, that is, that

E e y(X1,i-E[X1,i]) ≤ e σ 2 y 2 /2
holds for all y ∈ R and i ∈ [K]. It is easy to see that any random variable bounded in an interval of length B is B 2 /4-subgaussian. Under this assumption, it is well known that any algorithm will suffer a regret of at least Ω i>1 σ 2 log T ∆i , as shown in the classic paper of Lai and Robbins [START_REF] Lai | Asymptotically efficient adaptive allocation rules[END_REF]. There exist several algorithms guaranteeing matching upper bounds, even for finite horizons [START_REF] Auer | Finite-time analysis of the multiarmed bandit problem[END_REF][START_REF] Cappé | Kullback-leibler upper confidence bounds for optimal sequential allocation[END_REF][START_REF] Kaufmann | Thompson sampling: An asymptotically optimal finite-time analysis[END_REF]. We refer to the survey of Bubeck and Cesa-Bianchi [START_REF] Bubeck | Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems[END_REF] for an exhaustive treatment of the topic.

Boltzmann exploration done wrong

We now formally describe the heuristic form of Boltzmann exploration that is commonly used in the reinforcement learning literature [START_REF] Sutton | Reinforcement Learning: An Introduction[END_REF][START_REF] Cs | Algorithms for Reinforcement Learning[END_REF][START_REF] Kaelbling | Reinforcement learning: A survey[END_REF]. This strategy works by maintaining the empirical estimates of each µ i defined as

µ t,i = t s=1 X s,i I {Is=i} N t,i (3)
and computing the exponential-weights distribution (1) for an appropriately tuned sequence of learning rate parameters η t > 0 (which are often referred to as the inverse temperature). As noted on several occasions in the literature, finding the right schedule for η t can be very difficult in practice [START_REF] Kaelbling | Reinforcement learning: A survey[END_REF][START_REF] Vermorel | Multi-armed bandit algorithms and empirical evaluation[END_REF]. Below, we quantify this difficulty by showing that natural learning-rate schedules may fail to achieve near-optimal regret guarantees. More precisely, they may draw suboptimal arms too much even after having estimated all the means correctly, or commit too early to a suboptimal arm and never recover afterwards. We partially circumvent this issue by proposing an admittedly artificial learning-rate schedule that actually guarantees near-optimal performance. However, a serious limitation of this schedule is that it relies on prior knowledge of problem parameters ∆ and T that are typically unknown at the beginning of the learning procedure. These observations lead us to the conclusion that the Boltzmann exploration policy as described by Equations ( 1) and ( 3) is no more effective for regret minimization than the simplest alternative of ε-greedy exploration [START_REF] Sutton | Reinforcement Learning: An Introduction[END_REF][START_REF] Auer | Finite-time analysis of the multiarmed bandit problem[END_REF].

Before we present our own technical results, we mention that Singh et al. [START_REF] Singh | Convergence results for single-step on-policy reinforcement-learning algorithms[END_REF] propose a learning-rate schedule η t for Boltzmann exploration that simultaneously guarantees that all arms will be drawn infinitely often as T goes to infinity, and that the policy becomes greedy in the limit. This property is proven by choosing a learning-rate schedule adaptively to ensure that in each round t, each arm gets drawn with probability at least 1 t , making it similar in spirit to ε-greedy exploration. While this strategy clearly leads to sublinear regret, it is easy to construct examples on which it suffers a regret of at least Ω T 1-α for any small α > 0. In this paper, we pursue a more ambitious goal: we aim to find out whether Boltzmann exploration can actually guarantee polylogarithmic regret. In the rest of this section, we present both negative and positive results concerning the standard variant of Boltzmann exploration, and then move on to providing an efficient generalization that achieves consistency in a more universal sense.

Boltzmann exploration with monotone learning rates is suboptimal

In this section, we study the most natural variant of Boltzmann exploration that uses a monotone learning-rate schedule. It is easy to see that in order to achieve sublinear regret, the learning rate η t needs to increase with t so that the suboptimal arms are drawn with less and less probability as time progresses. For the sake of clarity, we study the simplest possible setting with two arms with a gap of ∆ between their means. We first show that, in order to guarantee near-optimal (logarithmic) regret, the learning rate has to increase at least at a rate log t ∆ even when the mean rewards are perfectly known, and that any learning-rate sequence that increases at a slower logarithmic rate will lead to polynomial regret. In other words, log t ∆ is the minimal affordable learning rate. Proposition 1. Let us assume that µ t,i = µ i for all t and i = 1, 2 with µ 1 > µ 2 . Assume that for some constants k ≥ 1, α ≥ 0 and ε ≤ 1 ∆ , the learning rate satisfies η t ≤ log(t∆ 2 ) (1+α)∆ + ε for all t ≥ k. Then, the regret grows as

• R T = Ω log T ∆ if α = 0, and • R T = Ω T α 1+α 1 ∆ 1-α 1+α if α > 0.
Proof. For t ≥ k, the probability of pulling the suboptimal arm can be bounded as

P [I t = 2] = 1 1 + e ηt∆ ≥ e -ηt∆ 2 = Ω ∆ 2 t -1 1+α
by our assumption on η t . Summing up for all t, we get that the regret is at least

R T = ∆ T t=1 P [I t = 2] ≥ ∆ • k + Ω T t=k ∆ 2 t -1 1+α .
The proof is concluded by observing that the sum

T t=k t -1 1+α is of the order Ω (log T ) if α = 0 and Ω T α 1+α if α > 0.
This simple proposition thus implies an asymptotic lower bound on the schedule of learning rates η t that provide near-optimal guarantees. In contrast, Theorem 1 below shows that all learning rate sequences that grow faster than 2 log t yield a linear regret, provided this schedule is adopted since the beginning of the game. This should be contrasted with Theorem 2, which exhibits a schedule achieving logarithmic regret where η t grows faster than 2 log t only after the first τ rounds. Theorem 1. There exists a 2-armed stochastic bandit problem with rewards bounded in [0, 1] where Boltzmann exploration using any learning rate sequence η t such that η t > 2 log t for all t ≥ 1 has regret R T = Ω(T ).

Proof. Consider the case where arm 2 gives a reward deterministically equal to 1 2 whereas the optimal arm 1 has a Bernoulli distribution of parameter p = 1 2 + ∆ for some 0 < ∆ < 1 2 . Note that the regret of any algorithm satisfies R T ≥ ∆(T -t 0 )P [∀t > t 0 , I t = 2]. Without loss of generality, assume that µ 1,1 = 0 and µ 1,2 = 1/2. Then for all t, independent of the algorithm, µ t,2 = 1/2 and p t,1 = e ηtBin(Nt-1,1,p) e ηt/2 + e ηtBin(Nt-1,1,p) and p t,2 = e ηt/2 e ηt/2 + e ηtBin(Nt-1,1,p) . For t 0 ≥ 1, Let E t0 be the event that Bin(N t0,1 , p) = 0, that is, up to time t 0 , arm 1 gives only zero reward whenever it is sampled. Then

P [∀t > t 0 I t = 2] ≥ P [E t0 ] 1 -P [∃t > t 0 I t = 1 | E t0 ] ≥ 1 2 -∆ t0 1 -P [∃t > t 0 I t = 1 | E t0 ] .
For t > t 0 , let A t,t0 be the event that arm 1 is sampled at time t but not at any of the times t 0 + 1, t 0 + 2, . . . , t -1. Then, for any t 0 ≥ 1,

P [∃t > t 0 I t = 1 | E t0 ] = P [∃t > t 0 A t,t0 | E t0 ] ≤ t>t0 P [A t,t0 | E t0 ] = t>t0 1 1 + e ηt/2 t-1 s=t0+1 1 - 1 1 + e ηs/2 ≤ t>t0 e -ηt/2 . Therefore R T ≥ ∆(T -t 0 ) 1 2 -∆ t0 1 - t>t0 e -ηt/2 .
Assume η t ≥ c log t for some c > 2 and for all t ≥ t 0 . Then

t>t0 e -ηt/2 ≤ t>t0 t -c 2 ≤ ∞ t0 x -c 2 dx = c 2 -1 t -( c 2 -1) 0 ≤ 1 2 whenever t 0 ≥ (2a) 1
a where a = c 2 -1. This implies R T = Ω(T ).

A learning-rate schedule with near-optimal guarantees

The above negative result is indeed heavily relying on the assumption that η t > 2 log t holds since the beginning. If we instead start off from a constant learning rate which we keep for a logarithmic number of rounds, then a logarithmic regret bound can be shown. Arguably, this results in a rather simplistic exploration scheme, which can be essentially seen as an explore-then-commit strategy (e.g., [START_REF] Garivier | On explore-then-commit strategies[END_REF]). Despite its simplicity, this strategy can be shown to achieve near-optimal performance if the parameters are tuned as a function the suboptimality gap ∆ (although its regret scales at the suboptimal rate of 1/∆ 2 with this parameter). The following theorem (proved in Appendix A.1) states this performance guarantee.

Theorem 2. Assume the rewards of each arm are in [0, 1] and let τ = 16eK log T ∆2

. Then the regret of Boltzmann exploration with learning rate

η t = I {t<τ } + log(t∆ 2 ) ∆ I {t≥τ } satisfies R T ≤ 16eK log T ∆ 2 + 9K ∆ 2 .

Boltzmann exploration done right

We now turn to give a variant of Boltzmann exploration that achieves near-optimal guarantees without prior knowledge of either ∆ or T . Our approach is based on the observation that the distribution p t,i ∝ exp (η t µ t,i ) can be equivalently specified by the rule I t = arg max j {η t µ t,j + Z t,j }, where Z t,j is a standard Gumbel random variable1 drawn independently for each arm j (see, e.g., Abernethy et al. [START_REF] Abernethy | Online linear optimization via smoothing[END_REF] and the references therein). As we saw in the previous section, this scheme fails to guarantee consistency in general, as it does not capture the uncertainty of the reward estimates. We now propose a variant that takes this uncertainty into account by choosing different scaling factors for each perturbation. In particular, we will use the simple choice β t,i = C 2 N t,i with some constant C > 0 that will be specified later. Our algorithm operates by independently drawing perturbations Z t,i from a standard Gumbel distribution for each arm i, then choosing action

I t+1 = arg max i { µ t,i + β t,i Z t,i } . (4)
We refer to this algorithm as Boltzmann-Gumbel exploration, or, in short, BGE. Unfortunately, the probabilities p t,i no longer have a simple closed form, nevertheless the algorithm is very straightforward to implement. Our main positive result is showing the following performance guarantee about the algorithm. 2 Theorem 3. Assume that the rewards of each arm are σ 2 -subgaussian and let c > 0 be arbitrary. Then, the regret of Boltzmann-Gumbel exploration satisfies

R T ≤ K i=2 9C 2 log 2 + T ∆ i /c 2 ∆ i + K i=2 c 2 e γ + 18C 2 e σ 2 /2C 2 (1 + e -γ ) ∆ i + K i=2 ∆ i .
In particular, choosing C = σ and c = σ guarantees a regret bound of

R T = O K i=2 σ 2 log 2 (T ∆ 2 i /σ 2 ) ∆ i .
Notice that, unlike any other algorithm that we are aware of, Boltzmann-Gumbel exploration still continues to guarantee meaningful regret bounds even if the subgaussianity constant σ is underestimated-although such misspecification is penalized exponentially in the true σ 2 . A downside of our bound is that it shows a suboptimal dependence on the number of rounds T : it grows asymptotically as i>1 log 2 (T ∆ 2 i ) ∆ i , in contrast to the standard regret bounds for the UCB algorithm of Auer et al. [START_REF] Auer | Finite-time analysis of the multiarmed bandit problem[END_REF] that grow as i>1 (log T ) ∆ i . However, our guarantee improves on the distribution-independent regret bounds of UCB that are of order √ KT log T . This is shown in the following corollary. Corollary 1. Assume that the rewards of each arm are σ 2 -subgaussian. Then, the regret of Boltzmann-Gumbel exploration with

C = σ satisfies R T ≤ 200σ √ KT log K.
Notably, this bound shows optimal dependence on the number of rounds T , but is suboptimal in terms of the number of arms. To complement this upper bound, we also show that these bounds are tight in the sense that the log K factor cannot be removed.

Theorem 4. For any K and T such that K/T log K ≤ 1, there exists a bandit problem with rewards bounded in [0, 1] where the regret of Boltzmann-Gumbel exploration with C = 1 is at least

R T ≥ 1 2 √ KT log K.
The proofs can be found in the Appendices A.5 and A.6. Note that more sophisticated policies are known to have better distribution-free bounds. The algorithm MOSS [START_REF] Audibert | Minimax policies for bandits games[END_REF] achieves minimax-optimal √ KT distribution-free bounds, but distribution-dependent bounds of the form (K/∆) log(T ∆ 2 ) where ∆ is the suboptimality gap. A variant of UCB using action elimination and due to Auer and Ortner [START_REF] Auer | UCB revisited: Improved regret bounds for the stochastic multi-armed bandit problem[END_REF] has regret i>1 log(T ∆ 2 i ) ∆ i corresponding to a KT (log K) distribution-free bound. The same bounds are achieved by the Gaussian Thompson sampling algorithm of Agrawal and Goyal [START_REF] Agrawal | Further optimal regret bounds for thompson sampling[END_REF], given that the rewards are subgaussian.

We finally provide a simple variant of our algorithm that allows to handle heavy-tailed rewards, intended here as reward distributions that are not subgaussian. We propose to use technique due to Catoni [START_REF] Catoni | Challenging the empirical mean and empirical variance: A deviation study[END_REF] based on the influence function

ψ(x) = log 1 + x + x 2 /2 , for x ≥ 0, -log 1 -x + x 2 /2 , for x ≤ 0.
Using this function, we define our estimates as

µ t,i = β t,i t s=1 I {Is=i} ψ X s,i β t,i N t,i
We prove the following result regarding Boltzmann-Gumbel exploration run with the above estimates. Theorem 5. Assume that the second moment of the rewards of each arm are bounded uniformly as E X 2 i ≤ V and let c > 0 be arbitrary. Then, the regret of Boltzmann-Gumbel exploration satisfies

R T ≤ K i=2 9C 2 log 2 + T ∆ i /c 2 ∆ i + K i=2 c 2 e γ + 18C 2 e V /2C 2 (1 + e -γ ) ∆ i + K i=2 ∆ i .
Notably, this bound coincides with that of Theorem 3, except that σ 2 is replaced by V . Thus, by following the proof of Corollary 1, we can show a distribution-independent regret bound of order √ KT log K.

Analysis

Let us now present the proofs of our main results concerning Boltzmann-Gumbel exploration, Theorems 3 and 5. Our analysis builds on several ideas from Agrawal and Goyal [START_REF] Agrawal | Further optimal regret bounds for thompson sampling[END_REF]. We first provide generic tools that are independent of the reward estimator and then move on to providing specifics for both estimators.

We start with introducing some notation. We define µ t,i = µ t,i + β t,i Z t,i , so that the algorithm can be simply written as I t = arg max i µ t,i . Let F t-1 be the sigma-algebra generated by the actions taken by the learner and the realized rewards up to the beginning of round t. Let us fix thresholds x i , y i satisfying µ i ≤ x i ≤ y i ≤ µ 1 and define q t,i = P [ µ t,1 > y i | F t-1 ]. Furthermore, we define the events

E µ t,i = { µ t,i ≤ x i } and E µ t,i = { µ t,i ≤ y i }.
With this notation at hand, we can decompose the number of draws of any suboptimal i as follows:

E [N T,i ] = T t=1 P I t = i, E µ t,i , E µ t,i + T t=1 P I t = i, E µ t,i , E µ t,i + T t=1 P I t = i, E µ t,i . (5)
It remains to choose the thresholds x i and y i in a meaningful way: we pick x i = µ i + ∆i 3 and y i = µ 1 -∆i 3 . The rest of the proof is devoted to bounding each term in Eq. ( 5). Intuitively, the individual terms capture the following events:

• The first term counts the number of times that, even though the estimated mean reward of arm i is well-concentrated and the additional perturbation Z t.i is not too large, arm i was drawn instead of the optimal arm 1. This happens when the optimal arm is poorly estimated or when the perturbation Z t,1 is not large enough. Intuitively, this term measures the interaction between the perturbations Z t,1 and the random fluctuations of the reward estimate µ t,1 around its true mean, and will be small if the perturbations tend to be large enough and the tail of the reward estimates is light enough.

• The second term counts the number of times that the mean reward of arm i is well-estimated, but it ends up being drawn due to a large perturbation. This term can be bounded independently of the properties of the mean estimator and is small when the tail of the perturbation distribution is not too heavy. • The last term counts the number of times that the reward estimate of arm i is poorly concentrated. This term is independent of the perturbations and only depends on the properties of the reward estimator.

As we will see, the first and the last terms can be bounded in terms of the moment generating function of the reward estimates, which makes subgaussian reward estimators particularly easy to treat. We begin by the most standard part of our analysis: bounding the third term on the right-hand-side of ( 5) in terms of the moment-generating function. Lemma 1. Let us fix any i and define τ k as the k'th time that arm i was drawn. We have

T t=1 P I t = i, E µ t,i ≤ 1 + T -1 k=1 E exp µ τ k ,i -µ i β τ k ,i • e -∆ i √ k 3C .
Interestingly, our next key result shows that the first term can be bounded by a nearly identical expression: Lemma 2. Let us define τ k as the k'th time that arm 1 was drawn. For any i, we have

T t=1 P I t = i, E µ t,i , E µ t,i ≤ T -1 k=0 E exp µ 1 -µ τ k ,1 β τ k ,1 e -γ-∆ i √ k 3C .
It remains to bound the second term in Equation ( 5), which we do in the following lemma: Lemma 3. For any i = 1 and any constant c > 0, we have

T t=1 P I t = i, E µ t,i , E µ t,i ≤ 9C 2 log 2 + T ∆ 2 i /c 2 + c 2 e γ ∆ 2 i .
The proofs of these three lemmas are included in the supplementary material.

The proof of Theorem 3

For this section, we assume that the rewards are σ-subgaussian and that µ t,i is the empirical-mean estimator. Building on the results of the previous section, observe that we are left with bounding the terms appearing in Lemmas 1 and 2. To this end, let us fix a k and an i and notice that by the subgaussianity assumption on the rewards, the empirical mean

µ τ k ,i is σ √ k -subgaussian (as N τ k ,i = k). In other words, E e α( µτ k ,i-µi) ≤ e α 2 σ 2 /2k
holds for any α. In particular, using this above formula for α

= 1/β τ k ,i = k C 2 , we obtain E exp µ τ k ,i -µ i β τ k ,i ≤ e σ 2 /2C 2 .
Thus, the sum appearing in Lemma 1 can be bounded as

T -1 k=1 E exp µ τ k ,i -µ i β τ k ,i • e -∆ i √ k 3C ≤ e σ 2 /2C 2 T -1 k=1 e -∆ i √ k 3C ≤ 18C 2 e σ 2 /2C 2 ∆ 2 i ,
where the last step follows from the fact3 that ∞ k=0 e c √ k ≤ 2 c 2 holds for all c > 0. The statement of Theorem 3 now follows from applying the same argument to the bound of Lemma 2, using Lemma 3, and the standard expression for the regret in Equation (2).

The proof of Theorem 5

We now drop the subgaussian assumption on the rewards and consider reward distributions that are possibly heavy-tailed, but have bounded variance. The proof of Theorem 5 trivially follows from the arguments in the previous subsection and using Proposition 2.1 of Catoni [START_REF] Catoni | Challenging the empirical mean and empirical variance: A deviation study[END_REF] (with θ = 0) that guarantees the bound

E exp ± µ i -µ t,i β t,i N t,i = n ≤ exp E X 2 i 2C 2 . (6)

Experiments

This section concludes by illustrating our theoretical results through some experiments, highlighting the limitations of Boltzmann exploration and contrasting it with the performance of Boltzmann-Gumbel exploration. We consider a stochastic multi-armed bandit problem with K = 10 arms each yielding Bernoulli rewards with mean µ i = 1/2 for all suboptimal arms i > 1 and µ 1 = 1/2 + ∆ for the optimal arm. We set the horizon to T = 10 6 and the gap parameter to ∆ = 0.01. We compare three variants of Boltzmann exploration with inverse learning rate parameters

• β t = C 2 (BE-const), • β t = C 2 / log t (BE-log), and
• β t = C 2 / √ t (BE-sqrt)
for all t, and compare it with Boltzmann-Gumbel exploration (BGE), and UCB with exploration bonus C 2 log(t)/N t,i .

We study two different scenarios: (a) all rewards drawn i.i.d. from the Bernoulli distributions with the means given above and (b) the first T 0 = 5,000 rewards set to 0 for arm 1. The latter scenario simulates the situation described in the proof of Theorem 1, and in particular exposes the weakness of Boltzmann exploration with increasing learning rate parameters. The results shown on Figure 1 (a) and (b) show that while some variants of Boltzmann exploration may perform reasonably well when initial rewards take typical values and the parameters are chosen luckily, all standard versions fail to identify the optimal arm when the initial draws are not representative of the true mean (which happens with a small constant probability). On the other hand, UCB and Boltzmann-Gumbel exploration continue to perform well even under this unlikely event, as predicted by their respective theoretical guarantees. Notably, Boltzmann-Gumbel exploration performs comparably to UCB in this example (even slightly outperforming its competitor here), and performs notably well for the recommended parameter setting of C 2 = σ 2 = 1/4 (noting that Bernoulli random variables are 1/4-subgaussian).

A Technical proofs

A.1 The proof of Theorem 2

For any round t and action i, e -ηt K ≤ e ηt µt-1,i K j=1 e ηt µt-1,j ≤ e ηt µt-1,i-µt-1,1 .

Now, for any i > 1, we can write

I {It=i} = I {It=i, µt-1,i-µt-1,1<-∆ i 2 } + I {It=i, µt-1,i-µt-1,1≥-∆ i 2 } ≤ I {It=i, µt-1,i-µt-1,1<-∆ i 2 } + I { µt-1,1≤µ1-∆ i 4 } + I { µt-1,i≥µi+ ∆ i 4 }
. We take expectation of the three terms above and sum over t = τ + 1, . . . , T . Because of [START_REF] Auer | Finite-time analysis of the multiarmed bandit problem[END_REF], the first term is simply bounded as

T t=τ +1 P I t = i, µ t-1,i -µ t-1,1 < - ∆ i 2 ≤ T t=τ +1 e -ηt∆i/2 ≤ T t=τ +1 1 t∆ 2 ≤ log(T + 1) ∆ 2 .
We control the second and third term in the same way. For the second term we have that

I { µt-1,1≤µ1-∆ i 4 } ≤ I {Nt-1,1≤t1} + I { µt-1,1≤µ1-∆ i 4 , Nt-1,1>t1}
holds for any fixed t and for any

t 1 ≤ t -1. Hence T t=τ +1 P µ t-1,1 ≤ µ 1 - ∆ i 4 ≤ T t=τ +1 P [N t-1,1 ≤ t 1 ] + T t=τ +1 P µ t-1,1 ≤ µ 1 - ∆ i 4 , N t-1,1 > t 1 .
Now observe that, because of (7) applied to the initial τ rounds, E [N t-1,1 ] ≥ τ eK holds for all t > τ . By setting

t 1 = 1 2 E [N t-1,1 ] ≥ τ 2eK , Chernoff bounds (in multiplicative form) give P [N t-1,1 ≤ t 1 ] ≤ e -τ
8eK . Standard Chernoff bounds, instead, give

P µ t-1,1 ≤ µ 1 - ∆ i 4 , N t-1,1 > t 1 ≤ t-1 s=t1+1 e -s∆ 2 8 ≤ 8 ∆ 2 e -t 1 ∆ 2 8 ≤ 8 ∆ 2 e -τ ∆ 2 16eK .
Therefore, for the second term we can write

T t=τ +1 P µ t-1,1 ≤ µ 1 - ∆ i 4 ≤ T e -τ 8eK + 8 ∆ 2 e -τ ∆ 2 16eK ≤ 1 + 8 ∆ 2 .
The third term can be bounded exactly in the same way. Putting together, we have thus obtained, for all actions i > 1,

i>1 E [N T,i ] ≤ τ + K + 8K ∆ 2 ≤ 16eK(log T ) ∆ 2 + 9K ∆ 2 .
This concludes the proof.

A.2 The proof of Lemma 1

Let τ k denote the index of the round when arm i is drawn for the k'th time. We let τ 0 = 0 and τ k = T for k > N T,i . Then,

T t=1 P I t = i, E µ t,i ≤ E T -1 k=0 τ k+1 t=τ k +1 I {It=i} I E µ t,i = E T -1 k=0 I E µ τ k ,i τ k+1 t=τ k +1 I {It=i} = E T -1 k=0 I E µ τ k ,i ≤ 1 + T -1 k=1 P [ µ τ k ,i ≥ x i ] ≤ 1 + T -1 k=1 P µ τ k ,i -µ i ≥ ∆ i 3 .
Now, using the fact that N τ k ,i = k, we bound the last term by exploiting the subgaussianity of the rewards through Markov's inequality:

P µ τ k ,i -µ i ≥ ∆ i 3 = P e α( µτ k ,i -µi) ≥ e α ∆ i 3 (for any α > 0) ≤ E e α( µτ k ,i-µi) • e -α ∆ i 3 (Markov's inequality) ≤ e α 2 σ 2 /2k • e -α ∆ i 3 (the subgaussian property) ≤ e σ 2 /2C 2 • e -∆ i √ k 3C (choosing α = k/C 2 )
Now, using the fact 4 that

∞ k=0 e c √ k ≤ 2
c 2 holds for all c > 0, the proof is concluded.

A.3 The proof of Lemma 2

The proof of this lemma crucially builds on Lemma 1 of Agrawal and Goyal [START_REF] Agrawal | Further optimal regret bounds for thompson sampling[END_REF], which we state and prove below.

Lemma 4 (cf. Lemma 1 of Agrawal and Goyal [START_REF] Agrawal | Further optimal regret bounds for thompson sampling[END_REF]).

P I t = i, E µ t,i , E µ t,i F t-1 ≤ 1 -q t,i q t,i • P I t = 1, E µ t,i , E µ t,i F t-1
Proof. First, note that E µ t,i ⊆ F t-1 . We only have to care about the case when E µ t,i holds, otherwise both sides of the inequality are zero and the statement trivially holds. Thus, we only have to prove

P I t = i F t-1 , E µ t,i ≤ 1 -q t,i q t,i • P I t = 1 F t-1 , E µ t,i .
Now observe that I t = i under the event E µ t,i implies µ t,j ≤ y i for all j (which follows from µ t,j ≤ µ t,i ≤ y i ). Thus, for any i > 1, we have

P I t = i F t-1 , E µ t,i ≤P ∀j : µ t,j ≤ y i F t-1 , E µ t,i =P µ t,1 ≤ y i F t-1 , E µ t,i • P ∀j > 1 : µ t,j ≤ y i F t-1 , E µ t,i =(1 -q t,i ) • P ∀j > 1 : µ t,j ≤ y i F t-1 , E µ t,i ,
where the last equality holds because the event in question is independent of E µ t,i . Similarly,

P I t = 1 F t-1 , E µ t,i ≥P ∀j > 1 : µ t,1 > y i ≥ µ t,j F t-1 , E µ t,i =P µ t,1 > y i F t-1 , E µ t,i • P ∀j > 1 : µ t,j ≤ y i F t-1 , E µ t,i =q t,i • P ∀j > 1 : µ t,j ≤ y i F t-1 , E µ t,i .
Combining the above two inequalities and multiplying both sides with P E µ t,i F t-1 gives the result.

We are now ready to prove Lemma 2.

Proof of Lemma 2. Following straightforward calculations and using Lemma 4,

T t=1 P I t = i, E µ t,i , E µ t,i ≤ T -1 k=0 E 1 -q τ k ,i q τ k ,i .
Thus, it remains to bound the summands on the right-hand side. To achieve this, we start with rewriting q τ k ,i as

q τ k ,i = P [ µ τ k ,1 > y i | F τ k -1 ] = P Z τ k ,1 > µ 1 -µ τ k ,1 -∆i 3 β τ k ,1 F τ k -1 = 1 -exp -exp - µ 1 -µ τ k ,1 -∆i 3 β τ k ,1 + γ , so that we have 1 -q τ k ,i q τ k ,i = exp -exp - µ1-µτ k ,1- ∆ i 3 βτ k ,1 + γ 1 -exp -exp - µ1-µτ k ,1- ∆ i 3 βτ k ,1 + γ ≤ exp µ 1 -µ τ k ,1 -∆i 3 β τ k ,1 -γ = exp µ 1 -µ t,1 β τ k ,1 • e -γ- ∆ i 3β τ k ,1 ,
where we used the elementary inequality e -1/x 1-e -1/x ≤ x that holds for all x ≥ 0. Taking expectations on both sides and using the definition of β t,i concludes the proof.

A.4 Proof of Lemma 3

Setting L = 9C 2 log 2 (T ∆ 2 i /c 2 ) ∆ 2 i
, we begin with the bound

T t=1 I It=i,E µ t,i ,E µ t,i ≤ L + T t=L I { µt,i>µ1-∆ i 3 , µt,i<µi+ ∆ i 3 ,Nt,i>L} .
For bounding the expectation of the second term above, observe that

P µ t,i > µ 1 - ∆ i 3 , µ t,i < µ i + ∆ i 3 , N t,i > L F t-1 ≤ P µ t,i > µ t,i + ∆ i 3 , N t,i > L F t-1 ≤ P β t,i Z t,i > ∆ i 3 , N t,i > L F t-1 = P Z t,i > ∆ i 3β t,i , N t,i > L F t-1 .
By the distribution of the perturbations Z t,i , we have

P Z t,i ≥ ∆ i 3β t,i F t-1 = 1 -exp -exp - ∆ i 3β t,i + γ ≤ exp - ∆ i 3β t,i + γ = exp - ∆ i N t,i 3C + γ ,
where we used the inequality 1 -e -x ≤ x that holds for all x and the definition of β t,i . Noticing that N t,i is measurable in F t-1 , we obtain the bound

P Z t,i > ∆ i 3β t,i , N t,i > L F t-1 ≤ exp - ∆ i N t,i 3C + γ • I {Nt,i>L} , ≤ exp - ∆ i √ L 3C + γ • I {Nt,i>L} ≤ c 2 e γ T ∆ 2 i ,
where the last step follows from using the definition of L and bounding the indicator by 1. Summing up for all t and taking expectations concludes the proof.

A.5 The proof of Corollary 1

Following the arguments in Section 5.1, we can show that the number of suboptimal draws can be bounded as

E [N T,i ] ≤ 1 + σ 2 A + B log 2 (T ∆ 2 i /σ 2 ) ∆ 2 i
for all arms i, with constants A = e γ + 18 √ e (1 + e -γ ) and B = 9. We can obtain a distributionindependent bound by setting a threshold ∆ > 0 and writing the regret as

R T ≤ σ 2 i:∆i>∆ A + B log 2 (T ∆ 2 i /σ 2 ) ∆ i + ∆T ≤ σ 2 K A + B log 2 (T ∆ 2 /σ 2 ) ∆ + ∆T
(since log 2 (x 2 )/x is monotone decreasing for x ≤ 1)

≤ σ √ T K A + B log 2 (K log 2 K) log K + σ √ T K log K (setting ∆ = σ K/T log K) ≤ σ √ T K A + 2B log 2 (K) log K + σ √ T K log K (using 2 log log(x) ≤ log(x)) ≤ σ √ T K log K (2B + A/ log K) + σ √ T K log K ≤ (2A + 2B + 1) σ √ T K log K,
where we used log K ≥ 1 2 that holds for K ≥ 2. The proof is concluded by noting that 2A+2B +1 ≈ 187.63 < 200.

A.6 The proof of Theorem 4

The simple counterexample for the proof follows the construction of Section 3 of Agrawal and Goyal [START_REF] Agrawal | Further optimal regret bounds for thompson sampling[END_REF]. Consider a problem with deterministic rewards for each arm: the optimal arm 1 always gives a reward of ∆ = K T C 1 and all the other arms give rewards of 0. Define B t-1 as the event that

K i=2 N t,i ≤ C2 √ KT ∆
. Let us study two cases depending on the probability P [A t-1 ]: If P [A t-1 ] ≤ 1 2 , we have

R T ≥ R t ≥ E i N t,i ∆ A t-1 • 1 2 . ≥ 1 2 C 2 √ KT . (8)
In what follows, we will study the other case when P [A t-1 ] ≥ 1 2 . We will show that, under this assumption, a suboptimal arm will be drawn in round t with at least constant probability. In particular, we have

P [I t = 1] = P [∃i > 1 : µ t,1 < µ t,i ] ≥ P [ µ t,1 < µ 1 , ∃i > 1 : µ 1 < µ t,i ] ≥ P [ µ t,1 < µ 1 , ∃i > 1 : µ 1 < µ t,i | A t-1 ] P [A t-1 ] ≥ E [P [ µ t,1 < µ 1 , ∃i > 1 : µ 1 < µ t,i | F t-1 , A t-1 ]] 1 2 = E [P [ µ t,1 < µ 1 | F t-1 , A t-1 ] • P [ ∃i > 1 : µ 1 < µ t,i | F t-1 , A t-1 ]] 1 2 = E [P [ Z t,1 < 0| F t-1 , A t-1 ] • P [ ∃i > 1 : ∆ < β t,i Z t,i | F t-1 , A t-1 ]] 1 2 .
To proceed, observe that P [Z t,1 < 0] ≥ 0.1 and P [ ∃i > 1 : ∆ < β t,i Z t,i | F t-1 , A t-1 ] = P ∃i > 1 : ∆ N t,i < Z t,i F t-1 , A t-1

= 1 - i>1 exp -exp -∆ N t,i + γ = 1 -exp - i>1 exp -∆ N t,i + γ = 1 -exp - i>1 K -1 K -1 exp -∆ N t,i + γ ≥ 1 -exp -(K -1) exp -∆ i>1 N t,i K -1 + γ (by Jensen's inequality) ≥ 1 -exp   -(K -1) exp   -∆ C 2 √ KT ∆ (K -1) + γ     = 1 -exp -(K -1) exp -∆ C 2 T C 1 (K -1) + γ ≥ 1 -exp -exp -C 1 C 2 C 1 + log(K -1) + γ .
Setting C 2 = C 1 = log K, we obtain that whenever P [A t-1 ] ≥ 1 2 , we have P [I t = 1] ≥ 1 -exp (-exp (-log K + log(K -1) + γ))

≥ 1 -exp (-exp (γ)) ≥ 0.83 > 1 2 .

Figure 1 :

 1 Figure 1: Empirical performance of Boltzmann exploration variants, Boltzmann-Gumbel exploration and UCB for (a) i.i.d. initialization and (b) malicious initialization, as a function of C 2 . The dotted vertical line corresponds to the choice C 2 = 1/4 suggested by Theorem 3.

31st Conference on Neural Information Processing Systems (NIPS 2017), Long Beach, CA, USA.

The cumulative density function of a standard Gumbel random variable is F (x) = exp(-e -x+γ ) where γ is the Euler-Mascheroni constant.

We use the notation log + (•) = max{0, •}.

This can be easily seen by bounding the sum with an integral.

This can be easily seen by bounding the sum with an integral.

Acknowledgements Gábor Lugosi was supported by the Spanish Ministry of Economy and Competitiveness, Grant MTM2015-67304-P and FEDER, EU. Gergely Neu was supported by the UPFellows Fellowship (Marie Curie COFUND program n • 600387).

This implies that the regret of our algorithm is at least

Together with the bound of Equation ( 8) for the complementary case, this concludes the proof.


Fabio Vitale
email: fabio.vitale@inria.fr

Nikos Parotsidis
email: nikos.parotsidis@uniroma2.it

Claudio Gentile
email: cla.gentile@gmail.com

Online Reciprocal Recommendation with Theoretical Performance Guarantees

A reciprocal recommendation problem is one where the goal of learning is not just to predict a user's preference towards a passive item (e.g., a book), but to recommend the targeted user on one side another user from the other side such that a mutual interest between the two exists. The problem thus is sharply different from the more traditional items-to-users recommendation, since a good match requires meeting the preferences at both sides. We initiate a rigorous theoretical investigation of the reciprocal recommendation task in a specific framework of sequential learning. We point out general limitations, formulate reasonable assumptions enabling effective learning and, under these assumptions, we design and analyze a computationally efficient algorithm that uncovers mutual likes at a pace comparable to that achieved by a clairvoyant algorithm knowing all user preferences in advance. Finally, we validate our algorithm against synthetic and real-world datasets, showing improved empirical performance over simple baselines.

Introduction

Recommendation Systems are at the core of many successful online businesses, from e-commerce, to online streaming, to computational advertising, and beyond. These systems have extensively been investigated by both academic and industrial researchers by following the standard paradigm of items-to-users preference prediction/recommendation. In this standard paradigm, a targeted user is presented with a list of items that s/he may prefer according to a preference profile that the system has learned based on both explicit user features (item data, demographic data, explicitly declared preferences, etc.) and past user activity. In more recent years, due to their hugely increasing interest in the online dating and the job recommendation domains, a special kind of recommendation systems called Reciprocal Recommendation Systems (RRS) have gained big momentum. The reciprocal recommendation problem is sharply different from the more traditional items-to-users recommendation, since recommendations must satisfy both parties, i.e., both parties can express their likes and dislikes and a good match requires meeting the preferences of both. Examples of RRS include, for instance: online recruitment systems (e.g., LinkedIn), [START_REF] Akehurst | CCR -A content-collaborative reciprocal recommender for online dating[END_REF] where a job seeker searches for jobs matching his/her preferences, say salary and expectations, and a recruiter who seeks suitable candidates to fulfil the job requirements; heterosexual online dating systems (e.g., Tinder), [START_REF] Akehurst | Explicit and Implicit User Preferences in Online Dating[END_REF] where people have the common goal of finding a partner of the opposite gender; roommate matching systems (e.g., Badi), [START_REF] Alanazi | A Scalable People-to-People Hybrid Reciprocal Recommender Using Hidden Markov Models[END_REF] used to connect people looking for a room to those looking for a roommate, online mentoring systems, customer-to-customer marketplaces, etc. From a Machine Learning perspective, the main challenge in a RRS is thus to learn reciprocated preferences, since the goal of the system is not just to predict a user's preference towards a passive item (a book, a movie, etc), but to recommend the targeted user on one side another user from the other side such that a mutual interest exists. Importantly enough, the interaction the two involved users have with the system is often staged and unsynced. Consider, for instance, a scenario where a user, Geena, is recommended to another user, Bob. The recommendation is successful only if both Geena and Bob mutually agree that the recommendation is good. In the first stage, Bob logs into the system and Geena gets recommended to him; this is like in a standard recommendation system: Bob will give a feedback (say, positive) to the system regarding Geena. Geena may never know that she has been recommended to Bob. In a subsequent stage, some time in the future, also Geena logs in. In an attempt to find a match, the system now recommends Bob to Geena. It is only when also Geena responds positively that the reciprocal recommendation becomes successful. The problem of reciprocal recommendation has so far being studied mainly in the Data Mining, Recommendation Systems, and Social Network Analysis literature (e.g., [7, 1, 14, 13, 11, 17, 21, 3, 15]), with some interesting adaptations of standard collaborative filtering approaches to user feature similarity, but it has remained largely unexplored from a theoretical standpoint. Despite each application domain has its own specificity, [START_REF] Brozovsky | Recommender system for online dating service[END_REF] in this paper we abstract such details away, and focus on the broad problem of building matches between the two parties in the reciprocal recommendation problem based on behavioral information only. In particular, we do not consider explicit user preferences (e.g., those evinced by user profiles), but only the implicit ones, i.e., those derived from past user behavior. The explicit-vs-implicit user features is a standard dichotomy in Recommendation System practice, and it is by now common knowledge that collaborative effects (aka, implicit features) carry far more information about actual user preferences than explicit features, like, for instance, demographic metadata [16]. Similar experimental findings are also reported in the context of RRS in the online dating domain [2]. In this paper, we initiate a rigorous theoretical investigation of the reciprocal recommendation problem, and we view it as a sequential learning problem where learning proceeds in a sequence of rounds. At each round, a user from one of the two parties becomes active and, based on past feedback, the learning algorithm (called matchmaker) is compelled to recommend one user from the other party. The broad goal of the algorithm is to uncover as many mutual interests (called matches) as possible, and to do so as quickly as possible. We formalize our learning model in Section 2. After observing that, in the absence of structural assumptions about matches, learning is virtually precluded (Section 3), we come to consider a reasonable clusterability assumption on the preference of users at both sides. Under these assumptions, we design and analyze a computationally efficient matchmaking algorithm that leverages the correlation across matches. We show that the number of uncovered matches within T rounds is comparable (up to constant factors) to those achieved by an optimal algorithm that knows beforehand all user preferences, provided T and the total number of matches to be uncovered is not too small (Sections 3, and 4). Finally, in Section 5 we present a suite of initial experiments, where we contrast (a version of) our algorithm to noncluster-based random baselines on both synthetic and publicly available real-world benchmarks in the domain of online dating. Our experiments serve the twofold purpose of validating our structural assumptions on user preferences against real data, and showing the improved matchmaking performance of our algorithm, as compared to simple noncluster-based baselines.

Preliminaries

We first introduce our basic notation. We have a set of users V partitioned into two parties. Though a number of alternative metaphores could be adopted here, for concreteness, we call the two parties B (for "boys") and G (for "girls"). Throughout this paper, g, g and g will be used to denote generic members of G, and b, b , and b to denote generic members of B. For simplicity, we assume the two parties B and G have the same size n. A hidden ground truth about the mutual preferences of the members of the two parties is encoded by a sign function σ :

(B × G) ∪ (G × B) → {-1, +1}.
Specifically, for a pairing (b, g) ∈ B × G, the assignment σ(b, g) = +1 means that boy b likes girl g, and σ(b, g) = -1 means that boy b dislikes girl g. Likewise, given pairing (g, b) ∈ G × B, we have σ(g, b) = +1 when girl g likes boy b, and σ(g, b) = -1 when girl g dislikes boy b. The ground truth σ therefore defines a directed bipartite signed graph collectively denoted as ( B, G , E, σ), where E, the set of directed edges in this graph, is simply (B × G) ∪ (G × B), i.e., the sef of all possible 2n 2 directed egdes in this bipartite graph. A "+1" edge will sometimes be called a positive edge, while a "-1" edge will be called a negative edge. Any pair of directed edges (g, b) ∈ G × B and (b, g) ∈ B × G involving the same two subjects g and b is called a reciprocal pair of edges. We also say that (g, b) is reciprocal to (b, g), and vice versa. The pairing of signed edges (g, b) and (b, g) is called a match if and only if σ(b, g) = σ(g, b) = +1. The total number of matches will often be denoted by M . See Figure 1 for a pictorial illustration. Coarsely speaking, the goal of a learning algorithm A is to uncover in a sequential fashion as many matches as possible as quickly as possible. More precisely, we are given a time horizon T ≤ n 2 , e.g., T = n √ n, and at each round t = 1, . . . , T : (1 B ) A receives the id of a boy b chosen uniformly at random5 from B (b is meant to be the "next boy" that logs into the system); (2 B ) A selects a girl g ∈ G to recommend to b; (3 B ) b provides feedback to the learner, in that the sign σ(b, g ) of the selected boy-to-girl edge is revealed to A. Within the same round t, the three steps described above are subsequently executed after switching the roles of G and B (and will therefore be called Steps (1 G ), (2 G ), and (3 G )). Hence, each round t is made up of two halves, the first half where a boy at random is logged into the system and the learner A is compelled to select a girl, and the second half where a girl at random is logged in and A has to select a boy. Thus at each round t, A observes the sign of the two directed edges (b, g ) and (g, b ), where b ∈ B and g ∈ G are generated uniformly at random by the environment, and g and b are the outcome of A's recommendation effort. Notice that we assume the ground truth encoded by σ is persistent and noiseless, so that whereas the same user (boy or girl) may recur several times throughout the rounds due to their random generation, there is no point for the learner to request the sign of the same edge twice at two different rounds. The goal of algorithm A is to maximize the number of uncovered matches within the T rounds. The sign of the two reciprocal edges giving rise to a match need not be selected by A in the same round; the round where the match is uncovered is the time when the reciprocating edge is selected, e.g., if in round t 1 we observe σ(b, g ) = -1, σ(g, b ) = +1, and in round t 2 > t 1 we observe σ(b , g) = +1, σ(g , b ) = +1, we say that the match involving b and g has been uncovered only in round t 2 . In fact, if A has uncovered a positive edge g → b in (the second half of) round t 1 , the reciprocating positive edge (b , g) need not be uncovered any time soon, since A has at the very least to wait until b will log into the system, an event which on average will occur only n rounds later. We call matching graph, and denote it by M, the bipartite and undirected graph having B ∪ G as nodes, where (b, g) ∈ B × G is an edge in M if and only if b and g determine a match in the original graph ( B, G , E, σ). Given b ∈ B, we let N M (b) ⊆ G be the set of matching girls for b according to σ, and deg M (b) be the number of such girls. N M (g) and deg M (g) are defined symmetrically. See again Figure 1 for an example. The performance of algorithm A is measured by the number of matches found by A within the T rounds. Specifically, if M t (A) is the number of matches uncovered by A after t rounds of a given run, we would like to obtain lower bounds on M T (A) that hold with high probability over the random generation of boys and girls that log into the system as well as the internal randomization of A. To this effect, we shall repeatedly use in our statements the acronym w.h.p to signify with probability at least 1 -O( 1n ), as n → ∞. It will also be convenient to denote by E t (A) the set of directed edges selected by A during the first t rounds, with E 0 (A) = ∅. A given run of A may therefore be summarized by the sequence {E t (A)} T t=1 . Likewise, E r t (A) will denote the set of reciprocal (not necessarily matching) directed edges selected by A up to time t. Finally, E r will denote the set of all |B| • |G| = n 2 pairs of reciprocal (not necessarily matching) edges between B and G. We will first show (Section 3) that in the absence of further assumptions on the way the matches are located, there is not much one can do but try and simulate a random sampler. In order to further illustrate our model, the same section introduces a reference optimal behavior that assumes prior knowledge of the whole sign fuction σ. This will be taken as a yardstick to be contrasted to the performance of our algorithm SMILE (Section 4) that works under more specific, yet reasonable, structural assumptions on σ.

G x B → {-1,+1} B 1 2 3 4 1 2 3 4 1 -1 -1 +1 +1 +1 -1 -1 -1 +1 +1 +1 +1 -1 -1 +1 +1 +1 -1 +1 -1 +1 -1 -1 -1 +1 +1 +1 +1 +1 -1 -1 -1 G B x G → {-1,+1} σ σ 4 3 2 1 4 3 2 1 B G (c) (a) (b)

General limitations and optimal behavior

We now show [START_REF] Christiano | Online local learning via semidefinite programming[END_REF] that in the absence of specific assumptions on σ, the best thing to do in order to uncover matches is to reciprocate at random, no matter how big the number M of matches actually is.

Theorem 1 Given B and G such that |B| = |G| = n, and any integer m ≤ n 2 2 , there exists a randomized strategy for generating σ such that M = m, and the expected number of matches uncovered by any algorithm A operating on ( B, G , E, σ) satisfies7 EM T (A) = O T n 2 M . An algorithm matching the above upper bound is described next. We call this algorithm OOMM (Oblivious Online Match Maker), The main idea is to develop a strategy that is able to draw uniformly at random as many pairs of reciprocal edges as possible from E r (recall that E r is the set of all reciprocal edges between B and G). In particular, within the T rounds, OOMM will draw uniformly at random Θ(T )-many such pairs. The pseudocode of OOMM is given next. For brevity, throughout this paper an algorithm will be described only through Steps (2 B ) and (2 G ) -recall Section 2. OOMM simply operates as follows. In Step (2 B ) of round t, the algorithm chooses a girl g uniformly at random from the whole set G. OOMM maintains over time the set B g,t ⊆ B of all boys that so far gave their feedback (either positive or negative) on g, but for whom the feedback from g is not available yet. In Step (2 G ), if B g,t is not empty, OOMM chooses a boy uniformly at random from B g,t , otherwise it selects a boy uniformly at random from the whole set B. [START_REF] Gentile | Online similarity prediction of networked data from known and unknown graphs[END_REF] Note that, the way it is designed, the selection of g and b does not depend on the signs σ(b, g) or σ(g, b) collected so far. The following theorem guarantees that EM T (OOMM) = Θ T n 2 M , which is as if we were able to directly sample in most of the T rounds pairs of reciprocal edges.

Theorem 2 Given any input graph ( B, G , E, σ), with |B| = |G| = n, if T -n = Ω(n) then E r T (OOMM) is selected uniformly at random (with replacement) from E r , its size |E r T (OOMM)| is such that E |E r T (OOMM)| = Θ(T )
, and the expected number of matches disclosed by OOMM is such that EM T (OOMM) = Θ T n 2 M . We now describe an optimal behavior (called Omniscient Matchmaker) that assumes prior knowledge of the whole edge sign assignment σ. This optimal behavior will be taken as a reference performance for our algorithm of Section 4. This will also help to better clarify our learning model.

Definition 1

The Omniscient Matchmaker A * is an optimal strategy based on the prior knowledge of the signs σ(b, g) and σ(g, b) for all b ∈ B and g ∈ G. Specifically, based on this information, A * maximizes the number of matches uncovered during T rounds over all n 2T possible selections that can be made in Steps (2 B ) and (2 G ). We denote this optimal number of matches by M * T = M T (A * ). Observe that when the matching graph M is such that deg M (u) > T n for some user u ∈ B ∪ G, no algorithm will be able to uncover all M matches in expectation, since Steps (1 B ) and (1 G ) of our learning protocol entail that the expected number of times each user u logs into the system is equal to T n . In fact, this holds even for the Omniscient Matchmaker A * , despite the prior knowledge of σ. For instance, when M turns out to be a random bipartite graph [START_REF] Hazan | Near-optimal algorithms for online matrix prediction[END_REF] the expected number of matches that any algorithm can achieve is always upper bounded by O T n 2 M (this is how Theorem 1 is proven). On the other hand, in order to have M * T = Θ(M ) as n grows large, it is sufficient that deg M (u) ≤ T n holds for all users u ∈ B ∪ G, even with such a random M. In order to avoid the pitfalls of M being a random bipartite graph (and hence the negative result of Theorem 1), we need to slightly depart from our general model of Section 2, and make structural assumptions on the way matches can be generated. The next section formulates such assumptions, and analyzes an algorithm that under these assumptions is essentially optimal i.t.o. number of uncovered matches. The assumptions and the algorithm itself are then validated against simple baselines on real-world data in the domain of online dating (Section 5).

A model based on clusterability of received feedback

In a nutshell, our model is based on the extent to which it is possible to arrange the users in (possibly) overlapping clusters by means of the feedbacks they may potentially receive from the other party. In order to formally describe our model, it will be convenient to introduce the Boolean preference matrices B, G ∈ {0, 1} n×n . These two matrices collect in their rows the ground truth contained in σ, separating the two parties B and G. Specifically,

B i,j = 1 2 (1 + σ(b i , g j ))
, and G i,j = 1 2 (1 + σ(g i , b j )) (these are essentially the matrices exemplified in Figure 1(b) where the "-1" signs therein are replaced by "0"). Then, we consider the n column vectors of B (resp. G) -i.e., the whole set of feedbacks that each g ∈ G (resp. b ∈ B) may receive from members of B (resp. G) and, for a given radius ρ ≥ 0, the associated covering number of this set of Boolean vectors w.r.t. Hamming distance. We recall that the covering number at radius ρ is the smallest number of balls of radius ≤ ρ that are needed to cover the entire set of n vectors. The smaller ρ the higher the covering number. If the covering number stays small despite a small ρ, then our n vectors can be clustered into a small number of clusters each one having a small (Hamming) radius. As we mentioned in Section 3, a reasonable model for this problem is one for which our learning task can be solved in a nontrival manner, thereby specifically avoiding the pitfalls of M being a random bipartite graph. It is therefore worth exploring what pairs of radii and covering numbers may be associated with the two preference matrices G and B when M is indeed random bipartite. Assume M = o(n 2 ), so as to avoid pathological cases. When M is random bipartite, one can show that we may have ρ = Ω M n even when the two covering numbers are both 1. Hence, the only interesting regime is when ρ = o M n . Within this regime, our broad modeling assumption is that the resulting covering numbers for G and B are o(n), i.e., less that linear in n when n grows large. Related work. The approach of clustering users according to their description/preference similarities while exploiting user feedback is similar in spirit to the two-sided clusterability assumptions investigated, e.g., in [1], which is based on a mixture of explicit and implicit (collaborative filteringlike) user features. Yet, as far as we are aware, ours is the first model that lends itself to a rigorous theoretical quantification of matchmaking performance (see Section 4.1). Moreover, in general in our case the user set is not partitioned as in previous RRS models. Each user may in fact belong to more than one cluster, which is apparently more natural for this problem. The reader might also wonder whether the reciprocal recommendation task and associated modeling assumptions share any similarity to the problem of (online) matrix completion/prediction. Recovering a matrix from a sample of its entries has been widely analyzed by a number of authors with different approaches, viewpoints, and assumptions, e.g., in Statistics and Optimization (e.g., [5, 12]), in Online Learning (e.g., [18, 19, 20, 9, 8, 6, 10]), and beyond. In fact, one may wonder if the problem of predicting the entries of matrices B and G may somehow be equivalent to the problem of disclosing matches between B and G. A closer look reveals that the two tasks are somewhat related, but not quite equivalent, since in reciprocal recommendation the task is to search for matching "ones" between the two binary matrices B and G by observing entries of the two matrices separately. In addition, because we get to see at each round the sign of two pairings (b, g ) and (g, b ), where b and g are drawn at random and b and g are selected by the matchmaker, our learning protocol is rather half-stochastic and half-active, which makes the way we gather information about matrix entries quite different from what is usually assumed in the available literature on matrix completion.

An efficient algorithm

Under the above modeling assumptions, our goal is to design an efficient matchmaker. We specifically focus on the ability of our algorithm to disclose Θ(M ) matches, in the regime where also the optimal number of matches M * T is Θ(M ). Recall from Section 3 that the latter assumption is needed so as to make the uncovering of Θ(M ) matches possible within the T rounds. Our algorithm, called SMILE (Sampling Matching Information Leaving out Exceptions) is described as Algorithm 2. The algorithm depends on input parameter S ∈ [log n, n/ log n] and, after randomly shuffling both B and G, operates in three phases: Phase 0 (described at the end), Phase I, and Phase II. Due to space limitations, the actual pseudocode of Cluster Estimation() and User Matching() is presented in the appendix. What follows is an an informal, yet precise, description of their functioning.

Phase I: Cluster Estimation. SMILE approximates the clustering over users by: i. asking, for each cluster representative b ∈ B, Θ(n) feedbacks (i.e., edge signs) selected at random from G (and operating symmetrically for each representative g ∈ G), ii. asking Θ(S)-many feedbacks for each remaining user, where parameter S will be set later. In doing so, SMILE will be in a position to estimate the clusters each user belongs to, that is, to estimate the matching graph M, the misprediction per user being w.h.p of the order of (n log n)/S. The estimated M will then be used in Phase II. A more detailed description of the Cluster Estimation procedure follows. For convenience, we focus on clustering G (hence observing feedbacks from B to G), the procedure operates in a completely symmetric way on B. Let F g be the set of all b ∈ B who provided feedback on g ∈ G so far. Assume for the moment we have at our disposal a subset G r ⊆ G containing one representative for each cluster over B, and that for each g ∈ G r we have already observed n/2 feedbacks provided by n/2 distinct members of B, selected uniformly at random from B. Also, let B(g, S) be a subset of B obtained by sampling at random S = 2S + 4 √ S log n-many b from B. Then a Chernoff-Hoeffding bound argument shows that for any g ∈ G \ G r and any g r ∈ G r we have w.h.p. |B(g, S) ∩ F g r | ≥ S. We use the above to estimate the cluster each g ∈ G \ G r belongs to. This task can be accomplished by finding g r ∈ G r who receives the same set of feedbacks as that of g, i.e., who belongs to the same cluster as g r . Yet, in the absence of the feedback provided by all b ∈ B to both g and g r , it is not possible to obtain this information with certainty. The algorithm simply estimates g's cluster by exploiting Step (1 B ) of the protocol to ask for feedback on g from S = S (S) randomly selected b ∈ B, which will be seen as forming the subset B(g, S). We shall therefore assign g to the cluster represented by an arbitrary g r ∈ G r such that s(b, g) = s(b, g r ) for all b ∈ B(g, S) ∩ F g r . We proceed this way for all g ∈ G \ G r . We now remove the assumption on G r . Although we initially do not have G r , we can build through a concentration argument an approximate version of G r while asking for the feedback B(g, S) on each unclustered g. The Cluster Estimation procedure does so by processing girls g sequentially, as described next. Recall that G was randomly shuffled into an ordered sequence G = {g 1 , g 2 , . . . , g n }. The algorithm maintains an index i over G that only moves forward, and collects feedback information for g i . At any given round, G r contains all cluster representatives found so far. Given b ∈ B that needs to be served during round t (Step (1 B )), we include b in F gi . If |F gi | becomes as big as S , then we look for g ∈ G r so as to estimate g i 's cluster. If we succeed, index i is incremented and the algorithm will collect feedback for g i during the next rounds. If we do not succeed, g i will be included in G r , and the algorithm will continue to collect feedback on

g i until |F gi | < n 2 . When |F gi | ≥ n 2
, index i is incremented, so as to consider the next member of G. Phase I terminates when we have estimated the cluster of each b and g that are themselves not representative of any cluster.

Finally, when we have concluded with one of the two sides, but not with the other (e.g., we are done with G but not with B), we continue with the unterminated side, while for the terminated one we can select members (g ∈ G in this case) in Step 2 (Step (2 B ) in this case) arbitrarily. Phase II: User matching. In phase II, we exploit the feedback collected in Phase I so as to match as many pairs (b, g) as possible. For each user u ∈ B ∪ G selected in Step (1 B ) or Step (1 G ), we pick in step (2 G ) or (2 B ) a user u from the other side such that u belongs to an estimated cluster which is among the set of clusters whose members are liked by u, and viceversa. When no such u exists, we select u from the other side arbitrarily. Phase 0: Estimating M . In the appendix we show that the optimal tuning of S is to set it as a function of the number of hidden matches M , i.e. S := (n 2 log n)/M . Since M is unknown, we run a preliminary phase where we run OOMM (from Section 3) for a few rounds. Using Theorem 2 it is not hard to show that the number T M of rounds taken by this preliminary phase to find an estimate M of M which is w.h.p. accurate up to a constant factor

T M = Θ (n 2 log n)/M .
In order to quantify the performance of SMILE, it will be convenient to refer to the definition of the Boolean preference matrices B, G ∈ {0, 1} n×n . For a given radius ρ ≥ 0, we denote by C G ρ the covering number of the n column vectors of B w.r.t. Hamming distance. In a similar fashion we define C B ρ . Moreover, let C G and C B be the total number of cluster representatives for girls and boys, respectively, found by SMILE, i.e., C G = |G r | and C B = |B r | at the end of the T rounds. The following theorem shows that when the optimal number of matches M * T is M , then so is also M T (SMILE) up to a constant factor, provided M and T are not too small. Theorem 3 Given any input graph ( B, G , E, σ), with |B| = |G| = n, such that M * T = M w.h.p. as n grows large, then we have Notice in the above theorem the role played by the upper bounds CG and CB . If the minimizing ρ therein gives CG = CB = n, we have enough degrees of freedom for M to be generated as a random bipartite graph. On the other hand, when CG and CB are significantly smaller than n at the minimizing ρ (which is what we expect to happen in practice) the resulting M will have a cluster structure that cannot be compatible with a random bipartite graph. This entails that on both sides of the bipartite graph, each subject receives from the other side a set of preferences that can be collectively clustered into a relatively small number of clusters with small intercluster distance. Then the number of rounds T that SMILE takes to achieve (up to a constant factor) the same number of matches M * T as the Omniscient Matchmaker drops significantly. In particular, when S in SMILE has the form (n 2 log n)/ M , where M is the value returned by Phase 0, we have the following result. In order to evaluate in detail the performance of SMILE, it is very interesting to show to what extent the conditions bounding from below T in Theorem 3 are necessary. We have the following general limitation, holding for any matchmaker A. We now explain why it is possible that, when M = ω n 3/2 √ log n , the additive term (n 3 log n)/M in the bound T = ω n ( CG + CB ) + (n 3 log n)/M of Corollary 1 becomes o(M ), while the first term n ( CG + CB ) can be upper bounded by n (C G 0 + C B 0 ). Since the lower bound T = Ω(n (C G 0 + C B 0 ) + M ) of Theorem 4 has a linear dependence on M , it might seem surprising that the larger M is the smaller becomes the second in the bound of Corollary 1. However, it is important to take into account that T in Corollary 1 must be large enough to also satisfy the condition M * T = M . Let T * be the number of rounds T necessary to satisfy w.h.p. M * T = M . In Corollary 1, both the conditions T ≥ T * and T = ω n ( CG + CB ) + (n 3 log n)/M must simultaneously hold. When M is large, the number of rounds needed to satisfy the former condition becomes much larger than the one needed for the latter.

C G ≤ CG def = min min ρ≥0 C G ρ/2 + 3ρS , n , C B ≤ CB def = min min ρ≥0 C B ρ/2 + 3ρS , n .
As a further insight, consider the following. We either have M = O n( CG + CB ) or M = ω n( CG + CB ) . In the first case, the lower bound in Theorem 4 clearly becomes

T = Ω n (C G 0 + C B 0 + CG + CB )
, hence not directly depending on M . In the second case, whenever M = ω n 3/2 √ log n , T * is larger than n ( CG + CB ) + (n 3 log n)/M since, by definition, we must have T * = Ω(M ), while in this case n ( CG + CB ) + (n 3 log n)/M = o(M ). In conclusion, if the number of rounds SMILE takes to uncover Θ(M ) matches equals the number of rounds taken by the omniscient Matchmaker to uncover exactly M matches, then SMILE is optimal up to a constant factor, because no algorithm can outperform the omniscient Matchmaker. This provides a crucially important insight into the key factors allowing the additive term (n 3 log n)/M to be equal to o(M ) in Corollary 1, and is indeed one of the keystones in the proof of Theorem 3.

We conclude this section by emphasizing the fact that SMILE is indeed quite scalable. As proven in the appendix, an implementation of SMILE exists that leverages a combined use of suitable data-structures, leading to both time and space efficiency.

Experiments

In this section, we evaluate the performance of (a variant of) our algorithm by empirically contrasting it to simple baselines against artificial and real-world datasets from the online dating domain. The comparison on real-world data also serves as a validation of our modeling assumptions. Datasets. The relevant properties of our datasets are given in Table 1. Each of our synthetic datasets has |B| = |G| = 2000. We randomly partitioned B and G into C B and C G clusters, respectively. Each boy likes all the girls of a cluster C with probability 0.2, and with probability 0.8 dislikes them.

C B C G #likes #matches C B C G C B C G C B C G S-20-23 20
We do the same for the preferences from girls to boy clusters. Finally, for each preference (either positive or negative) we reverse its sign with probability 1/(2 • log n) (in our case, n = 2000). Notice that in Table 1, for all four datasets we generated, the number of likes is bigger than |B| • |G|/2. As for real-world datasets, we used the one from [4], which is also publicly available. This is a dataset from a Czech dating website, where 220,970 users rate each other in a scale from 1 (worst) to 10 (best). The gender of the users is not always available. To get two disjoint parties B and G, where each user rates only users from the other party, we disregarded all users whose gender is not specified. As this dataset is very sparse, we extracted dense subsets as follows. We considered as "like" any rating > 2, while all ratings, including the missing ones, are "dislikes". Next, we iteratively removed the users with the smallest number of ratings until we met some desired density level. Specifically, we executed the above process until we obtained two sets B and G such that the number of likes between the two parties is at least 2(min{|B|, |G|}) Random baselines. We included as baselines OOMM , from Section 3, and a random method that asks a user for his/her feedback on another user (of opposite gender) picked uniformly at random. We refer to this algorithm as UROMM.

Implementation of SMILE. In the implementation of SMILE, we slightly deviated from the description in Section 4.1. One important modification is that we interleaved Phase I and Phase II. The high-level idea is to start exploiting immediately the clusters once some clusters are identified, without waiting to learn all of them. Additionally, we gave higher priority to exploring the reciprocal feedback of a discovered like, and we avoided doing so in the case of a dislike. Finally, whenever we test whether two users belong in the same cluster, we allowed a radius of a (1/ log n) fraction of the tested entries. The parameter S in SMILE has been set to S + √ S log n, with S = (n 2 log n)/ M , where M is the estimate from Phase 0. We call the resulting algorithm I-SMILE (Improved SMILE). Evaluation. To get a complete picture on the behavior of the algorithms for different time horizons, we present for each algorithm the number of discovered matches as a function of T ∈ {1, . . . , 2|B||G|}. Figure 2 contains three representative cases. In all datasets we tested, I-SMILE clearly outperforms UROMM and OOMM. Our experiments confirm that SMILE (and therefore I-SMILE) quickly learns the underlying structure of the likes between users, and uses this structure to reveal the matches between them. Moreover, the variant I-SMILE that we implemented allows one not only to perform well on graphs with no underlying structure in the likes, but also to discover matches during the exploration phase while learning the clusters.

Conclusions and Ongoing Research

We have initiated a theoretical investigation of the problem of reciprocal recommendation in an ad hoc model of sequential learning. Under suitable clusterability assumptions, we have introduced an efficient matchmaker called SMILE , and have proven its ability to uncover matches at a speed comparable to the omniscient Matchmaker, so long as M and T are not too small (Theorem 3 and Corollary 1). Our theoretical findings also include a computational complexity analysis (Theorem 5), as well as limitations on the number of disclosable matches in both the general (Theorem 1) and the cluster case (Theorem 4). We complemented our results with an initial set of experiments on synthetic and real-world datasets in the online dating domain, showing encouraging evidence. Current ongoing research includes: i. Introducing suitable noise models for the sign function σ. ii. Generalizing our learning model to nonbinary feedback preferences. iii. Investigating algorithms whose goal is to maximize the area under the curve "number of matches-vs-time", i.e., the criterion t∈[T ] M t (A) , rather than the one we analyzed in this paper; maximizing this criterion requires interleaving the phases where we collect matches (exploration) and the phases where we do actually disclose them (exploitation). iv. More experimental comparisons on different datasets against heuristic approaches available in the literature. v. Incorporating in the protocol different frequencies for the user logins.

Figure 1 :

 1 Figure 1: (a) The (complete and directed) bipartite graph ( B, G , E, σ) with n = |B| = |G| = 4, edges are only sketched. (b) Representation of the σ function through its two pieces σ : B × G → {-1, +1} (B × G matrix on the left), and σ : G × B → {-1, +1} (G × B matrix on the right). For instance, in this graph, Boy 1 likes Girl 1 and Girl 3, and dislikes Girl 2 and Girl 4, while Girl 3 likes Boy 1, and dislikes Boys 2, 3, and 4. Out of the n 2 = 16 pairs of reciprocal edges, this graph admits only M = 4 matches, which are denoted by green circles on both matrices. For instance, the pairing of edges (1, 3) and (3, 1) are a match since Boy 1 likes Girl 3 and, at the same time, Girl 3 likes Boy 1. (c) The associated (undirected and bipartite) matching graph M. We have, for instance, deg M (Girl 1) = 3, and deg M (Boy 2) = 1.

Algorithm 1 :

 1 OOMM (Oblivious Online Match Maker) INPUT : B and G At each round t: (2 B ) Select g uniformly at random from G ; (2 G ) B g,t ← {b ∈ B : (b , g) ∈ E t (OOMM), (g, b ) ∈ E t-1 (OOMM)}; If B g,t = ∅ then select b uniformly at random from B g,t else select b uniformly at random from B .

Algorithm 2 :

 2 SMILE (Sampling Matching Information Leaving out Exceptions) INPUT : B and G; parameter S > 0. Randomly shuffle sets B and G ; Phase 0: Run OOMM to provide an estimate M of M ; Phase I: (C, F) ← Cluster Estimation( B, G , S); Phase II: User Matching( B, G , (C, F));

  Furthermore, when T and M are such that T = ω n( CG + CB + S ) and M = ω n 2 log n S , then we have w.h.p. M T (SMILE) = Θ(M ) .

Corollary 1

 1 Given any input graph ( B, G , E, σ), with |B| = |G| = n, such that M * T = M w.h.p. as n grows large, with T and M satisfying T = ω n ( CG + CB ) + (n 3 log n)/M , where CG and CB are the upper bounds on C G and C B given in Theorem 3, then we have w.h.p. M T (SMILE) = Θ(M ) .

Theorem 4 7 CB

 47 Given B and G such that |B| = |G| = n, any integer m ∈ (n log n, n 2 -n log n) , and any algorithm A operating on ( B, G , E, σ), there exists a randomized strategy for generating σ such that m -n C G 0 +C B 0 -1 < M ≤ m, and the number of rounds T needed to achieve EM T (A) = Θ(M ), satisfies T = Ω(n (C G 0 + C B 0 ) + M ) , as n → ∞. Remark 1 One can verify that the time bound for SMILE established in Corollary 1 is nearly optimal whenever M = ω n 3/2 √ log n . To see this, observe that by definition we have CG ≤ C G 0 and ≤ C B 0 . Now, if M = ω n 3/2 √ log n , then the additive term (n 3 log n)/M becomes o(M ) and the condition on T in Corollary 1 simply becomes T = ω n (C G 0 + C B 0 + M ) , where M = o(M ). This has to be contrasted to the lower bound on T contained in Theorem 4.

Theorem 5

 5 Let CG and CB be the upper bounds on C G and C B given in Theorem 3. Then the running time of SMILE is O T + n S CG + CB , the memory requirement is O(n ( CG + CB )). Furthermore, when T = ω n ( CG + CB ) + (n 3 log n)/M , as required by Corollary 1, the amortized time per round is Θ(1) + o( CG + CB ), which is always sublinear in n.

Figure 2 :

 2 Figure 2: Empirical comparison of the three algorithms on datasets S-95-100 (left), RW-1007-1286 (middle), RW-2265-3939 (right). Each plot gives number of disclosed matches vs. time.

Table 1 :

 1 Relevant

			23	2.45M	374K	20	23	20	23	445	429
	S-95-100	95	100	2.46M	377K	95	100	95	100	603	624
	S-500-480	500	480	2.47M	380K	500	480	500	480	983	950
	S-2000-2000	2000	2000	2.47M	382K	2000	2000	2000	2000	2000	2000
					Real-world datasets
		|B|	|G|	#likes	#matches	C B	C G	C B	C G	C B	C G
	RW-1007-1286	1007	1286	125K	13.9K	53	48	177	216	385	508
	RW-1526-2564	1526	2564	227K	19.6K	37	45	138	216	339	601
	RW-2265-3939	2265	3939	370K	25.0K	42	45	145	215	306	622

properties of our datasets. The last six columns present an approximation to the number of clusters when we allow radius 2 • n/ log n, n/ log n, and 0.5 • n/ log n between users of the same cluster.

  3/2 (resulting in dataset RW-1007-1286), 1.75(min{|B|, |G|}) 3/2 (dataset RW-1526-2564), or 1.5(min{|B|, |G|}) 3/2 (dataset RW-2265-3939).

https://www.linkedin.com/.

https://tinder.com.

32nd Conference on Neural Information Processing Systems (NIPS 2018), Montréal, Canada.

https://badiapp.com/en.

For instance, users in an online dating system have relevant visual features, and the system needs specific care in removing popular user bias, i.e., ensuring that popular users are not recommended more often than unpopular ones.

Though different distributional assumptions could be made, for technical simplicity in this paper we decided to focus on the uniform distribution only.

All proofs are provided in the appendix.

Recall that an upper bound on MT (A) is a negative result here, since we are aimed at making MT (A) as large as possible.

A boy could be selected more than once while serving a girl g during the T rounds. The optimality of OOMM (see Theorems 1 and 2) implies that this redundancy does not significantly affect OOMM's performance.

The matching graph M is a random bipartite graph if any edge (b, g) ∈ B × G is generated independently with the same probability p ∈ [0, 1].

Acknowledgements

We would like to thank the anonymous reviewers for their valuable comments and suggestions that helped improving the presentation of this paper. Special thanks to Flavio Chierichetti and Marc Tommasi for helpful discussions in early stages of our investigation. Fabio Vitale acknowledges support from the ERC Starting Grant "DMAP 680153", the Google Focused Award "ALL4AI", and grant "Dipartimenti di Eccellenza 2018-2022", awarded to the Department of Computer Science of Sapienza University.