Timezone: »
Poster
Online Learning with Knapsacks: the Best of Both Worlds
Matteo Castiglioni · Andrea Celli · Christian Kroer
We study online learning problems in which a decision maker wants to maximize their expected reward without violating a finite set of $m$ resource constraints. By casting the learning process over a suitably defined space of strategy mixtures, we recover strong duality on a Lagrangian relaxation of the underlying optimization problem, even for general settings with non-convex reward and resource-consumption functions. Then, we provide the first best-of-both-worlds type framework for this setting, with no-regret guarantees both under stochastic and adversarial inputs. Our framework yields the same regret guarantees of prior work in the stochastic case. On the other hand, when budgets grow at least linearly in the time horizon, it allows us to provide a constant competitive ratio in the adversarial case, which improves over the $O(m \log T)$ competitive ratio of Immorlica et al. [FOCS'19]. Moreover, our framework allows the decision maker to handle non-convex reward and cost functions. We provide two game-theoretic applications of our framework to give further evidence of its flexibility.
Author Information
Matteo Castiglioni (Politecnico di Milano)
Andrea Celli (Bocconi University)
Christian Kroer (Columbia University)
Related Events (a corresponding poster, oral, or spotlight)
-
2022 Spotlight: Online Learning with Knapsacks: the Best of Both Worlds »
Thu. Jul 21st 08:45 -- 08:50 PM Room Room 327 - 329
More from the Same Authors
-
2023 Poster: Optimal Rates and Efficient Algorithms for Online Bayesian Persuasion »
Martino Bernasconi · Matteo Castiglioni · Andrea Celli · Alberto Marchesi · Francesco Trovò · Nicola Gatti -
2023 Poster: Online Mechanism Design for Information Acquisition »
Federico Cacciamani · Matteo Castiglioni · Nicola Gatti -
2023 Poster: Statistical Inference and A/B Testing for First-Price Pacing Equilibria »
Luofeng Liao · Christian Kroer -
2023 Poster: Constrained Phi-Equilibria »
Martino Bernasconi · Matteo Castiglioni · Alberto Marchesi · Francesco Trovò · Nicola Gatti -
2022 Poster: Kernelized Multiplicative Weights for 0/1-Polyhedral Games: Bridging the Gap Between Learning in Extensive-Form and Normal-Form Games »
Gabriele Farina · Chung-Wei Lee · Haipeng Luo · Christian Kroer -
2022 Poster: Safe Learning in Tree-Form Sequential Decision Making: Handling Hard and Soft Constraints »
Martino Bernasconi · Federico Cacciamani · Matteo Castiglioni · Alberto Marchesi · Nicola Gatti · Francesco Trovò -
2022 Spotlight: Safe Learning in Tree-Form Sequential Decision Making: Handling Hard and Soft Constraints »
Martino Bernasconi · Federico Cacciamani · Matteo Castiglioni · Alberto Marchesi · Nicola Gatti · Francesco Trovò -
2022 Spotlight: Kernelized Multiplicative Weights for 0/1-Polyhedral Games: Bridging the Gap Between Learning in Extensive-Form and Normal-Form Games »
Gabriele Farina · Chung-Wei Lee · Haipeng Luo · Christian Kroer -
2021 : Invited Speaker: Christian Kroer: Recent Advances in Iterative Methods for Large-Scale Game Solving »
Christian Kroer -
2021 Poster: First-Order Methods for Wasserstein Distributionally Robust MDP »
Julien Grand-Clement · Christian Kroer -
2021 Spotlight: First-Order Methods for Wasserstein Distributionally Robust MDP »
Julien Grand-Clement · Christian Kroer -
2021 Poster: Multi-Receiver Online Bayesian Persuasion »
Matteo Castiglioni · Alberto Marchesi · Andrea Celli · Nicola Gatti -
2021 Spotlight: Multi-Receiver Online Bayesian Persuasion »
Matteo Castiglioni · Alberto Marchesi · Andrea Celli · Nicola Gatti -
2021 Poster: Connecting Optimal Ex-Ante Collusion in Teams to Extensive-Form Correlation: Faster Algorithms and Positive Complexity Results »
Gabriele Farina · Andrea Celli · Nicola Gatti · Tuomas Sandholm -
2021 Spotlight: Connecting Optimal Ex-Ante Collusion in Teams to Extensive-Form Correlation: Faster Algorithms and Positive Complexity Results »
Gabriele Farina · Andrea Celli · Nicola Gatti · Tuomas Sandholm -
2020 Poster: Stochastic Regret Minimization in Extensive-Form Games »
Gabriele Farina · Christian Kroer · Tuomas Sandholm -
2019 Poster: Stable-Predictive Optimistic Counterfactual Regret Minimization »
Gabriele Farina · Christian Kroer · Noam Brown · Tuomas Sandholm -
2019 Poster: Regret Circuits: Composability of Regret Minimizers »
Gabriele Farina · Christian Kroer · Tuomas Sandholm -
2019 Oral: Stable-Predictive Optimistic Counterfactual Regret Minimization »
Gabriele Farina · Christian Kroer · Noam Brown · Tuomas Sandholm -
2019 Oral: Regret Circuits: Composability of Regret Minimizers »
Gabriele Farina · Christian Kroer · Tuomas Sandholm