Nicolò Cesa-Bianchi

Nicolo Cesa-Bianchi

Pierre Gaillard
email: pierre.gaillard@

Claudio Gentile
email: claudio.gentile@uninsubria.

Sébastien Gerchinovitz
email: sebastien.gerchinovitz@math.

N Cesa-Bianchi

Algorithmic Chaining and the Role of Partial Feedback in Online Nonparametric Learning

Keywords: online learning, nonparametric, chaining, bandits

We investigate contextual online learning with nonparametric (Lipschitz) comparison classes under different assumptions on losses and feedback information. For full information feedback and Lipschitz losses, we design the first explicit algorithm achieving the minimax regret rate (up to log factors). In a partial feedback model motivated by second-price auctions, we obtain algorithms for Lipschitz and semi-Lipschitz losses with regret bounds improving on the known bounds for standard bandit feedback. Our analysis combines novel results for contextual second-price auctions with a novel algorithmic approach based on chaining. When the context space is Euclidean, our chaining approach is efficient and delivers an even better regret bound.

Introduction

In online learning [START_REF] Cesa | Prediction, learning, and games[END_REF]Shalev-Shwartz, 2011;[START_REF] Hazan | Introduction to online convex optimization[END_REF] an agent (or learner) interacts with an unknown and arbitrary environment in a sequence of rounds. At each round, the learner chooses an action from a given action space and incurs the loss associated with the chosen action. The loss functions, which are different in each round, are fixed by the environment at the beginning of the interaction. After choosing an action, the learner observes some feedback, which can be used to reduce his loss in subsequent rounds. A variety of different feedback models are discussed in the literature. The most common feedback model is full information, also known as prediction with expert advice, where the learner gets access to the entire loss function at the end of each round. Another common feedback model is bandit information, where the learner just observes the loss assigned to the action chosen in the current round. Feedback models in between full and bandit information are also possible, and can be used to describe many interesting online learning applications -see e.g., [START_REF] Noga Alon | Nonstochastic multi-armed bandits with graph-structured feedback[END_REF][START_REF] Noga Alon | Online learning with feedback graphs: Beyond bandits[END_REF]. The performance of an online learner is measured using a notion of regret, which is typically defined as the amount by which the learner's cumulative loss exceeds the cumulative loss of the best fixed action in hindsight.

Online contextual learning is a generalization of online learning where the loss functions generated by the environment are paired with contexts from a given context space. On each round, before choosing an action, the learner observes the current context. In the presence of contextual information, the learner's regret is no longer defined against the best action in hindsight, but rather against the best policy (i.e., mapping from the context space to the action space) in a given reference class of policies. In agreement with the online learning framework, online contextual learning is nonstochastic. Namely, regret bounds must hold for arbitrary sequences of contexts and losses.

In order to capture complex environments, the reference class of policies should be as large as possible. In this work, we focus on nonparametric classes of policies, such as classes containing policies that are Lipschitz with respect to metrics defined on the context and action spaces. The best possible (minimax) growth rate of the regret, as a function of the number T of rounds, is then determined by the interplay among the richness of the policy class, the constraints on the loss functions (e.g., Lipschitz, convex, etc.), and the type of feedback information (full, bandit, or in between). Whereas most of the previous works study online nonparametric learning with convex losses, in this paper we investigate nonparametric regret rates for general Lipschitz losses (in fact, some of our results apply to an even larger class of loss functions).

In the full information setting, a very general yet simple algorithmic approach to online nonparametric learning with convex and Lipschitz losses was introduced by [START_REF] Hazan | Online learning with prior knowledge[END_REF]. For any reference class of Lipschitz policies, they proved a O T (d+1)/(d+2) upper bound1 on the regret for any context space of metric dimension d, where the O notation hides logarithmic factors in T . In the same work, they also proved a Ω T (d-1)/d lower bound. The gap between the upper and lower bound was closed by [START_REF] Rakhlin | Online nonparametric regression with general loss functions[END_REF] for arbitrary Lipschitz (not necessarily convex) losses, showing that T (d-1)/d is indeed the minimax rate for full information. Yet, since their approach is nonconstructive, they did not give an explicit algorithm achieving this bound.

