betaFeedback

WorksComputer Science

UCB-min: Combining Bandits Under Variance Heterogeneity (Extended Version)

Abstract

Multi-armed bandits are a natural framework for many real-world sequential decision problems, from recommender systems and clinical trials to educational test recommendation and online advertising. The performance of these algorithms depends on how they explore different arms, and exploration strategies range from variance-independent (e.g., UCB1) to variance-aware (e.g., UCB-V). In practice the reward variance of each arm is rarely known and varies widely across arms, and the reward support is often underspecified. In these cases no single rule is uniformly best: variance-independent methods are robust but loose when variances are small, while variance-aware methods are tight only when their variance estimates and the assumed support bound are reliable. Such heterogeneous, unknown variances arise in many settings, for instance when multiple objectives are scalarized into a single reward. We propose UCB-min, a per-arm adaptive meta-algorithm that selects, for each arm, the tighter of a variance-independent and a variance-aware exploration bonus, without prior knowledge of the variance regime and without reward normalization. We prove that, with UCB-V as variance-aware base, its regret is bounded by the sum of the two base bounds at the standard exploration constant, and by their per-arm minimum, up to a constant, for a larger one. We validate it on synthetic data, an educational tutoring task, and two group-recommendation benchmarks (MovieLens, Steam), showing that UCB-min consistently tracks the best base algorithm across diverse variance regimes and datasets.

Introduction

Multi-armed bandit (MAB) algorithms are fundamental to sequential decision-making under uncertainty, with applications in clinical trials [1], [2], recommender systems [3], [4], resource allocation [5], and online advertising [6], [7]. UCB methods assign each arm an optimistic index combining its empirical mean with an exploration bonus and pull the arm with the highest index; these bonuses range from variance-independent (UCB1 [8]) to variance-aware (UCB-V [9], [10]) design. The formal definitions and regret comparisons are given in Section II.

In practice the reward variance of each arm is rarely known and varies widely across arms, so neither family is uniformly best: variance-independent methods are robust but loose when variances are small, while variance-aware methods are tight only when their variance estimates and the assumed support bound are reliable. Normalization could remove this scale dependence but is often impractical online (see Section IV-A).

This is the extended version of the short paper of the same title accepted at IEEE BigData 2026.

This occurs in many real-world applications, in particular inherently multi-objective ones: recommender systems trade off accuracy with diversity, novelty, and fairness [11], [12], clinical trials optimize efficacy and safety [2], and advertising platforms balance user satisfaction and diversity [13]. In the recommendation settings we consider, each arm is an item (e.g., a news article or product), pulling it recommends that item, and the reward vector’s dimensions capture properties such as relevance, clicks, ratings, or engagement. A common way to handle several objectives is scalarization: combining the reward dimensions into a single scalar via application-specific weights w∈RDw \in\mathbb{R}^{D}, after which standard single-objective bandits such as UCB apply. This reduction is itself a source of the variance heterogeneity above, since the scalarized variance depends on the weights and the cross-objective covariance, quantities often unknown in advance, which makes scalarized multi-objective bandits a natural motivation for our work.

To address this, we propose UCB-min, a per-arm adaptive meta-algorithm for scalarized multi-armed bandits that selects, for each arm, the tighter of a variance-independent and a variance-aware exploration bonus. This choice requires no prior knowledge of the variance regime and no reward normalization. The approach is validated on synthetic datasets and real-world multi-objective applications: an education dataset [14], where multi-objective formulations and algorithm choice matter depending on the variance regime, and group recommendation datasets [15], where per-arm adaptation provides robustness across arms with different variance profiles.

Contributions: Our main contributions are the following:

  1. We analyze the effect of variance scales on regret in multi-objective bandits and empirically show that the relative performance of variance-independent (UCB1) and variance-aware (UCB-V) algorithms is data dependent.

  1. We propose per-arm adaptive meta-algorithms that dynamically select between variance-independent and variance-aware exploration bonuses on a per-arm basis, without prior knowledge of the variance regime and without normalization.

  1. We provide a theoretical guarantee for the per-arm minimum rule with UCB-V (UCB-minV1): the cumulative expected regret has the same asymptotic bound as the original algorithms and, for a larger exploration constant, tracks the regret of the best algorithm (Theorem 1); the variant with UCB-V2 (UCB-minV2) is validated empirically.

  1. We validate our approach on synthetic, educational, and recommendation datasets, showing robust empirical improvements across diverse variance regimes.

Multi-Objective Multi-Armed Bandits

This section introduces the (multi-objective) bandit framework and the UCB algorithms used throughout the paper. We first define the general stochastic bandit setting with multiple objectives, then present linear scalarization as a means of reducing it to a single-objective problem, and discuss the challenges this reduction creates for algorithm selection.

Multi-Objective Bandit Framework

We consider a stochastic multi-armed bandit with KK arms A={1,…,K}\mathcal{A} = \{1, \ldots, K\} and DD objectives. At each round t=1,…,Tt = 1, \ldots, T, the bandit algorithm selects an arm at∈Aa_t \in\mathcal{A} and observes a reward vector rt∈RDr_t \in\mathbb{R}^{D}. For each arm aa, the rewards are i.i.d. with unknown mean vector μa∈RD\mu_a \in\mathbb{R}^{D} and covariance matrix Σa∈RD×D\boldsymbol{\Sigma}_a \in\mathbb{R}^{D \times D}. Let Na(t)=∑τ=1t1{aτ=a}N_a(t) = \sum_{\tau=1}^{t} 1\{a_\tau= a\} be the number of times arm aa has been pulled up to time tt. The empirical estimators are, with the variance normalized by Na(t)N_a(t) as in [16 Theorem 1]:

μ^a(t)=1Na(t)∑τ=1aτ=atrτ,\hat{\boldsymbol{\mu}}_a(t) = \frac{1}{N_a(t)} \sum_{\substack{\tau=1\\a_\tau=a}}^{t} \mathbf{r}_\tau,
Σ^a(t)=1Na(t)∑τ=1aτ=at(rτ−μ^a(t))(rτ−μ^a(t))T.\hat{\boldsymbol{\Sigma}}_a(t) = \frac{1}{N_a(t)} \sum_{\substack{\tau=1\\a_\tau=a}}^{t} \left(\mathbf{r}_\tau-\hat{\boldsymbol{\mu}}_a(t)\right)\left(\mathbf{r}_\tau-\hat{\boldsymbol{\mu}}_a(t)\right)^{\mathsf{T}}.

Pareto vs. scalarized: A natural performance criterion in multi-objective bandits is Pareto regret, which measures suboptimality with respect to the Pareto front, which is the set of arms not simultaneously dominated by any other in all objectives [17], [18]. However, identifying and tracking the Pareto front can be computationally expensive. We therefore focus on scalarized regret: given application-specific weights, the objectives are combined into a single scalar, reducing the problem to a standard single-objective bandit that is directly compatible with existing UCB-style algorithms and well-suited when the desired trade-off is known in advance.

Linear scalarization reduces the multi-objective problem to a standard single-objective stochastic bandit, enabling the direct use of well-studied UCB algorithms and their theoretical guarantees. Given a fixed weight vector w∈RD\mathbf{w} \in\mathbb{R}^{D} with wd≥0w_d \ge0 and ∑d=1Dwd=1\sum_{d=1}^{D} w_d = 1, the scalarized reward observed at round tt is Xt=wTrtX_t = \mathbf{w}^{\mathsf{T}}\mathbf{r}_t. For each arm aa, the scalarized mean and variance are:

μa(s)=wTμa,σa2,(s)=wTΣaw,(1)\mu_a^{(s)} = \mathbf{w}^{\mathsf{T}}\boldsymbol{\mu}_a,\qquad\sigma_a^{2,(s)} = \mathbf{w}^{\mathsf{T}}\boldsymbol{\Sigma}_a\mathbf{w}, \tag*{(1)}

