Pareto Optimal Risk-Agnostic Distributional Bandits with Heavy-Tail Rewards
Authors: Kyungjae Lee
Dohyeong Kim
Taehyun Cho
Chaeyeon Kim
Yunkyung Ko
Seungyub Han
Seokhun Ju
Dohyeok Lee
Sungbin Lim
Venue: NeurIPS 2025 poster ()
Keywords: Multi-Objective Bandits
Bandits with Heavy-Tail Rewards
Robust Distribution Estimation
Primary area: theory
TL;DR: We propose DistLCB, a multi-risk bandit algorithm for heavy-tailed rewards that leverages Wasserstein-based confidence bounds to achieve Pareto-optimality and provable regret guarantees.

Abstract: This paper addresses the problem of multi-risk measure agnostic multi-armed bandits in heavy-tailed reward settings. 
We propose a framework that leverages novel deviation inequalities for the $1$-Wasserstein distance to construct confidence intervals for Lipschitz risk measures. 
The distributional LCB (DistLCB) algorithm is introduced, which achieves asymptotic optimality by deriving the first lower bounds for risk measure aware bandits with explicit sub-optimality gap dependencies.
The DistLCB is further extended to multi-risk objectives, which enables Pareto-optimal solutions that consider multiple aspects of reward distributions.
Additionally, we provide a regret analysis that includes both gap-dependent and gap-independent bounds for multi-risk settings. 
Experiments validate the effectiveness of the proposed methods in synthetic and real-world applications.

Pareto Optimal Risk Measure Agnostic Distributional Bandits with Heavy-Tail Rewards
Kyungjae Lee Dohyeong Kim?
Taehyun Cho Chaeyeon Kim Sungbin Lim
Yunkyung Ko
Seungyub Han?
Seokhun Ju Dohyeok Lee²
1.3
DDepartment of Statistics, Korea University *Department of Electrical and Computer Engineering, Scoul National University
LG AI Research
Abstract
This paper addresses the problem of multi-risk measure agnostic multi-armed bandits in heavy-tailed reward settings. We propose a framework that leverages novel deviation inequalities for the I-Wasserstein distance construct confidence intervals for Lipschitz risk measures. The distributional LCB (Distl.CB) algo- rithm is introduced, which achieves asymptotic optimality by deriving the first lower bounds for risk measure aware bandits with explicit sub-optimality gap dependencies. The DistLCB is further extended to multi-risk objectives, which enables Pareto-optimal solutions that consider multiple aspects of reward distribu- tions. Additionally, we provide regret analysis that includes both gap-dependent and gap-in -nddeeedeeneent bounds for multi-risk settings. Experiments validate the effectiveness of the proposed methods in synthetic and real- world applications.
1 Introduction
The mulli-armee bandit (MAB) framework provides fundamental model for sequential decision- making under uncertainty (1]. Traditional approaches in the MAB aim maximize expected rewards by balancing exploration and exploitation. These methods have found widespread applications in areas such as clinical trials or recommendation systems. However, they typically rely on the expected value as the sole performance criterion, which limits their ability capture other important properties of reward distributions. This limitation becomes critical in risk-sensitive applications where rare but high-impact outcomes play a central role, such as financial crashes or adverse medical events.
Risk measure aware bandit frameworks aim address this drawback by incorporating alternative metrics such as conditional value-at-risk (CVaR) 245 mean-variance [6 7]. spectral risk measures (SRM) [8, [9) and distortion risk measures (DRM) [0]. These methods allow decision-male makers to prioritize different parts of the reward distribution, such as the lower tail, and are better suited to applications requiring safety, robustness, or downside control. However, most existing methods focus on optimizing a single risk measure, which still leaves important aspects of uncertainty unaddressed.
account for multiple risk perspectives the same time. For example, a portfolio manager must consider both expected returns and downside risks. In clinical decision-making, treatment effectiveness must be weighed against the risk of side effects. A toy example in Figure Ia and Table Tb illustrates how different risk measures prioritize distinct distributional properties. In such cases, identifying single best action may not be appropriate. Instead, one must identify Pareto-optimal set of actions that are not dominated under any of the chosen risk measures.
Many practical problems require eecisionnmmkeer
"Contact: (kyungjae, je_le,, sungbin)@kkorea.cc.u CConesponding author.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Action
Mcan
CVaRo..
CVaRo.
Wang
P. Opt.
Action A
Density
0.04
Action
A
25.0
19.4
15.2
21.0
B
20.0
6.1
2.2
10.0
0.02
Action C
C
50.0
15.1
5.3
24.7
0.00
Opt. Act.
C
A
A
C
0
20
40
60
80
Reward
(a) Toy example of three actions.
Summary of risk values.
Figure 1: (a) Reward histograms for three actions. (b) Summary of associated risk values. CVaRo.s and CVaRo.s are Conditional Value-at-Risk measures at the 50% and 80% quantiles, respectively. Wang [1I] represents distortion risk measure with g p². Opt. Act. shows the optimal action for each metric. P. Opt. marks actions that are Pareto-optimal. Action B is strictly dominated under all risk measures and thus not Pareto-optimgs while Actions A and C are each optimal under different risk criteria, making both Pareto-optimal in the multi-ri mult sense.
growing body of work has begun to explore the estimation of multiple risk measures simultaneously. Notably, methods have been proposed for constructing confidence intervals for risk measure classes such as CVaR and distortion- based risks under bounded or sub-Gaussian noise [0] For example, Zhang and Ong [12] considered quantile estimation in sub-Gaussian settings, while Cassel al. [8] Tan et al. 19] Liang and Luo [10] derived confidence bounds for the Lipschitz risk class under light-tailed assumptions. These contributions lay groundwork for multi-risk optimization, but their applicability remains limited in heavy-tailed environments, which are commonly encountered in finance, healthcare, and other real-world domains [33 20
To address this gap, we propose a unified multi-risk bandit framework that remains effective under heavy-tailed reward distributions. While prior works have studied multi-risk optimization under light-tailed assumptions, to the best of our knowledge, this is the first framework that supports general Lipschitz risk measures in multi-risk bandit problems under heavy-tailed noise. At the core of approach is the median of empirical quantiles (MoEQ) estimator, which extends median-of-means techniques to quantile estimation. MoEQ enables robust estimation of distributional properties and supports a wide range of Lipschitz risk measures without requiring manual construction of risk -iec-spcc confidence intervals. Our contribution is summarized follows:
We propose median of quantile estimation under heavy-tailed noise and introduce bootstrap resampling to mitigate its computational inefficiencies.
We derive new deviation inequalities for the 1- I-Wasserstein distance, enabling the construction of confidence intervals for Lipschitz risk measures in heavy-tailed reward settings. This result extends recent works (9] 10
We introduce the distributional LCB (DistLCB) algorithm, which leverages MoEQ to provide regret guarantees across all Lipschitz risk measures. We further extend this a multi-risk variant and present the first regret bounds for multi-risk bandits under heavy-tailed rewards.
We also establish the explicit dependency of sub-optimality gaps in the asymptotic lower bounds for risk measure aware bandits with SRM and DRM. We derive both gap-dependent and gap- independent regret bounds for single and multi-rish objectives, confirming the optimality of our algorithms.
2
Related Work
risk measure aware bandit algorithms have been studied under various risk measures and distributional assumptions. Early works primarily focused on specific risk criteria such CVaR mean- vvrrinn under light-tailed rewards, yielding asymptotic problem-dependent regret bounds 2 3 23)
To generalize beyond single risk types, bandit algorithms for Lipschitz risk measures, including CVaR, spectral, and distortion-based risks, have been proposed, but remain limited to sub- sub-Gaussian
or bounded settings [8] In contrast, works addressing heavy-tailed rewards largely focus on
single-risk setting, such as the mean CVaR 294 4 5 with only Bhatt et al. (30) analyzing the
broader Lipschitz risk class under infinite variance regimes. Multi-risk formulations, which aim to
optimize multiple risk measures simuitancously, have been explored in light-tailed settings (31334].

---

References
Multi-Risk
Risk Type
Distribution
Lower Bound
3 7
21
X
CVaR
Light Tails
Asymptotic [22
8
Lipschitz Risk Class
Light Tails
29
X
Mean
Heavy Tails
4 1
CVaR
Heavy Tails
30
Lipschitz Risk Class Mean
Heavy Tails
Minimax
31
Light Tails
Ours
Lipschitz Risk Class
Heavy-tails
Asymptotic, Minimax
Table 1: Comparison of representative risk measure aware bandit algorithms. The Lipschitz risk class includes mean and CVaR. Heavy-tailed distributions include light-tailed ones. Multi-Rish indicates whether multiple risks are jointly optimized; Lower Bound indicates whether regret lower bounds are analyzed.
but remain undeveloped for general Lipschitz risks or heavy-tailed environments. We address this gap with unified framework for multi-risk optimization under heavy-taile rewards, enabled by the MoEQ estimator with exponential convergence guarantees. This landscape is summarized in Table I which categorizes existing methods by their support for multi-risk objectives, risk types, distributional assumptions, and lower bound analyses. A more detailed comparison with prior work provided in Appendix B
3 Preliminaries
In this section, we introduce the foundational concepts of risk measure aware bandit problems with heavy-tailed rewards, Lipschitz risk measures, and Wasserstein distance.
3.1 risk measure aware Bandits with Heavy-Tailed Rewards
Consider a set of K actions, A {1, 21...... _ K each associated with an unknown reward distri- butions, [JoJoEA At each time t, the learner chooses action At by following some policy me and observes a random reward XA, μAA for the selected action. In risk measure aware bandits, the objective is to minimize a risk measure aware criterion rather than focusing solely on expected rewards. risk measure p(X,.) evaluates the risk each action and captures aspects of the reward
distribution beyond the mean, such as variability or tail behavior. The cumulative regret of risk measure aware bandits (9] 30 is defined
R R
((XA.) - -(XA)))((Xa))))
(1)
where a, denotes the optimal action, i.e., p(X.)) problems maximize rewards, this paper sets the objective to minimize cumulative risk for risk-sensitive decision-makee makinn. We also consider the heavy-tail assumption on the reward distributions:
(ainaeAp(X..) While traditional bandit
Assumption 3.1 (Heavy-Tailed Distribution and Bounded p-th Moment). For each action E A.
assume that μa belongs to the heavy-tailed class H(p) for some p (1, defined as: H(p)
{u: Ex= X < }, where is finite constant.
This assumption reflects the presence of heavy-tailed distributions, such as Pareto, Fréchet, or Weibull, where moments higher than p does not exist, necessitating robust estimation methods 24 26
3.2 Lipschitz Risk Meausre
Risk measures quantify various aspects of uncertainty reward distributions. Denote the space of all random variables with a finite expectation L1. A risk measure p maps random variable in C1 to real number. To handle multi-risk settings, it is necessary to estimate class of risk measures rather than single measure. We consider Lipschitz continuous risk measure with respect to distance metric on L1, which provides a broad framework for multiple risks, as in Tan et al. [9]
Definition 3.2 (k Lipschitz. Risk Measure w.r.t Distance ID). A risk measure defined on random variables is said to k Lipschitz continuous with respect to distance TD on L, if there exists constant A > 0 s.t. for all X, Y Lt, lp(X) p(Y)) xID x J.Y).

---

