arXiv CSopen access

Leveraging Similarities in Multi-Armed Bandits

Leveraging Similarities in Multi-Armed Bandits Khaled Eldowa

KHALED . ELDOWA @ INRIA . FR

Univ. Grenoble Alpes, Inria, CNRS, Grenoble INP, LJK, 38000 Grenoble, France

Thibaud Rahier

T. RAHIER @ CRITEO . COM

Criteo AI Lab, Paris, France

Augustin Cablant

AUGUSTIN . CABLANT @ INRIA . FR

arXiv:2606.23414v1 [cs.LG] 22 Jun 2026

Univ. Grenoble Alpes, Inria, CNRS, Grenoble INP, LJK, 38000 Grenoble, France

Panayotis Mertikopoulos PANAYOTIS . MERTIKOPOULOS @ IMAG . FR Univ. Grenoble Alpes, Inria, CNRS, Grenoble INP, LIG, 38000 Grenoble, France Pierre Gaillard

PIERRE . GAILLARD @ INRIA . FR

Univ. Grenoble Alpes, Inria, CNRS, Grenoble INP, LJK, 38000 Grenoble, France

Abstract In many online learning and bandit problems, the actions we consider possess inherent similarities–for instance because they share latent traits, tags, or hierarchical structure. We study online learning with a similarity-structured action set, encoded by a rooted tree whose leaves are the actions and whose levels quantify how closely two actions are related. The loss sequence is assumed tree-compatible: losses of similar actions are constrained to be close. We establish an impossibility result showing that usual one-point bandit feedback cannot, in general, leverage range or tree-induced similarity, even under very strong similarity constraints. We then provide a unified set of algorithms which adapt to a wide range of richer feedback models, from semi-bandit feedback down to multi-point bandit protocols, including the minimal two-point feedback setting. We show these algorithms exhibit best-of-both-worlds guarantees and provably exploit action similarities by replacing the number of actions K by a similarity-aware effective number of actions Keff in the regret bounds. As an application, we show that under two-point feedback, it is possible to achieve √ T regret in Lipschitz bandits when d ≤ 2. Keywords: Online Learning, Structured Bandits, Multi-Point Feedback, Best-of-Both-Worlds.

1. Introduction Consider the following recommendation problem: An ad placement platform has a catalogue of products—let’s say cars for concreteness—and is called to make product recommendations to a stream of users connecting to the system. This catalogue may have an innate structure: for example, cars may be classified according to brand (Ford, Chevrolet, Toyota, Peugeot,. . . ), type (SUVs, compacts, minivans,. . . ), propulsion (gas, hybrid, or electric), and/or any other relevant trait. In turn, this categorization across different traits (brand, type, propulsion, . . . ) may have a commensurate effect on the value of each product: thus, a user looking to buy a large family car might have a relatively high value for all mid-size cars in the catalogue, a somewhat lower value for SUVs, and a far lower value for compacts; and, depending on the user’s criteria on the catalogue’s other traits, this could further constrain the value range of each combination of traits. Seen as a repeated decision problem, the learner here seeks to minimize their regret in the presence of a large number of distinct alternatives, some of which may be more “similar” than others. These similarities are defined by means of a family of traits which group together alternatives © K. Eldowa, T. Rahier, A. Cablant, P. Mertikopoulos & P. Gaillard.

E LDOWA R AHIER C ABLANT M ERTIKOPOULOS G AILLARD

that share a given attribute (or more). More precisely, each trait gives rise to a partition of the set of possible choices, and each partition (or combination thereof) might greatly constrain the range of rewards that can be observed within: for instance, the value of two hybrid SUVs of the same make and model but different year would be highly correlated; by contrast, the rewards associated to a hybrid compact and a hybrid SUV of different make could diverge considerably. A natural goal here is to determine the degree to which such innate similarities within the set of alternatives may lead to improved regret guarantees, and how to achieve them. A natural way to operationalize such a structure is to encode it as a hierarchy, i.e., a treestructured notion of similarity over the alternatives. This presupposes fixing a priority ranking over the traits; e.g., 1) brand, 2) type, 3) propulsion, etc. Then, the traits from the first up to, say, the n-th collectively partition the alternatives, with each set of this partition corresponding to a possible combination of domain values that this group of traits can take. This partition in turn refines the one induced by the traits from 1 up to n − 1. Returning to our example, the combination of “brand” and “type” partitions the set of alternatives (here, cars) into “Ford sedans”, “Ford SUVs”, “Toyota sedans”, etc; which is a refinement of the partition induced by “brand” alone: “Ford”, “Toyota”, etc. Ultimately, one obtains a nested sequence of partitions of the set of alternatives, which can be represented as a tree whose root is the entire set of alternatives and whose leaves correspond to individual alternatives. See Appendix A for a more formal exposition of this process. Crucially, the difference in outcome between two alternatives (in terms of gains or losses) can now be simply bounded as a function of the height of their lowest common ancestor in the tree; the lower it is, the more traits they agree on. Motivated by this example, and taking a more abstract point of view, we study in this work a multi-armed bandit problem where the actions are the leaves of a given tree, and where the losses of any two actions can diverge by no more than a given function of the height of their most recent common ancestor. The main question we seek to answer is: when can these similarity constraints translate into strictly improved regret guarantees, and what feedback is needed to actually exploit them? The first point we establish is that, perhaps surprisingly, exploiting this structure is not possible in general under standard 1-point bandit feedback. This is in contrast to parametric bandit models like linear bandits (Bubeck et al., 2012), where one can improve upon the minimax regret rate of unstructured bandits. We prove this impossibility result by building upon the fact that one cannot exploit the effective range of the losses in (adversarial) multi-armed bandits (Gerchinovitz and Lattimore, 2016); that is, the maximum possible difference between the losses of two actions. It is no surprise then that the closely related nested bandit model of Martin et al. (2022) assumes access to more informative feedback. In that work, they also consider a tree-based representation with leaves as actions. They assume that the loss of an action admits a nested decomposition along the path to the root of the tree, with the expectation that the intrinsic losses are smaller for nodes at lower levels as they represent less relevant characteristics of the action. They adopt a semi-bandit feedback model: upon choosing an action, all node-level losses along the path to the root are revealed. The regret bounds they achieve depend on an effective number of actions Keff (which is a function of the importance and size of intermediate node sets) rather than on the total number of actions K. However, in many applications, this semi-bandit feedback is difficult to justify; in the car-catalogue example, one typically observes only an overall satisfaction signal for the recommended car, not separate losses attributable to brand, model, color, etc. As a second limitation, they only focus on adversarial losses and do not provide guarantees in the stochastic setting. 2

L EVERAGING S IMILARITIES IN M ULTI -A RMED BANDITS

Here, we address both limitations. We develop a best-of-both-worlds approach that yields guarantees in both stochastic and adversarial regimes depending on notions of effective number of actions, and we substantially weaken the feedback requirements by moving to multi-point protocols–culminating in a minimal two-point feedback model in which only the losses of two carefully coupled actions are observed at each round. Compared to semi-bandit feedback, it is often more realistic to obtain such multi-point feedback–for instance from several users making different choices. Likewise, in routing and path-finding applications, one may send several drivers along different routes and observe their corresponding total travel times. Importantly, our feedback model does not provide free exploration; the losses of all chosen actions are accounted for in the regret. In the final part of this work, we show that, beyond the tree-structured model, multi-point feedback can also be advantageous in the more familiar Lipschitz bandits problem (Kleinberg et al., 2008). In particular, under two-point feedback, we obtain new regret guarantees that, in lower dimensions, are significantly better than what can be achieved under one-point feedback. These new guarantees are obtained by applying our techniques to a hierarchical discretization of the action space. We now summarize our contributions. 1.1. Contributions Our contributions can be summarized as showing that action similarities can be leveraged, under a relatively weak feedback model, to obtain strictly sharper best-of-both-worlds bounds compared to standard bandit guarantees. (1) A lower bound for one-point bandit feedback. We prove that one-point (bandit) feedback cannot, in general, exploit tree-induced similarity √ constraints: for any such similarity structure, there always exist loss sequences that force Ω( KT ) regret. This motivates considering feedback models that reveal information from at least two actions per round. (2) Best-of-both-worlds guarantees under tree-induced similarities. We adopt a follow-theregularized-leader algorithmic template √ with a tree-aware regularizer that achieves logarithmic-type guarantees in stochastic regimes and T -type guarantees in adversarial regimes. In both cases, the similarity structure yields improvements over structure-agnostic baselines by replacing the ambient dependence on K with an effective number of actions Keff (and, in the stochastic case, an effective gap-dependent complexity), which can be dramatically smaller than K when losses vary smoothly across the action set. (3) Multi-point feedback relaxations, up to a minimal two-point protocol. We consider multipoint bandit protocols (m ≥ 2) ranging from an (L + 1)-point scheme (where L is the depth of the tree) aligned with the hierarchy down to a minimal two-point feedback model in which only the losses of two carefully coupled actions are observed per round. We show that we can achieve guarantees comparable to those that can be obtained under the semi-bandit model of (Martin et al., 2022). (4) Application to Lipschitz bandits. As an application, we show that under two-point feedback, our techniques can yield √ interesting results in the Lipschitz bandits problem, where we show that it is possible to achieve T regret when d ≤ 2. 3

E LDOWA R AHIER C ABLANT M ERTIKOPOULOS G AILLARD

1.2. Related Work Multi-armed bandits are a standard framework for sequential learning under uncertainty and have been extensively studied. We refer to Lattimore and Szepesvári (2020) for a comprehensive overview and focus here on the most relevant works for our setting. Exploiting structure in multi-armed bandits. Classical bandit models typically assume a finite set of independent arms. However, many modern applications involve structured action sets in which arms are related through geometry, correlations, or combinatorial constraints. This has motivated a substantial body of work on bandits with structured action spaces. Structured bandits extend the basic multi-armed bandit framework to large or infinite arm sets by imposing known relationships on the reward function across arms, which can be exploited to improve learning performance. Prominent examples include linear bandits (Abbasi-Yadkori et al., 2011; Agrawal and Goyal, 2013; Ito et al., 2020) and combinatorial bandits (Wen et al., 2015; Combes et al., 2015). A unifying treatment of several such structures in the stochastic setting was proposed by Combes et al. (2017). Another important class is given by Lipschitz or Hölder bandits, where arms lie in a metric (possibly continuous) space and regret bounds depend on the covering or packing dimension of this space (Kleinberg et al., 2008; Slivkins, 2011; Kleinberg et al., 2019; Podimata and Slivkins, 2021). In contrast to these parametric or metric-based models, we consider a setting where the similarity structure of the action space is encoded by a tree. This representation is motivated both by Lipschitz bandits (see Sec. 7) and by applications involving catalogues of objects that share hierarchical attributes (see Sec. 2). Such implicit tree structures have previously been studied by Slivkins (2011), who refer to them as taxonomies of arms, in the stochastic setting, and by Martin et al. (2022) for adversarial bandits with semi-bandit feedback. Another relevant line of work is hierarchical stochastic bandits (e.g., Hong et al. 2022a,b; Aouali et al. 2023; Nguyen et al. 2025), where correlations between rewards are imposed via hierarchical Bayesian models. Hong et al. (2022a), in particular, consider a tree-structured action set where nearby actions can have strongly correlated rewards. When the structure is favorable, they obtain better regret bounds compared to structure-agnostic algorithms. However, they only consider a Bayesian setting and do not provide ln T bounds. Finally, structural assumptions cannot always be fully exploited under standard bandit feedback. In particular, Gerchinovitz and Lattimore (2016) show that adaptation to the intrinsic loss range is impossible. We extend this limitation to our tree-structured setting in Section 3, motivating our multi-point feedback model. Multi-point bandit feedback. Several existing works have shown that improved regret guarantees can be obtained when the learner observes the loss at additional points at each round. Such√improvements date back to Agarwal et al. (2010), which improves the regret from O(T 3/4 ) to O( T ) compared to the original one-point feedback gradient descent method of (Flaxman et al., 2004; Kleinberg, 2004) for bandit convex optimization. Subsequent works (Duchi et al., 2015; Shamir, 2017; Lu et al., 2024) similarly demonstrate the benefits of two-point feedback for reducing the variance of gradient estimates or compete with non-stationary bandit environments. However, these approaches rely on gradient estimation techniques and assume convex losses, which is not the case in our setting. In the multi-armed bandit literature, observing an additional point has been studied by Sani et al. (2014) to adapt to “easy data” and by Thune and Seldin (2018) to adapt to the effective range of the losses, thereby circumventing the impossibility result of Gerchinovitz and Lattimore 4

L EVERAGING S IMILARITIES IN M ULTI -A RMED BANDITS

(2016) for one-point feedback. Additionally, Degenne et al. (2018) study a stochastic bandit problem with occasional (free) additional observations, which allows obtaining constant regret bounds. In our case, we show that two-point feedback allows us to exploit the tree structure of the action set. However, unlike in (Sani et al., 2014), (Thune and Seldin, 2018), and (Degenne et al., 2018), this additional observation does not constitute free exploration; rather, it is explicitly accounted for in our regret definition, which is better motivated by practical considerations.

2. Preliminaries A Tree-Based Action Set We consider an action set A := {1, . . . , K}. We will represent A as the set of leaves of a given, fixed rooted tree T of depth L. We summarize now some tree-related notation. For each level j ∈ {0, 1, . . . , L}, let Vj be the set of nodes at depth j, with V0 = {v0 } (the L root) and VL = A. We define V := ∪L j=1 Vj and V := ∪j=0 Vj . We use ▷ to denote the parenthood relation: v ▷ w means that w is a child of v. This can only happen if v ∈ Vj−1 and w ∈ Vj for some j ∈ [L]. We assume that every node has at least one child until level L: for any j ∈ {0, . . . , L − 1} and v ∈ Vj , there exists at least one w ∈ Vj+1 such that v ▷ w. In particular, v0 ▷ w holds for every w ∈ V1 . Let ≻ denote the reflexive and transitive closure of ▷ (ancestry relation), so that v ≻ w means that v is an ancestor of w (and every node is its own ancestor). Additionally, the function lvl : V → [L]∪{0} yields for any S v ∈ V the unique level j such that v ∈ Vj . Moreover, for every j ∈ [L]∪{0}, the function ancj : l≥j Vl → Vj maps every node at level j or lower to its unique ancestor at level j. The function prt : V → V maps a node S v to its unique parent prt(v). For each j ∈ [L] ∪ {0}, we define the equivalence relation ∼j on l≥j Vl by v ∼j w

⇐⇒

ancj (v) = ancj (w).

When restricted to leaves, a ∼j b means that a and b lie in the same subtree rooted at ancj (a). We encode the hierarchical proximity between actions through their divergence level, using a similarity function s : A × A → {1, . . . , L + 1} defined as s(a, b) := 1 + max{j ∈ {0, . . . , L} | a ∼j b},

a, b ∈ A.

Equivalently, for two actions a, b ∈ A, s(a, b) is the first level at which a and b diverge (s(a, a) = L + 1), so the larger s(a, b), the more similar a and b are. We identify functions x : A → R with vectors in RK through an arbitrary (fixed) bijection between A and [K]. The same applies to probability distributions over A, which we view as vectors in ∆K , the probability simplex in RK . For any vector x ∈ RK and any node v ∈ V, we define the subtree aggregate X x[v] := x(a), a∈A: v≻a

i.e., the mass (or value) of x restricted to the subtree rooted at v. Tree-compatible loss model This work is framed under a sequential online bandit problem (described in more detail later) in which the learner faces a sequence of loss functions (yt )t≥1 with yt : A → R generated by the environment. We will assume that the loss functions respect the similarity between actions in the following sense: we assume there exist parameters (σj )j∈[L+1] (with σL+1 = 0) such that for all rounds t and all a, b ∈ A, |yt (a) − yt (b)| ≤ σs(a,b) . (1) 5

E LDOWA R AHIER C ABLANT M ERTIKOPOULOS G AILLARD

That is, pairs sharing a deeper common ancestor have more similar losses. We posit, naturally, that σ1 ≥ σ2 ≥ · · · ≥ σL . Additionally, for the similarity structure to provide an advantage to the learner, these values need to decrease sufficiently fast compared to the growth of the number of nodes in deeper levels of the tree. The regret guarantees provided in the coming sections are naturally sensitive to this aspect. Their precise dependence on the tree structure can serve as a guiding metric when constructing the tree starting from a more general similarity model. In this work, we will mostly focus on the regret minimization aspect, taking the tree structure for granted. The application of Section 7 is the exception to this, as there, we also undertake the task of designing the tree. Online bandit game and multi-point feedback We now describe the sequential protocol and the regret notion used throughout the paper. Fix an integer m between 1 and L + 1. At every round t, the environment secretly draws a tree-compatible loss function yt , and simultaneously, the learner plays m ≥ 1 actions At,1 , . . . , At,m ∈ A, observes yt (At,1 ), . . . , yt (At,m ), and incurs their average 1 Pm i=1 yt (At,i ). The regret at horizon T is m RegT,m := E

" T m X 1 X t=1

m

# yt At,i

i=1

− min E a∈A

" T X

# yt (a) ,

t=1

which the learner aims to minimize. Note that the case m = 1 coincides with the standard (onepoint) bandit setting. The case of m ≥ 2 is considered in the light of the impossibility result presented in Section 3. We assume that yt is independent of the learner’s actions at round t or later, conditioned on the random events up to the end of round t − 1. Besides this, we make no further assumption about the loss generating mechanism. However, in Sections 5 and 6 we achieve improved guarantees when the loss sequence is benign in the following sense. Condition 1 (Generalized Stochastic Setting) There exists a vector ∆ ∈ RK + satisfying |{a ∈ PT 1 Pm A : ∆(a) = 0}| ≤ 1 such that RegT,m ≥ E t=1 m i=1 ∆(At,i ) holds for any algorithm. Conditions of this form are common in the literature (see e.g., Zimmert and Seldin (2021); Ito et al. (2022); Dann et al. (2023)), in particular, this subsumes the standard stochastic setting where the losses are drawn from a fixed distribution at each round.

