Complexity Analysis of a Countable-armed Bandit Problem

The statistical complexity of this problem setting is best illustrated via the paradigmatic case of $K=2$ and $\alpha_{1}\leqslant 1/2$. In this case, one anticipates the problem to be at least as hard as the classical two-armed bandit with a mean reward gap of $\underline{\Delta}$. Indeed, we establish this in Theorem 3.2 via information-theoretic reductions adapted to handle a countable number of arms (proof is provided in Appendix C). In what follows, an instance $\nu$ of the problem refers to a collection of reward distributions with gap $\underline{\Delta}$; note that we are excluding the reservoir probabilities $\boldsymbol{\alpha}=\left(\alpha_{1},\alpha_{2}\right)$ from the definition of an instance. Recall that $\alpha_{1}$ denotes the reservoir probability associated with the optimal mean reward, and $\alpha_{2}=1-\alpha_{1}$ is the probability of the inferior. We will overload the notation for expected cumulative regret slightly to emphasize its dependence on $\nu$ as well as $\boldsymbol{\alpha}$.

We remark that the aforementioned definition is not restrictive in our problem setting since it is only natural that any reasonable policy should incur a larger cumulative regret (in expectation) in problems where the reservoir holds fewer optimal arms (in proportion).

Distinction from classical MAB. Although the above result bears resemblance to classical information-theoretic lower bounds for finite-armed bandits, it is imperative to note that the setting has a fundamentally greater complexity that requires a more nuanced analysis vis-à-vis the finite-armed problem. Traditional proofs, as a result, cannot be tailored to our setting in a translational manner. To see this, note that when $\alpha_{1}$ is high, a query of the reservoir is very likely to return an arm of the optimal type; in the limit as $\alpha_{1}\to 1$, the problem becomes degenerate as all policies incur zero expected regret. Clearly, the problem cannot be harder than a two-armed bandit with gap $\underline{\Delta}$ uniformly over all values of $\alpha_{1}$. While we conjecture $\alpha_{1}<1$ to be a sufficient condition for the existence of $\Omega\left(\log n/\underline{\Delta}\right)$ instance-dependent and $\Omega\left(\sqrt{n}\right)$ instance-independent (minimax) lower bounds, there are technical challenges due to probabilistic type associations over countably many arms. The restriction to $\alpha_{1}\leqslant 1/2$ and admissible policies (Definition 3.1) is then necessary for tractability of the proof and it remains unclear if this can be generalized further. Furthermore, when $K>2$, even defining an appropriate notion of admissibility à la Definition 3.1 is non-trivial and will likely involve dependencies on $\boldsymbol{\mu}$ in addition to $\boldsymbol{\alpha}$; pursuits in this direction are currently left to future work.

Though the bounds in Theorem 3.2 are tight in $n$ as we shall later see, they fail to provide any actionable insights w.r.t. ${\boldsymbol{\alpha}}$. A natural question in the CAB setting is whether and in what manner does the presence of countably many arms affect achievable regret. In particular, how does the difficulty associated with finding optimal arms from the reservoir (and the dependence on the distribution ${\boldsymbol{\alpha}}$) come into play. Below, we propose a lower bound that explicitly captures this dependence, albeit with respect to a somewhat restricted policy class.

