Balanced Sampling in Stochastic Multi-objective Bandits

Mengfan Xu

cs.LGOct 26, 2026

Balanced Sampling in Stochastic Multi-objective Bandits

Authors: Mengfan Xu

Organizations: Mechanical and Industrial Engineering, University of Massachusetts Amherst

Abstract

In stochastic multi-objective bandits, Pareto optimal arms may represent different trade-offs among objectives. Balanced sampling across them is important in practical settings such as online advertising. Yet, there seems to be little consensus on how to measure fairness, to our best knowledge. Achieving fairness is also tough as the set of Pareto optimal arms is unknown, and early sampling decisions may create imbalances that are difficult to erase afterwards. We measure unfairness by the KL divergence from the uniform distribution over the true Pareto set to the empirical measure induced by the sampling trajectory. Nicely, this measure admits an exact decomposition that separates the cost of sampling suboptimal arms from the imbalance among Pareto optimal arms. With a recursive form for unfairness, we develop adaptive top-two sampling, which combines sampling counts and empirical evidence of Pareto membership to define a gain for each arm and guide sampling without committing to an estimated Pareto set. When the Pareto set is stable under small perturbations, we establish an $O(\log T/T)$ and $O(T^{-1})$ bound on expected unfairness and variance, respectively. Information-theoretic lower bounds show that the $\log T/T$ rate can be unavoidable for uniformly fair policies on stable instances, matching our upper bound. More surprisingly, stability is indeed crucial, as the expected unfairness can be $ω(\log T/T)$ without it. Finally, we create a variant that encourages exploration of undersampled arms to reduce the risk of persistent underallocation. At sufficiently large horizons, it preserves the rate on the expected unfairness while admitting a sharper bound of $O(\log^2 T/T^2)$ on variance. Numerical studies support these findings and suggest practical insights.

Figures & tables

Horizon $T=5,000$
	$\eta_{\mu}=0.005$		$\eta_{\mu}=0.01$		$\eta_{\mu}=0.1$
Method	Mean	Variance	Mean	Variance	Mean	Variance
ATT (mean+SD BO)	$0.3655$	$0.0042$	$0.3041$	$0.0090$	$0.0246$	$0.0028$
ATT (log BO)	$\bm{0.3651}$	$0.0043$	$0.3099$	$0.0048$	$0.0246$	$0.0028$
EG-ATT (mean+SD BO)	$0.3719$	$0.0014$	$\bm{0.3020}$	$0.0100$	$0.0227$	$6.55\times 10^{-5}$
EG-ATT (log BO)	$0.4048$	$\bm{2.70\times 10^{-6}}$	$0.4053$	$\bm{7.50\times 10^{-10}}$	$0.2650$	$\bm{1.92\times 10^{-14}}$

Table 1: Mean and variance of terminal KL unfairness on Bernoulli rewards for

T\in\{5{,}000,50{,}000\}

. The smallest mean and variance for each separation margin and horizon are in bold.

Horizon $T=5,000$
	$\eta_{\mu}=0.005$		$\eta_{\mu}=0.02$		$\eta_{\mu}=0.1$
Method	Mean	Variance	Mean	Variance	Mean	Variance
ATT (mean+SD BO)	$0.3188$	$0.0098$	$0.0516$	$0.0123$	$\bm{0.0018}$	$1.94\times 10^{-6}$
ATT (log BO)	$0.3468$	$0.0078$	$0.0516$	$0.0123$	$0.0026$	$1.12\times 10^{-6}$
EG-ATT (mean+SD BO)	$\bm{0.2826}$	$0.0196$	$\bm{0.0390}$	$0.0020$	$0.0072$	$\bm{<10^{-15}}$
EG-ATT (log BO)	$0.4923$	$\bm{4.89\times 10^{-5}}$	$0.2196$	$\bm{6.07\times 10^{-15}}$	$0.0072$	$2.19\times 10^{-9}$

Table 2: Mean and variance of terminal KL unfairness on Gaussian rewards for

T\in\{5{,}000,50{,}000\}

. The smallest mean and variance for each separation margin and horizon are in bold.

Appendix figures & tables4 assets

Supplementary material from the paper’s appendix.

Appendix

