Benjamin Girault

Paulo Gonc ¸alves ⋄

Éric Fleury

Arashpreet Singh Mor

SEMI-SUPERVISED LEARNING FOR GRAPH TO SIGNAL MAPPING: A GRAPH SIGNAL WIENER FILTER INTERPRETATION

Keywords: Signal processing on graphs, Semisupervised learning, Spectral analysis, Network science

In this contribution, we investigate a graph to signal mapping with the objective of analysing intricate structural properties of graphs with tools borrowed from signal processing. We successfully use a graph-based semi-supervised learning approach to map nodes of a graph to signal amplitudes such that the resulting time series is smooth and the procedure efficient and scalable.

Theoretical analysis of this method reveals that it essentially amounts to a linear graph-shift-invariant filter with the a priori knowledge put into the training set as input. Further analysis shows that we can interpret this filter as a Wiener filter on graphs. We finally build upon this interpretation to improve our results.

INTRODUCTION

Network science is expanding rapidly with the availability of large datasets issued from complex systems. In a wide range of applications, the amount of collected data comes with an intricate organisation that is naturally or adequately captured by a graph structure. In that case, the relevant information often lies in the weighted edges that measure the strength binding entities viewed as nodes of a graph. Depending on the entities -computers in communication networks [START_REF] Easley | Networks, Crowds, and Markets: Reasoning About a Highly Connected World[END_REF], individuals in social or peer-to-peer networks [START_REF] Boldi | The webgraph framework I: compression techniques[END_REF] or proteins in biological systems [START_REF] Jonsson | Cluster analysis of networks generated through homology: automatic identification of important protein communities involved in cancer metastasis[END_REF], to cite only a few -the nature of the interactions can be manifold: capacities, contacts, similarities. . . However, usual graph analytics do not always succeed in revealing or characterising the relational complexity of the underlying systems, such as communities or hidden patterns. One alternative, constructed on a duality principle, is then to associate to the graph structure a dual random walk time series whose states correspond to the nodes and where the transitions are encoded by the graph edges [START_REF] Campanharo | Duality between Time Series and Networks[END_REF]. Thanks to this duality, graph analytics transposes to a signal analysis problem that can benefit from a rich signal processing toolkit.

In other scenarios, each node of a graph is itself the support of a measure (scalar or vector) that can be interpreted as one sample of a graph signal. This is for instance the case for temperatures delivered by a sensor network [START_REF] Sandryhaila | Discrete Signal Processing on Graphs: Frequency Analysis[END_REF], activity of brain functional regions [START_REF] Hagmann | Mapping the Structural Core of Human Cerebral Cortex[END_REF], or bacteria strains carried by interacting people [START_REF] Girault | Graphe de contacts et ondelettes : étude d'une diffusion bactérienne[END_REF]. The analysis of these high-dimensional signals supported by complex structures, as arbitrary graphs, generates a crescent interest [START_REF] Shuman | The Emerging Field of Signal Processing on Graphs: Extending High-Dimensional Data Analysis to Networks and Other Irregular Domains[END_REF] but faces the difficulty that they do not necessarily live in a Euclidean vector space. Therefore, extending the standard algorithms of signal (or image) processing to these structured objects is a topical challenge that already has marked successes. That is notably the case with the diffusion wavelets [START_REF] Coifman | Diffusion wavelets[END_REF], the wavelets on graphs [START_REF] Hammond | Wavelets on graphs via spectral graph theory[END_REF] and more generally the emerging field of discrete signal processing on graphs [START_REF] Shuman | The Emerging Field of Signal Processing on Graphs: Extending High-Dimensional Data Analysis to Networks and Other Irregular Domains[END_REF][START_REF] Sandryhaila | Discrete Signal Processing on Graphs[END_REF].

In this contribution, we first tackle the problem of finding a sensible mapping between the nodes of a graph and the states of a dual time series. To this end, we propose to use graph-based semisupervised learning methods [START_REF] Zhu | Introduction to Semi-Supervised Learning[END_REF] and we show that the results outperform standard approaches in many ways: (i) the resulting mapping entails dual signals that are smoother; (ii) the solution is unique; and (iii) algebraically scalable to massive datasets.

In a second step, we give this graph-based semi-supervised learning mapping an interpretation in terms of spectral filtering. Notably, we demonstrate that it corresponds to a linear graph-shift invariant filter, in accordance with the theoretical framework developed in [START_REF] Sandryhaila | Discrete Signal Processing on Graphs[END_REF]. In addition, we introduce the notion of Wiener filter in the context of graph signals, thus contributing to enrich the toolbox of graph signal processing.

DUALITY BETWEEN TIME SERIES AND GRAPHS

Notations and State of the Art

We consider a discrete graph structure that we note G = (V, E), with V the set of nodes (|V | = N ) and E ⊆ V × V the set of edges between any two nodes. We call W the adjacency matrix whose entries {wij} 1≤i,j≤N are the weights of each existing edge e = (i, j) ∈ E and zero if the nodes i and j are not connected. Let D = {dii = N j=1 wij} 1≤i≤N be the diagonal matrix of the nodes' degree. Finally, we denote

L = D -1/2 (D -W )D -1/2 the normalised graph Laplacian.
It is common practice to map time series into graph objects with the aim of using the relational or the geometric structures of the latter to better characterise certain hidden dynamics of the former (see [START_REF] Donner | Recurrence-Based Time Series Analysis by Means of Complex Network Methods[END_REF] for a survey of a number of proposed mappings). Although the converse transformation is less frequent, it raised a recent and strong interest where the rich arsenal of signal processing techniques could be exploited to reveal interesting structural or dynamic properties of complex networks.

Schematically, we can distinguish two possible approaches to perform this mapping: one relies on a decomposition of the matrix form W of the graph into node-series that can be interpreted as many dual time series of the graph. A particularly interesting case uses multidimensional scaling methods and shows very promising results [START_REF] Shimada | From Networks to Time Series[END_REF][START_REF] Hamon | Transformation de graphes dynamiques en signaux non stationnaires[END_REF]. On the other hand, a more direct approach consists to establish a one-to-one correspondence between the nodes of the graph and a set of values (integers, real intervals, sequences. . . ) that the time series can take on. Then, after proper normalisation, the weights wij are interpreted as transition probabilities between the different amplitude levels of a random walk.

In this direction, the certainly most accomplished work is presented in [START_REF] Campanharo | Duality between Time Series and Networks[END_REF] and proposes to find a permutation (or renumbering) p : {1, . . . , N } → {1, . . . , N } so as to reorder the N nodes of the graph according to their affinity as measured by the weights. More precisely, the sought permutation p * is solution of the following optimisation problem:

p * = argmin p N i=1 N j=1 wij|p(i) -p(j)|, (1)
imposing p(i) and p(j) to be close in the mapped space when wij is large, that is for strongly tied nodes i and j. The dual time series are then generated as random walks visiting the different mapped amplitude states. One motivation behind this procedure is to get smooth time series, by precluding too frequent strong discontinuities in the signal due to transitions between distant amplitudes. As a striking illustration, we consider the oriented cyclic graph of Fig. 1a to which we apply the procedure described in [START_REF] Campanharo | Duality between Time Series and Networks[END_REF]. Here, assuming an initial sequential numbering of the nodes, and owing to the cyclic structure of the graph, one trivial permutation p * is the identity yielding the periodic dual time series of the plot 1b. However, the optimisation problem of Eq. ( 1) is a NP-hard quadratic assignment problem, which does not systematically have a unique solution. To circumvent this issue, the authors of [START_REF] Campanharo | Duality between Time Series and Networks[END_REF] propose to use the simulated annealing heuristic that leads to an approximated solution of p * with no closed-form expression. In the case of the cyclic graph, we can easily verify that other permutations satisfying (1) exist, yielding different periodic time series as the one plotted in Fig. 1c.

