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.

May 6, 2026

On-line Learning in Tree MDPs by Treating Policies as Bandit Arms

A Tree Markov Decision Problem (T-MDP) is a finite-horizon MDP with a starting state

s_{1}

, in which every state is reachable from

s_{1}

through exactly one state-action trajectory. T-MDPs arise naturally as abstractions of decision making in sequential games with perfect recall, against stationary opponents. We consider the problem of on-line learning in T-MDPs, both in the PAC and the regret-minimisation regimes. We show that well-known bandit algorithms -- Lucb and Ucb -- can be applied on T-MDPs by treating each policy as an arm. The apparent technical challenge in this approach is that the number of policies is exponential in the number of states. Our main innovation is in the design of confidence bounds based on data shared by the policies, so that the bandit algorithms can yet be implemented with polynomial memory and per-step computation. We obtain instance-dependent upper bounds on sample complexity and regret that sum a ``gap term'' from every terminal state, rather than every policy. Empirically, our algorithms consistently outperform available alternatives on a suite of hidden-information games.

Anvay Shah, Ramsundar Anandanarayanan, Sharayu Moharir +1

Indian Institute of Technology Bombay · Mumbai, India

Markov Decision Processes Markov Models Interval Markov Decision Processes Policy Learning Bandit Learning

May 2, 2026

AI Alignment via Incentives and Correction

We study AI alignment through the lens of law-and-economics models of deterrence and enforcement. In these models, misconduct is not treated as an external failure, but as a strategic response to incentives: an actor weighs the gain from violation against the probability of detection and the severity of punishment. We argue that the same logic arises naturally in agentic AI pipelines. A solver may benefit from producing a persuasive but incorrect answer, hiding uncertainty, or exploiting spurious shortcuts, while an auditor or verifier must decide whether costly monitoring is worthwhile. Alignment is therefore a fixed-point problem: stronger penalties may deter solver misbehavior, but they can also reduce the auditor's incentive to inspect, since auditing then mainly incurs cost on a population that appears increasingly aligned. This perspective also changes what should count as a post-training signal. Standard feedback often attaches reward to the final answer alone, but a solver-auditor pipeline exposes the full correction event: whether the solver erred, whether the auditor inspected, whether the error was caught, and whether oversight incentives remained active. We formalize this interaction in a two-agent model in which a principal chooses rewards over joint correction outcomes, inducing both solver behavior and auditor monitoring. Reward design is therefore a bilevel optimization problem: rewards are judged not by their immediate semantic meaning, but by the behavioral equilibrium they induce. We propose a bandit-based outer-loop procedure for searching over reward profiles using noisy interaction feedback. Experiments on an LLM coding pipeline show that adaptive reward profiles can maintain useful oversight pressure and improve principal-aligned outcomes relative to static hand-designed rewards, including a substantial reduction in hallucinated incorrect attempts.

Rohit Agarwal, Joshua Lin, Mark Braverman +1

Princeton University

AI Alignment Bandit Learning

May 1, 2026

Trading off rewards and errors in multi-armed bandits

In multi-armed bandits, the most-explored arms are the most informative, while reward maximization typically pulls only the best arm. We study the tradeoff between identifying arm means accurately and accumulating reward, and present an algorithm with regret guarantees that interpolates between the two objectives. We provide both upper and lower bounds and validate empirically.

Akram Erraqabi, Alessandro Lazaric, Michal Valko +2

Inria SequeL · CMU · EnLearn

Multi-Armed Bandits Exploration-Exploitation Tradeoff Best-Arm Identification Regret Minimization Bandit Learning

Apr 28, 2026

Online learning with Erdős-Rényi side-observation graphs

We consider adversarial multi-armed bandit problems where the learner is allowed to observe losses of a number of arms beside the arm that it actually chose. We study the case where all non-chosen arms reveal their loss with a fixed but unknown probability

r

, independently of each other and the action of the learner. We propose two algorithms that work for different ranges of

r

. We show that after

T

rounds in a bandit problem with

N

arms, the expected regret of our first algorithm is

O(\sqrt{(T /r) \log N })

whenever

r\ge(\log T)/(2N)

, while our second algorithm achieves a regret of

O(\sqrt{(T/r) \log (N+T)})

for smaller values of

r

. We also give a quick estimation procedure that decides the range of~

r

. All our bounds are within logarithmic factors of the best achievable performance of any algorithm that is even allowed to know~

r

.

Tomáš Kocák, Gergely Neu, Michal Valko