Arm	$\eta_{\mu}=0.005$	$\eta_{\mu}=0.01$	$\eta_{\mu}=0.1$
1	$(0.525,0.5)$	$(0.55,0.5)$	$(0.6,0.1)$
2	$(0.515,0.505)$	$(0.53,0.51)$	$(0.4,0.2)$
3	$(0.51,0.52)$	$(0.52,0.54)$	$(0.3,0.5)$
4	$(0.5,0.535)$	$(0.5,0.57)$	$(0.1,0.8)$
5	$(0.505,0.505)$	$(0.51,0.51)$	$(0.2,0.2)$
6	$(0.5,0.5)$	$(0.5,0.5)$	$(0.1,0.1)$

Appendix

Table 3: Mean reward vectors for the bernoulli instances.

Arm	$\eta_{\mu}=0.005$	$\eta_{\mu}=0.02$	$\eta_{\mu}=0.1$
1	$(0.5425,0.53)$	$(0.67,0.62)$	$(0.8,0.55)$
2	$(0.53,0.5425)$	$(0.62,0.67)$	$(0.55,0.8)$
3	$(0.535,0.535)$	$(0.64,0.64)$	$(0.65,0.65)$
4	$(0.5275,0.5275)$	$(0.61,0.61)$	$(0.5,0.5)$
5	$(0.525,0.535)$	$(0.6,0.64)$	$(0.45,0.65)$

Appendix

Table 4: Mean reward vectors for the gaussian instances.

$\eta_{\mu}$	$T$	Method	BO	$\bm{\theta}$	$\bm{\omega}$	Mean	Variance
0.005	5,000	ATT	M	$(2.87,0.658,0.010,0.155,0.452,0.994)$	–	$0.3655$	$0.004249$
0.005	5,000	ATT	L	$(2.88,0.597,0.200,0.669,0.317,0.994)$	–	$0.3651$	$0.004257$
0.005	5,000	EG-ATT	M	$(2.90,0.589,0.267,0.523,0.325,0.994)$	$(107.52,0.552,0.494,9.67)$	$0.3719$	$0.001447$
0.005	5,000	EG-ATT	L	$(1.88,0.581,0.028,0.189,0.414,0.912)$	$(155.33,0.762,0.673,8.62)$	$0.4048$	$2.7\times 10^{-6}$
0.005	50,000	ATT	M	$(1.57,0.578,0.280,0.026,0.482,0.920)$	–	$0.2495$	$0.01683$
0.005	50,000	ATT	L	$(3.00,0.801,0.266,0.116,0.507,0.936)$	–	$0.2758$	$0.004433$

Appendix

Table 5: Selected BO parameters and held-out unfairness for Bernoulli rewards. M denotes mean+SD tuning; L denotes log-scale tuning.

$\eta_{\mu}$	$T$	Method	BO	$\bm{\theta}$	$\bm{\omega}$	Mean	Variance
0.005	5,000	ATT	M	$(2.20,0.586,0.221,0.080,0.460,0.915)$	–	$0.3188$	$0.009786$
0.005	5,000	ATT	L	$(2.92,0.560,0.446,0.580,0.307,0.993)$	–	$0.3468$	$0.007814$
0.005	5,000	EG-ATT	M	$(0.758,0.813,0.068,0.351,0.450,0.921)$	$(42.86,0.943,0.004,6.00)$	$0.2826$	$0.01957$
0.005	5,000	EG-ATT	L	$(2.05,0.662,0.389,0.172,0.386,0.922)$	$(155.36,0.580,0.806,8.67)$	$0.4923$	$4.89\times 10^{-5}$
0.005	50,000	ATT	M	$(1.00,0.700,0.250,0.150,0.450,0.950)$	–	$0.07131$	$0.0168$
0.005	50,000	ATT	L	$(1.80,0.697,0.270,0.036,0.440,0.939)$	–	$0.09463$	$0.001683$

Appendix

Table 6: Selected BO parameters and held-out unfairness for Gaussian rewards. M denotes mean+SD tuning; L denotes log-scale tuning.

Multi-Armed Bandits

Multi-Armed Bandits study how to choose among uncertain actions over time while balancing immediate rewards with learning.

See all 352 papers

Apr 8, 2026

Are Stochastic Multi-objective Bandits Harder than Single-objective Bandits?

Multi-objective bandits have attracted increasing attention for their broad applicability, with

d

-dimensional reward vectors inducing Pareto regret. There has been a subtle debate over whether this added structure makes the problem fundamentally harder than single-objective bandits. We answer this by showing that, in terms of Pareto regret, it is surprisingly no harder: Pareto regret scales inversely with

g^\dagger