where the superscript (s)(s) marks scalarized quantities. After tt rounds, the empirical estimators are:

μ^a(s)(t)=wTμ^a(t),σ^a2,(s)(t)=wTΣ^a(t)w.(2)\hat{\mu}_a^{(s)}(t) = \mathbf{w}^{\mathsf{T}}\hat{\boldsymbol{\mu}}_a(t),\qquad\hat{\sigma}_a^{2,(s)}(t) = \mathbf{w}^{\mathsf{T}}\hat{\boldsymbol{\Sigma}}_a(t)\mathbf{w}. \tag*{(2)}

UCB Algorithms and Regret

The goal of bandit algorithms is to minimize the cumulative regret. Let a⋆=arg⁡max⁡aμa(s)a^\star= \arg\max_a \mu_a^{(s)}, μ⋆(s)=μa⋆(s)\mu_\star^{(s)} = \mu_{a^\star}^{(s)}, and Δa=μ⋆(s)−μa(s)\Delta_a = \mu_\star^{(s)} - \mu_a^{(s)}. The expected cumulative regret is:

R(T)=E[∑t=1T(μ⋆(s)−Xt)]=∑a∈AΔaE[Na(T)].(3)R(T) = \mathbb{E}\left[\sum_{t=1}^{T}\left(\mu_\star^{(s)} - X_t\right)\right] = \sum_{a\in\mathcal{A}}\Delta_a\mathbb{E}[N_a(T)]. \tag*{(3)}

To minimize this quantity, UCB-type algorithms assign each arm an index combining the empirical scalarized mean with an exploration bonus and select the arm with the highest index. βa(⋅)(t)\beta_a^{(\cdot)}(t) denotes a pure exploration bonus and Ba(⋅)(t)=μ^a(s)(t)+βa(⋅)(t)B_a^{(\cdot)}(t) = \hat{\mu}_a^{(s)}(t) + \beta_a^{(\cdot)}(t) the corresponding full index; the algorithm pulls arg⁡max⁡aBa(⋅)(t)\arg\max_a B_a^{(\cdot)}(t). This work builds upon well-known algorithms (presented below) which we apply to the scalarized multi-objective setting for rewards having support [0,b][0,b].

UCB1 [8]: UCB1 is variance-independent; its bonus and index are

βa(1)(t)=b2log⁡tNa(t),Ba(1)(t)=μ^a(s)(t)+βa(1)(t),(4)\beta_a^{(1)}(t) = b\sqrt{\frac{2\log t}{N_a(t)}},\qquad B_a^{(1)}(t) = \hat{\mu}_a^{(s)}(t) + \beta_a^{(1)}(t), \tag*{(4)}

achieving regret

∑a:Δa>08b2log⁡TΔa+(1+π23)∑aΔa.\sum_{a:\Delta_a>0}\frac{8b^2\log T}{\Delta_a}+\left(1+\frac{\pi^2}{3}\right)\sum_a\Delta_a.

When b=1b=1 this reduces to the standard formulation. Two refinements from the same work are UCB1-Tuned and UCB1-Normal [8]. UCB1-Tuned replaces the exploration bonus by

log⁡tNa(t)min⁡{14,σ^a2,(s)(t)+2log⁡tNa(t)}\sqrt{\frac{\log t}{N_a(t)}\min\left\{\frac{1}{4},\widehat{\sigma}_a^{2,(s)}(t)+\sqrt{\frac{2\log t}{N_a(t)}}\right\}}

using an empirical variance estimate to tighten the bonus; it often improves empirical performance but lacks formal regret guarantees. UCB1-Normal [8] targets Gaussian rewards; in our case, this assumption may not hold after scalarization of objectives.

UCB-V [9]: UCB-V explicitly uses variance in the exploration bonus:

βa(V)(t)=2σ^a2,(s)(t)clog⁡tNa(t)+3cblog⁡tNa(t),(5)\beta_a^{(V)}(t)=\sqrt{\frac{2\widehat{\sigma}_a^{2,(s)}(t)c\log t}{N_a(t)}}+\frac{3cb\log t}{N_a(t)}, \tag*{(5)}

with Ba(V)(t)=μ^a(s)(t)+βa(V)(t)B_a^{(V)}(t)=\widehat{\mu}_a^{(s)}(t)+\beta_a^{(V)}(t) and c=1.2c=1.2. Its regret bound [16 Theorem 4] is

10∑a:Δa>0(σa2,(s)Δa+2b)log⁡T,10\sum_{a:\Delta_a>0}\left(\frac{\sigma_a^{2,(s)}}{\Delta_a}+2b\right)\log T,

which improves over UCB1 when per-arm variances are small relative to bb.

UCB-V2 [10]: UCB-V2, our name for the version of UCB-V analyzed in [10], refines UCB-V with the bonus

βa(V2)(t)=max⁡(σ^a(s)(t)ρlog⁡T,bNa(t))⋅ρlog⁡TNa(t),(6)\beta_a^{(V2)}(t)=\max\left(\frac{\widehat{\sigma}_a^{(s)}(t)}{\sqrt{\rho\log T}},\frac{b}{\sqrt{N_a(t)}}\right)\cdot\frac{\rho\log T}{\sqrt{N_a(t)}}, \tag*{(6)}

and Ba(V2)(t)=μ^a(s)(t)+βa(V2)(t)B_a^{(V2)}(t)=\widehat{\mu}_a^{(s)}(t)+\beta_a^{(V2)}(t), where ρ\rho is a tuning parameter (ρ=2\rho=2 in our experiments). When b=1b=1, T≥3T\ge3, and ρ≥C0\rho\ge C_0 for a universal constant C0C_0, with probability at least 1−3K/T21-3K/T^2, its regret scales as

16min⁡{∑a=2Kσa2,(s),∑a=2K16σa2,(s)σ1(s)}ρTlog⁡T+(K−1)ρlog⁡T,16\min\left\{\sqrt{\sum_{a=2}^{K}\sigma_a^{2,(s)}},\sum_{a=2}^{K}\frac{16\sigma_a^{2,(s)}}{\sigma_1^{(s)}}\right\}\sqrt{\rho T\log T}+(K-1)\sqrt{\rho\log T},

where the arms are indexed so that the optimal arm a⋆=1a^\star=1.

We review related work on MAB alternatives and on meta-combination strategies for bandit algorithms beyond the UCB-based methods already introduced in Section II-B.

MAB alternatives: Thompson Sampling (TS) [19], [20] and KL-UCB [21] often perform well but rely on distributional assumptions: TS needs a prior and likelihood model, and KL-UCB derives bounds from KL-divergences for specific families (e.g., Bernoulli); EUCBV [22] combines variance estimates with arm elimination. After scalarization, which mixes heterogeneous objectives (e.g., binary and continuous), the reward distribution is unknown in advance, so we focus on distribution-free UCB methods and do not compare against TS or KL-UCB, but against UCB1, UCB1-Tuned, UCB-V, UCB-V2, and EUCBV (§ 5).

Multi-objective problems: Multi-objective sequential decision problems are addressed either through Pareto-based methods, which maintain the set of non-dominated solutions, or through scalarization-based methods, which reduce the objectives to a single scalar [17, 23]. Pareto-based approaches require repeated dominance checks, and the Pareto front can be prohibitively large [23 Sec. 4.2.2], which has motivated cost-reducing heuristics such as annealing [24]. Scalarization (linear, Chebyshev, randomized, etc.) is a lightweight alternative, directly compatible with UCB/Thompson-style bandit and RL algorithms. Studies include a MOMAB framework with empirical comparisons [17], contextual Pareto regret bounds [18], the Generalized Gini Index [25], and, in multi-objective RL, a survey of MOMDP/MORL methods with conditions under which scalarization preserves optimality [23] and the learning of policies that treat several users equitably [26]. As discussed in § 1, scalarization induces heterogeneous per-arm variance, which motivates the per-arm rule validated in § 5.