Discussion. The proof is located in Appendix D. Several comments are in order. (i) The class $\tilde{\Pi}$, in particular, includes policies that front-load queries, i.e., query the reservoir upfront for a pre-specified number of arms and then deploy a regret minimizing routine on the queried set until the end of the playing horizon, see, e.g., the Sampling-UCB algorithm due to de Heide et al. (2021). (ii) The cited paper also derives an information-theoretic $\Omega\left(\log n/\alpha_{1}\underline{\Delta}\right)$ lower bound based on a standard reduction to a hypothesis testing problem, although notably their setting is non-trivially distinct from ours (this reflects starkly different sensitivities of achievable regret to $1/\alpha_{1}$-scale, as we shall later see). Importantly though, akin to Theorem 3.2, their bound too, establishes the existence of an instance with logarithmic regret. On the other hand, the foremost noticeable aspect of Theorem 3.3 that differs from aforementioned results is that it provides a uniform lower bound over all instances that are at least $\underline{\Delta}$-separated in the mean reward, as opposed to merely establishing their existence. (iii) The presence of $\underline{\Delta}$ in the numerator (unlike traditional bounds where $\underline{\Delta}$ resides in the denominator) suggests that while this bound may be vacuous if $\underline{\Delta}$ is “small,” it certainly becomes most relevant when $\underline{\Delta}$ is “well-separated.” At the same time, it should be noted that Theorem 3.3 does not contradict the $\mathcal{O}\left(\log n/\alpha_{1}\underline{\Delta}\right)$ upper bound (up to logarithmic factors in $\underline{\Delta}$) of Sampling-UCB; it merely provides a tool to separate regimes of $\underline{\Delta}$ where one bound captures the dominant effects vis-à-vis the other. (iv) A novelty of Theorem 3.3 lies in its proof, which differs from classical lower bound proofs in that it is based entirely on ideas from convex analysis as opposed to the information-theoretic and change-of-measure techniques hitherto used in the literature.

Remarks. (i) It is not impossible to avoid the $1/\alpha_{1}$-scaling of the instance-dependent logarithmic regret. We will later show via an upper bound for one of our algorithms (ALG2$(n)$) that the $\alpha_{1}$-dependence can, in fact, be relegated to constant order terms (ALG2$(n)$ queries arms adaptively based on sample-history and therefore does not belong to $\tilde{\Pi}$). Importantly, this will somewhat surprisingly establish that the instance-dependent logarithmic bound in Theorem 3.2 is optimal w.r.t. to its dependence on $\alpha_{1}$ (the scaling w.r.t. $\underline{\Delta}$, however, may not be best possible as forthcoming upper bounds suggest). (ii) Theorem 3.3 holds also for any arm-reservoir where the optimal type is at least $\underline{\Delta}$-separated from the rest, the nature of types (countable or uncountable) notwithstanding.

In the classical $K$-armed bandit problem, the (instance-dependent) regret scales linearly with the number of arms. We will next show that the $K$-typed countable-armed setting studied in this paper differs from its $K$-armed counterpart on account of a fundamentally distinct scaling of regret w.r.t. $K$. We will illustrate this by pivoting to a full information setting with one-sample learning, i.e., a setting where the decision maker observes the mean reward of an arm immediately upon pulling it, but does not learn whether it is optimal. Under such a setting, the optimal policy $\pi^{\ast}$ for the $K$-armed problem will pull each of the $K$ arms once and subsequently commit the residual budget of play to the optimal arm, thus incurring a lifetime regret of $\mathbb{E}R_{\infty}^{\pi^{\ast}}=\sum_{i=2}^{K}\left(\mu_{1}-\mu_{i}\right)=\Theta(K)$. The optimal policy for the $K$-typed countable-armed setting will, analogously, keep querying new arms from the reservoir until it has collected one of each of the $K$ types, and will subsequently commit to the arm within said collection that has the best mean reward. In this case, regret will only accrue until the decision maker has pulled one arm of each type.

If the reservoir distribution remains non-degenerate w.r.t. the optimal type, i.e., the fraction $\alpha_{1}$ of optimal arms in the reservoir remains bounded away from $1$ as $K$ increases, it is ensured that $\sum_{i=2}^{K}\alpha_{i}\left(\mu_{1}-\mu_{i}\right)$ remains non-vanishing in $K$. Consequently, the lower bound in Theorem 3.4 grows as $\Omega\left(K\underline{\Delta}\log K\right)$.

This result establishes a fundamentally distinct scaling of regret w.r.t. $K$ in the countable-armed setting vis-à-vis the $K$-armed one (in the full information setting). When the true type of an arm is not immediately observable, one only expects the $\Omega\left(K\log K\right)$ scaling to exacerbate. In fact, when the learning horizon is $n$, we conjecture that regret grows at least as $\Omega\left(K\log K\log n\right)$, where the $\Omega(\cdot)$ is modulo gap-dependent constants. Characterizing the information-theoretic optimal rate, however, remains a challenging open problem. The proof of Theorem 3.4 is provided in Appendix E.

