CS Paper Radar

Variance-Adaptive Upper Confidence Bounds for Multi-Armed Bandits with Kaplan--Meier Survival Estimation

Yangfan Cui, Andrew Papanicolaou

cs.LG stat.MLmath.PR ·submitted 2026-11-18 05:42 UTC · v1

Abstract

We study the stochastic multi-armed bandit problem in which the reward associated with each arm is the survival probability at a pre-specified time horizon, and the observed outcome is a right-censored time-to-event variable. Standard bandit algorithms face delayed and partial observations in this setting. Prior adaptations for the Kaplan--Meier (KM) estimator rely on Hoeffding-type bounds that ignore the inherent heteroscedasticity of continuous survival processes. To bridge this gap, we propose KM-UCB, a variance-adaptive policy that unites continuous-time survival analysis with discrete sequential decision-making. By leveraging martingale theory and continuous influence functions, we derive a fixed-cohort empirical Bernstein bound parameterized by Greenwood's variance formula. For realtime allocation, we retain the Greenwood index and use a survival bound from completed records to review the recommended arm. Under catch-up reporting, the policy has logarithmic expected regret with an arm-specific variance term in the exploration bound. We evaluate the original policy in a dual-layer delayed simulation and a retrospective replay of breast cancer trial data, and evaluate the correction in a separate paired simulation.

Closest papers

Nearest neighbours by meaning across the whole index.

The Price of Current-Effect Inference in Nonstationary Multi-Armed Bandits

cs.LG stat.ML ·2026-10-21 ·Sharan Sahu, Martin T. Wells
similarity 0.76
Abstract · 49 pages, 8 figures, 5 tables

Adaptive experiments use bandit algorithms to favor interventions with higher expected rewards. However, decision-makers also require reliable inference on current treatment effects: differences between intervention and reference-arm mean rewards at the present time, rather than historical averages. These objectives conflict: reward maximization favors better interventions, whereas current-effect inference requires continued exploration of potentially suboptimal interventions as outcomes change over time. We characterize this tradeoff for $K$-arm bandits with Hölder-smooth mean rewards of exponent $β\in(0,1]$ and constant $L$. Requiring high-probability simultaneous coverage of all current effects by confidence intervals of width at most $w$, we establish matching minimax bounds, up to logarithmic factors, on expected dynamic regret. Over horizon $T$, our algorithm TRACE (Tracking Rewards and Current Effects) achieves regret of order $\widetilde{O}_β\left(\sqrt{KT}+K^{β/(2β+1)}L^{1/(2β+1)}T^{(β+1)/(2β+1)}+Kw^{-2}(1+L^{1/β}w^{-1/β})\right)$, where the notation hides logarithms and constants depending only on $β$. This regret--precision tradeoff separates reward-learning regret from the cost of refreshing current-effect estimates, which remains unavoidable even when one arm is uniformly optimal. An empirical-Bernstein e-process extension adapts exploration to realized prediction errors while preserving worst-case guarantees. When within-block drift is negligible relative to sampling error, all observations, including reward-learning observations, can be reused for asymptotically normal pointwise inference and stronger local stationarity yields local asymptotic efficiency. Finally, we show that regret constraints can prevent honest adaptation to unknown smoothness and support our theory with extensive numerical experiments.

0.08

Safety by Design: Realized-Cost Constraints for Contextual Bandits with Continuous Actions

cs.LG ·2026-08-27 ·Spyros Dragazis, Aldo Pacchiano
theory similarity 0.75
Abstract

Contextual bandits are a standard framework for sequential decision-making under uncertainty, with applications in clinical trials, dosage selection, recommendation systems, and autonomous systems. Safety is central in many of these applications, since a single unsafe decision in settings such as dosage selection or autonomous driving can have catastrophic consequences. A common way to model safety in bandit problems is to associate each action with both a reward signal and a cost signal, and to optimize reward subject to constraints on cost. Most existing safety-constrained bandit models enforce safety by requiring the expected cost of each action to remain below a prescribed threshold. However, this may be insufficient in heteroscedastic settings, where the chosen action affects not only the expected reward and cost, but also the variability of the observed outcomes. We study contextual bandits with one-dimensional continuous actions and stage-wise high-probability constraints on the realized cost. We propose High-Probability Constrained UCB, an optimistic-pessimistic algorithm that explores for reward while conservatively estimating the safe action set. For linear reward and cost models, we prove a tight $\tilde{\mathcal{O}}(d\sqrt{T})$ regret bound, and we extend the analysis to general function classes using the eluder dimension. Experiments show that enforcing realized-cost safety substantially reduces violations compared with expected-cost constrained baselines.

