Yang Liu
email: yangl@seas.harvard.edu

Goran Radanovic
email: gradanovic@seas.harvard.edu

Christos Dimitrakakis
email: christos.dimitrakakis@gmail.com

Debmalya Mandal
email: dmandal@g.harvard.edu

David C Parkes
email: parkes@eecs.harvard.edu

Calibrated Fairness in Bandits

, which protects an on-average be er arm from being less favored. We also explain how to extend our algorithm to the dueling bandit se ing.

INTRODUCTION

Consider a sequential decision making problem where, at each time-step, a decision maker needs to select one candidate to hire from a set of k groups (these may be a di erent ethnic groups, culture, and so forth), whose true qualities are unknown a priori. e decision maker would like to make fair decisions with respect to each group's underlying quality distribution and to learn such a rule through interactions. is naturally leads to a stochastic multiarmed bandit framework, where each arm corresponds to a group, and quality corresponds to reward.

Earlier studies of fairness in bandit problems have emphasized the need, over all rounds t, and for any pair of arms, to weakly favor an arm that is weakly be er in expectation [START_REF] Ma Hew | Fairness in learning: Classic and contextual bandits[END_REF]. is notion of meritocratic fairness has provided interesting results, for example a separation between the dependence on the number of arms in the regret bound between fair and standard non-fair learning. But this is a somewhat weak requirement in that it (i) it allows a group that is slightly be er than all other groups to be selected all the time and even if any single sample from the group may be worse than any single sample from another group, and (ii) it allows a random choice to be made even in the case when one group is much be er than another group. 1 In this work, we adopt the framework of "treating similar individuals similarly" of Dwork et al. [START_REF] Dwork | Fairness through awareness[END_REF]. In the current context, it is arms that are the objects about which decisions are made, and thus the 'individual' in Dwork et al. corresponds to an 'arm'. We study the classic stochastic bandit problem, and insist that over all rounds t, and for any pair of arms, that if the two arms have a similar quality distribution then the probability with each arm is selected should be similar. is smooth fairness requirement addresses concern (i), in that if one group is best in expectation by only a small margin, but has a similar distribution of rewards to other groups, then it cannot be selected all the time.

By itself we don't consider smooth fairness to be enough because it does not also provide a notion of meritocratic fairness-it does not constrain a decision maker in the case that one group is much stronger than another (in particular, a decision maker could choose the weaker group). For this reason, we also care about calibrated fairness and introduce the concept of fairness regret, which corresponds to the degree to which an algorithm is not calibrated. Perfect calibration requires that the probability of selecting a group is equal to the probability that a group has the best quality realization. Informally, this is a strengthening of "treating similar individuals similarly" because it further requires that dissimilar individuals be treated dissimilarly (and in the right direction.) In the motivating se ing of making decisions about who to hire, groups correspond to divisions within society and each activation of an 1 Joseph et al. [START_REF] Ma Hew | Rawlsian fairness for machine learning[END_REF] also extend the results to contextual bandits and in nite bandits. Here, there is additional context associated with an arm in a given time period, this context providing information about a speci c individual. Weak meritocratic fairness requires, for any pair of arms, to weakly favor an arm that is weakly be er in expectation conditioned on context. When this context removes all uncertainty about quality, then this extension addresses critique (i). But in the more general case we think it remains interesting for future work to generalize our de nitions to the case of contextual bandits.

Y. Liu et al.

arm to a particular candidate. An algorithm with low fairness regret will give individuals a chance proportionally to their probability of being the best candidate rather than protect an entire group based on a higher average quality.

Our Results

In regard to smooth fairness, we say that a bandit algorithm is (ϵ 1 , ϵ 2 , δ )-fair with respect to a divergence function D (for ϵ 1 , ϵ 2 ≥ 0, and 0 ≤ δ ≤ 1) if, with probability 1δ , in every round t and for every pair of arms i and j,

D(π t (i)||π t (j)) ≤ ϵ 1 D(r i ||r j ) + ϵ 2 ,
where D(π t (i)||π t (j)) denotes the divergence between the Bernoulli distributions corresponding to activating arms i and j, and D(r i ||r j ) denotes the divergence between the reward distributions of arms i and j.

e fairness regret R f ,T of a bandit algorithm over T rounds is the total deviation from calibrated fairness:

R f ,T = T t =1 E k i =1 max(P * (i) -π t (i), 0) (1)
where P * (i) is the probability that the realized quality of arm i is highest and π t (i) is the probability that arm i is activated by the algorithm in round t.

Our main result is stated for the case of Bernoulli bandits. We show that a ompson-sampling based algorithm, modi ed to include an initial uniform exploration phase, satis es:

(1) (2, ϵ 2 , δ )-fair with regard to total variation distance for any ϵ 2 > 0, δ > 0, where the amount of initial exploration on each arm scales as 1/ϵ 2 2 and log(1/δ ), and (2) fairness regret that is bounded by Õ((kT ) 2/3 ), where k is the number of arms and T the number of rounds. We also show that a simpler version of ompson sampling can immediately satisfy a subjective version of smooth fairness. Here, the relevant reward distributions are de ned with respect to the posterior reward distribution under the belief of a Bayesian decision maker, this decision maker having an initially uninformed prior. In addition, we draw a connection between calibrated fairness and proper scoring functions: there exists a loss function on reward whose maximization in expectation would result in a calibrated-fair policy. In Section 5 we also extend our results to the dueling bandit se ing in which the decision maker receives only pairwise comparisons between arms.

Related work

Joseph et al. [START_REF] Ma Hew | Fairness in learning: Classic and contextual bandits[END_REF] were the rst to introduce fairness concepts in the bandits se ing. ese authors adopt the notion of weak meritocratic fairness, and study it within the classic and contextual bandit se ing. eir main results establish a separation between the regret for a fair and an un-fair learning algorithm, and an asymptotically regret-optimal, fair algorithm that uses an approach of chained con dence intervals. While their de nition promotes meritocracy in regard to expected quality, this present paper emphasizes instead the distribution on rewards, and in this way connects with the smoothness de nitions and "similar people be treated similarly" of Dwork et al. [START_REF] Dwork | Fairness through awareness[END_REF].

Joseph et al. [START_REF] Ma Hew | Rawlsian fairness for machine learning[END_REF] study a more general problem in which there is no group structure; rather, a number of individuals are available to select in each period, each with individual context (they also consider an in nite bandits se ing.) Jabbari et al. [START_REF] Jabbari | Fair learning in Markovian environments[END_REF] also extend the notion of weakly meritocratic fairness to Markovian environments, whereby fairness requires the algorithm to be more likely to play actions that have a higher utility under the optimal policy.

In the context of fair statistical classi cation, a number of papers have asked what does it mean for a method of scoring individuals (e.g., for the purpose of car insurance, or release on bail) to be fair. In this se ing it is useful to think about each individual as having a latent outcome, either positive or negative (no car accident, car accident.) One suggestion is that of statistical parity, which requires the average score of all members of each group be equal. For bandits we might interpret the activation probability as the score, and thus statistical parity would relate to always selecting each arm with equal probability. Another suggestion is calibration within groups [START_REF] Kleinberg | Inherent tradeo s in the fair determination of risk scores[END_REF], which requires for any score s ∈ [0, 1] and any group, the approximate fraction of individuals with a positive outcome should be s; see also Chouldechova [START_REF] Chouldechova | Fair prediction with disparate impact: A study of bias in recidivism prediction instruments[END_REF] for a related property. Considering also that there is competition between arms in our se ing, this relates to our notion of calibrated fairness, where an arm is activated according to the probability that its realized reward is highest. Other de nitions rst condition on the latent truth; e.g., balance [START_REF] Kleinberg | Inherent tradeo s in the fair determination of risk scores[END_REF] requires that the expected score for an individual should be independent of group when conditioned on a positive outcome; see also Hardt et al. [9] for a related property.

ese concepts are harder to interpret in the present context of bandits problems. Interestingly, these di erent notions of fair classi cation are inherently in con ict with each other [START_REF] Chouldechova | Fair prediction with disparate impact: A study of bias in recidivism prediction instruments[END_REF][START_REF] Kleinberg | Inherent tradeo s in the fair determination of risk scores[END_REF].

is statistical learning framework has also been extended to decision problems by Corbe -Davies et al. [START_REF] Corbe -Davies | Algorithmic decision making and the cost of fairness[END_REF], who analyze the tradeo between utility maximization and the satisfaction of fairness constraints. Another direction is to consider subjective fairness, where the beliefs of the decision maker or external observer are also taken into account [START_REF] Dimitrakakis | Subjective fairness: Fairness is in the eye of the beholder[END_REF]. e present paper also brie y considers a speci c notion of subjective fairness for bandits, where the similarity of arms is de ned with respect to their marginal reward distribution.

THE SETTING

We consider the stochastic bandits problem, in which at each time step, a decision maker chooses one of k possible arms (possibly in a randomized fashion), upon which the decision maker receives a reward. We are interested in decision rules that are fair in regard to the decisions made about which arms to activate while achieving high total reward.

