Greedy Algorithm Almost Dominates in Smoothed Contextual Bandits

DOI10.1137/19M1247115MaRDI QIDQ5890034zbMATH OpenOpenAlexFDO

Authors Manish Raghavan, Aleksandrs Slivkins, Jennifer Wortman Vaughan, Zhiwei Steven Wu

Publication date 28 April 2023

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2005.10624

zbMATH Keywords

Bayesian regretdata diversitygreedy algorithmlinear banditsmultiarmed banditssmoothed analysis

Mathematics Subject Classification ID

Artificial intelligence (68T99)

Recommendations

• Smoothness-Adaptive Contextual Bandits
• A Structured Multiarmed Bandit Problem and the Greedy Policy
• Smooth Contextual Bandits: Bridging the Parametric and Nondifferentiable Regret Regimes
• Contextual bandits with continuous actions: smoothing, zooming, and adapting
• A minimax and asymptotically optimal algorithm for stochastic bandits
• Regulating greed over time in multi-armed bandits
• Multi-objective Contextual Multi-armed Bandit With a Dominant Objective
• Better algorithms for benign bandits

Cites work

• 10.1162/153244303321897663
• A contextual bandit bake-off
• Adaptive estimation of a quadratic functional by model selection.
• An elementary proof of a theorem of Johnson and Lindenstrauss
• Bandit algorithms
• Batched bandit problems
• Finite-time analysis of the multiarmed bandit problem
• Regret analysis of stochastic and nonstochastic multi-armed bandit problems
• Smoothed analysis of algorithms
• Tail bounds for sums of geometric and exponential variables
• The convex geometry of linear inverse problems
• User-friendly tail bounds for sums of random matrices

Describes a project that uses

Uses Software

• GitHub

This page was built for publication: Greedy Algorithm Almost Dominates in Smoothed Contextual Bandits

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5890034)