Regarding smoothness, the sawtooth solution shows one strong discontinuity per period. Intuitively though, one would expect the cyclic graph to be dual of a discretised pure sine wave, a C ∞ periodic function. However, we can easily convince ourselves that no mapping of {1, . . . , N } onto itself can lead to a pure harmonic signal as solution of the dual problem stated in [START_REF] Campanharo | Duality between Time Series and Networks[END_REF].

Duality and Graph-Based Semi-Supervised Learning

We propose to reformulate the mapping problem exposed in the previous section, as a classification problem using graph-based semisupervised learning (SSL) methods [START_REF] Zhu | Introduction to Semi-Supervised Learning[END_REF]. Before adapting it to our specific problem, we first recall the main lines of SSL. The goal of graph-based SSL is to assign each node i ∈ V of a non-oriented graph G = (V, E) of size N , to a class k(i) ∈ {1, . . . , K}, taking into account relations of dependence between nodes, via the weights {wij} 1≤i,j≤N , and using a few labelled nodes as training set.

Formally, we write this training set as a label matrix Y of size N -by-K where each row corresponds to a node in the graph, and each column corresponds to a class k ∈ {1, . . . , K}. For a labelled node i, for which a ground truth k(i) ∈ {1, . . . , K} is known, only the entry Y i,k(i) = 1 while Y i,k ′ = 0, ∀k ′ = k(i). For unlabelled nodes, the corresponding rows of Y are identically set to zero. The objective of the generalised graph-based SSL derived in [START_REF] Zhu | Introduction to Semi-Supervised Learning[END_REF] is to find the classification matrix F of the same size as Y and solution of the following optimisation problem:

min F K k=1 D σ-1 2 (F .k -Y .k ) 2 2 fitting term +α D σ-1 2 F .k 2 L penalty . (2)
We readily recognise in this setting the expression of a regularised inverse problem where the fitting term forces the sought solution F to match the training set Y and where the penalising term constrains the solution F to be smooth with respect to the Laplacian semi-norm of the underlying graph. In this expression also, the regularisation factor α allows to tune the trade-off between these two effects and σ is a free unifying parameter that was introduced in [START_REF] Sokol | Generalized Optimization Framework for Graph-based Semisupervised Learning[END_REF] to get a canonical formulation of different semi-supervised machine learning methods: standard (σ = 1) or normalised (σ = 1/2) Laplacian, PageRank (σ = 0). Then, according to [START_REF] Sokol | Generalized Optimization Framework for Graph-based Semisupervised Learning[END_REF][START_REF] Varah | A Practical Examination of Some Numerical Methods for Linear Discrete Ill-Posed Problems[END_REF], the solution of (2) has a closed-form expression that reads:

F = Cσ,αY s.t. Cσ,α = (1 + α)IN -αD -σ W D σ-1 -1 . (3)
The classification task is then to assign to each node i the class

k(i) = argmax k ′ F i,k ′ .
As it is thoroughly commented in [START_REF] Avrachenkov | On the Choice of Kernel and Labelled Data in Semi-supervised Learning Methods[END_REF], SSL methods show to perform remarkably well when only a few labelled points are known.

Let us now apply this SSL scheme to our mapping problem, seeking for a more relevant and easier to determine mapping between the nodes of the graph and the amplitudes set of the corresponding time series. To start with, we must identify sensible classes of the nodes and a corresponding training set. Actually, this choice is relatively free, and therefore we adopt the most obvious one that amounts to identify two most distant nodes in the graph (w.r.t. the shortest path) and to label those as the centroids of two distinct classes. With this choice, the label matrix Y encompasses only two columns, each of them having only one non-zero entry for its associated centroid. Then, computing straightforwardly the solution given by expression (3), yields for a given σ and α, a classification matrix F with only two columns and real entries comprised in the interval [0, 1]. Now, instead of sorting the coefficients Fi,1 and Fi,2 to determine the class of each node i, we form the function defined on each node:

X(i) = Fi,1 -Fi,2 Fi,1 + Fi,2 , (4)
corresponding to its relative position with respect to the two classes.

It is this function that we directly associate to a mapping from the nodes indices {1, . . . , N } onto the time series amplitudes lying in the interval [-1, 1]. Applied to our toy example of an oriented cyclic graph1 , the resulting dual time series corresponding to different choices for the regularisation parameter α are plotted in Fig. 2. Let us notice that in this particular case, the matrix D of degrees is equal to the identity matrix and therefore the choice of σ has no effect on the solution F . In contrast to the permutation solution of Eq. ( 1), each of these mappings is uniquely derived from the closed-form expression (3) and scalable to very large datasets [START_REF] Avrachenkov | Classification of content and users in BitTorrent by semisupervised learning methods[END_REF]. Moreover, regarding our original motivation about smoothness of the dual time series, a pertinent choice of α yields a harmonic-like solution (see Fig. 2b) as the paradigm that one would naturally expect for a smooth periodic function.

SEMI-SUPERVISED LEARNING AS A GRAPH SIGNAL FILTER

As we saw in the previous section, the SSL classifier can be viewed as an operator whose input is a K-dimensional signal Y defined on the graph and the output, a transformed version F of it. We now show in a more general setting, that the SSL solution of Eq. ( 2) is the output of a linear, shift-invariant filter consistent with the discrete signal processing on graphs theory developed in [START_REF] Sandryhaila | Discrete Signal Processing on Graphs[END_REF]. Furthermore, we identify the frequency response of this regularising SSL operator to a Wiener filter. Thereafter, we consider only non-oriented graphs with doubly stochastic adjacency matrices W , leading in particular to identity matrices D and to Laplacians of the form L = IN -W .

Graph filters

In [START_REF] Sandryhaila | Discrete Signal Processing on Graphs[END_REF], the authors generalised the linear shift-invariant filter theory on discrete signals to graph signals. In their framework, the usual time-shift operator is replaced by a graph-shift operator simply defined as the multiplication by the adjacency matrix. Then, a filter on a graph signal is said to be linear shift-invariant if it verifies the superposition principle and commutes with the graph-shift operator.

We use two important results from [START_REF] Sandryhaila | Discrete Signal Processing on Graphs[END_REF]: (i) a filter H is linear shift invariant on a graph signal if and only if it can be written as a polynomial in the graph shift operator h(W ) 2 . (ii) Given the diagonalisation W = U ΛU T and identifying eigenvectors of the graph shift to eigenmodes, by analogy to the standard case, the Fourier operator on graphs is defined by F = U -1 = U T . Formally then, the analogue of the convolution of a graph signal s with a filter H can be expressed as Hs = h(Λ) s, where • denotes the Fourier transform and h is the polynomial form of H.

2 Additionally, a general condition is assumed on W which in our case amounts to say that all the eigenvalues of W must have a onemultiplicity. This condition is circumvented, as suggested in [START_REF] Sandryhaila | Discrete Signal Processing on Graphs[END_REF], using an equivalent filter on a graph shift operator W ′ constructed by slightly changing the eigenvalues of W .

Let us now use the diagonalisation of W and rewrite the semisupervised learning operator Cσ,α defined in Eq. (3) as:

Cσ,α = U (1 + α)IN -αΛ -1 U T = N i=1 ui 1 (1 + α) -αλi u T i = N i=1 ui gα(λi) u T i . (5)
Since the set of entries {λi : i ∈ {1, . . . , N }} of the diagonal matrix Λ is finite, we can find an interpolating polynomial hα(λ) verifying ∀i ∈ {1, . . . , N }, hα(λi) = gα(λi). Then, Eq. ( 5) reads:

Cσ,α = U hα(Λ)U T = hα(W ), (6)
thus proving that the SSL operator Cσ,α is a linear shift-invariant graph filter on Y .

In standard Fourier analysis on L 2 (R), the eigenvalues of the continuous Laplacian operator are the square of its eigenfrequencies. By identification and recalling that we considered graphs such that L = IN -W , we pose ωi = √ 1 -λi, ∀i ∈ {1, . . . , N }, the eigenfrequencies of the graph. With this change of variables, the (eigen-)frequency response of the SSL filter becomes:

gα(ωi) = gα(1 -ω 2 i ) = 1 1 + αω 2 i . (7)
We recognise in the above expression [START_REF] Girault | Graphe de contacts et ondelettes : étude d'une diffusion bactérienne[END_REF], the frequency response of an optimal Wiener filter found in usual signal processing theory to solve the following problem: let y = x + η, be the observation of a signal x corrupted by an additive white Gaussian noise η independent of x. Estimating x faces an ill-posed inverse problem that we tackle imposing a Tikhonov regularisation on the least square regression. Choosing, as the penalty, to minimise the L 2 -norm of the gradient, or equivalently the Laplacian, yields a similar form as in [START_REF] Girault | Graphe de contacts et ondelettes : étude d'une diffusion bactérienne[END_REF], where α is the inverse of the signal to noise ratio [START_REF] Feigin | Anisotropic Regularization for Inverse Problems with Application to the Wiener Filter with Gaussian and Impulse Noise[END_REF].

Graph signal Wiener filter and duality

Let us reinterpret the smooth mapping we obtained from semisupervised learning applied to the oriented cyclic graph of Fig. 1a, in the light of the Wiener filtering of a graph signal. Using Eq. ( 4), we transformed the initial classification problem into the estimation of a one-dimensional function X defined on the nodes of a graph. Following the same lines, we can consider the label matrix Y of Eq. ( 3) to be the observation measured on the nodes of a graph and being the input of the Wiener-like SSL filter. For instance, we can assume that the time series plotted in Fig. 1c, is a rough and possibly noisy version of an underlying smooth signal that we want to recover using SSL filtering. Fig. 3 shows the results obtained for different values of the regularisation parameter α. Plots in the left column represent the input Y (i) and the output X(i) of the SSL filter. The right column displays the corresponding Graph-Fourier transforms Y (λi) and X(λi) superimposed to the frequency response of the low-pass filters of expression [START_REF] Girault | Graphe de contacts et ondelettes : étude d'une diffusion bactérienne[END_REF].

A small value of the regularisation parameter (α = 0.1 in the top plots) is not very stringent on the smoothness penalty in relation [START_REF] Boldi | The webgraph framework I: compression techniques[END_REF]. By contrast, it gives a high confidence to the observation, which is reflected by a SSL filter with a all-pass frequency response that leaves the input almost unchanged. Conversely, an overstressed regularisation term (α = 1000 in the bottom plots) overwrites the entire relevance of the input, with an equivalent SSL filter that zeroes all the frequency modes in the spectral domain. Finally, α = 10 (middle plots) yields a low-pass SSL filter with a cut-off frequency that preserves the first harmonic only. The corresponding output achieves a a good trade-off between smoothness and coherence with the input.

CONCLUSIONS

The main contribution of the current paper is twofold: on one hand, it introduces a graph-based semi-supervised learning technique to derive more adaptive and more efficient mappings between graphs and time series. Compared to the state-of-the-art, our method yields smoother time series that are easier to analyse in general. Moreover, the formulation we proposed leads to a unique solution, whose closed-form expression is algebraically straightforward and scalable to large datasets. On the other hand, our work bridges an original connection between graph-based semi-supervised learning and the theory of linear graph-shift invariant filters, with special emphasis on optimal Wiener filters. Since SSL techniques form a wide class of statistical classifiers, they open further research directions. We first plan to benefit from key characteristics of SSL to investigate adaptive mappings that match the changes of dynamic graphs. We also conduct an ongoing work to investigate the use of N classes instead of only 2, bearing in mind to take advantage of the classifier to derive efficient algorithms for mining multiscale communities.

By revisiting graph-based semi-supervised learning in terms of linear graph-shift invariant signal filtering, we embedded the duality problem into a more general framework of signal recovery from noisy observations. Under this angle, we believe that we can leverage the assets of SSL to better deal with uncertainty. Here, uncertainty may relate to the signal observed on the nodes of the graph (e.g. the a priori knowledge of a training set), or to the graph structure itself which may be known only partially or unreliably.

Finally, in the present contribution, we focused on graphs corresponding to doubly stochastic weight matrices. An important question that is left open is to better understand the role of the canonical parameter σ in the relation ( 2) and its impact on the (general) eigenvectors of the weight matrix W . We are currently considering general graphs beyond the case of Markov matrices.

Fig. 1 .

 1 Fig. 1. (a) Cyclic oriented graph (N = 20). (b)-(c) Periodic time series, dual of the cyclic graph and corresponding to two distinct permutations p * , solutions of Eq. (1)

Fig. 2 .

 2 Fig. 2. Dual signals of the non-oriented cyclic graph where the mappings stem from graph-based semi-supervised learning methods (σ = 1/2) with different regularisation parameters α.

Fig. 3 .

 3 Fig.3. Semi-supervised learning as a graph signal filter. Left column: input (black dashed) and output (blue plain) of the SSL filter. Right column: frequency response (red curve) of the SSL filter (Eq. (7)) superimposed to the graph Fourier transforms of the input (black) and of the output (blue). Top row: α = 0.1. Middle row: α = 10. Bottom row: α = 1000.

To apply SSL methods on oriented graphs, we first symmetrize the weight matrix (W T + W )/2. This operation does not alter the proximity relations between nodes, and therefore does not hinder the pertinence of the mapping. The orientation of the links is taken into account when generating the states transitions in the dual random walk.


Odalric-Ambrym Maillard
email: odalric-ambrym.maillard@ens-cachan.org

Shie Mannor

Latent Bandits

Keywords: Multi-armed Bandits, Latent variables, Regret analysis

We consider a multi-armed bandit problem where the reward distributions are indexed by two sets -one for arms, one for type-and can be partitioned into a small number of clusters according to the type. First, we consider the setting where all reward distributions are known and all types have the same underlying cluster, the type's identity is, however, unknown. Second, we study the case where types may come from different classes, which is significantly more challenging. Finally, we tackle the case where the reward distributions are completely unknown. In each setting, we introduce specific algorithms and derive non-trivial regret performance. Numerical experiments show that, in the most challenging agnostic case, the proposed algorithm achieves excellent performance in difficult scenarios.

Introduction

