Solenne Gaucher
email: solenne.gaucher@math.u-psud.fr

Alexandra Carpentier
email: carpentier@uni-potsdam.de

Christophe Giraud
email: christophe.giraud@universite-paris-saclay.fr

The price of unfairness in linear bandits with biased feedback

In this paper, we study the problem of fair sequential decision making with biased linear bandit feedback. At each round, a player selects an action described by a covariate and by a sensitive attribute. The perceived reward is a linear combination of the covariates of the chosen action, but the player only observes a biased evaluation of this reward, depending on the sensitive attribute. To characterize the difficulty of this problem, we design a phased elimination algorithm that corrects the unfair evaluations, and establish upper bounds on its regret. We show that the worst-case regret is smaller than O(κ 1/3 * log(T ) 1/3 T 2/3 ), where κ * is an explicit geometrical constant characterizing the difficulty of bias estimation. We prove lower bounds on the worst-case regret for some sets of actions showing that this rate is tight up to a possible sub-logarithmic factor. We also derive gap-dependent upper bounds on the regret, and matching lower bounds for some problem instance. Interestingly, these results reveal a transition between a regime where the problem is as difficult as its unbiased counterpart, and a regime where it can be much harder.

Introduction

Artificial intelligence is increasingly used in a wide range of decision making scenarii with higher and higher stakes, with application in online advertisement [START_REF] Perlich | Machine learning for targeted display advertising: transfer learning in action[END_REF], credit [START_REF] Byanjankar | Predicting credit risk in peer-to-peer lending: A neural network approach[END_REF], health care [START_REF] Fauw | Clinically applicable deep learning for diagnosis and referral in retinal disease[END_REF], education [START_REF] Papamitsiou | Learning analytics and educational data mining in practice: A systematic literature review of empirical evidence[END_REF] and job interviews [START_REF] Raghavan | Mitigating bias in algorithmic hiring: evaluating claims and practices[END_REF], in the hope of improving accuracy and efficiency. Recent works have shown that the decisions made by algorithms can be dangerously biased against certain categories of people, and have endeavored to mitigate this behavior [START_REF] Köchling | Discriminated by an algorithm: a systematic review of discrimination and fairness by algorithmic decision-making in the context of hr recruitment and hr development[END_REF][START_REF] Fuster | Predictably unequal? the effects of machine learning on credit markets[END_REF][START_REF] Chawla | Individual Fairness in Advertising Auctions Through Inverse Proportionality[END_REF][START_REF] Mehrabi | A survey on bias and fairness in machine learning[END_REF]. Studies have underlined that the main cause of algorithmic unfairness is the presence of bias in the training set [START_REF] Mehrabi | A survey on bias and fairness in machine learning[END_REF], which led to the development of methods aiming to guarantee the fairness of the algorithms. This paper, in lines with these works, addresses the problem of online decision making under biased feedback.

Linear bandits have become a very popular tool in online decision making problems, when side information on the actions is available in the form of covariates. In the present paper, we consider a variant of this problem, where the agent only has access to an unfair assessment of the action taken, that is systematically biased against a group of actions. For example, examiners may be prejudiced against people from a minority group, and give them lower grades; similarly, algorithms trained on 36th Conference on Neural Information Processing Systems (NeurIPS 2022). biased data may produce unfair assessments of the credit risk of individuals belonging to a minority group. Note that not correcting biased evaluation can have adverse effects for all parties: on the one hand, actions disadvantaged by the evaluation mechanism will be unfairly discriminated against; on the other hand, the agent may spend his budget on an unfairly advantaged action that is actually sub-optimal. The problem of sequential decision making under biased feedback can be formalized as follows.

Biased linear bandit problem A player is presented with a set of k distinct actions characterized by covariates x ∈ X ⊂ R d , and by known sensitive attributes z x ∈ {-1, 1} indicating the group of the action. For the sake of clarity, we consider here a two-group model (respectively privileged or discriminated against), and we defer to Appendix D discussions on how to extend this model and our algorithm to more than two groups. At each round t ≤ T , the player chooses the action x t and receives an unobserved reward x t γ * , where γ * ∈ R d is the regression parameter specifying the true value of the action. The regret of the player is given by

R T = E t≤T (x * -x t ) γ * , where x * ∈ argmax x∈X x γ * .
(

) 1
By contrast to the classical linear bandit, the player does not observe a noisy version of the unbiased reward x t γ * . Instead, she observes an unfair evaluation y t of the value of the action x t γ * , given by the following biased linear model:

y t = x t γ * + z xt ω * + ξ t where ξ t i.i.d
∼ N (0, 1) is a noise term. The evaluation are systematically biased against a certain group: this unequal treatment of the groups is captured by the bias parameter ω * ∈ R.

Preliminary discussion

The biased linear bandit is a variant of the linear bandit. By contrast, in the classical linear bandit model, the agent observes a noisy version of the reward. Obviously, applying directly an algorithm designed for linear bandit to biased linear bandits without correcting the evaluations would lead to a linear regret if the evaluation mechanism is prejudiced against the group of the best action in terms of reward, and if the best action in terms of feedback belongs to the advantaged group. To avoid this pitfall, one must estimate the bias in order to correct the evaluations. This implies a change in the exploration-exploitation trade-off, as exploration becomes more expensive. Indeed, in classical bandit problems, one can compare the rewards of two actions by repeatedly sampling them -or, to put it differently, one can find the best action by sampling only those actions that seem optimal. This does not hold in the biased linear bandit: if, at some point, the set of potentially optimal actions contains representatives from both groups, and does not span R d , one is forced to sample sub-optimal actions to estimate the bias and improve the estimation of the unbiased rewards. For this reason, classical algorithm for linear bandit that only sample actions considered as potentially optimal, such as OFUL [START_REF] Abbasi-Yadkori | Improved algorithms for linear stochastic bandits[END_REF] or Phase Elimination [START_REF] Lattimore | Bandit Algorithms[END_REF], can suffer linear regret. This underlines the necessity to ensure sufficient estimation of the bias parameter, even when it implies sampling sub-optimal actions.

Related work

Fairness in bandit problems has mostly been studied from the perspective of fair budget allocation between actions. This problem is motivated by the fact that classical bandit algorithms select suboptimal actions only a vanishing fraction of the time, which may be undesirable in many situations. To mitigate this problem and guarantee diversity in the actions selected, some papers [START_REF] Celis | An algorithmic framework to control bias in bandit-based personalization[END_REF][START_REF] Patil | Achieving fairness in the stochastic multi-armed bandit problem[END_REF][START_REF] Claure | Multi-armed bandits with fairness constraints for distributing resources to human teammates[END_REF][START_REF] Hadiji | Diversity-Preserving K-Armed Bandits[END_REF][START_REF] Wang | Fairness of exposure in stochastic bandits[END_REF] have proposed new algorithms ensuring fairness of the selection frequency of each action. The framework studied in this paper is different: we consider here that the mechanism for observing the rewards is unfair, and we aim at correcting it in order to maximize a (fair) true cumulative reward.

In this work, we consider that the agent knows the sensible attributes, and that she can treat actions differently according to their sensible attributes, in order to correct the prejudice caused by the unfair bias in the evaluation. This situation falls into the awareness framework, by contrast to the unawareness one, where using the sensitive attributes is prohibited. Whether or not it is preferable to treat different groups differently remains a controversial question. While using sensitive attributes at the time of prediction is sometimes forbidden by law, some recent works have highlighted critical issues related to unawareness. For example, empirical evidence [START_REF] Lipton | Does mitigating ml's impact disparity require treatment disparity[END_REF] have shown that classification algorithms based on disparate learning processes use non-sensitive features correlated with the sensitive attribute as a proxy for the later. These empirical findings have recently been supported by theoretical results established in [START_REF] Gaucher | Fair learning with wasserstein barycenters for non-decomposable performance measures[END_REF] in the case of demographic parity. Similarly, the authors of [START_REF] Chzhen | A unified approach to fair online learning via blackwell approachability[END_REF] study a problem of fair online learning, and show that some problems feasible in the awareness framework become infeasible in the unawareness one (such as no-regret learning under demographic parity constraints). These examples, amongmany others, advocate for the use of the sensitive attribute, as it allows for better fairness guarantees while preventing unfair discrimination based on (possibly irrelevant) non-sensitive features correlated with the sensitive attribute. Without taking a position in this debate, we underline that, in practice, this attribute (gender or minority status) is often known to the decision-maker, and that its use is in some cases allowed or even encouraged (e.g. for affirmative action).

By contrast to a line of work on statistical fairness, the aim of our model is not to correct for the possibly unequal distribution of features x and values x γ * across the different groups. Our approach is instead related to causal fairness [START_REF] Khademi | Fairness in algorithmic decision making: An excursion through the lens of causality[END_REF]: in the causal fairness framework, the dependencies between prediction, sensitive attributes and non-sensitive attributes are captured by a causal model. The goal is then to ensure that the sensitive attribute does not directly influence the prediction (in other words, that conditionally on selected resolving variables, the prediction is independent of the sensitive attribute).

Here, the resolving variables may depend on the sensitive attribute in a manner that is considered as non-discriminatory. For example, one group may have, on average, more physical strength than the other one, and this skill can be considered as fair when it comes to recruit a piano mover. The biased linear model studied in this paper is a simple example of causal model with linear structural model equations x = f (z, ξ ) and y = x γ * + zω * + ξ, where ξ and ξ are noise terms: the covariates x may depend on the sensitive attribute z, and the biased evaluation y depends on both. In our work, we treat x γ * as a fair evaluation of the value of action x, since it is independent of z conditionally on the resolving variable x.

The biased linear model has been studied in the batch setting in [START_REF] Chzhen | A minimax framework for quantifying risk-fairness trade-off in regression[END_REF], where the authors investigate the optimal trade-off between minimax risk and Demographic Parity. Detection of systematic bias, interpreted as a treatment effect, has been investigated in a batch setting in [START_REF] Khademi | Fairness in algorithmic decision making: An excursion through the lens of causality[END_REF]. In [START_REF] Barik | Fair sparse regression with clustering: An invex relaxation for a combinatorial problem[END_REF], the authors consider a similar model, with unobserved sensitive attribute z and known bias parameter ω * , under additional assumption that the sensitive attribute z is independent from the covariate x. By contrast, we show that bias estimation is one of the main difficulties of the biased bandit problem.

The linear bandit with biased feedback can be viewed as a stochastic partial monitoring game. With the terminology of partial monitoring, the biased problem considered in the present paper is globally observable but not locally observable: in this case, the optimal worst-case regret rate typically increases as Õ(T 2/3 ). This regret rate is for example achieved in the related problem of partial linear monitoring with linear feedback and linear reward using an Information Directed Sampling algorithm [START_REF] Kirschner | Information directed sampling for linear partial monitoring[END_REF]. However, the dependence of the regret on the geometry of the action set and on the dimension d remains in most cases an open question [START_REF] Lin | Combinatorial partial monitoring game with linear feedback and its applications[END_REF][START_REF] Chaudhuri | Phased exploration with greedy exploitation in stochastic combinatorial partial monitoring games[END_REF][START_REF] Kirschner | Information directed sampling for linear partial monitoring[END_REF]. In this paper, we characterize the geometry of the biased linear bandit problem, and we investigate dependence of the regret on the gaps.

Contribution and outline

In this paper, we introduce the linear bandit problem with biased feedback. We design a new algorithm based on optimal design for this problem. We derive an upper bound on the worst case regret of this algorithm of order κ 1/3 * log(T ) 1/3 T 2/3 for large T , where κ * is an explicit constant depending on the geometry of the action set. We provide matching lower bounds on some problem instances, showing that the constant κ * characterizes the difficulty of the action set. Note that this regret is higher than the classical rates of order Õ(dT 1/2 ) obtained for d-dimensional linear bandits: this increase corresponds to the price to pay for debiasing the unfair evaluations.

We also characterize the gap-depend regret, showing that it is of order ( d /∆min ∨ κ(∆) /∆ 2 = ) log(T ), where ∆ min is the minimum gap, ∆ = is the gap between the best actions of the two groups, and κ(∆) corresponds to the minimum regret to pay for estimating the bias with a given variance. This bound underlines the relative difficulties of the d-dimensional linear bandit and of the bias estimation. When d /∆min ≥ κ(∆) /∆ 2 = , i.e. when one group contains all near-optimal actions, the difficulty is dominated by that of the corresponding linear bandit problem. When both groups contain near-optimal actions, and d /∆min ≤ κ(∆) /∆ 2 = , the regret corresponds to the price of debiasing the rewards. The rest of the paper is organized as follows. In Section 2, we present the FAIR PHASED ELIMI-NATION algorithm: we first discuss parameter estimation in Section 2.1, before presenting a sketch of the algorithm in Section 2.2 (a detailed version of this algorithm is provided in Appendix B). Then, in Section 3, we establish an upper bound on its worst-case regret. In Section 4, we derive a gap-dependent upper bound on the regret of our algorithm. In Section 5, we establish lower bounds on some action sets for both the worst-case and the gap-dependent regret, showing that these rates are sharp respectively up to a sub-logarithmic factor and an absolute multiplicative constant. Additional discussions on the geometry of bias estimation are postponed to Appendix A.

Notations and additional assumptions

We assume that all covariates x ∈ X are distinct, which implies that the group z x of action x is well defined. We also assume that no group is empty, that the set { x zx : x ∈ X } spans R d+1 (which guarantees identifiability of the parameters), and that the rewards are bounded:

max x∈X |x γ * | ≤ 1.
When necessary, we underline the dependence of the regret on the parameter θ by denoting it R θ T . We denote by a x = x zx the vector describing an action and its group, by θ * = γ * ω * ∈ R d+1 the unknown parameter, and by A = {a x : x ∈ X } the set of actions and of corresponding sensitive attributes. We denote by ∆ = (∆ x ) x∈X the vector of gaps ∆ x = max x ∈X (x -x) γ * , and by C(X ) = γ ∈ R d : ∀x ∈ X , |x γ| ≤ 1 the set of admissible parameters. Note that for all x ∈ C(X ), ∆ x ≤ 2. For i ≤ d + 1, let e i be the i-th vector of the canonical basis of R d+1 , and for any matrix M , let M + be a generalized inverse of M . We denote by P X the set of probability measures on X , and M X = {µ : X → R + }. For any µ ∈ P X or µ ∈ M X , we denote V (µ) = x∈X µ(x)a x a x the covariance matrix corresponding to this allocation. For u ∈ R d+1 (resp. U ∈ R d+1 ), we denote by P X u (resp. M X u ) the measures µ in P X (resp. in M X ) such that u ∈ Range(V (µ)). For U ⊂ R d+1 , we denote by P X U (resp. M X U ) the measures µ such that µ ∈ P X u (resp. M X u ) for all u ∈ U.

Fair Phased Elimination algorithm

The Fair Phased Elimination algorithm belongs to the category of sequential elimination algorithms. Classical sequential elimination algorithms typically proceed by phases, indexed by l = 1, 2, . . .. At phase l, these algorithms consider a set of potentially optimal actions X l . The rewards of all actions x ∈ X l are then estimated with a given precision O( l ), typically chosen as l = 2 2-l , by sampling actions in X l . Actions sub-optimal by a gap larger than the precision level are then removed from the set X l+1 of potentially optimal actions for the phase l + 1.

As underlined previously, classical sequential elimination algorithms may suffer linear regret in the biased linear bandit problem if actions allowing to estimate the bias are discarded by the algorithm before the best group is identified (this happens for example if at a phase l, less that d + 1 action remains, with at least one action in each group). To mitigate this problem, we first estimate the biased evaluations of the potentially optimal actions, using ordinary least squares estimation. We then debias the estimations using an estimator for the bias relying on independent observations, which may be obtained by sampling sub-optimal actions. Before presenting the algorithm, let us discuss the estimation of the evaluations and of the bias parameter.

2.1 Optimal design for parameter estimation in the biased linear bandit G-optimal design for biased evaluation estimation As in the Phased Elimination algorithm [START_REF] Lattimore | Bandit Algorithms[END_REF], we rely on G-optimal design to estimate the biased evaluations a x θ * with small error uniformly over a set of actions X l . More precisely, for a given set of potentially optimal actions X l , we compute the G-optimal design solution to the problem

minimize π∈P X l X l max x∈X l a x (V (π)) + a x . (G-optimal design) (2)
This can be done using polynomial-time algorithms, relying for example on interior points method [START_REF] Vandenberghe | Determinant maximization with linear matrix inequality constraints[END_REF], or on mixed integer second-order cone programming [START_REF] Sagnol | Computing exact d-optimal designs by mixed integer second order cone programming[END_REF]. The celebrated General Equivalence theorem of Kiefer [START_REF] Kiefer | General Equivalence Theory for Optimum Designs (Approximate Theory)[END_REF] and Pukelsheim [START_REF] Pukelsheim | On linear regression designs which maximize information[END_REF] states that the value of Equation ( 2) is bounded by d + 1.

Let π * denote any design solution to the G-optimal design problem (2), and let θ denote the ordinary least square estimator obtained by sampling each action x ∈ X l exactly nπ * (x) times for a given n > 0. Then, for all x ∈ X l , the General Equivalence theorem implies that the variance of the estimate a x θ is smaller than (d+1) /n. Moreover, the G-optimal design π * can be chosen so that it is supported by at most (d+1)(d+2) /2 points, so the total number of samples is at most n + (d+1)(d+2) /2.

∆-optimal design for bias evaluation In this paragraph, we introduce the ∆-optimal design, which is discussed in greater depth in Appendix A. ∆-optimal design aims at estimating a parameter with a given accuracy and with minimal regret. Similar ideas have recently been used in [START_REF] Wagenmaker | Experimental design for regret minimization in linear bandits[END_REF] to solve classical linear bandit problems. To estimate the bias parameter ω * , we use the estimator ω = e d+1 θ, where θ is the ordinary least square estimator for the full parameter θ * . Now, if we sample each action x ∈ X exactly µ(x) time, the variance of ω is equal to e d+1 V (µ) + e d+1 . Given the vector of gaps ∆, the design µ minimizing the regret of this exploration phase, while ensuring that the variance of ω is smaller than 1, is solution of the problem

minimize µ∈M e d+1 X x µ(x)∆ x such that e d+1 V (µ) + e d+1 ≤ 1. (∆-optimal design) (3)
In the following, we denote µ ∆ a minimizer of (3), and κ(∆) = x∈X µ ∆ (x)∆ x . Lemma 9 in Appendix A explains how to compute the design µ ∆ in polynomial time by adapting tools from c-optimal design. This lemma also shows that the support of µ ∆ can be chosen to be of cardinality at most d + 1. Then, choosing each action exactly nµ ∆ (x) times for a given n > 0 allows us to estimate the bias with variance lower than n -1 and a regret no larger than nκ(∆) + 2(d + 1). Obviously, we do not know the gap vector ∆ beforehand, so we must estimate it as we go.

Outline of the Fair Phased Elimination algorithm

The Fair Phased Elimination algorithm, sketched in Algorithm 3, relies on the following key ideas. First, note that within a group, the order of the true rewards and of the biased evaluations are the same. Hence, within a group, we can use classical algorithms for linear bandits to choose the actions and estimate the biased evaluations with a controlled within-group regret: this is done using G-exploration and elimination. Second, to compare actions belonging to different groups, we independently estimate the bias parameter ω * , using ∆-exploration and elimination. Finally, we underline that bias estimation may require to sample very sub-optimal actions. Therefore, it can be overly costly to estimate the bias up to the precision level required to identify the best group. To prevent this, we use a stopping criterion.

G-exploration and elimination At each phase l = 1, 2, ..., we keep two sets of potentially optimal actions belonging to the groups +1 and -1, denoted respectively X (+1) l and X

(-1) l

. If we have not identified the group containing the best action, we run a G-EXP-ELIM routine 1 on each set X (z) l for z = 1 and z = -1. This routine samples actions according to a rounded G-optimal design on X (z) l , with a total number of observations chosen so that the biased evaluations of all actions in X (z) l are known with an error at most l . The set X (z) l+1 is obtained by removing from X (z) l actions whose estimated evaluations are sub-optimal by a gap larger than 3 l , compared to the empirical best action in the group. This allows to ensure that only actions sub-optimal by a gap O( l ) remain in X (z) l+1 , and to estimate the gap vector ∆ with a precision sufficient for ∆-optimal estimation.

If the group containing the best action has been identified, we discard the other group, and run a G-EXP-ELIM routine 1 on the set of potentially optimal actions in this group.

∆-exploration and elimination

