Proceedings of Machine Learning Research vol 65:1–37, 2017

Algorithmic Chaining and the Role of Partial Feedback
in Online Nonparametric Learning
Nicolò Cesa-Bianchi

NICOLO . CESA - BIANCHI @ UNIMI . IT

arXiv:1702.08211v2 [stat.ML] 30 Jun 2017

Università degli Studi di Milano, Milano, Italy

Pierre Gaillard
PIERRE . GAILLARD @ INRIA . FR
INRIA - Sierra Project-team, Département d’Informatique de l’École Normale Supérieure, Paris, France
Claudio Gentile

CLAUDIO . GENTILE @ UNINSUBRIA . IT

Università degli Studi dell’Insubria, Varese, Italy

Sébastien Gerchinovitz

SEBASTIEN . GERCHINOVITZ @ MATH . UNIV- TOULOUSE . FR

Université Toulouse III - Paul Sabatier, Toulouse, France

Abstract
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.
Keywords: online learning, nonparametric, chaining, bandits.

1. Introduction
In online learning (Cesa-Bianchi and Lugosi, 2006; Shalev-Shwartz, 2011; Hazan, 2015) 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., (Alon et al., 2014, 2015). 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.
Accepted
.
for presentation at Conference on Learning Theory (COLT) 2017.

c 2017 N. Cesa-Bianchi, P. Gaillard, C. Gentile & S. Gerchinovitz.

C ESA -B IANCHI G AILLARD G ENTILE G ERCHINOVITZ

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 Hazan
 and Megiddo (2007). For
e T (d+1)/(d+2) upper bound1 on the regret
any reference class of Lipschitz policies, they proved a O
e notation hides logarithmic factors in T . In
for any context space of metric dimension d, where
the O

(d−1)/d
the same work, they also proved a Ω T
lower bound. The gap between the upper and lower
bound was closed by Rakhlin et al. (2015) 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 Hazan and Megiddo (2007)
e T (d+p+1)/(d+p+2) upper bound on the regret against any class
can be also adapted to prove a O
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; Kleinberg et al., 2008) 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

e T (d−1)/d for Lipschitz policies and Lipschitz losses (excluding logathe minimax regret rate O
rithmic 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

e T d/(d+1) , which is larger than the minimax regret for full information
Lipschitz losses of order O
but smaller than the upper bound for bandit information when p = 1. For the special case when the
1. This bound has a polynomial dependence on the metric dimension of the action space, which is absorbed by the
asymptotic notation.

2

A LGORITHMIC C HAINING AND THE ROLE OF PARTIAL F EEDBACK IN O NLINE N ONPARAMETRIC L EARNING

context space is [0, 1]d , we use a specialized approach offering the double advantage of an improved
e T (d−1/3)/(d+2/3) regret bound which is also attained by a time-efficient algorithm.
O
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 semiLipschitz. When the feedback after each auction is the
 seller’s revenue together with the highest bid
e T (d+1)/(d+2) regret bound against Lipschitz policies (in this
for the current auction, we prove a O
setting,
√ a policy maps contexts to reserve prices for the seller). As a by-product, we show the first
e
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.
Feedback model
Bandit
One-sided full information

Loss functions
Lipschitz
Convex

T
d+1
T d+2

Semi-Lipschitz

T d+2

Lipschitz
Full information

Upper bound
d+2
d+3

Lipschitz

d+1

T
T

d−1/3
d+2/3
d−1
d

(Theorem 1)
(Corollary 2)
(Theorem 3)
(Theorem 6)
(Theorem 7)

Table 1: Some regret bounds obtained in this paper. The rates are up to logarithmic factors for
Lipschitz policies 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 Hazan and Megiddo (2007).

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 (Freund and Schapire, 1997) and Exp3/Exp4 (Auer et al., 2002). The simplest of our
algorithms, adapted from Hazan and Megiddo (2007), 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 (Dudley, 1967). In particular,
inspired by previous works in this area (especially the work of Gaillard and Gerchinovitz, 2015),
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.
3

C ESA -B IANCHI G AILLARD G ENTILE G ERCHINOVITZ

Hence, there exist CX , CY > 0 such that, for all 0 < ε 6 1, X and Y can be covered, respectively,
with at most CX ε−d and at most CY ε−p balls of radius ε. For any 0 < ε 6 1, we use Yε to denote
any ε-covering of Y of size Kε 6 CY ε−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 (x1 , ℓ1 ), (x2 , ℓ2 ), . . . of contexts xt ∈ X and loss
functions ℓt : Y → [0, 1], for every round t = 1, 2, . . . :
1. The environment reveals context xt ∈ X ;

2. The learner selects an action ybt ∈ Y and incurs loss ℓt ybt ;
3. The learner obtains feedback from the environment.
Loss functions ℓt satisfy the 1-Lipschitz2 condition ℓt (y) − ℓt (y ′ ) 6 ρ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 (b
yt ) of the selected action ybt ), 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 > ybt ). 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,
" T
#
T
X
X


ℓt ybt − inf
RegT (F) , E
ℓt f (xt ) ,
f ∈F

t=1

t=1

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 1Lipschitz3 w.r.t. ρX and ρY . Namely, ρY f (x), f (x′ ) 6 ρX (x, x′ ) for all f ∈ F and all x, x′ ∈ X .
We occasionally use the dot product notation pt · ℓt to indicate the expectation of ℓt according to
law pt . 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).

2. Related Work
Contextual online learning generalizes online convex optimization (Hazan, 2015) to nonconvex
losses, nonparametric policies, and partial feedback. Papers about nonparametric online learning
in full information include (Vovk, 2007; Gaillard and Gerchinovitz, 2015) for the square loss, and
(Hazan and Megiddo, 2007; Rakhlin and Sridharan, 2015) for general convex losses. In the bandit
2. Assuming a unit Lipschitz constant is without loss of generality because our algorithms are oblivious to it.
3. Assuming a unit Lipschitz constant Lf 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 Lf via a simple modification—see also (Bubeck et al., 2011b) for regret bounds optimized for Lf in a stochastic
and non-contextual bandit setting when Lf is unknown.

4

A LGORITHMIC C HAINING AND THE ROLE OF PARTIAL F EEDBACK IN O NLINE N ONPARAMETRIC L EARNING

feedback model, earlier work on context-free bandits on metric spaces includes (Kleinberg, 2004;
Kleinberg et al., 2008). The paper (Auer et al., 2002) 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
Maillard and Munos (2011), 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 (Dudley, 1967) 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 Cesa-Bianchi and Lugosi (1999) to design an algorithm for linear losses, and
nonconstructively by Rakhlin et al. (2015) to derive minimax rates for Lipschitz losses. Other notable examples of chaining are the stochastic bandit algorithms of Contal et al. (2015) and Contal and Vayatis
(2016). The constructive algorithmic chaining technique developed in this work is inspired by the
nonparametric analysis of the full information setting of Gaillard and Gerchinovitz (2015). 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 Gerchinovitz and Lattimore (2016) 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 (Rakhlin et al., 2015).
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 (Agarwal et al., 2014; Rakhlin and Sridharan, 2016; 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.

3. 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 Hazan and Megiddo (2007) and maintains
a set of balls of fixed radius ε in the context space, where each ball hosts an instance of the Exp3

5

C ESA -B IANCHI G AILLARD G ENTILE G ERCHINOVITZ

algorithm of Auer et al. (2002).4 At each round t, if a new incoming context xt ∈ X is not contained
in any existing ball, then a new ball centered at xt is created, and a fresh instance of Exp3 is allocated
to handle xt . Otherwise, the Exp3 instance associated with the closest context so far w.r.t. ρX is
used to handle xt . Each allocated Exp3 instance operates on the discretized action space Yε whose
size Kε is at most CY ε−p . For completeness, the proof of the following theorem is provided in
Algorithm 1: ContextualExp3 (for bandit feedback)
Input: Ball radius ε > 0, ε-covering Yε of Y such that |Yε | ≤ CY ε−p .
for t = 1, 2, . . . do
1. Get context xt ∈ X ;
2. If xt does not belong to any existing ball, then create a new ball of radius ε centered on xt ,
and allocate a fresh instance of Exp3;
3. Let the active Exp3 instance be the instance allocated to the existing ball whose center xs is
closest to xt ;
4. Draw an action
ybt using the active Exp3 instance;

5. Get ℓt ybt and use it to update the active Exp3 instance.
end

Appendix B.
Theorem 1 Fix any any sequence (x1 , ℓ1 ), (x2 , ℓ2 ), . . . of contexts xt ∈ X and 1-Lipschitz loss
functions ℓt : Y → [0, 1]. If ContextualExp3 is run in the bandit feedback model with parameter5
2
1
ε = (ln T ) p+d+2 T − p+d+2 , then its regret RegT (F) with respect to the set F of 1-Lipschitz functions
p+d+1 
e T p+d+2 , where the O
e notation hides factors polynomial in
f : X → Y satisfies RegT (F) = O
CX and CY , and ln T factors.

A lower bound matching up to log factors the upper bound of Theorem 1 is contained in (Slivkins,
2014) —see also (Lu et al., 2010) 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.
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); Kleinberg et al. (2008) 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 Rp . 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 (Audibert and Bubeck, 2010), 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 ε 6 1.

6

A LGORITHMIC C HAINING AND THE ROLE OF PARTIAL F EEDBACK IN O NLINE N ONPARAMETRIC L EARNING

action space Y. The regret of the algorithm that
by Bubeck et al. (2016), run on the non-discretized
√
replaces Exp3 is bounded by poly(p, ln T ) T . This immediately gives the following corollary.
Corollary 2 Fix any any sequence (x1 , ℓ1 ), (x2 , ℓ2 ), . . . of contexts xt ∈ X and convex loss functions ℓt : Y → [0, 1], where Y is a convex and compact subset of Rp . Then there exists an algorithm
for the bandit feedback model whose regret with respect to the set F of 1-Lipschitz functions satisfies
RegT (F) 6 poly(p, ln T )T (d+1)/(d+2) , where poly is a polynomial function of its arguments.

4. 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 ybt ∈ Y, the
learner can compute the loss ℓt (y) of any number of actions y > ybt . This in contrast to observing
only ℓt ybt , 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.
4.1. 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 (Ostrovsky and Schwarz, 2011)
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 Cesa-Bianchi et al. (2015) 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 efe T with
ficient strategy for setting reserve prices such that the seller’s regret is bounded by O
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
√ 
e T regret bound for the seller in nonstochastic and noncontextual second-price auctions. UnO
like (Cesa-Bianchi et al., 2015), 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 yb
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 yb 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 yb is bigger than b(1), thenthe
item is not sold and the seller’s revenue is zero. Formally, the seller’s revenue is g yb, b(1), b(2) =
7

