Random-Walk Perturbations for Online Combinatorial Optimization Luc Devroye, Gábor Lugosi and Gergely Neu

Abstract-We study online combinatorial optimization problems where a learner is interested in minimizing its cumulative regret in the presence of switching costs. To solve such problems, we propose a version of the follow-the-perturbedleader algorithm in which the cumulative losses are perturbed by independent symmetric random walks. In the general setting, our forecaster is shown to enjoy near-optimal guarantees on both quantities of interest, making it the best known efficient algorithm for the studied problem. In the special case of prediction with expert advice, we show that the forecaster achieves an expected regret of the optimal order O( √ n log N ) where n is the time horizon and N is the number of experts, while guaranteeing that the predictions are switched at most O( √ n log N ) times, in expectation.

Index Terms-Online learning, Online combinatorial optimization, Follow the Perturbed Leader, Random walk

I. PRELIMINARIES

In this paper we study the problem of online prediction with expert advice (see [START_REF] Cesa-Bianchi | Prediction, Learning, and Games[END_REF]), and in particular, online linear optimization (see, e.g., [START_REF] Gentile | Linear hinge loss and average margin[END_REF], [START_REF] Kivinen | Relative loss bounds for multidimensional regression problems[END_REF], [START_REF] Grove | General convergence results for linear discriminant updates[END_REF], [START_REF] Takimoto | Paths kernels and multiplicative updates[END_REF], [START_REF] Kalai | Efficient algorithms for online decision problems[END_REF], [START_REF] Warmuth | Randomized online PCA algorithms with regret bounds that are logarithmic in the dimension[END_REF], [START_REF] Helmbold | Learning permutations with exponential weights[END_REF], [START_REF] Hazan | Learning rotations with little regret[END_REF], [START_REF] Koolen | Hedging structured concepts[END_REF], [START_REF] Cesa-Bianchi | Combinatorial bandits[END_REF], [START_REF] Audibert | Regret in online combinatorial optimization[END_REF]). The problem may be described as a repeated game between a forecaster and an adversary-the environment. At each time instant t = 1, . . . , n, the forecaster chooses one of the N available actions and suffers a loss corresponding to the chosen action i. Each action i is represented by a vector v i ∈ R d , while the losses assigned by the environment at time t are described by the loss vector t ∈ [0, 1] d . Thus, given the set of actions S = {v i : i = 1, 2, . . . , N } ⊆ R d at every time instant t, the forecaster chooses, in a possibly randomized way, a vector V t ∈ S and suffers loss V T t t . We consider the so-called oblivious adversary model in which the environment selects all losses before the prediction game starts and reveals the loss vector t at time t after the forecaster has made its prediction. The losses are deterministic but the forecaster may randomize: at time t, the forecaster chooses a probability distribution p t over the set of N actions and draws a random action V t according to the distribution p t . The prediction protocol is described in Figure 1.

The usual goal for the standard prediction problem is to devise an algorithm such that the cumulative loss L n = n t=1 V T t t is as small as possible, in expectation and/or L. Devroye is with the School of Computer Science, McGill University, Montreal, Canada H3A 2K6 (email: lucdevroye@gmail.com). G. Lugosi is with ICREA and the Department of Economics, Pompeu Fabra University, Ramon Trias Fargas 25-27, 08005 Barcelona, Spain (email: gabor.lugosi@gmail.com). G. Neu is with the SequeL team, INRIA Lille -Nord Europe, 40 avenue Halley, 59650 Villeneuve d'Ascq, France (email: gergely.neu@gmail.com).

A previous version of this paper was published in the Proceedings of the 26th Annual Conference on Learning Theory, 2013 as [START_REF] Devroye | Prediction by random-walk perturbation[END_REF].

Parameters: set of actions S ⊆ R d , number of rounds n;

The environment chooses the loss vector t ∈ [0, 1] d for all t = 1, . . . , n. For all t = 1, 2, . . . , n, repeat

1) The forecaster chooses a probability distribution p t over S.

2) The forecaster draws an action V t randomly according to p t .

3) The environment reveals t . 4) The forecaster suffers loss V T t t . with high probability (where probability is with respect to the forecaster's randomization). Since we do not make any assumption on how the environment generates the losses t , we cannot hope to minimize the above loss. Instead, a meaningful goal is to minimize the performance gap between our algorithm and the strategy that selects the best action chosen in hindsight. This performance gap is called the regret and is defined formally as

R n = max i∈{1,2,...,N } n t=1 (V t -v) T t = L n -L * n ,
where we have also introduced the notation L * n = min v∈S v T n t=1 t . To gain simplicity in the presentation, we restrict our attention to the case of online combinatorial optimization in which S ⊂ {0, 1} d , that is, each action is represented as a binary vector. This special case arguably contains most important applications such as the online shortest path problem. In this example, a fixed directed acyclic graph of d edges is given with two distinguished vertices u and w. The forecaster, at every time instant t, chooses a directed path from u to w. Such a path is represented by its binary incidence vector v ∈ {0, 1} d .

The components of the loss vector t ∈ [0, 1] d represent losses assigned to the d edges and v T t is the total loss assigned to the path v. Another (non-essential) simplifying assumption is that every action v ∈ S has the same number of 1's: v 1 = m for all v ∈ S. The value of m plays an important role in the bounds presented in the paper.

A fundamental special case of the framework above is prediction with expert advice. In this setting, we have m = 1, d = N , and the learner has access to the unit vectors S = {e i } N i=1 as the decision set. Minimizing the regret in this setting is a well-studied problem (see the book of Cesa-Bianchi and Lugosi [START_REF] Cesa-Bianchi | Prediction, Learning, and Games[END_REF]). It is known that no matter what algorithm the forecaster uses,

lim inf n,N →∞ sup ER n (n/2) ln N ≥ 1,
where the supremum is taken with respect to all possible loss assignments with losses in [0, 1]. On the other hand, several prediction algorithms are known whose expected regret is of optimal order O( √ n log N ) and many of them achieve a regret of this order with high probability. Perhaps the most popular one is the exponentially weighted average forecaster (a variant of weighted majority algorithm of Littlestone and Warmuth [START_REF] Littlestone | The weighted majority algorithm[END_REF], and aggregating strategies of Vovk [START_REF] Vovk | Aggregating strategies[END_REF], also known as Hedge by Freund and Schapire [START_REF] Freund | A decision-theoretic generalization of on-line learning and an application to boosting[END_REF]). The exponentially weighted average forecaster assigns probabilities to the actions that are inversely proportional to an exponential function of the loss accumulated by each action up to time t.

Another popular forecaster is the follow the perturbed leader (FPL) algorithm of Hannan [START_REF] Hannan | Approximation to Bayes risk in repeated play[END_REF]. Kalai and Vempala [START_REF] Kalai | Efficient algorithms for online decision problems[END_REF] showed that Hannan's forecaster, when appropriately modified, indeed achieves an expected regret of optimal order. At time t, the FPL forecaster adds a random perturbation vector Z t ∈ R d to the cumulative loss L t-1 = t-1 s=1 s of each action and chooses an action v that minimizes v T (L t-1 + Z t ). If the elements of the perturbation vector have joint density (η/2) N e -η z 1 for η ∼ log N/n, then the expected regret of the forecaster is of order O( √ n log N ) ( [START_REF] Kalai | Efficient algorithms for online decision problems[END_REF], see also [START_REF] Cesa-Bianchi | Prediction, Learning, and Games[END_REF], [START_REF] Hutter | Prediction with expert advice by following the perturbed leader for general weights[END_REF], [START_REF] Poland | FPL analysis for adaptive bandits[END_REF]). This is true whether Z 1 , . . . , Z n are independent or not. It they are independent, then one may show that the regret is concentrated around its expectation. Another interesting choice is when

Z 1 = • • • = Z n ,
that is, the same perturbation is used over time. Even though this forecaster has an expected regret of optimal order, it may fail with reasonably high probability since its regret is much less concentrated.

While the results presented above still hold in the general case where m > 1 when treating each v ∈ S as a separate action, one may gain important computational advantage by taking the structure of the action set into account. In particular, as [START_REF] Kalai | Efficient algorithms for online decision problems[END_REF] emphasize, FPL-type forecasters may often be computed efficiently. Interestingly, this efficiency does not come at the price of inferior regret guarantees: as Neu and Bartók [START_REF] Neu | An efficient algorithm for learning with semibandit feedback[END_REF] have recently shown, an appropriately tuned version of FPL achieves the same regret of O(m 3/2 √ d log d) as the straightforward extension of the exponentially weighted forecaster. The only known forecaster to achieve better performance than this is Component Hedge proposed by Koolen, Warmuth and Kivinen [START_REF] Koolen | Hedging structured concepts[END_REF], guaranteeing a minimax optimal regret of O(m n log(d/m)). However, this forecaster can only be implemented efficiently for some special decision sets, and can still take Ω(d 6 ) time to run in the worst case (see [START_REF] Suehiro | Online prediction under submodular constraints[END_REF]). In this paper, we propose an FPL-variant that retains the nearoptimal regret guarantees of O(m 3/2 √ d log d), while having nice additional properties discussed below.

Small regret is not the only desirable feature of an online forecasting algorithm. In many applications, one would like to define forecasters that do not change their prediction too often. For instance, consider a sequential routing problem on a computer network where predictions correspond to selecting a path in a graph for each packet to traverse. In this situation, switching between routes might result in out-of-order delivery of packets due to changing delays, and eventually lead to decoding errors. Further examples of such problems include the online buffering problem described by Geulen, Voecking and Winkler [START_REF] Geulen | Regret minimization for online buffering problems using the weighted majority algorithm[END_REF] and the online lossy source coding problem of György and Neu [START_REF] György | Near-optimal rates for limited-delay universal lossy source coding[END_REF]. A more abstract problem where the number of abrupt switches in the behavior is costly is the problem of online learning in Markovian decision processes, as described by Even-Dar, Kakade and Mansour [START_REF] Even-Dar | Online Markov decision processes[END_REF] and Neu, György, Szepesvári, and Antos [START_REF] Neu | Online Markov decision processes under bandit feedback[END_REF].

To be precise, define the number of action switches up to time n by

C n = |{1 < t ≤ n : V t-1 = V t }| .
In particular, we are interested in defining randomized forecasters that achieve a regret R n of near-optimal order while keeping the number of action switches C n as small as possible. However, the usual forecasters with small regret-such as the exponentially weighted average forecaster or the FPL forecaster with i.i.d. perturbations-may switch actions a large number of times, typically Θ(n). Therefore, the design of special forecasters with small regret and small number of action switches is called for.

The first known algorithm to address this issue is the Follow the Lazy Leader (FLL) algorithm proposed by Kalai and Vempala [START_REF] Kalai | Efficient algorithms for online decision problems[END_REF]. This algorithm is designed to behave identically to their FPL algorithm in expectation (with an O(m 3/2 √ n log d) bound on the regret, as shown by Neu and Bartók [START_REF] Neu | An efficient algorithm for learning with semibandit feedback[END_REF]), while guaranteeing that the expected number of action switches is O(d (n/m) log d). The "Shrinking Dartboard" algorithm proposed by Geulen, Voecking and Winkler [START_REF] Geulen | Regret minimization for online buffering problems using the weighted majority algorithm[END_REF] is based on a similar idea: this algorithm simulates the exponentially weighted forecaster in expectation, guaranteeing a regret of O(m 3/2 √ n log d), while improving the upper bound on the expected number of switches to O( √ mn log d). In this paper, we propose a family of methods based on FPL in which perturbations are defined by independent symmetric random walks. We show that these intuitively appealing forecasters have similar regret and switch-number guarantees as Shrinking Dartboard and FLL.

In particular, we first propose an FPL-variant in which perturbations are generated by independent Gaussian random walks for each coordinate of the perturbation vector. We show that this algorithm guarantees a regret of O(m 3/2 √ n log d), while keeping the number of switches bounded by O(m √ n log d). While this bound is inferior to that of the Shrinking Dartboard algorithm by a factor of √ m log d, that algorithm can only be efficiently implemented for some special decision sets S-see [START_REF] Koolen | Hedging structured concepts[END_REF] and [START_REF] Cesa-Bianchi | Combinatorial bandits[END_REF] for some examples. On the other hand, our algorithm can be efficiently implemented whenever there exists an efficient implementation of the static optimization problem of finding arg min v∈S v T for any ∈ R d . We compare our results to other results known in the literature in Table I.

Notice that our regret bound described above only guarantees that the number of switches is of O( √ n log N ) in the setting of prediction with expert advice. In the second half of Regret Switches Efficient Shrinking Dartboard [START_REF] Geulen | Regret minimization for online buffering problems using the weighted majority algorithm[END_REF] O(m [START_REF] Kalai | Efficient algorithms for online decision problems[END_REF] AND [START_REF] Geulen | Regret minimization for online buffering problems using the weighted majority algorithm[END_REF].

the paper, we show that this can be improved to O( √ n log N ) by using symmetric binary random walks as perturbations. An interesting property of the resulting algorithm is that the expected regret can be directly upper bounded in terms of the expected number of switches.

We also note that a similar variant of the FPL forecaster was recently derived by Rakhlin, Shamir and Sridharan [START_REF] Rakhlin | Relax and randomize : From value to algorithms[END_REF], who use perturbations of the form Z i,t = n s=t+1 X i,s , where X i,s are i.i.d. random variables with an arbitrary symmetric distribution. Rakhlin, Shamir and Sridharan exploit the fact that these perturbations can serve as a relaxation of the Rademacher complexity of the prediction game, and prove an O( √ n log N ) bound on the expected regret of the resulting algorithm. While this approach cannot be used for analyzing our FPL-variant, our analysis can be directly applied to provide both regret and switch-number guarantees for their method. Additionally, note that our algorithm does not need to use prior knowledge of the number of rounds.

An interesting open question left for future research is characterizing the minimax rate for the quantity R n + C n in terms of m. For all known algorithms (including ours), the upper bounds on this quantity depend on m as m 3/2 , as contributed by the bound on R n . However, this dependence is known to be suboptimal: the optimal linear dependence of the regret on m is achieved by the Component Hedge algorithm of [START_REF] Koolen | Hedging structured concepts[END_REF]. We conjecture that the correct minimax rate of R n + C n matches the minimax rate of R n , which is of Θ(m n log(d/m)). Such a bound could be achieved by a switch-constrained algorithm that implements Component Hedge on expectation in a similar way as the Shrinking Dartboard implements the exponentially weighted forecaster or FLL implements FPL. However, constructing such an implementation is far from trivial and is left here as an interesting open problem.

II. RANDOM-WALK PERTURBATIONS FOR ONLINE COMBINATORIAL OPTIMIZATION

To address the problem described in the previous section, we propose a variant of the Follow the Perturbed Leader (FPL) algorithm. The proposed forecaster perturbs the loss of each action at every time instant by a zero-mean Gaussian random variable with variance η 2 > 0 and chooses an action with minimal cumulative perturbed loss. More precisely, the algorithm draws independent random variables X i,t ∼ N (0, η 2 ) and the vector X t = (X 1,t , . . . , X d,t ) is added to the observed loss vector t-1 . At time t action v ∈ S is chosen that minimizes t s=1 v T ( t-1 + X t ) (where we define 0 as the all-zero vector 0). Equivalently, the forecaster may be thought of as an FPL algorithm in which the cumulative losses L t-1 are perturbed by the independent symmetric random walks Algorithm 1 Online combinatorial optimization by randomwalk perturbations. Initialization: set L 0 = 0 and Z 0 = 0. For all t = 1, 2, . . . , n, repeat 1) Draw X t with i.i.d. Gaussian components

X i,t ∼ N (0, η 2 ) 2) Let Z t = Z t-1 + X t .
3) Choose action