As noted elsewhere -see, e.g., (Slivkins, 2014)-the approach of [START_REF] Hazan | Online learning with prior knowledge[END_REF] can be also adapted to prove a O T (d+p+1)/(d+p+2) upper bound on the regret against any class of Lipschitz policies in the bandit information setting with Lipschitz losses, where p is the metric dimension of the action space. The lower bound Ω T (p+1)/(p+2) proven for d = 0 (Bubeck et al., 2011a;[START_REF] Kleinberg | Multi-armed bandits in metric spaces[END_REF] rules out the possibility of improving the dependence on p in the upper bound.

Our contributions. In the full information model, we show the first explicit algorithm achieving the minimax regret rate O T (d-1)/d for Lipschitz policies and Lipschitz losses (excluding logarithmic factors in T and polynomial factors in the metric dimension of the action space). When the context space is [0, 1] d , our algorithm can be implemented efficiently (i.e., with a running time polynomial in T ).

Motivated by a problem in online advertising where the action space is the [0, 1] interval, we also study a "one-sided" full information model in which the loss of each action greater than or equal to the chosen action is available to the learner after each round. For this feedback model, which lies between full and bandit information, we prove a regret bound for Lipschitz policies and Lipschitz losses of order O T d/(d+1) , which is larger than the minimax regret for full information but smaller than the upper bound for bandit information when p = 1. For the special case when the context space is [0, 1] d , we use a specialized approach offering the double advantage of an improved O T (d-1/3)/(d+2/3) regret bound which is also attained by a time-efficient algorithm.

We then study a concrete application for minimizing the seller's regret in contextual secondprice auctions with reserve price, a setting where the loss function is not Lipschitz but only semi-Lipschitz. When the feedback after each auction is the seller's revenue together with the highest bid for the current auction, we prove a O T (d+1)/(d+2) regret bound against Lipschitz policies (in this setting, a policy maps contexts to reserve prices for the seller). As a by-product, we show the first O √ T regret bound on the seller's revenue in context-free second-price auctions under the same feedback model as above. Table 1 summarizes our results.

f : [0, 1] d → [0, 1] with d 2.
All upper bounds are constructive (i.e., achieved by explict algorithms). The only matching lower bound is the one for full information feedback due to [START_REF] Hazan | Online learning with prior knowledge[END_REF].

In order to prove our results, we approximate the action space using a finite covering (finite coverability is a necessary condition for our results to hold). This allows us to use the many existing algorithms for experts (full information feedback) and bandits when the action space is finite, such as Hedge [START_REF] Freund | A decision-theoretic generalization of on-line learning and an application to boosting[END_REF] and Exp3/Exp4 [START_REF] Auer | The nonstochastic multiarmed bandit problem[END_REF]. The simplest of our algorithms, adapted from [START_REF] Hazan | Online learning with prior knowledge[END_REF], incrementally covers the context space with balls of fixed radius. Each ball hosts an instance of an online learning algorithm which predicts in all rounds when the context falls into the ball. New balls are adaptively created when new contexts are observed which fall outside the existing balls (see Algorithm 1 for an example). We use this simple construction to prove the regret bound for contextual second-price auctions, a setting where losses are not Lipschitz. In order to exploit the additional structure provided by Lipschitz losses, we resort to more sophisticated constructions based on chaining [START_REF] Richard | The sizes of compact subsets of Hilbert space and continuity of Gaussian processes[END_REF]. In particular, inspired by previous works in this area (especially the work of [START_REF] Gaillard | A chaining algorithm for online nonparametric regression[END_REF], we design a chaining-inspired algorithm applied to a hierarchical covering of the policy space. Despite we are not the first ones to use chaining algorithmically in online learning, our idea of constructing a hierarchy of online learners, where each node uses its children as experts, is novel in this context as far as we know. Finally, the time-efficient algorithm achieving the improved regret bound is derived from a different (and more involved) chaining algorithm based on wavelet-like approximation techniques.

Setting and main definitions. We assume the context space X is a metric space (X , ρ X ) of finite metric dimension d and the action space Y is a metric space (Y, ρ Y ) of finite metric dimension p.

Hence, there exist C X , C Y > 0 such that, for all 0 < ε 1, X and Y can be covered, respectively, with at most C X ε -d and at most C Y ε -p balls of radius ε. For any 0 < ε 1, we use Y ε to denote any ε-covering of Y of size K ε C Y ε -p . Finally, we assume that Y has diameter bounded by 1 with respect to metric ρ Y .

We consider the following online learning protocol with oblivious adversary and loss functions

t : Y → [0, 1].
Given an unknown sequence (x 1 , 1 ), (x 2 , 2 ), . . . of contexts x t ∈ X and loss functions t : Y → [0, 1], for every round t = 1, 2, . . . :

1. The environment reveals context x t ∈ X ; 2. The learner selects an action y t ∈ Y and incurs loss t y t ; 3. The learner obtains feedback from the environment. Loss functions t satisfy the 1-Lipschitz2 condition t (y)t (y ) ρ Y (y, y ) for all y, y ∈ Y. However, we occasionally consider losses satisfying a weaker semi-Lipschitz condition.

We study three different types of feedback: bandit feedback (the learner only observes the loss t ( y t ) of the selected action y t ), full information feedback (the learner can compute t (y) for any y ∈ Y), and one-sided full information feedback (Y ≡ [0, 1], and the learner can compute t (y) if and only if y y t ). Given a reference class F ⊆ Y X of policies, the learner's goal is to minimize the regret against the best policy in the class,

Reg T (F) E T t=1 t y t -inf f ∈F T t=1 t f (x t ) ,
where the expectation is with respect to the learner's internal randomization. We derive regret bounds for the competitor class F made up of all bounded functions f : X → Y that are 1-Lipschitz3 w.r.t. ρ X and ρ Y . Namely, ρ Y f (x), f (x ) ρ X (x, x ) for all f ∈ F and all x, x ∈ X . We occasionally use the dot product notation p t • t to indicate the expectation of t according to law p t . Finally, the set of all probability distributions over a finite set of K elements is denoted by ∆(K).

Organization of the paper. The rest of the paper is organized as follows. In Section 2, we give an overview of the related literature. Then, starting from the subsequent section, our results are presented in the order dictated by the amount of feedback available to the learner, from bandit feedback (Section 3) to one-sided full information feedback (Section 4) to full information feedback (Section 5).

Related Work

Contextual online learning generalizes online convex optimization [START_REF] Hazan | Introduction to online convex optimization[END_REF] to nonconvex losses, nonparametric policies, and partial feedback. Papers about nonparametric online learning in full information include (Vovk, 2007;[START_REF] Gaillard | A chaining algorithm for online nonparametric regression[END_REF] for the square loss, and [START_REF] Hazan | Online learning with prior knowledge[END_REF][START_REF] Rakhlin | Online nonparametric regression with general loss functions[END_REF] for general convex losses. In the bandit feedback model, earlier work on context-free bandits on metric spaces includes [START_REF] Kleinberg | Nearly tight bounds for the continuum-armed bandit problem[END_REF][START_REF] Kleinberg | Multi-armed bandits in metric spaces[END_REF]. The paper [START_REF] Auer | The nonstochastic multiarmed bandit problem[END_REF] introduces the Exp4 algorithm for nonstochastic contextual bandits when both the action space and the policy space are finite, and policies are maps from contexts to distributions over actions. Moreover, rather than observing the current context, the learner sees the output of each policy for that context. In the contextual bandit model of [START_REF] Maillard | Adaptive bandits: Towards the best history-dependent strategy[END_REF], context space and action space are finite, and the learner observes the current context while competing against the best policy among all functions mapping contexts to actions. Finally, a nonparametric bandit setting related to ours was studied by Slivkins (2014). We refer the reader to the discussion after Theorem 1 for connections with our results.

Chaining [START_REF] Richard | The sizes of compact subsets of Hilbert space and continuity of Gaussian processes[END_REF] is a powerful technique to obtain tail bounds on the suprema of stochastic processes. In nonparametric online learning with full information feedback, chaining was used constructively by [START_REF] Cesa | On prediction of individual sequences[END_REF] to design an algorithm for linear losses, and nonconstructively by [START_REF] Rakhlin | Online nonparametric regression with general loss functions[END_REF] to derive minimax rates for Lipschitz losses. Other notable examples of chaining are the stochastic bandit algorithms of [START_REF] Contal | Optimization for gaussian processes via chaining[END_REF] and [START_REF] Contal | Stochastic process bandits: Upper confidence bounds algorithms via generic chaining[END_REF]. The constructive algorithmic chaining technique developed in this work is inspired by the nonparametric analysis of the full information setting of [START_REF] Gaillard | A chaining algorithm for online nonparametric regression[END_REF]. However, their multi-variable EG algorithm heavily relies on convexity of losses and requires access to loss gradients. In order to cope with nonconvex losses and lack of gradient information, we develop a novel chaining approach based on a tree of hierarchical coverings of the policy class, where each internal tree node hosts a bandit algorithm.

In our nonstochastic online setting, chaining yields improved rates when the regret is decomposed into a sum of local regrets, each one scaling with the range of the local losses. However, deriving regret bounds that scale with the effective range of the losses is not always possible, as shown by [START_REF] Gerchinovitz | Refined lower bounds for adversarial bandits[END_REF] in the nonstochastic K-armed bandit setting. This result suggests that chaining might not be useful in online nonparametric learning when the feedback is bandit. However, as we show in this paper, algorithmic chaining does help improving the regret when the feedback is one-sided full information or full information. In full information, chainingbased algorithms deliver regret bounds that match (up to log factors) the nonconstructive bounds of [START_REF] Rakhlin | Online nonparametric regression with general loss functions[END_REF].

In a different but interesting research thread on contextual bandits, the learner is confronted with the best within a finite (but large) class of policies over finitely-many actions, and is assumed to have access to this policy class through an optimization oracle for the offline full information problem. Relevant references include [START_REF] Agarwal | Taming the monster: A fast and simple algorithm for contextual bandits[END_REF][START_REF] Rakhlin | Bistro: an efficient relaxation-based method for contextual bandits[END_REF]Syrgkanis et al., 2016). The main concern is to devise (oracle-based) algorithms with small regret and requiring as few calls to the optimization oracle as possible.

Warmup: Nonparametric Bandits

As a simple warmup exercise, we prove a known result -see e.g., (Slivkins, 2014). Namely, a regret bound for contextual bandits with Lipschitz policies and Lipschitz losses. ContextualExp3 (Algorithm 1) is a bandit version of the algorithm by [START_REF] Hazan | Online learning with prior knowledge[END_REF] and maintains a set of balls of fixed radius ε in the context space, where each ball hosts an instance of the Exp3 algorithm of [START_REF] Auer | The nonstochastic multiarmed bandit problem[END_REF]. 4 At each round t, if a new incoming context x t ∈ X is not contained in any existing ball, then a new ball centered at x t is created, and a fresh instance of Exp3 is allocated to handle x t . Otherwise, the Exp3 instance associated with the closest context so far w.r.t. ρ X is used to handle x t . Each allocated Exp3 instance operates on the discretized action space Y ε whose size K ε is at most C Y ε -p . For completeness, the proof of the following theorem is provided in Algorithm 1: ContextualExp3 (for bandit feedback) A lower bound matching up to log factors the upper bound of Theorem 1 is contained in (Slivkins, 2014) -see also [START_REF] Lu | Contextual multi-armed bandits[END_REF] for earlier results in the same setting. However, our setting and his are subtly different: the adversary of Slivkins (2014) uses more general Lipschitz losses which, translated into our context, imply that the Lipschitz assumption is required to hold only for the composite function t (f (•)), rather than the two functions t and f separately. Hence, being the adversary less constrained (and the comparison class wider), the lower bound contained in (Slivkins, 2014) does not seem to apply to our setting.

Input: Ball radius ε > 0, ε-covering Y ε of Y such that |Y ε | ≤ C Y ε -p . for t =
While we are unaware of a lower bound matching the upper bound in Theorem 1 when F is the class of (global) Lipschitz functions and d 1, in the noncontextual case (d = 0), the lower bound Ω T (p+1)/(p+2) proven by Bubeck et al. (2011a); [START_REF] Kleinberg | Multi-armed bandits in metric spaces[END_REF] shows that improvements on the dependence on p are generally impossible. Yet, the dependence on p in the bound of Theorem 1 can be greatly improved in the special case when the Lipschitz losses are also convex. Assume Y is a convex and compact subset of R p . Then we use the same approach as in Theorem 1, where the Exp3 algorithm hosted at each ball is replaced by an instance of the algorithm 4. Instead of Exp3 we could use INF [START_REF] Audibert | Regret bounds and minimax policies under partial monitoring[END_REF], which enjoys a minimax optimal regret bound up to constant factors. This would avoid a polylog factor in T in the bound. Since we do not optimize for polylog factors anyway, we opted for the better known algorithm. 5. Here and throughout, T is assumed to be large enough so as to ensure ε 1.

by [START_REF] Bubeck | Kernel-based methods for bandit convex optimization[END_REF], run on the non-discretized action space Y. The regret of the algorithm that replaces Exp3 is bounded by poly(p, ln T )

√

T . This immediately gives the following corollary.

Corollary 2 Fix any any sequence (x 1 , 1 ), (x 2 , 2 ), . . . of contexts x t ∈ X and convex loss func-

tions t : Y → [0, 1],
where Y is a convex and compact subset of R p . Then there exists an algorithm for the bandit feedback model whose regret with respect to the set F of 1-Lipschitz functions satisfies Reg T (F) poly(p, ln T )T (d+1)/(d+2) , where poly is a polynomial function of its arguments.

One-Sided Full Information Feedback

In this section we show that better nonparametric rates can be achieved in the one-sided full information setting, where the feedback is larger than the standard bandit feedback but smaller than the full information feedback. More precisely, we consider the same setting as in Section 3 in the special case when the action space Y is [0, 1]. We further assume that, after each play y t ∈ Y, the learner can compute the loss t (y) of any number of actions y y t . This in contrast to observing only t y t , as in the standard bandit setting. We start with an important special case: maximizing the seller's revenue in a sequence of repeated second-price auctions. In Section 4.2, we use the chaining technique to design a general algorithm for arbitrary Lipschitz losses in the one-sided full information model. An efficient variant of this algorithm is obtained using a more involved construction in Section 4.3.

Nonparametric second-price auctions

In online advertising, publishers sell their online ad space to advertisers through second-price auctions managed by ad exchanges. For each impression (ad display) created on the publisher's website, the ad exchange runs an auction on the fly. Empirical evidence [START_REF] Ostrovsky | Reserve prices in Internet advertising auctions: a field experiment[END_REF] shows that an informed choice of the seller's reserve price, disqualifying any bid below it, can indeed have a significant impact on the revenue of the seller. Regret minimization in second-price auctions was studied by [START_REF] Cesa-Bianchi | Regret minimization for reserve prices in second-price auctions[END_REF] in a non-contextual setting. They showed that, when buyers draw their bids i.i.d. from the same unknown distribution on [0, 1], there exists an efficient strategy for setting reserve prices such that the seller's regret is bounded by O √ T with high probability with respect to the bid distribution. Here we extend those results to a nonstochastic and nonparametric contextual setting with nonstochastic bids, and prove a regret bound of order T (d+1)/(d+2) where d is the context space dimension. This improves on the bound T (d+2)/(d+3) of Theorem 1 when p = 1. As a byproduct, in Theorem 3 (Appendix C) we prove the first O √ T regret bound for the seller in nonstochastic and noncontextual second-price auctions. Unlike [START_REF] Cesa-Bianchi | Regret minimization for reserve prices in second-price auctions[END_REF], where the feedback after each auction was "strictly bandit" (i.e., just the seller's revenue), here we assume the seller is also observing the highest bid together with the revenue. This richer feedback, which is key to proving our results, is made available by some ad exchanges such as AppNexus.

The seller's revenue in a second-price auction is computed as follows: if the reserve price y is not larger than the second-highest bid b(2), then the item is sold to the highest bidder and the seller's revenue is b(2). If y is between b(2) and the highest bid b(1), then the item is sold to the highest bidder but the seller's revenue is the reserve price. Finally, if y is bigger than b(1), then the item is not sold and the seller's revenue is zero. Formally, the seller's revenue is g y, b(1), b(2) = max y, b(2) I y≤b(1) . Note that the revenue only depends on the reserve price y and on the two highest bids b(1) ≥ b(2), which -by assumption-belong all to the unit interval [0, 1].

In the online contextual version of the problem, unknown sequences of contexts x 1 , x 2 , . . . ∈ X and bids are fixed beforehand (in the case of online advertising, the context could be public information about the targeted customers). At the beginning of each auction t = 1, 2, . . . , the seller observes context x t and computes a reserve price y t ∈ [0, 1]. Then, bids b t (1), b t (2) are collected by the auctioneer, and the seller (which is not the same as the auctioneer) observes his revenue g t y t = g y t , b t (1), b t (2) , together with the highest bid b t (1). Crucially, knowing g t ( y t ) and b t (1) allows to compute g t (y) for all y y t . For technical reasons, we use losses t y t = 1 -g t y t instead of revenues, see Figure 1 for a pictorial representation. Remarkably, the loss functions t are not Lipschitz and not even continuous, and so this problem falls outside the scope of standard results for contextual bandits. Instead, the losses only satisfy the semi-Lipschitz property t (y + δ) ≥ t (y) -δ for all 0 y y + δ 1. We now state a bound on the regret Reg T (F) with respect to any class F of Lipschitz functions f : X → [0, 1]. The algorithm that achieves this bound is ContextualRTB (where RTB stands for Real Time Bidding -see Algorithm 3 in Appendix C), a variant of ContextualExp3 (Algorithm 1), where each ball hosts an instance of Exp3-RTB, instead of Exp3. The proof is given in Appendix D.

0 0.2 0.4 0.6 0.8 1 0 0.2 0.4 0.6 0.8 1 b t (2) b t (1) 1 -b t (2) 1 -b t (1)
Theorem 3 Fix any sequence of contexts x t ∈ X and bid pairs 0

b t (2) b t (1) 1 for t 1. If ContextualRTB is run with parameter ε = T -1 d+2 and Exp3-RTB is tuned with parameter γ = ε, then the regret with respect to any class of 1-Lipschitz functions f : X → [0, 1] satisfies Reg T (F) = O T d+1 d+2
, where d is the dimension of X and the O notation hides constants and ln T factors.

ContextualRTB and ContextualExp3 of Section 3 can be modified so to avoid knowing the horizon T and so that the dimension d of the context space is replaced in the bound by the (unknown, and possibly much smaller) dimension of the set of contexts actually occurring in the sequence chosen by the adversary. This modification involves using a time-varying radius ε and a doubling trick to check when the current guess for the dimension is violated by the current number of balls.

The omitted proof of this statement goes along the lines of the proof in [START_REF] De | The ABACOC algorithm: A novel approach for nonparametric classification of data streams[END_REF], Theorem 1).