In what follows (and all subsequent algorithms), a new arm is one that is freshly queried from the reservoir (an arm without a history of previous pulls). This arm belongs to type $i$ with probability $\alpha_{i}$ independent of the problem history thus far (collection of arms and types queried and the corresponding reward realizations until the current time).

Discussion of Algorithm 1. The foremost noticeable feature of this algorithm is the (nearly) exponentially increasing exploration schedule. Specifically, in the $k$^th epoch, each of the $K$ arms in the consideration set is played $\left\lceil e^{2\sqrt{k}}\log n\right\rceil$ times. It suffices to cap the size of the consideration set at $K$ since the decision maker is a priori aware of the existence of exactly $K$ arm-types in the reservoir. Upon completion of the $k$^th epoch, the cumulative-difference-of-reward statistic for each of the ${K\choose 2}$ arm-pairs is compared against a threshold of $2e^{-\sqrt{k}}m$, where $2e^{-\sqrt{k}}$ should be imagined as a proxy for a lower bound on the minimal reward gap $\delta$. If said statistic is small relative to the threshold for some pair, the pair is likely to contain arms of the same type (equal means), in which case, the algorithm discards the entire consideration set and ushers in a new epoch with a larger exploration phase. This is done to avoid the possibility of incurring linear regret should an optimal arm be missing from the consideration set (e.g., when all $K$ arms belong to type $2$). On the other hand, if all arm-pairs are sufficiently separated, the algorithm simply commits permanently to the empirically best arm. The intuition behind the (nearly) exponential schedule is that as $k$ grows, $2e^{-\sqrt{k}}$ will eventually provide a lower bound on $\delta$, and one may hope to achieve appropriate levels of error control using window sizes in the $k$^th epoch. Full proof is provided in Appendix F.

Discussion. The dependence on the minimal reward gap $\delta$ in Theorem 4.1 is not an artifact of our analysis but, in fact, reflective of the operating principle of the algorithm. ALG1$(n)$ keeps querying new consideration sets of size $K$ until it determines with high enough confidence that the queried arms are all distinct-typed; this is the genesis of $\delta$ in the upper bound. Importantly, equipped just with knowledge of $K$, it remains unclear if there exists an alternative sampling strategy that does not rely on assessing pairwise similarities between the queried arms, without necessitating any additional information on ${\boldsymbol{\alpha}}$. Furthermore, while ALG1$(n)$ is evidently rate-optimal in $n$ (in the instance-dependent sense), the scaling of its upper bound w.r.t. ${\boldsymbol{\alpha}}$ is far from optimal. In particular, the ${\boldsymbol{\alpha}}$-dependent factor in the leading term is attributable to a naive pre-determined exploration schedule. This dependence can, in fact, be relegated to $\mathcal{O}(1)$ terms using a more sophisticated policy that operates based on an adaptive determination of stopping and re-initialization times.

Remarks. (i) When $K=2$, the upper bound in Theorem 4.1 reduces to $\left(\tilde{C}_{{\boldsymbol{\alpha}}}/\underline{\Delta}\right)\log^{2}\left({4}/{\underline{\Delta}}\right)\log n+4\underline{\Delta}$, leading to a worst-case regret (w.r.t. $\underline{\Delta}$) of $\tilde{\mathcal{O}}\left(\tilde{C}_{{\boldsymbol{\alpha}}}\sqrt{n}\right)$, where the big-Oh only hides poly-logarithmic factors in $n$. This settles an open question concerning the best achievable minimax regret in the countable-armed problem with two types.²²2Minimax guarantees in previous work were polynomially bounded away from $\sqrt{n}$; see Kalvit and Zeevi (2020). (ii) While specifying the exploration schedule, the choice of the exponent in $k$ can be fairly general as long as it is coercive and grows sufficiently fast but sub-linearly; the square-root function is chosen for technical convenience. Instead, if one were to use a linear function of $k$ in the exponent, the algorithm’s performance would become fragile w.r.t. ex ante knowledge of ${\boldsymbol{\alpha}}$; an ill-calibrated ALG1$(n)$ can potentially incur linear regret.