If the group of the best action has not been found before phase l, we run the ∆-EXP-ELIM routine 2. More precisely, relying on a previous estimate ∆ l of the gap vector ∆, we compute the ∆ l -optimal design µ. We then estimate the bias using actions sampled according to a rounded version of this design, with a total number of observations chosen so that the Routine 1 G-EXP-ELIM (X , n, ) 1: Compute G-optimal design π solution of (2) on X , with | supp(π)| ≤ (d+1)(d+2) /2 2: Sample nπ(x) times each action a x for x ∈ X G-optimal parameter estimation 3: Compute the ordinary least square estimator θ 4: X ← x ∈ X : max x ∈X (x -x) θ ≤ 3

Suboptimal actions elimination 5: return θ and X error of bias estimation is smaller than l , and use it to debias the reward estimation. If the debiased evaluation of the best action of each group are separated by a gap larger than 4 l , we consider that the best group is the one containing the empirical best action in terms of biased evaluation, and we discard the other group.

If we cannot find the best group, we rely on estimates of the bias and of the biased evaluations obtained during the previous round to update the estimate of the gap vector ∆ l+1 .

Routine 2 ∆-EXP-ELIM (X , (X (z) , θ (z) ) z∈{-1,1} , ∆, n, ) 1: Compute ∆-optimal design μ, κ( ∆) solution of (3) on X , with | supp(μ)| ≤ d + 1 2: Sample nμ(x)
times each action a x for x ∈ X ∆-optimal bias estimation 3: Compute ω = e d+1 θ, where θ is the ordinary least square estimator 4:

for z ∈ {-1, 1} and x ∈ X (z) do m x ← a x θ (z) -z ω Debiased rewards estimation 5: if ∃z ∈ {-1, 1} such that max x∈X (z) m x ≥ max x∈X (-z) m x + 4 then Z ← {z} Group elimination 6: else ∆ x ← 2 ∧ (max x ∈X (-1) ∪X (1) m x -m x + 4
) for all x ∈ X (-1) ∪ X (1) 7: return Z and ∆

Stopping criterion

As underlined previously, the ∆-EXP-ELIM routine samples actions that can be very sub-optimal. As a consequence, when the gap between the best two actions of each group is small, finding the best group can be overly costly in terms of regret. To prevent this, if the best group has not been found at stage l fulfilling l ≤ κ( ∆ l ) log(T ) /T 1/3 , the bias estimation is stopped and the empirical best action in X

(1)

l+1 ∪ X (-1)
l+1 is sampled for the remaining time (see Algorithm 3)

Algorithm 3 FAIR PHASED ELIMINATION (sketched) 1: input: δ, T , X , k = |X |, l = 2 2-l for l ≥ 1 2: initialize: X (+1) 1 ← {x : z x = 1}, X (-1) 1 ← {x : z x = -1}, 3: Z 1 ← {-1, +1}, ∆ 1 ← (2, ..., 2), l ← 0 4: while the budget is not spent do l ← l + 1 5: for z ∈ Z l do 6: θ (z) , X (z) l+1 ← G-EXP-ELIM X (z) l , 2(d+1) 2 l log kl(l+1) δ , l 7: if Z l = {-1, +1} then 8: if l ≤ κ( ∆ l ) log(T )/T 1/
Z l+1 , ∆ l+1 ← ∆-EXP-ELIM X , X (z) l+1 , θ (z) l z∈{-1,1} , ∆ l , 2 2 l log l(l+1) δ , l
3 Upper bound on the worst-case regret of FAIR PHASED ELIMINATION

The regret of the FAIR PHASED ELIMINATION depends on the difficulty of estimating the bias parameter, captured by κ(∆). Lemma 7 in Appendix A. [START_REF] Chawla | Individual Fairness in Advertising Auctions Through Inverse Proportionality[END_REF] shows that for all parameter γ * ∈ X , κ(∆) is upper bounded by 2κ * , where κ * is the minimal variance of the bias estimator given by

κ * = min π∈P X e d+1
e d+1 (V (π)) + e d+1 .

The following theorem provides a bound on the worst case regret depending on κ * . Proofs are postponed to Appendix C.2. Theorem 1. For the choice δ = T -1 , there exists two numerical constants C, C > 0 such that the following bound on the regret of the FAIR PHASED ELIMINATION algorithm 4 holds

R T ≤ C κ 1/3 * T 2/3 log(T ) 1/3 + (d ∨ κ * ) log(T ) + d 2 + dκ -1/3 * T 1/3 log(kT ) log(T ) -1/3 ≤ C κ 1/3 * T 2/3 log(T ) 1/3 for T ≥ (d ∨ κ * ) 3/2 log(T ) ∨ d 3 √ κ * ∨ (d log(kT )) 3 (κ * log(T )) 2 .
In Section 5.1, we show that the upper bound obtained in Theorem 1 is sharp in some settings, up to the sub-logarithmic factor log(T ) 1/3 .

Theorem 1 shows that the worst-case regret of the Fair Phased Elimination algorithm asymptotically grows as Cκ 1/3 * T 2/3 log (T ) 1/3 . This worst-case regret rate is higher than the typical rate

Cd log(T )T 1/2 obtained under unbiased feedback on the rewards (see, e.g., [START_REF] Abbasi-Yadkori | Improved algorithms for linear stochastic bandits[END_REF]). This increase in the regret corresponds to the cost of learning from unfair evaluations. It is due to the fact that the algorithm may need to sample actions that are sub-optimal in order to estimate the bias parameter. Note that this rate O(T 2/3 ) is typical for globally observable bandit problems with partial linear monitoring, and can be obtained by applying results established in [START_REF] Kirschner | Information directed sampling for linear partial monitoring[END_REF] for in the partial linear monitoring setting to the biased linear bandit problem.

By contrast to previous results, Theorem 1 characterizes precisely the dependence of the worst-case regret on the geometry of the action set. The relevant constant κ * is the minimal variance for estimating the bias, which appears when considering the related c-optimal design problem. While the connection between G-optimal design and the linear bandit problem has already been exploited, it is to the best of our knowledge the first time that c-optimal design is related to partial monitoring.

The constant κ * corresponds to the minimum number of samples required for estimating the bias with a variance equal to 1 (up to rounding issues). Intuitively, if the actions are very correlated with their sensitive attributes, more samples will be needed to estimate the bias with the same precision. This situation corresponds to cases where κ * is large, and leads to a higher regret. Lemma 1, illustrated in Figure 2, relates κ * to the margin between the two groups of actions. Lemma 1. κ * is the largest constant κ ≥ 0 such that, there exists an hyperplane H containing zero and separating the two groups, and such that, the margin to H is at least √ κ-1 / √ κ+1 times the maximum distance of all points to the hyperplane (see Figure 2). When no such hyperplane exists, then κ * = 1. Interestingly, Lemma 1 underlines that under reasonable assumptions, the constant κ * may not depend on the ambient dimension d, and it can even be equal to 1. By contrast, while the Information Directed Sampling algorithm can be applied to the biased linear bandit problem, the regret bounds established in [START_REF] Kirschner | Information directed sampling for linear partial monitoring[END_REF] are of order α 1/3 d 1/2 T 2/3 log(kT ) 1/2 , where α is a measure of the complexity of the action set called the worst-case alignment constant. Lemma 6 in Appendix A shows that α is equivalent to the minimal variance of the bias estimator κ * . Hence, our bound improves over previous results by a factor d 1/2 log(T ) 1/6 (log(kT )/ log(T )) 1/2 . The gaps are not involved in the definition of the minimal variance of bias estimation κ * . The reader may have expected to get, instead of κ * , the minimax regret for estimating the bias

κ = max γ∈C(X ),x ∈X x∈X µ(x)(x -x) γ, where µ = argmin µ max x ∈X ,γ∈C(X ) x∈X µ(x)(x -x) γ, such that µ ∈ M X e d+1 and e d+1 V (µ) + e d+1 ≤ 1.
Next lemma shows that κ * and κ are in equivalent up to a factor 2. We refer the interested reader to Appendix A, where further discussions on the geometry of bias estimation are postponed, due to space constraints. Lemma 2. κ /2 ≤ κ * ≤ 2 κ.

4 Upper bound on the gap-depend regret of FAIR PHASED ELIMINATION

In this section, we provide an upper bound on the worst-case regret that depends on the gap between the two best actions, and on the gap between the best actions of the two groups. Compared to instance-dependent bounds, established in the linear bandit problem in [START_REF] Lattimore | The End of Optimism? An Asymptotic Analysis of Finite-Armed Linear Bandits[END_REF][START_REF] Kirschner | Asymptotically optimal informationdirected sampling[END_REF], gap-dependent bounds characterize the dependence of the regret on a small number of parameters. They are typically less sharp than instance-dependent bounds, but allow to better highlight the influence of the parameters on the difficulty of the problem. The bound established in the following theorem relates the difficulty of the biased linear bandit to that of bias estimation, and to that of the corresponding d-dimensional linear bandit. Proofs are postponed to Appendix C.2. Theorem 2. Assume that x * ∈ argmax x∈X x γ * is unique. Then, there exists two numerical constants C, C > 0 such that, for the choice δ = T -1 , the following bound on the regret of the FAIR PHASED ELIMINATION algorithm 4 holds

R T ≤ C d ∆ min ∨ κ ∆ ∨ ∆ = ∨ ε T ∆ 2 = log(T ) + d 2 + d ∆ min log (k) ≤ C d ∆ min ∨ κ ∆ ∨ ∆ = ∨ ε T ∆ 2 = log(T ) for T ≥ k ∨ e d∆min
where ∆ min = min x∈X \x * ∆ x , ∆ = = min x∈X :zx=-z x * ∆ x , and ε T = ( κ * log(T ) /T ) 1/3 .

The term d /∆min ∨ κ(∆∨∆ = ∨ε T ) /∆ 2 = highlights the two sources of difficulty of the problem. On the one hand, the term d /∆min is unavoidable: even if the algorithm knew beforehand the group containing the best action, it would still need to play a game of d-dimensional linear bandits in this group, and suffer, in the worst-case, the corresponding gap-dependent regret [START_REF] Abbasi-Yadkori | Improved algorithms for linear stochastic bandits[END_REF]. Note that lower bounds on gap-depend regret of classical linear bandits follow from considering a setting with one near-optimal action with gap ∆ min in each of the d dimensions. Then, any algorithm needs to explore each dimension up to ∆ -2 min log(T ) times in order to find the best action, but can do so by choosing the near-optimal actions, thus having a regret ∆ -1 min log(T ) in each direction. By contrast, the term κ(∆∨∆ = ∨ε T ) /∆ 2 = is characteristic of the biased linear bandit problem: it is due to the fact that the algorithm may need to sample very sub-optimal actions in order to find the group containing the best action. Indeed, to identify this group, one must estimate the bias with a precision ∆ = , i.e. sample sub-optimal actions with average regret κ(∆) approximately ∆ -2 = log(T ) times. When d /∆min ≤ κ(∆∨∆ = ∨ε T ) /∆ 2 = , the regret corresponds to the regret of this bias estimation phase. In other words, when both groups contain near-optimal actions, the difficulty of the problem is dominated by the price to pay for debiasing the unfair evaluations. Interestingly, when d /∆min > κ(∆∨∆ = ∨ε T ) /∆ 2 = , the difficulty of the linear bandit with systematic bias is dominated by that of the classical d-linear bandit. In this case, the algorithm is able to find the group containing the best action, and the problem reduces to a linear bandit in dimension d. Thus, the linear bandit with systematic bias is a non trivial example of a globally observable game that can be locally observable around the best action.

Finally, we underline that the magnitude of the bias does not appear in the regret: intuitively, no matter its magnitude, the algorithm always need to estimate it up to the same precision (of order ∆ = ) in order to find the best group and to be optimal in terms of gap-depend regret. This indicates that our algorithm is robust against important discriminations in the evaluation mechanism.

Lower bounds on the regret

In this section, we derive lower bounds on the worst-case regret and the gap-dependent regret that respectively match the upper bounds established in Theorems 1 and 2 up to sub-logarithmic factors or numerical constants.

Lower bound on the worst-case regret

Theorems 1 and 2 underline the dependence of the regret on the geometry of the action set. Before stating our result, we begin by introducing the notion of κ * -correlated action set. Definition 1 (κ * -correlated action set). For κ * ≥ 1, a set of actions A is κ * -correlated if A ∈ A κ * ,d , where

A κ * ,d =        A = {a 1 , ..., a k } ⊂ R d × {-1, +1} k : k ∈ N * , min π∈P A e d+1 e d+1 a∈A π(a)aa + e d+1 ≥ κ *       
is the set of actions sets such that the minimal variance of the bias estimator is larger than κ * .

In the following theorem, we establish a lower bound on the regret valid for all κ * ≥ 1 by designing κ * -correlated sets of actions A ∈ A κ * ,d , and obtaining lower bounds on the regret of any algorithm on these sets of actions. Theorem 3. Let κ * ≥ 1, d ≥ 2 and T ≥ 4 3 κ * . There exists an action set A ∈ A κ * ,d such that for any algorithm, there exists a bandit problem with parameter θ T ∈ R d+1 such that the regret of this algorithm on the problem characterized by

θ T satisfies R θ T T ≥ κ 1/3 * T 2/3 /8e.
Previous lower bounds on the regret of linear bandits with partial monitoring, established in [START_REF] Kirschner | Information directed sampling for linear partial monitoring[END_REF], state that the regret must be at least c A T 2/3 for some parameter θ T ∈ R d+1 , where c A > 0 is a constant depending (not explicitly) on A. By contrast, Theorem 3 provides an explicit characterization of the dependence of the regret rate on the geometry of the problem, which matches the upper bound of Theorem 1 up to a sub-logarithmic factor. Note that the assumption d ≥ 2 is necessary here: if d = 1, there are at most two potentially optimal actions (namely, max{x : x ∈ X } and min{x : x ∈ X }).

Then, the problem becomes locally observable, and regret of order O(T 1/2 ) can be achieved [START_REF] Kirschner | Information directed sampling for linear partial monitoring[END_REF].

Lower bound on the gap-dependent regret

We now present a lower bound on the gap-dependent regret. More precisely, for given values of ∆ min and ∆ = , we establish a lower bound on the worst case regret among parameters θ verifying ∆ min ≤ min x∈X \x * ∆ x , and ∆ = ≤ min x∈X :zx=-z x * ∆ x . Before stating formally the result, let us define the corresponding parameter set. For an action set A ∈ A κ * ,d , and for (∆ min , ∆ = ) ∈ (0, 1) 2 such that ∆ min ≤ ∆ = , we denote

Θ A ∆min,∆ = =          θ = γ ω : γ ∈ C(X ), ∃ ! x * z x * ∈ argmax ( x zx )∈A {x γ}, ∀ x z x ∈ A such that x = x * , (x * -x ) γ ≥ ∆ min , ∀ x z x ∈ A such that z x = z x * , (x * -x ) γ ≥ ∆ =         
the set of parameters with minimum gap ∆ min , and minimum between-group-gap ∆ = .

The upper bounds established in Theorem 2 underline the dependence of the gap-dependent regret on the minimal regret κ(∆) for estimating the bias. Before stating our results, we define a class of problems Θ A ∆min,∆ = ,κ such that κ(∆) ≤ κ. For a parameter γ ∈ C(X ), let us denote ∆(γ) x = max x ∈X (x -x) γ, and ∆(γ) = (∆(γ) x ) x∈X . Moreover, for a given set A, let us denote

Θ A ∆min,∆ = ,κ = Θ A ∆min,∆ = ∩ θ = γ ω : γ ∈ C(X ), κ(∆(γ)) ≤ κ .
Theorem 4. For all κ ≥ 2 and all d ≥ 4, there exists a set of actions A ∈ R d+1 such that for all

(∆ min , ∆ = ) ∈ (0, 1 /8) 2 with ∆ min ≤ ∆ = , lim inf T →∞ sup θ∈Θ A ∆ min ,∆ = ,κ R θ T log (T ) ≥ d 10∆ min ∨ κ + 2 8∆ 2 = . (4)
Theorem 4 shows that for some action sets A, the gap-depend regret of the FAIR PHASED ELIM-INATION algorithm is asymptotically optimal up to a numerical constant. Note that the assumption d ≥ 4 is necessary in our proof to design an action set A such that Equation ( 4) holds for all ∆ min , ∆ = ∈ (0, 1 /8). On the other hand, as discussed in Appendix C.6, for d ≥ 2, for all ∆ min , ∆ = ∈ (0, 1/8), we can show that there exists action sets A and θ ∈ Θ A ∆min,∆ = such that the lower bound in Equation ( 4) still holds, by considering separately the cases d /∆min > κ /∆ 2 = and d /∆min ≤ κ /∆ 2 = .

Conclusion

In this paper, we addressed the problem of online decision making under biased bandit feedback. We designed a new algorithm based on ∆and G-optimal design, and obtained worst-case and gap-dependent upper bounds on its regret. We obtained lower bounds on the regret for some problem instances showing that these rates are tight up to sub-logarithmic factors in some settings. These rates highlight two behaviors: on the one hand, the worst case rate O(κ

1/3 * log(T ) 1/3 T 2/3
) highlights the cost induced by the biased feedback, and the need to select sub-optimal actions in order to debias it. On the other hand, the gap-dependent bound shows that for some instance, the problem can be locally observable around the best action: then, the difficulty of the problem is dominated by the difficulty of the corresponding linear bandit problem, and is no more difficult than this problem. When this is not the case, the regret scales as κ(∆)∆ -2

= log(T ), where ∆ = is the gap between the best actions of the two groups, and κ(∆) is the minimum regret for estimating the bias with a given precision. In Appendix D, we discuss the extension of the biased linear model and of the Fair Phased Elimination algorithm to multiple groups with different biases. This work paves the way for studying other bandit models with unfair feedback, considering for example continuous, multi-dimensional sensitive attributes.

Broader impact

In this work, we propose a model for sequential decision making under biased feedback. Our goal is primarily to provide a good strategy for sequential learning in an unfair environment, and to characterize the difficulty of this problem by bounding the regret. On the one hand, our results reveal that maximizing the fair rewards instead of unfair evaluations may be more difficult in terms of regret, which may discourage practitioners from correcting unfair feedbacks. On the other hand, we believe that as fairness is an important long-term key objective, rather than discouraging the practitioner, it will inform them to better plan the adaptation of their methods toward this aim.

the FG DFG, by the DFG CRC 1294 'Data Assimilation', Project A03, by the Forschungsgruppe FOR 5381 "Mathematical Statistics in the Information Age -Statistical Efficiency and Computational Tractability", Project TP 02, by the Agence Nationale de la Recherche (ANR) and the DFG on the French-German PRCI ANR ASCAI CA 1488/4-1 "Aktive und Batch-Segmentierung, Clustering und Seriation: Grundlagen der KI" and by the UFADFH through the French-German Doktorandenkolleg CDFA 01-18 and by the SFI Sachsen-Anhalt for the project RE-BCI. Christophe Giraud received partial support by grant ANR-19-CHIA-0021-01 ("BiSCottE", Agence Nationale de la Recherche) and by the ANR and the DFG on the French-German PRCI ANR-21-CE23-0035 (ASCAI).

Appendix

The Appendix is organized as follows. In Section A, we further discuss the geometry of bias estimation, and provide additional results on the constants κ * and κ(∆). Then, we provide in Section B a detailed version of the FAIR PHASED ELIMINATION algorithm 3. In Section C, we prove the main results of this paper. Finally, in Section D, we discuss the extension of the biaised linear bandits to more than 2 groups.

A On the geometry of bias estimation

We begin in Section A.1 by highlighting the relationship of the constant κ * with the problem of e d+1optimal design. Then, in Section A.2, we show that the geometrical constant κ * can be expressed in terms of separation of the two groups. In Section A.3 and Section A.4, we relate κ * to classical geometrical measures of the difficulty of a set of actions such as the condition.ing number and the worst-case alignment constant of [START_REF] Kirschner | Information directed sampling for linear partial monitoring[END_REF]. In Section A.5, we show that κ * is equivalent to the variance of the optimal design for estimation the bias against the worst parameter θ * . In Section A.6, we provide further results on κ(∆), the ∆-optimal regret for estimation the bias with variance 1 when the gap vector is ∆. Finally, in Section A.7, we propose guidance for computing the G-optimal and ∆-optimal designs.

A.1 Bias estimation as a e d+1 -optimal design problem