C ESA -B IANCHI G AILLARD G ENTILE G ERCHINOVITZ


max yb, b(2) Iyb≤b(1) . Note that the revenue only depends on the reserve price yb 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 x1 , x2 , . . . ∈
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 xt and computes a reserve price ybt ∈ [0, 1]. Then, bids bt (1), bt (2) are collected
by the auctioneer, and the seller (which is not the same as the auctioneer) observes his revenue
yt ) and bt (1)
gt ybt = g ybt , bt (1), bt (2) , together with the highest bid bt (1). Crucially, knowing gt (b
allows to compute gt (y) for all y > ybt . For technical reasons, we use losses ℓt ybt = 1 − gt ybt
instead of revenues, see Figure 1 for a pictorial representation.
1

0.8
0.6
1 − bt (2)
1 − bt (1)

0.4
0.2
0

0

0.2

0.4

0.6

bt (2)

0.8

1

bt (1)

Figure 1: The loss function ℓt (b
yt ) = 1−max{b
yt , bt (2)}Iybt ≤bt (1) when bt (1) = 0.7 and bt (2) = 0.5.
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 6 y 6 y + δ 6 1. We now state a bound
on the regret RegT (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.
Theorem 3 Fix any sequence of contexts xt ∈ X and1 bid pairs 0 6 bt (2) 6 bt (1) 6 1 for
t > 1. If ContextualRTB is run with parameter ε = T − 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
d+1 
e T d+2 , where d is the dimension of X and the O
e notation hides constants and ln T
RegT (F) = O
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 (De Rosa et al., 2015, Theorem 1).
8

A LGORITHMIC C HAINING AND THE ROLE OF PARTIAL F EEDBACK IN O NLINE N ONPARAMETRIC L EARNING

4.2. 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 > ybt — is combined with Lipschitz losses (rather than just semiLipschitz), 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) f0 → f1 → · · · → fM → f ∗ , where f0 is the root and
fM 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 Af 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 A0 running on the root node is the output of the tree. For any given sequence of pairs
(xt , ℓt ) of contexts and losses, the regret against f ∗ with path f0 → f1 → · · · → fM → f ∗ can
then be written (ignoring some constants) as
#
" T
−1
T 

 M
X
X
X





+ 2−M T
ℓt Am (xt ) − ℓt Am+1 (xt )
E
E ℓt A0 (xt ) − ℓt f ∗ (xt ) 6
t=1

m=0

t=1

where Am is the instance running on node fm for m = 0, . . . , M − 1 and AM ≡ fM . The last
term 2−M T accounts for the cost of approximating f ∗ with the closest function fM 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 Am
against the instances running on the children of the node hosting Am . 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 A0 to draw
actions in the bandit problem, and so the other Exp4 instances receive loss estimates that are based
on the distribution used by A0 rather than being based on their own distributions. A second issue
is that our regret decomposition crucially relies on the fact that each instance Am only competes
(in the sense of regret) against functions f at the leaves of the subtree rooted at the node where
Am 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 Am 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
kf − gk∞ = sup f (x) − g(x) .
x∈X

9

(1)

C ESA -B IANCHI G AILLARD G ENTILE G ERCHINOVITZ


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
is
 property
d
known as total boundedness). In Section 4.3 we will focus on the special case F = f : [0, 1] →
[0, 1] : f is 1-Lipschitz to derive an efficient version of our algorithm.
We now define a tree TF 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 Fm be a (2−m )-covering of F in sup
norm with minimal cardinality Nm = N∞ (F, 2−m ). Since the diameter of (F, k·k∞ ) is bounded
by 1, we have N0 = 1 and F0 = {f0 } for some f0 ∈ F. For each m = 0, 1, . . . , M and for every
fv ∈ Fm we have a node v in TF 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

kfv′ − fw k∞

(ties broken arbitrarily)

and we say that w is a child of v. Let L be the set of all the leaves of TF , Lv be the set of all the
leaves under v ∈ TF (i.e., the leaves of the subtree rooted at v), and Cv be the set of children of
v ∈ TF .
u

Level m

2−m covering of F

Level m + 1

2−(m+1) covering

Exp4

...

..

..
...

Exp4

.

v

.

.

Exp4

..

..

.

...

...

w

Level M (=leaves L)

2−M covering