Meta algorithms: Several works consider meta-combination of bandit strategies. Meta-UCB [27] treats each base learner as a single arm in a higher-level bandit, and its regret depends only on that of the best base learner. Corralling [28] adaptively selects which base algorithm to run each round. [29] proposes MIN-UCB, a per-arm min-of-indices approach combining online samples with offline data via a bias-correction term, providing instance-dependent and near-minimax guarantees but requiring offline data and a known bias bound. None of these works studies a fully online, distribution-free per-arm rule selecting between variance-independent and variance-aware indices without offline data or known bias bound, a gap this work addresses. These are therefore not directly comparable baselines: Meta-UCB and Corralling select among entire algorithms rather than per arm, MIN-UCB additionally requires offline data and a known bias bound, and adversarial selectors such as Exp3 ignore variance entirely. A related idea appears in the stopping-rule literature, where [30] combines a variance-independent and a variance-aware stopping rule by stopping at the earlier of the two; that work targets (ϵ,δ)(\epsilon, \delta) mean estimation rather than per-arm bandit regret minimization. Another family of methods scales bandits to large recommendation settings by sharing statistics across users: CLUB [31] and its data-dependent refinement [32] cluster users online, DCCB [33] distributes the clustering over a peer-to-peer network, and DistCLUB [34] constructs clusters lazily to reduce communication. These are contextual linear bandits requiring item features and the identity of the user at each round, hence not comparable baselines in the featureless scalarized setting we consider: they exploit similarity across users, whereas UCB-min adapts to per-arm variance.

UCB-min: Per-Arm Adaptive Meta-Algorithm

Variance Changes in Multi-Objective Scalarization

Eq. (1) shows that the scalarized variance depends on the weights and on the covariance structure of the objectives, and correlation effects can reduce it substantially. Scalarized variances may therefore range from very small to comparable to the largest single-objective variance, creating a dilemma between variance-aware methods (effective when variance is small) and variance-independent ones (more robust otherwise).

Two practical difficulties make this dilemma worse. First, normalization is often impractical: reward scales are unknown online, non-stationary settings require continuous re-estimation, and for physical objectives (energy, time, cost) no predetermined upper bound exists. It does not reliably reduce regret either (see Figure 7a-Figure 7b). Second, the algorithms above require the support bound bb, which is generally unknown without normalization: Gaussian rewards are unbounded and, for real-world data, the effective range is hard to determine in advance. Using a large bb inflates all exploration bonuses and leads to near-linear regret (see Figure 8b).

Figure 7. Effect of normalization (a: raw rewards in [0,5][0, 5], b: normalized to [0,1][0, 1]) on MovieLens cumulative regret.

Figure 8. Effect of the support bound bb (a: b=1b = 1, b: b=5b = 5, one group) on MovieLens cumulative regret.

The UCB-min Meta-Algorithm

To control these issues, we propose UCB-MIN, an adaptive per-arm meta-algorithm that selects, for each arm, the tighter of a variance-independent and a variance-aware exploration bonus. It is analyzed in Theorem 1, validated in § 5, and, although both bonuses still, in theory, depend on the support bound bb, is empirically robust to an underestimated bb, allowing the default b=1b = 1 across variance regimes. Throughout, “meta” refers to combining existing base algorithms in this sense, and not to meta-learning.

Algorithm 1 UCB-min

Require: Arms A\mathcal{A}, horizon TT, weight vector w\mathbf{w}

  1. Initialize: ∀a\forall a: Na←0N_a \leftarrow0, μ^a←0D\hat{\boldsymbol{\mu}}_a \leftarrow0_D, Σ^a←0D×D\hat{\boldsymbol{\Sigma}}_a \leftarrow0_{D \times D}

  2. Pull each arm a∈Aa \in\mathcal{A} once.

  3. for t=1t = 1 to TT do

  4. for each a∈Aa \in\mathcal{A} do

  5. Compute μ^a(s)(t)\hat{\mu}^{(s)}_a(t) and σ^a2,(s)(t)\hat{\sigma}^{2,(s)}_a(t) (Eq. (2))

  6. Compute the bonuses βa(1)(t)\beta^{(1)}_a(t) (Eq. (4)) and βa(var)(t)\beta^{(\mathrm{var})}_a(t) (Eq. (5) or (6))

  7. Ba(t)←μ^a(s)(t)+min⁡{βa(1)(t),βa(var)(t)}B_a(t) \leftarrow\hat{\mu}^{(s)}_a(t) + \min\{\beta^{(1)}_a(t), \beta^{(\mathrm{var})}_a(t)\}

  8. end for

  9. Pull at←arg⁡max⁡aBa(t)a_t \leftarrow\arg\max_a B_a(t), observe rt\mathbf{r}_t, update NatN_{a_t}, μ^at\hat{\boldsymbol{\mu}}_{a_t}, Σ^at\hat{\boldsymbol{\Sigma}}_{a_t}

  10. end for

For each arm aa, we compute both the variance-independent bonus βa(1)(t)\beta^{(1)}_a(t) (Eq. (4)) and a variance-aware bonus βa(var)(t)\beta^{(\mathrm{var})}_a(t) (Eq. (5) or (6)), keep the tighter one, and add the empirical mean once:

Ba(t)=μ^a(s)(t)+min⁡{βa(1)(t),βa(var)(t)}=min⁡{Ba(1)(t),Ba(var)(t)}.(7)B_a(t) = \hat{\mu}^{(s)}_a(t) + \min\left\{\beta^{(1)}_a(t), \beta^{(\mathrm{var})}_a(t)\right\} = \min\left\{B^{(1)}_a(t), B^{(\mathrm{var})}_a(t)\right\}. \tag*{(7)}

Both forms coincide since μ^a(s)(t)\hat{\mu}^{(s)}_a(t) is shared, and Appendix A uses the second one, which reasons directly on indices. Each arm thus benefits from variance-aware exploration when its empirical variance is low, and reverts to UCB1 when the variance-aware bonus would be too large. Both bonuses are already valid upper confidence bounds, so their minimum is valid as well, and being the tighter of the two it avoids the exploration that a larger combination (maximum, mean) would incur for no gain in guarantee. This is especially useful when bb is misspecified: for a small bb (e.g., the default b=1b = 1), βa(1)(t)\beta^{(1)}_a(t) remains tight while the variance-aware bonus may still be inflated by large empirical variances. The selection also depends on the pull count Na(t)N_a(t): the variance-aware bonus carries an extra O(1/Na(t))O(1/N_a(t)) term that dominates in early iterations, so the minimum then falls back on βa(1)(t)\beta^{(1)}_a(t), and the variance plays its role mainly once Na(t)N_a(t) is large enough.

We consider two variants depending on the variance-aware base:

  • UCB-minV1: βa(var)=βa(V)\beta^{(\mathrm{var})}_a = \beta^{(V)}_a, Eq. (5),

  • UCB-minV2: βa(var)=βa(V2)\beta^{(\mathrm{var})}_a = \beta^{(V2)}_a, Eq. (6).

Both share the same structure, presented in Algorithm 1. At each round, we compute scalarized statistics μ^a(s)(t)=wTμ^a(t)\hat{\mu}^{(s)}_a(t) = \mathbf{w}^{\mathsf{T}}\hat{\boldsymbol{\mu}}_a(t) and σ^a2,(s)(t)=wTΣ^a(t)w\hat{\sigma}^{2,(s)}_a(t) = \mathbf{w}^{\mathsf{T}}\hat{\boldsymbol{\Sigma}}_a(t)\mathbf{w}, evaluate both bonuses, and pull arg⁡max⁡aBa(t)\arg\max_a B_a(t) with Ba(t)B_a(t) as in Eq. (7).

