Advanced Bandit Algorithms Research

Latest papers

• When May a Bandit Leave Its Anchor? E-Process-Authorized Thompson Sampling under Non-stationarity

  Mayand Gulati, Kerong Wang, WeiChen Au · 5 October 2026

  Stationarity rewards memory, but after a change the same history can mislead. We ask when forgetting should be permitted. E-process-authorized Thompson sampling (e-ATS) gives each arm full-history and discounted Beta states. An anytime-valid e-process first authorizes the discounted state, then a re…

• Bandits via Additive Quantized Representations

  Ami Tavory, Noam Touitou, Tal Sarig, Frank Cheng, Ido Guy · 5 October 2026

  Contextual bandits require balancing nonlinear reward modeling with online efficiency. Tree ensembles and neural methods capture nonlinearities but require periodic retraining and large replay buffers. Linear models update efficiently per observation with O(1) memory, but are fundamentally restricte…

• Parameter-Free Interval-Dynamic Regret under Heavy-Tailed Noise

  Vaneet Aggarwal · 5 October 2026

  We study online convex optimization with one unbiased stochastic subgradient per round and an unknown finite conditional $p$th noise moment, $1<p\le2$. For every fixed interval $I$ of length $n$ and comparator path with $\Lambda_I=1+P_I/D$, one learner achieves \[ E[Regret_I(u)]\le\min(GDn, C[GD\s…

• Nearly Optimal Fixed-Confidence Best-Arm Identification with 1-Bit Feedback

  Khang Luong, Dinh Thai Son, Hoang Ta, Hung The Tran, Tuan Quang Dam · 5 October 2026

  We study fixed-confidence best-arm identification under strict 1-bit feedback constraints. At each round, the learner selects an arm and a query set, and receives only a single bit indicating whether the sampled reward belongs to that set. We consider a distribution-free finite-variance setting with…

• Instance-Dependent Regret for CMDPs with Step-Wise Constraints

  Qian Zuo, Francesco Emanuele Stradi, Leyang Xue, Sattar Vakili · 5 October 2026

  We study online learning in episodic tabular constrained Markov decision processes with step-wise safety constraints. In such a setting, the constraints induce a safe subgraph that shapes the variance of cumulative rewards under feasible policies and, consequently, the difficulty of learning. Exploi…

• Bandits with Multiple Optimal Arms: Minimax Regret and Non-Adaptivit

  Kaixuan Ji, Qiwei Di, Qingyue Zhao, Heyang Zhao, Quanquan Gu · 1 October 2026

  We study multi-armed bandits (MAB) with multiple optimal arms, motivated by the fact that many practical decision making problems admit multiple correct answers. For $K$-armed bandits with $A$ optimal arms, we first provide a sharper analysis of previous sub-sampling algorithms (De Heide et al., 202…

• On the Complexity of Preference-Based Bandits

  Ahmed Ben Yahmed (CREST, ENSAE Paris, FAIRPLAY), Marc Abeille (FAIRPLAY), Cl\'ement Calauz\`enes (FAIRPLAY) · 1 October 2026

  We study preference-based bandits with general reward function classes, where a learner sequentially selects pairs of arms and observes binary preference feedback governed by the Bradley--Terry model. This setting naturally arises in applications such as recommender systems, tournament ranking, and …

• Reserve-Aware Contrast Certificates for Conservative Bandits with Uncertain Baselines

  Qinchuan Cheng · 1 October 2026

  Conservative bandits must improve an incumbent policy without exhausting a prescribed performance budget. When the incumbent is uncertain, separately bounding candidate and baseline rewards can charge twice for shared estimation error. We develop Reserve-C4B around the baseline-relative contrast its…

• Adaptive Random Matrices in Gaussian Bandits: Spectral Universality and Selection-Induced Outliers

  Sudarshan Manikantan (Abstract Math Institute), Abhishek Bhattacharjee (Abstract Math Institute) · 28 September 2026

  Adaptive arm selection changes the distribution of the observations collected by a bandit algorithm, but it need not change their limiting empirical spectrum. We study Gaussian bandit designs in which the dimension and the number of observations grow proportionally. A quantitative coupling theorem c…

• Cost-Aware Best-LLM Identification using Dueling Feedback

  Sarvesh Gharat, Nikhil Karamchandani, Jayakrishnan Nair · 28 September 2026

  Inspired by the problem of identifying the best model from a collection of large language models (LLMs) with heterogeneous querying costs, we formulate and analyse a variant of the multi-armed bandit (MAB) with (i) dueling feedback, where pairwise comparisons between model responses provide robust p…

• Cost-Sensitive Online Window Size Selection for Portfolio Management

  Yi-Chen Liu, Chung-Han Hsieh · 25 September 2026

  This paper investigates cost-sensitive online window size selection for portfolio management under changing market conditions. Specifically, we propose a two-level framework that constructs portfolios using candidate window sizes and dynamically aggregates them through online learning. By treating c…

• Exact Bayes Regret and Asymptotic Optimality in High-Dimensional Gaussian Bandits

  Prakhar Singhvi (Abstract Math Institute), Yi Zou (Abstract Math Institute), Abhishek Bhattacharjee (Abstract Math Institute) · 25 September 2026

  We study Bayesian linear bandits with an isotropic Gaussian parameter, independent Gaussian candidate arms, and Gaussian reward noise when the horizon is proportional to the dimension. The normalized posterior uncertainty has an explicit limit that is uniform over all causal policies. Gaussian poste…

• Canopy: Exploiting Piecewise Smooth Tree Priors for Multi-Fidelity Bandits

  Michael Jerge, Suman Jana · 25 September 2026

  Many LLM inference problems, including model routing, prefix-cache management, prompt trimming, and test-time search, can be viewed as optimization over a tree. This structure arises naturally from autoregressive generation: every prefix defines a node, and its continuations form a subtree below it.…

• Prediction with Expert Advice: Anytime Regret with Many Experts Matches the Fixed-Time Constant

  Yang Cai, Vineet Gupta, Yanchen Jiang, Christopher Liaw, Aranyak Mehta, Grigoris Velegkas, Di Wang · 24 September 2026

  Prediction with expert advice is a fundamental problem in online learning. When the time horizon $T$ is known in advance, the minimax cumulative regret over $n$ experts is asymptotically $\sqrt{\frac{T \ln n}{2}}$. This is achieved by the Multiplicative Weights Update algorithm with a learning rate …

• Efficient Linear Bandits via Cluster-Aware Sketching

  Hantao Yang, Hong Xie, Defu Lian · 24 September 2026

  We study the problem of computational efficiency for linear bandits in high-dimensional settings with a finite arm set. In linear bandits, the increase in the dimension $d$ of the feature vectors leads to growing computational costs of $O(d^2)$ at each round of update. Traditional sketching-based me…

• Efficient Cost-Aware LLM Evaluation via Bayesian Bandit Gittins Indices

  Qian Xie, Yueli He, Nairen Cao · 23 September 2026

  Exhaustively evaluating every candidate LLM configuration on every benchmark item to identify a high-performing one is costly. We formulate configuration selection as a cost-aware Bayesian bandit problem and propose GittinsEval, which draws on the Bayesian-optimal Gittins policy to determine which c…

• Provable Anytime Ensemble Sampling Algorithms in Nonlinear Contextual Bandits

  Jiazheng Sun, Weixin Wang, Pan Xu · 23 September 2026

  We provide a unified algorithmic framework for ensemble sampling in nonlinear contextual bandits and develop corresponding regret bounds for two most common nonlinear contextual bandit settings: Generalized Linear Model Ensemble Sampling (GLM-ES) for generalized linear contextual bandits and Neural …

• Improved Multiplayer Bandit Algorithm for Bernoulli Rewards

  Khang Nguyen, Ricardo Parada, William Chang · 23 September 2026

  We study the multiplayer multi-armed bandit problem with information asymmetry under Bernoulli rewards, for three information structures: asymmetry in actions, in rewards, and in both. Replacing the Hoeffding-style confidence intervals of prior work with Kullback--Leibler (KL) divergence-based bound…

• Optimal No-Regret Learning for Repeated Prophet Inequality

  Kun Wang · 22 September 2026

  We study repeated prophet inequalities under prefix feedback. In each of $T$ rounds, a learner encounters fresh values drawn independently from $n$ boxes with unknown $[0,1]$-supported distributions in a fixed order and must irrevocably accept one, observing only the prefix up to its stopping box. R…

• The Role of Coordinates in Pareto Regret for Adversarial Multi-Objective Bandits

  Changkun Guan, Mengfan Xu · 22 September 2026

  Adversarial multi-objective bandits hold the potential to help us optimize choices (arms) whose reward is a multidimensional vector chosen by an adversary and whose performance is measured by Pareto regret. We define loss as one minus reward and measure the easiness of a coordinate by the smallest c…

• Multi-Armed Bernoulli Bandits via Minimax Single-Arm Stopping

  Huikang Liu, Zhengchao Wang, Daniel Kuhn, Wolfram Wiesemann · 22 September 2026

  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-antic…

• Rollout Total Correlation for Deep Reinforcement Learning

  Bang You, Huaping Liu, Jan Peters, Oleg Arenz · 21 September 2026

  Learning task-relevant representations is crucial for reinforcement learning. Recent approaches aim to learn such representations by improving the temporal consistency in the observed transitions. However, they only consider individual transitions and can fail to achieve long-term consistency. Inste…

• From Switching to Dynamic Regret: A Simple Reduction via Unbiased Random Sequences

  Yibo Wang, Wenhao Yang, Sifan Yang, Yuanyu Wan, Lijun Zhang · 21 September 2026

  In non-stationary online learning, dynamic regret has attracted increasing attention as a measure of how well an online learner performs against a time-varying comparator sequence. Despite considerable advances, attaining optimal bounds for strongly convex and exp-concave losses often involves intri…

• Odds-Ratio Thompson Sampling: A Specification and Design Guide for Contrast-Based Multi-Armed Bandits

  Sulgi Kim · 18 September 2026

  Batched multi-armed bandits update on a service's own schedule, and the usual implementation carries each arm's absolute reward rate from one update to the next. When the shared level moves between batches, that memory goes stale even though the comparisons between arms may not have. Odds-Ratio Thom…

• Adapting to Decision-Relevant Non-Stationarity in Decentralized Heterogeneous Bandits

  Zhaojun Peng · 16 September 2026

  Decentralized bandit systems often contain heterogeneous agents: rewards can change at individual agents even when the best action for the network stays the same. These local changes may cancel when rewards are averaged across agents, so the number of local changes $\Stloc$ can be much larger than t…