Leaves under v = Lv

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 TF constructed above (see Figure 2). Let K = 2M and K =
{y1 , . . . , yK }, where yk = 2−M (k − 1) for k = 1, . . . , 2M , be our discretization of the action
space Y = [0, 1]. At every round t, after observing context xt ∈ X , each leaf v ∈ L recommends
the best approximation of fv (xt ) in K, it (v) ∈ arg mini=1,...,K yi − fv (xt ) . Therefore, the leaves
v ∈ L correspond to deterministic strategies t 7→ it (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 ∈ TF \ 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 Exp4v be
the instance of the Exp4 variant run on node v. At each time t, this instance updates a distribution
qt (v, ·) ∈ ∆(|C
Pv |) over experts in Cv and a distribution pt (v, ·) ∈ ∆(K) over actions in K defined
by pt (v, i) = w∈Cv qt (v, w)pt (w, i).
Let v0 be the root of TF . The prediction of HierExp4 at time t is ybt = yIt ∈ K, where It is
drawn according to a mixture of pt (v0 , ·) and a unit mass on the minimal action y1 ∈ K.
For each v ∈ TF \ L, let Kt (v) = {i : (∃w ∈ Cv ) pt (w, i) > 0} and jt (v) = max Kt (v).
Note that ℓbt (v, i) in (2) has to be explicitly computed only for those actions i such that i > It and
10

A LGORITHMIC C HAINING AND THE ROLE OF PARTIAL F EEDBACK IN O NLINE N ONPARAMETRIC L EARNING

i ∈ Kt (v). This is because ℓbt (v, i) is needed for the computation of ℓet (v, w) only when pt (w, i) > 0.
Therefore, whenever
ℓbt (v, i) has to be computed for some i, then It 6 i 6 max Kt (v) = jt (v), so

that ℓt yjt (v) is observed and ℓbt (v, i) is well defined.
Algorithm 2: HierExp4 (for one-sided full information feedback)
Input
: Tree TF with root v0 and leaves L, exploration parameter γ ∈ (0, 1), learning rate
sequences η1 (v) > η2 (v) > · · · > 0 for v ∈ TF \ L.
Initialization: Set q1 (v, ·) to the uniform distribution in ∆(|Cv |) for every v ∈ TF \ L.
for t = 1, 2, . . . do
1. Get context xt ∈ X ;
2. Set pt (v, i) = Ii=it (v) for all i ∈ K and for all v ∈ L;
3. Set pt (v, i) = qt (v, ·) · pt (·, i) for all i ∈ K and for all v ∈ TF \ L;
4. Draw It ∼ p∗t and play ybt = yIt , where p∗t (i) = (1 − γ)pt (v0 , i) + γIi=1 for all i ∈ K;
5. Observe ℓt (y) for all y > yIt ;
6. For every v ∈ TF \ L and for every i ∈ Kt (v) compute

ℓt (yi ) − ℓt yjt (v)
ℓbt (v, i) =
IIt 6i ,
Pi
∗
k=1 pt (k)

end

where Kt (v) = {i : (∃w ∈ Cv ) pt (w, i) > 0} and jt (v) = max Kt (v).
7. For each v ∈ TF \ L and for each w ∈ Cv compute the expert loss
ℓet (v, w) = pt (w, ·) · ℓbt (v, ·) and perform the update


P
exp −ηt+1 (v) ts=1 ℓes (v, w)


qt+1 (v, w) = P
Pt e
′)
exp
−η
(v)
ℓ
(v,
w
′
t+1
s=1 s
w ∈Cv

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 (x1 , ℓ1 ), (x2 , ℓ2 ), . . .
of contexts xt ∈ 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 TF of depth M = ⌊ln2 (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 Vet−1 (v) is the cumulative variance of ℓes (v, ·) according to qs (v, ·) up to time
s = t − 1. Then for all T > 1 the regret satisfies
!
Z 1/2 s

1
T
7
RegT (F) 6 5γT + 2
ln N∞ (F, ε) + 1
dε .
ln N∞ (F, ε) +
γ
γ
γ/2
In particular, if X ≡ [0, 1]d is endowed with the sup norm ρX (x, x′ ) = kx − x′ k∞ , 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.
11

(2)

(3)

C ESA -B IANCHI G AILLARD G ENTILE G ERCHINOVITZ

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


 O T 2/3

RegT (F) =
O T 2/3 (ln T )2/3

O T d/(d+1)

the set of all 1-Lipschitz functions
if d = 1
if d = 2
if d > 3

where the last inequality is obtained by optimizing the choice of γ for the different choices of d.
4.3. Efficient chaining

Though very general, HierExp4 (Algorithm 2) may be very inefficient. For example, when F is the
d
set of all 1-Lipschitz
 functions from [0, 1] 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., (Gaillard and Gerchinovitz, 2015)— 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 TF⋆ 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 cT (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 (x1 , ℓ1 ), . . . , (xT , ℓT ) of contexts xt ∈ [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 TF⋆ of depth M = ⌈ln2 (1/γ)⌉, exploration
1
1
d
parameter γ = T −1/2 (ln
)−1 Id=1 + T −1/(d+2/3) Id>1 , learning rate ηm = cT 2m( 4 +1) γ 2 T − 4 ,
PT
4−2j η for m = 0, . . . , M − 1. Then the regret satisfies
and penalization αm = M
j
j=m+1 2
(
√

O T ln T
if d = 1,
d−1/3
RegT (F) =

O T d+2/3 (ln T )3/2 if d > 2.

Moreover, the running time at every round is O T a with a = (1 + ln2 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)
e T ) for nonparametric bandits
from Corollary 5. Remarkably, Theorem 6 also yields a regret of O(
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 Exp3RTB 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.

12

A LGORITHMIC C HAINING AND THE ROLE OF PARTIAL F EEDBACK IN O NLINE N ONPARAMETRIC L EARNING

5. 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 Rakhlin et al. (2015) in a nonconstructive
manner, and matches the lower bound of Hazan and Megiddo (2007). Our approach generalizes the
approach of Gaillard and Gerchinovitz (2015) 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 TF are replaced by instances of
Hedge —e.g., (Bubeck and Cesa-Bianchi, 2012). 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 (x1 , ℓ1 ), (x2 , ℓ2 ), . . . of
contexts xt ∈ 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 TF of depth M = ⌊ln2 (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 = |Cv |, and Vet−1 being the
cumulative variance of ℓes according to qs (v, ·) up to time s = t − 1. Then for all T > 1 the regret
satisfies
Z 1/2  p

2 T ln N∞ (F, x) + ln N∞ (F, x) dx .
RegT (F) 6 5εT + 27
ε/2

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

1/d
e (d−1)/d ,
[0, 1]p are endowed with their sup norms, the
√ choice ε = (p/T ) yields RegT (F) = O T
while for 1 6 d 6 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 p1/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.

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).

References
Alekh Agarwal, Daniel Hsu, Satyen Kale, John Langford, Lihong Li, and Robert Schapire. Taming
the monster: A fast and simple algorithm for contextual bandits. In International Conference on
Machine Learning (ICML), 2014.
13

C ESA -B IANCHI G AILLARD G ENTILE G ERCHINOVITZ

Noga Alon, Nicolò Cesa-Bianchi, Claudio Gentile, Shie Mannor, Yishay Mansour, and
Ohad Shamir. Nonstochastic multi-armed bandits with graph-structured feedback. CoRR,
abs/1409.8428, 2014.
Noga Alon, Nicolò Cesa-Bianchi, Ofer Dekel, and Tomer Koren. Online learning with feedback
graphs: Beyond bandits. In COLT, pages 23–35, 2015.
Jean-Yves Audibert and Sébastien Bubeck. Regret bounds and minimax policies under partial
monitoring. Journal of Machine Learning Research, 11(Oct):2785–2836, 2010.
Peter Auer, Nicolò Cesa-Bianchi, Yoav Freund, and Robert E Schapire. The nonstochastic multiarmed bandit problem. SIAM journal on computing, 32(1):48–77, 2002.
Sébastien Bubeck and Nicolò Cesa-Bianchi. Regret analysis of stochastic and nonstochastic multiarmed bandit problems. Foundations and Trends in Machine Learning, 5(1):1–122, 2012.
Sébastien Bubeck, Rémi Munos, Gilles Stoltz, and Csaba Szepesvári. X-armed bandits. Journal of
Machine Learning Research, 12(May):1655–1695, 2011a.
Sébastien Bubeck, Gilles Stoltz, and Jia Yuan Yu. Lipschitz bandits without the Lipschitz constant.
In International Conference on Algorithmic Learning Theory, pages 144–158. Springer, 2011b.
Sébastien Bubeck, Ronen Eldan, and Yin Tat Lee. Kernel-based methods for bandit convex optimization. arXiv preprint arXiv:1607.03084, 2016.
Nicolò Cesa-Bianchi and Gábor Lugosi. On prediction of individual sequences. The Annals of
Statistics, 27(6):1865–1895, 1999.
Nicolò Cesa-Bianchi and Gábor Lugosi. Prediction, learning, and games. Cambridge university
press, 2006.
Nicolò Cesa-Bianchi, Yishay Mansour, and Gilles Stoltz. Improved second-order bounds for prediction with expert advice. Machine Learning, 66(2-3):321–352, 2007.
Nicolò Cesa-Bianchi, Claudio Gentile, and Yishay Mansour. Regret minimization for reserve prices
in second-price auctions. IEEE Transactions on Information Theory, 61(1):549–564, 2015.
Emile Contal and Nicolas Vayatis. Stochastic process bandits: Upper confidence bounds algorithms
via generic chaining. arXiv preprint arXiv:1602.04976, 2016.
Emile Contal, Cédric Malherbe, and Nicolas Vayatis. Optimization for gaussian processes via
chaining. arXiv preprint arXiv:1510.05576, 2015.
Rocco De Rosa, Francesco Orabona, and Nicolò Cesa-Bianchi. The ABACOC algorithm: A novel
approach for nonparametric classification of data streams. In Proceedings of the IEEE International Conference on Data Mining (ICDM), pages 733–738, 2015.
Richard M Dudley. The sizes of compact subsets of Hilbert space and continuity of Gaussian
processes. Journal of Functional Analysis, 1(3):290–330, 1967.

14

A LGORITHMIC C HAINING AND THE ROLE OF PARTIAL F EEDBACK IN O NLINE N ONPARAMETRIC L EARNING

Yoav Freund and Robert E Schapire. A decision-theoretic generalization of on-line learning and an
application to boosting. Journal of Computer and System Sciences, 55(1):119–139, 1997.
Pierre Gaillard and Sebastien Gerchinovitz. A chaining algorithm for online nonparametric regression. In Proceedings of COLT’15, volume 40, pages 764–796. JMLR: Workshop and Conference
Proceedings, 2015.
Sébastien Gerchinovitz and Tor Lattimore. Refined lower bounds for adversarial bandits. In Advances in Neural Information Processing Systems 29 (NIPS’16), pages 1198–1206, 2016.
Elad Hazan. Introduction to online convex optimization. Foundations and Trends R in Optimization,
2(3-4):157–325, 2015.
Elad Hazan and Nimrod Megiddo. Online learning with prior knowledge. In International Conference on Computational Learning Theory (COLT’07), pages 499–513. 2007.
Robert Kleinberg. Nearly tight bounds for the continuum-armed bandit problem. In NIPS, volume 17, pages 697–704, 2004.
Robert Kleinberg, Aleksandrs Slivkins, and Eli Upfal. Multi-armed bandits in metric spaces. In
Proceedings of the fortieth annual ACM symposium on Theory of computing, pages 681–690.
ACM, 2008.
Tyler Lu, Dávid Pál, and Martin Pál. Contextual multi-armed bandits. In AISTATS, pages 485–492,
2010.
Odalric-Ambrym Maillard and Rémi Munos. Adaptive bandits: Towards the best history-dependent
strategy. In AISTATS, pages 570–578, 2011.
Michael Ostrovsky and Michael Schwarz. Reserve prices in Internet advertising auctions: a field
experiment. In ACM Conference on Electronic Commerce, pages 59–60, 2011.
Alexander Rakhlin and Karthik Sridharan. Online nonparametric regression with general loss functions. CoRR, abs/1501.06598, 2015.
Alexander Rakhlin and Karthik Sridharan. Bistro: an efficient relaxation-based method for contextual bandits. In Proceedings of the Twentieth International Conference on Machine Learning
(ICML), 2016.
Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari. Online learning via sequential complexities. Journal of Machine Learning Research, 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 adversarial contextual learning. In Proceedings of the Twentieth International Conference on Machine
Learning (ICML), 2016.
15

C ESA -B IANCHI G AILLARD G ENTILE G ERCHINOVITZ

Vladimir Vovk. Competing with wild prediction rules. Machine Learning, 69(2-3):193–212, 2007.

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
 distributions p1 , p2 , . . . where p1 is uniform and pt (i) is proP computes
portional to exp − ηt t−1
ℓ
(i)
for all actions i.
s
s=1
Lemma 8 The sequence p1 , p2 , . . . of probability distributions computed by Hedge when run on
K actions with learning rates η1 > η2 > · · · > 0 and losses ℓt (k) > 0 satisfies
T X
K
X
t=1 i=1

pt (i)ℓt (i) − min

k=1,...,K

T
X

ℓt (k) 6

t=1

T

K

t=1

i=1

1X X
ln K
pt (i)ℓt (i)2 .
ηt
+
ηT
2

Appendix B. Proof of Theorem 1
Proof Let Nt be the number of balls created by the ContextualExp algorithm after t rounds, Bs be
the s-th ball so created, being x̄s its center (x̄s is some past context), and Ts be the subsequence of
rounds t such that xt is handled by the s-th ball. Notice that Nt and Ts are deterministic quantities,
since the xt ’s are generated obliviously. Since f is 1-Lipschitz
and ℓt is also 1-Lipschitz, for all xt

handled by Bs , we can write ℓt f (xt ) − ℓt f (x̄s ) ≤ ε . Now fix any 1-Lipschitz policy f . For
each s = 1, . . . , NT , there exists ȳs ∈ Yε such that ρY ȳs , f (x̄s ) ≤ ε. Then we can write
E

" T
X
t=1

#

ℓt (b
yt ) −
=

T
X

t=1
NT
X


ℓt f (xt )

(4)

X 


E ℓt (b
yt ) − ℓt f (xt )

s=1 t∈Ts

=

NT X 

X




E ℓt (b
yt ) − ℓt ȳs + ℓt ȳs − ℓt (f (x̄s )) + ℓt (f (x̄s )) − ℓt (f (xt ))
s=1 t∈Ts

≤

NT X 
X



E ℓt (b
yt ) − ℓt ȳs + 2T ε .

(5)

s=1 t∈Ts

We now apply to each s = 1, . . . , NT the standard regret bound of Exp3 with learning rate η (e.g.,
(Bubeck and Cesa-Bianchi, 2012)) w.r.t. the best action ȳs . This yields
X 

 ln Kε η
+ |Ts | Kε ,
E ℓt (b
yt ) − ℓt ȳs 6
η
2

t∈Ts

implying
NT X 
X
 NT ln Kε η


E ℓt (b
yt ) − ℓt ȳs 6
+ T Kε .
η
2
s=1 t∈Ts

16

A LGORITHMIC C HAINING AND THE ROLE OF PARTIAL F EEDBACK IN O NLINE N ONPARAMETRIC L EARNING

q

Combining with (5), setting η = 2NTT KlnεKε , recalling that Kε 6 CY ε−p and observing that, by
the way balls are constructed, NT can never exceed the size of the smallest ε/2-cover of X (that is,
NT 6 CX (ε/2)−d ), we obtain
!
r
p
1
T ε−(d+p) ln + T ε .
RegT (F) 6 2 T NT Kε ln Kε + 2 T ε = O
ε
Setting ε =



p+d
2



ln T
T 1/2



2
p+d+2

 p+d+1 
e T p+d+2 as claimed.
gives RegT (F) = O

Appendix C. The Exp3-RTB algorithm for reserve-price optimization
√ 
e T can be achieved with high probCesa-Bianchi et al. (2015) showed that a regret of order O
ability 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 6 y 6 y + δ 6 1.

(6)

In each auction instance t = 1, 2, . . . , the learner selects a reserve price ybt ∈ Y = [0, 1] and suffers
the loss ℓt (b
yt ). The learner’s feedback is ℓt (y) for all y > ybt (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
#
" T
T
X
X
ℓt (b
yt ) − inf
ℓt (y) ,
RegT , E
06y61

t=1

t=1

where the expectation is with respect to the randomness in the predictions ybt . We introduce the
Exp3-RTBalgorithm (Algorithm 3 below), a variant of Exp3 (Auer et al., 2002) exploiting the richer
feedback ℓt (y) : y > ybt . The algorithm uses a discretization of the action space [0, 1] in
K = ⌈1/γ⌉ actions yk := (k − 1)γ for k = 1, . . . , K.

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


2 ln⌈1/γ⌉
1 e
.
+
RegT 6 γT 2 + ln
4 γ
γ
√ 
e T .
In particular, γ = T −1/2 gives RegT = O
17

C ESA -B IANCHI G AILLARD G ENTILE G ERCHINOVITZ

Algorithm 3: Exp3-RTB (for one-sided full information feedback)
Input
: Exploration parameter γ > 0.
Initialization: Set learning rate η = γ/2 and uniform distribution p1 over {1, . . . , K} where
K = ⌈1/γ⌉;
for t = 1, 2, . . . do
1. compute distribution qt (k) = (1 − γ)pt (k) + γIk=1 for k = 1, . . . , K;
2. draw It ∼ qt and choose ybt = yIt = (It − 1)γ;
3. for each k = 1, . . . , K, compute the estimated loss
ℓt (yk )
IIt 6k
ℓbt (k) = Pk
j=1 qt (j)

end

4. for each k = 1, . . . , K, compute the new probability assignment

P
exp − η ts=1 ℓbs (k)
 P
.
pt+1 (k) = P
K
t
bs (j)
exp
−η
ℓ
j=1
s=1

Proof The proof follows the same lines as the regret analysis of Exp3 in (Auer et al., 2002). The
key change is a tighter control of the variance term allowed by the richer feedback.
Pick any reserve price yk = (k − 1)γ. We first control the regret associated with actions drawn
from pt (the regret associated with qt will be studied as a direct consequence). More precisely, since
the estimated losses ℓbt (j) are nonnegative, we can apply Lemma 8 to get
T
X
t=1

pt · ℓbt −

T K
ln K
η XX
b
.
pt (j)ℓbt (j)2 +
ℓt (k) 6
2 t=1
η
t=1

T
X

(7)

j=1

Writing Et−1 [ · ] for the expectation conditioned on I1 , . . . , It−1 , we note that


Et−1 ℓbt (j) = ℓt (yj )

and


 pt (j)ℓt (yj )2
qt (j)
Et−1 pt (j)ℓbt (j)2 = Pj
6
,
P
(1 − γ) ji=1 qt (i)
i=1 qt (i)

where we used the definition of qt and the fact that |ℓt (yj )| 6 1 by assumption. Therefore, taking
expectation on both sides of (7) entails, by the tower rule for expectations,


#
" T
K
T
T
X
X
X
X
q
(j)
η
t
 + ln K .
E
ℓt (yk ) 6
p t · ℓt −
E
Pj
2(1 − γ)
η
i=1 qt (i)
t=1

t=1

t=1

18

j=1

A LGORITHMIC C HAINING AND THE ROLE OF PARTIAL F EEDBACK IN O NLINE N ONPARAMETRIC L EARNING

Setting st (j) ,
K
X
j=1

Pj

i=1 qt (i),

qt (j)

Pj

i=1 qt (i)

we can upper bound the sum with an integral,

=1+

K
X
st (j) − st (j − 1)

st (j)

j=2

61+

K Z
X
j=2

st (j)
st (j−1)

=1+

K Z
X
j=2

dx
=1+
x

Z

1
qt (1)

st (j)
st (j−1)

dx
st (j)

dx
1
6 1 − ln qt (1) 6 1 + ln ,
x
γ

where we used qt (1) > γ. Therefore, substituting into the previous bound, we get
#
" T
T
X
X
ηT ln(e/γ) ln K
ℓt (yk ) 6
p t · ℓt −
E
+
.
2(1 − γ)
η

(8)

t=1

t=1

We now control the regret of the predictions ybt = yIt , where It is drawn from qt = (1 − γ)pt + γδ1 .
By the tower rule,
" T
#
#
" T
T
T
X
X
X
X

ℓt (yk )
ℓt (yk ) = E
(1 − γ)pt · ℓt + γℓt (y1 ) −
ℓt (b
yt ) −
E
t=1

t=1

t=1

6 (1 − γ) E
6

"

T
X
t=1

p t · ℓt −

T
X
t=1

#

t=1

ℓt (yk ) + γT

ηT ln(e/γ) ln K
+
+ γT ,
2
η

(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 ∈ [yk , yk + γ], and since each ℓt satisfies the semi-Lipschitz
condition (6), we have ℓt (y) > ℓt (yk ) − γ. This gives
#
" T
T
X
X
ℓt (yk ) 6 min
min E
ℓt (y) + γ T .
k=1,...,K

06y61

t=1

t=1

Replacing the last inequality into (9), and recalling that K = ⌈1/γ⌉ and η = γ2 , finally yields
RegT 6

γT
e 2 ln⌈1/γ⌉
ln +
+ 2γT .
4
γ
γ

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, . . . , NT , we define the
constant approximation of f in the s-th ball by ysmin = mint∈Ts f (xt ). Since f is 1-Lipschitz and
19

C ESA -B IANCHI G AILLARD G ENTILE G ERCHINOVITZ

the balls have radius ε, we have maxt,t′ ∈Ts f (xt ) − f (xt′ ) ≤ 2ε. Hence, for all t ∈ Ts , by the
semi-Lipschitz property (6),

ℓt f (xt ) ≥ ℓt (ysmin ) − 2ε .
(10)
Therefore,
T
X
t=1

E[ℓt (b
yt )] −

T
X
t=1

NT X 
 X

ℓt f (xt ) =
E[ℓt (b
yt )] − ℓt f (xt )
s=1 t∈Ts

=

NT X 
NT X 
 X
X

ℓt (ysmin ) − ℓt f (xt )
E[ℓt (b
yt )] − ℓt (ysmin ) +
s=1 t∈Ts

≤ γT

|



{z

Rs

1 e
2 + ln
4 γ



+

}

s=1 t∈Ts

2NT ln⌈1/γ⌉
+ 2εT .
γ

Each term Rs is the regret suffered by the s-th instance of Exp3-RTB against the constantP
value ysmin ,
and so we bound it using Theorem 9 in Appendix C and then sum over s recalling that s Ts = T .
The other double sum is bounded by 2T ε using (10). We bound NT as in Theorem 1 obtaining


ε−d 1
1
ln + εT .
+
RegT (F) . γT 1 + ln
γ
γ
γ
Finally, choosing ε = γ = T −1/(d+2) 6 1 gives

concluding the proof.

 d+1 
e T d+2
RegT (F) = O

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
(Maillard and Munos, 2011). Namely, when the action It 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 qt ∈ ∆(N ). These coefficients are computed by Hedge
b
based on the expert losses ℓet (j) = ξt (j, ·) · ℓbt for j = 1, . . . , N , where
PNℓt is a vector of suitably
defined loss estimates. The distribution prescribed by Exp4 is pt = j=1 qt (j)ξt (j, ·) ∈ ∆(K),
but the learner’s play at time t is It ∼ p∗t for some other distribution p∗t ∈ ∆(K). The feedback at
time t is the vector of losses ℓt (i) for all i > It .

20

A LGORITHMIC C HAINING AND THE ROLE OF PARTIAL F EEDBACK IN O NLINE N ONPARAMETRIC L EARNING

Algorithm 4: Exp4 with unspecified sampling distributions p∗t (for one-sided full info feedback)
Input
: Learning rate sequence η1 > η2 > · · · > 0.
Initialization: Set q1 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 It ∼ p∗t and observe ℓt (i) for all i > It ;
4. compute loss estimates ℓbt (i) for i = 1, . . . , K;
5. compute expert losses ℓet (j) = ξt (j, ·) · ℓbt for j = 1, . . . , N ;
6. compute the new probability assignment


P
exp −ηt+1 ts=1 ℓes (j)


for each j = 1, . . . , N .
qt+1 (j) = P
Pt e
N
k=1 exp −ηt+1
s=1 ℓs (k)
end

In this setting, the goal is to minimize the regret with respect to the performance of the best
expert,
#
" T
T
X
X
ξt (j, ·) · ℓt
p t · ℓt −
max E
j=1,...,N

t=1

t=1

in expectation with respect to the random draw of I1 , . . . , IT , 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 I1 , . . . , It−1 .
For all k ∈ K let
k
X
p∗t (i) .
Pt∗ (k) =
i=1

Also, let Kt ≡ {k ∈ K : (∃j) ξt (j, k) > 0} (in chaining, Kt 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 max
ℓt (k) − ℓt (k′ ) 6 E .
′
t=1,...,T k,k ∈Kt

The rich feedback
structure (ℓt (k), k > It ) is crucial to get our result, since it enables us to use

ℓt max Kt in the definition of the loss estimates ℓbt (k) below. Indeed, as explained in Section 4.2,
ℓbt (k) has to be explicitly computed only for those actions k such that It 6 k and ξt (j, k) > 0 for
some j, i.e., k ∈ Kt . In this case, It 6 k 6 max Kt so that ℓt max Kt 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

21

C ESA -B IANCHI G AILLARD G ENTILE G ERCHINOVITZ

ℓ1 , ℓ2 , . . . with loss estimates


ℓt (k) − ℓt max Kt
b
ℓt (k) =
IIt 6k
Pt∗ (k)

for k = 1, . . . , K

and adaptive learning rate

ηt = min

(

γ
,
2E

s

2

)

2 − 1 (ln N )
(e − 2)Vet−1

√

for t > 2

(11)


P
PN
e
e 2 is the cumulative
for some parameter E > 0 and where Vet−1 = t−1
s=1
j=1 qs (j) ℓs (j) − qs · ℓs
variance of Hedge up to time t − 1. If p∗t (1) > γ and
max ℓt (k) − ℓt (k′ ) 6 E

max

t=1,...,T k,k ′ ∈Kt

almost surely for all t > 1, then, for all T > 1,
s
#
" T
T
X
X
E
T ln N
ξt (j, ·) · ℓt 6 4E
p t · ℓt −
max E
+ (4 ln N + 1) .
j=1,...,K
γ
γ
t=1

t=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 Kt and because Pt∗ (k) > p∗t (1) > γ,
max

i,j=1,...,N

ℓet (i) − ℓet (j) =

max

i,j=1,...,N

ξt (i, ·) · ℓbt − ξt (j, ·) · ℓbt

6 max
ℓbt (k) − ℓbt (k′ )
′
6

k,k ∈Kt

2E
2E
6
.
∗
mink∈K Pt (k)
γ

e = (2E)/γ is an upper bound on the size of the range of the losses ℓet (j), we can use
Since E
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
q
T
T
X
X
e
e
e
e ln N + E .
(12)
qt · ℓt 6 min
ℓt (j) + 4 (ln N )VeT + 2E
j=1,...,N
2
t=1

t=1

Note that qt · ℓet = pt · ℓbt . Moreover, Kt = max Kt is measurable with respect to (I1 , . . . , It−1 ),
implying Et−1 ℓbt (k) = ℓt (k)−ℓt (Kt ). Therefore, taking the expectation on both sides of (12) with
P P
respect to the random draw of I1 , . . . , IT , and using Jensen together with VeT ≤ Tt=1 N
j=1 qt (j) ·
2
ℓet (j) , we get
#
" T
T
X
X
ξt (j, ·) · ℓt
p t · ℓt −
max E
j=1,...,N

t=1

t=1

v


u
T
N
u


X
X
2
4E
E
u
qt (j) ξt (j, ·) · ℓbt  +
E
6 4t(ln N )
ln N + .
γ
γ
t=1
j=1

22

(13)

A LGORITHMIC C HAINING AND THE ROLE OF PARTIAL F EEDBACK IN O NLINE N ONPARAMETRIC L EARNING

The variance term inside the square root can be upper bounded as follows. Using Jensen again,
N
X
j=1

K
N
2 X

X
b
qt (j)
ξt (j, k)ℓbt (k)2
qt (j) ξt (j, ·) · ℓt 6

=

j=1

k=1

N
X

K
X

qt (j)

j=1

6

ξt (j, k)

k=1



ℓt (k) − ℓt (Kt )
Pt∗ (k)

2

IIt 6k

K
N
X
E2 X
ξt (j, k)
qt (j)
II 6k
γ
Pt∗ (k) t
j=1

k=1

where the last inequality is because ℓt (k) − ℓt (Kt ) 6 E when ξt (j, k) > 0 and because Pt∗ (k) >
p∗t (1) > γ. Therefore, recalling Pt∗ (k) = Pt−1 (It 6 k),


N
K
N
X
X
2
ξt (j, k)
E2 X
E2
Et−1 
qt (j) ξt (j, k) · ℓbt  6
qt (j)
P
(I
6
k)
=
.
t−1 t
γ
Pt∗ (k)
γ
j=1

j=1

k=1

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 pent ∈ RK measurable with respect to (I1 , . . . , It−1 ) at time t. Suppose
Exp4 (Algorithm 4) is run with one-sided full information feedback on an arbitrary loss sequence
ℓt ∈ RK , t > 1, with loss estimates

ℓt (k) − ℓt max Kt + E
b
IIt 6k + pent (k) + F
for k = 1, . . . , K
ℓt (k) =
Pt∗ (k)

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

max ℓt (k) − ℓt (k′ ) 6 E

and

t=1,...,T k,k ′ ∈Kt

max max pent (k) 6 F ,

t=1,...,T k∈Kt

then, for all T > 1,
max E

j=1,...,K

"

T
X
t=1



pt · ℓt + pent −

T
X

ξt (j, ·) · ℓt + pent

t=1
T
X
2

ln N
6
+ 4ηT F 2 + 4ηE
η

t=1

"

K
X
pt (k)
E
Pt∗ (k)
k=1

#

#


.

Proof From the definition of Kt and because E and F are upper bounds on the losses and penalties
associated with actions in Kt ,
min ℓet (j) =

j=1,...,N

min ξt (j, ·) · ℓbt > min ℓbt (k) > 0 .

j=1,...,N

k∈Kt

23

C ESA -B IANCHI G AILLARD G ENTILE G ERCHINOVITZ

We can thus use the regret bound for Hedge with weight vectors qt , constant learning rate η, and
nonnegative losses ℓet (k) (see Lemma 8 in Appendix A):
T
X
t=1

qt · ℓet 6

min

j=1,...,N

T
X
t=1

T

N

η XX
ln N
+
qt (j)ℓet (j)2 .
ℓet (j) +
η
2

(14)

t=1 j=1

Note that qt · ℓet = pt · ℓbt . Moreover,

 Kt = max Kt and pent are measurable with respect to
b
(I1 , . . . , It−1 ), implying Et−1 ℓt (k) = ℓt (k) − ℓt (Kt ) + E + pent (k) + F . Therefore, taking the
expectation on both sides of (14) with respect to the random draw of I1 , . . . , IT , we get
#
" T
T
X

 X
ξt (j, ·) · ℓt + pent
pt · ℓt + pent −
max E
j=1,...,N

t=1

t=1

6

ln N
η
+
η
2

T
X
t=1



N
2

X
qt (j) ξt (j, ·) · ℓbt  .
E

(15)

j=1

The variance term can be upper bounded as follows. Using Jensen’s inequality,
N
X
j=1

K
N
2 X

X
qt (j)
ξt (j, k)ℓbt (k)2
qt (j) ξt (j, ·) · ℓbt 6
j=1

=

N
K X
X

k=1

qt (j)ξt (j, k)

k=1 j=1



ℓt (k) − ℓt (Kt ) + E
IIt 6k + pent (k) + F
Pt∗ (k)

2

K
X
pt (k)
II 6k ,
6 8F + 8E
Pt∗ (k)2 t
2

2

k=1

where the last inequality is because ℓt (k) − ℓt (Kt ) 6 E and pent (k) 6 F when ξt (j, k) > 0
and because (a + b + c + d)2 6 4 a2 + b2 + c2 + d2 . Therefore, recalling Pt∗ (k) = Pt−1 (It 6 k),


N
K
X
X
2
pt (k)
Et−1 
qt (j) ξt (j, k) · ℓbt  6 8F 2 + 8E 2
.
Pt∗ (k)
j=1

k=1

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

∗
Note that when
p pent ≡ 0 and pt (1) > γ almost surelypfor all t > 1, Theorem 11 above used with
−1
η = (2E)
γ 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 pent (k) =
−α/Pt∗ (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 ∈ RK ,
t > 1, with loss estimates

ℓt (k) − ℓt max Kt + E
α
α
b
IIt 6k − ∗
+
for k = 1, . . . , K
ℓt (k) =
∗
Pt (k)
Pt (k) γ
24

A LGORITHMIC C HAINING AND THE ROLE OF PARTIAL F EEDBACK IN O NLINE N ONPARAMETRIC L EARNING

and constant learning rate η > 0. If we have, for all t > 1, almost surely,
max ℓt (k) − ℓt (k′ ) 6 E

max

t=1,...,T k,k ′ ∈Kt

and

p∗t (1) > γ ,

then, for all T > 1,
" T K
 X
#


T X
K
XX
α
α + 4ηE 2
−
ξt (j, k) ℓt (k) − ∗
max E
pt (k) ℓt (k) −
j=1,...,K
Pt∗ (k)
Pt (k)
t=1 k=1

t=1 k=1

6

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 TF .
Lemma 13 Let v ∈ T be any node at level m ∈ {0, 1, . . . , M − 1}. Then all leaves w, w′ ∈ Lv
satisfy fw − fw′ ∞ 6 2−m+2 . Therefore, ℓt (yit (w) ) − ℓt (yit (w′ ) ) 6 2−m+3 for all t > 1.

Proof Consider a path v = vm → vm+1 → · · · → vM = w joining v to leaf w in the tree. For each
k = m, . . . , M −1, since Fk is a (2−k )-covering of F in sup norm, we have kfvk −fvk+1 k∞ 6 2−k .
Therefore,
kfv − fw k∞ =

M
−1
X
k=m

(fvk − fvk+1 )

6
∞

M
−1
X
k=m

kfvk − fvk+1 k∞ 6

M
−1
X

2−k 6 2−m+1 .

k=m

Therefore, since
∈ Lv as well, kfw − fw′ k∞ = kfv − fw k∞ + kfv − fw′ k∞ 6 2−m+2 , which
proves the first inequality. Now, since ℓt is 1-Lipschitz,

ℓt (yit (w) ) − ℓt (yit (w′ ) ) 6 yit (w) , yit (w′ ) 6 2−M +1 + kfw − fw′ k∞

6 2−M +1 + 2−m+2 6 2−m+3
w′

where the second inequality uses the definition of it (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 Cv , where the advice of
w ∈ Cv is ξt (w, ·) = pt (w, ·), and effective action set Kt = {i : (∃w ∈ Cv ) pt (w, i) > 0} = Kt (v).
Note that, for any w ∈ Cv , the distribution pt (w, ·) is a mixture of actions in Lw ⊆ Lv , so that
Kt (v) ⊆ {it (w′ ) : w′ ∈ Lv }. 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 = |Cv | ≤ Nm+1 , and obtain the bound
s
#
" T
T
X
X
T ln Nm+1 2−m+3
+
(4 ln Nm+1 + 1)
pt (w, ·) · ℓt 6 2−m+5
pt (v, ·) · ℓt −
max E
w∈Cv
γ
γ
t=1

t=1

25

C ESA -B IANCHI G AILLARD G ENTILE G ERCHINOVITZ

(for simplicity, we use ℓt to denote the vector of elements ℓt (yi ) for i = 1, . . . , K). Now consider
the path v0 → v1 → · · · → vM = w∗ from the root v0 to the leaf vM = w∗ minimizing ℓ1 (yi1 (w) )+
· · · + ℓT (yiT (w) ) over w ∈ L. Recalling that pt (w, i) = Ii=it (w) for any leaf w, we get
E

" T
X
t=1

#

pt (v0 , ·) · ℓt − min

ℓt (yit (w) )
t=1
" T
M
−1
X
X

w∈L

=

T
X

E

m=0

6 25

t=1

M
−1
X

pt (vm , ·) · ℓt −
s

2−m

m=0

T
X
t=1

pt (vm+1 , ·) · ℓt

#

!
1
T ln Nm+1
+ (ln Nm+1 + 1) .
γ
γ

(16)

Now, recalling that It ∼ p∗t and p∗t (i)ℓt (yi ) = (1 − γ)pt (v0 , i)ℓt (yi ) + γ Ii=1 ℓt (y1 ) we get
)
#
( T
" T
T 
X
X
X


∗
ℓt (y1 ) − ℓt yit (w)
ℓt yit (w) + γ
E
pt · ℓt 6 min
w∈L

t=1

+ 25

M
−1
X

s

2−m

m=0

t=1

t=1

!
1
T ln Nm+1
+ (ln Nm+1 + 1) .
γ
γ


Now clearly ℓt (y1 ) − ℓt yit (w) 6 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 yit (w) − ℓt f (xt ) 6
yit (w) − f (xt ) 6 1 yit (w) − fw (xt ) + fw (xt ) − f (xt ) 6 21−M by definition of it (w). Hence,
E

" T
X
t=1

#

p∗t · ℓt − inf

f ∈F

T
X
t=1


ℓt f (xt )

6 (21−M + γ)T + 25

M
−1
X

2−m

m=0

s

!
T ln Nm+1
1
+ (ln Nm+1 + 1) .
γ
γ

(17)

We now use Nm+1 = N∞ (F, 2−(m+1) ), and follow the standard chaining approach approximating
the sums by integrals,
M
−1
X
m=0

−m

2

p

ln Nm+1 = 4
64

M
−1 
X

−(m+1)

2

m=0
M
−1 Z 2−(m+1)
X
m=0

2−(m+2)

−(m+2)

−2
p

q

ln N∞ (F, 2−(m+1) )

ln N∞ (F, ε)dε 6 4

Z

1/2 p

γ/2

ln N∞ (F, ε)dε

(18)

where the second inequality is by monotonicity of ε 7→ ln N∞ (F, ε) and the last inequality follows
from γ 6 2−M due to M = ⌊ln2 (1/γ)⌋. Similarly,
M
−1
X
m=0

−m

2

ln Nm+1 6 4

Z

26

1/2
γ/2

ln N∞ (F, ε)dε .

(19)

A LGORITHMIC C HAINING AND THE ROLE OF PARTIAL F EEDBACK IN O NLINE N ONPARAMETRIC L EARNING

We conclude the proof by substituting (18) and (19) into (17), and using 2−M 6 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

 q
1
1
T

+
ln
if d = 1
O

γ
γ

q γ

T
1
−2
RegT (F) 6 5T γ +
O
if d = 2
γ ln γ + γ


√


O T γ (1−d)/2 + γ −d if d > 3.
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
1-Lipschitz functions from [0, 1]d to [0, 1].
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 2md equal cubes of width 2−m . Each cube Xm (σ1:m ) ⊆
[0, 1]d at depth m is indexed by σ1:m = (σ1 , . . . , σm ) ∈ {1, . . . , 2d }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 Xm (σ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, . . . , 2d }.
They correspond to sub-cubes of Xm (σ1:m ).
Wavelet-like approximation of F. Using the above dyadic discretization P, we approximate any
f ∈ F with piecewise-constant functions fM : [0, 1]d → [−1/2, 3/2] of the form
fM (x) =

M
1 X
+
2 m=1

X

2−m cm (σ1:m ) Ix∈Xm (σ1:m )

σ1:m ∈{1,...,2d }m


where cm (σ1:m ) ∈ −1, 0, 1 . (20)


As shown in the next lemma, the functions fM form a 2−M -covering of F in the sup norm
kgk∞ = supx∈[0,1]d g(x) . We use the following important property: for any given x ∈ [0, 1]d ,
there exists a unique σ1:M ∈ {1, . . . , 2d }M such that x ∈ Xm (σ1:m ) for all m = 1, . . . , M , so that
M
1 X −m
fM (x) = +
2 cm (σ1:m ) .
2 m=1

(21)


Lemma 14 Let f ∈ F and M > 1. There exist coefficients cm (σ1:m ) ∈ −1, 0, 1 such that fM
defined in (20) satisfies kfM − f k∞ 6 2−M .

27

C ESA -B IANCHI G AILLARD G ENTILE G ERCHINOVITZ

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


(22)
fM xM (σ1:M ) − f xM (σ1:M ) 6 2−(M +1) .

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



fM (x) − f (x) 6 fM xM (σ1:M ) − f xM (σ1:M ) + f xM (σ1:M ) − f (x)
6 2−(M +1) + 2−(M +1) = 2−M .

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

c∈{−1,0,1}


1 c
+ − f x1 (σ1 ) ,
2 2

which corresponds to projecting the value of f at the center x1 (σ1 ) onto the coarse grid {0, 1/2, 1}.
Therefore 1/2 + c1 (σ1 )/2 − f (x1 (σ1 )) 6 1/4, which implies (22) by (21).
Now, let M > 2 and assume that there exist coefficients cm (σ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
σ1:M ∈ {1, . . . , 2d }M , we set


c
cM (σ1:M ) ∈ arg min fM −1 xM (σ1:M ) + M − f xM (σ1:M ) .
2
c∈{−1,0,1}
Note that by (21) and xM (σ1:M ) ∈ XM (σ1:M ) ⊂ XM −1 (σ1:(M −1) ), we have
 cM (σ1:M )

.
fM xM (σ1:M ) = fM −1 xM (σ1:M ) +
2M

(23)

Therefore, the definition of cM (σ1:M ) above corresponds to making fM xM (σ1:M ) as close to
f xM (σ1:M ) as possible. Now, note that fM −1 is constant over XM −1 (σ1:(M −1) ), so that the


difference ∆M −1 , fM −1 xM (σ1:M ) − f xM (σ1:M ) satisfies


∆M −1 = fM −1 xM −1 (σ1:(M −1) ) − f xM (σ1:M )




6 fM −1 xM −1 (σ1:(M −1) ) − f xM −1 (σ1:(M −1) ) + f xM −1 (σ1:(M −1) ) − f xM (σ1:M )
(22)

6 2−M + xM −1 (σ1:(M −1) ) − xM (σ1:M )

∞

= 2−M + 2−(M +1) ,

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 ∆M −1 6 2−M +2−(M +1) implies the existence


of cM (σ1:M ) ∈ {−1, 0, 1} such that fM xM (σ1:M ) − f xM (σ1:M ) 6 2−(M +1) , as required
to finish the induction. We can indeed consider three possible cases. If ∆M −1 6 2−(M +1) , then
setting cM (σ 1:M ) = 0 concludes the proof
(by (23)). If ∆M −1 > 2−(M +1) , then ∆M −1 lies in

the interval 2−(M +1) , 2−M + 2−(M +1) , so that setting cM (σ1:M ) = −1 also concludes the proof
(using (23) again). Similarly we set cM (σ1:M ) = 1 when ∆M −1 < −2−(M +1) .
We are now ready to define our hierarchical covering of F.
28

A LGORITHMIC C HAINING AND THE ROLE OF PARTIAL F EEDBACK IN O NLINE N ONPARAMETRIC L EARNING

Construction of TF⋆ . We build a tree TF⋆ such that the value of any function fM 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
TF⋆ . Unlike Section 4.2, this tree is not labeled by functions but instead by either values in R or
cubes Xm (σ1:m ) ⊆ [0, 1]d , as illustrated in Figure 3. More precisely, our tree TF⋆ is composed of
two types of nodes:
• Nodes at depths m. The root v0 = ∅ (at depth m = 0) is labeled by 1/2. Each node at depth
m = 1, 2, . . . is indexed by a tuple (σ1 , c1 , σ2P
, c2 , . . . , σm , cm ) with σk ∈ {1, . . . , 2d } and
−k
ck ∈ {−1, 0, 1}; the node is labeled by 1/2 + m
k=1 2 ck , 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 , c1 , σ2 , c2 , . . . , σm , cm , σm+1 ) with σk ∈ {1, . . . , 2d } and ck ∈ {−1, 0, 1}; the node is
labeled by the cube Xm (σ1:m+1 ).

We connect nodes in the following natural way. Nodes v = (σ1 , c1 , σ2 , c2 , . . . , σm , cm ) at depth m
are connected to all nodes at depth m + 1/2 of the form (v, σm+1 ), with σm+1 ∈ {1, . . . , 2d }.
Nodes w = (σ1 , c1 , σ2 , c2 , . . . , σm , cm , σm+1 ) at depth m + 1/2 are connected to all nodes at depth
m + 1 of the form (w, cm+1 ), with cm+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 TF⋆ ,
by Lv the set of all the leaves under v ∈ TF⋆ , and by Cv the set of children of v ∈ TF⋆ .
1
2

depth

0

depth

0+

depth

1

depth

1+

binning
Exp4 0, 12


[ 12 , 1[



1
2

0

1

Exp4

1
2

0

1

[0, 41 [

[ 41 , 12 [

[0, 14 [

[ 14 , 12 [

[0, 41 [

[ 14 , 21 [

[ 12 , 43 [

[ 43 , 1]

[ 12 , 43 [

[ 43 , 1]

[ 21 , 34 [

[ 34 , 1]

..
.

..
.

..
.

..
.

..
.

..
.

..
.

..
.

..
.

..
.

..
.

..
.

1
2

1
2

Figure 3: The structure of the efficient chaining tree in dimension d = 1.
Algorithm HierExp4⋆ . Our new bandit algorithm HierExp4⋆ (Algorithm 5) is an efficient modification of HierExp4 based on the tree TF⋆ 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 Y = [0, 1] with
K = k2−M : k = 1, . . . , 2M } of cardinality K = 2M . Note that, af −M
ter projecting onto 2 , 1 , the set of labels of all the leaves v ∈ L exactly corresponds to this
discretization, i.e.,
! !
) 
(

M
1
k
1 X −m
M
2 cm , M , 1 : cm ∈ {−1, 0, 1} =
+
: k = 1, . . . , 2
= K.
min max
2 m=1
2
2M
At every round t, after observing
context xt ∈ [0, 1]d , the algorithm activates the root v0 and all

nodes σ1 , c1 , . . . , σm (, cm ) such that xt ∈ Xm (σ1:m ); the other nodes are asleep during that
round. In particular, there are 3M activated leaves v = (σ1 , c1 , . . . , σM , cM ) ∈ L. Each such leaf
29

C ESA -B IANCHI G AILLARD G ENTILE G ERCHINOVITZ



recommends the action it (v) ∈ {1, . . . , K} matching its label after projection onto 2−M , 1 , i.e.,
such that
! !
M
it (v)
1
1 X −m
2 cm , M , 1 .
= min max
+
(24)
2M
2
2
m=1

TF⋆

Each node v ∈
maintains a probability distribution pt (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
pt (v, i) = Ii=it (v) . As mentioned earlier, the internal nodes v ∈ TF⋆ \ L are of two types:
• Each internal node v = (σ1 , c1 , σ2 , c2 , . . . , σm , cm ) at depth m = 0, . . . , M − 1 is a “binning
node". When activated, it identifies its only child w = (v, σm+1 ) handling xt (i.e., such that
xt ∈ Xm+1 (σ1:(m+1) )) and outputs pt (v, ·) = pt (w, ·). We denote by Tbin ⊂ TF⋆ \ L the set
of “binning nodes".

• Each internal node v = (σ1 , c1 , σ2 , c2 , . . . , σm , cm , σ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 Exp4v be the instance of the Exp4 variant run at node v. On all the rounds t
when v is activated, thisP
instance updates a distribution qt (v, ·) ∈ ∆(|Cv |) over experts in Cv
and outputs pt (v, i) = w∈Cv qt (v, w)pt (w, i) for all actions i = 1, . . . , K. We denote by
TExp4 ⊂ TF⋆ \ L the set of “Exp4 nodes".
Note that the root v0 of TF⋆ is activated at all rounds t. The prediction of HierExp4⋆ at time t is
ybt = It 2−M ∈ K, where It is drawn according to a mixture of pt (v0 , ·) 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 ∈ TExp4 , with depth m + 1/2, m ∈ {0, . . . , M − 1}. Then, all leaves w, w′ ∈ Lv
in the subtree rooted at v satisfy




it (w)
it (w′ )
ℓt
6 21−m
− ℓt
2M
2M
at all rounds t > 1 when w and w′ are both activated.
′ , c′ ). First, we remark that
Proof Denote w = (σ1 , c1 , . . . , σM , cM ) and w′ = (σ1′ , c′1 , . . . , σM
M
since w and w′ have the common ancestor v at level m, we have σi = σi′ and ci = c′i for all i 6 m,
′
as well as σm+1 = σm+1
(recall that v ∈ TExp4 ). Thus,
M
X
j=1

−j

2

cj −

M
X
j=1

2−j c′j

6

M
X

j=m+1

−j

2 |cj −

30

c′j |

6

M
X

j=m+1

2−j+1 6 21−m .

A LGORITHMIC C HAINING AND THE ROLE OF PARTIAL F EEDBACK IN O NLINE N ONPARAMETRIC L EARNING

Algorithm 5: HierExp4⋆ (for the one-sided full information feedback)
Input
: Tree TF⋆ with root v0 and leaves L, exploration parameter γ ∈ (0, 1), penalization
parameters α0 , . . . , αM −1 > 0, learning rates η0 , . . . , ηM −1 > 0.
Initialization: Set q1 (v, ·) to the uniform distribution in ∆(|Cv |) for every v ∈ TExp4 .
for t = 1, 2, . . . do
1. Get context xt ∈ X ;

2. Activate v0 and all nodes v = σ1 , c1 , . . . , σm (, cm ) ∈ TF⋆ such that xt ∈ Xm (σ1:m );
3. Set pt (v, i) = Ii=it (v) for all i ∈ K and all activated leaves v ∈ L;
4. Set pt (v, i) = qt (v, ·) · pt (·, i) for all i ∈ K and all activated nodes v ∈ TExp4 ;
5. Set pt (v, ·) = pt (w, ·) for all activated nodes v ∈ Tbin , where w ∈ Cv is the unique activated
child of v;
6. Draw It ∼ p∗t and play ybt = It 2−M , where p∗t (i) = (1 − γ)pt (v0 , i) + γIi=1 for all i ∈ K;
7. Observe ℓt (y) for all y > ybt ;
8. For all m = 0, . . . , M − 1 and all activated nodes v ∈ TExp4 at level m + 1/2, with
v = (σ1 , c1 , σ2 , c2 , . . . , σm , cm , σm+1 ), compute the loss estimate for each i ∈ Kt (v),

ℓt (i/2M ) − ℓt jt (v)/2M + 21−m
αm
αm
b
,
(25)
IIt 6i − Pi
+
ℓt (v, i) =
Pi
∗
∗
γ
k=1 pt (k)
k=1 pt (k)
where Kt (v) = {i : (∃w ∈ Cv ) pt (w, i) > 0} and jt (v) = max Kt (v).
Then, for each w ∈ Cv , compute the expert loss ℓet (v, w) = pt (w, ·) · ℓbt (v, ·) and perform the
update

qt+1 (v, w) =

exp −ηm

X

w ′ ∈Cv

t
X
s=1

exp −ηm

end

ℓes (v, w)Ixs ∈Xm+1 (σ1:(m+1) )

t
X
s=1

!

ℓes (v, w )Ixs ∈Xm+1 (σ1:(m+1) )
′

!.

(26)

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

M

j=1

j=1

it (w) it (w′ )
1 X −j
1 X −j ′
6
2
c
−
2 cj 6 21−m ,
−
+
−
j
2M
2M
2
2

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 fM : [0, 1]d → −1/2, 3/2 of the

form (20), with coefficients cm (σ1:m ) ∈ −1, 0, 1 , and such that kfM − f k∞ 6 2−M .
In the proof of Theorem 4, we rewrite the regret with respect to fM as the sum of M regrets
along the path joining the root of TF to the leaf corresponding to fM . Next, we proceed similarly
except that now fM corresponds to a (2d )-ary subtree of TF⋆ indexed by σ1:M ∈ {1, . . . , 2d }M . The
31

C ESA -B IANCHI G AILLARD G ENTILE G ERCHINOVITZ


2dM leaves σ1 ,c1 (σ1 ), σ2 , c2 (σ1:2 ), . . . , σM , cM (σ1:M ) are labeled with the values of fM (before
projecting onto 2−M , 1 ) over the cubes XM (σ1:M ).
We control the regret of HierExp4⋆ with respect to fM by starting from the root v0 of TF⋆ and
by progressively moving
down the tree. We write Pt−1 and Et−1 for conditioning on I1 , . . . , It−1 ,
Pk
∗
∗
and set Pt (k) , i=1 pt (i) = Pt−1 (It 6 k). In the sequel, we repeatedly use Corollary 12 with
parameters Em , 21−m , αm and γ to control the regret on each “Exp4 node". This corollary applies
to loss estimates penalized with pent (k) = −αm /Pt∗ (k) for “Exp4 nodes" at depth m + 1/2, with
m = 0, . . . , M − 1.
Since the root v0 is a “binning node", we have pt (v0 ,k) = pt (σ1 , k) at all rounds t such that
xt ∈ X1 (σ1 ). Therefore, writing ℓt (k) instead of ℓt k/2M ,
"

#
α0 + 4η0 E02
E
pt (v0 , k) ℓt (k) −
Pt∗ (k)
t=1 k=1




K
2
X
X
X
α0 + 4η0 E0 
pt (σ1 , k) ℓt (k) −
=
E
Pt∗ (k)
t: xt ∈X1 (σ1 ) k=1
σ1 ∈{1,...,2d }


K
X
X
X


pt (σ1 , c1 ), k ℓt (k) −
6
min E


T X
K
X

σ1 ∈{1,...,2d }

6

X
σ1



E

c1 ∈{−1,0,1}

t: xt ∈X1 (σ1 ) k=1

ln 3 4η0 T (σ1 )α20
+
+
η0
γ2

X

K
X

t: xt ∈X1 (σ1 ) k=1

!


pt [σ1 , c1 (σ1 )], k ℓt (k) −






α0

Pt∗ (k)
(27)





2
d
α0
 + 2 ln 3 + 4η0 T α0 ,
Pt∗ (k)
η0
γ2

(28)

where (27) follows from Corollary 12 with parameters E0 = 2, α0 and γ, and where T (σ1 ) is
the number of rounds t such that xt ∈ X1 (σ1 ). Indeed, the probability distributions pt (σ1 , c1 ), ·
are mixtures of actions it (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
c1 = c1 (σ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 22−2m =

32

A LGORITHMIC C HAINING AND THE ROLE OF PARTIAL F EEDBACK IN O NLINE N ONPARAMETRIC L EARNING

2 , we get
αm + 4ηm Em
" T K
#

XX
α0 + 4η0 E02
E
pt (v0 , k) ℓt (k) −
Pt∗ (k)
t=1 k=1




K
X
X
X

α
M −1 
6
E
pt [σ1 , c1 (σ1 ), . . . , σM , cM (σ1:M )], k ℓt (k) − ∗
P
t (k)
σ1:M
t: xt ∈X1 (σ1:M ) k=1
!
M
−1
X
2(m+1)d ln 3 4ηm T α2m
+
+
ηm
γ2
m=0


!
M
−1
(m+1)d ln 3
2
X
X
X

2
4η
T
α
m
m

ℓt it (v)  +
6
+
,
(29)
2
η
γ
m
σ
m=0
t: xt ∈X1 (σ1:M )

1:M


where in the last inequality v denotes the leaf σ1 , c1 (σ1 ), . . . , σM , cM (σ1:M ) , whose probability
distribution pt (v, ·) is the unit mass on its action it (v).



We define feM (x) , min max fM (x), 2−M , 1 to be the projection of fM (x) onto 2−M , 1 ,
 
and, similarly, fe(x) , min max f (x), 2−M , 1 . Since projection can only reduce the distance
between two points, feM (x) − fe(x) 6 fM (x) − f (x) 6 kfM − f k∞ 6 2−M . But, noting that
fe(x) is 2−M -close to f (x) ∈ [0, 1], this yields feM (x)−f (x) 6 feM (x)− fe(x) + fe(x)−f (x) 6
21−M . Therefore, since ℓt is 1-Lipschitz, and using both (21)
 and the definition (24) of it (v), we
get that, when the leaf v = σ1 , c1 (σ1 ), . . . , σM , cM (σ1:M ) is activated,




ℓt it (v) = ℓt feM (xt ) 6 ℓt f (xt ) + feM (xt ) − f (xt ) 6 ℓt f (xt ) + 21−M .

We plug
 last bound into (29) and multiply the resulting inequality by 1 − γ. Then, using
 the
Et−1 ℓt ybt = (1 − γ)pt (v0 , ·) · ℓt + γℓt (1), together with ℓt (y) ∈ [0, 1], we obtain
#
!
" T K
M
−1
X
XX
2(m+1)d ln 3 4ηm T α2m
α0 + 4η0 E02
RegT (F) 6
+
+ (1 − γ) E
pt (v0 , k)
ηm
γ2
Pt∗ (k)
m=0
t=1
k=1

1−M

+ γT + 2

T.

(30)

Now, we use that by definition p∗t (k) = (1 − γ)pt (v0 , k) + γIk=1 > (1 − γ)pt (v0 , k). Therefore,
similarly to the analysis of Exp3-RTB, we can control the variance term
(1 − γ)

K
K
K Z P ∗ (k)
X
X
X
t
p∗t (k)
Pt∗ (k) − Pt∗ (k − 1)
dx
=
1
+
=
1
+
∗
∗
∗
∗ (k)
∗
Pt (k)
Pt (k)
Pt (k)
P
k=1
k=2
k=2 Pt (k−1) t
Z 1
K Z P ∗ (k)
X
t
dx
1
e
dx
=1+
6 1 − ln Pt∗ (1) 6 1 + ln = ln ,
61+
γ
γ
Pt∗ (1) x
Pt∗ (k−1) x

K
X
pt (v0 , k)
k=1

6

k=2

where we used Pt∗ (1) = p∗t (1) > γ. Hence, substituting into the previous bound (30) and recalling
that E0 = 2, we get
!
M
−1
e
X
2(m+1)d ln 3 4ηm T α2m
+ γT + 21−M T . (31)
+
+
(α
+
16η
)T
ln
RegT (F) 6
0
0
ηm
γ2
γ
m=0

33

C ESA -B IANCHI G AILLARD G ENTILE G ERCHINOVITZ

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
2 =
will sometimes write f . g instead of f = O(g). First, recall that αm−1 = αm + 4ηm Em
αm + 24−2m ηm . We thus make the approximation αm ≈ 24−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
2(m+1)d ln 3
4ηm T α2m
=
ηm
γ2
which we approximate, using the previous remark, by
3
2md
T 2−4m ηm
≈
ηm
γ2

d

1

1

ηm = c2m( 4 +1) γ 2 T − 4 ,

hence our choice

(32)

where c > 0 will be optimized by the analysis. Now, from these values of ηm , we can compute αm
by choosing αM = 0 and using the recursion αm−1 = αm + 24−2m ηm . This yields
αm =

M
X

M
X

1

1

24−2j ηj = c24 γ 2 T − 4

d

2j( 4 −1) .

(33)

j=m+1

j=m+1

We now upper bound (31) by distinguishing between the two cases 1 6 d 6 4 and d > 4.
• If d 6 4, then the terms inside the sum in (33) are non-increasing, so that
1

1

d

αm 6 c24 M1 γ 2 T − 4 2m( 4 −1) ,

(34)

where M1 = M if 2 6 d 6 4 and M1 = 2 > 1/ 21−d/4 − 1 if d = 1. The sum in the
right-hand side of (31) then becomes, by substituting the definition of ηm (see (32)) and the
above upper bound on αm ,
! M −1
!
M
−1
X 2m( 34 d−1)+d T 14 ln 3 210 c3 M 2 2m( 3d4 −1) T 41
X
2(m+1)d ln 3 4ηm T α2m
1
+
6
+
1
1
2
η
γ
2
m
cγ
γ2
m=0
m=0
=

 2d ln 3
c

(∗)

1

−1
 1 1M
X
3
+ 210 M12 c3 T 4 γ − 2
2m( 4 d−1)
m=0

1

1

6 27 M12 T 4 γ − 2

6

(

M
−1
X

3

2m( 4 d−1)

m=0

211 T

1
4

γ

3
27 M 2 T

− 12
1
4

γ

− 21 M ( 34 d−1)

2

if d = 1
if 2 6 d 6 4
−1/2

where inequality (∗)Pis by using d 6 4 and choosing c = 2−5/4 M1
, while the last in−m/4 6 23 for d = 1. Plugging this inequality into (31), upper
equality is because ∞
2
m=0
bounding α0 using (34) and η0 using (32), and recalling that M = ⌈ln2 (1/γ)⌉, we get
– case d = 1: choosing γ = T −1/2 / ln(T ),
RegT (F) = O
34

√


T ln T .

(35)

A LGORITHMIC C HAINING AND THE ROLE OF PARTIAL F EEDBACK IN O NLINE N ONPARAMETRIC L EARNING

– case 2 6 d 6 4: choosing γ = T −1/(d+2/3) ,
3

1

1

1

3

3

RegT (F) . ln(1/γ) 2 T 4 γ − 2 γ −( 4 d−1) + ln(1/γ)2 γ 2 T 4 + γT
3d/4

d−1/3

3

d−1/3

3

d−1/3

. (ln T ) 2 T d+2/3 + (ln T )2 T d+2/3 + T d+2/3 . (ln T ) 2 T d+2/3 ,

(36)

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
d

2 4 −1

1
1
d
1
d
1
c24
γ 2 T − 4 2M ( 4 −1) 6 c27 γ 2 T − 4 2M ( 4 −1) .
d
−1/4
−1
1−2
24 − 1
(37)
Then, following the lines of the case d 6 4, by substituting ηm (see (32)) and αm in the sum
in the right-hand side of (31)
!
M
−1
X
2(m+1)d ln 3 4ηm T α2m
+
ηm
γ2
m=0
!
3
d
1
1
d
M
−1
X
2m( 4 d−1)+d T 4 ln 3 216 c3 2m( 4 +1)+M ( 2 −2) T 4
6
+
1
1
cγ 2
γ2
m=0
!
1
M −1
M
−1
X
d
d
T 4 2d ln 3 X m( 3 d−1)
2 4
= 1
2m( 4 +1)
+ 216 c3 2M ( 2 −2)
c
2
γ
m=0
m=0

1 
4+d
3d
3
T4 2
2M ( 4 d−1) + 216 c3 2M ( 4 −1)
6 1
c
γ2

1 
3
T 4 24+d
16 3
= 1
+ 2 c 2M ( 4 d−1)
c
γ2

4

1
2

αm 6 c2 γ T

− 14 M ( d4 −1)

2

1

1

6

3

3

6 T 4 γ − 2 2M ( 4 d−1)+8+ 4 d
where in the last inequality we used c = 2d/4−3 . Plugging into the regret bound (31), upper
bounding α0 using (37) and η0 using (32), and recalling that M = ⌈ln2 (1/γ)⌉, we get
1

1

3

3

d

3

RegT (F) . T 4 γ 2 − 4 d + γ 2 − 4 T 4 ln(1/γ) + γT
d−1/3

d−1

d−1/3

d−1/3

. T d+2/3 + T d+2/3 ln(T ) + T d+2/3 . T d+2/3 , (38)
where the second inequality is by setting γ = T −1(d+2/3) .
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 TF⋆ is
TExp4 =
=

M
−1
X

m=0
M
−1
X
m=0

n
o
v = (σ1 , c1 , σ2 , c2 , . . . , σm , cm , σm+1 ) : σk ∈ {1, . . . , 2d }, ck ∈ {−1, 0, 1}

3m 2d(m+1)

M +1

− 3 · 2d
1 3 · 2d
d M

=
6
3
·
2
.
3
3 · 2d − 1
35

C ESA -B IANCHI G AILLARD G ENTILE G ERCHINOVITZ

M
M
Similarly, Tbin 6 3 · 2d
and L 6 3 · 2d . Summing the three upper bounds, we get
M
TF⋆ 6 3 3 · 2d . Therefore, using M = ⌈ln2 (1/γ)⌉ and γ = T −1/(d+2/3) , we obtain
 d+ln 3 
2
ln2 T
⋆
so that
TF = O T d+2/3 .
M 61+
d + 2/3
1

The number of actions in K is 2M = O T 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) ∈ TF⋆ × K and w ∈ Cv , is at most

of the order of TF⋆ × K × max 2d , 3 . Therefore, the running time is at most of the order of

T

d+1+ln2 3
d+2/3

6 T 1.8 for all d > 2.

d+1+ln2 3

A tighter analysis however yields a smaller time complexity than the rate T 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
M
−1
X
3M − 1
3m =
2
m=0
1+ln2 3

so that the running time per round is at most of the order of 3M 2M . T d+2/3 , which concludes
the proof for d > 2. Similarly, in the case d = 1, the choice of γ = T −1/2 /(ln T ) entails a running
 1+ln2 3 
√

time at most of the order of 3M 2M = O T ln T )1+ln2 3 = o T 1+2/3 , 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 pt (v, ·) ∈ ∆(K) is computed
by Hedge and is supported on the set {it (w) : w ∈ Lv }. 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) with N = |Cv | 6 Nm+1 , E = 2−m+3 , and Vet 6 E 2 obtaining
#
" T
T

p
X
X
T ln Nm+1 + ln Nm+1 + 1 .
pt (w, ·) · ℓt 6 2−m+5
pt (v, ·) · ℓt −
max E
w∈Cv

t=1

t=1

As in the proof of Theorem 4, we sum the above along a path v0 → v1 → · · · → vM = w for any
leaf w ∈ L and get
#
" T
M
−1
T
p

X
X
X
2−m
ℓt (it (w)) 6 25
pt (v0 , ·) · ℓt − min
E
T ln Nm+1 + ln Nm+1 + 1 .
t=1

w∈L

m=0

t=1

36

A LGORITHMIC C HAINING AND THE ROLE OF PARTIAL F EEDBACK IN O NLINE N ONPARAMETRIC L EARNING

Algorithm 6: HierHedge (for the full information feedback)
Input
: Tree TF with root v0 and leaves L, learning rate sequences
η2 (v) > η3 (v) > · · · > 0 for v ∈ TF \ L.
Initialization: Set q1 (v, ·) to the uniform distribution in ∆(|Cv |) for every v ∈ TF \ L.
for t = 1, 2, . . . do
1. Get context xt ∈ X ;
2. Set pt (v, i) = Ii=it (v) for all i = 1, . . . , K and for all v ∈ L;
3. Set pt (v, i) = qt (v, ·) · pt (·, i) for all i = 1, . . . , K and for all v ∈ TF \ L;
4. Draw It ∼ pt (v0 , ·);
5. Observe ℓt (i) for all i = 1, . . . , K;
6. For each v ∈ TF \ L and for each w ∈ Cv compute the expert loss ℓet (v, w) = pt (w, ·) · ℓt
and perform the update


P
exp −ηt+1 (v) ts=1 ℓes (v, w)


qt+1 (v, w) = P
(39)
Pt e
′)
exp
−η
(v)
ℓ
(v,
w
′
t+1
s
s=1
w ∈Cv
end

Since L is a (2−M )-covering of F, 2−M ≤ 2ε, and Kε is a ε-covering of Y, we get
#
" T
M
−1
T
p

X
X
X


T ln Nm+1 + ln Nm+1 + 1 .
2−m
ℓt f (xt ) 6 5εT + 25
E
ℓt yIt − inf
t=1

f ∈F

m=0

t=1

Overapproximating the sums with integrals similarly to (18) and (19),
RegT (F) 6 5εT + 27

Z


p
2 T ln N∞ (F, x) + ln N∞ (F, x) dx .

1/2 

ε/2

d
p
d
If F is a set of Lipschitz functions f : [0,
 1] → [0, 1] , where [0, 1] is endowed with the norm
′
−d
kx − x k∞ , then ln N∞ (F, ε) = O pε
implying



√
 O √pT + p ln(1/ε)
 if d = 1
1−d
O pT ln(1/ε) + pε  if d = 2
RegT (F) 6 5T ε +
√

O pT ε1−d/2 + pε1−d
if d > 3.

Optimizing in ε, we obtain the stated result.

37