Discussion of Algorithm 2. At any time, the algorithm computes two thresholds; $\mathcal{O}\left(\sqrt{m\log m}\right)$ and $\mathcal{O}\left(\sqrt{m\log n}\right)$ for the ${K\choose 2}$ pairwise difference-of-reward statistics, $m$ being the per-arm sample count. If said statistic is dominated by the former threshold for some arm-pair, it is likely to contain arms of the same type (equal means). The explanation stems from the Law of the Iterated Logarithm (see Durrett (2019), Theorem 8.5.2): a zero-drift length-$m$ random walk has its envelope bounded by $\mathcal{O}\left(\sqrt{m\log\log m}\right)$. In the aforementioned scenario, the algorithm discards the entire consideration set and ushers in a new one. This is done to avoid the possibility of incurring linear regret should an optimal arm be missing from the consideration set. In the other scenario that the difference-of-reward statistic dominates the larger threshold for all arm-pairs, the consideration set is likely to contain arms of distinct types (no two have equal means) and the algorithm simply commits to the empirically best arm. Lastly, if difference-of-reward lies between the two thresholds (signifying insufficient learning), the sample count for each arm is advanced by one, and the entire process repeats.

Reason for introducing zero-mean corruptions supported on $\boldsymbol{\mathbb{R}}$. Centered Gaussian noise is added to the difference-of-reward statistic in step (9) of ALG2$(n)$ to avoid the possibility of incurring linear regret should the support of the reward distributions be a “very small” subset of $[0,1]$. To illustrate this point, suppose that $K=2$, $s_{n}=1$, and the rewards associated with the two types are deterministic with $\underline{\Delta}<2\sqrt{2\log 2}$. Then, as soon as the algorithm queries a heterogeneous consideration set (one arm optimal and the other inferior) and the per-arm sample count reaches $2$, the difference-of-reward statistic will satisfy $\left\lvert\sum_{j=1}^{2}\left(X_{1,j}-X_{2,j}\right)\right\rvert=2\underline{\Delta}<4\sqrt{2\log 2}$, resulting in the consideration set getting discarded. On the other hand, if the consideration set is homogeneous (both arms simultaneously optimal or inferior), the algorithm will still re-initialize as soon as the per-arm count reaches $2$.³³3$\left\lvert\sum_{j=1}^{m}\left(X_{1,j}-X_{2,j}\right)\right\rvert=0$ identically in this case for any $m\in\mathbb{N}$ while $4\sqrt{m\log m}>0$ only for $m\geqslant 2$. This will force the algorithm to keep querying new arms from the reservoir at rate that is linear in time, which is tantamount to incurring linear regret in the horizon. The addition of centered Gaussian noise hedges against this risk by guaranteeing that the difference-of-reward process essentially has an infinite support at all times even when the reward distributions might be degenerate. This rids the regret performance of its fragility w.r.t. the support of reward distributions. The next proposition crystallizes this discussion; proof is provided in Appendix G.

Interpretation of $\boldsymbol{\beta_{\delta,K}}$. First of all, note that $\beta_{\delta,K}$ admits a closed-form characterization in terms of standard functions and satisfies $\beta_{\delta,K}>0$ for $\delta>0$ with $\lim_{\delta\to 0}\beta_{\delta,K}=0$. Secondly, $\beta_{\delta,K}$ depends exclusively on $\delta$ and $K$, and represents a lower bound on the probability that ALG2$(n)$ will never discard a consideration set containing arms of distinct types. This meta-result will be key to the upper bound on the regret of ALG2$(n)$ stated next in Theorem 4.3.