V t = arg min v∈S {v T (L t-1 + Z t )} ,
where ties are broken in favor of V t-1 . 4) Observe the loss vector t , suffer loss

V T t t . 5) Set L t = L t-1 + t . Z t = t s=1
X s . This is the way the algorithm is presented in Algorithm 1.

Conceptually, the difference between standard FPL and the proposed version is the way the perturbations are generated: while common versions of FPL use perturbations that are generated in an i.i.d. fashion, the perturbations of the algorithm proposed here are dependent. This will enable us to control the number of action switches during the learning process. Note that the standard deviation of these perturbations at time t is still of order √ t just like for the standard FPL forecaster with optimal parameter settings.

To obtain intuition why this approach will solve our problem, first consider a problem with action set S = {(1, 0) T , (0, 1) T } and an environment that generates equal losses, say i,t = 0 for all i and t. When using i.i.d. perturbations, FPL switches actions with probability 1/2 in each round, thus yielding C t = t/2 + O( √ t) with overwhelming probability. The same holds for the exponentially weighted average forecaster. On the other hand, when using the randomwalk perturbations described above, we only switch between the actions when the leading random walk is changed, that is, when the difference of the two random walks-which is also a symmetric random walk-hits zero. This distribution is well understood and the probability that this occurs more than x √ n times during the first n steps is roughly

2P{N > 2x} ≤ 2e -2x 2
where N is a standard normal random variable (see [START_REF] Feller | An Introduction to Probability Theory and its Applications[END_REF]Section III.4]). Thus, in this case we see that the number of switches is bounded by O n log(1/δ) , with probability at least 1 -δ. As we show below, assuming all-zero losses is the worst case for the number of switches.

Even though we only prove bounds for the expected regret and the expected number of switches, the above example gives some intuition about the upper tail probabilities. While the above idea can be extended to the case of non-zero loss sequences to obtain high-confidence switch-number guarantees, proving similar results for the general setting is a highly nontrivial problem. We note that by our Lemma 2 (stated later in Section III), the regret of our algorithm can be directly bounded in terms of the number of switches, thus we can guarantee upper bounds of O( √ n) on both C n and R n with high probability. We are not aware of any other algorithm that provides high-confidence guarantees on both quantities of interest even in this simple special case.

The next theorem bounds the performance of the proposed forecaster. We are not only interested in the regret but also the number of switches C n = n t=1 1 {Vt+1 =Vt} . The regret is of similar order as that of the standard FPL forecaster, up to an additive logarithmic factor. Moreover, the expected number of switches is O (m √ n log d). Remarkably, the dependence on d is only logarithmic and it is the weight m of the actions that plays an important role.

Theorem 1: The expected regret and the expected number of action switches satisfy (under the oblivious adversary model),

ER n ≤ m 2n log d 2m η + η + m 2 (log n + 1) η 2
and

EC n ≤ n t=1 m 1 + η √ 2 log d √ 2 log d η √ t + n t=1 m 1+2η √ 2 log d+η 2 2 log d+ √ 2 log d+1 4η 2 t .
In particular, setting η = √ 2m yields

ER n ≤ 4m 3/2 n log d + m(log n + 1) 2 .
and

EC n = O m √ n log d .
The proof of the regret bound follows the steps of the proof of Theorem 1 in [START_REF] Neu | An efficient algorithm for learning with semibandit feedback[END_REF], and is deferred to the appendix. The more interesting part is the bound for the expected number of action switches

EC n = n t=1 P [V t+1 = V t ].
For proving a bound on this quantity, we study the evolution of the lead pack A t defined as the set of actions with near-optimal loss given by

A t = w ∈ S : (w -V t ) T (L t-1 + Z t ) ≤ w -V t 1 • t + X t+1 ∞ . (1)
We sometimes refer to t + X t+1 ∞ as the diameter of the lead pack. Observe that no action outside A t can take the lead at time t + 1, since if w ∈ A t , then

(w -V t ) T (L t-1 + Z t ) > |(w -V t ) T ( t + X t+1 )| so w T (L t + Z t+1 ) > V T t (L t + Z t+1
) and w cannot be the new leader. It follows that we can upper bound the probability of switching as

P [V t+1 = V t ] ≤ P [|A t | > 1] ,
which leaves us with the problem of upper bounding

P [|A t | > 1].
The following lemma gives a bound of this quantity. Putting this statement together with the well-known

facts that E [ X 1 ∞ ] ≤ η √ 2 log d and E X 1 2 ∞ ≤ η 2 2 log d + √ 2 log d + 1
(see, e.g., [START_REF] Boucheron | Concentration inequalities:A Nonasymptotic Theory of Independence[END_REF]) proves the second statement of the theorem.

Lemma 1: For each t = 1, 2, . . . , n,

P [|A t | > 1 |X t+1 ] ≤ m t + X t+1 ∞ √ 2 log d η √ t + m t + X t+1 2 ∞ 2η 2 t .
Proof: We use the notation

P t [•] = P [• |X t+1 ] and E t [•] = E [• |X t+1 ]. Also, let h t = t + X t+1 and H t = t-1 s=0 h s .
Furthermore, we use the shorthand notation c = h t ∞ . We start by analyzing P t [|A t | = 1]:

P t [|A t | = 1] = = v∈S P t [∀w = v : (w -v) T H t > w -v 1 c] = v∈S y∈R f v (y)P t ∀w = v : w T H t > y + w -v 1 c v T H t = y dy, (2)
where f v is the density of v T H t . Next, we crucially use the fact that the conditional distributions of correlated Gaussian random variables are also Gaussian. In particular, let us fix an arbitrary v ∈ S and define k w = (m -wv 1 ) for all w ∈ S. Then, the covariance between the perturbed loss of w and v is given as

cov (w T H t , v T H t ) = η 2 (m -w -v 1 )t = η 2 k w t.
Organizing all actions w ∈ S \ v into a matrix W = (w 1 , w 2 , . . . , w N -1 ), the conditional distribution of W T H t is an (N -1)-variate Gaussian distribution with mean vector

µ v (y) = w T i L t-1 + y k wi m , . . . , w T N -1 L t-1 + y k w N -1 m T and covariance matrix Σ v , given that v T H t = y. Defining K = k w1 , . . . , k w N -1
T and using the notation

ϕ v (x) = 1 (2π) N -1 |Σ v | exp - x T Σ -1 v x 2 ,
we get that

P t [∀w = v : w T H t > y + w -v 1 c |v T H t = y ] = ∞ • • • zi=y+(m-kw i )c ϕ v (z -µ v (y)) dz = ∞ • • • zi=y+mc ϕ v (z -µ v (y) -cK) dz = ∞ • • • zi=y+mc ϕ v (z -µ v (y + mc)) dz = P t [ ∀w = v : w T H t > y + mc| v T H t = y + mc] ,
where we used µ v (y + mc) = µ v (y) + cK. Using this, we rewrite (2) as

P t [|A t | = 1] = v∈S y∈R f v (y)P t [ ∀w = v : w T H t > y| v T H t = y] dy - v∈S y∈R f v (y) -f v (y -mc) • • P t [ ∀w = v : w T H t > y| v T H t = y] dy
Observing that the first term above corresponds to the probability that the leader is unique and that this event holds almost surely under our perturbation scheme, we get that the last term equals

P t [|A t | > 1].
To treat this term, we use that v T H t is Gaussian with mean v T L t-1 and variance η 2 mt to obtain

f v (y) -f v (y -mc) =f v (y) 1 - f v (y -mc) f v (y) ≤f v (y) mc 2 2η 2 t - c(y -v T L t-1 ) η 2 t .
Also observe that the density of

V T t H t at y ∈ R is exactly v∈S f v (y)P t [ ∀w = v : w T H t > y| v T H t = y] .
Thus,

P t [|A t | > 1] ≤ v∈S y∈R f v (y) -f v (y -mc) • • P t [ ∀w = v : w T H t > y| v T H t = y] dy ≤ v∈S y∈R f v (y)P t [ ∀w = v : w T H t > y| v T H t = y] • • mc 2 2η 2 t - c(y -v T L t-1 ) η 2 t dy = mc 2 2η 2 t - cE [V T t Z t ] η 2 t ≤ mc 2 2η 2 t + mcE [ Z t ∞ ] η 2 t .
Using the definition of c and

E [ Z t ∞ ] ≤ η √ 2t log d gives the result.

III. RANDOM-WALK PERTURBATIONS FOR PREDICTION WITH EXPERT ADVICE

In this section we refine our method to obtain bounds of optimal order in the special case of prediction with expert advice, that is, when the set of actions is the set of d = N unit vectors. In this case, we use I t to denote the unique coordinate i of V t with V i,t = 1. While the straightforward application of Algorithm 1 and Theorem 1 guarantees a regret of optimal order in this case, the switch-number guarantees are of a suboptimal O( √ n log N ). In this section, we propose a variant of our algorithm that achieves order-optimal regret guarantees while switching its predictions only O( √ n log N ) times, similarly to the algorithms of [START_REF] Kalai | Efficient algorithms for online decision problems[END_REF] and [START_REF] Geulen | Regret minimization for online buffering problems using the weighted majority algorithm[END_REF].