SequeL team INRIA Lille - Nord Europe · Universitat Pompeu Fabra Barcelona, Spain

Multi-Armed Bandits Adversarial Bandits Bandit Learning

Apr 28, 2026

Online combinatorial optimization with stochastic decision sets and adversarial losses

Most work on sequential learning assumes a fixed set of actions that are available all the time. However, in practice, actions can consist of picking subsets of readings from sensors that may break from time to time, road segments that can be blocked or goods that are out of stock. In this paper we study learning algorithms that are able to deal with stochastic availability of such unreliable composite actions. We propose and analyze algorithms based on the Follow-The-Perturbed-Leader prediction method for several learning settings differing in the feedback provided to the learner. Our algorithms rely on a novel loss estimation technique that we call Counting Asleep Times. We deliver regret bounds for our algorithms for the previously studied full information and (semi-)bandit settings, as well as a natural middle point between the two that we call the restricted information setting. A special consequence of our results is a significant improvement of the best known performance guarantees achieved by an efficient algorithm for the sleeping bandit problem with stochastic availability. Finally, we evaluate our algorithms empirically and show their improvement over the known approaches.

Gergely Neu, Michal Valko

SequeL team, INRIA Lille – Nord Europe, France

Multi-Armed Bandits Follow-the-Perturbed-Leader Exploration-Exploitation Tradeoff Combinatorial Optimization Bandit Learning

Apr 24, 2026

Reliable Self-Harm Risk Screening via Adaptive Multi-Agent LLM Systems

Emerging AI systems in behavioral health and psychiatry use multi-step or multi-agent LLM pipelines for tasks like assessing self-harm risk and screening for depression. However, common evaluation approaches, like LLM-as-a-judge, do not indicate when a decision is reliable or how errors may accumulate across multiple LLM judgements, limiting their suitability for safety-critical settings. We present a statistical framework for multi-agent pipelines structured as directed acyclic graphs (DAGs) that provides an alternative to heuristic voting with principled, adaptive decision-making. We model each agent as a stochastic categorical decision and introduce (1) tighter agent-level performance confidence bounds, (2) a bandit-based adaptive sampling strategy based on input difficulty, and (3) regret guarantees over the multi-agent system that shows logarithmic error growth when deployed. We evaluate our system on two labeled datasets in behavioral health : the AEGIS 2.0 behavioral health subset (N=161) and a stratified sample of SWMH Reddit posts (N=250). Empirically, our adaptive sampling strategy achieves the lowest false positive rate of any condition across both datasets, 0.095 on AEGIS 2.0 compared to 0.159 for single-agent models, reducing incorrect flagging of safe content by 40% and still having similar false negative rates across all conditions. These results suggest that principled adaptive sampling offers a meaningful improvement in precision without reducing recall in this setting.

Meghana Karnam, Ananya Joshi

Johns Hopkins University Baltimore, USA

AI Agent Reliability Multi-Agent LLM Systems Healthcare Mental Health Bandit Learning Clinical Risk Prediction+1

Apr 23, 2026

A single algorithm for both restless and rested rotting bandits

In many application domains (e.g., recommender systems, intelligent tutoring systems), the rewards associated to the actions tend to decrease over time. This decay is either caused by the actions executed in the past (e.g., a user may get bored when songs of the same genre are recommended over and over) or by an external factor (e.g., content becomes outdated). These two situations can be modeled as specific instances of the rested and restless bandit settings, where arms are rotting (i.e., their value decrease over time). These problems were thought to be significantly different, since Levine et al. (2017) showed that state-of-the-art algorithms for restless bandit perform poorly in the rested rotting setting. In this paper, we introduce a novel algorithm, Rotting Adaptive Window UCB (RAW-UCB), that achieves near-optimal regret in both rotting rested and restless bandit, without any prior knowledge of the setting (rested or restless) and the type of non-stationarity (e.g., piece-wise constant, bounded variation). This is in striking contrast with previous negative results showing that no algorithm can achieve similar results as soon as rewards are allowed to increase. We confirm our theoretical findings on a number of synthetic and dataset-based experiments.

Julien Seznec, Pierre Ménard, Alessandro Lazaric +1

SCOOL, Inria Lille · FAIR Paris · DeepMind Paris

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

Apr 16, 2026

Calibration-Gated LLM Pseudo-Observations for Online Contextual Bandits

