Greg Bigwood

Aline Carneiro Viana

Mathias Boc

Marcelo Dias De Amorim

Aline Carneiro

Viana -Mathias Boc

Opportunistic data collection through delegation

Keywords: collaborative data collection, centrality, sparse networks, social interactions

We consider a collection system where collectors move around gathering information generated by data producers. In such a system, data may remain uncollected when the number of collectors is insufficient to cover the whole population of producers. Motivated by the observation that node encounters are sufficient to build a connected relationship graph, we propose to take advantage of the inherent interactions among nodes and transform some producers into delegates. With such an approach, collectors only need to meet delegates that, in turn, are responsible for gathering data from a subset of standard producers. We achieve this goal through two contributions. First, we investigate several delegation strategies based on the relative importance of nodes in their social interactions (i.e., the node centrality). Second, by considering a prediction strategy that estimates the likelihood of two nodes meeting each other, we investigate how the delegation strategies perform on predicted traces. We evaluate the delegation strategies both in terms of coverage and size of the delegation existing real mobility data sets. We observe that delegation strategies that rely on localized information perform as well as the ones that consider a complete view of the topology.

Opportunistic data collection through delegation

Résumé : Nous considérons un système de collecte où les collectionneurs se déplacent et collectent les informations générées par les producteurs de données. Dans un tel système, les données peuvent ne pas être collectées lorsque le nombre de collectionneurs est insuffisant pour couvrir l'ensemble de la population des producteurs. Motivé par le fait que les rencontres de nIJuds sont suffisants pour construire un graphe connecté, nous proposons de profiter des interactions inhérentes entre les nIJuds et transformer certains producteurs en délégués. Avec une telle approche, les collectionneurs ont seulement besoin de rencontrer les délégués que, à leur tour, sont responsables de la collecte de données d'un sous-ensemble des producteurs. Nous atteignons cet objectif grâce à deux contributions. Tout d'abord, nous étudions plusieurs stratégies de délégation basée sur l'importance relative des nIJuds dans leurs interactions sociales (par exemple, la centralité du nIJud). Deuxièmement, en considérant une stratégie de prédiction qui donne les estimations de la probabilité d'une rencontre de deux nIJuds, nous étudions les stratégies de délégation avec les traces prédit. Nous évaluons les stratégies de délégation à la fois en termes de couverture et de la taille du groupe de délégation en utilisant des traces de mobilité réelles. Nous n'observons que les stratégies de délégation qui se basent sur des informations localisées fournis aussi des bons résultats comparés aux résultats considérant une vue complète de la topologie.

Mots-clés : collecte collaborative de données, centralité, les réseaux de faible densité, les interactions sociales 1 Context and motivation Cellular phones have recently been considered as a pervasive mobile sensing platform due to their increasing proliferation and multiple advanced capabilities (e.g., cameras, GPS, sensors, wireless communication). As a result, global sensing has appeared as one of the most challenging pervasive applications aiming at improving the quality of life of the population [START_REF] Perez | G-sense: a scalable architecture for global sensing and monitoring[END_REF]. In such applications, also referred to as participatory sensing, mobile nodes (or producers) generate data from observations of the surrounding environment or from users (healthy, activity, behavior,etc) and send it to a central entity that evaluates the global behavior of the system from localized views. In addition, the underlying wireless network may face problems of intermittent and/or sparse connectivity, high degree of mobility, and unreliable links, which greatly impairs the effectiveness of both data collection and delivery.

There are many possibilities of how sensed data can be sent to the central entity. When possible, the most straightforward one is to rely on a reliable deployed infrastructure that maintains permanent connectivity with each one of the nodes, e.g., the 3G network. Nevertheless, there are many situations where the use of such infrastructure is prohibitive, either because of cost constraints or capacity limitations. Indeed, depending on the target scenario, information generated by each node might be huge, requiring a significant amount of communication resources to transfer sensed data to the infrastructure (e.g, multimedia contents).

We propose to design a collection system composed of specialized devices called collectors whose role is to move around and collect data when they enter within communication range with producers. As part of a general-interest system, collectors can be provided by administrative entities in order to alleviate end-users from using a costly deployed infrastructure (e.g. 3G access). Our idea is to use direct communications among nodes whenever available and use that infrastructure as little as possible. There are two main issues that arise when designing such a system: (i) the number of producers might be much larger than the number of collectors and (ii) we need to decide which collector to "visit" which producer, a challenging problem considering the previous issue. To address these challenges, we need alternative solutions to overcome the insufficiency of the collection system. We suggest to benefit from the inherent contact opportunities that emerge due to the natural mobility of the nodes to tackle these problems.

To the best of our knowledge, this is the first time that this specific problem is addressed. Indeed, although previous work makes use of mobile entities to perform some network task, the perspective therein is different from ours [START_REF] Glance | Pollen: using people as a communication medium[END_REF][START_REF] Jea | Multiple controlled mobile elements (data mules) for data collection in sensor networks[END_REF][START_REF] Zhao | A message ferrying approach for data delivery in sparse mobile ad hoc networks[END_REF]. In particular, data mules and message ferries are mobility-assisted strategies that aim at providing "connectivity opportunities" among nodes [START_REF] Jea | Multiple controlled mobile elements (data mules) for data collection in sensor networks[END_REF][START_REF] Zhao | A message ferrying approach for data delivery in sparse mobile ad hoc networks[END_REF]. These approaches are concerned with controlling the trajectories of ferries or mules to meet static or mobile nodes with the goal of minimizing message drops. Trajectories are adjusted based on requests from nodes, or the nodes adjust themselves their trajectories to meet the ferries. These approaches only partially solve the problem considered in this paper. Indeed, we do not deal with collectors placement or their trajectory design to visit all producers in the network. We instead focus on detecting which subset of producers could help collectors in the data collection task, while keeping their "normal" behavior within the network.

More specifically, we propose to take advantage of the inherent mobility of producers and transform some of them into delegates of the collection system. Delegates are responsible to collect data from other producers and serve as intermediate relays between them and the collectors (see Fig. 1). This is motivated by the fact that social networks exhibit the small world phenomenon which comes from the observation that individuals are often linked by a short chain of acquaintances [START_REF] Milgram | The small world problem[END_REF] and that encounters are sufficient to build a connected relationship graph [START_REF] Hsu | On nodal encounter patterns in wireless lan traces[END_REF]. The problem here is to determine which producers should be promoted as delegates. To this end, we make the following contributions:

Collector Producer

• Because contacts are not deterministic, we propose a prediction strategy to estimate the likelihood of two producers meeting each other (Section 3).

• Based on such a prediction system, we investigate different social-inspired strategies to select which producers should become delegates (Section 4).

• We evaluate the strategies using trace-driven analysis obtained in real situations (Section 5).