The algorithm-presented as Algorithm 2-is obtained by replacing the Gaussian increments in Algorithm 1 by independent random variables that take values ±1/2 with equal probabilities. The benefit of using this perturbation scheme is that the diameter of the lead packs defined in (1) can be upper bounded by a constant, and thus we can eliminate higher moments of X t+1 ∞ in the upper bound on P [|A t | > 1]. To gain further intuition, notice that choosing any fixed (i.e., nonrandom) lead-pack diameter in the proof of Lemma 1 would allow experts from outside the lead pack to take the lead with positive probability. While this probability can be decreased at the expense of slightly expanding the diameter, its rate of decay is not sufficiently fast for improving our previously presented results. In fact, balancing the two terms constituting the probability of switching gives the exact same result. On the other hand, when using ±1/2-valued random increments, it is possible to set a fixed diameter of 1 that ensures that the new leader comes from the lead pack with probability 1, and thus the extra term vanishes.

Algorithm 2 Random-walk perturbations for prediction with expert advice. Initialization: set L i,0 = 0 and Z i,0 = 0 for all i = 1, 2, . . . , N . For all t = 1, 2, . . . , n, repeat 1) Draw X i,t for all i = 1, 2, . . . , N such that

X i,t = 1 2
with probability 1 2 -1 2 with probability 1 2 . 2) Let Z i,t = Z i,t-1 + X i,t for all i = 1, 2, . . . , N .

3) Choose action

I t = arg min i (L i,t-1 + Z i,t ) ,
where ties are broken in favor of I t-1 . 4) Observe losses i,t for all i = 1, 2, . . . , N , suffer loss It,t . 5) Set L i,t = L i,t-1 + i,t for all i = 1, 2, . . . , N .

The next theorem summarizes our performance bounds for the proposed forecaster.

Theorem 2: The expected regret and expected number of switches of actions of the forecaster of Algorithm 2 satisfy, for all possible loss sequences (under the oblivious-adversary model),

ER n ≤ 2EC n ≤ 8 2n log N + 16 log n + 16 .
While it is possible to perform the analysis of Algorithm 2 similarly to that of Algorithm 1, we take a different path: The proof we present below is based on the observation that the regret of Algorithm 2 can be bounded in terms of the number of action switches. The next simple lemma formalizes this statement.

Lemma 2: Fix any i ∈ {1, 2, . . . , N }. Then

L n -L i,n ≤ 2C n + Z i,n+1 - n+1 t=1 X It-1,t .
Proof: We apply Lemma 3.1 of [START_REF] Cesa-Bianchi | Prediction, Learning, and Games[END_REF] (sometimes referred to as the "be-the-leader" lemma) for the sequence ( •,t-1 + X •,t ) ∞ t=1 with j,0 = 0 for all j ∈ {1, 2, . . . , N }, obtaining n+1 t=1

( It,t-1 + X It,t ) ≤ n+1 t=1 ( i,t-1 + X i,t ) = L i,n + Z i,n+1 .
Reordering terms, we get

n t=1 It,t ≤ L i,n + n+1 t=1 It-1,t-1 -It,t-1 +Z i,n - n+1 t=1
X It,t .

(3) The last term can be rewritten as

- n+1 t=1 X It,t = - n+1 t=1 X It-1,t + n+1 t=1 X It-1,t -X It,t .
Now notice that X It-1,t -X It,t and It-1,t-1 -It,t-1 are both zero when I t = I t-1 and are upper bounded by 1 otherwise. That is, we get that

n+1 t=1 It-1,t-1 -It,t-1 + n+1 t=1 X It-1,t -X It,t ≤ 2 n+1 t=1 1 {It-1 =It} = 2C n .
Putting everything together gives the statement of the lemma.

Next we analyze the number of switches C n . Similarly to the analysis of Algorithm 1, we study the lead pack A t defined as

A t = {i ∈ {1, . . . , N } : L i,t-1 +Z i,t < L It,t-1 +Z It,t +2} .
Once again, observe that no action from outside the lead pack has a positive probability of taking the lead at time t + 1. We bound the probability of lead change as

P [I t = I t+1 ] ≤ 1 2 P [|A t | > 1] .
The key to the proof of the theorem is the following lemma that gives an upper bound for the probability that the lead pack contains more than one action. It implies, in particular, that

E [C n ] ≤ 4 2n log N + 4 log n + 4 ,
which is what we need to prove the bounds of Theorem 2.

Lemma 3:

P [|A t | > 1] ≤ 4 2 log N t + 8 t .
Proof: Define p t (k) = P Z i,t = k 2 for all k = -t, . . . , t and we let S t denote the set of leaders at time t:

S t = j ∈ {1, . . . , N } : L j,t-1 +Z j,t = min i {L i,t-1 +Z i,t } .
The forecaster picks I t ∈ S t arbitrarily when I t-1 ∈ S t , otherwise it stays with I t = I t-1 . Let us start with analyzing the probability of the event {A t = {I t }} = {|A t | = 1}:

P [|A t | = 1] = t k=-t N j=1 p t (k)P min i =j {L i,t-1 + Z i,t } ≥ L j,t-1 + k 2 + 2 ≥ t k=-t+4 N j=1 p t (k-4)P min i =j {L i,t-1 +Z i,t } ≥ L j,t-1 + k 2 = t k=-t+4 N j=1 p t (k)P min i =j {L i,t-1 +Z i,t } ≥ L j,t-1 + k 2 p t (k-4) p t (k) .
Before proceeding, we need to make two observations. First of all, N j=1 p t (k)P min i∈{1,2,...,N }\j

{L i,t-1 + Z i,t } ≥ L j,t-1 + k 2 ≥ P ∃j ∈ S t : Z j,t = k 2 ≥ P min j∈St Z j,t = k 2 ,
where the first inequality follows from the union bound and the second from the fact that the latter event implies the former. Also notice that t+Z1,t 2 is binomially distributed with parameters t and 1/2 and therefore p

t (k) = t t+k 2 1 2 t . Hence, p t (k -4) p t (k) = t+k 2 ! t-k 2 ! t+k 2 -2 ! t-k 2 + 2 ! = 1 + 4(t + 1)(k -2) (t -k + 2)(t -k + 4)
.

It can be easily verified that

4(t + 1)(k -2) (t -k + 2)(t -k + 4) ≥ 4(t + 1)(k -2) (t + 2)(t + 4)
holds for all k ∈ [-t, t]. Using our first observation and the bound on P [|A t | = 1], we get

P [|A t | = 1] ≥ t k=-t+4 P min j∈St Z j,t = k 2 p t (k -4) p t (k) .
Along with our second observation, this implies

P [|A t | > 1] ≤ 1 - t k=-t+4 P min j∈St Z j,t = k 2 p t (k -4) p t (k) ≤ 1 - t k=-t+4 P min j∈St Z j,t = k 2 1 + 4(t + 1)(k -2) (t + 2)(t + 4) ≤ t k=-t P min j∈St Z j,t = k 2 4(2 -k)(t +

APPENDIX

Proof of the first statement of Theorem 1: The proof is based on the proof of Theorem 4.2 of [START_REF] Cesa-Bianchi | Prediction, Learning, and Games[END_REF] and Theorem 3 of [START_REF] Audibert | Regret in online combinatorial optimization[END_REF], with key insights taken from Neu and Bartók [START_REF] Neu | An efficient algorithm for learning with semibandit feedback[END_REF]. The main difference from those proofs is that the standard deviation of our perturbations changes over time, however, this issue is easy to treat. First, we define an infeasible "forecaster" that peeks one step into the future and uses perturbation Z t = √ tX 1 :

V t = arg min w∈S w T L t + Z t .
Now fix any v ∈ S. Applying Lemma 3.1 of [START_REF] Cesa-Bianchi | Prediction, Learning, and Games[END_REF] for the sequence

t-1 + Z t -Z t-1 ∞ t=1 with 0 = 0, we get n t=1 V T t ( t + ( Z t -Z t-1 )) ≤ v T (L n + Z n ).
After reordering, we obtain

n t=1 V T t t ≤v T L n + v T Z n + n t=1 (V t -V t ) T t - n t=1 V T t ( Z t -Z t-1 ) =v T L n + v T Z n + n t=1 (V t -V t ) T t + n t=1 ( √ t -1 - √ t) V T t X 1
The last term can be bounded as n t=1

( √ t -1 - √ t) V T t X 1 ≤ n t=1 ( √ t - √ t -1) V T t X 1 ≤m n t=1 ( √ t - √ t -1) X 1 ∞ ≤m √ n X 1 ∞ .
Taking expectations, we obtain the bound

E L n -v T L n ≤ n t=1 E (V t -V t ) T t + ηm 2n log d,
where we used E [ X 1 ∞ ] ≤ η √ 2 log d. Thus, we are left with the problem of bounding E (V t -V t ) T t for each t ≥ 1. Similarly to [START_REF] Neu | An efficient algorithm for learning with semibandit feedback[END_REF], we do this by introducing p t (u) = P [V t = u] and pt (u) = P V t = u for all u ∈ S and studying the relationship between the distributions p t and pt . To this end, let us fix an arbitrary u ∈ S and define the "sparse loss vector" ˜ t (u) with its k-th component being ˜ k,t (u) = u k k,t . Let V t (u) = arg min w∈S w T L t-1 + ˜ t (u) + Z t and pt (u) = P V t (u) = u .

As shown in Lemma 2 of [START_REF] Neu | An efficient algorithm for learning with semibandit feedback[END_REF], pt (u) ≤ pt (u) holds independently of the distribution of the perturbations, given that all components of the loss vector are nonnegative. Now define w t (z) = arg min w∈S w T (L t-1 + z) for all z ∈ R d and let f t (z) be the density of Z t (which coincides with the density of Z t ). For all u ∈ S, we have

p t (u) =E

Fig. 1 .

 1 Fig. 1. Online linear optimization.

  Now using E [max j Z j,t ] ≤ t log N

								1)
								(t + 2)(t + 4)
	=	8(t + 1) (t + 2)(t + 4)	-8	t + 1 (t + 2)(t + 4)	E min j∈St	Z j,t
	≤	8 t	+	8 t	E	max j∈{1,2,...,N }	Z j,t .
								2	implies
						P [|A t | > 1] ≤ 4	2 log N t	+	8 t
	as desired.

  d f t z + ˜ t (u) -f t (z) 1 {wt(z)=u} dz .While the first term is upper bounded by pt (u), the last one can be upper bounded as where we have used that ˜ t (u) 2 2 ≤ m and ˜ t (u) 1 ≤ m hold by the definition of ˜ t (u). Using that P V t = u = pt (u), we obtain where we used E [ Z t ∞ ] ≤ η √ 2t log d in the last step. Putting everything together, we obtainE L n -v T L n ≤

	E [V T t t ] =	p t (u)u T	t ≤	pt (u)u T	t
				u∈S						u∈S
										
	+	u∈S	 p t (u)m η 2 t	+	m η 2 t	z∈R d	f t (z) z ∞ 1 {wt(z)=u} dz	 u T	t
	≤ E V T t t +	m 2 η 2 t	+	m 2 η 2 t	z∈R d	f t (z) z ∞	u∈S	1 {wt(z)=u} dz
	= E V T t t +	m 2 η 2 t	+	m 2 η 2 t	E [ Z t ∞ ]
	≤ E V T t t +	m 2 η 2 t	+	m 2 η	2 log d t	,
			≤	n t=1 2m 2 √ 2n log d m 2 η 2 t + η + ηm 2n log d + n m 2 η 2 log d t t=1	+ ηm 2n log d m 2 (log n + 1) η 2 ,
										z∈R z∈R d f t (z) 1 -exp	z -˜ t (u) η 2 t	T ˜ t (u)	1 {wt(z)=u} dz
										≤ -	f t (z)	(z -˜ t (u)) T ˜ t (u) η 2 t	1 {wt(z)=u} dz
										z∈R d
										≤	p t (u) ˜ t (u) η 2 t	2 2	+	1 η 2 t