At each time step t, the decision maker chooses a distribution π t over the available arms, which we refer to as the decision rule.

en nature draws an action a t ∼ π t , and draws rewards:

r i (t)|a t =i ∼ P(r i |θ i ),
where θ i is the unknown parameter of the selected arm a t = i, and where we denote the realized reward for arm i at time t by r i (t). We denote the reward distribution P(r i |θ i ) of arm i under some parameter θ i as r i (θ i ), with r i denote the true reward distribution. Denote the vector form as r = (r 1 , ..., r k ), while r -i, j removes r i and r j from r. If the decision maker has prior knowledge of the parameters θ = (θ 1 , ..., θ k ), we denote this by β(θ ).

Smooth Fairness

For divergence function D, let D(π t (i) π t (j)) to denote the divergence between the Bernoulli distributions with parameters π t (i) and π t (j), and use D(r i r j ) as a short-hand for the divergence between the reward distributions of arm i and j with true parameters θ i and θ j .

We de ne (ϵ 1 , ϵ 2 , δ )-fair w.r.t. a divergence function D for an algorithm with an associated sequence of decision rules {π t } t as:

De nition 2.1 (Smooth fairness). A bandit process is (ϵ 1 , ϵ 2 , δ )- fair w.r.t. divergence function D, and ϵ 1 ≥ 0, ϵ 2 ≥ 0, 0 ≤ δ ≤ 1, if
with probability at least 1δ , in every round t, and for every pair of arms i and j:

D(π t (i) π t (j)) ≤ ϵ 1 D(r i r j ) + ϵ 2 .
(

) 2
Interpretation. is adapts the concept of "treating similar individuals similarly" [START_REF] Dwork | Fairness through awareness[END_REF] to the banditrs se ing. If two arms have a similar reward distribution, then we can only be fair by ensuring that our decision rule has similar probabilities.

e choice of D is crucial. For the KL divergence, if r i , r j do not have common support, our action distributions may be arbitrarily di erent. A Wasserstein distance, requires to treat two arms with a very close mean but di erent support similarly to each other. Most of the technical development will assume the total variation divergence.

As a preliminary, we also consider a variation on smooth fairness where we would like to be fair with regard to a posterior belief of the decision maker about the distribution on rewards associated with each arm.

For this, let the posterior distribution on the parameter θ i of arm i be β(θ i |h t ), where h t = (a 1 , r a 1 (1), . . . , a t , r a(t ) (t)), is the history of observations until time t. e marginal reward distribution under the posterior belief is

r i (h t ) ∫ Θ P(r i | θ i ) dβ(θ i | h t ).
De nition 2.2 (Subjective smooth fairness). A bandit process is (ϵ 1 , ϵ 2 , δ )-subjective fair w.r.t. divergence function D, and ϵ 1 ≥ 0, ϵ 2 ≥ 0, and 0 ≤ δ ≤ 1, if, with probability at least 1 -δ , for every period t, and every pair of arms i and j,

D(π t (i) π t (j)) ≤ ϵ 1 D(r i (h t ) r j (h t )) + ϵ 2 , (3)
where the initial belief of the decision maker is an uninformed prior for each arm.

Calibrated Fairness

Smooth fairness by itself does not seem strong enough for fair bandits algorithms. In particular, it does not require meritocracy: if two arms have quite di erent reward distributions then the weaker arm can be selected with higher probability than the stronger arm. is seems unfair to individuals in the group associated with the stronger arm.

For this reason we also care about calibrated fairness: an algorithm should sample each arm with probability equal to its reward being the greatest.

is would ensure that even very weak arms will be pulled sometimes, and that be er arms will be pulled signi cantly more o en.

De nition 2.3 (Calibrated fair policy).

A policy π t is calibratedfair when it selects actions a with probability π t (a) = P * (a), P * (a) P(a = arg max

j ∈[k] {r j }), (4)
equal to the probability that the reward realization of arm a is the highest, and we break ties at random in the case that two arms have the same realized reward.

Unlike smooth fairness, which can always be achieved exactly (e.g., through selecting each arm with equal probability), this notion of calibrated fairness is not possible to achieve exactly in a bandits se ing while the algorithm is learning the quality of each arm. For this reason, we de ne the cumulative violation of calibration across all rounds T :

De nition 2.4 (Fairness regret).

e fairness regret R f of a policy π at time t is:

R f (t) E k i =1 max(P * (i) -π t (i), 0) θ . e cumulative fairness regret is de ned as R f ,T T t =1 R f (t).
Example 2.5. Consider a bandits problem with two arms, whose respective reward functions are random variables with realization probabilities:

• P(r 1 = 1) = 1.0; • P(r 2 = 0) = 0.6 and P(r 2 = 2) = 0.4.

Since E(r 1 ) = 1.0 and E(r 2 ) = 0.8, a decision maker who optimizes expected payo (and knows the distributions) would prefer to always select arm 1 over arm 2. Indeed, this satis es weakly meritocratic fairness [START_REF] Ma Hew | Fairness in learning: Classic and contextual bandits[END_REF].

In contrast, calibrated fairness requires that arm 1 be selected 60% of the time and arm 2 40% of the time, since this matches the frequency with which arm 2 has the higher realized reward. In a learning context, we would not expect an algorithm to be calibrated in every period. Fairness regret measures the cumulative amount by which an algorithm is miscalibrated across rounds.

Smooth fairness by itself does not require calibration. Rather, smooth fairness requires, in every round, that the probability of selecting arm 1 be close to that of arm 2, where "close" depends on the particular divergence function. In particular, smooth fairness would not insist on arm 1 being selected with higher probability than arm 2, without an additional constraint such as maximising expected reward.

In Section 3, we introduce a simple ompson-sampling based algorithm, and show that it satis es smooth-subjective fairness.

is algorithm provides a building block towards our main result, which is developed in Section 4, and provides smooth fairness and low fairness regret. Section 5 extends this algorithm to the dueling bandits se ing.

SUBJECTIVE FAIRNESS

Subjective fairness is a conceptual departure from current approaches to fair bandits algorithms, which empasize fairness in every period t with respect to the true reward distributions for each arm. Rather, subjective fairness adopts the interim perspective of a Bayesian decision maker, who is fair with respect to his or her current beliefs. Subjective smooth fairness is useful as a building block towards our main result, which reverts to smooth fairness with regard to the true, objective reward distribution for each arm.

Stochastic-Dominance ompson sampling

In ompson sampling (TS), the probability of selecting an arm is equal to its probability of being the best arm under the subjective belief (posterior). is draws an immediate parallel with the Rawlsian notion of equality of opportunity, while taking into account informational constraints.

In this section we adopt a simple, multi-level sampling variation, which we refer to as stochastic-dominance ompson sampling, SD TS. is rst samples parameters θ from the posterior, and then samples rewards for each arm, picking the arm with the highest reward realization.

e version of this algorithm for Bernoulli bandits with a Beta prior, where each arm's reward is generated according to a Bernoulli random variable, is detailed in Algorithm 1, which considers the marginal probability of an individual arm's reward realization being the greatest, and immediately provides subjective smooth fairness.

Algorithm 1 (SD TS): Stoch.-Dom. ompson sampling For each action a ∈ {1, 2, ..., k }, set S a = F a = 1/2 (parameters for priors of Beta distributions). for t = 1, 2, ..., do

For each action, sample θ a (t) from Beta(S a , F a ). Draw ra (t) ∼ Bernoulli(θ a (t)), ∀a.

Play arm a t := argmax a ra (t) (with random tie-breaking).

Observe the true r a t (t):

• If r a t (t) = 1, S a t := S a t + 1; • else F a t := F a t + 1. end for T 3.1.
With (SD TS), we can achieve (2, 0, 0)-subjective fairness under the total variation distance.

P

. De ne:

X j (r i ) =          1 if r i (h t ) > max{r ′ j , r ′ -i, j } 0 if r ′ j > max{r i (h t ), r ′ -i, j } Bin(1, 1
2 ) otherwise where r ′ j ∼ r j (h t ) (similarly for r ′ -i, j ) and Bin is a binomial random variable. First, we have for ompson sampling:

D(r i (h t ) r j (h t )) = 1 2 • D(r i (h t ) r j (h t )) + 1 2 • D(r i (h t ) r j (h t )) (a) ≥ 1 2 • D(X i (r i (h t )) X i (r j (h t ))) + 1 2 • D(X j (r i (h t )) X j (r j (h t ))) = 1 2 • D( 1 2 π t (j) + 1 2 • π t (l i, j)) + 1 2 • D(π t (i) + 1 2 • π t (l i, j) 1 2 )
(l denotes an arbitrary other agent than i, j.)

(b ) ≥ D( 1 2 • 1 2 + 1 2 • π t (i) + 1 2 • 1 2 • π t (l i, j) 1 2 • 1 2 + 1 2 • π t (j) + 1 2 • 1 2 • π t (l i, j)) = 1 2 |π t (i) -π t (j)| = 1 2 • D(π t (i) π t (j))
where step (a) is by monotonicty and step (b) is by convexity of divergence function D.

erefore, ϵ 1 is equal to 2, and ϵ 2 = δ = 0.