In all of the social-based strategies, the selection of delegates is based on the quantification of the relative importance of a producer in the network. We investigate two types of centrality approaches, namely degree and betweenness, combined with different network knowledge, namely global and ego networks (see Section 4). The analysis are performed on two different data sets available in the literature (Dartmouth College wireless traces [START_REF] Kotz | CRAWDAD trace dartmouth/campus/syslog/01 04[END_REF] and San Francisco taxi traces [START_REF]San Francisco Exploratorium's Invisible Dynamics initiative[END_REF]). By using measured and predicted traces generated from these data sets (see Section 3), we investigate the properties of the social-based strategies in terms of coverage and size of the resulting delegation set. We make then recommendations for the use of specific social-based strategies and show that the use of predicted traces is effective for the selection of good delegates (see Section 5). Finally, we discuss related works and present our work outlook at the end of this paper (see Section 6 and Section 7). As briefly defined in the introduction, our goal is to select a subset of producers that will be promoted as delegates to help the collectors obtain the data generated by each producer. In fact, producers that are promoted as delegates do not have to change their trajectories to meet collectors or other producers. They continue producing their own data while gathering data from producers they meet. In the rest of this paper, the words node and producer will be used interchangeably.

Because of storage and communication capacity constraints, we wish to avoid relying on fully epidemic approaches. We adopt in this paper a two-level strategy where a node is either a delegate or a producer that meets a delegate. In this way, simple producers transfer their data to one or more delegates they meet and collectors have only to visit these latter. Note that no forwarding is required, since data is transmitted through direct contact opportunities. Furthermore, in order to save deployment costs, it is also desirable that the number of delegates be as small as possible, so that fewer collectors are necessary (i.e., less nodes to visit). In particular, let Π = {p 1 , p 2 , . . . , p P } be the set of producers in the network. Our problem consists then in computing the delegates subset ∆ of Π such that Π is the smallest subset of producers whose movement guarantees the biggest achievable number of visited other producers within a certain time slot. Finally, we allow the utilization of an already deployed infrastructure (e.g., 3G network) but only for control information, i.e., to help the operation of the system (see Section 3).

How do we do?

In order for the system to compute the set ∆ of delegates, we need to know in advance what will be the contact patterns among producers. We have two alternatives to solve this problem. Either we promote all producers as delegates, which would bring our system to the original problem (i.e., the collectors visit all producers), or we try to predict future encounters. We naturally adopt the latter alternative (Section 3). Once encounters are predicted, we apply social-inspired selection schemes consisting in the quantification of the relative importance of producers, to compute the set of delegates (see Section 4).

Globally speaking, the system works as follows (to be detailed in the following sections):

• In the very beginning, there is no way to do predictions in the network (i.e., no history available). Collectors must then visit all producers.

• As the network operates, nodes store their encounters during some time (we refer to this as measurement period). At the end of this period, nodes send their contact patterns to a centralized administrative entity using an already deployed network infrastructure (e.g., 3G).

• The centralized administrative entity uses the contact patterns to predict future encounters. Based on this prediction, the set of delegates is determined. The producers selected as delegates are informed through the 3G infrastructure that they will have to play this role during the next measurement period. The collectors are also informed about the set of delegates to be visited.

• Since delegates are computed based on predictions, it is likely that some producers will be not covered by any delegate. In this case, these "isolated" producers are the only nodes to use the deployed infrastructure to upload their data. In this way, we limit the use of the 3G networks for data collection, reducing cost constraints and avoiding the capacity limitation problem.

What do we not do?

Our focus here is on the study of social interaction of producers for delegates selection.

Trajectory design of collectors in terms of time and space for guaranteeing delegates visits is not considered in this paper, although we leave this for future work. As discussed in Section 3, we use simple prediction algorithms, allowing quick computation and short measurement periods. In this paper, such algorithms are sufficient for the validation of the proposed strategies. More sophisticated algorithms could be used, which would allow decreasing the number of not covered producers due to wrong predictions. This is also left for future work.

Sketch of the solution

In this section, we present a high-level view of our approach. By applying different social-inspired strategies, we investigate the relative importance of producers in their social interactions or in the global network and select a set of potential good relay nodes (i.e., delegates) to help collectors perform their task. In this scheme, data is first collected from producers by delegates and then sent by these latter to the collectors. There are many ways to predict future contacts based on the history of encounters [START_REF] Franã Ąois | Delivery guarantees in predictable disruption tolerant networks[END_REF][START_REF] Liu | Routing in a cyclic mobispace[END_REF]. In this paper, we propose to use a slotted prediction strategy with a history window of two days (see explanation below). We will see in Section 5 that, although simple, this strategy leads to good results.

Let C(i) be the collection period i of duration |C|. We divide this period into J slots of fixed duration so that C(i) = {c(i, 1), c(i, 2), . . . , c(i, J)}. To each c(i, j) we associate two matrixes

M (i, j) = [N × N ] and P (i, j) = [N × N ],
where N is the total number of producers.

The first matrix M (i, j) is called the measurement matrix. In this matrix, element m x,y (i, j) is 1 if node x meets node y at least once during the time slot c(i, j), and 0 otherwise. As stated before, the problem is that we cannot compute the delegates based on the measurement matrix for a given time slot because this matrix is only available at the end of the slot period (after the real contacts are observed).

The second matrix P (i, j) is the prediction matrix. Each element of this matrix is based on the history of observations previously made. We propose to rely on the observations made during the same slot of the previous collection periods. We predict that a contact will happen if it already happened during the same slot of the previous two measurement periods. This procedure is illustrated in Fig. 2. The reason for this value is that we empirically observed that this leads to better results. More formally, we have:

p x,y (i, j) = { 1, if [m x,y (i -1, j) ∧ m x,y (i -2, j)] = 1, 0, otherwise. (1)
INRIA Figure 2: Observed encounters are used to feed the prediction matrix.

Social-oriented delegation

In the previous section, we proposed a prediction approach to determine the encounters that are likely to happen during a given time slot. We have now to determine, based on these expected encounters, which producers should be promoted to delegates. In the following, we investigate several strategies to this end. We classify them based both on the social metric and on the awareness a producer has about the topology.

Social-inspired metrics

To investigate the relative importance of producers, we exploit the well known centrality concept from graph theory and network analysis. Centrality will allow us designing how important a producer is within a social sphere, in order to identify potential delegates. In a social network, an individual is considered as important if, for instance, she/he has a strong capability of meeting others or connecting disjoint tightly connected groups. In the literature, "importance" is described through three different metrics [START_REF] Freeman | A set of measures of contrality based on betweenness[END_REF][START_REF] Freeman | Centrality in social networks conceptual clarification[END_REF]: closeness, degree, or betweenness. We use the last two centrality metrics in our analysis and a combination between them, described hereafter.

Degree centrality (DC). This metric describes the number of direct connections that involve a given node. In this way, a node with high degree centrality can be seen as a popular node. This also means it can be used as a good conduit for information exchange, since it maintains contact with numerous other network nodes. Thus, by exploiting degree centrality we aim to see if node degree can be used to find a near to perfect level of coverage, without having to select large numbers of nodes. The degree centrality of a given producer p i is calculated by simply counting the number of contacts this producer has during a time slot with other producers in the network:

D(p i ) = |N pi |.
Betweenness centrality (BC). This metric measures the frequency a node lies on the paths linking other nodes. In this way, a node with a high betweenness centrality is on more paths than the average and, therefore, has the capacity to facilitate interaction between the nodes that it links. The betweenness of producers is thus computed by analyzing all the paths between all nodes in the network, and then scoring a producer based on the amount of times it appears on the paths of other nodes. Note, however, that, nodes with high betweenness do not frequently have a large number of connections, since they are usually the only route to a place and are frequently "bridging nodes". By harvesting these nodes, we attempt to see if they are enough to cover the rest of the network.

Betweenness and degree centrality (BDC). By combining popularity and betweenness, we hope to play off the strengths of both of these metrics, whilst overcoming their shortcomings. A metric utilizing both degree and betweenness centrality seeks to gain the benefit of connecting to a large number of nodes, whilst simultaneously reaping the benefit of selecting nodes that bridge groups of nodes within the network. This would then ensure capturing nodes that bridge distinct cliques of nodes as well as network locations that would expect to see the most traffic. Considering we are interested in determining a subset of size |∆| of good delegates, the resulting set BDC is half made up of top nodes in the betweenness centrality set BC, and half made up of high popular nodes in the degree centrality set DC.

Topology-awareness

We compute the three metrics presented above to each node by considering nodes have access to the following levels of network knowledge:

Complete and bounded network (C). Also referred to as socio-centric network, it requires the complete knowledge of the network topology. A large node population may thus make difficult the analysis of centrality metrics in this kind of network topology. Nevertheless, we use this socio-centric network to get the upper-bounded results to be compared to the ones obtained when using knowledge-limited network topologies.

Ego-centric networks (E). This network topology represents the network viewed from the perspective of a single node and can be locally computed without the complete knowledge of the entire network. An ego-centric network consists of a single actor (named ego), its 1-hop neighbor (named alters), and all the links among those alters. This means the ego node itself can work out its ego network, after exchanging its neighborhood list with each new encounter, which allows distributing computation. An Ego network requires less state than a 2-hop neighborhood topology such as the one required for the computation of dominating sets. It has been shown in the literature that degree and betweenness centrality, when computed in ego networks, allow quite good results when compared to the socio-centric networks [START_REF] Marsden | Egocentric and sociocentric measures of network centrality[END_REF].

We combine the previous described centrality metrics and types of networks and originate six strategies, which we investigate in the rest of this paper.

Benchmark strategy

For the sake of comparison, we also consider a benchmark solution that leads to the best possible result. More specifically, the ideal case would be the smallest set of delegates that guarantee 100% coverage (i.e., during the collection period, all producers could deliver their data to either a collector or a delegate). This corresponds to computing the minimum dominating set (MDS) on the encounter graph for each time slot. Because this problem is known to be NP-hard, we consider an alternative solution borrowed from the computation of multi-point relays as our benchmark [START_REF] Adjih | Computing connected dominated sets with multipoint relays[END_REF].

INRIA

A dominating set DS of a graph G = (V, E) is a subset V ′ ⊆ V such that every vertex not in V ′ (i.e. for all u ∈ V -V ′ ) is adjacent to at least one vertex of V ′ by some edge (i.e., there is a v ∈ V ′ for which (u, v) ∈ E). We have used the following greedy algorithm for computing dominating sets, which takes O(m 2 ) time for a maximum connectivity degree m [START_REF] Adjih | Computing connected dominated sets with multipoint relays[END_REF]: (i) begin with an empty set; (ii) select the nodes that are the only ones neighbor of some two-hop neighbors of i, and add them to the DS set; (iii) add in the DS the neighbor node of i that covers the largest number of two-hop neighbors of i that are not yet covered by the current DS. Repeat this step until all two-hop neighbors are covered.

The results obtained with the proposed delegation strategies are then compared to the benchmark. Note that, unlike [START_REF] Polat | Message ferries as generalized dominating sets in intermittently connected mobile networks[END_REF], connection among delegates is not required here, since collectors will later visit them. The reason for not adopting the benchmark as the delegation strategy is that, as we will see in Section 5, although leading to better coverage, it requires a large number of delegates to perform the work.

For the sake of clarity, we present in Table 1 the acronyms used in the remainder on this paper.

Evaluation

We evaluate the performance of the social-inspired delegation strategies described in Section 4 using measured and predicted traces out of two data sets. We first describe the data sets used and the evaluation methodology in Sections 5.1 and 5.2, respectively. Secondly, in Section 5.3, we investigate the performance of the benchmark approach when applied to the different traces. Thirdly, by considering nodes with different network topology awareness (cf., Section 4), we evaluate the performance obtained with each social metric (cf. Section 5.4). Finally, we provide some discussion on the results in Section 5.5.

Data sets and methodology

We decided to use two data sets that are well-known by the research community: Dartmouth College campus and San Francisco Taxi cabs. By nature, they show different mobility patterns, types of users, and environment conditions. We expect then to observe different social behaviors, resulting in different usage models. This diversity will allow us better understanding the characteristics of the analyzed strategies. Although well-known, we briefly describe them in the following. [START_REF] Kotz | CRAWDAD trace dartmouth/campus/syslog/01 04[END_REF]. This data set shows associations and disassociations of wireless devices with 566 wireless access points in the Dartmouth College campus. For the purposes of this work, this data set has to be translated into a contact graph. In the literature, authors generally assume that two nodes are in contact with each other if they are associated with the same access point at the same time [5]. We decided instead to use the geographic coordinates of the nodes and consider that two nodes are in contact if their distance is below 250 meters. To obtain their geographic positions, we adopt the filtering approach proposed by Kim et al. [START_REF] Kim | Extracting a mobility model from real user traces[END_REF]. We consider mobility information over one month and focus our analysis on the 1, 000 most active nodes (in terms of presence). Note that nodes are not active at the same time, leading to an average number of 577 active nodes and 6 contacts per node per time slot of one hour, as shown in Figs. 3(a) and 3(c). The corresponding predicted traces, generated following the prediction strategy described in Section 3, lead to an average number of 737 active nodes and 4 contacts per node, as shown in Figs. [START_REF]San Francisco Exploratorium's Invisible Dynamics initiative[END_REF]. This data set describes the movement of taxicabs in San Francisco. GPS devices installed in the cabs are polled every minute or so whether they are free, inactive, or on route. We consider movements of the entire population of taxicabs that were active during a period of 28 days, resulting in a total of 542 nodes. We have, per time slot, an average number of 506 active nodes and of 130 contacts per node, as shown in Figs. 4(a Prediction vs. measurement. Note that for both data sets, the predicted traces resulted in lower average numbers of contacts per node and higher average numbers of active nodes. The reasons are as follows. On the one hand, we predict that a contact will happen at a given time slot if the same contact happened in the equivalent slot in both the two previous days. This explains why the expected degree is lower. On the other hand, we assume the a node will be active in a given time slot if it was active in either of the two previous days. This results in a higher expectation.

Dartmouth College campus

Taxi cabs in San Francisco

Evaluation methodology

We are interested in selecting a limited set of producers ∆ as delegates to opportunistically collect data generated by producers. In order to evaluate the performance of each delegation strategy, we focus on both coverage and size of the resulting ∆ sets, on a per-slot basis. We evaluate the coverage property of the strategies by determining the percentage of producers not met by any of the delegates -we refer to this parameter as missed nodes. We also evaluate the size of the |∆| set as an indicator of the efficiency of the delegation system.

Benchmark analysis

We first evaluate the performance of the benchmark approach when applied to the measured traces and the corresponding predicted traces, of both Dartmouth and Taxi data sets. Table 2 summarizes the average amount of producers that become delegates (in both absolute and relative terms). As previously discussed, we observe that the sizes of the prediction sets are larger than the measured ones (cf., Section 5.1).

In order to evaluate the precision of results obtained with the predicted traces, we investigate (i) the delegates that appear in both measured and predicted traces and (ii) the amount of nodes not covered when we use the predicted delegates. Fig. 5(a) (resp. Fig. 5(b)) shows the overlap comparison for the Dartmouth data set (resp. Taxi data set). An average of 71.47% (resp. 86.57% in the Taxi data set) of delegates found using the measured traces are also present in the corresponding predicted sets. Additionally, Fig. 5(c) shows for the Dartmouth data set (resp. Fig. 5(d) for the Taxi data set) that an average of 5.7% (resp. 0.08%) of nodes are not covered by the predicted delegates. These results are encouraging and confirm that the prediction scheme leads to good performance.

Topology-awareness

We investigate now the performance of the social-inspired metrics for delegate selection according to the topology-awareness of nodes. For every strategy discussed hereafter, we provide: (i) tables summarizing the average percentage of set sizes, for both the measured and predicted traces, (ii) figures showing the overlap between the measured and predicted delegate sets, and (iii) figures showing the amount of uncovered producers if we use the predicted delegates.

Influence of complete network view (C)

We consider here that nodes have a complete view of the network at each time slot. Producers are first ordered based on their social influence. In order to select the best delegates, we use as reference the same size of the delegate set obtained for the measured data set in the benchmark approach, and pick the top-rated producers until the delegate sets' sizes are the same.

DC-C. Table 3 summarizes the average percentage of missed nodes and the set size resulting from the degree centrality selection applied to the complete network. Fig. 6(a) shows that an average of 71.42% (resp. 86.77% in Fig. 6(b)) of delegates overlapping between the traces, while Fig. 6(c) shows that an average of 9.22% (resp. 0.59% in Fig. 6(d)) of nodes are not be covered predicted delegates. BC-C. As with the previous strategy, Table 4 shows the results of the betweenness centrality selection applied to the complete network. Fig. 7(a) shows that an average of 86.76% (resp. 99.07% in the Taxi data set in Fig. 7(b)) of delegates' overlap. Fig. 7(c) shows that an average of 7.31% (resp. 0.13% in the Taxi data set) of nodes remain uncovered. BDC-C. Table 5 summarizes the results for the BDC-C strategy. As in the previous two cases, we show in Figs. 8(a) and 8(b) the overlaps between the measured and predicted traces for both data sets. We observe an average overlap of 74.86% for the Dartmouth data set and 90.64% for the Taxi data set. Figs. 8(c) and 8(d) show that the proportion of nodes not covered is 8.04% in the Dartmouth case and 0.23% in the Taxi case.

Influence of ego-centric network view (E)

Nodes are now considered to have an ego-centric view of the network. The goal is to verify if nodes can locally select good delegate sets. As in the previous section, the sizes |∆| of the measured sets in the benchmark case are used as reference sizes for the delegate sets. The difference here is that producers use the ego-centric view instead of INRIA the complete view of the network, which gives a different network view to each node. Thus, each node firstly ranks all the nodes it sees in its ego-centric network according to the considered social-inspired strategy. An ordered list containing the best nodes of each ego network is then generated and the best |∆| nodes are selected to compose the delegate sets. Since duplications can happen (i.e. a best node in the ego network of node p i can also be the best node in the ego network of node p j ), they are removed from the final selected delegate set. This may result in smaller sets compared to the ones provided by the benchmark approach.

DC-E. Table 6 summarizes the average percentage set sizes resulted from the degree centrality selection applied to an ego-centric network. Details are presented in Fig. 9(a), which shows that an average of 61.94% (resp. 71.68% in the Taxi data set in Fig. 9(b)) of delegates overlap between the traces. Fig. 9(c) shows that an average of 11.85% of nodes (resp. 1.88% in the Taxi data set in Fig. 9(d)) remain uncovered.

BC-E. We now evaluate the betweenness centrality selection applied to an ego-centric network. The results are summarized in Table 7. BDC-E. Table 8 summarizes the results for the BDC-C strategy. Fig. 11(a) shows that, on average, 69.24% (resp. 73.33% in the Taxi data set) of the delegates overlap between the traces. In terms of producers that remain uncovered, Fig. 11(c) details the results for the Dartmouth set, with an average of 10.67%, while Fig. 11(d

Discussion

To summarize our analysis, we present in Tables 9 and 10 the average percentage of producers selected as delegates, from the predicted sets and the average percentage of missed producers in the measured traces when those delegates are used. Although we know that degree and betweenness measures on both ego-centric and complete networks are equivalent [START_REF] Marsden | Egocentric and sociocentric measures of network centrality[END_REF], we still were surprised to see that, in both data sets and for equivalent coverage, ego-centric solutions require a much smaller number of delegates. Additionally, we observe that better coverage and set sizes are obtained for the Taxi data set. This is expected because of its much higher average contacts per nodes (cf. Fig. 4).

For the sake of clarity, we show in Fig. 12 the average percentage of delegates against the average percentage of uncovered producers, as described in Section 5.4. We can observed that the results obtained through prediction are equivalent to the ones obtained through measurements. This confirms our expectation that: (i) a window of two days is enough to obtain good prediction and (ii) our prediction strategy is a reliable basis for good delegate set selection.

We have also investigated times slots of 24 hours, which resulted, as expected, in smaller delegate sets (we do not show the results here due to the lack of space. It is worth noting however that the time slot impacts the speed and trajectory design of the collectors. As for the design of collectors' trajectories, this impact study is left for future work.

Related work

Reactive and proactive schemes have been proposed in the domain of data delivery in sparsely connected networks and mobility-assisted schemes. Reactive schemes rely on movement that is inherent of the devices themselves to help deliver messages. When disconnected, nodes passively wait for their own mobility to allow them to reconnect [START_REF] Burgess | MaxProp: routing for vehicle-based disruption-tolerant networks[END_REF][START_REF] Lindgren | Probabilistic routing in intermittently connected networks[END_REF][START_REF] Ramanathan | Prioritized epidemic routing for opportunistic networks[END_REF]. More closely related to our work, proactive approaches make nodes modifying their trajectories for communication purposes, making use of mobility to improve capacity and connectivity [START_REF] Beaufour | Smart-tag based data dissemination[END_REF][START_REF] Jea | Multiple controlled mobile elements (data mules) for data collection in sensor networks[END_REF][START_REF] Zhao | A message ferrying approach for data delivery in sparse mobile ad hoc networks[END_REF]. In particular, data mules [START_REF] Jea | Multiple controlled mobile elements (data mules) for data collection in sensor networks[END_REF] and message ferrying [START_REF] Zhao | A message ferrying approach for data delivery in sparse mobile ad hoc networks[END_REF] are mobile nodes that move around the deployment area and take responsibility for carrying data between nodes. Smart-Tag [START_REF] Beaufour | Smart-tag based data dissemination[END_REF] proposes to use mobile individuals to carry messages between disconnected devices and physical places, but no social interaction between nodes is considered.

Other works investigate human mobility in terms of pairwise contact and intercontact times [4][5][START_REF] Conan | Characterizing pairwise inter-contact patterns in delay tolerant networks[END_REF]. Recently, underlying mobility patterns have been explored for social-based routing [START_REF] Daly | Social network analysis for routing in disconnected delaytolerant manets[END_REF][START_REF] Hui | BUBBLE Rap: Social-based forwarding in delay tolerant networks[END_REF][START_REF] Polat | Message ferries as generalized dominating sets in intermittently connected mobile networks[END_REF]. In particular, Plat et al. propose to use connected dominating sets as message ferries and routing relays [START_REF] Polat | Message ferries as generalized dominating sets in intermittently connected mobile networks[END_REF]. Nevertheless, neither social behavior nor relative importance of mobile nodes are explored, since message ferries are selected based only on neighborhood analysis.

The originality of our work is that we investigate established social-inspired techniques and evaluate the relative importance of mobile nodes in the specific case of data collection. By taking advantage of inherent social cyclicity, we do not need to enforce mobility to help the collection system.

Summary and outlook

In this paper, we have addressed the design of system support for robust data collection in wireless networks that face problems as sparse connectivity, high degree of mobility, and unreliable links. We have focused on the case of a data collection system where the number of collectors is much larger than the number of producers. To solve this problem, we have proposed a two-tiered approach where a subset of the producers are promoted to the rank of delegates, which are responsible for helping collectors gather data from the network. By relying on the social behavior of nodes, we moved beyond the current state of-the-art that introduces particular entities such as data mules or message ferries. To decide which producers to promote, we have investigated several strategies based on the social interactions producers have among them. In building our system, we observe that much can be extracted from the inherent mobility of the nodes and that our prediction strategy is effective when used for delegate selection. Among the many results using existing real mobility traces, we were very surprised to note that local knowledge of the network is more than enough to achieve high collection ratios, with values that are close to those obtained with full knowledge of the topology. As part of ongoing work, we are applying the same analysis to other mobility traces and are working on trajectory design to decide the order in which delegates should be visited by collectors.

Figure 1 :

 1 Figure 1: (a) The collector has to visit all producers. (b) Delegates gather information on behalf of the collector.

INRIA 2

 2 Problem definition and sketch of the solution 2.1 What do we do?

Figure 3 :

 3 Figure 3: Dartmouth measured and predicted traces: (a)-(b) active nodes and (c)-(d) average number of contacts over 695 hours, using time slots of 1 hour.

  3(b) and 3(d).

Figure 4 :

 4 Figure 4: Taxi measured and predicted traces: (a)-(b) active nodes and (c)-(d) average number of contacts over 672 hours, using time slots of 1 hour.

  ) and 4(c). As in the Dartmouth trace, we consider that two taxis are in contact if their distance is below 250 meters. The predicted results are shown in Figs.4(b) and 4(d), with an average number of 515 active nodes and 52 contacts per node.

Figure 5 :

 5 Figure 5: Benchmark approach. (a)-(b) Percent of nodes per timeslot in the ∆ set obtained from the measured traces that are also found in the ∆ sets obtained from the predicted traces: (a) Dartmouth: 71.47%, (b) Taxi: 86.57%. (c)-(d) Amount of notcovered nodes by the ∆ sets gotten from the predicted traces: (c) Dartmouth: 5.7% (d) Taxi: 0.08%.

Figure 6 :

 6 Figure 6: DC-C strategy. (a)-(b) Percent of nodes per timeslot in the ∆ set obtained from the measured traces that are also found in the ∆ sets obtained from the predicted traces: (a) Dartmouth: 71.42% (b) Taxi: 86.77% . (c)-(d) Amount of not-covered nodes by the ∆ sets gotten from the predicted traces: (c) Dartmouth: 9.22% (d) Taxi: 0.59%.

Figure 7 :

 7 Figure 7: BC-C strategy. (a)-(b) Percent of nodes per timeslot in the ∆ set obtained from the measured traces that are also found in the ∆ sets obtained from the predicted traces: (a) Dartmouth: 86.76%, (b) Taxi: 99.07%. (c)-(d) Amount of not-covered nodes by the ∆ sets gotten from the predicted traces: (c) Dartmouth: 7.31% (d) Taxi: 0.13%.

Figure 8 :

 8 Figure 8: BDC-C strategy. (a)-(b) Percent of nodes per timeslot in the ∆ set obtained from the measured traces that are also found in the ∆ sets obtained from the predicted traces: (a) Dartmouth: 74.86%, (b) Taxi: 90.64%. (c)-(d) Amount of not-covered nodes by the ∆ sets gotten from the predicted traces: (c) Dartmouth: 8.04% (d) Taxi: 0.23%.

Fig. 10 (

 10 a) shows an delegate overlap of 69.78% on average (resp.77.63% in the Taxi data set in Fig.10(b)), while numbers of uncovered producers are presented in Figs.10(c) and 10(d). The average values are 15.7% for the Dartmouth trace and 1.91% for the Taxi data set.

) shows 1 .

 1 48% of producers left uncovered in the Taxi data set.

Figure 9 :

 9 Figure 9: DC-E strategy. (a)-(b) Percent of nodes per timeslot in the ∆ set obtained from the measured traces that are also found in the ∆ sets obtained from the predicted traces: 11.85% (d) Taxi: 1.88%.

Figure 10 :

 10 Figure 10: BC-E strategy. (a)-(b) Percent of nodes per timeslot in the ∆ set obtained from the measured traces that are also found in the ∆ sets obtained from the predicted traces: (a) Dartmouth: 69.78%, (b) Taxi: 77.63%. (c)-(d) Amount of not-covered nodes by the ∆ sets gotten from the predicted traces: (c) Dartmouth: 15.7% (d) Taxi: 1.91%.

Figure 11 :

 11 Figure 11: BDC-E strategy. (a)-(b) Percent of nodes per timeslot in the ∆ set obtained from the measured traces that are also found in the ∆ sets obtained from the predicted traces: (a) Dartmouth: 69.24%, (b) Taxi: 73.33%. (c)-(d) Amount of not-covered nodes by the ∆ sets gotten from the predicted traces: (c) Dartmouth: 10.67% (d) Taxi: 1.48%.

Figure 12 :

 12 Figure 12: Average percentage of delegates as a function of the average percentage of not-covered nodes. (a)-(b) Dartmouth data sets. (c)-(d) Taxi data sets.

Table 1 :

 1 Acronyms for the different strategies.

	Acronym	Strategy
	DC-C	Degree centrality with complete view
	DC-E	Degree centrality with egocentric view
	BC-C	Betweenness centrality with complete view
	BC-E	Betweenness centrality with egocentric view
	BDC-C	Betw. and degr. centrality with complete view
	BDC-E	Betw. and degr. centrality with egocentric view
	Benchmark Dominating set

Table 2 :

 2 Avg. results for the benchmark.

	Data set	Traces	|∆|	% delegates
	Dartmouth	measured 304.36 predicted 508.43	56.14 70.97
	Taxi	measured 326.06 predicted 419.33	64.22 81.38

Table 3 :

 3 Avg. results for DC-C.

	Data set	Traces	|∆|	% delegates
	Dartmouth	measured 304.36 predicted 508.43	55.08 70.87
	Taxi	measured 325.09 predicted 418.59	64.02 81.24

Table 4 :

 4 Avg. results for BC-C.

	Data set	Traces	|∆|	% delegates
	Dartmouth	measured 304.30 predicted 507.54	56.12 70.97
	Taxi	measured 326.06 predicted 419.33	64.22 81.38

Table 5 :

 5 Avg. results for BDC-C.

			Data set	Traces	|∆|	% delegates
			Dartmouth	measured 304.36 predicted 507.33	56.14 70.87
			Taxi	measured 326.06 predicted 419.33	64.22 81.38
	Overlap comparison (%)	20 40 60 80
		0	100 200 300 400 500 600 700
			Timeslot (1 hour)

Table 6 :

 6 Avg. results for DC-E.

	Data set	Traces	|∆|	% delegates
	Dartmouth	measured 159.62 predicted 255.22	32.6 38.9
	Taxi	measured predicted	33.15 84.93	6.57 16.48

Table 7 :

 7 Avg. results for BC-E.

	Data set	Traces	|∆|	% delegates
	Dartmouth	measured 110.06 predicted 190.88	21.78 28.34
	Taxi	measured predicted	31.67 80.58	6.27 15.64

Table 8 :

 8 Avg. results for BDC-E.

	Data set	Traces	|∆|	% delegates
	Dartmouth	measured 174.75 predicted 292.54	35.29 44.02
	Taxi	measured predicted	37.71 97.93	7.48 19.01

Table 9 :

 9 Summary of Dartmouth results.

	Strategy	% missed % delegates
	Benchmark	5.7	70.97
	DC-C	9.22	70.87
	BC-C	7.31	70.97
	BDC-C	8.04	70.87
	DC-E	11.85	38.9
	BC-E	15.7	28.34
	BDC-E	10.67	44.02

Table 10 :

 10 Summary of Taxi results.

	Strategy	% missed % delegates
	Benchmark	0.08	81.38
	DC-C	0.59	81.24
	BC-C	0.13	81.38
	BDC-C	0.23	81.38
	DC-E	1.88	16.48
	BC-E	1.91	15.64
	BDC-E	1.48	19.01

RR n°7361

Bigwood & Carneiro Viana & Boc & Dias de Amorim


Maillard Rémi Munos

Adaptive Bandits: Towards the best history-dependent strategy Odalric-Ambrym

We consider multi-armed bandit games with possibly adaptive opponents. We introduce models Θ of constraints based on equivalence classes on the common history (information shared by the player and the opponent) which define two learning scenarios:

(1) The opponent is constrained, i.e. he provides rewards that are stochastic functions of equivalence classes defined by some model θ * ∈ Θ. The regret is measured with respect to (w.r.t.) the best history-dependent strategy. (2) The opponent is arbitrary and we measure the regret w.r.t. the best strategy among all mappings from classes to actions (i.e. the best history-class-based strategy) for the best model in Θ. This allows to model opponents (case 1) or strategies (case 2) which handles finite memory, periodicity, standard stochastic bandits and other situations.

When Θ = {θ}, i.e. only one model is considered, we derive tractable algorithms achieving a tight regret (at time T) bounded by Õ( √ T AC), where C is the number of classes of θ. Now, when many models are available, all known algorithms achieving a nice regret O( √ T ) are unfortunately not tractable and scale poorly with the number of models |Θ|. Our contribution here is to provide tractable algorithms with regret bounded by T 2/3 C 1/3 log(|Θ|) 1/2 .

Introduction

Designing medical treatments for patients infected by the Human Immunodeficiency Virus (HIV) is challenging due to the ability of the HIV to mutate into new viral strains that become, with time, resistant to a specific drug [START_REF] Ernst | Clinical data based optimal sti strategies for hiv; a reinforcement learning approach[END_REF]. Thus we need to alternate between drugs. The standard formalism of stochastic bandits (see [START_REF] Robbins | Some aspects of the sequential design of experiments[END_REF]) used for designing medical treatment strategies models each possible drug as an arm (action) and the immediate efficiency of the drug as a reward. In this setting, the rewards are assumed to be i.i.d., thus the optimal strategy is constant in time. However in the case of adapting viruses, like the HIV, no constant strategy (i.e., a strategy that constantly uses the same drug) is good on the long term. We thus need to design new algorithms (together with new performance criteria) to handle a larger class of strategies that may depend on the whole treatment history (i.e., past actions and rewards).

More formally, we consider a sequential decision making problem with rewards provided by a possibly adaptive opponent. The general game is defined as follows: At each time-step t, the decision-maker (or player, or agent) selects an action a t ∈ A (where A is a set of A = |A| possible actions), and simultaneously the opponent (or adversary or environment) chooses a reward function r t : A → [0, 1]. The agent receives the reward r t (a t ). In this paper we consider the so-called bandit information setting where the agent only sees the rewards of the chosen action, and not the other rewards provided by the opponent. The goal of the agent is to maximize the cumulative sum of the rewards received, i.e. choose a sequence of actions (a t ) t≤T that maximizes T t=1 r t (a t ).

Motivating example In order to better understand our goal, consider the following very simple problem for which no standard bandit algorithm achieves good cumulative rewards.

The set of actions is A = {a, b}, and the opponent is defined by: r(a) = 1 and r(b) = 0 if the last action of the player is b, and r(a) = 0 and r(b) = 1 if the last action is a. Finally r(a) = r(b) = 1 for the first action.

In that game, playing a constant action a (or b) yields a cumulative reward of T /2 at time T . On the other hand, a player that would switch its actions at each round would obtain a total rewards of T , which is op-timal. Although this opponent is very simple, the loss of using any usual multi-armed bandit algorithm (such as UCB [START_REF] Auer | Finitetime analysis of the multiarmed bandit problem[END_REF] and EXP3 [START_REF] Auer | The nonstochastic multiarmed bandit problem[END_REF]) instead of this simple switching strategy will be linear in T .

Adaptive opponents In this paper, we consider the setting when the opponent is adaptive, in the sense that the reward functions can be arbitrary measurable functions of the past common history, where by common history we mean all the observed rewards (r s (a s )) s<t and actions (a s ) s<t played before current time t. We write h <t or simply h the common history up to time t, so we can write r t (a) = r(h <t , a). Due to the motivating example, we naturally want to compare to the best history-dependent strategy against the adaptive opponent, and introduce a more challenging notion of regret (see Section 2.1) than usual for that purpose. Since this may be not possible without assumptions on the opponent or the comparison strategies (see [START_REF] Ryabko | On the possibility of learning in reactive environments with arbitrary dependence[END_REF]), we consider some model of constraints, and thus we want to adapt to a class Θ of possible constraints. The question is: can we adapt to the (unknown) model of constraints of the opponent?

Adversarial Bandits in literature A first approach when considering adversarial bandits providing arbitrary rewards (when no constraint is put on the complexity of the adversary) is to assess the performance of the player in terms of the best strategy that is constant in time (best constant action), which defines the external regret [START_REF] Auer | The nonstochastic multiarmed bandit problem[END_REF][START_REF] Freund | A decisiontheoretic generalization of on-line learning and an application to boosting[END_REF]. However, since this approach does not consider limitations on the strategy of the opponent with respect to the history, it can only give partial answer to the question of adaptivity to the best possible history-dependent strategy against a given opponent.

In [START_REF] Auer | The nonstochastic multiarmed bandit problem[END_REF], the authors extend the class of comparison strategies to piecewise constant strategies with at most S switches. The corresponding Exp3S (aka ShiftBand) algorithm achieves a regret of order T SA log(T 3 A), provided that T is large enough. However, against the opponent described in the previous section, the best strategy would need to switch S = T /2 times, thus this algorithm still suffers a linear regret compared to the optimal strategy. The notion of internal regret (see [START_REF] Foster | Asymptotic calibration[END_REF]), which compares the loss of an online algorithm to the loss of a modified algorithm that consistently replaces one action by another, has been also considered in many works [START_REF] Hart | A simple adaptive procedure leading to correlated equilibrium[END_REF][START_REF] Stoltz | Incomplete information and internal regret in prediction of individual sequences[END_REF][START_REF] Cesa | Potentialbased algorithms in on-line prediction and game theory[END_REF][START_REF] Foster | Regret in the on-line decision problem[END_REF]. In [START_REF] Blum | From external to internal regret[END_REF], the authors propose a way to convert any external regret minimization algorithm into an algorithm minimizing an extended notion of internal regret, using the so-called modifications rules that are functions h, a → b, where h is the history, and a and b are actions. This enables to compare the ac-tions selected by the algorithm to an alternative sequence and thus to assess the performance of the algorithm to other slightly perturbed algorithm. Assuming that the opponent's strategy can be described with the modification rules, then we might also see the corresponding modified regret minimization algorithm as adaptive to the opponent, in some sense. However, the proposed algorithm uses exponentially many internal variables and will not provide tight performance bounds in terms of regret w.r.t. the best history-based strategy, that we consider in Section 2.1.

On a more theoretical aspect, the work by [START_REF] Ryabko | On the possibility of learning in reactive environments with arbitrary dependence[END_REF] addresses the learnability problem in reactive environments (adaptive opponents). The authors introduce the notion of value-stable and recoverable environments, and show that environments satisfying such mild conditions are learnable. This also means that it is not possible to obtain sublinear regret w.r.t. the best strategy against any arbitrary opponent: we need to consider limitations of the opponent. Note also that the main proof of the paper by [START_REF] Ryabko | On the possibility of learning in reactive environments with arbitrary dependence[END_REF] is constructive, but unfortunately the would-be corresponding player is not implementable.

Tractability Since bandit algorithms are the base stone for Reinforcement Learning (RL) algorithms, it is thus important if not crucial to consider numerically efficient algorithms. The question of adaptability is not trivial because of tractability: Although the works of [START_REF] Blum | From external to internal regret[END_REF] and [START_REF] Ryabko | On the possibility of learning in reactive environments with arbitrary dependence[END_REF] already provide adaptive algorithms, none of them would be tractable in our setting (even with only one θ). Moreover, for a pool of possible behaviors Θ of the opponent (see Section 3), we define the Θ-regret w.r.t. the best possible strategy for the best model θ ∈ Θ. We then show (in Section 3) that our problem can be seen as a special instance of sleeping bandits. The best regret bounds known with tractable algorithms would be of order Õ((T C Θ ) 4/5 ) (see [START_REF] Varun Kanade | Sleeping experts and bandits with stochastic action availability and adversarial rewards[END_REF]) whereas there exists a non-tractable algorithm achieving Õ( √ T C Θ ), where C Θ = θ∈Θ C θ and C θ is the complexity of model θ. If the regret of the second algorithm nicely scales with the time horizon T , both of them provide loose bounds for large |Θ|. So the question is: can we design tractable algorithms that can adapt to a large pool of models of constraints?

Our contribution

The main contribution of this paper is a new way of considering adversarial opponents. For some equivalence relation Φ on histories, we write [h] Φ for the equivalence class of the history h w.r.t. Φ. We introduce Φ-constrained opponents that are such that the reward functions only depend on the equivalence classes of history, i.e. r t (a) = r([h <t ], a). Similarly, one can consider classes of strategies of the form H/Φ → A, where H/Φ is the set of equivalence classes of histories. Interestingly, such equivalence re-lations were also introduced in [START_REF] Hutter | Feature reinforcement learning: Part I: Unstructured MDPs[END_REF], with the goal to build relevant equivalence relations for Reinforcement Learning. The author provides useful insights, but no performance analysis. Our model of constraints, although seemingly simple, has two main advantages:

(1) the notion of Φ-regret (see Section 2) captures the regret w.r.t. such strategies and is expressive enough to handle many kinds of situations (like finite memory, periodicity, etc) and thus enables to define opponents that can be anything from the worst possible (fully adversarial), to a simple stochastic multi-armed bandit.

(2) such a model leads to simple and efficient algorithms that are built directly from standard algorithms, and yet achieve significantly good performances.

The introductory Section 2 starts with a single model and provides algorithms with expected regret w.r.t. the optimal history-based strategy bounded by O( √ T AC log A), where C is a measure of the complexity (number of equivalence classes of H/Φ) of the opponent, and a lower bound Ω( √ T AC). This applies to the switching opponent described in the introduction. The complexity of those algorithms is C times the complexity of the standard algorithms they are built from (namely UCB and Exp3), as opposed to the complexity of order A C for algorithms that would be derived directly from [START_REF] Blum | From external to internal regret[END_REF] in our setting. Note also that for the special case of a Φ-constrained opponent with a known model Φ, one can consider a RL point of view instead, and apply algorithms such as [START_REF] Ortner | Online regret bounds for markov decision processes with deterministic transitions[END_REF].

Our main contribution in this paper is to consider the more challenging situation where we have a pool of possible models Θ. In this case, we provide tractable algorithms with Θ-regret of order (see Section 3). (T A) 2/3 (C θ * log(T )) 1/3 log(|Θ|) 1/2 when the opponent belongs to the pool (i.e. θ * ∈ Θ, in which case we compare the performance to that of the optimal historybased strategy), and T 2/3 (AC log(A)) 1/3 log(|Θ|) 1/2 where C = max θ C θ , when it does not (in which case we compare to the best H/Φ θ -history-class-based strategy for the best model θ ∈ Θ).

We finally report numerical experiments in Section 4 which compares standards algorithms for bandits (from stochastic to adversarial) (UCB, MOSS, EXP3, ShiftBand) to the algorithms proposed here.

Definitions and preliminary results

Model of constrained opponents

Let H be the set of all histories, i.e. sequences of action played and information received. Let Φ : H → Y be a given function mapping histories to an abstract space Y , and let H/Φ denote the class of equivalence of histories w.r.t. the relation h 1 ∼ h 2 if and only if Φ(h 1 ) = Φ(h 2 ). We write also [h] Φ (or [h] when there is no ambiguity) for the equivalence class of h.

Based on an equivalence-class Φ, one can define Φconstrained opponents, which are intuitively the opponents that are Φ-classwise stochastic:

Definition 1 A Φ-constrained opponent is a function f : H/Φ → ∆(A)
, where ∆(A) is the set of distribution over the set A, taking values in [0, 1] (i.e. we assume that all rewards belongs to the interval [0, 1]).

Examples: Definition 1 covers many situations:

• When Φ(h) = 1 for all h ∈ H, then H/Φ consists of only one class, and Definition 1 reduces to a stochastic multi-armed bandit. We define the expected history-class-based regret for the equivalence class defined by Φ, also called stochastic Φ-regret, as:

• When Φ m : H → A m is Φ m (h) = a 1 ...a m ,
R Φ T = E T t=1 max a∈A µ [h<t] (a) -µ [h<t] (a t )) , (1)
where (a t ) t≤T is the sequence of actions played, h <t is the history observed by the player up to time t, and max a µ [h<t] (a) is the best action, which respect to the expected rewards provided by the opponent, given the history-class [h <t ]. Now, for an arbitrary adversary and an equivalence class Φ, one can define a (non-stochastic) regret w.r.t. the best H/Φ-history-class-based strategy, also called adversarial Φ-regret,

RΦ T = sup g:H/Φ→A E T t=1 r t (g([h <t ])) -r t (a t ) , (2)
where g([h <t ]) is the action that a strategy g would play given the history-class [h <t ] activated at time t, where g belongs to the set of strategies that are constant per H/Φ-history-class, i.e. mappings H/Φ → A.

In both cases, the expectation is w.r.t. all sources of randomness: the possible internal randomization of the player, and the possible random rewards provided by the opponent.

Note that by definition the Φ-regret is always bigger than the external regret (i.e. w.r.t. the best constant action), and that in the case when Φ defines only one class, those two notions of regret reduce to their usual definitions in stochastic and adversarial bandits, respectively.

Upper bounds on the Φ-regret

In the case we play against a constrained opponent, we observe from the definition of the Φ-regret ( 1)

that if we introduce R T (c) = E T t=1 max a µ [h<t] (a) - µ c (a t ) I [h<t]=c for a class c ∈ H/Φ, then R Φ T = c∈H/Φ R T (c)
. This enables us to use usual stochastic bandit algorithms, such as UCB [START_REF] Auer | Finitetime analysis of the multiarmed bandit problem[END_REF], per history-class, and the resulting behavior will enable to minimize the stochastic Φ-regret.

Similarly, if we consider an arbitrary opponent, and an equivalence class Φ, by using usual adversarial bandit algorithms, such as Exp3 [START_REF] Auer | The nonstochastic multiarmed bandit problem[END_REF], per history-class, one can minimize the per-class regret

E T t=1 r t (g(c)) - r t (a t ) I [h<t]=c w.r.t.

any constant-per-class strategy g, thus minimizing the adversarial Φ-regret RΦ

T . The two corresponding algorithms, called respectively Φ-UCB and Φ-EXP3, are described in Figure 1 (α and η are parameters) and we report the regret upperbounds in the next result. Theorem 1 In the case of a Φ-constrained opponent, using the Φ-UCB algorithm with parameter α > 1/2, we have the distribution-dependent bound:

R Φ T ≤ c∈H/Φ;E(Ic(T ))>0 a∈A;∆c(a)>0 4α log(T ) ∆ c (a) + ∆ c (a)c α where I c (T ) = T t=1 I [h<t]=c , the per-class gaps ∆ c (a) def = sup b∈A µ c (b) -µ c (a), and the constant c α = 1 + 4 log(α+1/2) ( α+1/2 α-1/2 ) 2 .
We also have a distributionfree bound (i.e. which does not depend on the gaps):

R Φ T ≤ T AC 4α log(T ) + c α where C = |{c ∈ |H/Φ|; E(I c (T )) > 0}|
is the number of classes that may be activated. Now, in the case of an arbitrary opponent, using Φ-Exp3 algorithm, we have:

RΦ T ≤ 3 √ 2 T CA log(A).
The proof of these statements is reported in the supplementary material and directly derives from the analysis detailed in [START_REF] Bubeck | Bandits Games and Clustering Foundations[END_REF] and the previous remarks. Note that (2) Define μt,c(a) = μt,c(a) + α log(Ic(t)) Ic(t-1,a) .

For each round t = 1, 2, . . . , T (1)
(3) Compute ct = Φ(h<t).

(4) Play at ∈ argmax a∈A μt,c t (a)

Initialization: Define ∀a ∈ A ξ1(a) = 1 A For each round t = 1, 2, . . . , T (1)
Play at ∼ ξt, observe rt(at).

(

) Define lc t (a) = 1-r t (a t ) ξ t (a) Ia t =aIc=[h <t ] . 2
(3) Define w c t+1 (a) = exp(-η t s=1 lc s (a)).

(4) Compute ct+1 = Φ(h<t+1).

(

) Define ξt+1(a) = w c t+1 t+1 (a) a w c t+1 t+1 5
. one can use other bandit algorithms (such as UCB-V [START_REF] Audibert | Exploration-exploitation trade-off using variance estimates in multi-armed bandits[END_REF], MOSS [START_REF] Audibert | Minimax policies for adversarial and stochastic bandits[END_REF]) and derive straightforwardly the corresponding result for the Φ-regret.

Lower bounds on the Φ-regret

We now derive lower bounds on the Φ-regret to show that the previous upper bounds are tight.

Intuitively, on each class c, one may suffer a regret of order I c (T )A, where I c (T ) is the number of times class c is visited. Now, since the way classes are "visited" depends on the structure of the game and the strategy of both the player and the opponent, those classes cannot be controlled by the player only. Thus we show that there always exist an environment such that whatever the strategy of the player is, a particular opponent will lead to visit all history-classes uniformly in expectation.

We consider here, for a given class function Φ, players that may depend on Φ and opponents that may depend both on Φ and on the player. Then we consider the worst opponent for the best player over the worst classfunction Φ of given complexity (expressed in terms of number of classes C of H/Φ). The following result easily follows from [START_REF] Bubeck | Bandits Games and Clustering Foundations[END_REF].

Theorem 2 Let sup represents the supremum taken over all Φ-constrained opponents and inf the infimum over all players, then the stochastic Φ-regret is lower-bounded as:

sup Φ;|H/Φ|=C inf algo sup Φ-opp R Φ T ≥ 1 20 √ T AC.
Let sup represents the supremum taken over all possible opponents, then the adversarial Φ-regret is lowerbounded as:

sup Φ;|H/Φ|=C inf algo sup opp RΦ T ≥ 1 20 √ T AC.
3 Playing against an opponent using a pool of models

After this introductory section, we now turn to the main challenge of this paper. When playing against a given opponent, its model of constraints Φ may not be known. It is thus natural to consider several equivalence relations defined by a pool of class functions (models) Φ Θ = (Φ θ ) θ∈Θ , and that the opponent plays with some model induced by some Φ * . We consider two cases: either Φ * = Φ θ * ∈ Φ Θ , i.e. the opponent is a Φ θ * -constrained opponent with θ * ∈ Θ, or the opponent is arbitrary, and we will compare our performance to that of the best model in Θ.

We define accordingly two notions of regret: If we consider a Φ * -constrained opponent, where Φ * ∈ Φ Θ , then one can define the so-called stochastic Φ Θ -regret as:

R Θ T = E T t=1 max a∈A µ [h<t] * (a) -µ [h<t] (a t )) . (3)
where [h <t ] * is the history-class used by the opponent. Now, for an arbitrary opponent and a pool of equivalence classes Φ Θ , we define a regret w.r.t. the best H/Φ θ -history-class-based strategy for the best model θ ∈ Θ, also called adversarial Φ Θ -regret:

RΘ T = sup θ∈Θ sup g:H/Φ θ →A E T t=1 r t (g([h <t ] θ )) -r t (a t ) , (4)
where the class [h <t ] θ corresponds to the model θ.

Tractability This problem can be seen as a Sleeping bandits ( [START_REF] Kleinberg | Regret bounds for sleeping experts and bandits[END_REF][START_REF] Varun Kanade | Sleeping experts and bandits with stochastic action availability and adversarial rewards[END_REF]) with stochastic availability and adversarial rewards. Indeed, by considering each class c in each model θ, we get a total of C Θ = θ∈Θ C θ experts. Now at each time step, only one class per model is awake, and thus the best awake expert changes with time. Recasting this problem in a usual bandit setting where the best expert is constant over time requires considering the C Θ ! possible rankings (see [START_REF] Kleinberg | Regret bounds for sleeping experts and bandits[END_REF]), each ranking being now seen as an expert. Running Exp4 algorithm on top of this new experts would give a sleeping-bandit regret (and thus a Φ Θ -regret)

of order O( T A log(C Θ !)) = O( T AC Θ log(C Θ )).
Unfortunately this algorithm is intractable and the bound is very loose when the number of models is large. In [START_REF] Varun Kanade | Sleeping experts and bandits with stochastic action availability and adversarial rewards[END_REF], they proposed a (tractable) algorithm that would achieve in our setting a regret bounded by O((T C Θ ) 4/5 log(T )).