Lipschitz risk measure is general class of risk meausures including CVaR, spectral risk measures (SRM), distortion risk measures (DRM), utility-based shortfall risk (UBSR), or certainty equivalent risk measure (CERM). See Appendix C for more details.
In analyzing Lipschitz risk measures, the choice of distance metric plays crucial role. Commonly used metrics such as f1, f2, fxo and the 1-Wasserstein distance have been primarily analyzed under
bounded support, sub-Gaussian, and sub-Exponential assumptions [21 9 10 30). In this paper, we focus on the I-Wasserstein distance, which has been less explored in heavy-tailed settings.
Definition 3.3 W--assesstein Distance). Let F and be cumulative distribution functions (CDFs) supported on R. and let F-1 and G denote their corresponding quantile functions (i.e., inverse CDFs). The 1- I-Wasserstein distance between F' and G is defined by
Ci( = f- F(x) G(x) = L. | (F'((1) - (1)
3.3 Multi-Risk Bandit Problems
In classical risk measure aware bandit problems, single risk measure evaluates actions but offers limited perspective on the reward distribution. Multi-risk bandit problems address this by considering number of Lipschitz risk measures, 2 P2, pr), with their corresponding Lipschitz constants K. == (M1, K2, ... ) to capture diverse risk characteristics such as variability and tail behavior. The objective is to identify the Pareto optimal set of actions, P., where action dominates
another across all risks 31 32 34). The dominance relationship is defined as follows:
Definition 3.4 (Dominance). Let u and v be a vector in R
u dominates v, u > o: For all d E [r]. Ud 2 ea and there exists at least one d' Ue Ut.
u is non-dominated by o, u A There exists a dimension d E [r] such that un >> Ud-
u is incomparable with v, u Neither
nor V > u.
Formally, the Pareto optimal set defined P, == {a A Va' AA fa), e(X.') e(xa))
To analyze the convergence rate to the Pareto optimal set, we barrow mathematical framework in Drugan and Nowe 311. The sub-optimality gap of arm a is defined as
Pareso
= inf( el <20
2(Xa) + +el @(X.), Va' PPP
(3)
where 1 denotes vector of ones. Note that if E P., then, A Pareto 0 holds. Then, the regret can be defined as
R
Pareto
A Pareto [Ta(.)].
(4)
aea
Multi-risk bandits are especially important in heavy-tailed settings, where multiple risk measures can highlight wide spectra of events more effectively.
4 Median of Empirical Quantiles for Heavy-Tailed Distribution
We introduce the median of empirical quantiles (MoEQ), robust method for estimating reward distributions heavy-tailed settings. From the definition of Lipschitz risk measures, the confidence interval depends on the distance between the empirical and true distributions. Constructing reliable confidence intervals under heavy-tailed distributions requires robust quantile estimation. MoEQ addresses this by ensuring stable estimates and allows accurate computation of various risk measures within the Lipschitz risk class. This approach has significant advantages for multi-risk bandits because it supports the evaluation of multiple risks simultaneously.
4.1 Median of Empirical Quantiles
Definition 4.1. Let X1, X2, Xx,, be independent and identically distributed random variables with a cumulative distribution function (CDF) F(r). Divide the n samples into & groups of size N = [n/k], indexed by j E f1....,ke .k.. If n is not divisible by k, the remaining = kN

---

samples are dropped. The empirical CDF and quantile function of the jth group is defined as
N
Σ 1[Xxs < < FNJ inf(x P5(x) v). E [0
(5)
N
The median of empirical quantiles (MoEQ) and its empirical CDF are defined as
N Σ
med, N (v) median (V) Fmnd M (x) _E(1...) .)
N xx
(i/N) < a²).
(6)
Remark 4.2 (Validity of MoEQ). We would like to note that F med.NN and Findd are valid quantile function and CDF (See Lemma E.1 Furthermore, F also can be represented as the median of
CDFs, i.e., F
med Fx.j(xr)) (See Lemma B.2 Hence, this MoEQ is in the
domain of general risk measure p. in other words, p p(Fmed,NV is well defined.
While MoEQ offers robustness by aggregating empirical quantiles and reducing the influence of outliers in heavy-tailed distributions, it has a computational drawback, mentioned in Bhatt et al. 30. that updating MoEQ requires new samples for the k groups. This dependency makes updates infeasible when fewer than l samples are collected, as balanced group sizes cannot be maintained. To address this issue, we propose a bootstrap resampling.
4.2 Bootstrap Resampling for Efficient Updates
Suppose we have n data points divided into l groups, with each group ideally containing N = |n/k] samples. If is not divisible by k the remainder r kN creates imbalance across groups. To address this, two bootstrap resampling approaches can be employed to ensure uniform group sizes while maintaining statistical properties.
Partial Bootstrap Augmentation. The first approach, named partial bootstrap augmentation, handles the imbalance by assigning the r remaining samples r groups. making them contain N + samples. For the remaining k r groups, one additional sample is drawn with replacement to bring them to N ++1 samples. After resampling, the empirical quantile function for each group, FN+1, is computed, and the median of these quantiles across all groups is obtained as
fPB.-1 (v).
pPB.-1 (v) := median FPB.-1 (v).
(E(1.n..)) .k) FN
Full Bootstrap Augmentation. The second approach, named full bootstrap, creates all groups by sampling N points with replacement from the original n samples. This method eliminates the need for handling remainders and ensures uniform group sizes across all k groups For & bootstrap datasets, the median of the quantile functions is defined as
PPB.-1 (v) = median F (E(1....)
BFB.-1 (y),
(8)
In summary, we introduce two approaches for balancing group sizes: partial bootstrap augmentation redistributes remainders and resamples for balance, while full bootstrap creates uniform groups by resampling with replacement. Partial bootstrap is preferred requires only one bootstrap sample per group, whereas full bootstrap demands a larger resample size to ensure convergence rates, which will be analyzed the following section.
4.3 Deviation Inequality of MoEQQ
To analyze the deviation inequalities for MoEQ, partial bootstrap MoEQ (PB-MoEQ), and full bootstrap MoEQ (FB-MoEQ), we assume the stability of the underlying distribution. Specifically, the empirical measure ft... constructed from n i.i.d. samples, concentrates around the true distribution j under given distance metric D. This stability assumption, formalized below, provides the basis for deriving deviation bounds for the three methods.
Assumption 4.3 (Stability). Assume that E H(p) satisfies the following concentration inequality. Specifically, there exists a distance D and constant Cp > O, which is only dependent on p. such that for any N and any 0,
P (D((n. > x) S Cp/(n x²))
(9)
See Appendix for examples of distributions and metrics that satisfy this assumption.
5

---

This assumption enables us to quantify the deviation bounds for MoEQ under heavy-tailed settings. Theorem 4,4, Let Assumptions 3.7 and 4.3 hold for some p E (1,2), and let F(x) denote the CDF of the distribution with i.dd. samples. Consider the MoEQ estimator F and its empirical distribution F Fmed,N. Define k 18in(e1/8/85 and N = |n/k]. Then, with probability at least 1 - 6,
D' (fmed.,,,) F) S Sp,n(0), [((Fmad.x) - p(F) s (8),
(10)
where (p) = (4C,Up) (161n (c1/8/8) /m)
1-1/1
Proof can be found in Appendix E.1.1 Theorem 4.4 holds for any distance D satisfying Assumption
4.3
Importantly, the application to the Wi under heavy-tailed distributions is notable distinction, as
shown in the following corollary.
Corollary 4.5 (Confidence Intervals for MoEQ Variants), Under the same assumptions as Theorem
4.4 the following confidence intervals hold with probability at least 1 - 6:
Wi (F.F) S 3(5),
(o(F) p(F) s kB(6),
(11)
where F. and B(8) depend on the variant as follows.
For MoEQ. F- F medd,N, B(6) pp (6) defined in Theorem 4.4
For PB-MoEQ, F = Fird. N+1 B(6) = 8 (6) = (C//,,) (op.c()))) where C2 =2 + 2
For FB-MoEQ, = FFB.
Mo ((6) = Pp (8) = (r/ assuming N 2
In(32n1/2. ((8,) Mr) and k 2 (1)(1
Proof can be found in Appendix E.1.2 Our results derive deviation inequalities and confidence intervals for W1 under heavy-tailed distributions, covering 1 < p S 2 without boundedness or finite variance assumptions. This broadens applicability to the widest class of distributions.
Remark 4.6 (Comparisons with Prior Work on Deviation Inequalities of W1). First, bounded distribu- tions have been studied extensively in the context of risk measure aware bandits. Tamkin et al. [21) and Liang and Luo [10 used the Dvoretzky- Manrezzk-KKefer--- Wolfowitz (DKW) inequality to derive deviation inequalities for &oo and WT, establishing these metrics as suitable for Lipschitz risk measures in bounded support settings. However, the DKW inequality is insufficient for unbounded distributions. To address unbounded support, Tan et al. [9] extended the analysis to sub-Gaussian, sub-F Exponentian, and finite variance (p = 2) distributions, deriving deviation inequalities for W1- Yet, their approach does not cover the cases of infinite variance (p E (1, 2]), leaving gap in the thcoretical understanding of heavy-tailed distributions. Bhatt al. (30] proposed truncated empirical distribution (TED) framework for E (1, 2] but did not address deviation inequalities for W,. To fill this gap and com- pare TED with MoEQ, we manually derived deviation inequalities, showing that the bounds of TED scale as (1-))), which is less tight than MoEQ (see Appendix Ib. Our analysis extends these results by enabling SRM, DRM, UBSR, and CERM to be applied under heavy-tailed distributions, advancing the theoretical framework for Lipschitz risk measures in broader contexts.
5 Risk Measure Agnostic Distributional Bandits with Heavy-Tails
We begin with the single-risk setting, where MoEQ is used to estimate the reward distribution for each action. For an action a, the MoEQ at round is denoted as (t.Ta(t-1), based on T, 1) observations, which represents the total number of times action a has been chosen up to round t 1. This single-risk algorithm will be further extended the multi-risk setting, where multiple risk measures & are estimated for each action.
5.1 Risk Measure Agnostic Distributional Lower Confidence Bounds with MoEQ
We present a distributional lower confidence bounds (DistLCB) algorithm. Using the deviation inequality and confidence interval derived for MoEQ in Theorem 4.4 the learner computes the following LCB index for each action:
LCB.(t) pl p(xa.T..t-15)) 12) r=Bp,r,((-1)(66))
(12)

---

where TT, (t-1)) is the risk measure applied to the MoEQ estimate, and (t-)(()-1)(6)) is the confidence width determined by Theorem 4.4 The confidence width depends on the number of observations (t- 1), the tail parameter p. and the confidence level o, At each time step i, the learner selects the action A, with the lowest LCB index: A, = arg aA I.C This approach uses MoEQ's s robustness to estimate heavy-tailed rewards and balance exploration and exploitation with risk measure aware confidence intervals. Detail algorithm is described in Appendix F
5.2 Multi-Risk DistI CB with MoEQ
The multi-risk setting extends the DistLCB to multi-risk distributional LCB (MR-Distl CC)) to handle multiple risk measures @ by leveraging the robustness of the MoEQ for all Lpschitz risk measures. For each action the learner computes r-dimensional LCB indices similarly to (12) At each time step I, the learner estimates the Pareto optimal set P.,, r by checking dominance relationships among actions based on LCB indices. An action selected uniformly at random from P.,,, its reward is observed, and the estimates are updated. This extension is possible because our derived results apply to all Lipschitz risk measures and are the first to address 1- I-Wasserstein distance under heavy-tailed settings. Detail algorithm is described in Appendix
6 Regret Analysis
In this section, we analyze the regret bounds of two algorithms: DistLCB and MR-DistLCB, We provide both asymptotic lower bounds and regret bounds for these algorithms under heavy-tailed reward distributions. To analyze asymptotic optimality, we first derive the asymptotic and minimax lower bounds of SRM and DRM.
6.1 Lower Bounds of Risk Measure Aware Bandits with Heavy-Tailed Rewards
Theorem 6.1 (Asymptotic Lower Bound for SRM and DRM). For any C E (0, 1/4), let X1 and X2 be Bernoulli random variables supported on {0, 1/7,, where y (2c)1/(-1)) Their distributions are defined as pl == (1 + 07 - 60 + (T2 07)81/7 and (12 == (1 - 76) + y 1/81/7 where ōR denotes a point mass at x. For this Bernoulli bandit problem, the p-th moments satisfy U/ Consider SRM and DRM as risk measure and the sub-optimality gap of the second arm is DG =
p(X2)= p(Xi). Then, for any algorithm satisfying [T)) o(n²) for a > O, the regret satisfies
lim inf (n() 2 2 (1/(A2)
Proof Sketch. Proof can be found Appendix G.I.I To derive the asymptotic lower bounds, we construct two Bernoulli random variables X, and X₂ to satisfy V/p 1. By using specific properties of SRM and DRM, we compute the sub-optimality gap A2 explicitly, showing AS 2 2(c) for both SRM and DRM. Finally, by employing the generic lower bound of bandits, in Bubeck et al.
244, Lattimore and Szepesvári [35), and explicitly deriving the KL divergence DKI, X,) S
(ce ), we establish the asymptotic regret bound as / DKL X1) 2 Ω (1/(Ag) 1/6
demonstrating the dependency on the sub-optimality gap and the heavy-tail parameter p.
Remark 6.2 (Comparison with Prior Work on Asymptotic Lower Bounds). Theorem 6._ presents a novel asymptotic lower bound for regret in risk measure aware bandit problems under SRM and
DRM. By extending the approach of Baudry et al. 22), which builds on the generic lower bound from
Lai and Robbins (36), we generalize their CVaR-specine establish that the dependency of the sub-optimality gap AG follows the order 1/(p 1), providing broader theoretical foundation for regret bounds in risk measure aware bandits. Moreover, the dependency on A matches the results for expectation-basee bandits with heavy-tailed rewards (24)
results to SRM and DRM. Additionally, we
This similarity is natural since expectation is an SRM.
Theorem 6.3 (Minimax Lower Bound for SRM and DRM). Let K > 1 and n 2 K - 1. Consider SRM and DRM as a risk measure. For any policy, there exists a K-armed Bernoulli bandit problem such that Re, 2 Q((K- - -1)² 1)1 1))p-//p"///) holds.
Proof can found in Appendix G.1.2 The proof strategy is similar to that of Theorem 6.1 Note
that, if we set expectation risk measure, the minimax lower bound of SRM (or DRM) matches
7

---

that of expectation based bandits, scaling as S2(K' /P)
24 Furthermore, this result is also
consistent with the minimax lower bound derived in Bhatt et 30
Remark 6.4 (Limitations). A limitation of Theorem 6.1 [ and 6.3 lies in its focus on SRM and DRM. The proof leverages specific properties of SRM and DRM, making it inapplicable to other risk measures such as UBSR and CERM. As a result, this work does not provide a generalized lower bound for all Lipschitz risk measures. Extending the analysis to include broader class of risk measures remains an open problem and an important direction for future research.
6.2 Optimality of DistLCB
To establish the optimality of the DistLCB algorithm, we analyze its regret bounds under heavy-tailed reward distributions and Lipschitz risk measures.
Theorem 6.5. Consider a K -aareed stochastic bandit problem with a k. Lipschitz risk measure W.E.. W1 under Assumption 3.1 At each time t, define the number of groups in the MoEQ as kg = 18811 [8ln(c1/8(1)) Then, the expected regret R2, of the DistL.CB algorithm has the following
bounds,
Bound:
O
Σ kTCI
Cpplp A.
In(n))
a:
Indeenndeenndntt Bound: 0 (K(C)U))) (K In(n)) 1=1 n
Proof can be found in Appendix G.2 The proof can be done by applying analysis techniques of
UCB 24 to the confidence interval of MoEQ. This theorem establishes that the DistLCB achieves asymptotic optimality, with its gap-dependent regret matching the lower bound of Theorem 66. scaling as O (1/(Ag) (1/(Ag)1/6-1) 1/)-1)). Furthermore, the algorithm achieves near-minimax optimality up to logarithmic factor of n.
Remark 6.6 (Universality of DistI LCB Regret Bounds). This result demonstrates the universality of the regret bounds achieved by the DistLCB across various settings for Lipschitz risk measures and heavy- tailed rewards. For p = 2 case that includes bounded support, sub-Gaussian, and sub-Exuuo Feb--Expnnnntal distributions, the regret bounds recover all previous results on expectations [24 28 229,, CVaR-
based bandits 12] 77.. and Lipschitz risk bandits 88 30 This consistency highlights its ability to unify existing analyses across different risk measures and distributional assumptions. For p 2, which have infinite variance, the minimax regret bound aligns with the results Bhatt et al. [30] for Lipschitz risk bandits under heavy-taile distributions. Additionally, the gap-dependent regret bound presented here complements existing studies by providing refined guarantees for Lipschitz risk measures in heavy-tailed settings.
6.3 Regret Bounds of MR-DistLCB
Theorem 6.7. Consider a K-armed stochastic bandit problem with Lipschitz risk measures @ with vector of Lipschitz constants, K., under Assumption 3.1 At each time I, let hig [8 (81n(e2/ Kr(*)]. Then, the regret R Pareto satisfies the following bounds,
K. (CpUp) In(Krm)
Depe-deendent Bound:
Σ
(A [AParoto) p-r
GEAiP.
p-1 Ko (Cpup) (K In((rr))) F nd
Gap-Independent Bound:
where K. = max Kdd-
Proof is provided in Appendix G.3 Since MoEQ constructs confidence intervals for all Lipschitz risk measures, it naturally extends to multi-risk settings. The adaptability of MoBQ various Lipschitz risk measures builds upon techniques from Drugan and Nowe BI. For < < 2, our results provide the first regret bounds for multi-objective bandits under heavy-tailed rewards and MR-DistLCB enables decision-makinn
that considers diverse perspectives of reward distributions. Remark 6.8 (Comparisons with Multi-Objective Bandits). For p 2. the gap-dependent and gap- independent bounds align with Drugan and Nowe 31 and the extended results of Xu and Klabjan 34), matching the lower bounds ((In(z)) and ②( (R) respectively.
8

---

7 Numerical Experiments
Setup. We test our methods in synthetic and real-world multi-risk bandit settings with heavy-tailed rewards. We consider two settings: (1) Real-world portfolio selection, using daily returns from the top 20 S&P 500 stocks; and (2) Synthetic 20-armed Pareto bandits. In the real-world case, we evaluate 3-, 6-, and 9-risk settings with CVaR, Wang M. and CERM. Tail indices estimated via Hill's method range from p = 1.5 to 4.69, and we fix p = 1.5 for all algorithms. In the synthetic case, vary p E {1.01, 1.2, 1.5) to study the effect of tail heaviness, with 1.2 used as the baseline heavy-tail configuration. All experiments run for 10,000 steps and are repeated with 20 random seeds.
Additional setup details are provided in Appendix H
Comparison Methods. We compare against three baselines: (1) MR Trunc, a multi-risk adaptation
of the truncated empirical distribution (TED) method 330 (2) MR LCB, multi-risk extension
of LCB [9]. incorporating ideas from the multi multi-objective setting of [31]; and (3) SR DistLCB, single-risk version of our method used to assess the necessity of multi-risk exploration.
RorldWorld Results. As shown in Figure 2 MR DistLCB consistently outperforms all baselines across 3-, 6-, and 9-risk settings. This reflects its use of tight, distributionally robust confidence bounds and risk measure aware exploration. MR Trunc performs slightly worse due to its simplified truncation strategy (see Appendix D]. This supports the theoretical advantage of MR DistLCB in multi-risk settings, particularly complexity increases. As noted in Remark 4.6 baseline methods suffer from weaker deviation bounds, which slow convergence for distortion-basee risks like Wang and CERM. In contrast, MR DistLCB maintains stable risk estimation the number of risks grows. MR LCB performs the worst among multi-risk methods, as its nab-Gaussian assumptions lead to unstable or miscalibrated decisions. SR DistLCB performs poorly in the 3-risk case where the Pareto set is small, often failing to identify Pareto-optimal arms. Although its performance improves in 6- and 9-risk settings as the Pareto set expands, it still fails to match MR DistLCB. This confirms that single-risk methods do not suffice for multi-risk optimization.
Synthetic Results. Figure 3 compares cumulative Pareto regret across 3-, 6-, and 9-risk config- urations under different tail indices p. MR-DistLCB consistently achieves the lowest cumulative regret in all settings, while MR Trunc and MR LCB exhibit higher regret and larger variance. The MoEQ- aggregation enables robust estimation even when reward distributions have infinite variance, whereas truncation-bast based or Sab-Gassiinn methods degrade significantly under heavier tails.
Across tail indices p = 1.01, 1.2, 1.5, MR-DistLCB maintains the lowest mean regret and smallest standard deviation. For extremely heavy-tailed rewards (p 1.01), its performance advantage deviation bound
becomes most pronounced, highlighting the effectiveness of the exponential-ty in controlling uncertainty. As increases and the tails become lighter, all methods exhibit reduced variability, yet MR-DistLCB preserves its lead, demonstrating robustness to varying tail heaviness. MR Trunc remains limited by its conservative cutoff rule, and MR LCB continues to misestimate uncertainty under non-sub-Ga -n--su--Gaussian noise.
These results collectively confirm that MR-DistLCB achieves strong empirical robustness across diverse tail regimes. Even in the extreme heavy-tail setting (p = 1), it achieves substantially lower and more stable regret, consistent with the theoretical rates derived in Section 6. This stability across risk complexity and tail indices underscores the method's practical applicability in weal-world heavy-tailed domains such as finance and risk-aware decision-makinn
8 Conclusion
We introduce a Pareto-optimal multi-risk bandit framework under heavy-tailed rewards and derive deviation inequalities for the 1-Wasserstein distance, which enables confidence intervals for Lipschitz risk measures and the first lower bounds for risk measure aware bandits. The proposed MR-DistLCB algorithm achieves minimax-optimal regret bounds and outperforms truncation- based methods in real-world experiments. These results highlight the necessity of specialized multi-risk frameworks for decision-makinn under uncertainty. Although truncation-based methods show limitations in multi-risk settings, since we do not establish lower bounds for truncation- based LCBs, the possibility

---

(3 Risks)
Risks)
Risks)
DisucB
MIL DIALCH
Parete Rogret
GR etLCCs
MR Thint
Hill Trunc
Mr. LOS
MY. LCB
NR
300
X02
130
190
20
3003
1226
2000
2030
3000
520
3230
3265
1030
2030
300
223
3000
1200
2009
2700
3000
Timee step
Time stop
Timee step
Figure 2: Cumulative regret the real-world S&P 500 dataset. Solid/dotted lines show averages;
shaded areas denote standard deviations.
Ricks
3000
5002
5803
NR DistLCB
MR DisLUCB
MR DetucB
Pareto Regret
1000
HR LCB
7r.nc
4052
MR LCB
Pareto Regret
4803
MR LCB
Thunc
2003
Pareto
Step
Time Step
Step
(a) 3-risk (p = 1.01)
(b) 6-risk (p = 1.01)
(c) 9-risk (p = 1.01)
Risks
6 Risks
Risks
LCB MR Trun:
Pareto Regret
Nit Trunc
Pareto Regret
Trunc
Pareto Regret
3003
2000
Time
Time step
Time
(d) 3-risk (p = 1.2)
(c) 6-risk (p = 1.2)
(f) 9-risk (p = 1.2)
Risks
Risks
Risks
MBl DivilSs
HR DEALCS
MR WiDDet
Pareto Regret
4000
NR LCS
-002
Pareto Regret
4003
MR
Pareto
Time Step
Time Step
Step
(g) 3-risk (p = 1.5)
(h) 6-risk (p = 1.5)
(i) 9-risk (p = 1.5)
Figure 3: Cumulative regret on the synthetic 20-armed Pareto bandit across different numbers of risk measures (3, 6, 9) and tail indices Solid and dotted lines represent mean regret across runs, while shaded regions denote one standard deviation. As the tail index decreases (heavier tails), MR DistLCB maintains lower and more stable regret compared to MR Trunc and MR LCB.
of improvement remains open. Future research could investigate whether adaptive truncation or alternative refinements can enhance confidence intervals SRM and DRM, potentially addressing the observed limitations.
10

---

Acknowledgments
This work was partly supported by the National Research Foundation of Korea (NRF) grant funded by the Korea government (MSIT) (No.RS-20222 2022-NR088754, 25%) and (No.RS (-S-2023--0022 1357, Smart Assembler: Robot Active Learning for Unseen Parts Assembly, 25%) and (No.RS-2022 00410082, 25%) and (No. 000022233JA1106359999 and also supported by Institute of Information communications Technology Planning (valuation(IITP grant funded by the Korea government (MSITTXN0.222--0-0066 25%), and partly supported by Korea University Grant (K2512961).
References
[1] Peter Auer, Nicolò Cesa-Bianchi and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Mach. Learn., 47(2-3):235 256, 2002.
[2] Nicolas Galichet, Michele Sebag, and Olivier Teytaud. Exploration exploitation vs safety: Risk-aware multi-armed bandits. In Asian conference on machine learning, pages 245-260, 2013.
[3] Odalric-Ambrym Maillard. Robust risk-averse stochastic multi- bandits. In 24th Inter- national Conference on Algorithmic Learning Theory 2013., volume 8139, pages 213. Springer, October 2013.
[4] Anmol Kagrecha, Jayakrishnan Nair, and Krishna Jagannathan. Distribution oblivious, risk- aware algorithms for multi-armed bandits with unbounded rewards. 32th Annual Conference on Neural Information Processing Systems, December 2019.
[5] Prashanth L. A., Krishna P. Jagannathan, and Ravi Kumar Kolla. Concentration bounds for evar estimation: The cases of light-tailed and heavy-tailed distributions. In Proceedings of the 37th International Conference on Machine Learning, 13-18 July, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages 5577-5586. PMLR, 2020.
[6] Amir Sani, Alessandro Lazaric, and Rémi Munos. Risk-aversion in multi-armed bandits. In 26th Annual Conference on Neural Information Processing Systems, pages 3284-3292, 2012.
[7] Sattar Vakili and Qing Zhao, Mean-variance and value at risk multi-armed bandit problems. In 53rd Annual Allerton Conference on Communication, Control, and Computing, Allerton Park Retreat Center, Monticello, IL, USA, September 29 October 2, pages 1330-1335. IEEE, 2015.
[8] Asaf B. Cassel, Shie Mannor, and Assaf Zeevi. A general approach to multi multi-armed bandits under risk criteria. In Conference On Learning Theory, Stockholm, Sweden, 6-9 July, volume 75 of Proceedings of Machine Learning Research, pages 1295-1306. PMLR, 2018.
[9] Vincent Y. F. Tan, Prashanth L. A., and Krishna P. Jagannathan. A survey of risk-aware multi- armed bandits. In Proc. of the 31st International Joint Conference on Artificial Intelligence, Vienna, Austria, 23-29 July, pages 5623-5629. ijcai.org, 2022.
[10] Hao Liang and Zhi-Quan Luo. distribution optimization framework for confidence bounds of risk measures. In International Conference on Machine Learning, 23-29 July, Honolulu, Hawaii, USA, volume 202 of Proceedings of Machine Learning Research, pages 20677-20705 PMLR, 2023.
[11] Shaun S Wang. A class of distortion operators for pricing financial and insurance risks. Journal of risk and insurance, pages 15-36, 2000.
[12] Mengyan Zhang and Cheng Soon Ong. Quantile bandits for best arms identification. In Proc. of the 38th International Conference on Machine Learning, 18-24 July, Virtual Event, volume 139, pages 12513-12523. PMLR, 2021.
[13] Parameswaran Gopikrishnan, Martin Meyer, LA Nunes Amaral, and H Eugene Stanley. Inverse cubic law for the distribution of stock price variations. The European Physical Journal B- Condensed Matter and Complex Systems, 3(2):139-140, 1998.
[14] Svetlozar Todorov Rachev. Handbook of heavy tailed distributions in finance: Handbooks in finance Book 1, volume 1. Elsevier, 2003.
[15] Zi-Yi Guo. Heavy-tailed distributions and risk management of equity market tail events. Journal of Risk & Control, 4(1):31-4) 2017.

---

[16] Feruzbek Davletov. Estimating the tail index of conditional distribution of asset returns. International Journal of Financial Research, 13(2), 2022.
[17] Hugo Gobato Souto. Distribution analysis of s&p 500 financial turbulence. Journal of Mathe- matical Finance, 13(1):67-88, 2023.
[18] Hyeonjun Park and Kyungjac Lec. Contextually adaptive algorithms for gaussian process bandit optimization under heavy-tailed noise. In ECAL, pages 3171-3178, 2024.
[19) Taehyun Cho, Seungyub Han, Seokhun Ju, Dohyeong Kim, Kyungjae Lee, and Jungwoo Lee. Bellman unbiasedness: Toward provably efficient distributional reinforcement learning with general value function approximation. In Forty-second International Conference on Machine Learning, 2025.
[20] Tachyun Cho, Seokhun Ju, Seungyub Han, Dohyeong Kim, Kyungjae Lee, and Jungwoo Lee. Policy-labeled preference learning: Is preference enough for RLHF? In Forty-second International Conference on Machine Learning. 2025.
[21] Alex Tamkin, Ramtin Keramati, Christoph Dann, and Emma Brunskill. Distributionally-awarr exploration for evar bandits. In 32th Annual Conference on Neural Information Processing Systems Workshop on Safety and Robustness on Decision Making, 2019.
[22] Dorian Baudry, Romain Gautron, Emilie Kaufmann, and Odalric Maillard. Optimal thompson sampling strategies for support-aware aware cvar bandits. In Proc. of the 38th International Conference on Machine Learning, 18-24 July, Virtual Event, volume 139, pages 716-726. PMLR, 2021.
[23] Chenmien Tan and Paul Weng. Cvar-regret bounds for multi-armed bandits. In Asian Conference on Machine Learning, 12-14 December, Hyderabad, India, volume 189 of Proceedings of Machine Learning Research, pages 974-989, PMLR, 2022.
[24] Sébastien Bubeck, Nicolo Cesa-Bianchi and Gábor Lugosi. Bandits with heavy tail. IEEE Trans. on Information Theory. 59(11):7711-711) 2013.
[25] Lai Wei and Vaibhav Srivastava. Minimax policy for heavy-tailed bandits. IEEE Control Systems Letters, 4(4):1423-1428, 2020.
[26] Kyungjae Lee, Hongjun Yang, Sungbin Lim, and Songhwai Oh. Optimal algorithms for stochastic multi-armed bandits with heavy tailed rewards. 33th Anmual Conference on Neural Information Processing Systems, December 2020.
[27] Jiatai Huang, Yan Dai, and Longho Huang. Adaptive best-of-both- worlds algorithm for heavy- tailed multi-armed bandits. In Proc. of the 39th International Conference on Machine Learning, 17-23 July, Baltimore, Maryland, USA, volume 162 of Proceedings of Machine Learning Research, pages 9173-9200. PMLR, 2022.
[28] Gianmarco Genalti, Lupo Marsigli, Nicola Gatti, and Alberto Maria Metelli. (E. u)-adaptive regret minimization in heavy-tailed bandits. In The 37th Annual Conference on Learning Theory, June 30- July 3, Edmonton, Canada, volume 247, pages 1882-1915. PMLR, 2023.
[29] Kyungjae Lee and Sungbin Lim. Minimax optimal bandits for heavy tail rewards. IEEE Trans. Neural Networks Learn. Syst., 35(4):5280-5244 2024.
[30] Sujay Bhatt, Guanhua Fang, and Ping Li. Piecewise stationary bandits under risk criteria. In International Conference Artificial Intelligence and Statistics, 25-27 April. Palau de Congressos, Valencia, Spain, volume 206 of Proceedings of Machine Learning Research, pages 4313-4335. PMLR, 2023.
[31] Madalina M. Drugan and Ann Nowe. Designing multi-objective multi-armed bandits algorithms: A study. In The 2013 International Joint Conference on Neural Networks (IJCNN), pages 1-8, 2013.
[32] Madalina M. Drugan, Ann Nowé, and Bernard Manderick. Pareto upper confidence bounds algorithms: An empirical study. In IEEE Symposium on Adaptive Dynamic Programming and Reinforcement Learning, Orlando, FL, USA, December 92 pages 1-8. IEEE, 2014.
[33] Róbert FeketFe Balázs Szörényi, Paul Weng, and Shie Mannor. Multi-objective bandits: Optimizing the generalized gini index. In Proceedings of the 34th International Conference on Machine Learning, Sydney, NSW, Australia, 6-1 August, volume 70 of Proceedings of Machine Learning Research, pages
PMLR, 2017.
12

---

[34] Mengfan Xu and Diego Klabjan. Pareto regret analyses in multi- multi armed bandit. In International Conference on Machine Learning, 23-29 July, Honolulu, Hawaii, USA, volume
202, pages 38499-38517. PMIR, 2023.
[35] Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
[36] Tze Leung Lai and Herbert Robbins. Asymptotically efficient adaptive allocation rules. Ad- vances in applied mathematics, 6(1):4-22 1985.
[37] Prashanth L. A. and Sanjay P. Bhat. A wasserstein distance approach for concentration of empirical risk estimates. J. Mach. Learn. Res., 11-238:1-238:66 2022.
[38] Aryeh Dvoretzky, Jack Kiefer, and Jacob Wolfowitz. Asymptotic minimax character of the sam- ple distribution function and of the classical multinomial estimator. The Annals of Mathematical Statistics, pages 642-669, 1956.
[39] Jéröme Dedecker and Florence Merlevède. Behavior of the empirical Wasserstein distance in Rd under moment conditions. Electronic Journal of Probubility, 24(none): - 32, 2019.
[40] LA Prashanth and Sanjay P Bhat. A wasserstein distance approach for concentration of empirical risk estimates. Journal of Machine Learning Research, 23(238):1-61, 2022.
[41] Milan Merkle. Jensen's inequality for medians. Statistics & Probability Letters, 7133):277-281,
2005. ISSN 0167-7152.
NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract and introduction clearly summarize our main contributions: (i) deviation inequalities for the 1- Wasseerstei distance under heavy-tailed rewards, (ii) a robust estimator (MoEQ), (iii) the DistLCB and IR--DisLCB algorithms, (iv) regret bounds with matching lower bounds, and (v) experimental validation. Each of these contributions is precisely developed in later sections.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize other settings.
is fine to include aspirational goals as motivation as long as clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
See Section 6.2, Remark on Limitations.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
13

---

The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: Yes. See Assumptions and Sections and 4.3. Complete proofs are deferred to the appendix (Sections A-E).
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: main paper and appendix fully describe the algorithms (DistL.CB, MR- DistLCB), risk estimators (MoEQ), evaluation metrics, and experimental setup. Algorithm pseudocode is included in Appendix[[ F and synthetic and real-world experiments are clearly explained in Section 7. All experimental results directly support theoretical claims and conclusions.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data provided or not.
the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
14

---

Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome describe the particular way they provide for reproducibilityy In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results. 5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [No]
Justification: While code is not yet released, will make it available upon acceptance, and the information in Sec. 7 and Appendix sufficient to reproduce all key experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
swi.iiossiippcccc.oo for more details. //wpss.c/ppubll. wttp:/cccccggguuueee///e/////e// wwcpi///gidssse/eoo Caaeeee//ooSSSmmiieeeeeee
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
15

---

Answer: [Yes]
Justification: All key settings and parameters are specified in the text and appendix.
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: Standard deviations are reported in plots and tables.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2-gigm error bar than state that they have 96% CI, if the hypothesis of Normality of eтrоrs is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (c.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [No]
Justification: Since our experiments involve simple setups and the main contributions are theoretical, the computational demands were minimal and not a limiting factor.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (c.g., preliminary or failed experiments that didn't make it into the paper).
9. Code of ethics
16

---

Question:
Does the research conducted in the paper conform, in every respect. with the
NeurIPS Code of Ethics
Answer: [Yes]
Justification: The work follows the NeurIPS Code of Ethics in all respects.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: The paper is theoretical with no direct societal applications.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation. generating fake profiles, surveillance), fairness considerations (e.g.. deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (c.g., gated release models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: This work does not release any such resource or asset.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
17

---

We recognize that providing effective safeguards is challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: No external code, data, models were used.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g.. website). the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperswi thcode. cow datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: Our paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
18

---

According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/teview based on the requirements of your country institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology. scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification:
The core method development in this research does involve LLMs.
Guidelines:
The answer NA means that the method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our L.M for what should or should not be described.
htttps://neuriissccc////e httppe//eearrrrsscc/////eeeeeeee
19

---

A Notations, Definitions, and Assumptions
p (1, Order of the bounded moment
Vy Constant bound of the moment
H(p) = (u L1 Bi, s.t. Ex~a [XX] - 1p}
pc Probability measure
Pu: Empirical measure with samples
Li Space of probability measure with finite expectation.
X₁: ith sample
((): ith smallest sample
F(x) and (t): CDF and Quantile
(z) and Fr (x)): Empirical CDF and quantile with samples
(x)) and (x)) Empirical CDF and quantile constructed by bootstrap-resampled
points
F and F med..: Median of empirical quantiles and its corresponding CDF.
f and f Median of empirical quantiles and its corresponding CDF constructed by partially bootstraped samples.
f.PB,-1 and f. Median of empirical quantiles and its corresponding CDF constructed by fully bootstraped samples.
DMp, f(): Distance between probability measures in Li
W1: I-Wasserstein distance
p(X): Lipschitz risk measure
Lipschitz constant of Lipschitz risk measure
A: Set of actions
a E A: Action
and n: Time step and total rounds (or total number of samples)
A₁: The action selected at time
(t):): The selection count for action a over f. steps
Xa.: Random reward of action a at time step
Pa p(Xa): Risk measure of action
Xan: The median of empirical quantiles for action
p(Xa,n) Estimated risk measure for action based on samples.
p(Na,I,(0): Estimated risk measure for action a at time t, where (t) is the number of times action has been selected up time t.
a, := arg min p(X.): Optimal action that maximizes the given risk p.
AS = p(X.) p(Xa.) Sub-optimality gap given risk p
Rí = [Σ ]: Cumulative regret
e(X.): == Ip
... (x.)))) dimensional risk vector
v < u: A vector u dominates a vector e
v * u: A vector does dominates vector v. There exists least one dimension d such
that ea 2 ua holds.
P. == {a E Alva' E A/(a), e(Xa) A e(Xar)}: Pareto optimal actions that are not dominated by any other action across all risk measures.
A Pareto = inf.20f ( e(Xa) + el e(X)), Va' e P, J: Pareto sub-optimality gap
R.P Pareto = E E A Pareto]: Cumulative Pareto regret
20

---

B Detailed Comparison of Prior Work
This appendix presents a structured comparison of prior risk measure aware bandit methods across risk types, reward distributions, and theoretical guarantees.
risk measure aware Bandits with Light-Taile Tailed Rewards. Numerous studies have analyzed bandits
under light-tailed rewards for specific risk measures, including CVaR 2 A or mean-variance 6 7 Especially, CVaR-baser bandits have garnered significant attention among risk measures. Galichet et al. (2) achieved O (In(n) regret bounds for CVaR-based bandits with bounded rewards, and Vakili and Zhao 77. Maillard [3] achieved similar bounds under sub-Gaussian assumptions. For bounded support distributions, Tamkin et al. [21] and Baudry et al. [22] provided regret bounds with detailed dependency on the sub-optimality gap, achieving problem-dependent bounds of O lug(n)/a ( and problem-independee
bounds of O(y Kn log(n)), where A is the sub-optimality gap under CVaR. Recently, Tan and Weng [23] extended these results to sub-Gaussian reward settings for stochastic and adversarial CVaR bandits. These works significantly advance optimization for specific single risk measures but do not generalize to broader risk classes or heavy-tailed settings.
risk measure aware Bandits for Lipschitz Risk Measures. Beyond single risk measures, re- searchers have developed bandit algorithms for Lipschitz risk measures [8]10], which is broad class including CVaR, SRM, DRM, UBSR, and CERM. These risk measures satisfy Lipschitz continuity with respect distribution distances, allowing algorithms to address multiple risk metrics in this class, simultaneously. Several studies have explored Lipschitz risk measures in risk measure aware bandit settings. Cassel al. 88 considered uub-Gaussian rewards and achieved regret bounds of (In(n)). A. and Bhat (37] Tan et al. [9] expanded the scope further to sub sub-Exponential and finite variance distributions, with regret bounds of (In(n)) for sub- Gaussian rewards, OVVTi) for sub-Exponential distributions, and ((nP/p++1) ) for finite variance distributions (2 < p). where p is the order of finite moment. Liang and Luo 10 extended this result to locally Lipschitz risk measures under bounded support rewards. However, none of these works address distributions with infinite variance, leaving heavy-tailed rewards unexplored.
risk measure aware Bandits with Heavy-Tailed Rewards. Most studies on heavy-tailed dis- tributions have focused on specific risk settings, such as maximizing expected rewards 224 or optimizing CVaR [4] [5,, while research on a broad class of risk measures under heavy-tailed assumptions remains scarce. To the best of our knowledge, Bhatt al. [30] is the only study that addresses Lipschitz risk class under heavy-tailed reward distributions with infinite variance. Bhatt
al. [30] analyzed bandits under piecewise-stational regimes with heavy-tailed rewards, achieving regret bounds of Ö Kn) for gap-dependent cases and ((K1/1/pp)1/)) for worst-case scenarios, where p E (1, 2] is the largest order of the finite moment They also proposed a truncated empirical distribution method applicable to the Lipschitz risk class. However, since their analysis considers non-stationary distributions, it does not provide tight regret bounds for multi-risk settings in stationary distributions.
OThey
Multi-Risk Bandits. Multi-risk bandits extend single-risk settings by optimizing multiple risk measures simultaneously, often through Pareto-optimality. Existing works [31 have focused on Pareto regret minimization but are limited light-tailed distributions and do not address broader risk classes like Lipschitz risk measures. Efforts to combine multi-risk settings with heavy-tailed rewards or generalize to diverse risk measures remain unexplored.
Lower Bounds of risk measure aware Bandits. Lower regret bounds in risk measure aware bandit settings depend on the chosen risk measure and the reward distribution assumptions. For CVaR- based bandits under the sub-Gaussian assumption, Baudry et al. [22] established an asymptotic lower bound However, no asymptotic lower bounds exist for Lipschitz risk
of aiE. A CVaB (att))/KK(t... measures, even under sub-Gaussian distributions, and remain unexplored for heavy-tailed rewards.
Bhatt et al. Ō(V M Kn) for gap-dependent cases and (((MM))))////-// for worst-case scenarios. Here, M represents the number of distribution changes. Setting M = 1 corresponds to stationary haile- reward settings, which is the focus of this paper.
3D originally considered piscewise-stationaayy reward settings, where the regret bounds are
21

---

Establishing the dependency of asymptotic lower bounds on the sub-optimality gap (e.g., A A for generalized risk classes and heavy-tailed settings remains a critical open problem. We would like to note that the minimax lower bound general risk measure aware bandits are derived as 0(K111/Pn in Bhatt et al. 33).
C
Summary of Lipschitz Risk Measure
The following well-known risk measures satisfy Lipschitz continuity defined Definition 3.2 Note that we generally follow the definition of risk measures in Tan et al. 9 and Liang and Luo [I]]
Conditional Value-at-Risk (CVaR);
Definition: CVaR at level a E (0, 1) is defined as
I- 1 F (t)
CVaR (X)
(13)
Lipschitz Constant: (1 - a)= where is the risk level.
Distance Metric: W1.
Condition Lipschitzness: None explicitly required beyond the definition.
Spectral Risk Measure (SRM):
Definition: spectral risk measure defined as
SRM(X) = L." ott)
(14)
where s(t) is the risk spectrum satisfying ((t) 2 0 and fo s(t) dt = and increasing function.
Lipschitz Constant: supse|o.1] p(3), where ((3) is the risk spectrum.
Distance Metric: W1.
Condition on Lipschitzness: (33) must be bounded.
Distortion Risk Measure (DRM)
Definition: A distortion risk measure is defined as:
| 9(1 F(x))
DRM(F)
(15)
where g: 10 1] [0, 1] continuous, concave, and increasing distortion function satisfying g(0) = 0 and (()) = 1. We further assume that is strictly increasing
g((x) 0, thus, infz=jo,1] 9 (x)) holds.
Lipschitz Constant: ||g'|loo where |o is the supremum of the derivative g' over its
domain [0, I].
Distance Metric: W1 (1 (1-Wasserstein distance).
Condition on Lipschitzness: The derivative g' (t) of the distortion function must be bounded, i.c., (t) < |lg ol for all & E [0, 1]. To prove the Lipschitz property of DRM under the Wasserstein distance W apply the Mean Value Theorem for the distortion function g. yielding g F(x)) g(1 G(x)) I (l() G(x)).
Integrating over the domain gives:
DRM(F) - DRM(G)) < 11 10 (F.GG).
(16)
Thus, the Lipschitz constant of DRM with respect to W, is ||g lloo-
Utility-Based Shortfall Risk (UBSR):
Definition: UBSR is defined as
UBSR(X) inf e R B[([X m)] S n)
(17)
where is utility function and is threshold parameter.
Lipschitzz Constant: K where K the Lipschitz constant of the utility function 7, and k is its strong convexity parameter.
Distance Metric: W1.
22

---

Condition on Lipschitzness: The utility function must be K-Lipschitz and satisfy the strong convexity property (xx2) 2 ((x1) + k(æz 21) for 22 2 21.
Certainty Equivalent (CE) Risk Measure:
Definition: The Certainty Equivalent (CE) risk measure is defined
CE(F) =u ( u(æ) dF(z))
(18)
where u(x) is continuous, strictly increasing, and differentiable utility function, and u is its inverse.
Lipschitz Constant:
1 11
(19)
infore)gs( u'xx)
where || is the supremum of the derivative u'(x), and inf inf =Erango(u) v((x) is the minimum derivative over the range of u.
Distance Metric: W1.
Condition on Lipschitzness: The utility function u(z) must be continuously differen- tiable, with u' (2) bounded above and away from zero, i.e., iinfeee u (x) S
u' (x) < | ooo
oc.
D On the Validity of Assumption 4.3
In this section, provide additional justification and concrete examples supporting Assumption 4.3
which postulates polynomial concentration inequality for the empirical distribution under a given distance metric. The validity of this assumption depends both the underlying distributional class and the choice of distance metric. Below, we demonstrate that the assumption is satisfied in range of settings, including both heavy-tailed and light-tailed regimes.
ii) distance under heavy-tailed distributions (1 < <). By the Dvoretzky-Kiefee Wolfowitz (DKW) inequality 38), for the empirical distribution function F of n ii.d. samples and the true CDF F, have:
I
sup
(( F(u) >
xx) <
Since the exponential bound decays faster than any polynomial, there exists a constant Cp such that:
Cpup 1P-12P"
P sup F(u) - F(u) > >x) S
for all E N, > 0.
Wi distance under heavy-tailed distributions < < 2). Dedecker and Merlevède [39 Theorem 2.1] provide the following deviation bound for the I-Wasserstein distance between F and F under finite p-th moment conditions:
CpPp 1P-12P
P(W,(F,F) 2)
(iii) Wi distance under bounded, sub-Gaussian, or sub-Exponential distributions. Prashanth and Bhat (40) show that for light-tailed distributions, deviation bounds for the Wasserstein distance admit exponential tails:
P(W1(F,)) x) S ()xpp)))))( exp(-nx²))
for some Assumption
Since the exponential decay dominates polynomial tails, this again satisfies 4.3 with appropriate constants.
23