In a recommender system [START_REF] Li | A contextual-bandit approach to personalized news article recommendation[END_REF][START_REF] Li | Unbiased offline evaluation of contextual-bandit-based news article recommendation algorithms[END_REF]; [START_REF] Adomavicius | Toward the next generation of recommender systems : A survey of the state-of-the-art and possible extensions[END_REF], an agent must display an ad to each incoming client, and a context vector summarizes the observed properties of a client, such as its navigation history or its geographic localization. In a cognitive radio [START_REF] Avner | Decoupling exploration and exploitation in multi-armed bandits[END_REF]; [START_REF] Filippi | A near optimal policy for channel allocation in cognitive radio[END_REF], an agent must select a communication channel, based on its current known location and network conditions, while avoiding collision with other sources (such as radar, WiFI, etc). Both examples can be analyzed within the contextual-multi-armed bandit framework [START_REF] Langford | The Epoch-Greedy Algorithm for Multi-armed Bandits with Side Information[END_REF]; [START_REF] Pál | Contextual multi-armed bandits[END_REF], where the contexts summarize the information available to the learner. However, the context alone may not be sufficient to solve these problems optimally : In recommender systems, information such as gender or salary, is typically missing (due to privacy). In cognitive radios, information that a source (or an existing user) is close or far is unknown. In both cases, important information about the reward structure is not observed. Such would enable to classify similar situations and possibly output much better predictions.

We study in this paper the underlying problem that we call the latent multi-armed bandit problem (we do not consider the contextual part of the problem, that is handled by previous work). More formally, let {ν a,b } a∈A,b∈B be a set of real-valued probability distributions, that is indexed by two finite sets A of items (actions) and B of types. For clarity, and to highlight the role of latent information, we assume that both sets are finite. Extension to continuous parametric settings such as linear contextual-bandit [START_REF] Abbasi-Yadkori Y | Improved algorithms for linear stochastic bandits[END_REF]; [START_REF] Hayes | Stochastic Linear Optimization under Bandit Feedback[END_REF] is straightforward. We denote µ a,b ∈ R the mean of ν a,b and assume ν a,b to be R-sub-Gaussian (with known R), that is

∀λ ∈ R log E ν a,b exp (λ(X -µ a,b )) R 2 λ 2 /2 .
(1)

At each step n ∈ N, Nature selects some b n ∈ B according to some unknown stochastic process Υ. Then b n is revealed, and we must select some a n ∈ A. Finally, a reward X n is sampled from ν an,bn and observed. Our goal is to find for all N a sequence of actions a 1:N = {a n } 1 n N with maximal cumulated reward. The optimal sequence is given by {⋆ bn } n∈N where ⋆ b ∈ argmax a∈A E X∼ν a,b [X]. The expected regret of an algorithm A that produces a sequence of actions a 1:N is then simply defined by

R A N = N n=1 E Xn∼ν ⋆ bn ,bn X n - N n=1
E Xn∼ν an ,bn X n .

We model the latent information by assuming that B is partitioned into C clusters C = {B c } c=1,...,C such that the distributions {ν a,b } a∈A are the same for each b ∈ B c . This common distribution is denoted ν a,c and called a cluster distribution. We denote the optimal action in B c by ⋆ c , and introduce the optimality gaps ∆ a,c = µ ⋆c,cµ a,c . Both the partition and the number of clusters are unknown. In the recommender system example, B would be the set of Ids of users having a same context, partitioned for instance into C = 4 groups according to whether the user is a Male/Female and has High/Low income. In the cognitive radio scenario, B could represent hours of the day, partitioned into C = 2 3 parts according to three local radios being active or not1 .

Previous work

In [START_REF] Agrawal R | Asymptotically Efficient Adaptive Allocation Schemes for Controlled I.I.D. processes[END_REF] and more recently in [START_REF]Deviations of stochastic bandit regret[END_REF] the case when all cluster distributions are known and all users b come from the same unknown cluster c is considered. In this already non-trivial setting, [START_REF] Agrawal R | Asymptotically Efficient Adaptive Allocation Schemes for Controlled I.I.D. processes[END_REF] provided an asymptotic lower bound that significantly differs from the standard lower bound known for the multi-armed bandit problem [START_REF] Lai | Asymptotically efficient adaptive allocation rules[END_REF]; [START_REF] Burnetas | Optimal adaptive policies for sequential allocation problems[END_REF], thus showing that the problem is intrinsically different from a bandit problem.

They also analyze a near-optimal (yet costly) algorithm for that problem. In Salomon & Audibert (2011), a simpler algorithm is introduced and analyzed with less tight guarantee. We contribute to that setting in Section 2 with a tighter regret bound for a simple algorithm. We then consider two challenging extensions. In Section 3 users may come from different (instead of one) clusters, and in Section 4 nothing is known about the environment. These new settings could be loosely related to [START_REF] Slivkins | Contextual bandits with similarity information[END_REF] and [START_REF] Hazan | Online learning with prior knowledge[END_REF], as well as to the recent work [START_REF] Gheshlaghi Azar | Sequential transfer in multi-armed bandit with finite set of models[END_REF].

Contribution

In Section 2, we review the important case when the cluster distributions {ν a,c } a∈A,c∈C are known, and all users come from the same cluster c. We provide intuition about the setting, introduce a new algorithm called Single-K-UCB that is computationally less demanding than that of [START_REF] Agrawal R | Asymptotically Efficient Adaptive Allocation Schemes for Controlled I.I.D. processes[END_REF], and prove an explicit finite-time bound (Theorem 4) on its regret, improving on Salomon & Audibert (2011). In Section 3, we analyze the significantly harder and largely unaddressed setting when the cluster distributions are still known, but the users may now come from all clusters. We provide a lower bound (Theorem 5) showing that when the number of clusters is too large with respect to the time horizon, sub-linear regret is not attainable. We introduce an algorithm called Multiple-K-UCB and prove a nontrivial regret bound (Theorem 6) that makes explicit the effect of the distribution of users Υ on the regret. In Section 4, we target the challenging setting when nothing is known (neither Υ, the cluster distributions, nor even the number of clusters). We provide regret bounds for benchmark UCB-like algorithms (Theorem 7), and a new algorithm called A-UCB. Despite the very general setting and poor available information, we are able to prove a weak result (Proposition 1), that enables us to deduce a regret guarantee under mild conditions on the structure of arms (Lemma 1,2). Numerical simulations show in Section 4.2 that the introduced algorithm achieves excellent performance in a number of hard situations. All proofs are provided in the extended version [START_REF] Mannor | Latent bandits[END_REF].

Notations. At round n, we denote the number of observations for the pair (a, b) by N a,b (n) = n t=1 I{a t = a, b t = b} and use ν a,b (n) and µ a,b (n) to denote the empirical distribution and empirical mean built from the same observations, respectively. We also introduce N b (n) = a∈A N a,b (n). For observations associated to the pair a, b, we denote U a,b (n) a high probability upper bound on the mean µ a,b , and L a,b (n) a high probability lower bound. Unless specified, in the sequel we choose the following U a,b (n) coming from concentration inequality for R-sub-Gaussian variables (see (1)), and define L a,b (n) symmetrically :

U a,b (n) = µ a,b (n) + R 2 log(N b (n) 3 ) N a,b (n) L a,b (n) = µ a,b (n) -R 2 log(N b (n) 3 ) N a,b (n) .
One could instead use Hoeffding's inequality if the distributions have bounded support, empirical Bernstein's inequality to take the variance into account, self-normalized concentration inequality such as in Garivier & Moulines (2008); [START_REF] Abbasi-Yadkori Y | Improved algorithms for linear stochastic bandits[END_REF], or even tighter upper bounds based on Kullback-Leibler divergence as explained in [START_REF] Cappé | Kullback-leibler upper confidence bounds for optimal sequential allocation[END_REF]. These would lead to slightly improved constants in the regret bounds, at the price of clarity. Thus we focus here on bounds based on the mean only. Let the confidence set be S