We now describe tractable algorithms with regret upper-bounded by O(T 2/3 log(|Θ|) 1/2 ) for both the stochastic and adversarial Φ Θ -regret, which improves upon previous bounds for our setting.

EXP4/UCB and EXP4/EXP3 algorithms: A natural approach is to consider each model θ ∈ Θ as one expert defined by a equivalence function Φ θ and then run the Exp4 meta-algorithm (see [START_REF] Auer | The nonstochastic multiarmed bandit problem[END_REF]) to select an action based on the recommendations of all experts. More precisely, at each time t, the meta algorithm plays a t according to a distribution q t (•) = θ p t (θ)ξ θ t (•) which is a mixture of distributions ξ θ t that each expert θ assigns to each action, weighted by a distribution p t (θ) over the set of experts Θ. Figure 2 describes the Exp4 algorithm (see [START_REF] Auer | The nonstochastic multiarmed bandit problem[END_REF] for more details) using a mixing parameter γ > 0.

Initialization: Define ∀θ ∈ Θ, p1(θ) = 1 |Θ| .
For each round t = 1, 2, . . . , T ,

(1) Define qt(a) = (1 -γ) θ∈Θ pt(θ)ξ θ t (a) + γ A .

(2) Draw at ∼ qt, and observe rt(at).