Chaining the bandits

We now show that whenever the richer feedback structure -i.e., the learner can compute the loss t (y) of any number of actions y y t -is combined with Lipschitz losses (rather than just semi-Lipschitz), then an improved regret bound T d/(d+1) can be derived. The key technical idea enabling this improvement is the application of the chaining technique to a hierarchical covering of the policy space (as opposed to the flat covering of the context space used in both Section 3 and Section 4.1). We start with a computationally inefficient algorithm that works for arbitrary policy classes F (not only Lipschitz) and is easier to understand. In Section 4.3 we derive an efficient variant for F that are Lipschitz. In this case we obtain even better regret bounds via a penalization trick.

A way of understanding the chaining approach is to view the hierarchical covering of the policy class F as a tree whose nodes are functions in F, and where the nodes at each depth m define a (2 -m )-covering of F. The tree represents any function f * ∈ F (e.g., the function with the smallest cumulative loss) by a unique path (or chain)

f 0 → f 1 → • • • → f M → f * ,
where f 0 is the root and f M is the function best approximating f * in the cover at the largest available depth M . By relying on this representation, we control the regret against any function in F by running an instance of an online bandit algorithm A on each node of the tree. The instance A f at node f uses the predictions of the instances running on the nodes that are children of f as expert advice. The action drawn by instance A 0 running on the root node is the output of the tree. For any given sequence of pairs (x t , t ) of contexts and losses, the regret against f * with path

f 0 → f 1 → • • • → f M → f * can
then be written (ignoring some constants) as

T t=1 E t A 0 (x t ) -t f * (x t ) M -1 m=0 E T t=1 t A m (x t ) -t A m+1 (x t ) + 2 -M T
where A m is the instance running on node f m for m = 0, . . . , M -1 and A M ≡ f M . The last term 2 -M T accounts for the cost of approximating f * with the closest function f M in a (2 -M )cover of F under suitable Lipschitz assumptions. The outer sum in the right-hand side of the above display can be viewed as a sum of M regrets, where the m-th term in the sum is the regret of A m against the instances running on the children of the node hosting A m . Since we face an expert learning problem in a partial information setting, the Exp4 algorithm of Auer et al. ( 2002) is a natural choice for the learner A. However, a first issue to consider is that we are using A 0 to draw actions in the bandit problem, and so the other Exp4 instances receive loss estimates that are based on the distribution used by A 0 rather than being based on their own distributions. A second issue is that our regret decomposition crucially relies on the fact that each instance A m only competes (in the sense of regret) against functions f at the leaves of the subtree rooted at the node where A m runs. By construction, these functions at the leaves are roughly (2 -m )-close to each other and -by Lipschitzness-so are their losses. As a consequence, the regret of A m should scale with the true loss range 2 -m . Via an appropriate modification of the original Exp4 algorithm, we manage to address both these issues. In particular, in order to make the regret dependent on the loss range, we heavily rely on the one-sided full information model assumed in this section. Finally, the hierarchical covering requires that losses be Lipschitz, rather than just semi-Lipschitz as in the application of Subsection 4.1, which uses a simpler flat covering.

Fix any class F of functions f :

X → [0, 1]. Let us introduce the sup norm f -g ∞ = sup x∈X f (x) -g(x)
.

(1)

We denote by N ∞ F, ε the cardinality of the smallest ε-cover of F w.r.t. the sup norm. Throughout this section, our only assumption on F is that N ∞ F, ε < +∞ for all ε > 0 (this property is known as total boundedness). In Section 4.3 we will focus on the special case

F = f : [0, 1] d → [0, 1] : f is 1-Lipschitz to derive
an efficient version of our algorithm.

We now define a tree T F of depth M , whose nodes are labeled by functions in the class F, so that functions corresponding to nodes with a close common ancestor are close to one another according to the sup norm (1). For all m = 0, 1, . . . , M , let F m be a (2 -m )-covering of F in sup norm with minimal cardinality N m = N ∞ (F, 2 -m ). Since the diameter of (F, • ∞ ) is bounded by 1, we have N 0 = 1 and F 0 = {f 0 } for some f 0 ∈ F. For each m = 0, 1, . . . , M and for every

f v ∈ F m we have a node v in T F at depth m. The parent of a node w at depth m + 1 is some node v at depth m such that v ∈ arg min v : depth(v )=m f v -f w ∞ (ties broken arbitrarily)
and we say that w is a child of v. Let L be the set of all the leaves of T F , L v be the set of all the leaves under v ∈ T F (i.e., the leaves of the subtree rooted at v), and C v be the set of children of v ∈ T F .

Exp4 Exp4 Exp4

Leaves

under v = L v Level m 2 -m covering of F Level m + 1 2 -(m+1) covering Level M (=leaves L) 2 -M covering
Figure 2: Hierarchical covering of the function space (used in Algorithm 2).

Our new bandit algorithm HierExp4 (Algorithm 2 below) is a hierarchical composition of instances of Exp4 on the tree T F constructed above (see Figure 2). Let K = 2 M and K = {y 1 , . . . , y K }, where

y k = 2 -M (k -1) for k = 1, . . . , 2 M , be our discretization of the action space Y = [0, 1]. At every round t, after observing context x t ∈ X , each leaf v ∈ L recommends the best approximation of f v (x t ) in K, i t (v) ∈ arg min i=1,...,K y i -f v (x t )
. Therefore, the leaves v ∈ L correspond to deterministic strategies t → i t (v), and we will find it convenient to view a set of leaves L as the set of actions played by those leaves at time t. Each internal node v ∈ T F \ L runs an instance of Exp4 using the children of v as experts. More precisely, we use a variant of Exp4 (see Algorithm 4 in Appendix E) which adapts to the effective range of the losses. Let Exp4 v be the instance of the Exp4 variant run on node v. At each time t, this instance updates a distribution q t (v, •) ∈ ∆(|C v |) over experts in C v and a distribution p t (v, •) ∈ ∆(K) over actions in K defined by p t (v, i) = w∈Cv q t (v, w)p t (w, i).

Let v 0 be the root of T F . The prediction of HierExp4 at time t is y t = y It ∈ K, where I t is drawn according to a mixture of p t (v 0 , •) and a unit mass on the minimal action y 1 ∈ K.

For 2) has to be explicitly computed only for those actions i such that i I t and i ∈ K t (v). This is because t (v, i) is needed for the computation of t (v, w) only when p t (w, i) > 0. Therefore, whenever t (v, i) has to be computed for some i, then I t i max K t (v) = j t (v), so that t y jt(v) is observed and t (v, i) is well defined.