To further reduce the value of ϵ 1 , we can randomize between the selection of the arms in the following manner:

• With probability ϵ/2 select an arm selected by (SD TS); • Otherwise select uniformly at random another arm.

In that case, we have:

D(π t (i) π t (j)) = D( ϵ 2 π t,ts (i) + 1 -ϵ 2 1 2 ϵ 2 π t,ts (j) + 1 -ϵ 2 1 2 ) monotonicity ≤ ϵ 2 D(π t,ts (i) π t,ts (j)) + 1 -ϵ 2 D( 1 2 1 2 )
≤ ϵD(r i (h t ) r j (h t )).

Also see Sason and Verdú [START_REF] Sason | f -divergence inequalities[END_REF] for how to to bound D(r i (h t )||r j (h t )) using another f -divergence (e.g. through Pinsker's inequality).

While, SD TS algorithm is de ned in a subjective se ing, we can develop a minor variant of it in the objective se ing. Even though the original algorithm already uses an uninformative prior,2 to ensure that the algorithm output is more data than prior-driven, in the following section we describe an algorithm, based on SD TS, which can achieve fairness with respect to the actual reward distribution of the arms.

OBJECTIVE FAIRNESS

In this section, we introduce a variant of SD TS, which includes an initial phase of uniform exploration. We then prove the modi ed algorithm satis es (objective) smooth fairness.

Many phased reinforcement learning algorithms [START_REF] Kearns | Near-optimal reinforcement learning in polynomial time[END_REF], such as those based on successive elimination [START_REF] Even-Dar | Action elimination and stopping conditions for the multi-armed and reinforcement learning problems[END_REF], explicitly separate time into exploration and exploitation phases. In the exploration phase, arms are prioritized that haven't been selected enough times. In the exploitation phase, arms are selected in order to target the chosen objective as best as possible given the available information. e algorithm maintains statistics on the arms, so that O(t) is the set which we have not selected su ciently to determine their value. Following the structure of the deterministic exploration algorithm [START_REF] Sa Ar Vakili | Deterministic sequencing of exploration and exploitation for multi-armed bandit problems[END_REF], we exploit whenever this set is empty, and uniformly choosing among all arms otherwise. 3 Algorithm 2 Fair SD TS At any t, denote by n i (t) the number of times arm i is selected up to time t. Check the following set:

O(t) = {i : n i (t) ≤ C(ϵ 2 , δ )},
where C(ϵ 2 , δ ) depends on ϵ 2 and δ .

• If O(t) = ∅, follow (SD TS), using the collected statistics.

(exploitation)

) 2/3
).

e proof of eorem 4.1 is given in the following sketch.

P . (sketch)

We begin by proving the rst part of eorem 4.1: that for any ϵ 2 , δ > 0, and se ing C(ϵ 2 , δ ) appropriately, we will have that Fair SD TS is (2, 2ϵ 2 , δ )-fair w.r.t. total variation divergence. In the exploration phase, D(π t (i)||π t (j)) = 0, so the fairness de nition is satis ed. For other steps, using Cherno bounds we have that with probability at least 1δ

| θi -θ i | ≤ ϵ 2 2 max D(r i ||r j ) + 1 , ∀i
Let the error term for θ i be ϵ(i). Note that for a Bernoulli random variable, we have the following for the mixture distribution:

r i ( θi ) = (1 -ϵ(i)/2)r (θ i ) + ϵ(i)/2r (1 -θ i ) with ϵ(i) ≤ ϵ 2 2 max D(r i | |r j )+1
. Furthermore, using the convexity of D we can show that:

D(r i ( θi )||r j ( θj )) ≤ D(r i ||r j ) + ϵ 2 (5)
Following the proof for eorem 3.1, we then obtain that

D(π t (i)||π t (j)) ≤ 2D(r i ( θi )||r j ( θj )),
which proves our statement. We now establish the fairness regret. e regret incurred during the exploration phase can be bounded as O(k 2 C(ϵ 2 , δ )). 4 For the exploitation phase, the regret is bounded by O((ϵ 2 + δ )T ). Se ing

O((ϵ 2 + δ )T ) = O(k 2 C(ϵ 2 , δ ))
we have the optimal ϵ is ϵ := k 2/3 T -1/3 . Further se ing δ = O(T -1/2 ), we can show the regret is at the order of Õ((kT ) 2/3 ). 3 However, in our case, the actual drawing of the arms is stochastic to ensure fairness. 4 is is di erent from standard deterministic bandit algorithms, where the exploration regret is o en at the order of kC (ϵ 2 , δ ).

e additional k factor is due to the uniform selection in the exploration phase, while in standard deterministic explorations, the arm with the least number of selections will be selected.

It is possible to modify the sampling of the exploitation phase, alternating between sampling according to SD TS and sampling uniformly randomly. is can be used to bring the factor 2 down to any ϵ 1 > 0, at the expense of reduced utility.

Connection with proper scoring rules

ere is a connection between calibrated fairness and proper scoring rules. Suppose we de ne a fairness loss function L f for decision policy π , such that L f (π ) = L(π, a t,best ), where arm a t,best is the arm with the highest realized reward at time t. e expected loss for policy π is

E(L f (π )) = k i =1 P * (i) • L(π, i).
If L is strictly proper [START_REF] Gneiting | Strictly proper scoring rules, prediction, and estimation[END_REF], then the optimal decision rule π in terms of L f is calibrated.

L f (π ) = L(π, a t,best ),
where L is a strictly proper loss function. en a decision rule π that minimizes expected loss is calibrated fair.

P

. We have:

π ∈ arg min π E(L f (π )) = arg min π k i =1 P * (i) • L(π, i) = {P * (i)},
where the last equality comes from the strict properness of L.

is connection between calibration and proper scoring rules suggests an approach to the design of bandits algorithms with low fairness regret, by considering di erent proper scoring rules along with online algorithms to minimize loss.

DUELING BANDIT FEEDBACK

A er an initial exploration phase, Fair SD TS selects an arm according to how likely its sample realization will dominate those of other arms. is suggests that we are mostly interested in the stochastic dominance probability, rather than the joint reward distribution. Recognizing this, we now move to the dueling bandits framework [START_REF] Yue | e k-armed dueling bandits problem[END_REF], which examines pairwise stochastic dominance.

In a dueling bandit se ing, at each time step t, the decision maker chooses two arms a t (1), a t (2) to "duel" with each other. e decision maker doesn't observe the actual rewards of r a t (1) (t), r a t (2) (t), but rather the outcome ½(r a t (1) (t) > r a t (2) (t)). In this section, we extend our fairness results to the dueling bandits se ing.

A Plackett-Luce model

Consider the following model. Denote the probability of arm i's reward being greater than arm j's reward by: p i, j := P(i ≻ j) := P(r i > r j ),

where we assume a stationary reward distribution over time t. To be concrete, we adopt the Placke -Luce (PL) model [START_REF] Cheng | Label ranking methods based on the placke -luce model[END_REF][START_REF] Guiver | Bayesian inference for placke -luce ranking models[END_REF], where every arm i is parameterized by a quality parameter, ν i ∈ R + , such that

p i, j = ν i ν i + ν j . ( 7
)

CONCLUSION

In this paper we adapt the notion of "treating similar individuals similarly" [START_REF] Dwork | Fairness through awareness[END_REF] to the bandits problem, with similarity based on the distribtion on rewards, and this property of smooth fairness required to hold along with (approximate) calibrated fairness. Calibrated fairness requires that arms that are worse in expectation still be played if they have a chance of being the best, and that be er arms be played signi cantly more o en than weaker arms. We analyzed ompson-sampling based algorithms, and showed that a variation with an initial uniform exploration phase can achieve a low regret bound with regard to calibration as well as smooth fairness. We further discussed how to adopt this algorithm to a dueling bandit se ing together with Placke -Luce.

In future work, it will be interesting to consider contextual bandits (in the case in which the context still leaves residual uncertainty about quality), to establish lower bounds for fairness regret, to consider ways to achieve good calibrated fairness uniformly across rounds, and to study the utility of fair bandits algorithms (e.g., with respect to standard notions of regret) and while allowing for a tradeo against smooth fairness for di erent divergence functions and fairness regret. In addition, it will be interesting to explore the connection between strictly-proper scoring rules and calibrated fairness, as well as to extend Lemma 5.1 to more general ranking models.

