Rémi Munos
email: remi.munos@inria.fr

From Bandits to Monte-Carlo Tree Search: The Optimistic Principle Applied to Optimization and Planning

Optimists and pessimists inhabit different worlds, reacting to the same circumstances in completely different ways.

Learning to Hope, Daisaku Ikeda.

Habits of thinking need not be forever. One of the most significant findings in psychology in the last twenty years is that individuals can choose the way they think.

Learned Optimism, Martin Seligman.

Humans do not hold a positivity bias on account of having read too many self-help books. Rather, optimism may be so essential to our survival that it is hardwired into our most complex organ, the brain.

The Optimism Bias: A Tour of the Irrationally Positive Brain, Tali Sharot.

Abstract

This work covers several aspects of the optimism in the face of uncertainty principle applied to large scale optimization problems under finite numerical budget. The initial motivation for the research reported here originated from the empirical success of the so-called Monte-Carlo Tree Search method popularized in Computer Go and further extended to many other games as well as optimization and planning problems. Our objective is to contribute to the development of theoretical foundations of the field by characterizing the complexity of the underlying optimization problems and designing efficient algorithms with performance guarantees.

The main idea presented here is that it is possible to decompose a complex decision making problem (such as an optimization problem in a large search space) into a sequence of elementary decisions, where each decision of the sequence is solved using a (stochastic) multi-armed bandit (simple mathematical model for decision making in stochastic environments). This so-called hierarchical bandit approach (where the reward observed by a bandit in the hierarchy is itself the return of another bandit at a deeper level) possesses the nice feature of starting the exploration by a quasi-uniform sampling of the space and then focusing progressively on the most promising area, at different scales, according to the evaluations observed so far, until eventually performing a local search around the global optima of the function. The performance of the method is assessed in terms of the optimality of the returned solution as a function of the number of function evaluations.

Our main contribution to the field of function optimization is a class of hierarchical optimistic algorithms designed for general search spaces (such as metric spaces, trees, graphs, Euclidean spaces) with different algorithmic instantiations depending on whether the evaluations are noisy or noiseless and whether some measure of the "smoothness" of the function is known or unknown. The performance of the algorithms depends on the "local" behavior of the function around its global optima expressed in terms of the quantity of near-optimal states measured with some metric. If this local smoothness of the function is known then one can design very efficient optimization algorithms (with convergence rate independent of the space dimension). When this information is unknown, one can build adaptive techniques which, in some cases, perform almost as well as when it is known.

In order to be self-contained, we start with a brief introduction to the stochastic multi-armed bandit problem in Chapter 1 and describe the UCB (Upper Confidence Bound) strategy and several extensions. In Chapter 2 we present the Monte-Carlo Tree Search method applied to Computer Go and show the limitations of previous algorithms such as UCT (UCB applied to Trees). This provides motivation for designing theoretically well-founded optimistic optimization algorithms. The main contributions on hierarchical optimistic optimization are described in Chapters 3 and 4 where the general setting of a semimetric space is introduced and algorithms designed for optimizing a function assumed to be locally smooth (around its maxima) with respect to a semi-metric are presented and analyzed. Chapter 3 considers the case when the semi-metric is known and can be used by the algorithm, whereas Chapter 4 considers the case when it is not known and describes an adaptive technique that does almost as well as when it is known. Finally in Chapter 5 we describe optimistic strategies for a specific structured problem, namely the planning problem in Markov decision processes with infinite horizon discounted rewards.

The stochastic multi-armed bandit problem

We start with a brief introduction to the stochastic multi-armed bandit setting. This is a simple mathematical model for sequential decision making in unknown random environments that illustrates the so-called exploration-exploitation trade-off. Initial motivation in the context of clinical trials dates back to the works of [START_REF] Thompson | On the likelihood that one unknown probability exceeds another in view of the evidence of two samples[END_REF][START_REF] William | On the theory of apportionment[END_REF] and [START_REF] Robbins | Some aspects of the sequential design of experiments[END_REF]. In this chapter we consider the optimism in the face of uncertainty principle, which recommends following the optimal policy in the most favorable environment among all possible environments that are reasonably compatible with the observations. In a multi-armed bandit the set of "compatible environments" is the set of possible distributions of the arms that are likely to have generated the observed rewards. More precisely we investigate a specific strategy, called UCB (where UCB stands for upper confidence bound) introduced by Auer, [START_REF] Auer | Finite time analysis of the multiarmed bandit problem[END_REF], that uses simple highprobability confidence intervals (one for each arm) for the set of possible "compatible environments". The strategy consists of selecting the arm with highest upper-confidence-bound (the optimal strategy for the most favorable environment).

We introduce the setting of the multi-armed bandit problem in Sec-tion 1.1.1, then present the UCB algorithm in Section 1.1.2 and existing lower bounds in Section 1.1.3. In Section 1.2 we describe extensions of the optimistic approach to the case of an infinite set of arms, either when the set is denumerable (in which case a stochastic assumption is made) or where it is continuous but the reward function has a known structure (e.g. linear, Lipschitz).

The K-armed bandit 1.Setting

Consider K arms (actions, choices) defined by distributions (ν k ) 1≤k≤K with bounded support (here we will assume that the support lies in [0, 1]) that are initially unknown to the player. At each round t = 1, . . . , n, the player selects an arm I t ∈ {1, . . . , K} and obtains a reward X t ∼ ν It , which is a random sample drawn from the distribution ν It corresponding to the selected arm I t , and is assumed to be independent of previous rewards. The goal of the player is to maximize the sum of obtained rewards in expectation.

Define

μ k = E X∼ν k [X]
as the mean values of each arm, and μ * = max k μ k = μ k * as the mean value of one best arm k * (there may exist several).

If the arm distributions were known, the agent would select the arm with the highest mean at each round and obtain an expected cumulative reward of nμ * . However, since the distributions of the arms are initially unknown, he needs to pull each arm several times in order to acquire information about the arms (this is called exploration) and while his knowledge about the arms improves, he should pull increasingly often the apparently best ones (this is called exploitation). This illustrates the so-called exploration-exploitation trade-off.

In order to assess the performance of any strategy, we compare its performance to an oracle strategy that would know the distributions in advance (and would thus play the optimal arm). For that purpose we define the notion of cumulative regret: at round n,

R n def = nμ * - n t=1 X t .
(1.1)

This defines the loss, in terms of cumulative rewards, resulting from not knowing from the beginning the reward distributions. We are thus interested in designing strategies that have a low cumulative regret. Notice that using the tower rule, the expected regret can be written:

ER n = nμ * -E n t=1 μ It = E K k=1 T k (n)(μ * -μ k ) = K k=1 E[T k (n)]Δ k ,
(1.2) where Δ k def = μ *μ k is the gap in terms of expected rewards, between the optimal arm and arm k, and T k (n) def = n t=1 1{I t = k} is the number of pulls of arm k up to time n.

Thus a good algorithm should not pull sub-optimal arms too often. Of course, in order to acquire information about the arms, one needs to explore all the arms and thus pull sub-optimal arms. The regret measures how fast one can learn relevant quantities about one's unknown environment while simultaneously optimizing some criterion. This combined learning-optimizing objective is central to the exploration-exploitation trade-off.

Proposed solutions: Since initially formulated by [START_REF] Robbins | Some aspects of the sequential design of experiments[END_REF], several approaches have addressed this exploration-exploitation problem, including:

• Bayesian exploration: A prior is assigned to the arm distributions and an arm is selected as a function of the posterior (such as Thompson sampling [START_REF] Thompson | On the likelihood that one unknown probability exceeds another in view of the evidence of two samples[END_REF][START_REF] William | On the theory of apportionment[END_REF] which has been analyzed recently in [START_REF] Goyal | Analysis of Thompson sampling for the multi-armed bandit problem[END_REF][START_REF] Kauffmann | Thompson sampling: An asymptotically optimal finite time analysis[END_REF][START_REF] Agrawal | Further optimal regret bounds for Thompson sampling[END_REF][START_REF] Kaufmann | Thompson sampling for 1-dimensional exponential family bandits[END_REF], the Gittins indexes, see [START_REF] Gittins | Bandit processes and dynamic allocation indices[END_REF][START_REF] Gittins | Multi-armed Bandit Allocation Indices[END_REF], and optimistic Bayesian algorithms such as in [START_REF] Srinivas | Gaussian process optimization in the bandit setting: No regret and experimental design[END_REF][START_REF] Kauffman | On Bayesian upper confidence bounds for bandit problems[END_REF]).

• -greedy exploration: The empirical best arm is played with probability 1and a random arm is chosen with probability (see e.g. [START_REF] Auer | Finite time analysis of the multiarmed bandit problem[END_REF] for an analysis),

• Soft-max exploration: An arm is selected with a probability that depends on the (estimated) performance of this arm given previous reward samples (such as the EXP3 algorithm introduced in Auer et al. [2003], see also the learning-from-expert setting of [START_REF] Cesa | Prediction, Learning, and Games[END_REF]).

• Follow the perturbed leader: The empirical mean reward of each arm is perturbed by a random quantity and the best perturbed arm is selected (see e.g. [START_REF] Kalai | Efficient algorithms for online decision problems[END_REF], [START_REF] Kujala | Following the perturbed leader to gamble at multi-armed bandits[END_REF]).

• Optimistic exploration: Select the arm with the largest high-probability upper-confidence-bound (initiated by Lai and [START_REF] Leung | Asymptotically efficient adaptive allocation rules[END_REF], Agrawal [1995b], Burnetas and Katehakis [1996a]), an example of which is the UCB algorithm [START_REF] Auer | Finite time analysis of the multiarmed bandit problem[END_REF] described in the next section.

The Upper Confidence Bounds (UCB) algorithm

The Upper Confidence Bounds (UCB) strategy by [START_REF] Auer | Finite time analysis of the multiarmed bandit problem[END_REF] consists of selecting at each time step t an arm with largest B-values:

I t ∈ arg max k∈{1,...,K} B t,T k (t-1) (k),
where the B-value of an arm k is defined as:

B t,s (k) def = μk,s + 3 log t 2s , (1.3)
where μk,s def = 1 s s i=1 X k,i is the empirical mean of the s first rewards received from arm k, and X k,i denotes the reward received when pulling arms k for the i-th time (i.e., by defining the random time τ k,i to be the instant when we pull arm k for the i-th time, we have X k,i = X τ k,i ). We described here a slightly modified version where the constant defining the confidence interval is 3/2 instead of 2 for the original version UCB1 described in [START_REF] Auer | Finite time analysis of the multiarmed bandit problem[END_REF].

This strategy follows the so-called optimism in the face of uncertainty principle since it selects the optimal arm in the most favorable environments that are (in high probability) compatible with the observations. Indeed the B-values B t,s (k) are high-probability upperconfidence-bounds on the mean-value of the arms μ k . More precisely for any 1 ≤ s ≤ t, we have P(B t,s (k) ≥ μ k ) ≤ 1-t -3 . This bound comes from the Chernoff-Hoeffding inequality which is described below. Let Y i ∈ [0, 1] be independent copies of a random variable of mean μ. Then

P 1 s s i=1 Y i -μ ≥ ≤ e -2s 2 and P 1 s s i=1 Y i -μ ≤ -≤ e -2s 2 .
(1.4) Thus for any fixed 1 ≤ s ≤ t, P μk,s + 3 log t 2s ≤ μ k ≤ e -3 log(t) = t -3 , (1.5) and P μk,s -3 log t 2s ≥ μ k ≤ e -3 log(t) = t -3 .

(1.6)

We now deduce a bound on the expected number of plays of suboptimal arms by noticing that with high probability, the sub-optimal arms are not played whenever their UCB is below μ * . Proposition 1.1. Each sub-optimal arm k is played in expectation at most

ET k (n) ≤ 6 log n Δ 2 k + π 2 3 + 1
time. Thus the cumulative regret of UCB is bounded as

ER n = k Δ k ET k (n) ≤ 6 k:Δ k >0 log n Δ k + K π 2 3 + 1 .
First notice that the dependence in n is logarithmic. This says that out of n pulls, the sub-optimal arms are played only O(log n) times, and thus the optimal arm (assuming there is only one) is played n-O(log n) times. Now, the constant factor in the logarithmic term is 6 k:Δ k >0 1 Δ k which deteriorates when some sub-optimal arms are very close to the optimal one (i.e., when Δ k is small). This may seem counter-intuitive, in the sense that for any fixed value of n, if all the arms have a very small Δ k , then the regret should be small as well (and this is indeed true since the regret is trivially bounded by n max k Δ k whatever the algorithm). So this result should be understood (and is meaningful) for a fixed problem (i.e., fixed Δ k ) and for n sufficiently large (i.e., n > min k 1/Δ 2 k ).

Proof. Assume that a sub-optimal arm k is pulled at time t. This means that its B-value is larger than the B-values of the other arms, in particular that of the optimal arm k * :

μk,T k (t-1) + 3 log t 2T k (t -1) ≥ μk * ,T k * (t-1) + 3 log t 2T k * (t -1)
.

(1.7)

Now, either one of the two following inequalities hold:

• The empirical mean of the optimal arm is not within its confidence interval:

μk * ,T k * (t-1) + 3 log t 2T k * (t -1) < μ * , (1.8)

• The empirical mean of the arm k is not within its confidence interval:

μ k,T k (t-1) > μ k + 3 log t 2T k (t -1)
, (1.9)

or (when both previous inequalities (1.8) and (1.9) do not hold), then we deduce from (1.7) that

μ k + 2 3 log t 2T k (t -1) ≥ μ * , which implies T k (t -1) ≤ 6 log t Δ 2 k .
This says that whenever T k (t -1) ≥ 6 log t Δ 2 k + 1, either arm k is not pulled at time t, or one of the two small probability events (1.8) or

(1.9) holds. Thus writing u def = 6 log t Δ 2 k + 1, we have:

T k (n) ≤ u + n t=u+1 1{I t = k; T k (t) > u} ≤ u + n t=u+1
1{(1.8) or (1.9) holds}.

(1.10)

Now, the probability that (1.8) holds is bounded by

P ∃1 ≤ s ≤ t, μk * ,s + 3 log t 2s < μ * ≤ t s=1 1 t 3 = 1 t 2 ,
using Chernoff-Hoeffding inequality (1.5). Similarly the probability that (1.9) holds is bounded by 1/t 2 , thus by taking the expectation in (1.10) we deduce that

E[T k (n)] ≤ 6 log(n) Δ 2 k + 1 + 2 n t=u+1 1 t 2 ≤ 6 log(n) Δ 2 k + π 2 3 + 1 (1.11)
The previous bound depends on some properties of the distributions: the gaps Δ k . The next result states a problem-independent bound.

Corollary 1.1. The expected regret of UCB is bounded as:

ER n ≤ Kn 6 log n + π 2 3 + 1 (1.12)
Proof. Using Cauchy-Schwarz inequality,

ER n = k Δ k ET k (n) ET k (n) ≤ k Δ 2 k ET k (n) k ET k (n).
The result follows from (1.11) and that k ET k (n) = n

Lower bounds

There are two types of lower bounds: (1) The problem-dependent bounds [Lai and Robbins, 1985, Burnetas andKatehakis, 1996b] say that for any problem in a given class, an "admissible" algorithm will suffer -asymptotically-a logarithmic regret with a constant factor that depends on the arm distributions, (2) The problem-independent bounds [Cesa-Bianchi andLugosi, 2006, Bubeck, 2010] states that for any algorithm and any time-horizon n, there exists an environment on which this algorithm will suffer a regret lower-bounded by some quantity.

Problem-dependent lower bounds: Lai and [START_REF] Leung | Asymptotically efficient adaptive allocation rules[END_REF] considered a class of one-dimensional parametric distributions and showed that any admissible strategy (i.e. such that the algorithm pulls each sub-optimal arm k a sub-polynomial number of times: ∀α > 0, ET k (n) = o(n α )) will asymptotically pull in expectation any suboptimal arm k a number of times such that:

lim inf n→∞ ET k (n) log n ≥ 1 K(ν k , ν k * )
(1.13) (which, from (1.2), enables the deduction of a lower bound on the regret), where K(ν k , ν k * ) is the Kullback-Leibler (KL) divergence between ν k and ν k * (i.e., K(ν, κ) def = 1 0 dν dκ log dν dκ dκ if ν is dominated by κ, and +∞ otherwise). Burnetas and Katehakis [1996b] extended this result to several classes P of multi-dimensional parametric distributions. By writing

K inf (ν, μ) def = inf κ∈P:E(κ)>μ K(ν, κ),
(where μ is a real number such that E(ν) < μ), they showed the improved lower bound on the number of pulls of sub-optimal arms:

lim inf n→∞ ET k (n) log n ≥ 1 K inf (ν k , μ * )
.

(1.14)

Those bounds consider a fixed problem and show that any algorithm that is reasonably good on a class of problems (i.e. what we called an admissible strategy) cannot be extremely good on any specific instance, and thus needs to suffer some incompressible regret. Note also that these problem-independent lower-bounds are of an asymptotic nature and do not say anything about the regret at any finite time n.

A problem independent lower-bound: In contrast to the previous bounds, we can also derive finite-time bounds that do not depend on the arm distributions: For any algorithm and any time horizon n, there exists an environment (arm distributions) such that this algorithm will suffer some incompressible regret on this environment [Cesa-Bianchi andLugosi, 2006, Bubeck, 2010]:

inf sup ER n ≥ 1 20 √ nK,
where the inf is taken over all possible algorithms and the sup over all possible (bounded) reward distributions of the arms.

Recent improvements

Notice that in the problem-dependent lower-bounds (1.13) and (1.14), the rate is logarithmic, like for the upper bound of UCB, however the constant factor is not the same. In the lower bound it uses KL divergences whereas in the upper bounds the constant is expressed in terms of the difference between the means. From Pinsker's inequality (see e.g. [START_REF] Cesa | Prediction, Learning, and Games[END_REF]) we have:

K(ν, κ) ≥ (E[ν]-E[κ]) 2
and the discrepancy between K(ν, κ) and (E[ν] -E[κ]) 2 can be very large (e.g. for Bernoulli distributions with parameters close to 0 or 1). It follows that there is a potentially large gap between the lower and upper bounds, which motivated several recent attempts to reduce this gap. The main line of research consisted in tightening the concentration inequalities defining the upper confidence bounds.

A first improvement was made by Audibert et al. [2009] who introduced UCB-V (UCB with variance estimate) that uses a variant of Bernstein's inequality to take into account the empirical variance of the rewards (in addition to their empirical mean) to define tighter UCB on the mean reward of the arms:

B t,s (k) def = μk,s + 2 V k,s log(1.2t) s + 3 log(1.2t) s , (1.15)
where V k,s is the empirical variance of the rewards received from arm k. They proved that the regret is bounded as follows:

ER n ≤ 10 k:Δ k >0 σ 2 k Δ k + 2 log(n),
which scales with the actual variance σ 2 k of the arms. Then Honda andTakemura [2010, 2011] proposed the DMED (Deterministic Minimum Empirical Divergence) algorithm and proved an asymptotic bound that achieves the asymptotic lower-bound of Burnetas and Katehakis [1996b]. Notice that Lai and [START_REF] Leung | Asymptotically efficient adaptive allocation rules[END_REF] and Burnetas and Katehakis [1996b] also provided an algorithm with asymptotic guarantees (under more restrictive conditions). It is only in [START_REF] Garivier | The KL-UCB algorithm for bounded stochastic bandits and beyond[END_REF], Maillard et al., 2011[START_REF] Cappé | Kullback-leibler upper confidence bounds for optimal sequential allocation[END_REF] that a finite-time analysis was derived for KL-based UCB algorithms, KL-UCB and K inf -UCB, that achieve the asymptotic lower bounds of [START_REF] Leung | Asymptotically efficient adaptive allocation rules[END_REF] and [Burnetas and Katehakis, 1996b] respectively. Those algorithms make use of KL divergences in the definition of the UCBs and use the full empirical reward distribution (and not only the two first moments). In addition to their improved analysis in comparison to regular UCB algorithms, several experimental studies showed their improved numerical performance.

Finally let us also mention that the logarithmic gap between the upper and lower problem-independent bounds (see (1.12) and (1.14)) has also been closed (up to a constant factor) by the MOSS algorithm of [START_REF] Audibert | Minimax policies for adversarial and stochastic bandits[END_REF], which achieves a minimax regret bound of order √ Kn.

Extensions to many arms

The principle of optimism in the face of uncertainty has been successfully extended to several variants of the multi-armed stochastic bandit problem, notably when the number of arms is large (possibly infinite) compared to the number of rounds. In those situations one cannot even pull each arm once and thus in order to achieve meaningful results we need to make some assumptions about the unobserved arms. There are two possible situations:

• When the previously observed arms do not give us any information about unobserved arms. This is the case when there is no structure in the rewards. In those situations, we may rely on a probabilistic assumption on the mean value of any unobserved arm.

• When the previously observed arms can give us some information about unobserved arms: this is the case of structured rewards, for example when the mean reward function is a linear, convex, or Lipschitz function of the arm position, or also when the rewards depend on some tree, graph, or combinatorial structure.

Unstructured rewards

The so-called many-armed bandit problem considers a countably infinite number of arms where there is no structure among arms. Thus at any round t the rewards obtained by pulling previously observed arms do not give us information about the value of the unobserved arms.

To illustrate, think of the problem of selecting a restaurant for dinner in a big city like Paris. Each day you go to a restaurant and receive a reward indicating how much you enjoyed the food you were served. You may decide to go back to one of the restaurants you have already visited either because the food there was good (exploitation) or because you have not been there many times and want to try another dish (exploration). However you may also want to try a new restaurant (discovery) chosen randomly (maybe according to some prior information). Of course there are many other applications of this explorationexploitation-discovery trade-off, such as in marketing (e.g. you want to send catalogs to good customers, uncertain customers, or random people), in mining for valuable resources (such as gold or oil) where you want to exploit good wells, explore unknown wells, or start digging at a new location.

A strong probabilistic assumption that has been made by [START_REF] Banks | Denumerable-armed bandits[END_REF], [START_REF] Berry | Bandit problems with infinitely many arms[END_REF] to model such situations is that the mean-value of any unobserved arm is a random variable that follows some known distribution. More recently this assumption

K(t) played arms

Arms not played yet has been weakened by [START_REF] Wang | Algorithms for infinitely many-armed bandits[END_REF] with an assumption focusing on this distribution upper tail only. More precisely, they assume that there exists β > 0 such that the probability that the mean-reward μ of a new randomly chosen arm is -optimal, is of order β :

P(μ(new arm) > μ * -) = Θ( β ), 1 (1.16)
where μ * = sup k≥1 μ k is the supremum of the mean-reward of the arms. Thus the parameter β characterizes the probability of selecting a near-optimal arm. A large value of β indicates that there is a small chance that a new random arm will be good, thus an algorithm trying to achieve a low regret (defined like in (1.1) with respect to μ * ) would have to pull many new arms. Conversely, if β is small, then there is a reasonably large probability that a very good arm will be obtained by pulling a small number of new arms.

The UCB-AIR (UCB with Arm Increasing Rule) strategy introduced in [START_REF] Wang | Algorithms for infinitely many-armed bandits[END_REF] consists of playing a UCB-V strategy [Audibert et al., 2009] (see (1.15)) on a set of current arms, whose number is increasing with time. At each round, either an arm already played is chosen according to the UCB-V strategy, or a new random arm is selected. Theorem 4 of [START_REF] Wang | Algorithms for infinitely many-armed bandits[END_REF] states that by selecting at each round t a number of active arms defined by