a,b (n) = [L a,b (n), U a,b (n)] and its size (the gap) be G a,b (n) = U a,b (n) -L a,b (n).
To avoid some technical considerations, we assume that S a,b (n) is centered around µ a,b (n).

2 Known cluster distributions with single cluster arrivals.

In this section, we consider the case when all the distributions {ν a,c } a∈A,c∈C are known and arrivals {b n } n 1 belong to the same unknown cluster c ∈ C. The difference from a standard multi-armed bandit problem is that the set of possible distributions is finite and known. We can have for instance three arms, two clusters and Bernoulli distributions of respective parameter 0.8, 0.2, 0.9 for one cluster, and Bernoulli distributions of parameter 0.8, 0.1, 0.5 for the second one. This modifies the achievable guarantees :

Theorem 1 (Agrawal et al. (1989))
Let c ∈ C be the true class (that is supp(Υ) ⊂ B c ), and A -= A \ {⋆ c } be the set of sub-optimal arms. Then, a lower performance bound is

lim inf N →∞ R N log(N ) min ωc∈P(A-) max c ′ ∈C(c) a∈A- ω c,a ∆ a,c a∈A- ω c,a KL(ν a,c ||ν a,c ′ ) ,
where

C(c) = c ′ ∈ C : ν ⋆c,c ′ = ν ⋆c,c and ⋆ c = ⋆ ′ c .
Theorem

R N max c ′ ∈C(c) a∈A-ω ⋆ c,a ∆ a,c a∈A-ω ⋆ a,c KL(ν a,c ||ν a,c ′ ) +o(1) log(N ) .
Although theoretically appealing, it may be in general expensive to compute the quantities {ω ⋆ c } c∈C , which makes the algorithm less practical. On the other hand, Salomon & Audibert (2011) introduced the GCL algorithm, seemingly without being aware of the work of [START_REF] Agrawal R | Asymptotically Efficient Adaptive Allocation Schemes for Controlled I.I.D. processes[END_REF] and got the following non-asymptotic result :

Theorem 3 (Salomon & Audibert (2011))
Assume that for all c, c ′ ∈ C, for all a ∈ A, then either ν a,c = ν a,c ′ or (either

⋆ c = a or ⋆ ′ c = a), or ∃a ′ = a : P ν a ′ ,c ( dν a ′ ,c dν a ′ ,c ′ (X) > 0) = 0. Then if c ∈ C with unique best arm is the true environment, then for all β > 0 it holds for some constants C, C ′ that ∀n∀a = ⋆ c P b∈Bc N a,b (n) C log(n) ∆ 2 a,c C ′ n -β .
GCL is fairly easy to implement, however the way this bound is stated makes it hard to understand, all the more so that the constants are not explicit. Also the dependency with ∆ 2 a,c seems sub-optimal. For completeness, we now introduce an efficient algorithm directly inspired from Agrawal's work. The price for the reduced complexity is that we lose the asymptotic optimality. We start with some intuition about our setting.

High level intuition

For clarity, we focus on means only (instead of distributions). Let C n-1 = c ∈ C, ∀a ∈ A : µ a,c ∈ S a,B (n -1) be the set of admissible classes at round n -1, where the confidence set S a,B (n -1) is built using observations for the pairs {(a, b)} b∈B . Note that by concentration of measure, with high probability the true class c is admissible and thus C n-1 is not empty. Let then c ∈ C n-1 be an admissible class. It makes sense to pull its optimal arm ⋆ c = argmax a∈A µ a,c (that is known). Now several situations may occur : a) For another class

c ′ ∈ C, if |µ ⋆c,c ′ -µ ⋆c,c | > G a,B (n -1), then c ′ cannot be admissible. Now if when c ′ is admissible then ⋆ c = ⋆ c ′ , it means that choosing to play ⋆ c for c ∈ C n-1 is safe (that is ⋆ c = ⋆ c happens with high probability). JFPDA 2014 b) If ∃c ′ ∈ C such that both |µ ⋆c,c ′ -µ ⋆c,c | G a,B (n -1)
and ⋆ c = ⋆ c ′ , there are many admissible classes that lead to different actions to play. The situation is tricky since playing arm ⋆ c does not separate c from c ′ (it may be that ν ⋆c,c = ν ⋆c,c ′ ), and may moreover be sub-optimal since we may have ⋆ c = ⋆ c .

Algorithm Agrawal et al. (1989) uses a fancy procedure to handle case b). Here, we note that if we choose the class c (and thus action ⋆ c) with maximal best mean, this ensures that µ ⋆c,cµ ⋆c,c µ ⋆c,cµ ⋆c,c and thus a controlled error. This observation leads to the Single-K-UCB algorithm, whose pseudo-code is provided in Algorithm 1. Straightforwardly, if C n-1 is empty, it reduces to playing round-robin, in case a), A ⋆ n-1 is a singleton, and in case b), we have a controlled error.

Algorithm 1 The Single-K-UCB algorithm. Require: The cluster distributions {ν a,c } a∈A,c∈C . 1: for n = 1...N do 2:

Receive b n ∼ Υ.

3:

Define the set of admissible classes

C n-1 = c ∈ C : ∀a ∈ A µ a,c ∈ S a,B (n -1) . 4:
Define the set of "elite" admissible arms

A ⋆ n-1 = {a ∈ A; ∃c ∈ C n-1 ⋆ c = a}. 5:
Choose the next arm (breaks ties with round-robin)

a n = argmax a=⋆c,c∈Cn-1 µ ⋆c,c . (2)
6: end for Regret bound Such an algorithm enjoys the following regret performance :

Theorem 4 (Regret bound for single cluster arrivals)

The regret of Single-K-UCB satisfies

R Single-K-UCB N a∈A ⋆ 24R 2 ∆ a,c log(N ) ∆ + 2 a,c + ∆ a,c 1+ π 2 3 ,
where

A ⋆ = a ∈ A : ∃c ∈ C s.t. ⋆ c = a and ∆ + a,c = inf c ′ ∈C µ a,c ′ -µ a,c : ⋆ c ′ = a ∩ µ ⋆ c ′ ,c ′ µ ⋆c,c .
The notation ∆ + a,c comes from the fact that ∆ + a,c ∆ a,c . Note the link between this bound and that of Theorem 2 (also ∆ + a,c and C(c)). Of course the bound of Theorem 2 can be better and this seems to be the price for the simplicity of Single-K-UCB. On the other hand, since Theorem 4 scales with ∆ + a,c (which can be arbitrarily larger than ∆ a,c ; see Figure 1), it improves on the result of Theorem 3, and moreover provides explicit constants. Finally, it is straightforward to improve the constants using tighter confidence bounds as discussed in the introduction.

3 Known cluster distributions with multiple cluster arrivals.

We now turn to the more challenging case when the distributions {ν a,c } a∈A,c∈C are still known to the learner, but when the users may come from different clusters, and the learner does not know what class c corresponds to some input b ∈ B. In this setting, the lower bound from Theorem 1 can be strengthen. Indeed, without further assumptions, it may be the case that if the number of clusters C is too large with respect to the time horizon N , we don't have time to learn and we can not ensure to have sub-linear regret :

