Risk-Sensitive Non-Parametric and Kernel Bandits

Devdan Dey; Sujoy Bhore; Avishek Ghosh

stat.MLNov 4, 2026

Risk-Sensitive Non-Parametric and Kernel Bandits

Authors: Devdan Dey, Sujoy Bhore, Avishek Ghosh

Organizations: Department of Computer Science and Engineering, Indian Institute of Technology Bombay.

Abstract

We study non-parametric bandits in which arms are evaluated using Cumulative Prospect Theory (CPT) rather than expected reward. We consider continuous action spaces with arm-dependent noise and propose Non-Parametric CPT Bandits ( $\mathtt{NPCB}$ ), an optimistic algorithm that decouples mean estimation from CPT-based decision-making. We prove CPT regret of order $\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 its covering number in the sup norm. This matches the order-wise regret of classical non-parametric bandits, showing that CPT risk sensitivity incurs no additional order-wise regret cost. We extend $\mathtt{NPCB}$ to unknown noise CDFs, retaining the known-CDF mean-learning term and adding a CDF-learning cost governed by a distributional Eluder dimension. We also study Kernel-CPT bandits and obtain information-gain-based regret bounds for a broad range of kernels, matching the corresponding risk-neutral kernel rates up to logarithmic factors.

Figures & tables

Kernel	$\gamma_{T}(1)$	General NPCB	CPT-BPE
Linear	$O(d\log T)$	$\widetilde{O}(d\sqrt{T})$	$\widetilde{O}(d\sqrt{T})$
Sq. Exp.	$O((\log T)^{d+1})$	$\widetilde{O}(\sqrt{T})$	$\widetilde{O}(\sqrt{T})$
Matérn	$\widetilde{O}(T^{d/(2\nu+d)})$	$\widetilde{O}(T^{1/2+2d/\nu})$	$\widetilde{O}(T^{(\nu+d)/(2\nu+d)})$

Table 1: 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.

Figure 1: Risk preferences and CPT learning. (a)–(b) Population objective scores in Config B (rare loss) and Config E (rare gain). CVaR uses $\alpha=0.10$ , MV uses $c=1$ , and CPT uses identity utility and Tversky–Kahneman weighting with $\gamma=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.

	Mean CPT regret ( $\pm$ s.e.)
Cfg	Known law	Plug-in MLE	NPCB-Learned
A	$35.2\pm 0.1$	$2692.1\pm 248.3$	$901.7\pm 50.7$
B	$33.4\pm 0.0$	$5354.7\pm 442.8$	$681.3\pm 34.2$
C	$33.6\pm 0.1$	$1846.2\pm 133.0$	$821.5\pm 29.7$
D	$33.4\pm 0.0$	$2701.0\pm 195.4$	$652.4\pm 14.4$
E	$50.1\pm 0.0$	$204225.3\pm 0.9$	$98458.2\pm 887.7$

Table 2: Unknown-CDF mean CPT regret

\pm

s.e. over

30

trials;

T=(20000,10000,5000,5000,30000)

for A–E.

Appendix figures & tables12 assets

Supplementary material from the paper’s appendix.

Appendix

c=B+\frac{\eta}{\sqrt{\lambda}}\sqrt{2\log\frac{2m|\mathcal{A}|}{\delta}}.

Appendix

Algorithm 3 CPT Batched Pure Exploration. ( CPT-BPE )

\displaystyle\ell_{t}(f,h)

\displaystyle=\sum_{\tau<t}\log p_{h}(r_{\tau}-f(a_{\tau})\mid a_{\tau}).

Appendix

Algorithm 4 NPCB-Learned

Instance	Arms	Noise	Compared methods
Six-route configurations A–E	$100$ in $[0,1]$	Gaussian background; two-point tails	Mean, CVaR, MV, KCB ( $2\sigma$ )
Bounded 1D kernel	$50$ in $[0,1]$	Centered two-point laws	KCB , CPT-BPE
Bounded 2D kernel	$7\times 7$ in $[0,1]^{2}$	Centered two-point laws	KCB , CPT-BPE , W-UCB
Gaussian linear	$50$ arms with varying norms in $\mathbb{R}^{3}$	Gaussian in-parameter noise	Linear KCB , WOFUL, OFUL

Appendix

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.

Cfg	Mean	CVaR(.1)	MV(1)	MV(2)	CPT(.5)
A	R3	R3	R3	R3	R1
B	R3	R3	R1	R1	R1
C	R3	R1	R3	R1	R1
D	R3	R1	R1	R1	R1
E	R1	R1	R1	R1	R3

Appendix

Table 4: Population-optimal routes on the

100

-arm grid in Part I. CVaR uses