Recall that κ * is the minimal variance of the bias estimator related to the problem of e d+1 -optimal design. e d+1 -optimal design Optimal design theory addresses the following problem: a scientist must design a set of n experiments {x 1 , ..., x n } ∈ X n so as to estimate at best a parameter of interest, where each experiment x ∈ X corresponds to a point a x ∈ R d+1 . The aim of the scientist is to choose a design, i.e. a function µ : X → N indicating the budget µ(x) to be allocated to each experiment x ∈ X . Each experiment x is then repeated exactly µ(x) times, and the corresponding observations y x,1 , ..., y x,µ(x) are collected for each x ∈ X . The law of the observations corresponding to experiment x at point a x is given by

y x,i = a x θ * + ξ x,i ,
where ξ x,i ∼ N (0, 1) are independent noise terms, and θ * ∈ R d+1 is an unknown parameter. The aim of the scientist is to choose the design µ so as to best estimate (some features of) the parameter θ * , under a constraint on the total number of experiments x∈X µ(x) ≤ n for some n ∈ N.

Different criteria can be used to characterize the optimality of a design µ. For example, one may need to estimate the full parameter θ * , in order to predict the outcomes of the experiments x ∈ X with a small uniform error: this leads to the G-optimal design problem (2). Alternatively, for c a vector in R d+1 , one may aim at finding the best design µ ∈ N X for estimating the scalar product c θ * under a budget constraint x∈X µ(x) ≤ n, where N X = {µ : X → N}. This problem is known as c-optimal design. Unbiased linear estimation of c θ * is possible only when c belongs to the image of V (µ), and in this case the best linear unbiased estimator of the scalar product c θ * is given by c θ, where θ is the least-square estimator defined as

θ = V (µ) + x∈X a x   i≤µ(x) y x,i   for V (µ) = x∈X µ(x)a x a x . (5)
The variance of the estimator c θ is then equal to c V (µ) + c.

Exact c-optimal design aims at choosing the allocation µ ∈ N X minimizing the variance of c θ for a given budget x µ(x) ≤ n, under the constraint that c ∈ Range(V (µ)). Let us define the normalized design π : x ∈ X → µ(x)/n, and let us underline that π defines a probability on X . The variance of c θ is then equal to n -1 c V (π) + c. In the limit n → +∞, the problem is equivalent to the problem of approximate c-optimal design (sometimes simply referred to as c-optimal design), that aims at finding a probability measure π ∈ P X c := {π ∈ P X : c ∈ Range(V (π))} solution to the following problem

min π∈P X c c V (π) + c .
(c-optimal design) Note that when {a x : x ∈ X } spans R d+1 , for any c ∈ R d+1 , there exists a design π such that c ∈ Range(V (π)), and hence the c-optimal design problem admits a solution.

Computation of the e d+1 -optimal design Finding an exact optimal allocation µ ∈ N X under the constraint that x∈X µ(x) ≤ n is unfortunately NP-complete. However, finding an approximate optimal design π ∈ P X c can be done in polynomial time [START_REF] Černý | Two complexity results on c-optimality in experimental design[END_REF]. Several algorithms, including multiplicative algorithms [START_REF] Fellman | On the Allocation of Linear Observations[END_REF] and a simplex method of linear programming [START_REF] Harman | Computing c-optimal experimental designs using the simplex method of linear programming[END_REF], have been proposed to iteratively approximate the optimal design. More recently, [START_REF] Pronzato | Removing inessential points in c-and A-optimal design[END_REF] suggested using screening tests to remove inessential points to accelerate optimization algorithms.

Classical results from e d+1 -optimal design show that there exists a c-optimal design supported by at most d + 1 points (see, e.g., [START_REF] Pázman | Foundations of Optimum Experimental Design[END_REF][START_REF] Harman | Computing c-optimal experimental designs using the simplex method of linear programming[END_REF] for a proof of this result). The following Lemma indicates how to obtain an exact design by rounding an approximate design supported by at most d + 1 points. Lemma 3. For any π ∈ M X e d+1 and any m > 0, the estimator e d+1 θ µ computed from the design µ : x → mπ(x) is an unbiased estimator of e d+1 θ and it has a variance at most m -1 e d+1 V (π) + e d+1 .

Obviously, similar results also hold for G-optimal design. Lemma 4. Let π be a solution of the G-optimal design problem (2). Then, for any m > 0 and any x ∈ X , the estimator a x θ µ computed from the design µ : x → mπ(x) is an unbiased estimator of the evaluation a x θ, and it has a variance

a x V (µ) + a x ≤ m -1 (d + 1).
A.2 Interpretation of κ * in terms of separation of the groups Next theorem, due to Elfving, characterizes solutions to the c-optimal design problem. Theorem 5 ([10]). Let S = convex hull {+a x , -a x : x ∈ X } be the Elfving's set of {a x : x ∈ X } ⊂ R d+1 , and let ∂S denote the boundary of S. A design π ∈ P X c is c-optimal for c ∈ R d+1 if and only if there exists ζ ∈ {-1, +1} X and t > 0 such that

tc = x∈X π(x)ζ x a x ∈ ∂S. Moreover, t -2 = c (V (π))
+ c is value of the c-optimal design problem.

Elfving's characterization of the e d+1 -optimal design allows us to derive the following equivalent characterization of κ * .

Lemma 5. κ * = max

u∈R d 1 max x∈X (x u + z x ) 2 .
Lemma 1 follows from the characterization in Lemma 5. When κ * > 1, the vector ũ defined as The set of actions A spans R d+1 , however it is easy to see that only x 1 and x d+1 can be used to estimate the bias. On the one hand, when κ = 1, x d+1 zx d+1 = 0 -1 , so the bias can be evaluated just by sampling x d+1 . In the other hand, in the limit where κ * → ∞, the problems becomes more difficult as x d+1 zx d+1 tends to -x1 zx 1 . In the limit κ * = ∞, it is impossible to distinguish between the contribution of γ e 1 and ω in the evaluations of actions 1 and d + 1: the problem becomes not identifiable. We represent this setting for an intermediate value of κ * in Figure 2. We also represent the separating hyperplane, margin m and distance M of Lemma 1.

ũ = argmax u∈R d 1 max x∈X (x u+zx

A.3 Comparison to the conditioning number

By contrast to classical complexity measures such as conditioning numbers that give equal weight to all observations, optimal design gives flexibility to choose d + 1 best actions to estimate the bias, and therefore allows for sharper bounds.

Indeed, by definition of κ

* , κ * ≤ e d+1 V (π u ) + e d+1 ,
where π u is the uniform measure giving the same weight 1/k to all actions. Now, V (π u ) is the classical covariance matrix associated with the design points a x ∈ A, so the condition number CN of this design is given by

CN = λ max (V (π u )) λ min (V (π u )) .
We see that e d+1 V (π u ) + e d+1 ≤ λ min (V (π u )) -1 . When the actions a x are bounded (for example a x ≤ M ), this implies that κ * ≤ CN/M .

We provide an example showing that κ * can be much smaller than the conditioning number. Consider the following example in dimension d = 2 with k ≥ 4 actions, where x 1 = (1, 0) and x 2 = (-1, 0) belong to group 1, and x 3 , ..., x k are identical, equal to (0, 1), and in group -1. Then, Lemma 1 shows that the minimal variance for estimating the bias is indeed 1, and that the optimal design puts equal mass on x 1 and x 2 . On the other hand, straightforward computations show that the conditioning number of the covariance matrix is

1+(k-2) -1 + √ 1+(k-2) -2 1+(k-2) -1 - √ 1+(k-2) -2
. Thus, on this example, CN/κ * is of order k.

A.4 Comparison to the worst-case alignment constant

Lemma 5 also allows us to compare the bound in Theorem 1 with previous results on linear bandit with partial monitoring, expressed in terms of the worst-case alignment constant.

Previous work on linear bandit with partial linear monitoring measures the difficulty of the bandit game using the worst-case alignment constant α, defined as

α = max u∈R d max x,x ∈X ((x -x ) u) 2 max x∈X (z x x u + 1) 2 .
The following Lemma shows that this constant is essentially equivalent to the minimal variance of the bias estimator κ * . Lemma 6. κ * 3 ≤ α ≤ 16κ * . On the one hand, Lemma 6 shows that κ * and α are essentially equivalent. In particular, Theorem 3 implies that the large T regret is of order α 1/3 log(T ) 1/3 T 2/3 . This improves over previous known rates, obtained in [START_REF] Kirschner | Information directed sampling for linear partial monitoring[END_REF], by a factor d 1/2 log(T ) 1/6 (log(kT )/ log(T )) 1/2 .

On the other hand, as underlined, the constant κ * appears when considering the well-studied problem of c-optimal design. Therefore, classical results and algorithms for optimal design can be used to characterize and compute this constant.

A.5 Optimal bias estimation against the worst parameter

The constant κ * also appears naturally when considering the related problem of optimal bias estimation against the worst parameter.

Regret of e d+1 -optimal design Recall that κ * denotes the minimal variance of the bias estimator, i.e. the value of the solution of the e d+1 -optimal design problem

κ * = min π∈P X e d+1 e d+1 (V (π)) + e d+1 ,
The e d+1 -optimal design can be equivalently defined as the solution of the problem

minimize x∈X µ(x) such that µ ∈ M X e d+1 and e d+1 V (µ) + e d+1 ≤ κ * . (6)
The characterization given in Equation [START_REF] Chawla | Individual Fairness in Advertising Auctions Through Inverse Proportionality[END_REF] underlines that the e d+1 -optimal design provides (up to discretization issues) the minimal number of samples required for estimating ω * with a variance κ * . Let us denote by µ * the optimal design for estimating ω * with a variance 1, defined as

µ * = argmin µ x∈X
µ(x) such that µ ∈ M X e d+1 and e d+1 V (µ) + e d+1 ≤ 1.

Note that from the definition of κ * , we have x µ * (x) = κ * .

A first (naive) approach to obtain an estimate of the bias parameter ω * with precision level > 0 would consist in sampling actions according to -2 µ * , rounded according to the procedure defined in Lemma 3. Let us denote by ∆ x the gap ∆ x = max x ∈X (x -x) γ * between the (non-observed) reward of the best action and the reward of the action x. The regret corresponding to this estimation phase would then be

-2 x∈X µ * (x)∆ x ,
which can be as large as κ * -2 max x ∆ x . Interestingly, we show that the regret corresponding to the e d+1 -optimal design is equivalent (up to a small multiplicative constant) to the minimax regret.

Optimal worst-case estimation The minimax regret corresponds to the regret of the best sampling scheme against the worst admissible parameter γ. Note that, for a given design µ, this worst-case regret is given by max

x ∈X ,γ∈C(X ) x µ(x)(x -x) γ,
where we recall that C(X ) = γ ∈ R d : ∀x ∈ X , |x γ| ≤ 1 is the set of admissible parameters. To achieve the lowest regret against the worst parameter, we must use the minimax optimal design µ solution to the problem

µ = argmin µ max x ∈X ,γ∈C(X ) x∈X µ(x)(x -x) γ such that µ ∈ M X e d+1 and e d+1 V (µ) + e d+1 ≤ 1.
Lemma 2 underlines that the regret corresponding to the e d+1 -optimal design is no larger than twice the minimax regret.

A.6 Additionnal results the ∆-optimal design

Recall that for a vector of gaps ∆ = (∆ x ) x∈X , µ ∆ denotes the ∆-optimal design, defined as the solution of the following problem

µ ∆ = argmin µ x∈X µ(x)∆ x such that µ ∈ M X e d+1 and e d+1 V (µ) + e d+1 ≤ 1. (∆-optimal design)
If we knew the gaps ∆ x , we could sample the actions according to the ∆-optimal design µ ∆ , and pay the regret -2 κ(∆) (up to rounding error) for estimating ω * with an error smaller than , where

κ(∆) = x∈X µ ∆ (x)∆ x . Lemma 7. If γ * ∈ C(X ), then κ(∆) ≤ 2κ *
Proof. Be definition of C(X ), for all γ * ∈ C(X), all x, x ∈ X , we have

(x -x ) γ * ≤ |x γ * | + |x γ * | ≤ 2.
Then,

κ(∆) ≤ 2 min µ x∈X µ(x) such that µ ∈ M X e d+1 and e d+1 V (µ) + e d+1 ≤ 1.
Let µ * be the solution of the e d+1 -optimal design problem minimize µ e d+1 V (µ) + e d+1 such that µ ∈ P X e d+1 .

By definition of κ * , we see that e d+1 V (µ * ) + e d+1 = κ * . This implies that the measure κ * × µ * verifies the constraints e d+1 V (κ * × µ * ) + e d+1 ≤ 1 and κ * µ * ∈ M X e d+1 . Thus,

κ(∆) ≤ 2 x∈X κ * µ * (x) = 2κ * .
On the regret κ(∆) The function κ verifies the following properties. Lemma 8. For two vectors of gaps ∆, ∆ , denote by ∆ ∧ ∆ (respectively ∆ ∨ ∆ ) the vector of gaps given by

(∆ ∧ ∆ ) x = ∆ x ∧ ∆ x (respectively (∆ ∨ ∆ ) x = ∆ x ∨ ∆ x ) for all x ∈ X . Moreover, denote ∆ ≤ ∆ if ∆ x ≤ ∆ x for all x ∈ X .
Then, the following properties hold :

i) for all c > 0, κ(c∆) = cκ(∆); ii) if ∆ ≤ ∆ , then κ(∆) ≤ κ(∆ ); iii) κ(∆ ∨ ∆ ) ≥ κ(∆) ∨ κ(∆ ); iv) the function → κ(∆ ∨ ) is continuous at 0.

A.7 Computation of G-and ∆-optimal design

Computing the optimal design is a convex problem, for which many algorithms have been proposed. The first method to compute G-optimal design is due to [START_REF] Fedorov | Theory of optimal experiments[END_REF] and [START_REF] Wynn | The Sequential Generation of D-Optimum Experimental Designs[END_REF]; later, [START_REF] Titterington | Algorithms for computing D-optimal design on finite design spaces[END_REF] proposed a multiplicative weight update algorithm. More recently, [START_REF] Vandenberghe | Determinant maximization with linear matrix inequality constraints[END_REF] suggested to use a Semi-Definite Programming approach to solve the G-optimal design problem. Linear programming was used in [START_REF] Harman | Computing c-optimal experimental designs using the simplex method of linear programming[END_REF] to compute c-optimal design, while [START_REF] Qi | A semidefinite programming study of the elfving theorem[END_REF] studied a SDP formulation of this problem. Reducing the G-optimal problem to a Mixed-Integer, Second Order Cone Programming, [START_REF] Sagnol | Computing exact d-optimal designs by mixed integer second order cone programming[END_REF] proposed a new algorithm based on interior point methods. We refer the interested reader to the review in [START_REF] Sagnol | Plans d'expériences optimaux et application à l'estimation des matrices de trafic dans les grands réseaux : programmation conique du second ordre et sous-modularité[END_REF].

In practice, one can rely on the R package OptimalDesign or the Python Package PICOS [START_REF] Sagnol | Picos: A python interface to conic optimization solvers[END_REF] to compute G-and c-optimal design.

The following Lemma allows us to reduce the problem of finding a ∆-optimal design to that of a c-optimal design for some rescaled features.

Lemma 9. For any vector ∆ ∈ (0, +∞) X , let π ∆ be the e d+1 -optimal design relative to the set

A ∆ = ∆ -1/2 x x zx :
x ∈ X and let κ ∆ = e d+1 V (π ∆ ) + e d+1 be the e d+1 -optimal variance relative to A ∆ . Then, the ∆-optimal design µ ∆ is given by µ

∆ (x) = κ ∆ π ∆ (x)∆ -1
x for all x ∈ X . In addition, the support of µ ∆ can be chosen to be of cardinnality at most d + 1.

Thus, Lemma 9 shows that to compute the ∆-optimal design, one should follow these steps :

1. Compute the rescaled features A ∆ ; 2. Compute the e d+1 -optimal design π ∆ on A ∆ , as well as the variance term

κ ∆ = e d+1 x∈X π ∆ (x) ∆x a x a x + e d+1 ;
3. Compute the ∆-optimal design µ ∆ given by µ ∆ (x) = κ ∆ π ∆ (x)∆ -1

x for all x ∈ X .

B Detailed Fair Phased Elimination algorithm

We present the notations used in Algorithm 4. The phases are indexed by l ∈ N * . The sets X (z) l for z ∈ {-1, +1} corresponds to actions in group z that are considered as potentially optimal in phase l. The variable z * l encodes the group determined as optimal: it is 0 as long as this group has not been determined. The subscript (z) refer to the group z when z ∈ {-1, +1}, and otherwise to the estimation of the bias ω * : for example, the probability π (z) l for z ∈ {-1, +1} and l > 1 corresponds to the approximate G-optimal design on X (z) l . Then, for z ∈ {-1, +1}, allocations µ (z) (resp. µ (0) ) correspond to allocation of samples in the exploration phase Exp l ) is a Boolean variable indicating whether the exploration at phase l for group z (resp. for the bias parameter) has been performed. It is used in the proofs to ensure that the corresponding estimators are well defined.

Algorithm 4 Fair Phased Elimination (detailed version)

1: Input: δ, T , k = |X | 2: Initialize: Recovery ← ∅, t ← 0, l ← 1 z * 1 ← 0, 3: X (+1) 1 ← {x : z x = 1}, X (-1) 1 ← {x : z x = -1}, ∆ 1 x ← 2 for x ∈ X 4: while t < T do 5: Initialize: l ← 2 2-l , z * l+1 ← z * l , ∆ l+1 ← ∆ l , Explore (z) l ← False for z ∈ {-1, 0, +1} 6:
for z ∈ {-1, +1} such that z = -z * l do G-optimal Exploration and Elimination 7:

π (z) l ← argmin π max x∈X (z) l a x V (π) + a x : π ∈ P X (z) l X (z) l , | supp(π)| ≤ (d+1)(d+2) 2 8: µ (z) l (x) ← 2(d+1)π (z) l (x) 2 l log kl(l+1) δ for all x ∈ X (z) l 9: n (z) l ← x∈X (z) l µ (z) l (x), Exp (z) l ← t + 1, ..., T ∧ (t + n (z) l ) 10: if t + n (z) l ≤ T then 11: Explore (z) l ← True, choose each action x ∈ X (z) l exactly µ (z) l (x) times 12: V (z) l ← t∈Exp (z) l a xt a xt , θ (z) l ← V (z) l + t∈Exp (z) l y t a xt 13: X (z) l+1 ← x ∈ X (z) l : max x ∈X (z) l (a x -a x ) θ (z) l ≤ 3 l 14:
else for t ∈ Exp

t ← t + n (z) l 16: if z * l = 0 then 17:
compute the ∆ l -optimal design µ l and the corresponding regret κ( ∆ l )

18:

if l ≤ κ( ∆ l ) log(T )/T 1/
µ (0) l (x) ← 2μ l (x)
V (0) l ← t∈Exp (0) l a xt a xt , ω (0) l ← e d+1 V (0) l + t∈Exp (0) l y t a xt 27: for x ∈ X (-1) l+1 ∪ X (1)
l+1 do 28:

m l,x ← a x θ (zx) l -z x ω (0) l 29: ∆ l+1 x ← max x ∈X (-1) l+1 ∪X (1) l+1 m l,x -m l,x + 4 l ∧ 2 30: for z ∈ {-1, +1} do 31: if max x∈X (z) l+1 m l,x -2 l ≥ max x∈X (-z) l+1 m l,x + 2 l then z * l+1 ← z 32:
else sample empirical best action in X

(-1) l+1 ∪ X (1)
l+1 until the end of the budget, t ← T 33:

t ← t + n (0) l 34: l ← l + 1

C Proofs

Before proving the main results our this paper, we begin by outlining in Section D.1 the main ideas used to obtain upper and lower bounds on the regret. Then, Theorem 1 is proved in Section C. The proof of Theorem 1 can be found in Appendix C.2. We outline here the keys ingredients to this proofs. We begin by introducing some notations.

Notations We denote by L T the largest integer l such that l ≥ κ 1/3 * T -1/3 log(T ) 1/3 . We denote by L (0) the last phase where ∆ l -optimal Exploration and Elimination happens. We denote by Exp the time indices where ∆-exploration is performed at phase l. We also denote by Recovery the time indices subsequent to the stopping criterion, this set being empty when the stopping criterion is not activated. We define a "good" event F such that the errors a x θ * -θ l and |ω * -ω (0) l | are smaller than l for all l such that these quantities are defined, and all x ∈ X (-1) l and X (+1) l . In the following, we use c, c to denote positive absolute constants, which may vary from line to line. With these notations, we decompose the regret as follows :

R T ≤ 2T P (F) + E |F l≤L T z∈{-1,+1} t∈Exp (z) l (x * -x t ) γ * R G T + E |F l≤L (0) t∈Exp (0) l (x * -x t ) γ * R ∆ T +E |F l≥L T +1 z∈{-1,+1} t∈Exp (z) l (x * -x t ) γ * + t∈Recovery (x * -x t ) γ * R Rec T .
Bound on T P (F). Using arguments based on concentration of Gaussian variables, we show that

