Risk-Sensitive Non-Parametric and Kernel Bandits: CPT Regret at No Extra Cost

When Bandits Meet Cumulative Prospect Theory

Traditional Bandits algorithms typically optimize expected reward, but human decision-making often exhibits risk-sensitive characteristics—exactly what Cumulative Prospect Theory (CPT) captures. A new theoretical study introduces CPT into non-parametric Bandits and kernel Bandits frameworks, proposes the NPCB algorithm, and proves that risk-sensitive decision-making incurs no additional order-level regret cost.

Cumulative Prospect Theory (CPT), proposed by Tversky and Kahneman in 1992, is a refinement of the original prospect theory that describes human risk decisions under uncertainty. CPT has two core components: first, a probability weighting function, whereby people over-weight small-probability events and under-weight medium-to-high-probability events, systematically deviating from expected utility; second, a value function, which defines utilities for gains and losses relative to a reference point, with the loss region typically steeper (loss aversion) and risk attitudes reversing at the two ends—risk aversion in the gain region and risk seeking in the loss region. Unlike expected utility theory, CPT utility is not a linear expectation of rewards but a nonlinear functional of the reward distribution: it applies nonlinear weights to sorted cumulative probabilities before weighting the value function. This property is the main technical obstacle to introducing CPT into Bandits: traditional optimistic algorithms rely on the linear additivity of expectations, whereas the CPT objective breaks this structure, requiring redesign of the estimation and decision-making pipeline.

Core Problem: Continuous Action Spaces under CPT

The study considers continuous action spaces, where each arm's noise distribution can differ (arm-dependent noise). The goal is no longer to maximize expected reward but to maximize CPT utility. CPT uses different weighting and value functions for gains and losses, making the decision objective a nonlinear functional; directly applying traditional optimistic algorithms is no longer feasible.

The authors' proposed NPCB (Non-Parametric CPT Bandits) algorithm adopts a decoupled design: mean estimation and CPT-based decision-making are performed separately. The mean-learning component follows optimistic estimation from non-parametric regression, while CPT decisions compute utility based on the estimated reward distribution and select arms. This decoupling allows the algorithm to exploit the structure of non-parametric function classes while embedding risk-sensitive preferences.

Eluder dimension is a combinatorial measure of the "complexity" of a function class, introduced by Russo and Van Roy, commonly used to analyze the regret of optimistic algorithms. Intuitively, it characterizes the maximum length of a point sequence in a function class that can be "distinguished point by point"—if function values at new points can always be constrained by prior observations, the sequence stops growing. For linear function classes, the Eluder dimension is of the same order as the dimension; for general non-parametric function classes, it is typically related to covering numbers or metric entropy. In regret bounds for non-parametric Bandits, the Eluder dimension replaces the finite number of arms or hypotheses as the key quantity controlling exploration cost. The CPT regret bound in this paper features both the Eluder dimension and the covering number, which is the standard way to characterize the complexity of non-parametric function classes, and explains why the bound is of the same order as classical non-parametric Bandits—CPT only changes the decision criterion, not the learning difficulty of the function class itself.

Regret Bound: Same Order as Classical Non-Parametric Bandits

The theoretical analysis yields an upper bound on CPT regret:

$$\widetilde{\mathcal O}\bigl(\sqrt{T,\dim_E(\mathcal F,T^{-2}),\log N(\mathcal F,T^{-2},|\cdot|_\infty)}\bigr)$$

where $\dim_E$ is the Eluder dimension of the function class $\mathcal F$, $T$ is the time horizon, and $N$ is the covering number under the supremum norm. This result is of the same order as the regret of classical non-parametric Bandits, meaning that CPT risk sensitivity incurs no additional order-level regret cost. This is the work's most central conclusion: risk preferences can be incorporated without sacrificing learning efficiency.

Extension to Unknown Noise CDF

In practice, noise distributions are often unknown. The authors extend NPCB to the case of unknown noise CDF; the algorithm retains the mean-learning term from the known-CDF setting and adds a CDF-learning cost controlled by a distributional Eluder dimension. This extension shows that the additional cost of distribution learning can be clearly characterized and does not break the overall order structure of the regret.

The distributional Eluder dimension is a generalization of the Eluder dimension idea to distribution learning. When the noise CDF is unknown, the algorithm must learn not only the conditional mean function but also the full reward distribution (at least its CDF), because CPT utility depends on the entire distribution rather than just the mean. The distributional Eluder dimension measures the growth rate of the number of distributions in the candidate class that remain distinguishable given historical observations. It quantifies the difficulty of "learning the distribution" as a dimension-like quantity related to the structure of the function class, thereby enabling CDF estimation error to be incorporated into regret analysis. The value of this concept is that it allows the regret under unknown noise to be decomposed into a mean-learning term and a distribution-learning term, and clearly shows that the latter does not dominate the overall order—as long as the distributional Eluder dimension of the distribution class grows controllably, the CPT risk-sensitive objective under unknown noise retains the same regret order as in the known-noise case.

Information-Gain Perspective for Kernel CPT Bandits

The study further examines kernel CPT Bandits and provides information-gain-based regret bounds for a broad class of kernels, matching the rates of corresponding risk-neutral kernel methods up to logarithmic factors. This shows from an information-theoretic perspective that the CPT risk-sensitive objective also does not change the order of the learning rate within the kernel methods framework.

Information gain is a core tool in the analysis of kernel Bandits and Gaussian process Bandits, typically defined as the reduction in posterior entropy of the unknown function before and after observation, denoted $\gamma_T$. In kernel methods, the maximum information gain is directly related to the effective dimension of the kernel matrix and determines the size of the exploration term in the regret bound of optimistic algorithms. Information-gain-based regret bounds are algorithm-agnostic: they do not depend on the specific kernel form and only require the kernel to satisfy certain regularity conditions, thus uniformly covering a broad class of kernels such as finite-dimensional linear kernels, squared exponential kernels, and Matérn kernels. The significance of providing an information-gain-type regret bound for kernel CPT Bandits lies in embedding the CPT risk-sensitive objective into this mature analytical framework and proving that the resulting rate matches that of risk-neutral kernel methods up to logarithmic factors. This shows from an information-theoretic perspective that CPT's nonlinear utility only changes the decision rule, not the amount of information the kernel function class can provide, and thus does not introduce an additional order of learning cost.

Practical Significance and Open Problems

This work provides a theoretical foundation for risk-sensitive decision-making: in continuous action spaces and kernel methods, the CPT objective can coexist with efficient learning. Potential applications include financial decision-making, recommender systems, and medical treatment selection—scenarios that require characterizing risk preferences. However, the current results are primarily theoretical; experimental validation and practical guidelines for specific CPT parameterizations remain to be supplemented.

Key Takeaways

• NPCB achieves risk-sensitive Bandits in continuous action spaces by decoupling mean estimation from CPT decision-making.
• CPT regret is of the same order as classical non-parametric Bandits, with no additional order-level cost for risk sensitivity.
• The unknown-noise-CDF extension introduces a distributional Eluder dimension to characterize learning cost.
• The information-gain regret bound for kernel CPT Bandits matches the risk-neutral rate.