1 {wt(Zt)=u} = z∈R d f t (z)1 {wt(z)=u} dz = z∈R d f t z + ˜ t (u) 1 wt z+ ˜ t(u) =u dz =E 1 wt Zt+ ˜ t(u) =u + z∈R d f t z + ˜ t (u) -f t (z) 1 {wt(z)=u} dz =p t (u) + z∈R d f t (z) z T ˜ t (u) 1 {wt(z)=u} dz ≤ p t (u)m η 2 t + m η 2 t z∈R d f t (z) z ∞ 1 {wt(z)=u} dz,

concluding the proof of the statement.

ACKNOWLEDGMENT

This research was supported in part by the Natural Sciences and Engineering Research Council (NSERC) of Canada, the Spanish Ministry of Science and Technology grant MTM2012-37195, INRIA, the European Union Seventh Framework Programme (FP7/2007-2013) under grant agreement 270327 (project CompLACS), the Ministry of Higher Education and Research, and by FUI project Hermès. The authors thank László and János Györfi, as well as László Németh for organizing the workshop PICSA 2012 in Jásd, during which some major details of the paper were worked out.


Gergely Neu

First-order regret bounds for combinatorial semi-bandits

Keywords: online learning, online combinatorial optimization, semi-bandit feedback, follow the perturbed leader, improvements for small losses, first-order bounds

We consider the problem of online combinatorial optimization under semi-bandit feedback, where a learner has to repeatedly pick actions from a combinatorial decision set in order to minimize the total losses associated with its decisions. After making each decision, the learner observes the losses associated with its action, but not other losses. For this problem, there are several learning algorithms that guarantee that the learner's expected regret grows as O( √ T ) with the number of rounds T . In this paper, we propose an algorithm that improves this scaling to O( √ L * T ), where L * T is the total loss of the best action. Our algorithm is among the first to achieve such guarantees in a partial-feedback scheme, and the first one to do so in a combinatorial setting.

Introduction

Consider the problem of sequential multi-user channel allocation in a cognitive radio network (see, e.g., [START_REF] Gai | Combinatorial network optimization with unknown variables: Multi-armed bandits with linear rewards and individual observations[END_REF]. In this problem, a network operator sequentially matches a set of N secondary users to a set of M channels, with the goal of maximizing the overall quality of service (QoS) provided for the secondary users, while not interfering with the quality provided to primary users. Due to different QoS preferences of users and geographic dispersion, different users might perceive the quality of the same channel differently. Furthermore, due to uneven traffic on the channels and other external conditions, the quality of each matching may change over time in a way that is very difficult to model by statistical assumptions. Formally, the loss associated with user i being matched to channel j in the t th decision-making round is t,(ij) ∈ [0, 1], and the goal of the network operator is to sequentially select matchings V t so as to minimize its total loss T t=1

(ij)∈Vt t,(ij) after T rounds. It is realistic to assume that the operator learns about the instantaneous losses of the allocated user-channel pairs after making each decision, but counterfactual losses are never revealed. Among many other sequential optimization problems of practical interest such as sequential routing or online advertising, the above problem can be formulated in the general framework of online combinatorial optimization [START_REF] Audibert | Regret in online combinatorial optimization[END_REF]. This learning problem can be formalized as a repeated game between a learner and an environment. In every round t = 1, 2, . . . , T , the learner picks a decision V t from a combinatorial decision set S ⊆ {0, 1} d . Simultaneously, the environment fixes a loss vector t ∈ [0, 1] d and the learner suffers a loss of V T t t . We assume that v 1 ≤ m holds for all v ∈ S, entailing V T t t ≤ m. At the end of the round, the learner observes some feedback based on V t and t . The simplest setting imaginable is called the full-information setting where the learner observes the entire loss vector t . In most practical situations, however, the learner cannot expect such rich feedback. In this paper, we focus on a more realistic and challenging c 2015 G. Neu. feedback scheme known as semi-bandit: here the learner observes the subset of components t,i of the loss vector with V t,i = 1. Note that this precise feedback scheme arises in our cognitive-radio example. The performance of the learner is measured in terms of the regret

R T = max v∈S T t=1 (V t -v) T t ,
that is, the gap between the total loss of the learner and that of the best fixed action. The interaction history up to time t is captured by F t-1 = σ(V 1 , . . . , V t-1 ). In the current paper, we focus on oblivious environments who are only allowed to pick each loss vector t independently of F t-1 .

The learner is allowed to (and, by standard arguments, should) randomize its decision V t based on the observation history F t-1 . With these remarks in mind, we will focus on the expected regret E [R T ] from now on, where the expectation integrates over the randomness injected by the learner.

Most of the literature is concerned with finding algorithms for the learner that guarantee that the regret grows as slowly as possible with T . Of equal importance is establishing lower bounds on the learner's regret against specific classes of environments. Both of these questions are by now very well-studied, especially in the simple case where S is the set of d-dimensional unit vectors; this setting is known as prediction with expert advice when considering full feedback (e.g., [START_REF] Cesa-Bianchi | Prediction, Learning, and Games[END_REF] and the multi-armed bandit problem when considering semi-bandit feedback (e.g., Auer et al., 2002a). In these settings, the minimax regret is known to be of Θ( √ T log d) and Θ( √ dT ), respectively. Several learning algorithms are known to achieve these regret bounds, at least up to logarithmic factors in the bandit case, with the notable exception of the POLYINF algorithm proposed by [START_REF] Audibert | Minimax policies for adversarial and stochastic bandits[END_REF]. The minimax regret for the general combinatorial setting was studied by [START_REF] Audibert | Regret in online combinatorial optimization[END_REF], who show that no algorithm can achieve better regret than Ω(m T log(d/m)) in the full-information setting, or Ω( √ mdT ) in the semi-bandit setting. Audibert et al. also propose algorithms that achieve these guarantees under both of the above feedback schemes. Furthermore, they show that a natural (although not always efficient) extension of the EXP3 strategy of Auer et al. (2002a) guarantees a regret bound of O m dT log(d/m) in the semi-bandit setting (see also [START_REF] György | on-line shortest path problem under partial monitoring[END_REF]. A computationally efficient strategy for the same setting was proposed by [START_REF] Neu | An efficient algorithm for learning with semi-bandit feedback[END_REF], who show that an augmented version of the FPL algorithm of [START_REF] Kalai | Efficient algorithms for online decision problems[END_REF] achieves a regret of O(m √ dT log d), essentially matching the bound of EXP3.

Even though the above guarantees cannot be substantially improved under the worst possible realization of the loss sequence, certain improvements are possible for specific types of loss sequences. Arguably, one of the most fundamental of these improvements are bounds that replace the number of rounds T with the loss of the best action

L * T = min v∈S v T L T , thus guaranteeing a regret of O( √ L * T )
. Such improved bounds, often called first-order regret bounds, are abundant in the online learning literature when assuming full feedback: the key for obtaining such results is usually a clever tuning rule for otherwise standard learning algorithms such as HEDGE [START_REF] Cesa-Bianchi | Improved second-order bounds for prediction with expert advice[END_REF][START_REF] Cesa-Bianchi | Prediction, Learning, and Games[END_REF] or FPL [START_REF] Hutter | Prediction with expert advice by following the perturbed leader for general weights[END_REF][START_REF] Kalai | Efficient algorithms for online decision problems[END_REF][START_REF] Van Erven | Follow the leader with dropout perturbations[END_REF]. The intuitive advantage of such first-order bounds that they can effectively take advantage of "easy" learning problems where there exists an action with superior performance. In our cognitive-radio example, this corresponds to the existence of a user-channel matching that tends to provide high quality of service.

One obvious question is whether such improvements are possible under partial-information constraints. We can answer this question in the positive, although such bounds are far less common than in the full information case. In fact, we are only aware of three algorithms that achieve such bounds: EXP3LIGHT described in Section 4.4 of [START_REF] Stoltz | Incomplete information and internal regret in prediction of individual sequences[END_REF], GREEN by [START_REF] Allenberg | Hannan consistency in on-line learning in case of unbounded losses under partial monitoring[END_REF] and SCRiBLe by [START_REF] Abernethy | Interior-point methods for full-information and bandit online learning[END_REF], as shown by [START_REF] Rakhlin | Online learning with predictable sequences[END_REF] √ L * T log(dT )) in the multi-armed bandit problem, respectively. These results, however, either do not generalize to the combinatorial setting (see Section 2 for a discussion on GREEN) or already scale poorly with the problem size in the simplest partial-information setting. Furthermore, implementing these algorithms is also not straightforward for combinatorial decision sets.

In this paper, we propose a computationally efficient algorithm that guarantees similar improvements for combinatorial semi-bandits. Our approach is based on the Follow-the-Perturbed-Leader (FPL) algorithm of [START_REF] Hannan | Approximation to Bayes risk in repeated play[END_REF], as popularized by [START_REF] Kalai | Efficient algorithms for online decision problems[END_REF]. We show that an appropriately tuned variant of our algorithm guarantees a regret bound of O m √ dL * T log(d/m) , largely improving on the minimax-optimal bounds whenever L * T = o(T ). In the case of multiarmed bandits where m = 1, the bound becomes O( √ dL * T log d). Notice however that when m > 1, L * T can be as large as Ω(mT ) in the worst case, making our bounds inferior to the best known bounds concerning FPL and EXP3. To circumvent this problem, as well as the need to know a bound on L * T to tune our parameters, we also propose an adaptive variant of our algorithm that guarantees a regret of O m √ min{dL * T , dT } log(d/m) . Thus, our performance guarantees are in some sense the strongest among known results for non-stochastic combinatorial semi-bandits.