P (F) ≤ 2T -1 .

Bound on R G

T . We show that on F, only actions with gaps smaller than c l remain in the sets X (-1) l and X (+1) l

. The length of each G-optimal Exploration and Elimination phase is of the order d log(klT )/2 l , so the regret of each phase is of the order d log(klT )/ l . Summing over the different phases, we find that

R G T ≤ cd log(kL T T )/ L T . (7)
Using the definition of L T , we find that R G T ≤ cd log(kL T T )κ

-1/3 * log(T ) -1/3 T 1/3 .
Bound on R ∆ T . We show that on F, ∆ l ≥ ∆ for all l ≥ 1. Then, our choice of design µ (0) l ensures that for l ≤ L (0) , on F,

t∈Exp (0) l (x * -x t ) γ * ≤ c log(l(l + 1)T )
for some constant c > 0. Summing over the different phases, we find that

R ∆ T ≤ cκ( ∆ L (0) ) log(L (0) T )/ 2 L (0) . (8)
Now, the algorithm does not enter the Recovery phase before phase L (0) + 1, so we must have -2

L (0) ≤ T 2/3 log(T ) -2/3 κ( ∆ L (0) ) -2/3 . This implies that R ∆ T ≤ cκ( ∆ L (0) ) 1/3 log(T ) 1/3 T 2/3 . Since κ( ∆ l ) ≤ 2κ * , we find that R ∆ T ≤ c κ 1/3 * log(T ) 1/3 T 2/3 .
Bound on R Rec T . On the one hand, the actions selected during the Phases Exp (-1) l

and Exp (+1) l for l ≥ L T + 1 are sub-optimal by a gap at most c L T on the event F. On the other hand, if the algorithm enters the Recovery phase at a phase l, then

l ≤ κ( ∆ L (0) ) 1/3 T -1/3 log(T ) 1/3 ≤ κ 1/3 * T -1/3 log(T ) 1/3 , so we must have l = L (0) + 1 ≥ L T + 1.
Therefore, all actions selected during the Recovery phase are sub-optimal by a gap at most c L T . Then, R Rec T can be bounded as

R Rec T ≤ c L T T . This implies in particular that R Rec T ≤ c κ 1/3 * log(T ) 1/3 T 2/3 .
When T ≥ T κ * ,d,k for some T κ,d,k large enough, we find that R T ≤ c κ

1/3 * log(T ) 1/3 T 2/3 .

C.1.2 Outline of the Proof of Theorem 2

The proof of Theorem 2 is close to that of Theorem 1, and we adopt the same notations as in the proof sketch above.

Notations We denote by L (0) the last phase where ∆ l -optimal Exploration and Elimination happens. We denote F some "good" event such that the errors |a x (θ * -θ the time indices where ∆-exploration is performed at phase l. We also denote by Recovery the time indices subsequent to the stopping criterion, this set being empty when the stopping criterion is not activated. In the following, we use c, c to denote positive absolute constants, which may vary from line to line.

Fact 1 Let l ∆min be the largest integer such that l∆ min ≥ C∆ min for some well-chosen absolute constant C > 0. We show that on the good event F, no more than l ∆min G-optimal Exploration and Elimination phases are needed to find the best action. For all phases l ≥ l ∆min , the algorithm always chooses x * , and suffers no regret.

Fact 2 We show that on the good event F, for each phase l, ∆ l ≤ c (∆ ∨ l ) for some constant c. Lemma 8 then implies that for all l ≤ L (0) and all τ > 0, κ(

∆ l ) ≤ cκ(∆ ∨ l ) ≤ c(1 + l τ -1 )κ(∆ ∨ τ ).
Fact 3 Let l ∆ = be the largest integer such that l∆ = ≥ C∆ = for some well-chosen absolute constant C > 0. On the good event F, if the algorithm enters the ∆ l -optimal Exploration and Elimination phase at round l ≥ l ∆ = , we show that the algorithm finds the best group at this phase. This implies that L (0) ≤ l ∆ = .

Fact 4 We denote by L T the largest integer l such that l ≥ (κ * log(T )/T )

1/3 . Since κ * ≥ κ( ∆ l )
for all l ≥ 1, we see that if the algorithm enters the Recovery phase, we must have L T ≤ L (0) , and

L (0) ≤ L T ≈ ε T .
Using Fact 1, we find that the regret can be written as

R T ≤ 2T P (F) + E |F l≤l∆ min z∈{-1,+1} t∈Exp (z) l (x * -x t ) γ * R G T +E |F l≤L (0) t∈Exp (0) l (x * -x t ) γ * R ∆ T + E |F t∈Recovery (x * -x t ) γ * R Rec T .
Bound on R G T . We rely on arguments similar to those used in Equation ( 7) to show that

R G T ≤ c(d + 1) log(kl ∆min T ) -1 l∆ min . Since l∆ min ≥ C∆ min , this implies that R G T ≤ c(d + 1) log(kl ∆min T ) ∆ min ≤ c d log(T ) ∆ min if T ≥ k. Bound on R ∆ T + R Rec T . We begin by bounding R ∆ T . Recall that Equation (8) states that R ∆ T ≤ cκ( ∆ L (0) ) log(l L (0) T ) -2
L (0) . Using Fact 2, we find that for any τ > 0,

R ∆ T ≤ cκ(∆ ∨ τ ) log(l L (0) T ) -2 L (0) + -1 L (0) τ -1 . (9)
Let us now consider two cases, corresponding to Recovery= ∅ and Recovery = ∅.

Case 1: Recovery= ∅. On the one hand, our case assumption implies that

R Rec T = 0.
On the other hand, by Fact 3, we know that on F, L (0) ≤ l ∆ = . Then, using the definition of l ∆ = and Equation ( 9) with τ = ∆ = , we find that

R ∆ T ≤ cκ(∆ ∨ ∆ = ) log(L (0) T )∆ -2 = .
Case 2: Recovery = ∅. All actions selected during the Recovery phase belong to X (-1)

L (0) +1 ∪ X (+1)
L (0) +1 , so on F these actions are sub-optimal by a gap at most c L (0) +1 , so R Rec T ≤ cT L (0) +1 . Now, since the algorithm enters the Recovery phase, we must have L (0) +1 ≤ (κ(∆ L (0) +1 ) log(T )/T ) 1/3 , which implies that

R Rec T ≤ cκ( ∆ L (0) +1 ) log(T ) 2 L (0) +1
.

Using Fact 2 with τ = L (0) together with Equation ( 9), we find that

R ∆ T + R Rec T ≤ cκ(∆ ∨ L (0) ) log(T ) 2 L (0)
.

On the one hand, Fact 3 guarantees that, since we entered the Recovery phase before finding the best group, we must have L (0) ≥ l∆ = . On the other hand, Fact 4 ensures that L (0) ≤ ε T . Thus,

R Rec T ≤ cκ(∆ ∨ ε T ) log(T ) ∆ 2 = .
Conclusion Combining these results, we find that

R T ≤ c d ∆ min ∨ κ(∆ ∨ ∆ = ) ∆ 2 = ∨ κ(∆ ∨ ε T ) ∆ 2 = log(T ) when T ≥ k. Using Lemma 8, we get that κ(∆ ∨ ∆ = ) ∨ κ(∆ ∨ ε T ) ≤ κ(∆ ∨ ∆ = ∨ ε T )
, which concludes the proof of the results.

C.1.3 Outline of the Proof of Theorem 4

We outline the main ingredients used to prove Theorem 4. Theorem 3 relies on similar arguments.

To prove the lower bounds, we need to construct two close problem instances with optimal actions belonging to different groups -to obtain the part of the lower bound involving ∆ = -and in addition we must also create confusing instances with different optimal actions belonging to a same group -to obtain the part of the lower bound involving ∆ min . This is done by considering the following set of actions and of problems.

Lemma
     e d+1    ( x z )∈A π(x) x z x x z x    + e d+1      = κ * .
We also define the following parameters:

γ (1) = 1 + ∆ = -∆ min 2   1≤j≤ d/2 e j   + 1 -∆ = -∆ min 2   d/2 +1≤j≤d e j   +∆ min e 1 + ∆ min e d/2 +1 γ (i) = γ (1) + 2∆ min e i + 2∆ min e d/2 +i ∀i ∈ {2, ..., d/2 } γ ( d/2 +1) = 1 -∆ = -∆ min 2   1≤j≤ d/2 e j   + 1 + ∆ = -∆ min 2   d/2 +1≤j≤d e j  
+∆ min e 1 + ∆ min e d/2 +1 .

The bias parameters are given by ω (i) = -

∆ = 2 ∀i ∈ {1, ..., d/2 }, and ω ( d/2 +1) = ∆ = 2 . The parameters θ (i) = γ (i) ω (i)
characterize d/2 + 1 problems, with noise distribution i.i.d. N (0, 1).

We write Problem i for the problem characterized by θ (i) . Note that by construction and for any i ∈ {1, ..., d/2 + 1}, we have that θ (i) ∈ Θ A ∆min,∆ = . The following facts hold:

• For any i ∈ {1, ..., d/2 + 1}, action x i is the unique optimal action in Problem i. Since 1/2 ≥ ∆ = ≥ ∆ min , sampling any other (sub-optimal) action leads to an instantaneous regret of at least ∆ min . Moreover, choosing an action in the group -z i leads to an instantaneous regret of at least ∆ = .

• In Problem i for any i ∈ {1, ..., d/2 + 1}, action d + 1 is very sub-optimal and sampling it leads to an instantaneous regret higher than (1

-2/( √ κ * + 1))(1 -∆ = + ∆ min ) + (1 + ∆ = + ∆ min )/2 ≥ 1/2, since κ * ≥ 1 and 1/2 ≥ ∆ = ≥ ∆ min .
This action is the worst action in all problems.

• Many actions are such that their distributions are the same across problems. More specifically:

-For any i ∈ {2, ..., d/2 }, between Problem 1 and Problem i, the only actions that provide different evaluations when sampled are action i and action d/2 + i, and the mean difference between the evaluations in both cases is 2∆ min . -Between Problem 1 and Problem d/2 + 1, the only actions that provide different evaluations when sampled is action d+1, and the mean gap in this case is 2 √ κ * +1 ∆ = := α∆ = .

The proof is then divided in two parts, one part for proving the part of the bound depending on ∆ min and one part for proving the part of the bound depending on ∆ = .

Part of the bound depending on ∆ min . This part of the proof is obtained using classical arguments for K-armed bandit problems. For i ∈ {2, ..., d/2 , all actions but x i and x d/2 +i have the same feedback under Problem 1 and Problem i. On the other hand, the average feedback for actions x i and x d/2 +i differs by 2∆ min , so either action needs to be selected approximately log(T ) ∆ 2 min times in order to identify the problem at hand with high enough probability. In Problem 1, the simple regret for choosing x i or x d/2 +i is larger than ∆ min , so the total regret obtained when doing this is at least of the order log(T ) ∆min . Summing over the different actions i leads to a lower bound of the order d log(T ) ∆min .

Part of the bound depending on ∆ = . To obtain the second part of the lower bound, we note that all actions but x d+1 have the same feedback under Problem 1 and Problem d/2 + 1. The average feedback for actions x d+1 differs by α∆ = under these parameters, so action x d+1 needs to be selected approximately log(T )

α 2 ∆ 2 = log(T )κ * ∆ 2 =
times to identify the problem at hand with high enough probability. Since selecting action x d+1 leads to an simple regret larger than 1/2 under Problem 1, this implies that the regret must be at least of the order κ * log(T )

∆ 2 = .
Bounds on κ(∆) Finally, the following lemma allows to express κ(∆) as a function of κ * . Lemma 11. For any i ∈ {1, ..., d/2 + 1}, the gap vector ∆ verifies

κ(∆) = (1 + √ κ * ) 2 ∆ d+1 4 where ∆ d+1 = max i (x i -x d+1 ) γ (i) .
On the one hand, since κ * ≥ 1, we see that κ * ≤ (1 + √ κ * ) 2 ≤ 4κ * . On the other hand,

1/2 ≤ ∆ d+1 ≤ 2, so κ(∆) ∈ κ * 8 , 2κ * .

C.2 Proof of Theorem 1

We begin by defining for z ∈ {-1, 0, +1}

L (z) = max l ≥ 1 : Explore (z) l = True
the largest integer l such that Explore (z) l = True. Recall that κ * is the e d+1 -optimal variance. By definition of the algorithm, for all l ≤ L (0) + 1, ∆ l ≤ 2, so κ( ∆ l ) ≤ 2κ * . Now, let us also define

L T = max l ≥ 1 : l > 2κ * log(T ) T 1/3 .
Then, if Recovery = ∅, we must have L (0) ≥ L T . Moreover, we see that since L T = 2 2-L T , we have L T ≤ 2 + log 2 (T /(2κ * log(T ))) 3 ≤ 3 log 2 (T ) when T > 1.

We define a "bad" event F, such that, on F, our estimators γ (z) l

and ω

(z) l are close to the true parameters γ * and ω * for all rounds l. More precisely, let

F = l≥1 F l , (10)
where for l ≥ 1

F l =    ∃z ∈ {-1, 1} such that Explore (z) l = True, and x ∈ X (z) l such that γ (z) l -γ * ω (z) l -ω * x z x ≥ l    Explore (0) l = True and ω (0) l -ω * ≥ l .
Then, the regret decomposes as

R T ≤ t≤T E |F (x * -x t ) γ * + 2T P [F] . (11)
The following lemma relies on concentration of Gaussian variables to bound the probability of the event F.

Lemma 12. P (F) ≤ 2δ.

Now, the first term of ( 11) can be decomposed as

t≤T (x * -x t ) γ * ≤ z∈{-1,0,+1} L (z) +1 l=1 t∈Exp (z) l (x * -x t ) γ * + t∈Recovery (x * -x t ) γ * ,
where we use as convention that the sum over an empty set is null. Note that for z ∈ {-1, +1}, during the phase Exp L (0) +1 , but does not have enough budget to complete the last ∆ l -optimal Exploration and Elimination Phase, it samples the remaining actions in the set X (-1)

L (0) +2 ∪ X (+1) L (0) +2 .
Hence, the first term of ( 11) can be upper-bounded by

t≤T (x * -x t ) γ * ≤ z∈{-1,+1} L T l=1    x∈X (z) l µ (z) l (x)    max x∈X (z) l (x * -x) γ * (12)
+ z∈{-1,+1} L (z) +1 l=L T +1 t∈Exp (z) l (x * -x t ) γ * + t∈Recovery (x * -x t ) γ * + L (0) l=1 x∈X µ (0) l (x)∆ x + 1 Explore (0) L (0) +1 = False t∈Exp (0) L (0) +1 max x∈X ( -1)
L (0) +2 ∪X (+1) L (0) +2 (x * -x) γ * .
We begin by bounding the sum of the regret corresponding to the Recovery phase and to the phases Exp (z)

L for z ∈ {-1, +1} and l > L T on the event F.

Bound on

z∈{-1,+1}

L (z) +1 l=L T +1 t∈Exp (z) l (x * -x t ) γ * + t∈Recovery (x * -x t ) γ * .
Lemma 13. Let x * ∈ argmax x∈X x γ * be an optimal action. Then, on the event F defined in Equation [START_REF] Elfving | Optimum Allocation in Linear Regression Theory[END_REF], for l ≥ 1 such that Explore

(z x * ) l = True, X (z x * ) l+1 ⊂ x ∈ X (z x * ) 1 : (x * -x) γ * < 10 l+1 . (13)
Moreover, for l ≥ 1 such that Explore

(-z x * ) l = True, X (-z x * ) l+1 ⊂ x ∈ X (-z x * ) 1 : (x * -x) γ * < 42 l+1 .
Recall that if Recovery = ∅, L (0) ≥ L T . Then, all actions sampled during the Recovery phase belong to X

(-1) l+1 ∪ X (+1)
l+1 for some l ≥ L T . Lemma 13 shows that, on F, for l ≥ L T , the actions in X (z) l+1

are sub-optimal by at most 42 L T +1 . Then, we get that on the event F,

z∈{-1,+1} L (z) +1 l=L T +1 t∈Exp (z) l (x * -x t ) γ * + t∈Recovery (x * -x t ) γ * ≤ T × 42 L T +1 ≤ 53κ 1/3 * T 2/3 log(T ) 1/3 . ( 14
)
Bound on

L (0) l=1 x∈X µ (0) l (x)∆ x + 1 Explore (0) L (0) +1 = False t∈Exp (0) L (0) +1 max x∈X (-1) L (0) +2 ∪X (+1) L (0) +2 (x * - x) γ * .
We begin by bounding 1 Explore (0)

L (0) +1 = False t∈Exp (0) L (0) +1 max x∈X (-1) L (0) +2 ∪X (+1) L (0) +2 (x * -x) γ * . Recall that n (0) L (0) +1 = x∈X µ (0)
L (0) +1 (x) is the budget that would be necessary to complete the ∆ l -optimal Exploration and Elimination phase at phase L (0) + 1. On the one hand, Lemma 13 implies that on the event F,

1 Explore (0) L (0) +1 = False t∈Exp (0) L (0) +1 max x∈X (-1) L (0) +2 ∪X (+1) L (0) +2 (x * -x) γ * ≤ 42n (0) L (0) +1 L (0) +2 ≤ 21n (0) L (0) +1 L (0) +1 .
On the other hand, for all l ≤ L (0) + 1, the definition of ∆ l implies that ∆ l

x ≥ l for all x ∈ X . Therefore, 21n (0)

L (0) +1 L (0) +1 ≤ 21n (0) L (0) +1 min x ∆ L (0) +1
x . This implies that on F,

1 Explore (0) L (0) +1 = False t∈Exp (0) L (0) +1 max x∈X (-1) L (0) +2 ∪X (+1) L (0) +2 (x * -x) γ * ≤ 21 x∈X µ (0) L (0) +1 (x) ∆ L (0) +1 x . (15)
Next, to bound the remaining terms of Equation ( 12), we bound the regret x∈X µ (0) l (x)∆ x of exploration phase Exp (0) l using the following lemma. Lemma 14. For all l > 0, and z ∈ {-1, +1}, we have

x∈X (z) l µ (z) l (x) ≤ 2(d + 1) 2 l log kl(l + 1) δ + (d + 1)(d + 2) 2 .
and on F, we have

x∈X µ (0) l (x)∆ x ≤ x∈X µ (0) l (x) ∆ l x ≤ 2κ( ∆ l ) 2 l log l(l + 1) δ + 2(d + 1).
Then, Equation [START_REF] Gaucher | Fair learning with wasserstein barycenters for non-decomposable performance measures[END_REF] and Lemma 14 imply that on F

L (0) l=1 x∈X µ (0) l (x)∆ x + 1 Explore (0) L (0) +1 = False t∈Exp (0) L (0) +1 max x∈X (-1) L (0) +2 ∪X (+1) L (0) +2 (x * -x) γ * ≤ 21
L (0) +1 l=1 x∈X µ (0) l (x) ∆ l x ≤ 42
L (0) +1 l=1 κ( ∆ l ) 2 l log l(l + 1) δ + 42(d + 1)(L (0) + 1) (16)
We rely on the following Lemma to bound κ( ∆ l ).

Lemma 15. On F, we have for any l ≥ 1 and any τ > 0

κ( ∆ l ) ≤ 513 1 + l τ κ(∆ ∨ τ ). and κ( ∆ l ) ≥ κ(∆ ∨ l ).
Lemma 14 and Lemma 15 with τ = L (0) imply that on F,

L (0) +1 l=1 κ( ∆ l ) 2 l log l(l + 1) δ ≤ 513κ(∆ ∨ L (0) ) log (L (0) + 1)(L (0) + 2) δ   L (0) +1 l=1 1 2 l + L (0) +1 l=1 1 l L (0)   ≤ 513κ(∆ ∨ L (0) ) log 6L (0) δ 16 2 L (0) + 4 2 L (0) ≤ 10260 log 6L (0) δ κ( ∆ L (0) ) 2 L (0) (17)
where the last line follows from the second claim of Lemma 15. Now, by definition of L (0) ,

L (0) ≥ κ( ∆ L (0) ) log(T )/T 1/3
. Then, Equation ( 17) implies that

L (0) +1 l=1 κ( ∆ l ) 2 l log l(l + 1) δ ≤ 10260 log 6L (0) δ κ( ∆ L (0) ) 1/3 log(T ) -2/3 T 2/3 . ( 18
)
Moreover, we observe that during each phase l, but the last one, we sample at least

max z∈{-1,1} x∈X (z) l τ (z) l,x ≥ 2(d + 1) δ 2 l log(kl(l + 1)/δ)
actions during the G-optimal explorations, so the number of phases L (0) is never larger than T = 1 ∨ log 4 (T ). Using this remark, together with Equations ( 16) and ( 18), we find that on F

L (0) l=1 x∈X µ (0) l (x) ∆ l x + 1 Explore (0) L (0) +1 = False t∈Exp (0) L (0) +1 max x∈X (-1) L (0) +2 ∪X (+1) L (0) +2 (x * -x) γ * ≤ 2 19 log 6L (0) δ κ( ∆ L (0) )T 2/3 log(T ) -2/3 + 42 T . ( 19
)
Bound on

z∈{-1,+1} L T l=1   x∈X (z) l µ (z) l (x)   max x∈X (z) l (x * -x) γ * .
We bound the remaining term in Equation ( 12) using the first claim in Lemma 14 and Lemma 13. On F,

z∈{-1,+1} L T l=1    x∈X (z) l µ (z) l (x)    max x∈X (z) l (x * -x) γ * ≤ 2 L T l=1 2(d + 1) 2 l log kl(l + 1) δ + (d + 1)(d + 2) 2 42 l ≤ 336(d + 1) L T log kL T (1 + L T ) δ + 168(d + 1)(d + 2) ≤ 267(d + 1)κ -1/3 * T 1/3 log(T ) -1/3 log kL T (1 + L T ) δ +168(d + 1)(d + 2). ( 20
)
Combing Equations ( 11), ( 12), ( 14), [START_REF] Kiefer | General Equivalence Theory for Optimum Designs (Approximate Theory)[END_REF], and (20), and using

δ = T -1 , κ( ∆ L (0) ) ≤ κ * and L T ≤ 4T / log(2), we get for all T ≥ 1 R T ≤ C κ 1/3 * T 2/3 log(T ) 1/3 + (d ∨ κ * ) log(T ) + d 2 + dκ -1/3 * T 1/3 log(kT ) log(T ) -1/3
for some absolute constant C > 0. Finally, for

T ≥ (d ∨ κ * ) 3/2 log(T ) ∨ d 3 √ κ * ∨ (d log(kT )) 3 (κ * log(T )) 2 , we get R T ≤ C κ 1/3 * T 2/3 log(T ) 1/3 .

C.3 Proof of Theorem 2

The beginning of the proof of Theorem 2 follows the same lines as the proof of Theorem 1. We begin by decomposing the regret as

R T ≤ t≤T E |F (x * -x t ) γ * + 2T P [F] . ( 21
)
where F is defined in Equation ( 10). On the one hand, Lemma 12 implies T P [F] ≤ 2δT . Then, Equation ( 21) implies

R T ≤ 4δT + E |F    z∈{-1,+1} L (z) +1 l≥1 t∈Exp (z) l (x * -x t ) γ *    + E |F   t∈Recovery (x * -x t ) γ *   ( 22
)
+E |F   L (0) l=1 x∈X µ (0) l (x)∆ x   + E |F     1 Explore (0) L (0) +1 = False t∈Exp (0) L (0) +1 max x∈X (-1) L (0) +2 ∪X (+1) L (0) +2 (x * -x) γ *    
where F is defined in Equation ( 10), and where we used the convention that the sum over an empty set is null.

Bound on 1 Explore (0)

L (0) +1 = False t∈Exp (0) L (0) +1 max x∈X L (z) +1 (x * -x) γ * .
Similarly to the proof of Theorem 1, we use Lemma 13 and Lemma 15 to show that on F 1 Explore (0)

L (0) +1 = False t∈Exp (0) L (0) +1 max x∈X L (z) +1 (x * -x) γ * ≤ 21 x∈X µ (0) L (0)+1 (x) ∆ L (0) +1 x . (23)

Bound on

z∈{-1,+1}

L (z) +1 l≥1 t∈Exp (z) l (x * -x t ) γ * .
Lemma 13 shows that for l ≤ L (z) , the actions in X (z) l+1 are sub-optimal by at most an additional factor at most 21 l . Let us set l ∆min = -log 2 (∆ min /21) , so that

∆ min 42 ≤ l∆ min ≤ ∆ min 21 .
For l ≥ l ∆min , we have X

(-1) l+1 ∪ X (+1) l+1 = {x z * }.
Thus, l (-z x * ) ≤ l ∆min , and for l ≥ l ∆min , the algorithm selects only x * during the phase Exp (z * ) l . Then, combining Lemmas 14 and 13, and the fact that L (z) + 1 ≤ T , we find that, on F,

z∈{-1,+1} L (z) +1 l=1 t∈Exp (z) l (x * -x t ) γ * ≤ z∈{-1,+1} l∆ min +1∧ T l=1    x∈X (z) l µ (z) l (x)    max x∈X (z) l (x * -x) γ * ≤ 2 l∆ min +1∧ T l=1 2(d + 1) 2 l log kl(l + 1) δ + (d + 1)(d + 2) 2 42 l ≤ 84(d + 1)(d + 2) + -1 l∆ min × 672(d + 1) log k(1 + T )(2 + T ) δ ≤ 84(d + 1)(d + 2) + 28224(d + 1) ∆ min log k(1 + T ))(2 + T )) δ . (24)
Bound on t∈Recovery