each v ∈ T F \ L, let K t (v) = {i : (∃w ∈ C v ) p t (w, i) > 0} and j t (v) = max K t (v). Note that t (v, i) in (
Algorithm 2: HierExp4 (for one-sided full information feedback) Input : Tree T F with root v 0 and leaves L, exploration parameter γ ∈ (0, 1), learning rate sequences

η 1 (v) η 2 (v) • • • > 0 for v ∈ T F \ L. Initialization: Set q 1 (v, •) to the uniform distribution in ∆(|C v |) for every v ∈ T F \ L. for t = 1, 2, . . . do 1. Get context x t ∈ X ; 2. Set p t (v, i) = I i=it(v) for all i ∈ K and for all v ∈ L; 3. Set p t (v, i) = q t (v, •) • p t (•, i
) for all i ∈ K and for all v ∈ T F \ L; 4. Draw I t ∼ p * t and play y t = y It , where p * t (i) = (1 -γ)p t (v 0 , i) + γI i=1 for all i ∈ K; 5. Observe t (y) for all y y It ; 6. For every v ∈ T F \ L and for every i

∈ K t (v) compute t (v, i) = t (y i ) -t y jt(v) i k=1 p * t (k) I It i , (2)
where K t (v) = {i : (∃w ∈ C v ) p t (w, i) > 0} and j t (v) = max K t (v). 7. For each v ∈ T F \ L and for each w ∈ C v compute the expert loss t (v, w) = p t (w, •) • t (v, •) and perform the update

q t+1 (v, w) = exp -η t+1 (v) t s=1 s (v, w) w ∈Cv exp -η t+1 (v) t s=1 s (v, w ) (3)
end Next, we show that the regret of HierExp4 is at most of the order of T d/(d+1) , which improves on the rate T (d+1)/(d+2) obtained in Section 4.1 without using chaining. The required proofs are contained in Appendix F.

Theorem 4 Fix any class F of functions f : X → [0, 1] and any sequence (x 1 , 1 ), (x 2 , 2 ), . . . of contexts x t ∈ X and 1-Lipschitz loss functions t : [0, 1] → [0, 1]. Assume the HierExp4 (Algorithm 2) is run with one-sided full information feedback using tree T F of depth M = ln 2 (1/γ) . Moreover, the learning rate η t (v) used at each node v at depth m = 0, . . . , M -1 is given by (11) in Appendix E, where V t-1 (v) is the cumulative variance of s (v, •) according to q s (v, •) up to time s = t -1. Then for all T 1 the regret satisfies

Reg T (F) 5γT + 2 7 1/2 γ/2 T γ ln N ∞ (F, ε) + 1 γ ln N ∞ (F, ε) + 1 dε .
In particular, if X ≡ [0, 1] d is endowed with the sup norm ρ X (x, x ) = x -x ∞ , then the set F of all 1-Lipschitz functions from X to [0, 1] satisfies ln N ∞ (F, ε) ε -d . Theorem 4 thus entails the following corollary.

Corollary 5 Under the assumptions of Theorem 4, if F is the set of all 1-Lipschitz functions f : [0, 1] d → [0, 1], then the regret of HierExp4 satisfies

Reg T (F) =    O T 2/3 if d = 1 O T 2/3 (ln T ) 2/3 if d = 2 O T d/(d+1) if d 3
where the last inequality is obtained by optimizing the choice of γ for the different choices of d.

Efficient chaining

Though very general, HierExp4 (Algorithm 2) may be very inefficient. For example, when F is the set of all 1-Lipschitz functions from [0, 1] d to [0, 1], a direct implementation of HierExp4 would require exp poly(T ) weight updates at every round. In this section we tackle the special case when F is the class of all 1-Lipschitz functions f : [0, 1] d → [0, 1] w.r.t. the sup norm on [0, 1] d (for simplicity). We construct an ad-hoc hierarchical covering of F and define a variant of HierExp4 whose running time at every round is polynomial in T . We rely on a well-known wavelet-like approximation technique which was used earlier -see, e.g., [START_REF] Gaillard | A chaining algorithm for online nonparametric regression[END_REF]-for online nonparametric regression with full information feedback. However, we replace their multi-variable Exponentiated Gradient algorithm, which requires convex losses and gradient information, with a more involved chaining algorithm that still enjoys a polynomial running time. The definitions of our covering tree T F and of our algorithm HierExp4 , as well as the proof of the following regret bound, can be found in Appendix G. The exact value of c T (depending at most logarithmically on T ) is also provided there.

Theorem 6 Let F be the set of all 1-Lipschitz functions f :

[0, 1] d → [0, 1] w.r.t. the sup norm on [0, 1] d . Consider T 3 and any sequence (x 1 , 1 ), . . . , (x T , T ) of contexts x t ∈ [0, 1] d and 1-Lipschitz loss functions t : [0, 1] → [0, 1]. Assume HierExp4 (Algorithm 5 in Appendix G) is run with one-sided full information feedback using tree T F of depth M = ln 2 (1/γ) , exploration parameter γ = T -1/2 (ln T ) -1 I d=1 + T -1/(d+2/3) I d>1 , learning rate η m = c T 2 m( d 4 +1) γ 1 2 T -1 4
, and penalization α m = M j=m+1 2 4-2j η j for m = 0, . . . , M -1. Then the regret satisfies

Reg T (F) = O √ T ln T if d = 1, O T d-1/3 d+2/3 (ln T ) 3/2 if d 2.
Moreover, the running time at every round is O T a with a = (1 + ln 2 3)/(d + 2/3).

The above result improves on Corollary 5 in two ways. First, as we said, the running time is now polynomial in T , contrary to what could be obtained via a direct implementation of HierExp4. Second, when d 2, the regret bound is of order T (d-1/3)/(d+2/3) , improving on the rate T d/(d+1)

from Corollary 5. Remarkably, Theorem 6 also yields a regret of O( √ T ) for nonparametric bandits with one-sided full information feedback in dimension d = 1. The improvement on the rates compared to HierExp4 is possible because we use a variant of Exp4 with penalized loss estimates. This allows for a careful hierarchical control of the variance terms inspired by our analysis of Exp3-RTB in Appendix C.

Note that the time complexity decreases as the dimension d increases. Indeed, when d increases the regret gets worse but, at the same time, the size of the discretized action space and the number of layers in our wavelet-like approximation can be both set to smaller values.

A Tight Bound for Full Information through an Explicit Algorithm

In this section we apply the machinery developed in Section 4.2 to the full information setting, where after each round t the learner can compute the loss t (y) of any number of actions y ∈ Y. We obtain the first explicit algorithm achieving, up to logarithmic factors, the minimax regret rate T (d-1)/d for all classes of Lipschitz functions, where d is the dimension of the context space. This achieves the same upper bound as the one proven by [START_REF] Rakhlin | Online nonparametric regression with general loss functions[END_REF] in a nonconstructive manner, and matches the lower bound of [START_REF] Hazan | Online learning with prior knowledge[END_REF]. Our approach generalizes the approach of [START_REF] Gaillard | A chaining algorithm for online nonparametric regression[END_REF] to nonconvex Lipschitz losses. We consider a full information variant of HierExp4 (Algorithm 2, Section 4.2), where -using the same notation as in Section 4.2-the Exp4 instances running on the nodes of the tree T F are replaced by instances of Hedge -e.g., [START_REF] Bubeck | Regret analysis of stochastic and nonstochastic multiarmed bandit problems[END_REF]. Note that, due to the full information assumption, the new algorithm, called HierHedge, observes losses at all leaves v ∈ L. As a consequence, no exploration is needed and so we can set γ = 0. For the same reason, the estimated loss vectors defined in (2) can be replaced with the true loss vectors, t . See Algorithm 6 in Appendix H for a definition of HierHedge. The same appendix also contains a proof of the next result.

Theorem 7 Fix any class F of functions f : X → Y and any sequence (x 1 , 1 ), (x 2 , 2 ), . . . of contexts x t ∈ X and 1-Lipschitz loss functions t : Y → [0, 1]. Assume HierHedge (Algorithm 6 in Appendix H) is run with full information feedback on the tree T F of depth M = ln 2 (1/ε) with action set Y ε for ε > 0. Moreover, the learning rate η t (v) used at each node v at depth m = 0, . . . , M -1 is given by (11) in Appendix E, with E = 2 -m+3 , N = |C v |, and V t-1 being the cumulative variance of s according to q s (v, •) up to time s = t -1. Then for all T 1 the regret satisfies

Reg T (F) 5εT + 2 7 1/2 ε/2 2 T ln N ∞ (F, x) + ln N ∞ (F, x) dx .
In particular, if d 3 and F is the set of 1-Lipschitz functions f : [0, 1] d → [0, 1] p , where [0, 1] d and [0, 1] p are endowed with their sup norms, the choice ε = (p/T ) 1/d yields Reg T (F) = O T (d-1)/d , while for 1 d 2 the regret is of order √ pT , ignoring logarithmic factors.

When using the sup norms, the dimension p of the action space only appears as a multiplicative factor p 1/d in the regret bound for Lipschitz functions. Note also that an efficient version of HierHedge for Lipschitz functions can be derived along the same lines as the construction in Section 4.3.

Appendix A. A Useful Lemma

The following is a standard result in the analysis of Hedge with variable learning rate -see, e.g., the analysis of (Bubeck and Cesa-Bianchi, 2012, Theorem 3.2). Recall that, when run on a loss sequence 1 , 2 , . . . Hedge computes distributions p 1 , p 2 , . . . where p 1 is uniform and p t (i) is proportional to exp -η t t-1 s=1 s (i) for all actions i. Lemma 8 The sequence p 1 , p 2 , . . . of probability distributions computed by Hedge when run on K actions with learning rates η 1 η 2 • • • > 0 and losses t (k) 0 satisfies

T t=1 K i=1 p t (i) t (i) -min k=1,...,K T t=1 t (k) ln K η T + 1 2 T t=1 η t K i=1 p t (i) t (i) 2 .

Appendix B. Proof of Theorem 1

Proof Let N t be the number of balls created by the ContextualExp algorithm after t rounds, B s be the s-th ball so created, being xs its center (x s is some past context), and T s be the subsequence of rounds t such that x t is handled by the s-th ball. Notice that N t and T s are deterministic quantities, since the x t 's are generated obliviously. Since f is 1-Lipschitz and t is also 1-Lipschitz, for all x t handled by B s , we can write t f (x t )t f (x s ) ≤ ε . Now fix any 1-Lipschitz policy f . For each s = 1, . . . , N T , there exists ȳs ∈ Y ε such that ρ Y ȳs , f (x s ) ≤ ε. Then we can write

E T t=1 t ( y t ) - T t=1 t f (x t ) (4) = N T s=1 t∈Ts E t ( y t ) -t f (x t ) = N T s=1 t∈Ts E t ( y t ) -t ȳs + t ȳs -t (f (x s )) + t (f (x s )) -t (f (x t )) ≤ N T s=1 t∈Ts E t ( y t ) -t ȳs + 2T ε . (5)
We now apply to each s = 1, . . . , N T the standard regret bound of Exp3 with learning rate η (e.g., [START_REF] Bubeck | Regret analysis of stochastic and nonstochastic multiarmed bandit problems[END_REF])) w.r.t. the best action ȳs . This yields

t∈Ts E t ( y t ) -t ȳs ln K ε η + η 2 |T s | K ε , implying N T s=1 t∈Ts E t ( y t ) -t ȳs N T ln K ε η + η 2 T K ε .
Combining with (5), setting η = 2N T ln Kε T Kε

, recalling that K ε C Y ε -p and observing that, by the way balls are constructed, N T can never exceed the size of the smallest ε/2-cover of X (that is,

N T C X (ε/2) -d ), we obtain Reg T (F) 2 T N T K ε ln K ε + 2 T ε = O T ε -(d+p) ln 1 ε + T ε . Setting ε = p+d 2 ln T T 1/2 2 p+d+2 gives Reg T (F) = O T p+d+1 p+d+2
as claimed.

Algorithm 3: Exp3-RTB (for one-sided full information feedback) Input : Exploration parameter γ > 0. Initialization: Set learning rate η = γ/2 and uniform distribution p 1 over {1, . . . , K} where K = 1/γ ; for t = 1, 2, . . . do 1. compute distribution q t (k) = (1 -γ)p t (k) + γI k=1 for k = 1, . . . , K; 2. draw I t ∼ q t and choose y t = y It = (I t -1)γ; 3. for each k = 1, . . . , K, compute the estimated loss

t (k) = t (y k ) k j=1 q t (j) I It k
4. for each k = 1, . . . , K, compute the new probability assignment

p t+1 (k) = exp -η t s=1 s (k) K j=1 exp -η t s=1 s (j)
.

end

Theorem 9 In the one-sided full information feedback, the Exp3-RTB algorithm tuned with γ > 0 satisfies

Reg T γT 2 + 1 4 ln e γ + 2 ln 1/γ γ .
In particular, γ = T -1/2 gives Reg T = O √ T .

Proof The proof follows the same lines as the regret analysis of Exp3 in [START_REF] Auer | The nonstochastic multiarmed bandit problem[END_REF]. The key change is a tighter control of the variance term allowed by the richer feedback. Pick any reserve price y k = (k -1)γ. We first control the regret associated with actions drawn from p t (the regret associated with q t will be studied as a direct consequence). More precisely, since the estimated losses t (j) are nonnegative, we can apply Lemma 8 to get

T t=1 p t • t - T t=1 t (k) η 2 T t=1 K j=1 p t (j) t (j) 2 + ln K η . ( 7
) Writing E t-1 [ • ]
for the expectation conditioned on I 1 , . . . , I t-1 , we note that E t-1 t (j) = t (y j ) and E t-1 p t (j) t (j) 2 = p t (j) t (y j ) 2 j i=1 q t (i)

q t (j) (1 -γ) j i=1 q t (i)
,

where we used the definition of q t and the fact that | t (y j )| 1 by assumption. Therefore, taking expectation on both sides of (7) entails, by the tower rule for expectations,

E T t=1 p t • t - T t=1 t (y k ) η 2(1 -γ) T t=1 E   K j=1 q t (j) j i=1 q t (i)   + ln K η .
Setting s t (j) j i=1 q t (i), we can upper bound the sum with an integral, K j=1 q t (j)

j i=1 q t (i) = 1 + K j=2 s t (j) -s t (j -1) s t (j) = 1 + K j=2 st(j) st(j-1) dx s t (j) 1 + K j=2 st(j) st(j-1) dx x = 1 + 1 qt(1) dx x 1 -ln q t (1) 1 + ln 1 γ ,
where we used q t (1) γ. Therefore, substituting into the previous bound, we get

E T t=1 p t • t - T t=1 t (y k ) ηT ln(e/γ) 2(1 -γ) + ln K η . ( 8
)
We now control the regret of the predictions y t = y It , where I t is drawn from q t = (1 -γ)p t + γδ 1 .

By the tower rule,