P 4 . 2 .

 42 Consider a fairness loss function L f de ned as:

  • If O(t) ∅, select all arms equally likely. (exploration) Fair SD TS) is (2, 2ϵ 2 , δ )-fair w.r.t. total variation; and further it has fairness regret bounded as R f ,T ≤ Õ((kT

	T	4.1. For any ϵ 2 , δ > 0, se ing
		C(ϵ 2 , δ ) :=	(2 max D(r i ||r j ) + 1) 2 2ϵ 2 2	log	2 δ	,
	we have that (

FAT-ML17, Calibrated Fairness in Bandits 2017x. 978-x-xxxx-xxxx-x/YY/MM. . . $15.00 DOI: 10.1145/nnnnnnn.nnnnnnn

e use of Beta parameters equal to 1/2, corresponds to a Je rey's prior for Bernoulli distributions.

Acknowledgements. e research has received funding from: the People Programme (Marie Curie Actions) of the European Union's Seventh Framework Programme (FP7/2007-2013) under REA grant

Y. Liu et al.

Furthermore, let M = [p i, j ] denote the matrix of pairwise probabilities p i, j . is is a standard se ing to consider in the dueling bandit literature [START_REF] Szörényi | Online rank elicitation for placke -luce: A dueling bandits approach[END_REF][START_REF] Yue | e k-armed dueling bandits problem[END_REF].

With knowledge of M, we can e ciently simulate the best arm realization. In particular, for the rank over arms rank ∼ M generated according to the PL model (by selecting pairwise comparisons one by one, each time selecting one from the remaining set with probability proportional to ν i ), we have [START_REF] Guiver | Bayesian inference for placke -luce ranking models[END_REF]:

where o = rank -1 . In particular, the marginal probability in the PL model that an arm is rank 1 (and the best arm) is just:

Finally, knowledge of M allows us to directly qcalculate each arm's quality from [START_REF] Gneiting | Strictly proper scoring rules, prediction, and estimation[END_REF].

us, with estimates of the quality parameters (M) we can estimate P(rank(1) = i) and directly sample from the best arm distribution and simulate stochastic-dominance ompson sampling.

We will use dueling bandit feedback to estimate pairwise probabilities, denoted pi, j , along with the corresponding comparison matrix denoted by M. In particular, let n i, j (t) denote the number of times arms i and j are selected up to time t. en we estimate the pairwise probabilities as:

With accurate estimation of the pairwise probabilities, we are able to accurately approximate the probability that each arm will be rank 1. Denote rank ∼ M as the rank generated according to the PL model that corresponds with matrix M. We estimate the ratio of quality parameters ( ν i ν j ) using pi, j , as

Given this, we can then estimate the probability than arm i has the best reward realization:

L 5.1. When | pi, jp i, j | ≤ ϵ, and ϵ is small enough, we have that in the Placke -Luce model, |P( rank(1

is lemma can be established by establishing a concentration bound on ( ν i ν j ). We defer the details to a long version of this paper. Given this, we can derive an algorithm similar to Fair SD TS that can achieve calibrated fairness in this se ing, by appropriately se ing the length of the exploration phase, and by simulating the probability that a given arm has the highest reward realization.

is dueling version of Fair SD TS is the algorithm Fair SD DTS, and detailed in Algorithm 3.

Algorithm 3 (Fair SD DTS)

At any t, select two arms a 1 (t), a 2 (t), and receive a realization of the following comparison: ½(r a t (1) (t) > r a t (2) (t)).

Check the following set:

where C(ϵ 2 , δ ) depends on ϵ 2 and δ .

• If O(t) = ∅, follow (SD TS), using the collected statistics.

(exploitation)

∅, select all pairs of arms equally likely. (exploration) Update pa t (1), a t (2) , for the pair of selected arms (Eqn. ( 8)). Update P(rank(1) = i) using M (Eqn. ( 9)).

Due to the need to explore all pairs of arms, a larger number of exploration rounds C(ϵ 2 , δ ) is needed, and thus the fairness regret scales as R f (T ) ≤ Õ(k 4/3 T 2/3 ): T 5.2. For any ϵ 2 , δ > 0, se ing

we have that (Fair SD DTS) is (2, 2ϵ 2 , δ )-fair w.r.t. total variation; and further it has fairness regret bounded as R f ,T ≤ Õ(k 4/3 T 2/3 ).

is proof is similar to the fairness regret proof for eorem 4.1, once we established Lemma 5.1. We defer the details to the full version of the paper. agreement 608743, the Future of Life Institute, and SNSF Early Postdoc.Mobility fellowship.


Nataliya Kosmyna
email: nkosmyna@media.mit.edu

Jussi T Lindgren

Anatole Lécuyer

Attending to Visual Stimuli versus Performing Visual Imagery as a Control Strategy for EEG-based Brain-Computer Interfaces

Currently the most common imagery task used in Brain-Computer Interfaces (BCIs) is motor imagery, asking a user to imagine moving a part of the body. This study investigates the possibility to build BCIs based on another kind of mental imagery, namely "visual imagery". We study to what extent can we distinguish alternative mental processes of observing visual stimuli and imagining it to obtain EEGbased BCIs. Per trial, we instructed each of 26 users who participated in the study to observe a visual cue of one of two predefined images (a flower or a hammer) and then imagine the same cue, followed by rest. We investigated if we can differentiate between the different subtrial types from the EEG alone, as well as detect which image was shown in the trial. We obtained the following classifier performances: (i) visual imagery vs. visual observation task (71% of classification accuracy), (ii) visual observation task towards different visual stimuli (classifying one observation cue versus another observation cue with an accuracy of 61%) and (iii) resting vs. observation/imagery (77% of accuracy between imagery task versus resting state, and the accuracy of 75% between observation task versus resting state). Our results show that the presence of visual imagery and specifically related alpha power changes are useful to broaden the range of BCI control strategies.

A brain-computer interface (BCI) typically translates the electrophysiological brain signals into an output that reflects the user's intent or mental activity. BCIs can be beneficial to people with severe motor disabilities 1 and may also be used beyond the scope of medical applications 2,3 . BCI is not a perfectly accurate technology as it suffers from numerous issues, namely it is known to be a difficult task to reliably discriminate brain signal patterns from every subject. There are different approaches to improve the performance of BCIs. Most studies focus on signal processing and classification aspects. However, BCI performance can also be improved by optimizing the user's control strategies and therefore by identifying new and efficient mental tasks to achieve reliable control 4 .

Nowadays, the most common imagery task used in BCI is motor imagery, asking a user to imagine moving a specific part of the body such as a hand or a foot 5 . It is used to control assistive technologies 6 , or even computer games 7 . However, motor imagery based BCIs are seldom used outside laboratories due to their lack of reliability. The following main findings can be highlighted. First, around 20% of the BCI users are not able to obtain effective control. This phenomenon is being sometimes referred to as "BCI illiteracy" 8 . Second, for even the remaining 80% of the people, motor imagery might not be the best mental task to control a BCI (not very intuitive for people with motor disabilities). One option is to explore other mental strategies for BCI control. A broad set of possibilities is proposed in the literature, such as imagining music 9 , phoneme imagery 10 , visual imagery of faces 11 , mental rotation and word association 4 .

Here we are interested in mental tasks that have not been much tested yet for controlling a BCI, namely visual imagery of objects. We focus on visualization in this work because we respond to and process visual data better than any other type of data: the human brain processes images 60,000 times faster than text 12 , and 90 percent of information transmitted to the brain is visual 13 . Since we are visual by nature, and given how important the visual modality is, we propose to use this skill to design control strategies for BCIs.

For our study we chose two visual stimuli: a flower and a hammer. However there is a challenging problem to interpret the performance of visual imagery (and any type of mental imagery in general): some participants may show good performance but which is due to resorting to other strategies that do not involve imagery in the target modality [START_REF] Ganis | Visual imagery in cerebral visual dysfunction[END_REF] . Assessing mental imagery and the ability to distinguish between the different types of imagery thus requires a carefully designed experimental paradigm. For this end, we performed a study where imagery is guided by previously perceived stimuli. This also provides EEG data during visual perception focused on cued image, data that can be used to study differences in brain activity between perception and imagery processes.

Visual Imagery

Visual imagery is defined as "the manipulation of visual information that comes not from perception but from memory" [START_REF] Knauff | Cortical activation evoked by visual mental imagery as measured by functional MRI[END_REF] . Visual imagery has been mostly studied with PET or fMRI. However, PET and fMRI require sitting/ laying down in the scanner, which may not be realistic for some human-computer interaction settings. Another disadvantage for using PET lies in the fact that it involves injection of a radioactive material into the blood. The other problem is that although PET, similarly to fMRI has excellent spatial resolution, the delay between the shift in activity and the resulting change in blood flow is between 6 and 9 seconds (one can interpret where the event occurred but not be sure of exactly when it occurred, which makes statements about the relative order of activations problematic). These acquisition tools are quite expensive, and not portable, which also limits their use cases. In our work we will focus on the EEG-based BCI systems as the currently most affordable ones for research labs and centers. We are particularly interested if EEG can provide evidence of visual imagery to achieve desirable end-user BCI applications, as EEG-based BCIs give a possibility of independent use, set-up simplicity and wearability.

Visual Observation and Visual Imagery using EEG-based BCIs

Visual observation (sometimes "attention" in the literature) has been used with EEG-based BCIs to test if different classes of stimuli, such as cars, mushrooms, chairs, shoes, animals, etc., evoke spatially and temporally different responses when observing the images [START_REF] Carmel | Domain specificity versus expertise: factors influencing distinct processing of faces[END_REF][START_REF] Grill-Spector | The neural basis of object perception[END_REF][START_REF] Itier | N170 or N1? Spatiotemporal Differences between Object and Face Processing Using ERPs[END_REF] .

In their work, Shenoy and Tan [START_REF] Shenoy | Human-Aided Computing: Utilizing Implicit Human Processing to Classify Images[END_REF] explore whether the Event Related Potential (ERP) features that encode object category can be used to label images on a single-trial basis, without explicitly requiring users to consciously categorize the images but just to observe them. They perform an experiment where they show three different categories of images: faces, inanimate objects and animals, where the discrimination was achieved at more than 65 percent of accuracy. Simanova et al. [START_REF] Simanova | Identifying object categories from event-related EEG: toward decoding of conceptual representations[END_REF] . build an offline BCI system based on conceptual category detection by studying event-related potential (ERP) activations. They show that it is possible to get a system that allows detecting the semantic categories of a few concrete concepts (e.g. a lamp, a chair).

Another work by Kosmyna et al. [START_REF] Kosmyna | Operationalization of Conceptual Imagery for BCIs[END_REF] builds on Simanova's et al. study and explores further whether it is possible to build and asynchronous ERP-based BCI to distinguish between objects of similar and dissimilar "conceptual" categories. They obtained classification accuracies around 65% for similar conceptual categories and around 70% for conceptually distinct categories. Several studies reported that similar patterns of brain activity are observed when perceiving objects [START_REF] Shenoy | Human-Aided Computing: Utilizing Implicit Human Processing to Classify Images[END_REF][START_REF] Humphreys | Hierarchies, similarity, and interactivity in object recognition: "category-specific" neuropsychological deficits[END_REF][START_REF] Chao | Attribute-based neural substrates in temporal cortex for perceiving and knowing about objects[END_REF][START_REF] Mahon | Concepts and categories: a cognitive neuropsychological perspective[END_REF][START_REF] Pinto | Why is real-world visual object recognition hard?[END_REF] .

However, all the aforementioned studies focus on asking the participants to observe the objects on the images and there are almost no studies that investigate visual imagery of actual objects on the pictures using EEG. Moreover, we were interested in investigating visual imagery as a control paradigm to be used in offline and/ ir online BCIs, thus for this study we chose two images which could be considered as "ecological" and "user friendly" (images coming from the environment and not generated artificially) and they represent actual, real objects: a flower and a hammer. We include visual observation task in our experimental set-up to have a comparison with the state of the art on visual observation. We also include ERP analysis as well as one of the mostly well-studied brain activity that is used to analyse mental imagery -alpha rhythms.

Manifestation of Mental Imagery in EEG recordings: Alpha Oscillations

The most commonly measured rhythm in the human EEG is the alpha rhythm, generally referring to the frequency band spanning from 8 to 12 Hz. For a long time the alpha activity was reported to be strongest when people keep their eyes closed and rest, and it was known as an <<idling rhythm>> [START_REF] Pfurtscheller | Event-related synchronization (ERS) in the alpha band-an electrophysiological correlate of cortical idling: a review[END_REF] . Over the last 20 years, this <<idling>> hypothesis has been revisited. A lot of studies report that "alpha activity can increase with cognitive load" [START_REF] Schupp | Neurophysiological differences between perception and imagery[END_REF][START_REF] Williams | Psychophysiological correlates of dynamic imagery[END_REF] . Ray and Cole [START_REF] Ray | EEG activity during cognitive processing: influence of attentional factors[END_REF][START_REF] Ray | EEG alpha activity reflects attentional demands, and beta activity reflects emotional and cognitive processes[END_REF] found increased alpha power in a mental imagery task, particularly at parietal sites. Klinger et al. [START_REF] Klinger | Physiological correlates of mental activity: eye movements, alpha, and heart rate during imagining, suppression, concentration, search, and choice[END_REF] observed similar findings of increased alpha during imagery process.

Klimesch and colleagues [START_REF] Klimesch | Alpha frequency and memory performance[END_REF] introduced a theory about a wider role of alpha oscillatory networks in cognitive processes that involve attention and memory. The main principle is that "activation of this network leads to alpha desynchronization and the greater task demands are within the network, the more inhibition is needed, thus inducing alpha synchronization" meaning that alpha activity is higher with the cognitive load related to the task at hand difficulty increasing. Cooper et al. [START_REF] Cooper | Paradox lost? Exploring the role of alpha oscillations during externally vs. internally directed attention and the implications for idling and inhibition hypotheses[END_REF] showed that alpha synchronization is related to internally versus externally directed attention. They presented sequences of stimuli in the visual, auditory and tactile domains and then asked their participants to imagine the sequences. They found that "alpha activity was higher during the imagery of stimulus sequences (i.e., internally directed attention) than during their presentation (i.e., externally directed attention)". In these studies the observed synchronization of alpha activity has been interpreted to reflect "selective inhibition of task-irrelevant brain areas or inhibition of interfering external input" [START_REF] Klimesch | Simultaneous desynchronization and synchronization of different alpha responses in the human electroencephalograph: a neglected paradox?[END_REF][START_REF] Rihs | Mechanisms of selective inhibition in visual spatial attention are indexed by α-band EEG synchronization[END_REF] , and to reflect "internal information processing involving top-down control of internally represented information" (e.g. [START_REF] Sauseng | EEG alpha synchronization and functional coupling during top-down processing in a working memory task[END_REF][START_REF] Stein | Different frequencies for different scales of cortical integration: From local gamma to long range alpha/ theta synchronization[END_REF] ). The increase of alpha power over regions processing the distracting information was reported by Frey et al. [START_REF] Frey | Not so different after all: The same oscillatory processes support different types of attention[END_REF] . In this study the participants were required to maintain the "representation of the face identities versus face orientation, and more alpha power was observed over the ventral visual stream".

Hypotheses

Based on the mentioned literature, we can conclude that up to now, very few studies proposed investigating the plausibility of using visual imagery as a paradigm for EEG-based BCIs. The objective of the current study is to examine if differences are present between the two visual imagery conditions in general. Moreover we investigate, if it is possible to distinguish between imagery and observation conditions. Finally, we test if we are able to differentiate the imagery condition from the "resting" state, e.g. when users are not controlling their brain activity in order to generate any particular brain pattern. Almost each BCI system nowadays uses this state, mostly to provide the users a break between the trials. However, several papers [START_REF] Power | Towards a system-paced near-infrared spectroscopy brain-computer interface: differentiating prefrontal activity due to mental arithmetic and mental singing from the no-control state[END_REF][START_REF] Dyson | Sequential classification of mental tasks vs. idle state for EEG based BCIs[END_REF] use the resting state as an actual class for comparing it to the other mental imagery action. They evoke the ease of the designing of a BCI system, when considering resting state: the user needs to produce the desired brain pattern intentionally only during the periods in which he/she wants to activate the BCI, and he/she can remain in resting state at all other times.

We study the following null hypotheses that based on EEG, H1. visual observation and imagery tasks cannot be differentiated, H2. imagery of different visual stimuli cannot be differentiated, H3. observation task towards different visual stimuli cannot be differentiated, H4. observation or imagery tasks cannot be not differentiated from the rest state.

Results

We first present the obtained results on the observation tasks of two stimuli and then we discuss the results on imagery tasks. We refer to the observation task and the imagery task as "observation" and "imagery" when we talk about 2-class classification problem. We refer to observation task and imagery task as "observation-merged" and "imagery-merged" when we take a union of two tasks, e.g., we consider a classification result for observation task for the two stimuli that were present as one task and one result. This means that we collected all the trials regardless of stimuli (hammer or flower) where the task is to imagine as trials representing the 'imagery-merged' class. We do likewise for the 'observation-merged' class. Hence, the classification problem will still remain a 2 class problem, but there will be more trials per class.

Classification of observation stimuli. The Spectrally Weighted Common Spatial Patterns (SpecCSP) classifier could distinguish between two observation stimuli with around 60% classification accuracy, which however does not exceed the confidence interval upper boundary for the design (65%). In the 2-class classification between the both observation stimuli merged together versus rest, the SpecCSP classifier could distinguish between observation and rest with a 72% classification accuracy (boundary at 60% due to more trials). The results for classifying between the observation stimuli and between observation stimuli and rest are shown in Figs 1 and2. In the plots on the Figs 1 and 2 and all similar plots in this paper, the red line denotes the median of the cross-validation accuracy across the users for the method, with the upper and lower boundaries of the box denoting the 25% and 75% quantiles, respectively. The strikethrough lines are the upper bounds of the used confidence interval. The red stars denote such accuracies as were considered outliers by the Matlab's boxplot routine. We compared the five different algorithms using Friedman's non-parametric rank test with a corresponding post-hoc test [START_REF] Demšar | Statistical Comparisons of Classifiers over Multiple Data Sets[END_REF] . Further, to better understand the possible similarities in the behavior of the tested algorithms, we plotted Critical Difference (CD) images as introduced by Demšar, relying on post-hoc Nemenyi tests [START_REF] Demšar | Statistical Comparisons of Classifiers over Multiple Data Sets[END_REF] with a threshold alpha = 0.01. In the CD images, two algorithms are not significantly different if they are connected by a bold line. We relied on public R implementations to compute the tests [START_REF] Calvo | Scmamp: Statistical Comparison of Multiple Algorithms in Multiple Problems[END_REF] .

The behavior and meaning of the ERP1 and ERP2 classifiers will be discussed later. Please also refer to Table 1, "Observation VS Observation, SpecSCP" column to see the classification accuracy of observation (during cue display) of the two visual categories for each participant presented individually.

Classification of observation versus imagery task.

The SpecCSP classifier could distinguish between observation-merged task versus imagery-merged task with 71% of classification accuracy (confidence boundary at 60%). The results for classifying between the imagery categories and between observation stimuli are shown in Fig. 3. Thus, our null hypotheses H1 and H3 can be rejected.

Classification of visual imagery tasks.

The SpecCSP pipeline could distinguish between two imagery tasks with 52% classification accuracy, which is under the 65% confidence bound. In the 2-class classification between the imagery-merged task versus rest, the SpecCSP pipeline could distinguish between the two with the 77% classification accuracy (with confidence bound at 60%). The results for classifying between the imagery categories and between imagery-merged task and rest are shown in Figs 4 and5. Please also refer to Table 1, "Imagery VS Imagery, SpecSCP" column to see the classification accuracy of two imagined visual categories for each participant presented individually. Figure 6 illustrates a set of SpecCSPs filters of a single participant in the study, who obtained 65% of classification accuracy. The SpecCSPs are computed for the discrimination of visual imagery of the flower from visual imagery of the hammer. These results indicate that although it is difficult to tell the two imagery categories apart by the pipelines we are using, as the result is close to random one, the imagery segments are nevertheless distinguishable from the rest condition. Thus, the null hypothesis H2 cannot be rejected, but H4 can be rejected.

Reliability of the classification results.

In addition to comparing the classification pipelines against two trivial random classifiers and the confidence bounds, we implemented a few other controls to investigate if we could find simple, alternative explanations to the obtained accuracies.

The ERP1 and ERP2 pipelines using the Window Means algorithm were run for different time segments, ERP1 for [0, 0.8]s and ERP2 for 1,3 s, the latter like the other pipelines. The results indicate that switching from condition to condition in the experimental timeline does create event related potentials that can be discriminated from each other to some extent. I.e. if the condition is rest, the rest-onset can be discriminated from cue-display or imagery condition onsets. If the condition is observation, the cue type can be discriminated to some extent as well. The type of imagery could be predicted with much lower accuracy. However, after 1 s, this ERP-type activity has largely ceased and ERP2 working on a later time segment provides much lower accuracies. This suggests that the results obtained from the tested methods during the 1,3 s segment may not be simply due to stimulus-locked ERP activity resulting from transitions from one condition to another.

The chronological cross-validation in BCILAB mitigates accuracy biases from time-correlated EEG to some extent. To further test that the presented results are not trivially due to some slow temporal change of brain state during our experiment, we additionally split a trial of each type to two segments which were 1,2 s and 2,3 s after stimulus onset. Then, we considered these two segments as separate classes to discriminate; for example, first half of cue-display of hammer versus second half of cue-display of hammer. We tested the SpecCSP pipeline with various balanced, 2-class pairings, and obtained per-recording cross-validation accuracies from 40% to 64%. This suggests that tiny accuracy improvements over random can be obtained in our setting even if the underlying categories are not different. The implication is that the possible drift of the brain state that may segregate the first part of each trial from the second part is not well exploitable by the pipelines we test. The contrary would have given evidence that the classifiers are indeed able to use temporal drifts in the EEG.

One possible criticism is that in our experimental design, the sequence of events is always repeated in the same order. In principle it could be possible that a specific trial is discriminable because of some pre-condition residual remains in the EEG until the actual condition. A proper way to control for this would be designing a new experiment where the condition order is perfectly randomized.

ERD/S patterns in alpha band. Difference between the observation and imagery tasks was reflected in their ERD/S patterns.

Alpha activity is significantly higher during the imagery than during the observation. This significance is strong. ERPs are significant on all the channels on the visual area and though all the time windows, beginning-end of the trial; Event Related Spectral Perturbations (ERSPs) are significant for all channels on the visual area (Fig. 7).

Significant main effects for observation versus imagery were observed in all channels on the visual area (Fig. 8). This finding goes in line with the work of [START_REF] Cooper | Paradox lost? Exploring the role of alpha oscillations during externally vs. internally directed attention and the implications for idling and inhibition hypotheses[END_REF] that showed that alpha activity was significantly higher during the imagery process than during the observation one. This finding contradicts the "idling theory" that alpha power desynchronizes when users are engaged when performing cognitively demanding tasks. Klimesch [START_REF] Klimesch | EEG alpha and theta oscillations reflect cognitive and memory performance: a review and analysis[END_REF] reported a "synchronization of alpha activity during the retention period in a short term memory task". Synchronization of alpha activity was also reported by various studies [START_REF] Ray | EEG activity during cognitive processing: influence of attentional factors[END_REF][START_REF] Ray | EEG alpha activity reflects attentional demands, and beta activity reflects emotional and cognitive processes[END_REF][START_REF] Sauseng | EEG alpha synchronization and functional coupling during top-down processing in a working memory task[END_REF][START_REF] Jensen | Oscillations in the alpha band (9-12 Hz) increase with memory load during retention in a short-term memory task[END_REF][START_REF] Klimesch | EEG alpha oscillations: The inhibition-timing hypothesis[END_REF] during different cognitive tasks such as mental imagery, memorization tasks, so on.

Discussion

In the current study we explored the potential of Visual Imagery for BCIs. We studied to what extent can we distinguish two different visual imagery tasks using EEG-based Brain-Computer Interfaces to provide a broader range of reliable control tasks.

Firstly, for the observation-merged task versus imagery-merged task, we obtained the classification accuracy of 73%. This finding is further confirmed by a clear difference of alpha amplitude between imagery and observation stimuli.

Our results confirm the state of the art studies reporting that "increasing alpha desynchronization for higher memory load or task complexity was found for tasks which require constant externally directed observation, while findings for increasing alpha synchronization for higher memory load (or task complexity) have been obtained in tasks which relate to retention and manipulation of internally represented information (i.e., top-down processing)". Moreover, we could distinguish between two observation stimuli with around 60% classification accuracy. In summary, these findings suggest that observation stimuli could be further investigated for usage in a BCI paradigm. This suggestion is further supported by another finding of our experiment, as we obtained the classification accuracy of 77% between imagery task (for both stimuli) versus resting state, and the classification accuracy of 75% between observation task (for both stimuli) versus resting state. Collectively, these results are promising, as they demonstrate the potential of a BCI system with one "active" state corresponding either to imagery or observation task (as in [START_REF] Power | Towards a system-paced near-infrared spectroscopy brain-computer interface: differentiating prefrontal activity due to mental arithmetic and mental singing from the no-control state[END_REF] ).

As for the imagery versus imagery task, we obtained the classification accuracy of 52%. The difference to random accuracy is small, and this could be due to several reasons. Firstly, the selected images of hammer and daisy may be difficult to discriminate from the resulting EEG, regardless of technique. There is currently no study using these images that would prove otherwise. The reasons could be due to the nature how the neural assemblies work in the imagery case, due to volume conduction, etc. This limitation may even be user-specific taking into consideration our limited number of participants (10-30% of users cannot obtain any control using mental imagery BCIs [START_REF] Allison | Could Anyone Use a BCI[END_REF] ). Secondly, the problem might be due to our signal processing pipelines. We did not try to find alternative features to represent the data, but used well-known feature types from previous BCI studies. Another possible reason for our classification results are due to the naivety of our subjects. Almost none of them have performed a mental imagery task with BCIs before, and they only underwent a single recording session, which is not the case for most of studies that present mental imagery tasks, where users are asked to perform multiple sessions of training and recordings [START_REF] Lafleur | Quadcopter control in three-dimensional space using a noninvasive motor imagery based brain-computer interface[END_REF][START_REF] Jeunet | Predicting Mental Imagery-Based BCI Performance from Personality, Cognitive Profile and Neurophysiological Patterns[END_REF] . It should be also mentioned that we obtained the classification accuracy of around 60% for half of the subjects in our study (see Table 1), and these subjects could be seen as candidates for whom a further improvement may be possible with additional training sessions as suggested in Dyson et al. [START_REF] Pfurtscheller | Motor imagery and direct brain-computer communication[END_REF] . Although [START_REF] Pfurtscheller | Motor imagery and direct brain-computer communication[END_REF] suggested this approach for motor imagery paradigm, it could be a beneficial strategy for any mental imagery approach. Although we have chosen the images from different semantic categories, several studies [START_REF] Chao | Attribute-based neural substrates in temporal cortex for perceiving and knowing about objects[END_REF][START_REF] Mahon | Concepts and categories: a cognitive neuropsychological perspective[END_REF] showed that visual response is segregated by semantic category. We consider that the obtained results could be explained without invoking a notion of semantic categorization. The obtained result could be related to the selectivity to certain visual attributes that differentiate the two images (a rounded form of the flower, an elongated form of the hammer), as in [START_REF] Humphreys | Hierarchies, similarity, and interactivity in object recognition: "category-specific" neuropsychological deficits[END_REF][START_REF] Lloyd-Jones | Perceptual differentiation as a source of category effects in object processing: evidence from naming and object decision[END_REF] . Moreover the two images we have chosen for our study could be considered as "ecologically" user-friendly, although this introduces one of the limitations: the images were not controlled for the visual attributes such as contrast, color distribution, total amount of lightness, covered volume of visual field, etc. [START_REF] Pinto | Why is real-world visual object recognition hard?[END_REF] showed that if two classes of visual stimuli have a low amount of within-class variation, it is possible to get around 60% of correct classification.

Improving Bcis Using Visual Imagery?

In this study we found that it is possible to discriminate: (i) presence of visual imagery vs. observation, (ii) observation task towards different visual stimuli and (iii) rest vs. observation/imagery. We thus conclude that presence of visual imagery and specifically related alpha power changes are useful to broaden the range of reliable BCI strategies. But how could we use these findings to improve BCIs?

Consider BCIs we have nowadays, which are applied to different domains and applications: communication (yes/no; spellers; web browser navigation); environmental control (wheelchair control, robotics); recreation (games); creative expression (music, visual art); attention monitoring; meditation training; computational user experience (mental workload); coma detection and rehabilitation.

The nature of the BCI control rarely corresponds to the semantics of the task; for example, Galan et al [START_REF] Galán | A brain-actuated wheelchair: Asynchronous and non-invasive Brain-computer interfaces for continuous control of robots[END_REF] . propose to use word association task to turn the wheelchair right; and there are more examples of this type, as the most well studied BCI paradigm for active control remains motor imagery. BCIs usually do not highlight the directness of the mapping between the user's mental activity (e.g., imagining a melody) and the semantics of the task carried by the system (telephone rings). Such lack of logical connection may impact the performance of the task drastically [START_REF] Tan | Brain-Computer Interaction: Applying our Minds toHuman-Computer Interaction[END_REF] . A broader range of imagery strategies could help developing a broader range of reliable BCI-based control applications. Consider a BCI that detects motor imagery poorly, but reliably detects visual imagery. This BCI might be only 50% accurate if the user tries to communicate via motor imagery but 65% accurate if the user imagines an object he/she wants to manipulate. In that case the BCI could be re-configured to rely on visual imagery. Having more options for BCI control is an opportunity for users for whom classical, state of the art imagery approach (e.g. currently -motor imagery) BCIs are not successful, as it could provide them with a possibility of having another try with another type of imagery. Nowadays, this option is not much studied in the research laboratories. To the best of our knowledge, there are only works that propose to replace one limb-type of motor imagery by another (e.g., arm imagined movement is replaced by foot imagined movement [START_REF] Fruitet | Bandit Algorithms boostBrain Computer Interfaces for motor-task selection of a brain-controlled button[END_REF][START_REF] Iáñez | Mental tasks selection method for a SVM-based BCI system[END_REF] , but not one type of active imagery by another one, as the choices are very limited. The question of applications is also rising: if a user is navigating in the space, motor imagery is more preferable than visual one, but if he/she wants to use a coffee machine, than the latter could be of higher interest by imagining a cup of coffee, for example.

Study Limitations and Future Work

Our study has several limitations that need to be pointed out. As such, we can anticipate several directions of future research efforts to overcome the limitations of the present study:

• Other images should be tested as the stimuli, both close semantically but also in visual properties, such as form and color, in order to investigate the degree of generalizability of the studied paradigm. • The types of extracted features and used classifiers should be further studied to find which suit the visual modality best. • Further investigation should be performed to study the use of observation task and/or alpha activity as a potential BCI control paradigm. We plan to conduct another experiment, where the stimuli will be present to the participants during the whole duration of the trial (during observation and imagery tasks), so it will be possible to confirm if we are able to disentangle the imagery process from the observation process. • The current study and the obtained results should be considered as preliminary. We encourage the community to pursue the research efforts on investigating in more depth the visual imagery as a control signal for BCIs in general but also to replicate the current experiment to gather more insight and data for further analysis.

More generally, using visual imagery paradigm and visual observation tasks could make BCI-based systems more realistic with relation to particular tasks and more representative when it comes to evaluating the actual performance (imagining/looking at a telephone ringtone to answer a phone versus a hand movement imagery). These types of systems would go in the direction of user-centered design, essential to the design of real-life systems and yet little developed for BCIs. However, to confirm this statement, we would need to run additional online, real-time experiments.

Methods

Participants. This study included 26 right-handed participants (7 women), between 18 and 45 years old, without any reported disabilities. All had normal or corrected-to normal vision. Each participant gave informed consent to the study. The experiment was approved and carried out in accordance with the relevant guidelines, regulations and authorizations of Inria Rennes (where actual study took place) and with respect of the Declaration of Helsinki. 20/26 participants had never participated in BCI experiment before. 6 participants tried BCIs for the second time.

Stimuli.

Visual stimuli were two images: a hammer and a daisy (Fig. 9). The rationale behind this choice was the following: we took the images of the same size from different semantic categories (tool, nature), which had different color and form and concept of use. We wanted the images to be different, as it might correspondingly increase discriminable differences in the EEG data. Moreover these two images could be considered as "ecologically" user friendly (images come from the environment and not generated artificially), although this introduces one of the first limitations of the present study: the images used in the study are not controlled for the visual attributes such as contrast, color distribution, total amount of lightness, covered volume of visual field.

Our experimental protocol is based on the standard Graz BCI training protocol [START_REF] Pfurtscheller | Motor imagery and direct brain-computer communication[END_REF] . Details on the experimental paradigm are summarized in Fig. 10. Users were asked to perform successively a visual observation and a visual imagery task for 4 seconds each while staying motionless. At t = 0 s, a fixation cross was presented on the screen (baseline) for 1 second together with an audible beep. The screen remained blank for 2 seconds after the cross disappeared. At t = 3 s, one of two cues was displayed for 4 seconds. Once the cue disappeared, the screen remained blank for another 4 seconds, during which the users were asked to perform an imagery task for 4 seconds. At t = 11 s, a word REST appeared and remained on the screen for 5 seconds. It indicated the end of the trial. Finally, at t = 16 s, the word REST disappeared and the screen remained blank till the beginning of the new trial. Before the beginning of the very first trial, a baseline of 30 seconds was recorded. After each 10 th trial there was a pause with a duration between 120 and 240 seconds.

We make sure that the same observation cue is never presented two times in a row. Please refer to the video of the paper to see the experimental paradigm.

Users were asked to perform the mental task following these instructions:

1. Visual observation task: observe carefully the image you see in front of you; 2. Visual imagery task: imagine the image that was previously displayed.

Before users performed the task, they completed an overt exercise run: the users observed the two cue images and then they were asked to imagine them. The purpose of this exercise run was to familiarize the participants with the task and to ensure that they understood it and performed it according to the instructions.

During the periods when the word REST appeared on the screen, the users were instructed not to perform any type of imagery/observation tasks.

Procedure, EEG Recordings and Evaluation of Tasks. We used the electrode configuration of Iz, P7, P8, CP3, CPz, T7, T8, O1, Oz, O2, P3, Pz, P4, CP4, F7, C4, FC4, FC3, C3, FCz, F3, Fz, F8, POz, O9, O10, PO4, PO3, AFz, FPz, Cz, PO8, P8, PO10, PO7, PO9 using 2 g.tec USBAmp amplifiers. Each electrode was referenced to the left and grounded at the right mastoid. The data was filtered (0.5-100 Hz; 50 Hz notch filter), amplified and digitized (512 Hz). The whole experimental set-up (including the instruction, EEG montage, and 1 h of EEG recordings) lasted 1h20. The participants were instructed not to move. The stimuli were presented on a Dell notebook with a 15.4" TFT monitor that was positioned horizontally (flat on a table). The viewing distance was approximately 50 cm from the eyes to the center of the visual display.

This was a within-subject experiment design where the total number of trials was 80 (40 trials per class, and hence 80 in cases where two trial types are merged).

To record the data, we used an open source software OpenViBE [START_REF] Renard | An Open-Source Software Platform to Design, Test and Use Brain-Computer Interfaces in Real and Virtual Environments[END_REF] .

Signal processing. We used the freely available EEGLAB and BCILAB packages [START_REF] Delorme | New Tools for Advanced EEG Processing[END_REF] for the data analysis and classification, respectively. Note that the data was processed in two ways (data analysis and classification) and these two processing types do not have the same signal processing pipeline. In data analysis we wish the data to be as clean as possible for interpretability. However, as one of the motivations of our study was investigating the visual imagery for EEG-based BCIs, online BCI classification has to make predictions on the trials as they are received. Expert intervention or offline clean-up stages cannot be used. For this reason, we used BCILAB classification pipelines as they were defined in BCILAB, directly on the raw data. The same amount of data was used for each user in classification. No trials or channels were removed for classification (BCILAB, including SpecCSP patterns). For generating ERSPs/ERPs (in EEGLAB), e.g., for data analysis, most users have different amount of trials. Data analysis. We first bandpass filtered the signal to a frequency range of 0.1 Hz-40 Hz using a Hamming windowed FIR band-pass filter from EEGLAB and then removed the eye artifacts using Infomax Independent Component Analysis (ICA) [START_REF] Bell | An information maximisation approach to blind separation and blind deconvolution[END_REF] . For each separate recording, we visually identified 0-2 ICA components corresponding to strong, frontally localized activity patterns and removed these components from the signal by setting them to zero, followed by reconstruction of the signal. Note that the present recordings did not seem to have many during-trial eye-artifacts, possibly due to the instructions to the users. Next, we epoched the data to 4.875 second segments starting one second before each stimulus (event) onset. The last 125 ms were removed from each epoch simply to avoid overlapping event markers in the epoched data. Next, we used an iterative algorithm to remove the outlying trials and channels from each recording. The algorithm worked as follows: a high initial threshold for acceptable signal range was set, and then all epochs were marked as outliers that exceeded the specified range. If more than 20% of the epochs per channel were marked as rejected, then the channel itself was rejected. The process was iterated with a little lower threshold each time while disregarding previously rejected channels and epochs until the total number of rejected epochs exceeded 10% of the total epoch count for the dataset. The rejected epochs were dropped from further consideration and the rejected channels were restored by spherical interpolation of nearby electrodes using routines available in EEGLAB. With our data, this procedure rejected around 0-3 electrodes per dataset and around 10% of the trials in each.

For computing time/frequency power plots (ERSP, in EEGLAB), we removed the Event Related Potentials (ERPs) from the epochs by mean subtraction in the time/voltage representation. Note that we have not done any other baseline removal or normalization for the displayed plots (Figs 5 and6), as the present objective is to examine if differences are present between the two conditions in general.

Classification. In addition to statistical analysis of the EEG ERSP features, we also investigated classification of the trials of different types. For this, we applied classifiers from the BCILAB toolbox [START_REF] Delorme | New Tools for Advanced EEG Processing[END_REF] . Here we used the recorded data directly without discarding any trials or channels. We used only such preprocessing as the BCILAB classifier paradigms do by default (e.g. bandpass filtering). Out of the methods provided by the BCILAB toolbox, we chose the Spectrally Weighted CSP (SpecCSP) [START_REF] Tomioka | An iterative algorithm for spatio-temporal filter optimization[END_REF] and the Window Means paradigms (ERP2 58 ). We selected two-second long segments of each trial to represent the trial, each segment starting 1 second after the event onset to avoid possible transition effects. As the Window Means classifier is usually used to classify ERP patterns, we also used it during a [0, 800]ms segment after stimulus onset (ERP1).

SpecCSP method run with a wide spectral band of 2.5-30 Hz of the signal. This was done to provide the methods with relatively loose spectral priors. The wide band allows the Spectrally Weighted CSP the possibility to select a tighter spectral weighting in that range. For the Window Means (ERP classifiers), we used 0.1-15 Hz band with six consecutive time windows, each 50 ms long and starting at 250 ms after the segment start. We used Logistic Regression as the classification technique for SpecCSP pipeline. We also created two trivial classification pipelines, one predicting the training set majority class label ('majority') and the other outputting random predictions using class weights from the training fold class label distribution ('rand'). In several plots, we include the results of these control pipelines. The main intent is to visualize to what extent the real classification pipelines deviate from random baseline behavior.

The accuracies we report were obtained by using 10-fold chronological cross-validation from BCILAB, with the margin width set to 5 trials. We used the chronological cross-validation to avoid nearby trials ending up in both train and test folds. We did this in order to reduce possible bias due to time-correlations between neighboring EEG trials.

To double-check if the classification results are significantly different from what could be achieved by chance, we follow Muller-Putz et al. [START_REF] Müller-Putz | Better than Random? A closer look on BCI results[END_REF] . They propose that the reported accuracies should be compared against the upper bound of a confidence interval around the expected accuracy of a random classifier. Accuracy averages inside the confidence interval cannot be rejected from being essentially random. The interval bounds depend on the amount of trials in the experimental design. In the accuracy plots we present, a horizontal line denotes the upper boundary for the confidence interval with a threshold α = 0.01 as obtained from Muller-Putz et al. [START_REF] Müller-Putz | Better than Random? A closer look on BCI results[END_REF] .

Conclusion

This study investigated the use of Visual Imagery for Brain-Computer Interfaces. We studied to what extent can we distinguish mental processes of observing and imagining two different stimuli in visual perception using EEG-based BCI system. 26 subjects were instructed to alternatively and selectively observe one of two visual stimuli (a flower or a hammer) and mentally imagine one of them following a visual cue. We investigated the EEG correlates of these tasks and analyzed the classification accuracies for visual imagery versus observation of visual stimuli but also versus rest. We found that it is possible to discriminate: (i) visual imagery vs observation task, (ii) observation directed towards different visual stimuli and (iii) rest vs. observation/imagery. We thus conclude that presence of visual imagery and specifically related alpha power changes are useful to broaden the range of reliable BCI control strategies.

Figure 1 .

 1 Figure 1. Left. Classification of observation tasks (during cue display) of the two visual categories. Right. Comparison of all classifiers against each other with the Nemenyi test. Groups of classifiers that are not significantly different are connected.

Figure 2 .

 2 Figure 2. Left. Classification of observation task versus rest. Right. Comparison of all classifiers against each other with the Nemenyi test. Groups of classifiers that are not significantly different are connected.

Figure 3 .

 3 Figure 3. Left. Classification of observation-merged task (during cue display) versus imagery-merged task. Right. Comparison of all classifiers against each other with the Nemenyi test. Groups of classifiers that are not significantly different are connected.

Figure 4 .

 4 Figure 4. Left. Classification of two imagined visual categories. Right. Comparison of all classifiers against each other with the Nemenyi test. Groups of classifiers that are not significantly different are connected.

Figure 5 .

 5 Figure 5. Left. Classification of imagery-merged task versus rest. Right. Comparison of all classifiers against each other with the Nemenyi test. Groups of classifiers that are not significantly different are connected.

Figure 6 .

 6 Figure 6. Spectrally Weighted Common Spatial Pattern Maps; a set of SpecCSPs filters of a single participant in the study, who obtained 65% of classification accuracy. The SpecCSPs are computed for the discrimination of visual imagery of the flower from visual imagery of the hammer.

Figure 7 .

 7 Figure 7.Examples of ERSP visualization of channels PO4, Iz, P4. Alpha activity being significantly higher during the imagery task than during the observation task. In each ERSP image, the abscissa represents the time (-500 to +3000 ms), while the ordinate represents the frequency (from 3 to 40 Hz), the red color indicates power increase with respect to the baseline (dB), while the blue color the power decrease (dB).

Figure 8 .

 8 Figure 8. Alpha activity is significantly higher during the imagery task than during the observation task, here from 770 ms till 830 ms. The black dots represent the electrode positions.

Figure 9 .

 9 Figure 9. Two visual stimuli used in the current experiment: a flower and a hammer.

Figure 10 .

 10 Figure 10. Experimental paradigm with two possible visual stimuli, a hammer and a flower. The duration of the each phase of the trial is indicated above the image, the description of what was happening during each moment of time is indicated below the image.

Subject number Imagery VS Imagery, SpecCSP, % Observation VS Observation, SpecCSP, %

	1	0.4833	0.4667
	2	0.6333	0.8667
	3	0.6333	0.8
	4	0.5431	0.5778
	5	0.5319	0.5194
	6	0.5306	0.4306
	7	0.5167	0.6403
	8	0.5542	0.6056
	9	0.5306	0.5194
	10	0.5444	0.5458
	11	0.7153	0.7667
	12	0.5056	0.5556
	13	0.6889	0.6319
	14	0.4806	0.6153
	15	0.6403	0.5958
	16	0.6667	0.7139
	17	0.5069	0.6764
	18	0.5069	0.7028
	19	0.6194	0.6292
	20	0.5181	0.6694
	21	0.4819	0.5292
	22	0.5556	0.6778
	23	0.5681	0.6194
	24	0.4806	0.6542
	25	0.5097	0.6083
	26	0.5319	0.4319
	Mean value	0.5594	0.6096

Table 1 .

 1 The first column represents the subject number, the second column -classification accuracy of two imagined visual categories, and the third column -classification accuracy of observation (during cue display) of the two visual categories.

Scientific REPoRTS | (2018) 8:13222 | DOI:10.1038/s41598-018-31472-9

Acknowledgements

This research project was funded by CominLabs project SABRE.

Data Availability

The datasets generated during and/or analyzed during the current study are available from the corresponding author on request.

Author Contributions

N.K. designed the experiment and performed it with the participants. All authors discussed the experiment. J.L. and N.K. analysed data, N.K. wrote the paper, J.L. completed one section of the paper, the full paper was read, commented and checked by both authors with the remarks of A.L.

Additional Information

Competing Interests: The authors declare no competing interests.

Publisher's note: Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.


published or not. The documents may come

The tools made from wild boar canine in the French

Mesolithic: technological and functionnal study