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 , 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:
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.
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.
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.
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 arms and objectives. At each round , the bandit algorithm selects an arm and observes a reward vector . For each arm , the rewards are i.i.d. with unknown mean vector and covariance matrix . Let be the number of times arm has been pulled up to time . The empirical estimators are, with the variance normalized by as in [16 Theorem 1]:
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 with and , the scalarized reward observed at round is . For each arm , the scalarized mean and variance are:
where the superscript marks scalarized quantities. After rounds, the empirical estimators are:
UCB Algorithms and Regret
The goal of bandit algorithms is to minimize the cumulative regret. Let , , and . The expected cumulative regret is:
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. denotes a pure exploration bonus and the corresponding full index; the algorithm pulls . This work builds upon well-known algorithms (presented below) which we apply to the scalarized multi-objective setting for rewards having support .
UCB1 [8]: UCB1 is variance-independent; its bonus and index are
achieving regret
When 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
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:
with and . Its regret bound [16 Theorem 4] is
which improves over UCB1 when per-arm variances are small relative to .
UCB-V2 [10]: UCB-V2, our name for the version of UCB-V analyzed in [10], refines UCB-V with the bonus
and , where is a tuning parameter ( in our experiments). When , , and for a universal constant , with probability at least , its regret scales as
where the arms are indexed so that the optimal arm .
Other Related Work
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 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 , 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 inflates all exploration bonuses and leads to near-linear regret (see Figure 8b).
Figure 7. Effect of normalization (a: raw rewards in , b: normalized to ) on MovieLens cumulative regret.
Figure 8. Effect of the support bound (a: , b: , 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 , is empirically robust to an underestimated , allowing the default 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 , horizon , weight vector
Initialize: : , ,
Pull each arm once.
for to do
for each do
Compute and (Eq. (2))
end for
Pull , observe , update , ,
end for
For each arm , we compute both the variance-independent bonus (Eq. (4)) and a variance-aware bonus (Eq. (5) or (6)), keep the tighter one, and add the empirical mean once:
Both forms coincide since 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 is misspecified: for a small (e.g., the default ), remains tight while the variance-aware bonus may still be inflated by large empirical variances. The selection also depends on the pull count : the variance-aware bonus carries an extra term that dominates in early iterations, so the minimum then falls back on , and the variance plays its role mainly once is large enough.
We consider two variants depending on the variance-aware base:
Both share the same structure, presented in Algorithm 1. At each round, we compute scalarized statistics and , evaluate both bonuses, and pull with 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 given the scalarized statistics. With a fixed weight vector , these statistics are the empirical mean and variance of the scalarized rewards observed on each arm, since
and can be updated online in time and memory per arm; maintaining the full covariance , at a cost of 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 , , and support bound . The statement holds for any bounded rewards, so we omit the superscript here and in the proof.
(i) For 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:
i.e. it is never worse than the better of the two on any arm.
(ii) At the standard [9], UCB-minV1 still enjoys the weaker guarantee of being bounded by the sum of the two base bounds:
We use in our experiments, the value fixed by [9], at which only part (ii) is proved; a larger 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 , 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 arms and independent Gaussian objectives, with means in and standard deviations in . 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 based on global success rate; each student’s proficiency is the highest level with correct answers. Arms correspond to the difficulty levels. Following [14], pulling arm (level ) for a student at level yields the following reward components that all lie in :
Aptitude (A): : a binary reward indicating correct/incorrect answer.
Competence (C): (difficulty matching).
Performance (P): (potential progression).
Gap (G): (recovery from failure with 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 for group yields:
Relevance: for randomly sampled user .
Pairwise Disagreement: for sampled pair .
Disagreement is inverted to for maximization, where is the maximum rating of the dataset. Rewards lie in for MovieLens (not normalized) and 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@, assessing whether one of the last 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 ; 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 everywhere. This matches the true support for the educational and Steam data (rewards in ); 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 . 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 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 in this regime, 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 () and the other half have high variance (). 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.

Figure 1. Cumulative regret across variance regimes: (a) , (b) , (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 () and the other has high variance (). With (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 (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 (low variance), Dim 2 has (high variance).
Educational dataset (short horizon): For this dataset, matches the true support since all rewards lie in . Figure 4 reports both cumulative regret and the progression skill for (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 . 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.

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 (not normalized), so 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 (). 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).
| Algorithm | Low | High | Hetero. | A | A+P | A+C+G | ||
| UCB1 | 1005.5 | 1064 | 1373 | 38.0 | 21.1 | 37.8 | 234 | 1381 |
| UCB1-Normal | 271.7 | 4124 | 6490 | 7.4 | 18.4 | 19.9 | 450 | 638 |
| UCB-V | 776.9 | 3248 | 3729 | 67.3 | 25.3 | 46.9 | 908 | 1086 |
| UCB-V2 | 94.5 | 2323 | 851 | 38.4 | 20.4 | 37.7 | 406 | 613 |
| EUCBV | 172.9 | 1621 | 965 | - | - | - | - | - |
| UCB-minV1 | 742.0 | 969 | 1267 | - | - | - | - | - |
| UCB-minV2 | 92.6 | 958 | 799 | 38.2 | 20.4 | 37.7 | 233 | 612 |
Table 1. Final cumulative regret at the horizon 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 , , and . 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 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 and rewards normalized to by dividing by the maximum rating, with in both cases.
The two settings induce different variance regimes. With raw rewards, empirical variances are large (), 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 on MovieLens regret: (used throughout) vs. (the true support ). With , UCB1 and UCB-minV2 reach substantially lower regret than UCB-V2, whose variance-dependent bonus already over-explores. With , all bonuses grow proportionally and every method reaches near-linear regret, confirming that a large , even well-specified, penalizes all UCB-type algorithms alike, variance-aware or not, and motivating as a default. The minimum rule is especially useful here: even when 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 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 with indexes , where is the index of arm at step when has been pulled times (here counts pulls, unrelated to the superscript of scalarized quantities), with an optimal arm and its expected reward. The approach of [8], [16] to bound the expected regret of UCB1 (resp. UCB-V) is to decompose it as . They bound for suboptimal arms by noting that, under the UCB rule, arm is pulled at step only if its index is at least that of , which requires one of two “bad” events: (i) the index of is larger than , or (ii) the index of is smaller than . Fixing some value to be tuned later and bounding the probability of the two events for each step after has been pulled times, any UCB bandit must satisfy:
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 , , the threshold value, index, and upper bound on obtained in [8] for UCB1, and will use similarly , and for UCB-V, while the version without superscript will be used for UCB-minV1. So it suffices to prove that to establish our regret bound for UCB-minV1 with .
Furthermore by monotonicity of the left expression w.r.t. :
and by union bound
Since [8] and [16] obtain their bound by bounding all the probabilities appearing in the sums for their respective choice of , combining Equations (8), (9) and (10) with 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 in the Theorem.
For the tighter result, we prove that for UCB-minV1 does not pull arm more than a few times above the best of the two bounds above, namely . 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, for all and . When , the empirical Bernstein inequality [16], Eq. (7) of Theorem 1 provides a similar concentration bound for UCB-V, so we can assume . For any choice of , we next show that the last term of Eq. (8) is bounded by a constant. For all and , we have by union bound:
Consequently and decomposing by union bound:
This proves that
To fix a choice for , we compare the two bounds: if , we set . Otherwise, we set . 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)),
Combining with Eq. (11), we deduce that
which concludes our proof of the tighter result in the Theorem, obtained for .
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 , let be the recommendation list (last recommendations) and the truly relevant arms (ground truth). For we define Precision@k and Hit Rate@k ; the paper reports Hit Rate@1, the remaining values being available online.4 These assess whether relevant items appear among the last recommendations; we take as the top- arms by true scalar mean , with .
c) Engagement and domain: CTR , where is the observed relevance of the recommended item at (higher is better); Skill progression (NCC): number of difficulty levels mastered, a level requiring consecutive correct responses (higher is better).
References
- [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]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]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]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]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]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]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]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]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]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]A. Lacerda, “Multi-objective ranked bandits for recommender systems,” Neurocomputing, vol. 246, pp. 12–24, 2017.DOI
- [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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]A. Cutkosky, A. Das, and M. Purohit, “Upper confidence bounds for combining stochastic bandits,” arXiv preprint arXiv:2012.13115, 2020.
- [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]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]V. Minh, “Efficient stopping rules,” Master’s thesis, University of Alberta, 2008.
- [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]S. Li, C. Gentile, A. Karatzoglou, and G. Zappella, “Data-dependent clustering in exploration-exploitation algorithms,” arXiv preprint arXiv:1502.03473, 2015.
- [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]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]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.