0.08

UCB-min: Combining Bandits Under Variance Heterogeneity (Extended Version)

cs.LG ·2026-11-09 ·Lilia Izri, Benoit Groz, Silviu Maniu
publishedtheory similarity 0.73
Abstract · Extended version of short conference paper accepted at IEEE BigData 2026

Multi-armed bandits are a natural framework for many real-world sequential decision problems, from recommender systems and clinical trials to educational test recommendation and online advertising. The performance of these algorithms depends on how they explore different arms, and exploration strategies range from variance-independent (e.g., UCB1) to variance-aware (e.g., UCB-V). In practice the reward variance of each arm is rarely known and varies widely across arms, and the reward support is often underspecified. In these cases no single rule is uniformly best: variance-independent methods are robust but loose when variances are small, while variance-aware methods are tight only when their variance estimates and the assumed support bound are reliable. Such heterogeneous, unknown variances arise in many settings, for instance when multiple objectives are scalarized into a single reward. We propose UCB-min, a per-arm adaptive meta-algorithm that selects, for each arm, the tighter of a variance-independent and a variance-aware exploration bonus, without prior knowledge of the variance regime and without reward normalization. We prove that, with UCB-V as variance-aware base, its regret is bounded by the sum of the two base bounds at the standard exploration constant, and by their per-arm minimum, up to a constant, for a larger one. We validate it on synthetic data, an educational tutoring task, and two group-recommendation benchmarks (MovieLens, Steam), showing that UCB-min consistently tracks the best base algorithm across diverse variance regimes and datasets.

0.19

Multi-Armed Bernoulli Bandits via Minimax Single-Arm Stopping

cs.LG math.OCstat.ML ·2026-09-19 ·Huikang Liu, Zhengchao Wang, Daniel Kuhn, Wolfram Wiesemann
benchmark similarity 0.72
Abstract · This work is a preprint and has not been submitted to any conference or journal yet

We develop an index policy for finite-horizon Bernoulli multi-armed bandits from minimax solutions to single-arm bandit (SAB) problems. Each SAB problem involves choosing between an unknown Bernoulli arm and a known reward. We show that minimizing worst-case regret of SAB problems over all non-anticipative policies admits an exact semi-infinite linear programming formulation. The resulting stopping policies offer a natural way to compare arms: the higher the known reward against which a policy continues sampling, the more promising the unknown arm. We turn this intuition into indices based on cumulative continuation probabilities, with a monotone adjustment and a reward-shortfall cap. By relating index errors to the regret of single-arm stopping policies, we establish a distribution-free regret bound of $4.45\sqrt{KT}+10.75K$ for $K$ arms and horizon $T$. This bound matches the minimax-optimal regret order established in the literature. The guarantee extends to rewards supported on $[0,1]$ through Bernoulli randomization. We also provide a finite-grid implementation with quantified approximation loss. In numerical experiments, the SAB-based index policy achieves lower worst-case regret than every tested benchmark policy across all evaluated numbers of arms and horizons, while closely matching the grid-based MAB minimax policy in the two-arm setting.

0.21

Meta-LinEXP3: Online-within-Online Learning for Adversarial Linear Contextual Bandits

cs.LG math.OC ·2026-09-09 ·Hao Li, Jie Xu, Zheng Xie
similarity 0.71
Abstract

Meta-learning has emerged as an effective paradigm for transferring knowledge across sequential bandit tasks. While substantial progress has been made for stochastic bandits and non-contextual adversarial bandits, meta-learning for adversarial linear contextual bandits (ALCBs) with random action sets remains largely unexplored. To address this problem, we propose Meta-LinEXP3, an online-within-online algorithm that constructs a predictable task-level prior from completed tasks to guide the inner LinEXP3 learner. For known context distributions, we develop a policy-centered estimator that achieves an intrinsic-dimension $\mathcal{O}(\sqrt{n})$ per-task regret bound. For unknown distributions, we introduce a past-only regularized moment estimator with an $\mathcal{O}(n^{2/3})$ leading regret term and explicit finite-sample error. We further establish a direct connection between prior accuracy and transfer regret, showing that increasingly accurate priors yield sublinear transfer-dependent regret across tasks. Experiments demonstrate the effectiveness of Meta-LinEXP3, including its application to structured hyperspectral tensor sampling.

