Amine Balafrej
email: amine.balafrej@mines-nantes.fr

Anastasia Paparrizou
email: paparrizou@lirmm.fr

Multi-Armed Bandits for Adaptive Constraint Propagation *

Adaptive constraint propagation has recently received a great attention. It allows a constraint solver to exploit various levels of propagation during search, and in many cases it shows better performance than static/predefined. The crucial point is to make adaptive constraint propagation automatic, so that no expert knowledge or parameter specification is required. In this work, we propose a simple learning technique, based on multiarmed bandits, that allows to automatically select among several levels of propagation during search. Our technique enables the combination of any number of levels of propagation whereas existing techniques are only defined for pairs. An experimental evaluation demonstrates that the proposed technique results in a more efficient and stable solver.

Introduction

Constraint propagation is an essential component for efficiently solving constraint satisfaction problems (CSPs). Due to its ability to reduce the search space, constraint propagation is considered as the reason for the success and spread of Constraint Programming (CP) in solving many large-scale, real-world problems. Since the early 70's, CP research has provided a wide range of effective, either general-purpose or specialized propagation techniques. Despite this big variety, CP solvers need a expert user to tune the solver so that it becomes more efficient. In addition, solvers are constraint oriented, in the sense that they associate a specialized propagation for each type of constraint. On the other hand, the drawback of this design, is that they overlook the general picture of the problem (i.e., structural dependencies, constraint intersections) as well as the internal operations that occur during search. For example, in many cases, propagation effects indicate a need for changing the ordering in variable selection (e.g., domain wipeouts in dom/wdeg heuristic [Boussemart et al., 2004]).

This work aims at developing a simple framework that can learn the right combination of propagation levels during solving (online). It is based on a light learning technique, called multi-armed bandits (MAB), that was inspired by the slot machines in casinos and the problem that a gambler has to decide which machines to play, in which order and how many times to play each one. Each machine, after being used, returns a reward from a distribution specific to that machine. The goal is to maximize the sum of rewards obtained through a sequence of plays [Gittins, 1989].

We use a MAB model to select the right level of propagation (also called level of consistency) to enforce at each node during the exploration of the search tree. We specify a simple reward function and the upper confidence bound (UCB) to estimate the best arm, namely the best consistency to apply. An experimental evaluation on various benchmark classes shows that the proposed framework, though being simple and preliminary, results in a more efficient and stable solver. We provide a clear evidence that the proposed adaptive technique is able to construct the right combination of the available consistency algorithms of a solver. It can be much more efficient than any level of consistency alone. The MAB framework as proposed here does not require any training or information from preprocessing and can improve its decision vigorously during search.

Related Work

Although CP community has provided a wide range of efficient propagation techniques, standard solvers do not adjust the propagation level depending on the characteristics of the problem. They either preselect the propagator or use costs and other measures to order the various propagation techniques. In [START_REF] Schulte | [END_REF], some state-of-theart methods are presented to order propagation techniques in well known solvers (e.g., Gecode, Choco).

