NESTED BANDITS

Let $\mathcal{A}=\{a_{i}:i=1,\dotsc,n\}$ be a set of alternatives (or atoms) indexed by $i=1,\dotsc,n$. A similarity structure (or structure of attributes) on $\mathcal{A}$ is defined as a tower of nested similarity partitions (or attributes) $\mathcal{S}_{\ell}$, $\ell=0,\dotsc,L$, of $\mathcal{A}$ with $\{\mathcal{A}\}\eqqcolon\mathcal{S}_{0}\mathrel{}\succcurlyeq\mathrel{}\mathcal{S}_{1}\mathrel{}\succcurlyeq\mathrel{}\dotsm\mathrel{}\succcurlyeq\mathrel{}\mathcal{S}_{L}\coloneqq\{\{a\}:a\in\mathcal{A}\}$. As a result of this definition, each partition $\mathcal{S}_{\ell}$ captures successively finer attributes of the elements of $\mathcal{A}$ (in our music catalogue example, these attributes would correspond to genre, artist, album, etc.).¹¹1The trivial partitions $\mathcal{S}_{0}=\{\mathcal{A}\}$ and $\mathcal{S}_{L}=\{\{a\}:a\in\mathcal{A}\}$ do not carry much information in themselves, but they are included for completeness and notational convenience later on. Accordingly, each constituent set $A$ of a partition $\mathcal{S}_{\ell}$ will be referred to as a similarity class and we assume it collects all elements of $\mathcal{A}$ that share the attribute defining $\mathcal{S}_{\ell}$: for example, a similarity class for the attribute “artist” might consist of all Beethoven symphonies, all songs by Led Zeppelin, etc.

Collectively, a structure of attributes will be represented by the disjoint union

of all class/attribute pairs of the form $(A,\ell)$ for $A\in\mathcal{S}_{\ell}$. In a slight abuse of terminology (and when there is no danger of confusion), the pair $S=(A,\ell)$ will also be referred to as a “class”, and we will write $S\in\mathcal{S}_{\ell}$ and $a\in S$ instead of $A\in\mathcal{S}_{\ell}$ and $a\in A$ respectively. By contrast, when we need to clearly distinguish between a class and its underlying set, we will write $A=\mathrm{elem}(S)$ for the set of atoms contained in $S$ and $\ell=\mathrm{attr}(S)$ for the attached attribute label.

Moving forward, if a class $S\in\mathcal{S}_{\ell}$ contains the class $S^{\prime}\in\mathcal{S}_{k}$ for some $k>\ell$, we will say that $S^{\prime}$ is a descendant of $S$ (resp. $S$ is an ancestor of $S^{\prime}$), and we will write “$S^{\prime}\mathrel{}\prec\mathrel{}S$” (resp. “$S\mathrel{}\succ\mathrel{}S^{\prime}$”).²²2More formally, we will write $S^{\prime}\mathrel{}\prec\mathrel{}S$ when $\mathrm{elem}(S^{\prime})\subseteq\mathrm{elem}(S)$ and $\mathrm{attr}(S^{\prime})>\mathrm{attr}(S)$. The corresponding weak relation “$\mathrel{}\preccurlyeq\mathrel{}$” is defined in the standard way, i.e., allowing for the case $\mathrm{attr}(S^{\prime})=\mathrm{attr}(S)$ which in turn implies that $S^{\prime}=S$. As a special case of this relation, if $S^{\prime}\mathrel{}\prec\mathrel{}S$ and $k=\ell+1$, we will say that $S^{\prime}$ is a child of $S$ (resp. $S$ is parent of $S^{\prime}$) and we will write “$S^{\prime}\mathrel{}\vartriangleleft\mathrel{}S$” (resp. “$S\mathrel{}\vartriangleright\mathrel{}S^{\prime}$”). For completeness, we will also say that $S^{\prime}$ and $S^{\prime\prime}$ are siblings if they are children of the same parent, and we will write $S^{\prime}\sim S^{\prime\prime}$ in this case. Finally, when we wish to focus on descendants sharing a certain attribute, we will write “$S^{\prime}\mathrel{}\prec_{\ell}\mathrel{}S$” as shorthand for the predicate “$S^{\prime}\mathrel{}\prec\mathrel{}S$ and $\mathrm{attr}(S^{\prime})=\ell$”.