Besides first-order bounds, there are several other known ways of improving worst-case performance guarantees of O( √ T ) for non-stochastic multi-armed bandits. A common improvement is replacing T by the gain of the best action, T -L * T (see, e.g., Auer et al., 2002a;[START_REF] Audibert | Minimax policies for adversarial and stochastic bandits[END_REF]. Such bounds, while helpful in some cases where all actions tend to suffer large losses (e.g., in online advertising where even the best ads have low clickthrough rates), are not as satisfactory as our bounds: these bounds get worse and worse as one keeps increasing the gain of the best action, even if all other losses are kept constant, despite the intuition that this operation actually makes the learning problem much easier. That is, bounds of the above type fail to reflect the "hardness" of the learning problem at hand. The work of [START_REF] Hazan | Better algorithms for benign bandits[END_REF] considers a much more valuable type of improvement: they provide regret bounds of

O(d 2 √ Q T ), where Q T = min µ∈R d T t=1 t -µ 2
2 is the quadratic variation of the losses. Such bounds are very strong in situations where the sequence of loss vectors "stays close" to its mean in all rounds. Notice however that, unlike our first-order bounds, this improvement requires a condition to hold for entire loss vectors and not just the loss of the best action. This implies that first-order bounds are more robust to loss variations of obviously suboptimal actions. On the other hand, it is also easy to construct an example where L * T grows linearly while Q T is zero. In summary, we conclude that first-order bounds and bounds depending on the quadratic variation are not comparable in general, as they capture very different kinds of regularities in the loss sequences. For further discussion of higher-order and variation-dependent regret bounds, see [START_REF] Cesa-Bianchi | Improved second-order bounds for prediction with expert advice[END_REF] and [START_REF] Hazan | Extracting certainty from uncertainty: regret bounded byvariation incosts[END_REF]. We also mention that several other types of improvements exist for full-information settings-we refer to recent works of [START_REF] Rakhlin | Online learning with predictable sequences[END_REF], [START_REF] Sani | Exploiting easy data in online optimization[END_REF] and the references therein.

Finally, let us comment on related work on the so-called stochastic bandit setting where the loss vectors are drawn i.i.d. in every round. In this setting, combinatorial semi-bandits have been studied under the name "combinatorial bandits" [START_REF] Gai | Combinatorial network optimization with unknown variables: Multi-armed bandits with linear rewards and individual observations[END_REF][START_REF] Chen | Combinatorial multi-armed bandit: General framework and applications[END_REF], giving rise to a bit of confusion2 . This line of work focuses on proving bounds on the pseudo-regret defined as max v∈S T t=1 (V t -v) T µ, where µ ∈ R d is the mean of the random vector 1 . We highlight the result of [START_REF] Kveton | Tight regret bounds for stochastic combinatorial semi-bandits[END_REF], who have very recently proposed an algorithm that guarantees bounds on the pseudo-regret of O(md(1/∆) log T ) for some distribution-dependent constant ∆ > 0 and a worst-case bound of O( √ mdT log T ). Note however that comparing these pseudo-regret bounds to bounds on the expected regret can be rather misleading. In fact, a simple argument along the lines of Section 9 of [START_REF] Audibert | Regret bounds and minimax policies under partial monitoring[END_REF] shows that even algorithms with zero pseudo-regret can actually suffer an expected regret of Ω( √ T ), when permitting multiple optimal actions. A more refined argument shows that this bound can be tightened to Ω( √ L * T ) when assuming non-negative losses, suggesting that first-order bounds on the expected regret are in some sense unbeatable even in a distribution-dependent setting3 .

From zero-order to first-order bounds: Keeping the loss estimates close together

We now explain the key idea underlying our analysis. Our approach is based on the observation that regret bounds for many known bandit algorithms (such as EXP3 by Auer et al. 2002a, OSMD with relative-entropy regularization by [START_REF] Audibert | Regret in online combinatorial optimization[END_REF], and the bandit FPL analysis of Neu and Bartók 2013) take the form

η T t=1 d i=1 t,i • t,i + D η ≤ η d i=1 L T,i + D η , (1)
where t,i is an estimate of the loss t,i , L T,i = T t=1 t,i , η > 0 is a tuning parameter, and D > 0 is a constant that depends on the particular algorithm and the decision set. The standard approach is then to design the loss estimates to be unbiased so that the above bound becomes η d i=1 L T,i + D η after taking expectations. Unfortunately, this form does not permit proving first-order bounds as L T,i may very well be Ω(T ) for either i even in very easy problem instances-that is, even an optimized setting of η gives a regret bound of O( √ dDT ) at best. Applying a similar line of reasoning, one can replace T in the above bound by (T -L * T ), the largest total gain associated with any component, but, as already discussed in the introduction, this improvement is not useful for our purposes.

In this paper, we take a different approach to optimize bounds of the form (1). The idea is to construct a loss-estimation scheme that keeps every L T,i "close" to L * T = min v∈S v L T , the estimate of the optimal action in the sense that

L T,i ≤ L * T + O 1 η . ( 2
)
Observe that this property allows rewriting the bound (1) as ηd L * T + D η + O(1). Of course, a loss-estimation scheme guaranteeing the above property has to come at the price of a certain bias. Guaranteeing that the bias satisfies certain properties and is optimistic in the sense that E L * T ≤ L * T , we can arrive at a first-order bound by choosing η = Θ( 1/L * T ). The remaining challenge is to come up with an adaptive learning-rate schedule that achieves such a bound without prior knowledge of L * T .

Our approach is not without a precedent: [START_REF] Allenberg | Hannan consistency in on-line learning in case of unbounded losses under partial monitoring[END_REF] derive a first-order bound for multi-armed bandits based on very similar principles. Their algorithm, called GREEN, relies on a clever trick that prevents picking arms that seem suboptimal. Specifically, GREEN maintains a set of weights w t,i over the arms and computes an auxiliary probability distribution p t,i ∝ w t,i . The true sampling distribution over the arms is computed by setting p t,i = 0 for all arms such that p t,i is below a certain threshold γ, and then redistributing the removed weight among the remaining arms proportionally to w t,i . The intuitive effect of this thresholding operation is that poorly performing arms are eliminated, which harnesses the further growth of their respective estimated losses. Specifically, Allenberg et al. show that property (2) and E L * T ≤ L * T simultaneously hold for their algorithm, paving the way for their first-order bound.

While providing strong technical results, [START_REF] Allenberg | Hannan consistency in on-line learning in case of unbounded losses under partial monitoring[END_REF] give little intuition as to why this approach is key to obtaining first-order bounds and how to generalize their algorithm to more complicated problem settings such as ours. Even if one is able to come up with a generalization on a conceptual level, efficient implementation of such a variant would only be possible on a handful of decision sets where EXP3 can be implemented in the first place (see, e.g., [START_REF] Koolen | Hedging structured concepts[END_REF][START_REF] Cesa-Bianchi | Combinatorial bandits[END_REF]. The probabilistic nature of the approach of Allenberg et al. does not seem to mix well with the mirror-descent type algorithms of [START_REF] Audibert | Regret in online combinatorial optimization[END_REF] either, whose proofs rely on tools from convex analysis. In the current paper, we propose an alternative way to restrict sampling of suboptimal actions that leads to property (2) in a much more transparent and intuitive way.

The algorithm: FPL with truncated perturbations and implicit exploration

Our algorithm is a variant of the well-known Follow-the-Perturbed-Leader (FPL) learning algorithm [START_REF] Hannan | Approximation to Bayes risk in repeated play[END_REF][START_REF] Kalai | Efficient algorithms for online decision problems[END_REF][START_REF] Hutter | Prediction with expert advice by following the perturbed leader for general weights[END_REF][START_REF] Neu | An efficient algorithm for learning with semi-bandit feedback[END_REF], equipped with a perturbation scheme that will enable us to prove first-order bounds through guaranteeing property (2). In every round t, FPL chooses its action as

V t = arg min v∈S v T η t L t-1 -Z t , (3)
where η t > 0 is a parameter of the algorithm, L t-1 is a vector serving as an estimate of the cumulative loss vector L t-1 = t-1 s=1 s and Z t ∈ R d is a vector of random perturbations. FPL is very well-studied in the full-information case where one can choose L t-1 = L t-1 ; several perturbation schemes are known to work well in this setting [START_REF] Kalai | Efficient algorithms for online decision problems[END_REF][START_REF] Rakhlin | Relax and randomize : From value to algorithms[END_REF][START_REF] Devroye | Prediction by random-walk perturbation[END_REF][START_REF] Van Erven | Follow the leader with dropout perturbations[END_REF][START_REF] Abernethy | Online linear optimization via smoothing[END_REF]. In what follows, we focus on exponentially distributed perturbations, which is the only scheme known to achieve near-optimal performance guarantees under bandit feedback [START_REF] Poland | FPL analysis for adaptive bandits[END_REF][START_REF] Neu | An efficient algorithm for learning with semi-bandit feedback[END_REF].

In order to guarantee that the condition (2) is satisfied, we propose to suppress suboptimal actions by using bounded-support perturbations. Specifically, we propose to use a truncated exponential distribution with the following density function:

f B (z) = e -z 1-e -B , if z ∈ [0, B] 0 otherwise.
Here, B > 0 is the bound imposed on the perturbations. In each round t, our FPL variant draws components of the perturbation vector Z t independently from an exponential distribution truncated at B t > 0, another tuning parameter of our algorithm. To define our loss estimates, let us define q t,i = E [ V t,i | F t-1 ] and the vector t with components

t,i = t,i V t,i q t,i + γ t , (4)
where γ t > 0 is the so-called implicit exploration (or IX) parameter of the algorithm controlling the bias of the loss estimates. Notice that E t,i ≤ t,i holds by construction for all i. Then, L t is simply defined as

L t = t s=1 s .
In what follows, we refer to our algorithm as FPL-TRIX, standing for "FPL with truncated perturbations and implicit exploration". Pseudocode for FPL-TRIX is presented as Algorithm 1.

Algorithm 1 FPL-TRIX Parameters: Learning rates (η t ), implicit exploration parameters (γ t ), truncation parameters (B t ). Initialization: L 0 = 0. For t = 1, 2, . . . , T , repeat 1. Draw perturbation vector Z t with independent components Z t,i ∼ f Bt .

Play action

V t = arg min v∈S v T η t L t-1 -Z t .
3. For all i, observe losses t,i V t,i and compute t,i = t,i V t,i q t,i +γt .

4. Set L t = L t-1 + t .

It will also be useful to introduce the notations D = log(d/m)+1 and β t = e -Bt . For technical reasons, we are going to assume that the sequence of learning rates (η t ) t , exploration parameters (γ t ) t and truncation parameters (β t ) t are all nonincreasing.

Before proceeding, a few comments are in order. First, note that the probabilities q t,i are generally not efficiently computable in closed form. This issue can be circumvented by the simple and efficient loss-estimation method proposed by [START_REF] Neu | An efficient algorithm for learning with semi-bandit feedback[END_REF] that produces equivalent estimates on expectation; we resort to the loss estimates (4) to preserve clarity of presentation. Otherwise, similarly to other FPL-based methods, FPL-TRIX can be efficiently implemented as long as the learner has access to an efficient linear-optimization oracle over S. Second, we remark that loss estimates of the form (4) were first proposed by [START_REF] Kocák | Efficient learning by implicit exploration in bandit problems with side observations[END_REF] as an effective way to trade off the bias and variance of importance-weighted estimates. Finally, one may ask if the truncations we introduce are essential for our algorithm to work. Answering this question requires a little deeper technical understanding of FPL-TRIX than the reader might have at this point, and thus we defer this discussion to Section 6. (For the impatient reader, the short answer is that one can get away without truncations at the price of an additive O(log T ) term in the bounds. Note however that the proof of this result still relies on the analysis of FPL-TRIX that we present in this paper.)

Some properties of FPL-TRIX

In this section, we present some key properties of our algorithm. We first relate the predictions of FPL-TRIX to those of an FPL instance that employs standard (non-truncated) exponential perturbations. Specifically, we study the relation between the expected performance of FPL-TRIX that selects the action sequence (V t ) and an auxiliary algorithm that uses a fixed exponentiallydistributed perturbation vector Z, and plays

V t = arg min v∈S v T η t L t-1 -Z (5) in round t.
In particular, we are interested in the relation between the quantities

p t (v) = P [ V t = v| F t-1 ] , p t (v) = P V t = v F t-1 , q t,i = E [ V t,i | F t-1 ] , q t,i = E V t,i F t-1
defined for all t, i and v. The following lemma establishes a bound on the total variation distance between the distributions induced by Z and Z, and thus relates the above quantities to each other.

Lemma 1 Let the components of Z and Z be drawn independently from f Bt and f ∞ , respectively.

Then, for any function G : R → [0, 1], we have EG(Z) -EG( Z) ≤ β t d. In particular, this implies that |p t (v) -p t (v)| ≤ β t d for all t and v and |q t,i -q t,i | ≤ β t d for all t and i.

Proof For ease of notation, define f = f ∞ , g = EG(Z) and g = EG( Z). We first prove g ≤ g + β t d. To this end, observe that by the definition of f Bt ,

g = z∈[0,Bt] d G(z)f Bt (z) dz ≤ 1 (1 -e -Bt ) d • z∈[0,∞] d G(z)f (z) dz = g (1 -e -Bt ) d .
After reordering and using the inequality (1 -x) d ≥ 1 -dx that holds for all x ≤ 1 and all d ≥ 1, we obtain g(1 -β t d) ≤ g. The upper bound on g follows from reordering again and using g ≤ 1.

To prove the lower bound on g, we can use a similar argument as

g = z∈[0,Bt] d G(z)f Bt (z) dz = 1 (1 -e -Bt ) d • z∈[0,Bt] d G(z)f (z) dz ≥ 1 (1 -e -Bt ) d • g - z∈[Bt,∞) d f (z) dz = g (1 -e -Bt ) d - 1 -1 -e -Bt d
(1 -e -Bt ) d .

After reordering and using (1 -x) d ≥ 1 -dx again, we obtain

g ≤ g 1 -e -Bt d + 1 -1 -e -Bt d ≤ g + β t d,
concluding the proof.

The other important property of FPL-TRIX that we highlight in this section is that the loss estimates generated by the algorithm indeed satisfy property (2). NEU Lemma 2 Assume that the sequences (η t ), (γ t ) and (β t ) are nonincreasing. Then for any i and v ∈ S, we have

L T,i ≤ v T L T + m (D + B T ) η T + 1 γ T .
Proof Fix an arbitrary i and v and let τ denote the last round in which q t,i > 0. This entails that L T,i = L τ,i holds almost surely, as V t,i = 0 for all t > τ . By the construction of the algorithm and the perturbations, q τ,i > 0 implies that there exists a w with w i = 1 and p t (w) > 0. Thus,

w T L τ -1 ≤ min u∈S u T L τ -1 + B τ m η τ ≤ V T τ L τ -1 + B T m η T = V T τ L τ -1 - 1 η t Z + 1 η t V T t Z + B T m η T ≤ v T L τ -1 - 1 η t Z + V T τ Z + B T m η T ,
where the first inequality follows from the fact that p t (w) > 0, the second one follows from B τ /η τ ≤ B T /η T and the last one from the definition of V τ . After integrating both sides with respect to the distribution of Z and bounding τ,i ≤ 1/γ τ ≤ 1/γ T , we obtain the result as

L T,i = L τ -1,i + τ,i ≤ w T L τ -1 + 1 γ T ≤ v T L T + m (D + B T ) η T + 1 γ T ,
where we used the fact that L t,j is nonnegative for all j, w i = 1, and E V T τ Z ≤ m (log(d/m) + 1) = mD, which follows from Lemma 10 stated and proved in the Appendix.

Regret bounds

This section presents our main results concerning the performance of FPL-TRIX under various parameter settings. We begin by stating a key theorem.

Theorem 3 Assume that the sequences (η t ), (γ t ) and (β t ) are nonincreasing and β t d ≤ γ t holds for all t. Then for all v ∈ S, the total loss suffered by FPL-TRIX satisfies

T t=1 V T t t ≤v T L T + mD η T + T t=1 (η t m + β t d + γ t ) • d i=1 t,i .
The proof of the theorem is deferred to Section 5. Armed with this theorem, we are now ready to prove our first main result: a first-order bound on the expected regret of FPL-TRIX.

Corollary 4 Consider FPL-TRIX run with the time-independent parameters γ = ηm and βd = γ (and thus B = log(d/m) -log η). The expected regret of the resulting algorithm satisfies

E [R T ] ≤ mD η + 3ηmdL * T + 3m 2 d(D + B) + 3d.
In particular, setting η = min 1, 3 log(d/m)+1

dL * T guarantees E [R T ] ≤ 5.2m dL * T (log(d/m) + 1) + 1.5m 2 d max {log(dL * T ), 0} + O m 2 d log(d/m) . Proof Let v * = arg min v∈S v T L T .
E [R T ] ≤3m 3dL * T D + mD + 3m 2 d 2 log(d/m) + 1 + 3d,
proving the statement as 3 √ 3 < 5.2. For the case η ≤ 1, the bound follows from substituting the value of η as

E [R T ] ≤2m 3dL * T D + 3 2 m 2 d log(dL * T ) + 3m 2 d 2 log(d/m) + 1 + 3d,
where we used that B = log(d/m) + log(1/η) and log(1/η) ≤ log(dL * T )/2. Notice that achieving the above bounds requires perfect knowledge of L * T , which is usually not available in practice. While one could use a standard doubling trick to overcome this difficulty, we choose to take a different path to circumvent this issue, and propose a modified version of FPL-TRIX that is able to tune its learning rate and other parameters solely based on observations. We note that our tuning rule has some unorthodox qualities and might be of independent interest.

Similarly to the parameter choice suggested by Corollary 4, we will use a single sequence of decreasing non-negative learning rates (η t ) and set γ t = mη t and β t = (m/d)η t for all t. For simplicity, let us define the notations s t = d i=1 t,i and S t = 1 D + t k=1 s k , with S 0 = 1 D > 0. With these notations, we define our tuning rule as

η t = D S t-1 . (6)
Notice that η 1 = D, and thus β 1 = η 1 (m/d) = (m/d)(log(d/m) + 1) < 1, ensuring that B 1 > 0 and the algorithm is well-defined. This follows from the inequality z(1 -log z) < 1 that holds for all z ∈ (0, 1). The delicacy of the tuning rule ( 6) is that the terms s t are themselves bounded in terms of the random quantity 1/η t , and not some problem-dependent constant. To the best of our knowledge, all previously known analyses concerning adaptive learning rates apply a deterministic bound on s t at some point, largely simplifying the analysis. As we will see below, treating this issue requires a bit more care than usual. The following theorem presents the performance guarantees of the resulting variant of FPL-TRIX.

Theorem 5 The regret of FPL-TRIX with the adaptive learning rates defined in Equation (6) simultaneously satisfies

E [R T ] ≤13m dL * T (log(d/m) + 1) + O m 2 d log(dT )
and

E [R T ] ≤13m dT (log(d/m) + 1) + 9.49m.
Proof Let v * = arg min v∈S v T L T . First, notice that the learning-rate sequence defined by Equation ( 6) is nonincreasing as required by Theorem 3. Also note that s t is nonnegative and is bounded by m γt = 1 ηt for all t, and 1 ηt = S t-1 /D ≤ S t-1 holds since S t-1 ≥ 1 D for all t. These facts together imply that η t ≤ 2D/S t as

2D S t = 2D S t-1 + s t ≥ 2D S t-1 + 1 ηt ≥ 2D S t-1 + S t-1 = D S t-1 = η t .
Combining the above bound with Lemma 3.5 of Auer et al. (2002b), we get

T t=1 η t s t ≤ √ 2D T t=1 s t √ S t ≤ 2 2DS T .
Using η T ≤ 2D/S T again, the right-hand side can be further bounded as 2 √ 2DS T ≤ 4D η T and the bound of Theorem 3 applied for v * becomes

T t=1 V T t t -v T * L T ≤ 13m D η T . (7)
Now, we are ready to prove the second bound in the theorem. Notice that D η T = DS T -1 ≤ √ DS T holds by the tuning rule and

E [S T ] = 1 D + d i=1 E L T,i ≤ 1 + dT, (8)
where we used that E t,i ≤ t,i ≤ 1. The statement then follows from plugging this bound into Equation ( 7), taking expectations and using Jensen's inequality.

Proving the first bound requires a bit more care. First, an application of Lemma 2 gives

S T ≤ 1 D + d v T * L T + m(B T + D) + 1 m η T .
Now recall that D η T ≤ √ DS T holds by the tuning rule. Bounding S T as above, this implies

D η T ≤ 1 + dD v T * L T + m(B T + D) + 1 m η T .
Solving the resulting quadratic equation for the largest possible value of 1/η T gives

D η T ≤ 1 + dDv T * L T + 2md(log(1/β T ) + D) + 2d m ≤ dDv T * L T + md(log(S T ) + 3 log(d/m) + 2) + 2d m + 1.
The first term can be directly bounded by using Jensen's inequality as

E v T * L T ≤ v T * L T = L *
T . Finally, we bound E [log(S T )] ≤ log(dT + 1) by using the inequality (8). The statement of the theorem now follows from substituting into Equation ( 7) and taking expectations.

The proof of Theorem 3

Finally, let us turn to proving our key theorem. For the proof, we recall the auxiliary forecaster defined in Equation ( 5) that uses a fixed non-truncated perturbation vector Z and also define a variant that also allowed to peek one step into the future:

V t = arg min v∈S v T η t L t-1 -Z and V + t = arg min v∈S v T η t L t -Z .
We will use the notation p + t (v) = P V + t = v F t for all v ∈ S. We start with the following two standard statements concerning the performance of the auxiliary forecaster [START_REF] Neu | An efficient algorithm for learning with semi-bandit feedback[END_REF]. Note that the first of these lemmas slightly improves on the result of [START_REF] Neu | An efficient algorithm for learning with semi-bandit feedback[END_REF] in replacing their log d factor by log(d/m). For completeness, we provide the proof of this improved bound in the Appendix.

Lemma 6 For any v ∈ S,

T t=1 u∈S p + t (u) (u -v) t ≤ m (log(d/m) + 1) η T . (9)
Lemma 7 For all t,

u∈S p t (u) -p + t (u) u t ≤ η t u∈S p t (u) u t 2 .
The following lemma bounds the term on the right-hand side of the above bound.

Lemma 8 Assume that βd ≤ γ. Then for all t,

u∈S p t (u) u T t 2 ≤ m d j=1 t,j .
Proof The statement is proven as

u∈S p t (u) u T t 2 = E   d i=1 d j=1 V t,i t,i • V t,j t,j F t   ≤ d i=1 V t,i q t,i q t,i + γ t • d j=1 t,j ≤ d i=1 V t,i q t,i + β t d q t,i + γ t • d j=1 t,j ≤ m d j=1 t,j ,
where the first inequality follows from the definitions of t and q t,i and bounding V t,j ≤ 1, the second one follows from using Lemma 1 and the last one from β t d ≤ γ t and V t 1 ≤ m.

Our final lemma quantifies the bias of the learner's estimated losses.

Lemma 9 For all t,

u∈S p t (u) u T t ≥ V T t t -(γ t + β t d) d i=1 t,i .
Proof First, note that by Lemma 1, we have

u∈S p t (u) u T t = d i=1 q t,i t,i ≥ d i=1 q t,i t,i -β t d d i=1 t,i .
Then, the proof is concluded by observing that d i=1 q t,i t,i = d i=1 q t,i V t,i t,i q t,i + γ t = V T t t -γ t d i=1

V t,i t,i q t,i + γ t = V T t t -γ t d i=1 t,i .

The statement of Theorem 3 follows from piecing the lemmas together.

Discussion

We conclude by discussing some implications and possible extensions of our results.

Why truncate? One might ask whether truncating the perturbations is really necessary for our bounds to hold. We now provide an argument that shows that it is possible to achieve similar results without explicit truncations, if we accept an additive O(log(dT )) term in our bound. In particular, consider FPL with non-truncated exponential perturbations. It is easy to see that with probability at least 1 -δ/(dT ), all perturbations remain bounded by B = log( dT δ ). One can then analyze FPL under this condition along the same lines as the proof of Corollary 4, the main difference being that we also have to account for the regret arising from the low-probability event that not all perturbations are bounded. Bounding the regret in this case by the trivial bound dT , this additional term becomes δdT . Setting δ = dL * T /dT makes the total regret dL * T -however, notice that this gives B = Θ(log(dT )), which shows up additively in the bound. A similar argument can be shown to work for the adaptive version of FPL-TRIX. We note that the implicit exploration induced by the bias parameter γ and other techniques developed in this paper are still essential to prove these results.

High-probability bounds. Another interesting question is whether our results can be extended to hold with high probability. Luckily, it is rather straightforward to extend Corollary 4 to achieve such a result by replacing t,i with t,i = 1 ω log(1 + ω t,i ) for an appropriately chosen ω > 0, as suggested by [START_REF] Audibert | Regret bounds and minimax policies under partial monitoring[END_REF]. While such a result would also enable us to handle adaptive environments, it has the same drawback as Corollary 4: it requires perfect knowledge of L * T . Proving high-confidence bounds for the adaptive variant of FPL-TRIX, however, is far less straightforward; we leave this investigation for future work.

Lugosi, 2006, Lemma 3.1) to the loss sequence defined as 1 -µ 1 Z, 2 -(µ 2 -µ 1 ) Z, . . . , T -(µ T -µ T -1 ) Z to obtain

T t=1 V + t T t -(µ t -µ t-1 ) Z ≤ v T L T -µ T Z .
After reordering and observing that -v T Z ≤ 0, we get

T t=1 V + t -v T t ≤ T t=1 (µ t -µ t-1 ) V + t T Z ≤ T t=1 (µ t -µ t-1 ) • max u∈S u T Z = µ T • max u∈S u T Z,
where we used that the sequence (µ t ) is nondecreasing and u T Z ≥ 0 for all u ∈ S. The result follows from integrating both sides with respect to the distribution of Z and applying Lemma 10 to obtain E max u∈S u T Z ≤ m (log(d/m) + 1).

  The proof of the first statement follows directly from combining the bounds of Theorem 3 and Lemma 2 for v = v * , taking expectations and noticing that E v T * L T ] ≤ L * T . For the second statement, first consider the case when η = 1 and thus β = η(m/d) = m/d, giving B = log(1/β) = log(d/m). Now notice that the setting of η implies L * T ≤ (3D)/d and thus L * T ≤ (3L * T D)/d. Then, substituting the value of η into the first bound of the theorem gives