There has been a significant amount of work on adaptive solving through the use of machine learning (ML) methods, either with a training phase or without. The goal of the learning process is to automatically select or adapt the search strategy, so that the performance of the system is improved. There are two main approaches that have been studied. In the first case, a specific strategy (e.g., a search algorithm or a specific solver) is selected automatically among an array of available strategies, either for a whole class of problems or for a specific instance. Such methods, called portfolios, perform the learning phase offline, on a training set of instances. Portfolios have been initially proposed for SAT (e.g., SATzilla [START_REF] Xu | [END_REF]) and then for CSPs (e.g., CPHydra [O'Mahony et al., 2008], Proteus [START_REF] Hurley | [END_REF]). In the second case, a new strategy can be synthesized (e.g., a combination of search algorithm and heuristics) through the use of ML [START_REF] Epstein | [END_REF]Xu et al., 2009]. The learning phase is again performed as a preprocessing. On the contrary, in [START_REF] Loth | [END_REF], multi-armed bandits are exploited to select online (i.e., without training phase) which node of a Monte Carlo Tree Search (MCTS) to extend. In that paper, the Bandit Search for Constraint Programming (BaSCoP) algorithm adapts MCTS to the CSP search to explore the most promising regions according to a specified reward function.

There has been little research on learning strategies for constraint propagation. In [START_REF] Epstein | [END_REF], ML is used to construct a static method for the pre-selection between Forward Checking and Arc Consistency. The work in [START_REF] Kotthoff | [END_REF] evaluates ensemble classification for selecting an appropriate propagator for the alldifferent constraint. But this is again done in a static way prior to search.

Recent papers have shown an increasing interest for adapting the propagation level through the use of heuristic methods. The initial approach, appeared in [Stergiou, 2008], showed many advantages in favor of heuristics. They are both inexpensive to apply and dynamic, based on the actual effects of propagation during search (i.e., domain wipeouts (DWOs), value deletions). This approach was later improved by a more general model for n-ary constraints that does not require any parameter tuning [START_REF] Paparrizou | [END_REF]. This direction of research has led to the parameterized local consistency approach for adjusting the level of consistency depending on a stability parameter over values [Balafrej et al., 2013;Woodward et al., 2014]. Parameterized local consistencies choose to enforce either arc consistency or a stronger local consistency on a value depending on whether the stability of the value is above or below a given threshold. Interestingly, they propose ways to dynamically adapt the parameter, and thus the level of local consistency, during search. In [START_REF] Balafrej | [END_REF], the number of times variables are processed for singleton tests on their values is adapted during search. The learning process is based on measuring a stagnation in the amount of pruned values. Thus, we have on the one hand the use of ML techniques that are heavy to be applied online and can be mainly used prior to search (static). Hence the actual effect during search is ignored. In addition, the vast majority of works in this direction were proposed for adapting the variable ordering heuristics, not for adapting the propagation level during search. On the other hand, we have heuristics methods to automatically adapt consistency during search, but heuristics are only defined for two levels of consistency (i.e., a weak and a strong one). This limits their applicability.

The technique we propose in this paper fills the gap in the literature by proposing a ML approach for selecting automatically and dynamically among any number of propagation levels, without the need for training.

Background

A constraint network is defined as a set of n variables X = {x 1 , ..., x n }, a set of domains D = {D(x 1 ), ..., D(x n )}, and a set of e constraints C = {c 1 , ..., c e }. Each constraint c k is defined by a pair (var(c k ), sol(c k )), where var(c k ) is an ordered subset of X , and sol(c k ) is a set of combinations of values (tuples) satisfying c k .

The technique presented in this paper is totally generic in the sense that it can be used with any set of local consistencies. In our experiments, we use arc consistency (AC), max restricted path consistency (maxRPC), and partition one arc consistency (POAC). We give the necessary background to understand them. As maxRPC is defined for binary constraints only, we simplify the notations by considering that all constraints are binary. A binary constraint between x i and x j will be denoted by c ij , and Γ(x i ) will denote the set of variables x j involved in a constraint with x i .

A value

v j ∈ D(x j ) is called an arc consistent (AC) sup- port for v i ∈ D(x i ) on c ij iff (v i , v j ) ∈ sol(c ij ). A value v i ∈ D(x i ) is arc consistent (AC) if and only if for all x j ∈ Γ(x i ) v i has an AC support on c ij . A network is arc consistent if all the
values of all its variables are arc consistent. We denote by AC(N ) the network obtained by enforcing arc consistency on N .

A value v j ∈ D(x j ) is a max restricted path consistent (maxRPC) support for v i ∈ D(x i ) on c ij if and only if it is an AC support and the tuple (v i , v j ) can be extended to any third variable x k while satisfying c ik and c jk . A value

v i ∈ D(x i ) is maxRPC iff for all x j ∈ Γ(x i ) v i has a maxRPC support v j ∈ D(x j ) on c ij . A network is maxRPC if all the values of all its variables are maxRPC. Given a constraint network N = (X , D, C), a value v i ∈ D(x i ) is partition-one-AC (POAC) iff AC(N ∪ {x i = v i })
does not have empty domains, and ∀j ∈ 1..n, j = i, ∃v j ∈ D(x j ) such that v i ∈ AC(N ∪ {x j = v j }). A network is POAC if all the values of all its variables are POAC.

Multi-Armed Bandits for Adaptive Constraint Propagation

We describe a simple framework for adaptive propagation based on Multi-Armed Bandits (MAB). The successive selection of a consistency level during search is a sequential decision problem and as such, it can be represented as a multiarmed or k-armed (for k different consistencies) bandit problem. One needs to select amongst k consistencies to enforce in order to maximize the cumulative reward by selecting each time the best one. Initially, such a choice is taken under uncertainty, since the underlying reward distributions are unknown.

Later in the process, potential rewards are estimated based on past observations. The more the search tree grows, the more knowledge we acquire and the better decisions we make.

The critical question that needs to be addressed in bandit problems is related to the tradeoff between "exploitation" of the arm with the greatest expected reward (based on the knowledge already acquired) and "exploration" of other, currently sub-optimal arms to further increase knowledge about them and which may become superior in the future. This is related to the exploitation vs. exploration dilemma in reinforcement learning.

The multi-armed bandit model

We use the multi-armed bandit problem to learn what is the appropriate level of consistency to enforce during solving a CSP. We call MAB selector the ML component that decides a level of consistency to use. We can have such a selector for each constraint, for each variable, or, more coarsely, for each level of the search tree. The selector is based on a model defined over:

• A set of k arms {LC 1 , . . . , LC k }. Each arm corresponds to an algorithm that enforces a specific level of local consistency.

• A set of rewards R i (j) ∈ R, 1 ≤ i ≤ k, j ≥ 1, where R i (j)
is the reward delivered when an arm LC i has been chosen at time j.

The reward function can be any measure that reflects the performance or a criterion that indicates the appropriate arm. The performance can be either positive (e.g., values removed) or negative (e.g., CPU time).

In MAB models, we must define a policy to choose the next arm based on the sequence of previous trials. It is important not to discard an arm forever to ensure that any arm that could become later optimal is not omitted in favor of other currently sub-optimal arms. As a result, it is useful to know the upper confidence bound (UCB) that any given arm will be optimal.

Since the model cannot always make the best decision, its expected loss or regret is considered after m times. Auer et al. [Auer and Cesa-Bianchi, 2002], propose a simple UCB policy that has an expected logarithmic growth of regret uniformly over m (not just asymptotically) without any prior knowledge regarding the reward distributions. Their policy, called UCB1, selects the arm i that maximizes:

ρ(i) = Ri + 2 ln m m i (1)
where Ri is the mean of the past rewards of the i arm, m i is the number of times arm i was selected and m is the current number of all trials. The reward term Ri encourages the exploitation of local consistencies with higher-rewards, while the 2 ln m mi term promotes the exploration of the less selected local consistencies.

The literature contains more elaborated versions of multiarmed bandits where additional parameters allow to insist more on exploration or exploitation depending on the context. As one of our goal is to assess the simplicity of this direction of research, we use the most basic regret policy defined in equation 1, where no parameter tuning is required.

A MAB selector for adapting consistency online

When designing a MAB selector we have to define the reward function and to decide the granularity at which the MAB operates. Concerning the granularity, there exist various natural ways to attach MAB selectors to a CP solver. We could decide to attach a MAB selector per variable in the network, per constraint, etc. Depending on the place where a MAB selector is attached, the most natural parameters used for the reward function may change.

In this preliminary work, we follow an observation made by Debruyne. In [Debruyne, 1998], he observed that changing the level of consistency with the depth in the search tree can improve search significantly. By depth, we mean the number of variables assigned. 1 In his work, Debruyne was manually tuning the solver to change the level of consistency from AC to maxRPC or maxRPC to AC at predefined depths depending on the class of problems, based on his own experience. We then decided to define a MAB model where we have a MAB selector at each depth in the search tree. Our goal is to show that the MAB selectors will learn by themselves which level of local consistency to use at which depth.

Once the places to attach MAB selectors is decided, we have to define the reward function. We chose to define a reward function that takes into account the actual CPU time needed to explore the subtree rooted at this depth once the decision of which local consistency to use has been taken by the MAB selector of the given depth.

For each depth in the search tree we have a separate MAB selector, with its own time parameter j. We denote by T i (m) the CPU time needed to enforce LC i at the mth visit of a node at the given depth plus the time to explore the subtree rooted there. (T i (m) is not defined if this is not LC i that has been chosen at time m.) The reward R i (j) is computed based on the performance of LC i at time j compared to performance of all consistencies at previous visits at this depth.

R i (j) = 1 - T i (j) max i=1..k,m=1..j (T i (m)) (2)
Formula 2 is normalized so that R i (j) ∈ [0, 1]. Indeed, remember that ρ in Formula 1 computes the sum of rewards.

The backtrack search algorithm that uses this MAB model calls the MAB selector of a given depth h each time it instantiates a variable at depth h in the search tree. The search algorithm progressively builds a search tree and applies a local consistency LC i at depth h guided by results of previous choices at the same depth.

These are the steps that the algorithm follows after each variable assignment x ← a:

1. We call the MAB selector of the depth at which x ← a occurs. 2. We select the LC i that maximizes ρ(i). 3. We store the current time startT ime[depth] of the machine. 4. LC i is executed on that node. 5. When backtracking to that node, we read the current time endT ime of the machine and we update the reward R i (j). T i (j), which was defined as the sum of the CPU time required to enforce LC i after the assignment of x plus the CPU time required to explore the resulting subtree is simply obtained by endT ime -startT ime [depth].

Experimental Evaluation

We ran experiments on problem classes from real world applications and classes following a regular pattern involving a random generation (REAL and PATT in www.cril.univartois.fr/˜lecoutre/benchmarks.html). The algorithms were implemented with a CP solver written in Java and tested on an 2.8 GHz Intel Xeon processor and 16 GB RAM. A cut-off of 3,600 seconds was set for all algorithms and all instances. We used the dom/deg heuristic for variable ordering and lexicographic value ordering. We used three levels of consistency: AC (AC2001 [START_REF] Bessiere | [END_REF]), maxRPC (maxRPC3 [Balafoutis et al., 2011]), and POAC (POAC1 [START_REF] Balafrej | [END_REF]). For AC2001 and maxRPC3 we used their residual versions ( [START_REF] Lecoutre | [END_REF]) to avoid maintaining AC and maxRPC supports during search. From these three consistencies we built six solving methods: Three of them maintain a single local consistency during the whole search (AC, maxRPC or POAC). The three others are adaptive methods using a MAB selector to decide which local consistency to apply among {AC, maxRPC}, {AC, POAC} and {AC, maxRPC, POAC}, respectively denoted by AC-maxRPC, AC-POAC and AC-maxRPC-POAC. Table 1 (except last column) shows the results of the six solving methods where the adaptive ones use a MAB selector for each depth in the search tree and a reward function based on CPU time as described in Section 4.2. Comparing these six methods on the instances solved by all of them, we observe that overall, adaptive methods are faster than methods maintaining a single consistency. This is especially true on difficult problems. The row 'Total' (last row of the table) shows that all adaptive methods have a total sum of CPU time smaller than the CPU time of methods maintaining a single consistency. The adaptive method using the three consistencies (AC-maxRPC-POAC) is the fastest. The total number of solved instances confirms this behavior as adaptive methods including a strong consistency LC solve more instances than those maintaining LC alone. Once more, AC-maxRPC-POAC is the best, solving 309 instances among the 313 tested.

When looking at the results in more details, we observe that in a few cases, when one of the local consistencies behaves significantly worse than the others (such as POAC in graph), the MABs including it are penalized. The reason is that UCB forces the MABs to select this bad consistency for exploration purposes. It takes some time to learn not to select it.

In the last column of Table 1, we report the results of an experiment done to assess the learning capabilities of our MAB selectors. The solver uses the three consistencies AC, maxRPC, and POAC, but instead of using a MAB selector to select the right consistency to apply at a node, it selects one consistency randomly. Thanks to the use of three consistencies, this baseline algorithm has a good behavior. It is better than any single consistency and also better than MAB selectors with only two consistencies. But when the MAB also uses three consistencies, it has a significantly better behavior (faster and solving more instances).

In Figure 1, we report the cactus plot of the number of instances solved per method while the time limit increases. What we see on the zoom on the first seconds of time is that AC is the one that solves the more instances in less than 5 seconds and POAC the less. When the time limit is between 5 seconds and approximately 200 seconds, maxRPC is the one that solves more instances while AC deteriorates. Among the methods maintaining a single consistency, POAC is the one that solves the fewest instances until we reach a time limit of 500 seconds. After 500 seconds, AC becomes the worst among all and it remains the worst until the cutoff of 3600 seconds. Concerning the adaptive methods, AC-maxRPC is second best in the zone where maxRPC is the best (5-200 seconds). But as time increases, AC-POAC and AC-maxRPC-POAC solve more instances than the other methods, AC-maxRPC-POAC being the clear winner by solving more instances than all others from 200 seconds until the cutoff.

The important information that this cactus plot gives us, is that, on very hard instances, the adaptive methods are never worse than any consistency they include (e.g., AC-maxRPC is close to maxRPC and better than AC) and they can even be superior to any consistency they include (e.g., AC-POAC solves constantly more instances than AC or POAC). This means that given an instance to solve, they not only understand which consistency is the best overall, but they benefit from the temporary superiority of another consistency. We also ran Adaptive POAC [START_REF] Balafrej | [END_REF] on the same classes. Adaptive POAC is generally faster than MABs on easy instances. On hard instances, Adaptive POAC is far slower than MABs containing POAC: it only solves 296 instances overall, that is, more than single consistencies and AC-maxRPC, but less than AC-POAC, AC-maxRPC-POAC, and AC-maxRPC-POAC(rand).

Discussion

Simplicity of use and low computation cost are good reasons to choose multi-armed bandits for adapting consistency during search. Low computation cost is an essential property for an online technique. Another reason is that successive choices of a consistency at a given depth yield rewards that are independent. This ensures that there is no hidden correlation that a MAB selector could not learn (as MABs only learn independent rewards). In a setting where we would learn sequences of choices of local consistencies on a sequence of successive depths, a Q-learning framework would probably be more relevant [START_REF] Sutton | [END_REF]Xu et al., 2009].

The MAB model as defined in equations 1 and 2 has originally been proposed for stationary arms, that is, arms for which the reward received when playing an arm follows a probability distribution that remains unchanged along the plays. Under this condition, UCB1 ensures that the average regret converges to zero with probability 1, that is, UCB1 ensures that the optimal arm is played exponentially more often than any other arm. In our setting, however, we cannot guarantee that arms are stationary because the reward of a local consistency may change as search progresses. Several versions of UCB have been proposed to deal with environments that change over time. However, it is recognized that the basic UCB has low probability to show a worst-case behavior when applied to such changing environments [START_REF] Fialho | [END_REF]. In addition, versions of UCB that deal with changing environments require some parameter tuning, such as the decay factor or the length of time window. As observed in [START_REF] Fialho | [END_REF], a bad configuration of the parameters can produce too much forgetting when the environment does not change as fast as expected. For these reasons, in this first attempt to exploit MAB in adaptive propagation, we chose to remain on the simple version of UCB where there is no parameter to tune before use.

To illustrate this ability of UCB to adapt despite dynamic environment, we focus on the internal behavior of our MABs. Figure 2 displays the internal behavior of the MAB selector AC-maxRPC-POAC at several depths (77, 104, 155) when solving the instance 3-insertion-4-3. As time increases, the values of the mean reward Ri and the ratio of calls to each consistency are plotted. (The ratio is the number of times LC i was selected divided by total number of times the selector was called.) On all three graphs we observe that MAB selects more frequently the local consistency with the highest mean reward. On the top graph we see that at depth 77, POAC is learned as the best and is then chosen the most often. On the middle graph we see that in the begining, POAC is preferred to AC and maxRPC because its mean reward is the highest. After 6000 time steps, maxRPC suddenly starts increasing its reward resulting in being quickly promoted, as the steep inclination of its ratio curve shows. This both illustrates that rewards are non stationary and that our simple UCB is able to detect it. Finally, on the bottom graph we see that at depth 155 (close to the leaves) things are less clear but AC tends to be the preferred one, confirming an observation made in [Debruyne, 1998].

Figure 2 shows that MAB learns what is the most efficient consistency to enforce at a given time during search. AC-maxRPC-POAC solved this instance in 1, 661 seconds, POAC in 4, 602 seconds and both AC and maxRPC failed to solve it in 4 hours. The adaptive technique was able to be faster than the best consistency alone (here POAC), be-cause it is able to enforce the right consistency at the right node during search. MAB selectors can construct the right combination of the available propagation levels of a solver, adapted to each instance, without any preprocessing knowledge or other information prior to search. These first results show the potentiality of a CP solver that is able to exploit any algorithm that it has in its arsenal without having the knowledge of when/where to use it. This is another step in the direction of an autonomous solver.

Conclusion

In this paper, we have introduced a simple framework for adaptive constraint propagation based on multi-armed bandits learning. The proposed framework allows the automatic selection of the right propagation technique among several, overcoming the strong limitation of previous works. Due to its light learning mechanism, our framework can be applied dynamically, considering the effects of propagation during search. The experiments on various benchmark classes showed that the proposed framework increases the efficiency and robustness of a CP solver.

Figure 1 :

 1 Figure 1: Number of instances solved per algorithm when the time allowed increases (cactus plot).

Figure 2 :

 2 Figure 2: Instance 3-insertion-4-3: Mean rewards and ratios of each consistency at depths 77 (top), 104 (middle), and 155 (bottom).

Table 1 :

 1 Sum of CPU times (in sec.) and #solved instances per class and per algorithm.

			AC	maxRPC	POAC	AC-maxRPC	AC-POAC	AC-maxRPC-POAC	AC-maxRPC-POAC(rand)
		#solved	10	10	10	10	10	10	10
	Qwh-10	by all (10)	0.13	0.90	1.70	0.98	1.17	1.10	0.88
		total (10)	0.13	0.90	1.70	0.98	1.17	1.10	0.88
		#solved	10	10	10	10	10	10	10
	Qwh-15	by all (10)	57.05	101.58	64.99	90.43	43.38	43.04	23.82
		total (10)	57.05	101.58	64.99	90.43	43.38	43.04	23.82
		#solved	9	9	10	9	10	10	10
	Qwh-20	by all (9)	10,462.54	8,154.69	1,887.81	7,316.04	1,206.34	1,322.77	875.43
		total (10)	-	-	5,216.10	-	2,498.25	2,747.93	1,908.37
		#solved	0	0	1	0	0	1	0
	Qwh-25	by all (0)	0.00	0.00	0.00	0.00	0.00	0.00	0.00
		total (1)	-	-	1,097.18	-	-	2,756.81	-
		#solved	15	14	15	15	15	15	15
	Qcp-10	by all (14)	1,214.43	3,771.64	3,136.48	1,535.67	919.30	1,011.78	1,351.31
		total (15)	2,446.10	-	6,672.00	3,064.59	1,792.01	2,472.14	2,985.48
		#solved	11	11	14	12	15	15	15
	Qcp-15	by all (11)	5,314.59	5,984.78	1,405.99	4,895.20	762.87	779.71	750.86
		total (15)	-	-	-	-	5,559.25	5,752.51	5,302.56
		#solved	0	0	1	0	1	1	1
	Qcp-20	by all (0)	0.00	0.00	0.00	0.00	0.00	0.00	0.00
		total (1)	-	-	3,463.16	-	425.46	2,085.15	2,259.63
		#solved	21	21	18	21	21	21	21
	fullins	by all (18)	83.64	93.56	5,662.63	74.39	1,722.36	941.24	1,815.86
		total (21)	295.18	273.65	-	248.83	7,707.86	4,536.69	8,472.53
		#solved	16	16	15	16	16	17	16
	K-insertion	by all (15)	763.65	993.19	2,015.41	875.71	969.95	660.66	646.94
		total (17)	-	-	-	-	-	5,475.87	-
		#solved	4	8	8	8	8	8	8
	mug	by all (4)	0.00	0.01	0.80	0.01	0.39	0.27	0.24
		total (8)	-	523.43	115.77	2,233.90	142.03	115.73	177.32
		#solved	12	12	11	12	11	11	11
	myciel	by all (11)	167.19	273.72	1,815.73	204.77	607.56	486.10	573.75
		total (12)	944.54	1,622.67	-	1,279.06	-	-	-
		#solved	7	7	7	7	7	7	7
	driver	by all (7)	45.74	225.61	125.14	130.11	121.18	98.94	93.83
		total (7)	45.74	225.61	125.14	130.11	121.18	98.94	93.83
		#solved	14	14	12	14	13	14	14
	graph	by all (12)	1.31	274.28	9,420.51	23.33	6,289.40	3,192.09	3,121.45
		total (14)	1.99	288.66	-	32.63	-	6,019.48	6,358.70
		#solved	11	11	9	11	11	11	11
	scen	by all (9)	3.46	12.20	1,630.91	9.91	915.99	469.27	541.49
		total (11)	18.36	47.07	-	36.99	6,157.79	3,595.95	4,709.37
		#solved	9	9	9	9	9	9	9
	sub	by all (9)	0.29	0.02	0.40	0.02	0.42	0.02	0.05
		total (9)	0.29	0.02	0.40	0.02	0.42	0.02	0.05
		#solved	5	6	9	6	10	10	8
	graphMod	by all (5)	31.51	1.12	984.18	1.04	538.94	296.68	1,508.19
		total (10)	-	-	-	-	1,830.11	1,300.54	-
		#solved	3	9	9	8	9	9	9
	scenMod	by all (3)	0.37	1.31	193.59	1.04	83.67	57.48	56.93
		total (9)	-	21.58	3,182.17	-	1,694.72	1,017.94	1,979.75
		#solved	8	7	2	7	2	7	5
	fapp02	by all (2)	0.63	1.05	0.63	1.44	0.58	1.58	0.81
		total (10)	-	-	-	-	-	-	-
		#solved	5	6	6	5	5	6	5
	e0ddr1	by all (5)	35.92	11.15	1,038.62	10.47	525.02	302.13	272.21
		total (6)	-	271.36	3,958.70	-	-	3,783.61	-
		#solved	7	6	7	6	7	7	7
	e0ddr2	by all (6)	1,859.00	425.52	2,143.04	720.36	1,256.85	996.04	717.12
		total (7)	1,859.14	-	2,492.11	-	1,493.95	1,106.86	819.77
		#solved	100	100	100	100	100	100	100
	Bqwh-18	by all (100)	5,539.53	2,376.40	696.34	4,677.91	423.80	360.47	386.93
		total (100)	5,539.53	2,376.40	696.34	4,677.91	423.80	360.47	386.93
		#solved	10	10	10	10	10	10	10
	BlackHole-4-4	by all (10)	18.94	337.52	371.11	48.02	46.34	82.80	273.99
		total (10)	18.94	337.52	371.11	48.02	46.34	82.80	273.99
		#solved	287	296	293	296	300	309	302
	Total	by all (270)	25,599.92	23,040.25	32,596.01	20,616.86	16,435.51	11,104.16	13,012.12
		Total (313)	-	-	-	-	-	-	-

In

2-way branching, x = a is considered as an assignment whereas the refutation x = a is not.

Acknowledgments

We would like to thank Nadjib Lazaar for his help on multiarmed bandits.

* This work was supported by the EU under the project "Inductive Constraint Programming", contract FP7 FET-Open 284715.


Aristide C Y Tossou
email: aristide@chalmers.se

Christos Dimitrakakis

Algorithms for Differentially Private Multi-Armed Bandits

We present differentially private algorithms for the stochastic Multi-Armed Bandit (MAB) problem. This is a problem for applications such as adaptive clinical trials, experiment design, and user-targeted advertising where private information is connected to individual rewards. Our major contribution is to show that there exist (ǫ, δ) differentially private variants of Upper Confidence Bound algorithms which have optimal regret, O(ǫ -1 + log T ). This is a significant improvement over previous results, which only achieve poly-log regret O(ǫ -2 log 2 T ), because of our use of a novel intervalbased mechanism. We also substantially improve the bounds of previous family of algorithms which use a continual release mechanism. Experiments clearly validate our theoretical bounds.

Introduction

The well-known stochastic K-armed bandit problem [START_REF] Thompson | On the Likelihood that One Unknown Probability Exceeds Another in View of the Evidence of two Samples[END_REF]Robbins and others 1952) involves an agent sequentially choosing among a set of arms A = {1, . . . , K}, and obtaining a sequence of scalar rewards {r t }, such that, if the agent's action at time t is a t = i, then it obtains reward r t drawn from some distribution P i with expectation µ i E(r t | a t = i). The goal of the decision maker is to draw arms so as to maximize the total reward T t=1 r t obtained. This problem is a model for many applications where there is a need for trading-off exploration and exploitation. This occurs because we only see the reward of the arm we pull. An example is clinical trials, where arms correspond to different treatments or tests, and the goal can be to maximise the number of cured patients over time while being uncertain about the effects of treatments. Other problems, such as search engine advertisement and movie recommendations can be formalised similarly [START_REF] Pandey | Handling advertisements of unknown quality in search advertising[END_REF].