Building on this, a similarity structure on $\mathcal{A}$ can also be represented graphically as a rooted directed tree – an arborescence – by connecting two classes $S,S^{\prime}\in\mathcal{S}$ with a directed edge $S\to S^{\prime}$ whenever $S\mathrel{}\vartriangleright\mathrel{}S^{\prime}$. By construction, the root of this tree is $\mathcal{A}$ itself,³³3Stricto sensu, the root of the tree is $(\mathcal{A},0)$, but since there is no danger of confusion, the attribute label “0” will be dropped. and the unique directed path $\mathcal{A}\equiv S_{0}\mathrel{}\vartriangleright\mathrel{}S_{1}\mathrel{}\vartriangleright\mathrel{}\dotsm\mathrel{}\vartriangleright\mathrel{}S_{\ell}\equiv S$ from $\mathcal{A}$ to any class $S\in\mathcal{S}$ will be referred to as the lineage of $S$. For notational simplicity, we will not distinguish between $\mathcal{S}$ and its graphical representation, and we will use the two interchangeably; for an illustration, see Fig. 1.

Throughout what follows, we will consider loss models in which alternatives that share a common set of attributes incur similar costs, with the degree of similarity depending on the number of shared attributes. More precisely, given a similarity class $S\in\mathcal{S}$, we will assume that all its immediate subclasses $S^{\prime}$ share the same base cost $c_{S}$ (determined by the parent class $S$) plus an idiosyncratic cost increment $r_{S^{\prime}}$ (which is specific to the child $S^{\prime}\mathrel{}\vartriangleleft\mathrel{}S$ in question). Formally, starting with $c_{\mathcal{A}}=0$ (for the root class $\mathcal{A}$), this boils down to the recursive definition

which, when unrolled over the lineage $\mathcal{A}\equiv S_{0}\mathrel{}\vartriangleright\mathrel{}S_{1}\mathrel{}\vartriangleright\mathrel{}\dotsm\mathrel{}\vartriangleright\mathrel{}S_{\ell}\equiv S$ of a target class $S\in\mathcal{S}_{\ell}$, yields the expression

Thus, in particular, when $S\leftarrow a\in\mathcal{A}$, the cost assigned to an individual alternative $a\in\mathcal{A}$ will be given by

Finally, to quantify the “intra-class” variability of costs, we will assume throughout that the idiosyncratic cost increments within a given parent class $S$ are bounded as

This terminology is justified by the fact that, under the loss model (2), the costs $c_{S^{\prime}},c_{S^{\prime\prime}}$ to any two sibling classes $S^{\prime},S^{\prime\prime}\mathrel{}\vartriangleleft\mathrel{}{S}$ (i.e., any two classes parented by $S$) differ by at most $R_{S}$. Analogously, the costs to any two alternatives $a,a^{\prime}\in\mathcal{A}$ that share a set of common attributes $S_{1},\dotsc,S_{\ell}$ will differ by at most $\sum_{k=\ell+1}^{L}R_{S_{k}}$.

With all this in hand, we will consider a generic online decision process that unfolds over a set of alternatives $\mathcal{A}$ endowed with a similarity structure $\mathcal{S}=\coprod_{\ell}\mathcal{S}_{\ell}$ as follows:

1. (1)

   At each stage $t=1,2,\dotsc$, the learner selects an alternative $a_{t}\in\mathcal{A}$ by selecting attributes from $\mathcal{S}$ one-by-one.

2. (2)

   Concurrently, nature sets the idiosyncratic, intra-class losses $r_{S,t}$ for each similarity class $S\in\mathcal{S}$.

3. (3)

   The learner incurs $r_{S,t}$ for each chosen class $S\ni a_{t}$ for a total cost of $c_{t}=\sum_{S\ni a_{t}}r_{S,t}$, and the process repeats.

To align our presentation with standard bandit models with losses in $[0,1]$, we will assume throughout that $\sum_{S\ni a}R_{S}\leq 1$ for all $a\in\mathcal{A}$, meaning in particular that the maximal cost incurred by any alternative $a\in\mathcal{A}$ is upper bounded by $1$. Other than this normalization, the sequence of idiosyncratic loss vectors $r_{t}\in\mathbb{R}^{\mathcal{S}}$, $t=1,2,\dotsc$, is assumed arbitrary and unknown to the learner as per the standard adversarial setting [10, 24].

