Distribution-Dependent Rates for Multi-Distribution Learning

$\newcommand{\Uj}{\mathcal{U}_j}$ Thank you for the feedback. To answer your first point, let us detail how the algorithms presented mirror their BAI counterparts:

• The UE strategy in the BAI literature similarly samples $n$ times from each arm $a$ and ultimately picks the one with best empirical reward $\mu_T^\text{o}(a) \coloneqq \frac{1}{n}\sum_{i=1}^n r(X_a^{(i)})$. Since this is an unbiased estimate of the true mean, the regret analysis is a straightforward application of Hoeffding's inequality and yields the rate $\sum_a \Delta(a)\exp(-n\Delta^2(a))$, ignoring constants. In the MDL setting, there are two variables: the decision $a$ and the distributions $Q$ (serving the role of the ''arm'' in the BAI context). In essence, we apply UE on the latter to construct empirical proxy $\mu_T^\text{o}(a) = \min_Q \frac{1}{n}\sum_{i=1}^n r(a,X_Q^{(i)})$. Now, the analysis is more involved since $\mu_T^\text{o}$ is no longer an unbiased estimate of the true objective function, due to the minimization. For this reason, we instead rely on tools from empirical process theory and obtain the analogous regret of $\sum_a \Delta(a)\exp(-n[\Delta(a)-\sqrt{\log k / n}]^2)$. For more details on the BAI UE, we refer to Chapter 33 of Lattimore and Szepesvári - Bandit Algorithms.

• Our LCB-DR algorithm essentially uses the UCB-E strategy from BAI to find the worst-performing distribution for each decision $a$. Hence, let us take an iteration $j$ of LCB-DR and compare it to UCB-E for $k$ arms over $T$ rounds. Focusing on the exponentially decaying term, the latter guarantees a rate of $\exp(-(T-k)/H)$, where $H = \sum_a \Delta^{-2}(a)$ captures the instance complexity. In LCB-DR, our goal is to apply the same idea on the distributions $Q\in\mathcal{U}$. However, by round $j$, we have already collected data in the first $j-1$ rounds and would like to make use of it, in addition to the $T_j$ samples collected in this round. Intuitively, if some distribution has already been played enough times, the learner can identify it as suboptimal. This is what the set $\Uj\subset\mathcal{U}$ captures: it is a guess of the distributions that the learner is still unsure about and will thus end up playing on round $j$ (note that we do not constrain the decision to be from $\Uj$, so this quantity can be unknown). In Appendix D, we derive a new analysis of UCB-E for the setting where the learner starts the game with some samples, as is the case here. Corollary D.1 shows that $\Uj$ indeed contains the arms played. The regret bound shows that the learner essentially plays UCB-E only on arms $\Uj$ and, thus, the resulting rate scales with $H_j=\sum_{Q\in \Uj}\Delta_{a_j}^{-2}(Q)$, which can be much smaller than $H$ (in MDL, this translates to summing over all of $\mathcal{U}$) as it only sums over a subset of $\mathcal{U}$. In addition, the total number of pre-existing samples $\tilde T_j$ from $\Uj$ also contributes to the rate and we only offset by the size $k_j$ of $\Uj$. Putting these together, the LCB-DR regret for this round scales with $\exp(-(C_{a_j}^2\wedge 1)(T_j+\tilde T_j-k_j)/H_j)$, where $C_{a_j}$ is a complexity measure specific to MDL (see Section 4.1 for some intuition).

With regards to tightness of these bounds, it remains an open question. Translating results from BAI to MDL is not very straightforward, for the reasons mentioned above, and our work does not focus on the lower bounds. It would be interesting to see such guarantees in follow-up works.

As for the questions posed:

• We apologize for the omission. Here, $a^* = \text{arg}\max_{a\in\mathcal{A}} \mu_\text{DR}(a)$ is the optimal distributionally robust decision, which is assumed to be unique for the LCB-DR algorithm (its analysis is the only one that uses $C_a$). More generally, we can define

• $l=|\mathcal{A}|$ is the number of decisions available to the learner, as defined in Assumption 1.

• $M$ does not have to be known to the learner.

• Perhaps a more appropriate characterization would be $\Delta_\text{DR}(a)-B_n$ being suitably small. The idea is to mirror the Hoeffding v.s. Bernstein difference: for a random variable bounded in $[0,M]$ and with variance $\sigma^2$, the bounds are $\text{exp}(-t^2/M^2)$ v.s. $\text{exp}(-t^2/(\sigma^2+Mt))$, up to constants. For suitably small $t$, the $\sigma^2$ term dominates the sum $\sigma^2+Mt$ and the comparison boils down to $M^2$ v.s. $\sigma^2$, where the smaller term is better (note that here, the latter is always better). Similarly, when $\Delta_\text{DR}(a)-B_n$ is small relative to $\sigma_T^2+\Sigma_T^2+V_T$ (which occurs in small sample regimes), the latter dominates the denominator of the NUE rate and the UE v.s. NUE comparison reduces to $M^2/n$ v.s. $\sigma_T^2+\Sigma_T^2+V_T$.