It has been previously noted [START_REF] Jain | Differentially private online learning[END_REF][START_REF] Thakurta | nearly) optimal algorithms for private online learning in full-information and bandit settings[END_REF][START_REF] Mishra | nearly) optimal differentially private stochastic multi-arm bandits[END_REF]Zhao et al. 2014) that privacy is an important consideration for many multi-armed bandit applications. Indeed, privacy can be easily violated by observing changes in the prediction of the bandit algorithm. This has been demonstrated for recommender systems such as Amazon by [START_REF] Calandrino | you might also like: " privacy risks of collaborative filtering[END_REF]) and for user-targeted advertising such as Facebook by [START_REF] Korolova | Privacy violations using microtargeted ads: A case study[END_REF]. In both cases, with a moderate amount of side information and by tracking changes in the output of the system, it was possible to learn private information of any targeted user.

Differential privacy (DP) [START_REF] Dwork | Differential privacy[END_REF] provides an answer to this privacy issue by making the output of an algorithm almost insensitive to any single user information. That is, no matter what side information is available to an outside observer, he can not have more information about a user than he already had by observing the outputs released by the algorithm. This goal is achieved by formally bounding the loss in privacy through the use of two parameters (ǫ, δ) as shown in Definition 2.1.

For bandit problems, differential privacy implies that the actions taken by the bandit algorithm do not reveal information about the sequence of rewards obtained. In the context of clinical trials and diagnostic tests, it guarantees that even an adversary with arbitrary side information, such as the identity of each patient, cannot learn anything from the output of the learning algorithm about patient history, condition, or test results.