Theorem 5 (Regret lower-bound for multiple cluster arrivals) Let Υ be the uniform distribution over B and consider that the distributions are partitioned exactly into C > A groups of equal size. Then, it holds

inf algo sup νa,c R N 1 20 min{ √ N AC, N } .
This shows that for the scaling C = Ω(N ) the problem becomes hopeless, since for any bandit algorithm there exists a set of distributions {ν a,b } a∈A,b∈B such that the regret is linear in N .

Despite this difficulty, it is possible to slightly modify Single-K-UCB for that setting, which leads to algorithm 2 that enjoys the following regret performance. Define the set of "elite" admissible arms

A ⋆ n-1 = {a ∈ A; ∃c ∈ C n-1 (b n ) ⋆ c = a}. 5:
Choose the most optimistic "elite" arm

a n = argmax a=⋆c, c∈Cn-1(bn)
µ ⋆c,c .

6: end for Theorem 6 (Regret for multiple cluster arrivals)

The regret of Multiple-K-UCB satisfies

R Multiple-K-UCB N b∈B a∈A ⋆ min 24R 2 ∆ a,c b log(N Υ(b)) ∆ + 2 a,c b + O Υ(b) -1 , ∆ a,c b N Υ(b) ,
where c b ∈ C denotes the class corresponding to b ∈ B.

In order to see the benefit of knowing the distributions {ν a,c } a∈A,c∈C , a natural benchmark algorithm is the one that simply plays independent copies of UCB on each b ∈ B (see [START_REF] Auer | Using confidence bounds for exploitation-exploration trade-offs[END_REF]), without using the knowledge of the cluster distributions. We call this algorithm UCB on B ; see Algorithm 3. Importantly, due to the inequality ∆ + Receive b t ∼ Υ.

3:

Compute the empirical means µ a,b (n -1).

4:

Choose the next arm (breaks ties arbitrary)

a n = argmax a∈A U a,bn (n -1) . (3)
5: end for Illustration In order to highlight the role played by ∆ + a,c , Figure 1 depicts the upper-bounds from Theorem 6 and and from Theorem 7, for one randomly generated problem (we do not compare the regret, but the bounds, to emphasize the theoretical gap). For clarity, we reported the values of ∆ + a,c as well as of the optimality gaps ∆ a,c for each arm and each class. Here three arms that may be pulled by UCB on B are never pulled by Multiple-K-UCB. Note that the improvement can sometimes be huge : for instance when all ⋆ c are equal, then ∆ + a,c = ∞ for all sub-optimal arm and the bound from Theorem 6 equals zero.

4 The agnostic case.

In Sections 2 and 3, using the knowledge of the cluster distributions, we derived regret bounds that may significantly improve on their equivalent agnostic version. We now detail an improvement that is even more effective and applicable both in case cluster distributions are known or not. We first note that using estimates from each distributions ν a,b separately in order to decide the best action for the cluster c(b) = c seems sub-optimal since the number of samples N a,b (n) available for the couple (a, b) is typically small, while we could possibly gain much more by using all observations in each B c (This is basically what happens in Section 2). Indeed, if two distributions ν a,b and ν a,b ′ are the same, then grouping the corresponding observations provides a faster convergence speed. In general, grouping subsets of {ν a,b } b∈B may lead to a dramatic speed-up if we group similar distributions, and may create a bias if they significantly differ. Thus, there is a trade-off between getting fast versus accurate convergence, and it is a priori not clear whether we can get a provable improvement.

Benchmark We now introduce an oracle that knows the identity of the clusters perfectly. The simplest one is an algorithm that runs a version of UCB separately on each group B c (and not each b). We call this benchmark UCB on C. Note that although it knows the clusters this is not the best oracle : In some cases, it may be better to further group some clusters together. This algorithm is easy to analyze. To understand the kind of improvement we are targeting, the following theorem compares the regret of UCB on B, to that of the oracle UCB on C.

Theorem 7 (Baseline and Oracle regret for multiple cluster arrivals)

The expected regret at time N of the algorithm UCB on B is upper bounded by

R UCB on B N b∈B a∈A min 24R 2 log(N Υ(b)) ∆ a,b + O Υ(b) -1 , ∆ a,b N Υ(b) , where ∆ a,b = µ π ⋆ (b),b -µ a,b
is the optimality gap of arm a for environment b. Similarly, the expected regret at time N of UCB on C is upper bounded by

R UCB on C N C c=1 a∈A min 24R 2 log(N Υ(B c )) ∆ a,c + O Υ(B c ) -1 , ∆ a,c N Υ(B c ) ,
where ∆ a,c is the common value of the ∆ a,b for b ∈ B c .

As a result, the regret of UCB on C can be significantly smaller than the one of UCB on B. Indeed, only looking at the term in factor of log(N ), we get an improvement going from b∈B a∈A ∆ -1 a,b to C c=1 a∈A ∆ -1 a,c . This can be substantial, since typically C is much smaller than B. Note of course that the partition C is unknown in practice. Also, we emphasize that the lower bound of Theorem 5 also holds for that setting.

Grouping distributions

We now detail the improvement we are going to consider. Let B ⊂ B. We define, similarly to µ a,b (n), L a,b (n) and U a,b (n) the empirical group estimate ν a,B (n) with associated group mean µ a,B (n), confidence intervals U a,B (n), L a,B (n) and confidence set S a,B (n), where

ν a,B (n) = b ′ ∈B ν a,b ′ (n)N a,b ′ (n)I{b ′ ∈ B} b ′ ∈B N a,b ′ (n)I{b ′ ∈ B} , µ a,B (n) = b ′ ∈B µ a,b ′ N a,b ′ (n)I{b ′ ∈ B} b ′ ∈B N a,b ′ (n)I{b ′ ∈ B} .
Note that in the special case when B = B c , then µ a,Bc (n) = µ a,c . This may not hold in general for other sets B in case the {µ a,b ′ } b ′ ∈B are distinct from µ a,c . Thus, grouping the observations generally creates a bias. However, the speed of convergence of the group depends on N a,B (n

) = b ′ ∈B N a,b ′ (n)I{b ′ ∈ B}, which is typically much faster than that of a single point b (that depends on N a,b (n)). Thus the confidence interval S a,B (n) = [L a,B (n), U a,B (n)] is potentially much smaller than S a,b (n).
Finally, note that, by construction, we have µ a,B (n) ∈ S a,B (n) with high probability, but that for some b ∈ B there is no reason that µ a,b ∈ S a,B (n) due to the introduced bias.

In order to leverage the structural bias, we restrict possible groups B, using two observations. First, if

µ a,b = µ a,b ′ , then we must have S a,b (n) ∩ S a,b ′ (n) = ∅ with high probability. More generally, a set B such that µ a,b = µ a,b ′ for all b, b ′ ∈ B must satisfy that for all B ′ ⊂ B and all B ′′ ⊂ B, with high probability, S a,B ′′ (n) ∩ S a,B ′ (n) = ∅. Second, we define, for an adaptive ε = ε a,b,b ′ ,n , the enlarged confidence bounds U a,b (n; 1 + ε) = µ a,b (n) + (1 + ε) U a,b (n) -µ a,b (n) , L a,b (n; 1 + ε) = µ a,b (n) -(1 + ε) µ a,b (n) -L a,b (n) ,
a,b = µ a,b ′ and 2 G a,b ′ (n) ε 2 G a,b (n), we must have S a,b ′ (n) ⊂ S a,b (n; 1 + ε)
with high probability. Note that we here focus only on mean-based procedures for clarity, but it is of course possible to use empirical distributions ν a,b (n) to remove points sb ′ that have an obvious mismatch in Kullback-Leibler divergence. We do not discuss such improvements to avoid distracting the reader from the main message.