\alpha=0.10

, and CPT uses

\gamma=0.50

. The MV column with

c=2

supports the sensitivity discussion. These are population optima, not learned final routes.

Cfg	Metric	Mean-UCB	CVaR-UCB	MV-UCB	KCB ( $2\sigma$ )
A	Regret	$63.5\pm 0.38$	$63.2\pm 0.69$	$63.2\pm 0.69$	$24.2\pm 0.03$
	Success (native/CPT)	$97/3$	$95/5$	$95/5$	$100/100$
B	Regret	$151.6\pm 3.35$	$143.2\pm 5.08$	$25.7\pm 0.03$	$22.0\pm 0.03$
	Success (native/CPT)	$95/5$	$88/12$	$100/100$	$100/100$
C	Regret	$99.5\pm 4.39$	$25.2\pm 0.08$	$42.0\pm 4.54$	$21.9\pm 0.06$
	Success (native/CPT)	$82/18$	$100/100$	$18/82$	$100/100$

Appendix

Table 5: Practical six-route comparison over

60

paired trials at

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\sigma

exploration rule. Native optima are given in Table 4 .

Figure 2: 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\sigma

rule; the KCB legend here denotes KCB (

2\sigma

). These curves illustrate objective disagreement and practical learning behavior, rather than validate the analyzed KCB confidence construction.

Panel of Figure 3 — Figure 3: Cumulative CPT regret across eight horizons from $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

, 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

, mean regret per round is

0.030

for KCB ,

0.078

for CPT-BPE , and

0.189

for empirical-CDF W-UCB.

	Bounded 1D kernel		Bounded 2D kernel			Gaussian linear ( $d=3$ )
$T$	KCB	CPT-BPE	KCB	CPT-BPE	W-UCB	Linear KCB	WOFUL
500	$52.30\pm 0.09$	$128.52\pm 0.00$	$105.34\pm 0.13$	$147.95\pm 0.00$	$129.47\pm 0.16$	$57.83\pm 1.87$	$51.51\pm 1.23$
1000	$87.41\pm 0.12$	$245.23\pm 0.00$	$191.38\pm 0.12$	$294.18\pm 0.00$	$253.71\pm 0.29$	$83.61\pm 2.51$	$79.29\pm 2.38$
2000	$141.53\pm 0.13$	$448.93\pm 0.55$	$330.94\pm 0.21$	$583.45\pm 0.00$	$495.74\pm 0.24$	$118.21\pm 2.60$	$109.92\pm 2.43$
4000	$220.06\pm 0.19$	$713.56\pm 0.00$	$535.00\pm 0.32$	$1164.53\pm 0.00$	$961.21\pm 0.25$	$156.28\pm 2.45$	$143.74\pm 2.84$
8000	$333.33\pm 0.34$	$1113.10\pm 1.85$	$799.93\pm 0.41$	$2208.74\pm 4.81$	$1845.01\pm 0.68$	$215.71\pm 4.40$	$198.87\pm 4.02$

Appendix

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\sigma

rule in Table 5 . W-UCB estimates each arm’s CDF from observations. Values are rounded to two decimal places.

Cfg	$p$	$L$	$T$	Mean-UCB	NPCB (known law)	Plug-in MLE	NPCB-Learned	Success (%) plug-in/learned
A	0.001	15	20000	$3572.2\pm 0.6$ (R3)	$35.2\pm 0.1$ (R1)	$2692.1\pm 248.3$ (R3)	$901.7\pm 50.7$ (R1)	$20.0/100$
B	0.003	15	10000	$6610.2\pm 0.6$ (R3)	$33.4\pm 0.0$ (R1)	$5354.7\pm 442.8$ (R3)	$681.3\pm 34.2$ (R1)	$16.7/100$
C	0.018	5	5000	$2323.1\pm 0.8$ (R3)	$33.6\pm 0.1$ (R1)	$1846.2\pm 133.0$ (R3)	$821.5\pm 29.7$ (R1)	$13.3/100$
D	0.030	5	5000	$3296.7\pm 0.8$ (R3)	$33.4\pm 0.0$ (R1)	$2701.0\pm 195.4$ (R3)	$652.4\pm 14.4$ (R1)	$13.3/100$
E	0.010	100	30000	$211787.4\pm 214.7$ (R1)	$50.1\pm 0.0$ (R3)	$204225.3\pm 0.9$ (R1)	$98458.2\pm 887.7$ (R3)	$0.0/100$

Appendix

Table 7: Part II: cumulative CPT regret, mean

\pm

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.

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.

Panel of Figure 6 — 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.

Multi-Armed Bandits

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

See all 362 papers