Computational cost: UCB-min evaluates two bonuses per arm at each round, so its cost per round is of the same order as that of UCB1 and UCB-V, namely O(K)O(K) given the scalarized statistics. With a fixed weight vector w\mathbf{w}, these statistics are the empirical mean and variance of the scalarized rewards observed on each arm, since

wTΣ^a(t)w=1Na(t)∑τ≤t,aτ=a(Xτ−μ^a(s)(t))2,\mathbf{w}^{\mathsf{T}}\hat{\boldsymbol{\Sigma}}_a(t)\mathbf{w} = \frac{1}{N_a(t)} \sum_{\tau\le t, a_\tau= a} \left(X_\tau- \hat{\mu}^{(s)}_a(t)\right)^2,

and can be updated online in O(1)O(1) time and memory per arm; maintaining the full covariance Σ^a(t)\hat{\boldsymbol{\Sigma}}_a(t), at a cost of O(D2)O(D^2) per arm, is only needed to evaluate several weight vectors on the same observations, where diagonal or low-rank approximations would reduce this cost for many objectives.

Regret upper bound: We next show that the asymptotic regret bound of UCB-minV1 is the same as the regret bound of the original algorithms:

Theorem 1. Fix per-arm Δa\Delta_a, σa2\sigma_a^2, and support bound bb. The statement holds for any bounded rewards, so we omit the (s){}^{(s)} superscript here and in the proof.

(i) For c≥4c \ge4 in the UCB-V index, UCB-minV1 attains for each arm the minimum of the UCB1 and UCB-V regret bounds, up to a constant:

O((∑amin⁡(σa2Δa+b,b2/Δa))log⁡T+∑aΔa).O\left(\left(\sum_a \min\left(\frac{\sigma_a^2}{\Delta_a}+b, b^2/\Delta_a\right)\right)\log T+\sum_a\Delta_a\right).

i.e. it is never worse than the better of the two on any arm.

(ii) At the standard c=1.2c = 1.2 [9], UCB-minV1 still enjoys the weaker guarantee of being bounded by the sum of the two base bounds:

O((∑aσa2+b2Δa+b)log⁡T+∑aΔa).O\left(\left(\sum_a\frac{\sigma_a^2+b^2}{\Delta_a}+b\right)\log T+\sum_a\Delta_a\right).

We use c=1.2c = 1.2 in our experiments, the value fixed by [9], at which only part (ii) is proved; a larger cc would keep the guarantee valid but enlarges the bonus, hence adds exploration, which is not always desirable (e.g. Figure 8b). While our theoretical guarantees are limited to UCB-minV1 and the stronger guarantee of part (i) also requires a larger cc, our experiments in § 5 provide empirical evidence for similar behavior beyond the scope of the theorem, with both UCB-minV1 and UCB-minV2 appearing to track the best of their base algorithms.

Note: An alternative is global selection: at each round, estimate the regret upper bounds of both UCB1 and the variance-aware algorithm, then apply the one with the smaller bound to all arms (Meta-1 with UCB-V, Meta-2 with UCB-V2). However, it ignores heterogeneous per-arm variance, accumulates early-round estimation errors, and relies on bounds that may greatly overestimate actual regret; our experiments confirm it is unreliable, so we focus on the per-arm rule.

Experiments

We present the experimental results, with two objectives: (1) show how UCB-MIN adapts to different variance regimes, and (2) show that real-world multi-objective applications benefit from this adaptation.

Datasets

We evaluate on three types of data: synthetic instances, an educational tutoring simulator, and two group recommendation benchmarks (MovieLens, Steam).

Synthetic Data. We generate instances with K=20K = 20 arms and D=2D = 2 independent Gaussian objectives, with means in [0,1][0, 1] and standard deviations in [σmin⁡,σmax⁡][\sigma_{\min}, \sigma_{\max}]. Two dimensions suffice, as the goal is to validate behavior under controlled variance regimes.

Educational Data.1 The dataset [35] contains 4,918 students, 948 questions, and 1.38M responses. Each question is assigned a difficulty level l∈{1,…,5}l \in\{1,\ldots,5\} based on global success rate; each student’s proficiency lul_u is the highest level with ≥50%\ge50\% correct answers. Arms correspond to the K=5K = 5 difficulty levels. Following [14], pulling arm aa (level lal_a) for a student at level lul_u yields the following reward components that all lie in [0,1][0,1]:

  • Aptitude (A): r(A)r^{(A)}: a binary reward indicating correct/incorrect answer.

  • Competence (C): r(C)=1−∣lu−la∣/Kr^{(C)} = 1-\lvert l_u-l_a\rvert/K (difficulty matching).

  • Performance (P): r(P)=max⁡{0,(la−lu)/K}r^{(P)}=\max\{0,(l_a-l_u)/K\} (potential progression).

  • Gap (G): r(G)=1−∣lfail−la∣/Kr^{(G)}=1-\lvert l_{\mathrm{fail}}-l_a\rvert/K (recovery from failure with lfaill_{\mathrm{fail}} the user’s failing level).

Steam2 and MovieLens 25M3: Group Recommendations. MovieLens 25M [36] contains 25M ratings (scale 0.5-5) from 162K users on 62K movies across 20 genres. Steam contains 41M recommendations from 14M users on 51K games with 337 tag categories; we use an extract of 4M user profiles. MovieLens groups of 20 users are formed via a variance-constrained process, whereas Steam groups are real community groups extracted via the Steam API. The relevance of a category for a group is the average rating over group members and items in that category. Objectives follow [15]; arms are categories and pulling category cc for group GG yields:

  • Relevance: rc,t(R)=rel⁡(u,c)r_{c,t}^{(R)} = \operatorname{rel}(u,c) for randomly sampled user u∈Gu \in G.

  • Pairwise Disagreement: rc,t(D)=∣rel⁡(u,c)−rel⁡(v,c)∣r_{c,t}^{(D)} = \lvert\operatorname{rel}(u,c) - \operatorname{rel}(v,c) \rvert for sampled pair u,vu,v.

Disagreement is inverted to rmax⁡−r(D)r_{\max} - r^{(D)} for maximization, where rmax⁡r_{\max} is the maximum rating of the dataset. Rewards lie in [0,5][0,5] for MovieLens (not normalized) and [0,1][0,1] for Steam.

Evaluation Metrics

The algorithms are evaluated along three categories of metrics, formally defined in Appendix B.

Regret: cumulative regret, as defined in Eq. (3).

Ranking quality: Hit Rate@kk, assessing whether one of the last kk recommended arms is among the 5 arms with the highest true scalarized mean.

Domain-specific: Click-Through Rate (CTR) for MovieLens and Steam; skill progression (NCC) for the educational task.

Implementation and Experiments Details

Machine specifications: All experiments ran on a Linux server (8-core Intel Xeon E5-2609v2 2.5GHz, 64GB RAM).

Experiments: Each algorithm is run 50 times and averaged, under identical seeds, horizon and value of bb; all objectives get equal weights. We aggregate over 200 users (diverse skill levels) for Education and 50 groups for Steam and MovieLens, the latter formed to ensure variance heterogeneity. We report the algorithms of Sections II-IV; on the real-world datasets, EUCBV and Meta-1 are omitted for clarity as they never reach the lowest regret on synthetic data, and UCB-minV1 as the experiments focus on UCB-minV2; their full curves are available online.4 Error bars report one standard deviation over the runs; they are omitted in some figures for readability. The open-source Python implementation, datasets descriptions and supplementary materials are available online.4 The raw experimental results, additional results and datasets are also available online.5

Support bound: We set b=1b = 1 everywhere. This matches the true support for the educational and Steam data (rewards in [0,1][0,1]); for MovieLens and high-variance synthetic data it underestimates the support, matching our setting where the reward range is unknown in advance. The theoretical guarantees of all compared methods no longer apply there; this is exactly the purpose of this evaluation, which assesses their empirical robustness to an underestimated bb. Figure 8b reports a well-specified bound for MovieLens.