Thank you for the thoughtful comments. Below, we address the weaknesses and questions posed.

Weaknesses

• (Distribution-dependent analysis) Our motivation for studying distribution-dependent rates is not necessarily to leverage domain knowledge of suboptimality gaps to devise algorithms, but to understand how regret scales with instance-specific quantities (e.g., suboptimality gaps). In the multi-armed bandit literature, it is well-established that such guarantees typically decay much faster with the sample budget compared to their distribution-independent counterpart (e.g., $\exp(-T)$ vs. $1/\sqrt{T}$). Our goal is to bring this perspective to the MDL paradigm.

  A consequence of this is that when domain knowledge is indeed available, distribution-dependent rates can reveal the benefits of exploiting this information. For example, the NUE analysis shows the interplay between variance and sample size allocations, so that when the data is real-valued and the learner has some understanding of the variances across distributions, they can gain insight on how directing more data to higher-variance distributions impacts regret.

• (DR Bayesian optimization) The setting of https://arxiv.org/pdf/2002.09038 is quite different from ours: they assume the learner receives some stochastic context $c_t$, sampled from a distribution in an uncertainty set $\mathcal{U}_t$ that changes with time, makes a decision $x_t$ and receives a reward $f(x_t,c_t)$ with additive noise. Their objective is to optimize a cumulative notion of regret. In our setting, we have a fixed uncertainty set and the task is to collect data from it, with the end goal of producing a decision that is distributionally robust in an offline sense.

Questions

• (Paper motivation) This interpretation is a good way to put it. As highlighted above, the idea is to understand how the rates scale with (possibly unknown) instance-specific parameters. The stark contrast between the distribution-dependent and independent guarantees stem precisely from this difference in perspective: the former fixes an environment and studies how an algorithms performs in it, whereas the latter applies to worst-case environments for each sample size and, thus, cannot scale with environment-specific quantities.

• (Omitted literature) This literature is presented in Section 1.2. We will make the appropriate citations earlier for further clarity.

• (Non-unique optimum) The LCB-DR analysis (the other strategies do not assume a unique optimum) remains unchanged if we more generally redefine the complexity measure

• (Typo) Thank you for pointing this out. We will make the necessary adjustment.

Thank you for the thoughtful feedback. Below, we address the identified weaknesses and respond to your specific questions.

Weaknesses

• (UCB v.s. NUE) Our core interest is in comparing adaptive v.s. non-adaptive strategies. While NUE incorporates a more nuanced approach than UE by exploiting the variance of different distributions, its advantage arises from a fundamentally different principle than LCB-DR, which leverages optimism by collecting data in an adaptive manner. The comparison between UE and LCB-DR directly examines the impact of adaptivity in terms of suboptimality gaps, providing insights into the trade-offs between simple exploration and more sophisticated adaptive strategies. Switching to NUE does not add any insight in this direction. In essence, NUE and LCB-DR offer complementary benefits relative to UE, and we opted to evaluate each one separately.
• (Experimental results) While experiments are indeed interesting to evaluate our methods, the central goal of this work is to provide a fundamentally different type of analysis for MDL algorithms. Our distribution-dependent approach examines how regret decays relative to instance-specific parameters (e.g., suboptimality gaps), offering a perspective that previous analyses did not address. This type of theoretical insight is challenging to illustrate through experiments, as the distribution-dependent rates of existing algorithms are not known.

Questions

• Active learning (AL) shares some similarities with MDL in that both involve actively collecting data. However, there are two fundamental differences between the two:

  • AL is specific to supervised learning, where the data is i.i.d. from a single distribution; the learner's goal is then to select which points to label, given access to covariates. In contrast, MDL can also address unsupervised tasks and involves multiple distributions; the learner's goal is to decide which distributions to sample from. This distinction means that, in MDL, the data can be tailored to fundamentally different tasks (when distributions are very dissimilar), leading to sampling strategies that differ significantly from those in AL.
  • The ultimate goal of AL is to produce a decision with good expected performance under the single data-generating distribution. In MDL, the objective is instead to obtain uniformly good performance across a collection of distributions. As a result, the way the learner uses the collected data to make decisions can vary significantly between the two settings.

  Due to these fundamental differences in the scope of both settings, ideas from AL are not so directly transferable to MDL.

• As far as we are aware, there are no lower bounds for distribution-dependent rates.

$\newcommand{\Eb}{\mathbb{E}}\newcommand{\Xc}{\mathcal{X}}\newcommand{\Ac}{\mathcal{A}}\newcommand{\dam}{\Delta_{a_j,\text{min}}}$ Thank you for the insightful comments. Below, we address the issues presented:

• (1-dimensional data assumption) The restriction to real-valued data is only for NUE and its comparison to UE. Otherwise, the analyses hold for arbitrary spaces.