K(t) = ⎧ ⎨ ⎩ t β 2 if β < 1 and μ * < 1 t β β+1 if β ≥ 1 or μ * = 1
then the expected regret of UCB-AIR is upper-bounded as:

ER n ≤ ⎧ ⎨ ⎩ C log n 2 √ n if β < 1 and μ * < 1 C log n 2 n β 1+β if μ * = 1 or β ≥ 1 ,
where C is a (numerical) constant. This setting illustrates the exploration-exploitation-discovery tradeoff where exploitation means pulling an apparently good arm (based on previous observations), exploration means pulling an uncertain arm (already pulled), and discovery means trying a new (unknown) arm.

An important aspect of this model is that the coefficient β characterizes the probability of choosing randomly a near-optimal arm (thus the proportion of near-optimal arms), and the UCB-AIR algorithm requires the knowledge of this coefficient (since β is used for the choice of K( t )). An open question is whether it is possible to design an adaptive strategy that could show similar performance when β is initially unknown.

Here we see an important characteristic of the performance of the optimistic strategy in a stochastic bandit setting, that will appear several times in different settings in the next chapters: The performance of a sequential decision making problem in a stochastic environment depends on a measure of the quantity of near-optimal solutions, as well as on our knowledge about this quantity.

Structured bandit problems

In structured bandit problems we assume that the mean-reward of an arm is a function of some arm parameters, where the function belongs to some known class. This includes situations where "arms" denote paths in a tree or a graph (and the reward of a path being the sum of rewards obtained along the edges), or points in some metric space where the mean-reward function possesses a specific structure.

A well-studied case is the linear bandit problem where the set of arms X lies in a Euclidean space R d and the mean-reward function is linear with respect to (w.r.t.) the arm position x ∈ X : at time t, one selects an arm x t ∈ X and receives a reward r t def = μ(x t ) + t , where the mean-reward is μ(x) def = x•θ with θ ∈ R d is some (unknown) parameter, and t is a (centered, independent) observation noise. The cumulative regret is defined w.r.t. the best possible arm x * def = arg max x∈X μ(x):

R

n def = nμ(x * ) - n t=1 μ(x t ).
Several optimistic algorithms have been introduced and analyzed, such as the confidence ball algorithms in [START_REF] Dani | Stochastic linear optimization under bandit feedback[END_REF], as well as refined variants in [START_REF] Rusmevichientong | Linearly parameterized bandits[END_REF]Tsitsiklis, 2010, Abbasi-Yadkori et al., 2011]. See also [START_REF] Auer | Using confidence bounds for exploitation-exploration trade-offs[END_REF] for a pioneering work on this topic. The main bounds on the regret are either problemdependent, of the order O log n Δ (where Δ is the mean-reward difference between the best and second best extremal points), or problemindependent of the order2 O(d √ n). Several extensions to the linear setting have been considered, such as Generalized Linear models [START_REF] Filippi | Parametric bandits: The generalized linear case[END_REF] and sparse linear bandits [Carpentier andMunos, 2012, Abbasi-Yadkori et al., 2012].