Contextual bandit algorithms suffer from high regret during cold-start, when the learner has insufficient data to distinguish good arms from bad. We propose augmenting Disjoint LinUCB with LLM pseudo-observations: after each round, a large language model predicts counterfactual rewards for the unplayed arms, and these predictions are injected into the learner as weighted pseudo-observations. The injection weight is controlled by a calibration-gated decay schedule that tracks the LLM's prediction accuracy on played arms via an exponential moving average; high calibration error suppresses the LLM's influence, while accurate predictions receive higher weight during the critical early rounds. We evaluate on two contextual bandit environments - UCI Mushroom (2-arm, asymmetric rewards) and MIND-small (5-arm news recommendation) - and find that when equipped with a task-specific prompt, LLM pseudo-observations reduce cumulative regret by 19% on MIND relative to pure LinUCB. However, generic counterfactual prompt framing increases regret on both environments, demonstrating that prompt design is the dominant factor, more important than the choice of decay schedule or calibration gating parameters. We analyze the failure modes of calibration gating on domains with small prediction errors and provide a theoretical motivation for the bias-variance trade-off governing pseudo-observation weight.

Maksim Pershin, Ivan Golovanov, Pavel Baltabaev +1

Contextual Bandits Linear Contextual Bandits Bandit Learning

Apr 16, 2026

Best of both worlds: Stochastic & adversarial best-arm identification

We study bandit best-arm identification with arbitrary and potentially adversarial rewards. A simple random uniform learner obtains the optimal rate of error in the adversarial scenario. However, this type of strategy is suboptimal when the rewards are sampled stochastically. Therefore, we ask: Can we design a learner that performs optimally in both the stochastic and adversarial problems while not being aware of the nature of the rewards? First, we show that designing such a learner is impossible in general. In particular, to be robust to adversarial rewards, we can only guarantee optimal rates of error on a subset of the stochastic problems. We give a lower bound that characterizes the optimal rate in stochastic problems if the strategy is constrained to be robust to adversarial rewards. Finally, we design a simple parameter-free algorithm and show that its probability of error matches (up to log factors) the lower bound in stochastic problems, and it is also robust to adversarial ones.

Yasin Abbasi-Yadkori, Peter L. Bartlett, Victor Gabillon +2

Adobe Research, USA · University of California, Berkeley, USA · Queensland University of Technology - ACEMS, Australia +2

Multi-Armed Bandits Best-Arm Identification Adversarial Bandits Bandit Learning

Apr 6, 2026

Learning from Equivalence Queries, Revisited

Modern machine learning systems, such as generative models and recommendation systems, often evolve through a cycle of deployment, user interaction, and periodic model updates. This differs from standard supervised learning frameworks, which focus on loss or regret minimization over a fixed sequence of prediction tasks. Motivated by this setting, we revisit the classical model of learning from equivalence queries, introduced by Angluin (1988). In this model, a learner repeatedly proposes hypotheses and, when a deployed hypothesis is inadequate, receives a counterexample. Under fully adversarial counterexample generation, however, the model can be overly pessimistic. In addition, most prior work assumes a full-information setting, where the learner also observes the correct label of the counterexample, an assumption that is not always natural. We address these issues by restricting the environment to a broad class of less adversarial counterexample generators, which we call symmetric. Informally, such generators choose counterexamples based only on the symmetric difference between the hypothesis and the target. This class captures natural mechanisms such as random counterexamples (Angluin and Dohrn, 2017; Bhatia, 2021; Chase, Freitag, and Reyzin, 2024), as well as generators that return the simplest counterexample according to a prescribed complexity measure. Within this framework, we study learning from equivalence queries under both full-information and bandit feedback. We obtain tight bounds on the number of learning rounds in both settings and highlight directions for future work. Our analysis combines a game-theoretic view of symmetric adversaries with adaptive weighting methods and minimax arguments.

Mark Braverman, Roi Livni, Yishay Mansour +2

Princeton and Google · Tel-Aviv University · Tel-Aviv University and Google +2

Bandit Learning Concept Learning Statistical Learning Theory

Apr 2, 2026

Best-Arm Identification with Noisy Actuation

In this paper, we consider a multi-armed bandit (MAB) instance and study how to identify the best arm when arm commands are conveyed from a central learner to a distributed agent over a discrete memoryless channel (DMC). Depending on the agent capabilities, we provide communication schemes along with their analysis, which interestingly relate to the zero-error capacity of the underlying DMC.

Merve Karakas, Osama Hanna, Lin F. Yang +1

University of California, Los Angeles · Meta, Central Applied Science