Results

Variance regimes - Synthetic data: Figures 1a-1b show cumulative regret under two variance regimes with the same scalarization weights. In the low-variance regime (Figure 1a), UCB-V2 achieves roughly 10× lower final regret than UCB1, confirming the theoretical advantage of variance-aware bounds when σa2,(s)\sigma_a^{2,(s)} is small. In the high-variance regime (Figure 1b), this relationship reverses: UCB-V2 shows near-linear regret growth, as large empirical variances make its bonus too large and cause over-exploration. Since Gaussian rewards exceed [0,1][0,1] in this regime, b=1b=1 underestimates the true support; nonetheless, UCB1’s bonus is smaller than UCB-V2’s variance-dependent bonus, making UCB1 more robust in this regime. UCB-minV1 adapts automatically, tracking UCB-V in Figure 1a and UCB1 in Figure 1b without prior knowledge; UCB-minV2 behaves similarly but with lower regret thanks to the tighter UCB-V2 bound, so the remaining experiments focus on it, although Theorem 1 does not cover it. Figure 1c further motivates per-arm adaptation using a synthetic instance where half the arms have low variance (σ∈[0.2,0.4]\sigma\in[0.2,0.4]) and the other half have high variance (σ∈[2.0,4.0]\sigma\in[2.0,4.0]). In this heterogeneous setting, neither UCB1 nor UCB-V2 dominates: UCB1 is penalized on low-variance arms, while UCB-V2 over-explores high-variance arms. UCB-minV2 achieves the lowest regret by adapting its strategy per arm, outperforming all other tested algorithms by the end of all iterations. Figure 2 shows the resulting selection: the variance-aware bonus is chosen on 80-100% of the pulls of the low-variance arms, against 12-23% on the high-variance ones, letting UCB-minV2 reach the lowest final regret by following the variance profile of each arm.

Three cumulative-regret plots across low-variance, high-variance, and heterogeneous-arm regimes; curves are labeled UCB1, UCB1-tuned, UCB1-normal, UCB-V, UCB-V2, EUCBV, Meta-1, UCB-minV1, Meta-2, and UCB-minV2

Figure 1. Cumulative regret across variance regimes: (a) σ∈[0.1,0.3]\sigma\in[0.1,0.3], (b) σ∈[2,4]\sigma\in[2,4], (c) heterogeneous arms. (a) and (b) share the same scalarization weights, whereas (c) illustrates the impact of heterogeneous arm variances (high variance for half of the arms, low variance for the other half); its y-axis is cut at 2.2k (UCB-V and UCB1-Normal end at 3.7k and 6.5k).

Figure 2. Per-arm selection on the heterogeneous instance of Figure 1c. Top: true scalarized variance per arm. Bottom: how the pulls of each arm split between the two bonuses.

Figure 3 shows how the choice of scalarization weights affects the variance regime and thus the relative performance of the algorithms. Here, one objective dimension has low variance (σ∈[0.1,0.5]\sigma\in[0.1,0.5]) and the other has high variance (σ∈[2.0,4.0]\sigma\in[2.0,4.0]). With w=(0.2,0.8)w=(0.2,0.8) (Figure 3a), the weight vector emphasizes the high-variance dimension, resulting in large scalarized variances. In this regime, UCB1 performs better while UCB-V2 over-explores due to large variance-dependent bonuses. Conversely, with w=(0.8,0.2)w = (0.8, 0.2) (Figure 3b), the weight vector emphasizes the low-variance dimension, reducing the scalarized variance and shifting the regime toward one where variance-aware methods perform better. In both cases, UCB-minV2 tracks the better-performing base algorithm, adapting to the effective variance regime induced by the weights.

Figure 3. Impact of scalarization weights on cumulative regret. Dim 1 has σ∈[0.1,0.5]\sigma\in[0.1, 0.5] (low variance), Dim 2 has σ∈[2.0,4.0]\sigma\in[2.0, 4.0] (high variance).

Educational dataset (short horizon): For this dataset, b=1b = 1 matches the true support since all rewards lie in [0,1][0, 1]. Figure 4 reports both cumulative regret and the progression skill for T=300T = 300 (short horizon, realistic for exercise recommendation). Comparing columns (from left to right), progression skill increases, confirming the benefit of multi-objective formulations for this task. In terms of regret, UCB1 tends to perform better in the very early stages, while the variance-aware UCB-V2 becomes more effective later as more observations are collected and variance estimates stabilize. UCB-minV2 shows a similar transition: it behaves like UCB1 in the initial iterations (e.g. the first 50 in Figure 4c) before shifting toward UCB-V2.

Figure 4. Educational data: regret (top row) and progression skill (bottom row) for T=300T = 300. Columns correspond to different objective sets (A, A+P, A+C+G).

Figure 5 shows the reward distributions of one user across all arms in the A+C+G setting with equal weights, one row per objective dimension and the scalarized reward on the bottom row. The dimensions have very different shapes, Aptitude being binary and Competence and Gap continuous with arm- and user-dependent moments. After scalarization the resulting distributions differ across arms in both mean and variance, and their shape is arm-specific and hard to anticipate: some are close to Gaussian, others bi-modal. This motivates an algorithm that adapts its exploration per arm from observed data rather than from assumptions on the underlying distributions.

Reward distributions per arm for a given user

Figure 5. Reward distributions per arm for a given user (level 3) in the A+C+G setting with equal weights. Rows: individual objective dimensions and scalarized reward. Columns: difficulty levels (arms).

Group recommendation - MovieLens and Steam: These experiments use the two-objective formulation of [15] (relevance and pairwise disagreement) and show that the proposed meta-algorithm adaptively follows the best underlying base strategy.

On MovieLens (Figure 6a-Figure 6c), rewards lie in [0,5][0, 5] (not normalized), so b=1b = 1 underestimates the true support. UCB1’s bonus is then moderate and provides sufficient exploration, while UCB-V2 over-explores as its bonus scales with the empirical variances, which are large (>1> 1). UCB-minV2 identifies this regime and aligns with UCB1 throughout the horizon, also matching it on CTR (Figure 6b) and Hit Rate@1 (Figure 6c).

Figure 6. MovieLens (top row) and Steam (bottom row): Relevance and Pairwise Disagreement. Error bars are clipped in (a) and (d).

AlgorithmLowHighHetero.AA+PA+C+GT=3kT = 3\mathrm{k}T=30kT = 30\mathrm{k}
UCB11005.51064137338.021.137.82341381
UCB1-Normal271.7412464907.418.419.9450638
UCB-V776.93248372967.325.346.99081086
UCB-V294.5232385138.420.437.7406613
EUCBV172.91621965-----
UCB-minV1742.09691267-----
UCB-minV292.695879938.220.437.7233612

Table 1. Final cumulative regret at the horizon TT of each experiment (mean over the 50 runs), computed from the plotted curves of Figure 1, Figure 4, and Figure 6; lowest value per column in bold. UCB1-Tuned, Meta-1, and Meta-2 are not reported, as they have no regret guarantee. Synthetic: low-variance, high-variance, and heterogeneous regimes (Figure 1a-Figure 1c), with T=20kT = 20\mathrm{k}, 20k20\mathrm{k}, and 40k40\mathrm{k}. Education: objective sets A, A+P, and A+C+G. “-”: not shown in the figures of this dataset.

On Steam (Figure 6d-Figure 6f), rewards are in [0,1][0, 1] and per-arm variances are small, a regime where variance-aware exploration is optimal: among UCB1, UCB-V, and UCB-V2, UCB-V2 achieves the lowest regret (Figure 6d) and UCB-minV2 closely tracks it, consistently across all metrics (Figure 6e-Figure 6f); UCB1-Tuned reaches a lower regret on this dataset. This contrast with MovieLens illustrates the dataset-dependent nature of the optimal exploration strategy and the robustness of UCB-min.