Another popular setting is when the mean-reward function x → μ(x) is convex [START_REF] Flaxman | Online convex optimization in the bandit setting: gradient descent without a gradient[END_REF][START_REF] Agarwal | Stochastic convex optimization with bandit feedback[END_REF] in which case regret bounds of order O(poly(d)

√ n) can be achieved3 . Other weaker assumptions on the mean-reward function have been considered, such as Lipschitz condition [START_REF] Kleinberg | Nearly tight bounds for the continuum-armed bandit problem[END_REF], Agrawal, 1995a[START_REF] Auer | Improved rates for the stochastic continuum-armed bandit problem[END_REF], Kleinberg et al., 2008b] or even weaker local assumptions in [Bubeck et al., 2011a[START_REF] Valko | Stochastic simultaneous optimistic optimization[END_REF]. This setting of bandits in metric spaces as well as more general spaces will be further investigated in Chapters 3 and 4.

Conclusions

It is worth mentioning that there have been a huge development of the field of Bandit Theory over the last few years which have produced emerging fields such as contextual bandits (where the rewards depend on some observed contextual information), adversarial bandits (where the rewards are chosen by an adversary instead of being stochastic), and has drawn strong links with other fields such as online-learning (where a statistical learning task is performed online given limited feedback) and learning from experts (where one uses a set of recommendations given by experts). The interested reader may find additional references and developments in the following books and PhD theses [START_REF] Cesa | Prediction, Learning, and Games[END_REF][START_REF] Bubeck | Bandits Games and Clustering Foundations[END_REF], Maillard, 2011[START_REF] Bubeck | Regret analysis of stochastic and nonstochastic multi-armed bandit problems[END_REF].

This chapter presented a brief overview of the multi-armed bandit problem which can be seen as a tool for rapidly selecting the best action among a set of possible ones, under the assumption that each reward sample provides information about the value (mean-reward) of the selected action. In the next chapters we will use this tool as a building block for solving more complicated problems where the action space is structured (for example when it is a sequence of actions, or a path in a tree) with a particular interest for combining bandits in a hierarchy. The next chapter introduces the historical motivation for our interest in this problem while the later chapters provide algorithmic and theoretical contributions. This chapter presents the historical motivation for our involvement in the topic of hierarchical bandits. It starts with an experimental success: UCB-based bandits (see the previous chapter) used in a hierarchy demonstrated impressive performance for performing tree search in the field of Computer Go, such as in the Go programs Crazy-Stone [START_REF] Coulom | Efficient selectivity and backup operators in Monte-Carlo Tree Search[END_REF] and MoGo [Wang andGelly, 2007, Gelly et al., 2006]. This impacted the field of Monte-Carlo-Tree-Search (MCTS) [START_REF] Chaslot | Monte-Carlo Tree Search[END_REF][START_REF] Browne | A survey of monte carlo tree search methods[END_REF] which provided a simulation-based approach to game programming and has also been used in other sequential decision making problems. However, the analysis of the popular UCT (Upper Confidence Bounds applied to Trees) algorithm [START_REF] Kocsis | Bandit based Monte-Carlo planning[END_REF] have been a theoretical failure: the algorithm may perform very poorly (much worse than a uniform search) on toy problems and does not possess nice finite-time performance guarantees (see [START_REF] Coquelin | Bandit algorithms for tree search[END_REF]).

In this chapter we briefly review the initial idea of performing efficient tree search by assigning a bandit algorithm to each node of the search tree and following an optimistic search strategy that explores in priority the most promising branches (according to previous reward 19 samples). We then mention the theoretical difficulties and illustrate the possible failure of such approaches. This was the starting point for designing alternative algorithms (described in later chapters) with theoretical performance guarantees which will be analyzed in terms of a new measure of complexity.

Historical motivation: Computer-Go

The use of Monte-Carlo simulations in Computer Go started with the pioneering work of [START_REF] Brügmann | Monte Carlo Go[END_REF] followed by [START_REF] Bouzy | Computer Go: an AI oriented survey[END_REF], [START_REF] Bouzy | Monte-Carlo go developments[END_REF]. Note that a similar idea was introduced by [START_REF] Abramson | Expected-outcome: A general model of static evaluation[END_REF] for other games such as Othello. A position is evaluated by running many "playouts" (simulations of a sequence of random moves generated alternatively from the player and the adversary) starting from this position until a terminal configuration is reached. This enables to score each playout (where the winner is decided from a single count of the respective territories), and the empirical average of the scores provides an estimation of the position value. See the illustration in Figure 2.1. This method approximates the value of a Go position (which is actually the solution of a max-min problem) by an average. Notice that even when the number of runs goes to infinity, this average does not necessarily converge to the max-min value.

An important step was achieved by [START_REF] Coulom | Efficient selectivity and backup operators in Monte-Carlo Tree Search[END_REF] in his Crazy-Stone program. In this program, instead of selecting the moves according to a uniform distribution, the probability distribution over possible moves is updated after each simulation so that more weight is assigned to moves that achieved better scores in previous runs (see Figure 2.1, right). In addition, an incremental tree representation adding a leaf to the current tree representation at each playout enables the construction of an asymmetric tree where the most promising branches (according to the previously observed rewards) are explored to a greater depth.

This was the starting point of the so-called Monte-Carlo tree search (MCTS) method (see e.g. [START_REF] Chaslot | Monte-Carlo Tree Search[END_REF][START_REF] Browne | A survey of monte carlo tree search methods[END_REF]) that aims at approximating the solution of a max-min problem by a weighted

average.

This idea of starting with a uniform sampling over a set of available moves (or actions) and progressively focusing on the best actions according to previously observed rewards is reminiscent of the bandit strategy discussed in the previous chapter. The MoGo program initiated by Wang, Gelly, Teytaud, Coquelin and myself [Gelly et al., 2006] started from this simple observation and the idea of performing a tree search by assigning a bandit algorithm to each node of the tree. We started with the UCB algorithm and this lead to the so-called UCT (Upper Confidence Bounds applied to Trees) algorithm, which was independently developed and analyzed by [START_REF] Kocsis | Bandit based Monte-Carlo planning[END_REF]. Several major improvements (such as the use of features in the random playouts, the Rapid Action Value Estimation (RAVE), the parallelization of the algorithm, and the introduction of opening books) [START_REF] Gelly | Combining online and offline knowledge in UCT[END_REF][START_REF] Rimmel | Biasing Monte-Carlo simulations through RAVE values[END_REF][START_REF] Bourki | Scalability and parallelization of monte-carlo tree search[END_REF][START_REF] Silver | Reinforcement Learning and Simulation-Based Search in Computer Go[END_REF][START_REF] Chaslot | Monte-Carlo Tree Search[END_REF][START_REF] Gelly | Monte-carlo tree search and rapid action value estimation in computer Go[END_REF] enabled the MoGo program to rank among the best Computer Go programs (see e.g. [START_REF] Lee | The computational intelligence of MoGo revealed in Taiwan's computer Go tournaments[END_REF] and the URL http://www.lri.fr/∼teytaud/mogo.html) until 2012.

Upper Confidence Bounds in Trees

In order to illustrate the UCT algorithm [START_REF] Kocsis | Bandit based Monte-Carlo planning[END_REF], consider a tree search optimization problem on a uniform tree of depth D where each node has K children. A reward distribution ν i is assigned to each leaf i (there are K D such leaves) and the goal is to find the path (sequence of nodes from the root) to a leaf with highest mean-value

μ i def = E[ν i ].
Define the value of any node k as μ k def = max i∈L(k) μ i , where L(k) denotes the set of leaves that belong to the branch originating from k.

At any round t, the UCT algorithm selects a leaf I t of the tree and receives a reward r t ∼ ν It which enables it to update the B-values of all nodes in the tree. The way the leaf is selected is by following a path starting from the root and such that from each node j along the path, the next selected node is the one with highest B-value among the children nodes, where the B-value of any child k of node j is defined as:

B t (k) def = μk,t + c log T j (t) T k (t) , (2.1)
where c is a numerical constant, T k (t)

def = t s=1 1{I s ∈ L(k)}
is the number of paths that went through node k up to time t (and similarly for T j (t)), and μk,t is the empirical average of rewards obtained from leaves originating from node k, i.e., μk,t

def = 1 T k (t) t s=1 r s 1{I s ∈ L(k)}.
The intuition for the UCT algorithm is that at the level of a given node j, there are K possible choices, i.e. arms, corresponding to the children nodes, and the use of a UCB-type of bandit algorithm should enable the selection of the best arm given noisy rewards samples. Now, when the number of simulations goes to infinity, since UCB selects all arms infinitely often (indeed, thanks to the log term in the definition of the B-values (2.1), when a children node k is not chosen, its B-value increases and thus it will eventually be selected, as long as its parent j is), we deduce that UCT selects all leaves infinitely often.

Thus from an immediate backward induction from the leaves to the root of the tree we deduce that UCT is consistent, i.e. for any node k, lim t→∞ μt (k) = μ(k), almost surely.

The main reason why this algorithm demonstrated very interesting experimental performance in several large tree search problems is that it explores in priority the most promising branches according to previously observed sample rewards. This is very useful in situations where the reward function possesses some smoothness property (so that initial random reward samples provide information about where the search should focus) or when no other technique can be applied (e.g. in Computer Go where the branching factor is so large that regular minimax or alpha-beta methods fail). See [START_REF] Hyeong | Simulation-based Algorithms for Markov Decision Processes[END_REF][START_REF] Silver | Reinforcement Learning and Simulation-Based Search in Computer Go[END_REF][START_REF] Chaslot | Monte-Carlo Tree Search[END_REF][START_REF] Browne | A survey of monte carlo tree search methods[END_REF] and the references therein for different variants of MCTS and applications to games and other search, optimization, and control problems. These types of algorithms appear as possible alternatives to usual depth-first or breadth-first search techniques and apparently implement an optimistic exploration of the search space. Unfortunately in the next section we show that this algorithm does not enjoy tight finite-time performance guarantee and may perform very poorly even on some toy problems.

Poor finite-time performance

The main problem comes from the fact that the reward samples r t obtained from any node k are not independent and identically distributed (i.i.d.). Indeed, such a reward r t ∼ ν It depends on the selected leaf I t ∈ L(k), which itself depends on the arm selection process along the path from node k to the leaf I t , thus potentially on all previously observed rewards. Thus the B-values B t (k) defined by (2.1) do not define high-probability upper-confidence-bounds on the value μ k of the arm (i.e. we cannot apply Chernoff-Hoeffding inequality). Thus the analysis of the UCB algorithm seen in Section 1.1.2 does not apply.

The potential risk of UCT is to stop exploring the optimal branch too early because the current B-value of that branch is under-estimated. It is true that the algorithm is consistent (as discussed previously) and the optimal path will eventually be discovered but the time it takes for the algorithm to do so can be desperately long.

This point is described in [START_REF] Coquelin | Bandit algorithms for tree search[END_REF] with an illustrative example reproduced in Figure 2.2. This is a binary tree of depth D. The rewards are deterministic and defined as follows: For any node of depth d < D in the optimal branch (rightmost one), if Left action is chosen, then a reward of D-d D is received (all leaves in this branch have the same reward). If Right action is chosen, then this moves to the next node in the optimal branch. At depth D -1, Left action yields reward 0 and Right action reward 1.

For this problem, as long as the optimal reward has not been observed, from any node along the optimal path, the left branches seem better than the right ones and are thus explored exponentially more often (since out of n samples, UCB pulls only O(log n) times sub-optimal arms, as seen in previous chapter). Therefore, the time required before the optimal leaf is eventually reached is huge and we can deduce the following lower-bound on the regret of UCT:

R n = c exp(exp(. . . exp( D times 1) . . . )) + Ω(log(n)),
for some constant c. The first term of this bound is a constant independent of n (thus the regret is asymptotically of order log n as proven in [START_REF] Kocsis | Bandit based Monte-Carlo planning[END_REF]) but this constant is "D-uply" exponential. In particular this is much worse than a uniform sampling of all the leaves which will be "only" exponential in D.

The reason why this is a particularly hard problem for UCT is that, as long as the optimal reward has not been discovered, the previous rewards collected by the algorithm are very misleading, at any level of the tree, since they force the algorithm to explore for a very long time the left (sub-optimal) branches of the tree before going deeper along the optimal branch. But more deeply, the main reason for this failure is that the B-values computed by UCT do not represent highprobability upper-confidence-bounds on the true value of the nodes (since the rewards collected at any node are not i.i.d.), thus UCT does not implement the optimism in the face of uncertainty principle.

Conclusion

The previous observation represents our initial motivation for the research described in the following chapters. We have seen that UCT is very efficient in some well-structured problems and very inefficient in other, tricky problems (the vast majority...). Our objective is now to recover the optimism in the face of uncertainty principle and for that purpose we want to define a problem-dependent measure characterizing the complexity of optimization. We will do so by defining a notion of local smoothness property of the mean-reward function. This will be used to derive optimistic algorithms, which build correct highprobability UCBs, and enjoy tight finite-time performance guarantees that can be expressed in terms of this complexity measure in situations where this measure is known, and when it is not.

In this chapter we consider the optimism in the face of uncertainty principle applied to the problem of black-box optimization of a function f given (deterministic or stochastic) evaluations of the function.

We search for a good approximation of the maximum of a function f : X → R using a finite number n (i.e. the numerical budget) of function evaluations. More precisely, we want to design a sequential exploration strategy A of the search space X , i.e. a sequence x 1 , x 2 , . . . , x n of states of X , where each x t may depend on previously observed values f (x 1 ), . . . , f(x t-1 ), such that at round n (which may or may not be known in advance), the algorithm A recommends a state x(n) with the highest possible value. The performance of the algorithm is assessed by the loss (or simple regret):

r n = sup x∈X f (x) -f (x(n)). (3.1)
Here the performance criterion is the closeness to optimality of the recommendation made after n evaluations to the function. This criterion is different from the cumulative regret previously defined in the multi-armed bandit setting (see Chapter 1):

R n def = n sup x∈X f (x) - n t=1 f (x t ), (3.2)
which measures how well the algorithm succeeds in selecting states with good values while exploring the search space (notice that we write x 1 , . . . , x n as the states selected for evaluation, whereas x(n) refers to the recommendation made by the algorithm after n observations, and may differ from x n ). The two settings provide different exploration-exploitation tradeoffs in the multi-armed bandit setting (see [START_REF] Bubeck | Pure exploration in multi-armed bandits problems[END_REF][START_REF] Audibert | Best arm identification in multi-armed bandits[END_REF] for a thorough comparison between the settings).

In this chapter we prefer to consider the loss criterion (3.1), which induces a so-called numerical exploration-exploitation trade-off, since it more naturally relates to the problem of function optimization given a finite numerical budget (whereas the cumulative regret (3.2) mainly applies to the problem of optimizing while learning an unknown environment).

Since the literature on global optimization is very important, we only mention the works that are closely related to the optimistic strategy described here. A large body of algorithmic work has been developed using branch-and-bound techniques [START_REF] Neumaier | Interval Methods for Systems of Equations[END_REF][START_REF] Hansen | Global Optimization Using Interval Analysis[END_REF][START_REF] Kearfott | Rigorous Global Search: Continuous Problems[END_REF][START_REF] Horst | Global Optimization ? Deterministic Approaches[END_REF][START_REF] Pintér | Global Optimization in Action (Continuous and Lipschitz Optimization: Algorithms, Implementations and Applications[END_REF][START_REF] Floudas | Deterministic Global Optimization: Theory, Algorithms and Applications[END_REF][START_REF] Strongin | Global Optimization with Non-Convex Constraints: Sequential and Parallel Algorithms[END_REF] such as Lipschitz optimization where the function is assumed to be globally Lipschitz. For illustration purpose, Section 3.1 provides an intuitive introduction to the optimistic optimization strategy in the case where the function is assumed to be Lipschitz. The next sample is chosen to be the maximum of an upperbounding function which is built from previously observed values and knowledge of the function smoothness. This enables the algorithm to achieve a good numerical exploration-exploitation trade-off that makes an efficient use of the available numerical resources in order to rapidly estimate the maximum of f . However the main contribution of this chapter (starting from Section 3.2 where the general setting is introduced) is to considerably weaken the assumptions made in most of the previous literature since we do not require the space X to be a metric space but only to be equipped with a semi-metric , and we relax the assumption that f is globally Lipschitz in order to consider the much weaker assumption that f is locally smooth w.r.t. (this definition is made precise in Section 3.2.2). In this chapter we assume that the semi-metric (under which f is smooth) is known. The next chapter will consider the case when it is not.

The case of deterministic evaluations is presented in Section 3.3 where a first algorithm, Deterministic Optimistic Optimization (DOO) is introduced and analyzed. In Section 3.4, the same ideas are extended to the case of stochastic evaluations of the function, which corresponds to the so-called X -armed bandit, and two algorithms, Stochastic Optimistic Optimization (StoOO) and Hierarchical Optimistic Optimization (HOO) are described and analyzed.

The main contribution of this chapter is a characterization of the complexity of these optimistic optimization algorithms by means of a measure of the quantity of near-optimal states of the mean-rewards function f measured by some semi-metric , which is called the nearoptimality dimension of f w.r.t. . We show that if the behavior, or local smoothness, of the function around its (global) maxima is known, then one can select the semi-metric such that the corresponding near-optimality dimension is 0, implying very efficient optimization algorithms (whose loss rate does not depend on the space dimension). However their performance deteriorates when this smoothness is not known or incorrectly estimated.

Illustrative example

In order to illustrate the approach, we consider the simple case where the space X is metric (let denote the metric) and the function f : X → R is assumed to be Lipschitz continuous under , i.e., for all x, y ∈ X , |f (x)f (y)| ≤ (x, y).

(3.3)

Define the numerical budget n as the total number of calls to the function. At each round for t = 1 to n, the algorithm selects a state x t ∈ X , then either (in the deterministic case) observes the exact value of the function f (x t ), or (in the stochastic case) observes a noisy estimate

r t of f (x t ), such that E[r t |x t ] = f (x t ).
This chapter is informal and all theoretical results are deferred to the next chapters. The only purpose of this chapter is to provide some intuition about the optimistic approach for the optimization problem.

Deterministic setting

In this setting, the evaluations are deterministic, thus exploration does not refer to improving our knowledge about some stochastic environment but consists of evaluating the function at unknown but possibly important areas of the search space, in order to estimate the global maximum of the function.

Given that the function is Lipschitz continuous and that we know , an evaluation of the function f (x t ) at any point x t enables to define an upper bounding function for f , since for all x ∈ X , f (x) ≤ f (x t ) + l(x, x t ). This upper bounding function can be refined after each evaluation of f by taking the minimum of the previous upper-bounds (see illustration on Figure 3.1): for all x ∈ X ,

f (x) ≤ B t (x) def = min 1≤s≤t [f (x s ) + l(x, x s )] .
(3.4)

Now, the optimistic approach consists of selecting the next state x t+1 as the point with highest upper bound:

x t+1 = arg max x∈X B t (x).
(3.5)

We can say that this strategy follows an "optimism in the face of computational uncertainty" principle. The uncertainty does not come from the stochasticity of some unknown environment (as it was the case in the stochastic bandit setting), but from the uncertainty about the function given that the search space may be infinite and we possess a finite computational budget only.

Remark 3.1. Notice that we only need the property that B t (x) is an upper-bound on f (x) at the (global) maxima x * of f . Indeed, the algorithm selecting at each round a state arg max x∈X B t (x) will not be affected by having a B t (x) function under-evaluating f (x) at sub-optimal Optimistic optimization with known smoothness points x = x * . Thus in order to apply this optimistic sampling strategy, one really needs (3.4) to hold for x * only (instead of requiring it for all x ∈ X ). Thus we see that the global Lipschitz assumption (3.3) may be replaced by the much weaker assumption that for all x ∈ X , f (x * )f (x) ≤ (x, x * ). This important extension will be further detailed in Section 3.2.

f(x ) t x t f f *
Several issues remain to be addressed: (1) How do we generalize this approach to the case of stochastic rewards? (2) How do we deal with the computational problem of computing the maximum of the upper-bounding function in (3.5)? Question 1 is the object of the next subsection, and Question 2 will be addressed by considering a hierarchical partitioning of the space that will be discussed in Section 3.2.

Stochastic setting

Now consider the stochastic case, where the evaluations to the function are perturbed by noise (see Figure 3.2). More precisely, an evaluation of f at x t returns a noisy estimate r t of f (x t ) where we assume that

E[r t |x t ] = f (x t ).
In order to follow the optimism in the face of uncertainty principle, one would like to define a high probability upper bounding function B t (x) on f (x) at all states x ∈ X and select the point with highest bound arg max x∈X B t (x). So the question is how to define this UCB function.

A possible answer to this question is to consider a given subset X i ⊂ X containing x and define a UCB on f over X i . This can be done by averaging the rewards observed by points sampled in X i and using the Lipschitz assumption on f . More precisely, let T i (t) def = t u=1 1{x u ∈ X i } be the number of points sampled in X i at time t and let τ s be the absolute time instant when a point in X i was sampled for the s-th time, i.e. τ s = min{u :

T i (u) = s}. Notice that t u=1 (r u -f (x u ))1{x u ∈ X i } = T i (t)
s=1 (r τsf (x τs )) is a Martingale (w.r.t. the filtration generated by the sequence {(r τs , x τs )} s ) and we have

P 1 T i (t) T i (t) s=1 r τs -f (x τs ) ≤ -t,T i (t) ≤ P ∃1 ≤ u ≤ t, 1 u u s=1 r τs -f (x τs ) ≤ -t,u ≤ t u=1 P 1 u u s=1 r τs -f (x τs ) ≤ -t,u ≤ t u=1 e -2u 2 t,u , x xτ s rτ s f (xτ s ) diam(Xi)
Upper-bound

x log t/δ 2Ti(t) 1 Ti(t) Ti(t)
s=1 rτ s Figure 3.3: A possible way to define a high-probability bound on f at any x ∈ X is to consider a subset Xi x and average the Ti(t) rewards obtained in this subset t) , and add the diameter diam(Xi). This defines an UCB (with probability 1η) on f at any x ∈ Xi.

T i (t) s=1 rτ s , then add a confidence interval term log(t/η) 2T i (
where we used a union bound in the third line and Hoeffding-Azuma inequality [START_REF] Azuma | Weighted sums of certain dependent random variables[END_REF] in the last derivation. For any η > 0, setting

t,u def = log(t/η) 2u
we deduce that with probability 1η, we have

1 T i (t) T i (t) s=1 r τs + log(t/η) 2T i (t) ≥ 1 T i (t) T i (t) s=1 f (x τs ).
(3.6)

Now we can use the Lipschitz property of f to define a high probability UCB on sup x∈X i f (x). Indeed each element of the sum in the r.h.s. of (3.6) is bounded as f (x τs ) ≥ max x∈X i f (x)diam(X i ), where the diameter of X i is defined as diam(X i ) def = max x,y∈X i (x, y). We deduce that with probability 1η, we have

B t,T i (t) (X i ) def = 1 T i (t) T i (t) s=1 r τs + log t/η 2T i (t) + diam(X i ) ≥ max x∈X i f (x). (3.7) The UCB B t,T i (t) (X i ) is illustrated in Figure 3.3.
Remark 3.2. We see a trade-off in the choice of the size of X i : The bound (3.7) is poor either (1) when diam(X i ) is large, or (2) when X i contains so few samples (i.e. T i (t) is small) that the confidence interval width is large. Ideally we would like to consider several possible subsets X i (of different size) containing a given x ∈ X and define several UCBs on f (x) and select the tightest one:

B t (x) def = min i;x∈X i B t,T i (t) (X i ).
Now, an optimistic strategy would simply compute the tightest UCB at each state x ∈ X according to the rewards already observed, and choose the next state to sample as the one with highest UCB, like in (3.5). However this poses several problems: (1) One cannot consider concentration inequalities on an arbitrarily large number of subsets (since we would need a union bound over a too large number of events), (2) From a computational point of view, it may not be easy to compute the maximum point of the bounds if the shapes of the subsets are arbitrary.

In order to provide a simple answer to those two issues we consider a hierarchical partitioning of the space. This is the approach followed in the next section, which introduces the general setting.

General setting

Hierarchical partitioning

In order to address the computational problem of computing the optimum of the upper-bound (3.5) described above, our algorithms will make use of a hierarchical partitioning of the space X .

More precisely, we consider a set of partitions of X at all scales h ≥ 0: For any integer h, X is partitioned into a set of K h subsets X h,i (called cells), where 0 ≤ i ≤ K h -1. This partitioning may be represented by a K-ary tree where the root corresponds to the whole domain X (cell X 0,0 ) and each cell X h,i corresponds to a node (h, i) of the tree (indexed by its depth h and index i), and each node (h, i)

possesses K children nodes {(h + 1, i k )} 1≤k≤K such that the associated cells {X h+1,i k , 1 ≤ k ≤ K} form a partition of the parent's cell X h,i . See Figure 3.4.
In addition, to each cell X h,i is assigned a specific state x h,i ∈ X h,i , that we call the center of X h,i where f may be evaluated.

Assumptions

We now make 4 assumptions: Assumption 1 is about the semi-metric , Assumption 2 is about the smoothness of the function w.r.t. , and Assumptions 3 and 4 are about the shape of the hierarchical partitioning w.r.t. . Assumption 1 (Semi-metric). We assume that X is equipped with a semi-metric : X × X → R + . We recall that this means that for all x, y ∈ X , we have (x, y) = (y, x) and (x, y) = 0 if and only if x = y.

Note that we do not require that satisfies the triangle inequality (in which case, would be a metric). An example of a metric space is the Euclidean space R d with the metric (x, y) = xy (Euclidean norm). Now consider R d with (x, y) = x-y α , for some α > 0. When α ≤ 1, then is also a metric, but whenever α > 1 then does not satisfy the triangle inequality anymore, and is thus a semi-metric only. Now we state our assumption about the function f .

Assumption 2 (Local smoothness of f ).

There exists at least one global optimizer

x * ∈ X of f (i.e., f (x * ) = sup x∈X f (x)) and for all x ∈ X , f (x * ) -f (x) ≤ (x, x * ). (3.8)
This condition guarantees that f does not decrease too fast around (at least) one global optimum x * (this is a sort of a locally onesided Lipschitz assumption). Note that although it is required that (3.8) be satisfied for all x ∈ X , this assumption essentially sets constraints to the function f locally around x * (since at x such that (x, x * ) > range(f ) property holds, we say that f is locally smooth w.r.t. around its maximum. See an illustration in Figure 3.5. Now we state the assumptions about the hierarchical partitioning.

def = sup f -inf f the assumption is void). When this x * X f (x * ) f f (x * ) -(x, x * )

Assumption 3 (Decreasing diameters).

There exists a decreasing sequence δ(h) > 0, such that for any depth h ≥ 0 and for any cell X h,i of depth h, we have sup

x∈X h,i (x h,i , x) ≤ δ(h).
Assumption 4 (Well-shaped cells). There exists ν > 0 such that for any depth h ≥ 0, any cell X h,i contains a -ball of radius νδ(h) centered in x h,i .

In this chapter, we consider the setting where Assumptions 1-4 hold for a specific semi-metric , and that the semi-metric is known to the algorithm.

Deterministic Optimistic Optimization

The Deterministic Optimistic Optimization (DOO) algorithm described in Figure 3.6 uses the knowledge of through the use of δ(h).

DOO builds incrementally a tree T t for t = 1 . . . n, starting with the root node T 1 = {(0, 0)}, and by selecting at each round t a leaf of the current tree T t to expand. Expanding a leaf means adding its

Initialization: T 1 = {(0, 0)} (root node) for t = 1 to n do Select the leaf (h, j) ∈ L t with maximum b h,j def = f (x h,j )+δ(h) value.
Expand this node: add to T t the K children of (h, j) and evaluate the function at the points {x h+1,j1 , . . . , x h+1,jK } end for Return x(n) = arg max (h,i)∈Tn f (x h,i ) K children to the current tree (this corresponds to splitting the cell X h,j into K children-cells {X h+1,j 1 , . . . , X h+1,j K }) and evaluating the function at the centers {x h+1,j 1 , . . . , x h+1,j K } of the children cells. We write L t the leaves of T t (set of nodes whose children are not in T t ), which are the set of nodes that can be expanded at round t.

The algorithm computes a b-value b h,j def = f (x h,j ) + δ(h) for each leaf (h, j) ∈ L t of the current tree T t and selects the leaf with highest bvalue to expand next. Once the numerical budget is over (here, n node expansions corresponds to nK function evaluations), DOO returns the evaluated state

x(n) ∈ {x h,i , (h, i) ∈ T n } with highest value.
This algorithm follows an optimistic principle because it expands at each round a cell that may contain the optimum of f , based on the information about (i) the previously observed evaluations of f , and (ii) the knowledge of the local smoothness property (3.8) of f (since is known).

Thus the use of the hierarchical partitioning provides a computationally efficient implementation of the optimistic sampling strategy described in Section 3.1 and illustrated in Figure 3.1, where the (possibly complicated) problem of selecting the state with highest upperbound (3.5) is replaced by the (easy) selection process of the leaf with highest b-value.

Analysis of DOO

Notice that Assumption 2 implies that the b-value of any cell containing x * upper bounds f * , i.e., for any cell

X h,i such that x * ∈ X h,i , b h,i = f (x h,i ) + δ(h) ≥ f (x h,i ) + (x h,i , x * ) ≥ f * .
As a consequence, a leaf (h, i) such that f (x h,i ) + δ(h) < f * will never be expanded (since at any time t, the b-value of such a leaf will be dominated by the b-value of the leaf containing x * ). We deduce that DOO only expands nodes in the set I def = ∪ h≥0 I h , where

I h def = {nodes (h, i) such that f (x h,i ) + δ(h) ≥ f * }.
In order to derive a loss bound we now define a measure of the quantity of near-optimal states, called near-optimality dimension. This measure is closely related to similar measures introduced in [Kleinberg et al., 2008b[START_REF] Bubeck | Online optimization of X-armed bandits[END_REF]. For any > 0, let us write

X def = {x ∈ X , f(x) ≥ f * -}
the set of -optimal states.

Definition 3.1. The η-near-optimality dimension is the smallest d ≥ 0 such that there exists C > 0, for all > 0, the maximal number of disjoint -balls of radius η with center in X is less than

C -d .
Note that d is not an intrinsic property of f : it characterizes both f and (since we use -balls in the packing of near-optimal states), and also depends on the constant η. However it does not depend on the hierarchical partitioning of the space. Thus it is a measure of the function and the semi-metric space only, but not of any specific algorithm. Now, in order to relate this measure to the specificities of the algorithm (in order to bound the cardinality of the sets I h , see Lemma 3.1), we need to relate it to the properties of the partitioning, in particular the shape of the cells, which is the reason why d depends on the constant η, which will be chosen according to ν, as defined in Assumption 4.

Remark 3.3. Notice that in the definition of the near-optimality dimension, we require the packing property to hold for all > 0. We can relax this assumption and define a local near-optimality dimension by requiring this packing property to hold for all ≤ 0 only, for some 0 ≥ 0. If the space X is bounded and has finite packing dimension (i.e. X can be packed by C -D -balls of size , for any > 0), then the near-optimality and local near-optimality dimensions coincide. Only the constant C in their definition may change.

Indeed, let d be the near-optimality dimension and C the corresponding constant where the packing property is required for all > 0 (as defined in Assumption 3.1). Thus by setting C 0 = max(C, C -D 0 ) we have that the local near-optimality dimension (where the packing property is required to hold for ≤ 0 only) is the same d with C 0 being the corresponding constant.

Thus we see that the near-optimality dimension d captures a local property of f near x * whereas the corresponding constant C may depend on the global shape of f . We now bound the number of nodes in I h using the near-optimality dimension.

Lemma 3.1. Let d be the ν-near-optimality dimension (where ν is defined in Assumption 4), and C the corresponding constant. Then

|I h | ≤ Cδ(h) -d . Proof. From Assumption 4, each cell (h, i) contains a ball of radius νδ(h) centered in x h,i , thus if |I h | = |{x h,i ∈ X δ(h) }| exceeded Cδ(h) -d ,
this would mean that there exists more than Cδ(h) -d disjoint -balls of radius νδ(h) with center in X δ(h) , which would contradict the definition of d.

We now provide our loss bound for DOO.

Theorem 3.2. Let us write h(n) the smallest integer h such that

C h l=0 δ(l) -d ≥ n.
Then the loss of DOO is bounded as

r n ≤ δ(h(n)).
Proof. Let (h max , j max ) be the deepest node that has been expanded by the algorithm up to round n. We known that DOO only expands nodes in the set I. Thus the number of expanded nodes n is such that

n = hmax l=0 K l -1 j=0 1{(h, j) has been expanded} ≤ hmax l=0 |I l | ≤ C hmax l=0 δ(l) -d , from Lemma 3.1. Now from the definition of h(n) we have h max ≥ h(n).
Finally, since node (h max , j max ) has been expanded, we have that (h max , j max ) ∈ I, thus

f (x(n)) ≥ f (x hmax,jmax ) ≥ f * -δ(h max ) ≥ f * -δ(h(n)).
Now, let us make the bound more explicit when the diameter δ(h) of the cells decreases exponentially fast with their depth (this case is rather general as illustrated in the examples described next, as well as in the discussion in [Bubeck et al., 2011a]).

Corollary 3.3. Assume that δ(h) = cγ h for some constants c > 0 and γ < 1.

• If d > 0, then the loss decreases polynomially fast:

r n ≤ C 1 -γ d 1/d n -1/d .
• If d = 0, then the loss decreases exponentially fast:

r n ≤ cγ (n/C)-1 . Proof. From Theorem 3.2, whenever d > 0 we have n ≤ C h(n) l=0 δ(l) -d = Cc -d γ -d(h(n)+1) -1 γ -d -1 , thus γ -dh(n) ≥ n Cc -d 1 -γ d , from which we deduce that r n ≤ δ(h(n)) ≤ cγ h(n) ≤ C 1 -γ d 1/d n -1/d . Now, if d = 0 then n ≤ C h(n) l=0 δ(l) -d = C(h(n) + 1
), and we deduce that the loss is bounded as

r n ≤ δ(h(n)) = cγ (n/C)-1 .
Remark 3.4. Notice that in Theorem 3.2 and Corollary 3.3 the loss bound is expressed in terms of the number of node expansions n. The corresponding number of function evaluations is Kn (since each node expansion generates K children where the function is evaluated).

Examples

Example 1:

Let X = [-1, 1] D and f be the function f (x) = 1-x α
∞ , for some α ≥ 0. Consider a K = 2 D -ary tree of partitions with (hyper)squares. Expanding a node means splitting the corresponding square in 2 D squares of half length. Let x h,i be the center of any cell X h,i .

Consider the following choice of the semi metric: (x, y) = x-y β ∞ , with β ≤ α. We have δ(h) = 2 -hβ (recall that δ(h) is defined in terms of ), and ν = 1. The optimum of f is x * = 0 and f satisfies the local smoothness property (3.8). Now let us compute its near-optimality dimension. For any > 0, X is the L ∞ -ball of radius 1/α centered in 0, which can be packed by

r n ≤ 2 1-n .
It is interesting to compare this result to a uniform sampling strategy (i.e., the function is evaluated at the set of points on a uniform grid), which would provide a loss of order n -α/D . We observe that DOO is better than uniform whenever α < 2β and worse when α > 2β.

This result provides some indication on how to choose the semimetric (thus β), which is a key ingredient of the DOO algorithm (since δ(h) = 2 -hβ appears in the b-values): β should be as close as possible to the true α (which can be seen as a local smoothness order of f around its maximum), but never larger than α (otherwise f does not satisfy the local smoothness property (3.8) any more).

Example 2: The previous analysis generalizes to any function that is locally equivalent toxx * α , for some α > 0 (where • is any norm, e.g., Euclidean, L ∞ , or L 1 ), around a global maximum x * (among a set of global optima assumed to be finite). More precisely, we assume that there exists constants c 1 > 0, c 2 > 0, c > 0, such that

f (x * ) -f (x) ≤ c 1 x -x * α , for all x ∈ X , f (x * ) -f (x) ≥ c 2 min(c, x -x * ) α , for all x ∈ X . Let X = [0, 1] D . Again, consider a K = 2 D -
ary tree of partitions with (hyper)-squares. Let (x, y) = c xy β with c 1 ≤ c and β ≤ α (so that f satisfies (3.8)). For simplicity we do not make explicit all the constants using the O notation for convenience (the actual constants depend on the choice of the norm • ). We have δ(h) = O(2 -hβ ). Now, let us compute the local near-optimality dimension. For any small enough > 0, X is included in a ball of radius ( /c 2 ) 1/α centered in x * , which can be packed by O Thus we see that the behavior of the algorithm depends on our knowledge of the local smoothness (i.e. α and c 1 ) of the function around its maximum. Indeed, if this smoothness information is available, then one should define the semi-metric (which impacts the algorithm through the definition of δ(h)) to match this smoothness (i.e. set β = α) and derive an exponential loss rate. Now if this information is unknown, then one should underestimate the true smoothness (i.e. by choosing β ≤ α) and suffer a loss

r n = O n -1 D αβ α-β ,
rather than overestimating it (β > α) since in this case, (3.8) may not hold anymore and there is a risk that the algorithm converges to a local optimum (thus suffering a constant loss).

Illustration

We consider the optimization of the function f (x) = sin(13x) sin(27x) + 1 /2 in the interval X = [0, 1] (plotted in Figure 3.7). The global optimum is x * ≈ 0.86442 and f * ≈ 0.975599. Figure 3.7 shows two simulations of DOO, both using a numerical budget of n = 150 evaluations to the function, but using two different semi-metrics . In the first case (left figure), we used the property that f is globally Lipschitz and its maximum derivative is max x∈[0,1] |f (x)| ≈ 13.407.

Thus with the metric 1 (x, y) def = 14|x -y|, f is Lipschitz w.r.t. 1 and (3.8) holds. We remind that DOO algorithm requires the knowledge of the metric since the diameters δ(h) are defined in terms of this metric. Thus since we considered a dyadic partitioning of the space (i.e. K = 2), we used δ(h) = 14 × 2 -h in the algorithm.

In the second case (right figure), we used the property that f (x * ) = 0, thus f is locally quadratic around x * . Since f (x * ) ≈ 443.7, using a Taylor expansion of order 2 we deduce that f is locally smooth (i.e. satisfies (3.8)) w.r.t. 2 (x, y) def = 222|x -y| 2 . Thus here we defined

δ(h) = 222 × 2 -2h .
Table 3.8 reports the numerical loss of DOO with these two metrics.

As mentioned in previous subsection, the behavior of the algorithm heavily depends on the choice of metric. Although f is locally smooth (i.e. satisfies (3.8)) w.r.t. both metrics, the near-optimality of f w.r.t.

1 is d = 1/2 (as discussed in Example 2 above) whereas it is d = 0 w.r.t. 2 .
Thus 2 is better suited for optimizing this function since in that case, the loss decreases exponentially fast with the number of evaluations (instead of polynomially when using 1 ). The choice of the constants in the definition of the metric is also important. If we were to use a larger constant in the definition of the metric, the effect would be a more uniform exploration of the space at the beginning. This will impact the constant factor in the loss bound but not the rate (since the rate only depends on the near-optimality dimension d which characterizes a local behavior of f around x * whereas the corresponding constant C depends on the global shape of f ). Now, we should be careful of not selecting a metric (such as

3 (x, y) def = |x -y| 3
) which would overestimate the true smoothness of f around its optimum since in this case (3.8) would not hold anymore and the algorithm might not converge to the global optimum at all (it can be stuck in a local maximum).

Thus we see that the main technical difficulty when applying this optimistic optimization methods is the possible lack of knowledge about the smoothness of the function around its maximum (or equivalently the metric under which the function is locally smooth). In Chapter 4 we will consider adaptive techniques that apply even when this smoothness is unknown. But before this, let us discuss the stochastic case in the next section.

X -armed bandits

We now consider the case of noisy evaluations of the function, as in Subsection 3.1.2: At round t, the observed value (reward) is

r t = f (x t )+
t , where t is an independent sample of a random variable (whose law may depend on x t ) such that E[ t |x t ] = 0. We also assume that the rewards r t are bounded in [0, 1]. Thus the setting is a stochastic multiarmed bandit with the set of arms being X . There are several ways to extend the deterministic case described in the previous section to this stochastic setting.

The simplest way consists of sampling several times each point in order to build an accurate estimate of the value at that point, before deciding to expand the corresponding node. This leads to a direct extension of DOO where an additional term in the definition of the b-values accounts for a high-probability estimation interval. The corresponding algorithm is called Stochastic DOO (StoOO) and is close in spirit to the Zooming algorithm of Kleinberg et al. [2008b]. The analysis is simple but the time horizon n needs to be known in advance (thus this is not an anytime algorithm). This algorithm is described in Subsection 3.4.1. Now, another way consists of expanding the selected node each time we collect a sample. Thus the sampled points may always be different. In that case we can use the approach illustrated in Subsection 3.1.2 to generate high-probability upper bounds on the function in each cell of the tree in order to define a procedure to select in an optimistic way a leaf to expand at each round. The corresponding algorithm, Hierarchical Optimistic Optimization (HOO), is described in Subsection 3.4.2. The benefit is that HOO does not require the knowledge of the time horizon n (thus is anytime) and is more efficient in practice than StoOO (although this improvement is not reflected in the loss bounds). However it requires a slightly stronger assumption on the smoothness of the function.

Stochastic Optimistic Optimization (StoOO)

In the stochastic version of DOO the algorithm computes the b-values of all the leaves (h, j) ∈ L t of the current tree as

b h,j (t) def = μh,j (t) + log(n 2 /η) 2T h,j (t) + δ(h), (3.9)
where μh,j (t)

def = 1 T h,j (t) t s=1 r s 1{x s ∈ X h,j } is the empirical average of the rewards received in X h,j , and T h,j (t) def = t s=1 1{x s ∈ X h,j
} is the number of times (h, j) has been selected up to time t. We use the convention that if a node (h, j) has not been sampled at time t then T h,j (t) = 0 and its b-value is +∞.

Parameters: error probability η > 0, time horizon n Initialization: T 1 = {(0, 0)} (root node) for t = 1 to n do For each leaf (h, j) ∈ L t , compute the b-values b h,j (t) according to (3.9). Select (h t , j t ) = arg max (h,j)∈Lt b h,j (t)

Sample state x t def = x ht,jt and collect reward

r t = f (x t ) + t . If T h,j (t) ≥ log(n 2 /η)
2δ(h) 2 , expand this node: add to T t the K children of (h, j) end for Return the deepest node among those that have been expanded: The algorithm is similar to DOO, see Figure 3.9, except that a node (h, j) is expanded only if x h,j has been sampled at least a certain number of times. Another noticeable difference is that the algorithm returns a state x(n) which is the deepest among all nodes that have been expanded up to round n.

x(n) = arg max x h,j :(h,j)∈Tn\Ln h.

Analysis of StoOO:

For any η > 0, define the following event

ξ def = ∀h ≥ 0, ∀0 ≤ i < K h , ∀1 ≤ t ≤ n, μh,j (t) -f (x h,j ) ≤ log(n 2 /η) T h,j (t) . (3.10)
We now prove that this event holds with high probability:

Lemma 3.4. We have P(ξ) ≥ 1η.

Proof. Let m ≤ n be the (random) number of nodes expanded throughout the algorithm. For 1 ≤ i ≤ m, write t i as the time when the i-th node is expanded, and ( hi , ji ) = (h t i , j t i ) the corresponding node. Using "local clocks", denote by τ s i the time when the node ( hi , ji ) has been selected for the s-th time and write rs i = r τ s i the reward obtained at that time. Note that (h τ s i , j τ s i ) = ( hi , ji ). Using these notations, the event ξ can be redefined as

ξ = ∀1 ≤ i ≤ m, ∀1 ≤ u ≤ T hi , ji (n), 1 u u s=1 rs i -f (x hi , ji ) ≤ log(n 2 /η) u . Since we have E[r s i |x hi , ji ] = f (x hi , ji ), then t s=1 rs i -f (x hi , ji
) is a Martingale (w.r.t. the filtration generated by the samples collected at x hi , ji ), and Azuma's inequality [START_REF] Azuma | Weighted sums of certain dependent random variables[END_REF] applies. Taking a union bound over the number of samples u ≤ n and the number m ≤ n of expanded nodes, we deduce the result.

We now show that in this event of high probability StoOO only expands nodes that are near-optimal. Indeed, similarly to the analysis of DOO, define the sets

I h def = {nodes (h, i) such that f (x h,i ) + 3δ(h) ≥ f * }.
Lemma 3.5. In the event ξ, StoOO only expands nodes that belong to the set

I def = ∪ h≥0 I h .
Proof. Let (h t , j t ) be the node expanded at time t. From the definition of the algorithm, since this node is selected we have that its b-value is larger than the b-value of the cell (h * t , j * t ) containing x * . And since this node is expanded, we have log(n 2 /η) 2T h t ,j t (t) ≤ δ(h t ). Thus,

f (x ht,jt ) ≥ μht,jt (t) -δ(h t ) under ξ ≥ b ht,jt (t) -3δ(h t ) since the node is expanded ≥ b h * t ,j * t (t) -3δ(h t ) since the node is selected ≥ f (x h * t ,j * t ) + δ(h * t ) -3δ(h t ) under ξ ≥ f * -3δ(h t ) from Assumption (2)
which ends the proof.

We now relate the number of nodes in I h to the near-optimality dimension.

Lemma 3.6. Let d be the ν 3 -near-optimality dimension, and C the corresponding constant. Then

|I h | ≤ C[3δ(h)] -d . Proof. From Assumption 4, each cell (h, i) contains a ball of radius νδ(h) centered in x h,i , thus if |I h | = |{x h,i ∈ X 3δ(h) }| exceeded C[3δ(h)] -d ,
this would mean that there exists more than C[3δ(h)] -d disjoint -balls of radius νδ(h) with center in X 3δ(h) , which contradicts the definition of d (by taking = 3δ(h)).

We now provide a loss bound for StoOO.

Theorem 3.7. Let η > 0. Let us define h(n) to be the smallest integer h such that 2CK3 -d h l=0 δ(l) -(d+2) ≥ n log(n 2 /η) .
Then with probability 1η, the loss of StoOO is bounded as

r n ≤ δ(h(n)).
Proof. Let (h max , j max ) be the deepest node that has been expanded by the algorithm up to round n. At round n there are two types of nodes:

the leaves L n (nodes that have not been expanded) and the nodes that have been expanded T n \ L n , which from Lemma 3.5, belong to I in the event ξ. Each leaf j ∈ L n of depth h has been pulled at most log(n 2 /η)

2δ(h)
times (since it has not been expanded) and its parent (denoted by (h -1, j ) below) belongs to I h-1 . Thus the total number of expanded nodes n is such that

n = hmax l=0 K l -1 j=0 T l,j (n)1{(h, j) ∈ I h } + hmax+1 l=1 K l -1 j=0 T l,j (n)1{(h -1, j ) ∈ I h-1 } ≤ hmax l=0 |I l | log(n 2 /η) 2δ(l) + (K -1) hmax+1 l=1 |I l-1 | log(n 2 /η) 2δ(l -1) = K hmax l=0 C[3δ(l)] -d log(n 2 /η) 2δ(l)
where we used Lemma 3.6 to bound the number of nodes in I l . Now from the definition of h(n) we have h max ≥ h(n). And since node (h max , j max ) has been expanded, we have that (h max , j max ) ∈ I in ξ and

f (x(n)) = f (x hmax,jmax ) ≥ f * -3δ(h max ) ≥ f * -3δ(h(n))
happens with probability 1η from Lemma 3.4. Now, in the case of exponential diameters we have the following corollary.

Corollary 3.8. Assume that δ(h) = cγ h for some constants c > 0 and γ < 1. For any η > 0 the loss of StoOO run with parameter η is bounded with probability 1η as Proof. From the definition of h(n) in Theorem 3.7, we have d+2) . Now from Theorem 3.7, r n ≤ δ(h(n)) with probability 1-η from which we deduce the result in high probability. The result in expectation immediately follows from

r n ≤ c 1 log(n 2 /η) n 1 d+2 . with c 1 def = 2CK3 -d 1-γ d+2
n log(n 2 /η) ≤ 2CK3 -d h(n) l=0 [cγ l ] -(d+2) ≤ 2CK3 -d c -(d+2) γ -(h(n)+1)(d+2) -1 γ -(d+2) -1 ≤ c d+2 1 δ(h(n)) -(
Er n ≤ (1 -η)δ(h(n)) + η = O log n n 1 d+2 ,
for the choice η = 1/n as the loss is trivially bounded by 1 (since the rewards are in [0, 1]).

Notice that this algorithm is not an anytime algorithm, in contrary to the DOO algorithm. StoOO is close in spirit to the Zooming algorithm [Kleinberg et al., 2008b], and both algorithm can be made anytime in a somehow artificial way by resorting to the so-called doublingtrick technique, which consists of running the algorithm for a given time horizon n 0 , and once finished (if n > n 0 ), starting it again with a double time horizon n 1 = 2n 0 and repeating this process until the (unknown) horizon n is reached. One can show that the performance of the resulting algorithm is bounded by a quantity similar to the performance of the algorithm that would know n, up to a constant factor. The main difference between StoOO and Zooming algorithm is that StoOO is given a hierarchical partitioning which constrains the computation of the upper-confidence bounds but as a consequence simplifies the complexity of the sampling strategy, whereas Zooming requires a sampling oracle that can identify states that do not belong to the current covering centered at the set of active states.

In the next subsection we present a modification of the StoOO algorithm, called HOO -which is anytime-but which requires a slightly stronger assumption on f , called weak Lipschitz assumption.

Hierarchical Optimistic Optimization (HOO)

We make the following assumption on the function f : Assumption 5 (weak Lipschitz). The function f is such that for all x, y ∈ X ,

f * -f (y) ≤ f * -f (x) + max f * -f (x), (x, y) .
(3.11)

Intuitively, this says that around an optimum x * the values f (y) should be above f * -(x * , y), like the local smoothness property (3.8). But in addition, in the vicinity of other arms x, the constraint is milder as the arm x gets worse: around any -optimal point x the values f (y) should be larger than f * -2 for (x, y) ≤ and larger than f (x)-(x, y) elsewhere. In other words, there is no sudden and large drop in the mean-payoff function around states with values close to the optimum (note that this property can be satisfied even for discontinuous functions).

The HOO algorithm is described in Figure 3.10. The notation C(h, i) refers to the set of children of (h, i).

At each round t, the algorithm assigns b-values to all nodes of the current tree T t , defined as b h,j = +∞ for any leaf (h, j) ∈ L t (from which no sample has been observed yet), and for any node (h, i)

∈ T t \ L t , b h,i (t) def = min μh,i (t)+ 2 log t T h,i (t) +δ(h), max (h+1,j)∈C(h,i) b h+1,j (t) . (3.12)
Their computation can be done by backward induction, starting from the leaves, up to the root node.

The algorithm works as follows: At each round t a leaf (h t , j t ) ∈ L t of the current tree is selected. The way this leaf is chosen is by following an "optimistic path" from the root to a leaf where at each node along this path, the child node is the one with the highest b-value (Figure 3.11 illustrates the leaf selection procedure). Then a point x t is selected arbitrarily in the corresponding domain X ht,jt (for example x ht,jt but it can be any other point, possibly chosen randomly) and the random reward r t = f (x t ) + t is observed. Then the b-values of all nodes are updated and the process repeats.

Initialization: T 1 = {(0, 0)} (root node) for t = 1 to n do
Compute the b-values of all nodes in T t according to (3.12), Select a leaf (h t , j t ) ∈ L t by following an "optimistic path":

Let (h, i) ← (0, 0) (start from the root) While (h, i) ∈ T t \ L t do (h, i) ← arg max (h+1,j)∈C(h,i)
b h+1,j (t) (Ties broken arbitrarily)

The selected leaf is (h t , j t ) = (h, i) Sample a state x t arbitrarily in X ht,jt (for example x t = x ht,jt ) and collect the reward Finally, at round n, the algorithm returns one of the previously sampled states chosen (uniformly) randomly.

r t = f (x t ) + t . Expand node (h t , j t ): T t+1 ← T t ∪ C(h t , j t ) (add the K children of (h t , j t )) end for Return x(n) def = x T , where T ∼ U({1, 2, . . . , n}).
An optimistic sampling strategy: By defining the b min -value of any leaf (h, j) ∈ L t as the minimum of the b-values of all its ancestor nodes, i.e.,

b min h,j (t) def = min (l,i) ancestor of (h,j) μl,i (t) + 2 log t T l,i (t) + δ(l),
we have that b min h,j (t) is a refined high-probability upper-confidence bound on sup x∈X h,j f (x) (since each term of the min is). This is a way to implement the idea of improving the UCB using a hierarchy of domains mentioned in Remark 3.2.

Actually from the definition of the optimistic path chosen by the HOO algorithm, we have the property that the selected leaf (h t , j t ) is a leaf with highest b min value among all leaves in L t : This is exactly the optimistic methodology introduced in Section 3.1.2, especially described in Remark 3.2.

(h t , j t ) ∈ arg max (h,j)∈Lt b min h,j (t).

Analysis of HOO

The bound reported in [Bubeck et al., 2011a] is in terms of the cumulative regret R n def = nf * -n t=1 r t , i.e. the difference between the sum of rewards collected by the algorithm up to time n compared to n times the best possible expected reward f * .

However, from an algorithm achieving a cumulative regret R n one can design an algorithm that achieves a loss r n in expectation of Er n = ER n /n. This loss bound is not optimal for finitely many armed bandits (since there exists strategies that achieve exponential loss bounds as discussed in [START_REF] Bubeck | Pure exploration in multi-armed bandits problems[END_REF][START_REF] Audibert | Best arm identification in multi-armed bandits[END_REF]), but in the case of X -armed bandits (where the set of arms is larger than the number of rounds n), the problem of designing better strategies for the loss is an open problem. The version presented in Figure 3.10 is an adaptation of the HOO algorithm where the state x(n) returned at the end of the algorithm is chosen uniformly randomly among the states {x t } 1≤t≤n sampled by the algorithm up to round n:

x(n) def = x T , where T ∼ U({1, 2, . . . , n}).
(3.13)

Thus we immediately deduce that

E T r n = E T [f * -f (x T )] = 1 n n t=1 [f * -f (x t )] = 1 n R n . (3.14)
Theorem 3.9 (Regret bound for HOO [Bubeck et al., 2011a]). Under Assumption 5 on f . Let d be the ν 3 -near-optimality dimension of f w.r.t. . Then the loss of HOO is upper-bounded as

Er n = O n log n -1 d+2 .
Proof. From [Bubeck et al., 2011a] (proof not reproduced here) we have that the expected cumulative regret of HOO is O log n 1 d+2 n d+1 d+2 . Using (3.14) we deduce the result for the expected loss.

Remark 3.5. Since the state x(n) returned by the algorithm follows (3.13), the loss r n of HOO is directly related to the cumulative regret R n via (3.14). However for the problem of minimizing the loss r n (that we consider in this paper), it may be possible to define other choices for the recommended state x(n) such that the loss r n may not be related to the cumulative regret R n . Such a possible choice would be to return any point in the deepest leaf arg max (h,j)∈Ln h of the final tree T n built from HOO. Actually, numerical experiments indicate that this strategy provides better performance than the one defined by (3.13). However, there is currently no theoretical guarantee for it.

Remark 3.6. HOO requires that f satisfies (3.11) which is slightly stronger than (3.8). The reason is that since HOO expands a leaf at each round, it builds a high-probability UCB on sup x∈X h,i f (x) at a given node (h, i) based on different points in the cell X h,i (in contrary to StoOO that samples several times the same point in order to build an accurate estimate of the value before expanding the node). As a consequence, the rewards collected in sub-optimal cells may significantly impact the cumulative regret. Indeed, consider a sub-optimal cell X h,i (thus

x * / ∈ X h,i ) such that f (x h,i ) ≥ f * -δ(h).
Assuming that f satisfies (3.8) only, then sampling arbitrarily at x ∈ X h,i may cause a large cumulative regret (since the function may be arbitrarily low at points x = x h,i ). In contrast, assuming that f satisfies (3.11), one deduce that any sample x in the cell X h,i contributes to the cumulative regret by

f * -f (x) ≤ f * -f (x h,i ) + max{f * -f (x h,i ), (x h,i , x)} ≤ 2δ(h) only.
The loss bounds of HOO and StoOO are of the same order. The benefit of HOO over StoOO is that it is anytime (i.e. n does not need to be known in advance) and it is usually numerically more efficient since it does not wait until a cell has been sampled enough times to start refining the corresponding node. Thus inside a given cell X h,i the sampling is adaptive even when the number of samples is small, which enables HOO to localize more rapidly the maximum of f within the cell (contrary to StoOO which samples the same state O(log(n)/δ(h) 2 ) times before refining it). Those improvements come at the cost of a slightly more constraining assumption on the function f as explained in the previous remark.

Finally, we provide some numerical experiments on the same onedimensional problem as described in Subsection 3.3.3. The meanreward function is f (x) def = sin(13x) sin(27x)+1 /2 and the reward collected at a state x t follows a Bernoulli distribution with parameter f (x t ) (i.e. r t = 1 with probability f (x t ) and r t = 0 with probability 1-f (x t )). Figure 3.12 shows the trees built by HOO after n = 10 2 , 10 3 , 10 4 , and n = 10 5 calls to the function using the 2 -metric. Here the hierarchical partitioning is formed by dyadic intervals, δ(h) = 2 -h , and the points x t are uniformly randomly chosen in the selected cells X ht,jt .

A first observation is that the tree is more uniformly balanced here than in the deterministic case since the noise in the rewards makes it harder to distinguish between the relative values of the function. This is reflected in the performance bounds since the loss obtained in this stochastic case (both for StoOO and HOO) is of the order n -1 d+2 , where d is the near-optimality dimension, whereas in the deterministic setting, DOO achieves the improved rate n -1/d when d > 0, and even an exponential rate when d = 0 (see Corollary 3.3). A second remark is that, similarly to the deterministic case, the tree is more deeply refined where the mean-payoff function is near-optimal, and the heterogeneous aspect of the tree increases with n: The algorithm starts with a quasi-uniform initial exploration, then rapidly focus on the main peaks, and eventually performs a local search around the global optimum. We can intuitively grasp the advantages of such hierarchical optimistic optimization methods in the fact that they perform an efficient exploration of the search space for any possible numerical budget n (using the knowledge of the smoothness of f ).

Comparison with UCB-AIR algorithm: One can think of applying the UCB-AIR algorithm [START_REF] Wang | Algorithms for infinitely many-armed bandits[END_REF] introduced in Subsection 1.2.1 in this X -armed bandit setting, where new arms would be chosen uniformly at random over the space X .

For illustration, let us compare UCB-AIR with StoOO/HOO on Example 2 described in Section 3.3.2 where X = [0, 1] D and the meanreward function f is locally equivalent toxx * α , for some α > 0, around a global maximum x * .

UCB-AIR would pull randomly a new arm X according to the Lebesgue measure on [0, 1] D . We have

P(μ(X) > μ * -ε) = Θ(P(||X - x * || α < ε)) = Θ(ε D/α ), for ε → 0.
Thus Assumption (1.16) holds with β = D/α, and UCB-AIR provides an expected cumulative regret bounded as (in the case f * < 1) ER n = Õ( √ n) when D < α, and ER n = Õ(n D/(α+D) ) when D ≥ α. Using the recommendation strategy of x(n) defined as in (3.13), the expected loss of UCB-AIR is thus:

Er n = Õ n -1/2 for D < α Õ n -α α+D for D ≥ α
Thus the loss is small when the smoothness order α is large, since there is a reasonable chance to find a near-optimal point among a small number of samples chosen uniformly a random. Notice that in order to apply UCB-AIR, the coefficient α should be known. Now using StoOO or HOO with the semi-metric (x, y) = xy β with β ≤ α implies that the near-optimality dimension is d = D(1/β -1/α) (see Subsection 1.2.1), thus the expected loss of StoOO or HOO is

Er n = Õ n -1/2 for α = β Õ n - 1 D(1/β-1/α)+2 for α > β , (3.15)
So the important measure of the quality of this strategy is the discrepancy between the actual smoothness order α of f and the "believed" smoothness order β which is used in the algorithm. The closer β is from α, the better (since the near-optimality dimension depends on this discrepancy).

Thus if the local smoothness order α is known, then it is always better to apply StoOO or HOO with β = α than UCB-AIR since the loss is then Õ(n -1/2 ). If α is not known, then both UCB-AIR and StoOO/HOO would have to guess (or estimate) the smoothness order, resulting in poorer performance. For StoOO/HOO the guessed value β should be as close to α as possible while satisfying β ≤ α, since otherwise the smoothness property (3.8) or (3.11) would not hold, and the algorithms StoOO and HOO may not converge to the global optimum (i.e. the loss may not converge to 0).

Comparison with UCT:

Actually, one can see the UCT algorithm [START_REF] Kocsis | Bandit based Monte-Carlo planning[END_REF] exposed in Section 2.2 as a version of HOO where δ(h) is set to 0 in the definition of the upper-confidencebounds (3.12) (since when δ(h) = 0 the minimum of the two terms defining the bound is always the first one), which reduces to the UCT bound (2.1). Thus UCT can be seen as a version of HOO where the smoothness of the function is assumed to be infinite (i.e. β is set to ∞), and the local smoothness property (3.8) does not hold for such a metric. Thus in light of the previous comment, this algorithm may be stuck in local optima for a very long period of time (as illustrated in Chapter 2).

Monte-Carlo Tree Search: HOO can be seen as a Monte-Carlo Tree Search (MCTS) algorithm as illustrated in Figure 2.1. If we consider choosing the point x t uniformly at random over the selected cell X ht,jt then this is equivalent to performing an (infinite) rollout where uniformly random moves are chosen from node X ht,jt . Thus the results pre-sented in this chapter can be seen as preliminary foundations for MCTS in the sense that finite-time performance guarantees are obtained for the problem of function optimization in general spaces (i.e. semi-metric) under the assumption that the mean-reward function satisfies a local smoothness property w.r.t. a known semi-metric.

Conclusions

The performance of the algorithms DOO, StoOO, HOO described in this chapter depends on the near-optimality dimension d, which characterizes the quantity of near-optimal states of f measured with the semimetric . Actually d can be seen as a discrepancy between the actual smoothness order of the function around its maximum and the believed smoothness order that is used in the algorithm (through the choice of ), as illustrated in the previous example where

d = D(1/β -1/α).
Thus when the local smoothness of f around x * is known, it can be used for defining such that the near-optimality dimension is d = 0, which leads to a loss bound r n = Õ(n -1/2 ) in the stochastic case. Thus we obtain the nice property that the rate n -1/2 is independent of the space dimension, thus those techniques do not suffer from the "curse of dimensionality". However it is important to notice that the constant factor hidden in the O notation may be exponential in the dimension of the space. This is of course unavoidable when we consider a global optimization problem under such a weak and local assumption on the possible functions. The performance is somehow similar to a Monte-Carlo integration method where in order to estimate X fdμ one may use a Monte-

Carlo estimate 1 n n i=1 X i using n samples X i i.i.d.
∼ μ. The standard deviation of this estimate is σ(f )n -1/2 , where σ(f ) is the standard deviation of f (X) when X ∼ μ. The rate n -1/2 is independent of the space dimension, but the constant factor σ(f ) is usually exponential in the dimension. Thus, in terms of convergence rate, when the local smoothness of the function around its global optima is known, optimizing a function is not more difficult than estimating its integral! Now, when the local smoothness of f is not known, or when there is no semi-metric such that d = 0 then the loss bound deteriorates and the dimension of the space appears in the rate. Thus, like in Chapter 1, we see that the performance of the optimistic strategy depends on the smoothness of f around the global optimum (expressed in terms of a measure of the quantity of nearoptimal states) and on our knowledge about this smoothness.

The next chapter presents adaptive techniques that may apply when the smoothness of the function is unknown.

Optimistic Optimization with unknown smoothness

We now consider the setting where previous Assumptions 1, 2, 3, 4 hold for some semi-metric , but the semi-metric is unknown from the algorithm.

The hierarchical partitioning of the space is still given to the algorithm, but since is unknown, one cannot use the diameter δ(h) of the cells to design upper-bounds, like in DOO, StoOO, or HOO.

Alternatively, we can think of this setting as a lack of knowledge about the local smoothness of f around its maximum. For example, in the Examples 1 and 2 described in Section 3.3.2 the choice of β (defining the semi-metric ) is difficult when the smoothness order α of f is unknown, but this choice is critical since β should always be less than α (in order to guarantee the convergence of the algorithm) while as close to α as possible in order to optimize the performance.

The question we wish to address here is: If is unknown, is it possible to implement an optimistic optimization strategy with performance guarantees?

We provide a positive answer to this question and in addition we show that we can do almost as well as if were known, for the best possible valid (i.e., satisfying Assumptions 1, 2, 3, 4). Section 4.1 considers the deterministic case while Section 4.2 deals with the stochastic case.

Simultaneous Optimistic Optimization

In this section we consider the deterministic setting and use the same notations as in Section 3.3.

The idea introduced in [START_REF] Munos | Optimistic optimization of deterministic functions without the knowledge of its smoothness[END_REF] is to expand at each round simultaneously all the leaves (h, j) of the current tree for which there exists a semi-metric such that the corresponding upper-bound f (x h,j ) + sup x∈X h,j (x h,j , x) of the leaf (h, j) could be the highest. In other words, we select all cells that are potentially optimal for any valid metric. This is implemented by expanding at each round at most a leaf per depth, and a leaf is expanded only if it has the highest value among all leaves of same or lower depths. The Simultaneous Optimistic Optimization (SOO) algorithm is described in Figure 4.1.

The SOO algorithm takes as input parameter a function t → h max (t) which limits the tree to a maximal depth of h max (t) after t node expansions. Again, L t refers to the set of leaves of T t .

Analysis of SOO

All previously defined quantities such as the diameters δ(h) of the cells, the sets I h , and the ν-near-optimality dimension d depend on the (unknown) semi-metric (which is such that Assumptions 1, 2, 3, 4 are satisfied) and are defined as in Section 3.3.

At time t, let us define h * t to be the depth of the deepest expanded node in the branch containing x * (an optimal branch).

The next lemma provides a lower bound on t → h * t as a function of the size of the sets I h . The intuition for this result is that from the time when the optimal node of depth h is expanded, any node of depth h + 1 that is expanded before the optimal node of depth h + 1 is expanded, must be in I h . We deduce that once an optimal node of depth h is expanded, it takes at most |I h+1 | node expansions at depth h + 1 before the optimal node of depth h + 1 is expanded. From this we deduce a lower bound on h * t .

The maximum depth function t → h max (t) is a parameter of the algorithm.

Initialization: T 1 = {(0, 0)} (root node). Set t = 1. while True do Set v max = -∞. for h = 0 to min(depth(T t ), h max (t)) do Among all leaves (h, j) ∈ L t of depth h, select (h, i) ∈ arg max (h,j)∈Lt f (x h,j ) if f (x h,i ) ≥ v max then
Expand this node: add to T t the K children {(h+1, i 1 ), . . . , (h+ 1, i K )} and evaluate the function at the corresponding centers

{x h+1,i1 , . . . , x h+1,iK } Set v max = f (x h,i ), Set t = t + 1 if t = n then Return x(n) def = arg max (h,i)∈Tn f (x h,i )
end if end for end while.

≤ h ≤ h max (t), when- ever t ≥ (|I 0 | + |I 1 | + • • • + |I h |)h max (t), we have h * t ≥ h.
Proof. 1 The algorithm does not expand nodes with a strictly larger depth than h max (t), thus either h * t = h max (t) or h * t < h max (t). If h * t = h max (t) then the statement holds trivially. Now assume that h * t < h max (t). Let τ h denote the time when the optimal node (h, i * h ) (i.e. the one containing x * ) of depth h is expanded. We have the property that any node of depth h+1 ≤ h max (t) which is expanded at a time s ∈ Δ h def = [τ h , τ h+1 -1] belongs to I h+1 . Indeed, for any s ∈ Δ h the optimal node (h + 1, i * h+1 ) of depth h + 1 is a leaf of the current tree T s and has not been expanded yet. Thus, if SOO expands a node (h + 1, i) of depth h + 1 during Δ h this means that its value f (x h+1,i ) is at least as good as the value f (x h+1,i * h+1 ) of the optimal node of depth h + 1 (by definition of the algorithm), which is δ(h + 1)-optimal (from Assumption 2). Now it could be that during a crossing of the tree, no node of depth h + 1 is expanded because the currently best node of depth h + 1 is dominated by another node (l, i) of lower depth l ≤ h. In that case we have (l, i)

∈ I l since f (x l,i ) ≥ f (x h+1,i * h+1 ) ≥ f * -δ(h + 1) ≥ f * -δ(l).
Since each crossing of the tree may result in at most h max (t) node expansions, we deduce that for any 0 ≤ h < h max (t),

τ h+1 -τ h ≤ (h+1,i)∈I h+1 1{(h + 1, i) is expanded during Δ h } + h l=1 (l,i)∈I l 1{(l, i) is expanded during Δ h } h max (t) = h+1 l=1 (l,i)∈I l 1{(l, i) is expanded during Δ h } h max (t). Now since h * t < h max (t) we have h * t h=0 τ h+1 -τ h ≤ h * t h=0 h+1 l=1 (l,i)∈I l 1{(l, i) is expanded during Δ h }h max (t) = h * t +1 l=1 h * t h=l-1 (l,i)∈I l 1{(l, i) is expanded during Δ h }h max (t) ≤ h * t +1 l=1 (l,i)∈I l 1{(l, i) is expanded at any time}h max (t) ≤ h * t +1 l=1 |I l |h max (t).
By definition, τ h * t +1 > t and τ 0 = 1. We deduce that

t < 1 + h * t +1 l=1 |I l |h max (t) ≤ h * t +1 l=0 |I l |h max (t).

Thus for any

h ≤ h max (t) such that t ≥ (|I 0 |+|I 1 |+• • •+|I h |)h max (t), we have h ≤ h * t .
We deduce the following bound on the loss of SOO.

Theorem 4.2. Let be a semi-metric such that Assumptions 1, 2, 3, 4 are satisfied. Let us write h(n) the smallest integer h such that

Ch max (n) h l=0 δ(l) -d ≥ n, ( 4.1)
(where we remind that δ(l) and d depend on ), then the loss of SOO is bounded as

r n ≤ δ min(h(n) -1, h max (n)) . (4.2)
Proof. From Lemma 3.1 and the definition of h(n) we have

h max (n) h(n)-1 l=0 |I l | ≤ Ch max (n) h(n)-1 l=0 δ(l) -d < n, thus from Lemma 4.1, when h(n) -1 ≤ h max (n) we have h * n ≥ h(n) -1. Now in the case h(n) -1 > h max (n), since the SOO algorithm does not expand nodes beyond depth h max (n), we have h * n = h max (n). Thus in any case, h * n ≥ min(h(n) -1, h max (n)). Define (h *
n , i * ) to be the deepest expanded node containing x * . Using the local smoothness assumption (3.8), we deduce that:

f (x(n)) ≥ f (x h * n ,i * ) ≥ f * -δ(h * n ) ≥ f * -δ(min(h(n) -1, h max (n))).
This result may seem surprising: although the semi-metric is not known, the performance is almost as good as for DOO (see Theorem 3.2) which uses the knowledge of . The main difference is that the maximal depth h max (n) appears both as a multiplicative factor in the definition of h(n) in (4.1) and as a threshold in the loss bound (4.2). Those two appearances of h max (n) define a trade-off between deep (large h max ) versus broad (small h max ) types of exploration. We now illustrate the case of exponentially decreasing diameters.

Corollary 4.3. Let be a semi-metric such that Assumptions 1, 2, 3, 4 are satisfied. Assume that δ(h) = cγ h for some c > 0 and γ < 1.

• If the near-optimality d > 0, the loss of SOO is bounded as

r n ≤ max C 1 -γ d 1/d γ -1 n h max (n) -1/d , cγ hmax(n) .
Thus, for a choice of the depth-function h max (n) = Θ((log n) a ), for some a > 1, the regret is r n = Õ(n -1/d ).

• If the near-optimality d = 0, the loss of SOO run with the depth function h max (t) = √ t, is bounded for all n, as

r n ≤ cγ √ n min(1/C,1)-2 .
(where we remind that d, C, c, γ depend on ).

Proof. Using the notations of Theorem 4.2, when d > 0 we have

n ≤ Ch max (n) h(n) l=0 δ(l) -d = Cc -d h max (n) γ -d(h(n)+1) -1 γ -d -1 . Thus (cγ h(n) ) -d ≥ n h max (n) 1 -γ d C .
We deduce from Theorem 4.2 that

r n ≤ δ min(h(n) -1, h max (n)) = max cγ h(n)-1 , cγ hmax(n) ≤ max C 1 -γ d 1/d γ -1 n h max (n) -1/d , cγ hmax(n) .
Now, for h max (n) = Θ((log n) a ), for large enough n, the second element in the previous max is dominated by the first one, which is of the order Õ(n -1/d ).

Now, if d = 0 then n ≤ Ch max (n) h(n) l=0 δ(l) -d = Ch max (n)(h(n) + 1), thus for the choice h max (n) =
√ n we deduce that the loss decreases as:

r n ≤ δ min(h(n) -1, h max (n)) ≤ cγ √ n min(1/C,1)-2 .
Since our algorithm does not depend on , the analysis is actually true for any semi-metric that satisfies Assumptions 1, 2, 3, 4 thus Theorem 4.2 and Corollary 4.3 hold for the best possible choice of such a (which may depend on f itself!). In particular, we can think of problems for which there exists a semi-metric such that the corresponding near-optimality dimension d is 0. Actually, we will see in Section 4.2.2, as well as in the examples described in the next subsection, that the case d = 0 is already very general and covers a large class of functions.

Remark 4.1. The maximal depth function h max (t) is still a parameter of the algorithm, which somehow influences the behavior of the algorithm (deep versus broad exploration of the tree). However, for the case d = 0 that we illustrate next, one may choose a generic h max (t) = √ t for which a stretch exponential bound on the loss is guaranteed. In addition, even when d > 0, we see that the choice h max (t) = (log t) a , for a > 1, provides an asymptotic loss of the order n -1/d (up to a poly-logarithmic factor).

Examples

Example 1: Consider Example 1 described in Section 3.3.2 where X = [-1, 1] D and f (x) = 1x α ∞ , where α ≥ 1 is unknown. We have seen that DOO using the metric (x,

y) = x -y β ∞ provides a polynomial loss r n = O n -1 D αβ α-β
whenever β < α, and an exponential loss r n ≤ 2 1-n when β = α.

Consider the case when the smoothness order α is unknown and apply SOO with the maximum depth function h max (t) = √ t. As mentioned before, SOO does not require the knowledge of , thus we can apply the analysis for any that satisfies Assumptions 1, 2, 3, 4. So let us consider (x, y) = xy α ∞ . Then δ(h) = 2 -hα , ν = 1, and the near-optimality dimension of f under is d = 0 (and C = 1). We deduce that the loss of SOO is

r n ≤ 2 (2- √ n)α .
Thus SOO provides a stretched-exponential loss without requiring the knowledge of α.

Note that a uniform grid provides the loss n -α/D , which is polynomially decreasing only (and subject to the curse of dimensionality since the exponent of the rate depends on D). Thus, in this example SOO is always better than both Uniform and DOO, except if one knows perfectly α and applies DOO with β = α (in which case we obtain an exponential loss). The fact that SOO is not as good as DOO optimally fitted comes from the truncation of SOO at a maximal depth h max (n) = √ n (whereas DOO optimally fitted would explore the tree up to a depth linear in n).

Example 2: The same conclusion holds for Example 2, where we considered a function f defined on [0, 1] D that is locally equivalent to xx * α , for some unknown α > 0 (see the precise assumptions in Section 3.3.2). We have seen that DOO using (x, y) = c xy β with β < α has a loss r n = O n -1 D αβ α-β , and when α = β, then d = 0 and the loss is r n = O(2 -α(n/C-1) ). Now by using SOO (which does not require the knowledge of α) with h max (t) = √ t we deduce the stretched-exponential loss r n = O(2 - √ nα/C ) (by using (x, y) = xy α in the analysis, which gives δ(h) = 2 -hα and d = 0). Remark 4.2. All functions considered in the two previous examples are such that there exists a semi-metric such that the near-optimality of f w.r.t. is d = 0. Table 4.2 reports the loss of SOO for different numerical budgets. In comparison to Table 3.8 the loss of SOO is better than DOO using the sub-optimal semi-metric 1 and is almost as good as DOO with the optimal semi-metric 2 . This corroborates the theoretical guarantees stated in Subsection 4.1.1. Indeed, in this example the near-optimality dimension of f w.r.t. the semi-metric 2 is d = 0, as illustrated in Example 2 in Subsection 4.1.2, thus the loss of SOO is a stretchedexponential.

Illustrations

Figure 4.4 also shows the first iterations of the SOO algorithm for the (garland) function f (x) = x(1x) 4 -| sin(60x)| . We also used K = 3 and h max (t) = √ t. This function f has a local behavior (around its maximum) f (x) ≈ f (x * ) -c|xx * | α , for some constant c > 0 and α = 1/2. One can easily check that the near-optimality dimension of f w.r.t. the metric (x, y) def = c|x -y| 1/2 is d = 0, thus the loss of SOO is also stretched-exponentially decreasing to 0. Notice that SOO neither requires the knowledge of c nor α (in contrast to DOO).

Figure 4.5 illustrates the SOO algorithm for the optimization of a Brownian motion (i.e. f is a function sample of a Gaussian process). We can prove that with high-probability (w.r.t. the random choice of f ), f is lower-bounded as f (x) ≥ f (x * ) -c|xx * | α , for some constant c > 0 (which depends on the failure probability) and α = 1/2. An open question is whether the near-optimality dimension of f w.r.t. the metric (x, y) def = c|x -y| 1/2 is (in high probability) d = 0, in which case SOO would have a stretched-exponential loss, or d > 0 for which SOO would have a polynomial loss.

Finally, Figure 4.6 shows a 2-dimensional problem with the function f (x 1 , x 2 ) = f (x 1 )f (x 2 ) where f (x) = sin(13x) sin(27x) + 1 /2. Again we used h max (t) = √ t and K = 3 (where a cell is spit in 3 along the longest direction). In this situation again, the near-optimality dimension of f w.r.t. the semi-metric l(x, y)

= c|x 1 -y 1 | 2 |x 2 -y 2 | 2 (for some constant c > 0) is d = 0.

Discussions

Comparison with the DIRECT algorithm: The DIRECT (DIviding RECTangles) algorithm [START_REF] Jones | Lipschitzian optimization without the lipschitz constant[END_REF][START_REF] Finkel | Convergence analysis of the direct algorithm[END_REF][START_REF] Gablonsky | Modifications of the Direct algorithm[END_REF]] is a Lipschitz optimization algorithm that applies when the Lipschitz constant L of f is unknown. It uses an optimistic splitting technique similar to ours where at each round, it expands the set of nodes that have the highest upper-bound (such as defined in DOO) for at least some value of L.

Our approach may be considered as a generalization of DIRECT in the facts that (1) it simultaneously expands all the most promising nodes under any possible semi-metric (whereas DIRECT considers any possible Lipschitz constant for a fixed metric only), and (2) we only require the local smoothness assumption on the function (3.8), whereas DIRECT requires f to be (globally) Lipschitz.

Thus we are able to derive finite-time loss bounds in a much broader setting than the setting of DIRECT, for which, and to the best of our knowledge, there is no finite-time analysis (only the consistency property lim n→∞ r n = 0 is proven in [START_REF] Finkel | Convergence analysis of the direct algorithm[END_REF]).

We are not aware of other finite-time analyses of similar global optimization algorithms that do not require the knowledge of the smoothness of the function.

SOO is a rank-based algorithm:

The algorithm only requires the knowledge of the rank of the function evaluations and not their specific values. Indeed the decision to expand a node only depends on whether the value at this node is larger than the values of other nodes of the same or lower depth. The specific values are not important as long as their pairwise comparison is possible. This is also a property shared by the CMA-ES optimization algorithm (see e.g. Figure 10.4 in [START_REF] Auger | Theory of Randomized Search Heuristics: Foundations and Recent Developments, chapter Theory of Evolution Strategies: A New Perspective[END_REF]). Thus if g : R → R is strictly increasing, SOO will perform identically on f and g • f . For example SOO will perform identically on x → xx * and x → g( xx * ). And our analysis of the loss of SOO actually reflect this property since we can choose to define the semi-metric as (x, y) = g( xy ), as illustrated in subsection 4.1.2 for the case g(z) = z α . SOO for the hard function illustrated in Figure 2.2: Finally we report in Figure 4.7 the result of SOO applied to the function built from the example illustrated in Figure 2.2 (where we used D = 6). This function served as an illustration of the particularly bad behavior of UCT. If one looks at this function at a high level scale, this function does not possess any smoothness around its maximum. Actually, for this type of functions (say all functions equivalent to this one up to a permutation of the values at the leaves), the best algorithm would be a uniform search, since no information from higher levels can be used to guide the search.

In addition, any optimistic algorithm will be fooled here since, in any cell (not containing the optimum), the function has higher values on the left than on the right. Thus, as long as the optimum is not reached, the search will be focusing more on left branches than on right ones, at all levels, leading to a particularly misleading behavior. This is all the more true for UCT since the B-values computed by UCT are not true high probability upper-confidence-bounds, and we saw that the number of samples required by UCT to find the optimum can be as bad as Ω(exp(exp(. . . exp(1) . . . ))), where the number of entangled exponentials is D.

In contrast, SOO (fitted with h max (t) = √ t) requires "only" Ω(K 2D ) samples to find the optimum. This is because at each crossing of the tree, SOO expands a node with lowest depth. Thus after n node expansions, the n/h max (n) = √ n nodes of lowest depth have all been expanded. Now if the actual "smoothness" of the function were known (we can show that here d = 0 and C = 2 D ) one could use it to define true upper-confidence-bounds and use it in the DOO algorithm. Such a DOO optimally fitted would expand first the nodes with lowest depth (since the diameter term δ(h) would dominate the evaluations f (x h,j ) in the computation of the b-value b h,j , see Algorithm 3.6), thus reducing to a uniform search, which is the best thing to do here. The resulting number of samples required to find the optimum would be K D (only).

Thus in this hard instance of function optimization, the best possible search is the uniform search (achieved by DOO optimally fitted) and the cost is exponential in D. Now SOO is exponential in 2D which is much better than UCT which is "D-uply" exponential. This example illustrates the fact that any optimistic algorithm that does not know the smoothness of the function may be poorer than a uniform search on particularly unsmooth functions. But this is the price to pay in order to be able to do much better than uniform as soon as the function possesses some smoothness (even if it is unknown).

Extensions to the stochastic case

We now consider the case when an evaluation of f at a point x t ∈ X returns a noisy estimate r t of f (x t ) such that E[r t |x t ] = f (x t ).

In this X -armed bandit setting, several results have already been obtained for the cumulative regret. Bubeck et al. [2011b] derived minimax regret bounds when the mean-reward function f is assumed to be Lipschitz continuous with an unknown Lipschitz constant. However, f is assumed to be twice differentiable with a known bound on the second order derivative. Then [START_REF] Slivkins | Contextual bandits with similarity information[END_REF] considers a Lipschitz assumption on f in an "implicit metric space" (i.e. the metric is unknown) and derives a regret bound similar to that of the zooming algorithm (as well as HOO or StoOO seen in previous sections) run with the correct metric, under an assumption that some "quality" of the taxonomy is lower-bounded. Finally, [START_REF] Bull | Adaptive-treed bandits[END_REF] extends the previous work, and derive a Õ( √ n) bound on the cumulative regret R n for a large class of functions, called zooming continuous functions. Their result on the cumulative regret is stronger than our bound on the loss (or simple regret) since a bound on the cumulative regret R n implies a bound on the expected loss Er n , as already mentioned in Section 3.4.2. However the class of zooming continuous functions is not at general as the set of functions f that we study in sub-section 4.2.2 (i.e. for which there exists a semi-metric such that the near-optimality dimension of f w.r.t. is d = 0) for which we obtain a Õ(n -1/2 ) loss bound. Thus their results are complementary to ours.

Parameters: η > 0, the max number of samples per node k > 0, and the maximum depth function t → h max (t). x(n) = arg max

Initialization: T 1 = {(0, 0)} (root node). Set t = 1 (round number) while t ≤ n do Set v max = 0. For each leaf (h, j) ∈ L t , compute the b-values b h,j (t) according to (4.3). for h = 0 to min(depth(T t ), h max (t)) do if t ≤ n then Among all leaves of depth h, select (h, i) ∈ arg max (h,j)∈Lt b h,j (t) if b h,i (t) ≥ v max then Set v max = b h,i (t
x h,j ∈Tn\Ln μh,j (n). The direction followed here consists of extending SOO to the stochastic case in a similar way DOO has been extended to StoOO (see Section 3.4.1). The idea is to sample each state x h,j several times in order to build an accurate estimate of f (x h,j ) before expanding the corresponding node (h, j).

The corresponding algorithm, called StoSOO (for Stochastic and Simultaneous Optimistic Optimization), has been introduced in [START_REF] Valko | Stochastic simultaneous optimistic optimization[END_REF] where T h,j (t) def = t s=1 1{x s = x h,j } is the number of times the state x h,j has been selected up to time t, and μh,j (t)

def = 1 T h,j (t) t s=1 r s 1{x s = x h,j } is the empirical average of the rewards received in x h,j . In the case T h,j (t) = 0 we set b h,j (t) = ∞.
Now, like for StoOO, instead of selecting the most promising nodes according of their value f (x h,j ) we select them according to their b-value b h,j . The parameter k used in the algorithm is the number of samples that need to be collected from a state before the corresponding node is expanded. Finally, StoSOO returns the state x(n) with highest empirical value among the set of nodes that have been expanded (thus which have been sampled k times).

Analysis of StoSOO

We have the property that for any η > 0, defining the event ξ as in (3.10), Lemma 3.4 implies that P(ξ) ≥ 1η. Notice that the b-values b h,j (t) define high-probability upper-confidence-bounds on the values f (x h,j ) (and not on sup x∈X h,j f (x) as it was the case for the b-values defined by StoOO in (3.9)).

Thus the intuition of the algorithm is that in the event ξ, the bvalue b h,j (t) of a node X h,j that has been expanded (thus sampled k times) is an -upper-bound on the true value f (x h,j ), i.e. b h,j (t) -≤ f (x h,j ) ≤ b h,j (t), where = 2 log(n 2 /η) 2k . Thus, in the event ξ, StoSOO works in a very similar way as algorithm SOO does, except that:

• The sampling budget (the number of nodes that are expanded) is now at least m = n/k (instead of n for SOO), since each node may be sampled up to k times,

• We rely on -upper bounds b h,j of the nodes, instead of the exact values f (x h,j ), to decide which nodes to expand.

Thus the analysis of StoSOO (in the event ξ) reduces to the analysis of the so-called " -optimistic" SOO algorithm, which is defined exactly as the SOO algorithm except that each evaluation to the function is perturbed positively by at most (i.e., when sampling a state x h,j one observes b h,j , which is such that f

(x h,j ) ∈ [b h,j -, b h,j ]).
Let us now analyze this -optimistic SOO using a similar proof to that of SOO. Define the sets

I h def = {nodes (h, i) such that f (x h,i ) + δ(h) + ≥ f * }.
After t (perturbed) function evaluations, let us write h * t the depth of the deepest expanded node containing x * . Let (h * t + 1, i * ) be the optimal node of depth h * t + 1 (i.e., such that x * ∈ X h * t +1,i * ). As long as this node has not been expanded, any expanded node (h

* t + 1, i) of depth h * t + 1 is [δ(h * t + 1) + ]-optimal. Indeed, f (x h * t +1,i ) ≥ b h * t +1,i -≥ b h * t +1,i * - ≥ f (x h * t +1,i * ) -≥ f * -δ(h * t + 1) + .
We deduce a lower bound on the depth h * t as a function of the size of the sets |I h | in a same way as in Lemma 4.1 (proof not reproduced).

Lemma 4.4. For any depth 0 ≤

h ≤ h max (t), whenever t ≥ h max (t)(|I 0 | + |I 1 | + • • • + |I h |), we have h * t ≥ h.
Then the next results bounds the number of nodes in the sets

|I h | for any depth h ≤ h def = min{h ≥ 0, s.t. δ(h + 1) < }:
Lemma 4.5. Let d be the ν/2-near-optimality dimension (where ν is defined in Assumption 4), and C be the corresponding constant. Then for any h ≤ h , we have

|I h | ≤ C δ(h) + -d .
Proof. The proof is similar to that of Lemma 3.1. By contradiction: for

h ≤ h , if |I h | > C[δ(h) + ] -d we would have |I h | > C[2δ(h)] -d
, which would mean that there exists more than C[2δ(h)] -d disjoint -balls of radius νδ(h) with center in X δ(h) . This contradicts the fact that d is the ν/2-near-optimality dimension.

Now we can state our main result for -optimistic SOO using a budget of m -positively perturbed evaluations of f . Theorem 4.6. Let d be the ν/2-near-optimality dimension and h(m) be the smallest integer h such that

Ch max (m) h l=0 δ(l) + -d ≥ m. (4.4)
Then the loss of -optimistic SOO is bounded as

r m ≤ + δ min(h(m) -1, h max (m), h ) . (4.5)
Proof. Consider first the case when h(m)-1 ≤ h . Then using a similar argument as in the proof of Theorem 4.2 we deduce that after m node expansions, the depth h * m of the deepest expanded node in the branch containing x * satisfies h * m ≥ min(h(m)-1, h max (m)). Now if h(m)-1 > h , we can use Lemma 4.5 up to depth h to deduce similarly that h * m ≥ min(h , h max (m)). Thus altogether h * m ≥ min(h(m) -1, h , h max (m)). Now define (h * m , i * ) as the optimal node of depth h * m (i.e., containing x * ). Let x h,j be the state returned by the algorithm. Thus b h,j ≥ b h * m ,i * and we deduce that

f (x h,j ) ≥ b h,j -≥ b h * n ,i * - ≥ f (x h * n ,i * ) -≥ f * -δ(h * m ) - ≥ f * -δ(min(h(m) -1, h max (m), h )) -.
We now state our main result for StoSOO in the case where the near-optimality dimension for the best valid semi-metric is d = 0. Theorem 4.7. Assume there exists a semi-metric such that Assumptions 1, 2, 3, 4 hold. Assume that the diameter (measured with ) of the cells decrease exponentially fast, i.e. δ(h) = cγ h for some c > 0 and γ < 1. Assume that the ν/2-near-optimality dimension is d = 0 (and write C the corresponding constant). Then the expected loss of StoSOO run with parameters k, h max (t) = t/k, and η > 0, is bounded as:

E[r n ] ≤ (2 + 1/γ) log(n 2 /η) 2k + cγ √ n/k min(1/C,1)-1 + η. (4.6)
In particular, for the choice k = n (log n) 3 and η = 1/

√ n, we have

E[r n ] = O (log n) 2 √ n .
Proof. We have seen that in the event ξ, the StoSOO algorithm behaves like the -optimistic SOO with = 2 log(n 2 /η) k run for at least m = n/k rounds (node expansions).

When d = 0, from Theorem 4.6, we have that m ≤ Ch max (m) h(m) l=0 δ(l) + -d = Ch max (m)(h(m) + 1), thus for h max (m) = √ m we deduce that the loss of -optimistic SOO (thus the loss of StoSOO in the event ξ) is at most:

r n ≤ + δ min(h(m) -1, h max (m), h ) ≤ + δ(h ) + δ min(h(m) -1, h max (m)) ≤ (1 + 1/γ) + cγ √ m min(1/C,1)-2 .
The bound on the expected loss of StoSOO follows from the fact that ξ holds with probability 1η.

Finally, for the specific choice k = n (log n) 3 we notice that the second term in the bound ( 4

.6) is a o(1/ √ n).
Thus in the case the near-optimality dimension for the best valid semi-metric is d = 0 and the diameters are exponentially decreasing, StoSOO achieves the same rate Õ(n -1/2 ) as StoOO and HOO (which required the knowledge of the semi-metric ). In the next subsection we discuss this important case d = 0.

The important case d = 0

Notice that SOO and StoSOO algorithms do not require the knowledge of the semi-metric ; the semi-metric is only used in the analysis of the algorithm. Thus one can choose the best possible semi-metric , possibly according to the function f itself, as long as it satisfies the following properties:

• f is locally smooth w.r.t. around a global optimum x * (i.e. such that (3.8) holds)

• The cells are well-shaped (Assumption 4) and their diameter (measured with ) decreases exponentially fast

• There exists C > 0 such that for any > 0, the maximal number of disjoint -balls of radius ν centered in X is less than C (i.e. the near-optimality dimension d is 0).

In Examples 1 and 2 we illustrated the case of functions f defined on [-1, 1] D that are locally equivalent to a polynomial of degree α around their maximum, i.e., f (x * )f (x) = Θ( xx * α ) for some α > 0, where • is any norm. The precise definition is given in Example 2 of Subsection 3.3.2. In light of the discussion in Subsection 4.1.2, the choice of semi-metric (x, y) def = xy α implies that the previous properties are satisfied and the near-optimality dimension d = 0. This extends to the case when the function has different smoothness orders in different directions, even when those directions are not aligned with the axes of the hierarchical partitioning.

More generally, this result extends to any function whose upperand lower envelopes around x * are of the same order, as expressed in the next lemma.

Lemma 4.8. Consider a finite dimensional and bounded space, i.e., such that X can be packed by C -D -balls with radius , for any > 0, and such that X has a finite doubling constant (defined as the minimum value q such that every ball in X can be packed by at most q balls of half the radius). If there exists constants c > 0 and η > 0 such that min(η, c (x, x * )) ≤ f (x * )f (x) ≤ (x, x * ), for all x ∈ X , (4.7) then the near-optimality of f w.r.t. is d = 0.

Proof. For < η the left inequality in (4.7) implies that the set ofoptimal states X is included in a -ball of radius /c centered in x * . Since X has a finite doubling constant, this ball can be packed by no more than a constant number of -balls of radius . This proves that the local near-optimality of f w.r.t. is d = 0, and in light of Remark 3.3 we also deduce that the near-optimality dimension is d = 0 (since X is a finite dimensional and bounded space). Figure 4.9 provides an illustration of this condition when the envelope has a quadratic shape. The functions considered in Figures 4.3 and 4.4 also satisfy this property. Now, one can define a tight semi-metric according to the local behavior of f around x * in order that (3.8) holds (thus the right inequality in (4.7)). For example if the space X is a normed space (with norm • ), one can define (x, y)

x * f (x * ) f (x * ) -c (x, x * ) f (x * ) -(x, x * ) f (x * ) -η
def = ˜ ( x -y ) with ˜ (r) def = sup x: x * -x ≤r f (x * ) -f (x) . (4.8) Thus f (x * ) -(x, x *
) naturally forms a lower-envelope of f . Thus assuming that the left inequality of (4.7) (upper-envelope) holds, then the near-optimality dimension is d = 0 again.

However, although the case d = 0 is quite general, it does not hold in situations where there is a discrepancy between the upper-and lower-envelopes of f around x * , as illustrated in Figure 4.10.

(x) = 1 - √ x + (-x 2 + √ x) • (sin(1/x 2 ) + 1)/2
. The best possible semi-metric of the form (x, y) = c|x -y| α is such that α ≤ 1/2 in order to satisfy (3.8). However, since the upper-envelope of f is quadratic, the maximum number of -balls with radius that can pack X (i.e., Euclidean balls with radius 1/α ) is at most of order 1/2 / 1/α ≤ -3/2 since α ≤ 1/2. Thus there is no metric of the form (x, y) = c|x -y| α for which d < 3/2.

Finally, as discussed in Remark 3.3, the near-optimality dimension d is a local property of f near x * since it coincides with the local near-optimality dimension. However the corresponding constant C in Definition 3.1 depends on the global shape of f . For instance, let f be a function with near-optimality dimension d around x * with a corresponding constant C. Now consider the function f defined as f (x) def = max 1≤i≤k f (x *x + x i ), where {x 1 , . . . , x k } are k points in X (i.e. f is the maximum of k translated copies of f ). Thus f possesses k global optima {x 1 , . . . , x k } and the near-optimality dimension of f is still d but the corresponding constant can be as large as kC (this is simply because one may pack k times more balls in the set of -optimal states of f , than in the set of -optimal states of f ). Thus for a same bound on the loss, optimizing f will require k times more samples than for optimizing f .

About lower-bounds

The results stated in this chapter and in the previous one provide upper-bounds on the loss of optimistic algorithms applied to classes of functions defined by their behavior around their global optimum.

In order to evaluate the relevance of those results one would like to compare them to lower-bounds for the same classes of functions. Unfortunately little is known about lower-bounds for classes of functions defined by such a local smoothness property. Instead, the main classes of functions considered for lower-bounds are convex (or concave for the problem of maximization considered here) and Lipschitz. For example [START_REF] Nemirovsky | Problem Complexity and Method Efficiency in Optimization[END_REF][START_REF] Traub | Information-based Complexity[END_REF][START_REF] Nesterov | Introductory Lectures on Convex Optimization: A Basic Course[END_REF] used information-theoretic considerations to derive lower-bounds for several classes of concave and Lipschitz functions, under the assumption that one has access to an "oracle", which is a black box returning local information (such as the value and the derivative) of the function at any query state. We report lower-bounds for two types of oracle: the "zero-order" oracle (which is the same as what is considered in this paper, i.e. which returns the value of the function f (x t ), possibly perturbed by noise, at any query point x t ) and the "first-order" oracle (which returns both the value and a sub-gradient of the function). The following lower-bounds are of a worse-case type: they provide a lower-bound on the loss that any algorithm may suffer on at least one function in a given class.

In the case of deterministic evaluations, we have the following results (we do not mention the details of the results, such as the dependence on the size of the space X or other important constants and refer the interested reader to the previous references).

• For Lipschitz functions, using a zero-order oracle the lower-bound on the loss is Ω(n -1/D ), where D is the ambient dimension.

• For the class of r-times continuously differentiable functions, using a zero-order oracle we have a loss Ω(n -r/D ).

• For concave functions, using a first-order oracle, the loss is lowerbounded by an exponentially decreasing function Ω(e -n/D ).

• For strongly concave and Lipschitz functions, using a first-order oracle, the loss is Ω

√ q-1 √ q+1
2n with q = L/μ where L is the Lipschitz constant and μ the strong concavity constant. The bound does not explicitly mention the ambient dimension D but it is indirectly contained in μ.

Now for the stochastic setting, using a first-order oracle, for concave, Lipschitz functions, the loss is Ω( D/n) and for strongly concave functions, it is Ω(q 2 /n) (see also [START_REF] Agarwal | Information-theoretic lower bounds on the oracle complexity of stochastic convex optimization[END_REF] for other settings such as when the solution is sparse).

In light of those lower-bounds we can deduce the following properties of the optimistic algorithms discussed in this paper:

• In the deterministic case, DOO achieves a loss O(n -1/d ) which is better than the lower-bound Ω(n -1/D ) for Lipschitz functions as soon as the near-optimality dimension d is smaller than the ambient dimension D. Note that we always have d ≤ D for Lipschitz functions. We thus see that DOO benefits from the local property of the function near its maximum as captured by the locally smooth assumption. This also says that the lower bounds (which are defined in a worst-case sense) are achieved by functions that do not possess any local smoothness property (basically the set of near-optimal states X covers a positive proportion of the whole space).

• Now, in the case one knows the local smoothness of the function and uses a semi-metric such that d = 0, then DOO achieves an exponential loss O(γ -n/C ) which is even comparable to the lowerbounds for concave functions. This is remarkable given that the assumption required for DOO is only local, whereas concavity is a globally constraining property. However notice that the constant C (corresponding to the near-optimality definition) as well as γ depend on the ambient dimension D as well.

• When the local smoothness of the function is unknown, SOO achieves almost the same performance loss as DOO fitted with the best choice of semi-metric , which is better than the lowerbounds for Lipschitz functions, and almost as well as the exponential rate for concave functions.

• In the stochastic case, similar conclusions are drawn. StoOO and HOO fitted with the best semi-metric (as well as StoSOO without the knowledge of this metric) achieve a loss Õ(n -1/2 ) which is as good (up to a logarithmic factor) as the lower-bound for concave and Lipschitz functions (but not as good as that for the strongly concave case), although they only require a much weaker locally smooth property. However it is important to notice that the constant hidden behind the Õ notation may be exponential in D (as already mentioned in the conclusion of Chapter 3), in contrast to the lower-bound for concave functions. The reason is that the constant factor represents the cost of the initial exploration of the space, which needs to be exponential in D in general for functions having a locally smoothness property only, whereas it is not the case for globally concave functions. But the rate n -1/2 represents the asymptotic behavior of the algorithm. So we see that the optimistic algorithms discussed in this paper achieve the best possible rate indicated by the lower-bounds for general concave functions. This illustrates that those methods performs an natural (and efficient) transition from global to local search. An open question is whether one can achieve the same rate n -1 as the lower-bound for strongly concave functions under our locally smooth assumption only.

Finally, let us say that in general those lower-bounds do not tell us much about the optimality of the algorithms described in this paper since they consider general classes of functions (such as Lipschitz or concave) and not classes of function that are defined in terms of their local behavior around their maximum. For example, the class of functions that we considered in our examples where f (x * )-f (x * ) = Θ( x-x * α ) for 0 < α < 1 (illustrated in Figure 4.4) are not even locally concave, but still are as easy to optimize (using SOO) as any other locally concave function (e.g. by choosing α ≥ 1) (since SOO is a ranked-based algorithm). Thus we believe that the property of concavity or even Lipschitzness does not entirely capture the right notion of complexity for the problem of function optimization. The general problem of deriving lower-bounds for the class of functions described in this paper appears to be an important open question.

Conclusions

Assuming that the function f is locally smooth w.r.t. some semi-metric enables the design of optimistic exploration strategies, even when is unknown. Since the algorithm does not depend on , the loss analysis can be undertaken using the best possible valid (i.e. such that Assumptions 1, 2, 3, 4 hold) semi-metric.

In the deterministic case, the SOO algorithm performs almost as well as DOO optimally-fitted, and achieves an stretch exponential loss in the case where the near-optimality dimension d = 0 for any valid semi-metric. For the stochastic case, and under the same condition, the StoSOO algorithm performs almost as well as StoOO or HOO fitted with the best choice of semi-metric.

We showed that the case d = 0 covers already a large class of functions. Now, when there is no valid semi-metric such that d = 0 (as illustrated in Figure 4.10) the problem of designing an algorithm that would do almost as well as StoOO or HOO for a valid semi-metric with the lowest d > 0, is open.

Notice that StoSOO can be seen as a Monte Carlo Tree Search algorithm that strongly resembles the UCT algorithm. Indeed the nodes selected for sampling are based on a similar upper-confidence-bound (4.3) which does not contain the diameter of the cells, in contrary to the StoOO or HOO algorithms. The main differences with UCT are that (1) StoSOO selects several nodes simultaneously at different depths of the tree, and (2) samples the same state several times before deciding to expand the corresponding node. We believe that (1) is essential in that it implements the optimism in the face of uncertainty at different levels of the function representation, whereas (2) may be relaxed in a similar way as in HOO by allowing to expand a leaf at each sample (at the cost of the additional assumption that f satisfy the weak-Lipschitz property (3.11), as discussed in Remark 3.6). However StoSOO is not anytime in the sense that it requires the knowledge of the time horizon n in order to set the value of k (maximum number of samples per state). Designing an anytime version of StoSOO may require collecting a different number of samples per node (as a function of their depth), and is left for future work.

The main message of this chapter is to illustrate that the simple knowledge that the function possesses some smoothness, even though, this smoothness is unknown, may be sufficient to design optimistic optimization strategies with performance guarantees. The performance of such algorithms are expressed in terms of the best valid semi-metric under which the function is smooth, and we have seen that for a large class of functions, they perform almost as well as optimistic algorithms that would known (and use) the best semi-metric.

In this chapter we consider the optimistic approach for solving planning problems. In comparison to the previous chapters about optimization, the planning problem introduces some structure in the search space and the function to be optimized. Here, the search space is the set of available policies (where a policy may be a mapping from states to actions), and the function to be optimized (the so-called value function) is defined as the (possibly expected) sum of rewards collected along the trajectories resulting from following a policy.

In this chapter, we assume that a full model of the dynamics and the reward function is available but each call to the model has a (numerical) cost. Thus our goal is to return the best possible plan given a finite numerical budget (e.g., number of calls to the model, CPU time, ...).

More precisely, we consider the following online planning setting: at each time k, we perform a simulated search (planning) in the set of all possible policies starting from the current state x k and using a finite number n of calls to the model (our numerical budget). When the budget is exhausted, we return a recommended action a k to follow. This action is executed in the real environment, which generates a transition to a next state x k+1 . Then another search is performed from this new 90 state, and the same procedure is repeated again and again.

Since the budget for returning each action is limited, our goal is to perform the most efficient search in the space of policies starting from the current state, in order to recommend the best possible immediate action to follow.

Such algorithms belong to the planning class [START_REF] Steven | Planning Algorithms[END_REF]] and are known as online planning [Kearns et al., 2002a, Péret and[START_REF] Péret | On-line search for solving large Markov decision processes[END_REF] or lazy planning [START_REF] Defourny | Lazy planning under uncertainties by optimizing decisions on an ensemble of incomplete disturbance trees[END_REF] in the Computer Science literature, and as model-predictive or receding-horizon control [Maciejowski, 2002, Camacho and[START_REF] Camacho | Model Predictive Control[END_REF] in the Systems and Control literature. In the AI community, related works are the classical A* heuristic search [START_REF] Nilsson | Principles of Artificial Intelligence[END_REF] and the AO* variant from [START_REF] Hansen | A heuristic search algorithm for Markov decision problems[END_REF].

This online planning approach is different from the valuefunction and policy search methods usually considered in dynamic programming and reinforcement learning [START_REF] Sutton | Reinforcement Learning: An Introduction[END_REF][START_REF] Bertsekas | Neuro-Dynamic Programming[END_REF][START_REF] Szepesvári | Algorithms for Reinforcement Learning[END_REF][START_REF] Sigaud | Markov Decision Processes in Artificial Intelligence[END_REF][START_REF] Buşoniu | Reinforcement Learning and Dynamic Programming Using Function Approximators[END_REF]; the latter methods usually seek a global solution, whereas online planning finds actions on demand, locally for each state where they are needed. We thus expect those online planning techniques to be less dependent on the state space size.

In this chapter we present three settings where the optimistic principle can guide us in performing this search [Buşoniu et al., 2011a]. In all settings we consider an infinite-time horizon with discounted rewards. Section 5.1 considers the case of deterministic dynamics and reward functions, Section 5.2 the case of general stochastic rewards with deterministic dynamics, and Section 5.3 the general case of Markov Decision Processes.

In all three situations we provide performance bounds on the loss (how close the quality of the recommended action is from that of the optimal action) as a function of the number of calls to the model. For clarity, in this chapter we will make use of standard notations in reinforcement learning that may differ from the notations used in previous chapters.

Deterministic dynamics and rewards

Setting and notations

Here the dynamics and reward functions are deterministic. Let X denote the state space, A the action space, f : X × A → X the transition dynamics, and r : X ×A → R the reward function. If at time t, the current state is x t ∈ X and the chosen action a t , then the system jumps to the next state x t+1 = f (x t , a t ) and a reward r(x t , a t ) is received. Again we will assume that all rewards lie in the interval [0, 1].

We assume that the state space is large (possibly infinite), and the action space is finite, with K possible actions. We consider an infinite-time horizon problem with discounted rewards (0 ≤ γ < 1 is the discount factor). For any policy π : X → A we define the value function V π : X → R associated to that policy:

V π (x) def = t≥0 γ t r(x t , π(x t )),
where x t is the state of the system at time t when starting from x (i.e. x 0 = x) and following policy π.

We also define the Q-value function Q π : X × A → R associated to a policy π, for each state-action pair (x, a), as the value of playing a in x and π thereafter:

Q π (x, a) def = r(x, a) + γV π (f (x, a)).
We have the property that V π (x) = Q π (x, π(x)). Now the optimal value function (respectively Q-value function) is defined as: a), which corresponds to playing a now and optimally after). From the dynamic programming principle, we have the Bellman equations (see e.g., [START_REF] Bertsekas | Neuro-Dynamic Programming[END_REF]Tsitsiklis, 1996, Puterman, 1994]):

V * (x) def = sup π V π (x) (respectively Q * (x, a) def = sup π Q π (x,
V * (x) = max a∈A r(x, a) + γV * (f (x, a)) Q * (x, a) = r(x, a) + γ max b∈A Q * (f (x, a), b).

Planning under finite numerical budget

We assume that we possess a generative model of f and r that can be used to generate simulated transitions and rewards. We want to make the best possible use of this model in order to return a single action (or a sequence of actions) from any given initial state. The action-selection procedure takes as input the current state x of the system and outputs an action a(n) using at most n calls to the generative model. The amount n of available numerical resources may not be known before they are all used (e.g. because of time constraints), so we wish to design anytime algorithms that can return an action a(n) for any possible time n. Our goal is that the proposed action a(n) be as close as possible to the optimal action in that state. For that purpose, we define the performance loss r n as the difference in terms of the sum of obtained rewards between following the recommended action a(n) and then following an optimal path instead of following an optimal path from the beginning:

r n def = max a∈A Q * (x, a) -Q * (x, a(n)).
(5.1)

Now, from such an online planning algorithm one may define a policy π which would select in each state encountered along a trajectory the action recommended by the algorithm using n calls to the model. The previous definition of the loss is motivated by the fact that an algorithm with small loss at each state (say r n ≤ ) will generate a policy π which is near-optimal (i.e., such that V * (x) -V π (x) ≤ 1-γ , see e.g., [START_REF] Hren | Optimistic planning of deterministic systems[END_REF]).

The planning tree

For a given initial state x, consider the (infinite) planning tree defined by all possible sequences of actions (thus all possible reachable states starting from x). Write A ∞ the set of infinite sequences (a 0 , a 1 , a 2 , . . . ) where a t ∈ A. The branching factor of this tree is the number of actions |A| = K. Since the dynamics are deterministic, to each finite sequence a ∈ A d of length d corresponds a state that is reachable starting from x by following this sequence of d actions.

Using standard notations over alphabets, we write A 0 = {∅}, A * the set of finite sequences, for a ∈ A * we write h(a) the length of a, and aA h = {aa , a ∈ A h }, where aa denotes the sequence a followed by a . We identify the set of finite sequences a ∈ A * to the set of nodes of the tree.

The value v(a) of an infinite sequence a ∈ A ∞ is the discounted sum of rewards along the trajectory starting from the initial state x and defined by the choice of this sequence of actions:

v(a) def = t≥0 γ t r(x t , a t )
, where x 0 = x, and x t+1 = f (x t , a t ). Now, for any finite sequence a ∈ A * (or node) we define the value v(a) = sup a ∈A ∞ v(aa ). We write v * = v(∅) = sup a∈A ∞ v(a) the optimal value at the initial state (root of the tree). We also define the u- At any finite time t an algorithm has expanded a set of t nodes, which defines the expanded tree T t . Expanding a node a ∈ A h means using the generative model f and r to generate transitions and rewards for the K children nodes aA. The set of leaves of T t represents the set of nodes that can be expanded at time t + 1 and is denoted by L t .

Thus, once a node, a ∈ A * is expanded, the values u(a) and b(a) can be computed (since they only depend on rewards obtained along the finite sequence a).

Minimax bounds

First, consider a uniform planning strategy, defined by expanding at each round t any node in L t having the smallest depth. At round n (i.e., once n nodes have been expanded), the algorithm returns the immediate action a ∈ A having the largest u-value: a(n) def = arg max a∈A u(a) (ties broken arbitrarily).

This strategy expands the set of sequences in a uniform fashion; hence, at round n = 1

+ K + K 2 + • • • + K d = K d+1 -1
K-1 , all nodes of depth up to d have been expanded. Thus the value u(a) of each action a ∈ A is known up to an error v(a)u(a) ≤ γ d+1 1-γ , since the rewards of all paths up to depth d have been seen, and the remaining rewards from depths d + 1 on sum to at most γ d+1 1-γ . We deduce an upper-bound on the loss of uniform planning:

r n ≤ 1 γ(1 -γ) n(K -1) + 1 - log 1/γ log K .
(5.3)

In addition we have the following lower-bound (see [START_REF] Hren | Optimistic planning of deterministic systems[END_REF]): For any algorithm and any n, there exists a reward function, such that its loss is at least

r n ≥ γ 1 -γ n(K -1) + 1 - log 1/γ log K .
(5.4)

We thus observe that the uniform planning strategy achieves a loss Ω(n -log 1/γ log K ) in a minimax sense (i.e. for any possible environment). And the lower-bound tells us that (up to a constant factor) there is no algorithm that can do better uniformly over all problems.

However, this does not tell us that there is no better algorithms for some problems. In the next section we show that strictly better algorithms can be designed for specific classes of problems.

Optimistic planning

The infinite set of sequences A ∞ is our search space (denoted by X in previous sections) and each a ∈ A ∞ is a point in that space. The value v(a) of each sequence a ∈ A ∞ is the sum of discounted rewards along the sequence. Now, by defining the metric (a, a ) = γ h(a,a )

1-γ , where h(a, a ) def = max{t ≥ 0, ∀0 ≤ s < t, a s = a s } (with the convention that h(a, a ) = 0 if a 1 = a 1 ), we have the property that for all a, a ∈ A ∞ , |v(a)v(a )| ≤ (a, a ), i.e., the value function v is Lipschitz w.r.t. the metric .

Any subtree T t corresponds to a partitioning of A ∞ into subsets. To each subset a ∈ L t the value b(a) is an upper-bound on v(a). Expanding a leaf a ∈ L t of this tree means splitting the corresponding subset into K smaller subsets aa , for a ∈ A.

Thus one may apply the DOO algorithm from Section 3.3: at each round t, we expand the leaf of the expanded tree with highest b-value. And after n node expansions, we return the action with highest u-value (where the values are defined in (5.2)).

This defines an algorithm, called Optimistic Planning algorithm (OPD) (see Algorithm 1), that builds an asymmetric planning tree aiming at exploring first the most promising parts of the tree. Branches with low rewards close to the root will not be further explored and only near-optimal paths will be continually expanded. Although OPD is directly inspired from DOO, there are two important differences with DOO: (1) here we have a structured problem where the value v(a) of any point a ∈ A ∞ is the sum of (discounted) rewards along an (infinite) sequence of actions, and (2) the budget n represents the number of calls to the generative model (i.e. transitions and rewards) and is not directly related to the number of evaluations of the function v.

Analysis: Like for DOO, we have the property that the b-value of any node expanded by OPD is at least as much as the b-value of a leaf containing an optimal path, which is at least v * . Thus the deepest expanded node in the final tree T n has a u-value which is at least v * -γ dn 1-γ , where d n is the maximal depth of nodes in T n . We deduce that the value of the best path in T n (thus also the recommended action) has a u-value which is at least v * -γ dn 1-γ , which implies that the loss of OPD is bounded as

r n ≤ γ dn 1 -γ .
(5.5)

As a consequence, for any reward function, the upper bound on the loss for the optimistic planning is never larger than that of the uniform planning (since the uniform exploration is the exploration strategy that implies the smallest depth d n for any given n).

However the lower bound tells us that no improvement (compared to uniform planning) may be expected in a worst-case setting. In order to quantify a possible improvement over uniform planning, one thus needs to define specific classes of problems.

We now define a measure of the quantity of near-optimal sequences. By denoting T + the set of sequences in A h , for any h, that are γ h 1-γoptimal, we define κ ∈ [1, K] as the (asymptotic) branching factor of T + :

κ = lim sup h→∞ a ∈ A h : v(a) ≥ v * - γ h 1 -γ 1/h .
(5.6)

This measure is closely related to the notion of near-optimality dimension d (and corresponding constant C) introduced in Chapter 3.3. Indeed, if there are C κ h (for some constant C ) sequences of length h in T + , then the corresponding nodes represents a set of -balls of diameter γ h 1-γ that form a packing of the set of (infinite) sequences that are γ h 1-γ -optimal. Writing = γ h 1-γ we have that the set of -optimal points of A ∞ can be packed by C κ h = C -d such -balls, where the near-optimality dimension d and corresponding constant C are:

d = log κ log 1/γ and C = C κ(1 -γ) -d .
(5.7)

We have the following result: The proof of this result can be found in [START_REF] Hren | Optimistic planning of deterministic systems[END_REF], but in light of the previous discussion, it is a direct consequence of the analysis of DOO. Some intuition about T + : By definition, T + is the set of finite sequences that are γ h 1-γ -optimal, thus from any a ∈ T + , given the set of rewards obtained along this sequence, one cannot decide whether this sequence belongs to an optimal path or not. Now, once a sequence does not belong to T + , it is not useful to further expand it since it is clear that whatever the later rewards are, it is not be part of an optimal path. Thus T + is exactly the set of sequences that deserve to be further expanded in order to find the optimal path.

The nice property of OPD is that it only expands nodes in T + (which explains why the performance of OPD is expressed in terms of the branching factor κ of T + ). This implies that OPD cannot be improvable uniformly over the class of problems characterized by a given κ.

Indeed, by defining the class of problems P(κ) by all environments having a set T + with branching factor κ, we have that the loss of OPD on any problem P ∈ P(κ) satisfies:

r n (P ) = O n - log 1/γ log κ
. And we may also deduce a κ-minimax lower bound (not proven here): for any algorithm and for any κ ∈ [1, K], there exists a problem P ∈ P(κ) such that the loss of this algorithm applied to P is at least r n = Ω n -log 1/γ log κ . Thus OPD is κ-minimax optimal.

Remark 5.1. OPD greatly improves over the uniform planning whenever there is a small proportion of near-optimal paths (i.e. κ is small), and the bound is always at least as good as that for uniform planning. The case κ = 1 provides exponential rates. In particular, this is the case when there exists a depth h 0 such that for any sequence of depth h ≥ h 0 along an optimal path, the gap in the Q-values at the corresponding state x h is lower bounded by a quantity independent of h: ∃Δ > 0, for all h ≥ h 0 ,

V * (x h ) - max a∈A s.t. Q * (x h ,a)<V * (x h ) Q * (x h , a) ≥ Δ. (5.8)
Indeed in such a situation, the number of nodes in a sub-optimal branch departing from any state x h (along the optimal path) is at most

K H where γ H /(1 -γ) ≥ Δ. Thus a ∈ A h : v(a) ≥ v * -γ h 1-γ
is bounded by a constant independent of h, thus κ = 1.

SOO for planning?

In previous sections (see e.g. Section 5.3.2) we built a metric defined over the space of policies, such that the value function v is Lipschitz w.r.t. (see e.g. (5.14)). Now it could be the case that the value function possesses some additional local smoothness around the optimal policy π * , in the sense that there exists another semi-metric of "higher order" such that (3.8) holds, i.e. for all π, v(π * )v(π) ≤ (π * , π) (in a way similar to the example illustrated in Section 3.3.3 where the function f was globally Lipschitz w.r.t. 1 and locally smooth w.r.t. the higher-order semi-metric 2 ). In such cases, it would be interesting to use a version of SOO for planning. In the deterministic case described in Section 5.1, an extension of OPD to the simultaneous node expansion strategy implemented in SOO is straightforward and is expected to improve the numerical performances in some planning problems that possess such higher order smoothness.

Deterministic dynamics, stochastic rewards

Now we consider the problem of planning in environments where transitions are deterministic but rewards are stochastic. Thus for any state x and action a ∈ A, the call to the generative model returns a transition to a unique next-state f (x, a) and a reward sample drawn (independently from previous samples) from a probability distribution ν(x, a) (with mean r(x, a)) on [0, 1]. Thus several calls to the generative model for each state action (x, a) are required in order to estimate precisely the average reward r(x, a). Again we consider an infinite-time horizon problem with discounted rewards and the value function is defined identically as in Section 5.1.1. Now consider the planning problem given an initial state x and define the set of infinite sequences of actions A ∞ like in Subsection 5.1.2. For any finite sequence a ∈ A * , we write ν(a) the corresponding reward distribution, and r(a) its expectation. During the exploration of the environment, the agent sequentially makes calls to the generative model, under the global constraint that the number of calls is at most n in total. For a ∈ A h , write Y m h ∼ ν(a) the reward sample collected when selecting the sequence a for the m th time.

OLOP algorithm

We now describe the Open Loop Optimistic Planning (OLOP) algorithm introduced in [START_REF] Bubeck | Open loop optimistic planning[END_REF]. In that paper, the term "open-loop" refers to policies that are function of a sequence of actions only and not of the underlying resulting states. However in the setting described here (where the transitions are deterministic), the underlying state is uniquely defined by the sequence of actions, thus the planning is actually closed-loop.

The OLOP algorithm is described in Algorithm 2. Given a budget n (which here needs to be known before the algorithm starts), the algorithms generates M sequences of actions of length L (where LM ≤ n). The algorithm defines b-values assigned to any sequence of actions in A L . At time m = 0, the b-values are initialized to +∞. Then, after episode m ≥ 1, the b-values are defined as follows: For any

1 ≤ h ≤ L, for any a ∈ A h , let T m (a) = m s=1 1{a s 0:h-1 = a}
be the number of times we played a sequence of actions beginning with a. Now we define the empirical average of the rewards for the sequence a as:

μ m (a) = 1 T m (a) m s=1 Y s h 1{a s 0:h-1 = a},
if T m (a) > 0, and 0 otherwise. The corresponding upper-confidencebound on the value of the sequence of actions a ∈ A h is defined as: end for return Action a(n) = arg max a∈A T a (M ).

b m (a) = h-1 t=0 γ t μ m (a 0:t ) + γ t 2 log M T m (a 0:t ) + γ h 1 -γ , if T m (a)

Analysis of OLOP

Let κ ∈ [1, K] be defined as

κ = lim sup h→∞ a ∈ A h : v(a) ≥ v * -2 γ h 1 -γ 1/h .
(5.10)

Notice that this definition is very close to (5.6), where the additional 2 factor accounts for the additional uncertainty due to the empirical estimation of the rewards. We deduce the following bound on the expected loss, whose proof is omitted here but can be found in [START_REF] Bubeck | Open loop optimistic planning[END_REF].

Theorem 5.2. For any κ > κ, the expected loss is bounded as:

Er n = ⎧ ⎪ ⎨ ⎪ ⎩ Õ n - log 1/γ log κ if γ √ κ > 1, Õ n -1 2 if γ √ κ ≤ 1.

Discussion

In this section we compare the performance of OLOP with previous algorithms that can be adapted to this framework. This discussion is summarized in Figure 5.1. We also point out several open questions raised by these comparisons.

Many good arms Few good arms

log K log 1/γ log K log 1/γ d β 0 2 1 0 ÜÔÓÒ ÒØ 0 ÀÇǸ ÓÓÑ Ò ÇÄÇÈ Í ¹ ÁÊ -1 d+2 -1 d -1 β+1 -1/2
∈ [0, log K log 1/γ ], or equivalently β ∈ [0, log K log 1/γ ], or κ ∈ [1, K], in the case Kγ 2 > 1. We have the relations κ = Kγ β and β = log K log 1/γ -d.
Comparison with HOO/StoOO/Zooming algorithms: In Section 5.1.5 we showed that the mapping a ∈ A ∞ → v(a) is Lipschitz w.r.t. some metric defined over the space A ∞ . Thus we could use the HOO algorithm described in Section 3.4.2 (or the zooming algorithm of [Kleinberg et al., 2008a]) and derive performance bounds in terms of the near-optimality dimension d = log κ log 1/γ (see (5.7)). The expected loss of HOO would thus be of order

Er n = Õ(n -1/(d+2) ) = Õ(n - log 1/γ log κ+2 log 1/γ ). (5.11)
Clearly, this rate is always worse than the ones in Theorem 5.2. This is expected since these algorithms do not use the specific structure of the global reward function (which is the sum of rewards obtained along a sequence) thus do not estimate efficiently the mean-rewards based on generalization across arms. More precisely, they do not consider the fact that a reward sample observed for an arm (or sequence) ab provides information for the estimation of any other arm in aA ∞ . Thus we see that it is crucial to take into account the specific reward structure of the problem in order to obtain tight bounds.

Comparison with UCB-AIR: If one knows that there are many nearoptimal sequences of actions (i.e. when κ is close to K), then one may deduce that among a given number of paths chosen uniformly at random, there exists at least one which is very good with high probability. This idea is exploited by the UCB-AIR algorithm [START_REF] Wang | Algorithms for infinitely many-armed bandits[END_REF], introduced in Section 1.2.1 for the setting of many-armed bandits. This algorithm could be used here, where at each round one may choose either to generate a new sequence by selecting a set of actions uniformly randomly, or to re-sample a sequence already explored. We have seen that the regret bound of UCB-AIR is expressed in terms of the coefficient β > 0, which is such that the probability of selecting an -optimal sequence is of the order of β . In the planning problem, one can see that κ is closely related to β. Indeed, our definition of κ implies that the proportion of -optimal sequences (chosen uniformly randomly), for = 2 γ h 1-γ , is O(κ h ), resulting in κ = Kγ β . Thus applying UCB-AIR in our setting yields the bound on the expected loss:

Er n = ⎧ ⎨ ⎩ Õ(n -1 2 ) i f κ > Kγ Õ(n -1 1+β ) = Õ(n - log 1/γ log K/κ+log 1/γ ) if κ ≤ Kγ
As expected, UCB-AIR is very efficient when there is a large proportion of near-optimal paths. However UCB-AIR requires the knowledge of β (or equivalently κ) whereas OLOP (as well as HOO/Zooming) does not.

Figure 5.1 shows a comparison of the exponents in the loss bounds for OLOP, uniform planning, UCB-AIR, and HOO (in the case Kγ 2 > 1). We note that the rate for OLOP is better than UCB-AIR when there is a small proportion of near-optimal paths (small κ). Uniform planning is always dominated by OLOP and corresponds to a minimax lower bound for any algorithm. HOO/Zooming are always strictly dominated by OLOP and they do not attain minimax performances.

Open questions are whether or not (1) one can do as well as UCB-AIR (for large κ) when κ is unknown, (2) one can do better than both OLOP and UCB-AIR in intermediate cases (i.e. when 1/γ 2 < κ < γK).

Comparison with OPD: Remarkably, in the case κγ 2 > 1, we obtain the same rate for the loss as planning with deterministic rewards (using OPD). Intuitively, the reason is that in the case κγ 2 > 1 the planning problem is hard since either the planning horizon 1/ log(1/γ) and/or the branching factor κ may be large. Thus the planning tree has to be explored both in breadth and in depth. Fortunately, it is in those situations that the cross estimation of rewards among sequences (as discussed in the previous comparison with HOO) is the most beneficial. Indeed in such cases, a reward r(a) is estimated using reward samples from many observed sequences ab. Thus using the specific structure of the rewards enables a fast estimation of the mean rewards, and OLOP achieves the same order (in the bound) on the expected loss as when the rewards are deterministic. We deduce that, in terms of loss rates, in hard instances of planning problems (under deterministic transitions), planning with stochastic rewards is not harder than planning with deterministic rewards.

Markov decision processes

Now we consider the setting of Markov decision processes where transitions are stochastic. More precisely we denote by p(y|x, a) the probability of a transition from x to y given action a. Here we assume that the number N of possible next-states is finite, i.e. sup x∈X,a∈A |{y : p(y|x, a) > 0}| def = N < ∞. We also assume that the rewards r(x, a) are deterministic and lie in [0, 1].

Again we consider a infinite-time horizon problem with discounted rewards. For any policy π : X → A the value function is defined as the expected sum of discounted rewards:

V π (x) def = E t≥0 γ t r(x t , π(x t )) ,
where x t is the state of the system at time t when starting from x (i.e. x 0 = x) and following policy π. We also define the Q-value function Q π : X × A → R associated to a policy π, in state-action (x, a), as:

Q π (x, a) def = r(x, a) + γ y p(y|x, a)V π (y).
The optimal value function (respectively Q-value function) is defined as

V * (x) def = sup π V π (x) (respectively Q * (x, a) def = sup π Q π (x, a))
and satisfies the Bellman equations:

V * (x) = max a∈A r(x, a) + γ y p(y|x, a)V * (y) Q * (x, a) = r(x, a) + γ y p(y|x, a) max b∈A Q * (y, b).
We assume that we possess a full model of the transition probabilities p and the reward function r, which can be used by the planning algorithm. The model takes as input a state x and returns for each action a the reward r(x, a) as well as the N next states y and the corresponding transition probabilities p(y|x, a). An algorithm takes as input an initial state x, and outputs an action a(n) using at most n calls to the model. Again the performance is assessed with the loss r n of choosing a(n) and then following an optimal path instead of following an optimal path from the beginning, as defined in (5.1).

This setting is different from the two previous sections in the fact that the space of policies cannot be identified with the set of infinite sequences of actions anymore, since a policy depends on the actual resulting states and not only on the sequence of actions.

Optimistic Planning in MDP

The Optimistic Planning in MDP (OP-MDP) algorithm [START_REF] Buşoniu | Optimistic planning for sparsely stochastic systems[END_REF]Munos, 2012] works by building incrementally a tree corresponding to the set of states that can be reached from the initial state. Notice that several nodes may correspond to the same state because of different transitions from the root to a given state. Such duplicates could be merged by transforming the tree into a graph; however here we restrict ourselves to a simple version of OP-MDP that ignores duplicates (thus each node corresponds to a unique path to any state).

We use the following notations: T denotes the infinite planning tree and T n ⊂ T is the subtree resulting from n node expansions, as illustrated in Figure 5.2 for n = 4. L t is the set of leaves of T t . We denote by x i the state associated to any node i ∈ T . For any policy π : T → A defined over the tree T , we denote by T π the (infinite) subtree corresponding to the set of nodes that are reachable when following π. For any finite subtree T ⊂ T , we define a policy-class Π : T → A as a set of policies π : T → A that share the same actions on T . We denote by T Π the corresponding (finite) subtree.

(i) γ h(i)
1-γ is expanded (represented in red): a call to the model returns the rewards and transition probabilities to the next states for each action.

Algorithm 3 describes OP-MDP. T 0 is initialized to be the root node, and for each t = 1 to n -1, a leaf J t of L t is selected and expanded, which results in adding KN children nodes (the number K of actions times the number N of next states) to the current tree. After n node expansions, OP-MDP returns the first action of the best policy found so far.

The way the leaf J t is selected is by first computing the optimistic policy-class Π + t and then selecting a leaf of the corresponding subtree with largest "contribution", as defined by (5.13). More precisely, at each round t, we define the b-values and u-values of any node of the current tree T t as follows: for any leaf j ∈ L t , b t (j) def = 1 1-γ and u t (j) def = 0, and for any other node

i ∈ T t \ L t we define b t (i) def = max a∈A r(x i , a) + γ j∈C(i,a) p(x j |x i , a)b t (j) , u t (i) def = max a∈A r(x i , a) + γ j∈C(i,a) p(x j |x i , a)u t (j) ,
where C(i, a) denotes the set of children nodes of node i when choosing Algorithm 3 Optimistic planning in MDP (OP-MDP) Initial state x 0 , model of p and r, budget n Initialize tree: T 0 = {0} (root node is called 0) for i = 1, . . . , n -1 do Build optimistic subtree T + t according to (5.12), Select leaf J t ∈ L + t with largest contribution:

J t = arg max j∈L + t p(j) γ h(j) 1 -γ ,
Expand J t (adding KN new leaves) end for Return arg max a∈A r(x 0 , a) + γ j∈C(0,a) p(x j |x 0 , a)u n (j) . action a.

By a backward induction starting from the leaves up to the root, we immediately deduce that the b-value (respectively the u-value) of any node i ∈ T t provides an upper-bound (resp. a lower bound) on the optimal value function at the corresponding state: u t (i) ≤ V * (x i ) ≤ b t (i), for any t.

We define the optimistic policy-class Π + t : T t → A as the optimal policy for the b-values for any i ∈ T t :

Π + t (i) ∈ arg max a∈A r(x i , a) + γ j∈C(i,a) p(x j |x i , a)b t (j) .
(5.12)

We denote by T + t = T π + t the corresponding optimistic subtree of the set of nodes that can be reached when following the optimistic policy, and L + t the leaves of this subtree. Now, for each leaf j ∈ L + t (of depth h(j)) we define p(j) as the probability of reaching the leaf j when starting from the root and following policy Π + t :

p(j) def = h(j)-1 h=0 p(i h+1 |i h , π + t (i h )) > 0,
where the h(j) + 1 nodes (i 0 def = 0, i 1 , . . . , i h(j) def = j) is the path from the root to j. Notice that we have j∈L + t p(j) = 1. Finally, we call contribution of a leaf j ∈ L + t the quantity

c(j) def = p(j) γ h(j) 1 -γ .
(5.13) OP-MDP selects the leaf of the optimistic subtree with largest contribution: J t ∈ arg max j∈L + t c(j). The intuition for that choice is that the diameter (difference between the upper and lower bounds) at the root is the sum of contributions of the leaves j ∈ L + t : b t (0)u t (0) = j∈L + t c(j). Thus expanding the one with largest contribution reduces as much as possible the diameter at the root, thus the accuracy of the value function at the initial state.

Analysis of OP-MDP

For any two policies π, π : T → A, define T (π, π ) = T π ∩ T π the set of their common nodes, and L(π, π ) the set of leaves of T (π, π ) (with the convention that L(π, π ) = ∅ if T π = T π ). Define (π, π ) def = j∈L(π,π ) c(j) the sum of the contributions of L(π, π ). We have the property that the value function, defined for any π : T → A, as

v(π) def = i∈T π p(i)γ h(i) r(x i , π(x i )), is Lipschitz w.r.t. : |v(π) -v(π )| ≤ (π, π ).
(5.14)

For any policy-class Π : T → A, define the diameter of Π as

diam(Π) def = sup π,π ∈Π (π, π ).
Note that from the definition of the contributions, we have that diam(Π) = j∈L(Π) c(j), where L(Π) denotes the set of leaves of the policy-class Π.

Thus one can see OP-MDP as a deterministic optimistic optimization algorithm (see DOO in Chapter 3.3) where at each round t:

• the search space T is partitioned into policy-classes defined by the current subtree T t

• an upper bound on each policy-class can be computed with the b-values and the optimistic policy-class Π + t is the one with largest upper-bound

• the diameter of the policy-class Π + t is the sum of contributions of its leaves L + t , thus expanding the leaf J t ∈ L + t with largest contribution c(j) "splits" the optimistic policy class along its "widest" direction. Now the main difference is that we are not directly working on the set of policies but on the set of nodes of the tree (which is no more equivalent). Thus expanding a node has an impact on possibly many policies, actually on all policies containing that node. Thus in order to analyze this algorithm we should not try to characterize the quantity of near-optimal policies, but instead the quantity of nodes that contribute to near-optimal policies.

For any node i ∈ T , let Π i be the policy-class Π i such that min j∈L(Π) c(j) ≥ c(i) and that has the largest diameter: S represents the set of nodes that (1) belong to a policy-class Π i with a diameter at least and (2) belong to a policy that is diam(Π i )optimal. In other words, those are the set of nodes that contribute in a significant way to near-optimal policies.

The paper [START_REF] Buşoniu | Optimistic planning for markov decision processes[END_REF] uses a slightly different definition of S (taking into account the number of leaves of Π i ) but the main results stated next are immediate consequences of the analysis undertaken in that paper. (5.15)

Then the loss of OP-MDP after n node expansions, is

r n = ⎧ ⎨ ⎩ Õ(n -1 d ) i fd > 0 O(exp[-( n a ) 1 b ]) if d = 0
The full proof of this result can be found in [START_REF] Buşoniu | Optimistic planning for markov decision processes[END_REF]. We now provide a sketch of proof and relate this near-optimality planning exponent d to the branching factor κ ∈ [1, KN] of the set of near-optimal nodes, like in previous sections with (5.6) and (5.10).

Define the set of near-optimal nodes T + ⊂ T :

T + def = i ∈ T , v(i) ≤ v * -diam(Π i ) ,
where the value of a node v(i) is the value of the best possible policy containing that node v(i) def = max π,T π i v(π). Then the near-optimality exponent d is related to the branching factor κ of T + by d = log κ log 1/γ . And like for the OPD, the set of near-optimal nodes represents the set of nodes that deserve to be expanded in order to discover the optimal policy. Similarly to OPD, the main intuition for the analysis of OP-MDP is that this algorithms only expands nodes in T + . Indeed, if at time t, a node J t is expanded, this means that its contribution is larger than that of any other leaf in L + t . Thus diam(Π + t ) = j∈L + t c(j) ≤ j∈L(Π J t ) c(j) = diam(Π Jt ) (by definition of Π Jt ). Now since Π + t is the optimistic policy-class, it means that its upper-bound v(Π + t ) + diam(Π + t ) is larger than v * . Thus

v(J t ) ≥ v(Π + t ) ≥ v * -diam(Π + t ) ≥ v * -diam(Π Jt ),
which means that J t ∈ T + .

Interesting values of d

The loss is small when d is small (and we obtain exponential rate when d = 0), or equivalently when the branching factor κ is 1.

Uniform rewards and probabilities. The worst possible rate is achieved for κ = KN (i.e. the branching factor of T + is the same as that of T ) and in this case the loss is r n = n -log(KN) log 1/γ . This happens when all policies provide the same rewards and the transition probabilities are uniform. In that case OP-MDP reduces to a uniform search, where all nodes of depth up to log n log(KN) are expanded. It may seem surprising that the performance is poor when the problem seems easy, but we should keep in mind that one usually does not know in advance what the difficulty of the problem is (i.e. d or κ are not known by the algorithm although the performance of OP-MDP is expressed in terms of those parameters). If this measure of difficulty of the problem were known, one could design algorithms that would exploit it, like the UCB-AIR algorithm presented in Chapter 1 and discussed in previous section.

Now, for any n, consider the class of problems where all rewards up to depth log n log(KN) are the same but differ from that depth on. Thus no algorithm can be uniformly better than a uniform planning algorithm on this class of problems. Thus OP-MDP is minimax-optimal on the class of problems characterized by κ = KN .

Heterogeneous transition probabilities.

When the transition probabilities are significantly heterogeneous, the part of the branching factor of T + due to the number of next states may be significantly less than N . Indeed, the set of nodes T + that may be expanded by OP-MDP contains nodes with significant contribution only. Thus the nodes that can be reached with a very small probability only are not be part of T + thus do not need to be expanded. This saves computations when the transition probabilities are very heterogeneous, and in the limit, when the probability (from any state) to one next state is close to 1, then the branching factor approaches 1, and the performance of OP-MDP is as good as OPD for deterministic dynamics (see Section 5.1).

Structured rewards.

In the case of structured rewards (i.e. the rewards along branches corresponding to different actions are heterogeneous), then the part of the branching factor of T + due to the number of actions may be significantly less than K. This case was already illustrated in Section 5.1. Now when the problem has both structured rewards and heterogeneous transition probabilities, then κ can be much less than KN and even close to 1, which provides a loss bound of order n -log 1/γ log κ . Thus like previous optimistic algorithms, the performance of OP-MDP depends on a measure of the quantity of near-optimal nodes, which are the nodes that deserve to be expanded in order to build a near-optimal policy. Our main contribution is to show that the right measure of complexity for optimistic planning is defined by the size of T + which represents the set of states that significantly contribute to near-optimal policies.

Conclusions and extensions

Generative model. OP-MDP requires a full model of the transition dynamics (i.e., for each state-action pair (x, a), a call to the model returns the set of next states y and the exact values of the transition probabilities p(y|x, a)). In many situations, only a generative model is available: Given (x, a), each call to the model returns a single next state y drawn from the true (but unknown) transition probabilities: y ∼ p (•|x, a). This is the case when an agent interacts online with an unknown environment (such as in Reinforcement learning, see [START_REF] Sutton | Reinforcement Learning: An Introduction[END_REF]Barto, 1998, Szepesvári, 2010]) from which he only observes trajectories, or when one uses Monte-Carlo simulations to numerically approximate heavy computations. Thus it would be useful to extend OP-MDP to situations where only a generative model of the transition dynamics (and rewards) is available. Also we would like to cover the case of potentially infinite number of next states (like in [Kearns et al., 2002b]) by using an number of next state samples that would depend both on the node characteristics (such as its contribution) and the numerical budget n. Designing a planning algorithm enjoying finite-time performance guarantees using a generative model only is still an open problem.

Extensions to POMDPs. In a partially observable Markov decision process (POMDP) the state of the system x t cannot be observed by the agent (see e.g. [Kaelbling et al., 1998, Bäuerle and[START_REF] Bäuerle | Markov Decision Processes with Applications to Finance[END_REF]). However, in each time t, the agent receives an observation y t , which is a stochastic function of the unknown state. In a POMDP, the best policy (which maximizes the expected rewards given the uncertainty over the state) can be obtained as a function of the belief state b t (which is a distribution over the state space X). The literature on online planning algorithms in this setting is large and we refer the interested reader to [START_REF] Ross | Online planning algorithms for POMDPs[END_REF] for a complete overview. The point-based approximation method [START_REF] Pineau | Anytime pointbased approximations for large POMDPs[END_REF]] builds a search tree of belief states, using a heuristic best-first expansion procedure which may be combined with a branch-and-bound procedure based on computations of upper and lower bounds on the value function. However no finite-time guarantee on the quality of the resulting action in terms of the numerical budget is provided.

Casting this POMDP problem into our online planning setting, the initial state is the current belief state, and the nodes of the tree that are expanded are the belief states that can be reached from the initial belief given a sequence of actions and observations. Using the work described in the previous chapter one can use OP-MDP (assuming the number N of possible observations is finite) to perform an efficient online planning whose performance does not depend on the size of the belief space (which is infinite) but on characteristics of the belief planning space, such as the quantity of belief states that contributes in a significant way to near-optimal policies.

In the case a full model of the POMDP is unknown, one can use sampling-based techniques such as the one (based on UCT) described in [START_REF] Silver | Monte-carlo planning in large POMDPs[END_REF]. Unfortunately this method does not enjoy finite-time guarantee (since UCT can be arbitrarily poor in some situations as illustrated in Section 2.3). This provides an additional motivation for extending the OP-MDP to situations where a generative model only is available.

Bayesian RL. In Bayesian Reinforcement learning (see e.g. [START_REF] Duff | Optimal learning: Computational procedures for Bayes-adaptive Markov decision processes[END_REF][START_REF] Vlassis | Reinforcement Learning: State of the Art, chapter Bayesian Reinforcement Learning[END_REF]) some parameters of the Markov decision process are initially unknown and exploration can be performed by using a Bayesian reasoning where one starts with a prior over the unknown parameters and based on the transition and reward samples observed at any time t, a posterior distribution over those parameters can be computed (either in a closed form or using numerical approximation). The so-called Bayesian-adaptive MDP (BAMDP) defines an enriched MDP which contains both the current state and the current posterior distribution over the unknown parameters. The interesting property of the BAMDP is that its state dynamics are known. Also, following the optimal action of the BAMDP from the current state provides a good exploration-exploitation strategy (which is optimal in a Bayesian sense) [START_REF] Duff | Optimal learning: Computational procedures for Bayes-adaptive Markov decision processes[END_REF]. The planning problem (of solving the BAMDP) can be addressed using sampling techniques similar to the ones for MDPs, see [START_REF] Wang | Bayesian sparse sampling for on-line reward optimization[END_REF]. Monte-Carlo tree search approaches have been developed also recently, such as in [START_REF] Asmuth | Learning is planning: near Bayesoptimal reinforcement learning via Monte-Carlo tree search[END_REF]Littman, 2011, Guez et al., 2012]. However, no finite-time guarantees were provided in those works. By using the fact that the dynamics of the BAMDP are known and by noticing that the branching factor of the BAMDP planning tree is the same as that of the original MDP (i.e. A × N ), [START_REF] Fonteneau | Optimistic planning for beliefaugmented Markov decision processes[END_REF] applied OP-MDP to the BAMDP planning problem and derived loss bounds in terms of the available numerical budget.

Finally, let us mention the harder problem of solving a POMDP when the parameters of the dynamics or observation function are unknown. An analogous Bayesian approach introduces the Bayesian-Adaptive POMDP (BAPOMDP) [START_REF] Ross | A Bayesian approach for learning and planning in partially observable Markov decision processes[END_REF] and an optimal policy in the BAPOMDP provides a Bayes-optimal exploration in the POMDP. However the planning problem of the BAPOMDP is more challenging because the branching factor now scales with the number of states of the original POMDP (see [START_REF] Ross | A Bayesian approach for learning and planning in partially observable Markov decision processes[END_REF]). Again extending the OP-MDP to handle a possible infinite number of next-states using sampling from a generative model would contribute to the problem.

Conclusion on optimistic planning. When the dynamics are deterministic, the set of policies is equivalent to the set of sequences of actions. In such cases we can design optimistic planning algorithms (OPD and OLOP) that takes into account the specific structure of the planning problem (i.e. that the value of a policy is defined as the sum of, possible expected, discounted rewards). Like for optimization algorithms, we derived performance bounds as a function of the quantity of near-optimal policies, measures with quantities like d, κ, or β. When the rewards are stochastic we described an algorithm OLOP that uses the specific structure of the planning problem to improve over a direct application of an X -armed bandit algorithm, such as HOO. This implied that in hard instances of planning problems with stochastic rewards (but deterministic transitions), the loss rate of OLOP is the same as the loss achieved by OPD when the rewards are deterministic. Now when the dynamics are stochastic, a policy is no more equivalent to a sequence of actions, and a more subtle definition of the set of important nodes that any good planning algorithm should expand is required. We characterized the set of nodes that OP-MDP expands as those that contribute in a significant way to near-optimal policies, and derived loss bounds based on this new measure of complexity.

In all considered planning problems we used the property that since the discount factor γ < 1 the value function satisfied a global Lipschitz property w.r.t. some underlying metric defined on the planning tree. Now this opens several questions. One question is whether it is possible to extend those results to the case of average reward problems? Another question (already posed at the end of Section 5.1) is whether it is possible to improve those results by using a possibly tighter semi-metric (which may be unknown) under which the value function would be locally smooth (instead of globally Lipschitz) around the optimal policy, and extend the idea of SOO (seen in Chapter 4) to the planning problem.

Conclusion

The main message of this work is to show that the "optimism in the face of uncertainty" is a simple yet powerful principle that may guide the exploration in general optimization and planning problems. It applies when some unknown environment has to be explored while some criterion needs to be optimized.

In the multi-armed bandit problem, an unknown environment (set of arms with unknown distributions) has to be explored while maximizing the sum of rewards. In function optimization under finite numerical budget (e.g. number of function evaluations), the exploration of the space should be optimized in order to return the best possible recommendation of the maximum once the numerical resources are depleted. In both situations, the performance (either in terms of cumulative regret or in terms of loss of the final recommendation) depends on some complexity measure of the problem, which may be expressed in terms of the quantity of near-optimal solutions.

In multi-armed bandits, the complexity measure is the inverse of the "distance" (i.e. in the mean or in Kullback-Leibler divergence) between the distributions of sub-optimal and optimal arms. In function optimization and in planning, we have defined a complexity measure in terms of the quantity of near-optimal solutions (i.e. the near-optimality dimension d or the proportion of near-optimal path β or the branching factor κ of a relevant subset of the tree search) measured with respect to some semi-metric under which the function is locally smooth.

Another important factor is our knowledge about the local smoothness of the function around the global optimum. If this information is known, then it can be used to build efficient optimization algorithms with performance rate independent of the search space dimension. When it is not the case, then one can still build adaptive strategies that can, in some situations, perform almost as well as if this information were known.

Finally we have seen an application to the problem of onlineplanning which illustrates the benefit of using the specific structure of the problem (rewards, transitions) to design efficient algorithms. In such situations we showed that a relevant complexity measure for the problem of online planning in a MDP is the quantity of states that significantly contribute to the set of near-optimal policies.

Figure 1 . 1 :

 11 Figure 1.1: The UCB-AIR strategy: UCB-V algorithm is played on an increasing number K(t) or arms

Figure 2 . 1 :

 21 Figure 2.1: Illustration of the Monte-Carlo Tree Search approach (Courtesy of Rémi Coulom from his talk The Monte-Carlo revolution in Go). Left: Monte-Carlo evaluation of a position in Computer Go. Middle: each initial move is sampled several times. Right: The apparently best moves are sampled more often and the tree structure grows.

Figure 2 . 2 :

 22 Figure 2.2: An example of tree for which UCT performs very poorly.

Figure 3 . 1 :

 31 Figure 3.1: Left: The function f (dotted line) is evaluated at a point xt, which provides a first upper bound on f (given the Lipschitz assumption). Right: several evaluations of f enable the refinement of its upper-bound. The optimistic strategy samples the function at the point with highest upper-bound.

Figure 3 . 2 :

 32 Figure 3.2: The evaluation of the function is perturbed by a centered noise: E[rt|xt] = f (xt). How should we define a high-probability upper-confidence-bound on f at any state x in order to implement the optimism in the face of uncertainty principle?

Figure 3 . 4 :

 34 Figure3.4: Hierarchical partitioning of the space X equivalently represented by a K-ary tree (here K = 3). The set of leaves of any subtree corresponds to a partition of X .

Figure 3 . 5 :

 35 Figure 3.5: Illustration of the local smoothness property of f around x * w.r.t. the semi-metric : the function f (x) is lower-bounded by f (x * )-(x, x * ). This essentially constrains f around x * since for x away from x * the function can be arbitrarily nonsmooth (e.g., discontinuous).

Figure 3 . 6 :

 36 Figure 3.6: Deterministic Optimistic Optimization (DOO) algorithm.

  D L ∞ -balls of diameter (since a L ∞ -balls of diameter is a -ball of diameter 1/β ). Thus the nearoptimality dimension is d = D(1/β -1/α) (and the constant C = 1). From Corollary 3.3 we deduce that (i) when α > β, then d > 0 and in this case, r n = O n -1 D αβ α-β , and (ii) when α = β, then d = 0 and the loss decreases exponentially fast:

D

  -balls of diameter . Thus the local near-optimality dimension (thus the near-optimality dimension in light of Remark 3.3) is d = D(1/β -1/α), and the results of the previous example apply (up to constants), i.e. for α > β, then d > 0 and r n = O n -1 D αβ α-β . And when α = β, then d = 0 and one obtains the exponential rate r n = O(2 -α(n/C-1) ).

Figure 3 . 7 :

 37 Figure 3.7:The trees Tn built by DOO after n = 150 rounds with the choice of (x, y) = 14|x -y| (left) and (x, y) = 222|x -y| 2 (right). The upper parts of the figure shows the binary trees built by DOO. Note that both trees are extensively refined where the function is near-optimal, while it is much less developed in other regions. Using a metric that reflects the quadratic local regularity of f around its maximum (right figure) enables a much more precise refinement to the discretization around x * than using the metric under which the function is globally Lipschitz (left).

nFigure 3 . 8 :

 38 Figure 3.8: Loss rn for different values of n for a uniform grid and DOO with the two semi-metric 1 and 2.

Figure 3 . 9 :

 39 Figure 3.9: Stochastic Optimistic Optimization (StoOO) algorithm

1

  d+2 . Now, setting the parameter η as a function of the time horizon n enables the derivation of the expected loss bound. For example with the choice η = 1/n we have Er n = O log n n 1 d+2 .

Figure 3 . 10 :

 310 Figure 3.10: Hierarchical Optimistic Optimization (HOO) applied to the problem of minimizing the loss rn.

Figure 3 . 11 :

 311 Figure3.11: Illustration of the leaf selection procedure in round t. The tree represents Tt. In the illustration, B h+1,i 1 (t) > B h+1,i 2 (t), therefore, the selected path traverses the node (h + 1, i1). The point xt is chosen in the selected leaf (ht, jt).

Figure 3 . 12 :

 312 Figure 3.12: The trees T n built by HOO after n = 10 2 , 10 3 , 10 4 and 10 5 noisy function evaluations. The mean-payoff function (shown in the bottom part of the figures) is x ∈ [0, 1] -→ f (x) = sin(13x) sin(27x) + 1 /2 and the corresponding rewards are Bernoulli-distributed.

Figure 4 . 1 :

 41 Figure 4.1: Simultaneous Optimistic Optimization (SOO) algorithm.

Figure 4 .

 4 Figure 4.3 shows the first iterations of SOO on the function f (x) = 1/2 sin(13x) sin(27x) + 1 already considered in Section 3.3.3. At each round several cells (indicated by the circled dots and the bold segments) are simultaneously split. Here we used a branching factor K = 3 and the maximal depth function h max (t) = √ t.

Figure 4 . 2 :

 42 Figure 4.2: Numerical performance of SOO for the function f (x) = 1/2 sin(13x) sin(27x) + 1

Figure 4 . 3 :

 43 Figure 4.3: The first 5 iterations of the SOO algorithm and the resulting tree Tn after n = 150 function evaluations. Here f (x) = sin(13x) sin(27x) + 1 /2 and K = 3. The blue dots represent the evaluations of the function at the center of the cells. The circle around the dots and the bold segments shows the nodes that are expanded at each iteration.

Figure 4 . 4 :

 44 Figure 4.4: The first 5 iterations of the SOO algorithm and the resulting tree Tn after n = 150 function evaluations for the garland function f (x) = x(1x) 4 -| sin(60x)| .

Figure 4 . 5 :

 45 Figure 4.5: The first 5 iterations of the SOO algorithm and the resulting tree Tn after n = 150 function evaluations. Here f (x) is a (function) sample of a Brownian motion.

Figure 4 . 6 :

 46 Figure 4.6: The first 5 iterations of the SOO algorithm and the resulting tree Tn after n = 150 function evaluations. Here we considered the 2-dimensional function f (x1, x2) = f (x1)f (x2) where f (x) = sin(13x) sin(27x) + 1 /2 and K = 3. When a node is expanded, its corresponding cell is split in the widest direction in 3 subsets of same size.

Figure 4 . 7 :

 47 Figure 4.7: The first 3 iterations of the SOO algorithm and after n = 17, 53 and 54 function evaluations on the function built from the example illustrated in Figure 2.2.

Figure 4 . 8 :

 48 Figure 4.8: The Stochastic Simultaneous Optimistic Optimization (StoSOO) algorithm

Figure 4 . 9 :

 49 Figure 4.9: Any function satisfying (4.7) (i.e., lying in the gray area) has a nearoptimality dimension d = 0 since it possesses a lower-and upper-envelopes that are of same order around x * .

Figure 4 . 10 :

 410 Figure 4.10: We illustrate the case of a function with different order in the upper and lower envelopes. Here f(x) = 1 -√ x + (-x 2 + √ x) • (sin(1/x 2 ) + 1)/2.The best possible semi-metric of the form (x, y) = c|x -y| α is such that α ≤ 1/2 in order to satisfy (3.8). However, since the upper-envelope of f is quadratic, the maximum number of -balls with radius that can pack X (i.e., Euclidean balls with radius 1/α ) is at most of order 1/2 / 1/α ≤ -3/2 since α ≤ 1/2. Thus there is no metric of the form (x, y) = c|x -y| α for which d < 3/2.

  and b-values (respectively lower-and upper-bounds on v(a)) as uall rewards are in [0, 1] we trivially have that u(a) ≤ v(a) ≤ b(a).

Algorithm 1

 1 Optimistic Planning algorithm (OPD) Expand the root. for t = 1 to n do Expand a node a t ∈ arg max a∈Lt b(a),

Theorem 5. 1 .-.

 1 If κ > 1 then the loss of OPD is r n = O n If κ = 1 and there are at most C sequences of length h in T + (for any h ≥ 0), the loss decreases exponentially fast as r n = O e -log 1/γ C n .

Algorithm 2

 2 > 0 and +∞ otherwise. Now that we have upper confidence bounds on the value of many sequences of actions we can sharpen these bounds for the sequences a ∈ A L by defining the b-values as: each episode m = 1, 2, . . . , M, OLOP selects a sequence a m ∈ A L with highest b-value, observes the rewards Y m t ∼ ν(a m 0:t-1 ), t = 1, . . . , L provided by the environment, and updates the b-values. At the end of the exploration phase, OLOP returns an action that has been the most often played, i.e. a(n) = arg max a∈A T a (M ). Open Loop Optimistic Planning Let M be the largest integer such that M log M/(2 log 1/γ) ≤ n. Let L = log M/(2 log 1/γ) . for m = 1 to M do Computes the b-values at time m -1 for sequences of actions in A L using (5.9) and chooses a sequence that maximizes the corresponding b-value: a m ∈ arg max a∈A L b a (m -1).

Figure 5 . 1 :

 51 Figure 5.1: Comparison of the exponent rate of the bounds on the loss for OLOP, uniform planning, UCB-AIR, and HOO/StoOO/Zooming, as a function of d∈ [0, log K log 1/γ ], or equivalently β ∈ [0, log K log 1/γ ], or κ ∈ [1, K],in the case Kγ 2 > 1. We have the relations κ = Kγ β and β = log K log 1/γd.

Figure 5 . 2 :

 52 Figure 5.2:The subtree corresponding to the set of states that can be reached from the initial state. The big arrows represent the actions (K = 2) and the thin arrows the transitions to the next states (N = 2). Here 4 nodes have been expanded. The optimistic policy and the leaves of the resulting optimistic subtree are represented in yellow.

Figure 5 . 3 :

 53 Figure 5.3: Among the leaves of the current optimistic subtree, the one with the largest contribution p(i) γ h(i)1-γ is expanded (represented in red): a call to the model returns the rewards and transition probabilities to the next states for each action.

Π

  i = arg max Π i;min j∈L(Π) c(j)≥c(i) diam(Π),and for any > 0, defineS def = i ∈ T , diam(Π i ) ≥ , and ∃Π i, v(Π) ≥ v *diam(Π i ) .

Theorem 5. 3 .

 3 Let d ≥ 0 be any constant such that |S | = Õ( -d ), i.e. such that there exists a, b > 0, for all > 0, |S | ≤ a(log(1/ )) b -d .

end if end if end if end for end while.

  Return the state with highest empirical mean whose node has been expanded:

). if T h,i (t) < k then Sample state x t = x h,i and collect reward r t t ← t + 1 else Add the K children of (h, i) to T t (we expand this node)

  and is described in Figure 4.8. StoSOO defines the b-values b h,j (t) of any node at round t, by

	b h,j (t)	def = μh,j (t) +	log(n 2 /η) 2T h,j (t)	,	(4.3)

We write f ( ) = Θ(g( )) if ∃c1, c2, 0, ∀ ≤ 0, c1g( ) ≤ f ( ) ≤ c2g( ).

where O stands for a O notation up to a polylogarithmic factor

where poly(d) refers to a polynomial in d

This proof is a correction of the one in[Munos,

2011]

Acknowledgements

I would like to thank all my students and colleagues who worked with me on the topics presented in this paper, including (by alphabetic order) Jean-Yves Audibert, Sébastien Bubeck, Lucian Buşoniu, Alexandra Carpentier, Pierre-Arnaud Coquelin, Rémi Coulom, Raphael Fonteneau, Sylvain Gelly, Jean-Bastien Grill, Jean-François Hren, Nathaniel Korda, Odalric-Ambrym Maillard, Amir Sani, Marta Soare, Gilles Stoltz, Csaba Szepesvári, Olivier Teytaud, Michal Valko, and Yizao Wang. This work was supported by the European Community's Seventh Framework Programme (FP7/2007-2013) under grant agreement n • 270327.