Bandit Learning

Follow this topic Ask about this topic

Latest papers

52 papers9 papers in the last four weeks, against 2 the four weeks before. 0.1% of all new papers.

Oct 14, 2026

When Does Momentum Help in Reinforcement Learning with Verifiable Rewards?

Momentum is a classical tool for accelerating convex optimization and a standard component of modern large language model training. Yet recent empirical work has questioned the usefulness of first-moment momentum in reinforcement learning with verifiable rewards (RLVR). We study this question through a bandit formulation of RLVR with bias-corrected exponential moving average (EMA) momentum, where the EMA coefficient

β

controls how quickly the weights on past gradients decay. When policy gradients are evaluated exactly, we prove that increasing

β

within a range that prevents overshoot strictly accelerates optimization. When gradients are estimated from sampled responses, a positive expected gain can be obscured by sampling fluctuations. We show that as the learning rate

η

decreases, the expected gain with fixed

β

vanishes faster than these fluctuations, whereas increasing

β

to keep

η/(1-β)

within the safe regime preserves a nonvanishing gain that eventually dominates them. Bandit simulations quantitatively validate these predictions. RLVR experiments on Qwen3-4B-Base using SGD with EMA and AdamW support our principle of choosing larger coefficients in practical LLM post-training. On Qwen2.5-32B with AdamW, simply increasing

β_1

improves mean validation accuracy by nearly

2

percentage points over the conventional choice, demonstrating the principle's effectiveness at a larger model scale.

Kaifei Wang, Zikang Shan, Liwei Wang +2

Peking University · Shanghai Jiao Tong University, SIMIS, and Stanford University · Shanghai Jiao Tong University

Bandit Learning Momentum Methods Reinforcement Learning with Verifiable Rewards RL Post-Training

Oct 13, 2026

Reliable Scale-Free Bandits via Empirical Likelihood

We study stochastic bandits without knowledge of reward scales or tail parameters. Almost-sure regret guarantees describe eventual learning but do not quantify expected performance or the risk of large regret in a finite run. We introduce

\texttt{EL-F}

, an anytime empirical-likelihood (EL) extension of the

g

-Forcing policy of Cowan and Katehakis (2020), and characterize its performance at three levels. First, for integrable rewards and non-decreasing, diverging exploration schedules

g

with vanishing increments,

\texttt{EL-F}

preserves the

g

-Forcing asymptotics for pseudo-regret

R(T)

:

R(T)/g(T)\to\sum_{i:Δ_i>0}Δ_i

almost surely as

T\to\infty

, where

Δ_i

is the suboptimality gap of arm

i

. Second, on every sub-exponential instance, for non-decreasing

g(t)=ω(\log t)

satisfying a mild feasibility condition, expected pseudo-regret is at most

g(T)\sum_{i:Δ_i>0}Δ_i+C_{\underline{P}}

, where

C_{\underline{P}}

is an instance-dependent constant independent of

T

. Moreover, we also establish finite-time tail bounds with super-polynomial decay in regret beyond the forced-exploration budget. For slowly varying

g

, we determine the exact exponent of linear regret deviations on two-armed Gaussian instances with common variance and establish a matching lower bound among policies satisfying the same expected-regret budget on every such Gaussian instance. These quantitative guarantees also cover the greedy variant obtained at zero EL radius. A fixed positive radius introduces local optimism while preserving the leading asymptotic regret. We establish coupled pathwise dominance over the greedy variant in two-armed bandits with a deterministic suboptimal arm. Experiments demonstrate reductions in prolonged suboptimal allocation compared with

g

-Forcing on challenging instances.

Pratham Gupta, Alhad Sethi, Shubhada Agrawal

Indian Institute of Science

Multi-Armed Bandits Bandit Learning

Oct 9, 2026

Decentralized Bandit Learning of Markov Perfect Equilibria

We study decentralized bandit learning in discounted infinite-horizon, general-sum Markov games with continuous actions. Agents observe the public state, but only their own realized rewards, and use simultaneous perturbation stochastic approximation to update their actions. Under strong monotonicity of the negative running-reward gradients and sufficiently small time steps, we prove that the fully decentralized procedure converges almost surely to the unique stationary Markov perfect equilibrium. We obtain an

O(n^{-1/2})

convergence rate and present a natural extension to episodic finite-horizon learning.

Felix Höfer, H. Mete Soner

Booth School of Business, The University of Chicago, Chicago, IL, 60637, USA · Department of Operations Research and Financial Engineering, Princeton University, Princeton, NJ, 08540, USA

Bandit Learning Nash Equilibrium Multi-Armed Bandits

Oct 7, 2026

m-Set Adversarial Bandits with Winner Feedback

We show upper and lower bounds on the regret of

m

-set adversarial bandits for different utilities (winner reward or sum of rewards) and feedback models (winner index, winner reward, sum of rewards, and their combinations). By comparing to standard bounds for combinatorial and MNL bandits, our results reveal how subtle changes in the setting can have a dramatic impact on the learning rates. Our main technical contributions are the information-theoretic lower bounds on the regret. Experiments on synthetic data confirm our theoretical analyses.

Nicolò Cesa-Bianchi, Matteo Papini