Effect of Reward Normalization on MovieLens: Figures 7a-7b compare UCB-type algorithms on MovieLens under raw rewards in [0,5][0, 5] and rewards normalized to [0,1][0, 1] by dividing by the maximum rating, with b=1b = 1 in both cases.

The two settings induce different variance regimes. With raw rewards, empirical variances are large (>1> 1), placing the problem in a high-variance regime where UCB1 outperforms UCB-V2, which over-explores. After normalization, variances are reduced by a factor of 25 and UCB-V2 becomes competitive.

In both cases, UCB-minV2 identifies the prevailing regime and tracks the better base algorithm throughout the horizon, confirming the robustness of the per-arm minimum rule.

Normalization does not improve the best achievable cumulative regret either. It is thus not a straightforward remedy to variance heterogeneity and, critically, requires knowing the reward upper bound in advance, which is unavailable online. Upper Bound Reward Effect: Figures 8a-8b compare the effect of the support bound bb on MovieLens regret: b=1b = 1 (used throughout) vs. b=5b = 5 (the true support [0,5][0, 5]). With b=1b = 1, UCB1 and UCB-minV2 reach substantially lower regret than UCB-V2, whose variance-dependent bonus already over-explores. With b=5b = 5, all bonuses grow proportionally and every method reaches near-linear regret, confirming that a large bb, even well-specified, penalizes all UCB-type algorithms alike, variance-aware or not, and motivating b=1b = 1 as a default. The minimum rule is especially useful here: even when bb underestimates the support, it picks the tighter per-arm bonus.

Conclusion

This paper studied exploration in bandits whose arms have different variance regimes. We showed that the scalarization step in multi-objective optimization can lead to different variance levels across arms, making the choice between variance-independent and variance-aware exploration both arm- and instance-dependent. Neither UCB1 nor UCB-V2 uniformly dominates the other: their relative performance depends on the variance regime, the covariance structure of the objectives, and the reward support bound. We proposed UCB-MIN, a per-arm adaptive meta-algorithm that selects, for each arm and at each round, the tighter of the two exploration bonuses. It requires no prior knowledge of the variance regime, no reward normalization, and is empirically robust to an underestimated reward bound. Experiments on synthetic data, an educational tutoring task, and two group recommendation benchmarks confirmed that it consistently tracks the best base algorithm across diverse variance regimes and datasets.

Future work includes characterizing when minimum-of-bounds meta-algorithms achieve best-of-both-worlds regret, in particular whether the guarantee holds at the standard c=1.2c = 1.2 of [9] and whether UCB-minV2’s strong empirical behavior admits a matching bound. Other directions include experiments with other weight vectors and more objectives on the real-world datasets.

Acknowledgment

This work was partly supported by DataGEMS, funded by the European Union’s Horizon Europe Research and Innovation Programme, under grant agreement number 101188416.

Generative AI tools were used for language editing and for suggesting related work, coding, and initial proof ideas; all technical content and results are the authors’ own.

[33] N. Korda, B. Szörényi, and S. Li, “Distributed clustering of linear bandits in peer to peer networks,” in Proceedings of the 33rd International Conference on Machine Learning, vol. 48. PMLR, 2016, pp. 1301–1309.

[34] K. Mahadik, Q. Wu, S. Li, and A. Sabne, “Fast distributed bandits for online recommendation systems,” in Proceedings of the 34th ACM International Conference on Supercomputing, 2020, pp. 4:1–4:13.

[35] Z. Wang, A. Lamb, E. Saveliev, P. Cameron, J. Zaykov et al., “Results and insights from diagnostic questions: The NeurIPS 2020 education challenge,” in NeurIPS 2020 Competition and Demonstration Track. PMLR, 2021, pp. 191–205.

[36] F. M. Harper and J. A. Konstan, “The MovieLens datasets: History and context,” ACM Transactions on Interactive Intelligent Systems, vol. 5, no. 4, pp. 19:1–19:19, 2015.

Appendix A: Proof of Theorem 1

Proof. Consider a UCB bandit π\pi with indexes Ba,s,tB_{a,s,t}, where Ba,s,tB_{a,s,t} is the index of arm aa at step tt when aa has been pulled ss times (here ss counts pulls, unrelated to the superscript (s)(s) of scalarized quantities), with a⋆a^\star an optimal arm and μ⋆\mu^\star its expected reward. The approach of [8], [16] to bound the expected regret R(T)R(T) of UCB1 (resp. UCB-V) is to decompose it as R(T)=∑aΔaE(Na(T))R(T)=\sum_a\Delta_a\mathbb{E}(N_a(T)). They bound E(Na(T))\mathbb{E}(N_a(T)) for suboptimal arms by noting that, under the UCB rule, arm aa is pulled at step tt only if its index is at least that of a⋆a^\star, which requires one of two “bad” events: (i) the index of aa is larger than μ⋆\mu^\star, or (ii) the index of a⋆a^\star is smaller than μ⋆\mu^\star. Fixing some value uu to be tuned later and bounding the probability of the two events for each step tt after aa has been pulled uu times, any UCB bandit π\pi must satisfy:

E(Na(T))≤u+∑t=u+1TP(∃u≤s≤t−1:Ba,s,t>μ⋆)+∑t=u+1TP(∃1≤s≤t−1:Ba⋆,s,t≤μ⋆)(8)\mathbb{E}(N_a(T)) \leq u+\sum_{t=u+1}^{T}\mathbb{P}\left(\exists u\leq s\leq t-1:B_{a,s,t}>\mu^\star\right) +\sum_{t=u+1}^{T}\mathbb{P}\left(\exists1\leq s\leq t-1:B_{a^\star,s,t}\leq\mu^\star\right) \tag*{(8)}

This equation appears in slightly different forms, each upper bounding every term of Eq. (8), in [16 Theorem 2] and [8 Proof of Theorem 1]; both papers bound the expected regret of UCB1 and UCB-V by bounding each term of the sum.

We will denote by ua(1)u_a^{(1)}, Ba,s,t(1)B_{a,s,t}^{(1)}, Ua(1)(T)U_a^{(1)}(T) the threshold value, index, and upper bound on E(Na(T))\mathbb{E}(N_a(T)) obtained in [8] for UCB1, and will use similarly ua(V)u_a^{(\mathrm{V})}, Ba,s,t(V)B_{a,s,t}^{(\mathrm{V})} and Ua(V)(T)U_a^{(\mathrm{V})}(T) for UCB-V, while the version without superscript will be used for UCB-minV1. So it suffices to prove that E(Na(T))≤Ua(1)(T)+Ua(V)(T)\mathbb{E}(N_a(T))\leq U_a^{(1)}(T)+U_a^{(\mathrm{V})}(T) to establish our regret bound for UCB-minV1 with c=1.2c=1.2.

ua(1)=⌈8b2log⁡T/Δa2⌉,u_a^{(1)}=\left\lceil8b^2\log T/\Delta_a^2\right\rceil,
ua(V)=⌈8(σa2Δa2+2bΔa)clog⁡T⌉.u_a^{(\mathrm{V})}=\left\lceil8\left(\frac{\sigma_a^2}{\Delta_a^2}+\frac{2b}{\Delta_a}\right)c\log T\right\rceil.

Furthermore by monotonicity of the left expression w.r.t. BB:

P(∃u≤s≤t−1:Ba,s,t>μ⋆)≤min⁡(P(∃u≤s≤t−1:Ba,s,t(1)>μ⋆),P(∃u≤s≤t−1:Ba,s,t(V)>μ⋆))(9)\mathbb{P}\left(\exists u\leq s\leq t-1:B_{a,s,t}>\mu^\star\right) \leq\min\left(\mathbb{P}\left(\exists u\leq s\leq t-1:B_{a,s,t}^{(1)}>\mu^\star\right), \mathbb{P}\left(\exists u\leq s\leq t-1:B_{a,s,t}^{(\mathrm{V})}>\mu^\star\right)\right) \tag*{(9)}