, the largest objective-wise suboptimality gap, and thus matches the smallest objective-wise classical regret. We formalize this idea via a novel method with upper and lower confidence-bound estimators for every arm-objective pair. It uses top-two races to compare arms within each objective and an uncertainty-greedy rule to allocate exploration toward the largest objective-wise gap

g^\dagger

, until the corresponding Pareto-optimal arm is committed to. We prove that it achieves Pareto regret of

O(\nicefrac{\log T}{g^\dagger})

, where

T

is the horizon, with \emph{no dependence on

d

}. A matching lower bound of

Ω(\nicefrac{\log T}{g^\dagger})

implies optimality. We evaluate the method on synthetic and real-world datasets, confirming the theory and achieving order-of-magnitude reductions in Pareto regret over baselines. Real-world results further show that our method commits to a Pareto optimal arm, possibly at the cost of empirical fairness, suggesting a potential hardness absent in single-objective bandits.

Changkun Guan, Mengfan Xu

H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology · Mechanical and Industrial Engineering, University of Massachusetts Amherst

Multi-Armed Bandits

Ask PDF

May 20, 2026

SURF: Steering the Scalarization Weight to Uniformly Traverse the Pareto Front

Scalarization is widely used in multi-objective optimization owing to its simplicity and scalability. In many applications, the goal is to generate solutions that represent diverse user preferences, ideally with uniform coverage of the Pareto front (PF). However, uniformly sampling scalarization weights usually induces non-uniform coverage of the PF. We explain this mismatch through the geometry of the scalarization path. As the weight varies, the corresponding solutions traverse the PF at a generally nonuniform speed. Integrating this speed gives cumulative arc length. After normalization by the total length, it defines a cumulative distribution function (CDF) on weights whose inverse selects points at equal arc-length intervals. Building on this insight, we propose SURF (Sampling Uniformly along the Pareto Front). For structured problems, including bi-objective bandits, we derive analytical expressions for this CDF map and the resulting PF-aware weight sampling rule. For general problems, SURF alternates between CDF reconstruction and weight sampling. Theoretically, we show that under provable conditions for bi-objective LS, SURF's CDF reconstruction error converges linearly to an

O(N^{-2})

discretization floor. Empirically, experiments on bandits, multi-objective-gymnasium, and multi-objective LLM alignment demonstrate that SURF efficiently achieves more uniform PF coverage than baselines.

Liuyuan Jiang, Chentong Huang, Lisha Chen

Department of Electrical and Computer Engineering University of Rochester, Rochester, NY 14627

Adaptive Sampling Multi-Objective Optimization Pareto Optimization

Ask PDF

May 7, 2026

Multi-Objective Multi-Agent Bandits: From Learning Efficiency to Fairness Optimization

We study multi-objective multi-agent multi-armed bandits (MO-MA-MAB) under stochastic rewards, where agents observe heterogeneous reward vectors and communicate over time-varying graphs. We formulate this emerging problem setting to address efficient learning, measured by Pareto regret, and incorporate fair learning as an additional goal, captured via social welfare. To measure efficiency, we formulate Pareto regret and develop Pareto UCB1 Gossip, whose novel exploration radius explicitly separates statistical uncertainty in Pareto-based inference from consensus error. To express the fairness constraint, we formulate a Nash Social Welfare objective over preference-scalarized rewards and propose Simulated NSW UCB Gossip, which integrates preference-based reward simulation, gossip-based utility estimation, and UCB-style exploration. We prove that Pareto UCB1 Gossip achieves

\mathcal{O}(\log T)

regret and an instance-independent rate of

\mathcal{O}(\sqrt{T})

, while Simulated NSW UCB Gossip achieves an instance-independent regret bound of

\mathcal{O}(T^{3/4})

. This separation reveals the cost of imposing the fairness constraint to our efficiency objective: fairness limits information aggregation and slows convergence. Experiments show that our methods consistently outperform baselines, improving performance by approximately

100\%

and

50\%

in the efficiency and fairness settings, respectively.

John Wang, Mengfan Xu

University of Massachusetts Amherst

Multi-Armed Bandits Multi-Agent System Optimization Multi-Agent Bandits Algorithmic Fairness Multi-Objective Optimization Social Welfare Maximization

Ask PDF

Abstract

Multi-Armed Bandits

Explore similar work

Are Stochastic Multi-objective Bandits Harder than Single-objective Bandits?

SURF: Steering the Scalarization Weight to Uniformly Traverse the Pareto Front

Multi-Objective Multi-Agent Bandits: From Learning Efficiency to Fairness Optimization