(3) Define lt(a) = 1-r t (a t ) q t (a) Ia t =a.

(4) Define gt(θ) = a ξ θ t (a) lt(a).

(5) Define wt+1(θ) = exp(-γ t s=1 gt(θ)/A).

(

) Define pt+1(θ) = w t+1 (θ) θ w t+1 (θ) . 6

Figure 2: The Exp4 meta algorithm

In [START_REF] Auer | The nonstochastic multiarmed bandit problem[END_REF] the authors relate the performance of the meta algorithm to that of any individual expert (see Theorem 7.1 in [START_REF] Auer | The nonstochastic multiarmed bandit problem[END_REF]). However, it is not obvious to build an algorithm for each individual expert Φ θ that will minimize its Φ θ -regret. Indeed, the actions played by the meta algorithm differ from the ones that would have been played by each specific expert θ. This means that for each expert, not only we have a limited (bandit) information w.r.t. the reward function, but also each expert does not see the reward of its recommended action. This results in individual expert algorithms with poorer regret bounds than in the single model case described in the previous section (for which one observes the reward of the chosen action).

We provide two algorithms based respectively on UCB and Exp3, that may be used by each individual expert θ:

• Φ θ -UCB is defined as before (see Figure 1), except that instead of step (4) we define ξ θ t as a Dirac distribution at the recommended action argmax a∈A μt,ct (a).