(x * -x t ) γ * + L (0) l=1 x∈X µ (0) l (x)∆ x + x∈X µ (0) L (0) +1 (x) ∆ L (0) +1 x .
We use the following lemma to bound the number of phases necessary to eliminate the sub-optimal group.

Lemma 16. On the event F defined in Equation [START_REF] Elfving | Optimum Allocation in Linear Regression Theory[END_REF], for l ≥ 1 such that l ≤ ∆ = 8 and Explore

(0) L = True, z * l+1 = z x * .
Let l ∆ = = -log(∆ = /8)/ log(2) be such that

∆ = 16 ≤ l∆ = ≤ ∆ = 8 . ( 25
)
Lemma 16 implies that on F, L (0) ≤ l ∆ = .

To bound the remaining terms, we consider two cases, corresponding to Recovery= ∅ and Recovery = ∅.

Case 1: Recovery= ∅. Our case assumption implies that t∈Recovery

(x * -x t ) γ * = 0. ( 26
)
Lemma 15 implies that

L (0) l=1 x∈X µ (0) l (x)∆ x + x∈X µ (0) L (0) +1 (x) ∆ L (0) +1 x ≤ L (0) +1 l=1 x∈X µ (0) l (x) ∆ l x .
Moreover, L (0) ≤ l ∆ = ∧ T , so on F

L (0) +1 l=1 x∈X µ (0) l (x) ∆ l x ≤ (l∆ = ∧ T )+1 l=1 x∈X µ (0) l (x) ∆ l x .
Using Lemma 14, we find that on F

(l∆ = ∧ T )+1 l=1 x∈X µ (0) l (x) ∆ l x ≤ (l∆ = ∧ T )+1 l=1 2κ( ∆ l ) 2 l log l(l + 1) δ + 2(d + 1)( T + 1) ≤ 2 log ( T + 1)( T + 2) δ l∆ = +1 l=1 κ( ∆ l ) 2 l + 2(d + 1)( T + 1).
Using Lemma 15 with τ = ∆ = and ( 25), we have on

F l∆ = +1 l=1 κ( ∆ l ) 2 l ≤ 513κ(∆ ∨ ∆ = ) l∆ = +1 l=1 -2 l + -1 l /∆ = ≤ 2 18 κ(∆ ∨ ∆ = ) ∆ 2 = .
We obtain on F

L (0) +1 l=1 x∈X µ (0) l (x) ∆ l x ≤ 2 19 log ( T + 1)( T + 2) δ κ(∆ ∨ ∆ = ) ∆ 2 = + 2(d + 1)( T + 1). ( 27
)
Combining Equations ( 24), ( 23), [START_REF] Lipton | Does mitigating ml's impact disparity require treatment disparity[END_REF], and ( 27), we find that on F, when Recovery= ∅, there exsists an absolute constant c > 0 such that for δ

= T -1 , z∈{-1,+1} L (z) +1 l≥1 t∈Exp (z) l (x * -x t ) γ * + t∈Recovery (x * -x t ) γ * + L (0) l=1 x∈X µ (0) l (x)∆ x ( 28
)
+1 Explore (0)

L (0) +1 = False t∈Exp (0) L (0) +1 max x∈X (-1) L (0) +2 ∪X (+1) L (0) +2 (x * -x) γ * ≤ c d 2 + d ∆ min ∨ κ(∆ ∨ ∆ = ) ∆ 2 = log(T ) + d ∆ min log(k) .
Case 2: Recovery = ∅. In this case, the algorithm enters Recovery at phase L (0) , so Explore (0)

L (0) +1 =False and Exp (0) L (0) +1 = ∅, and 1
Explore (0) L (0) +1 = False t∈Exp (0) L (0) +1 max x∈X (-1) L (0) +2 ∪X (+1) L (0) +2 (x * -x) γ * = 0. ( 29
)
Using Lemma 13, we see that

t∈Recovery (x * -x t ) γ * ≤ 21T L (0) +1 .
On the other hand, in the Recovery phase,

L (0) +1 ≤ κ( ∆ L (0) +1 ) log(T )/T ) 1/3
. Thus,

t∈Recovery (x * -x t ) γ * ≤ 21κ( ∆ L (0) +1 ) log(T ) 2 L (0) +1
. Now, Lemma 14 show that

L (0) l=1 x∈X µ (0) l (x)∆ x ≤ 4 log(2L (0) δ -1 ) L (0) l=1 κ( ∆ l ) 2 l + 4dL (0) .
Combining these results, and using L (0) ≤ T , we see that

t∈Recovery (x * -x t ) γ * + L (0) l=1 x∈X µ (0) l (x)∆ x ≤ 4dL (0) + 4 log(2 T δ -1 ) ∨ 21 log(T ) L (0) +1 l=1 κ( ∆ l ) 2 l
.

(30) Using Lemma 15 with τ = L (0) , we see that

L (0) +1 l=1 κ( ∆ l ) 2 l ≤ 513 L (0) +1 l=1 κ(∆ ∨ L (0) ) 2 l + 513 L (0) +1 l=1 κ(∆ ∨ L (0) ) L (0) l ≤ 10260 κ(∆ ∨ L (0) ) 2 L (0)
. Now, the algorithm enters the Recovery phase before finding the best group, so we must have L (0) ≤ l ∆ = . This implies that

L (0) +1 l=1 κ( ∆ l ) 2 l ≤ 2 18 κ(∆ ∨ L (0) ) ∆ 2 = .
Finally, note that L (0) ≥ L T , so L (0) ≤ L T = ε T , and

L (0) +1 l=1 κ( ∆ l ) 2 l ≤ 2 18 κ(∆ ∨ ε T ) ∆ 2 = . ( 31
)
Combining Equations ( 24), ( 29), [START_REF] Pázman | Foundations of Optimum Experimental Design[END_REF], and ( 31), we find that on F, when Recovery = ∅, there exists an absolute constant c > 0 such that for

δ = T -1 , z∈{-1,+1} L (z) +1 l≥1 t∈Exp (z) l (x * -x t ) γ * + t∈Recovery (x * -x t ) γ * + L (0) l=1 x∈X µ (0) l (x)∆ x ( 32
)
+1 Explore (0)

L (0) +1 = False t∈Exp (0) L (0) +1 max x∈X (-1) L (0) +2 ∪X (+1) L (0) +2 (x * -x) γ * ≤ c d 2 + d ∆ min ∨ κ(∆ ∨ ε T ) ∆ 2 = log(T ) + d log(k) ∆ min .

Conclusion

We conclude the proof of Theorem 2 by combining Equations ( 22), ( 28) and [START_REF] Pronzato | Removing inessential points in c-and A-optimal design[END_REF].

C.4 Proof of Theorem 3

Consider the actions A defined in the following lemma.

min π∈P A      e d+1    ( x z )∈A π x x z x x z x    + e d+1      = κ.
By Lemma 17, A ∈ A κ * ,d . We will introduce two bandit problems characterized by two parameters θ

T and θ

T -assuming that the noise ξ t is Gaussian and i.i.d. -and we prove that for any algorithm, the regret for one of those two problems must be of larger order than κ 1/3 * T 2/3 . We also consider the following two alternative problems. For a small 1/4 > ρ T > 0 where

ρ T = T -1/3 κ 1/3 *
(satisfied since T > 4 3 κ * ), the two alternative action parameters are defined as:

γ (1) T = 1 + ρ T 2 e 1 + 1 -ρ T 2 e 2 - ρ T 2   3≤j≤d e j   γ (2) T = 1 -ρ T 2 e 1 + 1 + ρ T 2 e 2 + ρ T 2   3≤j≤d e j   .
On top of this, two bias parameters are defined as ω

T = -ρ T 2 and ω

(2)

T = ρ T 2 .
Through this, we define the two bandit problems of the sketch of proof of Lemma 17 characterized by θ

(1)

T = γ (1) T ω (1) T and θ (2) T = γ (2) T ω (2) T
-and where the distribution of the noise ξ t is supposed to be Gaussian and i.i.d.

We refer to these two problems respectively as Problem 1 and Problem 2. We write R

T , P (1) and

E (1) (respectively R (2)
T , P (2) and E (2) ) for the regret, probability and expectation for the first bandit problem, when the parameter is θ T ). We also write P (i) j for the distribution of a sample received in Problem i when sampling action x j at any given time t -note that by definition of the bandit problems, this distribution does not depend on t and on the past samples given that action x j is sampled.

The three following facts hold on these two bandit problems:

Fact 1 The parameters γ (1)
T and γ

T are chosen so that x 1 is the unique best action for Problem 1, and x 2 is the unique best action for Problem 2. Choosing any sub-optimal action induces an instantaneous regret of at least ρ T , and choosing the very sub-optimal action x d+1 induces an instantaneous regret of at least 1/2. Fact 2 Because of the chosen bias parameters, the distributions of the evaluations of all actions but

x d+1 are exactly the same under the two bandit problems characterized by θ (1) and θ

Ti.e. exactly the same data is observed under the two alternative bandit problems defined by the two alternative parameters for all actions but x d+1 . More precisely, for i ∈ {1, 2}, in Problem i and at any time t, when sampling action x i where i ≤ 2, we observe a sample distributed according to N (1/2, 1) -i.e. P (i) j is N (1/2, 1) -and when sampling action x i where 2 < i ≥ d + 1, we observe a sample distributed according to N (0, 1) -i.e. P (i) j is N (0, 1).

Fact 3

The distributions of the outcomes of the evaluation of action x d+1 differs in the two bandit problems. Set α = 2/( √ κ * + 1). In Problem 1, P

d+1 is N (-1-α-ρ T α 2 , 1). In Problem 2, P (1)
d+1 is N (-1-α+ρ T α 2 , (2)
). So that the difference between the means of the evaluations of action x d+1 in the two bandit problems is

∆ = ρ T α = 2ρ T √ κ * +1 ≤ 2ρ T √ κ * .
For i ≤ d + 1, we write N i (T ) for the number of times that action x i has been selected before time T . In Problem 1, choosing the action x d+1 leads to an instantaneous regret larger than 1 2 (Fact 1), so that

R (1) T ≥ E (1) N x d+1 (T ) 2 .
If E (1) [N d+1 (T )] ≥

T 2/3 κ 1/3 *

2

, then Theorem 1 follows immediately; we therefore consider from now on the case when

E (1) [N d+1 (T )] ≤ T 2/3 κ 1/3 * 2 . (33)
Now, let us define the event

F = N 1 (T ) ≥ T 2 κ 1/3 * .
Note that action x 1 is optimal for Problem 1 and that action x 2 is optimal for Problem 2 (Fact 1).

Since choosing an action that is sub-optimal leads to an instantaneous regret larger than ρ T (Fact 1), we also have R

T ≥ T ρ T 2 P (1) F and R (1)
T ≥ T ρ T 2 P (2) (F ) . (2)
Then, Bretagnolle-Huber inequality (see, e.g., Theorem 14.2 in [START_REF] Lattimore | Bandit Algorithms[END_REF]) implies that R

T + R (1)
T ≥ T ρ T 4 exp -KL P (1) , P (2) .

For the choice ρ T = T -1/3 κ 1/3 * , this implies that R

T + R (1)
T ≥ T 2/3 κ 1/3 * 4 exp -KL P (1) , P (2) .

Now, the Kullback-Leibler divergence between P (1) and P (2) can be rewritten as follows (see, e.g., Lemma 15.1 in [START_REF] Lattimore | Bandit Algorithms[END_REF]) :

