Regret in online combinatorial optimization
From MaRDI portal
Publication:5169692
Abstract: We address online linear optimization problems when the possible actions of the decision maker are represented by binary vectors. The regret of the decision maker is the difference between her realized loss and the best loss she would have achieved by picking, in hindsight, the best possible action. Our goal is to understand the magnitude of the best possible (minimax) regret. We study the problem under three different assumptions for the feedback the decision maker receives: full information, and the partial information models of the so-called "semi-bandit" and "bandit" problems. Combining the Mirror Descent algorithm and the INF (Implicitely Normalized Forecaster) strategy, we are able to prove optimal bounds for the semi-bandit case. We also recover the optimal bounds for the full information setting. In the bandit case we discuss existing results in light of a new lower bound, and suggest a conjecture on the optimal regret in that case. Finally we also prove that the standard exponentially weighted average forecaster is provably suboptimal in the setting of online combinatorial optimization.
Recommendations
Cited in
(49)- Regret to the best vs. regret to the average
- Regret in the on-line decision problem
- Regret bounds for sleeping experts and bandits
- Online learning for min-max discrete problems
- An inverse optimization approach for a capacitated vehicle routing problem
- Regret bounded by gradual variation for online convex optimization
- Maximin effects in inhomogeneous large-scale data
- Decentralized online integer programming problems with a coupling cardinality constraint
- Regrets of proximal method of multipliers for online non-convex optimization with long term constraints
- Combinatorial optimization. Abstracts from the workshop held November 7--13, 2021 (hybrid meeting)
- Regret bounds and minimax policies under partial monitoring
- Online prediction problems with variation
- Simple regret optimization in online planning for Markov decision processes
- Gains and losses are fundamentally different in regret minimization: the sparse case
- Sequential decision making with vector outcomes
- Combinatorial bandits
- Beyond the hazard rate: more perturbation algorithms for adversarial multi-armed bandits
- Multi-player bandits: the adversarial case
- Learning to optimize via information-directed sampling
- Sequential interdiction with incomplete information and learning
- Game of thrones: fully distributed learning for multiplayer bandits
- Online learning over a finite action set with limited switching
- Efficient online linear optimization with approximation algorithms
- Nested-Batch-Mode Learning and Stochastic Optimization with An Application to Sequential MultiStage Testing in Materials Science
- Efficient algorithms for online decision problems.
- scientific article; zbMATH DE number 7064051 (Why is no real title available?)
- Near-optimal algorithms for online matrix prediction
- Small-Loss Bounds for Online Learning with Partial Information
- Internal regret in on-line portfolio selection
- Internal regret in on-line portfolio selection
- Unifying mirror descent and dual averaging
- The role of optimization in some recent advances in data-driven decision-making
- Adversarial bandits with knapsacks
- A study of distributionally robust mixed-integer programming with Wasserstein metric: on the value of incomplete data
- A unified analysis of nonstochastic delayed feedback for combinatorial semi-bandits, linear bandits, and MDPs
- Optimal sequential stochastic shortest path interdiction
- Robust matroid bandit optimization: near-optimal rates under adversarial contamination
- Robust matroid bandit optimization against adversarial contamination
- Railway crew planning with fairness over time
- Eldan's stochastic localization and the KLS conjecture: isoperimetry, concentration and mixing
- Follow-the-perturbed-leader achieves best-of-both-worlds for bandit problems
- Top-k combinatorial bandits with full-bandit feedback
- First-order Bayesian regret analysis of Thompson sampling
- An efficient algorithm for cooperative semi-bandits
- Asymptotically optimal strategies for combinatorial semi-bandits in polynomial time
- Stochastic top-K subset bandits with linear space and non-linear feedback
- Scale-free adversarial multi armed bandits
- Online linear optimization with sparsity constraints
- Convergence to equilibrium of no-regret dynamics in congestion games
This page was built for publication: Regret in online combinatorial optimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5169692)