Related Work

Differential privacy (DP) was introduced by [START_REF] Dwork | Calibrating noise to sensitivity in private data analysis[END_REF]; a good overview is given in [START_REF] Dwork | The algorithmic foundations of differential privacy[END_REF]. While initially the focus in DP was static databases, interest in its relation to online learning problems has increased recently. In the full information setting, [START_REF] Jain | Differentially private online learning[END_REF]) obtained differentially private algorithms with near-optimal bounds. In the bandit setting, [START_REF] Thakurta | nearly) optimal algorithms for private online learning in full-information and bandit settings[END_REF] were the first to present a differentially private algorithm, for the adversarial case, while (Zhao et al. 2014) present an application to smart grids in this setting. Then, [START_REF] Mishra | nearly) optimal differentially private stochastic multi-arm bandits[END_REF] provided a differentially private algorithm for the stochastic bandit problem. Their algorithms are based on two non private stochastic bandit algorithms: Upper Confidence Bound (UCB, [START_REF] Auer | Finite time analysis of the multiarmed bandit problem[END_REF]) and Thompson sampling (Thompson 1933). Their results are sub-optimal: although simple index-based algorithms achieving O(log T ) regret exist [START_REF] Burnetas | Optimal adaptive policies for sequential allocation problems[END_REF][START_REF] Auer | Finite time analysis of the multiarmed bandit problem[END_REF], these differentially private algo-rithms additional poly-log terms in time T , as well further linear terms in the number of arms compared to the nonprivate optimal regret O(log T ).

We provide a significantly different and improved UCBstyle algorithm whose regret only adds a constant, privacydependent term to the optimal. We also improve upon previous algorithms by relaxing the need to know the horizon T ahead of time, and as a result we obtain a uniform bound. Finally, we also obtain significantly improved bounds for a variant of the original algorithm of [START_REF] Mishra | nearly) optimal differentially private stochastic multi-arm bandits[END_REF], by using a different proof technique and confidence intervals. Let's note that similarly to their result, we only make distributional assumptions on the data for the regret analysis. To ensure privacy, our algorithms do not make any assumption on the data. We summarize our contributions in the next section.

Our Contributions

• We present a novel differentially private algorithm (DP-UCB-INT) in the stochastic bandit setting that is almost optimal and only add an additive constant term (depending on the privacy parameter) to the optimal non private version. Previous algorithms had in large multiplicative factors to the optimal. • We also provide an incremental but important improvement to the regret of existing differentially private algorithm in the stochastic bandit using the same family of algorithms as previously presented in the literature. This is done by using a simpler confidence bound and a more sophisticated proof technique. These bounds are achieved by DP-UCB-BOUND and DP-UCB algorithms. • We present the first set of differentially private algorithm in the bandit setting which are unbounded and do not require the knowledge of the horizon T . Furthermore, all our regret analysis holds for any time step t.

Preliminaries

Multi-Armed Bandit

