Introduction
The Multi-Armed Bandit framework is a fundamental paradigm for sequential decision-making under uncertainty. In the vast majority of this literature [26 , 5 ] , the objective is to minimize appropriately defined regret, which depends simply on the mean of the reward distribution associated with the arm pulled. However, in real-world applications—ranging from clinical trials to financial portfolio optimization—the mean does not satisfactorily capture the merits of certain actions, especially when humans are involved in the decision. See [36 ] for a recent survey.
In such applications, risk plays an important role, and a risk-aware performance measure is often preferred over the average reward. Consequently, significant research has focused on diverse risk measures, including mean-variance (MV) [28 ] , Value-at-Risk (VaR) [3 ] , Conditional Value-at-Risk (CVaR) [3 , 32 ] , spectral risk measures [2 ] , and utility-based shortfall risk [3 , 19 ] . While these measures satisfy axioms of coherence or convexity, they often fail to model the nuances of human behavior, such as loss aversion and asymmetric preferences, which are best captured by the celebrated (and Nobel prize-winning) risk measure Cumulative Prospect Theory (CPT) [39 ] . The failure of standard risk measures is structural. MV penalizes all variance equally, treating rare massive gains and catastrophic losses identically. CVaR only examines the lower tail of the reward distribution, so rare disasters are averaged with ordinary outcomes when their probability is below the chosen tail level, while attractive lottery gains are not its focus. CPT avoids both failures through nonlinear probability weighting — a 1% chance of a fatal crash carries disproportionate psychological weight far exceeding 0.01. This amplification of rare events means CPT simultaneously penalizes hidden disasters and values rare large gains, capturing the two asymmetric behaviors that characterize human decision-making under uncertainty.
To further motivate the necessity of CPT risk, consider the challenge of automated policy design motivated by the Asian Disease Problem [21 ] . Consider an agent tasked with optimizing a Public Health Score r r r (e.g., the number of lives saved). The agent must choose between two policies: a “Safe” protocol guaranteeing that 200 lives are saved (r = 200 r = 200 r = 200 ), and a “Risky” protocol with a 35% chance of saving 600 lives (r = 600 r = 600 r = 600 ) and a 65% chance of saving none (r = 0 r = 0 r = 0 ). A standard risk-neutral agent calculates the averages as μ R i s k y = 210 > μ S a f e = 200 \mu_{\mathrm{Risky}} = 210 > \mu_{\mathrm{Safe}} = 200 μ Risky = 210 > μ Safe = 200 , therefore identifying the risky protocol as optimal . However, empirical evidence shows that the vast majority of human decision-makers reject this gamble [39 ] and choose the safe protocol. This reveals a critical insight: the standard method of maximizing the mean reward is misaligned with human ethical and behavioral preferences.
CPT addresses this misalignment by evaluating actions not through a simple average, but through a distorted value V a ( f ) : = ∫ 0 ∞ w ( 1 − F a f ( z ) ) d z − ∫ 0 ∞ w ( F a f ( − z ) ) d z \mathcal{V}_a(f) := \int_{0}^{\infty} w(1-F_a^f(z))\mathrm{d}z - \int_{0}^{\infty} w(F_a^f(-z))\mathrm{d}z V a ( f ) := ∫ 0 ∞ w ( 1 − F a f ( z )) d z − ∫ 0 ∞ w ( F a f ( − z )) d z , where w ( ⋅ ) w(\cdot) w ( ⋅ ) is a non-linear weight (distortion) function applied to the cumulative distribution F X ( ⋅ ) F_X(\cdot) F X ( ⋅ ) . Note that if w ( ⋅ ) w(\cdot) w ( ⋅ ) is an identity function, we get the standard average, i.e., V ( X ) = E ( X ) \mathcal{V}(X) = \mathbb{E}(X) V ( X ) = E ( X ) . In the above-mentioned example, V S a f e = 200 \mathcal{V}_{\mathrm{Safe}} = 200 V Safe = 200 while V R i s k y = 600 w ( 0.35 ) \mathcal{V}_{\mathrm{Risky}} = 600w(0.35) V Risky = 600 w ( 0.35 ) . Hence the safe action is the subjective optimum precisely when w ( 0.35 ) < 1 / 3 w(0.35) < 1/3 w ( 0.35 ) < 1/3 . For instance, using the Tversky–Kahneman weighting form with γ = 0.5 \gamma= 0.5 γ = 0.5 gives w ( 0.35 ) ≈ 0.303 w(0.35) \approx0.303 w ( 0.35 ) ≈ 0.303 , and therefore V m a t h r m R i s k y ≈ 182 < 200 = V S a f e \mathcal{V}_{\\mathrm{Risky}} \approx182 < 200 = \mathcal{V}_{\mathrm{Safe}} V ma t h r m R i s k y ≈ 182 < 200 = V Safe . In general, with distorted weights, the sequence of actions chosen may differ from that under the risk-neutral measure. To demonstrate this distinction empirically, we construct instances in which risk-neutral and risk-sensitive objectives lead to systematically different decisions, with the separation persisting across repeated trials (see, Figure 1 (a)-(Figure 1 b)).
Figure 1. Risk preferences and CPT learning. (a)–(b) Population objective scores in Config B (rare loss) and Config E (rare gain). CVaR uses α = 0.10 \alpha= 0.10 α = 0.10 , MV uses c = 1 c = 1 c = 1 , and CPT uses identity utility and Tversky–Kahneman weighting with γ = 0.50 \gamma= 0.50 γ = 0.50 . (c) Bounded 2D kernel comparison on logarithmic axes: mean cumulative CPT regret ± \pm ± one standard error over 30 paired trials. Dashed lines are descriptive power-law fits.
Significant research has focused on diverse risk measures in the multi-armed bandit setting. For instance, [34 , 45 , 16 ] study the Mean-Variance setup extensively for K K K -armed bandits. [44 ] analyzes Value-at-Risk (VaR) in the context of the total reward sequence. [14 , 40 , 42 , 22 ] utilize the Conditional Value-at-Risk (CVaR) measure in K K K -armed Bandit setting. [23 ] proposes a distribution-oblivious algorithm for optimizing a linear combination of mean and CVaR, specifically for unbounded reward distributions in the best-arm identification setting. For Kernel bandits, [37 ] study the standard Upper Confidence Bound (UCB) type algorithms for CVaR and Mean-Variance risk measures and prove near-optimal results. To provide a systematic analysis of such metrics, [11 ] introduced a unified framework for multi-armed bandits under general risk satisfying a Lipschitz continuity condition with respect to probability distributions (e.g., in the Wasserstein distance). However, the CPT function is generally not Lipschitz continuous [36 ] , often causing the value to fluctuate wildly with small distribution changes. This lack of stability prevents the direct application of existing unified frameworks to CPT.
To the best of our knowledge, bandit optimization with CPT-based risk measures has been limited. Prior works have used CPT-based risk-sensitive measures for simple K K K -armed and linear bandits [13 ] , and achieve near-optimal regret bounds. Recently, [TMA^+25] proposes a unified framework for distortion risk measures in the K K K -armed bandit setting, covering both monotone and non-monotone distortions and showing that, for certain non-monotone objectives, an optimal policy may require a mixture of arms. However, their analysis is primarily focused on finite K K K -armed bandits, whereas our interest is in continuous action spaces and general non-parametric reward functions. Moreover, CPT introduces a distinct nonlinear probability distortion that is not covered by their mixture-based analysis. This leaves a theoretical gap in CPT optimization for non-parametric function classes. This prompts the central question of our work:
Is it possible to learn (general) non-parametric (including Kernel) bandits with CPT risk measure?
In this paper, we answer this question affirmatively. We analyze a learning algorithm, namely Non-Parametric CPT-Bandits (NPCB), that works for general functional bandits with the CPT risk measure. Notably, NPCB is agnostic to (non-parametric) function class and uses the Eluder Dimension [31 ] to characterize the complexity of the learning task. As a primary instantiation of our framework, we study Kernel bandits and obtain guarantees for Kernel CPT (KCB) algorithm. To the best of our knowledge, this is the first work to study Kernel Bandits (RKHS) under a CPT-based risk measure.
Summary of contributions
Non-parametric CPT bandits: We propose a learning algorithm with CPT-based risk for general, non-parametric bandits, namely NPCB. Our formulation captures continuous action spaces with arm-dependent noise. For this general setup, we derive the regret bound (refer to Theorem 4.2 ) which matches the order-wise performance of risk-neutral non-parametric bandits [31 ] . This demonstrates that non-linear human-centric risk measures can be incorporated into infinite-dimensional function learning without incurring a regret penalty.
Kernel CPT bandits: For an RKHS mean-reward class and known arm-dependent noise CDFs, we give kernel algorithms for CPT regret. Our phasewise procedure achieves O ~ ( T γ T ( λ ) ) \widetilde{O}\left(\sqrt{T\gamma_T(\lambda)}\right) O ( T γ T ( λ ) ) regret, matching the standard risk-neutral dependence on information-gain.
Modular Algorithm: Our algorithms decouple the Learning Module (mean estimation from undistorted rewards) from the Decision Module (CPT valuation). This makes our framework function-class-agnostic, allowing it to be seamlessly applied to any function class (e.g., Linear, RKHS, or Neural Nets), provided a valid confidence set can be constructed.
CPT stability for non-parametric learning: Building on the translation stability of [13 ] , we connect CPT uncertainty to confidence widths for general mean-function classes. Under additive noise, the CPT value is uniformly 2-Lipschitz in the mean, even without Hölder continuity of the weighting function1 . This connects CPT regret to the Eluder dimension and covering numbers, and supports our kernel instantiations.
Removing Known CDF assumption: For the case of linear bandits, [20 Section V, Remark 10] require the knowledge of the cumulative distribution function of the noise, remarking that online estimation of the CDF is an open problem left for future work. We learn the noise CDF online using a joint likelihood confidence set. The regret keeps the mean-learning term and adds a cost governed by joint distributional complexities. We bound these complexities for an explicit linear family and its RKHS extension.
Problem Formulation
We consider the sequential decision-making problem over a finite time horizon T T T , characterized by a compact and continuous action space A ⊆ R d \mathcal{A} \subseteq\mathbb{R}^{d} A ⊆ R d , which may be infinite. The environment is governed by an unknown true mean-reward function f ⋆ : A → R f^{\star}:\mathcal{A} \to\mathbb{R} f ⋆ : A → R , which belongs to a known class of non-parametric functions of real-valued functions F \mathcal{F} F . The value f ⋆ ( a ) f^{\star}(a) f ⋆ ( a ) represents the expected reward associated with action a ∈ A a \in\mathcal{A} a ∈ A . At each step t t t , the agent selects an action a t ∈ A a_t \in\mathcal{A} a t ∈ A based on the history of previous observations D t − 1 = { ( a τ , r τ ) } τ = 1 t − 1 \mathcal{D}_{t-1} = \{(a_\tau, r_\tau)\}_{\tau=1}^{t-1} D t − 1 = {( a τ , r τ ) } τ = 1 t − 1 . The environment then reveals a realized physical reward r t = f ∗ ( a t ) + ϵ t r_t = f^*(a_t) + \epsilon_t r t = f ∗ ( a t ) + ϵ t .
Unlike the standard bandit formulation, we allow arm-dependent noise . Conditional on the history and the selected arm a t = a a_t = a a t = a , the noise ϵ t \epsilon_t ϵ t has a fixed distribution F ϵ a F_{\epsilon_a} F ϵ a with mean zero. For a candidate f ∈ F f \in\mathcal{F} f ∈ F , the corresponding reward CDF is F a f ( z ) = F ϵ a ( z − f ( a ) ) F_a^f(z) = F_{\epsilon_a}(z - f(a)) F a f ( z ) = F ϵ a ( z − f ( a )) . We assume that these candidate reward distributions are supported in [ − M , M ] [-M, M] [ − M , M ] .
While the agent observes undistorted rewards r t r_t r t drawn from the distribution defined by F ϵ a F_{\epsilon_a} F ϵ a , its decision is governed by a subjective distortion of these probabilities. This distortion is parameterized by weight function w : [ 0 , 1 ] → [ 0 , 1 ] \mathsf{w} : [0, 1] \to[0, 1] w : [ 0 , 1 ] → [ 0 , 1 ] . We define the weight-distorted reward, denoted by V a ( f ) \mathcal{V}_a(f) V a ( f ) , by applying the distortion w \mathsf{w} w to the cumulative probabilities of the reward distribution as
V a ( f ) : = ∫ 0 ∞ w ( 1 − F a f ( z ) ) d z − ∫ 0 ∞ w ( F a f ( − z ) ) d z \mathcal{V}_a(f) := \int_0^\infty\mathsf{w}\left(1 - F_a^f(z)\right)\,\mathrm{d}z - \int_0^\infty\mathsf{w}\left(F_a^f(-z)\right)\,\mathrm{d}z V a ( f ) := ∫ 0 ∞ w ( 1 − F a f ( z ) ) d z − ∫ 0 ∞ w ( F a f ( − z ) ) d z
The weight function w : [ 0 , 1 ] → [ 0 , 1 ] \mathsf{w} : [0, 1] \to[0, 1] w : [ 0 , 1 ] → [ 0 , 1 ] is the behavioral core of CPT. Beyond the minimal conditions w ( 0 ) = 0 \mathsf{w}(0) = 0 w ( 0 ) = 0 , w ( 1 ) = 1 \mathsf{w}(1) = 1 w ( 1 ) = 1 , and monotone increasing [39 , 13 ] , we impose no additional assumptions. Together with the bounded-reward assumption above, w ( 0 ) = 0 \mathsf{w}(0) = 0 w ( 0 ) = 0 ensures that V a ( f ) \mathcal{V}_a(f) V a ( f ) is finite. Several families of w \mathsf{w} w satisfying these properties are widely used in behavioral economics, including the Tversky–Kahneman function [39 ] w ( p ) = p γ / ( p γ + ( 1 − p ) γ ) 1 / γ \mathsf{w}(p) = p^\gamma/ (p^\gamma+ (1-p)^\gamma)^{1/\gamma} w ( p ) = p γ / ( p γ + ( 1 − p ) γ ) 1/ γ , the Prelec function [30 ] w ( p ) = exp ( − ( ln 1 / p ) α ) \mathsf{w}(p) = \exp(-( \ln1/p)^\alpha) w ( p ) = exp ( − ( ln 1/ p ) α ) , and the Gonzalez–Wu function [15 ] w ( p ) = δ p γ / ( δ p γ + ( 1 − p ) γ ) \mathsf{w}(p) = \delta p^\gamma/ (\delta p^\gamma+ (1-p)^\gamma) w ( p ) = δ p γ / ( δ p γ + ( 1 − p ) γ ) . Our framework accommodates all of these. A detailed discussion of the behavioral interpretation of w \mathsf{w} w , its effect on V \mathcal{V} V is provided in Appendix § 14 .
Remark 2.1. For simplicity, we use reference point 0, identity utility, and a common probability weight for gains and losses. The theory extends to a fixed reference point x 0 x_0 x 0 , separate weights w + \mathsf{w}^{+} w + , and nondecreasing L ± \mathsf{L}^{\pm} L ± -Lipschitz gain/loss utilities. These extensions change only constant factors, as detailed in Appendix § 10 .§ 2 .
CPT Regret. The agent’s objective is to maximize the cumulative subjective, weight-distorted value of the rewards gathered over the horizon. Formally, under the true mean-reward function f ∗ f^* f ∗ and distortion mapping w ( ⋅ ) \mathsf{w}(\cdot) w ( ⋅ ) , we denote the subjectively optimal arm as, a ∗ ∈ arg max a ∈ A V a ( f ∗ ) a^* \in\arg\max_{a \in\mathcal{A}} \mathcal{V}_a(f^*) a ∗ ∈ arg max a ∈ A V a ( f ∗ ) . The goal of learning is to maintain a policy that competes with this optimum through sequential interaction with the environment. The performance of the learning policy is evaluated by its cumulative weight-distorted regret (CPT regret), given by
R ( T ) = ∑ t = 1 T ( V a ∗ ( f ∗ ) − V a t ( f ∗ ) ) . R(T) = \sum_{t=1}^{T}\left(\mathcal{V}_{a^*}(f^*) - \mathcal{V}_{a_t}(f^*)\right). R ( T ) = t = 1 ∑ T ( V a ∗ ( f ∗ ) − V a t ( f ∗ ) ) .
Remark 2.2. Designing such an algorithm is challenging because the agent observes samples from the undistorted distribution but must optimize the distorted value V a ( f ∗ ) \mathcal{V}_a(f^*) V a ( f ∗ ) . The non-linear transformation w ( ⋅ ) \mathsf{w}(\cdot) w ( ⋅ ) prevents the estimation of V a \mathcal{V}_a V a through the sample mean of r t r_t r t . The distortion can inflate the impact of tail events in F ϵ a F_{\epsilon_a} F ϵ a , potentially changing the preference order between arms.
Non-parametric CPT bandits (NPCB)
We now present our learning algorithm. Our approach follows the general template of optimistic exploration for general function classes, as discussed by [31 ] , but fundamentally deviates from it in the arm-selection step to accommodate the agent’s behavioral preferences.
Algorithm 1: Non-Parametric CPT Bandits (NPCB)
Input: F \mathcal{F} F , known noise CDFs, and { β t } \{\beta_t\} { β t } .
for t = 1 t = 1 t = 1 to T T T do
Set f ^ t L S ∈ arg min f ∈ F ∑ s < t ( r s − f ( a s ) ) 2 \hat{f}^{\mathrm{LS}}_t \in\arg\min_{f \in\mathcal{F}} \sum_{s<t}(r_s-f(a_s))^2 f ^ t LS ∈ arg min f ∈ F ∑ s < t ( r s − f ( a s ) ) 2 .
Set C t = { f ∈ F : ∑ s < t ( f ( a s ) − f ^ t L S ( a s ) ) 2 ≤ β t } C_t = \{f \in\mathcal{F}: \sum_{s<t}(f(a_s)-\hat{f}^{\mathrm{LS}}_t(a_s))^2 \le\beta_t\} C t = { f ∈ F : ∑ s < t ( f ( a s ) − f ^ t LS ( a s ) ) 2 ≤ β t } .
Choose a t ∈ arg max a ∈ A sup f ∈ C t V a ( f ) a_t \in\arg\max_{a \in\mathcal{A}} \sup_{f \in C_t} V_a(f) a t ∈ arg max a ∈ A sup f ∈ C t V a ( f ) .
Observe r t r_t r t .
end for
Design Philosophy. At the start of each round t t t , the algorithm constructs a least squares estimate , f ^ t L S ∈ arg min f ∈ F ∑ τ = 1 t − 1 ( f ( a τ ) − r τ ) 2 \hat{f}^{\mathrm{LS}}_t \in\arg\min_{f \in\mathcal{F}}\sum_{\tau=1}^{t-1}(f(a_\tau)-r_\tau)^2 f ^ t LS ∈ arg min f ∈ F ∑ τ = 1 t − 1 ( f ( a τ ) − r τ ) 2 , which minimizes the cumulative squared prediction error on the history of observations D t − 1 \mathcal{D}_{t-1} D t − 1 . To quantify the uncertainty around this estimate, we employ the empirical 2-norm , ∥ ⋅ ∥ 2 , D t \lVert\cdot\rVert_{2,\mathcal{D}_t} ∥ ⋅ ∥ 2 , D t . For any function g g g , this is defined as ∥ g ∥ 2 , D t 2 = ∑ τ = 1 t − 1 g 2 ( a τ ) \lVert g\rVert^2_{2,\mathcal{D}_t}=\sum_{\tau=1}^{t-1}g^2(a_\tau) ∥ g ∥ 2 , D t 2 = ∑ τ = 1 t − 1 g 2 ( a τ ) . Using this metric, we construct a confidence set C t C_t C t centered at the estimate: C t : = { f ∈ F : ∥ f − f ^ t L S ∥ 2 , D t − 1 ≤ β t } C_t:=\{f\in\mathcal{F}:\lVert f-\hat{f}^{\mathrm{LS}}_t\rVert_{2,\mathcal{D}_{t-1}}\le\sqrt{\beta_t}\} C t := { f ∈ F : ∥ f − f ^ t LS ∥ 2 , D t − 1 ≤ β t } . Here, β t \beta_t β t is an appropriately chosen confidence parameter that ensures the true function f ∗ f^* f ∗ lies within C t C_t C t with high probability. The algorithm operates by maintaining this statistically plausible set of environments and selecting actions based on the principle of Optimism in the Face of Uncertainty . However, unlike standard algorithms that select the arm with the highest optimistic mean, our algorithm selects the arm a t a_t a t that maximizes the optimistic weight-distorted reward feasible within the confidence set C t C_t C t : a t = arg max a ∈ A sup f ∈ C t V a ( f ) a_t=\arg\max_{a\in\mathcal{A}}\sup_{f\in C_t}V_a(f) a t = arg max a ∈ A sup f ∈ C t V a ( f ) . The pseudocode for the proposed method is provided in Algorithm 1.
Modular Design and Function-Class Agnostic Extension. As mentioned earlier, NPCB is modular, which strictly separates the CPT-based behavioral preferences from the statistical learning of the environment (e.g., [13 ] ). In Algorithm 1, lines 3-4 are for confidence set construction and environment learning, whereas lines 5-6 are used for CPT valuation and choice of action.
Computational Complexity. We note that for general function classes, solving max a ∈ A sup f ∈ C t V a ( f ) \max_{a\in\mathcal{A}}\sup_{f\in C_t}V_a(f) max a ∈ A sup f ∈ C t V a ( f ) is computationally hard in general [31 ] . For the kernel algorithms, posterior updates use the usual kernel matrices. We focus on statistical regret and assume access to the displayed arm maximizers; for the phasewise continuous-domain result, we use the finite discretization described in § 5.2 .
Main Results
In this section, we provide the theoretical analysis of our algorithm. We first introduce a complexity measure for general function classes, then construct valid confidence sets, and finally derive the regret bounds in terms of Eluder Dimension.
Complexity Measure: We utilize the concept of Eluder dimension , first introduced by [31 ] . Intuitively, this measure captures the worst-case difficulty of inferring unobserved values. A low Eluder dimension implies that observing a few points allows for accurate global predictions, whereas a high dimension suggests the function can exhibit “surprising” variations even after many observations.
Definition 4.1 (Eluder Dimension [31 ] ). An action a a a is ε \varepsilon ε -independent of a history { a 1 , … , a n } \{a_1,\ldots,a_n\} { a 1 , … , a n } with respect to F \mathcal{F} F if there exist f , f ~ ∈ F f,\widetilde{f}\in\mathcal{F} f , f ∈ F that are close on the history ( ∑ i = 1 n ( f ( a i ) − f ~ ( a i ) ) 2 ≤ ε ) \left(\sqrt{\sum_{i=1}^{n}(f(a_i)-\widetilde{f}(a_i))^2}\leq\varepsilon\right) ( ∑ i = 1 n ( f ( a i ) − f ( a i ) ) 2 ≤ ε ) yet differ significantly at the new action ( ∣ f ( a ) − f ~ ( a ) ∣ > ε ) \left(\lvert f(a)-\widetilde{f}(a)\rvert>\varepsilon\right) ( ∣ f ( a ) − f ( a )∣ > ε ) . The Eluder dimension dim E ( F , ε ) \dim_E(\mathcal{F},\varepsilon) dim E ( F , ε ) is the length of the longest sequence a 1 , … , a d a_1,\ldots,a_d a 1 , … , a d such that for some ε ′ ≥ ε \varepsilon'\geq\varepsilon ε ′ ≥ ε , every element a k a_k a k is ε ′ \varepsilon' ε ′ -independent of its predecessors { a 1 , … , a k − 1 } \{a_1,\ldots,a_{k-1}\} { a 1 , … , a k − 1 } .
To bound the regret of NPCB, we maintain a set C t \mathcal{C}_t C t of functions that are consistent with the observed data. The agent picks the action that looks best under the most optimistic function in C t \mathcal{C}_t C t , so the regret at each round is simply how uncertain we are about the chosen arm. We refer to this gap as the distorted width , formally defined as w C t V ( a ) : = sup f ∈ C t V a ( f ) − inf f ∈ C t V a ( f ) w^{\mathcal{V}}_{\mathcal{C}_t}(a):=\sup_{f\in\mathcal{C}_t}\mathcal{V}_a(f)-\inf_{f\in\mathcal{C}_t}\mathcal{V}_a(f) w C t V ( a ) := sup f ∈ C t V a ( f ) − inf f ∈ C t V a ( f ) . The central technical challenge is controlling this width: since V a ( f ) \mathcal{V}_a(f) V a ( f ) involves a non-linear distortion w ( ⋅ ) w(\cdot) w ( ⋅ ) , it is not obvious that shrinking the statistical uncertainty in f f f translates to shrinking the subjective CPT uncertainty. We resolve this by establishing that the CPT functional is uniformly 2-Lipschitz in the mean reward without any assumption on w ( ⋅ ) w(\cdot) w ( ⋅ ) (Proposition B.3 ), which immediately bounds the distorted width by the plain statistical width of C t \mathcal{C}_t C t up to a constant factor (Appendix § 9 , Lemma B.2 ). This reduces CPT regret to a standard width-shrinkage problem on w C t ( a ) w_{\mathcal{C}_t}(a) w C t ( a ) , to which the Eluder dimension machinery applies directly.
Regret for NPCB
Theorem 4.2 (General Regret for NPCB). Under the additive reward model, with probability at least 1 − δ 1-\delta 1 − δ , the cumulative CPT regret R ( T ) R(T) R ( T ) satisfies
R ( T ) ≤ O ~ ( T dim E ( F , T − 2 ) ⋅ log N ( F , T − 2 , ∥ ⋅ ∥ ∞ ) + log ( 1 / δ ) ) . R(T)\leq\widetilde{O}\left(\sqrt{T\dim_E(\mathcal{F},T^{-2})}\cdot\sqrt{\log\mathcal{N}(\mathcal{F},T^{-2},\|\cdot\|_\infty)+\log(1/\delta)}\right). R ( T ) ≤ O ( T dim E ( F , T − 2 ) ⋅ log N ( F , T − 2 , ∥ ⋅ ∥ ∞ ) + log ( 1/ δ ) ) .
Proof Strategy: The bound follows by invoking the cumulative width bound of [31 ] on the standard width, after absorbing the CPT distortion via the 2-Lipschitz stability of Proposition B.3 . The CPT factor of 2 does not affect the leading rate.
A discussion of lower bounds and tightness is provided in Appendix § 11 .
Extension: Learning the Noise CDF Online (NPCB-Learned)
We now drop the assumption that the arm-dependent noise CDF is known. The mean-reward class remains F \mathcal{F} F , while the true noise CDF F F F belongs to a known class H \mathcal{H} H . For each h ∈ H h\in\mathcal{H} h ∈ H , let p h ( ⋅ ∣ a ) p_h(\cdot\mid a) p h ( ⋅ ∣ a ) denote its noise density at arm a a a . Every p h ( ⋅ ∣ a ) p_h(\cdot\mid a) p h ( ⋅ ∣ a ) is zero mean, supported on the common interval [ − s , s ] [-s,s] [ − s , s ] , and satisfies 0 < p min ≤ p h ( z ∣ a ) ≤ p max 0<p_{\min}\leq p_h(z\mid a)\leq p_{\max} 0 < p m i n ≤ p h ( z ∣ a ) ≤ p m a x on this support. We also assume ∣ f ( a ) ∣ ≤ B f \lvert f(a)\rvert\leq B_f ∣ f ( a )∣ ≤ B f for all f ∈ F f\in\mathcal{F} f ∈ F and a ∈ A a\in\mathcal{A} a ∈ A , so rewards are bounded by B f + s B_f+s B f + s . The assumptions on the CPT weight w w w are unchanged.
A candidate pair ( f , h ) (f,h) ( f , h ) induces reward density q f , h ( r ∣ a ) = p h ( r − f ( a ) ∣ a ) q_{f,h}(r\mid a)=p_h(r-f(a)\mid a) q f , h ( r ∣ a ) = p h ( r − f ( a ) ∣ a ) and reward CDF G f , h ( z ∣ a ) = h ( z − f ( a ) ∣ a ) G_{f,h}(z\mid a)=h(z-f(a)\mid a) G f , h ( z ∣ a ) = h ( z − f ( a ) ∣ a ) . Let Q \mathcal{Q} Q and G \mathcal{G} G denote the resulting density and CDF classes. Write N o p t ( Q , 1 / T ) \mathcal{N}_{\mathrm{opt}}(\mathcal{Q},1/T) N opt ( Q , 1/ T ) for the upper-density covering number of Q \mathcal{Q} Q , and define β H = log 2 N o p t ( Q , 1 / T ) δ 0 + 1 \beta^{\mathcal{H}}=\log\frac{2\mathcal{N}_{\mathrm{opt}}(\mathcal{Q},1/T)}{\delta_0}+1 β H = log δ 0 2 N opt ( Q , 1/ T ) + 1 , and D = min { dim E ( G , d ⋅ , 1 / T ) , T } D=\min\{\dim_E(\mathcal{G},d_{\cdot},1/T),T\} D = min { dim E ( G , d ⋅ , 1/ T ) , T } , where d a ( G 1 , G 2 ) = sup z ∣ G 1 ( z ∣ a ) − G 2 ( z ∣ a ) ∣ d_a(G_1,G_2)=\sup_z\lvert G_1(z\mid a)-G_2(z\mid a)\rvert d a ( G 1 , G 2 ) = sup z ∣ G 1 ( z ∣ a ) − G 2 ( z ∣ a )∣ .
At round t t t , NPCB-Learned keeps the usual mean confidence set C t C_t C t and additionally forms a joint likelihood set M t ⊆ F × H \mathcal{M}_t \subseteq\mathcal{F} \times\mathcal{H} M t ⊆ F × H . The latter retains all pairs whose log-likelihood is at most β H \beta^{\mathcal{H}} β H below the maximum likelihood. The algorithm then chooses the arm with the largest CPT value over pairs that are plausible under both confidence sets. The full algorithm is given in Appendix § 15 . Write w C t ( a ) = sup f 1 , f 2 ∈ C t ∣ f 1 ( a ) − f 2 ( a ) ∣ w_{C_t}(a) = \sup_{f_1,f_2 \in C_t} \lvert f_1(a) - f_2(a) \rvert w C t ( a ) = sup f 1 , f 2 ∈ C t ∣ f 1 ( a ) − f 2 ( a )∣ .
Theorem 4.5 (NPCB-Learned regret). Suppose f ∗ ∈ C t f^* \in C_t f ∗ ∈ C t for every t ≤ T t \le T t ≤ T with probability at least 1 − δ 1-\delta 1 − δ . Then, with probability at least 1 − δ − δ 0 1-\delta-\delta_0 1 − δ − δ 0 (for a constant C C C ),
R ( T ) ≤ C ( 1 + p max p min ) ∑ t = 1 T w C t ( a t ) + C p min ( 1 + D + D β H T ) . R(T) \le C\left(1+\frac{p_{\max}}{p_{\min}}\right)\sum_{t=1}^{T} w_{C_t}(a_t)+\frac{C}{p_{\min}}\left(1+D+\sqrt{D\beta^{\mathcal{H}}T}\right). R ( T ) ≤ C ( 1 + p m i n p m a x ) t = 1 ∑ T w C t ( a t ) + p m i n C ( 1 + D + D β H T ) .
The first term is the usual mean-learning contribution; the second is the additional cost of learning the noise distribution. For the least-squares confidence sets, the first term uses the same mean-width analysis as in the known-CDF case, with reward bound B f + s B_f+s B f + s .
The density constants are explicit in the bound and can be large for sparse-tail distributions. Thus the theorem gives a uniform guarantee over the stated class, but need not give a tight numerical prediction for rare-event instances.
Concrete linear example. Let f u ( a ) = ⟨ u , x ( a ) ⟩ f_u(a) = \langle u,x(a)\rangle f u ( a ) = ⟨ u , x ( a )⟩ , with ∥ u ∥ 2 ≤ B \lVert u\rVert_2 \le B ∥ u ∥ 2 ≤ B and ∥ x ( a ) ∥ 2 ≤ 1 \lVert x(a)\rVert_2 \le1 ∥ x ( a ) ∥ 2 ≤ 1 , and let ∥ ψ ( a ) ∥ 2 ≤ 1 \lVert\psi(a)\rVert_2 \le1 ∥ ψ ( a ) ∥ 2 ≤ 1 . For v ∈ R k v \in\mathbb{R}^k v ∈ R k , ∥ v ∥ 2 ≤ 1 \lVert v\rVert_2 \le1 ∥ v ∥ 2 ≤ 1 , consider
p v ( z ∣ a ) = 1 2 s [ 1 + ⟨ v , ψ ( a ) ⟩ ( z 2 s 2 − 1 3 ) ] 1 { ∣ z ∣ ≤ s } . p_v(z \mid a) = \frac{1}{2s}\left[1+\langle v,\psi(a)\rangle\left(\frac{z^2}{s^2}-\frac{1}{3}\right)\right]\mathbf{1}\{|z|\le s\}. p v ( z ∣ a ) = 2 s 1 [ 1 + ⟨ v , ψ ( a )⟩ ( s 2 z 2 − 3 1 ) ] 1 { ∣ z ∣ ≤ s } .
These are zero-mean arm-dependent densities. For fixed B , s B,s B , s , log N o p t ( Q , 1 / T ) = O ( ( d + k ) log T ) \log N_{\mathrm{opt}}(\mathcal{Q},1/T)=O((d+k)\log T) log N opt ( Q , 1/ T ) = O (( d + k ) log T ) and D = O ( ( d + k ) log T ) D=O((d+k)\log T) D = O (( d + k ) log T ) , giving R ( T ) = O ~ ( ( d + k ) T ) R(T)=\widetilde{O}((d+k)\sqrt{T}) R ( T ) = O (( d + k ) T ) . Thus, when k = O ( d ) k=O(d) k = O ( d ) , learning the noise preserves the known-CDF linear rate. This symmetric family illustrates the complexity calculation; symmetry is not an assumption of the general theorem. Asymmetric zero-mean noise classes are also permitted when they satisfy the stated density and complexity conditions.
Special cases: Linear & Kernel CPT bandits
Linear CPT Bandits
For the linear bandit setting, F = { ⟨ ⋅ , θ ⟩ : θ ∈ Θ } \mathcal{F}=\{\langle\cdot,\theta\rangle:\theta\in\Theta\} F = {⟨ ⋅ , θ ⟩ : θ ∈ Θ } with f θ ( a ) = ⟨ θ , a ⟩ f_\theta(a)=\langle\theta,a\rangle f θ ( a ) = ⟨ θ , a ⟩ , θ ∈ R d \theta\in\mathbb{R}^d θ ∈ R d , where θ ∈ R d \theta\in\mathbb{R}^d θ ∈ R d is an unknown parameter vector, and A ⊆ R d \mathcal{A}\subseteq\mathbb{R}^d A ⊆ R d . Since both dim E ( F , ε ) \dim_E(\mathcal{F},\varepsilon) dim E ( F , ε ) and log N ( F , ε , ∥ ⋅ ∥ ∞ ) \log N(\mathcal{F},\varepsilon,\lVert\cdot\rVert_\infty) log N ( F , ε , ∥ ⋅ ∥ ∞ ) scale as O ( d log ( 1 / ε ) ) O(d\log(1/\varepsilon)) O ( d log ( 1/ ε )) [31 ] , substituting ε = T − 2 \varepsilon=T^{-2} ε = T − 2 into Theorem 4.2 yields:
Corollary 5.1 (Linear CPT Regret). Let F \mathcal{F} F be the unit ball of linear functions in R d \mathbb{R}^d R d . Then, with probability at least 1 − δ 1-\delta 1 − δ ,
R ( T ) = O ~ ( d T + d T log ( 1 / δ ) ) . R(T)=\widetilde{O}\left(d\sqrt{T}+\sqrt{dT\log(1/\delta)}\right). R ( T ) = O ( d T + d T log ( 1/ δ ) ) .
Remark 5.2. For fixed confidence level, our general theorem recovers the O ~ ( d T ) \widetilde{O}(d\sqrt{T}) O ( d T ) linear CPT regret order of [13 ] .
Kernel CPT bandits
Let K \mathcal{K} K be a positive semidefinite kernel on A \mathcal{A} A with K ( a , a ) ≤ 1 \mathcal{K}(a,a)\le1 K ( a , a ) ≤ 1 for all a a a . Let f ∗ ∈ H K f^*\in\mathcal{H}_{\mathcal{K}} f ∗ ∈ H K with ∥ f ∗ ∥ K ≤ B \lVert f^*\rVert_{\mathcal{K}}\le B ∥ f ∗ ∥ K ≤ B . The noise CDF F ϵ a F_{\epsilon_a} F ϵ a is known for every arm a a a .
For n ≥ 1 n \ge1 n ≥ 1 and ρ > 0 \rho> 0 ρ > 0 , define
γ n ( ρ ) = sup a 1 , … , a n ∈ A 1 2 log det ( I + ρ − 1 K n ) , \gamma_n(\rho)=\sup_{a_1,\ldots,a_n\in\mathcal{A}}\frac{1}{2}\log\det(I+\rho^{-1}K_n), γ n ( ρ ) = a 1 , … , a n ∈ A sup 2 1 log det ( I + ρ − 1 K n ) ,
where ( K n ) i j = K ( a i , a j ) (K_n)_{ij}=\mathcal{K}(a_i,a_j) ( K n ) ij = K ( a i , a j ) , and set γ 0 ( ρ ) = 0 \gamma_0(\rho)=0 γ 0 ( ρ ) = 0 .
General NPCB for RKHS balls
We first ask what the general NPCB guarantee gives when F \mathcal{F} F is an RKHS ball. A class of arbitrary continuous functions can have infinite Eluder dimension. On any finite set of distinct arms, one can construct a continuous function that vanishes at all previously chosen arms and takes a nonzero value at a new arm. Thus continuity alone does not prevent arbitrarily long independent sequences.
An RKHS norm bound restricts this behavior. For F = { f ∈ H K : ∥ f ∥ K ≤ B } \mathcal{F}=\{f\in\mathcal{H}_{\mathcal{K}}:\|f\|_{\mathcal{K}}\le B\} F = { f ∈ H K : ∥ f ∥ K ≤ B } , the Eluder dimension can be controlled through the kernel information gain, as follows.
Lemma 5.1 (Eluder dimension of an RKHS ball). Let B > 0 B>0 B > 0 and F = { f ∈ H K : ∥ f ∥ K ≤ B } \mathcal{F}=\{f\in\mathcal{H}_{\mathcal{K}}:\|f\|_{\mathcal{K}}\le B\} F = { f ∈ H K : ∥ f ∥ K ≤ B } . For every ε > 0 \varepsilon>0 ε > 0 , if γ n ( ( ε / 2 B ) 2 ) ≤ n log ( 3 / 2 ) / 2 \gamma_n((\varepsilon/2B)^2)\le n\log(3/2)/2 γ n (( ε /2 B ) 2 ) ≤ n log ( 3/2 ) /2 for some n ≥ 1 n\ge1 n ≥ 1 , then dim E ( F , ε ) < n \dim_{\mathrm{E}}(\mathcal{F},\varepsilon)<n dim E ( F , ε ) < n . Consequently, if γ n ( ( ε / 2 B ) 2 ) = o ( n ) \gamma_n((\varepsilon/2B)^2)=o(n) γ n (( ε /2 B ) 2 ) = o ( n ) as n → ∞ n\to\infty n → ∞ , then dim E ( F , ε ) < ∞ \dim_{\mathrm{E}}(\mathcal{F},\varepsilon)<\infty dim E ( F , ε ) < ∞ .
We now substitute these RKHS complexity bounds into the general NPCB guarantee. At ε = T − 2 \varepsilon=T^{-2} ε = T − 2 , Lemma 5.1 evaluates information gain at the auxiliary scale ρ = T − 4 / ( 4 B 2 ) \rho=T^{-4}/(4B^2) ρ = T − 4 / ( 4 B 2 ) . For standard compact domains and fixed B B B , this gives O ~ ( d T ) \widetilde{O}(d\sqrt{T}) O ( d T ) regret for a linear kernel and O ~ ( T ( log T ) d + 1 ) \widetilde{O}(\sqrt{T}(\log T)^{d+1}) O ( T ( log T ) d + 1 ) for a squared exponential kernel.
For a Matérn kernel, however, the same generic reduction is much more conservative. Under the stated spectral conditions, [43 ] gives dim E ( F , T − 2 ) = O ~ ( T 2 d / ν ) \dim_{\mathrm{E}}(\mathcal{F},T^{-2})=\widetilde{O}(T^{2d/\nu}) dim E ( F , T − 2 ) = O ( T 2 d / ν ) , and [46 Lemma D.2] gives log N ( F , T − 2 , ∥ ⋅ ∥ ∞ ) = O ~ ( T 2 d / ν ) \log N(\mathcal{F},T^{-2},\|\cdot\|_{\infty})=\widetilde{O}(T^{2d/\nu}) log N ( F , T − 2 , ∥ ⋅ ∥ ∞ ) = O ( T 2 d / ν ) . Theorem 4.2 therefore gives at most O ~ ( T 1 / 2 + 2 d / ν ) \widetilde{O}(T^{1/2+2d/\nu}) O ( T 1/2 + 2 d / ν ) , which may be vacuous. This motivates exploiting the kernel structure directly.
Kernel-specific confidence: KCB
For an arm a a a and scalar mean m m m , let V a ( m ) \mathcal{V}_a(m) V a ( m ) denote the distorted value of the reward m + ϵ a m+\epsilon_a m + ϵ a . Here we relax the bounded-support assumption of § 2 . The noise need only be conditionally mean zero and η \eta η -sub-Gaussian. We additionally assume that ∫ 0 ∞ w ( 1 − F ϵ a ( z ) ) d z \int_0^\infty w(1-F_{\epsilon_a}(z))\,\mathrm{d}z ∫ 0 ∞ w ( 1 − F ϵ a ( z )) d z and ∫ 0 ∞ w ( F ϵ a ( − z ) ) d z \int_0^\infty w(F_{\epsilon_a}(-z))\,\mathrm{d}z ∫ 0 ∞ w ( F ϵ a ( − z )) d z are finite for every arm a a a . This ensures that CPT values are finite at every finite mean shift. Rather than using the generic NPCB confidence set, we estimate f ∗ f^* f ∗ by kernel ridge regression. For KCB, set λ = 1 + 2 / T \lambda=1+2/T λ = 1 + 2/ T .
At round t t t , let r t − 1 = ( r 1 , … , r t − 1 ) ⊤ \boldsymbol{r}_{t-1}=(r_1,\ldots,r_{t-1})^\top r t − 1 = ( r 1 , … , r t − 1 ) ⊤ and k t − 1 ( a ) = ( K ( a 1 , a ) , … , K ( a t − 1 , a ) ) ⊤ \boldsymbol{k}_{t-1}(a)=(\mathcal{K}(a_1,a),\ldots,\mathcal{K}(a_{t-1},a))^\top k t − 1 ( a ) = ( K ( a 1 , a ) , … , K ( a t − 1 , a ) ) ⊤ . Kernel ridge regression gives the predictor μ t − 1 ( a ) \mu_{t-1}(a) μ t − 1 ( a ) and uncertainty σ t − 1 ( a ) \sigma_{t-1}(a) σ t − 1 ( a ) . The algorithm forms an upper confidence bound U t ( a ) U_t(a) U t ( a ) on the mean and chooses the arm with the largest optimistic distorted value V a ( U t ( a ) ) \mathcal{V}_a(U_t(a)) V a ( U t ( a )) .
The estimator μ t − 1 \mu_{t-1} μ t − 1 is the kernel ridge-regression estimator, rather than the constrained least-squares estimator used in Algorithm 1. By [9 Theorem 2] , with probability at least 1 − δ 1-\delta 1 − δ , simultaneously for all t t t and a a a , ∣ f ∗ ( a ) − μ t − 1 ( a ) ∣ ≤ β t σ t − 1 ( a ) |f^*(a)-\mu_{t-1}(a)|\le\sqrt{\beta_t}\sigma_{t-1}(a) ∣ f ∗ ( a ) − μ t − 1 ( a ) ∣ ≤ β t σ t − 1 ( a ) . Since V a ( m ) \mathcal{V}_a(m) V a ( m ) is nondecreasing in m m m , V a ( U t ( a ) ) \mathcal{V}_a(U_t(a)) V a ( U t ( a )) is an upper confidence value for the true distorted reward of arm a a a .
Theorem 5.3 (Kernel CPT regret). With probability at least 1 − δ 1-\delta 1 − δ , Algorithm 2 satisfies
R ( T ) ≤ 4 C λ T γ T ( λ ) [ B + η 2 ( γ T − 1 ( λ ) + 1 + log ( 1 / δ ) ) ] , R(T)\le4\sqrt{C_\lambda T\gamma_T(\lambda)}\left[B+\eta\sqrt{2(\gamma_{T-1}(\lambda)+1+\log(1/\delta))}\right], R ( T ) ≤ 4 C λ T γ T ( λ ) [ B + η 2 ( γ T − 1 ( λ ) + 1 + log ( 1/ δ )) ] , where C λ = 2 log ( 1 + 1 / λ ) C_\lambda=\frac{2}{\log(1+1/\lambda)} C λ = l o g ( 1 + 1/ λ ) 2 .
Figure 2.
Unlike the generic NPCB bound, this result uses neither an Eluder dimension nor a covering number. For fixed B B B , η \eta η , δ \delta δ , it gives O ~ ( d T ) \widetilde{O}(d\sqrt{T}) O ( d T ) for the linear kernel and O ~ ( T ( log T ) d + 1 ) \widetilde{O}(\sqrt{T}(\log T)^{d+1}) O ( T ( log T ) d + 1 ) for the squared exponential kernel. For Matérn kernels it improves the generic bound to O ~ ( T 1 / 2 + d / ( 2 ν + d ) ) \widetilde{O}(T^{1/2+d/(2\nu+d)}) O ( T 1/2 + d / ( 2 ν + d ) ) .
The remaining loss comes from the confidence multiplier: β T \sqrt{\beta_T} β T itself contains a γ T ( λ ) \sqrt{\gamma_T(\lambda)} γ T ( λ ) term, while summing the posterior standard deviations contributes another T γ T ( λ ) \sqrt{T\gamma_T(\lambda)} T γ T ( λ ) factor. Thus the dominant term scales as T γ T ( λ ) \sqrt{T}\,\gamma_T(\lambda) T γ T ( λ ) . The phasewise refinement below removes this extra information-gain factor.
Phasewise confidence refinement
We adapt the batched pure-exploration strategy of [27 ] . Starting from all arms, our proposed algorithm CPT Batched Pure Exploration (CPT-BPE) runs phases of increasing length. Within each phase, arms are selected greedily by posterior variance using only the arms pulled in that phase; rewards from the phase are used only after the phase ends. A kernel confidence band is then fitted, and arms whose optimistic CPT value is below the best pessimistic CPT value are eliminated. The full procedure is given in Algorithm 3 in Appendix § 12 .
Theorem 5.4 (Phasewise kernel CPT regret). Under the assumptions above, let ∣ r t ∣ ≤ M |r_t| \le M ∣ r t ∣ ≤ M almost surely. For finite A \mathcal{A} A , with probability at least 1 − δ 1-\delta 1 − δ ,
R ( T ) ≤ 2 M ⌈ T ⌉ + 8 c C λ γ T ( λ ) ∑ i = 2 m n i n i − 1 . R(T) \le2M\lceil\sqrt{T}\rceil+ 8c\sqrt{C_{\lambda}\gamma_T(\lambda)}\sum_{i=2}^{m}\frac{n_i}{\sqrt{n_{i-1}}}. R ( T ) ≤ 2 M ⌈ T ⌉ + 8 c C λ γ T ( λ ) i = 2 ∑ m n i − 1 n i . Here a final truncated phase uses its actual length in the sum. In particular, this is O ~ ( T γ T ( λ ) ) \widetilde{O}(\sqrt{T\gamma_T(\lambda)}) O ( T γ T ( λ ) ) for fixed B B B , η \eta η , M M M , λ \lambda λ and polynomial ∣ A ∣ |\mathcal{A}| ∣ A ∣ .
The proof is in Appendix § 12 . For a Matérn kernel, the information-gain bound gives O ~ ( T ( ν + d ) / ( 2 ν + d ) ) \widetilde{O}(T^{(\nu+d)/(2\nu+d)}) O ( T ( ν + d ) / ( 2 ν + d ) ) . This is the risk-neutral Matérn upper-bound exponent. It holds for a finite arm set, including a finite discretization.
To extend CPT-BPE to a continuous arm space, let A \mathcal{A} A be a compact subset of R d \mathbb{R}^{d} R d and take a grid with mesh T − 1 / ( 2 α ) T^{-1/(2\alpha)} T − 1/ ( 2 α ) for some α > 0 \alpha>0 α > 0 . Assume the true CPT objective satisfies ∣ V a ( f ∗ ) − V b ( f ∗ ) ∣ ≤ L ∥ a − b ∥ α |V_a(f^*)-V_b(f^*)|\le L\|a-b\|^\alpha ∣ V a ( f ∗ ) − V b ( f ∗ ) ∣ ≤ L ∥ a − b ∥ α . Then the grid has polynomial size and introduces at most L T L\sqrt{T} L T additional regret, up to a domain constant. Moreover, ∣ A T ∣ = O ( T d / ( 2 α ) ) |\mathcal{A}_T|=O(T^{d/(2\alpha)}) ∣ A T ∣ = O ( T d / ( 2 α ) ) , so the log ∣ A T ∣ \log|\mathcal{A}_T| log ∣ A T ∣ term in the confidence multiplier contributes only logarithmic factors, and the same Matérn exponent follows. This spatial regularity condition accounts for variation in both the mean and the arm-dependent noise law, and is needed to compare the continuous optimizer with its nearest grid arm. For example, it holds if f ∗ f^* f ∗ is α \alpha α -Hölder and V a ( m ) \mathcal{V}_a(m) V a ( m ) is α \alpha α -Hölder in a a a , uniformly over the relevant means. The construction and regret decomposition are given in Appendix § 12 .§ 3 .
caption: Comparison of known-CDF kernel regret bounds for general NPCB and CPT-BPE under standard spectral assumptions. The CPT-BPE column is highlighted in green. The Matérn entry for general NPCB is highlighted in red to indicate that this bound can be vacuous.
Kernel means with learned noise CDFs
Keep the k k k -parameter noise family above and replace the linear mean class by the RKHS ball F = { f ∈ H K : ∥ f ∥ K ≤ B } \mathcal{F} = \{f \in\mathcal{H}_{K} : \lVert f \rVert_{K} \le B\} F = { f ∈ H K : ∥ f ∥ K ≤ B } . NPCB-Learned (Algorithm 4) applies unchanged.
For this RKHS specialization, the two distributional complexity terms in Theorem 4.5 can be controlled by the complexity of the mean class and the k k k -dimensional noise family. In particular, log N o p t ( Q , 1 / T ) ≤ log N ( F , c / T , ∥ ⋅ ∥ ∞ ) + k log ( C T ) \log N_{\mathrm{opt}}(\mathcal{Q},1/T) \le\log N(\mathcal{F},c/T,\lVert\cdot\rVert_{\infty}) + k\log(CT) log N opt ( Q , 1/ T ) ≤ log N ( F , c / T , ∥ ⋅ ∥ ∞ ) + k log ( C T ) , while min { dim E ( G , d ⋅ , 1 / T ) , T } ≤ C [ γ T ( c 0 / T 2 ) + k log ( 1 + C T 3 / k ) ] \min\{\dim_{E}(\mathcal{G},d\cdot,1/T),T\} \le C[\gamma_T(c_0/T^2) + k\log(1+CT^3/k)] min { dim E ( G , d ⋅ , 1/ T ) , T } ≤ C [ γ T ( c 0 / T 2 ) + k log ( 1 + C T 3 / k )] , for fixed B B B , s s s and constants c , c 0 , C > 0 c,c_0,C>0 c , c 0 , C > 0 .
Together with the kernel mean-width bound ∑ t = 1 T w C t ( a t ) = O ( T β T γ T ( λ ) ) \sum_{t=1}^{T}w_{\mathcal{C}_t}(a_t)=O(\sqrt{T\beta_T\gamma_T(\lambda)}) ∑ t = 1 T w C t ( a t ) = O ( T β T γ T ( λ ) ) , Theorem 4.5 gives an explicit learned-CDF kernel guarantee. Details are given in Appendix § 15 .§ 1 . The distributional Eluder term uses information gain at scale c 0 / T 2 c_0/T^2 c 0 / T 2 , rather than λ \lambda λ , so this argument does not recover the strongest known-CDF Matérn rate.
Experiments
We examine how risk criteria rank arms with rare losses or gains, how kernel algorithms learn the CPT-optimal arm, and the additional cost of learning unknown noise laws.
Risk preferences. We consider 100 candidate routes (arms), each yielding a stochastic reward. The arms are equally spaced in [ 0 , 1 ] [0,1] [ 0 , 1 ] , and their mean rewards form six Gaussian-shaped peaks. We compare Mean, lower-tail CVaR, mean–variance (MV), and CPT. Each risk metric assigns a score to every arm; the arm with the highest score is its preferred choice.
We study five experimental configurations, labelled A–E. Configs A–D vary the probability and magnitude of a rare loss for arms near the third peak; config E instead introduces a rare large gain for those arms. The remaining arms have Gaussian background noise. These settings illustrate contrasting human preferences associated with small probabilities: avoiding a rare large loss while favoring a rare large gain.
In config B, shown in Figure 1 (a), arms near the third peak have higher mean rewards but carry a small chance of a large loss. CPT lowers their risk scores sufficiently to favor a safer arm near the first peak, consistent with avoidance of rare severe outcomes. MV also favors this safer alternative, whereas Mean and CVaR retain their preference for the third peak.
Interestingly, the preference reverses for rare gains. In config E, shown in Figure 1 (b), arms near the third peak have lower mean rewards but offer a small chance of a large gain. CPT increases their scores sufficiently to favor them, capturing the attraction of rare large gains. Although MV favors the safer alternative in B, it also penalizes the variability introduced by the rare gain in E and therefore prefers an arm near the first peak, as do Mean and CVaR. Thus, at the tested settings, CPT captures both contrasting preferences within the same framework. The remaining settings, parameter sensitivity, and learning trajectories appear in Appendix I.§ 1 .
Kernel learning. We compare KCB, CPT-BPE, and empirical-CDF W-UCB under the same CPT objective on a bounded 49-arm grid in [ 0 , 1 ] 2 [0,1]^2 [ 0 , 1 ] 2 . The first two methods receive the noise CDFs and use their respective analyzed confidence constructions; W-UCB estimates each arm’s reward CDF from samples. We run 30 paired trials at eight horizons from T = 500 T = 500 T = 500 to 64000. Figure 1 (c) shows that KCB has the lowest mean regret throughout this range. CPT-BPE exhibits slower growth at larger horizons and has lower mean regret than W-UCB from T = 16000 T = 16000 T = 16000 onward. Its regret per round decreases from 0.296 to 0.078. Appendix I.§ 1 gives the confidence diagnostics, numerical results, and additional 1D kernel and linear WOFUL comparisons.
Learning unknown noise laws. We evaluate NPCB-Learned (Algorithm 4) on a finite realizable class containing the true mean and noise model. Configurations A–D contain rare losses and E contains rare gains. Table 2 compares it with a known-law specialization and a greedy plug-in MLE baseline.
Table 2. Unknown-CDF mean CPT regret ± \pm ± s.e. over 30 trials; T = ( 20000 , 10000 , 5000 , 5000 , 30000 ) T = (20000, 10000, 5000, 5000, 30000) T = ( 20000 , 10000 , 5000 , 5000 , 30000 ) for A–E.
NPCB-Learned has lower mean CPT regret than plug-in MLE in every configuration and reaches the CPT-optimal reporting region in all 30 trials, compared with 0–20% for plug-in MLE. The known-law specialization incurs substantially less regret, demonstrating the additional cost of learning the noise law.
The finite model construction, convergence curves, and confidence-set diagnostics appear in Appendix I.§ 2 .
Conclusion
We study risk-sensitive bandits beyond linear structure. For known arm-dependent noise CDFs, we derive general Eluder-dimension bounds and a pointwise kernel UCB bound; our phase-wise kernel algorithm matches the risk-neutral upper-bound exponent for finite arms, and for continuous domains under spatial regularity of the CPT objective. We further extend to learned noise CDFs via a joint likelihood approach, with explicit complexity bounds for linear and RKHS mean models. Open questions include extending CPT to RL, identifying complexity measures beyond the Eluder dimension suited to CPT, and designing implementable (approximate) algorithms for non-parametric CPT bandits.
AI Use Statement
In this work, we used generative AI tools to write the Python code for the experiments and plots in § 6 and Appendix I. The experimental design, including which experiments to run and which questions to investigate, was conceived entirely by the authors, and the generated code was manually verified for correctness by one of the authors. Additionally, we used generative AI tools for editing and grammar-checking the manuscript text. We have reviewed all AI-assisted work and take responsibility for the final content of this work, including text, claims, and artifacts.
Other Related Works
Much of the recent progress in the multi-armed bandit setup has focused on adopting risk-sensitive measures like VaR and CVaR. [14 ] introduced CVaR in the K-armed bandit setting, which was later studied extensively by [40 , 42 , 22 ] . [6 ] established the first asymptotically optimal Thompson Sampling strategies for support-aware CVaR bandits. Several works have sought to develop unified frameworks as well. [11 ] proposed a general framework using abstract norms, though their stability criteria are limited to Lipschitz-continuous measures and fail for singular functionals like Cumulative Prospect Theory (CPT). [1 , 41 ] address this gap under the Wasserstein metric to handle non-Lipschitz and heavy-tailed distributions. [12 ] established a Bayesian unification for “continuous” risk functionals. [25 ] introduced a distributional optimization framework that yields tighter confidence bounds by avoiding global Lipschitz constants. Despite these advancements, all these approaches remain confined to the finite-arm setting, leaving the optimization of singular risk measures like CPT in nonparametric contextual bandits as an unaddressed challenge.
[41 ] consider a different benchmark in which a distortion risk metric is applied to the reward distribution induced by a mixture of arms. For mixture π \pi π , their type of objective evaluates the risk functional after forming the mixed reward distribution. Our regret instead compares the per-round CPT value of the selected arm with that of the best individual arm. In particular, ∫ A V a ( f ⋆ ) π ( d a ) ≤ sup a ∈ A V a ( f ⋆ ) \int_{\mathcal A} \mathcal V_a(f^\star)\,\pi(\mathrm{d}a) \le\sup_{a\in\mathcal A} \mathcal V_a(f^\star) ∫ A V a ( f ⋆ ) π ( d a ) ≤ sup a ∈ A V a ( f ⋆ ) , so randomization cannot improve our benchmark. Applying CPT to the mixed reward distribution ∫ A F a ⋆ π ( d a ) \int_{\mathcal A} F_a^\star\,\pi(\mathrm{d}a) ∫ A F a ⋆ π ( d a ) is a different objective and is not considered here.
An adjacent but distinct field is reinforcement learning (RL), where these risk measures have also been extensively utilized to manage uncertainty in sequential decision-making. The foundation of risk-sensitive control in RL was established through entropic utility and variance-penalized objectives [18 , 35 ] . These were subsequently adapted into policy gradient and actor-critic algorithms to optimize exponential costs and minimize volatility by [7 PG13] . To ensure safety in high-stakes environments, research has increasingly adopted tail-risk measures like CVaR [38 , 10 ] . Behavioral measures, specifically CPT, have also been integrated to align agent behavior with human decision-making and probability distortions [4 ] .
Technical Details for Section 4
In this section, we provide the technical details supporting the regret analysis of Section § 4 . We detail the confidence set construction, formalize the mapping from statistical uncertainty to subjective distorted uncertainty, and present the key intermediate results that underpin Theorem 4.2 . The proofs of all results in this section are provided in Appendix § 10 .
Complexity Measure
We utilize the concept of Eluder dimension , first introduced by [R13]. Intuitively, this measure captures the worst-case difficulty of inferring unobserved values. A low Eluder dimension implies that observing a few points allows for accurate global predictions, whereas a high dimension suggests the function can exhibit “surprising” variations even after many observations.
Confidence Sets
A defining characteristic of our algorithm is its modularity. Since the statistical validity of the confidence set depends exclusively on the additive noise properties, we can adopt the construction from [31 ] , ensuring that the reward function’s mean concentrates objectively regardless of the agent’s subjective bias. We denote the confidence set at time t t t as an empirical ball centered at the least-squares estimate:
C t : = { f ∈ F : ∥ f − f ^ t L S ∥ 2 , D t − 1 ≤ β t } . C_t := \left\{f \in\mathcal{F}: \|f-\hat{f}^{\mathrm{LS}}_t\|_{2,\mathcal{D}_{t-1}} \le\sqrt{\beta_t}\right\}. C t := { f ∈ F : ∥ f − f ^ t LS ∥ 2 , D t − 1 ≤ β t } .
Here, ∥ g ∥ 2 , D t − 1 2 : = ∑ j < t g ( a j ) 2 \|g\|^2_{2,\mathcal{D}_{t-1}} := \sum_{j<t} g(a_j)^2 ∥ g ∥ 2 , D t − 1 2 := ∑ j < t g ( a j ) 2 .
For the confidence-set construction, it is enough that the noise is conditionally mean zero and uniformly η \eta η -sub-Gaussian: E [ e u ϵ t ∣ D t − 1 , a t ] ≤ e u 2 η 2 / 2 \mathbb{E}[e^{u\epsilon_t}\mid\mathcal{D}_{t-1},a_t]\le e^{u^2\eta^2/2} E [ e u ϵ t ∣ D t − 1 , a t ] ≤ e u 2 η 2 /2 , with u ∈ R u \in\mathbb{R} u ∈ R . Under the bounded-reward assumption of § 2 , Hoeffding’s lemma allows us to take η = M \eta=M η = M . Moreover, every f ∈ F f \in\mathcal{F} f ∈ F takes values in [ − M , M ] [-M,M] [ − M , M ] , so the range condition of [31 ] holds with C = 2 M C=2M C = 2 M .
We set α = T − 2 \alpha=T^{-2} α = T − 2 and assume N ( F , α , ∥ ⋅ ∥ ∞ ) < ∞ N(\mathcal{F},\alpha,\|\cdot\|_\infty)<\infty N ( F , α , ∥ ⋅ ∥ ∞ ) < ∞ . Following Proposition 2 of [31 ] , we use
β t = 8 η 2 log ( N ( F , α , ∥ ⋅ ∥ ∞ ) δ ) + 2 α t ( 16 M + 8 η 2 ln ( 4 t 2 / δ ) ) . \beta_t = 8\eta^2\log\left(\frac{N(\mathcal{F},\alpha,\|\cdot\|_\infty)}{\delta}\right)+2\alpha t\left(16M+\sqrt{8\eta^2\ln(4t^2/\delta)}\right). β t = 8 η 2 log ( δ N ( F , α , ∥ ⋅ ∥ ∞ ) ) + 2 α t ( 16 M + 8 η 2 ln ( 4 t 2 / δ ) ) .
This radius explicitly accounts for the function class complexity (via α \alpha α -covering numbers in sup-norm) and the discretization error inherent in continuous spaces.
No convexity of F \mathcal{F} F is required for this confidence construction. This is the general-function-class setting of [31 ] ; for completeness, the following direct argument also gives the desired 1 − δ 1-\delta 1 − δ confidence statement under our standing bounded-reward assumptions.
Lemma B.1 (Least-squares confidence for general function classes). Let F α ⊆ F \mathcal{F}_\alpha\subseteq\mathcal{F} F α ⊆ F be a finite α \alpha α -cover in the sup norm, and write N α = ∣ F α ∣ N_\alpha=|\mathcal{F}_\alpha| N α = ∣ F α ∣ . Then, with probability at least 1 − δ 1-\delta 1 − δ , simultaneously for every t ≤ T t\le T t ≤ T ,
∑ j < t ( f ^ t L S ( a j ) − f ∗ ( a j ) ) 2 ≤ 8 η 2 log N α δ + 12 M α ( t − 1 ) . \sum_{j<t}\left(\hat{f}^{\mathrm{LS}}_t(a_j)-f^*(a_j)\right)^2 \le8\eta^2\log\frac{N_\alpha}{\delta}+12M\alpha(t-1). j < t ∑ ( f ^ t LS ( a j ) − f ∗ ( a j ) ) 2 ≤ 8 η 2 log δ N α + 12 M α ( t − 1 ) . In particular, with η = M \eta=M η = M , the radius β t \beta_t β t above implies f ∗ ∈ C t f^*\in C_t f ∗ ∈ C t for every $t\le T.
Proof. For fixed g ∈ F α g\in\mathcal{F}_\alpha g ∈ F α , define
Q t ( g ) : = ∑ j < t ( g ( a j ) − f ∗ ( a j ) ) 2 , S t ( g ) : = ∑ j < t ϵ j ( g ( a j ) − f ∗ ( a j ) ) . Q_t(g):=\sum_{j<t}\left(g(a_j)-f^*(a_j)\right)^2,\qquad S_t(g):=\sum_{j<t}\epsilon_j\left(g(a_j)-f^*(a_j)\right). Q t ( g ) := j < t ∑ ( g ( a j ) − f ∗ ( a j ) ) 2 , S t ( g ) := j < t ∑ ϵ j ( g ( a j ) − f ∗ ( a j ) ) . Conditional sub-Gaussianity implies that
exp { S t ( g ) 2 η 2 − Q t ( g ) 8 η 2 } \exp\left\{\frac{S_t(g)}{2\eta^2}-\frac{Q_t(g)}{8\eta^2}\right\} exp { 2 η 2 S t ( g ) − 8 η 2 Q t ( g ) } is a nonnegative supermartingale starting at one. Hence, by Ville’s inequality and a union bound over F α \mathcal{F}_\alpha F α , with probability at least $1-\delta$, simultaneously for all g ∈ F α g\in\mathcal{F}_\alpha g ∈ F α and all $t\le T,
S t ( g ) ≤ 1 4 Q t ( g ) + 2 η 2 log N α δ . S_t(g)\le\frac{1}{4}Q_t(g)+2\eta^2\log\frac{N_\alpha}{\delta}. S t ( g ) ≤ 4 1 Q t ( g ) + 2 η 2 log δ N α . Work on this event and put h = f ^ t L S h=\hat{f}^{\mathrm{LS}}_t h = f ^ t LS . Least-squares optimality gives
Q t ( h ) ≤ 2 S t ( h ) . (1) Q_t(h)\le2S_t(h). \tag*{(1)} Q t ( h ) ≤ 2 S t ( h ) . (1)
Choose g ∈ F α g \in\mathcal{F}_{\alpha} g ∈ F α such that ∥ g − h ∥ ∞ ≤ α \lVert g-h\rVert_{\infty} \le\alpha ∥ g − h ∥ ∞ ≤ α . Since r j , f ∗ ( a j ) ∈ [ − M , M ] r_j, f^{*}(a_j) \in[-M,M] r j , f ∗ ( a j ) ∈ [ − M , M ] , we have ∣ ϵ j ∣ ≤ 2 M |\epsilon_j| \le2M ∣ ϵ j ∣ ≤ 2 M , and since g , h , f ∗ g,h,f^{*} g , h , f ∗ take values in [ − M , M ] [-M,M] [ − M , M ] ,
∣ S t ( h ) − S t ( g ) ∣ ≤ 2 M α ( t − 1 ) , ∣ Q t ( h ) − Q t ( g ) ∣ ≤ 4 M α ( t − 1 ) . |S_t(h)-S_t(g)| \le2M\alpha(t-1), \qquad|Q_t(h)-Q_t(g)| \le4M\alpha(t-1). ∣ S t ( h ) − S t ( g ) ∣ ≤ 2 M α ( t − 1 ) , ∣ Q t ( h ) − Q t ( g ) ∣ ≤ 4 M α ( t − 1 ) .
Therefore
Q t ( h ) ≤ 1 2 Q t ( g ) + 4 η 2 log N α δ + 4 M α ( t − 1 ) ≤ 1 2 Q t ( h ) + 4 η 2 log N α δ + 6 M α ( t − 1 ) . \begin{aligned}
Q_t(h) \le\frac{1}{2}Q_t(g)+4\eta^2\log\frac{N_\alpha}{\delta}+4M\alpha(t-1) \\
&\le\frac{1}{2}Q_t(h)+4\eta^2\log\frac{N_\alpha}{\delta}+6M\alpha(t-1).
\end{aligned} Q t ( h ) ≤ 2 1 Q t ( g ) + 4 η 2 log δ N α + 4 M α ( t − 1 ) ≤ 2 1 Q t ( h ) + 4 η 2 log δ N α + 6 M α ( t − 1 ) .
Rearranging proves the claim.
We further define the standard width of the confidence set at action a a a as the maximum variation in prediction:
w C t ( a ) : = sup f 1 , f 2 ∈ C t ∣ f 1 ( a ) − f 2 ( a ) ∣ . w_{C_t}(a) := \sup_{f_1,f_2\in C_t}|f_1(a)-f_2(a)|. w C t ( a ) := f 1 , f 2 ∈ C t sup ∣ f 1 ( a ) − f 2 ( a ) ∣.
Crucially, the Eluder dimension governs the shrinkage of this width.
Mapping confidence set to distorted value
While the confidence set C t C_t C t captures the statistical uncertainty surrounding the environment’s mean reward function f ∗ f^{*} f ∗ (learned from observed undistorted rewards), the agent’s decisions are governed by the subjective weight-distorted value functional V a ( f ) \mathcal{V}_a(f) V a ( f ) . To bridge these, we define the optimistic and pessimistic weight-distorted rewards for any action a a a at time t t t , respectively, as
V ~ t ( a ) : = sup f ∈ C t V a ( f ) , V ‾ t ( a ) : = inf f ∈ C t V a ( f ) . \widetilde{\mathcal{V}}_t(a) := \sup_{f\in C_t}\mathcal{V}_a(f), \qquad\underline{\mathcal{V}}_t(a) := \inf_{f\in C_t}\mathcal{V}_a(f). V t ( a ) := f ∈ C t sup V a ( f ) , V t ( a ) := f ∈ C t inf V a ( f ) .
Based on these boundary estimates, we define the distorted width of the confidence set for action a a a , denoted by w C t V ( a ) w^{\mathcal{V}}_{C_t}(a) w C t V ( a ) , as the subjective uncertainty gap: w C t V ( a ) : = V ~ t ( a ) − V ‾ t ( a ) w^{\mathcal{V}}_{C_t}(a) := \widetilde{\mathcal{V}}_t(a)-\underline{\mathcal{V}}_t(a) w C t V ( a ) := V t ( a ) − V t ( a ) .
It is important to emphasize that the confidence set C t C_t C t is constructed purely through square-loss estimation and is “blind” to the specific weight distortion function w ( ⋅ ) w(\cdot) w ( ⋅ ) . The distorted width w C t V ( a ) w^{\mathcal{V}}_{C_t}(a) w C t V ( a ) is introduced strictly as an analytical tool to quantify uncertainty relative to the agent’s subjective preference. This decoupling ensures that our framework maintains its modularity, learn the environment using standard statistical techniques while optimizing for non-linear behavioral values.
Regret Decomposition
Proposition B.1 (Regret Decomposition for Distorted Rewards). Assume that the true mean reward function f ∗ f^{*} f ∗ is contained in the confidence set C t C_t C t for all rounds t = 1 , … , T t=1,\ldots,T t = 1 , … , T . Then, the cumulative distorted regret R ( T ) R(T) R ( T ) is (almost surely) bounded by the sum of the distorted widths of the selected actions: R ( T ) ≤ ∑ t = 1 T w C t V ( a t ) R(T) \le\sum_{t=1}^{T}w^{\mathcal{V}}_{C_t}(a_t) R ( T ) ≤ ∑ t = 1 T w C t V ( a t ) .
Remark B.2. Although the agent cannot observe the true distorted rewards V a ( f ∗ ) \mathcal{V}_a(f^{*}) V a ( f ∗ ) , the regret bound in Proposition B.1 remains valid because the agent selects actions based on the optimistic estimator V ~ t \widetilde{\mathcal{V}}_t V t . By choosing a t = arg max a ∈ A V ~ t ( a ) a_t=\arg\max_{a\in\mathcal{A}}\widetilde{\mathcal{V}}_t(a) a t = arg max a ∈ A V t ( a ) , the algorithm guarantees that V ~ t ( a t ) ≥ V ~ t ( a ∗ ) \widetilde{\mathcal{V}}_t(a_t)\ge\widetilde{\mathcal{V}}_t(a^{*}) V t ( a t ) ≥ V t ( a ∗ ) . This selection rule ensures that the instantaneous regret is entirely dominated by the uncertainty, quantified as the distorted width w C t V ( a t ) w^{\mathcal{V}}_{C_t}(a_t) w C t V ( a t ) , thereby converting the problem of minimizing unknown regret into the problem of reducing subjective uncertainty.
Following Proposition B.1, the theoretical core of our analysis hinges on relating the subjective distorted width w C t V ( a ) w^{\mathcal{V}}_{C_t}(a) w C t V ( a ) to the standard width w C t ( a ) w_{C_t}(a) w C t ( a ) of a confidence set. This modularity allows us to leverage existing concentration results for general function classes while accounting for the non-linear transformation of rewards.
Connecting distorted width to standard width
The confidence set C t C_t C t controls uncertainty in the mean, whereas our regret decomposition involves the distorted width w C t V ( a ) w^{\mathcal{V}}_{C_t}(a) w C t V ( a ) . Using the translation-stability bound of [13 Lemma 5] , we relate these widths for general mean-function classes. This allows mean-estimation confidence guarantees to control CPT regret.
Proposition B.3 (Uniform Lipschitz Stability of Distorted Rewards). Assume the additive reward model, with both gain and loss CPT integrals finite at one mean for each arm. Let w : [ 0 , 1 ] → [ 0 , 1 ] w : [0, 1] \to[0, 1] w : [ 0 , 1 ] → [ 0 , 1 ] be Borel measurable with w ( 0 ) = 0 w(0) = 0 w ( 0 ) = 0 . Then, for every arm a a a and f 1 , f 2 ∈ F f_1, f_2 \in\mathcal{F} f 1 , f 2 ∈ F ,
∣ V a ( f 1 ) − V a ( f 2 ) ∣ ≤ 2 ∣ f 1 ( a ) − f 2 ( a ) ∣ . \left|\mathcal{V}_a(f_1)-\mathcal{V}_a(f_2)\right| \le2\left|f_1(a)-f_2(a)\right|. ∣ V a ( f 1 ) − V a ( f 2 ) ∣ ≤ 2 ∣ f 1 ( a ) − f 2 ( a ) ∣ .
Lemma B.2 (Bound on Distorted Width). Under the assumptions of Proposition B.3, for any action a a a , the distorted width satisfies w C t V ( a ) ≤ 2 w C t ( a ) w^{\mathcal{V}}_{C_t}(a) \le2w_{C_t}(a) w C t V ( a ) ≤ 2 w C t ( a ) .
Omitted Proofs from Section 4
Proof of Proposition B.1 (Regret Decomposition for Distorted Rewards)
Proof. The instantaneous regret at round t t t is i r t = V a ∗ ( f θ ∗ ) − V a t ( f θ ∗ ) ir_t = \mathcal{V}_{a^*}(f_{\theta^*}) - \mathcal{V}_{a_t}(f_{\theta^*}) i r t = V a ∗ ( f θ ∗ ) − V a t ( f θ ∗ ) . Since we assume true mean reward function f θ ∗ ∈ C t f_{\theta^*} \in C_t f θ ∗ ∈ C t for all round t t t , with high probability, the true distorted reward for any action is bounded by its optimistic and pessimistic estimates: V ‾ t ( a ) ≤ V a ( f θ ∗ ) ≤ V ~ t ( a ) \underline{\mathcal{V}}_t(a) \le\mathcal{V}_a(f_{\theta^*}) \le\widetilde{\mathcal{V}}_t(a) V t ( a ) ≤ V a ( f θ ∗ ) ≤ V t ( a ) . We can therefore bound the instantaneous regret as follows:
i r t = V a ∗ ( f θ ∗ ) − V a t ( f θ ∗ ) ≤ V ~ t ( a ∗ ) − V ‾ t ( a t ) (since f θ ∗ ∈ C t ) = V ~ t ( a t ) − V ‾ t ( a t ) + ( V ~ t ( a ∗ ) − V ~ t ( a t ) ) ⏟ ≤ 0 by the action selection rule ≤ V ~ t ( a t ) − V ‾ t ( a t ) = w C t V ( a t ) . \begin{aligned}
ir_t &= \mathcal{V}_{a^*}(f_{\theta^*})-\mathcal{V}_{a_t}(f_{\theta^*})\\
&\le\widetilde{\mathcal{V}}_t(a^*)-\underline{\mathcal{V}}_t(a_t) \qquad\text{(since } f_{\theta^*}\in C_t\text{)}\\
&= \widetilde{\mathcal{V}}_t(a_t)-\underline{\mathcal{V}}_t(a_t)+\underbrace{\left(\widetilde{\mathcal{V}}_t(a^*)-\widetilde{\mathcal{V}}_t(a_t)\right)}_{\le0\text{ by the action selection rule}}\\
&\le\widetilde{\mathcal{V}}_t(a_t)-\underline{\mathcal{V}}_t(a_t)\\
&= w^{\mathcal{V}}_{C_t}(a_t).
\end{aligned} i r t = V a ∗ ( f θ ∗ ) − V a t ( f θ ∗ ) ≤ V t ( a ∗ ) − V t ( a t ) (since f θ ∗ ∈ C t ) = V t ( a t ) − V t ( a t ) + ≤ 0 by the action selection rule ( V t ( a ∗ ) − V t ( a t ) ) ≤ V t ( a t ) − V t ( a t ) = w C t V ( a t ) .
Summing this inequality over t = 1 , … , T t = 1, \ldots, T t = 1 , … , T yields the desired result. □
Proof of Proposition B.3 (Uniform Lipschitz Stability of Distorted Rewards)
Proof. Fix an arm a a a and write V a ( m ) = V a ( m + ϵ a ) \mathcal{V}_a(m) = \mathcal{V}_a(m+\epsilon_a) V a ( m ) = V a ( m + ϵ a ) . For m 2 ≥ m 1 m_2 \ge m_1 m 2 ≥ m 1 , a change of variables in the two tail integrals gives
V a ( m 2 ) − V a ( m 1 ) = ∫ − m 2 − m 1 [ w ( 1 − F ϵ a ( u ) ) + w ( F ϵ a ( u ) ) ] d u . \mathcal{V}_a(m_2)-\mathcal{V}_a(m_1)=\int_{-m_2}^{-m_1}\left[w(1-F_{\epsilon_a}(u))+w(F_{\epsilon_a}(u))\right]\,du. V a ( m 2 ) − V a ( m 1 ) = ∫ − m 2 − m 1 [ w ( 1 − F ϵ a ( u )) + w ( F ϵ a ( u )) ] d u .
The integrand lies in [ 0 , 2 ] [0,2] [ 0 , 2 ] . Therefore 0 ≤ V a ( m 2 ) − V a ( m 1 ) ≤ 2 ( m 2 − m 1 ) 0 \le V_a(m_2)-V_a(m_1) \le2(m_2-m_1) 0 ≤ V a ( m 2 ) − V a ( m 1 ) ≤ 2 ( m 2 − m 1 ) . The same bound with the arguments exchanged proves the result. This argument also covers noise atoms and discontinuous weight functions. Bounded rewards ensure that both tail integrals are finite. More generally, the same argument applies whenever both tail integrals are finite at one mean, since they then remain finite under every finite mean shift.
Extension to reference points, separate weights, and Lipschitz utilities. Let X m = m + ϵ a X_m=m+\epsilon_a X m = m + ϵ a , fix a reference point x 0 x_0 x 0 , and define
U m = u + ( ( X m − x 0 ) + ) , W m = u − ( ( X m − x 0 ) − ) . U_m=u^+\left((X_m-x_0)^+\right), \qquad W_m=u^-\left((X_m-x_0)^-\right). U m = u + ( ( X m − x 0 ) + ) , W m = u − ( ( X m − x 0 ) − ) .
where u ± : [ 0 , ∞ ) → [ 0 , ∞ ) u^\pm:[0,\infty)\to[0,\infty) u ± : [ 0 , ∞ ) → [ 0 , ∞ ) are nondecreasing, L ± L^\pm L ± -Lipschitz, and satisfy u ± ( 0 ) = 0 u^\pm(0)=0 u ± ( 0 ) = 0 . Let w ± : [ 0 , 1 ] → [ 0 , 1 ] w^\pm:[0,1]\to[0,1] w ± : [ 0 , 1 ] → [ 0 , 1 ] be nondecreasing with w ± ( 0 ) = 0 w^\pm(0)=0 w ± ( 0 ) = 0 and w ± ( 1 ) = 1 w^\pm(1)=1 w ± ( 1 ) = 1 , and set
V a ( m ) = ∫ 0 ∞ w + ( P [ U m > z ] ) d z − ∫ 0 ∞ w − ( P [ W m > z ] ) d z . \mathcal{V}_a(m)=\int_0^\infty w^+\left(\mathbb{P}\left[U_m>z\right]\right)\,\mathrm{d}z-\int_0^\infty w^-\left(\mathbb{P}\left[W_m>z\right]\right)\,\mathrm{d}z. V a ( m ) = ∫ 0 ∞ w + ( P [ U m > z ] ) d z − ∫ 0 ∞ w − ( P [ W m > z ] ) d z .
Couple X m + Δ = X m + Δ X_{m+\Delta}=X_m+\Delta X m + Δ = X m + Δ for Δ ≥ 0 \Delta\ge0 Δ ≥ 0 . Since x ↦ u + ( ( x − x 0 ) + ) x\mapsto u^+\left((x-x_0)^+\right) x ↦ u + ( ( x − x 0 ) + ) is nondecreasing and L + L^+ L + -Lipschitz,
U m ≤ U m + Δ ≤ U m + L + Δ . U_m\le U_{m+\Delta}\le U_m+L^+\Delta. U m ≤ U m + Δ ≤ U m + L + Δ.
Define
g ( z ) = w + ( P [ U m > z ] ) , z ∈ R . g(z)=w^+\left(\mathbb{P}\left[U_m>z\right]\right), \qquad z\in\mathbb{R}. g ( z ) = w + ( P [ U m > z ] ) , z ∈ R .
For z < 0 z<0 z < 0 , P [ U m > z ] = 1 \mathbb{P}\left[U_m>z\right]=1 P [ U m > z ] = 1 , while g g g vanishes above the bounded support of U m U_m U m . Hence
0 ≤ ∫ 0 ∞ [ w + ( P [ U m + Δ > z ] ) − g ( z ) ] d z ≤ ∫ 0 ∞ [ g ( z − L + Δ ) − g ( z ) ] d z ≤ L + Δ . 0\le\int_0^\infty\left[w^+\left(\mathbb{P}\left[U_{m+\Delta}>z\right]\right)-g(z)\right]\,\mathrm{d}z\le\int_0^\infty\left[g(z-L^+\Delta)-g(z)\right]\,\mathrm{d}z\le L^+\Delta. 0 ≤ ∫ 0 ∞ [ w + ( P [ U m + Δ > z ] ) − g ( z ) ] d z ≤ ∫ 0 ∞ [ g ( z − L + Δ ) − g ( z ) ] d z ≤ L + Δ.
Similarly,
W m + Δ ≤ W m ≤ W m + Δ + L − Δ , W_{m+\Delta}\le W_m\le W_{m+\Delta}+L^-\Delta, W m + Δ ≤ W m ≤ W m + Δ + L − Δ ,
so the loss integral decreases by at most L − Δ L^-\Delta L − Δ . Therefore
0 ≤ V a ( m + Δ ) − V a ( m ) ≤ ( L + + L − ) Δ . 0\le\mathcal{V}_a(m+\Delta)-\mathcal{V}_a(m)\le(L^++L^-)\Delta. 0 ≤ V a ( m + Δ ) − V a ( m ) ≤ ( L + + L − ) Δ.
Thus
∣ V a ( m 1 ) − V a ( m 2 ) ∣ ≤ ( L + + L − ) ∣ m 1 − m 2 ∣ . \left|\mathcal{V}_a(m_1)-\mathcal{V}_a(m_2)\right|\le(L^++L^-)|m_1-m_2|. ∣ V a ( m 1 ) − V a ( m 2 ) ∣ ≤ ( L + + L − ) ∣ m 1 − m 2 ∣.
Taking x 0 = 0 x_0=0 x 0 = 0 , u + ( x ) = x u^+(x)=x u + ( x ) = x , and w + = w − = w w^+=w^-=w w + = w − = w recovers the factor 2 above. The same CDF-sandwich argument used in Lemma H.2 therefore gives
∣ V a h 1 ( f ) − V a h 2 ( f ) ∣ ≤ L + + L − p min sup z ∣ h 1 ( z ∣ a ) − h 2 ( z ∣ a ) ∣ . \left|\mathcal{V}_a^{h_1}(f)-\mathcal{V}_a^{h_2}(f)\right|\le\frac{L^++L^-}{p_{\min}}\sup_z|h_1(z\mid a)-h_2(z\mid a)|. V a h 1 ( f ) − V a h 2 ( f ) ≤ p m i n L + + L − z sup ∣ h 1 ( z ∣ a ) − h 2 ( z ∣ a ) ∣.
Consequently, the regret guarantees extend with the Lipschitz factor 2 replaced throughout by L + + L − L^++L^- L + + L − .
Proof of Lemma B.2 (Bound on Distorted Width)
Proof. The distorted width is defined as the maximum possible difference in the distorted reward between any two functions in the confidence set:
w C t V ( a ) = sup f 1 , f 2 ∈ C t ∣ V a ( f 1 ) − V a ( f 2 ) ∣ w^{\mathcal{V}}_{\mathcal{C}_t}(a)=\sup_{f_1,f_2\in\mathcal{C}_t}\left|\mathcal{V}_a(f_1)-\mathcal{V}_a(f_2)\right| w C t V ( a ) = f 1 , f 2 ∈ C t sup ∣ V a ( f 1 ) − V a ( f 2 ) ∣
From Proposition B.3 , we have the pointwise bound for any pair of functions f 1 , f 2 ∈ C t f_1,f_2\in\mathcal{C}_t f 1 , f 2 ∈ C t :
∣ V a ( f 1 ) − V a ( f 2 ) ∣ ≤ 2 ∣ f 1 ( a ) − f 2 ( a ) ∣ \left|\mathcal{V}_a(f_1)-\mathcal{V}_a(f_2)\right|\leq2\left|f_1(a)-f_2(a)\right| ∣ V a ( f 1 ) − V a ( f 2 ) ∣ ≤ 2 ∣ f 1 ( a ) − f 2 ( a ) ∣
Since this inequality holds for any pair, it must also hold for the supremum over all pairs. We can therefore substitute this bound into the definition of the distorted width:
w C t V ( a ) ≤ 2 ⋅ sup f 1 , f 2 ∈ C t ( ∣ f 1 ( a ) − f 2 ( a ) ∣ ) w^{\mathcal{V}}_{\mathcal{C}_t}(a)\leq2\cdot\sup_{f_1,f_2\in\mathcal{C}_t}\left(\left|f_1(a)-f_2(a)\right|\right) w C t V ( a ) ≤ 2 ⋅ f 1 , f 2 ∈ C t sup ( ∣ f 1 ( a ) − f 2 ( a ) ∣ )
The term inside the parentheses is the definition of the standard width, w C t ( a ) = sup f 1 , f 2 ∈ C t ∣ f 1 ( a ) − f 2 ( a ) ∣ w_{\mathcal{C}_t}(a)=\sup_{f_1,f_2\in\mathcal{C}_t}\left|f_1(a)-f_2(a)\right| w C t ( a ) = sup f 1 , f 2 ∈ C t ∣ f 1 ( a ) − f 2 ( a ) ∣ . Substituting this in yields the final result:
w C t V ( a ) ≤ 2 ( w C t ( a ) ) . w^{\mathcal{V}}_{\mathcal{C}_t}(a)\leq2\left(w_{\mathcal{C}_t}(a)\right). w C t V ( a ) ≤ 2 ( w C t ( a ) ) .
Proof of Theorem 4.2 (General Regret for NPCB)
Proof. By Lemma B.1, with probability at least 1 − δ 1-\delta 1 − δ , f ∗ ∈ C t f^*\in\mathcal{C}_t f ∗ ∈ C t for every t ≤ T t\leq T t ≤ T . On this event, Proposition B.1 and Lemma B.2 give R ( T ) ≤ 2 ∑ t = 1 T w C t ( a t ) R(T)\leq2\sum_{t=1}^{T}w^{\mathcal{C}_t}(a_t) R ( T ) ≤ 2 ∑ t = 1 T w C t ( a t ) . The cumulative-width bound of [31 ] , applied with accuracy α \alpha α , confidence radius β T \beta_T β T , and w C t ( a ) ≤ 2 M w_{\mathcal{C}_t}(a)\leq2M w C t ( a ) ≤ 2 M , yields
∑ t = 1 T w C t ( a t ) ≤ T α + 2 M min { dim E ( F , α ) , T } + 4 T β T min { dim E ( F , α ) , T } . \sum_{t=1}^{T}w_{\mathcal{C}_t}(a_t)\leq T\alpha+2M\min\{\dim_{\mathcal{E}}(\mathcal{F},\alpha),T\}+4\sqrt{T\beta_T\min\{\dim_{\mathcal{E}}(\mathcal{F},\alpha),T\}}. t = 1 ∑ T w C t ( a t ) ≤ T α + 2 M min { dim E ( F , α ) , T } + 4 T β T min { dim E ( F , α ) , T } .
Indeed, when dim E ( F , α ) ≤ T \dim_{\mathcal{E}}(\mathcal{F},\alpha)\leq T dim E ( F , α ) ≤ T this is the standard Eluder-width bound, while otherwise the same inequality follows from the trivial bound w C t ( a t ) ≤ 2 M w_{\mathcal{C}_t}(a_t)\leq2M w C t ( a t ) ≤ 2 M . Substituting α = T − 2 \alpha=T^{-2} α = T − 2 and multiplying by 2 gives R ( T ) ≤ 2 T − 1 + 4 M D T + 8 T β T D T R(T)\leq2T^{-1}+4MD_T+8\sqrt{T\beta_TD_T} R ( T ) ≤ 2 T − 1 + 4 M D T + 8 T β T D T , where D T = min { dim E ( F , T − 2 ) , T } D_T=\min\{\dim_{\mathcal{E}}(\mathcal{F},T^{-2}),T\} D T = min { dim E ( F , T − 2 ) , T } . The displayed O ~ \widetilde{O} O bound follows by substituting the definition of β T \beta_T β T .
Lower Bounds
When w ( p ) = p w(p)=p w ( p ) = p , the distorted value equals the mean reward. Thus any risk-neutral instance that obeys the assumptions of our model is also a CPT instance with a known noise CDF. This gives a reduction for minimax lower bounds on that same instance class. It does not lower-bound the realized regret of every algorithm on every instance.
[33 ] give the Matérn minimax lower-bound exponent ( ν + d ) / ( 2 ν + d ) (\nu+d)/(2\nu+d) ( ν + d ) / ( 2 ν + d ) for a Gaussian-noise RKHS bandit model. Their Gaussian noise has unbounded support. Our bounded-reward assumption does not contain that model as a special case. We therefore do not claim that this result alone proves a matching lower bound for the bounded-reward model studied here. Nor does our KCB theorem attain that exponent: its Matérn upper-bound exponent is 1 / 2 + d / ( 2 ν + d ) 1/2+d/(2\nu+d) 1/2 + d / ( 2 ν + d ) . The two exponents differ by d / [ 2 ( 2 ν + d ) ] d/[2(2\nu+d)] d / [ 2 ( 2 ν + d )] . Theorem 5.4 attains the same upper-bound exponent on its stated domain. The Gaussian-noise lower bound still does not directly establish a lower bound for our bounded-reward class.
Kernel CPT Regret Proof
The algorithm uses the kernel ridge predictor from Algorithm 2. The confidence statement needed here is pointwise. It holds for every arm and every round on one common event.
Lemma E.1 (Pointwise kernel confidence). Assume K ( a , a ) ≤ 1 \mathcal{K}(a,a) \le1 K ( a , a ) ≤ 1 , ∥ f ∗ ∥ K ≤ B \lVert f^* \rVert_{\mathcal{K}} \le B ∥ f ∗ ∥ K ≤ B , and conditionally mean-zero η \eta η -sub-Gaussian noise. Use λ = 1 + 2 / T \lambda= 1 + 2/T λ = 1 + 2/ T and the definitions in Algorithm 2. With probability at least 1 − δ 1-\delta 1 − δ , simultaneously for all t ≤ T t \le T t ≤ T and a ∈ A a \in\mathcal{A} a ∈ A ,
∣ f ∗ ( a ) − μ t − 1 ( a ) ∣ ≤ β t σ t − 1 ( a ) , β t = B + η 2 ( γ t − 1 ( λ ) + 1 + log ( 1 / δ ) ) . \lvert f^*(a)-\mu_{t-1}(a)\rvert\le\sqrt{\beta_t}\,\sigma_{t-1}(a),\qquad\sqrt{\beta_t}=B+\eta\sqrt{2\left(\gamma_{t-1}(\lambda)+1+\log(1/\delta)\right)}. ∣ f ∗ ( a ) − μ t − 1 ( a )∣ ≤ β t σ t − 1 ( a ) , β t = B + η 2 ( γ t − 1 ( λ ) + 1 + log ( 1/ δ ) ) .
Proof. Apply [9 Theorem 2] with its regularization 1 + 2 / T 1+2/T 1 + 2/ T . The theorem is simultaneous in the arm and round. It applies to conditionally mean-zero sub-Gaussian noise. □ \square □
Lemma E.2 (Optimistic distorted value). On the event of Lemma E.1,
V a ( f ∗ ) ≤ V a ( U t ( a ) ) for every a ∈ A and t ≤ T . \mathcal{V}_a(f^*) \le\mathcal{V}_a(U_t(a)) \qquad\text{for every } a \in\mathcal{A} \text{ and } t \le T. V a ( f ∗ ) ≤ V a ( U t ( a )) for every a ∈ A and t ≤ T .
Proof. The pointwise confidence bound gives f ∗ ( a ) ≤ U t ( a ) f^*(a) \le U_t(a) f ∗ ( a ) ≤ U t ( a ) . The integral identity in the proof of Proposition B.3 shows that V a ( m ) \mathcal{V}_a(m) V a ( m ) is increasing in m m m . Apply this fact to the two means. □ \square □
Lemma E.3 (Instantaneous CPT regret). On the same event, for the arm selected by Algorithm 2,
V a ∗ ( f ∗ ) − V a t ( f ∗ ) ≤ 4 β t σ t − 1 ( a t ) . \mathcal{V}_{a^*}(f^*)-\mathcal{V}_{a_t}(f^*) \le4\sqrt{\beta_t}\,\sigma_{t-1}(a_t). V a ∗ ( f ∗ ) − V a t ( f ∗ ) ≤ 4 β t σ t − 1 ( a t ) .
Proof. Optimism and the choice of a t a_t a t give
V a ∗ ( f ∗ ) ≤ V a ∗ ( U t ( a ∗ ) ) ≤ V a t ( U t ( a t ) ) . \mathcal{V}_{a^*}(f^*) \le\mathcal{V}_{a^*}(U_t(a^*)) \le\mathcal{V}_{a_t}(U_t(a_t)). V a ∗ ( f ∗ ) ≤ V a ∗ ( U t ( a ∗ )) ≤ V a t ( U t ( a t )) .
The distorted value is 2-Lipschitz in the mean. Thus the regret is at most 2 ( U t ( a t ) − f ∗ ( a t ) ) 2(U_t(a_t)-f^*(a_t)) 2 ( U t ( a t ) − f ∗ ( a t )) . The two sides of the pointwise confidence bound give U t ( a t ) − f ∗ ( a t ) ≤ 2 β t σ t − 1 ( a t ) U_t(a_t)-f^*(a_t) \le2\sqrt{\beta_t}\sigma_{t-1}(a_t) U t ( a t ) − f ∗ ( a t ) ≤ 2 β t σ t − 1 ( a t ) . □ \square □
Proof of Theorem 5.3 (Kernel CPT regret)
Proof. Sum Lemma E.3 and apply Cauchy–Schwarz:
R ( T ) ≤ 4 β T T ∑ t = 1 T σ t − 1 2 ( a t ) . R(T) \le4\sqrt{\beta_T}\sqrt{T\sum_{t=1}^{T}\sigma_{t-1}^2(a_t)}. R ( T ) ≤ 4 β T T t = 1 ∑ T σ t − 1 2 ( a t ) .
The determinant identity gives
1 2 log det ( I + λ − 1 K T ) = 1 2 ∑ t = 1 T log ( 1 + σ t − 1 2 ( a t ) / λ ) . \frac{1}{2}\log\det(I+\lambda^{-1}K_T)=\frac{1}{2}\sum_{t=1}^{T}\log(1+\sigma_{t-1}^2(a_t)/\lambda). 2 1 log det ( I + λ − 1 K T ) = 2 1 t = 1 ∑ T log ( 1 + σ t − 1 2 ( a t ) / λ ) .
Since 0 ≤ σ t − 1 2 ( a t ) ≤ 1 0 \le\sigma_{t-1}^2(a_t) \le1 0 ≤ σ t − 1 2 ( a t ) ≤ 1 , concavity of the logarithm gives
log ( 1 + σ t − 1 2 ( a t ) / λ ) ≥ σ t − 1 2 ( a t ) log ( 1 + 1 / λ ) . \log(1+\sigma_{t-1}^2(a_t)/\lambda)\ge\sigma_{t-1}^2(a_t)\log(1+1/\lambda). log ( 1 + σ t − 1 2 ( a t ) / λ ) ≥ σ t − 1 2 ( a t ) log ( 1 + 1/ λ ) .
The selected sequence has information gain at most γ T ( λ ) \gamma_T(\lambda) γ T ( λ ) . Therefore
∑ t = 1 T σ t − 1 2 ( a t ) ≤ 2 γ T ( λ ) log ( 1 + 1 / λ ) . \sum_{t=1}^{T}\sigma_{t-1}^2(a_t)\le\frac{2\gamma_T(\lambda)}{\log(1+1/\lambda)}. t = 1 ∑ T σ t − 1 2 ( a t ) ≤ log ( 1 + 1/ λ ) 2 γ T ( λ ) .
Substitute this bound and the definition of β T \beta_T β T . □ \square □
Algorithm 3: CPT Batched Pure Exploration. (CPT-BPE)
Input: finite arm set A \mathcal{A} A , horizon T T T , kernel K \mathcal{K} K , norm bound B B B , noise bound η \eta η , regularization λ > 0 \lambda> 0 λ > 0 , confidence level δ \delta δ , weight w w w , and known noise CDFs { F ϵ a } a ∈ A \{F_{\epsilon_a}\}_{a\in\mathcal{A}} { F ϵ a } a ∈ A .
Set A 1 = A \mathcal{A}_1 = \mathcal{A} A 1 = A , n 0 = 1 n_0 = 1 n 0 = 1 , and n i = ⌈ T n i − 1 ⌉ n_i = \lceil\sqrt{T n_{i-1}}\rceil n i = ⌈ T n i − 1 ⌉ for i ≥ 1 i \ge1 i ≥ 1 .
Let m m m be the smallest integer such that ∑ i = 1 m n i ≥ T \sum_{i=1}^{m} n_i \ge T ∑ i = 1 m n i ≥ T , and set
c = B + η λ 2 log 2 m ∣ A ∣ δ . c = B + \frac{\eta}{\sqrt{\lambda}}\sqrt{2\log\frac{2m|\mathcal{A}|}{\delta}}. c = B + λ η 2 log δ 2 m ∣ A ∣ .
Set the global round counter t = 1 t = 1 t = 1 .
for i = 1 , … , m i = 1,\ldots,m i = 1 , … , m do
Set the phase length N i = min { n i , T − t + 1 } N_i = \min\{n_i,T-t+1\} N i = min { n i , T − t + 1 } .
Initialize the phase design with no sampled locations.
for j = 1 , … , N i j = 1,\ldots,N_i j = 1 , … , N i do
Compute the kernel posterior variance σ i , j − 1 2 ( a ) \sigma_{i,j-1}^2(a) σ i , j − 1 2 ( a ) using only the arms pulled earlier in phase i i i .
Choose
a t ∈ arg max a ∈ A i σ i , j − 1 ( a ) . a_t \in\arg\max_{a\in\mathcal{A}_i}\sigma_{i,j-1}(a). a t ∈ arg a ∈ A i max σ i , j − 1 ( a ) .
Observe r t r_t r t and store ( a t , r t ) (a_t,r_t) ( a t , r t ) for this phase.
Set t ← t + 1 t \leftarrow t+1 t ← t + 1 .
end for
Fit kernel ridge regression using only the rewards and arms from phase i i i ; denote the resulting predictor and posterior standard deviation by μ i \mu_i μ i and σ i \sigma_i σ i .
if t ≤ T t \le T t ≤ T then
Set
A i + 1 = { a ∈ A i : V a ( μ i ( a ) + c σ i ( a ) ) ≥ max b ∈ A i V b ( μ i ( b ) − c σ i ( b ) ) } . \mathcal{A}_{i+1}=\left\{a\in\mathcal{A}_i:\mathcal{V}_a(\mu_i(a)+c\sigma_i(a))\ge\max_{b\in\mathcal{A}_i}\mathcal{V}_b(\mu_i(b)-c\sigma_i(b))\right\}. A i + 1 = { a ∈ A i : V a ( μ i ( a ) + c σ i ( a )) ≥ b ∈ A i max V b ( μ i ( b ) − c σ i ( b )) } .
end if
end for
Remark E.1 (Fixed design within each phase). Ties in the variance rule are broken independently of the current-phase rewards. Conditional on the earlier phases, the arms pulled in phase i i i are therefore determined without using the rewards from that phase. Hence the phase-i i i data form the fixed-design setting used in Lemma E.4.
Lemma E.4 (Confidence from one phase). Fix a phase whose sampling locations do not use the rewards from that phase. Conditional on the earlier phases, for each arm a a a and each u > 0 u>0 u > 0 ,
P { ∣ f ∗ ( a ) − μ i ( a ) ∣ > ( B + η λ 2 u ) σ i ( a ) } ≤ 2 e − u . \mathbb{P}\left\{\left|f^*(a)-\mu_i(a)\right|>\left(B+\frac{\eta}{\sqrt{\lambda}}\sqrt{2u}\right)\sigma_i(a)\right\}\le2e^{-u}. P { ∣ f ∗ ( a ) − μ i ( a ) ∣ > ( B + λ η 2 u ) σ i ( a ) } ≤ 2 e − u . The phase noises may have different distributions at different arms. They must be independent conditional on the chosen locations and satisfy the uniform η \eta η -sub-Gaussian bound.
Proof. Write ϕ ( a ) = K ( ⋅ , a ) \phi(a)=\mathcal{K}(\cdot,a) ϕ ( a ) = K ( ⋅ , a ) and V = λ I + ∑ j = 1 n i ϕ ( a j ) ⊗ ϕ ( a j ) V=\lambda I+\sum_{j=1}^{n_i}\phi(a_j)\otimes\phi(a_j) V = λ I + ∑ j = 1 n i ϕ ( a j ) ⊗ ϕ ( a j ) . Then σ i 2 ( a ) = λ ⟨ ϕ ( a ) , V − 1 ϕ ( a ) ⟩ \sigma_i^2(a)=\lambda\langle\phi(a),V^{-1}\phi(a)\rangle σ i 2 ( a ) = λ ⟨ ϕ ( a ) , V − 1 ϕ ( a )⟩ . The ridge bias is at most B σ i ( a ) B\sigma_i(a) B σ i ( a ) . The noise term is ∑ j b j ϵ j \sum_j b_j\epsilon_j ∑ j b j ϵ j , where b j = ⟨ ϕ ( a ) , V − 1 ϕ ( a j ) ⟩ b_j=\langle\phi(a),V^{-1}\phi(a_j)\rangle b j = ⟨ ϕ ( a ) , V − 1 ϕ ( a j )⟩ . Moreover, $\sum_j b_j^2\le
@page 23/46 starts_mid=0 ends_mid=1 Algorithm 3: CPT Batched Pure Exploration. (CPT-BPE)
Input: finite arm set A \mathcal{A} A , horizon T T T , kernel K \mathcal{K} K , norm bound B B B , noise bound η \eta η , regularization λ > 0 \lambda> 0 λ > 0 , confidence level δ \delta δ , weight w w w , and known noise CDFs { F ϵ a } a ∈ A \{F_{\epsilon_a}\}_{a\in\mathcal{A}} { F ϵ a } a ∈ A .
Set A 1 = A \mathcal{A}_1=\mathcal{A} A 1 = A , n 0 = 1 n_0=1 n 0 = 1 , and n i = ⌈ T n i − 1 ⌉ n_i=\lceil\sqrt{Tn_{i-1}}\rceil n i = ⌈ T n i − 1 ⌉ for i ≥ 1 i\ge1 i ≥ 1 .
Let m m m be the smallest integer such that ∑ i = 1 m n i ≥ T \sum_{i=1}^{m}n_i\ge T ∑ i = 1 m n i ≥ T , and set
c = B + η λ 2 log 2 m ∣ A ∣ δ . c=B+\frac{\eta}{\sqrt{\lambda}}\sqrt{2\log\frac{2m|\mathcal{A}|}{\delta}}. c = B + λ η 2 log δ 2 m ∣ A ∣ .
Set the global round counter t = 1 t=1 t = 1 .
for i = 1 , … , m i=1,\ldots,m i = 1 , … , m do
Set the phase length N i = min { n i , T − t + 1 } N_i=\min\{n_i,T-t+1\} N i = min { n i , T − t + 1 } .
Initialize the phase design with no sampled locations.
for j = 1 , … , N i j=1,\ldots,N_i j = 1 , … , N i do
Compute the kernel posterior variance σ i , j − 1 2 ( a ) \sigma_{i,j-1}^{2}(a) σ i , j − 1 2 ( a ) using only the arms pulled earlier in phase i i i .
Choose
a t ∈ arg max a ∈ A i σ i , j − 1 ( a ) . a_t\in\arg\max_{a\in\mathcal{A}_i}\sigma_{i,j-1}(a). a t ∈ arg a ∈ A i max σ i , j − 1 ( a ) .
Observe r t r_t r t and store ( a t , r t ) (a_t,r_t) ( a t , r t ) for this phase.
Set t ← t + 1 t\leftarrow t+1 t ← t + 1 .
end for
Fit kernel ridge regression using only the rewards and arms from phase i i i ; denote the resulting predictor and posterior standard deviation by μ i \mu_i μ i and σ i \sigma_i σ i .
if t ≤ T t\le T t ≤ T then
Set
A i + 1 = { a ∈ A i : V a ( μ i ( a ) + c σ i ( a ) ) ≥ max b ∈ A i V b ( μ i ( b ) − c σ i ( b ) ) } . \mathcal{A}_{i+1}=\left\{a\in\mathcal{A}_i:\mathcal{V}_a(\mu_i(a)+c\sigma_i(a))\ge\max_{b\in\mathcal{A}_i}\mathcal{V}_b(\mu_i(b)-c\sigma_i(b))\right\}. A i + 1 = { a ∈ A i : V a ( μ i ( a ) + c σ i ( a )) ≥ b ∈ A i max V b ( μ i ( b ) − c σ i ( b )) } .
end if
end for
Remark E.1 (Fixed design within each phase). Ties in the variance rule are broken independently of the current-phase rewards. Conditional on the earlier phases, the arms pulled in phase i i i are therefore determined without using the rewards from that phase. Hence the phase-i i i data form the fixed-design setting used in Lemma E.4.
Lemma E.4 (Confidence from one phase). Fix a phase whose sampling locations do not use the rewards from that phase. Conditional on the earlier phases, for each arm a a a and each u > 0 u>0 u > 0 ,
P { ∣ f ∗ ( a ) − μ i ( a ) ∣ > ( B + η λ 2 u ) σ i ( a ) } ≤ 2 e − u . \mathbb{P}\left\{\left|f^*(a)-\mu_i(a)\right|>\left(B+\frac{\eta}{\sqrt{\lambda}}\sqrt{2u}\right)\sigma_i(a)\right\}\le2e^{-u}. P { ∣ f ∗ ( a ) − μ i ( a ) ∣ > ( B + λ η 2 u ) σ i ( a ) } ≤ 2 e − u . The phase noises may have different distributions at different arms. They must be independent conditional on the chosen locations and satisfy the uniform η \eta η -sub-Gaussian bound.
Proof. Write ϕ ( a ) = K ( ⋅ , a ) \phi(a)=\mathcal{K}(\cdot,a) ϕ ( a ) = K ( ⋅ , a ) and V = λ I + ∑ j = 1 n i ϕ ( a j ) ⊗ ϕ ( a j ) V=\lambda I+\sum_{j=1}^{n_i}\phi(a_j)\otimes\phi(a_j) V = λ I + ∑ j = 1 n i ϕ ( a j ) ⊗ ϕ ( a j ) . Then σ i 2 ( a ) = λ ⟨ ϕ ( a ) , V − 1 ϕ ( a ) ⟩ \sigma_i^2(a)=\lambda\langle\phi(a),V^{-1}\phi(a)\rangle σ i 2 ( a ) = λ ⟨ ϕ ( a ) , V − 1 ϕ ( a )⟩ . The ridge bias is at most B σ i ( a ) B\sigma_i(a) B σ i ( a ) . The noise term is ∑ j b j ϵ j \sum_j b_j\epsilon_j ∑ j b j ϵ j , where b j = ⟨ ϕ ( a ) , V − 1 ϕ ( a j ) ⟩ b_j=\langle\phi(a),V^{-1}\phi(a_j)\rangle b j = ⟨ ϕ ( a ) , V − 1 ϕ ( a j )⟩ . Moreover, $\sum_j b_j^2\le σ i 2 ( a ) / λ \sigma_i^2(a)/\lambda σ i 2 ( a ) / λ . Hence its conditional sub-Gaussian variance proxy is at most η 2 σ i 2 ( a ) / λ \eta^2\sigma_i^2(a)/\lambda η 2 σ i 2 ( a ) / λ . Conditional sub-Gaussian concentration proves the claim.
Proof of Theorem 5.4 (Phasewise kernel CPT regret)
Proof. Use Lemma E.4 with u = log ( 2 m ∣ A ∣ / δ ) u = \log(2m|\mathcal{A}|/\delta) u = log ( 2 m ∣ A ∣/ δ ) . A union bound gives, in every phase and for every arm,
∣ f ∗ ( a ) − μ i ( a ) ∣ ≤ c σ i ( a ) |f^*(a)-\mu_i(a)| \le c\sigma_i(a) ∣ f ∗ ( a ) − μ i ( a ) ∣ ≤ c σ i ( a )
with probability at least 1 − δ 1-\delta 1 − δ . The inequality also holds when earlier phases and their surviving sets depend on past rewards: condition on that past.
Fix this event. The optimal arm a ∗ a^* a ∗ is never eliminated. Indeed, its upper CPT bound is at least its true value, which is at least every lower CPT bound. For any a ∈ A i + 1 a \in\mathcal{A}_{i+1} a ∈ A i + 1 , the elimination rule and the 2-Lipschitz property give
V a ∗ ( f ∗ ) − V a ( f ∗ ) ≤ 4 c σ i ( a ∗ ) + 4 c σ i ( a ) ≤ 8 c max b ∈ A i σ i ( b ) . \mathcal{V}_{a^*}(f^*)-\mathcal{V}_{a}(f^*) \le4c\sigma_i(a^*)+4c\sigma_i(a) \le8c\max_{b\in\mathcal{A}_i}\sigma_i(b). V a ∗ ( f ∗ ) − V a ( f ∗ ) ≤ 4 c σ i ( a ∗ ) + 4 c σ i ( a ) ≤ 8 c b ∈ A i max σ i ( b ) .
For clarity, each confidence interval for the CPT value has total width at most 4 c σ i ( a ) 4c\sigma_i(a) 4 c σ i ( a ) .
The variance-greedy choice gives
n i max a ∈ A i σ i 2 ( a ) ≤ ∑ j = 1 n i σ i , j − 1 2 ( a j ) ≤ C λ γ n i ( λ ) , C λ = 2 log ( 1 + 1 / λ ) . n_i\max_{a\in\mathcal{A}_i}\sigma_i^2(a) \le\sum_{j=1}^{n_i}\sigma_{i,j-1}^2(a_j) \le C_\lambda\gamma_{n_i}(\lambda), \qquad C_\lambda=\frac{2}{\log(1+1/\lambda)}. n i a ∈ A i max σ i 2 ( a ) ≤ j = 1 ∑ n i σ i , j − 1 2 ( a j ) ≤ C λ γ n i ( λ ) , C λ = log ( 1 + 1/ λ ) 2 .
The first inequality holds because variance decreases as locations are added. The second follows from the determinant identity and K ( a , a ) ≤ 1 \mathcal{K}(a,a)\le1 K ( a , a ) ≤ 1 . Thus every action in phase i + 1 i+1 i + 1 has regret at most 8 c C λ γ T ( λ ) / n i 8c\sqrt{C_\lambda\gamma_T(\lambda)/n_i} 8 c C λ γ T ( λ ) / n i . The first phase has at most 2 M n 1 2Mn_1 2 M n 1 regret. Sum these bounds over phases. The planned lengths obey
n i n i − 1 ≤ T + 1. \frac{n_i}{\sqrt{n_{i-1}}}\le\sqrt{T}+1. n i − 1 n i ≤ T + 1.
Truncating the last phase can only decrease its contribution. The schedule reaches the horizon in O ( log log T ) O(\log\log T) O ( log log T ) phases [27 ] . This proves the displayed bound. □
From finite arms to a continuous domain
Let A ⊂ R d \mathcal{A}\subset\mathbb{R}^d A ⊂ R d be nonempty and compact. Write g ( a ) = V a ( f ∗ ( a ) ) g(a)=\mathcal{V}_a(f^*(a)) g ( a ) = V a ( f ∗ ( a )) for the true CPT value. In addition to the assumptions of Theorem 5.4, assume ∣ g ( a ) − g ( b ) ∣ ≤ L ∥ a − b ∥ α |g(a)-g(b)|\le L\lVert a-b\rVert^\alpha ∣ g ( a ) − g ( b ) ∣ ≤ L ∥ a − b ∥ α for all a , b ∈ A a,b\in\mathcal{A} a , b ∈ A , with fixed L < ∞ L<\infty L < ∞ and α > 0 \alpha>0 α > 0 . The norm is Euclidean. This assumption makes g g g continuous, so it attains its maximum on A \mathcal{A} A .
A finite set of feasible arms. For 0 < h ≤ 1 0<h\le1 0 < h ≤ 1 , partition a bounding box of A \mathcal{A} A into cubes of side h / d h/\sqrt{d} h / d . Choose one representative in A \mathcal{A} A from each cube that intersects A \mathcal{A} A . The resulting deterministic set A h ⊂ A \mathcal{A}_h\subset\mathcal{A} A h ⊂ A satisfies ∣ A h ∣ ≤ C A h − d |\mathcal{A}_h|\le C_{\mathcal{A}}h^{-d} ∣ A h ∣ ≤ C A h − d , where C A C_{\mathcal{A}} C A depends only on the domain and d d d . Every a ∈ A a\in\mathcal{A} a ∈ A has a representative in A h \mathcal{A}_h A h at distance at most h h h . Set h T = T − 1 / ( 2 α ) h_T=T^{-1/(2\alpha)} h T = T − 1/ ( 2 α ) and A T = A h T \mathcal{A}_T=\mathcal{A}_{h_T} A T = A h T before collecting rewards. Thus ∣ A T ∣ ≤ C A T d / ( 2 α ) |\mathcal{A}_T|\le C_{\mathcal{A}}T^{d/(2\alpha)} ∣ A T ∣ ≤ C A T d / ( 2 α ) . Run Algorithm 3 on A T \mathcal{A}_T A T , using the original kernel and noise law at each representative. The restriction of f ∗ f^* f ∗ to A T \mathcal{A}_T A T belongs to the RKHS of the restricted kernel and has RKHS norm at most B B B .
Regret against the continuous optimum. Let a ∗ ∈ arg max a ∈ A g ( a ) a^*\in\arg\max_{a\in\mathcal{A}}g(a) a ∗ ∈ arg max a ∈ A g ( a ) and a T ∗ ∈ arg max a ∈ A T g ( a ) a_T^*\in\arg\max_{a\in\mathcal{A}_T}g(a) a T ∗ ∈ arg max a ∈ A T g ( a ) . Taking a representative of a ∗ a^* a ∗ gives 0 ≤ g ( a ∗ ) − g ( a T ∗ ) ≤ L h T α 0\le g(a^*)-g(a_T^*)\le Lh_T^\alpha 0 ≤ g ( a ∗ ) − g ( a T ∗ ) ≤ L h T α . For the actions a t ∈ A T a_t\in\mathcal{A}_T a t ∈ A T selected by the algorithm, define R g r i d ( T ) = ∑ t = 1 T [ g ( a t ⋆ ) − g ( a t ) ] R_{\mathrm{grid}}(T)=\sum_{t=1}^{T}[g(a_t^\star)-g(a_t)] R grid ( T ) = ∑ t = 1 T [ g ( a t ⋆ ) − g ( a t )] . Then
R c o n t ( T ) = ∑ t = 1 T [ g ( a ⋆ ) − g ( a t ) ] = R g r i d ( T ) + T [ g ( a ⋆ ) − g ( a T ⋆ ) ] ≤ R g r i d ( T ) + L T . \begin{aligned}
R_{\mathrm{cont}}(T) &= \sum_{t=1}^{T}[g(a^\star)-g(a_t)]\\
&=R_{\mathrm{grid}}(T)+T[g(a^\star)-g(a_T^\star)]\\
&\le R_{\mathrm{grid}}(T)+L\sqrt{T}.
\end{aligned} R cont ( T ) = t = 1 ∑ T [ g ( a ⋆ ) − g ( a t )] = R grid ( T ) + T [ g ( a ⋆ ) − g ( a T ⋆ )] ≤ R grid ( T ) + L T .
Applying the finite-arm theorem. Use the phase schedule of Algorithm 3 and set
c T = B + η λ 2 log 2 m ∣ A T ∣ δ . c_T=B+\frac{\eta}{\sqrt{\lambda}}\sqrt{2\log\frac{2m|\mathcal{A}_T|}{\delta}}. c T = B + λ η 2 log δ 2 m ∣ A T ∣ .
The confidence union bound is over the m m m phases and the finite set A T \mathcal{A}_T A T . No union bound over the continuous domain is needed. The information gain over A T \mathcal{A}_T A T is at most γ T ( λ ) \gamma_T(\lambda) γ T ( λ ) , since every sequence of arms in A T \mathcal{A}_T A T is also a sequence in A \mathcal{A} A . Theorem 5.4 therefore gives, with probability at least 1 − δ 1-\delta 1 − δ ,
R c o n t ( T ) ≤ L T + 2 M ⌈ T ⌉ + 8 c T C λ γ T ( λ ) ∑ i = 2 m n i n i − 1 . R_{\mathrm{cont}}(T)\le L\sqrt{T}+2M\lceil\sqrt{T}\rceil
+8c_T\sqrt{C_\lambda\gamma_T(\lambda)}\sum_{i=2}^{m}\frac{n_i}{\sqrt{n_i-1}}. R cont ( T ) ≤ L T + 2 M ⌈ T ⌉ + 8 c T C λ γ T ( λ ) i = 2 ∑ m n i − 1 n i .
The final phase uses its actual length in this sum. Polynomial grid size contributes only a logarithmic factor to c T c_T c T . Hence the bound is O ~ ( T γ T ( λ ) + T ) \widetilde{O}(\sqrt{T\gamma_T(\lambda)}+\sqrt{T}) O ( T γ T ( λ ) + T ) for fixed model and regularity constants. Under the stated Matérn information-gain bound, this is O ~ ( T ( ν + d ) / ( 2 ν + d ) ) \widetilde{O}(T^{(\nu+d)/(2\nu+d)}) O ( T ( ν + d ) / ( 2 ν + d ) ) .
When the regularity assumption holds. The exponent α \alpha α describes variation across arms, not regularity of the probability-weighting function. Smoothness of f ⋆ f^\star f ⋆ alone does not control arbitrary arm-dependent noise laws. A sufficient condition is ∣ f ⋆ ( a ) − f ⋆ ( b ) ∣ ≤ L f ∥ a − b ∥ α |f^\star(a)-f^\star(b)|\le L_f\|a-b\|^\alpha ∣ f ⋆ ( a ) − f ⋆ ( b ) ∣ ≤ L f ∥ a − b ∥ α and ∣ V a ( m ) − V b ( m ) ∣ ≤ L ϵ ∥ a − b ∥ α |V_a(m)-V_b(m)|\le L_\epsilon\|a-b\|^\alpha ∣ V a ( m ) − V b ( m ) ∣ ≤ L ϵ ∥ a − b ∥ α uniformly over m ∈ f ⋆ ( A ) m\in f^\star(\mathcal{A}) m ∈ f ⋆ ( A ) .
For example, if the kernel satisfies ∥ K ( ⋅ , a ) − K ( ⋅ , b ) ∥ K ≤ L K ∥ a − b ∥ α \|K(\cdot,a)-K(\cdot,b)\|_K\le L_K\|a-b\|^\alpha ∥ K ( ⋅ , a ) − K ( ⋅ , b ) ∥ K ≤ L K ∥ a − b ∥ α , then the reproducing property and ∥ f ⋆ ∥ K ≤ B \|f^\star\|_K\le B ∥ f ⋆ ∥ K ≤ B give ∣ f ⋆ ( a ) − f ⋆ ( b ) ∣ ≤ B L K ∥ a − b ∥ α |f^\star(a)-f^\star(b)|\le BL_K\|a-b\|^\alpha ∣ f ⋆ ( a ) − f ⋆ ( b ) ∣ ≤ B L K ∥ a − b ∥ α . Thus one may take L f = B L K L_f=BL_K L f = B L K . This kernel regularity is an additional sufficient condition and does not follow from K ( a , a ) ≤ 1 K(a,a)\le1 K ( a , a ) ≤ 1 alone.
Using the established 2-Lipschitz property in the mean,
∣ g ( a ) − g ( b ) ∣ ≤ ∣ V a ( f ⋆ ( a ) ) − V a ( f ⋆ ( b ) ) ∣ + ∣ V a ( f ⋆ ( b ) ) − V b ( f ⋆ ( b ) ) ∣ ≤ ( 2 L f + L ϵ ) ∥ a − b ∥ α . \begin{aligned}
|g(a)-g(b)| &\le|V_a(f^\star(a))-V_a(f^\star(b))|\\
&\quad+|V_a(f^\star(b))-V_b(f^\star(b))|\\
&\le(2L_f+L_\epsilon)\|a-b\|^\alpha.
\end{aligned} ∣ g ( a ) − g ( b ) ∣ ≤ ∣ V a ( f ⋆ ( a )) − V a ( f ⋆ ( b )) ∣ + ∣ V a ( f ⋆ ( b )) − V b ( f ⋆ ( b )) ∣ ≤ ( 2 L f + L ϵ ) ∥ a − b ∥ α .
If all arms share the same additive noise law, the second term vanishes and one may take L = 2 L f L=2L_f L = 2 L f .
Omitted Proofs from Section 5
Kernel ridge estimator
Lemma F.1 (Regularized least squares). For every fixed λ > 0 \lambda>0 λ > 0 , the function
μ t − 1 = arg min f ∈ H K { ∑ s < t ( r s − f ( a s ) ) 2 + λ ∥ f ∥ K 2 } \mu_{t-1}=\underset{f\in\mathcal{H}_K}{\arg\min}\left\{\sum_{s<t}(r_s-f(a_s))^2+\lambda\|f\|_K^2\right\} μ t − 1 = f ∈ H K arg min { s < t ∑ ( r s − f ( a s ) ) 2 + λ ∥ f ∥ K 2 }
satisfies μ t − 1 ( a ) = k t − 1 ( a ) ⊤ ( K t − 1 + λ I ) − 1 r t − 1 \mu_{t-1}(a)=\mathbf{k}_{t-1}(a)^{\top}(K_{t-1}+\lambda I)^{-1}r_{t-1} μ t − 1 ( a ) = k t − 1 ( a ) ⊤ ( K t − 1 + λ I ) − 1 r t − 1 . This need not be the minimizer of unregularized square loss over the fixed ball ∥ f ∥ K ≤ B \|f\|_{\mathcal{K}}\le B ∥ f ∥ K ≤ B .
Proof. The representer theorem puts the minimizer in the span of the kernel sections at the observed arms. Set α = ( K t − 1 + λ I ) − 1 r t − 1 \alpha=(K_{t-1}+\lambda I)^{-1}r_{t-1} α = ( K t − 1 + λ I ) − 1 r t − 1 and f = ∑ s < t α s K ( ⋅ , a s ) f=\sum_{s<t}\alpha_s\mathcal{K}(\cdot,a_s) f = ∑ s < t α s K ( ⋅ , a s ) . This f f f satisfies the normal equation for the regularized objective. That objective is strictly convex because λ > 0 \lambda>0 λ > 0 . Hence f f f is its unique minimizer, even if K t − 1 K_{t-1} K t − 1 is singular. Evaluating f f f at a a a gives the formula. □
Proof of Lemma 5.1 (Eluder Dimension and Information Gain)
Proof. Fix ε > 0 \varepsilon>0 ε > 0 and put ρ = ( ε / 2 B ) 2 \rho=(\varepsilon/2B)^2 ρ = ( ε /2 B ) 2 . Suppose, toward a contradiction, that dim E ( F , ε ) ≥ n \dim_E(\mathcal{F},\varepsilon)\ge n dim E ( F , ε ) ≥ n . Then there are ε ′ ≥ ε \varepsilon'\ge\varepsilon ε ′ ≥ ε and arms a 1 , … , a n a_1,\ldots,a_n a 1 , … , a n such that, for every i i i , some f i , f ~ i ∈ F f_i,\tilde f_i\in\mathcal{F} f i , f ~ i ∈ F satisfy ∑ j < i ( f i ( a j ) − f ~ i ( a j ) ) 2 ≤ ( ε ′ ) 2 \sum_{j<i}(f_i(a_j)-\tilde f_i(a_j))^2\le(\varepsilon')^2 ∑ j < i ( f i ( a j ) − f ~ i ( a j ) ) 2 ≤ ( ε ′ ) 2 and ∣ f i ( a i ) − f ~ i ( a i ) ∣ > ε ′ |f_i(a_i)-\tilde f_i(a_i)|>\varepsilon' ∣ f i ( a i ) − f ~ i ( a i ) ∣ > ε ′ .
Let g i = f i − f ~ i g_i=f_i-\tilde f_i g i = f i − f ~ i . Since ∥ g i ∥ K ≤ 2 B \|g_i\|_{\mathcal{K}}\le2B ∥ g i ∥ K ≤ 2 B , define V i − 1 = ρ I + ∑ j < i K ( ⋅ , a j ) ⊗ K ( ⋅ , a j ) V_{i-1}=\rho I+\sum_{j<i}\mathcal{K}(\cdot,a_j)\otimes\mathcal{K}(\cdot,a_j) V i − 1 = ρ I + ∑ j < i K ( ⋅ , a j ) ⊗ K ( ⋅ , a j ) . Then
∥ g i ∥ V i − 1 2 = ρ ∥ g i ∥ K 2 + ∑ j < i g i ( a j ) 2 ≤ ε 2 + ( ε ′ ) 2 ≤ 2 ( ε ′ ) 2 . \|g_i\|_{V_{i-1}}^2=\rho\|g_i\|_{\mathcal{K}}^2+\sum_{j<i}g_i(a_j)^2
\le\varepsilon^2+(\varepsilon')^2\le2(\varepsilon')^2. ∥ g i ∥ V i − 1 2 = ρ ∥ g i ∥ K 2 + j < i ∑ g i ( a j ) 2 ≤ ε 2 + ( ε ′ ) 2 ≤ 2 ( ε ′ ) 2 .
By the reproducing property and Cauchy–Schwarz,
g i ( a i ) 2 ≤ ∥ g i ∥ V i − 1 2 ∥ K ( ⋅ , a i ) ∥ V i − 1 − 1 2 . g_i(a_i)^2\le\|g_i\|_{V_{i-1}}^2\|\mathcal{K}(\cdot,a_i)\|_{V_{i-1}^{-1}}^2. g i ( a i ) 2 ≤ ∥ g i ∥ V i − 1 2 ∥ K ( ⋅ , a i ) ∥ V i − 1 − 1 2 .
Hence ∥ K ( ⋅ , a i ) ∥ V i − 1 − 1 2 > 1 / 2 \|\mathcal{K}(\cdot,a_i)\|_{V_{i-1}^{-1}}^2>1/2 ∥ K ( ⋅ , a i ) ∥ V i − 1 − 1 2 > 1/2 .
The determinant identity therefore gives
log det ( I + ρ − 1 K n ) = ∑ i = 1 n log ( 1 + ∥ K ( ⋅ , a i ) ∥ V i − 1 − 1 2 ) > n log ( 3 / 2 ) . \log\det(I+\rho^{-1}K_n)=\sum_{i=1}^{n}\log\left(1+\|\mathcal{K}(\cdot,a_i)\|_{V_{i-1}^{-1}}^2\right)>n\log(3/2). log det ( I + ρ − 1 K n ) = i = 1 ∑ n log ( 1 + ∥ K ( ⋅ , a i ) ∥ V i − 1 − 1 2 ) > n log ( 3/2 ) .
For the particular sequence a 1 , … , a n a_1,\ldots,a_n a 1 , … , a n constructed above,
1 2 log det ( I + ρ − 1 K n ) > n 2 log ( 3 / 2 ) . \frac{1}{2}\log\det(I+\rho^{-1}K_n)>\frac{n}{2}\log(3/2). 2 1 log det ( I + ρ − 1 K n ) > 2 n log ( 3/2 ) .
Since γ n ( ρ ) \gamma_n(\rho) γ n ( ρ ) is the supremum of this quantity over all sequences of n n n arms, γ n ( ρ ) > n log ( 3 / 2 ) / 2 \gamma_n(\rho)>n\log(3/2)/2 γ n ( ρ ) > n log ( 3/2 ) /2 . This contradicts the assumption γ n ( ρ ) ≤ n log ( 3 / 2 ) / 2 \gamma_n(\rho)\le n\log(3/2)/2 γ n ( ρ ) ≤ n log ( 3/2 ) /2 . Therefore dim E ( F , ε ) < n \dim_E(\mathcal{F},\varepsilon)<n dim E ( F , ε ) < n .
If γ n ( ρ ) = o ( n ) \gamma_n(\rho)=o(n) γ n ( ρ ) = o ( n ) , there exists an integer N N N such that γ N ( ρ ) ≤ N log ( 3 / 2 ) / 2 \gamma_N(\rho)\le N\log(3/2)/2 γ N ( ρ ) ≤ N log ( 3/2 ) /2 . The result just proved then yields dim E ( F , ε ) < N < ∞ \dim_E(\mathcal{F},\varepsilon)<N<\infty dim E ( F , ε ) < N < ∞ . □
This comparison follows from [17 Theorem 3.1] , with the factor 1 / 2 1/2 1/2 accounting for our definition of γ n \gamma_n γ n .
For completeness, put p = d / ( 2 ν + d ) p=d/(2\nu+d) p = d / ( 2 ν + d ) . Under the Matérn spectral conditions of [43 Theorem 3 and Corollary 1] , their information-gain estimate, with explicit dependence on the positive regularization scale λ \lambda λ , gives γ n ( λ ) = O ~ ( ( n / λ ) p ) \gamma_n(\lambda)=\widetilde{O}((n/\lambda)^p) γ n ( λ ) = O (( n / λ ) p ) , where p = d / ( 2 ν + d ) p=d/(2\nu+d) p = d / ( 2 ν + d ) . Choose n n n of order λ − p / ( 1 − p ) \lambda^{-p/(1-p)} λ − p / ( 1 − p ) up to logarithmic factors. The information gain is then at most n log ( 3 / 2 ) / 2 n\log(3/2)/2 n log ( 3/2 ) /2 after increasing the constant. Since p / ( 1 − p ) = d / ( 2 ν ) p/(1-p)=d/(2\nu) p / ( 1 − p ) = d / ( 2 ν ) and λ = ( ε / 2 B ) 2 \lambda=(\varepsilon/2B)^2 λ = ( ε /2 B ) 2 , the lemma gives dim E ( F , ε ) = O ~ ( ( B / ε ) d / ν ) \dim_E(\mathcal{F},\varepsilon)=\widetilde{O}((B/\varepsilon)^{d/\nu}) dim E ( F , ε ) = O (( B / ε ) d / ν ) . At ε = T − 2 \varepsilon=T^{-2} ε = T − 2 this is O ~ ( T 2 d / ν ) \widetilde{O}(T^{2d/\nu}) O ( T 2 d / ν ) for fixed B B B .
The CPT Weight Function: Behavioral Interpretation and Examples
The weight function w : [ 0 , 1 ] → [ 0 , 1 ] w : [0,1] \to[0,1] w : [ 0 , 1 ] → [ 0 , 1 ] governs the physical meaning of the distorted value V a ( f ) V_a(f) V a ( f ) . The key behavioral properties required to capture human decision-making are: w ( 0 ) = 0 w(0)=0 w ( 0 ) = 0 , w ( 1 ) = 1 w(1)=1 w ( 1 ) = 1 (boundary conditions); w ( p ) > p w(p)>p w ( p ) > p for small p p p (overweighting of rare events); w ( p ) < p w(p)<p w ( p ) < p for large p p p (underweighting of common events); monotone increasing; and an inverse S-shape with inflection near the endpoints. Our framework requires only that w w w is monotone increasing with w ( 0 ) = 0 w(0)=0 w ( 0 ) = 0 , w ( 1 ) = 1 w(1)=1 w ( 1 ) = 1 — all other properties are behavioral desiderata, not mathematical requirements.
The choice of w w w directly governs the physical meaning of V a ( f ) V_a(f) V a ( f ) . When w w w is the identity, V a ( f ) V_a(f) V a ( f ) reduces to the standard expectation (risk-neutral). An S-shaped w w w penalizes heavy tails and rare catastrophic losses, favoring safe arms over high-mean-but-risky ones. A more distorted w w w moves V a ( f ) V_a(f) V a ( f ) further from the mean, potentially reversing the preference order entirely. Several families satisfying these properties are widely used in practice:
[39 ] : w ( p ) = p γ / ( p γ + ( 1 − p ) γ ) 1 / γ w(p)=p^\gamma/(p^\gamma+(1-p)^\gamma)^{1/\gamma} w ( p ) = p γ / ( p γ + ( 1 − p ) γ ) 1/ γ
[30 ] : w ( p ) = exp ( − ( − ln p ) α ) w(p)=\exp(-(-\ln p)^\alpha) w ( p ) = exp ( − ( − ln p ) α )
[15 ] : w ( p ) = δ p γ / ( δ p γ + ( 1 − p ) γ ) w(p)=\delta p^\gamma/(\delta p^\gamma+(1-p)^\gamma) w ( p ) = δ p γ / ( δ p γ + ( 1 − p ) γ )
Neo-additive [8 ] : for p ∈ ( 0 , 1 ) p \in(0,1) p ∈ ( 0 , 1 ) , w ( p ) = δ 0 + ( 1 − δ 0 − δ 1 ) p w(p)=\delta_0+(1-\delta_0-\delta_1)p w ( p ) = δ 0 + ( 1 − δ 0 − δ 1 ) p , with w ( 0 ) = 0 w(0)=0 w ( 0 ) = 0 and w ( 1 ) = 1 w(1)=1 w ( 1 ) = 1 , where δ 0 , δ 1 ≥ 0 \delta_0,\delta_1 \ge0 δ 0 , δ 1 ≥ 0 and δ 0 + δ 1 ≤ 1 \delta_0+\delta_1 \le1 δ 0 + δ 1 ≤ 1 . It has endpoint jumps whenever δ 0 > 0 \delta_0>0 δ 0 > 0 or δ 1 > 0 \delta_1>0 δ 1 > 0 .
On removing Hölder continuity. Prior bandit work [13 ] assumes w w w to be α \alpha α -Hölder continuous. This assumption is a mathematical convenience, not a behavioral necessity. Kahneman and Tversky explicitly discuss “apparent discontinuities at the endpoints” in their original prospect-theory treatment [24 ] . Neo-additive capacities provide an explicit discontinuous example: for p ∈ ( 0 , 1 ) p \in(0,1) p ∈ ( 0 , 1 ) , w ( p ) = δ 0 + ( 1 − δ 0 − δ 1 ) p w(p)=\delta_0+(1-\delta_0-\delta_1)p w ( p ) = δ 0 + ( 1 − δ 0 − δ 1 ) p , with w ( 0 ) = 0 w(0)=0 w ( 0 ) = 0 and w ( 1 ) = 1 w(1)=1 w ( 1 ) = 1 . Such endpoint jumps violate every Hölder condition on [ 0 , 1 ] [0,1] [ 0 , 1 ] . Proposition B.3 and our learned-CDF analysis do not require Hölder continuity; monotonicity together with the endpoint conditions is sufficient.
Learning the noise online: CPT bandits without a known noise CDF
The algorithm 1 in the main paper uses the noise CDF at each arm. Here we learn that CDF from the observed rewards. We keep the additive model r t = f ∗ ( a t ) + ϵ t r_t=f^*(a_t)+\epsilon_t r t = f ∗ ( a t ) + ϵ t . Conditional on the past and the chosen arm, ϵ t \epsilon_t ϵ t has the specified arm-dependent law. The actions may be chosen adaptively.
Assumptions. Let H \mathcal{H} H be a known class of conditional noise CDFs, with true member F F F . For each h ∈ H h \in\mathcal{H} h ∈ H , let p h p_h p h be its density and write h ( z ∣ a ) = ∫ − s z p h ( u ∣ a ) d u h(z \mid a)=\int_{-s}^{z}p_h(u \mid a)\,du h ( z ∣ a ) = ∫ − s z p h ( u ∣ a ) d u , extended by 0 and 1 outside S = [ − s , s ] S=[-s,s] S = [ − s , s ] . We assume that every p h ( ⋅ ∣ a ) p_h(\cdot\mid a) p h ( ⋅ ∣ a ) is supported on S S S , has mean zero, and satisfies
0 < p min ≤ p h ( z ∣ a ) ≤ p max < ∞ , z ∈ S , a ∈ A . 0<p_{\min}\le p_h(z\mid a)\le p_{\max}<\infty,\qquad z\in S,\quad a\in\mathcal{A}. 0 < p m i n ≤ p h ( z ∣ a ) ≤ p m a x < ∞ , z ∈ S , a ∈ A .
We also assume sup f ∈ F , a ∈ A ∣ f ( a ) ∣ ≤ B f \sup_{f\in\mathcal{F},a\in\mathcal{A}}|f(a)|\le B_f sup f ∈ F , a ∈ A ∣ f ( a ) ∣ ≤ B f and ( f ∗ , F ) ∈ F × H (f^*,F)\in\mathcal{F}\times\mathcal{H} ( f ∗ , F ) ∈ F × H . Thus ∣ r t ∣ ≤ B f + s |r_t|\le B_f+s ∣ r t ∣ ≤ B f + s , and the noise is s s s -sub-Gaussian. For the mean confidence set C t C_t C t , we may use the full-history set of Section B.2, with its radius β t \beta_t β t chosen using these bounds. More generally, we choose C t C_t C t so that f ∗ ∈ C t f^*\in C_t f ∗ ∈ C t for every t ≤ T t\le T t ≤ T with probability at least 1 − δ 1-\delta 1 − δ . We assume the weight w : [ 0 , 1 ] → [ 0 , 1 ] w:[0,1]\to[0,1] w : [ 0 , 1 ] → [ 0 , 1 ] is nondecreasing, with w ( 0 ) = 0 w(0)=0 w ( 0 ) = 0 and w ( 1 ) = 1 w(1)=1 w ( 1 ) = 1 . No continuity is required.
For ( f , h ) ∈ F × H (f,h)\in\mathcal{F}\times\mathcal{H} ( f , h ) ∈ F × H , define the conditional reward density and CDF by
q f , h ( r ∣ a ) = p h ( r − f ( a ) ∣ a ) , G f , h ( z ∣ a ) = h ( z − f ( a ) ∣ a ) . q_{f,h}(r\mid a)=p_h(r-f(a)\mid a),\qquad G_{f,h}(z\mid a)=h(z-f(a)\mid a). q f , h ( r ∣ a ) = p h ( r − f ( a ) ∣ a ) , G f , h ( z ∣ a ) = h ( z − f ( a ) ∣ a ) .
Let Q \mathcal{Q} Q and G \mathcal{G} G be the resulting density and CDF classes. We use an upper density cover of Q \mathcal{Q} Q . At precision ε > 0 \varepsilon>0 ε > 0 , it is a finite set of nonnegative measurable functions Q ‾ \overline{\mathcal{Q}} Q such that, for every q ∈ Q q\in\mathcal{Q} q ∈ Q , some q ˉ ∈ Q ‾ \bar q\in\overline{\mathcal{Q}} q ˉ ∈ Q satisfies, for all a , r a,r a , r ,
q ˉ ( r ∣ a ) ≥ q ( r ∣ a ) , ∫ ( q ˉ ( r ∣ a ) − q ( r ∣ a ) ) d r ≤ ε . \bar q(r\mid a)\ge q(r\mid a),\qquad\int\bigl(\bar q(r\mid a)-q(r\mid a)\bigr)\,dr\le\varepsilon. q ˉ ( r ∣ a ) ≥ q ( r ∣ a ) , ∫ ( q ˉ ( r ∣ a ) − q ( r ∣ a ) ) d r ≤ ε .
The cover functions need not integrate to one. Write N o p t ( Q , ε ) N_{\mathrm{opt}}(\mathcal{Q},\varepsilon) N opt ( Q , ε ) for the smallest cover size, and assume N o p t ( Q , 1 / T ) < ∞ N_{\mathrm{opt}}(\mathcal{Q},1/T)<\infty N opt ( Q , 1/ T ) < ∞ . This is a condition on the shifted reward densities . A cover of the unshifted CDFs alone does not control their likelihoods when the support moves with f ( a ) f(a) f ( a ) .
For G 1 , G 2 ∈ G G_1,G_2\in\mathcal{G} G 1 , G 2 ∈ G , put d a ( G 1 , G 2 ) = sup z ∣ G 1 ( z ∣ a ) − G 2 ( z ∣ a ) ∣ d_a(G_1,G_2)=\sup_z\lvert G_1(z\mid a)-G_2(z\mid a)\rvert d a ( G 1 , G 2 ) = sup z ∣ G 1 ( z ∣ a ) − G 2 ( z ∣ a )∣ . We use dim E ( G , d ⋅ , ε ) \dim_{\mathcal{E}}(\mathcal{G},d_{\cdot},\varepsilon) dim E ( G , d ⋅ , ε ) as in Definition 4.1 , with the scalar difference replaced by d a d_a d a . In particular, a new action is ε \varepsilon ε -independent if two members of G \mathcal{G} G differ there by more than some ε ′ ≥ ε \varepsilon'\ge\varepsilon ε ′ ≥ ε , while the sum of their squared distances at earlier actions is at most ( ε ′ ) 2 (\varepsilon')^2 ( ε ′ ) 2 .
Algorithm. Let δ 0 ∈ ( 0 , 1 ) \delta_0\in(0,1) δ 0 ∈ ( 0 , 1 ) , and set
β H = log 2 N o p t ( Q , 1 / T ) δ 0 + 1. \beta^{\mathcal{H}}=\log\frac{2N_{\mathrm{opt}}(\mathcal{Q},1/T)}{\delta_0}+1. β H = log δ 0 2 N opt ( Q , 1/ T ) + 1.
Using the raw rewards, form the likelihood set
M t = { ( f , h ) ∈ F × H : ∑ τ < t log q f , h ( r τ ∣ a τ ) ≥ sup ( f ′ , h ′ ) ∈ F × H ∑ τ < t log q f ′ , h ′ ( r τ ∣ a τ ) − β H } . \mathcal{M}_t=\left\{(f,h)\in\mathcal{F}\times\mathcal{H}:\sum_{\tau<t}\log q_{f,h}(r_\tau\mid a_\tau)\ge\sup_{(f',h')\in\mathcal{F}\times\mathcal{H}}\sum_{\tau<t}\log q_{f',h'}(r_\tau\mid a_\tau)-\beta^{\mathcal{H}}\right\}. M t = { ( f , h ) ∈ F × H : τ < t ∑ log q f , h ( r τ ∣ a τ ) ≥ ( f ′ , h ′ ) ∈ F × H sup τ < t ∑ log q f ′ , h ′ ( r τ ∣ a τ ) − β H } .
At round t t t , choose an arm maximizing
V ~ t ( a ) = sup ( f , h ) ∈ M t , f ∈ C t V a h ( f ) . \widetilde{V}_t(a)=\sup_{\substack{(f,h)\in\mathcal{M}_t,\,f\in\mathcal{C}_t}}\mathcal{V}_a^h(f). V t ( a ) = ( f , h ) ∈ M t , f ∈ C t sup V a h ( f ) .
Here V a h ( f ) \mathcal{V}_a^h(f) V a h ( f ) is the CPT value defined in the main paper, using h ( z − f ( a ) ∣ a ) h(z-f(a)\mid a) h ( z − f ( a ) ∣ a ) as the reward CDF. We assume the displayed suprema are attained. The analysis also permits approximate maximizers, with their optimization errors added to the regret. See, Algorithm 4 for the pseudocode.
Lemma H.1 (Likelihood confidence set). With probability at least 1 − δ 0 1-\delta_0 1 − δ 0 , simultaneously for all t ≤ T t\le T t ≤ T , ( f ∗ , F ) ∈ M t (f^*,F)\in\mathcal{M}_t ( f ∗ , F ) ∈ M t . On the same event, every ( f , h ) ∈ M t (f,h)\in\mathcal{M}_t ( f , h ) ∈ M t satisfies
∑ τ < t d a τ ( G f , h , G f ∗ , F ) 2 ≤ C β H \sum_{\tau<t}d_{a_\tau}(G_{f,h},G_{f^*,F})^2\le C\beta^{\mathcal{H}} τ < t ∑ d a τ ( G f , h , G f ∗ , F ) 2 ≤ C β H for a numerical constant C C C .
Proof. Write q ∗ = q f ∗ , F q^*=q_{f^*,F} q ∗ = q f ∗ , F , N = N o p t ( Q , 1 / T ) N=N_{\mathrm{opt}}(\mathcal{Q},1/T) N = N opt ( Q , 1/ T ) , L = log ( 2 N / δ 0 ) L=\log(2N/\delta_0) L = log ( 2 N / δ 0 ) , and β H = L + 1 \beta^{\mathcal{H}}=L+1 β H = L + 1 . For each upper cover member q ˉ \bar q q ˉ , define Z q ˉ ( a ) = ∫ q ˉ ( r ∣ a ) d r Z_{\bar q}(a)=\int\bar q(r\mid a)\,dr Z q ˉ ( a ) = ∫ q ˉ ( r ∣ a ) d r and q ~ ( r ∣ a ) = q ˉ ( r ∣ a ) / Z q ˉ ( a ) \widetilde{q}(r\mid a)=\bar q(r\mid a)/Z_{\bar q}(a) q ( r ∣ a ) = q ˉ ( r ∣ a ) / Z q ˉ ( a ) . Then 1 ≤ Z q ˉ ( a ) ≤ 1 + 1 / T 1\le Z_{\bar q}(a)\le1+1/T 1 ≤ Z q ˉ ( a ) ≤ 1 + 1/ T . Under the true law, the likelihood-ratio process
Λ t ( q ~ ) = ∏ j < t q ~ ( r j ∣ a j ) q ∗ ( r j ∣ a j ) \Lambda_t(\widetilde q)=\prod_{j<t}\frac{\widetilde q(r_j\mid a_j)}{q^*(r_j\mid a_j)} Λ t ( q ) = j < t ∏ q ∗ ( r j ∣ a j ) q ( r j ∣ a j )
Algorithm 4: NPCB-Learned
Input: F , H \mathcal{F}, \mathcal{H} F , H , confidence schedules { β t } \{\beta_t\} { β t } and β H \beta^{\mathcal{H}} β H .
for t = 1 , … , T t = 1,\ldots,T t = 1 , … , T do
Construct the mean confidence set C t C_t C t from all observations before round t t t .
For ( f , h ) ∈ F × H (f,h) \in\mathcal{F} \times\mathcal{H} ( f , h ) ∈ F × H , compute
ℓ t ( f , h ) = ∑ τ < t log p h ( r τ − f ( a τ ) ∣ a τ ) . \ell_t(f,h) = \sum_{\tau< t} \log p_h(r_\tau- f(a_\tau) \mid a_\tau). ℓ t ( f , h ) = τ < t ∑ log p h ( r τ − f ( a τ ) ∣ a τ ) .
Form the likelihood confidence set
M t = { ( f , h ) : ℓ t ( f , h ) ≥ sup ( f ′ , h ′ ) ∈ F × H ℓ t ( f ′ , h ′ ) − β H } . \mathcal{M}_t = \left\{(f,h) : \ell_t(f,h) \ge\sup_{(f',h') \in\mathcal{F} \times\mathcal{H}} \ell_t(f',h') - \beta^{\mathcal{H}}\right\}. M t = { ( f , h ) : ℓ t ( f , h ) ≥ ( f ′ , h ′ ) ∈ F × H sup ℓ t ( f ′ , h ′ ) − β H } .
Choose a t ∈ a r g m a x a ∈ A sup ( f , h ) ∈ M t sup f ∈ C t V a h ( f ) a_t \in\mathop{\rm arg\,max}_{a \in\mathcal{A}} \sup_{(f,h) \in\mathcal{M}_t} \sup_{f \in C_t} V_a^h(f) a t ∈ arg max a ∈ A sup ( f , h ) ∈ M t sup f ∈ C t V a h ( f ) .
Observe r t r_t r t .
end for
is a nonnegative supermartingale. Its conditional expected multiplier is ∫ { q ∗ > 0 } q ~ ( r ∣ a t ) d r ≤ 1 \int_{\{q^*>0\}} \widetilde{q}(r \mid a_t)\,dr \le1 ∫ { q ∗ > 0 } q ( r ∣ a t ) d r ≤ 1 ; the inequality may be strict when q ~ \widetilde{q} q places mass outside the support of q ∗ q^* q ∗ . Ville’s inequality and a union bound imply log Λ t ( q ~ ) ≤ L \log\Lambda_t(\widetilde{q}) \le L log Λ t ( q ) ≤ L for all cover members and all t ≤ T t \le T t ≤ T , except on an event of probability δ 0 / 2 \delta_0/2 δ 0 /2 . If q ≤ q ~ q \le\widetilde{q} q ≤ q , then
ℓ t ( q ) − ℓ t ( q ∗ ) ≤ log Λ t ( q ~ ) + ∑ j < t log Z q ~ ( a j ) ≤ L + 1 = β H . \ell_t(q) - \ell_t(q^*) \le\log\Lambda_t(\widetilde{q}) + \sum_{j<t} \log Z_{\widetilde{q}}(a_j) \le L + 1 = \beta^{\mathcal{H}}. ℓ t ( q ) − ℓ t ( q ∗ ) ≤ log Λ t ( q ) + j < t ∑ log Z q ( a j ) ≤ L + 1 = β H .
Hence the true pair belongs to M t \mathcal{M}_t M t . Define H 2 ( p , q ) = ∫ ( p − q ) 2 H^2(p,q) = \int(\sqrt{p} - \sqrt{q})^2 H 2 ( p , q ) = ∫ ( p − q ) 2 and H a 2 = H 2 ( q ~ ( ⋅ ∣ a ) , q ∗ ( ⋅ ∣ a ) ) H_a^2 = H^2(\widetilde{q}(\cdot\mid a),q^*(\cdot\mid a)) H a 2 = H 2 ( q ( ⋅ ∣ a ) , q ∗ ( ⋅ ∣ a )) . The process
Λ t ( q ~ ) 1 / 2 exp { 1 2 ∑ j < t H a j 2 } \Lambda_t(\widetilde{q})^{1/2} \exp\left\{\frac{1}{2}\sum_{j<t} H_{a_j}^2\right\} Λ t ( q ) 1/2 exp { 2 1 j < t ∑ H a j 2 }
is also a nonnegative supermartingale, because its one-step conditional expectation is e H a 2 / 2 ( 1 − H a 2 / 2 ) ≤ 1 e^{H_{a}^2/2}(1-H_a^2/2) \le1 e H a 2 /2 ( 1 − H a 2 /2 ) ≤ 1 . A second maximal inequality, with failure probability δ 0 / 2 \delta_0/2 δ 0 /2 , gives simultaneously
1 2 log Λ t ( q ~ ) + 1 2 ∑ j < t H a j 2 ≤ L . \frac{1}{2}\log\Lambda_t(\widetilde{q}) + \frac{1}{2}\sum_{j<t} H_{a_j}^2 \le L. 2 1 log Λ t ( q ) + 2 1 j < t ∑ H a j 2 ≤ L .
For q ∈ M t q \in\mathcal{M}_t q ∈ M t , its normalized upper cover satisfies log Λ t ( q ~ ) ≥ − β H − 1 \log\Lambda_t(\widetilde{q}) \ge-\beta^{\mathcal{H}} - 1 log Λ t ( q ) ≥ − β H − 1 . Thus ∑ j < t H a j 2 ≤ 3 β H \sum_{j<t} H_{a_j}^2 \le3\beta^{\mathcal{H}} ∑ j < t H a j 2 ≤ 3 β H . Furthermore, TV ( q ( ⋅ ∣ a ) , q ~ ( ⋅ ∣ a ) ) ≤ 1 / T \operatorname{TV}(q(\cdot\mid a),\widetilde{q}(\cdot\mid a)) \le1/T TV ( q ( ⋅ ∣ a ) , q ( ⋅ ∣ a )) ≤ 1/ T . Using H 2 ≤ 2 TV H^2 \le2\operatorname{TV} H 2 ≤ 2 TV and the Hellinger triangle inequality,
∑ j < t H 2 ( q ( ⋅ ∣ a j ) , q ∗ ( ⋅ ∣ a j ) ) ≤ 6 β H + 4 ≤ 10 β H . \sum_{j<t} H^2(q(\cdot\mid a_j),q^*(\cdot\mid a_j)) \le6\beta^{\mathcal{H}} + 4 \le10\beta^{\mathcal{H}}. j < t ∑ H 2 ( q ( ⋅ ∣ a j ) , q ∗ ( ⋅ ∣ a j )) ≤ 6 β H + 4 ≤ 10 β H .
Finally, Kolmogorov distance is at most total variation, which is at most H H H under this convention. The claimed bound follows. All conditional arguments allow adaptively selected arms. □
Lemma H.2 (Stability without a smooth weight). For any f f f , a a a and h 1 , h 2 ∈ H h_1,h_2 \in\mathcal{H} h 1 , h 2 ∈ H ,
∣ V a h 1 ( f ) − V a h 2 ( f ) ∣ ≤ 2 p min sup z ∣ h 1 ( z ∣ a ) − h 2 ( z ∣ a ) ∣ . \left| \mathcal{V}^{h_1}_a(f) - \mathcal{V}^{h_2}_a(f) \right| \le\frac{2}{p_{\min}} \sup_z \left|h_1(z \mid a) - h_2(z \mid a)\right|. V a h 1 ( f ) − V a h 2 ( f ) ≤ p m i n 2 z sup ∣ h 1 ( z ∣ a ) − h 2 ( z ∣ a ) ∣ . For a fixed noise CDF h h h , the value is nondecreasing and 2-Lipschitz in the mean f ( a ) f(a) f ( a ) .
Proof. Write m = f ( a ) m=f(a) m = f ( a ) . If m 1 ≥ m 2 m_1 \ge m_2 m 1 ≥ m 2 , a change of variables in the two CPT integrals gives
V a h ( m 1 ) − V a h ( m 2 ) = ∫ − m 1 − m 2 { w ( 1 − h ( u ∣ a ) ) + w ( h ( u ∣ a ) ) } d u . \mathcal{V}^{h}_a(m_1) - \mathcal{V}^{h}_a(m_2) = \int_{-m_1}^{-m_2} \{\mathsf{w}(1-h(u \mid a)) + \mathsf{w}(h(u \mid a))\}\,\mathrm{d}u. V a h ( m 1 ) − V a h ( m 2 ) = ∫ − m 1 − m 2 { w ( 1 − h ( u ∣ a )) + w ( h ( u ∣ a ))} d u .
The integrand belongs to [ 0 , 2 ] [0,2] [ 0 , 2 ] . This proves the claim about the mean, including for discontinuous weights. Now let ξ = sup z ∣ h 1 ( z ∣ a ) − h 2 ( z ∣ a ) ∣ \xi= \sup_z |h_1(z \mid a) - h_2(z \mid a)| ξ = sup z ∣ h 1 ( z ∣ a ) − h 2 ( z ∣ a ) ∣ and Δ = ξ / p min \Delta= \xi/p_{\min} Δ = ξ / p m i n . The common support and the density lower bound give
h 1 ( z − Δ ∣ a ) ≤ h 2 ( z ∣ a ) ≤ h 1 ( z + Δ ∣ a ) , z ∈ R . h_1(z-\Delta\mid a) \le h_2(z \mid a) \le h_1(z+\Delta\mid a), \qquad z \in\mathbb{R}. h 1 ( z − Δ ∣ a ) ≤ h 2 ( z ∣ a ) ≤ h 1 ( z + Δ ∣ a ) , z ∈ R .
At either end of the support, the relevant CDF is 0 or 1. Pointwise CDF order reverses CPT value order because w \mathsf{w} w is nondecreasing. The preceding mean bound therefore sandwiches V a h 2 ( f ) \mathcal{V}^{h_2}_a(f) V a h 2 ( f ) between V a h 1 ( m − Δ ) \mathcal{V}^{h_1}_a(m-\Delta) V a h 1 ( m − Δ ) and V a h 1 ( m + Δ ) \mathcal{V}^{h_1}_a(m+\Delta) V a h 1 ( m + Δ ) . The result follows. □
Lemma H.3 (Stability for Lipschitz weights). Suppose w \mathsf{w} w is L w L_{\mathsf{w}} L w -Lipschitz. Let h 1 ( ⋅ ∣ a ) h_1(\cdot\mid a) h 1 ( ⋅ ∣ a ) and h 2 ( ⋅ ∣ a ) h_2(\cdot\mid a) h 2 ( ⋅ ∣ a ) be noise CDFs supported on [ − s , s ] [-s,s] [ − s , s ] , and let ξ = sup z ∣ h 1 ( z ∣ a ) − h 2 ( z ∣ a ) ∣ \xi= \sup_z |h_1(z \mid a) - h_2(z \mid a)| ξ = sup z ∣ h 1 ( z ∣ a ) − h 2 ( z ∣ a ) ∣ . For every fixed mean m m m ,
∣ V a h 1 ( m ) − V a h 2 ( m ) ∣ ≤ 2 s L w ξ . \left|\mathcal{V}^{h_1}_a(m) - \mathcal{V}^{h_2}_a(m)\right| \le2sL_{\mathsf{w}}\xi. V a h 1 ( m ) − V a h 2 ( m ) ≤ 2 s L w ξ . No density assumption is needed.
Remark H.1. Lemma H.3 permits atomic noise laws but requires Lipschitz weights. Lemma H.2 instead permits discontinuous weights under the stated density assumptions. These are alternative sufficient conditions for stability. The Lipschitz-weight lemma alone does not establish a learned-CDF regret theorem for atomic models; their likelihood confidence sets and distributional complexities require separate analysis.
Proof. Apply the Lipschitz inequality inside the gain and loss integrals. After changing variables, their domains partition the real line, up to the single point − m -m − m . Hence the sum is bounded by L w ∫ R ∣ h 1 ( u ∣ a ) − h 2 ( u ∣ a ) ∣ d u L_{\mathsf{w}}\int_{\mathbb{R}} |h_1(u \mid a)-h_2(u \mid a)|\,\mathrm{d}u L w ∫ R ∣ h 1 ( u ∣ a ) − h 2 ( u ∣ a ) ∣ d u . The CDFs agree outside [ − s , s ] [-s,s] [ − s , s ] , giving the claimed bound. □
Theorem H.2 (Regret with a learned noise CDF). Let w C t ( a ) = sup f 1 , f 2 ∈ C t ∣ f 1 ( a ) − f 2 ( a ) ∣ w_{\mathcal{C}_t}(a) = \sup_{f_1,f_2 \in\mathcal{C}_t}|f_1(a)-f_2(a)| w C t ( a ) = sup f 1 , f 2 ∈ C t ∣ f 1 ( a ) − f 2 ( a ) ∣ , and put
D = min { dim E ( G , d ⋅ , 1 / T ) , T } . D = \min\{\dim_{\mathbb{E}}(\mathcal{G},d_{\cdot},1/T),T\}. D = min { dim E ( G , d ⋅ , 1/ T ) , T } . Under the assumptions above, with probability at least 1 − δ − δ 0 1-\delta-\delta_0 1 − δ − δ 0 , the algorithm satisfies
R ( T ) ≤ C ( 1 + p max p min ) ∑ t = 1 T w C t ( a t ) + C p min ( 1 + D + D β H T ) . R(T) \le C\left(1+\frac{p_{\max}}{p_{\min}}\right)\sum_{t=1}^{T} w_{\mathcal{C}_t}(a_t) + \frac{C}{p_{\min}}\left(1+D+\sqrt{D\beta H T}\right). R ( T ) ≤ C ( 1 + p m i n p m a x ) t = 1 ∑ T w C t ( a t ) + p m i n C ( 1 + D + D β H T ) . For the least-squares sets, the first sum has the mean-width bound of [31 Lemma 2] , using the new reward bound B f + s B_f+s B f + s . No bound on D D D follows from the mean-function complexity alone.
Proof. Work on the intersection of the two confidence events, which holds with probability at least $1-\delta-\delta_0$. Thus f ∗ ∈ C t f^* \in\mathcal{C}_t f ∗ ∈ C t and ( f ∗ , F ) ∈ M t (f^*,F) \in\mathcal{M}_t ( f ∗ , F ) ∈ M t for every $t \le T. By optimism and the choice of a t a_t a t ,
V a ∗ F F ( f ∗ ) − V a t F ( f ∗ ) ≤ sup ( f , h ) ∈ M t f ∈ C t { V a t h ( f ) − V a t F ( f ∗ ) } . \mathcal{V}_{a_*^F}^{F}(f^*)-\mathcal{V}_{a_t}^{F}(f^*)\leq\sup_{\substack{(f,h)\in\mathcal{M}_t\\ f\in\mathcal{C}_t}}\left\{\mathcal{V}_{a_t}^{h}(f)-\mathcal{V}_{a_t}^{F}(f^*)\right\}. V a ∗ F F ( f ∗ ) − V a t F ( f ∗ ) ≤ ( f , h ) ∈ M t f ∈ C t sup { V a t h ( f ) − V a t F ( f ∗ ) } .
Lemma H.2 therefore gives
V a ∗ F F ( f ∗ ) − V a t F ( f ∗ ) ≤ 2 w C t ( a t ) + 2 p min sup ( f , h ) ∈ M t f ∈ C t sup z ∣ h ( z ∣ a t ) − F ( z ∣ a t ) ∣ . \mathcal{V}_{a_*^F}^{F}(f^*)-\mathcal{V}_{a_t}^{F}(f^*)\leq2w_{\mathcal{C}_t}(a_t)+\frac{2}{p_{\min}}\sup_{\substack{(f,h)\in\mathcal{M}_t\\ f\in\mathcal{C}_t}}\sup_z\lvert h(z\mid a_t)-F(z\mid a_t)\rvert. V a ∗ F F ( f ∗ ) − V a t F ( f ∗ ) ≤ 2 w C t ( a t ) + p m i n 2 ( f , h ) ∈ M t f ∈ C t sup z sup ∣ h ( z ∣ a t ) − F ( z ∣ a t )∣ .
For every ( f , h ) ∈ M t (f,h)\in\mathcal{M}_t ( f , h ) ∈ M t with f ∈ C t f\in\mathcal{C}_t f ∈ C t , the density upper bound and f ∗ ∈ C t f^*\in\mathcal{C}_t f ∗ ∈ C t imply
sup z ∣ h ( z ∣ a t ) − F ( z ∣ a t ) ∣ ≤ d a t ( G f , h , G f ∗ , F ) + p max w C t ( a t ) . \sup_z\lvert h(z\mid a_t)-F(z\mid a_t)\rvert\leq d_{a_t}(G_{f,h},G_{f^*,F})+p_{\max}w_{\mathcal{C}_t}(a_t). z sup ∣ h ( z ∣ a t ) − F ( z ∣ a t )∣ ≤ d a t ( G f , h , G f ∗ , F ) + p m a x w C t ( a t ) .
Hence
R ( T ) ≤ 2 ( 1 + p max p min ) ∑ t = 1 T w C t ( a t ) + 2 p min ∑ t = 1 T sup ( f , h ) ∈ M t d a t ( G f , h , G f ∗ , F ) . R(T)\leq2\left(1+\frac{p_{\max}}{p_{\min}}\right)\sum_{t=1}^{T}w_{\mathcal{C}_t}(a_t)+\frac{2}{p_{\min}}\sum_{t=1}^{T}\sup_{(f,h)\in\mathcal{M}_t}d_{a_t}(G_{f,h},G_{f^*,F}). R ( T ) ≤ 2 ( 1 + p m i n p m a x ) t = 1 ∑ T w C t ( a t ) + p m i n 2 t = 1 ∑ T ( f , h ) ∈ M t sup d a t ( G f , h , G f ∗ , F ) .
It remains to bound the second sum. By Lemma H.1, every ( f , h ) ∈ M t (f,h)\in\mathcal{M}_t ( f , h ) ∈ M t satisfies
∑ j < t d a j ( G f , h , G f ∗ , F ) 2 ≤ 10 β H . \sum_{j<t}d_{a_j}(G_{f,h},G_{f^*,F})^2\leq10\beta^{\mathcal{H}}. j < t ∑ d a j ( G f , h , G f ∗ , F ) 2 ≤ 10 β H .
Fix ϵ ≥ 1 / T \epsilon\geq1/T ϵ ≥ 1/ T . Whenever
sup ( f , h ) ∈ M t d a t ( G f , h , G f ∗ , F ) > ϵ , \sup_{(f,h)\in\mathcal{M}_t}d_{a_t}(G_{f,h},G_{f^*,F})>\epsilon, ( f , h ) ∈ M t sup d a t ( G f , h , G f ∗ , F ) > ϵ ,
choose a witnessing pair ( f , h ) ∈ M t (f,h)\in\mathcal{M}_t ( f , h ) ∈ M t . The preceding historical bound and the standard independent-sequence counting argument give
# { t : sup ( f , h ) ∈ M t d a t ( G f , h , G f ∗ , F ) > ϵ } ≤ D ( 1 + 10 β H ϵ 2 ) . \#\left\{t:\sup_{(f,h)\in\mathcal{M}_t}d_{a_t}(G_{f,h},G_{f^*,F})>\epsilon\right\}\leq D\left(1+\frac{10\beta^{\mathcal{H}}}{\epsilon^2}\right). # { t : ( f , h ) ∈ M t sup d a t ( G f , h , G f ∗ , F ) > ϵ } ≤ D ( 1 + ϵ 2 10 β H ) .
Indeed, the relevant rounds can be partitioned into at most 1 + 10 β H / ϵ 2 1+10\beta^{\mathcal{H}}/\epsilon^2 1 + 10 β H / ϵ 2 subsequences on each of which successive actions are ϵ \epsilon ϵ -independent; each such subsequence has length at most D D D .
Since d a d_a d a is the Kolmogorov distance between two CDFs, d a ( G 1 , G 2 ) ≤ 1 d_a(G_1,G_2)\leq1 d a ( G 1 , G 2 ) ≤ 1 . Integrating the preceding counting bound over ϵ ∈ [ 1 / T , 1 ] \epsilon\in[1/T,1] ϵ ∈ [ 1/ T , 1 ] , together with the trivial count T T T below the optimizing threshold, yields
∑ t = 1 T sup ( f , h ) ∈ M t d a t ( G f , h , G f ∗ , F ) ≤ C ( 1 + D + D β H T ) . \sum_{t=1}^{T}\sup_{(f,h)\in\mathcal{M}_t}d_{a_t}(G_{f,h},G_{f^*,F})\leq C\left(1+D+\sqrt{D\beta^{\mathcal{H}}T}\right). t = 1 ∑ T ( f , h ) ∈ M t sup d a t ( G f , h , G f ∗ , F ) ≤ C ( 1 + D + D β H T ) .
for a numerical constant C C C . If the optimizing threshold exceeds one, the same conclusion follows from the trivial bound by T T T .
Substituting this estimate above gives
R ( T ) ≤ C ( 1 + p max p min ) ∑ t = 1 T w C t ( a t ) + C p min ( 1 + D + D β H T ) , R(T)\leq C\left(1+\frac{p_{\max}}{p_{\min}}\right)\sum_{t=1}^{T}w_{\mathcal{C}_t}(a_t)+\frac{C}{p_{\min}}\left(1+D+\sqrt{D\beta^{\mathcal{H}}T}\right), R ( T ) ≤ C ( 1 + p m i n p m a x ) t = 1 ∑ T w C t ( a t ) + p m i n C ( 1 + D + D β H T ) ,
which proves the claim. □
Lemma H.4 (An arm-dependent family with explicit complexity). Suppose f u ( a ) = ⟨ u , x ( a ) ⟩ f_u(a)=\langle u,x(a)\rangle f u ( a ) = ⟨ u , x ( a )⟩ , where u ∈ R d u \in\mathbb{R}^d u ∈ R d , ∥ u ∥ 2 ≤ B \lVert u\rVert_2 \le B ∥ u ∥ 2 ≤ B , and ∥ x ( a ) ∥ 2 ≤ 1 \lVert x(a)\rVert_2 \le1 ∥ x ( a ) ∥ 2 ≤ 1 . Let ψ ( a ) ∈ R k \psi(a) \in\mathbb{R}^k ψ ( a ) ∈ R k satisfy ∥ ψ ( a ) ∥ 2 ≤ 1 \lVert\psi(a)\rVert_2 \le1 ∥ ψ ( a ) ∥ 2 ≤ 1 . For ∥ v ∥ 2 ≤ 1 \lVert v\rVert_2 \le1 ∥ v ∥ 2 ≤ 1 , put θ v ( a ) = ⟨ v , ψ ( a ) ⟩ \theta_v(a)=\langle v,\psi(a)\rangle θ v ( a ) = ⟨ v , ψ ( a )⟩ and
p v ( z ∣ a ) = 1 2 s ( 1 + θ v ( a ) ( z 2 s 2 − 1 3 ) ) 1 { ∣ z ∣ ≤ s } . p_v(z\mid a)=\frac{1}{2s}\left(1+\theta_v(a)\left(\frac{z^2}{s^2}-\frac{1}{3}\right)\right)\mathbf{1}\{\lvert z\rvert\le s\}. p v ( z ∣ a ) = 2 s 1 ( 1 + θ v ( a ) ( s 2 z 2 − 3 1 ) ) 1 {∣ z ∣ ≤ s } . This is a zero-mean, arm-dependent density. It satisfies p min = 1 / ( 6 s ) p_{\min}=1/(6s) p m i n = 1/ ( 6 s ) and p max = 5 / ( 6 s ) p_{\max}=5/(6s) p m a x = 5/ ( 6 s ) . For fixed B B B , s s s and T ≥ 2 T \ge2 T ≥ 2 ,
log N o p t ( Q , 1 / T ) = O ( ( d + k ) log T ) , min { dim E ( G , d , 1 / T ) , T } = O ( ( d + k ) log T ) . \log N_{\mathrm{opt}}(\mathcal{Q},1/T)=O((d+k)\log T),\qquad\min\{\dim_E(\mathcal{G},d,1/T),T\}=O((d+k)\log T). log N opt ( Q , 1/ T ) = O (( d + k ) log T ) , min { dim E ( G , d , 1/ T ) , T } = O (( d + k ) log T ) . Consequently, the theorem gives R ( T ) = O ~ ( ( d + k ) T ) R(T)=\widetilde{O}((d+k)\sqrt{T}) R ( T ) = O (( d + k ) T ) , with constants depending on B B B , s s s and the confidence levels.
Proof. The densities have uniformly bounded variation, including their jumps at − s -s − s and s s s . A uniform grid for u u u and v v v , followed by a pointwise upper envelope over each grid cell, gives an upper density cover. Moving u u u by ρ \rho ρ changes the location by at most ρ \rho ρ . The extra mass in its envelope is O ( ρ ) O(\rho) O ( ρ ) by bounded variation. Moving v v v by ρ \rho ρ adds O ( ρ ) O(\rho) O ( ρ ) mass as well. Taking ρ \rho ρ of order 1 / T 1/T 1/ T gives a cover of size at most
( C T ) d + k . (CT)^{d+k}. ( C T ) d + k .
For the Eluder bound, let m = f u ( a ) m=f_u(a) m = f u ( a ) and θ = θ v ( a ) \theta=\theta_v(a) θ = θ v ( a ) . All reward laws are supported on [ − B − s , B + s ] [-B-s,B+s] [ − B − s , B + s ] and have mean m m m . Thus a Kolmogorov gap ξ \xi ξ between two reward laws implies ∣ m − m ′ ∣ ≤ 2 ( B + s ) ξ \lvert m-m'\rvert\le2(B+s)\xi ∣ m − m ′ ∣ ≤ 2 ( B + s ) ξ . At z = s / 2 z=s/2 z = s /2 , the noise CDFs differ by ∣ θ − θ ′ ∣ / 16 \lvert\theta-\theta'\rvert/16 ∣ θ − θ ′ ∣ /16 . Shifting their arguments by m − m ′ m-m' m − m ′ changes a CDF by at most p max ∣ m − m ′ ∣ p_{\max}\lvert m-m'\rvert p m a x ∣ m − m ′ ∣ . Hence, for constants c , C > 0 c,C>0 c , C > 0 ,
c ( m − m ′ ) 2 + ( θ − θ ′ ) 2 ≤ d a ( G u , v , G u ′ , v ′ ) ≤ C ( m − m ′ ) 2 + ( θ − θ ′ ) 2 . c\sqrt{(m-m')^2+(\theta-\theta')^2}\le d_a(G_{u,v},G_{u',v'})\le C\sqrt{(m-m')^2+(\theta-\theta')^2}. c ( m − m ′ ) 2 + ( θ − θ ′ ) 2 ≤ d a ( G u , v , G u ′ , v ′ ) ≤ C ( m − m ′ ) 2 + ( θ − θ ′ ) 2 .
The right side is a two-coordinate linear prediction error in the parameter ( u , v ) ∈ R d + k (u,v)\in\mathbb{R}^{d+k} ( u , v ) ∈ R d + k . For a sequence independent at scale ϵ ′ ≥ 1 / T \epsilon' \ge1/T ϵ ′ ≥ 1/ T , apply the determinant argument to λ I + ∑ τ < t diag ( x ( a τ ) x ( a τ ) ⊤ , ψ ( a τ ) ψ ( a τ ) ⊤ ) \lambda I+\sum_{\tau<t}\operatorname{diag}(x(a_\tau)x(a_\tau)^\top,\psi(a_\tau)\psi(a_\tau)^\top) λ I + ∑ τ < t diag ( x ( a τ ) x ( a τ ) ⊤ , ψ ( a τ ) ψ ( a τ ) ⊤ ) , with λ \lambda λ proportional to ( ϵ ′ ) 2 (\epsilon')^2 ( ϵ ′ ) 2 . Each independent action increases its log determinant by a fixed positive amount. Its total increase over at most T T T actions is O ( ( d + k ) log T ) O((d+k)\log T) O (( d + k ) log T ) . This proves the second bound. The linear mean-confidence width has sum O ~ ( d T ) \widetilde{O}(d\sqrt{T}) O ( d T ) by [31 Lemma 2] . Substitution proves the regret claim. When k = O ( d ) k=O(d) k = O ( d ) , the rate is O ~ ( d T ) \widetilde{O}(d\sqrt{T}) O ( d T ) . Thus this family retains the known-CDF linear horizon rate. □
The complexity bounds above apply to this particular family. We do not assert that they hold for arbitrary skewed families. The experimental finite noise class is a separate instantiation and is not justified by this lemma.
Kernel means with learned noise CDFs
Lemma H.5 (Kernel means with the explicit noise family). Replace the linear mean in Lemma H.4 by F = { f ∈ H K : ∥ f ∥ K ≤ B } \mathcal{F}=\{f\in\mathcal{H}_{K}:\|f\|_{K}\le B\} F = { f ∈ H K : ∥ f ∥ K ≤ B } . Assume K ( a , a ) ≤ 1 K(a,a)\le1 K ( a , a ) ≤ 1 and k ≥ 1 k\ge1 k ≥ 1 . Assume the sup-norm cover below is finite. Keep its noise densities p v p_v p v and ∥ ψ ( a ) ∥ 2 ≤ 1 \|\psi(a)\|_2\le1 ∥ ψ ( a ) ∥ 2 ≤ 1 . For constants depending only on B B B and s s s ,
log N o p t ( Q , 1 / T ) ≤ log N ( F , c / T , ∥ ⋅ ∥ ∞ ) + k log ( C T ) , \log N_{\mathrm{opt}}(\mathcal{Q},1/T)\le\log N(\mathcal{F},c/T,\|\cdot\|_{\infty})+k\log(CT), log N opt ( Q , 1/ T ) ≤ log N ( F , c / T , ∥ ⋅ ∥ ∞ ) + k log ( C T ) , where c , C > 0 c,C>0 c , C > 0 are fixed. Moreover, for a fixed c 0 > 0 c_0>0 c 0 > 0 ,
min { dim E ( G , d ⋅ , 1 / T ) , T } ≤ C { γ T K ( c 0 / T 2 ) + k log ( 1 + C T 3 / k ) } . \min\{\dim_E(\mathcal{G},d_{\cdot},1/T),T\}\le C\left\{\gamma_T^{K}(c_0/T^2)+k\log(1+CT^3/k)\right\}. min { dim E ( G , d ⋅ , 1/ T ) , T } ≤ C { γ T K ( c 0 / T 2 ) + k log ( 1 + C T 3 / k ) } . Here γ T K ( λ ) \gamma_T^{K}(\lambda) γ T K ( λ ) is the information gain of K K K at regularization λ \lambda λ .
Proof. Take a sup-norm c / T c/T c / T -net of F \mathcal{F} F and a Euclidean c / T c/T c / T -net of the unit ball for v v v . For each pair of net points, take the pointwise supremum of p v ′ ( r − f ′ ( a ) ∣ a ) p_{v'}(r-f'(a)\mid a) p v ′ ( r − f ′ ( a ) ∣ a ) over the corresponding net cell. This function dominates every reward density in that cell. The densities p v p_v p v have uniformly bounded variation in r r r . A shift of size c / T c/T c / T therefore adds at most C / T C/T C / T to the integral of the supremum. Varying v v v adds at most C / T C/T C / T . Choose c c c small enough that the combined excess is at most 1 / T 1/T 1/ T . There are at most N ( F , c / T , ∥ ⋅ ∥ ∞ ) ( C T ) k N(\mathcal{F},c/T,\|\cdot\|_{\infty})(CT)^k N ( F , c / T , ∥ ⋅ ∥ ∞ ) ( C T ) k envelopes. This proves the first bound.
Write θ v ( a ) = ⟨ v , ψ ( a ) ⟩ \theta_v(a)=\langle v,\psi(a)\rangle θ v ( a ) = ⟨ v , ψ ( a )⟩ . The proof of Lemma H.4 shows, with fixed positive constants c 1 , C 1 c_1,C_1 c 1 , C 1 , that
c 1 ( f ( a ) − f ′ ( a ) ) 2 + ( θ v ( a ) − θ v ′ ( a ) ) 2 ≤ d a ( G f , v , G f ′ , v ′ ) ≤ C 1 ( f ( a ) − f ′ ( a ) ) 2 + ( θ v ( a ) − θ v ′ ( a ) ) 2 . c_1\sqrt{(f(a)-f'(a))^2+(\theta_v(a)-\theta_{v'}(a))^2}
\le d_a(G_{f,v},G_{f',v'})
\le C_1\sqrt{(f(a)-f'(a))^2+(\theta_v(a)-\theta_{v'}(a))^2}. c 1 ( f ( a ) − f ′ ( a ) ) 2 + ( θ v ( a ) − θ v ′ ( a ) ) 2 ≤ d a ( G f , v , G f ′ , v ′ ) ≤ C 1 ( f ( a ) − f ′ ( a ) ) 2 + ( θ v ( a ) − θ v ′ ( a ) ) 2 .
Use the two feature vectors ( K ( ⋅ , a ) , 0 ) (K(\cdot,a),0) ( K ( ⋅ , a ) , 0 ) and ( 0 , ψ ( a ) ) (0,\psi(a)) ( 0 , ψ ( a )) in H K ⊕ R k \mathcal{H}_K\oplus\mathbb{R}^k H K ⊕ R k . Their squared prediction errors add to the expression above. For the difference of two parameters, the squared norm is at most 4 ( B 2 + 1 ) 4(B^2+1) 4 ( B 2 + 1 ) . Put λ = c 0 / T 2 \lambda=c_0/T^2 λ = c 0 / T 2 and define the block operator
V i − 1 = diag ( λ I + ∑ j < i ϕ ( a j ) ⊗ ϕ ( a j ) , λ I + ∑ j < i ψ ( a j ) ψ ( a j ) T ) , ϕ ( a ) = K ( ⋅ , a ) . V_{i-1}=\operatorname{diag}\left(\lambda I+\sum_{j<i}\phi(a_j)\otimes\phi(a_j),\lambda I+\sum_{j<i}\psi(a_j)\psi(a_j)^{\mathsf{T}}\right),\qquad\phi(a)=K(\cdot,a). V i − 1 = diag ( λ I + j < i ∑ ϕ ( a j ) ⊗ ϕ ( a j ) , λ I + j < i ∑ ψ ( a j ) ψ ( a j ) T ) , ϕ ( a ) = K ( ⋅ , a ) .
For an independent sequence at accuracy ε ′ ≥ 1 / T \varepsilon'\ge1/T ε ′ ≥ 1/ T , its witness satisfies
∥ ( f − f ′ , v − v ′ ) ∥ V i − 1 2 ≤ ( 4 c 0 ( B 2 + 1 ) + c 1 − 2 ) ( ε ′ ) 2 . \|(f-f',v-v')\|_{V_{i-1}}^2\le\left(4c_0(B^2+1)+c_1^{-2}\right)(\varepsilon')^2. ∥ ( f − f ′ , v − v ′ ) ∥ V i − 1 2 ≤ ( 4 c 0 ( B 2 + 1 ) + c 1 − 2 ) ( ε ′ ) 2 .
Write g = f − f ′ g=f-f' g = f − f ′ and z = v − v ′ z=v-v' z = v − v ′ , and let V ϕ , i − 1 V_{\phi,i-1} V ϕ , i − 1 and V ψ , i − 1 V_{\psi,i-1} V ψ , i − 1 denote the two diagonal blocks of V i − 1 V_{i-1} V i − 1 . Define
ℓ ϕ , i = ∥ ϕ ( a i ) ∥ V ϕ , i − 1 − 1 2 , ℓ ψ , i = ∥ ψ ( a i ) ∥ V ψ , i − 1 − 1 2 . \ell_{\phi,i}=\|\phi(a_i)\|_{V_{\phi,i-1}^{-1}}^2,\qquad\ell_{\psi,i}=\|\psi(a_i)\|_{V_{\psi,i-1}^{-1}}^2. ℓ ϕ , i = ∥ ϕ ( a i ) ∥ V ϕ , i − 1 − 1 2 , ℓ ψ , i = ∥ ψ ( a i ) ∥ V ψ , i − 1 − 1 2 .
Applying Cauchy–Schwarz separately to the two prediction coordinates,
g ( a i ) 2 + ⟨ z , ψ ( a i ) ⟩ 2 ≤ ∥ g ∥ V ϕ , i − 1 2 ℓ ϕ , i + ∥ z ∥ V ψ , i − 1 2 ℓ ψ , i ≤ ∥ ( g , z ) ∥ V i − 1 2 ( ℓ ϕ , i + ℓ ψ , i ) . g(a_i)^2+\langle z,\psi(a_i)\rangle^2
\le\|g\|_{V_{\phi,i-1}}^2\ell_{\phi,i}+\|z\|_{V_{\psi,i-1}}^2\ell_{\psi,i}
\le\|(g,z)\|_{V_{i-1}}^2(\ell_{\phi,i}+\ell_{\psi,i}). g ( a i ) 2 + ⟨ z , ψ ( a i ) ⟩ 2 ≤ ∥ g ∥ V ϕ , i − 1 2 ℓ ϕ , i + ∥ z ∥ V ψ , i − 1 2 ℓ ψ , i ≤ ∥ ( g , z ) ∥ V i − 1 2 ( ℓ ϕ , i + ℓ ψ , i ) .
On the other hand, the upper metric-comparison bound and d a i ( G f , v , G f ′ , v ′ ) > ε ′ d_{a_i}(G_{f,v},G_{f',v'})>\varepsilon' d a i ( G f , v , G f ′ , v ′ ) > ε ′ imply g ( a i ) 2 + ⟨ z , ψ ( a i ) ⟩ 2 > ( ε ′ ) 2 C 1 2 g(a_i)^2+\langle z,\psi(a_i)\rangle^2>\frac{(\varepsilon')^2}{C_1^2} g ( a i ) 2 + ⟨ z , ψ ( a i ) ⟩ 2 > C 1 2 ( ε ′ ) 2 .
Combining the preceding inequalities gives
ℓ ϕ , i + ℓ ψ , i > 1 c 1 2 ( 4 c 0 ( B 2 + 1 ) + c − 1 2 ) . \ell_{\phi,i}+\ell_{\psi,i}>\frac{1}{c_1^2\left(4c_0(B^2+1)+c_{-1}^2\right)}. ℓ ϕ , i + ℓ ψ , i > c 1 2 ( 4 c 0 ( B 2 + 1 ) + c − 1 2 ) 1 .
The corresponding increase in the sum of the two log determinants is
log ( 1 + ℓ ϕ , i ) + log ( 1 + ℓ ψ , i ) ≥ log ( 1 + ℓ ϕ , i + ℓ ψ , i ) , \log(1+\ell_{\phi,i})+\log(1+\ell_{\psi,i})\ge\log(1+\ell_{\phi,i}+\ell_{\psi,i}), log ( 1 + ℓ ϕ , i ) + log ( 1 + ℓ ψ , i ) ≥ log ( 1 + ℓ ϕ , i + ℓ ψ , i ) ,
and is therefore bounded below by a fixed positive constant. Over n ≤ T n\le T n ≤ T independent arms, their total increase is at most
2 γ T K ( λ ) + k log ( 1 + T k λ ) . 2\gamma_T^{K}(\lambda)+k\log\left(1+\frac{T}{k\lambda}\right). 2 γ T K ( λ ) + k log ( 1 + k λ T ) .
For the finite block, use its rank at most k k k and trace at most T T T . For the RKHS block, use the Gram determinant identity. This proves the bound for an independent sequence of length at most T T T . If the dimension exceeds T T T , apply the argument to its first T T T arms. Substitute λ = c 0 / T 2 \lambda=c_0/T^2 λ = c 0 / T 2 to conclude. □
Remark H.6 (What the kernel bounds imply). The theorem now gives an explicit learned-CDF bound after substituting the two estimates above. For a kernel confidence band, this is
R ( T ) ≤ C ( 1 + p max p min ) T β T γ T K ( λ ) + C p min ( 1 + D ) + C p min T D [ log N ( F , c / T , ∥ ⋅ ∥ ∞ ) + k log ( C T ) + log ( 2 / δ 0 ) ] . \begin{aligned}
R(T)\le C\left(1+\frac{p_{\max}}{p_{\min}}\right)\sqrt{T\beta_T\gamma_T^{K}(\lambda)}+\frac{C}{p_{\min}}(1+D) \\
&+\frac{C}{p_{\min}}\sqrt{TD\left[\log\mathcal{N}\left(\mathcal{F},c/T,\|\cdot\|_{\infty}\right)+k\log(CT)+\log(2/\delta_0)\right]}.
\end{aligned} R ( T ) ≤ C ( 1 + p m i n p m a x ) T β T γ T K ( λ ) + p m i n C ( 1 + D ) + p m i n C T D [ log N ( F , c / T , ∥ ⋅ ∥ ∞ ) + k log ( C T ) + log ( 2/ δ 0 ) ] .
where D D D is bounded by Lemma H.5. The bound on D D D uses information gain at c 0 / T 2 c_0/T^2 c 0 / T 2 , not at the constant regularization used for the known-CDF kernel algorithm. Hence this argument alone does not preserve that algorithm’s Matérn regret exponent. A sharper learned-CDF analysis would be needed to make that claim.
Remark H.7 (When learning preserves the rate). The mean-width term has the same complexity dependence as in known-CDF learning, up to the density constants. The total rate is unchanged only when the added term fits within that mean-width bound. For fixed p min , p max p_{\min},p_{\max} p m i n , p m a x , it suffices that 1 + D + D β T H 1+D+\sqrt{D\beta_T^H} 1 + D + D β T H has at most that order. The explicit linear family satisfies this condition when k = O ( d ) k=O(d) k = O ( d ) . A finite-parameter noise class does not by itself establish this condition for every kernel mean class.
Remark H.8 (Scope of the learned-CDF guarantee). The common support, density bounds, finite upper-density cover, and distributional Eluder dimension are substantive assumptions. The density lower bound converts a CDF error into a horizontal shift, which permits discontinuous probability weights. The theorem does not promise sublinear regret for every density class. For fixed density bounds, sublinearity follows when the mean-width sum is o ( T ) o(T) o ( T ) , D = o ( T ) D=o(T) D = o ( T ) , and D β H = o ( T ) D\beta^H=o(T) D β H = o ( T ) .
I Experiments
Our experiments study the effect of the risk objective and the cost of learning under that objective. Part I assumes known noise CDFs. It compares risk criteria under a common practical exploration rule and evaluates KCB and CPT-BPE with their analyzed confidence constructions, together with CPT-aware baselines, on bounded kernel and Gaussian linear instances. Part II studies the finite-sample cost of learning unknown noise laws using Algorithm 4, with a known-law specialization and a plug-in MLE baseline.
The experiments use distinct statistical models. The practical comparison in Part I uses a kernel-ridge mean estimator; the additional kernel and linear instances evaluate the analyzed known-CDF algorithms. Part II uses a finite realizable mean–noise class so that confidence-set membership and joint optimistic optimization can be computed directly.
All experiments were run on a server with Ubuntu 24.04.3 LTS, an AMD EPYC 9124 16-core processor (32 hardware threads), and 125 GiB of RAM. The software environment used Python 3.12.14 with NumPy 2.5.3, SciPy 1.18.1, and Matplotlib 3.11.2. The reported experiments use only CPU computation.
Part I: Known-CDF Risk Criteria and Algorithms
Part I asks how risk criteria change the preferred arm and how CPT-aware algorithms learn that arm. We use four constructions (Table 3 ). The six-route construction compares Mean, CVaR, mean–variance (MV), and CPT on common reward distributions. The bounded kernel and Gaussian linear constructions evaluate the analyzed algorithms and CPT-aware comparators. All regret uses the population CPT objective with identity utility and the Tversky–Kahneman weight w ( p ) = p γ p γ + ( 1 − p ) 1 / γ w(p) = \frac{p^{\gamma}}{p^{\gamma} + (1-p)^{1/\gamma}} w ( p ) = p γ + ( 1 − p ) 1/ γ p γ , with reference parameter γ = 0.50 \gamma= 0.50 γ = 0.50 .
Table 3. Part I instances. A route groups nearby arms for reporting; it is not a separate selectable object. Noise laws are supplied to the known-CDF methods. W-UCB estimates each arm’s reward distribution from samples.
Six-route environment. The arms are 100 equally spaced points in [ 0 , 1 ] [0,1] [ 0 , 1 ] . An arm’s route is the region of its nearest center among c = ( 0.10 , 0.25 , 0.40 , 0.55 , 0.70 , 0.85 ) \boldsymbol{c} = (0.10, 0.25, 0.40, 0.55, 0.70, 0.85) c = ( 0.10 , 0.25 , 0.40 , 0.55 , 0.70 , 0.85 ) ; R1–R6 denote these regions. The mean is the sum of six Gaussian bumps, f ⋆ ( a ) = ∑ j = 1 6 h j exp ( − ( a − c j ) 2 / ( 2 ( 0.03 ) 2 ) ) f^{\star}(a) = \sum_{j=1}^{6} h_j \exp(-(a-c_j)^2/(2(0.03)^2)) f ⋆ ( a ) = ∑ j = 1 6 h j exp ( − ( a − c j ) 2 / ( 2 ( 0.03 ) 2 )) . Configs A–D use h = ( 10 , 8 , 10.6 , 6 , 4 , 2 ) \boldsymbol{h} = (10, 8, 10.6, 6, 4, 2) h = ( 10 , 8 , 10.6 , 6 , 4 , 2 ) ; Config E changes h 3 h_3 h 3 to 9.5. Arms in [ 0.35 , 0.45 ] [0.35, 0.45] [ 0.35 , 0.45 ] receive the rare-event noise law; all other arms have N ( 0 , 0.05 2 ) N(0,0.05^2) N ( 0 , 0.0 5 2 ) noise. The rare-event interval is a subset of the R3 reporting region. For a downside event, noise is − L -L − L with probability p p p and p L / ( 1 − p ) pL/(1-p) p L / ( 1 − p ) otherwise. For an upside event, it is L L L with probability p p p and − p L / ( 1 − p ) -pL/(1-p) − p L / ( 1 − p ) otherwise. Both laws are centered. A–D use downside pairs ( p , L ) = ( 0.001 , 15 ) , ( 0.003 , 15 ) , ( 0.018 , 5 ) , ( 0.030 , 5 ) (p,L) = (0.001,15), (0.003,15), (0.018,5), (0.030,5) ( p , L ) = ( 0.001 , 15 ) , ( 0.003 , 15 ) , ( 0.018 , 5 ) , ( 0.030 , 5 ) ; E uses the upside pair ( 0.010 , 100 ) (0.010,100) ( 0.010 , 100 ) .
Criteria, practical decisions, and evaluation. Lower-tail CVaR is CVaR α ( X ) = α − 1 ∫ 0 α F X − 1 ( u ) d u \operatorname{CVaR}_{\alpha}(X) = \alpha^{-1}\int_{0}^{\alpha} F_X^{-1}(u)\,\mathrm{d}u CVaR α ( X ) = α − 1 ∫ 0 α F X − 1 ( u ) d u , with F X − 1 ( u ) = inf { x : F X ( x ) ≥ u } F_X^{-1}(u) = \inf\{x : F_X(x) \ge u\} F X − 1 ( u ) = inf { x : F X ( x ) ≥ u } ; this definition handles atoms. MV is MV c ( X ) = E [ X ] − c Var ( X ) \operatorname{MV}_{c}(X) = \mathbb{E}[X] - c\operatorname{Var}(X) MV c ( X ) = E [ X ] − c Var ( X ) . The default parameters are α = 0.10 \alpha= 0.10 α = 0.10 , c = 1 c = 1 c = 1 , and γ = 0.50 \gamma= 0.50 γ = 0.50 . Population scores use the true mean and noise laws. Gaussian CVaR and variance are analytic, two-point scores are exact, and Gaussian CPT uses 32,768 deterministic midpoint quantiles.
For the practical comparison, each method uses kernel-ridge estimation with squared-exponential lengthscale 0.05, regularization 0.01, and U t ( a ) = μ t − 1 ( a ) + 2 σ t − 1 ( a ) U_t(a) = \mu_{t-1}(a) + 2\sigma_{t-1}(a) U t ( a ) = μ t − 1 ( a ) + 2 σ t − 1 ( a ) . It selects the arm maximizing its
Table 4 : Population-optimal routes on the 100-arm grid in Part I. CVaR uses α = 0.10 \alpha= 0.10 α = 0.10 , and CPT uses γ = 0.50 \gamma= 0.50 γ = 0.50 . The MV column with c = 2 c = 2 c = 2 supports the sensitivity discussion. These are population optima, not learned final routes.
Table 4. Population-optimal routes on the 100-arm grid in Part I. CVaR uses α = 0.10 \alpha= 0.10 α = 0.10 , and CPT uses γ = 0.50 \gamma= 0.50 γ = 0.50 . The MV column with c = 2 c = 2 c = 2 supports the sensitivity discussion. These are population optima, not learned final routes.
Table 5: Practical six-route comparison over 60 paired trials at T = 200 T = 200 T = 200 . Regret entries are cumulative reference-CPT regret, mean ± \pm ± one standard error. Success entries are native/CPT route-success percentages. All methods use the common 2 σ 2\sigma 2 σ exploration rule. Native optima are given in Table 4 .
criterion for U t ( a ) + ϵ a U_t(a) + \epsilon_a U t ( a ) + ϵ a . Each trial starts with six pulls at the grid arms nearest the route centers. We run 60 paired trials of length T = 200 T = 200 T = 200 . The fixed multiplier 2 is a practical exploration choice, rather than the confidence multiplier of Algorithm 2; its recorded all-arm mean-confidence coverage is zero. We denote this implementation by KCB (2 σ 2\sigma 2 σ ).
For selected arms a t a_t a t , cumulative CPT pseudo-regret is R T = ∑ t = 1 T [ g ( a ⋆ ) − g ( a t ) ] R_T = \sum_{t=1}^{T}[g(a^\star) - g(a_t)] R T = ∑ t = 1 T [ g ( a ⋆ ) − g ( a t )] , where g g g is the population reference CPT value and a ⋆ a^\star a ⋆ maximizes it on the actual arm grid. A trial’s final route is its modal route over the last 20% of rounds. Native success measures agreement with the learner’s own population-optimal route; CPT success measures agreement with the reference CPT-optimal route. These are route-level diagnostics, not exact-arm identification guarantees. When a native optimum has a positive CPT gap, a learner can accumulate linear CPT regret despite learning its own objective successfully. Thus these cross-objective curves measure the cost of decisions under the specified CPT preference; the CPT-aware comparisons below assess learning on the CPT task.
The population comparisons explain several different preferences (Table 4 ). In A, Mean, CVaR, and MV prefer R3 while CPT prefers R1; B and C separate CPT and MV in opposite directions. In E, R3 has lower mean and larger variance than R1 but a rare large upside: Mean, lower-tail CVaR, and MV prefer R1, whereas CPT prefers R3. The practical CPT learner reaches its reference-optimal route in every default-parameter trial. Native success prevents other learners’ CPT regret from being mistaken for unsuccessful native-objective learning; for example, MV-UCB in C reaches R1 in 82% of trials although its native optimum is R3.
Parameter sensitivity. We also test α ∈ { 0.05 , 0.10 , 0.20 } \alpha\in\{0.05, 0.10, 0.20\} α ∈ { 0.05 , 0.10 , 0.20 } , c ∈ { 0.5 , 1 , 2 } c \in\{0.5, 1, 2\} c ∈ { 0.5 , 1 , 2 } , and γ ∈ { 0.4 , 0.5 , 0.6 } \gamma\in\{0.4, 0.5, 0.6\} γ ∈ { 0.4 , 0.5 , 0.6 } . Changing a parameter changes the corresponding population objective. In B, CVaR prefers R1 at α = 0.05 \alpha= 0.05 α = 0.05 and R3 at 0.10 and 0.20; in C it prefers R1 at 0.05 and 0.10, and R3 at 0.20. In A, MV still prefers R3 at c = 2 c = 2 c = 2 (best scores 10.0539 versus 9.9894 on R1), although its practical learner finishes on R1 in all trials. CPT in A prefers R1 at γ = 0.4 \gamma= 0.4 γ = 0.4 and 0.5, but R3 at 0.6; the latter runs have 80% native success and 20% reference-CPT success. In E, all tested CVaR and MV parameters prefer R1, while all tested CPT parameters prefer R3; the corresponding practical learners reach those routes in every trial. These findings concern specified preferences and finite-horizon decisions, rather than universal dominance or a human-subject validation of the chosen CPT parameters.
Kernel instances and theoretical confidence rules. The bounded 1D instance has 50 equally spaced arms and k ( a , b ) = exp ( − ( a − b ) 2 / ( 2 ( 0.12 ) 2 ) ) k(a,b) = \exp(-(a-b)^2/(2(0.12)^2)) k ( a , b ) = exp ( − ( a − b ) 2 / ( 2 ( 0.12 ) 2 )) . Its mean is f ⋆ ( a ) = 0.54 k ( a , 0.25 ) + 0.60 k ( a , 0.72 ) f^\star(a) = 0.54k(a,0.25) + 0.60k(a,0.72) f ⋆ ( a ) = 0.54 k ( a , 0.25 ) + 0.60 k ( a , 0.72 ) . Arms in [ 0.62 , 0.82 ] [0.62, 0.82] [ 0.62 , 0.82 ] have noise − 0.30 -0.30 − 0.30 with probability 0.05 and 0.05 ⋅ 0.30 / 0.95 0.05 \cdot0.30/0.95 0.05 ⋅ 0.30/0.95 otherwise; other arms have symmetric noise ± 0.02 \pm0.02 ± 0.02 . The explicit kernel-section representation certifies B = 0.8074 B = 0.8074 B = 0.8074 , Hoeffding’s lemma gives η = 0.1579 \eta= 0.1579 η = 0.1579 , and all rewards lie in [ − M , M ] [-M,M] [ − M , M ] with M = 0.6154 M = 0.6154 M = 0.6154 . The mean/CPT optima are 0.714/0.245 on the grid.
The bounded 2D instance uses a 7 × 7 7 \times7 7 × 7 grid, k 0 ( a , b ) = exp ( − ∥ a − b ∥ 2 / ( 2 ( 0.16 ) 2 ) ) k_0(a,b) = \exp(-\lVert a-b\rVert^2/(2(0.16)^2)) k 0 ( a , b ) = exp ( − ∥ a − b ∥ 2 / ( 2 ( 0.16 ) 2 )) , and K = 0.20 + 0.80 k 0 \mathcal{K} = 0.20 + 0.80k_0 K = 0.20 + 0.80 k 0 . With c s = ( 0.25 , 0.25 ) c_s = (0.25, 0.25) c s = ( 0.25 , 0.25 ) and c r = ( 0.75 , 0.75 ) c_r = (0.75, 0.75) c r = ( 0.75 , 0.75 ) , its mean is f ⋆ ( a ) = 0.10 + 0.54 k 0 ( a , c s ) + 0.60 k 0 ( a , c r ) f^\star(a) = 0.10 + 0.54k_0(a,c_s) + 0.60k_0(a,c_r) f ⋆ ( a ) = 0.10 + 0.54 k 0 ( a , c s ) + 0.60 k 0 ( a , c r ) . Arms within distance 0.17 of c r c_r c r use the risky law above; the others have noise ± 0.02 \pm0.02 ± 0.02 . The direct-sum kernel representation gives
B 2 = 0.10 2 0.20 + 0.54 2 + 0.60 2 + 2 ( 0.54 ) ( 0.60 ) k 0 ( c s , c r ) 0.80 . B^2 = \frac{0.10^2}{0.20} + \frac{0.54^2 + 0.60^2 + 2(0.54)(0.60)k_0(c_s,c_r)}{0.80}. B 2 = 0.20 0.1 0 2 + 0.80 0.5 4 2 + 0.6 0 2 + 2 ( 0.54 ) ( 0.60 ) k 0 ( c s , c r ) .
Thus B = 0.9298 B = 0.9298 B = 0.9298 and η = 0.1579 \eta= 0.1579 η = 0.1579 . All reward endpoints lie in [ 0 , M ] [0,M] [ 0 , M ] , with M M M the largest endpoint on the grid. The mean/CPT optima are ( 2 / 3 , 2 / 3 ) / ( 1 / 3 , 1 / 3 ) (2/3, 2/3)/(1/3, 1/3) ( 2/3 , 2/3 ) / ( 1/3 , 1/3 ) .
On both instances, KCB implements Algorithm 2 with λ = 1 + 2 / T \lambda= 1 + 2/T λ = 1 + 2/ T , δ = 0.10 \delta= 0.10 δ = 0.10 , and its theoretical confidence multiplier:
β t = B + η 2 ( γ ˉ t − 1 ( λ ) + 1 + log ( 1 / δ ) ) , \sqrt{\beta_t} = B + \eta\sqrt{2\left(\bar{\gamma}_{t-1}(\lambda) + 1 + \log(1/\delta)\right)}, β t = B + η 2 ( γ ˉ t − 1 ( λ ) + 1 + log ( 1/ δ ) ) ,
γ ˉ n ( λ ) = r n 2 log ( 1 + n r n λ ) , r n = min { n , r } , n ≥ 1. \bar{\gamma}_n(\lambda) = \frac{r_n}{2}\log\left(1 + \frac{n}{r_n\lambda}\right), \qquad r_n = \min\{n,r\}, \qquad n \ge1. γ ˉ n ( λ ) = 2 r n log ( 1 + r n λ n ) , r n = min { n , r } , n ≥ 1.
Here γ ˉ 0 = 0 \bar{\gamma}_0 = 0 γ ˉ 0 = 0 and r r r is the finite kernel matrix rank bound. The trace and rank bounds imply γ n ( λ ) ≤ γ ˉ n ( λ ) \gamma_n(\lambda) \le\bar{\gamma}_n(\lambda) γ n ( λ ) ≤ γ ˉ n ( λ ) for every design, since K ( a , a ) ≤ 1 \mathcal{K}(a,a) \le1 K ( a , a ) ≤ 1 . KCB selects the arm maximizing the supplied-law CPT value at μ t − 1 + β t σ t − 1 \mu_{t-1} + \sqrt{\beta_t}\sigma_{t-1} μ t − 1 + β t σ t − 1 , with no fitted confidence scale. CPT-BPE implements Algorithm 3 with n 0 = 1 n_0 = 1 n 0 = 1 , n i = ⌈ T n i − 1 ⌉ n_i = \lceil\sqrt{Tn_{i-1}}\rceil n i = ⌈ T n i − 1 ⌉ , and c T = B + ( η / λ ) 2 log ( 2 m ∣ A ∣ / δ ) c_T = B + (\eta/\sqrt{\lambda})\sqrt{2\log(2m|\mathcal{A}|/\delta)} c T = B + ( η / λ ) 2 log ( 2 m ∣ A ∣/ δ ) , where m m m is the prescribed number of phases. Each phase’s design uses posterior variances and surviving arms, independently of current-phase rewards. Estimates use only that phase’s observations; CPT upper/lower scores determine elimination at its end. Both constructions have centered bounded noise and valid norm/noise certificates, satisfying the assumptions of the compared kernel procedures.
CPT-aware comparators. In 2D we additionally run empirical-CDF W-UCB [13 ] . It pulls every arm once, then maximizes its empirical CPT value plus L w M ( 3 log t / ( 2 n a ) ) α w / 2 L_w M(3 \log t/(2n_a))^{\alpha_w}/2 L w M ( 3 log t / ( 2 n a ) ) α w /2 , using the valid conservative weight constants α w = 0.50 \alpha_w = 0.50 α w = 0.50 and L w = 5 L_w = 5 L w = 5 . The empirical CPT calculation handles atoms and ties directly. W-UCB uses neither the kernel nor the supplied noise CDFs, and learns each arm’s distribution separately; KCB and CPT-BPE form the matched known-CDF kernel comparison.
The linear comparison uses 50 arms in R 3 \mathbb{R}^3 R 3 with heterogeneous norms and θ ⋆ = ( 2 , 0 , 0 ) \theta_\star= (2, 0, 0) θ ⋆ = ( 2 , 0 , 0 ) . Rewards follow r t = x t T ( θ ⋆ + N t ) r_t = x_t^\mathsf{T}(\theta_\star+ N_t) r t = x t T ( θ ⋆ + N t ) , where N t ∼ N ( 0 , I 3 ) N_t \sim\mathcal{N}(0, I_3) N t ∼ N ( 0 , I 3 ) independently across rounds. Thus the noise standard deviation at arm x x x is ∥ x ∥ 2 \lVert x\rVert_2 ∥ x ∥ 2 . For linear KCB, we use B = ∥ θ ⋆ ∥ 2 = 2 B = \lVert\theta_\star\rVert_2 = 2 B = ∥ θ ⋆ ∥ 2 = 2 and η = max a ∥ x a ∥ 2 = 1 \eta= \max_a \lVert x_a\rVert_2 = 1 η = max a ∥ x a ∥ 2 = 1 .
The CPT-optimal arm is x C P T = ( 0.300 , 0 , 0 ) x_{\mathrm{CPT}} = (0.300, 0, 0) x CPT = ( 0.300 , 0 , 0 ) . The mean-optimal arm is x m e a n = ( 0.305 , 1 − 0.305 2 , 0 ) x_{\mathrm{mean}} = (0.305, \sqrt{1 - 0.305^2}, 0) x mean = ( 0.305 , 1 − 0.30 5 2 , 0 ) . Their means are 0.600 and 0.610, respectively, but their CPT values at γ = 0.50 \gamma= 0.50 γ = 0.50 are approximately 0.4628 and 0.4355. The remaining arms comprise four coordinate-direction controls and 44 deterministically generated arms with norms in [ 0.35 , 0.95 ] [0.35, 0.95] [ 0.35 , 0.95 ] and means below 0.58. We compare linear KCB, WOFUL, and OFUL on this same instance.
The arm norms vary, so the projected Gaussian noise has arm-dependent variance. Consequently, CPT scores need not preserve mean ordering, and WOFUL need not select the same arms as OFUL. We include OFUL as a risk-neutral comparison and evaluate all three methods using the same CPT regret. This Gaussian comparison uses the sub-Gaussian KCB setting and finite Gaussian CPT integrals; the CPT-BPE comparisons use bounded rewards.
Algorithmic results. Table 6 reports the numerical results corresponding to Figure 3 . Figure 4 additionally shows the decrease in regret per round on the bounded 2D instance. We run 30 paired trials at each T ∈ { 500 , 1000 , 2000 , 4000 , 8000 , 16000 , 32000 , 64000 } T \in\{500, 1000, 2000, 4000, 8000, 16000, 32000, 64000\} T ∈ { 500 , 1000 , 2000 , 4000 , 8000 , 16000 , 32000 , 64000 } , with independently configured horizon-dependent parameters. KCB has lower mean regret than CPT-BPE on both bounded instances at every tested horizon. In 1D, regret per round decreases from 0.105 to 0.015 for KCB and from 0.257 to 0.060 for CPT-BPE. In 2D, it decreases from 0.211 to 0.030 for KCB, from 0.296 to 0.078 for CPT-BPE, and from 0.259 to 0.189 for W-UCB. CPT-BPE exhibits a pronounced slowdown at larger horizons and overtakes W-UCB at T = 16000 T = 16000 T = 16000 . The descriptive log–log slopes over the combined 2D range are 0.593, 0.742, and 0.937, respectively; these fits describe finite-horizon growth rather than establish asymptotic theoretical exponents.
Table 6. Cumulative CPT regret, mean ± \pm ± one standard error over 30 paired trials at each horizon. KCB and CPT-BPE use their analyzed confidence constructions, rather than the practical 2 σ 2\sigma 2 σ rule in Table 5 . W-UCB estimates each arm’s CDF from observations. Values are rounded to two decimal places.
Table 5. Practical six-route comparison over 60 paired trials at T = 200 T = 200 T = 200 . Regret entries are cumulative reference-CPT regret, mean ± \pm ± one standard error. Success entries are native/CPT route-success percentages. All methods use the common 2 σ 2\sigma 2 σ exploration rule. Native optima are given in Table 4 .
Figure 3. Cumulative CPT regret across eight horizons from T = 500 T = 500 T = 500 to 64000, with logarithmic axes. (a) KCB and CPT–BPE on the bounded 1D kernel instance. (b) KCB, CPT–BPE, and empirical-CDF W-UCB on the bounded 2D kernel instance. (c) Linear KCB, WOFUL, and OFUL on the Gaussian linear instance with varying arm norms. KCB and CPT–BPE use their respective analyzed confidence constructions. Each horizon is run independently with its horizon-dependent parameters. Dashed lines in (b) are descriptive log–log fits, not theoretical rates.
Figure 4. CPT regret per round, R T / T R_T/T R T / T , on the bounded 2D kernel instance. The horizontal axis is logarithmic. Average regret decreases across the tested horizons for all three methods, with a pronounced reduction for CPT–BPE at larger horizons. At T = 64000 T = 64000 T = 64000 , mean regret per round is 0.030 for KCB, 0.078 for CPT–BPE, and 0.189 for empirical-CDF W-UCB.
On the varying-norm linear instance, WOFUL has slightly lower mean regret at T = 500 T = 500 T = 500 , while linear KCB has lower mean regret at every larger tested horizon. Both CPT-aware methods have lower mean CPT regret than OFUL throughout the tested range. Their descriptive log–log slopes are 0.527 for linear KCB, 0.621 for WOFUL, and 0.672 for OFUL.
Recorded KCB all-arm mean-confidence coverage and CPT-BPE phase-end mean-confidence coverage are 1.000 on the bounded runs.
On the varying-norm linear instance, the recorded mean-confidence coverage is 1.000 in every trial for all three methods. These are observed confidence diagnostics for the tested runs. Some CPT-BPE standard errors round to zero because trials can produce identical sampling sequences when their phase-end elimination decisions coincide.
Part II: Learning the Noise CDF
Part II measures the additional learning cost when the regional noise laws are unknown. We evaluate NPCB-Learned (Algorithm 4) in a finite realizable mean–noise class, where confidence-set membership and optimistic maximization can be computed directly. This experiment tests the finite-class algorithm rather than the computational scalability or regret rates of the continuous kernel extension.
Environment and objectives. The selectable arms are 100 equally spaced points x a ∈ [ 0 , 1 ] x_a \in[0,1] x a ∈ [ 0 , 1 ] . An arm belongs to the route with nearest center among (0.10, 0.25, 0.40, 0.55, 0.70, 0.85); routes group arms for reporting and are not separate selectable objects. For region r ( a ) r(a) r ( a ) , the mean is f θ ( a ) = θ r ( a ) ϕ a f_{\theta}(a)=\theta_{r(a)}\phi_a f θ ( a ) = θ r ( a ) ϕ a , where ϕ a = exp ( − ( x a − c r ( a ) ) 2 / ( 2 ( 0.04 ) 2 ) ) \phi_a=\exp(-(x_a-c_{r(a)})^2/(2(0.04)^2)) ϕ a = exp ( − ( x a − c r ( a ) ) 2 / ( 2 ( 0.04 ) 2 )) . The true route heights are (10, 8.5, 10.6, 7, 5, 3.5) in A–D and (10, 8.5, 9.5, 7, 5, 3.5) in E. Route 3 carries the rare-event noise; the other routes use the no-tail law described below. In A–D, rare losses make Route 1 CPT-optimal despite Route 3’s higher mean. In E, rare gains make Route 3 CPT-optimal despite its lower mean. All methods are evaluated using cumulative population CPT regret R T = ∑ t = 1 T [ g ( a ∗ ) − g ( a t ) ] R_T=\sum_{t=1}^{T}[g(a^*)-g(a_t)] R T = ∑ t = 1 T [ g ( a ∗ ) − g ( a t )] , with identity utility and the reference Tversky–Kahneman weight parameter γ = 0.50 \gamma=0.50 γ = 0.50 .
Finite mean and noise classes. Each candidate route height belongs to Θ = { 0 , 0.1 , … , 14 } \Theta=\{0,0.1,\ldots,14\} Θ = { 0 , 0.1 , … , 14 } , giving ∣ F ∣ = 141 6 |\mathcal{F}|=141^6 ∣ F ∣ = 14 1 6 . The true route-height vector lies in this product grid. Each regional noise law belongs to a family with p ∈ { 0.001 , 0.002 , 0.003 , 0.005 , 0.010 , 0.018 , 0.030 , 0.050 } p\in\{0.001,0.002,0.003,0.005,0.010,0.018,0.030,0.050\} p ∈ { 0.001 , 0.002 , 0.003 , 0.005 , 0.010 , 0.018 , 0.030 , 0.050 } , L ∈ { 5 , 10 , 15 , 30 , 60 , 100 } L\in\{5,10,15,30,60,100\} L ∈ { 5 , 10 , 15 , 30 , 60 , 100 } , and a no-tail law. The tail sign is supplied: downside in A–D and upside in E. Thus each region has 49 candidate laws and ∣ H ∣ = 49 6 |\mathcal{H}|=49^6 ∣ H ∣ = 4 9 6 ; the regional assignments, tail probabilities, and magnitudes are unknown.
The laws are continuous densities on the common support [ − s , s ] [-s,s] [ − s , s ] , with s = 10 6 s=10^6 s = 1 0 6 . Each combines a uniform component of mass κ = 10 − 6 \kappa=10^{-6} κ = 1 0 − 6 with two truncated, normalized Gaussian components of standard deviation 0.1. For a downside law, the component centers are p L / ( 1 − p ) pL/(1-p) p L / ( 1 − p ) and − L -L − L , with respective mixture weights ( 1 − κ ) ( 1 − p ) (1-\kappa)(1-p) ( 1 − κ ) ( 1 − p ) and ( 1 − κ ) p (1-\kappa)p ( 1 − κ ) p ; for an upside law, both centers change sign. The no-tail law has one Gaussian component centered at zero and the same uniform component. The untruncated mixtures are centered; the truncation changes their means by less than floating-point resolution at these settings. Sampling, likelihood evaluation, and CPT evaluation use the same normalized compact-support law. The density bounds are ρ min = κ / ( 2 s ) ≃ 4.72 × 10 − 9 \rho_{\min}=\kappa/(2s)\simeq4.72\times10^{-9} ρ m i n = κ / ( 2 s ) ≃ 4.72 × 1 0 − 9 and the valid common upper bound ρ max = 4 \rho_{\max}=4 ρ m a x = 4 . Every candidate mean lies in [ 0 , 14 ] [0,14] [ 0 , 14 ] , so every candidate reward lies in [ − 106 , 120 ] ⊆ [ − 120 , 120 ] [-106,120]\subseteq[-120,120] [ − 106 , 120 ] ⊆ [ − 120 , 120 ] .
Methods and implementation. We compare four methods using the same six-round initialization, one pull at the arm nearest each route center. Mean–UCB maximizes the optimistic mean over the joint likelihood and mean confidence sets. NPCB (known law) is the known-law specialization of the finite-class CPT learner: the true regional noise laws are supplied, while the means remain unknown. NPCB-Learned learns both components and maximizes CPT value over the joint feasible set. Plug-in MLE selects an arm using CPT values at the current regional joint maximum-likelihood estimates, without a confidence-set optimism bonus. It uses the same candidate mean and noise families. This baseline isolates point-estimate decisions from optimistic decisions within the specified model family; it is not a nonparametric empirical-CDF estimator.
For a global pair ( f , h ) (f,h) ( f , h ) , the log-likelihood factorizes as ℓ t ( f , h ) = ∑ r = 1 6 ℓ t , r ( θ r , h r ) \ell_t(f,h) = \sum_{r=1}^{6}\ell_{t,r}(\theta_r,h_r) ℓ t ( f , h ) = ∑ r = 1 6 ℓ t , r ( θ r , h r ) . The likelihood set is M t = { ( f , h ) : ℓ t ( f , h ) ≥ sup f ′ , h ′ ℓ t ( f ′ , h ′ ) − β H } \mathcal{M}_t = \{(f,h) : \ell_t(f,h) \ge\sup_{f',h'} \ell_t(f',h') - \beta^{H}\} M t = {( f , h ) : ℓ t ( f , h ) ≥ sup f ′ , h ′ ℓ t ( f ′ , h ′ ) − β H } . We use δ 0 = 0.05 \delta_0 = 0.05 δ 0 = 0.05 and the finite-class radius β H = log ( 2 ∣ F ∣ ∣ H ∣ / δ 0 ) + 1 = 57.732 \beta^{H} = \log(2|\mathcal{F}||\mathcal{H}|/\delta_0) + 1 = 57.732 β H = log ( 2∣ F ∣∣ H ∣/ δ 0 ) + 1 = 57.732 . The finite shifted-density class supplies a valid upper cover with N o p t ( Q , 1 / T ) ≤ ∣ F ∣ ∣ H ∣ N_{\mathrm{opt}}(\mathcal{Q},1/T) \le|\mathcal{F}||\mathcal{H}| N opt ( Q , 1/ T ) ≤ ∣ F ∣∣ H ∣ ; this need not be the smallest cover. For the known-law specialization, the noise class is a singleton, so the corresponding radius is β H = log ( 2 ∣ F ∣ / δ 0 ) + 1 = 34.381 \beta^{H} = \log(2|\mathcal{F}|/\delta_0) + 1 = 34.381 β H = log ( 2∣ F ∣/ δ 0 ) + 1 = 34.381 . The mean set C t \mathcal{C}_t C t is the product of regional grid sets whose empirical squared losses are within 8 s 2 log ( 6 ∣ Θ ∣ / δ 0 ) 8s^2\log(6|\Theta|/\delta_0) 8 s 2 log ( 6∣Θ∣/ δ 0 ) of the corresponding regional least-squares minimum.
For each arm, NPCB-Learned computes V ~ t ( a ) = sup { V h r ( a ) ( f ( a ) ) : ( f , h ) ∈ M t , f ∈ C t } \widetilde{V}_t(a) = \sup\{\mathcal{V}_{h_{r(a)}}(f(a)) : (f,h) \in\mathcal{M}_t, f \in\mathcal{C}_t\} V t ( a ) = sup { V h r ( a ) ( f ( a )) : ( f , h ) ∈ M t , f ∈ C t } . Regional factorization permits this optimization without enumerating all 1416496 1416496 1416496 global pairs: other regions are assigned their best mean-feasible likelihood values when testing a candidate regional pair. The CPT score uses the same mean–noise pair that passes both constraints. The implementation reconstructs a full feasible global witness for the selected arm each round. Finite-set optimization is exact; CPT integrals are evaluated using deterministic quadrature and interpolation tables, with integration and mean-grid spacings 0.005.
Trials and reporting. The horizons and true tail parameters are listed in Table 7 . We use 30 paired trials with base seed 0. For each configuration and trial, a common table of potential noise realizations for every arm and round is supplied to all methods. A trial’s final route is its modal route over the last 20% of rounds. Learned success is the fraction of NPCB-Learned trials whose final route is CPT-optimal. This route statistic is distinct from exact-arm identification. Table entries report mean regret and one standard error; curve shading reports one standard deviation, showing variation across trials.
Table 7. Part II: cumulative CPT regret, mean ± one standard error over 30 paired trials. Parentheses give the most frequent final route across trials; each trial’s final route is measured over its last 20% of rounds. The final column reports CPT-optimal final-route success for plug-in MLE/NPCB-Learned. A–D have rare losses; E has rare gains.
Learning cost and the plug-in comparison. The known-law specialization quickly selects the CPT-preferred route and incurs only a small initialization and mean-learning cost. NPCB-Learned incurs additional regret while resolving uncertainty about the regional noise laws, then selects the CPT-preferred route in all recorded trials. In A–D, its final mean regret ranges from 652 to 902, compared with approximately 33–35 when the true laws are supplied. The especially rare downside event in A has probability 10 − 3 10^{-3} 1 0 − 3 ; observing such an event requires substantial sampling of its region.
E illustrates a larger finite-sample cost. NPCB-Learned incurs mean regret 98458, compared with 50.1 for the known-law specialization and 211787 for Mean-UCB, while reaching the CPT-optimal final route in all trials. The route-convergence curves show that this outcome follows a prolonged learning period rather than immediate identification.
NPCB-Learned has lower mean CPT regret than plug-in MLE in every configuration (Table 7 ). Its CPT-optimal final-route success is 100% throughout, whereas plug-in MLE achieves 20.0%, 16.7%, 13.3%, 13.3%, and 0% in A–E, respectively. Because both methods optimize CPT under the same unknown-law model, this comparison distinguishes confidence-set optimism from point-estimate decisions rather than disagreement between risk objectives. This observation concerns this plug-in rule and these instances; it does not establish superiority over all distribution-learning methods. Mean-UCB optimizes a different objective, so its continuing CPT regret primarily reflects the preference reversal rather than failed mean learning.
For NPCB-Learned, the median last round selecting a route other than the CPT-optimal route is approximately 3865, 788, 1461, 848, and 11519 in A–E, respectively; the corresponding maxima over trials are 8225, 1608, 2255, 1085, and 12446. All are before the final 20% of their respective horizons. The recorded regret trajectories also plateau over that final interval. Route selection alone would not imply zero regret within a region; the plateau is a separate observation from the arm-level regret records.
Confidence and feasibility diagnostics. For the confidence-set methods, the recorded fraction of rounds in which the generating model belongs to both confidence sets is 1.000 in every configuration and trial. For NPCB-Learned, the reconstructed global witness passes the likelihood and mean-confidence constraints at every selected arm; the recorded number of feasibility violations is zero. These are sample-path diagnostics for the tested runs, not a statement that a high-probability confidence event occurs on every possible run.
For NPCB-Learned, the mean confidence set excludes at least one regional candidate height in 37.84%, 5.17%, 0%, 0%, and 30.11% of rounds in configurations A–E, respectively. These frequencies measure candidate exclusion, not its effect on arm selection.
Experimental conclusions
The two parts support complementary conclusions.
Part I demonstrates that the choice of risk objective can qualitatively change the preferred route. Under the common practical exploration rule, KCB (2 σ 2\sigma 2 σ ) reaches the CPT-optimal final route in every trial at the reference parameters across the downside-trap and upside-lottery instances. The sensitivity analysis shows that CVaR and MV behavior depends on their tuning parameters; it does not support a parameter-independent claim that MV fails every rare-loss configuration. The additional known-CDF experiments evaluate KCB and CPT–BPE using their analyzed confidence constructions, include CPT-aware comparisons in two-dimensional kernel and linear instances, and report regret across multiple horizons. These scaling diagnostics do not establish theoretical regret exponents.
Part II isolates the statistical cost of learning the noise CDF within the finite realizable model. NPCB-Learned (Algorithm 4) reaches the CPT-optimal final route in every recorded trial, while paying a substantial, instance-dependent relative cost to the known-law specialization. It also achieves lower mean CPT regret than plug-in MLE in every configuration, with final-route success of 100% versus 0–20%. The large Config E gap illustrates the finite-sample cost of learning rare-upside laws when the mean favors another route. The confidence and feasibility diagnostics support the finite-class implementation; these experiments do not verify the continuous-class learned-CDF regret rates or their inverse-density dependence.
Uncertainty visualization. In the practical Part I comparison, learning-curve shading shows mean cumulative CPT regret ± \pm ± one standard error across 60 trials. The additional Part I scaling experiments use 30 paired trials, with error bars of one standard error. In Part II, learning-curve shading shows mean cumulative CPT regret ± \pm ± one standard deviation across 30 paired trials. Numerical regret tables report means ± \pm ± one standard error.
Figure 2 (PDF p. 43). Six-route objective landscapes and practical decisions. Each row is a configuration A–E. Left: population Mean, CVaR, MV, and CPT scores, computed from the true reward laws independently of exploration. Right: cumulative reference-CPT regret over 60 paired trials, with one standard-error shading. All right-panel methods use the common 2 σ 2\sigma 2 σ rule; the KCB legend here denotes KCB (2 σ 2\sigma 2 σ ). These curves illustrate objective disagreement and practical learning behavior, rather than validate the analyzed KCB confidence construction.
Figure 5. Part II: unknown-noise learning. Rows correspond to A–E. Left: true mean and CPT landscapes, with fitted CPT values from the joint maximum-likelihood model on arms pulled at least 30 times in a representative NPCB-Learned trial. The representative trial is the successful trial nearest the median final regret. These fitted values are diagnostics, not the optimistic scores used for selection or a full-domain CDF accuracy assessment. Right: mean cumulative CPT regret for Mean-UCB, the known-law specialization, NPCB-Learned, and plug-in MLE; shading is one standard deviation across 30 trials.
Figure 6. Selection of the CPT-optimal route in Part II. Each panel shows the smoothed fraction of the 30 trials selecting the CPT-optimal route at each round for the four methods. Smoothing is used only for visualization; route-success and last-selection statistics are calculated from the unsmoothed trajectories.