E T t=1 t ( y t ) - T t=1 t (y k ) = E T t=1 (1 -γ)p t • t + γ t (y 1 ) - T t=1 t (y k ) (1 -γ) E T t=1 p t • t - T t=1 t (y k ) + γT ηT ln(e/γ) 2 + ln K η + γT , (9)
where the last inequality is by (8).

To conclude the proof, we upper bound the regret against any fixed y ∈ [0, 1]. Since there exists k ∈ {1, . . . , K} such that y ∈ [y k , y k + γ], and since each t satisfies the semi-Lipschitz condition (6), we have t (y) t (y k ) -γ. This gives

min k=1,...,K E T t=1 t (y k ) min 0 y 1 T t=1 t (y) + γ T .
Replacing the last inequality into (9), and recalling that K = 1/γ and η = γ 2 , finally yields

Reg T γT 4 ln e γ + 2 ln 1/γ γ + 2γT .
Choosing γ ≈ T -1/2 concludes the proof.

Appendix D. Proof of Theorem 3

Proof The proof is very similar to that of Theorem 1. We only highlight the main differences. Let f ∈ F be any 1-Lipschitz function from X to [0, 1]. For all s = 1, . . . , N T , we define the constant approximation of f in the s-th ball by y min s = min t∈Ts f (x t ). Since f is 1-Lipschitz and the balls have radius ε, we have max t,t ∈Ts f (x t ) -f (x t ) ≤ 2ε. Hence, for all t ∈ T s , by the semi-Lipschitz property (6),

t f (x t ) ≥ t (y min s ) -2ε . (10) Therefore, T t=1 E[ t ( y t )] - T t=1 t f (x t ) = N T s=1 t∈Ts E[ t ( y t )] -t f (x t ) = N T s=1 t∈Ts E[ t ( y t )] -t (y min s ) Rs + N T s=1 t∈Ts t (y min s ) -t f (x t ) ≤ γT 2 + 1 4 ln e γ + 2N T ln 1/γ γ + 2εT .
Each term R s is the regret suffered by the s-th instance of Exp3-RTB against the constant value y min s , and so we bound it using Theorem 9 in Appendix C and then sum over s recalling that s T s = T . The other double sum is bounded by 2T ε using (10). We bound N T as in Theorem 1 obtaining

Reg T (F) γT 1 + ln 1 γ + ε -d γ ln 1 γ + εT . Finally, choosing ε = γ = T -1/(d+2) 1 gives Reg T (F) = O T d+1 d+2
concluding the proof.

Appendix E. Exp4 regret bound scaling with the range of the losses

In this section we revisit the Exp4 algorithm (Bubeck and Cesa-Bianchi, 2012, Figure 4.1) and prove a regret bound for the one-sided full information model that scales with the range of the losses. In view of the application to chaining, we formulate this result in a setting similar to [START_REF] Maillard | Adaptive bandits: Towards the best history-dependent strategy[END_REF]. Namely, when the action I t played at time t is not necessarily drawn from the distribution prescribed by Exp4. Exp4 (see Algorithm 4) operates in a bandit setting with K actions and N experts. We assume a total order 1 < • • • < K on the action set K = {1, . . . , K}. At each time step t = 1, 2, . . . the advice ξ t (j, •) of expert j is a probability distribution over the K actions. The learner combines the expert advice using convex coefficients q t ∈ ∆(N ). These coefficients are computed by Hedge based on the expert losses t (j) = ξ t (j, •) • t for j = 1, . . . , N , where t is a vector of suitably defined loss estimates. The distribution prescribed by Exp4 is p t = N j=1 q t (j)ξ t (j, •) ∈ ∆(K), but the learner's play at time t is I t ∼ p * t for some other distribution p * t ∈ ∆(K). The feedback at time t is the vector of losses t (i) for all i I t .

Algorithm 4: Exp4 with unspecified sampling distributions p * t (for one-sided full info feedback) Input : Learning rate sequence η 1 η 2 • • • > 0. Initialization: Set q 1 to the uniform distribution over {1, . . . , N }; for t = 1, 2, . . . do 1. get expert advice ξ t (1, •), . . . , ξ t (N, •) ∈ ∆(K); 2. compute distribution p * t over {1, . . . , K}; 3. draw I t ∼ p * t and observe t (i) for all i I t ; 4. compute loss estimates t (i) for i = 1, . . . , K; 5. compute expert losses t (j) = ξ t (j, •) • t for j = 1, . . . , N ; 6. compute the new probability assignment

q t+1 (j) = exp -η t+1 t s=1 s (j) N k=1 exp -η t+1 t s=1 s (k)
for each j = 1, . . . , N .

end

In this setting, the goal is to minimize the regret with respect to the performance of the best expert,

max j=1,...,N E T t=1 p t • t - T t=1 ξ t (j, •) • t
in expectation with respect to the random draw of I 1 , . . . , I T , where ξ t (j, •) • t is the expected loss of expert j at time t. In view of our chaining application, we defined the quantities ξ t (j, i) as random variables because the expert advice at time t might depend on the past realizations of I 1 , . . . , I t-1 . For all k ∈ K let

P * t (k) = k i=1 p * t (i) .
Also, let K t ≡ {k ∈ K : (∃j) ξ t (j, k) > 0} (in chaining, K t is typically small compared to K).

The next result shows that, when Exp4 is applied to arbitrary real-valued losses, there is a way of choosing the learning rate sequence so that the regret scales with a quantity smaller than the largest loss value. More specifically, the regret scales with a known bound E on the size of the effective range of the losses max

t=1,...,T max k,k ∈Kt t (k) -t (k ) E .
The rich feedback structure ( t (k), k I t ) is crucial to get our result, since it enables us to use t max K t in the definition of the loss estimates t (k) below. Indeed, as explained in Section 4.2, t (k) has to be explicitly computed only for those actions k such that I t k and ξ t (j, k) > 0 for some j, i.e., k ∈ K t . In this case, I t k max K t so that t max K t is observed.

Theorem 10 Let 1 < • • • < K be a total order on the action set K = {1, . . . , K}. Suppose Exp4 (Algorithm 4) is run with one-sided full information feedback on an arbitrary loss sequence 1 , 2 , . . . with loss estimates

t (k) = t (k) -t max K t P * t (k) I It k for k = 1, . . . , K
and adaptive learning rate

η t = min γ 2E , 2 √ 2 -1 (ln N ) (e -2) V t-1 for t 2 (11)
for some parameter E > 0 and where

V t-1 = t-1 s=1 N j=1 q s (j) s (j) -q s • s 2 is the cumulative variance of Hedge up to time t -1. If p * t (1) γ and max t=1,...,T max k,k ∈Kt t (k) -t (k ) E
almost surely for all t 1, then, for all T 1, max j=1,...,K

E T t=1 p t • t - T t=1 ξ t (j, •) • t 4E T ln N γ + E γ (4 ln N + 1) .
Note that the above regret bound does not depend on the number K of actions, but instead on a lower bound γ on the probability of observing the smallest action.

Proof From the definition of K t and because

P * t (k) p * t (1) γ, max i,j=1,...,N t (i) -t (j) = max i,j=1,...,N ξ t (i, •) • t -ξ t (j, •) • t max k,k ∈Kt t (k) -t (k ) 2E min k∈K P * t (k) 2E γ .
Since E = (2E)/γ is an upper bound on the size of the range of the losses t (j), we can use the bound of (Cesa-Bianchi et al., 2007, Theorem 5), which applies to Hedge run on arbitrary realvalued losses with the learning rate (11). This gives us

T t=1 q t • t min j=1,...,N T t=1 t (j) + 4 (ln N ) V T + 2 E ln N + E 2 . ( 12
) Note that q t • t = p t • t . Moreover, K t = max K t is measurable with respect to (I 1 , . . . , I t-1 ), implying E t-1 t (k) = t (k)-t (K t ).
Therefore, taking the expectation on both sides of ( 12) with respect to the random draw of I 1 , . . . , I T , and using Jensen together with

V T ≤ T t=1 N j=1 q t (j) • t (j) 2 , we get max j=1,...,N E T t=1 p t • t - T t=1 ξ t (j, •) • t 4 (ln N ) T t=1 E   N j=1 q t (j) ξ t (j, •) • t 2   + 4E γ ln N + E γ . (13)
The variance term inside the square root can be upper bounded as follows. Using Jensen again,

N j=1 q t (j) ξ t (j, •) • t 2 N j=1 q t (j) K k=1 ξ t (j, k) t (k) 2 = N j=1 q t (j) K k=1 ξ t (j, k) t (k) -t (K t ) P * t (k) 2 I It k E 2 γ N j=1 q t (j) K k=1 ξ t (j, k) P * t (k) I It k
where the last inequality is because t (k)t (K t ) E when ξ t (j, k) > 0 and because

P * t (k) p * t (1) γ. Therefore, recalling P * t (k) = P t-1 (I t k), E t-1   N j=1 q t (j) ξ t (j, k) • t 2   E 2 γ N j=1 q t (j) K k=1 ξ t (j, k) P * t (k) P t-1 (I t k) = E 2 γ .
Substituting the last bound in (13) concludes the proof.

Next we extend the previous result to penalized loss estimates, which is useful in Section 4.3 to control the variance terms all along the covering tree.

Theorem 11 Let 1 < • • • < K be a total order on the action set K = {1, . . . , K}. Let E, F > 0.

Consider any penalty pen t ∈ R K measurable with respect to (I 1 , . . . , I t-1 ) at time t. Suppose Exp4 (Algorithm 4) is run with one-sided full information feedback on an arbitrary loss sequence t ∈ R K , t 1, with loss estimates

t (k) = t (k) -t max K t + E P * t (k) I It k + pen t (k) + F for k = 1, . . . , K
and constant learning rate η > 0. If we have, for all t 1, almost surely,

max t=1,...,T max k,k ∈Kt t (k) -t (k ) E and max t=1,...,T max k∈Kt pen t (k) F , then, for all T 1, max j=1,...,K E T t=1 p t • t + pen t - T t=1 ξ t (j, •) • t + pen t ln N η + 4ηT F 2 + 4ηE 2 T t=1 E K k=1 p t (k) P * t (k)
.

Proof From the definition of K t and because E and F are upper bounds on the losses and penalties associated with actions in K t , min j=1,...,N t (j) = min j=1,...,N

ξ t (j, •) • t min k∈Kt t (k) 0 .
We can thus use the regret bound for Hedge with weight vectors q t , constant learning rate η, and nonnegative losses t (k) (see Lemma 8 in Appendix A):

T t=1 q t • t min j=1,...,N T t=1 t (j) + ln N η + η 2 T t=1 N j=1 q t (j) t (j) 2 . ( 14
)
Note that q t • t = p t • t . Moreover, K t = max K t and pen t are measurable with respect to (I 1 , . . . , I t-1 ), implying E t-1 t (k) = t (k)t (K t ) + E + pen t (k) + F . Therefore, taking the expectation on both sides of ( 14) with respect to the random draw of I 1 , . . . , I T , we get

max j=1,...,N E T t=1 p t • t + pen t - T t=1 ξ t (j, •) • t + pen t ln N η + η 2 T t=1 E   N j=1 q t (j) ξ t (j, •) • t 2   . ( 15
)
The variance term can be upper bounded as follows. Using Jensen's inequality,

