Online learning over a finite action set with limited switching

DOI10.1287/MOOR.2020.1052MaRDI QIDQ4991672zbMATH OpenOpenAlexFDO

Authors Kunal Talwar, Jason M. Altschuler

Publication date 3 June 2021

Published in Mathematics of Operations Research (Search for Journal in Brave)

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

zbMATH Keywords

adversarial multiarmed banditshigh-probability algorithmsminimax optimalityonline combinatorial optimizationonline learningprediction from expertsswitching budgetsswitching costs

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Reasoning under uncertainty in the context of artificial intelligence (68T37)

Recommendations

• Bandits with switching costs, \(T^{2/3}\) regret
• Multi-armed Bandits with Metric Switching Costs
• Regret bounds for sleeping experts and bandits
• Online regret bounds for Markov decision processes with deterministic transitions
• Learning hurdles for sleeping experts

Cites work

• 10.1162/1532443041424328
• A decision-theoretic generalization of on-line learning and an application to boosting
• An Efficient Algorithm for Learning with Semi-bandit Feedback
• Bandits with switching costs, \(T^{2/3}\) regret
• Combinatorial bandits
• Concentration inequalities. A nonasymptotic theory of independence
• Dynamic huffman coding
• Efficient algorithms for online decision problems
• How to use expert advice
• Learning permutations with exponential weights
• Markov decision processes with arbitrary reward processes
• Minimizing Regret With Label Efficient Prediction
• Near-Optimal Rates for Limited-Delay Universal Lossy Source Coding
• Online learning and online convex optimization
• Online linear optimization and adaptive routing
• Online Markov decision processes
• Predicting nearly as well as the best pruning of a planar decision graph.
• Prediction, Learning, and Games
• Random-Walk Perturbations for Online Combinatorial Optimization
• Regret analysis of stochastic and nonstochastic multi-armed bandit problems
• Regret bounds and minimax policies under partial monitoring
• Regret in online combinatorial optimization
• Self-adjusting binary search trees
• The Nonstochastic Multiarmed Bandit Problem
• The weighted majority algorithm

Cited in

(2)

• Bandits with switching costs, \(T^{2/3}\) regret
• Online learning over a finite action set with limited switching

Describes a project that uses

Uses Software

• AdaBoost.MH

This page was built for publication: Online learning over a finite action set with limited switching

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