All in all, we define two sets of sets : First B b (n) for compatible sets, and then B + b (n) for maximally compatible (or "elite") sets, that have maximal group speed of convergence and a controlled bias :

B b (n) def = B ⊂ B: ∀a ∈ A∀b ′ ,b ′′ ∈B S a,b ′ (n)⊂S a,b ′′ (n; 1+ε) ∩ b ∈ B ∩ ∀B ′ , B ′′ ⊂ B, S a,B ′′ (n) ∩ S a,B ′ (n) = ∅ , B + b (n) def = Argmax B∈B b (n) B (for the relation ⊂ ) . (4)
(Note that Argmax returns a set, contrary to argmax.) These sets are simply groups of points that are compatible with the properties that we expect from confidence intervals. They are thus the natural candidates for an algorithm that tries to aggregate observations from several users together.

4.1 The Agnostic UCB for clustered-bandits.

We are now ready to introduce A-UCB, whose pseudo-code is provided as Algorithm 4. Proving strong regret bounds in this agnostic setting is difficult without further assumptions, since the true class may change at each single time step. For that reason, we proceed in two steps : Proposition 1 controls the number of pulls of sub-optimal arms under some events, that we then handle in specific cases in Lemma 1 and 2. Note that A-UCB uses a parameter γ that enables to control the enlargement coefficient ε and that we discuss below. -1, 0 .

5:

Compute the set B + bn (n -1) of maximally compatible aggregation sets via (4).

6:

Pull an elite arm that is the most optimistic

a n ∈ argmax a∈A max B∈B + bn (n-1) U a,B (n -1) (5)
7: end for Proposition 1 (Control of the number of pulls of sub-optimal arms) Let Ω n = B cn ∈ B bn (n -1) be the event that the true class c n is admissible at round n, and E α n = G ⋆c n ,Bc n (n -1) < α∆ an,cn the event that the confidence interval of the optimal arm of cluster B cn is small enough, for small α ∈ (0, 1). Then,3 for a suboptimal a n , under Ω n ∩ E α n and for all η ∈ (α, 1],

either N an,bn (n -1)

< 1+ ε 2 2 24R 2 log(N bn (n -1)) (η -α) 2 ∆ 2 an,cn , or N an,Bc n (n -1) < 24R 2 log(N Bc n (n -1)) (1 -η) 2 ∆ 2 an,cn
.

That is, the total number of pulls, for either the current user b n or its class c n , of a chosen sub-optimal arm is controlled. As a result, the regret is small under Ω n ∩ E α n . In particular for small ε, α and η → 1, Proposition 1 shows that under Ω n ∩ E α n the regret of A-UCB is essentially in between that of UCB on B and UCB on C : up to constants, it is never worse than UCB on B, which is the naive baseline, and can be significantly better by competing occasionally with the oracle UCB on C. This is highlighted precisely on Figure 5, where A-UCB behaves like UCB on B, in the beginning, and then progressively behaves like UCB on C. It now remains to show that Ω n ∩ E α n happens with high probability in order to deduce a non-trivial regret bound.

Illustration Ω n is the event that the true class c n is admissible at round n,. Now the event E α n essentially says that then G ⋆c,Bc (25000) < 0.27, and for 50 visits, the bound reduces to 0.145. Similarly, for B = 250 we get abound 0.12 with 15 visits of the optimal action, which is enough to ensure that E α n happens in non-trivial situations. Of course these numbers can be significantly reduced by using better confidence bounds (see [START_REF] Abbasi-Yadkori Y | Improved algorithms for linear stochastic bandits[END_REF]). Let us now provide conditions under which both E α n and Ω n happen. Adaptive enlargement Let us first deal with the event Ω n that B cn is admissible. To that end, we resort to an adaptive enlargement ε. Indeed a constant ε (such that ε = 1) does not always ensure that B cn is admissible with high probability, but only that a subset of B cn is admissible at round n. In order to better understand the set of points that are gathered in S a,b (n; 1 + ε) and that are admissible, let us introduce the following problem-dependent quantity, that only depends on the law of arrivals Υ : Definition 1 (Internal balance of arrivals in a cluster) The γ-balance of B with respect to the cluster c, for a point b ∈ B c is defined by

N ⋆c n ,Bc n (n -1) > O(log(n)), that is, since N ⋆c,Bc (n) = b∈Bc N ⋆c,b (n), it is enough that one N ⋆c n ,b (n) be
B c (b; γ) = b ′ ∈ B c : Υ(b) γΥ(b ′ ) .
Together with this quantity, it is natural to introduce the distortion factor of group B c , defined by

γ c = max b∈Bc Υ(b) min b∈Bc Υ(b) .
These quantities enable us to quantify the effective number of points that are grouped together with b ∈ B. This directly defines the speed-up the algorithm can achieve for this environment. Importantly, note that if γ γ c , then it holds that B c (b; γ) = B c for all b ∈ B c . A-UCB uses an adaptive ε that ensures that if γ is essentially greater than γ c , then B c (b; γ) and thus B c is admissible with high probability (but one should choose a small γ since the regret is increasing with γ) ; more precisely Lemma 1 (Probability that the true class is admissible) Figure 5 presents a variant when the set of users B is large. Note that in this experiment, one only gets to see each b about 50 times, this setting is thus challenging. It can be seen that A-UCB still works fairly decently in this case. In accordance with Proposition 1, let us also remark that here A-UCB behaves initially like UCB on B, and progressively behaves like UCB on C (though with a shifted regret due to the initial phase).

In A-UCB, if γ is chosen such that γ γ c + O n -1/2 , then it holds that P(Ω n ) 1 -O n -2 A b∈B Υ(b) -2 -2|B|n -2 .
Finally figure 6 presents a variant when the number of clusters C is large. A-UCB still competes with the oracle here.

In all these experiments, we observe that A-UCB consistently competes with UCB on C, while UCB and UCB on B sometimes obtain poor regret. This indicates that the proposed strategy is essentially able to capture the right information and does not under nor over-group the inputs b. This is promising.

Discussion