KL(P (1) , P (2) ) = 1 2 j≤d+1 E (1) [N j (T )] KL(P

j , P (1)
.

By Fact 2, we have that for any j ≤ d, P

j = P (1)
j . So that KL(P (1) ,

P (2) ) = 1 2 E (1) [N d+1 (T )] KL(P (1)
d+1 , P

.

By the characterization of P

d+1 , P

d+1 in Fact 3, and recalling that the Kullback-Leibler divergence between two normalized Gaussian distributions is given by the squared distance between their means, we find that KL(P (1) ,

P (2) ) = 1 2 E (1) [N d+1 (T )] ∆2 .
Thus, by the definition of ∆ in Fact 3 and by Equation ( 33)

KL P (1) ,

P (2) = 1 2 E (1) [N d+1 (T )] 2ρ T √ κ * + 1 2 ≤ T 2/3 κ 1/3 * 4 × 4ρ 2 T κ * = 1, (35)
reminding that ρ T = T -1/3 κ 1/3 * . Combining Equations ( 34) and [START_REF] Raghavan | Mitigating bias in algorithmic hiring: evaluating claims and practices[END_REF]

implies that max R (1) T , R (2)
T ≥ T 2/3 κ 1/3 8 exp(-1),
which concludes the proof of Theorem 3.

C.5 Proof of Theorems 4

Theorems 4 follows directly from the next Theorem.

Theorem 6. For all κ * ≥ 1 and all d ≥ 4, there exists an action set A ∈ A κ * ,d , such that for all bandit algorithms, for all (∆ min , ∆ = ) ∈ (0, 1 /8) 2 with ∆ min ≤ ∆ = , and for all budget T ≥ 2, there exists a problem characterized by θ ∈ Θ A ∆min,∆ = such that the regret of the algorithm on the problem satisfies

R θ T ≥   d 10∆ min log (T )   1 - log 8d log(T ) ∆ 2 min log (T )     ∨    κ * + 1 4∆ 2 = log (T )   1 - log 8κ * log(T ) ∆ 3 = log (T )       ∨ κ * 4∆ 2 = 1 ∧ log T ∆ 3 = 8κ * . (36)
Moreover, on this problem, κ(∆) ∈ [ κ * /8, 2κ * ].

Remark 1. Note that Theorem 6 allows us to recover a lower bound similar to that of Theorem 3 by choosing ∆ = and ∆ min of the order κ 1/3 * T -1/3 , however this bound only holds for d larger than 4.

We prove Theorem 6 for the following set of actions

A: A = x1 zx 1 , ..., x d+1 zx d+1
, where

xi zx i = e i + e d+1 , for i ∈ {2, ..., d/2 }, xi zx i
= e i -e d+1 for i ∈ { d/2 + 1, ..., d}, and

x d+1 zx d+1 = -1 -2 √ κ * +1 e 1 -e d+1 .
Then, by Lemma 10, for this choice of action set, we have A ∈ A κ * ,d . We consider the following set of bandit problems: for i ∈ {1, ..., d/2 +1} Problem i is characterized by the parameter θ (i) , where θ (i) = γ (i) ω (i) is defined as:

γ (1) = 1 + ∆ = -∆ min 2   1≤j≤ d/2 e j   + 1 -∆ = -∆ min 2   d/2 +1≤j≤d e j   + ∆ min e 1 + ∆ min e d/2 +1 γ (i) = γ (1) + 2∆ min e i + 2∆ min e d/2 +i ∀i ∈ {2, ..., d/2 } γ ( d/2 +1) = 1 -∆ = -∆ min 2   1≤j≤ d/2 e j   + 1 + ∆ = -∆ min 2   d/2 +1≤j≤d e j   + ∆ min e 1 + ∆ min e d/2 +1 ,
and the bias parameters are defined as

ω (i) = - ∆ = 2 ∀i ∈ {1, ..., d/2 }, and otherwise ω ( d/2 +1) = ∆ = 2 .
We write

E (i) , P (i) , R (i)
T for resp. the probability, expectation, and regret, in Problem i. Note that this choice of parameters ensures that ∀i ∈ {1, ..., d/2 + 1},

θ (i) ∈ Θ A ∆min,∆ = . Set A = x1 zx 1 , ..., x d+1 zx d+1
, where xi

zx i = e i + e d+1 , for i ∈ {2, ..., d/2 }, xi zx i = e i -e d+1 for i ∈ { d/2 + 1, ..., d}, and x d+1 zx d+1 = -1 -2 √ κ * +1 e 1 -e d+1 .
Then, Lemma 10 shows that A ∈ A κ * ,d .

The following facts hold: Fact 1 For any i ∈ {1, ..., d/2 + 1}, action x i is the unique optimal action in Problem i. Since 1/2 ≥ ∆ = ≥ ∆ min , sampling any other (sub-optimal) action leads to an instantaneous regret of at least ∆ min . Moreover, choosing an action in the group -z i leads to an instantaneous regret of at least ∆ = . Fact 2 In Problem i for any i ∈ {1, ..., d/2 + 1}, action d + 1 is very sub-optimal and sampling it leads to an instantaneous regret higher than

(1 -2/( √ κ * + 1))(1 -∆ = + ∆ min ) + (1 + ∆ = + ∆ min )/2 ≥ 1/2, since κ * ≥ 1 and 1/2 ≥ ∆ = ≥ ∆ min . Fact 3
In Problem i, for i ∈ {1, ..., d/2 + 1}, when sampling action x j at time, t the distribution of the observation does not depend on t or on the past (except through the choice of x j ) and is

P (i) j .
It is characterized as:

∀i ∈ {1, ..., d/2 + 1}, P

d/2 +1 are N ((1 + ∆ min )/2, 1) ∀i ∈ {1, ..., d/2 + 1}, ∀j ∈ {2, ..., d} \ { d/2 + 1, i, d/2 + i}, P (i) j is N ((1 -∆ min )/2, 1), ∀i ∈ {2, d/2 }, P (i) i is N ((1 + 3∆ min )/2, 1) P (i) d/2 +i is N ((1 + 3∆ min )/2, 1) ∀i ∈ {1, d/2 }, P (i) d+1 is N (-(1 -α)(1 + ∆ = + ∆ min )/2 + ∆ = /2, 1), P ( d/2 +1) d+1 is N (-(1 -α)(1 -∆ = + ∆ min )/2 -∆ = /2, 1) where α = 2/( √ κ * + 1). (i) 1 , P (i)
So that: Fact 3.1 For any i ∈ {2, ..., d/2 }, between Problem 1 and Problem i, the only actions that provide different evaluations when sampled are action i and action d/2 + i, and the mean gaps in both cases is 2∆ min . Fact 3.2 Between Problem 1 and Problem d/2 + 1, the only action that provide different evaluation when sampled is action d + 1, and the mean gap in this case is α∆ = .

For j ≤ d + 1, we write N j (T ) for the total number of times action x j has been selected before time T . Then, for j ∈ {1, ..., d/2 }, let E (j) = {N i (T ) ≤ T /2}. Note that for i ∈ {1, ..., d/2 }, in Problem i the action x i is the optimal action. Therefore, for any efficient algorithm, for all i ∈ {1, ..., d/2 } the event E (i) should have a low probability under P (i) . Indeed, for i ∈ {1, ..., d/2 }, the regret of the algorithm under Problem i can be lower-bounded as follows -see Facts 1 and 2:

R (i) T ≥ j≤ d/2 , j =i E (i) [N j (T )] ∆ min + d/2 +1≤j≤d E (i) [N j (T )] ∆ = + E (i) [N d+1 (T )] 2 . ( 37
)
Since j E (i) [N j (T )] = T and ∆ min ≤ ∆ = ≤ 1 2 , this implies together with Facts 1:

R (i) T ≥ T -E (i) [N i (T )] ∆ min
Using the definition of E (i) , we find that

R (i) T ≥ T ∆ min 2 P (i) E (i) . (38)
In particular for Problem 1, for any i ∈ {1, ..., d/2 }, R

T ≥ T ∆ min 2 P (1) E (i) . (1)
since

E (1) ⊃ E (i) .
Similarly, let us also define the event F = i≤ d/2

N i (T ) ≥ T /2 . Then, in Problem 1, the group 1 contains the optimal action, and so for any efficient algorithm, the event F should have a low probability under P (1) . Indeed, Equation (37) also implies

R (1) T ≥   T -E (1)   i≤ d/2 N i (T )     ∆ = ≥ T ∆ = 2 P (1) F . (40)
On the other hand, for any efficient algorithm, the event F should have high probability under P ( d/2 +1) . Indeed,under problem Problem d/2 + 1, the regret can be lower-bounded as followssee Facts 1 and 2:

R ( d/2 +1) T ≥ j≤ d/2 E ( d/2 +1) [N j (T )] ∆ = + d/2 +2≤j≤d E ( d/2 +1) [N j (T )] ∆ min + E ( d/2 +1) [N d+1 (T )] 2 .
which implies that

R ( d/2 +1) T ≥ j≤ d/2 E ( d/2 +1) [N j (T )] ∆ = ≥ T ∆ = 2 P ( d/2 +1) (F ) . (41)
Now, Bretagnolle-Huber inequality (see, e.g., Theorem 14.2 in [START_REF] Lattimore | Bandit Algorithms[END_REF]) implies that for all i ∈ {2, ..., d/2 }, 1 2 exp -KL P (1) , P (i) ≤ P (i) E (i) + P (1)

E (i) (42)
and that 1 2 exp -KL P (1) , P ( d/2 +1) ≤ P ( d/2 +1) (F ) + P (1) F .

On the one hand, Equation [START_REF] Wagenmaker | Experimental design for regret minimization in linear bandits[END_REF] implies that for any i ∈ {2, ..., d/2 }, KL P (1) ,

P (i) ≥ -log 2P (i) E (i) + 2P (1) E (i) ≥ log (T ) -log 2T P (i) E (i) + 2T P (1) E (i) . (44)
Combining Equations ( 38), [START_REF] Titterington | Algorithms for computing D-optimal design on finite design spaces[END_REF], and (44), we find that KL P (1) , P (i) ≥ log (T ) -log 4(R

(i) T + R (1) T ) ∆ min . ( 45
)
On the other hand, Equation [START_REF] Wang | Fairness of exposure in stochastic bandits[END_REF] implies that KL P (1) , P ( d/2 +1) ≥ -log 2P ( d/2 +1) (F ) + 2P (1) F ≥ log (T ) -log 2T P ( d/2 +1) (F ) + 2T P (1) F .

Combining Equations ( 38), [START_REF] Titterington | Algorithms for computing D-optimal design on finite design spaces[END_REF], and (46), we find that KL P (1) , P ( d/2 +1) ≥ log (T ) -log 4(R

( d/2 +1) T + R (1)
T ) ∆ = .

(47) Also, note that for all i ∈ {2, ..., d/2 + 1}, the Kullback-Leibler divergence between P (1) and P (i) can be decomposed as follows (see, e.g., Lemma 15.1 in [START_REF] Lattimore | Bandit Algorithms[END_REF]) :

KL(P (1) , 1) [N j (T )] KL(P

P (i) ) = j≤d+1 E (
j , P (i) j ). (1)
Lower bound in d∆ -1 min log T . By design, for i ∈ {2, ..., d/2 }, all actions but x i and x d +i have the same distribution under P (1) and P (i) -see Fact 3.1. Then, Equation (48) becomes from Fact 3.1 and from the expression of KL divergence between standard Gaussian distributions: KL(P (1) ,

P (i) ) = 4∆ 2 min 2 E (1) [N i (T )] + 4∆ 2 min 2 E (1) N d +i (T ) .
So that, summing over i ∈ {2, ..., d/2 }, and by Fact 1:

i∈{2,..., d/2 } KL(P (1) ,

P (i) ) ≤ 2∆ min R (1)
T .

So that by Equation (45) (summing over i ∈ {2, ..., d/2 }):

2∆ min R (1) T ≥ i∈{2,..., d/2 } log (T ) -log 4(R (i) T + R (1)
T ) ∆ min = ( d/2 -1) log (T ) - i∈{2,..., d/2 } log 4(R (i) T + R (1)
T ) ∆ min .

Let us assume that our algorithm satisfies max i≤ d/2 R (i)

T ≤ d log(T ) ∆min -otherwise the bound immediately follows for this algorithm. Then Lower bound in κ * ∆ -2 = log T . By design, all actions but x d+1 have the same evaluation under Problem 1 and Problem d/2 + 1 -see Fact 3.2. Then, by Fact 3.2 and the expression between the KL divergence of standard Gaussians, Equation (48) becomes KL(P (1) , P ( d/2 +1) ) = E (1) [N d+1 (T )] (α∆ = )

2 2 = 1 2 E (1) [N d+1 (T )] 2∆ = √ κ * + 1 2 .
Combined with equation (47), this implies that

1 2 E (1) [N d+1 (T )] 2∆ = √ κ * + 1 2 ≥ log (T ) -log 4(R ( d/2 +1) T + R (1)
T ) ∆ = . ( 50
)
Let us assume that our algorithm satisfies max i≤ d/2 +1 R (i)

T ≤ κ * log(T ) ∆ 2 =
-otherwise the bound immediately follows for this algorithm. We then have

1 2 E (1) [N d+1 (T )] 2∆ = √ κ * + 1 2 ≥ log (T ) -log 8κ * log (T ) ∆ 3 = .
Using Equation [START_REF] Sagnol | Computing exact d-optimal designs by mixed integer second order cone programming[END_REF], we find that

R (1) T ≥ κ * + 1 4∆ 2 = log (T ) -log 8κ * log (T ) ∆ 3 = . ( 51
)
Lower bound in κ * ∆ -2 = . Let us assume that our algorithm satisfies max i≤ d/2 +1 R (i)

T ≤ κ * ∆ 2 =
otherwise the bound immediately follows for this algorithm. Then, Equation (50) implies

1 2 E (1) [N d+1 (T )] 2∆ = √ κ * 2 ≥ log (T ) -log 8κ * ∆ 3 = .
Using again Equation [START_REF] Sagnol | Computing exact d-optimal designs by mixed integer second order cone programming[END_REF], we find that

R (1) T ≥ κ * + 1 4∆ 2 = log T ∆ 3 = 8κ * . ( 52
)
We conclude the proof of Theorem 6 by combining Equations ( 49), ( 51) and (52).

Bounds on κ(∆) Finally, Lemma 11

zx d+1 = -1 -2 √ κ * +1 e 1 -e d+1 .
Using the same proof as in Lemma 17, we see that

min π∈P A      e d+1    ( x z )∈A π x x z x x z x    + e d+1      = κ.
Then, we consider the following problems : for i ≤ d, Problem i is characterized by the parameter θ (i) , where θ (i) = γ (i) ω (i) is defined as:

γ (1) = 1 -∆ min 2 i≤d e i + ∆ min e 1 γ (i) = 1 -∆ min 2
i≤d e i + ∆ min e 1 + ∆ min e i for i >1 and the bias parameters are defined as ω (i) = 0 for i ≤ d. The following facts hold:

Fact 1 For any i ∈ {1, ..., d}, action x i is the unique optimal action in Problem i. Sampling any other (sub-optimal) action leads to an instantaneous regret of at least ∆ min . Fact 2 In Problem i, for i ∈ {1, ..., d}, when sampling action x j at time, t the distribution of the observation does not depend on t or on the past (except through the choice of x j ) and is

P (i) j . It is characterized as: ∀i ∈ {1, ..., d}, P (i) 1 is N ((1 + ∆ min )/2, 1)
∀i ∈ {1, ..., d}, P

d+1 is N (-(1 - 2 √ κ * + 1 )(1 + ∆ min )/2, 1) (1)
∀i ∈ {2, ..., d}, P

(i) i is N ((1 + 3∆ min )/2, 1)
∀i, j ∈ {2, ..., d}, i = j :

P (i) j is N ((1 -∆ min )/2, 1)
So that for any i ∈ {2, ..., d}, between Problem 1 and Problem i, the only action that provides different evaluations when sampled is action i , and the mean gap is 2∆ min .

Moreover, max x∈X (1 + z x x ũ) 2 < 1, so max x∈X z x x ũ < 0. Thus, for all x ∈ X , x ũ and z x are of opposite sign, and x ũ = 0. This implies that the hyperplane containing 0 with normal vector ũ contains no action, and separates the two groups. Moreover,

κ -1/2 * = max x∈X |z x x ũ + 1|.
We denote x (1) ∈ argmax x∈X z z x ũ, and x (2) ∈ argmin x∈X z z x ũ. Let us show that

(z x (1)
x (1) ũ + 1) = -1 + z x (2) x (2) ũ , i.e that z x (1) x (1) ũ + z x (2) x (2) ũ = -2. Indeed, note that

κ -1/2 * = (z x (1) x (1) ũ + 1) ∨ -(1 + z x (2) x (2) ũ).
Then, for u = -2

(z x (1) x (1) +z x (2) x (2) ) ũ ũ, we see that

z x (1)
x (1) u

+ 1 = -1 + z x (2) x (2) u = max x∈X |z x x u + 1|.
By contradiction, let us first assume that z x (1) x (1) ũ + z x (2) x (2) ũ < -2. Then,

max x∈X |z x x u + 1| = z x (1) x (1) u + 1 < z x (1) x (1) ũ + 1 = κ -1/2 *
which contradicts the definition of κ * .

Similarly, if we assume that z x (1) x (1)

ũ + z x (2) x (2) ũ > -2, then max x∈X |z x x u + 1| = -(z x (2) x (2) u + 1) < -(z x (2) x (2) ũ + 1) = κ -1/2 *
which contradicts again the definition of κ * . Therefore,

(z x (1) x (1) ũ + 1) = -1 + z x (2) x (2) ũ = κ -1/2 * .
Then, the hyperplane containing 0 with normal vector ũ separates the actions of the two groups. Moreover, the margin is -z x (1) x (1)

ũ = 1 -κ -1/2 *
, while the maximum distance of all points is -z x (2) x (2)

ũ = 1 + κ -1/2 *
. Thus, there exists ũ such that the hyperplane containing 0 with normal vector ũ separates the actions of the two groups, with margin equal to √ κ * -1 √ κ * +1 times the maximum distance of all points to the hyperplane.

Conversely, assume that there exists κ > κ * such that there exists u ∈ R d such that the hyperplane containing 0 with normal vector u separates the actions of the two groups, with margin equal to

√ κ-1 √ κ+1 = 1-κ -1/2
1+κ -1/2 times the maximum distance of all points to the hyperplane, denoted hereafter d. Since the hyperplane separates the points, we can assume without loss of generality that for all x ∈ X , z x x u < 0. Similarly, up to a renormalization, we can assume without loss of generality that d = 1 + κ -1/2 . Then,

max x∈X |z x x u + 1| = (max x∈X z x x u + 1) ∨ -(min x∈X z x x u + 1) = - 1 -κ -1/2 1 + κ -1/2 × (1 + κ -1/2 ) + 1 ∨ -(1 -κ -1/2 -1) = κ -1/2 < κ -1/2 *
which contradicts the definition of κ * . This concludes the proof of the first statement.

To prove the second statement, let us assume that no separating hyperplane containing zero exists. Then, for all u ∈ R d , there exists x ∈ X such that z x x u ≥ 0. This implies that min u∈R d max x∈X (z x x u + 1) ≥ 1, so κ * ≤ 1. Choosing u = 0, we see that κ * ≥ 1, which implies that κ * = 1.

C.7.2 Proof of Lemma 2

Since for all γ ∈ X and all x ∈ X , |x γ| ≤ 1, it is easy to see that the gaps are bounded by 2, and that κ ≤ 2κ * .

Let us now show that κ ≥ κ * /2.

x (1) , x (2) , γ ∈ argmax

(x,x )∈X ,γ∈C(X ) (x -x ) γ x = 1 2 (x (1) + x (2) ) n = x∈X µ(x) and x = 1 n x∈X µ(x)x.
Recall that κ * can equivalently be defined as the budget necessary to estimate the bias with a variance smaller than 1. Therefore, we have n ≥ κ * .

(53) Let us define ∆ max as ∆ max = (x (1) -x (2) ) γ = max

(x,x )∈X ,γ∈C(X ) (x -x ) γ. By definition of κ and µ, κ ≥ x∈X µ(x)(x (1) -x) γ = n(x (1) -x) γ.
Using Equation (53), we find that

κ κ * ≥ (x (1) -x) γ + (x -x) γ = ∆ max 2 + (x -x) γ. (54)
Now, since γ ∈ C(X ), we also have -γ ∈ C(X ), and therefore

κ ≥ x∈X µ(x)(x (2) -x) (-γ) = n( x -x (2) ) γ
Using again Equation (53), we find that

κ κ * ≥ ( x -x) γ + (x -x (2) ) γ = ( x -x) γ + ∆ max 2 . ( 55
)
Combining Equations ( 54) and (55), we find that

κ κ * ≥ ∆ max 2 + |(x -x) γ|.
This implies in particular that κ ≥ ∆maxκ * 2 .

To conclude the proof of the Lemma, we show that ∆ max ≥ 1. By contradiction, assume that ∆ max < 1.

For all non-zero vector u ∈ R d , let us denote x u = argmax x∈X |x u|. Since X spans R d , we necessarily have |x u u| > 0, so we can define the normalized vector ũ = u/|x u u| such that ũ belongs to the set C(X ). Finally, denote x

(1) u , x (2)
u ∈ argmax x,x ∈X (x (1) u -x (2)
u ) ũ. Note that by definition of ∆ max , we always have (x

(1) u -x (2) u ) ũ ≤ ∆ max < 1.

C.7.3 Proof of Lemmas 3 and 4

We begin by proving Lemma 4. Recall that π is a G-optimal design for the set {a x : x ∈ X }, and that µ is defined as µ(x) = mπ(x) for all x ∈ X .

We first observe that V (π) = A π A π , where A π is the matrix with lines given by [ π(x)a x ] x∈X . Since the supports of µ and π are the same, we get that Range(A π ) = Range(A µ ). As a consequence Range(V (π)) = Range(A π ) = Range(A µ ) = Range(V (µ)), and x ∈ Range(V (µ)) for all x ∈ X . This ensures that a x θ µ is an unbiased estimator of a x θ * . Furthermore V (µ) mV (π), so the variance a x V (µ) + a x of a x θ µ is upper-bounded by a x V (µ) + a x ≤ m -1 a x V (π) + a x . Now, the General Equivalence Theorem of Kiefer and Pukelshein shows that max x∈X a x V (π) + a x ≤ d + 1. Thus, a x V (π) + a x ≤ m -1 (d + 1).

We now prove Lemma 3. Recall that π ∈ M X e d+1 is such that e d+1 ∈ Range V (π), and that µ is defined as µ(x) = mπ(x) for all x ∈ X . Using similar arguments, we can show that e d+1 ∈ Range(V (µ)), which ensures that e d+1 θ µ is an unbiased estimator of e d+1 θ * . The second part of the Lemma follows directly using that V (µ) mV (π).

C.7.4 Proof of Lemma 5

Elfving's set S for estimating the bias in the biased linear bandit problem is given by

S = convex hull x z x , -x -z x : x ∈ X , or equivalently by S = convex hull ± z x x 1 : x ∈ X . Now, Theorem 5 indicates that κ -1 /2 *
e d+1 belongs to a supporting hyperplane of S. We first show that when A spans R d+1 , any normal vector w ∈ R d+1 to this hyperplane is such that w e d+1 = 0.

By contradiction, let us assume that κ -1 /2 * e d+1 belongs to some supporting hyperplane H of S parametrized as H = a ∈ R d+1 : a w = b , where the normal vector w is of the form w = u 0 . Then, κ

-1 /2 * e d+1 ∈ H, so κ -1 /2 *
e d+1 w = b, and thus b = 0. Now, H is a supporting hyperplane of S, so for all a ∈ S we see that a w ≤ b. In particular, for all x ∈ X , x u ≤ 0 and -x u ≤ 0, so x u = 0. This implies that X is supported by an hyperplane in R d with normal vector u, which contradicts our assumption that A spans R d+1 . Thus, the supporting hyperplane of S containing κ -1/2 * e d+1 has a normal vector w ∈ R d+1 such that w e d+1 = 0. In particular, we can parameterize this hyperplane as

H u,b = a ∈ R d+1 : a u 1 = b for some b ∈ R and u ∈ R d . Now, if H u,b
is a supporting hyperplane of S, then, by definition, S is contained in the half space a ∈ R d+1 : a u 1 ≤ b . In particular, for all x ∈ X , one must have z x x u + 1 ≤ b and -z x x u -1 ≤ b : therefore, for all x ∈ X , |z x x u + 1| ≤ b. Moreover, H u,b is a supporting hyperplane of S, so there exists an extreme point a ∈ S such that a ∈ H u,b . Note that S is the convex hull of ± zxx 1 : x ∈ X , so the extreme points of S are in ± zxx 1 : x ∈ X . In particular, this implies that b = max |z x x u + 1| : x ∈ X . Thus, the supporting hyperplane of S containing κ -1/2 * e d+1 is necessarily of the form H u,max{|zxx u+1|:x∈X } .

On the one hand, κ

-1 /2 *
belongs to the boundary of S and therefore to a supporting hyperplane H u,max{|zxx u+1|:x∈X } of S. Then, there exists u ∈ R d such that κ

-1 /2 * = max |z x x u + 1| : x ∈ X .
On the other hand, it is easy to verify that for all u ∈ R d , H u,max{|zxx u+1|:x∈X } is a supporting hyperplane of S. Now, κ We prove that 2( √ κ * -1) 2 ∨ 1 ≤ α ≤ 8(κ * + 1). Lemma 6 follows directly by noticing that α ≥ 1 and κ * ≥ 1.

Let us begin by proving that 2( √ κ * -1) 2 ≤ α for κ * > 1 (otherwise this inequality is automatically verified). Note that for all u ∈ R d , lim

λ→+∞ 1 max x∈X (x (λu)+zx) 2 = 0, so the minimum over u ∈ R d of 1 max x∈X (x u+zx) 2 = 0 is attained for some vector ũ ∈ R d . Let us also denote x ∈ argmax x∈X (z x x ũ + 1) 2 , such that κ * = 1 (z x x ũ + 1) 2 .
With these notations, we see that for all x ∈ X , (z x x ũ + 1) 2 ≤ (z x x ũ + 1) 2 = κ -1 * < 1. This implies that for all x ∈ X ,

z x x ũ ≤ -1 + κ -1/2 * < 0.
Now, let us denote x (1) , x (2) ∈ argmax x,x ∈X (x -x ) ũ. By definition of α, we see that

α ≥ (x (1) -x (2) ) ũ 2 (z x x ũ + 1) 2 = (x (1) -x (2) ) ũ 2 × κ * .
Since z x x ũ < 0 for all x ∈ X , and since no group is empty, we can conclude that there exists x, x ∈ X such that x ũ > 0 and x ũ < 0. In particular, by definition of x (1) and x (2) , we see that (x (1) ) ũ > 0 and (x (2) ) ũ < 0. Then,

(x (1) -x (2) ) ũ 2 ≥ (x (1) ) ũ 2 + (x (2) ) ũ 2 ≥ 2(1 -κ -1/2 * ) 2 . This implies that α ≥ 2(1 -κ -1/2 * ) 2 × κ * = 2( √ κ * -1) 2 .
Let us now prove that α ≥ 1. Note that by assumption, X spans R d , and in particular there exists ũ ∈ R d and x, x ∈ X such that max x∈X x ũ > 0 and min x∈X x ũ ≤ 0. Thus, max x,x ∈X ((xx ) ũ) 2 ≥ max x∈X (x ũ) 2 . For any λ > 0, choosing u = λũ in the definition of α implies that

α ≥ λ 2 max x∈X (x u) 2 max x∈X (λz x x u + 1) 2 .
Letting λ go to infinity, we find that α ≥ 1.

Finally, we prove that α ≤ 8(κ * + 1). For all u ∈ R d , we see that

max x,x ∈X ((x -x ) u) 2 max x∈X (z x x u + 1) 2 ≤ 4 max x∈X (z x x u) 2 max x∈X (z x x u + 1) 2 . Now, we see that max x∈X (z x x u) 2 max x∈X (z x x u + 1) 2 ≤ 2 max x∈X (z x x u + 1) 2 + 2 max x∈X (z x x u + 1) 2 ≤ 2 + 2 max x∈X (z x x u + 1) 2 .
This in turn implies that for all u ∈ R d ,

max x,x ∈X ((x -x ) u) 2 max x∈X (z x x u + 1) 2 ≤ 8(1 + κ * ),
which finally implies that α ≤ 8(1 + κ * ).

C.7.6 Proof of Lemma 8

Proof of Claim i) The proof of the first claim is immediate by definition of κ. Indeed, let M = µ ∈ M X e d+1 : e d+1 V (µ) + e d+1 ≤ 1 be the set of measures µ admissible for estimating ω * with a precision level 1. Then,

κ(c∆) = min µ∈ M x µ(x)c∆ x = c min µ∈ M x µ(x)∆ x = cκ(∆). Proof of Claim ii) The proof of the second claim is also straightforward. If ∆ ≤ ∆ , then for all µ ∈ M, x µ(x)∆ x ≤ x µ(x)∆ x . Recall that µ ∆ = argmin µ∈ M x µ(x)∆ x . Then, κ(∆ ) = x µ ∆ (x)∆ x ≥ x µ ∆ (x)∆ x ≥ min µ∈ M x µ(x)∆ x = κ(∆).