Remarks. The dependence on $\delta$ in Theorem 4.3 is not incidental and has the same genesis as discussed in the context of Theorem 4.1. However, there is a prominent distinction from Theorem 4.1 in that the dependence on ${\boldsymbol{\alpha}}$ is captured exclusively through the constant term (as opposed to the logarithmic term). This should be viewed in light of the lower bound in Theorem 3.3; by allowing for policies that query the arm-reservoir adaptively, one can potentially make the regret performance robust w.r.t. ${\boldsymbol{\alpha}}$. Absence of ${\boldsymbol{\alpha}}$ from the leading term also leads to the somewhat remarkable conclusion that the lower bound in Theorem 3.2 is optimal w.r.t. dependence on ${\boldsymbol{\alpha}}$. The proof is provided in Appendix H.

More on the inverse scaling w.r.t. $\boldsymbol{\gamma\left(s_{n}\right)}$. This multiplicative factor is likely a consequence of the countable nature of arms (as opposed to finite). When $K=2$, $\alpha_{1}\leqslant 1/2$, and the burn-in phase $s_{n}$ has a fixed duration independent of $n$, the upper bound in Theorem 4.3 reduces to $\mathcal{O}\left(\beta_{\underline{\Delta},2}^{-1}\left(\log n/\underline{\Delta}+\underline{\Delta}/\alpha_{1}\right)\right)$, where the big-Oh only hides absolute constants. Evidently, there is an inflation by $\beta_{\underline{\Delta},2}^{-1}$ relative to the optimal $\mathcal{O}\left(\log n/\underline{\Delta}\right)$ rate achievable in the paradigmatic two-armed bandit with gap $\underline{\Delta}$. By setting $s_{n}$ as a coercive sub-logarithmic function of the horizon $n$ (e.g., $s_{n}=\sqrt{\log n}$), one can shave off the $\beta_{\underline{\Delta},2}^{-1}$ factor to achieve $\mathcal{O}\left(\log n/\underline{\Delta}\right)$ regret. This establishes tightness of the instance-dependent lower bound in Theorem 3.2 when $K=2$. On the other hand, owing to the dependence of $\gamma\left(s_{n}\right)$ (and $\beta_{\underline{\Delta},2}$) on $\underline{\Delta}$, the worst-case (instance-independent) upper bound of ALG2$(n)$ can be observed from Theorem 4.3 to be bounded away from $\Omega\left(\sqrt{n}\right)$. However, recall that Theorem 4.1 already settles the issue of characterizing the optimal minimax rate when $K=2$ (up to logarithmic factors in $n$). Thus, we provide a complete characterization of the complexity of this problem when $K=2$, thereby answering all the open problems in Kalvit and Zeevi (2020). For $K>2$, Theorem 4.3 guarantees an upper bound of $\mathcal{O}\left(K^{3}\bar{\Delta}/\delta^{2}\log n\right)$ under a coercive sub-logarithmic burn-in phase. In this case, characterizing the optimal dependence on $\bar{\Delta}$ and $\delta$ remains an open problem. The scaling w.r.t. $K$, however, cannot be improved to $\mathcal{O}(K)$ as suggested by the $\Omega\left(K\log K\right)$ lower bound in Theorem 3.4. A full characterization of the complexity of the general setting with $K>2$ arm-types remains challenging and is left to future work.

In this section, we revisit the UCB-based adaptive policy proposed in Kalvit and Zeevi (2020) for $K=2$. The policy is restated as ALG3 below after suitable modifications for reasons discussed next. The original policy (Algorithm 2 in cited paper) achieves an instance-dependent regret of $\mathcal{O}\left(\log n\right)$. Additionally, this algorithm enjoys the benefit of being anytime in $n$ owing to the use of UCB1 (Auer et al., 2002) as a subroutine. However, it suffers a major limitation through its dependence on ex ante knowledge of the support of reward distributions. In particular, the algorithm requires the reward distributions associated with the arm-types to have “full support” on $[0,1]$, e.g., only distributions such as Bernoulli$(\cdot)$, Uniform on $[0,1]$, Beta$(\cdot,\cdot)$, etc., are amenable to its performance guarantees; Uniform on $[0,0.5]$, on the other hand, is not. We identify a simple fix to this issue: Drawing inspiration from the design of ALG2$(n)$, we propose adding a centered Gaussian noise term to the difference-of-reward statistic (see step (6) of Algorithm 3) to essentially create an unbounded support. This rids the algorithm of fragility w.r.t. the reward support while also preserving $\mathcal{O}\left(\log n\right)$ regret guarantees (see Theorem 4.4).