and by union bound

P(∃s≤t−1:Ba⋆,s,t≤μ⋆)≤P(∃s≤t−1:Ba⋆,s,t(1)≤μ⋆)+P(∃s≤t−1:Ba⋆,s,t(V)≤μ⋆)(10)\mathbb{P}\left(\exists s\leq t-1:B_{a^\star,s,t}\leq\mu^\star\right) \leq\mathbb{P}\left(\exists s\leq t-1:B_{a^\star,s,t}^{(1)}\leq\mu^\star\right) +\mathbb{P}\left(\exists s\leq t-1:B_{a^\star,s,t}^{(\mathrm{V})}\leq\mu^\star\right) \tag*{(10)}

Since [8] and [16] obtain their bound by bounding all the probabilities appearing in the sums for their respective choice of uu, combining Equations (8), (9) and (10) with u=max⁡(ua(1),ua(V))u=\max(u_a^{(1)},u_a^{(V)}) yields a sum whose terms all appear in the corresponding sums for UCB1 or UCB-V. The expected number of pulls of suboptimal arms in UCB-minV1, hence its expected regret, is therefore at most the sum of those for UCB1 and UCB-V, which gives the result for c=1.2c=1.2 in the Theorem.

For the tighter result, we prove that for c≥4c\geq4 UCB-minV1 does not pull arm aa more than a few times above the best of the two bounds above, namely E(Na(T))≤min⁡(Ua(1)(T),Ua(V)(T))+O(1)\mathbb{E}(N_a(T))\leq\min(U_a^{(1)}(T),U_a^{(V)}(T))+O(1). We first bound by a constant the last sum in Eq. (8), then bound the first two terms.

Recall from [8] that by Chernoff-Hoeffding, P(Ba⋆,s,t(1)≤μ⋆)≤t−4\mathbb{P}(B_{a^\star,s,t}^{(1)}\leq\mu^\star)\leq t^{-4} for all ss and tt. When c≥4c\geq4, the empirical Bernstein inequality [16], Eq. (7) of Theorem 1 provides a similar concentration bound for UCB-V, so we can assume P(Ba⋆,s,t(V)≤μ⋆)≤3t−4\mathbb{P}(B_{a^\star,s,t}^{(V)}\leq\mu^\star)\leq3t^{-4}. For any choice of uu, we next show that the last term of Eq. (8) is bounded by a constant. For all tt and ss, we have by union bound:

P(Ba⋆,s,t≤μ⋆)≤P(Ba⋆,s,t(1)≤μ⋆)+P(Ba⋆,s,t(V)≤μ⋆)≤4t−4.\mathbb{P}(B_{a^\star,s,t}\leq\mu^\star)\leq\mathbb{P}(B_{a^\star,s,t}^{(1)}\leq\mu^\star)+\mathbb{P}(B_{a^\star,s,t}^{(V)}\leq\mu^\star)\leq4t^{-4}.

Consequently and decomposing by union bound:

∑t=u+1TP(∃1≤s≤t−1:Ba⋆,s,t≤μ⋆)≤∑t=u+1T∑s=1t−1P(Ba⋆,s,t≤μ⋆)≤∑t=u+1T∑s=1t−14t−4\begin{aligned} \sum_{t=u+1}^{T}\mathbb{P}(\exists1\leq s\leq t-1:B_{a^\star,s,t}\leq\mu^\star) &\leq\sum_{t=u+1}^{T}\sum_{s=1}^{t-1}\mathbb{P}(B_{a^\star,s,t}\leq\mu^\star)\\ &\leq\sum_{t=u+1}^{T}\sum_{s=1}^{t-1}4t^{-4} \end{aligned}

This proves that

∑t=u+1TP(∃1≤s≤t−1:Ba⋆,s,t≤μ⋆)∈O(1)(11)\sum_{t=u+1}^{T}\mathbb{P}(\exists1\leq s\leq t-1:B_{a^\star,s,t}\leq\mu^\star)\in O(1) \tag*{(11)}

To fix a choice for uu, we compare the two bounds: if Ua(1)≤Ua(V)U_a^{(1)}\leq U_a^{(V)}, we set u=ua(1)u=u_a^{(1)}. Otherwise, we set u=ua(V)u=u_a^{(V)}. As we are only summing terms that appear in the smallest of the two bounds, possibly replacing some of these terms by smaller terms from the other bound (according to Eq. (9)),

u+∑t=u+1TP(∃u≤s≤t−1:Ba,s,t>μ⋆)≤min⁡(Ua(1),Ua(V))u+\sum_{t=u+1}^{T}\mathbb{P}(\exists u\leq s\leq t-1:B_{a,s,t}>\mu^\star)\leq\min(U_a^{(1)},U_a^{(V)})

Combining with Eq. (11), we deduce that

E(Na(T))≤min⁡(Ua(1)(T),Ua(V)(T))+O(1)\mathbb{E}(N_a(T))\leq\min(U_a^{(1)}(T),U_a^{(V)}(T))+O(1)

which concludes our proof of the tighter result in the Theorem, obtained for c≥4c\geq4.

Appendix B: Metrics description

a) Bandit performance:

  • Cumulative Regret, as defined in Eq. (3), measures decision suboptimality (lower is better).

b) Ranking and interaction: At round tt, let Lt=(a1,…,ak)\mathcal{L}_t=(a_1,\ldots,a_k) be the recommendation list (last kk recommendations) and S⊆AS\subseteq A the truly relevant arms (ground truth). For k∈{1,3,5}k\in\{1,3,5\} we define Precision@k =∣{a1,…,ak}∩S∣/k=|\{a_1,\ldots,a_k\}\cap S|/k and Hit Rate@k =1(∣{a1,…,ak}∩S∣>0)=\mathbf{1}(|\{a_1,\ldots,a_k\}\cap S|>0); the paper reports Hit Rate@1, the remaining values being available online.4 These assess whether relevant items appear among the last kk recommendations; we take SS as the top-MM arms by true scalar mean μa(s)\mu_a^{(s)}, with M=5M=5.

c) Engagement and domain: CTR =1T∑t=1T1{relt>0}=\frac{1}{T}\sum_{t=1}^{T}\mathbf{1}\{\mathrm{rel}_t>0\}, where relt\mathrm{rel}_t is the observed relevance of the recommended item at tt (higher is better); Skill progression (NCC): number of difficulty levels mastered, a level requiring NN consecutive correct responses (higher is better).

