Adversarial bandits with knapsacks

DOI10.1145/3557045MaRDI QIDQ6551256FDOQ6551256

Authors Nicole Immorlica, Karthik Abinav Sankararaman, Robert E. Schapire, Aleksandrs Slivkins

Publication date 6 June 2024

Published in Journal of the ACM (Search for Journal in Brave)

zbMATH Keywords

competitive ratioregretmulti-armed banditsprimal-dual algorithmsadversarial banditsbandits with knapsacks

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Online algorithms; streaming algorithms (68W27) Applications of mathematical programming (90C90) Applications of game theory (91A80)

Recommendations

• Bandits with knapsacks
• Algorithms for adversarial bandit problems with multiple plays
• The Nonstochastic Multiarmed Bandit Problem
• A Knapsack Secretary Problem with Applications
• Bandits with global convex constraints and objective

Cites work

• scientific article; zbMATH DE number 2107836 (Why is no real title available?)
• A Polylogarithmic-Competitive Algorithm for the k-Server Problem
• A decision-theoretic generalization of on-line learning and an application to boosting
• A dynamic near-optimal algorithm for online linear programming
• A simple parallel algorithm with an \(O(1/t)\) convergence rate for general convex programs
• AdWords and generalized online matching
• Adaptive game playing using multiplicative weights
• An Online Convex Optimization Approach to Proactive Network Resource Allocation
• Approximation Algorithms for Correlated Knapsacks and Non-martingale Bandits
• Approximation algorithms for combinatorial problems
• Bandits with global convex constraints and objective
• Bandits with knapsacks
• Blind network revenue management
• Boosting. Foundations and algorithms.
• Close the gaps: a learning-while-doing algorithm for single-product revenue management problems
• Competitive paging algorithms
• Dynamic pricing without knowing the demand function: risk bounds and near-optimal algorithms
• Electrical flows, Laplacian systems, and faster approximation of maximum flow in undirected graphs
• Expander flows, geometric embeddings and graph partitioning
• Importance weighting without importance weights: an efficient algorithm for combinatorial semi-bandits
• Introduction to multi-armed bandits
• Jointly private convex programming
• Kernel-based methods for bandit convex optimization
• Lectures on modern convex optimization. Analysis, algorithms, and engineering applications
• Multi-armed Bandits with Metric Switching Costs
• Multi-armed bandit allocation indices. With a foreword by Peter Whittle.
• Near optimal online algorithms and fast approximation algorithms for resource allocation problems
• Near-optimal no-regret algorithms for zero-sum games
• On the ratio of optimal integral and fractional covers
• Online convex optimization in the bandit setting: gradient descent without a gradient
• Online matching and ad allocation
• Online network design algorithms via hierarchical decompositions
• Online primal-dual algorithms for covering and packing
• Online stochastic packing applied to display ad allocation
• Prediction, Learning, and Games
• Regret analysis of stochastic and nonstochastic multi-armed bandit problems
• Regret in online combinatorial optimization
• Stochastic bandits robust to adversarial corruptions
• The Design of Competitive Online Algorithms via a Primal—Dual Approach
• The Nonstochastic Multiarmed Bandit Problem
• The design of approximation algorithms
• The multiplicative weights update method: a meta-algorithm and applications
• The on-line shortest path problem under partial monitoring
• The online set cover problem
• The weighted majority algorithm
• Trading regret for efficiency: online convex optimization with long term constraints
• Watch and learn: optimizing from revealed preferences feedback

Cited in

(1)

• An \(\alpha \)-regret analysis of adversarial bilateral trade

This page was built for publication: Adversarial bandits with knapsacks

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