0.11

Sharper Regret Bounds for Time-Varying Gaussian Process Bandits with Constant Exploration

cs.LG stat.ML ·2026-08-19 ·Matthias Mandl, Hanne Kekkonen
similarity 0.70
Abstract · 23 pages, 1 figure. Code included as ancillary files

We study Bayesian optimization in a time-varying environment where the unknown reward function evolves according to a Gaussian process drift model. Existing GP-UCB analyses in this setting typically require the exploration parameter to grow with the horizon to maintain uniform confidence bounds. Using per-round local confidence events, we show that GP-UCB can instead be run with a constant exploration parameter and obtain an expected-regret bound whose coefficient depends on the drift rate. We also derive a sharper time-varying maximum-information-gain bound. For the squared exponential kernel, it yields $\tildeγ_T/T=\widetilde{\mathcal O}(ε^{1/2})$ and expected average regret $\widetilde{\mathcal O}(ε^{1/4})$ in the persistent-drift regime. The same constant-exploration analysis also yields realized-regret guarantees. Simulations support the predicted logarithmic dependence of the bound-suggested exploration parameter on $1/ε$.

0.11

Variance-Aware Non-Stationary Bandits:All-Budget Regret Bounds and Adaptation Costs

cs.LG ·2026-10-19 ·Xiaojin Zhang
theory similarity 0.70
Abstract

Low reward variance reduces estimation cost, but does not eliminate monitoring of arms that may improve while unobserved. We refine the variance--variation tradeoff and characterize how both costs depend on supplied variance and variation budgets in bounded, non-stationary multi-armed bandits. Let $A$ be the number of arms, $T$ the horizon, $B$ a bound on consecutive mean variation excluding the initial vector, and $Q$ a bound on the sum of the largest per-round reward variances. For every admissible pair $Q,B$, the minimax expected dynamic regret is, within a single logarithmic factor, \[ \min\{T,\;A+\sqrt{AQ}+(AQBT)^{1/3} +\sqrt{AT}\min\{B,\sqrt B\}\}. \] The deterministic boundary $Q=0$ is characterized without logarithms. For small positive budgets, a safe calibration phase identifies a common interval containing all future means of surviving arms. Clipping observations to a wider interval reduces the cost of restarting a prior hybrid static-regret algorithm; an original-mean analytical reference controls its residuals without charging the variation of clipped means. Balancing clipping bias and monitoring closes the small-budget noisy regime. Fixed oblivious constructions give the matching lower bound. We also quantify adaptation costs: on a disclosed deterministic one-improvement family, a stationary-regret budget has a matching worst-case change-regret frontier, including a finite improvement pulse. This implies an $Ω((T/A)^{1/4})$ loss when one policy competes with all supplied-budget deterministic oracle rates. The budget-free low-noise scheduling problem remains separate.

0.07

High-Probability Regret Bounds for Feel-Good Thompson Sampling

cs.IT stat.MLcs.LG ·2026-10-14 ·Xuheng Li, Qingyue Zhao, Quanquan Gu
similarity 0.70
Abstract · 22 pages

Feel-good Thompson sampling (FGTS) augments the posterior of vanilla Thompson sampling with an exploration term that favors reward functions with high predicted optimal values. This modification achieves minimax-optimal regret up to logarithmic factors in linear contextual bandits, but existing analyses of its two standard variants establish regret guarantees in expectation. In this paper, we derive the first high-probability regret bounds for both cumulative and current-step FGTS in contextual bandits with general realizable function approximation. Our bounds depend on the corresponding decoupling coefficients and the prior mass near the true reward function. In the $d$-dimensional linear setting, both variants satisfy $\mathrm{Regret}(T)=O\big(d\sqrt T\log(2T)+\sqrt T\log(1/δ)\big)$ with probability at least $1-δ$, where $T$ is the time horizon. This bound matches the dimension and horizon dependence of algorithms based on the upper confidence bounds, up to logarithmic factors. Relative to the expected-regret guarantees, the cost of controlling the regret with high probability is confined to additive terms with at most linear dependence on $\log(1/δ)$. The proof ideas are partially developed by GPT-6 Astra under the authors' guidance.

0.19