Proof of Claim iii)

To prove the third claim, note that

κ(∆ ∨ ∆ ) = min µ∈ M x µ(x) (∆ x ∨ ∆ x ) ≥ min µ∈ M x µ(x)∆ x ∨ x µ(x)∆ x ≥ min µ∈ M x µ(x)∆ x ∨ min µ∈ M x µ(x)∆ x ≥ κ(∆) ∨ κ(∆ ). Proof of Claim iv) Recall that κ(∆) = min µ∈ M x µ(x)∆ x .
Let us define a sequence (µ n ) n∈N ∈ M N such that x µ n (x)∆ x → n→∞ κ(∆), and let us denote

κ n = x µ n (x)∆ x . According to Claim ii), we have κ(∆) ≤ κ(∆ ∨ ) = min µ∈ M x µ(x) (∆ x ∨ ) ≤ x µ n (x)∆ x + x µ n (x).
It follows that for all n, κ(∆) ≤ lim inf

→0 + κ(∆ ∨ ) ≤ lim sup →0 + κ(∆ ∨ ) ≤ κ n .
Letting n go to infinity, we get that lim →0 + κ(∆ ∨ ) = κ(∆).

C.7.7 Proof of Lemma 9

Setting µ • ∆ = (µ(x)∆ x ) x∈X and

V ∆ (λ) = x∈X λ x ∆ -1/2 x x ∆ -1/2 x z x ∆ -1/2 x x ∆ -1/2 x z x , we observe that V ∆ (µ • ∆) = V (µ). Hence, κ(∆) = min µ∈M + e d+1 V∆(µ•∆) + e d+1 ≤1 x∈X (µ • ∆) x .
We observe that e d+1 ∈ Range(

V (µ)) is equivalent to e d+1 ∈ Range(V ∆ (µ • ∆)). Hence, µ ∆ • ∆ = λ ∆ where λ ∆ ∈ argmin λ∈R X + e d+1 ∈Range(V∆(λ)) e d+1 V∆(λ) + e d+1 ≤1 x∈X λ x .
The conclusion then follows by noticing that by homogeneity, λ ∆ = κ ∆ π ∆ .

C.7.8 Proof of Lemma 12

Lemma 12 follows directly from Lemmas 18 and 19. Lemma 18.

P

  ∃l ≥ 1, z ∈ {-1, 1} such that Explore (z) l = True, and x ∈ X (z) l such that γ (z) l -γ * ω (z) l -ω * x z x ≥ l   ≤ δ. Lemma 19.
P ∃l ≥ 1 such that Explore

C.7.9 Proof of Lemma 13

To prove Lemma 13, we rely on the following key lemma. This lemma proves that on F, i.e. when the error bounds hold, the algorithm never eliminates the best action or the best group.

Lemma 20. On the event F, for all x * ∈ argmax x∈X x γ * and all l such that Explore

(z x * ) l = True, x * ∈ X (z x * )
l+1 . Moreover, on the event F, for all l such that Explore (0) l = True, there exists

x * ∈ argmax x∈X x γ * such that z * l+1 = -z x * . Let l ≥ 1 be such that Explore (z x * ) l = True. Then, on F, x * ∈ X (z x * ) l+1 by Lemma 20. Moreover, for all x ∈ X (z x * ) l+1 , by definition of X (z x * ) l+1 , we have that on F x * z x * - x z x * γ (z) l ω (z) l ≤ 3 l . which implies that x * z x * - x z x * γ * ω * ≤ 3 l + x * z x * γ (z) l -γ * ω (z) l -ω * + x z x * γ (z) l -γ * ω (z) l -ω * .
Thus, on the event F, for all x ∈ X (z x * ) l+1 (x * -x) γ * < 5 l , which proves Equation [START_REF] Fellman | On the Allocation of Linear Observations[END_REF]. To prove the second claim of Lemma 13, assume that for all x ∈ argmax x∈X x γ * , z x = z x * (when this does not hold, the second claim follows from Equation ( 13)). Now, let l ≥ 1 be such that Explore (-z x * ) l = True. By Lemma 20, on F, x * ∈ X (z x * ) l and z * l = 0. Then, the algorithm is unable to determine the group containing the best set during the phase Exp (0) l-1 , so there must exist x ∈ X

(-z x * ) l such that x * z x * γ (z x * ) l-1 ω (z x * ) l-1 ≤ x -z x * γ (-z x * ) l-1 ω (-z x * ) l-1 + 2z x * ω (0) l-1 + 4 l-1 . It follows that x * -x 2z x * γ * ω * ≤ x * z x * γ * -γ (z x * ) l-1 ω * -ω (z x * ) l-1 + x -z x * γ (-z x * ) l-1 -γ * ω (-z x * ) l-1 -ω * +2z x * ω (0) l-1 +4 l-1 .
On F, this implies that

x * -x 2z x * γ * ω * < 2z x * ω (0) l-1 + 6 l-1 so (x * -x ) γ * ≤ 2z x * ω (0) l-1 -ω * + 6 l-1 < 8 l-1 = 16 l . (56)
Moreover, for all x ∈ X (-z x * ) l+1

we have (a x -a x ) θ (-z x * ) l ≤ 3 l , so following the same lines as for the first claim, we get (x -x) γ * < 5 l . Combining this bound with (56), we get max

x∈X (-z x * ) l+1 (x * -x) γ * < 21 l .
This concludes the proof of Lemma 13.

C.7.10 Proof of Lemma 14

For z ∈ {-1, +1} and l > 0, which proves the first claim of Lemma 14.

x µ (z) l (x) ≤ x 2(d + 1)π (z) l (x) 2 l log kl(l + 1) δ + | supp(π (z) l )|. Now, supp(π (z) l ) ≤ (d+1)(d+2)
To prove the second claim, we bound the regret for bias estimation at stage l as follows. On F, we have ∆ x ≤ ∆ l x for all x ∈ X and l ≥ 1, so

x∈X µ (0) l (x)∆ x ≤ x∈X µ (0) l (x) ∆ l x .
Recall that μl is the ∆ l -optimal design, and that for all x ∈ X , µ

l (x) = 2μ l (x)

C.7.11 Proof of Lemma 15

For the first claim, we rely on the next lemma.

Lemma 21. Let us set x = max l ≥ 1 : x ∈ X (-1) l ∪ X

(1) l

. On F, we have for any l ≥ 1 1. ∆ l x ≤ ∆ x + 16 l for all x ∈ X (-1) l ∪ X

(1) l (i.e. for all x such that l ≤ x ); 2. if ∆ x ≥ 21 l then x ≤ l;

3. x < ∆ x for all x ∈ X .

Lemma 15 relies on the following remarks : if ∆, ∆ are such that ∆ x ≤ ∆ x for all x ∈ X , then by Lemma 8 (ii)), κ(∆) ≤ κ(∆ ). Let us now prove that for all l ≥ 1 and all x ∈ X , ∆ l x ≤ 513(∆ ∨ l ). Case l ≥ ∆ x . On F, we have l ≤ x -1 according to the third claim of Lemma 21. So, on F, ∆ l

x ≤ ∆ x + 16 l ≤ 17(∆ x ∨ l ).

Case l < ∆ x . Then, on F, we have 32 l+5 < ∆ x and so l + 5 ≥ x according to the second claim of Lemma 21. Hence, on F, according to Lemma 21, we have Using Lemma 8 together with ∆ l

∆ l x ≤ max
x ≤ 513(∆ ∨ l ), we find that κ( ∆ l x ) ≤ 513κ(∆ ∨ l ) ≤ 513(1 + l /τ )κ(∆ ∨ τ ). This proves the first claim of Lemma 15.

To prove the second claim, we use Lemma 8 and the fact that for all x, ∆ l x ≥ l . Moreover, on F, ∆ l

x ≥ ∆ x for all x ∈ X . Then, κ( ∆) ≥ κ( l ∨ ∆) by Lemma 8 (iii)).

C.7.12 Proof of Lemmas 16

To prove Lemma 16, let us consider l such that l ≤ We prove Lemma 10. The proof of Lemma 17 follows by noticing that the two actions sets are equal up to a permutation of the direction of some basis vectors. To prove Lemma 17, we rely on Elfving's characterization of c-optimal design, given in Theorem 5. Theorem 5 shows that for π ∈ P {1,..,d+1} to be e d+1 -optimal, there must exist t > 0 and ζ ∈ {-1, +1} d+1 such that

1≤i≤d+1 π i = 1 0 = π 1 ζ 1 -(1 - 2 √ κ * + 1 )π d+1 ζ d+1 ∀i ∈ {2, ..., d}, 0 = π i ζ i t = 1≤i≤ d/2 π i ζ i - d/2 +1≤i≤d+1 π i ζ i .
Solving this system, we find that t -2 = κ * . Note that the unicity of the solution for the corresponding probability measure π guarantees that te d+1 belongs to the boundary of S.

C.7.14 Proof of Lemma 11

For a given parameter γ * , let us denote by ∆ i the gap corresponding to the action i. To compute κ(∆), we could want to rely on Lemma 9 to find the ∆-optimal design, corresponding to the e d+1 -optimal design on the rescaled features ∆ -1/2 x x zx . Theorem 5 indeed allows us to compute such a design, as seen in the proof of Lemma 10. Unfortunately, we cannot rescale the features using the true gaps, since ∆ x * = 0. To circumvent this problem, we rely on the following reasoning :

1. We use Lemma 9 and Theorem 5 to compute the design µ ∆∨ for ∈ (0, ∆ min ); and the corresponding regret κ(∆ ∨ ); 2. We find the value of κ(∆) by noticing that → κ(∆ ∨ ) is continuous at 0. For ∈ (0, ∆ min ), define ∆ = ∆ ∨ , and x = ∆ -1/2 x x. Let π denote the e d+1 -optimal design for the rescaled features x, and let κ * denote its variance. Then, Lemma 9 ensures that κ(∆) = κ * . Now, Theorem 5 shows that there exists ζ ∈ {-1, +1} d+1 such that .

As in Lemma 10, the unicity of the solution for the corresponding probability measure π guarantees that κ * -1/2 e d+1 belongs to the boundary of the Elfving's set. Now, ≤ ∆ min , so

κ(∆) -1/2 = κ(∆ ∨ ) -1/2 = 2 √ κ * +1 ∆ -1/2 d+1 1 + 1 -2 √ κ * +1 ∆ -1/2 d+1 1/2
Estimation of the bias By contrast, the bias elimination routine must be modified in order to handle Z groups. At each phase l, we denote by Z l the set of groups that have not been eliminated yet. If more than one group remain in Z l , we compute the difference ω 1 -ω z for all group z remaining in Z l with precision l /2 using a modified ∆-EXP-ELIM routine, which we call ∆-MULT-EXP-ELIM, described in 5. This routine samples action according to the distribution µ z , where for any groups z = 1, we defined µ z as the solution of the problem minimize µ∈M e d+1 -e d+z X

x µ(x)∆ x such that (e d+1 -e d+z ) V (µ) + (e d+1 -e d+z ) ≤ 1. (62)

We also define κ z (∆) as the corresponding regret :

κ z (∆) = x µ z (x)∆ x .
Note that the support of the distribution µ z is at most of size d + Z. This two-by-two comparison allows us to compute, for each z, z ∈ Z l , the difference of bias ω z -ω z = ω 1 -ω z -(ω 1 -ω z ) with precision level l . Then, we can use these bias estimates to eliminate groups that are sub-optimal by a gap larger than 4 l . Again, we rely on estimates of the biases and of the biased evaluations obtained during the previous round to update the estimate of the gap vector ∆ l+1 .

Algorithm 5 ∆-MULT-EXP-ELIM (X , Z, (X (z) , θ (z) ) z∈Z , ∆, n, )

1: for z ∈ Z, z = 1 do 2:

Compute ∆-optimal design μz solution of (62) on X , with | supp(μ z )| ≤ d + Z

3:

Sample nμ z (x) times each action a x for x ∈ X

4:

Compute ω 1 -ω z = (e d+1 -e d+z ) θ, where θ is the ordinary least square estimator 5: for z ∈ Z and x ∈ X (z) do m x ← a x θ (z) + ( ω 1 -ω z ) 6: for z ∈ Z and x ∈ X (z) do ∆ x ← 2 ∧ max z ∈Z,x ∈X (z ) m x -m x + 4 , bias estimation becomes too costly, so we sample the empirical best action for the remaining time. The FAIR PHASED ELIMINATION FOR MULTIPLE GROUPS algorithm is presented in 6.

D.1 Worst case regret

Before analyzing the worst case regret of Algorithm 6, we introduce a new quantity, κ * , defined as + (e d+1 -e d+z ) .

κ * = z∈Z,z =1
Note that for all z ∈ Z, z = 1, and l ≥ 1, we have κ Z l ( ∆ l ) ≤ 2 κ * . Sketch of Proof. We sketch here a proof of Claim 1, highlighting the main differences with the two-groups setting. We begin by introducing some notations.

Using Fact 2 with τ = ∆ =,z together with Fact 3, we find that . Since all actions selected during the Recovery phase belong to ∪ z∈S X (z) l , on F these actions are sub-optimal by a gap at most c L ∆ +1 , so R Rec T ≤ cT L ∆ +1 . Now, since the algorithm enters the Recovery phase, we must have L ∆ +1 ≤ ( κ S (∆ L ∆ +1 ) log(T )/T ) 1/3 , which implies that

R Rec T ≤ c κ S ( ∆ L ∆ +1 ) log(T ) 2 L ∆ +1
.

Together with Fact 2, this implies that

R ∆,S T + R Rec T ≤ c κ S (∆ ∨ L ∆ ) log(T ) 2 L ∆ .
On the one hand, Fact 3 guarantees that, since we entered the Recovery phase before eliminating any group in S, we must have L ∆ ≤ min z∈S\{z * } l ∆ =,z , so L ∆ ≥ c max z∈S ∆ =,z . On the other hand, Fact 4 ensures that L ∆ ≤ ε T . Thus,

R ∆ T + R Rec T ≤ s∈S\{z * } c κ z (∆ ∨ ε T ) log(T ) (∆ =,z ) 2 + c κ z * (∆ ∨ ε T ) log(T ) (∆ = ) 2 .
Conclusion Combining these results, we find that

R T ≤ c   d ∆ min ∨ z =z * ,z =1 κ z (∆ ∨ ∆ =,z ) ∨ κ z (∆ ∨ ε T ) (∆ =,z ) 2 + κ z * (∆ ∨ ∆ = ) ∨ κ z * (∆ ∨ ε T ) (∆ = ) 2   log(T )
when T ≥ k. Using Lemma 8, we get that κ z (∆ ∨ ∆ = ) ∨ κ z (∆ ∨ ε T ) ≤ κ z (∆ ∨ ∆ = ∨ ε T ), which concludes the proof of the results.

  (a) The margin m is equal to √ κ * -1 / √ κ * +1 times the maximum distance M of any action to the hyperplane. (b) κ * = 1: the groups cannot be separated by a hyperplane containing 0.

Figure 1 :

 1 Figure 1: Interpretation of κ * in terms of separation of the groups.Interestingly, Lemma 1 underlines that under reasonable assumptions, the constant κ * may not depend on the ambient dimension d, and it can even be equal to 1. By contrast, while the Information

  ) 2 is a normal vector of the separating hyperplane H in Figure2. Moreover, as shown in the proof of Lemma 1, the margin is in this case equal to 1 -κ -1/2 * , while the maximum distance of all points to the hyperplane is 1 + κ -1/2 * . Application to the action set A of Lemma 10 To provide the reader with intuition on κ * , we analyze here the set of actions used to derive the lower bound in Theorem 3. Let A = x1 zx 1 , ..., x d+1 zx d+1 , where xi zx i = e i + e d+1 , for i ∈ {2, ..., d/2 }, xi zx i = e i -e d+1 for i ∈ { d/2 + 1, ..., d}, and x d+1 zx d+1 = -1 -2√ κ * +1 e 1 -e d+1 . We show in Lemma 10 that the minimal variance for estimating the bias on A is indeed κ * .