• (NUE results) The UE v.s. NUE comparison mirrors the Hoeffding v.s. Bernstein inequalities for variables bounded in $[0,M]$ and with variance $\sigma^2$. In particular, the latter reduces to $\exp(-t^2/M^2)$ v.s. $\exp(-t^2/(\sigma^2+Mt))$, up to constants. For suitably small $t$, this boils down to $M^2$ v.s. $\sigma^2$, where the latter always wins. Similarly, in Section 3.3, we compare the rates when $\Delta_\text{DR}(a)-B_n$ is suitably small, which occurs in small sample regimes, yielding the analogous $M^2/n$ v.s. $\sigma_T^2+\Sigma_T^2+V_T$. As noted, this term indeed varies across arms and may be more ''suitably small'' for some.

  Moreover, while the guarantees of UE and NUE use $B_n=\sqrt{\log k/n}$ and $B_n=G_T$, respectively, we note in Appendix C that either term works for both rates. We use $G_T$ for NUE as it showcases the dependence on variance. However, when comparing the strategies, we assume small sample sizes, where $B_n$ is less significant and the focus is on the quantities above, so that we apply the same $B_n$ to both algorithms.

As for the prohibitive cost of creating a cover, this may indeed be a barrier in full generality. Let us highlight some settings where this is more feasible, the latter being the subject of your first question.

• (VC classes) Binary classification has been a major focus of the literature (e.g., Blum et al. (2017)). We mention this in Section 5 and further develop it in Appendix F. Suppose that the data is of the form $(X,Y)\in\Xc\times\\{0,1\\}$, decisions are binary-valued functions on $\Xc$ and the reward function is $r(a,(x,y)) = \mathbb{I}\\{a(x)=y\\}$. In Appendix F.1, we show that given a finite $\sqrt{\epsilon/k}$-cover $\Ac_\epsilon$ of $(\Ac,L^2(\bar Q_\Xc))$ (we refer to Appendix F.1 for the definitions), we can run the algorithms on it and incur an approximation penalty of $\epsilon$ on the regret. Suppose that $\Ac$ has finite VC dimension $d$. To construct a cover with high-probability, we can sample $O(k^2(d+\log(1/\delta))/\epsilon^2)$ points from $\bar Q_\Xc$ and project $\Ac$ onto this sample. By the Sauer–Shelah lemma, we also know that $|\Ac_\epsilon|\lesssim(k^2(d+\log (1/\delta))/(d\epsilon^2))^d$. With a slightly different analysis, we can also reduce the $k^2$ to $k$.
• (Linear classes) Suppose that $r(a,x)=v^\top\psi(a,x)$, for some known vector $v$ and feature mapping $\psi$ both lying in the unit Euclidean ball in $d$ dimensions (recall that the learner has access to $r$). Let $\psi(a,\bar Q)\coloneqq \Eb_{X\sim\bar Q}[\psi(a,X)]$, where $\bar Q$ is the uniform mixture of $Q_{1:k}$. The problem then reduces to constructing a cover of $\Ac$ w.r.t. the pseudo-metric $d(a,a')=\Vert\psi(a,\bar Q)-\psi(a',\bar Q)\Vert_2$. While we cannot access $\bar Q$ directly, we can sample from it to approximate $\psi(a,\bar Q)$. With $O(d\log(1/(\epsilon\delta))/\epsilon^2)$ samples, we can construct an $\epsilon$-cover of size $O(1/\epsilon^d)$ with high-probability.

Regarding unknown quantities in LCB-DR, we make some remarks:

• $\epsilon_j$ depends on the unknown quantities $H_{a_1:a_{j-1}}$ and $\dam$. The former are sums of the suboptimality gaps of $a_{1:j-1}$, for which we have already ran UCB-E. Hence, we can estimate them using the current data: $\Delta_{a_r}(Q)\approx\hat\mu_{n_{\bar T_{r}}}(a_r; Q) - \mu_T^\circ(a_r)$. The term $\dam$ is trickier as we have not yet collected samples for $a_j$. One idea is to use the data gathered so far via the proxy $Q\mapsto\hat\mu_{n_{\bar T_{j-1}}}(a_j; Q)$. However, this may not yield a good estimate if the available data is not informative for $a_j$. Given the assumption $r\in[0,1]$, another option is to use $1$ as a crude upper bound of $\dam$. Note that a large value for $\epsilon_j$ is not an issue since the regret is a decreasing function of it.
• Regarding $T_j$, we make a correction to Remark 4: Theorem 3 holds provided that the lower bound $T_j\gtrsim\epsilon_jH_j-\tilde T_j+k_j$ is satisfied. The regret, however, scales with $\epsilon_j$, and if the bound is loose, the dependence on $T_j$ is worse. The change is in Line 464: if we plug in a different value for $\epsilon_j$, the rate is no longer $O\left(\frac{(C_{a_j}^2\wedge 1)(T_j+\tilde T_j-k_j)}{H_j}\right)$. Ideally, we would choose $T_j$ so that the lower bound is as tight as possible. In practice, if the right-hand side is difficult to estimate, the learner can choose a large value for $\epsilon_j$, making the other terms relatively small, and select $T_j$ slightly above it. As discussed, a large $\epsilon_j$ should not be an issue.