Source-linked AI summary
Regret in Online Combinatorial Optimization
Jean-Yves Audibert, Sébastien Bubeck, Gábor Lugosi
TL;DR
The paper asks how minimax regret scales for online optimization with fixed-size binary actions under full-information, semi-bandit, and bandit feedback. It brings several algorithms under mirror descent and improves semi-bandit upper bounds while proving a new bandit lower bound and identifying the bandit optimum as conjectural.
Problem
The paper studies the order of minimax regret for fixed-size binary actions with bounded coordinate losses under three feedback models.
Source: §1 · p. 2Method
It unifies online combinatorial optimization strategies through mirror descent and develops Online Stochastic Mirror Descent using unbiased loss estimates.
Source: §2.2 · pp. 6, 8Results
The paper improves known semi-bandit upper bounds, proves EXP2 suboptimal, and establishes a new bandit minimax lower bound while conjecturing the optimal order.
Source: §1.3 · p. 5, §4 · p. 13Takeaways & Limitations
In bandit feedback, improving the upper bound seems to require substantially new ideas.
Source: §4 · p. 13For bandit feedback, improving the upper bound seems to require substantially new ideas.
Source: §4 · p. 13
Abstract
from arXiv · showhide
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.
1 Introduction.
The paper studies online linear optimization with fixed-size binary actions and bounded coordinate losses, asking how minimax regret depends on the feedback available. It unifies algorithms through mirror descent and develops improved semi-bandit bounds while examining full-information and bandit results.
1 Introduction.
- Actions are fixed-size binary vectors with coordinate losses in [0, 1]; the paper compares full-information, semi-bandit, and bandit feedback.The objective is the order of magnitude of minimax regret across these feedback assumptions.Source: §1 · p. 2, §1.3 · p. 4
1.1 Motivating examples.
- Online shortest path is an instance: each action is a path, its loss sums edge delays, and all valid paths are assumed to have length m.Ranking selection and choosing m items are other motivating examples.Source: §1.1 · pp. 2–3
1.2 Previous work.
- Prior work had optimal full-information bounds and near-optimal semi-bandit results for m-sets and ranking, while optimal bandit dependence on d and m remained open.The paper situates its bandit lower bound alongside existing bounds.Source: §1.2 · p. 4
1.3 Contribution and contents of the paper.
- The paper unifies several online combinatorial optimization algorithms under mirror descent, improves semi-bandit upper bounds, and proves lower bounds including EXP2's suboptimality.It also gives a new bandit minimax lower bound and conjectures the optimal regret order.Source: §1.3 · pp. 4–5
2 Algorithms.
The section introduces EXP2, which treats each combinatorial action as an expert, and shows that it is suboptimal. It then presents OSMD, a stochastic mirror-descent method with a general regret bound that underlies improved semi-bandit bounds.
2.1 Expanded Exponential weights (EXP2)
- EXP2 treats each action as an independent expert and applies an exponentially weighted average forecaster; in bandit settings it is mixed with an exploration distribution.The strategy is also called Expanded Hedge in the full-information setting.Source: §2.1 · pp. 5–6
- EXP2 is provably suboptimal in full-information online combinatorial optimization, despite an open question about whether its regret bound could be improved to the optimal order.The section contrasts EXP2 with Mirror Descent using negative entropy, for which an optimal bound is available.Source: §2.1 · p. 6
2.2 Online Stochastic Mirror Descent.
- OSMD performs gradient updates in the dual space defined by a Legendre function, using an unbiased gradient estimate rather than the true gradient.Its name combines Mirror Descent, stochastic gradient estimation, and online optimization.Source: §2.2 · p. 6
- OSMD is efficient when the convex hull of the action set has a polynomial-size constraint description, but this condition fails for some important examples, including paths on general graphs.The section restricts its analysis to binary action vectors and linear losses, while noting that OSMD's definition is not limited to this form.Source: §2.2 · p. 8
- Under its consistency condition and unbiased loss estimates, OSMD satisfies a regret bound expressed through the Bregman divergence of the dual function.The theorem is the basis for the paper's improved semi-bandit regret bounds.Source: §2.2 · p. 8
3 Semi-bandit feedback.
This section develops OSMD with potential-based regularization for semi-bandit feedback, using an unbiased loss estimate to obtain regret guarantees. Generalizing INF to combinatorial actions removes the logarithmic factor in the earlier upper bound, and the paper identifies a minimax-optimal strategy.
3 Semi-bandit feedback.
- The semi-bandit loss estimate uses only played-coordinate losses and is unbiased with respect to the random draw of the action.Its expectation over actions equals the loss vector coordinatewise.Source: §3 · p. 10
- The earlier upper bound had an extraneous logarithmic factor over the √(mdn) lower bound; generalizing INF to combinatorial actions removes it.The lower bound follows from the multi-armed bandit case, where A is the canonical basis.Source: §3 · p. 11
- OSMD with Fψ generalizes INF with potential ψ, and the algorithms coincide when the action set is the canonical basis.The paper also notes that ψ(x) = exp(x) recovers negative entropy for Fψ.Source: §3 · p. 12
- Theorem 4 gives a regret bound for OSMD with Fψ for any potential and any non-negative unbiased loss estimate.The section states that an appropriate choice of potential and estimate yields a minimax-optimal strategy.Source: §3 · pp. 10, 12
4 Bandit feedback.
Bandit feedback requires exploration, and existing upper bounds remain above the new minimax lower bound. The authors conjecture the lower bound gives the correct regret order, but closing the gap appears to require new ideas.
4 Bandit feedback.
- Existing bandit algorithms add exploration: EXP2 mixes in a fixed distribution, while OSMD perturbs its point before selecting an action.The cited John’s exploration approach yields the best known upper bound for this setting, but it remains above the lower bound.Source: §4 · p. 13
- No strategy can beat the paper’s bandit minimax lower bound, which the authors conjecture has the correct order of magnitude.Unlike the EXP2-specific limitation in Theorem 1, this bound applies to all strategies.Source: §4 · pp. 13–14
- The lower-bound and upper-bound orders remain separated by a factor of m, and improving the upper bound seems to require substantially new ideas.The authors conjecture minimax regret of order m√(dn); they point to OSMD with a non-diagonal Hessian as a promising direction.Source: §4 · pp. 13–14
A Proof of Theorem 1.
The proof constructs action sets and adversaries showing that EXP2 incurs substantial regret for every learning-rate choice. It uses two adversarial constructions to establish separate lower bounds.
A Proof of Theorem 1.
- The proof considers actions that select d/4 elements from the first half of coordinates and one of two disjoint intervals in the second half.The construction assumes d is a multiple of 4 and n is even.Source: A Proof of Theorem 1 · p. 14
- The proof combines the two adversarial constructions to establish a regret lower bound for EXP2 across learning-rate choices.The supplied theorem-proof passages state separate bounds but do not provide their complete expressions.Source: A Proof of Theorem 1 · p. 14
- An alternating adversary assigns losses to one of the two second-half intervals on alternating rounds, while the first half always has zero loss.At odd rounds the vertices have equal cumulative loss, so EXP2 selects uniformly; at even rounds the probability of selecting the currently costly interval depends on η.Source: A Proof of Theorem 1 · p. 15
- A second adversary assigns loss 1−ε to the first d/4 coordinates and loss 1 to the next d/4, leaving the remaining coordinates at zero.The construction is used to establish a further lower bound, with ε fixed positive.Source: A Proof of Theorem 1 · p. 15
B Proof of Theorem 5
The proof of Theorem 5 uses random adversaries and information inequalities to derive a bandit regret lower bound. It handles deterministic players first, then extends the argument to randomized players.
B Proof of Theorem 5
- Pinsker’s inequality reduces the lower-bound argument to bounding KL divergence between observations under paired adversaries.The proof uses a chain-rule calculation for the observed-loss distributions.Source: B Proof of Theorem 5 · pp. 16–18
- The proof’s central technical step is controlling the relevant KL divergences for the adversarial constructions.The authors identify this bound as the key conceptual difference from the earlier m=1 proof [3, Theorem 30].Source: B Proof of Theorem 5 · p. 16
- Random adversaries indexed by α make the selected action in each of m parallel games slightly better in expectation than the alternatives.The proof identifies the combinatorial action set with m games, each having d/m actions.Source: B Proof of Theorem 5 · pp. 16–17
- For deterministic players, the observed-loss sequence determines the empirical play distribution, enabling comparison of the paired adversary distributions.The proof then uses Fubini’s theorem to extend the result to randomized players.Source: B Proof of Theorem 5 · p. 18
C Technical lemmas.
The technical appendix supplies inequalities used in the lower-bound proof, including a bound for sums of Bernoulli variables. Its proofs use case analysis and elementary distributional estimates.
C Technical lemmas.
- For large k, the proof verifies the bound using numerical checking for k≤10^6 and estimates based on χ for larger k.It uses Stirling’s formula and a comparison of χ values in the large-k argument.Source: C Technical lemmas · p. 19
- Lemma 3 bounds a ratio involving sums of independent Bernoulli variables under specified parameter changes.The proof divides into cases according to whether q equals p′ or p.Source: C Technical lemmas · pp. 19–21
- The lemma proof compares the distributions through a chain-rule KL inequality and decomposes the Bernoulli sums into independent components.The decomposition isolates S, T, and V before bounding the resulting probabilities.Source: C Technical lemmas · p. 20
- Lemma 5 establishes an inequality by analyzing the derivative of an auxiliary function on [x0,∞).The derivative changes sign at 1, yielding nonnegativity of the function on the stated domain.Source: C Technical lemmas · pp. 19, 21