Best-Arm Identification Multi-Armed Bandits Bandit Learning

Mar 27, 2026

Adversarial Bandit Optimization with Globally Bounded Perturbations to Linear Losses

We study a class of adversarial bandit optimization problems in which the loss functions may be non-convex and non-smooth. In each round, the learner observes a loss that consists of an underlying linear component together with an additional perturbation applied after the learner selects an action. The perturbations are measured relative to the linear losses and are constrained by a global budget that bounds their cumulative magnitude over time. Under this model, we establish both expected and high-probability regret guarantees. As a special case of our analysis, we recover an improved high-probability regret bound for classical bandit linear optimization, which corresponds to the setting without perturbations. We further complement our upper bounds by proving a lower bound on the expected regret.

Zhuoyu Cheng, Kohei Hatano, Eiji Takimoto

Joint Graduate School of Mathematics for Innovation, Kyushu University, Japan. · Department of Informatics, Kyushu University, Japan. · RIKEN AIP, Japan.

Bandit Learning Adversarial Bandits

Mar 25, 2026

Transformers in the Dark: Navigating Unknown Search Spaces via Bandit Feedback

Effective problem solving with Large Language Models (LLMs) can be enhanced when they are paired with external search algorithms. By viewing the space of diverse ideas and their follow-up possibilities as a tree structure, the search algorithm can navigate such a search space and guide the LLM toward better solutions more efficiently. While the search algorithm enables an effective balance between exploitation and exploration of a tree-structured space, the need for an external component can complicate the overall problem-solving process. We therefore pose the following question: Can LLMs or their underlying Transformer architectures approximate a search algorithm? To answer this question, we first introduce a simplified framework in which tree extensions and feedback signals are externally specified, allowing for controlled evaluation of search capabilities. We call this setting unknown tree search with bandit feedback. Within this setting, we show that Transformers are theoretically expressive enough to implement distinct search strategies and can be trained from scratch to approximate those strategies. Our Transformer models exhibit the possibility of generalizing to unseen conditions such as longer horizons or deeper trees. Furthermore, we demonstrate that continued task-focused training unlocks the complete capabilities of a pretrained LLM, by fine-tuning the LLM on search trajectories.

Jungtaek Kim, Thomas Zeng, Ziqian Lin +5

University of Wisconsin–Madison · FuriosaAI · Yonsei University +1

Bandit Learning Tree Search Transformer

Mar 20, 2026

Does This Gradient Spark Joy?

Policy gradient computes a backward pass for every sample, even though the backward pass is expensive and most samples carry little learning value. The Delightful Policy Gradient (DG) provides a forward-pass signal of learning value: delight, the product of advantage and surprisal (negative log-probability). We introduce the Kondo gate, which compares delight against a compute price and pays for a backward pass only when the sample is worth it, thereby tracing a quality--cost Pareto frontier. In bandits, zero-price gating preserves useful gradient signal while removing perpendicular noise, and delight is a more reliable screening signal than additive combinations of value and surprise. On MNIST and transformer token reversal, the Kondo gate skips most backward passes while retaining nearly all of DG's learning quality, with gains that grow as problems get harder and backward passes become more expensive. Because the gate tolerates approximate delight, a cheap forward pass can screen samples before expensive backpropagation, suggesting a speculative-decoding-for-training paradigm.

Ian Osband

Google DeepMind

Bandit Learning Policy Gradient Neural Network Optimization Adaptive Computation

Mar 17, 2026

A Practical Algorithm for Feature-Rich, Non-Stationary Bandit Problems

Contextual bandits are incredibly useful in many practical problems. We go one step further by devising a more realistic problem that combines: (1) contextual bandits with dense arm features, (2) non-linear reward functions, and (3) a generalization of correlated bandits where reward distributions change over time but the degree of correlation maintains. This formulation lends itself to a wider set of applications such as recommendation tasks. To solve this problem, we introduce conditionally coupled contextual C3 Thompson sampling for Bernoulli bandits. It combines an improved Nadaraya-Watson estimator on an embedding space with Thompson sampling that allows online learning without retraining. Empirical results show that C3 outperforms the next best algorithm by 5.7% lower average cumulative regret on four OpenML tabular datasets as well as demonstrating a 12.4% click lift on Microsoft News Dataset (MIND) compared to other algorithms.

Wei Min Loh, Sajib Kumer Sinha, Ankur Agarwal +1

University of Waterloo, Vector Institute · Manulife Financial