The well-known stochastic K-armed bandit problem [START_REF] Thompson | On the Likelihood that One Unknown Probability Exceeds Another in View of the Evidence of two Samples[END_REF][START_REF] Lai | Asymptotically efficient adaptive allocation rules[END_REF][START_REF] Auer | Finite time analysis of the multiarmed bandit problem[END_REF] involves an agent sequentially choosing among a set of K arms A = {1, . . . , K}. At each time step t, the player selects an action a t = i ∈ A and obtains a reward

r t ∈ [0, 1].
The reward r t is drawn from some fixed but unknown distribution P i such that E(r t | a t ) = µ i . The goal of the decision maker is to draw arms so as to maximize the total reward obtained after T interactions. An equivalent notion is to minimize the total regret against an agent who knew the arm with the maximum expectation before the game starts and always plays it. This is defined by:

R T µ * -E π T t=1 r t . (2.1)
where µ * max a∈A µ a is the mean reward of the optimal arm and π(a t | a 1:t-1 , r 1:t-1 ) is the policy of the decision maker, defining a probability distribution on the next actions a t given the history of previous actions a 1:t-1 = a 1 , . . . , a t-1 and rewards r 1:t-1 = r 1 , . . . r t-1 . Our goal is to bound the regret uniformly over T .

Differential Privacy

Differential privacy was originally proposed by [START_REF] Dwork | Differential privacy[END_REF], as a way to formalise the amount of information about the input of an algorithm, that is leaked to an adversary observing its output, no matter what the adversary's side information is. In the context of our setup, the algorithm's input is the sequence of rewards, and its output the actions. Consequently, we use the following definition of differentially private bandit algorithms.

Definition 2.1 ((ǫ, δ)-differentially private bandit algorithm). A bandit algorithm π is (ǫ, δ)-differentially private if for all sequences r 1:t-1 and r ′ 1:t-1 that differs in at most one time step, we have for all S ⊆ A:

π(a t ∈ S | a 1:t-1 , r 1:t-1 ) ≤ π(a t ∈ S | a 1:t-1 , r ′ 1:t-1
)e ǫ +δ where A is the set of actions. When δ = 0, the algorithm is said to be ǫ-differential private.

Intuitively, this means that changing any reward r t for a given arm, will not change too much the best arm released at time t or later on. If each r t is a private information or a point associated to a single individual, then the definition aboves means that the presence or absence of that individual will not affect too much the output of the algorithm. Hence, the algorithm will not reveal any extra information about this individual leading to a privacy protection. The privacy parameters (ǫ, δ) determines the extent to which an individual entry affects the output; lower values of (ǫ, δ) imply higher levels of privacy.

A natural way to obtain privacy is to add a noise such as Laplace noise (Lap ) to the output of the algorithm. The main challenge is how to get the maximum privacy while adding a minimum amount of noise as possible. This leads to a trade off between privacy and utility. In our paper, we demonstrated how to optimally trade-off this two notions.

Hybrid Mechanism

The hybrid mechanism is an online algorithm used to continually release the sum of some statistics while preserving differential privacy. More formally, there is a stream σ t = r 1 , r 2 . . . r t of statistics with r i in [0, 1]. At each time step t a new statistic r t is given. The goal is to output the partial sum (y t = t i=1 r i ) of the statistics from time step 1 to t without compromising privacy of the statistics. In other words, we wish to find a randomised mechanism M (y t | σ t , y 1:t-1 ) that is (ǫ, δ)-differential private.

The hybrid mechanism solves this problem by combining the Logarithm and Binary Noisy Sum mechanisms. Whenever t = 2 k for some integer k, it uses the Logarithm mechanism to release a noisy sum by adding Laplace noise of scale ǫ -1 . It then builds a binary tree B, which is used to release noisy sums until t = 2 k+1 via the Binary mechanism. This uses the leaf nodes of B to store the inputs r i , while all other nodes store partial sums, with the root containing the sum from 2 k to 2 k+1 -1. Since the tree depth is logarithmic, there is only a logarithmic amount of noise added for any given sum, more specifically Laplace noise of scale log t ǫ and mean 0 which is denoted by Lap( log t ǫ ). [START_REF] Chan | Private and continual release of statistics[END_REF] proves that the hybrid mechanism is ǫ-differential private for any n where n is the number of statistics seen so far. They also show that with probability at least 1 -γ, the error in the released sum is upper bounded by 1 ǫ log( 1 γ ) log 1.5 n. In this paper, we derived and used a tighter bound for this same mechanism (see Appendix in Supplementary Material) which is:

√ 8 ǫ log( 4 γ ) log n + √ 8 ǫ log( 4 γ ) (2.2)
3 Private Stochastic Multi-Armed Bandits

We describe here the general technique used by our algorithms to obtain differential privacy. Our algorithms are based on the non-private UCB algorithm by [START_REF] Auer | Finite time analysis of the multiarmed bandit problem[END_REF]. At each time step, UCB based its action according to an optimistic estimate of the expected reward of each arm. This estimate is the sum of the empirical mean and an upper bound confidence equal to 2 log t na,t

where t is the time step and n a,t the number of times arm a has been played till time t. We can observe that the only quantity using the value of the reward is the empirical mean.

To achieve differential privacy, it is enough to make the player based its action on differentially private empirical means for each arm. This is so, because, once the mean of each arm is computed, the action which will be played is a deterministic function of the means. In particular, we can see the differentially private mechanism as a black box, which keeps track of the vector of non-private empirical means Y for the player, and outputs a vector of private empirical means X. This is then used by the player to select an action, as shown in Figure 1. We provide three different algorithms that use different techniques to privately compute the mean and calculate the index of each arm. The first, DP-UCB-BOUND, employs the Hybrid mechanism to compute a private mean and then adds a suitable term to the confidence bound to take into account the additional uncertainty due to privacy. The second, DP-UCB employs the same mechanism, but in such a way so as all arms have the same privacy-induced uncertainty; consequently the algorithm then uses the same index as standard UCB. The final one, employs a mechanism that only releases a new mean once at the beginning of each interval. This allows us to obtain the optimal regret rate.

The DP-UCB-BOUND Algorithm

In Algorithm 1, we compute the sum of the rewards of each arm using the hybrid mechanism [START_REF] Chan | Private and continual release of statistics[END_REF]. However, the number and the variance of Laplace noise added by the hybrid mechanism increases as we keep pulling an arm. This means that the sum of each arm get added different amount of noise bigger than the original confidence bound used by UCB. This makes it difficult to identify the best arms. To solve this issue, we add a tight upper

a t r t P i Y X t ∈ [T ]
Figure 1: Graphical model for the empirical and private means. a t is the action of the agent, while r t is the reward obtained, which is drawn from the bandit distribution P i . The vector of empirical means Y is then made into a private vector X which the agent uses to select actions. The rewards are essentially hidden from the agent by the DP mechanism. Proof. This follows directly from the fact that the hybrid mechanism is ǫ-DP after any number t of plays and a single flip of one reward in the sequence of rewards only affect one mechanism. Furthermore, the whole algorithm is a random mapping from the output of the hybrid mechanism to the action taken and using Proposition 2.1 of (Dwork and Roth 2013) completes the proof. Theorem 3.2 gives the regret for algorithm 1. While here we give only a sketch proof, the complete derivation can be found in the supplementary material (Tossou and Dimitrakakis 2016). Theorem 3.2. If Algorithm 1 is run with K arms having arbitrary reward distributions, then, its expected regret R after any number t of plays is bounded by: R ≤

a:µa<µ * max B (ln B + 7) , 8 λ 2 0 ∆ a log t + a:µa<µ * ∆ a + 2π 2 ∆ a 3 (3.1) B = √ 8 ǫ(1 -λ 0 )
• ln(4t 4 )

for any λ 0 such that 0 < λ 0 < 1 where µ 1 , . . . , µ K are the expected values of P 1 , . . . , P K and ∆ a = µ * -µ a .

Proof Sketch. We used the bound on the hybrid mechanism defined in equation 2.2 together with the union and Chernoff-Hoeffding bounds. We then select the error probability γ at each step to be t -4 . This leads to a transcendental inequality solved using the Lambert W function and approximated using section 3.1 of [START_REF] Barry | Analytical approximations for real values of the lambert w-function[END_REF].

The DP-UCB Algorithm