Figure 2 :

 2 Figure 2: Illustration of Lemma 1 on the action set A described above for d = 2.

  from observations made during phase Exp

←

  True, choose each action x ∈ X exactly µ (0) l (x) times 26:

2 ,

 2 Theorem 2 is proved in Section C.3, Theorem 3 is proved in Section C.4, and Theorem 4 is proved in Section C.5. Extension of Theorem 4 to d = 2 and d = 3 is discussed in Section C.6. Finally, auxiliary lemmas are proved in Appendix C.7. For an event F such that P (F) > 0, we denote by E |F (resp. P |F ) the expectation (resp. the probability) conditionally on F. C.1 Outline of the proofs C.1.1 Outline of the proof of Theorem 1

  (z) l the time indices where G-exploration is performed on X (z) l and by Exp (0) l

  |ω * -ω (0)l | are smaller than l for all l such that these quantities are defined, and all x ∈ X

l

  , even actions eliminated from the sets X (z) l can be sampled. Finally, if the algorithm stops during phase Exp

Lemma 17 . 1 , 1 = e 1 +

 17111 Let the action set be given by A = x1 zx e d+1 , xi zx i = e i -e d+1 for i ∈ {2, ..., d}, and x d+1 zx d+1 = -1 -2 √ κ * +1 e 1 -e d+1 . It holds that

( 1 )

 1 T (respectively the second bandit problem with θ[START_REF] Barik | Fair sparse regression with clustering: An invex relaxation for a combinatorial problem[END_REF]

RSine d ≥ 4 ,

 4 we note that d/2 -1 ≥ d/5. This concludes the proof for this part of the bound.

-1 / 2 *- 1 /2 * e d+1 u 1 ≤-C. 7 . 5

 21175 e d+1 belongs to S, so κ max |z x x u + 1| : x ∈ X . These two results imply that κ Proof of Lemma 6

l

  -ω * ≥ l ≤ δ.

  By definition of μl (x), we have thatx∈X µ l (x) ∆ l x = κ( ∆ l ).It follows that, on F, log l(l + 1) δ κ( ∆ l ) + 2(d + 1).

5 ≤

 5 k=0,...,5∆ x -k x ≤ ∆ x + 16 x-∆ x + 512 x ≤ 513∆ x .Thus, for all l ≥ 1 and all x ∈ X , ∆ l x ≤ 513(∆ ∨ l ).Now, let M = µ ∈ M X e d+1 : e d+1 V (µ) + e d+1 ≥ 1 the measures µ admissible for estimating ω * with a precision level 1. Note that for all a, b, c > 0,(1 + ab -1 )(c ∨ b) = (c + cab -1 ) ∨ (a + b) ≥ c ∨ (a + b) ≥ c ∨ a.(57)Using Equation (57) with a = ∆ x , b = τ and c = , we see that κ(∆ ∨ ) = min µ∈ M x µ(x)(∆ x ∨ ) ≤ (1 + /τ ) min µ∈ M x µ(x)(∆ x ∨ τ ) = (1 + /τ )κ(∆ ∨ τ ).

∆ = 8 .

 8 According to Lemma 20, on F we know that z * l = -z x * . When z * l = z x * , then we also have z * l+1 = z x * and the conclusion follows immediately. Let us consider now the case where z * l = 0. By definition of ∆ = , for all x ∈ X(-z x * ) l+1 , (x * -x ) γ * ≥ ∆ = . γ (z x * ) l -γ * ω (z x * ) l -ω * + min x∈X (-z x * ) l+1 x -z x * γ * -γ (-z x * ) l ω * -ω (-z x * ) l +∆ = + 2z x * ω * -ω x * ) l + z x * ω (0) l -6 l + ∆ = .When ∆ = ≥ 8 l , this implies that z * l+1 = z x * . C.7.13 Proof of Lemmas 10 and 17

1≤i≤d+1 π i = 1 0 = π 1 ζ 1 ∆- 1 /2 1 - 2 √

 11112 , ..., d}, 0 = π i ζ i ∆ and κ * -1/2 e d+1 belongs to the boundary of S. Solving this system, we find thatκ(∆) -1/2 = κ * -1/2 =

7 :

 7 for z ∈ Z do 8:if max z ∈Z max x∈X (z ) a x θ (z ) + ( ω 1 -ω z ) ≥ max x∈X (z) a x θ (z) + ( ω 1 -ω z ) + 4 then Z ← Z \ {z}9: return Z and ∆ Stopping criterion We denote by κ Z l ( ∆ l ) = z∈Z l ,z =1 κ z ( ∆ l ) the regret for estimating the biases at phase l. If l ≤ κ Z l ( ∆ l ) log(T )/T 1/3

  e d+z (e d+1 -e d+z ) (V (π))

Claim 1 .

 1 For the choice δ = T -1 , there exists an absolute constant C > 0 and a constant T κ * ,k,Z,d,k depending on κ * , k, Z, d, and k such that the following bound on the regret of the FAIR PHASED ELIMINATION FOR MULTIPLE GROUPS algorithm 6 holds R T ≤ CZ ( κ * log(T )) 1/3 T 2/3 for T ≥ T κ * ,k,Z,d,k .

2 .

 2 ∆ ∨ ∆ =,z ) log(L (z) T )(∆ =,z ) -Bound on R ∆,S T + R Rec T .If the algorithm does not enter the Recovery phase, then R Rec T = 0 and S = {z * }. Then, the algorithms finds the best group, and the last bias exploration phase is performed at phase max z =z * L (z) ≤ max z =z * l ∆ =,z = l ∆ = . Then, Equation (65) implies thatR ∆,S T ≤ c κ z * (∆ ∨ ∆ = ) log(L (z) T )(∆ = ) -2 .If the algorithms enters the Recovery phase, we can use again the same arguments to show thatR ∆,S T ≤ c z∈S κ z ( ∆ L ∆ ) log(l L (z) T ) -2L (z) . Using Fact 2 and Equation (65), we find that for τ= L ∆ , R ∆,S T ≤ c z∈S κ z (∆ ∨ L ∆ ) log(l L ∆ T ) -2 L ∆ = c κ S (∆ ∨ L ∆ ) log(l L ∆ T ) 2 L ∆

  [START_REF] Byanjankar | Predicting credit risk in peer-to-peer lending: A neural network approach[END_REF]

		then	Recovery phase
	19:	Recovery ← {t, ..., T }
	20:	sample empirical best action in X l+1 ∪ X (-1)	(1)

l+1 until the end of the budget, t ← T 21: else ∆ l -optimal Exploration and Elimination 22:

  [START_REF] Elfving | Optimum Allocation in Linear Regression Theory[END_REF]. Set A =

		x1 zx 1	, ..., x d+1 zx d+1	, where xi zx i	= e i + e d+1 , for i ∈ {2, ..., d/2 },
	xi zx i	= e i -e d+1 for i ∈ { d/2 + 1, ..., d}, and x d+1 zx d+1	= -1 -2 √ κ * +1 e 1 -e d+1 . It holds
	that
		min π∈P A e d+1

  allows us to express κ(∆) as a function of κ * . On the one hand, since κ * ≥ 1, we see that κ * ≤ (1 + √ κ * ) 2 ≤ 4κ * . On the other hand, 1/2 ≤ ∆ d+1 ≤ 2, so = e 1 + e d+1 for i ∈ {1, ..., d}, and x d+1

	κ(∆) ∈ κ * 8 , 2κ * .
	C.6 Extension of the gap-dependent lower bounds to d = 2, 3
	Theorem 4 can be extended to d ∈ {2, 3} by considering separately the cases d ∆min ≥ κ = ∆ 2	and
	d ∆min < κ = ∆ 2	.
	Case 1 : d ∆min ≥ κ ∆ 2 =	Let us consider the set of actions defined by A =	x1 zx 1	, ..., x d+1 zx d+1	,
	where xi zx i

l κ( ∆ l ) + d + 1

Acknowledgements.

The authors would like to thank Evgenii Chzhen and Nicolas Verzelen for their valuable discussions and suggestions.

The work of A. Carpentier is partially supported by the Deutsche Forschungsgemeinschaft (DFG) Emmy Noether grant MuSyAD (CA 1488/1-1), by the DFG -314838170, GRK 2297 MathCoRe, by

Since ∆ = ≤ 1 8 , this choice of parameters ensures that ∀i ∈ {1, ..., d}, θ (i) ∈ Θ A ∆min,∆ = ,κ * . Adapting the proof of Lemma 17, we note that the minimal variance of bias estimation is at least κ * . This proves that A ∈ Θ A ∆min,∆ = ,κ * . Now, the lower bound

2∆ min log (T ) -log 8d log (T ) ∆ 2 min follows directly using arguments from the proof of Theorem 6. = -1 -2 √ κ * +1 e 1 -e d+1 . By Lemma 17, A ∈ A κ * ,d . We consider two bandit problems characterized by two parameters θ (1) and θ (2) , defined as:

On top of this, two bias parameters are defined as ω (1) = -

2 and ω (2) = ∆ =

. The following facts hold:

Fact 1 For any i ∈ {1, 2}, action x i is the unique optimal action in Problem i. Since 1/2 ≥ ∆ = , sampling any other (sub-optimal) action leads to an instantaneous regret of at least ∆ = . Fact 2 In Problem i, for i ∈ {1, ..., d}, when sampling action x j at time, t the distribution of the observation does not depend on t or on the past (except through the choice of x j ) and is P is N (0, 1)

So that, between Problem 1 and Problem 2, the only action that provides different evaluations when sampled is action 1, and the mean gaps in both cases is

Note that the minimum gap for these parameters is ∆ = ≥ ∆ min . Thus, this choice of parameters ensures that ∀i ∈ {1, ..., d}, θ (i) ∈ Θ A ∆min,∆ = ,κ * . Adapting the proof of Lemma 17, we note that the minimal variance of bias estimation is at least κ * .This proves that A ∈ Θ A ∆min,∆ = ,κ * . Then, the lower bound

follows directly using arguments from the proof of Theorem 6.

C.7 Auxiliary Lemmas

C.7.1 Proof of Lemma 1

Lemma 1 follows from the characterization of κ * given in Lemma 5. We begin by proving the first statement. Assume that κ * > 1 (otherwise the first statement is void). Note that for all u ∈ R d , lim

Case 1 : x u ũ > 0 Then, by definition of x u and x

u , we see that x

(1)

u -x

(2)

ũ > 0, and in particular x

(2) u u > 0.

Case 2 : x u u < 0 Then, by definition of x u and x

(2)

u , we see that x

(2)

u -x

(2)

u ũ < 0, and in particular x

(1) u u < 0.

Putting together Case 1 and Case 2, we see that x u , we conclude that for all x ∈ X , the sign of x u is the same, and that x u is not 0. Since this is true for all non-zero vector u, this implies in particular that no hyperplane containing the origin can separate the actions, which contradicts the assumption that X spans R d .

.

C.7.15 Proof of Lemma 18

Recall that ξ t = y t -x t γ * -z xt ω * . For l ≥ 0 and z ∈ {-1, +1}, when Explore

l is given by

where

, multiplying the left and right hand side of the last equation by V

, we find that

By Lemma 4, for all x ∈ X (z)

, so

Then,

where the first and third lines follow from Equation (59), and the second line follows from Equation (58). By definition of our algorithm, conditionally on X = True, the variables (ξ t ) t∈Exp (z) l are independent centered normal gaussian variables. Then,

Expanding

zx , and using the definition of V (z) l

, we find that

which in turn implies (using Equation ( 59))

Now, using Lemma 4 and the definition of µ z l , we see that for all x ∈ X

2 log (kl(l + 1)/δ) .

Finally, for all x ∈ X (z)

.

Integrating out the conditioning on the value of X (z) l

and Explore

(z) l and using a union bound yields the desire result.

C.7.16 Proof of Lemma 19

The proof is similar to that of Lemma 18. If Explore (0) l = True, then ω l is defined as

spans R d+1 , µ is finite and e d+1 ∈ Range (V (μ l )). Then, according to Lemma 3, for every round l, we have e d+1 ∈ Range V

By definition of our algorithm, conditionally on Explore

l are independent centered normal gaussian variables. Then,

.

Using again V l , we find that

Now, Lemma 3 and the definition of µ

2 log (l(l + 1)/δ) .

Finally, Equation (60) implies that

.

Using a union bound over the phases Exp (0) l yields the result.

C.7.17 Proof of Lemma 20

To prove Lemma 20, we begin by showing that it is enough to prove that for l ≥ 1,

and

, we see that Equation (61) would then be rewritten as

Then, Equation (61) would imply that

, thus proving Lemma 20. To prove Equation (61), we show that both

l+1 . Without loss of generality, assume that l > 1 is the smallest integer such that Explore

(because either l = 1, or Explore

and in particular

x γ

Recall that by definition of x * , (γ * ) (x * -x) ≥ 0. This in turn implies that

The last equation implies that either

Note that this case can only hold if all optimal actions x * belong to the same group z x * . Without loss of generality, assume that l > 1 is the smallest integer such that Explore Then, there exists x ∈ X

Recall that all optimal actions x * are in the same group z x * , so (γ * ) (x * -x) > 0. This in turn implies that

The last equation implies that either

C.7.18 Proof of Lemma 21

The first claim holds for l = 1. For l ≥ 1, for any x ∈ X (-1) l+1 ∪ X For the second claim, Lemma 13 gives that, on F, ∆ x < 21 l for any x ∈ X

l+1 and hence l ≥ x on F. For the third claim, we notice that

. Since the left-hand side is smaller than ∆ x + 2 x on F, we get ∆ x > x .

D Extension to M groups

Model We extend the biased linear bandit to Z groups, denoted Z = {1, ..., Z}. The evaluations are given by

where Z x is the z x -th vector of the canonical basis in R Z , and ω = {ω 1 , ..., ω Z } ∈ R Z is the vector of biases. Note that for the model to be identifiable, we must assume it does not contain an intercept. For x ∈ X , we denote a x = x Zx . To ensure identifiability of the model, we further assume that the set A = {a x : x ∈ X } spans R d+Z .

Estimation of the biased evaluations Adapting the G-EXP-ELIM routine to the multiple group framework is rather straightforward. Note that this routine can be used as is to eliminate within-group sub-optimal actions. The actions of each group span a sub-space of dimension d + 1, so the G-optimal measure is still supported by O(d 2 ) points. Moreover, the variance corresponding to this G-optimal design is still d + 1.

Algorithm 6 FAIR PHASED ELIMINATION FOR MULTIPLE GROUPS

← {x : z x = z} 4: while the budget is not spent do l ← l + 1 5:

Notations We denote by L T the largest integer l such that l ≥ 2 κ 1/3 * log(T )/T 1/3

. For z ∈ Z, we denote by L ∆ the last phase where ∆ l -optimal Exploration and Elimination is performed. We denote by Exp-G the time indices where ∆-exploration is performed at phase l for estimating the difference ω 1 -ω z . We also denote by Recovery the time indices subsequent to the stopping criterion, this set being empty when the stopping criterion is not activated. We define a "good" event F such that for all z, z ∈ Z and all x ∈ X (z) 1 , the errors a x θ * -θ

| are smaller than l for all l such that these quantities are defined. In the following, we use c, c to denote positive absolute constants, which may vary from line to line. With these notations, we decompose the regret as follows :

Bound on T P (F). Using arguments based on concentration of Gaussian variables, we can show that

Bound on R G

T . The analysis is similar to the two-groups setting. We can show that on F, only actions with gaps smaller than c l remain in the sets X (z) l for z ∈ Z l . The length of each G-optimal Exploration and Elimination phase for one group is of the order (d + 1) log(klT )/ 2 l , so the regret corresponding to phase l is of the order Z(d + 1) log(klT )/ l . Summing over the different phases, we find that

Using the definition of L T , we find that

Bound on R Rec T . On the one hand, the actions selected during the Phases Exp-G (z) l for l ≥ L T + 1 are sub-optimal by a gap at most c L T on the event F. On the other hand, if the algorithm enters the Recovery phase at a phase l, then

Therefore, all actions selected during the Recovery phase are sub-optimal by a gap at most c L T . Then, R Rec T can be bounded as

Bound on R ∆ T . To bound R ∆ T , we introduce further notations. Let us denote by l 1 , ..., l R the phases at which at least one group is eliminated, by S 1 i the sets of groups remaining at the beginning of phase l i , and by S R+1 the set of groups that are never eliminated. We also write l R+1 = L ∆ . We abuse notations and denote Exp-D

The rest of the proof is similar to that in the two-communities setting. We show that on F, ∆ l ≥ ∆ for all l ≥ 1. Then, our choice of design µ z l ,z at phase l ensures that for i ≤ R + 1, on F, t∈Exp-D

for some constant c > 0. Using arguments similar to the two-groups setting, we can sum over the different phases l ≤ l i , and find that l≤li t∈Exp-D

By definition of S i we have that κ Z l i ( ∆ li ) = κ Si ( ∆ li ). Now, the algorithm does not enter the Recovery phase before phase l i + 1, so we must have -2

li ≤ T 2/3 log(T ) -2/3 κ Z l i ( ∆ li ) -2/3 . This implies that l≤li t∈Exp-D

We use that κ Z l i ( ∆ li ) ≤ κ * and sum over i ≤ R + 1 < Z, and we find that R ∆ T ≤ CZ κ 1/3 * log(T ) 1/3 T 2/3 for T large enough.

When T ≥ T κ * ,k,Z,d,k for some T κ * ,k,Z,d,k large enough, we find that R T ≤ c Z κ 1/3 * log(T ) 1/3 T 2/3 .

D.2 Gap-dependent regret

Before stating the bound on the gap-dependent regret, we introduce further notations. For z ∈ Z, we denote ∆ =,z = min

Sketch of Proof. We sketch here a proof of Claim 2. We begin by introducing some notations. Notations We define a "good" event F such that for all z, z ∈ Z and all x ∈ X (z)

1 , the errors a

| are smaller than l for all l such that these quantities are defined. For each group z ∈ Z, we denote by Exp-G (z) l the time indices where G-exploration is performed on X (z) l . For z ∈ Z, z = 1, we denote by Exp-D (z) l the time indices where ∆-exploration is performed at phase l to estimate the difference ω 1 -ω z , and by L (z) the last phase l such that z ∈ Z l and bias exploration is performed at this phase. We denote by L ∆ the last phase l where bias estimation is performed. Moreover, we denote by S the sets of groups eliminated before the stopping criterion is activated, and write S = Z \ S. We abuse notations and denote Exp-D

l . We also denote by Recovery the time indices subsequent to the stopping criterion, this set being empty when the stopping criterion is not activated. In the following, we use c, c to denote positive absolute constants, which may vary from line to line.

Fact 1 Let l ∆min be the largest integer such that l∆ min ≥ C∆ min for some well-chosen absolute constant C > 0. Similarly to the two-groups setting, we can show that on the good event F, no more than l ∆min G-optimal Exploration and Elimination phases are needed to find the best action. For all phases l ≥ l ∆min , the algorithm always chooses x * , and suffers no regret.

Fact 2 Similarly to the two-groups setting, we can show that on the good event F, for each phase l, ∆ l ≤ c (∆ ∨ l ) for some constant c. Moreover, for all l ≤ L ∆ , all groups z = 1, and all τ > 0, κ z ( ∆ l ) ≤ c κ z (∆ ∨ l ) ≤ c(1 + l τ -1 ) κ z (∆ ∨ τ ).

Fact 3 For z ∈ Z \ {z * }, let l ∆ =,z be the largest integer such that l∆ =,z ≥ C∆ =,z for some wellchosen absolute constant C > 0. On the good event F, if ∆ l -optimal Exploration and Elimination is performed at phase l ≥ l ∆ =,z , and z ∈ Z l , then the algorithm eliminates z at this phase. This implies that L (z) ≤ l ∆ =,z , and that L ∆ ≤ l ∆ = .

Fact 4 We denote by L T the largest integer l such that l ≥ (2 κ * log(T )/T ) 1/3 . Since 2 κ * ≥ κ( ∆ l ) for all l ≥ 1 and all z ∈ Z, we see that if the algorithm enters the Recovery phase, we must have L T ≤ L ∆ , and L ∆ ≤ L T ≈ ε T .

Using Fact 1, we find that the regret can be written as ) log(l L (z) T ) -2 L (z) .

(65)