References

  1. [1]S. S. Villar, J. Bowden, and J. Wason, “Multi-armed bandit models for the optimal design of clinical trials: benefits and challenges,” Statistical Science, vol. 30, no. 2, pp. 199–215, 2015.
  2. [2]M. Aziz, E. Kaufmann, and M.-K. Riviere, “On multi-armed bandit designs for dose-finding clinical trials,” Journal of Machine Learning Research, vol. 22, no. 14, pp. 1–38, 2021.
  3. [3]L. Li, W. Chu, J. Langford, and R. E. Schapire, “A contextual-bandit approach to personalized news article recommendation,” in Proc. 19th Int. Conf. World Wide Web, 2010, pp. 661–670.DOI
  4. [4]N. Silva, H. Werneck, T. Silva, A. C. M. Pereira, and L. Rocha, “Multi-armed bandits in recommendation systems: A survey of the state-of-the-art and future directions,” Expert Systems with Applications, vol. 197, p. 116669, 2022.DOI
  5. [5]J. Zuo and C. Joe-Wong, “Combinatorial multi-armed bandits for resource allocation,” in 2021 55th Annual Conference on Information Sciences and Systems (CISS). IEEE, 2021, pp. 1–4.arxiv.org/abs/2105.04373
  6. [6]E. M. Schwartz, T. T. Bradlow, and P. S. Fader, “Customer acquisition via display advertising using multi-armed bandit experiments,” Marketing Science, vol. 36, no. 4, pp. 500–522, 2017.
  7. [7]D. Bouneffouf and I. Rish, “A survey on practical applications of multi-armed and contextual bandits,” arXiv preprint arXiv:1904.10040, 2019.arxiv.org/abs/1904.10040
  8. [8]P. Auer, N. Cesa-Bianchi, and P. Fischer, “Finite-time analysis of the multiarmed bandit problem,” Mach. Learn., vol. 47, no. 2–3, pp. 235–256, 2002.DOI
  9. [9]J.-Y. Audibert, R. Munos, and C. Szepesvári, “Tuning bandit algorithms in stochastic environments,” in Proc. Int. Conf. Algorithmic Learn. Theory. Springer, 2007, pp. 150–165.DOI
  10. [10]Y. Fan, Y. Han, J. Lv, X. Xu, and Z. Zhou, “Precise asymptotics and refined regret of variance-aware UCB,” in Adv. Neural Inf. Process. Syst., vol. 38, 2025, pp. 160795–160837.DOI
  11. [11]A. Lacerda, “Multi-objective ranked bandits for recommender systems,” Neurocomputing, vol. 246, pp. 12–24, 2017.DOI
  12. [12]Y. Zhao, Y. Wang, Y. Liu, X. Cheng, C. C. Aggarwal, and T. Derr, “Fairness and diversity in recommender systems: a survey,” ACM Trans. Intell. Syst. Technol., vol. 16, no. 1, pp. 1–28, 2025.arxiv.org/abs/2307.04644
  13. [13]R. Mehrotra, N. Xue, and M. Lalmas, “Bandit based optimization of multiple objectives on a music streaming platform,” in Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining, 2020, pp. 3224–3233.DOI
  14. [14]N. Bouraour, I. Benouaret, and S. Amer-Yahia, “Multi-objective test recommendation for adaptive learning,” in Trans. Large-Scale Data- Knowl.-Centered Syst. LVI. Springer, 2024, pp. 1–36.
  15. [15]S. Amer-Yahia, S. Basu Roy, A. Chawla, G. Das, and C. Yu, “Group recommendation: Semantics and efficiency,” Proc. VLDB Endow., vol. 2, no. 1, pp. 754–765, 2009.
  16. [16]J.-Y. Audibert, R. Munos, and C. Szepesvári, “Exploration–exploitation tradeoff using variance estimates in multi-armed bandits,” Theor. Comput. Sci., vol. 410, no. 19, pp. 1876–1902, 2009.DOI
  17. [17]M. M. Drugan and A. Nowé, “Designing multi-objective multi-armed bandits algorithms: A study,” in Proc. Int. Joint Conf. Neural Netw. IEEE, 2013, pp. 1–8.DOI
  18. [18]E. Turgay, D. Oner, and C. Tekin, “Multi-objective contextual bandit problem with similarity information,” in International Conference on Artificial Intelligence and Statistics. PMLR, 2018, pp. 1673–1681.arxiv.org/abs/1803.04015
  19. [19]W. R. Thompson, “On the likelihood that one unknown probability exceeds another in view of the evidence of two samples,” Biometrika, vol. 25, no. 3/4, pp. 285–294, 1933.DOI
  20. [20]S. Agrawal and N. Goyal, “Analysis of Thompson sampling for the multi-armed bandit problem,” in Proceedings of the 25th Annual Conference on Learning Theory (COLT), ser. JMLR Workshop and Conference Proceedings, vol. 23, 2012, pp. 39.1–39.26.arxiv.org/abs/1111.1797
  21. [21]A. Garivier and O. Cappé, “The KL-UCB algorithm for bounded stochastic bandits and beyond,” in Proc. 24th Annu. Conf. Learn. Theory. JMLR Workshop and Conference Proceedings, 2011, pp. 359–376.arxiv.org/abs/1102.2490
  22. [22]S. Mukherjee, K. Naveen, N. Sudarsanam, and B. Ravindran, “Efficient-UCBV: An almost optimal algorithm using variance estimates,” in Proc. AAAI Conf. Artif. Intell., vol. 32, no. 1, 2018.arxiv.org/abs/1711.03591
  23. [23]D. M. R. Roijers, P. Vamplew, S. Whiteson, and R. Dazeley, “A survey of multi-objective sequential decision-making,” Journal of Artificial Intelligence Research, vol. 48, pp. 67–113, 2013.
  24. [24]S. Q. Yahyaa, M. M. Drugan, and B. Mandaric, “Annealing-Pareto multi-objective multi-armed bandit algorithm,” in IEEE Symposium on Adaptive Dynamic Programming and Reinforcement Learning. IEEE, 2014, pp. 1–8.
  25. [25]R. Busa-Fekete, B. Szörényi, P. Weng, and S. Mannor, “Multi-objective bandits: Optimizing the generalized Gini index,” in International Conference on Machine Learning. PMLR, 2017, pp. 625–634.
  26. [26]U. Siddique, P. Weng, and M. Zimmer, “Learning fair policies in multi-objective (deep) reinforcement learning with average and discounted rewards,” in International Conference on Machine Learning. PMLR, 2020, pp. 8905–8915.DOI
  27. [27]A. Cutkosky, A. Das, and M. Purohit, “Upper confidence bounds for combining stochastic bandits,” arXiv preprint arXiv:2012.13115, 2020.
  28. [28]R. Arora, T. V. Marinov, and M. Mohri, “Corraling stochastic bandit algorithms,” in Proc. Int. Conf. Artif. Intell. Statist. PMLR, 2021, pp. 2116–2124.arxiv.org/abs/2006.09255
  29. [29]W. C. Cheung and L. Lyu, “Leveraging (Biased) information: Multi-armed bandits with offline data,” in Proc. 41st Int. Conf. Mach. Learn., vol. 235. PMLR, 2024, pp. 8286–8309.
  30. [30]V. Minh, “Efficient stopping rules,” Master’s thesis, University of Alberta, 2008.
  31. [31]C. Gentile, S. Li, and G. Zappella, “Online clustering of bandits,” in Proceedings of the 31st International Conference on Machine Learning, vol. 32. PMLR, 2014, pp. 757–765.arxiv.org/abs/1401.8257
  32. [32]S. Li, C. Gentile, A. Karatzoglou, and G. Zappella, “Data-dependent clustering in exploration-exploitation algorithms,” arXiv preprint arXiv:1502.03473, 2015.
  33. [33]N. Korda, B. Szörényi, and S. Li, “Distributed clustering of linear bandits in peer to peer networks,” in Proceedings of the 33rd International Conference on Machine Learning, vol. 48. PMLR, 2016, pp. 1301–1309.arxiv.org/abs/1604.07706
  34. [34]K. Mahadik, O. Wu, S. Li, and A. Sabne, “Fast distributed bandits for online recommendation systems,” in Proceedings of the 34th ACM International Conference on Supercomputing, 2020, pp. 4:1–4:13.arxiv.org/abs/2007.08061
  35. [35]Z. Wang, A. Lamb, E. Saveliev, P. Cameron, J. Zaykov et al., “Results and insights from diagnostic questions: The NeurIPS 2020 education challenge,” in NeurIPS 2020 Competition and Demonstration Track. PMLR, 2021, pp. 191–205.
  36. [36]F. M. Harper and J. A. Konstan, “The MovieLens datasets: History and context,” ACM Transactions on Interactive Intelligent Systems, vol. 5, no. 4, pp. 19:1–19:19, 2015.

Paper details

vlnc:W_9gtyrgmq
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 10

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Generative AI tools

View statement
Looking for related papers…
Contents