The key observation used in Algorithm 2 is that if at each time step we insert a reward to all hybrid mechanisms, then the scale of the noise will be the same. This means that there is no need anymore to compensate an additional bound. More precisely, every time we play an arm a t = a and receive the reward r t , we not only add it to the hybrid mechanism corresponding to arm a but we also add a reward of 0 to the hybrid mechanism of all other arms. As these calculate a sum, it doesn't affect subsequent calculations. Theorem 3.3 shows the validity of this approach by demonstrating a regret bound with only an additional factor of O(ǫ -2 log 2 log t) to the optimal non private regret.

Algorithm 2 DP-UCB Run Algorithm 1 and set ν a to 0 When arm a t = a is played, insert 0 to all hybrid mechanisms corresponding to arm a ′ = a (Do not increase n a ′ ,t ) Theorem 3.3. If Algorithm 2 is run with K arms having arbitrary reward distributions, then, its expected regret R after any number t of plays is bounded by: R ≤

a:µa<µ * ∆ a max C 2 (ln C + 7) 2 , 8 ∆ 2 a log t + a:µa<µ * (∆ a + 4∆ a ζ(1.5)) C = 56(2 + √ 3.5) √ log t ǫ
where ζ denotes the Riemann zeta function.

Proof Sketch. The proof is similar to the one for Theorem 3.2, but we have to choose the error probability to be t -3.5 .

The DP-UCB-INT Algorithm

Both Algorithms 1 and 2 enjoy a logarithmic regret with only a small additional factor in the time step t to the optimal non-private regret. However, this includes a multiplicative factor of ǫ -1 and ǫ -2 respectively. Consequently, increasing privacy scales the total regret proportionally. A natural question is whether or not it is possible to get a differentially private algorithm with only an additive constant to the optimal regret. Algorithm 3 answers positively to this question by using novel tricks to achieve differential privacy. Looking at regret analysis of Algorithms 1 and 2, we observe that by adding noise proportional to ǫ, we will get a multiplicative factor to the optimal. In other words, to remove this factor, the noise should not depend on ǫ. But how can we get ǫ-DP in this case?

Note that if we compute and use the mean at each time step with an ǫ ′ na,t -DP algorithm, then after time step t, our overall privacy is roughly the sum E ′ of all ǫ ′ na,t . We then change the algorithm so that it only uses a released mean once every 1 ǫ times, making privacy ǫE ′ . In any case, ǫ ′ na,t needs to decrease, at least as n -1 a,t , for the sum to be bounded by log n a,t . However, ǫ ′ na,t should also be big enough such that the noise added keeps the UCB confidence interval used at the same order, otherwise, the regret will be higher.

A natural choice for ǫ ′ na,t is a p-series. Indeed, by making ǫ ′ na,t to be of the form

1 n v/2 a,t
, where n a,t is the number of times action a has been played until time t, its sum will converge to the Riemann zeta function when v is appropriately chosen. This choice of ǫ ′ na,t leads to the addition of a Laplace noise of scale

1 n 1-v/2 a,t
to the mean (See Lemma 3.1). Now our trade-off issue between high privacy and low regret is just reduced into choosing a correct value for v. Indeed, we can pick v > 2, for the privacy to converge; but the noise added at each time step will be increasing and greater than the UCB bound; which is not desirable. To overcome this issue, we used the more sophisticated k-fold adaptive composition theorem (III-3 in [START_REF] Dwork | Boosting and differential privacy[END_REF]). Roughly speaking, this theorem shows that our overall privacy after releasing the mean a number of times depends on the sum of the square of each individual privacy parameter ǫ ′ na,t . So, v > 1 is enough for convergence and with v ≤ 1.5, the noise added will be decreasing and will eventually become lower than the UCB bound.

In summary, we just need to lazily update the mean of each arm every 1 ǫ times. However, we show that the interval of release is much better than 1 ǫ and follows a series f as defined by Lemma (B.1) in the supplements (Tossou and Dimitrakakis 2016). Algorithm 3 summarizes the idea developed in this section.

The next lemma establishes the privacy ǫ ′ each time a new mean is released for a given arm a. Input ǫ ∈ (0, 1] v ∈ (1, 1.5]; privacy rate. K is the number of arms and A the set of all arms. f ← ⌈ 1 ǫ ⌉; x ← 0 (For simplicity, we take the interval f to be ⌈ 1 ǫ ⌉ here) for t ← 1 to T do if t ≤ Kf then play arm a = (t -1) mod K + 1 and observe r t else for all a ∈ A do if n a,t mod f = 0 then xa ← sa na,t + Lap(0,

(ǫ ′ , δ ′ )-differential private with ǫ ′ ≤ min   t n=1 ǫ √ n v , ǫ t n=1 e 1 √ n v -1 √ t v + ǫ t n=1 2 ln 1 δ ′ n v   for any δ ′ ∈ (0, 1], ǫ ∈ (0, 1]
Proof Sketch. We begin by using similar observations as in Theorem 3.1. Then, we compute the privacy of the mean of an arm using the k-fold adaptive composition theorem in [START_REF] Dwork | Boosting and differential privacy[END_REF] (see the supplements (Tossou and Dimitrakakis 2016)).

The next corollary gives a nicer closed form for the privacy parameter which is needed in practice.

Corollary 3.1. After playing for t time steps, Algorithm 3 is

(ǫ ′ , δ ′ )-differential private with ǫ ′ ≤ min ǫ t 1-v/2 -v/2 1 -v/2 , 2ǫζ(v) + 2ǫζ(v) ln(1/δ ′ ) with ζ the Riemann Zeta Function for any δ ′ ∈ (0, 1], ǫ ∈ (0, 1], v ∈ (1, 1.5].
Proof Sketch. We upper bounded the first term in theorem 3.4 by the integral test, then for the second term we used e x ≤ 1 + 2x for all x ∈ [0, 1] to conclude the proof.

The following corollary gives the parameter ǫ with which one should run Algorithm 3 to achieve a given ǫ ′ privacy.

Corollary 3.2. If you run Algorithm 3 with parameter

ǫ = log 1 δ ′ +4ǫ ′ 8ζ(v) - log 1 δ ′ 8ζ(v) 2 for any δ ′ ∈ (0, 1], ǫ ′ ∈ (0, 1], v ∈ (1, 1.5], you will be at least (ǫ ′ , δ ′ )-differential private.
Proof. The proof is obtained by inverting the term using the Riemann zeta function in corollary 3.1.

Finally, we present the regret of Algorithm 3 in theorem 3.5 . A simple observation shows us that it has the same regret as the non private UCB with just an additive constant.

Theorem 3.5. If Algorithm 3 is run with K arms having arbitrary reward distributions, then, its expected regret R after any number t of plays is bounded by: R ≤

a:µa<µ * ∆ a f 0 + 8 ∆ 2 a log t + 1 + 4ζ(1.5)
where f 0 ≤ 1 ǫ . More precisely, f 0 is the first value of the series f defined in Lemma B.1 in the supplements (Tossou and Dimitrakakis 2016).

Sketch. This is proven using a Laplace concentration inequality to bound the estimate of the mean then we selected the error probability to be t -3.5 .

Experiments

We perform experiments using arms with rewards drawn from independent Bernoulli distribution. The plot, in logarithmic scale, shows the regret of the algorithms over 100, 000 time steps averaged over 100 runs. We targeted 2 different ǫ privacy levels : 0.1 and 1. For DP-UCB-INT, we pick ǫ such that the overall privacy is (ǫ ′ , δ ′ )-DP with ǫ as defined in corollary 3.2 and δ ′ = e -10 , ǫ ′ ∈ {0.1, 1}, v = 1.1. We put in parenthesis the input privacy of each algorithm.

We compared against the non private UCB algorithm and the algorithm presented in [START_REF] Mishra | nearly) optimal differentially private stochastic multi-arm bandits[END_REF] (Private-UCB ) with a failure probability chosen to be t -4 .

We perform two scenarios. Firstly we used two arms: one with expectation 0.9 and the other 0.6. The second scenario is a more challenging one with 10 arms having all an expectation of 0.1 except two with 0.55 and 0.2.

As expected, the performance of DP-UCB-INT is significantly better than all other private algorithms. More importantly, the gap between the regret of DP-UCB-INT and the non private UCB does not increase with time confirming the theoretical regret. We can notice that DP-UCB is better than DP-UCB-BOUND for small time steps. However, as the time step increases DP-UCB-BOUND outperforms DP-UCB and eventually catches its regret. The reason for that is: DP-UCB spends less time to distinguish between arms with close rewards due to the fact that the additional factor in its regret depends on ∆ a = µ * -µ a which is not the case for DP-UCB. Private-UCB performs worse than all other algorithms which is not surprising. Moreover, we noticed that the difference between the best regret (after 100 runs) and worst regret is very consistent for all ours algorithms and the non private UCB (it is under 664.5 for the 2 arms scenario). However, this gap reaches 30, 000 for Private-UCB. This means that our algorithms are able to correctly trade-off between exploration and exploitation which is not the case for Private-UCB.