Universit`a degli Studi di Milano · Politecnico di Milano

Multi-Armed Bandits Bandit Learning Adversarial Bandits Combinatorial Multi-Armed Bandits Minimax Regret

Oct 7, 2026

Beyond Reward Suppression: Near-Optimal Offline Attacks on Warm-Start Bandits with Bounded Rewards

Adversarial attacks on bandits aim to mislead a learner toward a target arm while keeping the attack cost small. Existing attacks typically achieve this by suppressing non-target arms. In practice, however, manipulation such as fake reviews often directly promotes the target item. We study this gap through bounded offline attacks on warm-start bandits, where an attacker can inject only valid action-reward pairs into the warm-start history before deployment. We show that target promotion is not merely a heuristic: when the target arm lies near the lower reward boundary, any order-optimal-cost attack against UCB that makes it selected in nearly all online rounds must allocate a nonvanishing fraction of its cost to the target arm. We then design an attack that achieves the optimal sublinear cost and characterize its allocation between target promotion and non-target suppression. We further extend the attack to Thompson Sampling,

ε

-greedy, and a broader class of bandit algorithms. Experiments on real-world and synthetic data validate the effectiveness of our attacks.

Qirun Zeng, Manhin Poon, Xiangxiang Dai +2

City University of Hong Kong, Hong Kong SAR, China · The Chinese University of Hong Kong, Hong Kong SAR, China · Nanyang Technological University, Singapore

Adversarial Attacks Multi-Armed Bandits Bandit Learning Data Poisoning Attacks

Oct 6, 2026

The Deceptive Bandit Problem: Exploratory Coupling and the Fragility of Multi-Agent Learning

Randomized exploration is central to bandit learning, multi-agent reinforcement learning, and zeroth-order policy search, yet its independence and privacy are usually only treated as technical assumptions. We show that these properties are critical for security purposes and demonstrate how an adversarial agent can exploit privileged information on another agent's exploration. We analyze a deceiver-victim pair in the minimal two-player strongly monotone setting, where a deceptive player obtains leaked signals that are merely correlated with the victim's exploration. We show that, by coupling their own exploratory action with this information, the deceptive player injects an externality that steers the learning dynamics to a new steady state, called the deceptive Nash equilibrium (DNE). We prove that the deceptive bandit learning (DBL) dynamics converge to an arbitrarily small neighborhood of the DNE while retaining optimal convergence rates. Interestingly, our analysis attains these optimal rates while relaxing second-order smoothness conditions from standard bandit optimization literature. We characterize conditions under which deception strictly shifts the steady state and its effect on the deceiver's cost, illustrating the results in a resource-allocation game.

Michael Tang, Mahmoud Abdelgalil, Jorge I. Poveda

Electrical and Computer Engineering Department at the University of California, San Diego, La Jolla, CA, USA · Mechanical and Aerospace Engineering Department at the University at Buffalo, State University of New York, Buffalo, NY, USA

Multi-Agent Bandits Bandit Learning Multi-Agent Reinforcement Learning

Oct 6, 2026

On the Computational Tractability of Robust Bandits

Learning when the environment does not belong to the learner's hypothesis class is typically handled using agnostic learning guarantees. However, for anything beyond supervised learning, agnostic guarantees are difficult to come by. Recently, imprecise bandits (Kosoy, 2025) (later renamed to robust bandits in Appel and Kosoy, 2025) were introduced as another approach to unrealizable learning in the bandits setting and a

Θ(\sqrt{T})

regret learner was shown for a large class. However, no computational guarantees were provided. In this paper we identify a special case that admits a polynomial-time learner with

\tilde{O}(\sqrt{T})

regret. We also show that several small generalizations of this special case are NP-hard thus indicating that the special case is at the boundary of what is tractable. It has been recently suggested (Kosoy, 2018) that computationally efficient learners for unrealizable learning problems are crucial for solving the AI alignment problem. This work is a small step in that direction.

Vanessa Kosoy, Vinayak Pathak

Faculty of Mathematics, Technion, Haifa, Israel · CORAL† Computational Rational Agents Laboratory, Delaware, USA.

Multi-Armed Bandits Robust Multi-Armed Bandits Bandit Learning

Oct 5, 2026

Fast Last-Iterate Convergence in Zero-Sum Markov Games with Bandit Feedback

We study last-iterate convergence in unknown two-player zero-sum discounted Markov games with bandit feedback. The players learn independently along a single trajectory without observing each other's actions. We develop Adaptive Regularized TD Learning (ARTD), which achieves a

\widetilde{\mathcal{O}}(t^{-1/4})

duality gap bound for the current policies under a uniform hitting time assumption, with high probability simultaneously over all rounds and starting states. This improves the

\widetilde{\mathcal{O}}(t^{-1/(9+ν)})

rate of Cai et al. (2023), for any fixed

ν>0

, under the same feedback model and hitting time assumption. Our algorithm requires no knowledge of the hitting time bound, the time horizon, or the confidence level. To stabilize policy learning as value estimates change, we separate fast temporal difference averaging from bounded value updates. We adapt log-barrier regularization to the progress of value estimation, controlling both policy and value errors throughout learning. Together, these mechanisms enable fast convergence of the policies actually played, even when the players learn independently from bandit feedback.

Yuheng Zhang

University of Illinois Urbana-Champaign

Last-Iterate Convergence Reinforcement Learning Zero-Sum Games Temporal-Difference Learning Bandit Learning

Oct 5, 2026

Bellman-Centric Learning: Near-Optimal Regret for Linear Bandits with Memory

We study linear bandits with memory, where past actions induce endogenous nonstationarity through an arbitrary known, bounded matrix-valued memory map. To trade off exploration and exploitation while accounting for the memory dynamics, we develop RSM-LinUCB, a Bellman-centric algorithm that learns as in linear bandits and plans as in reinforcement learning. This design admits a novel regret decomposition which separates the memory-induced error from the cumulative reward estimation error along the learner's trajectory. We prove a high-probability regret bound of

\widetilde O\big(dRS(M+1)+σd\sqrt T\big)

, where

T

is the learning horizon,

d

is the parameter dimension,

M

is the memory length,

R

and

S

bound the memory-map operator norm and reward-parameter norm, respectively, and

σ

is the sub-Gaussian noise scale. Our results reveal that the multiplicative memory-horizon coupling in prior bounds is not intrinsic: memory only contributes an additive cost, up to logarithmic factors. We also prove a matching minimax lower bound, establishing near-optimality. We further extend the algorithm to generalized linear rewards, preserving this separation with near-optimal memory and leading statistical dependence. Our algorithms outperform the baselines in numerical experiments on synthetic instances and semi-synthetic KV- and semantic-cache tasks.

Jingyuan Liu, Huiwen Jia

Department of Industrial Engineering and Operations Research, University of California, Berkeley

Multi-Armed Bandits Non-Stationary Bandits Generalized Linear Bandits Bandit Learning

Sep 1, 2026

Bandits in Prod: Hyperparameter Optimization at Inference Time

Many production systems can assess a configuration only by using it on live requests and observing noisy feedback. Modern agentic systems are a prominent example, with inference-time choices such as model selection, retrieval depth, prompting strategy, and decoding temperature, yet often with no representative validation data. We formalize this setting as Online Hyperparameter Optimization (OHPO) and cast it as an infinitely many-armed bandit over mixed and conditional search spaces. We introduce IMABO, a general framework that combines any bandit policy for choosing among already sampled configurations with any oracle for proposing new ones. We instantiate it with IMOSS, a restart-free anytime policy whose active set grows as

t^β

, and prove an expected cumulative quantile-regret bound of

O(p_ρ^{-1/β} + T^{(1+β)/2})

, where

β\in(0,1)

controls active-set growth and

p_ρ

lower-bounds the probability that a proposed configuration falls in the top-

ρ

fraction of the search space. We combine IMOSS with three practical oracles: a Tree-structured Parzen Estimator, an incumbent-mutation oracle driven by a per-coordinate bandit, and a pretrained tabular foundation model, all three improving over the uniform random oracle baseline. IMABO outperforms all baselines in terms of regret across diverse OHPO settings, from tuning classical machine-learning models to configuring LLM-based agents. Our implementation is available at https://github.com/Tiime-Software/IMABO.

Louis Abraham, Tuan-Anh Nguyen, Nicolas Devatine

Tiime Paris, France

Multi-Armed Bandits Inference-Time Optimization Hyperparameter Optimization Bandit Learning

Aug 25, 2026

Bandit Submodular Maximization under Matroid Constraints: Learning Compressed Exchange Policy

We study adversarial bandit maximization of monotone submodular functions under a matroid constraint. For a rank-

k

matroid on

n

elements, we give a randomized oracle-polynomial algorithm that makes one feasible value query per round and has expected

(1-1/e)

-regret

\widetilde O(n^{1/3}k^{2/3}T^{2/3})

. This is the first sublinear-regret algorithm for adversarial bandit submodular maximization under general matroid constraints. Technically, we view the problem as learning an exchange policy for the Poisson base walk. This connects the problem to contextual bandits and gives an information-theoretic sublinear-regret guarantee, but directly learning the exponentially many policies requires exponential time and space. We therefore introduce balanced fractional exchanges, which compress the policy mixture into a single fractional base while retaining the exchange information needed by the Poisson analysis. This leads to an polynomial time algorithm with the same regret guarantee.

Zongqi Wan, Zhijie Zhang

Great Bay University · Fuzhou University

Submodular Optimization Bandit Learning Adversarial Bandits

Aug 2, 2026

Sharp Characterization of Bias in Post-Bandit Inference

Bandit algorithms generate data for downstream inference, but adaptive sampling biases post-bandit sample means. We analyze this bias for stable index algorithms, including UCB1 and its generalizations, and derive sharp leading-order expressions for the sample-mean bias and expected

Z

-statistic, in bandit experiments of fixed horizon

T

. Our characterization reveals the algorithmic origin of bias through a key index-function-dependent quantity, which we term effective exploration rate. For example, under UCB1, the effective exploration rate is of order

\sqrt{\log T}

, and the standardized bias of any arm (that is not uniquely optimal) decays at the extremely slow rate

1/\sqrt{\log T}

. We also show how the choice of the index function affects both regret and bias, which reveals a regret-bias trade-off: more exploratory algorithm reduces bias but increases regret. We further show how bias most severely distorts confidence intervals and hypothesis tests when the tested arm is one of the tied-optimal arms. Our sharp characterization for bias uses a novel empirical fluid approximation of the algorithm's sampling dynamics, which may be of independent interest.

Lisu Wang, Yilun Chen, Jiaqi Lu

School of Data Science, The Chinese University of Hong Kong, Shenzhen · School of Management and Economics, The Chinese University of Hong Kong, Shenzhen

Multi-Armed Bandits Algorithmic Bias UCB Algorithms Bandit Learning

Jul 14, 2026

Thompson Sampling Is 2-Competitive for Mistakes

We consider Bayesian bandit models and prove that Thompson sampling makes at most twice the expected number of mistakes (selections of a suboptimal arm) as any other policy. Our analysis applies as long as the latent arm processes are independent and each arm evolves only when played. For stochastic bandits with best arm defined via mean reward, this confirms a conjecture of Guha and Munagala from 2014, where the factor

2

is already best possible. The result holds under any nonincreasing sequence of round weights, including fixed horizon and geometric discounting.

Mark Sellke, Gregory Valiant

Thompson Sampling Multi-Armed Bandits Bandit Learning

Jul 12, 2026

Learning from Local Walks on Dynamic Graphs with Bandit Feedback

We study stochastic multi-armed bandits on dynamic graphs, where arms correspond to the vertices of a network with time-varying edges. In this setting, the learner is restricted to local movement, selecting only its current node or an immediate neighbor at each round. This constraint decouples best-arm identification from exploitation: even after the optimal arm is identified, the learner may remain unable to reach it through the evolving topology. We identify a process-agnostic structural condition, based on sliding-window mixing, that ensures the graph's intrinsic walk remains stable for both exploration and navigation. Under this regime, we analyze a family of local explore-then-commit algorithms and establish sublinear expected regret. Our framework includes a reward-aware strategy, for which we prove a worst-case safety theorem and a separate performance gain theorem.

Sourav Chakraborty, Amit Kiran Rege, Claire Monteleoni +1

Department of Computer Science, University of Colorado, Boulder, CO 80309, USA · INRIA, Paris, France

Multi-Armed Bandits Graph Bandits Exploration-Exploitation Tradeoff Bandit Learning

Jul 1, 2026

Class-Grouped Normalized Momentum and Faster Hyperparameter Exploration to Tackle Class Imbalance in Federated Learning

Class imbalance poses a critical challenge in federated learning (FL), where underrepresented classes suffer from poor predictive performance yet cannot be addressed by standard centralized techniques due to privacy and heterogeneity constraints. We propose FedCGNM (Federated Class-Grouped Normalized Momentum), a client-side optimizer in FL that partitions classes into a small number of groups based on minimum within-group variance, maintains a momentum per group, normalizes each group momentum to unit length, and uses the summation of the normalized group momentums as an update direction. This design both equalizes gradient magnitude across majority and minority groups and mitigates the noise inherent in rare-class gradients. We further provide a theoretical convergence analysis explicitly accounting for time-varying resampling-rates. Additionally, to efficiently optimize these rates in small-client regimes, we introduce FedHOO, an X-armed-bandit (XAB) based algorithm that exploits federated parallelism that evaluates many combinations of two candidate rates per client at linear cost. Empirical evaluation on four public long-tailed benchmarks and a proprietary chip-defect dataset demonstrates that FedCGNM consistently outperforms baselines, with FedHOO yielding further gains in small-scale federations.

Haemin Park, Diego Klabjan, Martin W. Braun +2

Department of Industrial Engineering & Management Sciences, Northwestern University, Evanston, IL, USA · Intel Corporation, Chandler, AZ, USA

Class-Imbalanced Learning Deep Learning Optimization Bandit Learning Hyperparameter Optimization Federated Learning

Jun 8, 2026

Bandits for Efficient Experimentation: Adapting to Control Group, Preferences, and Context Drifts

We consider a variant of the linear contextual stochastic multi-armed bandits, where the learner must provide recommendations to a group of users, each having its personalized preference vector, and in the presence of context distributions that are drifting over time. Under practitioner-friendly assumptions, we reduce this setting to linear bandit with stationary mean but heteroskedastic and non-stationary noise. We further study the case when the learner must ensure the mean reward of each decision must exceed that of a baseline strategy

\boldsymbolπ_0

at each decision step. We introduce Dri-MED, an algorithm inspired from the linear version of the MED strategy, and carefully adapted to handle the non-stationary heteroskedastic noise. We show that the instance-dependent regret scales as

\tilde{\mathcal O}\left(\fracκ{\tildeΔ}d^2(\log(T)\right)

, where

\tildeΔ

is the constraint-aware sub-optimality gap subject to policy

π_0

, with variance-aware multiplicative term

κ

that we carefully handle using heteroskedastic regression. We further show Dri-MED enjoys

\tilde{\mathcal{O}}(d)

expected constraint violations. Our numerical results suggest that Dri-MED significantly outperforms conservative baselines that ignores the drift and preference structure.

Udvas Das, Waris Radji, Debabrota Basu +1

Univ. Lille, Inria, CNRS, Centrale Lille, UMR 9189 – CRIStAL F-59000 Lille, France

Multi-Armed Bandits Non-Stationary Bandits Contextual Bandits Linear Contextual Bandits Bandit Learning

Jun 8, 2026

Online Learning with Recency: Algorithms for Sliding-window Streaming Multi-armed Bandits

Motivated by the recency effect in online learning, we study algorithms for single-pass sliding-window streaming multi-armed bandits (MABs) in this paper. In this setting, we are given

n

arms with unknown sub-Gaussian reward distributions and a parameter

W

. The arms arrive in a single-pass stream, and only the most recent

W

arms are considered valid. The algorithm is required to perform pure exploration and regret minimization with limited memory, defined as the number of stored arms. The model is a natural extension of the streaming multi-armed bandits model (without the sliding window) that has been extensively studied in recent years. We provide a comprehensive analysis of both the pure exploration and regret minimization problems with the model. For pure exploration, we prove that finding the best arm is hard with sublinear memory while finding an approximate best arm admits an efficient algorithm. For regret minimization, we explore a new notion of regret and give sharp memory-regret trade-offs for any single-pass algorithm. We complement our theoretical results with experiments, demonstrating the trade-offs between sample, regret, and memory.

Vladimir Braverman, Chen Wang, Liudeng Wang +1

Johns Hopkins University · Rensselaer Polytechnic Institute · Texas A&M University

Multi-Armed Bandits Best-Arm Identification Streaming Algorithms Bandit Learning

Jun 3, 2026

Offline-to-Online Learning in Linear Bandits

We study online learning with an additional offline dataset in the stochastic linear bandit setting. Although this problem arises frequently in practice, the offline-to-online tradeoff remains poorly understood in structured environments. We propose a linear bandit algorithm that balances this tradeoff: it relies on offline data during early rounds, and increasingly favors exploration as the horizon grows. We establish regret bounds showing that our method is simultaneously competitive with both purely online and purely offline solutions. In particular, it achieves sublinear regret relative to the optimal action in the number of online interactions, while its regret relative to an offline reference decreases as the number of offline samples grows. Empirical results further demonstrate its effectiveness across various problem parameters.

Kushagra Chandak, Toshinori Kitamura, Xiaoqi Tan

Department of Computing Science, University of Alberta, Canada

Multi-Armed Bandits Contextual Bandits Bandit Learning

Jun 1, 2026

Tree-Guided Identify-Then-Exploit: A Unified Framework of Best Arm Identification and Regret Minimization for Dueling Bandits

We study

N

-armed stochastic dueling bandits under the Condorcet-winner assumption, where three widely adopted objectives are considered: best-arm identification (BAI), weak regret, and strong regret. We propose Tree-Guided Identify-Then-Exploit (TG-ITE), the first unified framework to tackle all these objectives to our knowledge. Without requiring stronger assumptions, we propose a shared tree-guided identification approach to find a high-confidence incumbent within

O(N)

comparisons. We further propose varied exploitation strategies to utilize this warm-start stage to optimize the specific objectives at hand. This methodology enables our approach to (1) achieve

O(N)

sample complexity in BAI without commonly adopted stronger assumptions; (2) build the first winner-stays-style algorithm to achieve

O(N)

weak regret; (3) enjoy the same

O(N \log T)

guarantee as specialized strong-regret approaches; (4) realize the joint optimization of BAI and weak regret with

O(N)

guarantees for both, eliminating the sub-optimal gap of

O(\log N)

in the existing approach. Our results provide evidence that the trade-off between BAI and regret minimization is relatively benign in dueling bandits.

Pu Wang, Yao-Xiang Ding

State Key Lab of CAD&CG, Zhejiang University

Multi-Armed Bandits Best-Arm Identification Regret Minimization Dueling Bandits Bandit Learning

May 31, 2026

Fairness in two-player zero-sum games with bandit feedback

We study two-player zero-sum games (TPZSGs) with bandit feedback under fairness constraints requiring every action to be played with probability at least

α/m

. Existing instance-dependent results target

\textit{pure}

Nash equilibria, while fairness generically produces

\textit{mixed}

equilibria, a harder learning target. Our key technical tool is a reparametrization: every fair strategy decomposes as

p = (α/m)\mathbf{1} + (1-α)\widetilde{p}

with

\widetilde{p} \in Δ_m

, and substituting into the payoff form yields

p^{\top}Aq = \widetilde{p}^{\top}\widetilde{A} q

for a fair payoff matrix

\widetilde{A} := (1-α)A + α\mathbf{1} c^{\top}

, where

c_j = \tfrac{1}{m}\sum_i A(i,j)

is the column-mean vector. The fair game on

A

is then equivalent to a standard zero-sum game on

\widetilde{A}

, so equilibrium existence, KKT structure, and LP basis stability reduce to classical results applied to

\widetilde{A}

. We derive the fair minimax value, fair Nash equilibrium, fair regret, and a clean dual representation showing the price of fairness is at most

α(1-1/m)

and vanishes whenever the unconstrained equilibrium already has full support. Our main result is an

\widetilde{O}(T^{2/3})

regret bound for an Explore-Then-Commit algorithm,

\texttt{Fair-ETC-TPZSG}

, applicable to general mixed fair equilibria, together with a discussion of why naive action elimination does not readily improve it. When the fair equilibrium has a single dominant action, equivalently when

\widetilde{p}^{\star}

is a vertex of

Δ_m

, the bound sharpens to instance-dependent

\widetilde{O}(1/\widetildeΔ(α)^{2})

, where

\widetildeΔ(α)

is the LP-margin gap.

S Akash, Pratik Gajane

LatentForce.ai Bengaluru, India · Laboratoire d’Informatique Fondamentale d’Orléans University of Orléans, France

Nash Equilibrium Zero-Sum Games Algorithmic Fairness Bandit Learning Adversarial Bandits Nash Equilibrium Computation

May 29, 2026

Batched Stochastic Linear Bandits with 1-Bit Communication Constraints

We study stochastic linear bandits under a natural combination of batching and communication constraints: the time horizon is partitioned into batches of equal size

B

, and during each batch the learner sends

B

requested arm pulls to an agent, who then observes the corresponding

B

rewards and responds with a single bit of feedback to the learner. For each batch, the learner specifies the 1-bit quantization rule the agent uses, which may depend on all previously received bits but not on any past rewards directly. This setting addresses a significant yet unexplored ``middle ground'' between previous models having per-round quantization only or total bit budgets only. We establish a minimax lower bound showing that

Ω(B\min\{d,\log\lvert \mathcal{A} \rvert\})

regret is unavoidable due to the 1-bit communication bottleneck, even in the absence of noise. Combined with standard statistical limits, this yields a general lower bound of

\widetildeΩ(B\min\{d,\log\lvert \mathcal{A} \rvert\} + \sqrt{dT \min\{d,\log\lvert \mathcal{A} \rvert\}})

. We develop two phased-elimination algorithms based on

G

-optimal designs and 1-bit mean estimation. The first achieves

\widetilde{O}(dB + d\sqrt{T})

regret, matching the lower bound up to logarithmic factors when

\lvert \mathcal{A} \rvert = \exp(Ω(d))

, and the second incorporates a safe-arm identification and warm-start procedure to obtain

\widetilde{O}(B\log\lvert \mathcal{A} \rvert + d^{3/2}\sqrt{B} + \sqrt{dT\log\lvert \mathcal{A} \rvert})

regret, which is near-optimal in broad scaling regimes of

(\lvert \mathcal{A} \rvert, B, d, T)

. Together, our results demonstrate that a single bit of feedback per batch suffices to nearly match the minimax regret of unconstrained linear bandits in broad scaling regimes, even for batch sizes as large as

Θ(\sqrt{T})

.

Ivan Lau, Daniel McMorrow, Kevin Jamieson +1

National University of Singapore · University of Washington

Multi-Armed Bandits Minimax Regret Communication Complexity Low-Bit Quantization Bandit Learning

May 25, 2026

Online Learning on Hidden-Convex Losses via Algorithmic Equivalence: Optimal Regret, Geometric Barrier, and Bandit Feedback

We study adversarial online learning with hidden-convex losses, i.e., nonconvex losses that become convex after a nonlinear reparameterization. Ghai, Lu and Hazan (2022) proved that, under geometric and smoothness assumptions, online gradient descent (OGD) on such nonconvex losses approximately simulates online mirror descent (OMD) on the underlying convex losses with a suitable regularizer, yielding

\mathcal{O}(T^{2/3})

regret. They left open whether the optimal

Θ(\sqrt{T})

regret from online convex optimization can be recovered in this hidden-convex setting. We answer this question affirmatively. More specifically, via a sharper discrete-time algorithmic equivalence argument, we prove that OGD achieves

\mathcal{O}(\sqrt{T})

regret under the same assumptions, matching the optimal worst-case rate for adversarial online convex optimization. We also address another open question of Ghai, Lu and Hazan (2022) by clarifying the geometry required for this algorithmic equivalence. We replace the diagonal-Jacobian sufficient condition with a necessary-and-sufficient Hessian compatibility condition, thereby expanding the class of admissible reparameterizations. We complement our tight regret bound with a lower bound showing that the Hessian compatibility assumption is essential for OGD; when it fails, we construct a smooth reparameterization and an adversarial sequence of hidden-convex losses for which OGD suffers

Ω(T)

regret. Finally, we extend our analysis to one-point bandit feedback and prove a

\mathcal{O}(T^{3/4})

expected regret bound for bandit OGD with spherical smoothing, matching its classical rate on convex losses.

Anas Barakat, Andreas Kontogiannis, Vasilis Pollatos +2

Singapore University of Technology and Design · National Technical University of Athens · Archimedes, Athena Research Center, Greece +3

Online Convex Optimization Gradient Descent Bandit Learning Online Learning

May 22, 2026

An Interpretable CF-RL-TOPSIS Fusion Model for Skills-Aware Talent Recommendation

Effective skills-aware talent recommendation must balance behavioral transition patterns, trajectory-sensitive adaptation, and inspectable occupation-level criteria. Evidence from public benchmarks on how these signals interact, however, remains limited. This study proposes CF-RL-TOPSIS, an interpretable late-fusion model that integrates a transition-aware collaborative branch, a compact reinforcement-style occupation-family bandit, and an entropy-weighted TOPSIS branch constructed from six semantic proxies; the validation-selected fusion coefficients remain auditable. The model is evaluated on two frozen public ICT talent-history benchmarks, JobHop and Karrierewege, using repeated chronological top-5 ranking and paired Wilcoxon tests. On JobHop the full hybrid attains NDCG@5 = 0.3040 +/- 0.0073 and significantly surpasses repeat-last, item Markov, transition-aware collaborative filtering, the CF+TOPSIS hybrid, GRU4Rec, and SASRec (p <= 0.0039 across planned comparisons). On Karrierewege the hybrid remains competitive but does not significantly exceed the strongest Markov baseline, revealing a persistence-dominated setting in which the bandit branch appropriately shrinks to near-zero weight. Proxy-sensitivity, family-level deep Q-network, and runtime checks support this interpretation, and a worked user-level case shows how branch scores, criterion weights, and rank shifts can be inspected for an individual recommendation. The contribution is not a benchmark-agnostic superiority claim, but a reproducible account of the conditions under which transparent late fusion adds value beyond simple continuation heuristics. In semantically rich, non-saturating talent-history regimes the three branches reinforce one another; in persistence-dominated regimes the same architecture remains competitive through its collaborative backbone, with the adaptive branch correctly inactive.

Özkan Canay

aSakarya University, Department of Information Systems and Technologies, Faculty of Computer and Information Sciences, Sakarya, Türkiye

Sequential Recommendation Multi-Criteria Decision Analysis Bandit Learning Recommender Systems Collaborative Filtering

May 22, 2026

Prudent-Banker: No Extra Fees for Baseline Safety in Adversarial Bandits With and Without Delays

We study adversarial multi-armed bandits with and without delayed feedback under a safety-aware goal: achieving minimax-optimal worst-case regret while keeping nearly constant regret relative to a designated "safe" baseline policy. Existing approaches can balance this trade-off with immediate feedback for smooth comparators, but arbitrary delays can mistime transitions between conservatism and exploration, endangering the safety guarantee. To bridge this gap, we propose Prudent-Banker, a novel algorithm that combines a delay-adapted variant of Online Mirror Descent with a modified phased-aggression mechanism. Its key technical contribution is a delay-calibrated restart threshold that rigorously accounts for the worst-case distortion induced by unobserved feedback and reliably detects comparator suboptimality. We also establish new lower bounds for safety-constrained adversarial delayed bandits, showing that the regret guarantees of Prudent-Banker are unimprovable, up to logarithmic factors, under the baseline-safety requirement. To the best of our knowledge, Prudent-Banker is the first algorithm to achieve the optimal safety--robustness trade-off: pseudo-regret

\widetilde{O}(\sqrt{T}+\sqrt{D})

together with

\widetilde{O}(1)

regret against the safe comparator, both with and without delays. Experiments across diverse delay distributions show that, unlike standard delay-robust baselines, Prudent-Banker effectively balances safety and learning.

Ting Hu, Luanda Cai, Emmanouil-Vasileios Vlatakis-Gkaragkounis

Department of Finance University of Wisconsin–Madison · Department of Computer Sciences University of Wisconsin–Madison

Multi-Armed Bandits Minimax Regret Online Mirror Descent Bandits with Delayed Feedback Adversarial Bandits Bandit Learning

May 17, 2026

Delay-Adaptive Speculation Control for Low-Latency Edge-Cloud LLM Inference

Speculative decoding accelerates large language model (LLM) inference by using a lightweight draft model to propose tokens and a larger target model to verify them in parallel. In distributed edge-cloud inference, however, draft length must be controlled online: longer drafts amortize communication delay but reduce token acceptance, whereas shorter drafts preserve acceptance but trigger more communication rounds. We formulate this tradeoff as a ratio-type optimal stopping problem and prove that the optimal draft length is a finite delay-monotone threshold. The analysis identifies a critical delay below which single-token speculation is optimal and shows that the optimal length grows only logarithmically with communication delay. For time-varying networks, we extend the model to Markov-modulated channels and establish, under a bounded horizon and monotone stopping-region conditions, a state-dependent threshold policy. For unknown environments, we propose UCB-SpecStop, an online control algorithm with gap-free and gap-dependent expected regret bounds of

O(L_{\max}\sqrt{K_{\max}T\log(K_{\max}T)})

and

O(\sum_{k:Δ_k>0}L_{\max}^2\log(K_{\max}T)/Δ_k)

. We implement the method on a real edge-cloud testbed with a Jetson Orin Nano Super edge node and an RTX~~3090 Ti cloud node, using Qwen and Llama draft--target pairs. Experiments validate the predicted phase transition, with transition points near 83~~ms and 111~ms. Qwen matches the geometric prediction, while Llama requires empirical-prefix calibration due to heavy-head acceptance. Across the tested delay grid, UCB-SpecStop reduces per-token latency over SpecDec++ by up to 22.4%, approaches an offline oracle within 0.2--2.4% in communication-dominated regimes, improves over naive UCB by up to 7.5%, removes the 14.0--18.7% gap caused by static tuning under delay drift, and gains 3.0--6.8% with contextual channel-state information.

Kangkang Sun, Jianhua Li, Xiuzhen Chen +2

Shanghai Key Laboratory of Integrated Administration Technologies for Information Security, School of Computer Science, Shanghai Jiao Tong University, Shanghai 200240, China · School of Science and Engineering, The Chinese University of Hong Kong, Shenzhen, Guangdong, China

Sequential Decision Making Optimal Stopping Speculative Decoding Bandit Learning LLM Inference Acceleration Edge-Cloud Computing

May 13, 2026

Delightful Exploration

Most exploration algorithms search broadly until uncertainty is resolved. When the action space is too large to resolve within budget, practitioners default to

\varepsilon

-greedy, which bounds disruption but spends its override blindly. We introduce Delight-gated exploration (DE), a host--override rule that spends exploratory actions only when their prospective delight (expected improvement times surprisal) exceeds a gate price. This practical heuristic recovers a classical result: Pandora's reservation-value rule for costly search, with surprisal setting the effective inspection cost. Resolved arms exit the gate, fresh arms shut off above a prior-determined threshold, and selected linear-bandit overrides consume finite information budget. Across Bernoulli bandits, linear bandits, and tabular MDPs, the same hyperparameters transfer without retuning, and DE shows much weaker regret growth than Thompson Sampling and

\varepsilon

-greedy in the tested unresolved regimes. Delight improves acting for the same reason it improves learning: it prices scarce resources by the product of upside and surprisal.

Ian Osband

Google DeepMind

Multi-Armed Bandits Value of Information RL Exploration Decision-Making under Uncertainty Uncertainty-Aware Exploration Bandit Learning

May 12, 2026

Online Learning-to-Defer with Varying Experts

Learning-to-Defer (L2D) methods route each query either to a predictive model or to external experts. While existing work studies this problem in batch settings, real-world deployments require handling streaming data, changing expert availability, and shifting expert distribution. We introduce the first online L2D algorithm for multiclass classification with bandit feedback and a dynamically varying pool of experts. Our method achieves regret guarantees of

O((n+n_e)T^{2/3})

in general and

O((n+n_e)\sqrt{T})

under a low-noise condition, where

T

is the time horizon,

n

is the number of labels, and

n_e

is the number of distinct experts observed across rounds. The analysis builds on novel

\mathcal{H}

-consistency bounds for the online framework, combined with first-order methods for online convex optimization. Experiments on synthetic and real-world datasets demonstrate that our approach effectively extends standard Learning-to-Defer to settings with varying expert availability and reliability.

Dang Hoang Duy, Yannis Montreuil, Maxime Meyer +3

School of Computing, National University of Singapore, Singapore · IPAL, IRL 2955, Singapore · Department of Mathematics, National University of Singapore, Singapore, 117543 +2

Learning to Defer Bandit Learning Multiclass Classification Online Learning

May 10, 2026

Near-Optimal Last-Iterate Convergence for Zero-Sum Games with Bandit Feedback and Opponent Actions

Last-iterate convergence of learning dynamics in games has attracted significant recent attention. In two-player zero-sum games with bandit feedback, where only the loss of the selected action pair is observed, Fiegel et al. (2025) show a separation between average-iterate and last-iterate convergence in duality gap: while the optimal t^(-1/2) rate after t rounds is achievable for the former via standard no-regret algorithms, the latter cannot converge faster than t^(-1/3) in expectation or t^(-1/4) with high probability. However, in many practical settings, such as preference learning, the players observe not only their loss but also the opponent's action. This raises a natural question: can such additional information enable faster last-iterate convergence? We answer this question affirmatively, showing that t^(-1/2) last-iterate convergence is achievable with high probability in this setting, via an efficient algorithm that updates its strategy infrequently by solving an estimated log-barrier-regularized game. We identify fundamental obstacles preventing standard analysis for multi-armed bandits, the single-player case, from generalizing to games, and develop a novel analysis to overcome them. Experiments confirm that our algorithm indeed converges faster than naive baselines and prior methods that do not exploit opponent-action feedback. Finally, we note that our results also improve those for dueling bandits, a special case with skew-symmetric game matrices.

Soumita Hait, Ping Li, Haipeng Luo +1

University of Southern California · Shanghai University of Finance and Economics · University of Iowa

Last-Iterate Convergence Imperfect-Information Games Game Theory Zero-Sum Games Bandit Learning Convergence Analysis+1

May 8, 2026

Multi-Armed Bandits With Best-Action Queries

We study multi-armed bandits (MABs) augmented with best-action queries, in which the learner may additionally query an oracle that reveals the best arm in the current round. This setting was recently characterized by Russo et al. [2024] in the full-feedback model, where the learner observes the rewards of all arms after each round. They show that, in both stochastic and adversarial environments,

k

best-action queries reduce the optimal

\widetilde{\mathcal{O}}(\sqrt{T})

regret to

\widetilde{\mathcal{O}}(\min\{T/k,\sqrt{T}\})

. Whether this improvement extends to the more realistic bandit-feedback model -- where the learner observes only the reward of the played arm -- was left as an open problem. We fully resolve this question. When rewards are stochastic but correlated among arms, we show that the full-feedback result does not carry over: any algorithm must incur regret at least

Ω(\sqrt{T-k})

. This lower bound directly extends to adversarial environments. On the positive side, we show that

\widetilde{\mathcal{O}}(\min\{T/k,\sqrt{T-k}\})

regret is still achievable when rewards are stochastic and i.i.d., and establish a matching lower bound, up to logarithmic factors. Together, these results provide a complete characterization of the benefits of best-action queries in the bandit-feedback model.

Francesco Bacchiocchi, Matteo Castiglioni, Alberto Marchesi +1

Politecnico di Milano

Multi-Armed Bandits Adversarial Bandits Bandit Learning

May 7, 2026

Bandit Learning in General Open Multi-agent Systems

Open systems, where agents arrive and depart over time, are growing in digital platforms. Existing work on online learning in such systems, however, often relies on structural assumptions that may be restrictive in practice. In particular, heterogeneous rewards and general agent patterns create three new challenges: arrivals induce endogenous non-stationarity, agent patterns govern the rate of information accumulation, and uncertainty brought by new agents accumulates over time and scales regret. To this end, we formulate a learning problem for open systems that accommodates both forms of generality. We introduce new concepts to capture the inherent complexities: the pre-training degree of new agents quantifies how much information an agent carries upon entry, stability measures the impact of population changes on the global optimum, and global dynamic regret compares the cumulative expected reward with that of the varying optimal arms. We also study a manifold representation of agents and introduce a dynamic population embedding that directly encodes the population functional for each arm. We develop two UCB-based methods. The first combines entry information with online observations through agent-wise confidence bounds and aggregates the estimates and uncertainties for arm selection. The second pools agent-level observations through kernel regression on the manifold and constructs UCBs by projecting the confidence sets onto the current population embedding. Entry uncertainty enters the regret linearly through the pre-training error, while in stable regimes, regret is governed by the time needed to identify the stable optimal arm. With the manifold as a handle, regret is governed by the information gained from agent representations. These bounds all depend on population dynamics, but in different ways.

Mengfan Xu

Mechanical and Industrial Engineering, University of Massachusetts Amherst

Multi-Armed Bandits Multi-Agent Bandits Non-Stationary Bandits UCB Algorithms Bandit Learning