To avoid deterministic strategies that could be exploited by an adversary, we will assume that the learner selects an alternative $a_{t}$ at time $t$ based on a mixed strategy $X_{t}\in\operatorname{\operatorname{\Delta}}(\mathcal{A})$, i.e., $a_{t}\sim X_{t}$. The regret of a policy $X_{t}$, $t=1,2,\dotsc$, against a benchmark strategy $p\in\operatorname{\operatorname{\Delta}}(\mathcal{A})$ is then defined as the cumulative difference between the player’s mean cost under $p$ and $X_{t}$, that is

where $c_{t}=(c_{a,t})_{a\in\mathcal{A}}\in\mathbb{R}^{\mathcal{A}}$ denotes the vector of costs encountered by the learner at time $t$, i.e., $c_{a,t}=\sum_{S\ni a}r_{S,t}$ for all $a\in\mathcal{A}$. This definition will be our main figure of merit in the sequel.

We begin by introducing the attribute selection scheme that forms the backbone of our proposed policy. Our guiding principle in this is the nested logit choice (NLC) rule of McFadden [20] which selects an alternative $a\in\mathcal{A}$ by traversing $\mathcal{S}$ one attribute at a time and prescribing the corresponding conditional choice probabilities at each level of $\mathcal{S}$.

To set the stage for all this, if $x=(x_{1},\dotsc,x_{n})\in\operatorname{\operatorname{\Delta}}(\mathcal{A})$ is a mixed strategy on $\mathcal{A}$ we will write

for the conditional probability of choosing a descendant $S^{\prime}$ of $S$ assuming that $S$ has already been selected under $x$.⁴⁴4Note here that the joint probability of selecting both $S$ and $S^{\prime}$ under $x$ is simply $x_{S^{\prime}}$ whenever $S^{\prime}\mathrel{}\preccurlyeq\mathrel{}S$. Then the nested logit choice (NLC) rule proceeds as follows: first, it prescribes choice probabilities $x_{S_{1}}$ for all classes $S_{1}\in\mathcal{S}_{1}$ (i.e., the coarsest ones); subsequently, once a class $S_{1}\in\mathcal{S}_{1}$ has been selected, NLC prescribes the conditional choice probabilities $x_{S_{2}|S_{1}}$ for all children $S_{2}$ of $S_{1}$ and draws a class from $\mathcal{S}_{2}$ based on $x_{S_{2}|S_{1}}$. The process then continues downwards along $\mathcal{S}$ until reaching the finest partition $\mathcal{S}_{L}$ and selecting an atom $\{a\}\equiv S_{L}\mathrel{}\vartriangleleft\mathrel{}S_{L-1}\mathrel{}\vartriangleleft\mathrel{}\dotsm\mathrel{}\vartriangleleft\mathrel{}S_{0}\equiv\mathcal{A}$.

This step-by-step selection process captures the “nested” part of the nested logit choice rule; the “logit” part refers to the way that the conditional probabilities (8) are actually prescribed given the agent’s predisposition towards each alternative $a\in\mathcal{A}$. To make this precise, suppose that the learner associates to each element $a\in\mathcal{A}$ a propensity score $y_{a}\in\mathbb{R}$ indicating their tendency – or propensity – to select it. The associated propensity score of a similarity class $S_{\ell-1}\in\mathcal{S}_{\ell-1}$, $\ell=1,\dotsc,L$, is then defined inductively as

where $\mu_{\ell}>0$ is a tunable parameter that reflects the learner’s uncertainty level regarding the $\ell$-th attribute $\mathcal{S}_{\ell}$ of $\mathcal{S}$. In words, this means that the score of a class is the weighted softmax of the scores of its children; thus, starting with the individual alternatives of $\mathcal{A}$ – that is, the leaves of $\mathcal{S}$ – propensity scores are propagated backwards along $\mathcal{S}$, and this is repeated one attribute at a time until reaching the root of $\mathcal{S}$.

With all this in hand, given a propensity score profile $y=(y_{1},\dotsc,y_{n})\in\mathbb{R}^{\mathcal{A}}$, the nested logit choice (NLC) rule is defined via the family of conditional selection probabilities

where:

1. (1)

   $S_{\ell}\in\mathcal{S}_{\ell}$ and $S_{\ell-1}\in\mathcal{S}_{\ell-1}$ is a child / parent pair of similarity classes of $\mathcal{S}$.