Conclusion and Future Work

In this paper, we have proposed and analysed differentially private algorithms for the stochastic multi-armed bandit problem, significantly improving upon the state of the art. The first two, (DP-UCB and DP-UCB-BOUND) are variants of an existing private UCB algorithm [START_REF] Mishra | nearly) optimal differentially private stochastic multi-arm bandits[END_REF], while the third one uses an interval-based mechanism.

Those first two algorithms are only within a factor of O(ǫ -1 log log t) and O(ǫ -2 log 2 log t) to the non-private algorithm. The last algorithm, DP-UCB-INT, efficiently trades off the privacy level and the regret and is able to achieve the same regret as the non-private algorithm up to an additional additive constant. This has been achieved by using two key tricks: updating the mean of each arm lazily with a frequency proportional to the privacy ǫ -1 and adding a noise independent of ǫ. Intuitively, the algorithm achieves better privacy without increasing regret, because its output is less dependent on individual reward.

Perhaps it is possible to improve our bounds further if we are willing to settle for asymptotically low regret [START_REF] Cowan | Asymptotic behavior of minimal-exploration allocation policies: Almost sure, arbitrarily slow growing regret[END_REF]. A natural future work is to study if we can use similar methods for other mechanisms such as Thompson sampling (known to be differentially private [START_REF] Dimitrakakis | Robust and private Bayesian inference[END_REF])) instead of UCB. Another question is whether a similar analysis can be performed for adversarial bandits.

We would also like to connect more to applications by two extensions of our algorithms. The first natural extension is to consider some side-information. In the drug testing exam-ple, this could include some information about the drug, the test performed and the user examined or treated. The second extension would relate to generalising the notion of neighbouring databases to take into account the fact that multiple observations in the sequence (say m) can be associated with a single individual. Our algorithms can be easily extended to deal with this setting (by re-scaling the privacy parameter to ǫ m ). However, in practice, m could be quite large and it will be an interesting future work to check if we could get sub linearity in the parameter m under certain conditions.

From inequality (A.11), we have

n ≥ 8 λ 2 0 ∆ 2 a log(t). (A.13) Equation (A.12) leads to n ≥ B • log(n) + B with B = √ 8 ǫ(1 -λ 0 )∆ a • ln 4 γ = √ 8 ǫ(1 -λ 0 )∆ a • ln(4t 4 )
We can rewrite the inequality in a more familiar form:

e -(-1 B )n ≥ e • n This is a standard transcendental algebraic inequality whose solution is given by the Lambert W function. So,

n ≥ -B • W -1 e • B , -1
where W (x, k) is the Lambert function of x on branch k. Note here that the branch is -1 and because -1 e < -1 e•B < 0 ∀t > 1, we are always guaranteed to find a real number.

By using the approximation of the Lambert function provided in section 3.1 of [START_REF] Barry | Analytical approximations for real values of the lambert w-function[END_REF], we can conclude that

n ≥ -B • W -1 e • B , -1 ≈ -B ln( 1 e • B ) - 2 0.3361 ≥ B (ln B + 7) = √ 8 • ln(4t 4 ) ǫ(1 -λ 0 )∆ a ln √ 8 • ln(4t 4 ) ǫ(1 -λ 0 )∆ a + 7 (A.14)
Combining inequalities (A.13) and (A.14) yields,

n ≥ max B (ln (B) + 7) , 8 λ 2 0 ∆ 2 a log(t)
In summary,

T a (s) ≤ max B (ln B + 7) , 8 λ 2 0 ∆ 2 a log(t) + ∞ t=1 t-1 n=1 t-1 na=ℓ 4t -4 ≤ 1 + max B (ln B + 7) , 8 λ 2 0 ∆ 2 a log t + ∞ t=1 4t -2 ≤ 1 + max B (ln B + 7) , 8 λ 2 0 ∆ 2 a log t + 2π 2 3 (A.15)
which concludes the proof.

A.2 Proof for Theorem 3.3

The proof of this theorem is similar to the one for theorem 3.5 with

h n = 1 ǫ • √ 8(log n) • ln 4 γ • 1 n + 1 ǫ • √ 8 • ln 4 γ • 1 n .
We make the same choice of λ and γ. However, the minimum number n compatible with these choices lead a transcendental equations in the same form as the one in the proof of theorem 3.2.

B Proofs for UCB-Interval Algorithm Fact B.1. Differential privacy of the Laplace mechanism (See Theorem 4 in [START_REF] Dwork | The algorithmic foundations of differential privacy[END_REF]) For any real function g of the data, a mechanism adding Laplace noise with scale parameter β is ∆g/β-differentially private, where ∆g is the L1 sensitivity of g.

B.1 Proof of Lemma 3.1

Proof. Indeed, for each arm, we are adding a Laplace noise of mean 0 and scale n v/2-1 a,t where n a,t is the number of times this arm has been played. As the sensitivity of the mean is 1 na,t , we use the differential privacy of the Laplace Mechanism (Fact B.1) to conclude the proof.

B.2 Proof of Theorem 3.4

Similarly to the proof of Theorem 3.1, the overall privacy of Algorithm 3 will be the same as the overall privacy of the Mechanism computing the mean of the rewards received from a single arm.

A new Laplace Mechanism is used to compute the mean of each arm. However a new mean is only released t/f times (every f time steps) after t times steps where f is the interval used.

According to the k-fold adaptive composition theorem (III-3 in [START_REF] Dwork | Boosting and differential privacy[END_REF]), Algorithm 3 will be (ǫ ′ , δ ′ ) differential private for any δ ′ ∈ (0, 1] with

ǫ ′ ≤ min {C, D} C = n∈I na 1 ǫ 1 √ n v D = n∈I na 1 ǫ 1 √ n v (e 1 √ n v -1) + n∈I na 1 ǫ 2 n v ln(1/δ ′ )
where I na

1 ǫ = { 1 ǫ , 2 ǫ , 3 ǫ , • • • n a } We have D =    n∈I na 1 ǫ 1 √ n v (e 1 √ n v -1) + n∈I na 1 ǫ 2 n v ln(1/δ ′ )    (B.1) ≤    n∈I t 1 ǫ 1 √ n v (e 1 √ n v -1) + n∈I t 1 ǫ 2 n v ln(1/δ ′ )    (B.2) ≤   ǫ t n=1 1 √ n v (e 1 √ n v -1) + ǫ t n=1 2 n v ln(1/δ ′ )   (B.3) C = n∈I na 1 ǫ 1 √ n v (B.4) ≤ n∈I t 1 ǫ 1 √ n v (B.5) ≤ ǫ t n=1 1 √ n v (B.6)
which concludes the proof.

Lemma B.1 (Values of the interval of release of the means).

The interval f by which we should update the mean follows a series such that f n = W n+1 -W n with:

                     W 0 = 0 W n+1 is either x or y with x = inf x ′ ∈N    x ′ ≥ W n + 1 : x ′ i=Wn+1 1 √ i v ≥ 1 ǫ √ x ′ v    y = inf y ′ ∈N    y ′ ≥ W n + 1 : y ′ i=Wn+1 1 i v ≥ 1 ǫy ′ v    Furthermore f n is always such that f n ≤ 1 ǫ
Note that only one of the expression for W n+1 should be used up to the horizon T.

Proof. From the proof of theorem 3.4, we can easily see that we can pass from lines (B.2) to (B.3) if the conditions on y in Lemma B.1 is verified. Similarly, we can pass from lines (B.5) to (B.6) if the conditions on y in Lemma B.1 is verified. In both cases, 1

ǫ is an upper bound on the number x -W n and y -W n as the original interval used in both lines (B.2) and (B.5) is 1 ǫ .

B.3 Proof of Corollary 3.1

From theorem 3.4, we know that Algorithm 3 will be (ǫ ′ , δ ′ ) differential private for any δ ′ ∈ (0, 1], 1 < v ≤ 1.5 with

ǫ ′ ≤ min {C, D} C = t n=1 ǫ √ n v D = ǫ t n=1 e 1 √ n v -1 √ t v + ǫ t n=1 2 ln 1 δ ′ n v
It is easy to get an upper bound for C using the integral test inequality giving:

C ≤ ǫ t 1-v/2 -v/2 1-v/2
We will now simplify D using a standard approximation for exponential function.

D = ǫ t n=1 e 1 √ n v -1 √ t v + ǫ t n=1 2 ln 1 δ ′ n v (B.7) ≤   ǫ ∞ t=1 1 √ t v (e 1 √ t v -1) + ǫ ∞ t=1 2 t v ln(1/δ ′ )   (B.8) ≤   ǫ ∞ t=1 2( 1 √ t v ) 2 + ǫ ∞ t=1 2 t v ln(1/δ ′ )   (B.9) = 2ǫζ(v) + 2ǫζ(v) ln(1/δ ′ ) (B.10)
where ζ is the Riemann zeta function.

B.4 Proof of Corollary 3.2

The proof is immediate from corollary 3.1. It is obtained by inverting the term using the Riemann zeta function in corollary 3.1.

B.5 Proof of Theorem 3.5 First, let's ignore the effect of computing the means per interval and assume that we compute it at each time step after playing each arm f 0 times where f 0 ≤ 1 ǫ is the first value of the series f defined in lemma (B.1). As much of the proof is quite similar to that of Theorem 3.2, we shall omit some steps.

Similarly to the proof of Theorem 3.2, we will take a bad arm when one of the following 3 events happens:

X * n ≤ µ * -c t,n (B.12) X a,na ≥ µ a + c t,na (B.13) µ * < µ a + 2c t,n (B.14) Since we are adding Laplace noise, we can use Fact B.2 to show that:

Pr{|Y -X| ≥ log( 1 γ )n v/2-1 } ≤ γ (B.

15)

Let h n = log( 1 γ )n v/2-1 . Now we can bound the probability of events (B.13) using equation (B.15), the union bound and the Chernoff-Hoeffding bound. In order to be more precise, we use X a,na for xa and Y to denote the empirical mean xa at time t, while c t,na = 2 log(t)/n a as before.

Pr(B.13) = Pr(X Now, Let's compute the minimum value for n a which is consistent with our choice of λ 4 and γ. It is easy to show that n a ≥ ( 2- √ 3.5 3.5 √ 2 log t ) 2 v-1 . And this number converges to 0 as t increases.

The final event B.14 is exactly the standard UCB event and B.14 will be false for all n a ≥ 8 ∆ 2 a log t. Now, we can easily see that the effect of the interval in the algorithm will not change this number. Indeed, because we are only updating the mean each f steps, the number n a should be divided by f . Now, after updating the mean, we play this arm for a number of steps lower or equal to f . So, we should multiply n a by f which cancel out the effect of the division.

In summary, (and similarly to Theorem 3.2) T a (s) ≤ f 0 + max ( 2 -√ 3.5 3.5 √ 2 log t ) ǫ log( 4 γ ). Proof. Our improvement is based on two observations. Firstly, if γ ≤ n -b then we can use the alternative concentration bound for the sum of the Laplace distribution. Secondly, we note that given all the previous released sums, the current sum is only drawn from one of the two mechanisms. Thus there is no need to apply a composition theorem.

Lemma 3. 1 .

 1 The mean xa computed by Algorithm 3 for a Algorithm 3 DP-UCB-INT (ǫ, v, K, A)

  Regret for ǫ = 0.1, 10 arms

Figure 2 :

 2 Figure 2: Experimental results with 100 runs, 2 or 10 arms with rewards: {0.9, 0.6} or {0.1 . . . 0.2, 0.55, 0.1 . . .} .

Fact B. 2 (

 2 Fact 3.7 in[START_REF] Dwork | The algorithmic foundations of differential privacy[END_REF]). If Y ∼ Lap(b) then Pr(|Y |≥ b ln 1 γ ) = γ. (B.11)

  2 (Improved[START_REF] Chan | Private and continual release of statistics[END_REF] bound).For any γ ≤ n -b , where b > 0, Chan's hybrid mechanism is ǫ-differential private and has an error bounded with probability at least 1 -γ by √ 8 ǫ log( 4 γ ) log n + √ 8

  -1 log log t) factors are added to the optimal non private regret. In theorem 3.1, we demonstrate that Algorithm 1 is indeed ǫ-differential private.

	Algorithm 1 DP-UCB-BOUND
	Input ǫ, the differential privacy parameter.
	Instantiate K Hybrid Mechanisms (Chan, Shi, and Song
	2010); one for each arm a.
	else ν a ← end if	√ 8 ǫ log(4t 4 )	√ ǫ log(4t 4 ) 8
	end for
	Pull arm a t = arg max a	sa(t) na,t + 2 log t na,t + νa na,t
	Observe the reward r t
	Insert r t to the hybrid mechanism for arm a t
	end if
	end for
	bound defined in equation (2.2) on the noise added by the
	hybrid mechanism.
	Theorem 3.2 validates this choice by showing that only
	O(ǫ Theorem 3.1. Algorithm 1 is ǫ-differential private after any
	number of t of plays.

for t ← 1 to T do if t ≤ K then play arm a = t and observe the reward r t Insert r t to the hybrid mechanism a else for all arm a do s a (t) ← total sum computed using the hybrid mechanism a if n a,t is a power of 2 then ν a ← √ 8 ǫ log(4t 4 ) log n a,t +

  Pull arm a t = arg max a xa and observe r t Update sum s a ← s a + r t .

				1 1-v/2 n a,t	) + 2 log t na,t
	end if
	end for
	end if
	end for
	given arm a at each interval is n	-v/2 a,t -differential private
	with respect to the reward sequence observed by that arm.
	Proof. Sketch This follows directly from the fact that we
	add Laplace noise of scale n	v/2-1 a,t	.
	The next theorem establishes the overall privacy after hav-
	ing played for t time steps.
	Theorem 3.4. After playing for any t time steps, Algorithm
	3 is

  a,na ≥ µ a + c t,na ) = Pr(X a,na ≥ Y a,na + h na ∨ Y a,na ≥ µ a + c t,na -h na ) ≤ Pr(X a,na ≥ Y a,na + h na ) + Pr(Y a,na ≥ µ a + c t,na -h na ) ≤ γ + Pr(Y a,na ≥ µ a + c t,na -h na ). (B.16) ≤ γ + exp(-2n a (c t,na -h na ) 2 )In the above, we choose h na ≤ λ 4 c t,na with λ 4 = 1 -Similarly, we prove a bound on the probability (B.12):Pr(B.12) = Pr(X * n ≤ µ * -c t,n ) = Pr(X * n ≤ Y * n -h na ∨ Y * n ≤ µ * -c t,n + h na ) ≤ Pr(X * n ≤ Y * n -h na ) + Pr(Y * n ≤ µ * -c t,n + h na ) ≤ γ + t -3.5 = 2t-3.5 .(B.20)

			√ 3.5
		and γ = t -3.5	2
		(B.17)
	≤ γ + t -3.5 ≤ 2t -3.5	(B.18) (B.19)

A Collected proofs

A.1 Proof of Theorem 3.2 a will be used to indicate the index of an arm. ǫ is the differential privacy parameter. t is used to denote the time step.

From Lemma (B.2), we know that the error between the empirical and private mean is bounded as |Y -X| ≤ h n with probability at least 1 -γ, X is the empirical mean returned by the private mechanism, Y the true empirical mean, h n the error due to the differentially private mechanism. It is defined as:

We can rewrite this bound into equations A.1 and A.2.

Let T a (s) be the number of times arm a is played in the first s time steps. Let's c t,n

(2 ln t)/n denote the original UCB confidence index.

By following similar steps as in the demonstration of UCB in [START_REF] Auer | Finite time analysis of the multiarmed bandit problem[END_REF], we have

n is the mean returned by the private mechanism for the best arm when it has been played n times. Now we can observe that X * n + c t,n + h n ≤ X a,na + c t,na + h na implies that at least one of the following must hold

We can bound the probability of events (A.4) using equation (A.2), the union bound and the Chernoff-Hoeffding bound.

Similarly, to prove a bound on the probability (A.5) we use (A.1) , the union bound and the Chernoff-Hoeffding bound.

Let's choose γ = t -4 ; this leads respectively to Pr(A.4) ≤ 2t -4 (A.9)

Now consider the last condition (A.6). For this, we want to find the minimum number n for which event (A.6) is always false. Event (A.6) is false, implies that ∆ a > 2c t,n + 2h n where ∆ a = µ * -µ a . We observe that for ∆ a > 2c t,n +2h n to hold, it is enough that the following two conditions hold for any λ 0 such that 0 < λ 0 < 1. .12)