3. Lower Bound: The Insufficiency of One-Point Feedback √ In the absence of any structure, the minimax regret of the bandit problem is Θ( KT ) (Auer et al., 2002). We now show that also for our problem, an improvement of this rate is informationtheoretically impossible under√one-point bandit feedback: no matter how small the σ values are, the worst-case regret remains Ω( KT ). Fix a depth-L tree with leaf set A and scale parameters (σj )j∈[L] . Define the class n o YσT := (yt )Tt=1 : ∀t, yt : A → [0, 1], ∀a, b ∈ A, |yt (a) − yt (b)| ≤ σs(a,b) . Recalling that σL = minj∈[L] σj , we now formally state the lower bound. 6

L EVERAGING S IMILARITIES IN M ULTI -A RMED BANDITS

Proposition 1 (One-point lower boundp under tree-induced similarity) Let ρ := σL . For K > 2, T > 32(K −1) log(14), and ρ > 0.22 (K − 1)/T , any randomized one-point bandit algorithm satisfies   1 p sup E RegT,1 (y1:T ) > T (K − 1). 504 (yt )T ∈YσT t=1

Equivalently,√for any such algorithm there exists a tree-compatible loss sequence (yt )Tt=1 ∈ YσT inducing Ω( KT ) expected regret. Proof sketch. The argument is a direct reduction to the range-impossibility result of Gerchinovitz and Lattimore (2016, Corollary 4). Let n o n o Cρ := x ∈ [0, 1]K : max |x(a) − x(b)| ≤ ρ and CρT := (yt )Tt=1 : ∀t, yt ∈ Cρ . a,b∈A

Any x ∈ Cρ satisfies |x(a) − x(b)| ≤ ρ = σL ≤ σs(a,b) , hence CρT ⊆ YσT . Applying (Gerchinovitz √ and Lattimore, 2016, Corollary 4) with ρ = σL yields the claimed Ω( KT ) bound over YσT . ■ Intuition and impact on the sequel. A convenient way to interpret Cρ is via a “baseline + perturbation” representation: each x ∈ Cρ can be written as x(a) = b + u(a) where b = mina x(a) ∈ [0, 1 − ρ] and u(a) = x(a) − b ∈ [0, ρ]. With one-point feedback, the learner observes only a single absolute value yt (At ) = bt + ut (At ) per round and cannot disentangle the unknown baseline bt from the informative part ut (At ); an adversary may drift bt over time without violating the range constraint, making the observations informationally ambiguous even when ρ is tiny. This motivates our focus on multi-point feedback: contrasts such as yt (At,1 )−yt (At,2 ) cancel the common baseline and expose the effective range, making the structure of the action set exploitable.

4. Basic Results for the Standard Bandit Problem To properly contextualize the techniques used in the coming sections, we lay out here a brief summary of some basic tools and results pertaining to the standard bandit problem. A standard approach for tackling said problem is through a reduction to online convex optimization, employing an algorithm like follow-the-regularized-leader (FTRL) or mirror descent over the probability simplex of the actions as a decision set, see, e.g., (Orabona, 2025). In particular, if we fix a sequence (zt )t≥1 of vectors in RK and a sequence of regularizers (ψt )t≥1 with ψt : RK → R being a convex function whose domain includes ∆K , the FTRL algorithm produces a sequence of distributions over actions (pt )t≥1 given by P p1 = arg min ψ1 (p) and pt = arg min s≤t−1 zs , p + ψt (p) for t ≥ 2 , p∈∆K

p∈∆K

which one can utilize by sampling At from pt . A standard choice for zt (a) is Ja = At Kyt (a)/pt (a), which is an unbiased estimate of yt (a). The last ingredient to specify is the regularizer ψt . A P common form in bandit problems is ψt (p) := (1/ηt ) a∈A f (p(a)) for p ∈ ∆K , where f is a one-dimensional convex function. Assuming f is Legendre (see Rockafellar 1970, Chapter 26), it holds for any q ∈ ∆K that PT PT t=1 ⟨zt , pt − q⟩ ≤ ψT +1 (q) − ψ1 (p1 ) + t=1 ψt (pt+1 ) − ψt+1 (pt+1 )
PT P + t=1 (1/ηt ) a∈A Df ∗ f ′ (p(a)) − ηt (zt (a) − yt (At )) f ′ (p(a)) , (2) 7

E LDOWA R AHIER C ABLANT M ERTIKOPOULOS G AILLARD

where Df ∗ is the Bregman divergence induced by the convex conjugate of f . Note that the expectation of the left-hand side is the regret of the learner that samples At from pt . The terms in the first line of the bound are collectively referred to as the bias term, which depends primarily on the magnitude of the regularizer; while the last sum is usually referred to as the variance term, this is a measure of the stability of the sequence (pt )t≥1 , which depends on the magnitude of the losses and the curvature of the regularizer. √ Setting ηt = η/ t with η > 0 and f (x) = x ln x recovers the well-known EXP3 √ PT algorithm, whose variance and bias terms are respectively bounded in expectation by ηK t=1 1/ t and √ P PT up to constants, assuming yt ∈ [0, 1]K . A suitable (1/η)E t=1 (1/ t) a pt (a) ln(1/pt (a)) √ tuning of η yields a regret bound of order KT ln K. Note that the regularizer used by EXP3 √ is the negative Shannon entropy function. Alternatively, one can choose f (x) = 2(x − x), which √ yields the negative 1/2-Tsallis entropy as the regularizer. Using this function with ηt = 1/Pt, the bias and p variance terms are nicely balanced, both being bounded in expectation by √ P E Tt=1 (1/ t) ( pt (a) − pt (a)) up to constants. This yields an improved regret bound of a √ order KT , which is unimprovable in the minimax sense (Auer et al., 2002). Besides a minor improvement in the worst case regime, this algorithm enjoys a major advantage against easy loss sequences. In particular, since its regret scales with the sum of the Tsallis entropy of pt at each round, one expects improved performance if the sequence (pt )t≥1 rapidly concentrates mass on a single action. One such scenario is when the losses are drawn at every round in an i.i.d. manner from a fixed P distribution. More generally, under Condition 1, the algorithm enjoys a regret bound of order a : ∆(a)>0 ln(T )/∆(a), see (Zimmert and Seldin, 2021). It is worth noting that one can also achieve a logarithmic regret bound in the stochastic setting by equipping EXP3 with a certain adaptive sequence of learning rates (ηt )t≥1 , even if it is an inferior bound of order K ln(T )2 / mina : ∆(a)>0 ∆(a), see (Ito et al., 2022).

5. Warm-up: Full-Path Feedback In this section, we adopt the more structured model of Martin et al. (2022). The purpose here is to illustrate our results, specifically, our best-of-both-worlds bounds, in a simpler setting and provide an algorithmic template to build upon in the coming sections. To recall, compared to ours, the setting of Martin et al. (2022) involves two interdependent restrictions. The first, posits that the adversary selects at every round a function ℓt : V → [0, 1] assigning a loss to every node in the tree such that ℓt (v) ≤ Rj for all v ∈ Vj , where P (Rj )j∈[L] are fixed positive weights in [0, 1]. The loss yt (a) of any action a ∈ A is then taken as v≻a ℓt (v). Note that our level-wise smoothness property can be imposed on this model taking Rj = σj − σj+1 , though the class of admissible loss functions is now smaller. The second and more crucial restriction is that the learner gets to observe all the values (ℓt (v))v≻a upon choosing At = a. In practical scenarios, it can be difficult to specify the ℓt function and unrealistic to assume we can access its values along the whole path from the root to the played action. Nevertheless, we entertain this model for the moment as a starting point, providing in the process improved results compared to Martin et al. (2022). In the worst case (adversarial) regime, Martin et al. (2022) showed that it is possible to leverage the similarity structure of the problem and the extra feedback to improve upon the minimax √ optimal KT regret rate of the standard bandit problem. In particular, they achieve a bound of p p
2 P order Keff (R)T P log K, where Keff (R) := is seen as the effective number j∈[L] Rj |Vj | of actions. When j∈[L] Rj = 1, as assumed by Martin et al. (2022), Keff is never worse than 8

L EVERAGING S IMILARITIES IN M ULTI -A RMED BANDITS

K, and can be much smaller when the tree has a favorable structure, an example is provided at the end of this section. The algorithm they use to achieve this result is a nested version of the EXP3 algorithm, which can be seen as an instance of FTRL with two main features that distinguish it from the examples provided in the previous section. Firstly, they leverage the semi-bandit feedback by using P ℓbt (v) := Jv ≻ At Kℓt (v)/pt [v] as an unbiased estimate of ℓt (v), leading to the choice of zt (a) = v≻a ℓbt (v).1 The feature is the use of a nested Shannon entropy regularizer deP secondP fined as ψt (p) = (1/ηt ) j∈[L] αj v∈Vj p[v] ln p[v] , which is a weighted sum (with non-negative weights (αj )j∈[L] ) of the Shannon entropy of the aggregated version of p at every level. Ultimately though, the use of this special form of regularizer is not fully justified by thePresults of Martin et al. (2022). In particular, they present an upper bound of order (Keff (R)/αL ) Tt=1 ηt on the variance term of their algorithm, which holds even if α1 = · · · = αL−1 = 0, i.e., the standard version of EXP3. Their bound on the bias term takes a complex form that does involve all the weights, but is less significant as its dependence on the number of actions To gain P is logarithmic. P more insight, we show that for any regularizer of the form ψt (p) = (1/ηt ) j∈[L] αj v∈Vj f (p[v]) with f being Legendre, the bound in (2) holds with the last sum replaced by (see Lemma 11)
PT P P ′ ′ t=1 1/ηt j∈[L] αj v∈Vj Df ∗ f (p[v]) − ηt ζt (v)/αj f (p[v]) , P P where ζt : V → R is any function satisfying v≻a ζt (v) − w≻a′ ζt (w) = zt (a) − zt (a′ ) for all a, a′ ∈ A. When f (x) = x ln x, one can show that choosing ζt (v) = Jv ∈ AKzt (a), i.e., pushing PT all the weights to the last level, allows recovering the aforementioned bound of (Keff (R)/αL ) t=1 ηt . It is unclear if this can be significantly improved upon; moreover, one can safely neglect the tradeoff with the bias term (considering the tuning of the α weights) due to the great disparity of magnitude between bias and variance in this case (logarithmic vs linear in the number of actions). √ On the other hand, picking f (x) = 2(x − x) and making the more natural choice of ζt (v) = ℓbt (v) (up to a constant shift) balances the bias and variance bounds, as plong as αj ∝ Rj . Specif√ P P P ically, one obtains a bound of order Tt=1 1/ t E j∈[L] Rj v∈Vj pt [v] − pt [v] , which is an analogue of the entropy-dependent bound discussed in the previous section for the unstructured bandit problem. The advantage of this result is, again analogously to the discussion in the previous section, that it can be used to obtain improved bounds in more benign scenarios where the losses are drawn at every round from a fixed distribution, which was not addressed by Martin et al. (2022). Crucially, the appearance of the scale parameters in this bound allows leveraging the structure of the problem to obtain improved bounds (compared to unstructured bandits) also in the stochastic case. Imperative to this is the nested form of the regularizer, which injects the scale parameters also into the bias term. We present then in the following theorem a best-of-both-worlds: a slight improvement of the worst-case bound of Martin et al. (2022) and a new structure-aware logarithmic regret p
2 P bound holding in the stochastic setting. Recall that Keff (R) := j∈[L] Rj |Vj | , and define X p
2 P 1 := Keff,∆ (R) := R Γ(j, ∆) and Γ(j, ∆) . j j∈[L] mina≺v ∆(a) v∈Vj : mina≺v ∆(a)̸=0 p p P P Theorem 2 FTRL with ψt (p) = 5 max{t, 20} j∈[L] Rj v∈Vj p[v] − p[v] and zt (a) = P v≻a Jv ≻ At Kℓt (v)/pt [v] satisfies p  p 15pKeff (R) + 4 5Keff (R)T RegT,1 ≤ 30 Keff (R) + 20Keff,∆ (R) ln(eT ) (under Condition 1) 1. We use J·K to denote the indicator function.

9

E LDOWA R AHIER C ABLANT M ERTIKOPOULOS G AILLARD

The proof can be found in Appendix C. For comparison, P algorithms like UCB and TsallisINF enjoy in the stochastic setting a regret bound of order a : ∆(a)>0 ln(T )/∆(a), which is not P improvable in general in the unstructured bandit problem. Defining K∆ := a : ∆(a)>0 1/∆(a), P it is easy to see that Keff,∆ (R) improves upon K∆ , assuming as before that L j=1 Rj = 1. In P particular, Jensen’s inequality gives that Keff,∆ (R) ≤ j∈[L] Rj Γ(j, ∆), and clearly, Γ(j, ∆) ≤ K∆ at any level j since |Vj | ≤ K and every action has a unique ancestor in Vj . In fact, it is usually strictly better; we demonstrate now that Keff,∆ (R) may be exponentially smaller than K∆ on a simple example with A ⊂ [0, 1] and a dyadic partitioning of the space that correlates the losses of the  −j actions. Let L ≥ 1 and consider for each level Vj := i2 ; i = 0, . . . , 2j − 1 , A := VL and K = 2L . For each node v ∈ Vj , we set prt(v) = ⌊v2j−1 ⌋21−j and ℓt (v) = 0.5(v−prt(v))+2−(j+1) εt (v) with εt (v) ∼ Bernoulli(1/2) (we assign a loss 0 to the root). This implies that ℓt (v) ∈ [0, 2−j ] and P2j −1 j+1 mina≺v ∆(a) = v/2. Then, for all j ∈ [L], Γ(j, ∆) = i=1 2 i ≤ (j + 1)2j+1 , which, using P j
2 −2 ≤ 6 and Rj ≤ 2−j , yields Keff (R) = j∈[L] 2 Keff,∆ (R) :=

P

j∈[L] Rj

p
2
2 P 1−j √ 2 Γ(j, ∆) ≤ j + 1 ≤ 6(L + 1) = 12(log2 K + 1). j∈[L] 2

On the other hand, we have K∆ = Γ(L, ∆) ≥ 2L+1 L ln 2 = 2K ln K.

6. Multi-Point Bandit Feedback Having seen that exploiting the structure of our problem is impossible under (one-point) bandit feedback, we seek to demonstrate in this section that one can skirt this obstacle by executing more than one action in each round and observing all their losses. Precisely, just making two observations per round is already sufficient, but in some case observing more (up to L + 1) can lead to better performance. Importantly, the learner does not make these observations for free, but pays the average loss of the executed actions (some of which can be duplicates). This is decidedly milder than the feedback model considered in Section 5; not least of all because the environment (its feedback mechanism in particular) is not strongly coupled to the structure of the tree. Nevertheless, the manner in which we exploit this limited feedback is to simulate the full-path feedback of Section 5 and use the same algorithmic template. There, P we leveraged the fact that at every round, there exists a loss function ℓt : V → R such that (i) v≻a ℓt (v) = yt (a) for all a ∈ A; (ii) one observes (ℓt (v))v≻At after executing At ; and (iii) ℓt (v) ≤ Rj for all v ∈ Vj . Here, however, we will build our own ℓt function satisfying similar properties. Firstly, we associate with every node v ∈ V an action ωt (v) that is sampled from pt conditioned on having v as an ancestor. Then, define ℓt (v) := yt (ωt (v)) − yt (ωt (prt(v))) . Now, it is easy to see that Property (i) holds up to a constant shift (by yt (wt (v0 ))), which suffices. Moreover, an analogue of Property (iii) holds via the loss smoothness condition (1); in particular, |ℓt (v)| ≤ σj for all v ∈ Vj . Finally, for Property (ii), we sample an action At,1 ∼ pt and execute it along with ωt (v) for all ancestors v of At,1 (including v0 ), thus we observe (ℓt (v))v≻At,1 . Note that in this manner, we execute L + 1 actions, the marginal law of each is pt , conditioned on the events of past rounds. In practice, of course, one only needs to sample ωt (·) at the ancestors of At,1 . Using this reduction, we can recover the bounds of Theorem 2, but now for RegT,L+1 and with R swapped for σ. Going a step further, at a slight cost, we can get away with observing ℓt at only one node, which we can achieve by executing just two actions. In particular, we sample a level jt ∈ [L] 10

L EVERAGING S IMILARITIES IN M ULTI -A RMED BANDITS

Input: sequence of regularizers (ψt )t≥1 , sequence of constants (bj )L j=1 , distribution δ ∈ ∆L Initialization: p1 = arg minp∈∆K ψ1 (p) 1 for t ≥ 1 do 2 sample At,1 ∼ pt , jt ∼ δ , and At,2 ∼ pt | At,2 ∼jt −1 At,1 yt (At,1 ) − yt (At,2 ) + bjt 3 for all a ∈ A, set zt (a) = Ja ∼jt At,1 K δjt pt [ancjt (At,1 )] P 4 set pt+1 = arg min z , p + ψ (p) t+1 s≤t s p∈∆K

5 end