We introduced a novel setting for sequential decision making problem where there are some latent variables, such as in recommender systems, cognitive radio networks and others. We provided several contributions in a general framework in order to precisely address the issues raised by the latent structure. As a result, our contribution can be straightforwardly applied for instance to the linear-bandit setting (see [START_REF] Abbasi-Yadkori Y | Improved algorithms for linear stochastic bandits[END_REF][START_REF] Hayes | Stochastic Linear Optimization under Bandit Feedback[END_REF], where the number of actions is replaced with the dimension of a feature space, and confidence intervals with confidence ellipsoids, and potentially many others.

Let us remark that we assumed in this work that the reward distributions are clustered, that is each ν a,b is one of the {ν a,c } c . A natural extension is to consider the case when each ν a,b is a mixture of the {ν a,c } c , with an underlying low-rank structure. This is left for future research. In the non-trivial setting of Section 2, we showed that a simple procedure improves on Salomon & Audibert (2011) on the theoretical side and on [START_REF] Agrawal R | Asymptotically Efficient Adaptive Allocation Schemes for Controlled I.I.D. processes[END_REF] on the computational side. We then introduced the more challenging setting of Section 3, that has not been addressed previously, and extended our procedure to that setting. We provided a lower-bound explaining why the setting is challenging and then a non trivial regret bound that makes appear explicitly the role of the distribution Υ of arrivals.

We finally tackled the agnostic setting, when not even the number of clusters is known. We introduced an algorithm that demonstrates excellent performance on a number of difficult situations, and provided a result enabling to derive regret guarantees in some non-trivial situations. We leave the intricate question of extending Lemma 1 and 2 to the fully general case as an open problem.

  2 (Agrawal et al. (1989)) For each c ∈ C, let ω ⋆ c that achieves the minimum in the lower bound of Theorem 1. The algorithm proposed by Agrawal et al. (1989) makes use of {ω ⋆ c } c∈C and achieves

Algorithm 2

 2 The Multiple-K-UCB algorithm. Require: The cluster distributions {ν a,c } a∈A,c∈C . 1: for n = 1...N do 2: Receive b = b n ∼ Υ. 3: Define the set of admissible classes C n-1 (b) = c ∈ C, ∀a ∈ A : µ a,c ∈ S a,b (n -1) .4:

  a,c b ∆ a,c b and because only elite arms a ∈ A ⋆ are pulled, the regret of Multiple-K-UCB is never worse than that of UCB on B (Theorem 7) ; it can potentially be much smaller. Algorithm 3 The UCB on B algorithm 1: for n = 1...N do 2:

FIGURE 1 -

 1 FIGURE 1 -Theoretical regret bounds for Multiple-K-UCB (Theorem 6) and UCB on B (Theorem 7) for one problem characterized by |A| = 3, |B| = 50, |C| = 4 and 1 2 3 4 µa,c : 1 0.527 0.209 0.713 0.762 2 0.717 0.193 0.575 0.230 3 0.669 0.751 0.120 0.485 ∆ + a,c : 1 0.235 0.553 0.0 0.0 2 0.0 +∞ 0.142 +∞ 3 0.082 0.0 0.631 +∞ ∆a,c : 1 0.190 0.542 0.0 0.0 2 0.0 0.558 0.138 0.533 3 0.0475 0.0 0.593 0.277

  and then S a,b (n; 1+ε) = [L a,b (n; 1+ε), U a,b (n; 1+ε)]. This enables us to get the property that if µ

Algorithm 4

 4 The A-UCB algorithm Require: Parameter γ. 1: for n = 1...N do 2: Receive b n ∼ Υ, 3: Compute µ a,b (n -1), then U a,b (n -1), L a,b (n -1), S a,b (n -1) and G a,b (n -1). 4: Define the quantity ε = ε bn,b ′ ,n-1 by max 2γ log(N b ′ (n -1)) log(N bn (n -1))

  as large to ensure that E α n happens. For illustration, let us turn to the case of Bernoulli distributions (R = 1/2) with C = 4 equally probable classes of equal size B = 50. Individual upper bound confidence bounds U a,b (25000) are non trivial (i.e. less than 1) if (a, b) is seen at least 15 times. Now if each pair (⋆ c , b) for b ∈ B c is visited at least 15 times (out of the ≃ 125 available time steps for each b ∈ B c )

FIGURE 2 -FIGURE 3 -FIGURE 4 -

 234 FIGURE 2 -Regret of several algorithms in the following scenario with |A| = 3, |B| = 50, |C| = 4 and µ a,c 1 2 3 4 1 0.527 0.209 0.713 0.762 2 0.717 0.193 0.575 0.230 3 0.669 0.751 0.120 0.485

FIGURE 5 -

 5 FIGURE 5 -Regret of several algorithms in the following scenario with |A| = 3, |B| = 500, |C| = 4 and µ a,c 1 2 3 4 1 0.1 0.621 0.1 0.362 2 0.544 0.697 0.554 0.181 3 0.512 0.409 0.234 0.1

FIGURE 6 -

 6 FIGURE 6 -Regret of several algorithms in some randomly generated situation with |A| = 3, |B| = 100, |C| = 50.

We assume that radios are active at the same time everyday.

This is because we restrict to confidence interval centered around µ a,b (n) ; in general we would needG a,b ′ (n) ε min{U a,b (n)µ a,b (n), µ a,b (n) -L a,b (n)} .

In section C.2 of the extended version Maillard & Mannor (2013), we show a slightly stronger result, though more difficult to interpret.

Acknowledgements This work was supported by the European Community's Seventh Framework Programme (FP7/2007-2013) under grant agreement 306638 (SUPREL) and the Technion.

JFPDA 2014

Such a O(n -2 ) control is standard in regret proofs.

Ensuring the optimal arm is pulled enough We now turn to E α n . In full generality, there is no reason that A-UCB makes E α n happen. The following lemma however ensures that under a mild condition on the structure of the problem, this actually holds with high probability. A simple regret bound follows trivially.

Lemma 2 (Probability of small-enough confidence intervals under mismatch assumption) Let us assume that Υ is the uniform distribution, that all clusters have the same size B 0 , and that the cluster distributions satisfy ∀c,

(That is, a mismatch between two classes is either clear or harmless.) In such a case, if

Combining Proposition 1 together with Lemma 1 and Lemma 2, we deduce that, in some specific situations we are able to control with high probability the number of pulls of a sub-optimal arm, and as a result, the regret of the considered strategy. We currently do not know how to extend the analysis to handle the most general case. Note that the mismatch assumption in Lemma 2 is easy to check and holds in several situations (but we believe it is not necessary in order to get a controlled regret).

Numerical experiments

In this section, we study the behavior of the algorithm A-UCB on some experiments.

Algorithms We use the vanilla version of UCB (that aggregates all contexts), UCB on B that is the naive application of UCB separately on each context, and the oracle UCB on C. We implemented a simplified version of A-UCB where we do not compute the maximally compatible sets exactly (which is NP-hard in general), but average the means of the compatible sets instead. This slightly worsen the numerical constants in our results, even though characterizing entirely the effect of this relaxation in terms of regret and numerical efficiency goes beyond the scope of this paper.

Experiments We consider experiments with Bernoulli distributions : this is intuitively the hardest case, since one can only rely on the means to separate distributions ; it also appears in several applications. For each experiment, we show the number of actions |A|, of users |B|, of classes |C|, and the parameters {µ a,c } a∈A,c∈C when there are not too many. We plot the regret of all algorithms on the same figure : A thick line is used for the mean regret and dashed lines for quantiles at levels 0.25, 0.5, 0.75, 0.95 and 0.99. In all experiments, the parameters {Υ(b)} b∈B are defined by Υ(b) = w b / b∈B w b , where the weights w b are drawn uniformly randomly in [0.1, 0.9]. Thus for each class, the distortion factor γ c is less than 9, and we set the parameter γ of A-UCB to the value γ = 9. For one experiment with given fixed parameters, the algorithms are run over several trials (500) for a large time horizon N = 25000. We do not report the values of {Υ(b)} b∈B since this is generally uninformative.

Figure 2 presents an expected situation, where both the naive UCB and UCB on B perform poorly with respect to the oracle, whereas A-UCB performs very well. Note that here the best arm is different in the different classes, with corresponding value that is always very high and well separated from other arms.

Figure 3 presents a tricky situation : UCB on B performs poorly, while both A-UCB compete with the oracle, and all are defeated by UCB, which is not surprising since here one arm is the best in all contexts.

Figure 4 presents a variant when the set of actions A is large. As expected the performance of all algorithms degrade, but A-UCB is still competitive with respect to the oracle and benchmark algorithms.