Markovian Bandits

Follow this topic Ask about this topic

Latest papers

8 papers2 papers in the last four weeks, against 2 the four weeks before. 0.0% of all new papers.

Budgeted Bayesian Bandits for Future Utilization
Oct 16, 2026Sudipto GuhaMarkovian Bandits Multi-Armed Bandits
Minimax estimation of the pseudo-spectral gap of continuous Markov chains, with applications to empirical concentration bounds
Oct 14, 2026Vahe Karagulyan, Mikołaj Kasprzak, Pierre AlquierMarkovian Bandits Minimax Estimation
ESSEC Business School
Future Information-Directed Sampling for Bayesian Nonstationary Bandits
Sep 27, 2026Yichen Song, Alessio Russo, Aldo PacchianoMulti-Armed Bandits Non-Stationary Bandits
Boston University · Broad Institute of MIT and Harvard
Efficient Cost-Aware LLM Evaluation via Bayesian Bandit Gittins Indices
Sep 22, 2026Qian Xie, Yueli He, Nairen CaoMulti-Armed Bandits LLM Evaluation
Cornell University · Columbia University · New York University +1
On-Policy and Off-Policy Learning for Large Action Spaces
Jul 30, 2026Imad AoualiThompson Sampling Multi-Armed Bandits
Institut Polytechnique de Paris · Ecole nationale de la statistique et de l’administration économique · Ecole doctorale n◦574 Ecole Doctorale de Mathématique Hadamard (EDMH)
Learning in Markovian bandits with non-observable states and constrained decision epochs
Jun 25, 2026Thomas Hira, Victor Boone, Urtzi Ayesta +1Multi-Armed Bandits Markov Models
IRIT, Université de Toulouse, CNRS, Toulouse INP, Toulouse, France · Ikerbasque-UPV/EHU, University of the Basque Country, Bilbao, Spain
Mixing Makes Markovian Contexts Cheap for Linear Bandits
Mar 13, 2026Kaan Buyukkalayci, Osama Hanna, Christina FragouliMarkovian Bandits Contextual Bandits
University of California, Los Angeles · Meta, Superintelligence Lab
Bayesian Online Model Selection
Feb 20, 2026Aida Afshar, Yuke Zhang, Aldo PacchianoMarkovian Bandits Model Selection
Boston University · Broad Institute of MIT and Harvard

Oct 16, 2026J/K move · Enter open · S save

Budgeted Bayesian Bandits for Future Utilization

Sudipto Guha

Markovian Bandits Multi-Armed Bandits Approximation Algorithms

Open paper AskPDF arXiv

The multi-armed bandit problem models the trade-off between exploration and exploitation. In this paper, we study the variant where exploration has a hard budget and precedes exploitation. Prior guarantees include a 1/3 approximation by Guha and Munagala using Lagrangian duality, and a 4/27 approximation by Ma against a primal linear programming relaxation for a more general model. We show that the analyses of both algorithms are tight, even when their relaxations are asymptotically exact. We provide a different efficient algorithm that achieves a 0.43 approximation. We then provide an efficient algorithm whose guarantee approaches 1-e^{-1} approx 0.63 for bounded exchangeable reward observations in a non-vanishing regime, which is asymptotically tight against natural linear programming relaxations. The technique also gives certificates for stopping sequential model evaluation.