N j=1 q t (j) ξ t (j, •) • t 2 N j=1 q t (j) K k=1 ξ t (j, k) t (k) 2 = K k=1 N j=1 q t (j)ξ t (j, k) t (k) -t (K t ) + E P * t (k) I It k + pen t (k) + F 2 8F 2 + 8E 2 K k=1 p t (k) P * t (k) 2 I It k ,
where the last inequality is because t (k)t (K t ) E and pen t (k) F when ξ t (j, k) > 0 and because (a

+ b + c + d) 2 4 a 2 + b 2 + c 2 + d 2 . Therefore, recalling P * t (k) = P t-1 (I t k), E t-1   N j=1 q t (j) ξ t (j, k) • t 2   8F 2 + 8E 2 K k=1 p t (k) P * t (k)
.

Substituting the last bound in (15) concludes the proof.

Note that when pen t ≡ 0 and p * t (1) γ almost surely for all t 1, Theorem 11 above used with η = (2E) -1 γ ln(N )/T yields a regret bound of 4E T ln(N )/γ, similarly to Theorem 10.

We use yet another corollary in Section 4.3. It follows directly from the choice of pen t (k) = -α/P * t (k) and F = α/γ in Theorem 11.

Corollary 12 Let 1 < • • • < K be a total order on the action set K = {1, . . . , K}. Let E, α, γ > 0 be three parameters. Suppose Exp4 (Algorithm 4) is run on an arbitrary loss sequence t ∈ R K , t 1, with loss estimates

t (k) = t (k) -t max K t + E P * t (k) I It k - α P * t (k) + α γ for k = 1, . . . ,
- T t=1 K k=1 ξ t (j, k) t (k) - α P * t (k) ln N η + 4ηT α 2 γ 2 .
Appendix F. Missing Proofs from Section 4.2

We prove Theorem 4 and Corollary 5. As we said in the main text, the key contribution of chaining is that it allows us to sum up local regret bounds scaling as the range of the local losses. This is possible because of the richer feedback structure induced by the total order on the actions. We first state a lemma indicating that the losses associated with neighboring nodes are indeed close to one another. Recall that M is the depth of T F .

Lemma 13 Let v ∈ T be any node at level m ∈ {0, 1, . . . , M -1}. Then all leaves w, w

∈ L v satisfy f w -f w ∞ 2 -m+2 . Therefore, t (y it(w) ) -t (y it(w ) ) 2 -m+3 for all t 1. Proof Consider a path v = v m → v m+1 → • • • → v M = w joining v to leaf w in the tree. For each k = m, . . . , M -1, since F k is a (2 -k )-covering of F in sup norm, we have f v k -f v k+1 ∞ 2 -k . Therefore, f v -f w ∞ = M -1 k=m (f v k -f v k+1 ) ∞ M -1 k=m f v k -f v k+1 ∞ M -1 k=m 2 -k 2 -m+1 .
Therefore, since w ∈ L v as well,

f w -f w ∞ = f v -f w ∞ + f v -f w ∞ 2 -m+2
, which proves the first inequality. Now, since t is 1-Lipschitz,

t (y it(w) ) -t (y it(w ) ) y it(w) , y it(w ) 2 -M +1 + f w -f w ∞ 2 -M +1 + 2 -m+2 2 -m+3
where the second inequality uses the definition of i t (v) in Section 4.2 and the fact that K is a (2 -M )covering of [0, 1]. This concludes the proof.

We are now ready to prove Theorem 4 from the main text. Proof (of Theorem 4) Each node v at level m = 0, . . . , M -1 is running an instance of the variant of Exp4 described in Algorithm 4 (Appendix E) over expert set C v , where the advice of w ∈ C v is ξ t (w, •) = p t (w, •), and effective action set

K t = {i : (∃w ∈ C v ) p t (w, i) > 0} = K t (v).
Note that, for any w ∈ C v , the distribution p t (w, •) is a mixture of actions in L w ⊆ L v , so that K t (v) ⊆ {i t (w ) : w ∈ L v }. By Lemma 13, the losses of these actions belong to a range of size E = 2 -m+3 . Since p * t (1) γ by definition, we are in position to apply Theorem 10 in Appendix E with N = |C v | ≤ N m+1 , and obtain the bound

max w∈Cv E T t=1 p t (v, •) • t - T t=1 p t (w, •) • t 2 -m+5 T ln N m+1 γ + 2 -m+3 γ (4 ln N m+1 + 1)
(for simplicity, we use t to denote the vector of elements t (y i ) for i = 1, . . . , K). Now consider the path

v 0 → v 1 → • • • → v M = w * from the root v 0 to the leaf v M = w * minimizing 1 (y i 1 (w) )+ • • • + T (y i T (w)
) over w ∈ L. Recalling that p t (w, i) = I i=it(w) for any leaf w, we get