---

(iv) E distance under bounded support. bound:
Liang and Luo
[T0] establish the following concentration
32 e 8(b - a)
2
((L > x) 0 exp
where (a, b] denotes the support. Again, exponential decay implies the existence of Cp satisfying Assumption 4.3
These results confirm that Assumption 4.3 is satisfied under commonly used distance metrics across both heavy-tailed and light-tailed settings. the final version of the paper, we will include these clarifications along with appropriate citations to ensure completeness and transparency.
E
Median of Empirical Quantiles
E.1 Median of Empirical Quantiles
Lemma E.1.
F-1 Ned,N (y) and Fmnd,N(()) are valid quantile and cumulative distribution function, respectively.
Proof. First, the domain of F-11 x (y) is clearly y [0, Second, we prove the non-decreasing property. It is equivalent to show that, for any 31 y2, Fi mod.. (V1) I Fmed.. (322). If l: is odd, say
k = 2v + for some integer c, then, by definition of the median, at least v number of FN. are
greater than ( and at least o number of (21) are less than (yi Since FN (v) non-decreasing, we have, for all j. FN (31) (21) S F (32). Hence, any empirical CDF F (y1) that was greater than Fied, (v)) satisfies the same condition at y2. i.c., F S F (81) < FN' (22). So, at least number of empirical CDFs are still greater than m (81) at y/- In this regard, f- Feed (32) cannot be less than f Fmed. (81), i.c., Fi Fmed.N (v1) I N For even number 2v, the same argument also holds. Third, by definition of N (x), its quantile function is f-1 med.N (y)-
Lemma E.2. For all x E R, (m) median (FNs(z)) holds.
J6(1.2.. k3
Proof.
A Fmnd (I) =
F (1/N) <
1
[median (median,(X(o).)) <a
(20)
N Σ
mediang(I (I < x]) medianj
Σ
1
[X
(9) < <1]
(21)
N
median (Fxs(x))
(22)
E.1.1 Proof of Theorem
Proof. First, we would like to note that, due to convexity of D(,, F), we have
D D(Fmed, N. F) & median
(D( F)). EE(k
(23)
where detail proof can be found in Merkle 41). Then, the similar technique in Bubeck et al.
24
is applied. Let > 0 and Ye (FN,(F > x) for l [1,2,3,-. k). Then, from the Assumption 4.3 we have,
C₂up
== P(= = 1) P(D (ID(B,,, x)
(24)
NP-1
24

---

Note that for
(4CpVp) 1/2
(25)
Ni-1/2
we have 9 I 1/4. Then, by using Hoeffding's inequality for the tail of binomial distribution, we get
(D (Fmod..,, F) 2 2) s PP
median ZE(A]
(D(Fx.e; F)) 2x)
(26)
k
P
Yi
S exx (-2k(1/2 -2))
(27)
2
S exp
k/8) 5 6.
(28)
where the last incquality holds since h = 18 1/8 / > 8 In(1/8). Hence, we have N = Ln/k]
16 (lluee//88) Consequently, with probability at least 1 - 5,
(4C,0p)
[16ln(e4*/0) 1-1/8
D FF
Sx=
N1-1/p S (4Cpu))
(29)
E.1.2 Proof of Corollary 4.5
To handle bootstrap resampling, first derive the following two lemmas. Lemma E.3 (Deviation of PB-MoEQ). Under the same conditions as Theorem 4.4 and the 1- Wasserstein distance W,, let F + any fixed x > O,
be one sample bootstrapped empirical CDF of FN.. Then, for
2P+ Vp
(Wi((P8L) Pxs) >
(30)
NP-Lap
Proof. To quantify the difference between the empirical distributions before and after adding boossteap-eesmmpeed sample, we compute the 1-Wasserstein distance:
Wi(Fx,, P&t1,) [xx,(x) P F&t1, (x) dr.
(31)
Then, the difference between the two distributions is:
( (x) N Boot Sal N(N +)
1 Boot
Σ π[x x))
(32)
where Xoot is a bootstrapped sample. Then, reorganizing, this becomes:
F (x) Fx,)(x) N+1 (I[Xnoot x| (x))
(33)
Thus, the Wasserstein distance expressed as:
Wi (F F ( N +
[[X Sz] Sx]-FN,((t) dr <
2 max [X.].
(34)
N +11 iE(N]
where the last inequality holds since the gap between the indicator and empirical CDF is clearly zero outside of |- max; X,), max; [X,]]. Now, for the deviation probability,
P (WWi(ESt Px.)) > < P
2 max [Xa] > iE(N]
(35)
N +
(N (++11z) 1)x
2'NN
Up N
< NP
[X,]>
<
(36)
2
+N+11p2
Lemma E.4 (Deviation of FB-MoEQ). Under the same conditions as Theorem 4.4 and the
Wasserstein distance W.. let N.S be the Eth full bootstrap empirical CDF, and let Fa be the empirical CDF obtained by original dataset. Then, for any N, t O, and any fixed >
PP (WI F.) > x) < 2nexp (2N (mn)) (
2n
(37)
1
25

---

Proof. Consider the conditional probability:
P(W.(FN,2. F.) > x) = Ex,, Xn PFW,, F.) I XI,..., X,))
(38)
Then, given original datasets, the Wasserstein distance can be bounded by:
Wi(FNa, / [FNe(x)) - P.(x))dd mmax, [xx,1
[FN,e(x) - (o
(39)
max, lxxl
maxe |x1
I[x, x/de S
max [.x.).
(40)
|X,]
N
7
where k;2 is random variable that indicates the number of times X, is selected in the bootstrap resample. Given the original samples, uniform resampling with replacement is equivalent to sampling N independent categorical random variables with equal probability 1/n. Thus, we have:
P(Wi(FN.e.P.) X1," .,))) PP
ks N
X1, Xn
(41)
max, [x,]]
X1, Xn
(42)
2n max; X,
Note that marginal probability of k; is binomial distribution with N and 1 1/n. Using the Hoeffding inequality for the deviation of binomial variable:
P (Wi Fa) x XI, Xx.) ...) 2n exp
(-2N
x 4n max; X.
(43)
Now, consider the total probability, for t > 0,
F(Wi(fN.n, x/2) F(Wi Ft) > 2/2 max [X|] S P)P [xx]| 5()
(44)
+ +P(Wi F.) x/2 max [x,]| > L)P |xx > l).
(45)
For the first term:
(-2N ( (x))
4nt )
))) 2)
P ((W,(FN,e, > x max [Xi] S t) < 2n exp
(46)
For the second term, using the tail bound on max; X;|:
2n1p
P(max [X,| > t) S
(47)
1
Combining these, we have,
P(Wi(Fx.e Pa) x) S emxxp
-2N
12)
+
2n0p
(48)
1nt
By using the deviation inequalities of bootstrap resampling cases, we now prove Corollary 4.5
Proof of Corollary 4.5 Proof of MoEQ: First, for the case of MoEQ, let us verify that the 1-
Wasserstein distance satisfies Assumption 4.3 to apply Theorem 4.4 From Theorem 2.1 in Dedecker
and Merlevède [39], for an empirical distribution of heavy-tailed distribution with p > 1, we have:
Coup
(F.,
(49)
ND-1ap
This implies that W, satisfies Assumption 4.3 By applying Theorem 4.4 we know that ((6) 8p (8) (1 (1(e2/8/8//n)) LTp. Hence, the proof of the first is completed.
Proof of PB-MoEQ: For the case of PB-MoEQ, it follows directly from the proof of the Lemma E.3 By the triangle inequality:
P (Wi
> 20 + + (F (f#+1.:)) F) > x) s P (wi (AB (
25)
Wi (FN.s F) > )
(50)
22'
2'O Ng-1
C/Upp
(51)
Ne-1gø
26

---

where ;= 2 + pp From this fact, we can apply Theorem 4.4. From Theorem 4.4
we get:
1-1/p (161n(e4%/8) (1
W1 (Fimd, P) (4C,
= =p.n(0).
(52)
This completes the proof.
Proof of FB-MoEQ For the of FB-MoBQ, it is enough to prove the following probability bound,
IF (Wi F) > x) SP (wi (FN3. P.) x/2) + IP (wi (Fr. xx/2)
(53)
Then, for the first term, by using the Lemma E.4 get,
P(W1(F AFB F.) > x/2) $2nexp
-2N
+
2nd 1
(54)
8mt
exp exp
-2N
x
by choosing t 32n 32n u2 (55)
256n
1+
F
16
For the second term, again, from Theorem 2.1. in Dedecker and Merlevède 39
we have,
Cp
P(Wa > x/2)) S
(56)
1p-1
Finally, by combining two results, we get,
2.
q = P (wi (FW,F) F) x) s 2n exp
-2N
1
Cr
(57)
256n
1+
16
nd-1
Note that for
28- CD
In(32n)
(
128n² 2 (8C,)1/p)
.N>
(58)
n/-1/p
we get g S 1/4. Applying Hoeffding's inequality for the median, the probability bound is established, leading to:
Wi [ r)
2(8C,uz))1 n2. n²-1/2
(8)"
(59)
Consequently, this completes the proof.
F
Algoirthmic Details
F1
Distributional LCB
The Distributional LCB algorithm extends the classical lower confidence bound approach to risk measure aware settings by leveraging Lipschitz-continuous risk measure. At each round, algorithm constructs a confidence interval for the estimated risk of each arm using the median-of- empirical-quantike (MoFQ) estimator, and selects the arm with the lowest lower confidence bound. This design enables robust decision maaiing under heavy-tailed reward distributions.
27

---

Algorithm Distributional LCB
1: Input: A: Set of actions, K: Number of actions, (p,n): A Lipschitz risk measure with Lipschitz constant, n: Total time steps, p: The order of bounded moment, Up: The bound of the yth
moment, Cy: Scaling factor of deviation bound, k: Number of empirical quantiles
2: Output: Optimal action å.
3: Initialize To +- for all E A, Xa,0 + for all E A, LCB(a) + 0 for a E A
4: for all A do
5: Pull arm a and observe reward Xa. update Xa,1, and increment To < Ta +
6: end for
7: for = K + 1 to do
8: for all a E A do
9:
Compute 3a,t-1 based on Corollary 4.5
10:
LC + pl ((..,T.) KBO,T.
11:
end for
12:
Select action A, arg minae LC
13: Observe reward XA, and update TA, + TA, +
14:
Update XA.TA + (OBQ((XA,111-. XA,T
end for
16:
Return: à, t arg m a
F.2 Median Empirical Quantiles with Bootstrap Resampling
The Median of Empirical Quantiles (MoEQ) estimator is used to construct robust estimates of the reward distribution under heavy-tailed noise. The data is partitioned into multiple blocks, and the empirical quantiles of each block are computed. The final estimate is obtained by taking the median across blocks each quantile level. To ensure balanced partitioning, bootstrap resampling is applied if the sample size is not divisible by the number of blocks.
Algorithm 2 Median of Empirical Quantiles with Bootstrap Resampling
1: Input: X1, X2. Xn: Samples, k: Number of empirical quantiles (or groups)
1,2...., .N} 2: Output: The computed median quantiles { (j/N) :j Xn to ensure n KN.
3: If mod & &f O, bootstrap-resample from X
4: Compute block size: N + Ln/k].
5: Divide the data into i groups, each of size N:
Group, = (X N,), Group, = (XN+1..... X2N). Group, = (X XxN)
(60)
6: Sort each group: For each Group,, sort the observations to compute order statistics:
Xaa I X(2.. S S X(N).
(61)
7: Compute the median of quantiles: For each quantile level ف compute:
(iN) Median 1, xgyx)).
(62)
F.3 Multi-Risk Distributional L.BB
The Multi-Risk Distributional LCB algorithm generalizes the risk measure aware exploration to settings involving multiple Lipschitz risk measures. For each arm and risk type, the algorithm computes lower confidence bounds and identifies a Pareto-optimal set of actions that are non- dominated across all considered risks. An action is then sampled uniformly from this Pareto set, balaneing risk-sensitive exploration under multiple objectives. This approach is particularly useful in applications where trade-offs between different types of risks must be considered simultaneously.
28

---

Algorithm 3 Multi-Risk Distributional LCB
1: Input: A: Set of actions, K: The number of actions, {(p), K1), (p2, K2)..... (Pr, Krr,K Set of Lipschtiz, risk measures with Lipschtiz constants, n: Total time steps, p: The order of a bounded moment, Up: The bound of the pth moment, Cp: Scaling factor, k: The number of empirical quantiles
2: Ouput: Pareto optimal actions P...
3: Initialize P+, +- 0
4: Initialize T, + for all
5: Initialize X..0 f for all E A
6: Initialize LCB(a, d) + 0 for all E A, d E (1,2,-..,7)
7: for all E A do
8: Pull arm and observe reward X
9: Update Na,1 and increment Ta +- T. +
10: end for
11: for to K + to n do
for all a E A do
13: Compute 3a based on Corollary 4.5
for d = 1 do
15:
LCB(a, d) Pa( pa( - Ka.a.T.
end for 17: end for
for all a E A do
19:
Add to P., Va' E EA\ (a], LCB((') A LCB(a) (Pareto dominance check)
end for
21: Sample A, Uniform(P...) ....) (Select action)
22: Observe reward Xa, and update TA. < TA, + for selected action At
23: Update XA,TTA, + .A,,TA, }) (Update quantiles with all observed re-
wards of action Ac)
24: end for
G Regret Analysis
G.1 Lower Bounds of risk measure aware Bandits with Heavy-Tailed Rewards
G.1.1 Asymptotic Lower Bounds
Proof. The proof will be done by using the generic lower bound (See Chapter 16 in Lattimore and Szepesvári (35). Especially, apply the similar techniques in Bubeck al. [4 for SRM and DRM. we construct two Bernoulli random variable X1 and X2 on the set (0, 1/7), where 7 == (2c)a/(e-1) and a E (0, 1/4). Specifically, define the probability
P1 (1+cr- -1") 80 + ()P-c7) 81/7
(63)
and
J22 = -1->7) + P811/7
(64)
Here, 5g denotes a point mass at æ. Furthermore, we can check the pth moment Bernoulli distributions. Under the distribution μ4, the random variable X₁ takes the value 0 with probability (1 1I+c7-773 PP and with probability 7p cy. Therefore.
E X O. -1+ 7") + (2)² (c7- = -1- = 1/2.
(65)
For X², we have
E [| OP (1 (1-7P) + (2) -
(66)
Hence, for this Bernoulli bandit problem, 1/p for any choice of c.
29

---

Then, let us compute spectral risk measure and distortion risk measure for these two actions. First, for SRM, we get the following risk values. For X,, we have P1 7p cy and 21 /. Thus
((x)) = I 1-getor
(())da
(67)
For X2, we have P2 = = and 22 y. Hence
p(x2) = 7/ 1 1-70 o(a) da
(68)
Then, the sub-optimality gap of X2 and X1 becomes,
1 1oy Ag: :(X2) - p((x))
d(a) do 2 6(1 - -P- 6( (1/2)//001))) Dopc
7 1-
(69)
where Do.p == 6(1 (1/2)p/(-1)))
Next, for DRM, we get the following DRM values. For X1, we have = ey and T = 4. Thus
(())) 1 ?
g(2 -07).
(70)
For X2, we have
1 9(7²). 9
p(X2)
(71)
Similar to SRM, the sub-optimality gap becomes.
A = p(X2) - p(Xx) = 1 g(>))) - -17)-007) = - - 2 Dapc
(72)
where there exists E [0, 1] such that the last equality holds by the mean value theorem and Dg. == infff g'x)).
From the asymptotic regret lower bound for two-armed bandit problems, as in 24 lower bound becomes
35
the regret
inf R. -- In(m)
AC p2 - p2)
AG (1 "")
2 4g DKL,X2, X1)
(73)
(p2 p1)²
6222
AC . (2c) - (1 70)
Ag(1 - (1/2)=
1
2
20
(A
(74)
CP 2
22-12
2-p
G.1.2 Minimax Lower Bound
Proof. We prove the theorem using the minimax lower bound technique for K -armed bandits. We define two different bandit problems. For the first bandit problem, define K Bernoulli distributions where the first action has the distribution of (63) and other remaining K actions have the distribution of (64). Then, the sub-optimality gap of SRM and DRM is
A 2 Dp.p. for i 2
(75)
where D Dp.pp are constant only dependent on and p. To create the second bandit problem, let i arg miny>1 E, (T) (n)), where E, indicates the expectation over the first bandit problem and (n) denotes the number of times action is pulled up to time Since the total number of pulls satisfies Σラ= E, (T)
n, it follows that E, [m)] < रー Then, for the second bandit problem, we only change the distribution of action follows,
50
(76)
30

---

where action has all probability at zero. Here, by construction of both bandit problems, action is optimal under the first bandit problem. while action is optimal under the second bandit problem. Furthermore, for the second bandit problem, the sub-optimality gap of SRM of the first arm is obtained as
A - -(x)) - - - 2 7'11-"+t>)(r+" 1077+0
Φ(a) da
(77)
61 (1/2) D'pc.
(78)
where X and X indicate the Bernoulli distribution for the second problem. For DRM, the gap becomes
1 9(6 = -c7) ( D' (7" -c) D' c.p.
= = -
(79)
Furthermore, the KL divergence between X; and X is obtained as
(pi 1/12 (1 - p1)
(7 - -y)²
(2 --- )CF
(x,
(80)
(7p 70 +ry
(2 2 )c
(2 - - 1 Jcr
(81)
(1 (1/2) 2p
p-1
Then, the regret of the first problem is
Rr 2 Σ AT
M (T) S n/2)]
(82)
a#1
a#1
Dap
2 D p.p.
(T) S mn/2)
(83)
2
The regret of the second problem is
Do ne
Rh, 2 (T) 2 (TTT(T(() n/2)) 2
P2 (2(Ti(m) > n/2)
(84)
by using the Bretagnolle Huberr inequality, the regret of the two bandit problems satisfies R + Rh, 2
minn(Dppp Dp.p)nc
exp (
(-E,[Ti(n)]
(X.,(X.,,)))
(85)
4
min( Diin D' D' nc
EprcPEr
exp
K K-1
(86)
where Epp = 12 2--1) (1-(1/2) p-r) 1)/n)1-1/p follows,
Consequently, the result is completed by choosing ((K
R. + Rh. l (K 11)-1///11//11
ma RS Rr,2)
(87)
G.2 Optimality of Distributional LCB
Proof. 1. Gap-Dependent Bound: At any time f, the event (A, = a} (where action a is chosen at
time step t) can occur under the following scenarios:
881(e2/844) 1-1/2
(A. ac c ((Xe..ra.t-m) (0000=x((CC))) 1/ x(ACpu,)
> p(Xo.))
(88)
Ti -
u (D 5 -K(Cp,))) 114(62/814))
1-1/8
(89)
Ta(t - Ta(t-1)
31

---

u (Ta(l 1) < u).
(90)
( (Ac)
where a = 32(2k)
In(el/32n). The expected number of times action a is chosen
is:
B[Ta(n]]=1 =1
Σ
P(A: = a) s1+u+
Σ
=(Ae=a,Tale = Tatt 1)> u)
(91)
t=X+1
tmu+1
[lu((e1824) 1-1/0
+1+u+ ++
Σ
P
ol x((C)uu)))
> o(Xa.)
(92)
Ta. (t. 10--11 1)
1=++1
(1 1-1/p)
+ Σ P p( ((Xaaraten) S (X()) - <(1Cppp) 1/2
(93)
Ta(t 1)
(=u+1
+i+u+ S1+ut+++ Σ
" 2 1=++1 13
Su2
(94)
Substituting u, we obtain:
(4Cp o- (A6)=
S 332(2)))+++)
Infe 1/86)/881) +2
(95)
The regret for action is:
RSy Σ (T
(96)
Σ 32(2k)=
[4Cp12
p-1
In)
n) +2 Σ D.
(97)
AC
a:
2. Gap-Independent Bound:
p-1 [32K In(e
Define A
" )( The regret is:
Rr
Σ (T)
(98)
< <nA+ + Σ A[
(99)
<nA + Σ 32(2k) 25
44Cp/2 p-1
In(e1/92m) n) +2 Σ
A
(100)
A
an 20
4Cpupp +T
< <A + K32(2k) b
In In(2 n) + Σ A
(101)
< <n((AGub)) (32k
n +2
AG
(102)
G.3 Regret Bounds of Multi-Risk Distributional LCB
Proof. For any action a E P., we decompose the number of times it is pulled up to time n as
(x) 1+
Σ I.A. [A==
Σ I[A = a. T.(1 - 1) 2 4.
(103)
K+1+1
The second term can be further bounded
Ta(n) < 11+++
Σ T
(104)
1=1
32

---

From the fact that a is sampled from Pr.c. this becomes
S1= n
Σ r(e(K...-1)) KB & e(Xa,-1)) KB 2 (105)
d.EP.
Next, we use the union bound and consider the following decomposition;
{e(to...) KBBa.i A e(Xaic))= - KSSaiaa S
(106)
(e(X.)) - KBnns e(Sarve } fu elloa.)) - KBB... e(Xo.) } u (o(Xmn)) A e(x.) 2K, }.
(107)
(tmas, (a)) F Ilnkk)n the third term vanishes
For Sa 2 b>
(APareto) 1
(e(X...) A e(X.) 2IC,S.... = 0.
(108)
The first two terms can be bounded using concentration inequalities
P ((((X)) KB A e(Naisa) S
1
(109)
Krta
Kt4
(e(Xo..)) KB A e(Xo.)) S
1
(110)
Krtd
Kta
Substituting these bounds into the original sum,
(n)) 11+1+
(111)
Kt4
1r EP.
Su=t
2
s1+(+
(112)
KP
8. 1...P.
11+1+
(113)
3
Finally, substitute l (maxa (1C P-T 8 In(e" Krn")
we have
(AParoto) --
(maxa Kid (- Krn²)
+1+ x²
(T)) <
(114)
(aPreto)) =
3
Substituting the bound for E[Ta(n),, we obtain,
(max, (a), 1/36 (Kr)))
R
Pareto
1
Σ acA/P.
A Pareto
(115)
(A Parrtto)
3
PEA.P.
By repeating the same procedure to compute the worst case bound, the minimax regret bound is obtained
Pareto 2(mmaxaa)4C (32K (32K In(e (K)))( - n
x²
R.
(1+
Σ nEAdiP.
A
Pareto (116)
H Experimental Details
H.1 Werl-World Experiment Setup
We use daily stock return data from the top 20 S&P 500 companies over 3,184 trading days (2012.05.1 18-18825.01.144 At each time step, the algorithm selects one asset and observes daily return the reward. The task is to identify Pareto-optimal assets across multiple risk measures:
33

---

3-risk: CVaRo.75. Wang(-1.0)) CERM(a = 1.0)
6-risk: + CV. Wang(0.0), CERM(a 2.0)
9-risk: C.. Wang(1.0), CERM(a 3.0)
For CERM, u(x) := - is used as weight function. Tail indices estimated via Hill's estimator range from 1.50 to 4.69. We use 1.5 conservatively in our algorithm.
The heavy-tailed nature of stock returns is well-documented [33177. Using Hill's estimator, we find tail indices the range [1.50, 4.69], confirming heavy-tailed behavior. We adopt a conservative tail index of p 1.5.
H.2 Synthetic Experiment Setup
We simulate a 20-armed bandit problem with Pareto-distributed rewards. Arms d18. d1g, and a:0 belong the Pareto-optimal set. We vary the number of risks across:
3-risk: CV.Ra.9, SRM,, SRM2
6-risk: SRM1 to SRM,
9-risk: CV. SRM, to SRMs
step-function spectral risk measure (SRM) following the axiomatic framework of ]. Given a quantile level z E (0, 1], the spectrum function 6(x) is defined as a tight-continuous step function that assigns weight quantiles below threshold ar.. Formally, the spectrum is evaluated as:
Each SRM is implemented
(xx)
Sk
ll(r ax),
where I[()) is the indicator function, and the weights { are normalized to satisfy the coherence condition:
Σ Sh - on)) 1.
This construction allows SRMs to be expressed as weighted averages quantile values, where the shape of the spectrum reflects varying degrees of risk aversion.
We adopt this formulation flexibly construct variety of SRMs by adjusting the as and ox parameters. This enables controlled evaluation of our algorithms under diverse risk preferences and weight concentrations. The specific parameterizations used our experiments are listed below:
SRM; alphas = (0.2, 0.4, 0.6, 0.8), ranges = [0.25, 0.5, 0.75, 1.0]
SRM2 alphas = [0.1, 0.2, 0.5, 0.9), ranges = (0.2, 0.2, 1.0, 1.6]
SRM; alphas = [0.5, 0.75, 0.9]. ranges [1.0, 1.0, 2.5]
SRM; alphas = [0.25, 0.5, 0.75), ranges [0.5, 1.0, 0.5]
SRM; alphas [0.2, 0.4, 0.6, 0.8, 0.95), ranges [0.0, 0.333, 1.0, 1.0, 4.0)
SRM; alphas [0.2, 0.5, ranges [0.375, 1.0, 1.0]
SRM; alphas = [0.15, 0.35, 0.55, 0.75), ranges [0.0, 0.462, 1.0, 1.0]
SRM; alphas = [0.3, 0.7], ranges = [1.0, 1.0]
CVaRos: alpha = [0.9]
Each SRM captures different attitude toward risk by shifting the emphasis toward different regions of the tail. Reward means are sampled uniformly over [0, 1] and sorted ascending order. We run each experiment for 10,000 steps with 20 random seeds. We use a fixed tail index of 1.2, which simulates a more extreme heavy-tailed condition than observed in the S&P 500 dataset, allowing us to evaluate performance under high-risk environments.
34

---

I Discussions on Truncated Empirical Distribution
The truncated empirical distribution (TED), introduced by Bhatt al. [30], designed handle
heavy-tailed reward distributions by mitigating the impact of extreme outliers. The truncated empirical CDF defined as
Ftrune, n (x) = 1 Σ I[sign (X;) min( min( < x]
(117)
This truncation limits the contribution of extreme rewards by replacing large values [X,] with truncation level jl/p, where is the order of the bounded moment. Then, the lower confidence bound (LCB) for TED, as formulated by Bhatt et al. 330 computed as LCBB (1) p( (t)-)) 2y1 max A?)
(118)
where p is a Lipschitz risk measure, Ta (t- 1) is the number of times action a has been chosen to time 1, and
In(t)
In(t)
A: 1)) + 3(Ta(1 - 1))3/2-1/2
(119)
Here, is a tunable parameter to adjust the confidence width, defined in Bhatt et al. 30
We would like to emphasize that confidence interval of the TED in (118) holds for the risk class defined in Bhatt et al. [30] including CVaR. Bhatt et al. [30] derive deviation bounds for the semi- norm, which is equivalent to lg for CVaR, but their framework does not address the Wasserstein distance W1.
In this work, we extend their analysis to the Wasserstein distance W1. Let us first assume that there exist an increasing sequence of threshold B₁- While it is (²/p in (118). in the following analysis, we assume that is some increasing sequence and we will specify B, later.
1 F Firune,n is (I) == n
I[sign (X;) min (X,), B x]
(120)
F Firune,n (I) == P(sign(XX min [X,), B < x]. Note that F Fi is discountinuous at Bnn and Bn, Hence, we have,
(121)
2 Bn,
F Ferune, no (x)
F(x)
[-Bn, Bn);
(122)
x < Bn-
We first split the analysis into two parts,
(Ferunnn, Ftrunc,n)
Firune,n (a)) Forune, (x)
(123)
Bn
(i)unc,n(2)) F
(124)
B,
<2B,
sup -E.
Furune. (x) Firune. (x))
(125)
In(C//)
$2Bm1
(:: DKW incquality)
(126)
2m
W1 WF F)
|irunn, (x) F(z))dr
(127)
Br
Bn
Firune, - F(x))dr + [-p. Ferune.n (x) - F(r)ddr
(128)
Firunc, - F(x:)ddr
(129)
Bm
Bn
Bn F(x)dxx + fon Ftrane,n (z) -(x)) dx 1 1 - F(x)dr
(130)
Bn
35

---

F( d(-r)dr+ + /
1 F
(131)
Bn
1 V/2 dr
22
P ((X] > xr dr. 5
(132)
Bn
Bn x
21p (p-1)
2//
(133)
(p
Dn (p ---18 B).
Combining these, the total deviation is
Wi (F F) W1 (i(Frrun..n Firunc,n) + Wi(Farun.nn F)
(134)
In(C/5)
2
1 2B,,
(135)
2n
(p-
1)
The optimal truncation level Bn minimizes the combined deviation terms. Solving for B, gives
2m
B. =
(136)
ln(C/5)
Then, the confidence interval of deviation inequalities is computed as
(In(C/66) ((1-;)
W1 (firume,. F)
Up
(137)
p-
For Lipschitz risk measure p with Lipschitz constant K, we can derive the confidence interval for as
(1-
(In(C/0) 2n
p( ((Frrunc.)) p(FF) S 1m
(138)
This result provides robust confidence interval for risk measure aware bandit algorithms under heavy-tailed settings. However, the derived order of convergence, 1 }) worse than the ideal order of 1 1 This highlights limitation of the truncated empirical distribution approach, as the truncation mitigates extreme values but sacrifices optimal convergence rates for risk measure estimation.
36


Reviews:
[{"review_id": "zexMayR3TI", "reviewer": "Reviewer_5oZY", "summary": "This paper studies the problem of risk-aware stochastic multi-armed bandits under heavy-tailed rewards. The authors develop a unified framework for minimizing a wide class of Lipschitz risk measures when only a finite $p$-th moment exists for some $p \\in (1,2]$. The central technical contribution is the Median of Empirical Quantiles (MoEQ) estimator, which admits new deviation bounds under the 1-Wasserstein distance. Based on this, the authors propose DistLCB for single-risk minimization, and MR-DistLCB for multi-risk Pareto optimization. The paper also establishes regret upper and lower bounds under heavy tails and provides experimental results on synthetic and financial datasets.", "questions": "1. Please clarify the intended meaning of \"risk-agnostic\" and consider replacing it with a more precise term such as “risk-function-agnostic” or “uniform over Lipschitz risks.”\n2. Is the assumption $N = O(n^4)$ in Corollary 4.5 necessary for the FB-MoEQ bound to hold? Can this be relaxed, or does it reflect a limitation of the MoEQ analysis?\n3. Could the empirical results include more direct comparisons to robust baselines under heavy-tailed noise, such as TED or trimmed estimators?\n4. Is it possible to extend the regret lower bounds to other Lipschitz risks beyond SRM/DRM, such as UBSR or CERM?", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "### Strengths\n\n1. The proposed approach generalizes many prior works by covering both light-tailed and heavy-tailed settings, as well as both single-risk and multi-risk objectives.\n2. The Wasserstein deviation analysis for MoEQ appears to be new and enables confidence interval construction for arbitrary Lipschitz risk measures.\n3. The authors provide both minimax and gap-dependent regret bounds, and importantly, derive new lower bounds for SRM and DRM in the heavy-tailed regime.\n4. The authors also provide formal Pareto regret guarantees across multiple risk measures under heavy-tailed noise.\n\n### Weaknesses\n\n1. The term \"risk-agnostic\" is used in several places to describe the estimator or algorithms, but this term is ambiguous and potentially misleading. In other literature, “risk-agnostic” may imply risk-neutral, that is mean-based. This could lead to confusion about the intended scope of the methods, especially since the paper focuses on minimizing Lipschitz risk measures rather than mean-based risks.\n2. Unreasonable assumptions in Corollary 4.5: The sample complexity bound for the full-batch version of MoEQ (FB-MoEQ) assumes that the offline sample size $N = O(n^4)$, which is excessively large and unlikely to hold in any practical setting. This weakens the usefulness of the corollary and the empirical claims based on it.\n3. While the deviation analysis is novel, the estimator itself, i.e., median over quantiles of batches, is a natural variant of median-of-means and empirical quantiles. The innovation lies more in the analysis than in the estimator’s form.\n4. The experimental results are promising but narrow in scope. Comparisons to strong baselines are minimal, and the choice of synthetic distributions could be better motivated.", "was_revised": true, "final_justification": "I thank the authors for their response. I will keep my score.", "rebuttal": "We appreciate the reviewer’s insightful comments.\n\n**Q1) Clarify “risk‑agnostic”:** We thank the reviewer for highlighting this point and fully agree with the concern.  To avoid ambiguity, we will replace the term “risk‑agnostic” with “risk‑measure‑agnostic (RMA)” throughout the paper (title, abstract, and §5).  Risk‑measure‑agnostic explicitly means that the estimator and confidence index remain valid, without modification, for any Lipschitz risk functional.\n\n**Q2) Large‑n condition in Cor. 4.5 (FB‑MoEQ):**  We agree the large sample requirement in Cor. 4.5 looks strong, but it appears only in the proof of the full‑bootstrap (FB) setting, where a conservative union‑bound on the resampled maximum inflates the sample size; it is not inherent to MoEQ. The FB bound could be relaxed with sharper heavy‑tail tools (e.g., Bennett‑type inequalities) or other types of bootstraps (e.g., m‑out‑of‑n/Poisson bootstraps), yet tightening the FB analysis lies beyond this paper’s scope. We focus on establishing the first exponential‑decay guarantee for MoEQ under heavy tails, and we leave refinement of the FB analysis to future work. All experiments therefore employ the partial‑bootstrap (PB) MoEQ, which achieves the same exponential concentration without any oversampling.\n\n**Q3) More direct comparisons:** Thank you for the suggestion. Our MR‑Trunc (L326-327) baseline is the multi‑risk extension of TED, so TED‑style truncation is already evaluated on both the synthetic and S&P‑500 datasets (see Figures 2 and 3 in Section 7). In those results, MR‑DistLCB consistently outperforms MR‑Trunc/TED, especially as the number of risk measures grows. If the reviewer has a different comparison in mind, such as another evaluation metric, please let us know and we will be happy to include it.\n\n**Q4) Lower‑bound extension to other Lipschitz risks:** As noted in Remark 6.4, our proof on the lower bounds relies on the gap condition $\\Delta_{2}^{\\rho} ≥ \\Omega(c)$, which we can express explicitly for SRM/DRM because their risk difference decomposes into a weighted integral of the CDFs (see Proof of Theorem 6.1.). For utility‑based risks like UBSR or CERM, such a decomposition is missing; the risk is defined through a non‑linear utility function, so the current KL‑based argument cannot be applied directly. While there exist some trivial cases, such as a linear utility function, a new characterization of the utility term in UBSR or CERM would be required to obtain the similar lower bound, making this an open problem we leave for future work."}, {"review_id": "CHxyRlvymu", "reviewer": "Reviewer_HFsi", "summary": "This paper addresses the problem of regret minimization in heavy-tailed bandits. The focus is on risk-aware bandits, and the goal is to actually minimize the cumulative risk incurred by the algorithm. The concept of risk generalizes the usual expected value, and is assumed to be Lipschitz w.r.t. to a distance notion (e.g., 1-Wasserstein). The paper introduces a new estimator, Median of Empirical Quantiles, to estimate the CDF of a random variable while being robust to its heavy-tailedness. The estimator is then equipped with deviation inequalities, which are used to construct a UCB-like algorithm to deal with their regret minimization problem. The authors prove upper bounds for the regret of the resulting algorithm and matching lower bounds. Lower bounds only hold for the case of two specific risk measures.", "questions": "Can the authors better clarify what the main technical challenge is when trying to extend the lower bound from the considered risk measures to a general one?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths \n\n- The paper addresses a very general problem, and new technical tools are developed that may be of independent interest (e.g., MOEQ and its deviation inequalities).\n\n- The paper provides a comprehensive experimental evaluation, comparing their algorithm to baselines on both real-world and synthetic data.\n\n- Both gap-dependent and worst-case types of guarantees are provided, and even though they match only for two types of risk measures, the authors discuss this point and highlight the technical challenge involved.\n\nWeaknesses\n\n- The paper is hard to read in some points, and there are some typos (e.g., \"measure\" in line 95). In some points, there is an abrupt passage to the statement of a result, e.g. lines 141, 248, 305, where the result is immediately after the section title. Improving the writing there.", "was_revised": true, "final_justification": "The paper addresses a relevant problem, makes consistent contributions to the theory, and there is enough technical novelty to be accepted at NeurIPS without particular reserves.", "rebuttal": "We are grateful for your careful reading and constructive suggestions.\n\n**Typos and Readability:** Thank you for catching the typo; we will correct it. We also agree that theorems start too abruptly; space constraints led to this. In the revision, we will insert brief lead‑in sentences and intuitive remarks before each result to improve readability.\n\n**Q1) Lower‑bound extension to other Lipschitz risks:** As noted in Remark 6.4, our proof on the lower bounds relies on the explicit gap condition $\\Delta_{2}^{\\rho} ≥ \\Omega(c)$, which links the risk difference to the mean difference. For SRM/DRM cases, this condition holds because they are defined by spectral/distortion weights. For UBSR/CERM cases with a linear utility, our result is still applicable. However, for nonlinear utility functions, the current change-of-measure argument is nontrivial unless we impose a specific characterization on utility functions. Hence, extending the lower bound to a general family of utility-based risk measures remains an open question, so we leave it for future work."}, {"review_id": "5pMPGAzXm2", "reviewer": "Reviewer_WLa4", "summary": "In this paper, the authors consider a problem of multi-armed bandit with heavy-tailed rewards and multi-risk measures, i.e., the performance of an algorithm is measured by multiple risk-sensitive measures, and the reward distributions are heavy-tailed. They provided asymptotic and minimax lower bounds for single-risk bandits with heavy-tailed rewards for some classes of risk measures (SRM and DRM). They derived a concentration inequality for Lipschitz risk measures, and proposed LCB-type algorithms called DistLCB (single-risk case) and MR-DistLCB (multi-risk case). Using real-world and synthetic datasets, they demonstrated MR-DistLCB overall outperforms the baselines.", "questions": "- Is there a discussion of lower bounds for the multi-risk case? Do the authors believe that MR-DistLCB is optimal?\n- Could you elaborate on technical challenges of the theoretical results (e.g. Theorem 4.4).\n- Theorem 6.3 focuses on SRM and DRM. How strong is this assumption? For example, in the domain of finance, are most popular risk measures covered by these classes of risk measures?", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "- Strengths\n    - The heavy-tailed reward and multi-risk setting would be important for practical applications (such as finance).\n    - The deviation inequality (Theorem 4.4 and Cor. 4.5) extends existing results for the heavy-tailed reward setting for a wide class of risk measures. \n    - Although this is a theoretical paper, the experiments are conducted using a real-world dataset. \n- Weaknesses\n    - As far as I understand, the lower bound analysis focuses on the single risk case. Therefore, the optimality of MR-DistLCB is unclear.\n    - Although theoretical results are novel, the technical challenges are unclear. For example, could you elaborate technical challenge of Theorem 4.4 (or other main results)?\n    - The proposed methods seem standard LCB-type algorithms, and there seems to be limited novelty in the algorithms.", "was_revised": true, "final_justification": "After the discussion phase, my questions and concerns have been resolved. Therefore, I will keep my positive rating.", "rebuttal": "Thank you for the thoughtful feedback. Our detailed responses are provided below.\n\n**Q1) Optimality of MR-DistLCB:** We expect the Pareto regret lower bound for the multi‑risk bandit to have the same asymptotic order as the single‑risk lower bound. Any single‑risk instance can be embedded in a multi‑risk environment by copying that one risk measure across all $k$ objectives; under this construction, the Pareto regret is identical to the single‑risk regret, so the single‑risk lower bound carries over unchanged. Because our upper bound in Theorem 6.7 matches that rate, we regard MR‑DistLCB as order‑optimal. At present, heavy‑tail single‑risk lower bounds exist only for SRM and DRM (Theorems 6.1 and 6.3), so a matching multi‑risk lower bound can currently be proved only for these two families (see Remark 6.4). Extending the lower‑bound machinery to utility‑based risks such as UBSR and CERM remains an open problem, which we will emphasise in the revised manuscript.\n\n**Q2) Theoretical Challenges:** Our work closes three previously open gaps. First, we establish the first exponential‑type deviation bound in $W_{1}$ for a median‑based distribution estimator under heavy‑tail distributions (Theorem 4.4), extending median inequalities from scalar means to full CDFs. Second, we introduce partial‑bootstrap MoEQ, which updates with just one new sample, rather than an entire independent block, yet still enjoys exponential guarantees under heavy‑tail distributions, making it the first median method that is both online‑practical and theoretically sound in the infinite‑variance regime. Third, we derive the first heavy‑tail information‑theoretic lower bounds for SRM and DRM; the core difficulty here is to find an explicit, tractable expression for the gap $\\Delta_{2}^{\\rho}\\ge\\Omega(c)$ that links the risk difference to a mean (or KL) difference so the change‑of‑measure argument can go through.  We achieve this for SRM/DRM using their spectral/distortion structure.\n\n**Q3) Generality of Lower Bounds:** Regarding the scope of **Theorem 6.3**, the restriction to **Spectral Risk Measures (SRM)** and **Distortion Risk Measures (DRM)** is far less limiting than it may appear.  These two *families* already subsume the risk measures that dominate practical finance and insurance work (Jokhadze & Schmidt 2020), for example:\n\n - **CVaR / Expected Shortfall** (Rockafellar & Uryasev 2000; Acerbi & Tasche 2002)\n - **Power‑spectral** and **Exponential‑spectral** measures (Dowd, K., Cotter, J., & Sorwar, G. 2008)\n - **Wang transform** (Gaussian distortion), **Proportional‑Hazard** transform $g(u)=u^{\\beta}$, **Dual‑Power** and **Beta** distortion families (Wang 1995; Wang et al. 1997)\n\nThese SRM and DRM families already embrace most coherent risks used in practice so establishing heavy‑tail lower bounds for them gives the theory broad practical reach. That said, an important next step is to extend the analysis to utility‑based risks such as UBSR and CERM; handling those measures will require additional regularity assumptions and is therefore left for future work.\n\n**References:**\n\n1. **Acerbi, C., & Tasche, D.** (2002). *Spectral measures of risk: A coherent representation of subjective risk aversion*. **Journal of Banking & Finance, 26**(7), 1505‑1518.\n\n2. **Rockafellar, R. T., & Uryasev, S.** (2000). *Optimization of Conditional Value‑at‑Risk*. **Journal of Risk, 2**, 21‑42.\n\n3. **Dowd, K., Cotter, J., & Sorwar, G.** (2008). Spectral risk measures: properties and limitations. ***Journal of Financial Services Research***, *34*(1), 61-75.\n\n4. **Jokhadze, V. & Schmidt, W. M.** (2020). Measuring model risk in financial risk management and pricing. ***International Journal of Theoretical and Applied Finance***, 23(2), 2050012.\n\n5. **Wang, S. S.** (1995). Insurance pricing and increased limits ratemaking by proportional hazards transforms. ***Insurance: Mathematics and Economics*, 17**, 43‑54.\n\n6. **Wang, S. S., Young, V. R., & Panjer, H. H.** (1997). *A class of distortion operators for pricing financial and insurance risks*. **Journal of Risk and Insurance, 64**(2), 211‑232."}, {"review_id": "Sjtj2uRPLz", "reviewer": "Reviewer_5zap", "summary": "In risk-sensitive applications such as quantitative finance or healthcare, where outcomes in the tails of the distribution—like rare but catastrophic events—are crucial. Classical bandit algorithms aim to maximize expected rewards, which limits their usefulness in these aforementioned risk-sensitive areas.\nThis paper proposes a new framework for tackling multi-risk agnostic multi-armed bandit problems with heavy-tailed reward function. While previous work has explored risk-aware bandits using measures like CVaR, mean-variance, or distortion risk, these methods typically optimize a single risk criterion and often assume light-tailed distributions. In contrast, this paper addresses the need to handle multiple risk measures simultaneously under heavy-tailed noise.\n\nTo this end, the paper presents a robust estimation method called the Median of Empirical Quantiles (MoEQ), which extends the median-of-means technique to quantile estimation. This estimator is compatible with a broad class of Lipschitz risk measures without requiring risk-specific confidence bounds. They also derive new deviation inequalities for the 1-Wasserstein distance, which allow the construction of confidence intervals even in heavy-tailed settings. These tools form the basis of a new algorithm, DistLCB, which gets optimal performance guarantees across a wide range of risk criteria. The algorithm is further extended to handle multi-risk objectives, and enables identification of Pareto-optimal actions rather than a single best arm. The paper then provides both gap-dependent and gap-independent regret bounds for this setting and also establishes asymptotic lower bounds with explicit dependence on sub-optimality gaps. Experimental results on synthetic and real-world data demonstrate the effectiveness of the proposed method.", "questions": "**1**\nWhile the core results are rigorous, some theoretical analyses (e.g., lower bounds) are limited to only SRM and DRM, leaving out UBSR and CERM. This restricts the generality of the claims, even though the algorithms themselves can handle arbitrary Lipschitz risk measures. Some aspects of the empirical evaluation, such as sensitivity to the tail index pp, are not deeply explored.\n\n**2** Sensitivity to Tail Index $p$\nIn heavy-tailed settings, the tail index $p$ seems to play an important role in determining both the difficulty of estimation and the tightness of regret bounds. For example, the convergence rate of the MoEQ estimator and the confidence width explicitly depend on $p$. Lower values of $p$ mean heavier tails, which should in principle make the problem harder. The regret bounds also degrade as $p \\to 1$. However, it seems the paper does not thoroughly investigate this in experiments. I think synthetic settings are totally fine. But I do think it is important for this work to show that the algorithm maintains performance across a range of tail indices, or at least discuss limitations if it doesn’t. Afterall, the core motivation of the paper is robustness under heavy tails. \n\n\n**[Minor issues]**\n**3** \nThis is very minor but I personally suggest it would be better to also explain why heavy-tailedness brings so much challenge to the risk-aware bandit. The paper should explicitly and briefly explain (in the Appendix perhaps) that, in light-tailed settings, the problem is significantly easier, and existing methods suffice. This will make the paper more self-contained and friendly to readers not familiar with the area of bandit.", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Quality**\n\nThe paper has a fine quality. It provides some novel statistical theoretical results. For example, the paper gives new deviation inequalities for the 1-Wasserstein distance under heavy-tailed distribution. It also introduces the DistLCB, which achieves near-optimality via the first lower bounds for certain types of risk-aware bandits. Overall, the theoretical results have a good quality with well-established theorems and mathematical analysis.\nRegarding the empirical results, the experiments look carefully designed to me and cover both synthetic and real-world datasets. The results also seem to support the theoretical claims. \n\n**Clarity**\n\nThe paper has good clarity. The mathematical definitions and assumptions are introduced in a clear manner without ambiguity, which is important for a theoretical work. It is great to see that the main theoretical results are accompanied with high-level explanations. \nThe notations are a bit heavy but I personally do not think there is room for huge improvement. \n\n**Significance**\nLinear Bandit is an important area of research in various fields such as statistics and computer science. \nThe paper tackles a highly relevant and underexplored problem in this area: how to perform risk-aware decision-making in multi-objective bandit settings when rewards are heavy-tailed. The heavy-tailedness is a big challenge because it prohibits the use of powerful concentration inequalities and makes the classical statistical estimator like quantile estimator unstably distributed.  \nThe results bridge multiple research directions—distributionally robust learning, heavy-tailed statistics, and multi-objective optimization—filling a clear gap in the literature.\n\n**Originality**\n\nThe paper is original in the following respects. It is the first to provide deviation inequalities for 1-Wasserstein distance under infinite-variance (heavy-tailed) settings. The MoEQ estimator represents a novel adaptation of median-of-means to quantile estimation. The DistLCB and MR-DistLCB algorithms offer a principled way to conduct exploration in multi-risk settings with strong theoretical backing. The lower bound results for SRM and DRM are also new contributions that extend existing bandit theory.", "was_revised": true, "final_justification": "I thank the authors for their rebuttal and followup.\nI appreciate the additional result on tail sensitivity is very informative. \nGiven all the update, I think positive of this paper and vote for accept.\nGood luck!", "rebuttal": "We are grateful for your careful reading and constructive suggestions. Our detailed responses are provided below.\n\n**Q1) Generality of Lower Bounds:** We acknowledge that our heavy‑tail lower bounds presently cover only Spectral Risk Measures (SRM) and Distortion Risk Measures (DRM), so UBSR and CERM remain open.  Nonetheless, SRM and DRM are families, not single functionals: they subsume virtually all coherent risks used in practice, including CVaR / Expected Shortfall (Rockafellar & Uryasev 2000; Acerbi & Tasche 2002), power‑ and exponential‑spectral measures (Dowd, K., Cotter, J., & Sorwar, G. 2008), and the Wang, Proportional‑Hazard, Dual‑Power, and Beta distortions (Wang 1995; Wang et al. 1997).  Establishing heavy‑tail lower bounds for these two broad classes therefore already gives our results considerable practical reach, while extending the theory to utility‑based risks such as UBSR and CERM, whose proofs require additional regularity assumptions, remains an important direction for future work.\n\n**Q2) Sensitivity to Tail Index:** Thank you for pointing this out. We agree that showing results for additional tail indices would be informative. Because of space constraints we focused on the extreme heavy‑tail case $p=1.2$ (close to the limit case $p\\to1$) to highlight the algorithm’s robustness where existing methods struggle. During the discussion period we will run and report supplementary experiments for additional indices between $1$ and $1.5$ (e.g. $p=1.1$ and $p=1.5$) to illustrate how performance evolves as the distribution approaches the light‑tailed regime.\n\n**Q3) Heavy‑Tail Difficulty:** Thank you for the suggestion. Appendix B (“Detailed Comparison of Prior Work”) already contrasts light‑ and heavy‑tailed settings, but we will tighten that subsection by adding a brief, reader‑friendly note clarifying that light‑tailed rewards admit sub‑Gaussian concentration, so classic UCB analyses suffice, whereas heavy tails lack such exponential tails and thus require robust estimators like MoEQ. This addition should make the paper more accessible to readers new to risk‑aware bandits."}]

Author rebuttal:

Meta-review: This paper studies the risk-agnostic bandit problem with multiple risk measures for heavy-tailed rewards. The paper introduces the framework of risk measures based on Lipschitz continuity with respect to Wasserstein distance and proposes a novel estimator MoEQ with its deviation inequality, which can be of independent interest. Based on this estimator, algorithms are proposed with instance-dependent and -independent regret bounds.  

While reviewers raised several concerns such as the required number of samples and the one from the practical viewpoints, they largely agreed with the opinion that the technique of the new estimator is significant. I agree with these opinions after my own reading; while I felt that just considering the Pareto regret needs more motivation and justification rather than borrowing [28], the technique of MoEQ is indeed very interesting. I expect that the authors further polish the paper in the final version by appropriately incorporating the discussion with the reviewers.
Decision: Accept (poster)