• Φ θ -Exp3 is defined as before (see Figure 1), except that in step (1), no action is drawn from ξ t (since the meta algorithm chooses a t ∼ q t ), and step (2) is replaced by: lc t (a) = 1-rt(at) qt(a) I at=a I c=[h<t] θ (i.e. we re-weight by using the probability q t (a) of the meta algorithm instead of the probability ξ θ t (a) of the individual expert θ). Note that, like in EXP4, we obtain a logarithmic dependence on |Θ| since playing an action that has been chosen from a mixture of the probability distributions (over actions) of all models yields a reward which provides information about all the models.

Regret bounds (proved in

Experiments

We illustrate our approach with three different adaptive opponents and compare the results of standard algorithms to the algorithms described here using two measures of performance: the Φ-regret, and the external regret.

We consider only two actions A = {a, b}, and fix the time horizon at T = 500. The three considered opponents have finite short-term memory of length m = 0, 1, 2 respectively, i.e. are Φ m -constrained opponents in the sense of Definition 1. More precisely, the reward distributions are Bernoulli, and the opponents are

• O 0 is a simple stochastic bandit (no memory). We choose µ(a) = 0.4 and µ(b) = 0.7

• O 1 provides a mean reward 0.8 when the action changes at each step, and 0.3 otherwise, • O 2 provides a mean reward 0.8 when the action changes every two steps and 0.3 otherwise. The last two algorithms do not know the model of constraint corresponding to the opponent they are facing and still, they clearly outperform other standard algorithms (with frankly negative external regret) for the two adapting opponents (second and third). This clear improvement appears also when the model considered by the algorithm is more complex than that of the opponent (e.g. Φ 2 -UCB facing opponent 1). On the other hand, the reverse is false (Φ 1 -UCB and Φ 1 -Exp facing opponent 2) since a algorithm using a piece of history of length 1 cannot play well against an opponent with memory 2.

Future works

We do not know whether in the case of a pool of models Φ Θ , there exist tractable algorithms with Φ Θregret better that T 2/3 with log dependency w.r.t. |Θ|.

Here we have used a meta Exp4 algorithm, but we could have used other meta algorithms using a mixture q t (a) = θ p t (θ)ξ θ t (a) (where the p t are internal weights of the meta algorithm). However, when computing the approximation term of the best model θ * by models θ ∈ Θ (see the supplementary material), it seems that the Φ Θ -regret cannot be strongly reduced without making further assumptions on the structure of the game, since in general the mixture distribution q t may not converge to the distribution ξ θ t proposed by the best model θ ∈ Θ. However the question remains open.

A Some Technical proofs.

In order to relate the cumulative reward of the Exp4 algorithm to the one of the best expert on top of which it is run, we state the following simple Lemma. Note that in our case, since the ξ θ t are not fixed in advance but are random variables, we can not apply the original result of [START_REF] Auer | The nonstochastic multiarmed bandit problem[END_REF] for fixed expert advises, but need to adapt it. The proof easily follows from the original proof of Theorem 7.1 in [START_REF] Auer | The nonstochastic multiarmed bandit problem[END_REF], and is reported in the supplementary material.

Lemma 1 For any γ ∈ (0, 1], for any family of experts which includes the uniform expert such that all expert advises are adapted to the filtration of the past, one has

max θ T t=1 E a1,...,at-1 (E a∼ξ θ t (r t (a))) -E a1,...,a T ( T t=1 r t (a t ))
≤ (e -1)γT + A log(|Θ|) γ .

A.1 The rebel bandit setting

We now introduce the setting of Rebel bandits that may have its own interest. It will be used to compute the model-based regret of the Exp4 algorithm.

In this setting, we consider that at time t the player θ proposes a distribution of probability ξ θ t over the arms, but he actually receives the reward corresponding to an action drawn from another distribution, q t , the distribution of probability proposed by the meta algorithm.

Following (4), we define the best model of the pool:

θ * = argmax θ∈Θ sup g:H/Φ→A E T t=1 r t (g([h <t ])) -r t (a t ) .
We then define for any class c ∈ H/Φ θ * , the action a * c def = argmax a µ c (a) that corresponds to the best history-class-based strategy. We now analyze the (Φconstrained) Exp3 and UCB algorithms in this setting and bound the corresponding rebel-regret: Definition 2 (Rebel regret) The Rebel-regret of the algorithm that proposes at time t the distribution ξ θ t but in the game where the action a t ∼ q t is played instead is:

R q T (θ) = T t=1 E a1,..,at-1 r t (a * [h<t] θ * ) -E a∼ξ θ t (r t (a)) .

A.2 Φ-Exp3 in the Rebel bandit setting

We now consider using Exp4 on top of Φ-contrained algorithms. We first use the experts Φ θ -Exp3 for θ ∈ Θ with a slight modification on the definition of the function lc t (a). Indeed since the action a t are drawn according to the meta algorithm and not Φ θ -Exp3, we redefine lc t (a) = 1-rt(a) qt(a) I at=a I [h<t] θ =c so as to get unbiased estimate of r t (a) for all a. We now provide a bound on the Rebel-regret of the Φ * -Exp3 algorithm.

Theorem 4

The Φ θ * -Exp3 algorithm in the Rebel bandit setting where q t (a) ≥ δ for all a, and choosing the parameter

η θ t θ c (i) = δ log(A) i satisfies R q T (θ * ) ≤ 2 T C log A δ .
Proof: The proof is in six steps and mainly follows the proof in Section 2.1 of [START_REF] Bubeck | Bandits Games and Clustering Foundations[END_REF] that provides a bound on the regret of Exp3 algorithm.

Since we only consider the model θ * , we will simply refer to it as θ and also write c t for [h <t ] θ * to avoid cumbersome notations.

Step 1. Rewrite the regret term to make appear the actions a t chosen by the meta algorithm at time t. By definition of lθ t,c θ (a) we have E at∼qt ( lθ t,ct (a)) = 1r t (a), thus we get:

R q T (θ * ) = T t=1 E a1,..,at-1 E at∼qt (E a∼ξ θ t ( lθ t,ct (a))) -lθ t,ct (a * ct ) .
Step 2. Decompose the term E a∼ξ θ t ( lθ t,ct (a)) in order to use the definition of ξ θ t . Indeed, for φ(x)

def = 1 η θ t log E a∼ξ θ t exp(x)
, following the technique described in Section 2.1 of [START_REF] Bubeck | Bandits Games and Clustering Foundations[END_REF], we have:

E a∼ξ θ t ( lθ t,ct (a)) = φ -η θ t ( lθ t,ct (a) -E b∼ξ θ t ( lθ t,ct (b))) -φ(-η θ t lθ t,ct (a))
Now using the fact that log x ≤ x -1 and exp(-x) -1 + x ≤ x 2 , ∀x ≥ 0, the first term on the right hand of ( 5) is bounded by:

η θ t 2 E a∼ξ θ t ( lθ t,ct (a) 2 ) Thus, considering that ξ θ t (a) = exp(-η θ t t-1 s=1 lθ s,c t (a))
a exp(-η θ t t-1 s=1 lθ s,c t (a) , we can introduce the quantity Ψ θ t (η, c) =

1 η log( 1 A a exp(-η t s=1
lθ s,c (a))) so that the second right term of ( 5) is Ψ θ t-1 (η θ t , c t ) -Ψ θ t (η θ t , c t ). Thus we deduce that:

R q T (θ * ) ≤ T t=1 E a1,..,at-1 E at∼qt ( η θ t 2 (1 -r t (a t )) 2 ξ θ t (a t ) q 2 t (a t ) ) +E at Ψ θ t-1 (η θ t , c t ) -Ψ θ t (η θ t , c t ) -E at lθ t,ct (a * ct ) ,
where we have replace lθ t,ct (a) by its definition.

Step 3. Now we consider the first term in the right hand side of previous equation, which is bounded by:

E at∼qt ((1 -r t (a t )) 2 ξ θ t (a t ) q 2 t (a t ) ) ≤ a ξ θ t (a) q t (a) ≤ 1 δ .
Step 4. Introduce the equivalence classes. We now consider the second term defined with Ψ functions. Let us introduce the notations

I θ c (t) = t θ c (I θ c (T )) s=1 lθ s,c (a))), which is less than log A η θ t θ c (I θ c (T )) + t θ c (I θ c (T )) s=1
∂ ∂η Ψ θ (η, c) = 1 η 2 KL(p η t,c , π),
where π is the uniform distribution over the arms, and ,c) is increasing, we combine the results of each step to deduce that:

