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.

On-line Learning in Tree MDPs by Treating Policies as Bandit Arms
May 6, 2026Anvay Shah, Ramsundar Anandanarayanan, Sharayu Moharir +1Markov Decision Processes Markov Models
Indian Institute of Technology Bombay · Mumbai, India
AI Alignment via Incentives and Correction
May 2, 2026Rohit Agarwal, Joshua Lin, Mark Braverman +1AI Alignment Bandit Learning
Princeton University
Trading off rewards and errors in multi-armed bandits
May 1, 2026Akram Erraqabi, Alessandro Lazaric, Michal Valko +2Multi-Armed Bandits Exploration-Exploitation Tradeoff
Inria SequeL · CMU · EnLearn
Online learning with Erdős-Rényi side-observation graphs
Apr 28, 2026Tomáš Kocák, Gergely Neu, Michal ValkoMulti-Armed Bandits Adversarial Bandits
SequeL team INRIA Lille - Nord Europe · Universitat Pompeu Fabra Barcelona, Spain
Online combinatorial optimization with stochastic decision sets and adversarial losses
Apr 28, 2026Gergely Neu, Michal ValkoMulti-Armed Bandits Follow-the-Perturbed-Leader
SequeL team, INRIA Lille – Nord Europe, France
Reliable Self-Harm Risk Screening via Adaptive Multi-Agent LLM Systems
Apr 24, 2026Meghana Karnam, Ananya JoshiAI Agent Reliability Multi-Agent LLM Systems
Johns Hopkins University Baltimore, USA
A single algorithm for both restless and rested rotting bandits
Apr 23, 2026Julien Seznec, Pierre Ménard, Alessandro Lazaric +1Multi-Armed Bandits Non-Stationary Bandits
SCOOL, Inria Lille · FAIR Paris · DeepMind Paris
Calibration-Gated LLM Pseudo-Observations for Online Contextual Bandits
Apr 16, 2026Maksim Pershin, Ivan Golovanov, Pavel Baltabaev +1Contextual Bandits Linear Contextual Bandits
Best of both worlds: Stochastic & adversarial best-arm identification
Apr 16, 2026Yasin Abbasi-Yadkori, Peter L. Bartlett, Victor Gabillon +2Multi-Armed Bandits Best-Arm Identification
Adobe Research, USA · University of California, Berkeley, USA · Queensland University of Technology - ACEMS, Australia +2
Learning from Equivalence Queries, Revisited
Apr 6, 2026Mark Braverman, Roi Livni, Yishay Mansour +2Bandit Learning Concept Learning
Princeton and Google · Tel-Aviv University · Tel-Aviv University and Google +2
Best-Arm Identification with Noisy Actuation
Apr 2, 2026Merve Karakas, Osama Hanna, Lin F. Yang +1Best-Arm Identification Multi-Armed Bandits
University of California, Los Angeles · Meta, Central Applied Science
Adversarial Bandit Optimization with Globally Bounded Perturbations to Linear Losses
Mar 27, 2026Zhuoyu Cheng, Kohei Hatano, Eiji TakimotoBandit Learning Adversarial Bandits
Joint Graduate School of Mathematics for Innovation, Kyushu University, Japan. · Department of Informatics, Kyushu University, Japan. · RIKEN AIP, Japan.
Transformers in the Dark: Navigating Unknown Search Spaces via Bandit Feedback
Mar 25, 2026Jungtaek Kim, Thomas Zeng, Ziqian Lin +5Bandit Learning Tree Search
University of Wisconsin–Madison · FuriosaAI · Yonsei University +1
Does This Gradient Spark Joy?
Mar 20, 2026Ian OsbandBandit Learning Policy Gradient
Google DeepMind
A Practical Algorithm for Feature-Rich, Non-Stationary Bandit Problems
Mar 17, 2026Wei Min Loh, Sajib Kumer Sinha, Ankur Agarwal +1Bandit Learning Multi-Armed Bandits
University of Waterloo, Vector Institute · Manulife Financial
Design Experiments to Compare Multi-armed Bandit Algorithms
Mar 6, 2026Huiling Meng, Ningyuan Chen, Xuefeng GaoBandit Learning Multi-Armed Bandits
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.
Lookahead identification in adversarial bandits: accuracy and memory bounds
Feb 28, 2026Nataly Brukhim, Nicolò Cesa-Bianchi, Carlo CilibertoMulti-Armed Bandits Bandit Learning
DIMACS, Rutgers University · Institute for Advanced Study · Universit`a degli Studi di Milano +3
Learning with a Budget: Identifying the Best Arm with Resource Constraints
Feb 27, 2026Zitian Li, Wang Chi CheungBest-Arm Identification Multi-Armed Bandits
Department of Industrial Systems Engineering & Management, National University of Singapore, Singapore
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
Feb 24, 2026Arnab Maiti, Claire Jie Zhang, Kevin Jamieson +3Bandit Learning Last-Iterate Convergence
University of Washington · Amazon · University of California, Irvine
Flickering Multi-Armed Bandits
Feb 19, 2026Sourav Chakraborty, Amit Kiran Rege, Claire Monteleoni +1Multi-Armed Bandits Bandit Learning
University of Colorado Boulder, USA. · INRIA Paris, France.
Decentralized Projection-free Online Upper-Linearizable Optimization with Applications to DR-Submodular Optimization
Jan 30, 2025Yiyang Lu, Mohammad Pedramfar, Vaneet AggarwalSubmodular Optimization Online Convex Optimization
Purdue University, West Lafayette, IN, USA · Mila - Quebec AI Institute/McGill University, Montreal, QC, Canada
Bridging Rested and Restless Bandits with Graph-Triggering: Rising and Rotting
Sep 9, 2024Gianmarco Genalti, Marco Mussi, Nicola Gatti +3Multi-Armed Bandits Graph Bandits
Politecnico di Milano2026 Piazza Leonardo da Vinci 32, Milan, 20133, Italy

May 6, 2026J/K move · Enter open · S save

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

Anvay Shah, Ramsundar Anandanarayanan, Sharayu Moharir, Shivaram Kalyanakrishnan

Indian Institute of Technology Bombay · Mumbai, India

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

Open paper AskPDF arXiv

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.