Remark. The original Algorithm 2 in cited paper uses a threshold that is distinct from $4\sqrt{m\log m}$ (see step (6) of Algorithm 3); the choice of $4\sqrt{m\log m}$ here aims to unify the technical presentation with ALG2$(n)$, and facilitate a more transparent comparison between the corresponding upper bounds.

Discussion of Algorithm 3. Similar to ALG2$(n)$, ALG3 also has an episodic dynamic with exactly one pair of arms played per episode. The distinction, however, resides in the fact that ALG3 plays arms according to UCB1 in every episode as opposed to playing them equally often until committing to the empirically superior one. Secondly, unlike ALG2$(n)$, ALG3 never “commits” to an arm (or a consideration set). The implication is that the algorithm will keep querying new consideration sets throughout the playing horizon; this property is at the core of its anytime nature. Despite these differences, the performance guarantees of the two algorithms are essentially identical when $K=2$, as the next result illustrates. The proof is provided in Appendix J.

Remark. It is possible to shave off the $\beta_{\underline{\Delta},2}$ factor by introducing in ALG3 a horizon-dependent burn-in phase à la ALG2$(n)$. This may be achieved at the expense of ALG3’s anytime property.

Limitation of ALG3. The performance stated in Theorem 4.4 together with its anytime property might appear to give an edge to ALG3 over ALG2$(n)$. However, the former is theoretically disadvantaged in that its logarithmic upper bound is not currently amenable to extensions to the general $K$-typed setting. The issue traces its roots to the use of UCB1 as a subroutine. The concentration behavior of UCB1 leveraged towards the analysis of ALG3 when $K=2$ fails to hold when $K>2$, rendering proofs intractable. This is illustrated via a simple example with $K=3$ types discussed below.

Technical issues with generalizing ALG3 to $\boldsymbol{K}$ types. When $K=2$, there are only two possibilities for what a consideration set could be; arms can have means that are either (i) distinct, or (ii) equal. In the former case, an optimal arm is guaranteed to exist in the consideration set and UCB1 will spend the bulk of its sampling effort on it, which is good for regret performance. In the latter scenario, since arms have equal means, UCB1 will split samples approximately equally between the two with high probability (see Theorem 4(i) in Kalvit and Zeevi (2020)); subsequently the consideration set will be discarded within a finite number of samples in expectation (see steps (6) and (7) of ALG3). Contrast this with an alternative setting with $K=3$ and mean rewards $\mu_{1}>\mu_{2}>\mu_{3}$. A natural generalization of ALG3 (see ALG4 in Appendix B) will query consideration sets of size $3$. Thus, a query can potentially return one arm with mean $\mu_{2}$ and two with mean $\mu_{3}$. Since an optimal arm (mean $\mu_{1}$) is missing, the algorithm will incur linear regret on this set; it is therefore imperative to discard it at the earliest. Unfortunately though, UCB1 will invest an overwhelming majority of its sampling effort in the “locally optimal” arm (mean $\mu_{2}$) and allocate logarithmically fewer samples among the other two. This logarithmic rate of sampling arms with mean $\mu_{3}$ is proof-inhibiting (vis-à-vis the $K=2$ case where the rate is linear as previously discussed), making it difficult to theoretically answer if ALG4 might still be able to discard the arms within, say, logarithmically many pulls of the horizon. This is an open research question and at the moment, an $\mathcal{O}\left(\log n\right)$ bound exists only for $K=2$; we could only establish asymptotic-optimality ($o(n)$ regret) when $K>2$ (see Theorem B.1). Among other things, identifying the optimal (instance-dependent) scaling factors w.r.t. $\left({\boldsymbol{\mu}},{\boldsymbol{\alpha}}\right)$ and the optimal order of minimax regret when $K>2$ remain open problems.