Bandit Learning Multi-Armed Bandits Contextual Bandits Non-Stationary Bandits Thompson Sampling Recommender Systems

Mar 6, 2026

Design Experiments to Compare Multi-armed Bandit Algorithms

Online platforms routinely compare multi-armed bandit algorithms, such as UCB and Thompson Sampling, to select the best-performing policy. Unlike standard A/B tests for static treatments, each run of a bandit algorithm over

T

users produces only one trajectory, because the algorithm's decisions depend on all past interactions. Reliable inference therefore demands many independent restarts of the algorithm, making experimentation costly and delaying deployment decisions. We propose Artificial Replay (AR) as a new experimental design for this problem. AR first runs one policy and records its trajectory. When the second policy is executed, it reuses a recorded reward whenever it selects an action the first policy already took, and queries the real environment only otherwise. We develop a new analytical framework for this design and prove three key properties of the resulting estimator: it is unbiased; it requires only

T + o(T)

user interactions instead of

2T

for a run of the treatment and control policies, nearly halving the experimental cost when both policies have sub-linear regret; and its variance grows sub-linearly in

T

, whereas the estimator from a naïve design has a linearly-growing variance. Numerical experiments with UCB, Thompson Sampling, and

ε

-greedy policies confirm these theoretical gains.

Huiling Meng, Ningyuan Chen, Xuefeng Gao

Department of Systems Engineering and Engineering Management, The Chinese University of Hong Kong, Hong Kong, China. · Rotman School of Management, University of Toronto, Toronto, Canada.

Bandit Learning Multi-Armed Bandits

Feb 28, 2026

Lookahead identification in adversarial bandits: accuracy and memory bounds

We study an identification problem in multi-armed bandits. In each round a learner selects one of

K

arms and observes its reward, with the goal of eventually identifying an arm that will perform best at a {\it future} time. In adversarial environments, however, past performance may offer little information about the future, raising the question of whether meaningful identification is possible at all. In this work, we introduce lookahead identification, a task in which the goal of the learner is to select a future prediction window and commit in advance to an arm whose average reward over that window is within

\varepsilon

of optimal. Our analysis characterizes both the achievable accuracy of lookahead identification and the memory resources required to obtain it. From an accuracy standpoint, for any horizon

T

we give an algorithm achieving

\varepsilon = O\bigl(1/\sqrt{\log T}\bigr)

over

Ω(\sqrt{T})

prediction windows. This demonstrates that, perhaps surprisingly, identification is possible in adversarial settings, despite significant lack of information. We also prove a near-matching lower bound showing that

\varepsilon = Ω\bigl(1/\log T\bigr)

is unavoidable. We then turn to investigate the role of memory in our problem, first proving that any algorithm achieving nontrivial accuracy requires

Ω(K)

bits of memory. Under a natural local sparsity condition, we show that the same accuracy guarantees can be achieved using only poly-logarithmic memory.

Nataly Brukhim, Nicolò Cesa-Bianchi, Carlo Ciliberto