2. (2)

   $\mu_{1}\geq\dotsm\geq\mu_{L}>0$ is a nonincreasing sequence of uncertainty parameters (indicating a higher uncertainty level for coarser attributes; we discuss this later).

In more detail, the choice of an alternative $a\in\mathcal{A}$ under (NLC) proceeds as follows: given a propensity score $y_{a}\in\mathbb{R}$ for each $a\in\mathcal{A}$, every similarity class $S_{L-1}\in\mathcal{S}_{L-1}$ is assigned a propensity score via the recursive softmax expression (9), and the same procedure is applied inductively up to the root $\mathcal{A}$ of $\mathcal{S}$. Then, to select an alternative $a\in\mathcal{A}$, the conditional logit choice rule (NLC) proceeds in a top-down manner, first by selecting a similarity class $S_{1}\mathrel{}\vartriangleleft\mathrel{}S_{0}\equiv\mathcal{A}$, then by selecting a child $S_{2}\mathrel{}\vartriangleleft\mathrel{}S_{1}$ of $S_{1}$, and so on until reaching a leaf $\{a\}\equiv S_{L}\mathrel{}\vartriangleleft\mathrel{}S_{L-1}\mathrel{}\vartriangleleft\mathrel{}\dotsm\mathrel{}\vartriangleleft\mathrel{}S_{0}\equiv\mathcal{A}$ of $\mathcal{S}$.

Equivalently, unrolling (NLC) over the lineage $\mathcal{A}\equiv S_{0}\mathrel{}\vartriangleright\mathrel{}S_{1}\mathrel{}\vartriangleright\mathrel{}\dotsm\mathrel{}\vartriangleright\mathrel{}S_{\ell}\equiv S$ of a target class $S\in\mathcal{S}_{\ell}$, we obtain the expression

for the total probability of selecting class $S$ under the propensity score profile $y\in\mathbb{R}^{\mathcal{A}}$. Clearly, (NLC) and (10) are mathematically equivalent, so we will refer to either one as the definition of the nested logit choice rule.

The second key ingredient of our method is how to estimate the costs of alternatives that were not chosen under (NLC). To that end, given a cost vector $c\in[0,1]^{\mathcal{A}}$ and a mixed strategy $x\in\operatorname{\operatorname{\Delta}}(\mathcal{A})$ with full support, a standard way to do this is via the importance-weighted estimator [8, 17]

where $\hat{a}\sim x$ is the (random) element of $\mathcal{A}$ chosen under $x$.

This estimator enjoys the following important properties:

1. \edefnit\selectfonta\edefnn)

   It is non-negative.

2. \edefnit\selectfonta\edefnn)

   It is unbiased, i.e.,

   $$\operatorname{\mathbb{E}}[\hat{c}_{a}]=c_{a}\quad\text{for all $a\in\mathcal{A}$}.$$

   (11)

3. \edefnit\selectfonta\edefnn)

   Its importance-weighted mean square is bounded as

   $$\operatorname{\mathbb{E}}\left[\sum\nolimits_{a\in\mathcal{A}}x_{a}\hat{c}_{a}^{2}\right]\leq n$$

   (12)

This trifecta of properties plays a key role in establishing the no-regret guarantees of the vanilla exponential weights algorithm [4, 18, 27]; at the same time however, (IWE) fails to take into account any side information provided by similarities between different elements of $\mathcal{A}$. This is perhaps most easily seen in the original red bus / blue bus paradox: if the commuter takes a red bus, the observed utility would be immediately translateable to the blue bus (and vice versa). However, (IWE) is treating the red and blue buses as unrelated, so $\hat{c}_{\textrm{blue bus}}$ is not updated under (IWE), even though $c_{\textrm{blue bus}}=c_{\textrm{red bus}}$ by default.