Algorithm 1: FTRL with 2-Point Bandit Feedback from a fixed distribution δ and a node vt with probability ∝ J· ∈ Vjt Kpt [·]. Then, we simply execute ωt (vt ) and ωt (prt(vt )), giving us access to ℓt (vt ). A more direct version of this procedure is given in Algorithm 1. Note that we account for the reduced feedback by correcting the loss estimate with a factor of 1/δjt . Additionally, we shift ℓt by a level-dependent constant to enforce non-negativity for technical reasons. Ultimately, we arrive at the following theorem (see Appendix D). p √ P  p q P Theorem 3 Algorithm 1 with ψt (p) = 2 6 j∈[L] (σj / δj ) max t, 6/δj v∈Vj x[v]− x[v] and bj = σj for all j ∈ [L] satisfies ( p √ √ p 18pKeff (σ/δ) + 8 6 Keff (σ/ √ δ)T . RegT,2 ≤ 36 Keff (σ/δ) + 96Keff,∆ (σ/ δ) ln(eT ) (under Condition 1) √
2 p p P We used here the notation of Theorem 2, specifically, Keff (σ/ δ) := j (σj / δj ) |Vj | √
2 p p P and Keff,∆ (σ/ δ) := j (σj / δj ) Γ(j, ∆) . The choice of δ was left open in the√bounds above. At least for the adversarial regime, one can choose δ so as to minimize Keff (σ/ δ). In favorable cases, carefully choosing δ can render its effect on the bound negligible, see Section 7. In general, choosing √ the uniform distribution is a safe choice that results in the bound scaling with an extra factor of L in the adversarial regime and L in the stochastic one. If one has access to m-point feedback, where 2 ≤ m ≤ L + 1, then Algorithm 1 can be generalized by randomly drawing m − 1 levels at every round. We show in Appendix D that the bounds of Theorem 3 continue to hold in that case, with δj denoting the probability that level j is amongst the chosen levels at any round. Drawing p the m − 1 levels uniformly at random without replacement results in the bounds scaling with L/(m − 1) and L/(m − 1) in the adversarial and the stochastic regimes respectively. The issue of δ aside, the utility of the bounds presented here (compared to standard bandit bounds) relies on the tree being carefully constructed; specifically, that the values of σj decay quickly relative to the increase in |Vj |. For instance, in the example presented in Section 5, σj ≤ 2−j+1 , hence the bounds derived there continue to hold up to constant factors, illustrating again the huge advantage that Keff and Keff,∆ can bring. In general, these parameters are to be used as an efficiency criteria when constructing a tree from a similarity structure. We provide more insights on this issue in the next section.

7. Application: Lipschitz Bandits with Two-Point Feedback Under the same interaction model as before, suppose we are now given an arbitrary action set A and a set Y of admissible loss functions, whose members map A to R. We can always equip A with 11

E LDOWA R AHIER C ABLANT M ERTIKOPOULOS G AILLARD

the following metric: dA,∞ (a, b) := sup |y(a) − y(b)| ∀a, b ∈ A .

(3)

y∈Y

To be precise, this function is a metric only if no two actions behave identically on all loss functions in Y, which is fair to impose. All members of Y are obviously 1-Lipschitz with respect to dA,∞ . In the tree-based model we have studied thus far, Y was taken as the set of tree-compatible loss functions described in Section 2. In particular, the induced metric in this case is given by dA,∞ (a, b) = σs(a,b) , where, to recall, s(a, b) := 1 + max{j ∈ {0, . . . , L} | a ∼j b}. More than a metric, this function satisfies a strong form of the triangle inequality: σs(a,b) ≤ max{σs(a,c) , σs(c,b) } for all a, b, c ∈ A since σ1 ≥ · · · ≥ σL ; hence, it is an ultrametric. Note that the tree structure can be recovered from this distance function if the similarity scales are strictly decreasing. A similar notion of distance was studied by Slivkins (2011) in the stochastic setting, and was referred to as implicit distance. Seen from this angle, the algorithmic techniques presented so far are designed to leverage this special form of distance and the implied restriction on the losses via (3). We aim to illustrate here that our results can still be adapted to cases in which dA,∞ is a generic metric (or pseudometric). This is done, naturally, by constructing a tree over the action set and forcing a specific decay schedule for the resulting similarity scales. This constitutes a “truncation” or “compression” of the original metric structure, but still leads to interesting results. We will focus henceforth on the two-point feedback setting. In fact, the arguments used to prove the onepoint feedback lower bound of Proposition 1 can be easily adapted to show that it still holds in this more general setting provided that A is finite and the conditions of the proposition hold with ρ = mina,b∈A : a̸=b dA,∞ (a, b). Towards employing Algorithm 1 and its regret bound, we start by constructing a tree whose nodes are members of A. Unlike before, the nodes in the last level of this tree need not include the entire set A (which we do not require to be finite here). We specify now two parameters to be used in the sequel: a constant c > 0 and a positive integer L representing the number of levels as before. We will assume that c ≥ maxa,b∈A dA,∞ (a, b). For j ∈ [L], let Aj ⊆ A be a subset of actions that form a c2−j covering with respect to dA,∞ .2 For convenience, let A0 := {a0 } with some arbitrary action a0 . Then, for any a ∈ Aj , define its parent as its closest action in Aj−1 with ties broken arbitrarily; that is, prt(a) ∈ arg mina′ ∈Aj−1 dA,∞ (a, a′ ) with ties broken arbitrarily. If one action belongs to multiple covers, each of these occurrences is to be regarded as a distinct node. In this manner, it is possible that certain nodes in intermediate levels end up with no children. Hence, we define a pruned version of the covering at each level j: Aj = {a ∈ Aj | ∃a′ ∈ AL : a = ancj (a′ )} , implying that Aj ⊆ Aj for each j and
that AL = AL . Now the sequence (Aj )j=0,...,L forms a tree, which we will refer to as T (Aj )L j=0 , whose leaves are all at level L. This tree induces a nested sequence of partitions of the set AL , which will be the action set in the eyes of the algorithm. For 2. This means that mina′ ∈Aj dA,∞ (a, a′ ) ≤ c2−j for all a ∈ A.

12

L EVERAGING S IMILARITIES IN M ULTI -A RMED BANDITS

any pair of actions a, b ∈ AL such that s(a, b) = j,3 it holds that dA,∞ (a, b) ≤ dA,∞ (a, ancj−1 (a)) + dA,∞ (ancj−1 (b), b) ≤

L−1 X

dA,∞ (anck+1 (a), anck (a)) +

k=j−1

≤ 2c

L−1 X

L−1 X

dA,∞ (anck+1 (b), anck (b))

k=j−1

2−k ≤ c23−j

k=j−1

where we have used the triangle inequality and the fact that a ∼j−1 b. Hence, via (3), setting σj = c23−j is consistent with the assumption in (1), applied now to the new action set AL and the
. We can now instantiate the regret guarantee of Algorithm 1 on this tree structure, tree T (Aj )L j=0 yielding the following result (the proof can be found in Appendix E). We will focus here on the adversarial setting.
Corollary 4 Suppose we run Algorithm 1 on the tree T (Aj )L j=0 with parameters ψt , bj as defined in Theorem 3, σj = c23−j , and δj ∝ 2−2j/3 |Aj |1/3 . Then, assuming that minj∈[L] δj ≥ 1/T , it holds that √ q
−L RegT,2 ≤ 16 · (9 + 4 6) Keff (Aj )L T, j=0 T + c 2 P 3
2 −2j/3 |A |1/3 := where Keff (Aj )L c 2 . j j=0 j∈[L] The last term is a bound on the approximation error resulting from using AL as the action set. This holds because AL is a c2−L -cover of A. This term can be turned into a small constant by choosing L = ⌊log2 T ⌋, though in some cases balancing this term with the first can
be beneficial. When the cardinality of A is finite, denoted by K as before, then Keff (Aj )L j=0 is never larger than K up to small constants, regardless of the choice of L and the covers (Aj )j∈[L] . Of course,
in interesting examples, ones where the covers can be made small at coarser levels, Keff (Aj )L j=0 can be made significantly smaller than K. Hence, one should strive to ensure that the covers are near-optimal, which can be achieved by a simple greedy allocation strategy. We elaborate more on this in Appendix E.2, where we also argue that no other tree-building strategy results, via the bound of Theorem 3, in a significantly smaller Keff . Now, let A ⊂ Rd be a compact set with diameter D (w.r.t. to the Euclidean metric), and let Y be the set of G-Lipschitz loss functions from A to R. It holds then that dA,∞ (a, b) ≤ G∥a − b∥ ∀a, b ∈ A . In the ordinary interaction model—when the learner selects at each round a single action, observes the associated loss, and is evaluated through the regret RegT,1 — the minimax optimal regret rate is Ω(T (d+1)/(d+2) ), as shown by Kleinberg et al. (2008). Subsequent works have focused on adapting to the effective (zooming) dimension d of the metric space (Slivkins, 2011; Kleinberg et al., 2019; Podimata and Slivkins, 2021), designing more adaptive algorithms (Héliou et al., 2021), or improving robustness to corruption (Kang et al., 2023). However, all these approaches rely on one-point 3. To recall, this means that the lowest common ancestor of a and b is at level j − 1.

13

E LDOWA R AHIER C ABLANT M ERTIKOPOULOS G AILLARD

feedback and therefore suffer from the above minimax rate in the worst case. Under a richer feedback model (“one-sided” full-information) motivated by second-price auctions, Cesa-Bianchi et al. (2017) showed that this rate can be improved. We show now that under two-point feedback, Corollary 4 can be used to obtain better regret guarantees compared to the one-point feedback minimax rate. We will √ optimize the depth of the tree depending on the dimension. For each j = 1, . . . , L, let εj = D d 2−j be a precision level, and let Aj be an εj -cover of A (w.r.t. to the √ Euclidean metric) with minimal cardinality. Using a √ −j d jd uniform grid, one can show that |Aj | ≤ (D√ d/εj ) = 2 . Note that Aj is a GD d2 -cover w.r.t. dA,∞ ; hence, we can choose c = GD d, which is an upper bound for maxa,b∈A dA,∞ (a, b) as required. The following result is then easy to obtain from Corollary 4 (the proof can be found in Appendix E).
Corollary 5 Let T ≥ 8. Algorithm 1 run on the tree T (Aj )L j=0 induced by the covers described √ above with L = ⌊ d1 log2 (T )⌋ and parameters ψt , bj as defined in Theorem 3, σj = GD d 23−j and δj ∝ 2j(d−2)/3 , satisfies the following regret upper bound  √  if d = 1  T √ 3/2 (ln T ) T if d = 2 , RegT,2 ≲ GD ·   √dT d−1 d if d > 2 where ≲ denotes an inequality up to a universal constant. Interestingly, when d ≤ 2, the above result shows √ that two-point feedback is sufficient to recover (up to logarithmic factors for d = 2) the optimal Ω( T ) full-information rate. This follows from the fact that the effective number of arms induced by the underlying tree structure is O((log T )3 ) for d ≤ 2, even though the total number of leaves can be as large as T .

Acknowledgments This work was supported by funding from the French government, managed by the National Research Agency (ANR), under the France 2030 program, reference ANR-23-IACL-0006. Additionally, this work was supported in part by ANR in the framework of the PEPR IA FOUNDRY project (ANR-23-PEIA-0003). PM is also a member of the Archimedes Research Unit/Athena RC, and was partially supported by project MIS 5154714 of the National Recovery and Resilience Plan Greece 2.0 funded by the European Union under the NextGenerationEU Program.

References Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24, 2011. Alekh Agarwal, Ofer Dekel, and Lin Xiao. Optimal algorithms for online convex optimization with multi-point bandit feedback. In Colt, pages 28–40, 2010. Shipra Agrawal and Navin Goyal. Thompson sampling for contextual bandits with linear payoffs. In International conference on machine learning, pages 127–135. PMLR, 2013. 14

L EVERAGING S IMILARITIES IN M ULTI -A RMED BANDITS

Imad Aouali, Branislav Kveton, and Sumeet Katariya. Mixed-effect thompson sampling. In Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, volume 206 of Proceedings of Machine Learning Research, pages 2087–2115. PMLR, 2023. Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47(2):235–256, 2002. Dimitri Bertsekas. Convex optimization theory, volume 1. Athena Scientific, 2009. Sébastien Bubeck, Nicoló Cesa-Bianchi, and Sham M. Kakade. Towards minimax policies for online linear optimization with bandit feedback. In Proceedings of the 25th Annual Conference on Learning Theory, volume 23 of Proceedings of Machine Learning Research, pages 41.1– 41.14. PMLR, 2012. Nicolò Cesa-Bianchi, Pierre Gaillard, Claudio Gentile, and Sébastien Gerchinovitz. Algorithmic chaining and the role of partial feedback in online nonparametric learning. In Conference on Learning Theory, pages 465–481. PMLR, 2017. Richard Combes, Mohammad Sadegh Talebi Mazraeh Shahi, Alexandre Proutiere, et al. Combinatorial bandits revisited. Advances in neural information processing systems, 28, 2015. Richard Combes, Stefan Magureanu, and Alexandre Proutiere. Minimal exploration in structured stochastic bandits. In Advances in Neural Information Processing Systems (NeurIPS), 2017. Chris Dann, Chen-Yu Wei, and Julian Zimmert. A blackbox approach to best of both worlds in bandits and beyond. In Proceedings of Thirty Sixth Conference on Learning Theory, volume 195 of Proceedings of Machine Learning Research, pages 5503–5570. PMLR, 12–15 Jul 2023. Rémy Degenne, Evrard Garcelon, and Vianney Perchet. Bandits with side observations: Bounded vs. logarithmic regret. In Conference on Uncertainty in Artificial Intelligence, 2018. John C Duchi, Michael I Jordan, Martin J Wainwright, and Andre Wibisono. Optimal rates for zero-order convex optimization: The power of two function evaluations. IEEE Transactions on Information Theory, 61(5):2788–2806, 2015. Abraham D Flaxman, Adam Tauman Kalai, and H Brendan McMahan. Online convex optimization in the bandit setting: gradient descent without a gradient. arXiv preprint cs/0408007, 2004. Sébastien Gerchinovitz and Tor Lattimore. Refined lower bounds for adversarial bandits. Advances in Neural Information Processing Systems, 29, 2016. Amélie Héliou, Matthieu Martin, Panayotis Mertikopoulos, and Thibaud Rahier. Zeroth-order nonconvex learning via hierarchical dual averaging. In International Conference on Machine Learning, pages 4192–4202. PMLR, 2021. Joey Hong, Branislav Kveton, Sumeet Katariya, Manzil Zaheer, and Mohammad Ghavamzadeh. Deep hierarchy in bandits. In Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 8833–8851. PMLR, 2022a. 15

E LDOWA R AHIER C ABLANT M ERTIKOPOULOS G AILLARD

Joey Hong, Branislav Kveton, Manzil Zaheer, and Mohammad Ghavamzadeh. Hierarchical bayesian bandits. In Gustau Camps-Valls, Francisco J. R. Ruiz, and Isabel Valera, editors, Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, volume 151 of Proceedings of Machine Learning Research, pages 7724–7741. PMLR, 2022b. Shinji Ito, Shuichi Hirahara, Tasuku Soma, and Yuichi Yoshida. Tight first-and second-order regret bounds for adversarial linear bandits. Advances in Neural Information Processing Systems, 33: 2028–2038, 2020. Shinji Ito, Taira Tsuchiya, and Junya Honda. Nearly optimal best-of-both-worlds algorithms for online learning with feedback graphs. In Advances in Neural Information Processing Systems, volume 35, pages 28631–28643. Curran Associates, Inc., 2022. David S. Johnson. Approximation algorithms for combinatorial problems. Journal of Computer and System Sciences, 9(3):256–278, 1974. ISSN 0022-0000. Yue Kang, Cho-Jui Hsieh, and Thomas Chun Man Lee. Robust lipschitz bandits to adversarial corruptions. Advances in Neural Information Processing Systems, 36:10897–10908, 2023. Robert Kleinberg. Nearly tight bounds for the continuum-armed bandit problem. In Advances in Neural Information Processing Systems, volume 17. MIT Press, 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, 2008. Robert Kleinberg, Aleksandrs Slivkins, and Eli Upfal. Bandits and experts in metric spaces. Journal of the ACM (JACM), 66(4):1–77, 2019. Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020. Zhou Lu, Qiuyi Zhang, Xinyi Chen, Fred Zhang, David Woodruff, and Elad Hazan. Adaptive regret for bandits made possible: Two queries suffice. arXiv preprint arXiv:2401.09278, 2024. Matthieu Martin, Panayotis Mertikopoulos, Thibaud Rahier, and Houssam Zenati. Nested bandits. In International Conference on Machine Learning, pages 15093–15121. PMLR, 2022. Nicolas Nguyen, Imad Aouali, András György, and Claire Vernade. Prior-dependent allocations for bayesian fixed-budget best-arm identification in structured bandits. In Proceedings of The 28th International Conference on Artificial Intelligence and Statistics, volume 258 of Proceedings of Machine Learning Research, pages 379–387. PMLR, 2025. Francesco Orabona. A modern introduction to online learning. arXiv preprint arXiv:1912.13213, 2025. Chara Podimata and Alex Slivkins. Adaptive discretization for adversarial lipschitz bandits. In Conference on Learning Theory, pages 3788–3805. PMLR, 2021. R. Tyrrell Rockafellar. Convex analysis. Princeton Mathematical Series. Princeton University Press, 1970. 16

L EVERAGING S IMILARITIES IN M ULTI -A RMED BANDITS

Amir Sani, Gergely Neu, and Alessandro Lazaric. Exploiting easy data in online optimization. Advances in Neural Information Processing Systems, 27, 2014. Ohad Shamir. An optimal algorithm for bandit and zero-order convex optimization with two-point feedback. Journal of Machine Learning Research, 18(52):1–11, 2017. Petr Slavı́k. A tight analysis of the greedy algorithm for set cover. Journal of Algorithms, 25(2): 237–254, 1997. ISSN 0196-6774. Aleksandrs Slivkins. Multi-armed bandits on implicit metric spaces. Advances in Neural Information Processing Systems, 24, 2011. Tobias Sommer Thune and Yevgeny Seldin. Adaptation to easy data in prediction with limited advice. Advances in Neural Information Processing Systems, 31, 2018. Zheng Wen, Branislav Kveton, and Azin Ashkan. Efficient learning in large-scale combinatorial semi-bandits. In International Conference on Machine Learning, pages 1113–1122. PMLR, 2015. Julian Zimmert and Yevgeny Seldin. Tsallis-inf: An optimal algorithm for stochastic and adversarial bandits. Journal of Machine Learning Research, 22(28):1–49, 2021.

17

E LDOWA R AHIER C ABLANT M ERTIKOPOULOS G AILLARD

Appendix A. Motivation: Similarity structures and related notions In this appendix, we elaborate more on the motivating example given in the introduction. In particular, we give more details on how a tree structure can be induced from this general setting. A.1. From traits to trees Consider again a finite set of alternatives (or actions) indexed by a ∈ A = {1, . . . , K}. Based on their innate traits, these alternatives can be clustered in different ways so that each subgroup shares a common attribute: in our running example from the introduction, a collection of cars could be categorized by brand into Fords, Chevrolets, Toyotas, etc.; by type into sedans, compacts, SUVs, and so forth; by powertrain into gas, hybrid, or electric; etc. To formalize this idea, a trait is defined to be a partition T of A into pairwise disjoint subsets—called classes—each corresponding to a different instance of said trait. Thus, in the catalogue of cars considered above, type and brand would represent different traits, while Ford and Toyota would be different instances of the trait brand. Accordingly, to define a similarity structure on A, we will assume that A is equipped with a family of traits T = {Ti }ni=1 . Of course, two or more traits can be combined, leading to clusters like “Ford compacts”, “Toyota sedans”, etc. Formally, the combination (or logical conjunction) of two traits T, T ′ ∈ T is defined to be the “composite trait” T ∧ T ′ = {C ∩ C ′ : C ∈ T, C ′ ∈ T ′ } ; in words, T ∧ T ′ simply groups together all alternatives that combine an instance of T with an instance of T ′ . More generally, any subset S of T gives rise to a composite trait via the operation V S 7→ combine(S) ≡ T ∈S T . Then, to quantify all this, we will associate to each subset S of T a non-negative heterogeneity score ςS : the smaller this score, the more similar any two alternatives agreeing on the traits in S are. We naturally posit that ςT = 0 and that ςS ≤ ςS ′ when S ′ ⊆ S. Moving forward, when selecting an alternative, one may first focus on the type of a car before worrying about its brand, or one could do the reverse. To model this, we define a priority ranking on a family of traits T to be a strict total order > (read: “has higher priority than”). Given a priority ranking, we can define a sequence (Sj )nj=0 , where S0 = ∅, Sn = T , and Sj is the set composed of the first j traits. We thus obtain a nested sequence of partitions combine(S0 ), . . . , combine(Sn ), each successively refining its predecessor. This sequence is nothing but a tree structure on A, and, taken together, the family of traits, heterogeneity scores and the priority rank comprise what we call a similarity structure on A. In reference to the tree compatible loss model described in Section 2, if Sj is the combination of traits associated with the j-th level of the tree, then σj+1 is simply ςSj .4 Hence, the similarity scales depend on the priority ranking, and can hence affect the regret bounds. In the next section, we provide more technical details involving the aforementioned process of constructing the tree, and show how the number of logically admissible trees can be reduced. A.2. A logical structure for the traits In this section, our aim is to elaborate on certain aspects of priority rankings and their compatibility with the innate structure of the family of traits. 4. The +1 increment is due to the way s(·, ·) is defined.

18

L EVERAGING S IMILARITIES IN M ULTI -A RMED BANDITS

Binary relations between traits To that end, we begin by considering certain natural binary relations among a family of traits T = {Ti }ni=1 on A. The first such relation is that of refinement: given two traits T, T ′ ∈ T , we say that T is finer than T ′ —and we write T ≼ T ′ —if every element of T is a subset of some element of T ′ . Another natural relation arises when alternatives are categorized according to different traits, in which case some traits might be subordinate to other more “primitive”, higher-order traits that precede them in any chain of logical reasoning. For instance, the model of a car cannot be defined without implicitly specifying the car’s brand: after all, an Impala is, by definition, a Chevrolet. To capture this, we define a logical structure on a family of traits T as a binary relation ⊢ (read: “requires” or “is a primitive of ”) satisfying the following conditions for all T, T ′ , T ′′ ∈ T : (a) Irreflexivity: T ⊬ T . (b) Transitivity: If T ⊢ T ′ and T ′ ⊢ T ′′ , then T ⊢ T ′′ . (c) Consistency: If T ⊢ T ′ , then T ≼ T ′ . In short, condition (a) states that a trait T is not a primitive of itself, while condition (b) requires that primitives of primitives of T are themselves primitives of T ; thus, taken together, conditions (a) and (b) simply say that ⊢ is a strict partial order on T . The last condition (consistency) posits that two alternatives that differ by a primitive of T also differ by T itself: for example, since brand is a primitive of model, a Toyota and a Chevrolet can’t be the same model. 5 For posterity, we will write the set of primitives of T ∈ T as prim(T ) = {T ′ ∈ T : T ⊢ T ′ },

(4)

For example, if T = {brand, color, model, type}, the implied logical structure readily gives prim(model) = {brand, type} (an Impala is de facto a Chevrolet sedan), and prim(type) = prim(brand) = prim(color) = ∅ (since none of these traits implicitly requires another). A family of traits T equipped with a logical structure ⊢ will be called here a similarity structure on A, and we will denote it as Λ ≡ Λ(T , ⊢). Combining traits. We now proceed to detail the procedure of combining two or more traits, leading to clusters like “Ford compacts”, “Toyota sedans”, etc. In this case, a priority ranking gives rise to a nested succession of “composite” traits, which can be seen as a decision tree: at each step an additional trait is added to the mix, resulting in finer and finer partitions of A until all traits are present. Formally, define the combination (or logical conjunction) of two traits T, T ′ ∈ T as T ∧ T ′ = {C ∩ C ′ : C ∈ T, C ′ ∈ T ′ },

(5)

i.e., as the coarsest partition of A that refines both T and T ′ . Intuitively, this means that T ∧ T ′ groups together all alternatives that combine an instance of T with an instance of T ′ .6 Then, any 5. This implication does not go the other way round: in particular, if T is finer than T ′ , T ′ need not be a primitive of T . For example, if A = {a blue Ford, a yellow Chevy, a red Chevy} and Tcolor is a partition of A by color and Tbrand is a partition by brand, the partition Tcolor is (strictly) finer than Tbrand , even though brand is not a primitive of color: in general, a car’s color does not determine its brand, even though it happens to do so for this particular set of cars. This shows that the prerequisite relation ⊢ is about the traits themselves as abstract entities, not about the set of alternatives embodying those traits. 6. For book-keeping reasons, traits that are obtained this way will be called composite traits, to differentiate them from their “primitive” counterparts T ∈ T : for example, “Toyota sedan” is the instance of the composite trait “type and brand” which describes all cars that are of brand “Toyota” and type “sedan” (the two primitives).

19

E LDOWA R AHIER C ABLANT M ERTIKOPOULOS G AILLARD

subset S of T gives rise to a composite trait via the operation S 7→ combine(S) ≡

V

T ∈S T.

(6)

Under combine, the empty set ∅ is mapped to the combination of no traits, i.e., the partition of A V that refines no other partition, namely combine(∅) = T ∈∅ T ≡ 1. Then, including more traits in S makes the resulting partition combine(S) finer and finer, until there are no more traits left to tally. Hence, the finest partition induced by a family of traits T = {Ti }ni=1 is combine(T ) = {C1 ∩ · · · ∩ Cn : C1 ∈ T1 , . . . , Cn ∈ Tn },

(7)

i.e., the combination of all primitive traits T ∈ T .7 All this leads to a more explicit description: Given a priority ranking “>” on a set of traits T , we can define a sequence of nested partitions: At the j-th level of the hierarchy we have the combination of j traits, while a path connecting the root node of Λ to said node represents the order in which these traits were introduced. For example, the instances of the composite trait “type and brand” (e.g., “Ford wagons” or “Toyota sedans”) could be reached by first prescribing the car’s type and then its brand, or the other way around. Either order reflects a certain priority so, more broadly, a priority ranking corresponds to the order in which traits are progressively combined to form composite ones. In more precise language, since combine(S) ≼ combine(S ′ ) when S ′ ⊆ S (see theorem 6 for a formal statement and proof), we conclude that 1 = combine(S0 ) ≽ · · · ≽ combine(Sj ) ≽ · · · ≽ combine(Sn ) = 0.

(8)

i.e., a family of traits T on A equipped with a priority ranking respecting its logical structure gives rise to a nested sequence of partitions of A which also respects the logical structure of T . This reduction of a family of traits to a sequence of nested partitions—a tree structure on A—is what forms the core of our reduction to the nested model. V Further properties of combinations of traits Recall here that the combination T ∈S T of a subset of traits S ⊆ T is defined as the coarsest partition of A that refines all traits T ∈ S. Under this definition, combining traits is easily seen to be commutative and associative; moreover, if we set 1 = {A}

and 0 = {{a} : a ∈ A},

(9)

1∧T =T

and 0 ∧ T = 0.

(10)

we also have

for all T ∈ A. Thus, from an algebraic viewpoint, combining traits behaves much like multiplication: the coarsest partition of A acts as an identity element for ∧, while its finest partition acts as 7. A priori, the partition combine(T ) need not coincide with the finest possible partition of A. For example, if the set of alternatives contains a yellow 2012 Chevy Impala and a yellow 2016 Impala, these two Impalas cannot be distinguished by either type, brand, color, or model; one would need to consider a new trait, year, to tell them apart. That said, if two alternatives are indistinguishable relative to all possible traits considered by an agent, we posit that they are, in fact, equivalent for said agent. By this token, we will be assuming in what V follows that the set of primitive traits T = {Ti }n provides a complete description of A, i.e., combine(T ) = i=1 T ∈T T = 0.

20

L EVERAGING S IMILARITIES IN M ULTI -A RMED BANDITS

an absorbing element. Finally, it is also easy to check that “combine” preserves unions in the sense that combine(S1 ∪ S2 ) = combine(S1 ) ∧ combine(S2 ) (11) for all subsets S1 , S2 of T . In other words, combining traits satisfies the following properties for all T, T ′ , T ′′ ∈ T : (a) Commutativity: T ∧ T ′ = T ′ ∧ T . (b) Associativity: T ∧ T ′ ∧ T ′′ = T ∧ (T ′ ∧ T ′′ ) = (T ∧ T ′ ) ∧ T ′′ . (c) Idempotency: T ∧ T = T . A key feature of the above is the interplay between primitives and conjunctions. Since a trait refines all its primitives (T ≼ T ′ whenever T ⊢ T ′ ), we also have T ∧ T ′ = T whenever T ⊢ T ′ ; in other words, the conjunction of a trait with any of its primitives returns the original trait unchanged. This suggests that the set of distinct composite traits that can be obtained from a set of “primitive” traits T is intimately linked to the prerequisite structure of T . To formalize this, fix a logical structure ⊢ on T = {Ti }ni=1 , and write Λj (T ) = {combine({Ti1 , · · · , Tij }) : i1 , . . . , ij = 1, . . . , n}

(12)

= {Ti1 ∧ · · · ∧ Tij : i1 , . . . , ij = 1, . . . , n} for the set of composite traits obtained by taking j-tuple conjunctions of elements of T (j = 0, . . . , n). Subsequently, putting all these traits together, write Λ ≡ Λ(T ) =

n [

Λj (T )

(13)

j=0

for the collection of all composite traits generated by the primitive traits of T . Of course, as we noted above, it is possible that different combinations of traits of T might lead to the same composite trait when primitives are involved (since adding primitives of already-included traits does not refine a composite trait). In principle, the logical structure of T might preclude some element of Λ—i.e., a conjunction of an arbitrary group of traits—from being obtained as the conjunction combine(S) of the traits in a node S ∈ Λ of the decision lattice. In fact, our next result shows that this possibility is never realized: the set of composite traits Λ ≡ Λ(T ) obtained from primitive traits is naturally embedded in the associated similarity structure Λ ≡ Λ(T , ⊢). Theorem 6 Let T = {Ti }ni=1 be a family of traits equipped with a logical structure “⊢”. Then, with notation as above, we have: (a) Every element of Λ is of the form combine(S) for some S ∈ Λ; concretely, Λ = {combine(S) : S ∈ Λ}

(14)

(b) For all S, S ′ ∈ Λ, we have combine(S) ≼ combine(S ′ ) 21

whenever S ⊇ S ′ .

(15)

E LDOWA R AHIER C ABLANT M ERTIKOPOULOS G AILLARD

In words, the conjunction operator combine is a surjective, order-preserving map – a lattice epimorphism – from (Λ, ⊇) to (Λ, ≼). Proof To begin, we claim that prim(T ) ∧ T = T for all T ∈ T : indeed, since T ≼ T ′ for all T ′ ∈ prim(T ), this is a simple consequence of the associativity of ∧ and the fact that T ∧ T ′ = T whenever T ≼ T ′ . With this auxiliary result at hand, let Ti1 ∧ · · · ∧ Tij ∈ Λ be a composite trait generated by the primitive traits of T . Then, letting Sj = prim(Tij ) ∪ {Tij } for all j = 1, . . . , j, we get Ti1 ∧ · · · ∧ Tij = (prim(Ti1 ) ∧ Ti1 ) ∧ · · · ∧ (prim(Tij ) ∧ Tij ) = combine(prim(Ti1 ) ∪ {Ti1 }) ∧ · · · ∧ combine(prim(Tij ) ∪ {Tij }) = combine(S1 ) ∧ · · · ∧ combine(Sj ) = combine(S1 ∪ · · · ∪ Sj ),

(16)

where the second and fourth lines follow directly from (11). Note also that we have prim(Tij ) ∈ Λ for all j = 1, . . . , j; moreover, since Tij ∈ prim(Tij )+ by definition, it follows that Sj ∈ Λ for all j = 1, . . . , j. Thus, with Λ closed under unions, we get S ≡ S1 ∪ · · · ∪ Sj , and our claim follows. Finally, for part (b), let S ′ = {Ti1 , . . . , Tij ′ } ⊆ {Ti1 , . . . , Tij } = S for some j ′ ≤ j. Then, by (11), we obtain combine(S) = Ti1 ∧ . . . ∧ Tij = (Ti1 ∧ . . . ∧ Tij ′ ) ∧ (Tij ′ +1 ∧ . . . ∧ Tij ) ≼ Ti1 ∧ . . . ∧ Tij ′ = combine(S ′ ),

(17)

and our proof is complete. This theorem serves as a sanity check that the nested presentation of a similarity structure is, indeed, faithful.

Appendix B. Proofs of Section 3 We provide here the proof of Proposition 1, which is restated below. Proposition 1 (One-point lower boundp under tree-induced similarity) Let ρ := σL . For K > 2, T > 32(K −1) log(14), and ρ > 0.22 (K − 1)/T , any randomized one-point bandit algorithm satisfies   1 p sup E RegT,1 (y1:T ) > T (K − 1). 504 (yt )T ∈YσT t=1

Equivalently,√for any such algorithm there exists a tree-compatible loss sequence (yt )Tt=1 ∈ YσT inducing Ω( KT ) expected regret. Proof Let ρ := σL . We define n o Cρ := x ∈ [0, 1]K : max |x(a) − x(b)| ≤ ρ a,b∈A

22

and

n o CρT := (yt )Tt=1 : ∀t, yt ∈ Cρ .

L EVERAGING S IMILARITIES IN M ULTI -A RMED BANDITS

Input: sequence of regularizers (ψt )t≥1 Initialization: p1 = arg minp∈∆K ψ1 (p) 1 for t ≥ 1 do P ℓ (anc (A )) 2 sample At ∼ pt and set zt (a) = j∈[L] Ja ∼j At K ptt [ancjj (Att )] for all a ∈ A P 3 set pt+1 = arg min s≤t zs , p + ψt+1 (p) p∈∆K

4 end

Algorithm 2: FTRL with Semi-Bandit Feedback By Gerchinovitz and Lattimore (2016, Corollary 4), for K > 2, T > 32(K − 1) log(14), and p ρ > 0.22 (K − 1)/T , any randomized one-point bandit algorithm satisfies sup T (yt )T t=1 ∈Cρ

  E RegT,1 (y1:T ) >

1 p T (K − 1). 504

It remains to show that CρT ⊆ YσT . Fix any x ∈ Cρ and any a, b ∈ A. Then |x(a) − x(b)| ≤ ρ = σL . Since s(a, b) ∈ [L] for a ̸= b and (σj ) is nonincreasing, we have σL ≤ σs(a,b) . Thus |x(a) − x(b)| ≤ σs(a,b) , so x satisfies the tree-compatibility constraint. Therefore CρT ⊆ YσT , and taking the supremum over YσT yields the proposition.

Appendix C. Proofs of Section 5 For convenience, we summarize the algorithm template used in Section 5 in Algorithm 2. We prove the following proposition before moving on to the proof of Theorem 2, which is restated afterwards.

Proposition 7 Algorithm 2 with ψt (p) =

X X p p p[v] − p[v] satisfies that 5 max{t, 20} Rj j∈[L]

v∈Vj

T Xp √ X p 1 X √ E RegT,1 ≤ 15 Rj |Vj | + 2 5 Rj pt [v] − pt [v] . t j∈[L] v∈V t=1 j∈[L]

X

j

Proof This result is an application of Lemma 17 with c = 5; ξj = 1 for all j ∈ [L]; Mt = [L] for all t ≥ 1; and filtration (Ft )t≥0 with Ft being the σ-algebra generated by (As )s≤t and (ℓs )s≤t . In particular, as Lemma 17 requires, it holds that ℓt (v) ∈ [0, Rj ] for all j ∈ [L], v ∈ Vj , and t ≥ 1; pt is measurable w.r.t. Ft−1 ; the law of At conditioned on Ft−1 is pt ; and for all a, a′ ∈ A, X v≻a

Et [ℓt (v) | v ≻ At ] −

X

Et [ℓt (w) | w ≻ At ] = Et [yt (a) − yt (a′ )]

w≻a′

P simply since v≻a ℓt (v) = yt and ℓt (v) is independent of Jv ≻ At K conditioned on Ft−1 as the adversary can only react to the learner’s decisions that were made up to the previous round.

23

E LDOWA R AHIER C ABLANT M ERTIKOPOULOS G AILLARD

p p P P 5 max{t, 20} j∈[L] Rj v∈Vj p[v] − p[v] and zt (a) =

Theorem 2 FTRL with ψt (p) = P v≻a Jv ≻ At Kℓt (v)/pt [v] satisfies  RegT,1 ≤

p p 15pKeff (R) + 4 5Keff (R)T 30 Keff (R) + 20Keff,∆ (R) ln(eT ) (under Condition 1)

p P Proof Starting from the bound of Proposition 7, one can use the facts that v∈Vj pt [v] − pt [v] ≤ √ p √ P |Vj | for any j ∈ [L] and that Tt=1 1/ t ≤ 2 T to directly obtain the first result. Concerning the second result, Lemma 14 implies that √ X 2 5Rj X p 20 X 2 √ 2 pt [v] − pt [v] ≤ ⟨∆, pt ⟩ + Rj t t v∈V j∈[L] j∈[L] j

1

X e v∈Vj : ∆(v)̸ =0

e ∆(v)

P e e : V → R such that (i) ∆(v) e ∀a ∈ A, and (iii) for any ∆ ≥ 0 ∀v ∈ V , (ii) ∆(a) ≥ v≻a ∆(v) e |{v ∈ Vj | ∆(v) = 0}| ≤ 1 for all j ∈ [L]. Then, using that E∆(At ) = E⟨∆, pt ⟩, we obtain that RegT,1 ≤ 15

X j∈[L]

Then, using that we get that

" T # T q X X 1 1 X 2 Rj |Vj | + E ∆(At ) + 10 Rj 2 t t=1

t=1

j∈[L]

X e v∈Vj : ∆(v)̸ =0

1 . e ∆(v)

PT

t=1 1/t ≤ ln(eT ) and that, by assumption, the second term is at most RegT,1 /2,

RegT,1 ≤ 30

X

Rj

q X |Vj | + 20 Rj2

j∈[L]

j∈[L]

X e v∈Vj : ∆(v)̸ =0

ln(eT ) . e ∆(v)

(18)

e In particular, let ∆(v) b := To reach a more concrete bound we impose now a simple form on ∆. mina≺v ∆(a), and fixing any distribution q ∈ ∆L (with strictly positive weights) over the levels e b of the tree, we take ∆(v) = q(j)∆(v) for v ∈ Vj . This is a valid choice since it is non-negative, satisfies X X X e b ∆(v) = q(j)∆(anc q(j)∆(a) = ∆(a) j (a)) ≤ v≻a

j∈[L]

j∈[L]

for any a ∈ A, and can only vanish at one node per level by the assumption that |{a ∈ A : ∆(a) = 0}| ≤ 1. It then follows from (18) that RegT,1 ≤ 30

X j∈[L]

Rj

q X Rj2 |Vj | + 20 q(j) j∈[L]

The sought bound now follows by choosing q(j) ∝ Rj

24

X b v∈Vj : ∆(v)̸ =0

qP b v∈Vj : ∆(v)̸ =0

ln(eT ) . b ∆(v)

b 1/∆(v).

L EVERAGING S IMILARITIES IN M ULTI -A RMED BANDITS

Input: sequence of regularizers (ψt )t≥1 , sequence of constants (bj )L j=1 , number of extra queried points n ∈ [L], distribution Ξ over subsets of [L] of cardinality n P Define: for j ∈ [L], let ξj := S∈supp(Ξ) Jj ∈ SKΞ(S) Initialization: p1 = arg minp∈∆K ψ1 (p) 1 for t ≥ 1 do 2 sample At,1 ∼ pt 3 sample Mt ∼ Ξ 4 set Mt = {j ∈ Mt | j + 1 ∈ / Mt } 5 for j ∈ Mt do set smpt (j) = At,1 6 i←2 7 for j ∈ Mt do 8 sample At,i ∼ pt | At,i ∼j−1 At,1 9 set smpt (j − 1) = At,i 10 i←i+1 11 end X yt (smpt (j)) − yt (smpt (j − 1)) + bj 12 for all a ∈ A, set zt (a) = Ja ∼j At,1 K ξj pt [ancj (At,1 )] P j∈Mt 13 set pt+1 = arg min s≤t zs , p + ψt+1 (p) p∈∆K

14 end

Algorithm 3: FTRL with n + 1-Point Bandit Feedback

Appendix D. Proofs of Section 6 We provide here a generalization of Algorithm 1 to handle n + 1-point feedback, with n between 2 and L. We prove a generic regret bound for this algorithm, from which Theorem 3 (restated afterwards) follows as a corollary. Theorem 8 Algorithm 3 with ψt : Rd+ → R given by √ n√ q oX X σj p 4 c p max ψt (x) := p t, c(c − 1)/ξj x[v] − x[v] (c − 1) j∈[L] ξj v∈V j

where c ≥ 2, and bj = σj for all j ∈ [L] satisfies X σj p

RegT,n+1 ≤ 6c

j∈[L]

ξj

√ 16 c X σj p p |Vj | + p |Vj |T . (c − 1) j∈[L] ξj

Further, if Condition 1 holds, then, Algorithm 3 also satisfies X σj p 64c RegT,n+1 ≤ 12c |Vj | + ξj c−1 j∈[L]

!2 X σj p p Γ(j, ∆) ln(eT ) . ξ j j∈[L]

Proof Let Ft be the σ-algebra generated by (As,i )s≤t,i∈[n+1] , (Ms )s≤t , and (ys )s≤t . In the sequel, we will for brevity denote P(· | Ft−1 ) by Pt (·) and E[· | Ft−1 ] by Et [·]. Clearly, Pt (At,1 = a) = 25

E LDOWA R AHIER C ABLANT M ERTIKOPOULOS G AILLARD

pt (a). For 2 ≤ i ≤ n + 1, we posit that a fixed function ζi : supp(Ξ) → {0, . . . , L − 1} gives, at every round t, the unique level ζi (Mt ) such that At,i = smpt (ζi (Mt )). Notice then that for 2 ≤ i ≤ n + 1, X

Pt At,i = a | At,1 = a′ , Mt = S Pt At,1 = a′ , Mt = S Pt (At,i = a) = a′ ∈A,S∈supp(Ξ)

X

=

Pt At,i = a | At,1 = a′ , Mt = S Pt At,1 = a′ Pt Mt = S

a′ ∈A,S∈supp(Ξ)

X

=

Ja′ ∼ζi (S) aK

a′ ∈A,S∈supp(Ξ)

= pt (a)

X

Ξ(S)

a′ ∈A

S∈supp(Ξ)

= pt (a)

X

X

Ξ(S)

S∈supp(Ξ)

pt (a) pt (a′ )Ξ(S) pt [ancζi (S) (a′ )]

Ja′ ∼ζi (S) aK 1

1 pt [ancζi (S) (a′ )]

X

pt [ancζi (S) (a)] ′

a ∈A

pt (a′ )

Ja′ ∼ζi (S) aKpt (a′ ) = pt (a) ,

where the second equality uses that At and St are independent conditioned on Ft−1 , and the third equality follows from the sampling rules of Algorithm 3. Combining this with the fact that yt is independent of the learner’s actions at round t conditioned on Ft−1 , we get that " # n+1   1 X E yt (At,i ) = E yt (At,1 ) . n+1 i=1

Thus, RegT,n+1 = E

" T X

# yt (At,1 ) − min E a∈A

t=1

" T X

# yt (a) .

(19)

t=1

Towards applying Lemma 17, fix a mapping λ : V → A such that v ≻ λ(v) for all v ∈ V. Further, for each v ∈ V, let (ωt (v))t≥1 be a random sequence of actions given by ( smpt (lvl(v)) if v ≻ At,1 and {lvl(v), lvl(v) + 1} ∩ Mt ̸= ∅ ωt (v) = λ(v) otherwise . Note that for a ∈ A, ωt (a) = a. Next, we define at every round t a mapping ℓt : V → R given by ℓt (v) := yt (ωt (v)) − yt (ωt (prt(v))) + σlvl(v) . Note that for any v ∈ Vj , |ℓt (v)| ≤ 2σj

and ℓt (v) ≥ 0 .

Further, define   ℓet (v) := Et ℓt (v) | v ≻ At,1 , lvl(v) ∈ Mt , so that   ℓet (v) = Et yt (ωt (v)) | v ≻ At,1 , lvl(v) ∈ Mt   − Et yt (ωt (prt(v))) | v ≻ At,1 , lvl(v) ∈ Mt + σlvl(v) . 26

L EVERAGING S IMILARITIES IN M ULTI -A RMED BANDITS

We aim to show now that the sum of the first two terms over v ∈ V : v ≻ a is a telescoping sum for any action a ∈ A. Towards that, we can rewrite the second term as follows for any j ∈ [L] and v ∈ Vj :

    Et yt (ωt (prt(v))) | v ≻ At,1 , lvl(v) ∈ Mt = Et yt (ωt (prt(v))) | v = ancj (At,1 ), j ∈ Mt   = Et yt (smpt (j − 1)) | v = ancj (At,1 ), j ∈ Mt h  i = Et Et yt (smpt (j − 1)) | v = ancj (At,1 ), j ∈ Mt , yt hP i pt (a) = Et Jprt(v) ≻ aK y (a) , t a∈A pt [prt(v)]

where the second equality follows from the definition of ωt , the third is an application of the tower rule; and the fourth follows from the sampling rules of Algorithm 3, the fact that prt(v) = ancj−1 (At,1 ) whenever v = ancj (At,1 ), and the fact that yt is drawn by the environment independently of the learner’s actions at round t, conditioned on Ft−1 . At the same time, it similarly holds that

    Et yt (ωt (v)) | v ≻ At,1 , lvl(v) ∈ Mt = Et yt (ωt (v)) | v = ancj (At,1 ), j ∈ Mt   = Et yt (smpt (j)) | v = ancj (At,1 ), j ∈ Mt h  i = Et Et yt (smpt (j)) | v = ancj (At,1 ), j ∈ Mt , yt i hP pt (a) yt (a) , = Et a∈A Jv ≻ aK pt [v]

where in the last step we used that, at round t, given that ancj (At,1 ) and j ∈ Mt , the conditional law (w.r.t. Ft−1 ) of smpt (j) is Jv ≻ ·Kpt (·)/pt [v] regardless of whether j belongs to Mt↓ or Mt \ Mt↓ ; in the latter case, this holds directly via the sampling rule of Algorithm 3 for smpt (j), while in the former, we use that smpt (j) = At,1 and that conditioned on Ft−1 , the law of At,1 is pt . We can then conclude that for any a ∈ A,

X

  X   X ℓet (v) = Et yt (a) − pt (a′ )Et yt (a′ ) + σj . a′ ∈A

v≻a

j∈[L]

Implying that for any a, a′ ∈ A,

X v≻a

ℓet (v) −

X

  ℓet (w) = Et yt (a) − yt (a′ ) .

w≻a′

27

E LDOWA R AHIER C ABLANT M ERTIKOPOULOS G AILLARD

Notice, moreover, that X v≻a

Jv ≻ At,1 , lvl(v) ∈ Mt K

ℓt (v) ξlvl(v) pt [v]

X yt (ωt (v)) − yt (ωt (prt(v))) + σlvl(v) Jv ≻ At,1 , lvl(v) ∈ Mt K ξlvl(v) pt [v] v≻a

X yt ωt (ancj (a)) − yt ωt (ancj−1 (a)) + σj Ja ∼j At,1 , j ∈ Mt K = ξj pt [ancj (a)] j∈[L]

X yt ωt (ancj (At,1 )) − yt ωt (ancj−1 (At,1 )) + σj Ja ∼j At,1 , j ∈ Mt K = ξj pt [ancj (At,1 )] j∈[L]

X yt ωt (ancj (At,1 )) − yt ωt (ancj−1 (At,1 )) + σj Ja ∼j At,1 K = ξj pt [ancj (At,1 )] =

j∈Mt

=

X j∈Mt

Ja ∼j At,1 K

yt (smpt (j)) − yt (smpt (j − 1)) + σj = zt (a) , ξj pt [ancj (At,1 )]

where the last step follows form the definition of ωt . Finally, it is easily verifiable that in our case, Pt (j ∈ Mt ) = ξj ∀j ∈ [L], and Jv ≻ At K ⊥ ⊥ Jlvl(v) ∈ Mt K | Ft−1 ∀v ∈ V. We can now invoke Lemma 17 with Rj = 2σj for j ∈ [L]; At = At,1 for t ≥ 1; and ξj , Mt , yt , ℓt , and (Ft )t≥0 as used in the current context; yielding that

E

" T X t=1

# yt (At,1 ) − min E a∈A

√ 8 c

T X X p
1 X σj √ p E pt [v] − pt [v] yt (a) ≤ p (c − 1) t=1 t j∈[L] ξj v∈V t=1 j X σj q + 6c |Vj | . ξj

" T X

#

j∈[L]

which is also a bound on RegT,n+1 via (19). At this junction, the rest of the proof proceeds similarly to the proof of Theorem 2.

p √ P  p q P Theorem 3 Algorithm 1 with ψt (p) = 2 6 j∈[L] (σj / δj ) max t, 6/δj v∈Vj x[v]− x[v] and bj = σj for all j ∈ [L] satisfies ( p √ √ p 18pKeff (σ/δ) + 8 6 Keff (σ/ √ δ)T . RegT,2 ≤ 36 Keff (σ/δ) + 96Keff,∆ (σ/ δ) ln(eT ) (under Condition 1) Proof This follows as a special case of Theorem 8 choosing c = 3 and Mt = {jt } at every round.

28

L EVERAGING S IMILARITIES IN M ULTI -A RMED BANDITS

Appendix E. Proofs of Section 7 E.1. Proof of Corollary 4 We provide here the proof of Corollary 4, which is restated below.
Corollary 4 Suppose we run Algorithm 1 on the tree T (Aj )L j=0 with parameters ψt , bj as defined in Theorem 3, σj = c23−j , and δj ∝ 2−2j/3 |Aj |1/3 . Then, assuming that minj∈[L] δj ≥ 1/T , it holds that √ q
−L T, RegT,2 ≤ 16 · (9 + 4 6) Keff (Aj )L j=0 T + c 2 P 3
2 −2j/3 |A |1/3 := where Keff (Aj )L c 2 . j j=0 j∈[L] Proof Firstly, since AL is a c2−L -cover of A, we have that # " T # " T X X1
yt (At,1 ) + yt (At,2 ) − min E yt (a) + c 2−L T . RegT,2 ≤ E a∈AL 2 t=1

t=1

So, using Theorem 3 gives that p √ √ q RegT,2 ≤ 18 Keff (σ/δ) + 8 6 Keff (σ/ δ)T + c 2−L T √ √ q ≤ 2(9 + 4 6) Keff (σ/ δ)T + c 2−L T , q p √ where we have used in the second step that Keff (σ/δ) ≤ Keff (σ/ δ)T by the assumption that minj∈[L] δj ≥ 1/T . Next, observe that q X 2−j q X 2−j q X σj q √ 3 3 p p p Keff (σ/ δ) = |Aj | = c2 |Aj | ≤ c2 |Aj | , δj δj δj j∈[L] j∈[L] j∈[L] where the last step uses that Aj ⊆ Aj . Finally, our choice for δj entails that  3/2 X 2−j q X p |Aj | =  2−2j/3 |Aj |1/3  . δ j j∈[L] j∈[L]

E.2. On the Near-Optimality of the Tree Constructed in Section 7 We will assume here that A isp finite (with cardinality K) and that T is large enough so that dmin := mina,b∈A : a̸=b dA,∞ (a, b) ≥ K/T . The effect of this is that executing Algorithm 1 on a strict √ subset of the action set would force a worst-case approximation error of order KT , which would ′ nullify any attempt to leverage the structure. Now, any nested sequence (Pj )L j=0 of partitions of A such that P0 = {A} and PL′ = {{a}}a∈A can be used to build a tree of L′ levels with its leaves 29

E LDOWA R AHIER C ABLANT M ERTIKOPOULOS G AILLARD

coinciding with the action set. In a similar manner to Corollary 4, executing Algorithm 1 on this tree results in a regret bound featuring a Keff of (with the optimal choice of δ) !3

′

L X

2/3 σ∗,j |Pj |1/3

where σ∗,j := max max dA,∞ (a, b) . S∈Pj−1 a,b∈S

j=1

It is not clear if directly optimizing this quantity in terms of the nested structure is a feasible endeavor. Instead, we show in the following lemma that the recipe we described for constructing the tree—by forming a c2−j cover of A at level j—minimizes this quantity up to small constants, provided that these covers are optimal. Fortunately, near-optimal covers can be constructed in time polynomial in K. At any level j, we can associate each action a ∈ A with the set {a′ ∈ A : dA,∞ (a, a′ ) ≤ c2−j }; so, building an optimal c2−j -cover reduces to the set cover problem, which can be solved in polynomial time using a simple greedy algorithm (Johnson, 1974). In particular, using this greedy algorithm, one builds a cover that is at worst an extra factor of 1 + ln K larger than the minimum size (Johnson, 1974; Slavı́k, 1997). Lemma 9 Set c = maxa,b∈A dA,∞ (a, b) and L = 1 + ⌊− log2 (c−1 dmin )⌋. Let A0 := {a0 } for some arbitrary action a0 and (Aj )j∈[L] be a sequence of subsets of A such that Aj is an optimal ′ c2−j -cover of A. Then, for any nested sequence (Pi )L i=0 of partitions of A such that P0 = {A} and PL′ = {{a}}a∈A , it holds that  2

c

L X

3 −2j/3

2

|Aj |

1/3 

!3

′

≤ 20

j=1

L X

2/3 σ∗,i |Pi |1/3

,

i=1

where σ∗,i := maxS∈Pi−1 maxa,b∈S dA,∞ (a, b). Note that this choice of L ensures that c2−L < dmin , which implies that AL = A. Proof We begin by defining a mapping f : [L] → [L′ ] as follows: n o f (j) := min i ∈ [L′ ] | max dA,∞ (a, b) < c2−j ∀S ∈ Pi . a,b∈S

(20)

Since PL′ = {{a}}a∈A , maxa,b∈S dA,∞ (a, b) = 0 for all S ∈ PL′ ; thus, the set in the R.H.S. of (20) is never empty. Note that the pre-image of i ∈ [L′ ], if non-empty, is an interval Bi ⊆ [L] satisfying that max c2−j ≤ σ∗,i . j∈Bi

This is easy to see for i = 1: since we set c = maxa,b∈A dA,∞ (a, b), we have that σ∗,1 = c. (Recall that σ∗,i concerns the maximum diameter of the subsets of Pi−1 , not Pi .) For i ≥ 2, if c2−j > σ∗,i for a certain j ∈ Bi , then it must be that j ∈ Bi′ for some i′ ∈ {1, . . . , i − 1}, which is a contradiction. It then follows that X j∈Bi

−j 2/3

c2

2/3 ≤ σ∗,i

∞ X

2−2r/3 ≤

r=0

30

22/3 2/3 σ∗,i . 2/3 2 −1

L EVERAGING S IMILARITIES IN M ULTI -A RMED BANDITS

This allows concluding that  c2 

L X

3

!3

′

2−2j/3 |Pf (j) |1/3  ≤ 20

j=1

L X

2/3 σ∗,i |Pi |1/3

.

i=1

To obtain the sought result, it remains to use that |Pf (j) | ≥ |Aj |. This holds since Aj is a c2−j cover of A with minimum cardinality, meantime, collecting an arbitrary member of each subset in Pf (j) results too in a c2−j -cover of A.

E.3. Proof of Corollary 5 We provide here the proof of Corollary 5, which is restated below.
Corollary 5 Let T ≥ 8. Algorithm 1 run on the tree T (Aj )L j=0 induced by the covers described √ above with L = ⌊ d1 log2 (T )⌋ and parameters ψt , bj as defined in Theorem 3, σj = GD d 23−j and δj ∝ 2j(d−2)/3 , satisfies the following regret upper bound  √  if d = 1  T √ (ln T )3/2 T if d = 2 , RegT,2 ≲ GD ·   √dT d−1 d if d > 2 where ≲ denotes an inequality up to a universal constant. Proof Since |Aj | ≤ 2jd and L = ⌊ d1 log2 (T )⌋, Corollary 4 gives that (supposing for now that minj δj ≥ 1/T ) √

!3/2

√

RegT,2 ≤ 16 · (9 + 4 6) · GD d ·

X

2j(d−2)/3

√

√ d−1 T + 2GD d T d .

j∈[L]

Then, observe that !3/2 X

2

j(d−2)/3

( ≤

j∈[L]

L3/2 d 11 · 2L( 2 −1)+

if d = 2 if d ̸= 2

where ( · )+ = max{·, 0}. This leads to the stated regret bound after using that L = ⌊ d1 log2 (T )⌋. √ −1/2 To conclude the proof, it only remains to check that maxj∈[L] δj ≤ T for T ≥ 8. Indeed, • if d = 1, X 1/2 L √ j L L 1 −1/2 −1/2 − ≤ δL = 26 2 3 ≤ 2 · 2 6 ≤ 2T 6 ≤ T δj j=1

as soon as T ≥ 8; √ p √ −1/2 • if d = 2, δj = L ≤ log2 (T )/2 ≤ T ; 31

E LDOWA R AHIER C ABLANT M ERTIKOPOULOS G AILLARD

• if d ≥ 3, d−2 −1/2 −1/2 δj ≤ δ1 = 2− 6

X L

2

j

d−2 3

1/2

≤2

1+L

d−2 6

d−2

1

≤ 2T 6d ≤ 2T 6 ≤

√ T

j=1

as soon as T ≥ 8.

Appendix F. FTRL Analysis F.1. Helper Lemmas Lemma 10 For t ≥ 1, let (ψt )t be a sequence of functions where ψt : RK → (−∞, +∞]. Additionally, let (zt )t be an arbitrary sequence of vectors in RK . Define p1 := arg minp∈∆K ψ1 (p) and for t ≥ 2, P pt := arg min s≤t−1 zs , p + ψt (p) . p∈∆K

Then, assuming that the sequence (pt )t is well-defined, it holds for any comparator q ∈ ∆K and horizon T ≥ 1 that T T X X ⟨zt , pt − q⟩ ≤ ψT +1 (q) − ψ1 (p1 ) + ψt (pt+1 ) − ψt+1 (pt+1 ) t=1

t=1

+

T X

Ft pt ,

P

s≤t zs

− Ft pt+1 ,

P

s≤t zs

t=1

where for t ≥ 1, z ∈ Rd , and p ∈ ∆K ; we define Ft (p, z) := ⟨z, p⟩ + ψt (p). Proof For any t ∈ [T ], pt = arg minp∈∆K Ft p, T X

⟨zt , pt − q⟩ =

t=1

≤

T X t=1 T X

P

s≤t−1 zs . So,

⟨zt , pt ⟩ + ψT +1 (q) − FT +1 (q,

P

s≤T zs )

⟨zt , pt ⟩ + ψT +1 (q) − FT +1 (pT +1 ,

P

s≤T zs ) .

t=1

Moving on, −FT +1 (pT +1 ,

P

s≤t zs ) = −ψ1 (p1 ) + ψ1 (p1 ) − FT +1 (pT +1 ,

P

= −ψ1 (p1 ) + F1 (p1 , 0) − FT +1 (pT +1 , = −ψ1 (p1 ) +

T X

Ft (pt ,

t=1

32

P

s≤T zs )

P

s≤T zs )

s≤t−1 zs ) − Ft+1 (pt+1 ,

P

s≤t zs ) .

,

L EVERAGING S IMILARITIES IN M ULTI -A RMED BANDITS

Lastly at any round t, P P ⟨zt , pt ⟩ + Ft (pt , s≤t−1 zs ) − Ft+1 (pt+1 , s≤t zs ) P P = Ft (pt , s≤t zs ) − Ft+1 (pt+1 , s≤t zs ) P P = Ft (pt , s≤t zs ) − Ft (pt+1 , s≤t zs ) + ψt (pt+1 ) − ψt+1 (pt+1 ) , concluding the proof. We say that a convex function f : R → (−∞, +∞] is Legendre if it is proper, closed, essentially smooth (see (Rockafellar, 1970, Chapter 26) for a definition) and strictly convex on int(dom(f )). Lemma 11 Let f : R → (−∞, +∞] be a convex function of the Legendre type satisfying R++ ⊆ dom(f ). For any p ∈ ∆K , define X X f (p[v]) , µj ψ(p) := v∈Vj

j∈[L]

where µj > 0 is a fixed weight for level j. Fix two vectors y, z ∈ RK , and let q := arg min⟨p, y⟩ + ψ(p) . p∈∆K

Then, for any (cj )j∈[L] ∈ RL and ℓ : V → R such that z(a) =

P

v≻a ℓ(v), it holds that

⟨q, y + z⟩ + ψ(q) − min ⟨p, y + z⟩ + ψ(p) p∈∆K X X
≤ µj Df ∗ f ′ (p[v]) − (ℓ(v) − cj )/µj f ′ (p[v]) . j∈[L]

v∈Vj

Proof Associate to every v ∈ V a vector hv ∈ RK such that hv (a) := Jv ≻ aK; hence, for any vector x ∈ RK , X x ⊤ hv = x(a) = x[v] . a∈A : v≻a

Moreover, let ηv := 1/µlvl(v) . So, for any p ∈ ∆K , ψ(p) :=

X 1 v∈V

ηv

f (p⊤ hv ) .

Hence, the result would follow from Proposition 26 if its conditions on f and {hv }v∈V hold here. By the assumption that f is Legendre, it is indeed proper, closed, and essentially smooth as required. Next, note that for any v ∈ V, the definition of hv together with the assumption that R++ ⊆ dom(f ) K ⊤ guarantee that RK ++ ⊆ {x ∈ R : hv x ∈ dom(f )}. Hence, K ⊤ K relint({x ∈ RK : h⊤ v x ∈ dom(f )}) = int({x ∈ R : hv x ∈ dom(f )}) ⊇ R++ .

And since relint(∆K ) ⊂ RK ++ and relint(∆K ) ̸= ∅, it holds, as required, that
relint(∆K ) ∩ ∩v∈V relint({x ∈ RK : h⊤ v x ∈ dom(f )}) ̸= ∅ .

33

E LDOWA R AHIER C ABLANT M ERTIKOPOULOS G AILLARD

Lemma 12 Let f : R+ → (−∞, +∞] be a convex function of the Legendre type satisfying R++ ⊆ dom(f ). For any p ∈ ∆K , define X X µj f (p[v]) , ψ(p) := v∈Vj

j∈[L]

where µj > 0 is a fixed weight for level j. It holds for any p ∈ ∆K and ζ : V → R that X X X X µj f ∗ (−ζ(v)/µj ) . ζ(v) + −ψ(p) ≤ p(a) a∈A

v≻a

j∈[L]

v∈Vj

Proof Using the same arguments in the proof of Lemma 11 (note that µj f is Legendre when f is Legendre), we can leverage the first result of Lemma 25 (taking u = 0) to obtain that X X X X p(a) ζ(v) ≥ − f ∗ (−ζ(v)/µj ) , ψ(p) + µj a∈A

v≻a

j∈[L]

v∈Vj

where we have used that (µj f )∗ (·) = µj f ∗ (·/µj ).

F.1.1. S PECIFIC R ESULTS FOR THE NESTED T SALLIS R EGULARIZER √ Lemma 13 Let f (x) = η2 (x − x) with η > 0. Then, for any p > 0, c > 1, and y ∈ R, such that y ≥ − cη1√p , it holds that
Df ∗ f ′ (p) − y f ′ (p) ≤

c 3 ηp /2 y 2 . c−1

1 for ηz < 2. Note that Proof We have that f ′ (x) = η2 (1 − 2√1 x ) and f ∗ (z) = η1 · 2−ηz

1 1 1 1 ηf ′ (p) = 2 − √ < 2 and ηf ′ (p) − ηy = 2 − √ − ηy ≤ 2 − √ + √ < 2 , p p p c p where we have used that p > 0 and that ηy ≥ − c√1 p with c > 1. Hence,
Df ∗ f ′ (p) − y f ′ (p) = yp + f ∗ (f ′ (p) − y) − f ∗ (f ′ (p))   1√ 1 = yp + p √ −1 η 1 + ηy p yp = yp − √ 1 + ηy p ηp3/2 y 2 √ 1 + ηy p c 3 ≤ ηp /2 y 2 , c−1

=

where the last inequality uses the assumption that ηy ≥ − c√1 p .

34

L EVERAGING S IMILARITIES IN M ULTI -A RMED BANDITS

Lemma 14 P Fix any p ∈ ∆K , µj > 0 for j ∈ [L], λ ∈ R, g ∈ RK , and ζ : V → R such that g(a) + λ ≥ v≻a ζ(v) for a ∈ A and ζ(v)/µj > −2 for j ∈ [L] and v ∈ Vj . Then, it holds that 2

X

µj

Xp X X pt [v] − pt [v] ≤ ⟨g, p⟩ + λ + µj v∈Vj

j∈[L]

v∈Vj

j∈[L]

1 . 2 + ζ(v)/µj

e ≥ 0 ∀v ∈ V , (ii) g(a) ≥ In particular, for any ζe: V → R such that (i) ζ(v) e |{v ∈ Vj | ζ(v) = 0}| ≤ 1 for all j ∈ [L]; it holds that 2

X

µj

j∈[L]

Xp X µ2j pt [v] − pt [v] ≤ ⟨g, p⟩ + v∈Vj

j∈[L]

X e =0 v∈Vj : ζ(v)̸

P

v≻a ζ(v), and (iii)

e

1 . e ζ(v)

√ Proof Let f (x) = 2(x − x). Then f ∗ (y) = 1/(2 − y) for y < 2 and +∞ elsewhere. Hence, applying Lemma 12 with this function gives that 2

X

µj

j∈[L]

X X X Xp X pt [v] − pt [v] ≤ p(a) ζ(v) + µj v∈Vj

v≻a

a∈A

≤ ⟨g, p⟩ + λ +

v∈Vj

j∈[L]

X j∈[L]

µj

X v∈Vj

1 2 + ζ(v)/µj

1 , 2 + ζ(v)/µj

where the condition ζ(v)/µj > −2 for v ∈ Vj ensures we respect the effective domain of f ∗ . P e − µj for v ∈ Vj , getting as a Now, for the second part, choose λ = − j∈[L] µj and ζ(v) = ζ(v) consequence that

2

X j∈[L]

 X X Xp pt [v] − pt [v] ≤ ⟨g, p⟩ + µj  µj v∈Vj

j∈[L]

v∈Vj

 1 − 1 . e 1 + ζ(v)/µ j

e e Finally, to obtain the sought result we use that 1/(1 + ζ(v)/µ j ) ≥ µj /ζ(v) for any v such that e e ζ(v) ̸= 0 and that 1/(1 + ζ(v)/µ j ) = 1 otherwise, which we assumed to be the case for at most one node per level.

Lemma 15 Fix p ∈ ∆d and x ∈ Rd . It holds that for any j ∈ [d] that X i∈[d]

 
2 P 3 1 3 1 p(i) /2 Ji = jKx(i)/p(i) − x(j) = x(j)2 p(j)− /2 − 2p(j) /2 + i∈[d] p(i) /2 .

It also holds that X

  X P 1 1 3 1 p(j) p(j)− /2 − 2p(j) /2 + i∈[d] p(i) /2 ≤ 2 p(j) /2 − p(j) .

j∈[d]

j∈[d]

35

E LDOWA R AHIER C ABLANT M ERTIKOPOULOS G AILLARD

Proof We have that X
2 3 p(i) /2 Ji = jKx(i)/p(i) − x(j) i∈[d]

=

X i∈[d]

=

X i∈[d]

2 3 p(i) /2 Ji = jKx(j)/p(j) − x(j)
3 p(i) /2 Ji = jKx(j)2 /p(j)2 + x(j)2 − 2Ji = jKx(j)2 /p(j)

  P 1 1 3 = x(j)2 p(j)− /2 − 2p(j) /2 + i∈[d] p(i) /2 . Next, X

  P 1 1 3 p(j) p(j)− /2 − 2p(j) /2 + i∈[d] p(i) /2

j∈[d]

=

X

p(j) /2 − 2 1

j∈[d]

=

X

p(j) /2 − 1

=

X

X

p(j) /2 + 3

j∈[d]

j∈[d]

X

X

p(j) /2 3

j∈[d]

p(j) /2 3

j∈[d] 1/2

p(j) (1 − p(j))

j∈[d]

=

X

p(j) /2 (1 − p(j) /2 )(1 + p(j) /2 ) 1

1

1

j∈[d]

≤2

X

p(j) /2 (1 − p(j) /2 ) = 2 1

1

j∈[d]

X

p(j) /2 − p(j) . 1

j∈[d]

F.2. Generic Regret Guarantees for the Nested Tsallis Regularizer Lemma 16 Let (ηt,j )t≥1,j∈[L] be a sequence of positive numbers. Accordingly, for every t ≥ 1, define ψt : Rk → (−∞, +∞] as ψt (x) := 2

X 1 X p
x[v] − x[v] ηt,j

j∈[L]

v∈Vj

for x ∈ RK . Let (zt )t be a sequence of loss vectors in RK , and define P p1 := arg min ψ1 (p) and for t ≥ 2, pt := arg min s≤t−1 zs , p + ψt (p) . p∈∆K

p∈∆K

Fix c > 1, and for each t ≥ 1, fix a sequence (ct,j )j∈[L] ∈ RL and a function ℓt : V → R such that zt (a) =

X

ℓt (v) ∀a ∈ A and

ℓt (v) − ct,j ≥ −

v≻a

36

1 p ∀j ∈ [L] , v ∈ Vj . cηt,j pt [v]

L EVERAGING S IMILARITIES IN M ULTI -A RMED BANDITS

Then, it holds for horizon T ≥ 1 and comparator q ∈ ∆k that T T +1 X X p X X
⟨zt , pt − q⟩ ≤ 2 ηet,j pt [v] − pt [v] t=1

t=1 j∈[L]

v∈Vj

+

T X
3/2 c XX ηt,j pt [v] (ℓt (v) − ct,j )2 , c−1 t=1 j∈[L]

v∈Vj

−1 −1 −1 where ηe1,j = η1,j and for t ≥ 2, ηet,j = ηt,j − ηt−1,j .

Proof This is obtained by combining Lemmas 10, 11 and 13, and using the fact that ψT +1 (q) ≤ 0.

Lemma 17 Fix a sequence of positive numbers (Rj )j∈[L] and a sequence (ξj )j∈[L] of weights in [0, 1]. Moreover, with t ≥ 1, let (yt )t be a random sequence of loss functions each mapping A to R,(At )t a random sequence of actions from A, (Mt )t a random sequence of subsets of [L], and (ℓt )t a random sequence of functions mapping V to R such that ℓt (v) ∈ [0, Rj ] for all j ∈ [L], v ∈ Vj , and t ≥ 1. Accordingly, define p1 := arg min ψ1 (p)

and for t ≥ 2, pt := arg min

p∈∆K

p∈∆K

where for t ≥ 1 and a ∈ A, zt (a) :=

X v≻a

Jv ≻ At , lvl(v) ∈ Mt K

P

s≤t−1 zs , p

+ ψt (p) ,

ℓt (v) ; and for x ∈ Rd , ξlvl(v) pt [v]

√ oX n√ q X Rj p 2 c p max t, c(c − 1)/ξj x[v] − x[v] ψt (x) := p (c − 1) j∈[L] ξj v∈V j

with some constant c ≥ 2. Assume there exists a filtration (Ft )t≥0 such that (a) (pt )t≥1 is predictable w.r.t. (Ft )t≥0 , (b) Pt (At = a) = pt (a) ∀a ∈ A, (c) Pt (j ∈ Mt ) = ξj ∀j ∈ [L], (d) P Jv ≻ At K ⊥ ⊥ Jlvl(v) ∈ Mt K | Ft−1 ∀v ∈ V, P (e) E [ℓ v≻a t t (v) | v ≻ At , lvl(v) ∈ Mt ] − w≻a′ Et [ℓt (w) | w ≻ At , lvl(w) ∈ Mt ] = ′ ′ Et [yt (a) − yt (a )] ∀a, a ∈ A, where Pt (·) = P(· | Ft−1 ) and Et [·] = E[· | Ft−1 ]. Then, it holds for any horizon T ≥ 1 that

E

" T X t=1

# yt (At ) − min E a∈A

√ T X p
4 c X 1 X Rj √ p E pt [v] − pt [v] yt (a) ≤ p (c − 1) t=1 t j∈[L] ξj v∈V t=1 j X Rj q + 3c |Vj | . ξj

" T X

#

j∈[L]

37

E LDOWA R AHIER C ABLANT M ERTIKOPOULOS G AILLARD

hP i T Proof Let a∗ ∈ arg mina∈A E y (a) and let q ∈ ∆k be entirely concentrated on a∗ . For t=1 t brevity, we will use ℓet (v) to denote Et [ℓt (v) | v ≻ At , lvl(v) ∈ Mt ] for v ∈ V. With this definition, it holds that   Et Jv ≻ At , lvl(v) ∈ Mt Kℓt (v)

  = Pt (v ≻ At , lvl(v) ∈ Mt )Et ℓt (v)Jv ≻ At , lvl(v) ∈ Mt K | v ≻ At , lvl(v) ∈ Mt   + Pt (v ̸≻ At ∨ lvl(v) ∈ / Mt )Et ℓt (v)Jv ≻ At , lvl(v) ∈ Mt K | v ̸≻ At ∨ lvl(v) ∈ / Mt       = Et Jv ≻ At , lvl(v) ∈ Mt K ℓet (v) = Et Jv ≻ At K Et Jlvl(v) ∈ Mt K ℓet (v) ,

where the last step holds via the assumed independence of Jv ≻ At K and Jlvl(v) ∈ Mt K conditioned on Ft−1 . Note then that E⟨zt , pt ⟩ = E =E =E =E =E

X

pt (a)

X

a∈A

v≻a

X

pt (a)

X

a∈A

v≻a

X

pt (a)

X

a∈A

v≻a

X

pt (a)

X

a∈A

v≻a

X

X

ℓet (v)

X v∈V

=E

X v∈V

ℓt (v) ξlvl(v) pt [v]

  Et Jv ≻ At , lvl(v) ∈ Mt Kℓt (v)

1 ξlvl(v) pt [v]

Et [Jv ≻ At K] Et [Jlvl(v) ∈ Mt K]

ℓet (v) ξlvl(v) pt [v]

ℓet (v)

pt (a)

a≺v

v∈V

=E

Jv ≻ At , lvl(v) ∈ Mt K

ℓet (v)Et [Jv ≻ At K] ℓet (v)Jv ≻ At K = E

X

ℓet (v) ,

v≻At

where the first equality uses the definition of zt ; the second uses the tower rule and the fact that pt is deterministic given Ft−1 ; the fourth uses the definition of pt [v], the assumption that the law of At conditioned on Ft−1 is pt , and the assumption that Pt ({lvl(v) ∈ Mt }) = ξlvl(v) ; the sixth employs again the fact that the law of At conditioned on Ft−1 is pt ; and the seventh again uses the tower rule and the fact that ℓet (v) is measurable w.r.t. Ft−1 . In a similar fashion, it holds that E⟨zt , q⟩ = E =E =E =E

X

q(a)

X

a∈A

v≻a

X

q(a)

X

a∈A

v≻a

X

q(a)

X

a∈A

v≻a

X

q(a)

X

a∈A

Jv ≻ At , lvl(v) ∈ Mt K

ℓt (v) ξlvl(v) pt [v]

  Et Jv ≻ At , lvl(v) ∈ Mt Kℓt (v)

1 ξlvl(v) pt [v]

Et [Jv ≻ At K] Et [Jlvl(v) ∈ Mt K]

ℓet (v) ξlvl(v) pt [v]

ℓet (v) .

v≻a

38

L EVERAGING S IMILARITIES IN M ULTI -A RMED BANDITS

P P Since, by assumption, v≻a ℓet (v)− w≻a′ ℓet (w) = Et [yt (a)−yt (a′ )] for all a, a′ ∈ A, combining the last two result with an application of the tower rule gets us that   E⟨zt , pt − q⟩ = E yt (At ) − ⟨yt , q⟩ . Overall, we have shown that

E

" T X

# yt (At ) − min E a∈A

t=1

" T X

# yt (a) = E

t=1

T X

⟨zt , pt − q⟩ .

t=1

√ We can now invoke Lemma 16 with some c ≥ 2, ηt,j =

√

ξj Rj min

√c−1 , ct

√  ξj c

ℓ (ancj (At )) to get that ξj

, and ct,j = Jj ∈

Mt K t

√ T T +1 X X Rj X p

2 c X 1 X Rj X p √ p ⟨zt , pt −q⟩ ≤ 2c p1 [v]−p1 [v] + p pt [v]−pt [v] ξj ξj t (c − 1) t=1

j∈[L]

√

+√

T X

c c − 1 t=1

t=2

v∈Vj

j∈[L]

v∈Vj

p  
3/2 ℓt (ancj (At )) 2 1 X ξj X ℓt (v) √ pt [v] Jv = ancj (At ), j ∈ Mt K − Jj ∈ Mt K , Rj ξj pt [v] ξj t j∈[L]

v∈Vj

cR

−1 where we have used that ηe1,j = η1,j = ξjj , and for t ≥ 2,

 √  p  c(t − 1) c Rj Rj ct c √ ηet,j = p max √ ,p ,p − p max c−1 c−1 ξj ξj ξj ξj √ √ √ cRj ( t − t − 1) ≤p (c − 1)ξj √ cRj p ≤ . (c − 1)ξj t Note also that for every t ≥ 1, j ∈ [L], and v ∈ Vj , ℓt (ancj (At )) ℓt (v) Jv = ancj (At ), j ∈ Mt K − Jj ∈ Mt K ξj pt [v] ξj   Jj ∈ Mt K ℓt (v) Jv = ancj (At )K − ℓt (ancj (At )) = ξj pt [v] ℓt (ancj (At )) ≥− ξj Rj 1 1 p ≥− ≥− ; ≥− ξj cηt,j cηt,j pt [v] thus, the conditions of Lemma 16 are indeed satisfied. 39

E LDOWA R AHIER C ABLANT M ERTIKOPOULOS G AILLARD

Moving on, it holds that   X
3/2 ℓt (ancj (At )) 2 ℓt (v) Jv = ancj (At ), j ∈ Mt K Et pt [v] − Jj ∈ Mt K ξj pt [v] ξj v∈Vj 2 
3/2 Jj ∈ Mt K X ℓt (v) = Et − ℓt (ancj (At )) Jv = ancj (At )K pt [v] pt [v] ξj2 v∈Vj

 P Jj ∈ Mt Kℓ2t (ancj (At ))  1/2 3/2 −1/2 (p [anc (A )]) − 2(p [anc (A )]) + (p [v]) t j t t j t v∈Vj t ξj2  P Jj ∈ Mt K  1/2 3/2 −1/2 ≤ Rj2 Et (p [anc (A )]) − 2(p [anc (A )]) + (p [v]) t j t t j t v∈Vj t ξj2  X Jj ∈ Mt KJw ≻ At K  P 1/2 3/2 −1/2 = Rj2 Et (p [w]) − 2(p [w]) + (p [v]) t t v∈Vj t ξj2 = Et

w∈Vj

X Et [Jj ∈ Mt K]Et [Jw ≻ At K] 

= Rj2

ξj2

w∈Vj

=

(pt [w])− /2 − 2(pt [w]) /2 + 1

1

/2 v∈Vj (pt [v]) 3

P



  Rj2 X P 1 1 3 pt [w] (pt [w])− /2 − 2(pt [w]) /2 + v∈Vj (pt [v]) /2 ξj w∈Vj

≤2

Rj2 X p ξj

pt [v] − pt [v] ,

v∈Vj

where the second equality is an application of the first part of Lemma 15, the fourth equality uses the conditional independence of Jw ≻ At K and Jlvl(w) ∈ Mt K given Ft−1 , and the last inequality is an application of the second part of Lemma 15. Putting everything together, obtain that " T # " T # X X E yt (At ) − min E yt (a) a∈A

t=1

t=1

√

T X p X Rj X p

4 c X 1 X Rj √ p E ≤p E pt [v] − pt [v] + 2c p1 [v] − p1 [v] ξj (c − 1) t=1 t j∈[L] ξj v∈V v∈Vj j∈[L] j √ X Rj X p
2 c 1 p E +p ·√ pT +1 [v] − pT +1 [v] . T + 1 j∈[L] ξj v∈V (c − 1) j

The theorem then follows since the sum of the last two terms is no larger than 3c

Rj p |Vj |. j∈[L] ξj

P

Appendix G. Foundational Results Lemma 18 Fix a vector z ∈ Rd and let ψ : Rd → (−∞, +∞] be a proper and closed convex function. Assume further that relint(∆d ) ∩ relint(dom(ψ)) ̸= ∅. Then, it holds that min z ⊤ p + ψ(p) = max −ψ ∗ (u − z) + mini u(i) ,

p∈∆d

u∈Rd

40

L EVERAGING S IMILARITIES IN M ULTI -A RMED BANDITS

and that u∗ − z ∈ ∂ψ(p∗ ) , for p∗ ∈ arg minp∈∆d z ⊤ p+ψ(p) and u∗ ∈ arg maxu∈Rd −ψ ∗ (u−z)+mini u(i) . If, additionally, ψ is essentially smooth, then u∗ is unique, p∗ ∈ ∆d ∩ int(dom(ψ)), and u∗ − z = ∇ψ(p∗ ) . If ψ is also strictly convex on int(dom(ψ)), then p∗ too is unique. Proof Define Φ : Rd → (−∞, +∞] as Φ(x) := z ⊤ x + ψ(x) for all x ∈ Rd . This is a proper and closed convex function satisfying that dom(Φ) = dom(ψ) and Φ∗ (y) = ψ ∗ (y − z) for any y ∈ Rd . Define also g : Rd → [−∞, +∞) as ( 0 if x ∈ ∆d g(x) := −∞ otherwise , which is a closed and proper concave function satisfying that dom(g) = ∆d , g ∗ (y) = mini y(i) for any y ∈ Rd , and dom(g ∗ ) = Rd . Note then that relint(dom(g)) ∩ relint(dom(Φ)) ̸= ∅ since relint(∆d )∩relint(dom(ψ)) ̸= ∅ by assumption. Moreover, relint(dom(g ∗ ))∩relint(dom(Φ∗ )) ̸= ∅ since dom(g ∗ ) = Rd and dom(Φ∗ ) is not empty (because Φ∗ is proper). Hence, Theorem 31.1 in (Rockafellar, 1970) gives that inf Φ(x) − g(x) = sup g ∗ (y) − Φ∗ (y)

x∈Rd

y∈Rd

with both the infimum and the supremum being attained, which entails the first statement of the lemma. Now, fixing p∗ ∈ arg minp∈∆d Φ(p) and u∗ ∈ arg maxu∈Rd −ψ ∗ (u − z) + mini u(i), it holds that Φ(p∗ ) = −ψ ∗ (u∗ − z) + mini u∗ (i) = inf (z − u∗ )⊤ x + ψ(x) + mini u∗ (i) x∈Rd

= mini u∗ (i) + inf Φ(x) − x⊤ u∗ ∗

x∈Rd ∗

≤ mini u (i) + Φ(p ) − (p∗ )⊤ u∗ ≤ Φ(p∗ ) , where the last inequality just uses that p∗ ∈ ∆d . We can then conclude that p∗ ∈ arg minx∈Rd ψ(x)+ x⊤ (z − u∗ ), or equivalently p∗ ∈ arg max x⊤ (u∗ − z) − ψ(x) , x∈Rd

implying via Theorem 23.5 in (Rockafellar, 1970) that u∗ − z ∈ ∂ψ(p∗ ) , 41

(21)

E LDOWA R AHIER C ABLANT M ERTIKOPOULOS G AILLARD

which gives the second statement. Moving on, if ψ is essentially smooth, Theorem 26.1 in (Rockafellar, 1970) gives that ∂ψ(x) = {∇ψ(x)} for x ∈ int(dom(ψ)) and ∂ψ(x) = ∅ otherwise. It is then implied by (21) that u∗ is unique (since ∂ψ(p∗ ) is non-empty and must be a singleton), that p∗ ∈ int(dom(ψ)), and that u∗ − z = ∇ψ(p∗ ). If ψ is additionally strictly convex on int(dom(ψ)), Corollary 26.3.1 in (Rockafellar, 1970) gives that ∂ψ is a one-to-one mapping, hence the uniqueness of u∗ implies via (21) the uniqueness of p∗ . Lemma 19 For every i in a finite index set I, let ψi : Rd → (−∞, +∞] be a proper and closed convex Pfunction, and assume that ∩i∈I relint(dom(ψi )) ̸= ∅. If every ψi is essentially smooth, then so is i∈I ψi . P Proof Let ψ := i∈I ψi , which is also a proper and closed convex function. Theorem 26.1 in (Rockafellar, 1970) states that a proper and closed convex function f : Rd → (∞, +∞] is essentially smooth if and only if ∂f (x) contains at most one element for any x ∈ Rd , which hence holds for every ψ i )) ̸= ∅, (Bertsekas, 2009, Proposition 5.4.6) gives that Pi . Since ∩i∈I relint(dom(ψ d ∂ψ(x) = i∈I ∂ψi (x) for all x ∈ R . Thus, ∂ψ(x) too contains at most one element, implying the essential smoothness of ψ(x). Lemma 20 Fix a vector z ∈ Rd and a finite index set I. For every i ∈ I, let ψi : Rd → (−∞, +∞]
be a proper and closed convex function. Assume further that relint(∆d )∩ ∩i∈I relint(dom(ψi )) ̸= ∅. Then, it holds that X X min z ⊤ p + ψi (p) = max P sup − ψi∗ (yi ) + mini u(i) , p∈∆d

u∈Rd

i∈I

i∈I yi =u−z

i∈I

and for any p∗ ∈ ∆d minimizing the L.H.S. and u∗ ∈ Rd maximizing the R.H.S. , X X min z ⊤ p + ψi (p) = − ψi∗ (gi ) + mini u∗ (i) , p∈∆d

i∈I

i∈I

P for some (gi )i∈I satisfying gi ∈ ∂ψi (p∗ ) and i∈I gi = u∗ − z.PIf, additionally, every ψi is essentially smooth, then u∗ is unique, p∗ ∈ ∆d ∩ int(∩i∈I dom(ψi )), i∈I ∇ψi (p∗ ) = u∗ − z, and min z ⊤ p +

p∈∆d

If, moreover,

X i∈I

ψi (p) = −

X

ψi∗ (∇ψi (p∗ )) + mini u∗ (i) .

i∈I

P

i∈I ψi is strictly convex on int(∩i∈I dom(ψi )), then p

∗ too is unique.

Proof For brevity, define ψ :=

X

ψi .

i∈I

This is a convex function that is closed (Bertsekas, 2009, Proposition 1.1.5) and satisfies
dom(ψ) = ∩i∈I dom(ψi ). Hence, our assumption that relint(∆d ) ∩ ∩i∈I relint(dom(ψi )) ̸= ∅ implies that ψ is proper seeing as dom(ψ) ̸= ∅. Moreover, Theorem 6.5 in (Rockafellar, 1970) gives that 42

L EVERAGING S IMILARITIES IN M ULTI -A RMED BANDITS

relint(∩i∈I dom(ψi )) = ∩i∈I relint(dom(ψi )) seeing as ∩i∈I relint(dom(ψi )) ̸= ∅. Hence, it holds that relint(∆d ) ∩ relint(dom(ψ)) ̸= ∅. Lemma 18 then gives that min z ⊤ p + ψ(p) = max −ψ ∗ (u − z) + mini u(i) .

p∈∆d

u∈Rd

(22)

Since ∩i∈I relint(dom(ψi )) ̸= ∅, Theorem 16.4 in (Rockafellar, 1970) gives that X ψ ∗ (u − z) = P inf ψi∗ (yi ) , i∈I yi =u−z i∈I

implying, as sought, that min z ⊤ p +

p∈∆d

X i∈I

ψi (p) = max P sup u∈Rd

−

i∈I yi =u−z

X

ψi∗ (yi ) + mini u(i) .

i∈I

Fixing p∗ ∈ arg minp∈∆d z ⊤ p + ψ(p) and u∗ ∈ arg maxu∈Rd −ψ ∗ (u − z) + mini u(i), Lemma 18 also implies that u∗ − z ∈ ∂ψ(p∗ ) . Hence, by (Bertsekas, 2009, Proposition 5.4.6) and the assumption that ∩i∈I relint(dom(ψ i )) ̸= ∅, P there exists a collection of vectors (gi )i∈I each satisfying gi ∈ ∂ψi (p∗ ) such that i∈I gi = u∗ − z. We then get that ψ ∗ (u∗ − z) = (u∗ − z)⊤ p∗ − ψ(p∗ ) P = ( i∈I gi )⊤ p∗ − ψ(p∗ ) X
= gi⊤ p∗ − ψi (p∗ ) i∈I

=

X

ψi∗ (gi ) ,

i∈I

where the first and last equalities follow from (Rockafellar, 1970, Theorem 23.5). Combined with (22), this entails that X min z ⊤ p + ψ(p) = − ψi∗ (gi ) + mini u∗ (i) . (23) p∈∆d

i∈I

Next, Lemma 19 gives that ψ is essentially smooth when every ψi is. If this condition holds, Lemma 18 would additionally give that u∗ is unique and that p∗ ∈ ∆d ∩ int(∩i∈I dom(ψi )). The latter implies that p∗ ∈ int(dom(ψi )) for every i ∈ I, which entails via Theorem 26.1 ∗ in 1970) that ∂ψi (p∗ ) = {∇ψi (p∗ )}. Hence, gi in (23) becomes ∇ψi (p P (Rockafellar, P ) and ∗ ∗ ∗ i∈I ∇ψi (p ) = u − z. Finally, Lemma 18 implies that p is unique if it also holds that i ψi is strictly convex in int(∩i∈I dom(ψi )). For a convex function f : R → (−∞, +∞] and a vector h ∈ Rd , we denote by f ◦ h⊤ : Rd → (−∞, +∞] the function given by (f ◦ h⊤ )(x) := f (h⊤ x) . Whereas the function h ◦ f : Rd → (−∞, +∞] is given by (h ◦ f )(x) := inf f (α) . x=αh

43

E LDOWA R AHIER C ABLANT M ERTIKOPOULOS G AILLARD

Lemma 21 For a proper convex function f : R → (−∞, +∞] and a non-zero vector h ∈ Rd , it holds that (f ◦ h⊤ )∗ = h ◦ f ∗ . Proof Note that any vector y ∈ Rd satisfies y = αh + y ′ for some α ∈ R and y ′ ∈ Rd such that h⊤ y ′ = 0. Then, starting from the definition of the conjugate, we have that (f ◦ h⊤ )∗ (y) = sup x⊤ y − f (h⊤ x) x∈Rd

= sup x⊤ (αh + y ′ ) − f (h⊤ x) x∈Rd

=

(βh + x′ )⊤ (αh + y ′ ) − f (h⊤ (βh + x′ ))

sup

β∈R, x′ ∈Rd : h⊤ x′ =0

=

αβ∥h∥2 + x′⊤ y ′ − f (β∥h∥2 )

sup β∈R, x′ ∈Rd : h⊤ x′ =0

= f ∗ (α) +

x′⊤ y ′

sup x′ ∈Rd : h⊤ x′ =0

= inf f ∗ (α) = (h ◦ f ∗ )(y) , y=αh

where the penultimate equality uses that the supremum is 0 if y and h are collinear and +∞ otherwise. In the latter case {α ∈ R : y = αh} is empty and (h ◦ f ∗ )(y) is vacuously +∞, while in the former, said set is a singleton.

Lemma 22 For a proper convex function f : R → (−∞, +∞] and a non-zero vector h ∈ Rd , it holds for every x ∈ Rd that ∂(f ◦ h⊤ )(x) = h∂f (h⊤ x) . Proof This follows directly from Theorem 23.9 in (Rockafellar, 1970) since the range of h⊤ is R, and so, it automatically has a non-empty intersection with relint(dom(f )) (Rockafellar, 1970, Theorem 6.2).

Lemma 23 Let f : R → (−∞, +∞] be a proper and closed convex function, and let h ∈ Rd be a non-zero vector. If f is essentially smooth, then so is f ◦ h⊤ . Proof Firstly, f ◦ h⊤ is also a closed convex function via Proposition 1.1.4 in (Bertsekas, 2009). It is also proper since the range of h⊤ is the entirety of R. Theorem 26.1 in (Rockafellar, 1970) states that a proper and closed convex function is essentially smooth if and only if the sub-differential at any point contains at most one element. Since f is essentially smooth and, by Lemma 22, every x ∈ Rd satisfies ∂(f ◦ h⊤ )(x) = h∂f (h⊤ x) , it follows that (f ◦ h⊤ ) too is essentially smooth.

44

L EVERAGING S IMILARITIES IN M ULTI -A RMED BANDITS

Lemma 24 For every i in a finite index set I, let fi : R → (−∞, +∞] be a proper convex function and hi ∈ Rd be a non-zero vector. Assume that int(∩i∈I dom(fi ◦ h⊤ ̸= ∅ and that i )) P d span{hi }i∈I = R . Then, if every fi is strictly convex in int(dom(fi )), it holds that i∈I fi ◦ h⊤ i is strictly convex in int(∩i∈I dom(fi ◦ h⊤ )). i P d ⊤ ⊤ Proof Note that dom(fi ◦ h⊤ i ) = {x ∈ R : hi x ∈ dom(fi )}. Define ψ := i∈I fi ◦ hi . ⊤ Then, dom(ψ) = ∩i∈I dom(fi ◦ hi ) and ψ is a proper convex function. Note, moreover, that ⊤ x 7→ h⊤ i x maps vectors in int(dom(fi ◦ hi )) to int(dom(fi )). Now, for any α ∈ (0, 1) and x, y ∈ int(dom(ψ)) such that x ̸= y, we have that ψ(αx + (1 − α)y) =

X

=

X

<

X

fi (h⊤ i (αx + (1 − α)y))

i∈I ⊤ fi (αh⊤ i x + (1 − α)hi y)

i∈I ⊤ αfi (h⊤ i x) + (1 − α)fi (hi y)

i∈I

= αψ(x) + (1 − α)ψ(y) , ⊤ ⊤ ⊤ ⊤ where the inequality holds since h⊤ i x, hi y ∈ int(dom(fi ◦ hi )) for all i ∈ I and hi x ̸= hi y for d at least one i ∈ I since x − y ̸= 0 and span{hi }i∈I = R . We conclude then that ψ is strictly convex in int(dom(ψ)) as required.

Lemma 25 Fix a vector z ∈ Rd and a finite index set I. For every i ∈ I, let hi ∈ Rd be a non-zero vector and fi : R → (−∞, +∞] a proper
and closed convex function. Assume that relint(∆d ) ∩ ∩i∈I relint({x ∈ Rd : h⊤ i x ∈ dom(fi )}) ̸= ∅. Then, it holds that min z ⊤ p +

p∈∆d

X i∈I

fi (h⊤ i p) = max P u∈Rd

−

sup i∈I αi hi =u−z

X

fi∗ (αi ) + mini u(i) ,

i∈I

and for any p∗ ∈ ∆d minimizing the L.H.S. and u∗ ∈ Rd maximizing the R.H.S. , min z ⊤ p +

X

p∈∆d

fi (h⊤ i p) = −

X

i∈I

fi∗ (αi∗ ) + mini u∗ (i) ,

i∈I

P ∗ ∗ ∗ for some (αi∗ )i∈I satisfying αi∗ ∈ ∂fi (h⊤ i p ) and i∈I αi hi = u − z. If, additionally, every ∗ ∗ d ⊤ fP i is essentially smooth, then u is unique, p ∈ ∆d ∩ int(∩i∈I {x ∈ R : hi x ∈ dom(fi )}), ′ ⊤ ∗ ∗ i∈I fi (hi p )hi = u − z, and min z ⊤ p +

p∈∆d

X i∈I

fi (h⊤ i p) = −

X

∗ ∗ fi∗ (fi′ (h⊤ i p )) + mini u (i) .

i∈I

If, moreover, span{hi }i∈I = Rd and every fi is strictly convex on int(dom(fi )), then p∗ too is unique. 45

E LDOWA R AHIER C ABLANT M ERTIKOPOULOS G AILLARD

d ⊤ Proof Define ψi := fi ◦h⊤ i . Notice then that dom(ψi ) = {x ∈ R : hi x ∈ dom(fi )}. Moreover, ψi is a closed and proper convex function. Hence, our assumption that relint(∆d ) ∩ ∩i∈I relint({x ∈
d ⊤ R : hi x ∈ dom(fi )}) ̸= ∅ implies via Lemma 20 that

min z ⊤ p +

p∈∆d

X i∈I

−

ψi (p) = max P sup u∈Rd

i∈I yi =u−z

X

ψi∗ (yi ) + mini u(i) .

i∈I

Using this, the definition of ψi , and Lemma 21, we obtain that X X − inf min z ⊤ p + fi (h⊤ i p) = max P sup p∈∆d

u∈Rd

i∈I yi =u−z

= max P

sup

i∈I

u∈Rd

i∈I

−

i∈I αi hi =u−z

yi =αi hi

X

fi∗ (αi ) + mini u(i)

fi∗ (αi ) + mini u(i) .

i∈I

For any p∗ ∈ arg min z ⊤ p +

X

p∈∆d

i∈I

fi (h⊤ i p)

and u∗ ∈ arg max P u∈Rd

sup i∈I αi hi =u−z

−

X

fi∗ (αi ) + mini u(i) ,

i∈I

Lemma 20 also gives that min z ⊤ p +

p∈∆d

X

fi (h⊤ i p) = −

i∈I

for some (gi )i∈I satisfying gi ∈ ∂ψi (p∗ ) and of ψi and Lemma 22 give that

X

ψi∗ (gi ) + mini u∗ (i) ,

i∈I

P

∗ i∈I gi = u − z. On the other hand, the definition

∗ ⊤ ∗ ∂ψi (p∗ ) = ∂(fi ◦ h⊤ i )(p ) = hi ∂fi (hi p ) , ∗ implying the existence of real weights (αi∗ )i∈I such that gi = αi∗ hi and αi∗ ∈ ∂fi (h⊤ i p ). Hence, Lemma 21 gives that

ψi∗ (gi ) = ψi∗ (αi∗ hi ) =

inf

α∗i hi =αhi

fi∗ (α) = fi∗ (αi∗ ) ,

using in the end that hi ̸= 0. We have thus shown that X X min z ⊤ p + fi (h⊤ p) = − fi∗ (αi∗ ) + mini u∗ (i) , i p∈∆d

i∈I

(24)

i∈I

P ∗ ∗ ∗ for some (αi∗ )i∈I satisfying αi∗ ∈ ∂fi (h⊤ i p ) and i∈I αi hi = u − z. ⊤ Next, if fi is essentially smooth, then so is fi ◦ hi by Lemma 23. Under that condition, Lemma 20 gives that u∗ is unique and that p∗ ∈ ∆d ∩ int(∩i∈I {x ∈ Rd : h⊤ i x ∈ dom(fi )}). The latter implies that p∗ ∈ int({x ∈ Rd : h⊤ x ∈ dom(f )}) for every i ∈ I, which entails that i i ∗ ∈ int(dom(f )). The essential smoothness of f then entails via Theorem 26.1 in (Rockafelh⊤ p i i i ⊤ p∗ ) = {f ′ (h⊤ p∗ )}. Hence, α∗ in (24) becomes f ′ (h⊤ p∗ ) and we get that lar, 1970) that ∂f (h i i i i i P P P i i⊤ ′ ⊤ ∗ ∗ i∈I fi (hi p )hi = u − z. Finally, Lemma 24 gives that i ψi = i fi ◦ hi is strictly convex in 46

L EVERAGING S IMILARITIES IN M ULTI -A RMED BANDITS

the interior of its domain whenever it holds that span{hi }i∈I = Rd and every fi is strictly convex in the interior of its domain (which is not empty via essential smoothness). Thus, Lemma 20 implies under these conditions that p∗ is also unique. For a function f : Rd → (−∞, +∞] that is differentiable in the interior of its domain, the Bregman divergence with respect to f of x ∈ Rd from y ∈ int(dom(f ) is defined as Df (x∥y) := f (x) − f (y) − ⟨∇f (y), x − y⟩ . Proposition 26 Fix a finite index set I and associate to every i ∈ I a non-zero vector hi ∈ Rd and a weight ηi > 0. Let f : R → (−∞, +∞] be a convex function that is proper, closed,
and essentially smooth. Assume also that relint(∆d ) ∩ ∩i∈I relint({x ∈ Rd : h⊤ x ∈ dom(f )}) ̸= ∅. i d Fix y, z ∈ R and let X 1 p∗ ∈ arg min y ⊤ p + f (h⊤ i p) . η i p∈∆d i∈I

Then, ⊤ ∗

(y + z) p +

  X 1 ⊤ ⊤ (y + z) p + f (hi p) ηi i∈I X 1
∗ ′ ⊤ ∗ ≤ inf Df ∗ f ′ (h⊤ P i p ) − ηi αi f (hi p ) . ηi c,{αi }i∈I : i∈I αi hi =z−c1

X 1 i∈I

∗ f (h⊤ i p ) − min p∈∆d ηi

i∈I

Proof Fix any p ∈ ∆d and constant c ∈ R. Since ⟨c1, p∗ − p⟩ = 0, we get that (y + z)⊤ p∗ +

X 1 i∈I

ηi

∗ ⊤ f (h⊤ i p ) − (y + z) p −

X 1 ηi

i∈I

= (y + z)⊤ (p∗ − p) +

X 1

f (h⊤ i p)

∗ f (h⊤ i p )−

X 1

f (h⊤ i p) ηi ηi i∈I i∈I X 1 X 1 ∗ f (h⊤ f (h⊤ = (y + z − c1)⊤ (p∗ − p) + i p )− i p) . ηi ηi i∈I

i∈I

It can be readily seen that fi := (1/ηi )f satisfies the same properties of f that are listed in the statement of the proposition. Hence, Lemma 25 gives that y ⊤ p∗ +

X 1 i∈I

ηi

∗ f (h⊤ i p )=−

X

∗ fi∗ (fi′ (h⊤ i p )) + mini up∗ (i)

i∈I

=−

X 1 i∈I

=−

ηi

X 1 i∈I

ηi

∗ f ∗ (ηi fi′ (h⊤ i p )) + mini up∗ (i) ∗ f ∗ (f ′ (h⊤ i p )) + mini up∗ (i)

P ∗ for some up∗ ∈ Rd , which satisfies that i∈I (1/ηi )f ′ (h⊤ i p )hi = up∗ − y. Lemma 25 also implies ∗ d ⊤ ∗ that p ∈ int(∩i∈I {x ∈ R : hi x ∈ dom(f )}), thus, as a consequence, h⊤ i p ∈ int(dom(f )) for 47

E LDOWA R AHIER C ABLANT M ERTIKOPOULOS G AILLARD

every i ∈ I. At the same time, another implication of Lemma 25 is that − (y + z − c1)⊤ p −

X 1 i∈I

≤ min P u∈Rd

ηi

f (h⊤ i p) X

inf

i∈I αi hi =u−z−y+c1 i∈I

≤ − mini up∗ (i) + P = − mini up∗ (i) + P = − mini up∗ (i) + P = − mini up∗ (i) + P

fi∗ (αi ) − mini u(i) X

inf

i∈I αi hi =up∗ −z−y+c1

fi∗ (αi )

i∈I

X 1

inf

i∈I αi hi =up∗ −z−y+c1 i∈I

X 1

inf

i∈I αi hi =−z+c1 i∈I

ηi

X 1

inf i∈I αi hi =z−c1

i∈I

ηi

ηi

f ∗ (ηi αi )

∗ f ∗ (f ′ (h⊤ i p ) + η i αi )

∗ f ∗ (f ′ (h⊤ i p ) − ηi αi ) ,

∗ where the third equality uses that i∈I (1/ηi )f ′ (h⊤ i p )hi = up∗ − y. Combining the results derived thus far we get that

P

(y + z)⊤ p∗ +

X 1 i∈I

ηi

∗ ⊤ f (h⊤ i p ) − (y + z) p −

≤ (z − c1)⊤ p∗ + P =P

inf

X 1 i∈I

inf

X 1

i∈I αi hi =z−c1 i∈I

(z − c1)⊤ p∗ +

i∈I αi hi =z−c1

i∈I

ηi

X 1

f (h⊤ i p)

∗ f ∗ (f ′ (h⊤ i p ) − η i αi ) −

1 ∗ ′ ⊤ ∗ f (f (hi p )) ηi

∗ f ∗ (f ′ (h⊤ i p ) − η i αi ) −

1 ∗ ′ ⊤ ∗ f (f (hi p )) ηi

ηi

X 1

ηi

1 ∗ ′ ⊤ ∗ f (f (hi p )) ηi ηi i∈I αi hi =z−c1 i∈I i∈I  X 1 ∗ ∗ ′ ⊤ ∗ ∗ ′ ⊤ ∗ =P inf η i α i h⊤ p + f (f (h p ) − η α ) − f (f (h p )) i i i i i i∈I αi hi =z−c1 i∈I ηi  X 1 ∗ ∗ ′ ⊤ ∗ ∗ ′ ⊤ ∗ =P inf ηi αi f ∗ ′ (f ′ (h⊤ p )) + f (f (h p ) − η α ) − f (f (h p )) i i i i i i∈I αi hi =z−c1 i∈I ηi X 1
∗ ′ ⊤ ∗ =P inf Df ∗ f ′ (h⊤ i p ) − ηi αi f (hi p ) , ηi i∈I αi hi =z−c1 =P

inf

X

∗ αi h⊤ i p +

∗ f ∗ (f ′ (h⊤ i p ) − η i αi ) −

i∈I

∗ where the fourth equality follows from Theorem 26.5 in (Rockafellar, 1970) and the fact that h⊤ i p ∈ int(dom(f )) for every i ∈ I. The sought result now follows after taking the infimum over c and the minimum over p.

48