DIMACS, Rutgers University · Institute for Advanced Study · Universit`a degli Studi di Milano +3

Multi-Armed Bandits Bandit Learning Adversarial Bandits

Feb 27, 2026

Learning with a Budget: Identifying the Best Arm with Resource Constraints

In many applications, evaluating the effectiveness of different alternatives comes with varying costs or resource usage. Motivated by such heterogeneity, we study the Best Arm Identification with Resource Constraints (BAIwRC) problem, where an agent seeks to identify the best alternative (aka arm) in the presence of resource constraints. Each arm pull consumes one or more types of limited resources. We make two key contributions. First, we propose the Successive Halving with Resource Rationing (SH-RR) algorithm, which integrates resource-aware allocation into the classical successive halving framework on best arm identification. The SH-RR algorithm unifies the theoretical analysis for both the stochastic and deterministic consumption settings, with a new \textit{effective consumption measure

Zitian Li, Wang Chi Cheung

Department of Industrial Systems Engineering & Management, National University of Singapore, Singapore

Best-Arm Identification Multi-Armed Bandits Bandit Learning

Feb 24, 2026

Efficient Uncoupled Learning Dynamics with $\tilde{O}\!\left(T^{-1/4}\right)$ Last-Iterate Convergence in Bilinear Saddle-Point Problems over Convex Sets under Bandit Feedback

In this paper, we study last-iterate convergence of learning algorithms in bilinear saddle-point problems, a preferable notion of convergence that captures the day-to-day behavior of learning dynamics. We focus on the challenging setting where players select actions from compact convex sets and receive only bandit feedback. Our main contribution is the design of an uncoupled learning algorithm that guarantees last-iterate convergence to the Nash equilibrium with high probability. We establish a convergence rate of

\tilde{O}(T^{-1/4})

up to polynomial factors in problem parameters. Crucially, our proposed algorithm is computationally efficient, requiring only an efficient linear optimization oracle over the players' compact action sets. The algorithm is obtained by combining techniques from experimental design and the classic Follow-The-Regularized-Leader (FTRL) framework, with a carefully chosen regularizer function tailored to the geometry of the action set of each learner.

Arnab Maiti, Claire Jie Zhang, Kevin Jamieson +3

University of Washington · Amazon · University of California, Irvine

Bandit Learning Last-Iterate Convergence Nash Equilibrium Computation Zero-Sum Games Follow-the-Regularized-Leader

Feb 19, 2026

Flickering Multi-Armed Bandits

We introduce Flickering Multi-Armed Bandits (FMAB) to model sequential decision-making in environments with changing action availability, where accessibility of the next action is restricted to a subset dependent on the agent's current choice. We formalize these constraints through stochastically evolving graphs where actions are limited to local neighborhoods. This mobility-constrained structure imposes a dual challenge: the statistical requirement of information acquisition and the physical overhead of navigation. We analyze FMAB under i.i.d. Erdős--R'enyi and Edge-Markovian process, proposing a two-phase lazy random walk algorithm for robust exploration. We establish high-probability sublinear regret bounds and prove near-optimality via a matching information-theoretic lower bound. Our results characterize the intrinsic cost of learning under local-move constraints, complemented by a robotic disaster-response simulation.

Sourav Chakraborty, Amit Kiran Rege, Claire Monteleoni +1

University of Colorado Boulder, USA. · INRIA Paris, France.

Multi-Armed Bandits Bandit Learning Graph Bandits

Jan 30, 2025

Decentralized Projection-free Online Upper-Linearizable Optimization with Applications to DR-Submodular Optimization

We introduce a novel framework for decentralized projection-free optimization, extending projection-free methods to a broader class of upper-linearizable functions. Our approach leverages decentralized optimization techniques with the flexibility of upper-linearizable function frameworks, effectively generalizing traditional DR-submodular function optimization. We obtain the regret of

O(T^{1-θ/2})

with communication complexity of

O(T^θ)

and number of linear optimization oracle calls of

O(T^{2θ})

for decentralized upper-linearizable function optimization, for any

0\le θ\le 1

. This approach allows for the first results for monotone up-concave optimization with general convex constraints and non-monotone up-concave optimization with general convex constraints. Further, the above results for first order feedback are extended to zeroth order, semi-bandit, and bandit feedback.

Yiyang Lu, Mohammad Pedramfar, Vaneet Aggarwal

Purdue University, West Lafayette, IN, USA · Mila - Quebec AI Institute/McGill University, Montreal, QC, Canada

Submodular Optimization Online Convex Optimization Bandit Learning Constrained Optimization Decentralized Optimization

Sep 9, 2024

Bridging Rested and Restless Bandits with Graph-Triggering: Rising and Rotting

Rested and Restless Bandits are two well-known bandit settings that are useful to model real-world sequential decision-making problems in which the expected reward of an arm evolves over time due to the actions we perform or due to the nature. In this work, we propose Graph-Triggered Bandits (GTBs), a unifying framework to generalize and extend rested and restless bandits. In this setting, the evolution of the arms' expected rewards is governed by a graph defined over the arms. An edge connecting a pair of arms

(i,j)

represents the fact that a pull of arm

i

triggers the evolution of arm

j

, and vice versa. Interestingly, rested and restless bandits are both special cases of our model for some suitable (degenerated) graph. As relevant case studies for this setting, we focus on two specific types of monotonic bandits: rising, where the expected reward of an arm grows as the number of triggers increases, and rotting, where the opposite behavior occurs. For these cases, we study the optimal policies. We provide suitable algorithms for all scenarios and discuss their theoretical guarantees, highlighting the complexity of the learning problem concerning instance-dependent terms that encode specific properties of the underlying graph structure.

Gianmarco Genalti, Marco Mussi, Nicola Gatti +3

Politecnico di Milano2026 Piazza Leonardo da Vinci 32, Milan, 20133, Italy

Multi-Armed Bandits Graph Bandits Bandit Learning