The obscure nature of such first-order bounds is reflected by the fact that Rakhlin and Sridharan prove their corresponding result simply because they were not aware of the two previous results.

The term "combinatorial bandits" was first used by[START_REF] Cesa-Bianchi | Combinatorial bandits[END_REF], in reference to online combinatorial optimization problems under full bandit feedback where the learner only observes V T t t after round t.

3.[START_REF] Hazan | Extracting certainty from uncertainty: regret bounded byvariation incosts[END_REF] use a similar argument to show that variation-dependent bounds are unbeatable for signed losses in a similar sense.

Acknowledgments

This work was supported by INRIA, the French Ministry of Higher Education and Research, and by FUI project Hermès. The author wishes to thank the anonymous reviewers for their valuable comments that helped to improve the paper.

Appendix A. Some technical proofs

We first prove a statement regarding the mean of the sum of top m out of d independent exponential random variables.

Lemma 10 Let Z 1 , Z 2 , . . . , Z d be i.i.d. exponential random variables with unit expectation and let

Then, as Y is nonnegative, we have for any A ≥ 0 that

where the last inequality follows from the union bound. Setting A = m log(d/m) minimizes the above expression over the real line, thus proving the statement.

With this lemma at hand, we are now ready to prove Lemma 6.

Proof [Proof of Lemma 6] To enhance readability, define µ t = 1/η t for t ≥ 1 and µ 0 = 0. We start by applying the classical follow-the-leader/be-the-leader lemma (see, e.g., Cesa-Bianchi and


Michael Defoort
email: michael.defoort@univ-valenciennes.fr

Andrey Polyakov

Guillaume Demesure

Mohamed Djemai

Kalyana Chakravarthy Veluvolu

Leader

Keywords: Multi-agent system, Consensus, Fixed-time convergence, Distributed tracking

come

Introduction

Multi-agent systems (MAS) have been studied with great attention during the last few decades because multiple agents may perform a task more efficiently than a single one, reduce sensibility to possible agent fault and give high flexibility during the mission execution. Many recent works deal with cooperative scheme for MAS due to its broad range of applications in various areas, e.g. flocking [START_REF] Wen | A connectivity-preserving flocking algorithm for multi-agent dynamical systems with bounded potential function[END_REF], rendezvous [START_REF] Song | Rendezvous of mobile agents with constrained energy and intermittent communication[END_REF], formation control [START_REF] Fax | Information Flow and Cooperative Control of Vehicle Formations[END_REF][START_REF] Defoort | Sliding Mode Formation Control for Cooperative Autonomous Mobile Robots[END_REF], containment control [START_REF] Wang | Distributed containment control of second-order multi-agent systems with inherent non-linear dynamics[END_REF] and sensor network [START_REF] Zhang | Distributed average filtering for sensor networks with sensor saturation[END_REF].

Among them, the consensus problem, which objective is to design distributed control policies that enable agents to reach an agreement regarding a certain quantity of interest by relying on neighbors' information [START_REF] Ren | Consensus Seeking in Multi-agent Systems under Dynamically Changing Interaction Topologies[END_REF], has received considerable attention. They can be categorized into two separated directions depending on whether there is a leader or not. Many consensus schemes have been developed recently [START_REF] Ren | Consensus Seeking in Multi-agent Systems under Dynamically Changing Interaction Topologies[END_REF][START_REF] He | Consensus control for high-order multi-agent systems[END_REF][START_REF] Seyboth | Event-based broadcasting for multi-agent average consensus[END_REF][START_REF] Defoort | Self-triggered control for multi-agent systems with unknown nonlinear inherent dynamics[END_REF]. However, most of the existing consensus protocols have been derived when there is no leader or when the leader is static. Nevertheless, in many missions, a dynamic leader is required.

Many applications may require a dynamic leader, which could be virtual for its followers. Its behavior is independent of the other agents. The problem of leader-follower consensus is also referred to the cooperative or distributed consensus tracking [START_REF] Cao | Distributed coordinated tracking with reduced interaction via a variable structure approach[END_REF]. The coordination of a group of mobile autonomous agents following a leader has been firstly motivated in [START_REF] Jadbabaie | Coordination of groups of mobile autonomous agents using nearest neighbor rules[END_REF]. A multi-agent consensus problem with an active leader and a variable topology has been proposed in [START_REF] Hong | Tracking control for multi-agent consensus with an active leader and variable topology[END_REF]. In [START_REF] Ren | Consensus strategies for cooperative control of vehicle formations[END_REF], it has been highlighted the strong links between existing leader-follower formation control approaches and consensus-based strategies. The leader-following consensus problem for multi-agent systems with Lipschitz nonlinear dynamics is discussed in [START_REF] Xu | Leader-following consensus of non-linear multi-agent systems with jointly connected topology[END_REF]. Recently, a distributed output regulation approach has been proposed for the leader-follower consensus problem in [START_REF] Hong | Distributed output regulation of leader-follower multi-agent systems[END_REF].

In the study of consensus problem, the convergence rate has been an important topic. Indeed, this significant performance index is of high interest to study the effectiveness of a consensus protocol in the context of MAS. Most of the existing consensus algorithms focus on asymptotic convergence, where the settling time is infinite. However, many applications require a high speed convergence generally characterized by a finite-time control strategy [START_REF] Liu | Consensus problem in directed networks of multi-agents via nonlinear protocols[END_REF]. Moreover, finite-time control allows some advantageous properties such as good disturbance rejection and good robustness against uncertainties. A robust finite-time consensus tracking problem based on terminal sliding-mode control has been studied in [START_REF] Khoo | Robust finite-time consensus tracking algorithm for multirobot systems[END_REF], with input disturbances rejection. The finite-time consensus problem for multi-agent systems has been studied for single integrator [START_REF] Cao | Distributed coordinated tracking with reduced interaction via a variable structure approach[END_REF][START_REF] Wang | Finite-time consensus problems for networks of dynamic agents[END_REF], double integrator [START_REF] Li | Finite-time consensus algorithm for multi-agent systems with double-integrator dynamics[END_REF] and inherent non-linear dynamics [START_REF] Wen | Distributed finite-time consensus tracking for nonlinear multi-agent systems with a time-varying reference state[END_REF][START_REF] Cao | Finite-time consensus for multi-agent networks with unknown inherent nonlinear dynamics[END_REF].

Using finite time controller, an estimation of the settling time could be very useful when switching topology or networks of clusters are considered. It is worthy of noting that, for the above-mentioned works, the explicit expressions for the bound of the settling time depend on the initial states of agents. Therefore, the knowledge of these initial conditions usually prevent us from the estimation of the settling time using distributed architectures. A new approach, called fixed-time stability has been recently proposed to define algorithms which guarantee that the settling time is upper bounded regardless to the initial conditions [START_REF] Polyakov | Nonlinear feedback design for fixed-time stabilization of linear control systems[END_REF]. This concept is promising since one can design a controller such that some control performances are obtained in a given time and independently of initial conditions. In the case of leaderless strategies, the fixed-time average consensus problem has been solved for single integrator linear dynamics without disturbance in [START_REF] Parsegov | Fixed-time consensus algorithm for multi-agent systems with integrator dynamics[END_REF] and with bounded matched disturbances in [START_REF] Zuo | Distributed robust finite-time nonlinear consensus protocols for multi-agent systems[END_REF] even in the case of switching communication topologies [START_REF] Zuo | Fixed-time consensus for multi-agent systems under directed and switching interaction topology[END_REF]. To the best of our knowledge, although the finite-time leader-follower consensus problem has been well studied, the estimation of the convergence time off-line has not yet been proposed.

Motivated by the above works, in this paper, the fixed-time consensus tracking problem for MAS with inherent nonlinear dynamics is considered. The contribution of this paper is twofold. First, it is proposed a generalization of the finite-time leader-follower consensus protocol dealing with MAS with nonlinear inherent dynamics. Then, an explicit estimation of the settling time is provided regardless of the initial conditions. This paper is organized as follows. Sections 2 is devoted to the formulation of the leader-follower consensus problem. Section 3 presents the distributed consensus protocol, based on local information, to ensure the convergence of the tracking errors in finite time. Some conditions are derived to select the controller gains in order to obtain a prescribed convergence time regardless of the initial conditions. In Section 4, an illustrative example is discussed.

Notations:

We denote the transpose of a matrix M by M T and eig(M) its eigenvalues. λ min (M) (resp. λ max (M)) are the smallest and the largest eigenvalues of M. For a square symmetric matrix P ∈ R n×n , P ≻ 0 (resp. P ≺ 0) indicates that P is positive (resp. negative) definite.

Let

1 N = (1, 1, . . . , 1) T ∈ R n and diag(a 1 , a 2 . . . a n-1 , a n ) the diagonal matrix       a 1 0 . . . 0 0 . . . . . . . . . . . . . . . . . . 0 0 . . . 0 a n       ∈ R n×n . For a given vector x ∈ R n , |x| (resp. ||x||) denotes the 1-norm (resp. 2-norm) of x. For x = (x 1 , . . . , x n ) T ∈ R n and b ≥ 0, let us define ⌊x⌉ b = ( sign (x 1 ) |x 1 | b , . . . , sign (x n ) |x n | b ) T .

Formulation of the leader-follower consensus problem

Consider a multi-agent system consisting of a virtual leader and N followers. The dynamics of each follower and of the leader agent are given by ẋi = f (t,

x i ) + u i , i ∈ {1, • • • , N} ẋ0 = f (t, x 0 ) + u 0 (1)
where

x 0 ⊂ R m (resp. u 0 ∈ R m ) is the state (resp. control input) of the virtual leader, x i ∈ R m is the state of agent i and u i ∈ R m is the control input of agent i. Moreover, f : R + × D → R m is
an uncertain nonlinear dynamics of agent i, continuous in t, D ⊂ R m a domain containing the origin. Furthermore, there exist positive constants l 1 , l 2 and l 3 such that ∀x 1 ,

x 2 ∈ D, ∀t ≥ 0 ∥ f (t, x 1 ) -f (t, x 2 )∥ 2 ≤ l 1 + l 2 ∥x 1 -x 2 ∥ 2 + l 3 ∥x 1 -x 2 ∥ 4 (2)
Remark 1. The presented class of systems include Lipschitz (l 1 = l 3 = 0) and quasi-Lipschitz (l 3 = 0) as well as some essentially nonlinear (e.g polynomial) models (l 3 ̸ = 0). The polynomial term may appear, for example, in mechanical models with a viscous friction force proportional to square of velocity. Indeed, if x i is the velocity of some fast mobile vehicle, then √ l 3 is proportional to a coefficient of viscous friction.

It is worthy of noting that condition (2) is less restrictive than most of the existing works dealing on consensus for MAS with nonlinear inherent dynamics [START_REF] Wen | Distributed finite-time consensus tracking for nonlinear multi-agent systems with a time-varying reference state[END_REF]. Since f (t, x i ) is uncertain, it is not possible to cancel it with the control, namely (1) is not feedback equivalent to an m-dimensional integrator.

It is also assumed that the control u 0 of the leader is bounded by a known positive constant l, i.e.

∥u 0 ∥ ≤ l (3)
To solve the coordination problem and model exchanged information between agents, graph theory is briefly recalled hereafter. The communication topology among all followers is fixed and is represented by an undirected graph G which consists of a nonempty set of nodes V = {1, 2, • • • , N} and a set of edges E ⊂ V × V . Here, each node in V corresponds to an agent i, and each edge (i, j) ∈ E in the undirected graph corresponds to an information link between agent i and agent j. The topology of graph G is represented by the weighted adjacency matrix A = (a i j ) ∈ R N×N given by a i j > 0 if ( j, i) ∈ E and a i j = 0, otherwise. The Laplacian matrix of G is defined as L = (l i j ) ∈ R N×N with l ii = ∑ N j=1 a i j and l i j = -a i j for i ̸ = j. For an undirected graph, L is symmetric positive semi-definite. Graph G is connected if and only if its Laplacian matrix has a simple zero eigenvalue with associated eigenvector 1 N . The graph Ḡ is fixed and describes the communication topology of all followers and the virtual leader. The topology of Ḡ is described by the weighted matrix H = L + D ∈ R N×N where D = diag(a 10 , . . . , a N0 ) with a i0 > 0 if the leader state is available to follower i and with a i0 = 0 otherwise.

The objective of this paper is to design a distributed control protocol u i , based on available local information, such that each follower tracks the virtual leader in a prescribed time T max , i.e.

x i (t) = x 0 (t), ∀t ≥ T max , ∀i ∈ {1, • • • , N} (4)
Remark 2. For the sake of simplicity, in the following, it is assumed that m = 1. The analysis is valid for any arbitrary dimension m with the difference being that the expression should be written in terms of the Kronecker product.

Fixed-time consensus tracking protocol

In this section, a nonlinear finite time distributed control protocol will be designed such that each follower tracks the virtual leader in a prescribed time T max . Before that let us introduce the concept of fixed-time stability and a useful lemma.

Preliminaries on fixed-time stability

Let us consider the following system

{ ẋ(t) ∈ F(t, x(t)) x(0) = x 0 (5)
where x ∈ R n is the state, F : R + × R n → R n be an upper semicontinuous convex-valued mapping, such that the set F(t, x) is non-empty for any (t, x) ∈ R + × R n and F(t, 0) = 0 for t > 0. The solutions of (5) are understood in the Filippov sense [START_REF] Filippov | Differential equations with discontinuous right-hand side[END_REF].

Definition 1.

[29] The origin of system ( 5) is a globally finite time equilibrium if there is a function T : R n → R + such that for all x 0 ∈ R n , the solution x(t, x 0 ) of system ( 5) is defined and x(t, x 0 ) ∈ R n for t ∈ [0, T (x 0 )) and lim t→T (x 0 ) x(t, x 0 ) = 0. T (x 0 ) is called the settling time function.

Definition 2.

[23] The origin of system ( 5) is a globally fixed-time equilibrium if it is globally finite-time stable and the settling time function T (x 0 ) is bounded by some positive number T max > 0, i.e. T (x 0 ) ≤ T max for ∀x 0 ∈ R n .

The fixed-time stabilization at the origin can be demonstrated on the simplest scalar control system ẋ(t) = u(t), where x ∈ R is the state and u ∈ R is the control input. If the so-called negative relay feedback u =sign (x) is applied, then the closed-loop system is finite-time stable with the settling-time T (x 0 ) = |x 0 |. It is worthy of noting that the settling time depends on the initial conditions and is unbounded. The fixed-time control algorithm [START_REF] Polyakov | Nonlinear feedback design for fixed-time stabilization of linear control systems[END_REF] has the form u = -(|x| 2 + 1) sign (x). It guarantees finite convergence time independently of the initial conditions, namely, T (x 0 ) ≤ π 2 , where π = 3.1415926... is the well-know irregular number. More strong result is provided by the following lemma that refines the results of [START_REF] Polyakov | Nonlinear feedback design for fixed-time stabilization of linear control systems[END_REF] and [START_REF] Parsegov | Nonlinear Fixed-Time Control Protocol for Uniform Allocation of Agents on a Segment[END_REF]. Lemma 1. [START_REF] Parsegov | Fixed-time consensus algorithm for multi-agent systems with integrator dynamics[END_REF] Assume that there exists a continuously differentiable positive definite and radially unbounded function V : R n → R + such that sup t>0,y∈F(t,x)

∂V (x) ∂ x y ≤ -aV p (x) -bV q (x) for x ̸ = 0 where a, b > 0, p = 1 -1 µ , q = 1 + 1 µ , µ ≥ 1.
Then, the origin of the differential inclusion ( 5) is globally fixed-time stable with the settling time estimate

T (x 0 ) ≤ T max = π µ 2 √ ab .
In the next subsection, this lemma will be used to design a distributed nonlinear fixed-time control protocol and to analyze its robustness with respect to uncertainties and disturbances.

Fixed-time consensus protocol design

Based on Lemma 1, a distributed control protocol is derived to guarantee that each follower tracks the leader in a prescribed time T max regardless the initial condition in the following Theorem.

Theorem 1. Suppose that graph G is connected and at least one a i0 > 0. The control protocol

u i = α ⌊ N ∑ j=0 a i j (x j -x i ) ⌉ 2 + β N ∑ j=0 a i j (x j -x i ) + γ sign ( N ∑ j=0 a i j (x j -x i ) ) (6)
where the gains are defined as

α = √ l 3 (λ max (H)) 3/2 λ 7/2 min (H) + ε √ N (2λ min (H)) 3 2 β = √ l 2 λ min (H) γ = l + √ l 1 N + ε λ min (H) (7)
with ε > 0, achieves the convergence of the tracking errors xi = x ix 0 , ∀i ∈ {1, • • • , N} to zero in a finite time which is bounded by

T max = π ε (8)
Proof. Let us define the tracking errors as xi = x ix 0 , ∀i ∈ {1, • • • , N}. Equations ( 1), ( 6)

yield ẋi = α ⌊ N ∑ j=0 a i j (x j -x i ) ⌉ 2 + β N ∑ j=0 a i j (x j -x i ) + γ sign ( N ∑ j=0 a i j (x j -x i ) ) + f (t, x i ) -f (t, x 0 ) -u 0 ( 9
)
In a compact form, system (9) becomes

ẋ = -α ⌊H x⌉ 2 -β H x -γ sign (H x) + f -1 N u 0 with x = ( x1 , . . . , xN ) T f = ( f (t, x 1 ) -f (t, x 0 ), . . . , f (t, x N ) -f (t, x 0 )) T
Considering the candidate Lyapunov function

V = 1 2 xT H x
H ≻ 0 since graph G is connected and there is at least one a i0 positive [START_REF] Cao | Distributed coordinated tracking with reduced interaction via a variable structure approach[END_REF]. Its time derivative is given by

V = xT H ẋ = -α xT H ⌊H x⌉ 2 -β ∥H x∥ 2 2 -γ∥H x∥ 1 -xT H1 N u 0 + xT H f (10)
The later considerations uses the classical result about equivalence of the norms ∥ • ∥ q

∥y∥ q = ( N ∑ i=1 |y i | q ) 1 q , y = (y 1 , ..., y N ) T ∈ R N , q > 0
in a finite dimensional linear space. Namely, for p > r > 0 we always have

∥y∥ p ≤ ∥y∥ r ≤ N 1 r -1 p ∥y∥ p
The first term of ( 10) can be estimated as follows

-α xT H ⌊H x⌉ 2 = -α ∑ N i=1 ∑ N j=0 a i j (x j -x i ) 3 = -α∥H x∥ 3 3 ≤ -αN -1 2 ∥H x∥ 3 2 = -αN -1 2 ( xT H T H x) 3 2 ≤ -αN -1 2 (2λ min (H)) 3 2 V 3 2
The last term of (10) admits the following representation

xT H f ≤ ∥H x∥ 2 ∥ f ∥ 2 ≤ ∥H x∥ 2 ( l 1 N + l 2 ∥ x∥ 2 2 + l 3 ∥ x∥ 4 4 ) 1/2 ≤ ∥H x∥ 2 ( √ l 1 N + √ l 2 ∥ x∥ 2 + √ l 3 ∥ x∥ 2 4 ) ≤ √ l 1 N∥H x∥ 1 + √ l 2 λ min (H) ∥H x∥ 2 2 + √ l 3 N -1 2 (2λ max (H)) 3/2 λ 2 min (H) V 3/2 It follows that V ≤ ( -αN -1 2 (2λ min (H)) 3 2 + √ l 3 N -1 2 (2λ max (H)) 3/2 λ 2 min (H) ) V 3 2 - ( β - √ l 2 λ min (H) ) ∥H x∥ 2 2 -γ∥H x∥ 1 +(l + √ l 1 N)∥H x∥ 1 (11)
Let the gains be designed by [START_REF] Ren | Consensus Seeking in Multi-agent Systems under Dynamically Changing Interaction Topologies[END_REF]. Therefore, one gets

V ≤ -εV q -εV p with µ = 2 p = 1 -1 µ q = 1 + 1 µ
Hence, Lemma 1 guarantees that the origin of the closed-loop system (9) is globally fixed-time stable with the settling time bounded by T max = π ε .

Remark 3. It is worthy of noting that the settling time does not depend on the initial conditions. If a prescribed convergence time is required, one can easily tune the controller gains according to [START_REF] Ren | Consensus Seeking in Multi-agent Systems under Dynamically Changing Interaction Topologies[END_REF] to solve the leader-follower consensus problem. Such a requirement occurs when considering switching topologies. An extension of these results to the case of switching network is possible. Indeed, in this case, the sum of time intervals over which the graph is strongly connected must be larger that the settling time to guarantee that each follower tracks the virtual leader.

Numerical simulations

Let us consider the multi-agent system (1) with N = 6 followers and one virtual leader. The communication topology, given in Fig. 1 is undirected and fixed. It is connected and the corresponding matrix H is given by Hereafter, two scenarios are discussed. Scenario 1: We consider the case m = 1. The nonlinear dynamics, assumed uncertain, are f (t, x i ) = 0.1 sin (x i ), ∀i = {0, . . . , N}. The Lipschitz condition is verified. Indeed, in this case, l 1 = l 3 = 0 and l 2 = 0.1. The control input of the virtual leader is chosen as u 0 = 2 cos (0.1πt). It is bounded by l = 2. From Theorem 1, the control protocol [START_REF] Zhang | Distributed average filtering for sensor networks with sensor saturation[END_REF] achieves the convergence of the tracking errors xi = x ix 0 , ∀i ∈ {1, • • • , N} to zero in finite time. The control parameters are chosen as α = 5.38, β = 1.07, γ = 5.38. The estimated upper bounds of the settling time for the proposed distributed control scheme (6) is T max = 1.5s.

H =         2 -1 0 0 0 0 -1 3 -1 0 0 0 0 -1 4 -1 -1 0 0 0 -1 2 -1 0 0 0 -1 -1 3 -1 0 0 0 0 -1 2         2
The six followers start from the following initial conditions: x 1 (0) = -10, x 2 (0) = -5, x 3 (0) = -20, x 4 (0) = -15, x 5 (0) = 10 and x 6 (0) = 5. The virtual leader starts from x 0 (0) = 0. Fig. 2(a) depicts the trajectories of the virtual leader and the followers when the control protocol (6) is used. Fig. 2(b) shows that the consensus is achieved after 0.8s. It confirms the theoretical results obtained from Theorem 1.

Scenario 2: Now, we consider the case m = 2. The state of the virtual leader and the followers x i are written as The six followers start from the following initial conditions: x 1 (0) = (-2, -2) T , x 2 (0) = (-1, -3) T , x 3 (0) = (-4, 2) T , x 4 (0) = (-3, 4) T , x 5 (0) = (2, 2.4) T and x 6 (0) = (1, 3) T . The virtual leader starts from x 0 (0) = (0, 0) T . Fig. 3(a) depicts the trajectories of the virtual leader and the followers when the control protocol (6) is used. Fig. 3(b) shows that the consensus is achieved after 0.5s. It confirms the theoretical results obtained from Theorem 1.

x 0 = ( η x 0 , η y 0 ) T ∈ D and x i = ( η x i , η y

Conclusion

In this paper, the fixed-time consensus tracking problem for MAS with inherent nonlinear dynamics is considered. The contribution of this paper is twofold. First, it is proposed a generalization of the finite-time leader-follower consensus protocol dealing with MAS with nonlinear inherent dynamics. Then, an explicit estimation of the settling time is provided regardless of the initial conditions. Some conditions are derived to select the controller gains in order to obtain a prescribed convergence time regardless of the initial conditions.

Figure 1 :

 1 Figure 1: Communication topology.

i)

  T ∈ D where D = [-10, 10] × [-10, 10]. The nonlinear dynamics, assumed uncertain, are f (t, x i ) = 0.01 ( 0.01(η x i ) 2 , 0.01 sign ( (η y i ) )) T . This function does not satisfy the Lipschitz condition. Nevertheless, in this case, l 1 = 0.02 and l 3 = 0.1 on D. The control input of the virtual leader is chosen as u 0 = (0.1, 2 cos(π/2t)). It is bounded by l = 0.64. From Theorem 1, the control protocol (6) achieves the convergence of the tracking errors xi = x ix 0 , ∀i ∈ {1, • • • , N} to zero in finite time. The control parameters are chosen as α = 7.11, β = 0, γ = 4.36. The estimated upper bounds of the settling time for the proposed distributed control scheme (6) is T max = 1.5s.

Figure 2 :Figure 3 :

 23 Figure 2: Leader-follower consensus for multi-agent systems with unknown Lipschitz nonlinearities (a) Trajectories of each agent. (b) Tracking errors.

$ This work has been supported by International Campus on Safety and Intermodality in Transportation, the European Community, the Regional Delegation for research and Technology, the Nord-Pas-de-Calais Region, the Ministry of Higher Education and Research and the National Center for Scientific Research under the FUI EQUITAS and the ARCIR SUCRe projects.