Jun 18, 2026

Matching Markets meet Cumulative Prospect Theory: Towards Optimal and Adversarially Robust Learning

We study a multi-agent multi-armed bandit problem in the competitive setup with two-sided matching markets under a human centric decision making model. To capture human preferences, we use cumulative prospect theory (CPT) that weighs the actions of the agent in a nonlinear fashion using a (

α

-Hölder continuous) weight function. CPT has been widely used in behavioral economics and risk sensitive machine learning to emulate human preferences. We analyze the state-of-the-art learning algorithm with CPT weight distorted rewards and obtain a player optimal regret of

\mathcal{O}(K\log T \left(\frac{1}Δ\right)^{2/α})

, where

K

denotes the number of arms,

T

is the learning horizon, and

Δ

represents (suitably defined) players' minimum preference gap. Noticing the dependence on

Δ

to be sub-optimal, we further improve this regret by judiciously selecting the active set of arms during exploration, which removes the dependence on

K

in the dominant term and achieves an improved (optimal) regret guarantees in the setting where the number of arms

K

is significantly larger than the number of players

N

. In addition, we consider adversarial markets where the observed rewards of the agents may be corrupted. We propose and analyze algorithms for robust markets with CPT as risk sensitive measure in both settings where the total corruption budget is known and where it is unknown, and establish logarithmic player-optimal regret guarantees in both cases.

Ananya Kunisetty, Avishek Ghosh

Indian Institute of Technology Bombay, Mumbai 400076, India

Multi-Armed Bandits Decision-Making under Uncertainty Adversarial Bandits

Ask PDF

Jun 8, 2026

Asymptotic Optimality of Thompson Sampling for Risk-Averse Bandits with Sub-Gaussian Rewards

We prove that

ρ\text{-}\mathrm{NPTS}_{\mathrm{SG}}

, an anchor-free nonparametric Thompson Sampling algorithm for risk-averse bandits, achieves regret matching the instance-dependent lower bound to leading order in

\log n

, establishing it as asymptotically optimal for any continuous risk functional

ρ

(CVaR, mean-variance, Sharpe ratio, distortion risk measures, and more) on the class of distributions with bounded density and sub-Gaussian tails, including Gaussian arms. Both this result and its bounded-support counterpart require only continuity of

ρ

: strictly weaker than the dominance condition of prior parametric Thompson Sampling results, and strictly weaker than the Lipschitz condition of UCB-type algorithms, yielding the first instance-optimal guarantees for non-Lipschitz functionals such as the Sharpe ratio without parametric reward assumptions. The bounded-support case is developed first as a stepping stone sharing the same proof structure. The key technical contributions are a discretisation lemma (bounded support) and a truncated discretisation lemma (sub-Gaussian tails), each projecting the growing-alphabet Dirichlet posterior onto a fixed grid via the Dirichlet aggregation property, holding all polynomial prefactors at fixed degree independent of sample size and breaking the super-exponential barrier that blocked prior proofs.

Joel Q. L. Chang

Thompson Sampling Multi-Armed Bandits

Ask PDF

Apr 16, 2026

Regret Tail Characterization of Optimal Bandit Algorithms with Generic Rewards

We study the tail behavior of regret in stochastic multi-armed bandits for algorithms that are asymptotically optimal in expectation. While minimizing expected regret is the classical objective, recent work shows that even such algorithms can exhibit heavy regret tails, incurring large regret with non-negligible probability. Existing sharp characterizations of regret tails are largely restricted to parametric settings, such as single-parameter exponential families. In this work, we extend the

\KLinf

-UCB algorithm of to a broad nonparametric class of reward distributions satisfying mild assumptions, and establish its asymptotic optimality in expectation. We then analyze the tail behavior of its regret and derive a novel upper bound on the regret tail probability. As special cases, our results recover regret-tail guarantees for both bounded-support and heavy-tailed (moment-bounded) bandit models. Moreover, for the special case of finitely-supported reward distributions, our upper bound matches the known lower bound exactly. Our results thus provide a unified and tight characterization of regret tails for asymptotically optimal KL-based UCB algorithms, going beyond parametric models.

Subhodip Panda, Shubhada Agrawal

Department of ECE · Indian Institute of Science · Bangalore, India

Multi-Armed Bandits UCB Algorithms

Ask PDF

Abstract

Multi-Armed Bandits

Explore similar work

Matching Markets meet Cumulative Prospect Theory: Towards Optimal and Adversarially Robust Learning

Asymptotic Optimality of Thompson Sampling for Risk-Averse Bandits with Sub-Gaussian Rewards

Regret Tail Characterization of Optimal Bandit Algorithms with Generic Rewards