p η t,c (a) = exp(-η t-1 s=1 lθ s,c t (a)) a exp(-η t-1 s=1 lθ s,c t (a) . Step 6. Now since η θ t θ c (i) ≤ η θ t θ c (i)+1 , and Ψ θ t θ c (i) (•
R q T (θ * ) ≤ E c I θ c (T ) i=1 η θ t θ c (i) 2δ + log A η θ t θ c (I θ c (T ))
.

Since we choose

η θ t θ c (i) = δ log(A) i
, we get:

R q T (θ * ) ≤ 2E c I θ c (T ) log A δ ≤ 2 T C log A δ .
We now combine Lemma 3 and Theorem 9 using Exp4 meta algorithm with δ = γ A to get the final bound:

Theorem 5 For any opponent, the adversarial Φ Θregret of Exp4/Exp3 is bounded as

RΘ T = O(T 2/3 (AC log(A)) 1/3 log(|Θ|) 1/2 ), where C = max θ∈Θ |H/Φ θ |

A.3 Φ-UCB in the Rebel-bandit setting

Similarly, a bound on the Rebel-regret of the Φ * -UCB algorithm can be derived assuming that we consider a Φ * -constrained opponent with Φ * = Φ θ * ∈ Φ Θ . The proof of the following statement is reported in the supplementary material.

Theorem 6

The Φ θ * -UCB algorithm in the Rebel bandit setting where q t (a) ≥ δ for all a, and provided α > 1/2, satisfies

R q T (θ * ) ≤ c∈H/Φ * a =a * c ∆ c (a) 2α log(T ) ∆ c (a) 2 δ + πδ∆ c (a) 2 32α log T +c α
We also have the distribution-free bound:

R q T (θ * ) ≤ √ T C * A 4α log(T ) δ + c α + πδ 32α log(T )
.

This enables us to deduce the first part of Theorem 3, following the same method as Theorem 10 but for the stochastic Φ Θ -regret of Exp4/UCB.

A Playing against an opponent using a known model

c α = 1 + 4 log(α+1/2) ( α+1/2 α-1/2 ) 2 .
We also have a distributionfree bound (i.e. which does not depend on the gaps):

R Φ T ≤ T AC 4α log(T ) + c α where C = |{c ∈ |H/Φ|; E(I c (T )) > 0}|
is the number of classes that may be activated during the run. Now, in the case of an arbitrary opponent, using Φ-Exp3 algorithm, we have:

RΦ T ≤ 3 √ 2 T CA log(A).
Proof: Φ-UCB: The distribution-dependent bound for Φ-UCB is a direct application of the result of [START_REF] Bubeck | Bandits Games and Clustering Foundations[END_REF] for the algorithm UCB about τ a (t) def = t s=1 I as=a where a t is played by UCB, that states that E(τ a (t)) ≤ 4α log(t) ∆ 2 c (a) + c α . Indeed, we use the fact that R Φ T = c∈H/Φ R T (c) and thus remark that when a class c is visited, then we play according to a UCB algorithm for this class.

Thus, for the distribution-free bound, we have:

R Φ T = c a ∆ c (a)E(τ a (I c (T ))) ≤ c a E(τ a (I c (T ))) 4α log(T ) + c α ≤ c E(I c (T )) √ A 4α log(T ) + c α ≤ T CA 4α log(T ) + c α ,
where we used that a τ a (s) = s for all s, and c I c (T ) = T , and the Cauchy-Schwartz inequality twice.

Φ-Exp3: The bound for Φ-Exp3 follows from the bound of the anytime version of the Exp3 algorithm.

Indeed we have RΦ

T ≤ c E( A 2 Ic(T ) i=1 η c i + log(A) η c Ic(T )
), from which we deduce the bound by setting

η c i = 2 log A Ai .
A.2 Lower bounds on the regret Theorem 8 Let sup represents the supremum taken over all Φ-constrained opponents and inf the infimum over all forecasters, then the stochastic Φ-regret is lower-bounded as:

sup Φ;|H/Φ|=C inf algo sup Φ-opp R Φ T ≥ 1 20 √ T AC.
Now, let sup represents the supremum taken over all possible opponents and inf the infimum over all forecasters, then the adversarial Φ-regret is lower-bounded as:

sup Φ;|H/Φ|=C inf algo sup opp RΦ T ≥ 1 20 √ T AC.
Proof: Let us fix the horizon T and the number of classes C. We consider the opponent defined using the specific class-function Φ such that each class c is periodically visited every C time steps, thus T /C times. Note that T = T C C and that this is intuitively the opponent that makes the algorithm switch between classes the most. Now we define more precisely the rewards output by the opponent. Let us consider the stochastic bandits such that for each class c, one arm a c is a Bernoulli B((1 + ǫ c )/2), and all others are B((1 -ǫ c )/2).

Then by application of Lemma 2.2 in [START_REF] Bubeck | Bandits Games and Clustering Foundations[END_REF], for ǫ c of order A s , we have in the Bandit information setting the following inequality:

sup ac s t=1 µ c (a c ) -µ c (a t ) ≥ sǫ c 1- 1 A - sǫ c 2A log( 1 + ǫ c 1 -ǫ c ) .
Thus with the notations I c (T ) =

≥ c I c (T )ǫ c 1 - 1 A -ǫ c log( 1 + ǫ c 1 -ǫ c ) I c (T ) 2A .
Since the a c are chosen by the opponent such that each class is visited exactly I c (T ) = T /C times, then we deduce that the Φ-pseudo-regret is lower-bounded as:

sup

(ac)c c T t=1 (µ c (a c ) -µ c (a t ))I c=[h<t] ≥ c T C ǫ c 1 - 1 A -ǫ c log( 1 + ǫ c 1 -ǫ c ) T 2AC .
Thus, after some tedious computations to optimize ǫ c , we finally get a lower bound of order:

1 20 c T C A = 1 20 √ T AC. Note that this is valid only if ǫ c ∼ A Ic(T )
is small (less than 1), i.e. if the number of classes C is smaller than a constant times T A (anda if this not the case, then the lower bound becomes obviously of order T ).

The second part of the Theorem can be proved using the same construction.

B Playing against an opponent using a pool of models

We first remind the result of [START_REF] Auer | The nonstochastic multiarmed bandit problem[END_REF] relating the cumulative reward of the Exp4 algorithm to the one of the best expert on top of which it is run. We have:

Lemma 2 For any γ ∈ (0, 1], for any family of experts which includes the uniform expert, one has

max θ T t=1 E a∼ξ θ t (r t (a)) -a1,...,a T ( T t=1 r t (a t ))
≤ (e -1)γT + A log(|Θ|) γ .

In our case, since the ξ θ t are not fixed in advance but are random variables, we can not apply this Lemma directly and need to adapt it. Based on the proof of [START_REF] Auer | The nonstochastic multiarmed bandit problem[END_REF], we can prove the following bound: ≤ (e -1)γT + A log(|Θ|) γ .

Proof: Indeed, by construction of the algorithm, the beginning of the original proof from [START_REF] Auer | The nonstochastic multiarmed bandit problem[END_REF] applies and gives

T t=1 r t (a t ) ≥ (1 -γ) T t=1 E a∼ξ θ t (r t (a)) - A log(|Θ|) γ -(e -2) γ A T t=1 a∈A rt (a),
where rt (a) = rt(at) qt(a) I at=a . Now, we use the fact that ξ θ t (a) is adapted to the filtration of the past (which we denote F t-1 ) and the property that E(r t (a)|F t-1 ) = E(r t (a)|F t-1 ) to deduce that

E(E a∼ξ θ t (r t (a))) = E( a∈A E(r t (a)ξ θ t (a)|F t-1 )) = E( a∈A E(r t (a)|F t-1 )ξ θ t (a)) = E( a∈A E(r t (a)|F t-1 )ξ θ t (a)) = E( a∈A E(r t (a)ξ θ t (a)|F t-1 )) = E(E a∼ξ θ t (r t (a)))
On the other hand, since by assumption the uniform expert belongs to the set of considered experts, we also have

1 A E( T t=1 a∈A rt (a)) = T t=1 E(E a∼U (A) (r t (a))) ≤ max θ T t=1 E(E a∼ξ θ t (r t (a))),
where U (A) denotes the uniform distribution over the set of actions A. This concludes the proof.

We now define the best model of the pool θ * to be

θ * = argmax θ∈Θ sup g:H/Φ→A E T t=1 r t (g([h <t ])) -r t (a t ) ,
We then define for any class c ∈ H/Φ θ * , the action

B.1 The rebel bandit setting

We now introduce the setting of Rebel bandits that is interesting by itself. It will be used in order to compute the model-based regret of the Exp4 algorithm. In this setting, we consider that at time t the player θ proposes a distribution of probability ξ θ t over the arms, but he/she actually receives the reward corresponding to an action drawn with another distribution, say q t . This will be the distribution of probability proposed by the meta algorithm. We now analyze the (Φ-constrained) Exp3 and UCB algorithms in this setting and bound the corresponding rebel-regret define by: Definition 3 (Rebel regret) The Rebel-regret of the algorithm that proposes at time t the distribution ξ θ t but in the game where the action a t ∼ q t is played instead is:

R q T (θ) = t=1 T E a1,..,at-1 r t (a * [h<t] θ * ) -E a∼ξ θ t (r t (a)) .

B.2 Φ-Exp3 in the Rebel bandit setting

We now consider using Exp4 on top of Φ-contrained algorithms. We first use the experts Φ θ -Exp3 for θ ∈ Θ with a slight modification on the definition of the function lc t (a). Indeed since the action a t are driven according to the meta algorithm and not Φ θ -Exp3, we redefine lc t (a) = 1-rt(a) qt(a) I at=a I [h<t] θ =c so as to get unbiased estimate of r t (a) for all a. We now provide a bound on the Rebel-regret of the Φ * -Exp3 algorithm.

Theorem 9

The Φ θ * -Exp3 algorithm in the Rebel bandit setting where q t (a) ≥ δ for all a, and choosing the parameter η

θ t θ c (i) = δ log(A) i satisfies R q T (θ * ) ≤ 2 T C log A δ .
The proof of this Theorem is reported in the main paper. We now combine Lemma 3 and Theorem 9 to get the final bound:

Theorem 10 For any opponent, the adversarial Φ Θregret of Exp4/Exp3 is bounded as

RΘ T = O(T 2/3 (AC log(A)) 1/3 log(|Θ|) 1/2 ),
where C = max θ∈Θ |H/Φ θ | is the maximum number of classes for models θ ∈ Θ.

Proof: Indeed we can apply Theorem 9 using Exp4 meta algorithm with δ = γ A . Thus we get:

RΘ T = T t=1 E a1,...,at-1 (r t (a * [h<t] θ * ) -E at∼qt r t (a t )) ≤ R q T (θ * ) + (e -1)γT + A log(|Θ|) γ ≤ 2 T AC log A γ + 2γT + A log(|Θ|) γ .
We thus choose γ = (AC log(A)) 1/3 log(|Θ|) 1/2 (4T ) 1/3

to conclude.

B.3 Φ-UCB in the Rebel-bandit setting

Similarly, a bound on the Rebel-regret of the Φ * -UCB algorithm can be derived assuming that we consider a Φ * -constrained opponent with Φ * = Φ θ * ∈ Φ Θ .

Theorem 11

The Φ θ * -UCB algorithm in the Rebel bandit setting where q t (a) ≥ δ for all a, and provided α > 1/2, satisfies

R q T (θ * ) ≤ c∈H/Φ * a =a * c ∆ c (a) 2α log(T ) ∆ c (a) 2 δ + πδ∆ c (a) 2 32α log T +c α
We also have the distribution-free bound:

R q T (θ * ) ≤ √ T C * A 4α log(T ) δ + c α + πδ 32α log(T )
.

Proof: We write b t the action proposed by the Φ-UCB algorithm at time t, and a t the action effectively played according to distribution q t . We introduce the notations:

I c (T ) = T t=1 I [h<t]=c , then t c (i) = min{t; I c (t) = i} and for all a ∈ A, I c (T, a) = T t=1 I [h<t]=c I at=a .
The proof mainly follows the lines of [START_REF] Bubeck | Bandits Games and Clustering Foundations[END_REF]. Note that by definition, we want to bound the following term:

R q T (θ * ) = c a ∆ c (a)E( I θ c (T ) i=1 I bt=a ) (5)
Step one. Decompose the event b t = a. Let us consider a time t for which [h <t ] = c. Then let us consider a sub-optimal arm a such that ∆ c (a) > 0. Thus it appears that b t = a if one of the following conditions holds:

(

1) μt,c (a c ) ≤ µ c (a c ) (2) μt,c (a) > µ c (a) (3) ∆ c (a) < 2 α log T I θ c (t-1,a)
Indeed, otherwise we would have

μc (a c ) > µ c (a c ) = µ c (a) + ∆ c (a) ≥ µ c (a) + 2 α log I c (t) I c (t -1, a) ≥ μc (a).
Thus we introduce the quantity u c (a) = 4α log T ∆c(a) 2 , and deduce that: Now we can bound the second term of ( 6) by a constant depending only on α, by an easy peeling argument (we refer to Section 2.2 of [START_REF] Bubeck | Bandits Games and Clustering Foundations[END_REF]): Step 3. Thus we focus on the first term E(i c (a)) of ( 6). Since we know that q t (a) ≥ δ for all a, t, we thus deduce that:

E I θ c (T ) i=1 I bt=a ≤ E I θ c (T ) i=1 I (
E(i c
Step 4. Finally, by combining ( 7), ( 8) with ( 6) and ( 5), we deduce the following distribution-dependent bound on the rebel regret: This enables us to deduce the following Theorem, that we prove using the same method as that of Theorem 10 but for the stochastic Φ Θ -regret of Exp4/UCB.

C Approximation error of the models

The following result sheds light on a specific term that appears to be an approximation term of the true model θ * by other models θ.

Theorem 13 For any (p t (θ)) t,θ ∈ [0, 1], thus for any meta algorithm run on top of Exp3 algorithm and defined with q t (a) = θ p t (θ)ξ θ t (a) and decreasing coefficient η θ t , the following holds true:

(r t θ c (i) (a * [h <t θ c (i) ] ) -r t θ c (i) (a θ c ))p t θ c (i) (θ) .

The term on the second line is actually a mixture of approximation errors of each model, and it seems it can not be reduced without further assumption on the quality of the models.

Proof: The proof is in four steps.

Step 1. Rewrite the regret to make appear the probabilities ξ θ t (a). We first introduce: Step 3. Introduce the equivalence classes. We now consider the term in the right hand side of the above equation defined with Ψ functions. Note that we do not change the bound on the term RT by considering the sum over the θ such that p t (θ) > 0.

R
Let us introduce the following notations I θ c (t) =

  Regret against the best history-class-based strategy: If we consider a Φ-constrained opponent, then one can define for each class c ∈ H/Φ, and action a ∈ A the expected reward µ c (a) = E[r(c, a)].

  Define μt,c(a) = 1 Ic(t-1,a) F c t-1 (a), where F c t (a) = t s=1 rs(a)I [h<s]=c Ia s =a and Ic(t, a) = t s=1 I [h<s]=c Ia s =a.

Figure 1 :

 1 Figure 1: Φ-UCB (top) and Φ-Exp3 (down) algorithms.

Theorem 3

 3 Appendix B.2,B.3) of the meta algorithm Exp4 combined respectively with individual algorithms UCB and Exp3 (called respectively Exp4/UCB and Exp4/Exp3) are given below. Assume that we consider a Φ *constrained opponent with Φ * ∈ Φ Θ , then the stochastic Φ Θ -regret of Exp4/UCB is bounded as: R Θ T = O (T A) 2/3 (C log(T )) 1/3 log(|Θ|) 1/2 , where C = |H/Φ * | is the number of classes of the model Φ * of the opponent. Now, for any opponent, the adversarial Φ Θ -regret of Exp4/Exp3 is bounded as RΘ T = O T 2/3 (AC log(A)) 1/3 log(|Θ|) 1/2 , where C = max θ∈Θ |H/Φ θ | is the maximum number of classes for models θ ∈ Θ.

Figure 3 :

 3 Figure 3: Regret w.r.t. the best history-dependent strategy (red) and best constant strategy (cyan) for 3 opponents. All experiments have been averaged over 50 trials. Each plot of Figure 3 corresponds to one opponent (O 0 is left, O 1 right, and O 2 is bottom). In each plot, we represent the external regret (cyan) and Φ-regret (red) obtained for several algorithms. From left to right, the first four algorithms are UCB, MOSS, Exp3 and ShiftBand. The next four correspond respectively to Φ 1 -UCB, Φ 2 -UCB, Φ 1 -Exp3, and Φ 2 -Exp3 algorithms (i.e. versions of UCB and Exp3 with memory of length 1 and 2). Note that Φ 0 -UCB (resp. Exp3) is just UCB (resp. Exp3). The last two algorithms correspond to the Exp4/UCB (resp. Exp4/Exp3), i.e. meta algorithm Exp4 run on top of Φ m -UCB (resp Φ m -Exp3) algorithms, for m = 0, 1, 2) as defined in Section 3.

  lθ s,c (a) for any given a = a θ * c (we remind that θ = θ * ), in particular, we can use the optimal action a * c when c = [h <t ] θ * . Step 5. Remark that Ψ θ t (•, c) is increasing for all θ, c. Indeed, we can show that

  is the maximum number of classes for models θ ∈ Θ.Proof: By Lemma 3 and Theorem 9, we get RΘ

A. 1 7

 17 Regret upper bounds against the best history-class-based strategy Theorem In the case of a Φ-constrained opponent, using the Φ-UCB algorithm with parameter α > 1/2, we have the distribution-dependent bound: R Φ T ≤ c∈H/Φ;E(Ic(T ))>0 a∈A;∆c(a)>0 4α log(T ) ∆ c (a) + ∆ c (a)c α where I c (T ) = T t=1 I [h<t]=c , the per-class gaps ∆ c (a) def = µ c (a * c ) -µ c (a), and the constant

T t=1 I

 t=1 c=[h<t] and t c (i) = min{t; I c (t) ≥ i}, we deduce that: sup (ac)c c T t=1 (µ c (a c ) -µ c (a t ))I c=[h<t] = c sup ac Ic(T ) i=1 (µ c (a c ) -µ c (a tc(i) ))

Lemma 3

 3 For any γ ∈ (0, 1], for any family of experts which includes the uniform expert such that all expert advices are adapted to the filtration of the past, one hasmax θ T t=1 E a1,...,at-1 (E a∼ξ θ t (r t (a))) -E a1,...,a T ( T t=1 r t (a t ))

  a µ c (a) that corresponds to the best history-class-based strategy. Thus we can also writea * t = a * [h<t] θ * .

Step 2 .

 2 1)or(2)orI θ c (t-1,a)<uc(a) . Now since I θ c (., a) is an increasing function of time (note though, that it does not increase by one each time b t is proposed...), we can define the stopping time τ c (a) = min{t; I θ c (t, a) ≥ u c (a)}, or equivalently the stopping instant i c (a) = min{i; I θ c (t θ c (i), a) ≥ u c (a)}. Thus we deduce that: E I θ c (T ) i=1 I bt=a ≤ E(i c (a)) + E I θ c (T ) i=ic(a)+1 I (1)or(2) (6)

  (a)) = ∞ l=0 P(i c (a) > l) ≤ l 0 + ∞ l=l0 P ∀j ≤ l I θ c (t θ c (j), a) < u c (a) ≤ l 0 + ∞ l=l0 P ∀j ≤ l j i=1 I a t θ c (i) =a -q t θ c (i) (a) < u c (a)-δj . Now by property of martingale difference sequences, we deduce by setting l 0 = uc(a) δ , that:E(i c (a)) ≤ l 0 + ∞ l=l0 exp(-2(l -l 0 ) 2 δ 2 l) ≤ l 0 + ∞ l=l0 exp(-(l -l 0 ) 2 2σ 2 ),where we introduced the quantity σ 2 = 1 4δ 2 l0 . Thus we deduce that:E(i c (a) ≤ u c (a)

4 log(α+1/ 2 )

 42 R q T (θ * ) ≤ c∈H/Φ * a =a * c ∆ c (a) 2α log(T ) ∆ c (a) 2 δ + πδ∆ c (a) 2 32α log T +c α ,wherec α = 1 + ( α+1/2 α-1/2 ) 2 .We deduce the distribution-free bound by the same argument as for Theorem 7, remarking that π 8 δ∆c(a) 2 4α log T ≤ π 32α log(T ) = c ′ α .

Theorem 12

 12 Assume that we consider a Φ *constrained opponent with Φ * ∈ Φ Θ , then the stochastic Φ Θ -regret of Exp4/UCB is bounded as: R Θ T = O (T A) 2/3 (C log(T )) 1/3 log(|Θ|) 1/2 , where C = |H/Φ * | is the number of classes of the model Φ * of the opponent.

  (a t )p t (θ) q t (a t )I at=a [h <t ] * ) -r t (a t )ξ θ t (a t )p t (θ) q t (a t ).Now we have : lθ t,c θ (a) = (1-r t (a)) pt(θ) qt(a) I at=a I c θ =[h<t] θ , thus taking the expectation over a t for each time t, we have: t (a) =

			T
			t=1	r t (a [h<t] * ) -r t (a t )
	= r t exp(-η θ θ T t=1 E at∼qt ( t t-1 s=1 lθ s,[h <t ] θ (a)) a exp(-η θ t t-1 s=1 lθ (a) , we can introduce the quan-s,[h <t ] θ tity Ψ θ t (η, c) = 1 η log( 1 A a exp(-η t lθ s,c (a))) so s=1 that the previous regret term writes:
	RT ≤	θ	T t=1	E at (	η θ t 2	(1 -r t (a t )) 2 p 2 t (θ)ξ θ t (a t ) q 2 t (a t )	)
			T
	+	θ	t=1	E at (Ψ θ t-1 (η θ t , [h <t ] θ ) -Ψ θ t (η θ

T = t , [h <t ] θ )) -E at ( lθ t,[h<t] θ (a [h<t] * )) .

Appearing in Proceedings of the 13 th International Conference on Artificial Intelligence and Statistics (AISTATS) 2011, Chia Laguna Resort, Sardinia, Italy. Volume 9 of JMLR: W&CP 9. Copyright 2011 by the authors.