To exploit this type of similarities, we introduce below a layered estimator that shadows the step-by-step selection process of (NLC). To define it, let $x\in\operatorname{\operatorname{\Delta}}(\mathcal{A})$ be a mixed strategy on $\mathcal{A}$ with full support, and assume that an element $\hat{a}\in\mathcal{A}$ is selected progressively according to $x$ as in the case of (NLC):⁵⁵5To clarify, this process adheres to the “nested” part of (NLC); the conditional probabilities $x_{S^{\prime}|S}$ may of course differ. First, the learner chooses a similarity class $\hat{S}_{1}\in\mathcal{S}_{1}$ with probability $\operatorname{\mathbb{P}}(\hat{S}_{1}=S_{1})=x_{S_{1}}$; subsequently, conditioned on the choice of $\hat{S}_{1}$, a class $\hat{S}_{2}\mathrel{}\vartriangleleft\mathrel{}\hat{S}_{1}$ is selected with probability $\operatorname{\mathbb{P}}(\hat{S}_{2}=S_{2}|\hat{S}_{1})=x_{S_{2}|\hat{S}_{1}}$, and the process repeats until reaching a leaf $\hat{S}_{L}=\{\hat{a}\}$ of $\mathcal{S}$ (at which point the selection procedure terminates and returns $\hat{a}$). Then, given a loss profile $r\in[0,+\infty)^{\mathcal{S}}$ and a mixed strategy $x\in\operatorname{\operatorname{\Delta}}(\mathcal{A})$, the nested importance weighted estimator (NIWE) is defined for all $\ell=1,\dotsc,L$ as

where the chain of categorical random variables $\mathcal{A}\equiv\hat{S}_{0}\mathrel{}\vartriangleright\mathrel{}\hat{S}_{1}\mathrel{}\vartriangleright\mathrel{}\dotsm\mathrel{}\vartriangleright\mathrel{}\hat{S}_{L}=\{\hat{a}\}$ is drawn according to $x\in\operatorname{\operatorname{\Delta}}(\mathcal{A})$ as outlined above.⁶⁶6The indicator in (NIWE) is assumed to take precedence over $x_{S_{k}|S_{k-1}}$, i.e., $\hat{c}_{S_{\ell}}=0$ if $S_{k}\neq\hat{S}_{k}$ for some $k=1,\dotsc,\ell$.

This estimator will play a central part in our analysis, so some remarks are in order. First and foremost, the non-nested estimator (IWE) is recovered as a special case of (NIWE) when there are no similarity attributes on $\mathcal{A}$ (i.e., $L=1$). Second, in a bona fide nested model, we should note that $\hat{c}_{S_{\ell}}$ is $\hat{S}_{\ell}$-measurable but not $\hat{S}_{\ell-1}$-measurable: this property has no analogue in (IWE), and it is an intrinsic feature of the step-by-step selection process underlying (NIWE). Third, it is also important to note that (NIWE) concerns the idiosyncratic losses of each chosen class, not the base costs $c_{a}$ of each alternative $a\in\mathcal{A}$. This distinction is again redundant in the non-nested case, but it leads to a distinct estimator for $c_{a}$ in nested environments, namely

In particular, in the red bus / blue bus paradox, this means that an observation for the class “bus” automatically updates both $\hat{c}_{\textrm{red bus}}$ and $\hat{c}_{\textrm{blue bus}}$, thus overcoming one of the main drawbacks of (IWE) when facing irrelevant alternatives.

To complete the comparison with the non-nested setting, we summarize below the most important properties of the layered estimator (NIWE):

Of course, Proposition 1 yields the standard properties of (IWE) as a special case when $L=1$ (in which case there are no similarities to exploit between alternatives). To streamline our presentation, we prove this result in Appendix B.

We are finally in a position to present the nested exponential weights (NEW) algorithm in detail. Building on the original exponential weights blueprint [18, 4, 27], the main steps of the NEW algorithm can be summed up as follows:

1. (1)

   For each stage $t=1,2,\dotsc$, the learner maintains and updates a propensity score profile $Y_{t}\in\mathbb{R}^{\mathcal{A}}$.

2. (2)

   The learner selects an action $a_{t}\in\mathcal{A}$ based on the nested logit choice rule $a_{t}\sim P(\eta_{t}Y_{t})$ where $\eta_{t}\geq 0$ is the method’s learning rate and $P$ is given by (NLC).

3. (3)

   The learner incurs $r_{S,t}$ for each class $S\ni a_{t}$ and constructs a model $\hat{c}_{t}$ of the cost vector $c_{t}$ of stage $t$ via (NIWE).

4. (4)

   The learner updates their propensity score profile based on $\hat{c}_{t}$ and the process repeats.

For a presentation of the algorithm in pseudocode form, see Algorithm 1; the tuning of the method’s uncertainty parameters $\mu_{1}\geq\dotsc\geq\mu_{L}>0$ and the learning rate $\eta_{t}$ is discussed in the next section, where we undertake the analysis of the NEW algorithm.