E T t=1 p t (v 0 , •) • t -min w∈L T t=1 t (y it(w) ) = M -1 m=0 E T t=1 p t (v m , •) • t - T t=1 p t (v m+1 , •) • t 2 5 M -1 m=0 2 -m T ln N m+1 γ + 1 γ (ln N m+1 + 1) . ( 16
+ 2 5 M -1 m=0 2 -m T ln N m+1 γ + 1 γ (ln N m+1 + 1) . Now clearly t (y 1 ) -t y it(w) 1. Moreover, because L is a (2 -M )-covering of F and K is a (2 -M )-covering of [0, 1], for any f ∈ F there exists w ∈ L such that t y it(w) -t f (x t ) y it(w) -f (x t ) 1 y it(w) -f w (x t ) + f w (x t ) -f (x t )
2 1-M by definition of i t (w). Hence,

E T t=1 p * t • t -inf f ∈F T t=1 t f (x t ) (2 1-M + γ)T + 2 5 M -1 m=0 2 -m T ln N m+1 γ + 1 γ (ln N m+1 + 1) . ( 17
)
We now use N m+1 = N ∞ (F, 2 -(m+1) ), and follow the standard chaining approach approximating the sums by integrals,

M -1 m=0 2 -m ln N m+1 = 4 M -1 m=0 2 -(m+1) -2 -(m+2) ln N ∞ (F, 2 -(m+1) ) 4 M -1 m=0 2 -(m+1) 2 -(m+2) ln N ∞ (F, ε)dε 4 1/2 γ/2 ln N ∞ (F, ε)dε (18)
where the second inequality is by monotonicity of ε → ln N ∞ (F, ε) and the last inequality follows from γ 2 -M due to M = ln 2 (1/γ) . Similarly,

M -1 m=0 2 -m ln N m+1 4 1/2 γ/2 ln N ∞ (F, ε)dε . ( 19
)
Construction of T F . We build a tree T F such that the value of any function f M at any point x ∈ [0, 1] d -as given by ( 21)-can be computed by following a path from the root to a leaf of T F . Unlike Section 4.2, this tree is not labeled by functions but instead by either values in R or cubes X m (σ 1:m ) ⊆ [0, 1] d , as illustrated in Figure 3. More precisely, our tree T F is composed of two types of nodes:

• Nodes at depths m. The root v 0 = ∅ (at depth m = 0) is labeled by 1/2. Each node at depth m = 1, 2, . . . is indexed by a tuple (σ 1 , c 1 , σ 2 , c 2 , . . . , σ m , c m ) with σ k ∈ {1, . . . , 2 d } and c k ∈ {-1, 0, 1}; the node is labeled by 1/2 + m k=1 2 -k c k , which corresponds to (21).

• Nodes at depths m + 1/2. Each node at depth m + 1/2, m 0, is indexed by a tuple (σ 1 , c 1 , σ 2 , c 2 , . . . , σ m , c m , σ m+1 ) with σ k ∈ {1, . . . , 2 d } and c k ∈ {-1, 0, 1}; the node is labeled by the cube X m (σ 1:m+1 ).

We connect nodes in the following natural way. Nodes v = (σ 1 , c 1 , σ 2 , c 2 , . . . , σ m , c m ) at depth m are connected to all nodes at depth m + 1/2 of the form (v, σ m+1 ), with σ m+1 ∈ {1, . . . , 2 d }. Nodes w = (σ 1 , c 1 , σ 2 , c 2 , . . . , σ m , c m , σ m+1 ) at depth m + 1/2 are connected to all nodes at depth m + 1 of the form (w, c m+1 ), with c m+1 ∈ {-1, 0, 1}.

We stop the tree at depth M 1. As previously, we denote by L the set of all the leaves of T F , by L v the set of all the leaves under v ∈ T F , and by Algorithm HierExp4 . Our new bandit algorithm HierExp4 (Algorithm 5) is an efficient modification of HierExp4 based on the tree T F defined above. HierExp4 alternates between "binning nodes" at depths m and "Exp4 nodes" at depths m + 1/2 (see Figure 3). We discretize the action space

C v the set of children of v ∈ T F . 1 2 0, 1 2 0 [0, 1 4 [ [ 1 4 , 1 2 [ 1 2 [0, 1 4 [ [ 1 4 , 1 2 [ 1 [0, 1 4 [ [ 1 4 , 1 2 [ [ 1 2 , 1[ 0 [ 1 2 , 3 4 [ [ 3 4 , 1] 1 2 [ 1 2 , 3 4 [ [ 3 4 , 1] 1 [ 1 2 , 3 4 [ [ 3
Y = [0, 1] with K = k2 -M : k = 1, . . . , 2 M } of cardinality K = 2 M .
Note that, after projecting onto 2 -M , 1 , the set of labels of all the leaves v ∈ L exactly corresponds to this discretization, i.e.,

min max 1 2 + M m=1 2 -m c m , 1 2 M , 1 : c m ∈ {-1, 0, 1} = k 2 M : k = 1, . . . , 2 M = K .
At every round t, after observing context x t ∈ [0, 1] d , the algorithm activates the root v 0 and all nodes σ 1 , c 1 , . . . , σ m (, c m ) such that x t ∈ X m (σ 1:m ); the other nodes are asleep during that round. In particular, there are 3 M activated leaves v = (σ 1 , c 1 , . . . , σ M , c M ) ∈ L. Each such leaf recommends the action i t (v) ∈ {1, . . . , K} matching its label after projection onto 2 -M , 1 , i.e., such that i

t (v) 2 M = min max 1 2 + M m=1 2 -m c m , 1 2 M , 1 . (24)
Each node v ∈ T F maintains a probability distribution p t (v, •) ∈ ∆(K) over actions in K, which is only used and updated when v is activated. The activated leaves v ∈ L correspond to unit masses p t (v, i) = I i=it(v) . As mentioned earlier, the internal nodes v ∈ T F \ L are of two types:

• Each internal node v = (σ 1 , c 1 , σ 2 , c 2 , . . . , σ m , c m ) at depth m = 0, . . . , M -1 is a "binning node". When activated, it identifies its only child w = (v, σ m+1 ) handling x t (i.e., such that x t ∈ X m+1 (σ 1:(m+1) )) and outputs p t (v, •) = p t (w, •). We denote by T bin ⊂ T F \ L the set of "binning nodes".

• Each internal node v = (σ 1 , c 1 , σ 2 , c 2 , . . . , σ m , c m , σ m+1 ) at depth m + 1/2 is an "Exp4 node". It runs an instance of Exp4 using the children of v as experts. The variant of Exp4 we use is Algorithm 4 (see Appendix E) applied to penalized loss estimates (cf. ( 2)), which adapts to the range of the losses and allows for a careful control of the variance terms along the tree. Let Exp4 v be the instance of the Exp4 variant run at node v. On all the rounds t when v is activated, this instance updates a distribution q t (v, •) ∈ ∆(|C v |) over experts in C v and outputs p t (v, i) = w∈Cv q t (v, w)p t (w, i) for all actions i = 1, . . . , K. We denote by T Exp4 ⊂ T F \ L the set of "Exp4 nodes".

Note that the root v 0 of T F is activated at all rounds t. The prediction of HierExp4 at time t is y t = I t 2 -M ∈ K, where I t is drawn according to a mixture of p t (v 0 , •) and a unit mass on the minimal action i = 1. A pseudo-code for HierExp4 can be found in Algorithm 5.

G.2. Proof of Theorem 6

As for the proof of Theorem 4, we start by stating a lemma indicating that the losses associated with neighboring leaves are close to one another.

Lemma 15 Let v ∈ T Exp4 , with depth m + 1/2, m ∈ {0, . . . , M -1}. Then, all leaves w, w ∈ L v in the subtree rooted at v satisfy

t i t (w) 2 M -t i t (w ) 2 M 2 1-m
at all rounds t 1 when w and w are both activated.

Proof Denote w = (σ 1 , c 1 , . . . , σ M , c M ) and w = (σ 1 , c 1 , . . . , σ M , c M ). First, we remark that since w and w have the common ancestor v at level m, we have σ i = σ i and c i = c i for all i m, as well as σ m+1 = σ m+1 (recall that v ∈ T Exp4 ). Thus,

M j=1 2 -j c j - M j=1 2 -j c j M j=m+1 2 -j |c j -c j | M j=m+1 2 -j+1 2 1-m .
2 dM leaves σ 1 , c 1 (σ 1 ), σ 2 , c 2 (σ 1:2 ), . . . , σ M , c M (σ 1:M ) are labeled with the values of f M (before projecting onto 2 -M , 1 ) over the cubes X M (σ 1:M ).

We control the regret of HierExp4 with respect to f M by starting from the root v 0 of T F and by progressively moving down the tree. We write P t-1 and E t-1 for conditioning on I 1 , . . . , I t-1 , and set

P * t (k) k i=1 p * t (i) = P t-1 (I t k).
In the sequel, we repeatedly use Corollary 12 with parameters E m 2 1-m , α m and γ to control the regret on each "Exp4 node". This corollary applies to loss estimates penalized with pen t (k) = -α m /P * t (k) for "Exp4 nodes" at depth m + 1/2, with m = 0, . . . , M -1.

Since the root v 0 is a "binning node", we have p t (v 0 , k) = p t (σ 1 , k) at all rounds t such that x t ∈ X 1 (σ 1 ). where ( 27) follows from Corollary 12 with parameters E 0 = 2, α 0 and γ, and where T (σ 1 ) is the number of rounds t such that x t ∈ X 1 (σ 1 ). Indeed, the probability distributions p t (σ 1 , c 1 ), • are mixtures of actions i t (w) associated with activated leaves w ∈ L σ 1 , whose losses are at most at distance 2 by Lemma 15 with m = 0. The last inequality (28) above is obtained by choosing c 1 = c 1 (σ 1 ). So far we have showed how to move from depth m = 0 to depth 1. Repeating the same argument at all subsequent depths m = 1, . . . , M -1, and noting that α m-1 = α m + 4η m 2 2-2m = α m + 4η m E 2 m , we get

t i t (v)   + M -1 m=0 2 (m+1)d ln 3 η m + 4η m T α 2 m γ 2 , ( 29
)
where in the last inequality v denotes the leaf σ 1 , c 1 (σ 1 ), . . . , σ M , c M (σ 1:M ) , whose probability distribution p t (v, •) is the unit mass on its action i t (v).

We define f M (x) min max f M (x), 2 -M , 1 to be the projection of f M (x) onto 2 -M , 1 , and, similarly, f (x) min max f (x), 2 -M , 1 . Since projection can only reduce the distance between two points, f M (x) -f (x)

f M (x) -f (x) f M -f ∞ 2 -M . But, noting that f (x) is 2 -M -close to f (x) ∈ [0, 1], this yields f M (x)-f (x)
f M (x)-f (x) + f (x)-f (x) 2 1-M . Therefore, since t is 1-Lipschitz, and using both (21) and the definition (24) of i t (v), we get that, when the leaf v = σ 1 , c 1 (σ 1 ), . . . , σ M , c M (σ 1:M ) is activated,

t i t (v) = t f M (x t ) t f (x t ) + f M (x t ) -f (x t ) t f (x t ) + 2 1-M .
We plug the last bound into (29) and multiply the resulting inequality by 1 -γ. Then, using E t-1 t y t = (1 -γ)p t (v 0 , •) • t + γ t (1), together with t (y) ∈ [0, 1], we obtain

Reg T (F) M -1 m=0 2 (m+1)d ln 3 η m + 4η m T α 2 m γ 2 + (1 -γ) E T t=1 K k=1 p t (v 0 , k) α 0 + 4η 0 E 2 0 P * t (k) + γT + 2 1-M T . (30)
Now, we use that by definition p * t (k) = (1 -γ)p t (v 0 , k) + γI k=1 (1 -γ)p t (v 0 , k). Therefore, similarly to the analysis of Exp3-RTB, we can control the variance term Optimization of the parameters. In the sequel, we show that the prescribed choices of M , γ, (α m ), and (η m ) lead to the stated regret bound. Before that, we explain these particular choices by approximately optimizing (31), which will lead to (32) and (33). For the sake of readability, we will sometimes write f g instead of f = O(g). First, recall that α m-1 = α m + 4η m E 2 m = α m + 2 4-2m η m . We thus make the approximation α m ≈ 2 4-2m η m , and start by optimizing in η m the terms inside the sum appearing in (31). To do so, we equalize the terms to get the equality where the second inequality is by setting γ = T -1(d+2/3) .

(1 -γ) K k=1 p t (v 0 ,
Putting together the three cases ( 35), (36), and (38) concludes the proof of the regret bound.

Running time of HierExp4 . We only address the case d 2. First note that the total number of "Exp4 nodes" in T F is

T Exp4 = M -1 m=0 v = (σ 1 , c 1 , σ 2 , c 2 , . . . , σ m , c m , σ m+1 ) : σ k ∈ {1, . . . , 2 d }, c k ∈ {-1, 0, 1} = M -1 m=0 3 m 2 d(m+1) = 1 3 3 • 2 d M +1 -3 • 2 d 3 • 2 d -1 3 • 2 d M .
Algorithm 6: HierHedge (for the full information feedback) Input : Tree T F with root v 0 and leaves L, learning rate sequences η 2 (v) η 3 (v) • • • > 0 for v ∈ T F \ L. Initialization: Set q 1 (v, •) to the uniform distribution in ∆(|C v |) for every v ∈ T F \ L. for t = 1, 2, . . . do 1. Get context x t ∈ X ; 2. Set p t (v, i) = I i=it(v) for all i = 1, . . . , K and for all v ∈ L; 3. Set p t (v, i) = q t (v, •) • p t (•, i) for all i = 1, . . . , K and for all v ∈ T F \ L; 4. Draw I t ∼ p t (v 0 , •); 5. Observe t (i) for all i = 1, . . . , K; 6. For each v ∈ T F \ L and for each w ∈ C v compute the expert loss t (v, w) = p t (w, •) • t and perform the update q t+1 (v, w) = exp -η t+1 (v) t s=1 s (v, w)

w ∈Cv exp -η t+1 (v) t s=1 s (v, w ) (39
if d = 1 O √ pT ln(1/ε) + pε 1-d if d = 2 O √ pT ε 1-d/2 + pε 1-d if d 3.
Optimizing in ε, we obtain the stated result.

  Fix any any sequence (x 1 , 1 ), (x 2 , 2 ), . . . of contexts x t ∈ X and 1-Lipschitz loss functionst : Y → [0, 1]. If ContextualExp3 isrun in the bandit feedback model with parameter 5 ε = (ln T ) its regret Reg T (F) with respect to the set F of 1-Lipschitz functions f : X → Y satisfies Reg T (F) = O T p+d+1 p+d+2 , where the O notation hides factors polynomial in C X and C Y , and ln T factors.

Figure 1 :

 1 Figure 1: The loss function t ( y t ) = 1-max{ y t , b t (2)}I yt≤bt(1) when b t (1) = 0.7 and b t (2) = 0.5.

Figure 3 :

 3 Figure 3: The structure of the efficient chaining tree in dimension d = 1.

  σ 1 , c 1 (σ 1 ), . . . , σ M , c M (σ 1:M )], k t (k) -1 (σ 1:M )

  Reg T (F)M -1 m=0 2 (m+1)d ln 3 η m + 4η m T α 2 m γ 2 + (α 0 + 16η 0 )T ln e γ + γT + 2 1-M T . (31)

2

  )end Since L is a (2 -M )-covering of F, 2 -M ≤ 2ε, and K ε is a ε-covering of Y, we get E T ln N m+1 + ln N m+1 + 1 .Overapproximating the sums with integrals similarly to (18) and (19), T ln N ∞ (F, x) + ln N ∞ (F, x) dx . If F is a set of Lipschitz functions f : [0, 1] d → [0, 1] p , where [0, 1] d is endowed with the norm x -x ∞ , then ln N ∞ (F, ε) = O pε -d implying Reg T (F) 5T ε +

Table 1 :

 1 Some regret bounds obtained in this paper. The rates are up to logarithmic factors for Lipschitz policies

  1, 2, . . . do 1. Get context x t ∈ X ; 2. If x t does not belong to any existing ball, then create a new ball of radius ε centered on x t , and allocate a fresh instance of Exp3; 3. Let the active Exp3 instance be the instance allocated to the existing ball whose center x s is closest to x t ; 4. Draw an action y t using the active Exp3 instance; 5. Get t y t and use it to update the active Exp3 instance.

  Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari. Online learning via sequential complexities. Journal of Machine LearningResearch, 16:155-186, 2015.

	Shai Shalev-Shwartz. Online learning and online convex optimization. Foundations and Trends in
	Machine Learning, 4(2):107-194, 2011.
	Aleksandrs Slivkins. Contextual bandits with similarity information. Journal of Machine Learning
	Research, 15(1):2533-2568, 2014.
	Vasilis Syrgkanis, Akshay Krishnamurthy, and Robert Schapire. Efficient algorithms for adversar-
	ial contextual learning. In Proceedings of the Twentieth International Conference on Machine
	Learning (ICML), 2016.
	Vladimir Vovk. Competing with wild prediction rules. Machine Learning, 69(2-3):193-212, 2007.

  Kand constant learning rate η > 0. If we have, for all t 1, almost surely,

			max t=1,...,T	max k,k ∈Kt	t (k) -t (k )	E	and	p * t (1) γ ,
	then, for all T 1,
	max j=1,...,K	E	T t=1	K k=1	p t (k) t (k) -	α + 4ηE 2 P * t (k)

)

  Now, recalling that I t ∼ p * t and p * t (i) t (y i ) = (1 -γ)p t (v 0 , i) t (y i ) + γ I i=1 t (y 1 ) we get

		T			T		T
	E	t=1	p * t • t	min w∈L	t=1	t y it(w) + γ	t=1	t (y 1 ) -t y it(w)

  Therefore, writing t (k) instead of t k/2 M ,

	E	T t=1	K k=1	p t (v 0 , k) t (k) -	α 0 + 4η 0 E 2 0 P * t (k)
	=	σ 1 ∈{1,...,2 d }	E   t: xt∈X 1 (σ 1 )	K k=1	p t (σ 1 , k) t (k) -	α 0 + 4η 0 E 2 0 P * t (k)	 
										
		σ 1 ∈{1,...,2 d }	min c 1 ∈{-1,0,1}	E 	α 0 P * t (k)	
					+	ln 3 η 0	+	4η 0 T (σ 1 )α 2 0 γ 2	(27)
		σ 1	E   t: xt∈X 1 (σ 1 )	K k=1	p α 0 P * t (k)	  +	2 d ln 3 η 0	+	4η 0 T α 2 0 γ 2 , (28)

t: xt∈X 1 (σ 1 ) K k=1 p t (σ 1 , c 1 ), k t (k)t [σ 1 , c 1 (σ 1 )], k t (k) -

This bound has a polynomial dependence on the metric dimension of the action space, which is absorbed by the asymptotic notation.

Assuming a unit Lipschitz constant is without loss of generality because our algorithms are oblivious to it.

Assuming a unit Lipschitz constant L f for the functions in f ∈ F is also without loss of generality because our algorithms are oblivious to it. The only exception is algorithm HierExp4 of Section

4.3, which is only guaranteed to work with unit Lipschitz constants. However, a similar regret bound can be achieved for arbitrary (yet known) values of L f via a simple modification-see also(Bubeck et al., 2011b) for regret bounds optimized for L f in a stochastic and non-contextual bandit setting when L f is unknown.

Acknowledgments

This work was partially supported by the CIMI (Centre International de Mathématiques et d'Informatique) Excellence program. Pierre Gaillard and Sébastien Gerchinovitz acknowledge the support of the French Agence Nationale de la Recherche (ANR), under grants ANR-13-BS01-0005 (project SPADRO) and ANR-13-CORD-0020 (project ALICIA).

Appendix C. The Exp3-RTB algorithm for reserve-price optimization [START_REF] Cesa-Bianchi | Regret minimization for reserve prices in second-price auctions[END_REF] showed that a regret of order O √

T can be achieved with high probability for the problem of regret minimization in second-price auctions with i.i.d. bids, when the feedback received after each auction is the seller's revenue. In this appendix, we show that the same regret rate can be obtained even when the sequence of bids is nonstochastic, provided the feedback also includes the highest bid. We use this result in order to upper bound the contextual regret in Section 4.1.

We consider a setting slightly more general than second-price auctions. Fix any unknown sequence 1 , 2 , . . . of loss functions t : [0, 1] → [0, 1] satisfying the semi-Lipschitz condition, t (y + δ) ≥ t (y) -δ for all 0 y y + δ 1.

In each auction instance t = 1, 2, . . . , the learner selects a reserve price y t ∈ Y = [0, 1] and suffers the loss t ( y t ). The learner's feedback is t (y) for all y y t (i.e., the one-sided full information feedback). As explained in Section 4.1, this setting includes online revenue maximization in secondprice auctions as a special case when the learner's feedback includes both revenue and highest bid. The learner's regret is defined by

where the expectation is with respect to the randomness in the predictions y t . We introduce the Exp3-RTB algorithm (Algorithm 3 below), a variant of Exp3 [START_REF] Auer | The nonstochastic multiarmed bandit problem[END_REF] exploiting the richer feedback t (y) : y y t . The algorithm uses a discretization of the action space [0, 1] in K = 1/γ actions y k := (k -1)γ for k = 1, . . . , K.

We conclude the proof by substituting ( 18) and ( 19) into (17), and using 2 -M 2γ.

Proof (of Corollary 5)

The metric entropy satisfies ln N ∞ (F, ε) = O ε -d . Therefore, substituting into the regret bound of Theorem 4 and computing the integrals, the regret satisfies

Optimizing γ for the different choices of d concludes the proof.

Appendix G. Algorithm HierExp4 and proof of Theorem 6

G.1. Algorithm HierExp4

We first construct the HierExp4 algorithm used in Theorem 6. It is a variant of HierExp4 based on a special hierarchical covering of F that we first define below. Recall that F is the set of all

In the sequel, we use a dyadic discretization of the input space [0, 1] d . For each depth m = 0, 1, . . . we define a partition of [0, 1] d with 2 md equal cubes of width 2 -m . Each cube X m (σ 1:m ) ⊆ [0, 1] d at depth m is indexed by σ 1:m = (σ 1 , . . . , σ m ) ∈ {1, . . . , 2 d } m . Note that the partitions at different depths are nested. We can thus represent them via a tree P whose root ∅ is labeled by [0, 1] d and whose each node σ 1:m at depth m is labeled with the cube X m (σ 1:m ). The children of node σ 1:m are the nodes at depth m + 1 of the form (σ 1 , . . . , σ m , σ m+1 ) with σ m+1 ∈ {1, . . . , 2 d }. They correspond to sub-cubes of X m (σ 1:m ).

Wavelet-like approximation of F. Using the above dyadic discretization P, we approximate any

As shown in the next lemma, the functions

. We use the following important property: for any given

Proof We denote the center of each cube X m (σ 1:m ) by x m (σ 1:m ) and prove by induction on M 1 that there exist coefficients c m (σ 1:m ), m = 0, . . . , M , such that

This directly yields the conclusion, since every x ∈ X M (σ 1:M ) is 2 -(M +1) -close to the center x M (σ 1:M ) in sup norm and f is 1-Lipschitz, which by ( 22) and

We now carry out the induction. For M = 1 and σ 1 ∈ {1, . . . , 2 d }, we set

which corresponds to projecting the value of f at the center x 1 (σ 1 ) onto the coarse grid {0, 1/2, 1}.

1/4, which implies ( 22) by ( 21). Now, let M 2 and assume that there exist coefficients c m (σ 1:m ), m = 0, . . . , M -1, such that ( 22) holds true at level M -1. We complete these coefficients at level M as follows: for all

Note that by ( 21) and

Therefore, the definition of c M (σ 1:M ) above corresponds to making f M x M (σ 1:M ) as close to f x M (σ 1:M ) as possible. Now, note that f M -1 is constant over X M -1 (σ 1:(M -1) ), so that the difference

where the last inequality is by ( 22) at level M -1, and where the last equality is by comparison of two cube centers at subsequent depths.

To conclude the proof, we note that the bound +1) , as required to finish the induction. We can indeed consider three possible cases. If ∆ M -1

2 -(M +1) , then setting c M (σ 1:M ) = 0 concludes the proof (by ( 23 +1) , so that setting c M (σ 1:M ) = -1 also concludes the proof (using (23) again). Similarly we set c M (σ

We are now ready to define our hierarchical covering of F.

Algorithm 5: HierExp4 (for the one-sided full information feedback) Input : Tree T F with root v 0 and leaves L, exploration parameter γ ∈ (0, 1), penalization parameters α 0 , . . . , α M -1 > 0, learning rates η 0 , . . . , η M -1 > 0.

for all i ∈ K and all activated leaves v ∈ L; 4. Set p t (v, i) = q t (v, •) • p t (•, i) for all i ∈ K and all activated nodes v ∈ T Exp4 ; 5. Set p t (v, •) = p t (w, •) for all activated nodes v ∈ T bin , where w ∈ C v is the unique activated child of v; 6. Draw I t ∼ p * t and play y t = I t 2 -M , where p * t (i) = (1 -γ)p t (v 0 , i) + γI i=1 for all i ∈ K; 7. Observe t (y) for all y y t ; 8. For all m = 0, . . . , M -1 and all activated nodes v ∈ T Exp4 at level m + 1/2, with v = (σ 1 , c 1 , σ 2 , c 2 , . . . , σ m , c m , σ m+1 ), compute the loss estimate for each i ∈ K t (v),

where

Then, for each w ∈ C v , compute the expert loss t (v, w) = p t (w, •) • t (v, •) and perform the update

end Therefore, by definition (24) of i t (w) and i t (w ), and since projecting two real numbers onto 2 -M , 1 can only reduce their distance, we get, when w and w are both activated,

which implies the result since t is 1-Lipschitz.

We are now ready to prove Theorem 6 from the main text.

Proof (of Theorem 6) Let f ∈ F. By Lemma 14, we can fix

In the proof of Theorem 4, we rewrite the regret with respect to f M as the sum of M regrets along the path joining the root of T F to the leaf corresponding to f M . Next, we proceed similarly except that now f M corresponds to a (2 d )-ary subtree of T F indexed by σ 1:M ∈ {1, . . . , 2 d } M . The

where inequality ( * ) is by using d 4 and choosing c = 2 -5/4 M -1/2 1

, while the last inequality is because ∞ m=0 2 -m/4 2 3 for d = 1. Plugging this inequality into (31), upper bounding α 0 using (34) and η 0 using (32), and recalling that M = ln 2 (1/γ) , we get

where the last inequality is because 3d/4 < d -1/3 for d 2.

• If d 5, then the terms inside the sum in (33) are exponentially increasing, so that

(37) Then, following the lines of the case d 4, by substituting η m (see ( 32)) and α m in the sum in the right-hand side of (31) Similarly, T bin 3 • 2 d M and L 3 • 2 d M . Summing the three upper bounds, we get

Therefore, using M = ln 2 (1/γ) and γ = T -1/(d+2/3) , we obtain

.

The number of actions in K is 2 M = O T 1 d+2/3 . The running time at every round t, which is at most proportional to the total number of tuples (v, w, i) for (v, i) ∈ T F × K and w ∈ C v , is at most of the order of T F × K × max 2 d , 3 . Therefore, the running time is at most of the order of

T 1.8 for all d 2.

A tighter analysis however yields a smaller time complexity than the rate T d+1+ln 2 3 d+2/3 derived above. This is because -from Algorithm 5-all elementary computations only need to be computed on activated "Exp4 nodes" nodes, on their (finite number of) children, and on actions in K. Fix a round t 1. From a computation similar to the one above, but noting that all activated nodes share the same coefficients σ m for all depths m, we can see that the total number of activated "Exp4 nodes" at round t is at most of

so that the running time per round is at most of the order of 3 M 2 M T , so that the stated running time also holds true for d = 1.

Appendix H. Algorithm HierHedge and proof of Theorem 7

The proof goes along the same lines as the proof of Theorem 4. Let v be any internal node at depth m = 0, . . . , M -1. By construction of HierHedge, the distribution p t (v, •) ∈ ∆(K) is computed by Hedge and is supported on the set {i t (w) : w ∈ L v }. By Lemma 13, the losses of any pair of actions in this set differ by at most 2 -m+3 . Hence, we may apply (Cesa-Bianchi et al., 2007, Theorem 5)