Source-linked AI summary
Towards minimax policies for online linear optimization with bandit feedback
Sébastien Bubeck, Nicolò Cesa-Bianchi, Sham M. Kakade
TL;DR
The paper addresses online linear optimization with bandit feedback, where only incurred losses are observed. It combines exponential weights and Mirror Descent to obtain improved regret bounds generally and computationally efficient minimax strategies for the hypercube and Euclidean ball. The results include √(dn log N) regret for finite action sets and specialized efficient bounds for these canonical geometries.
Problem
The paper addresses bandit linear optimization and the gap between general regret optimality and computationally efficient optimal strategies for particular action sets.
Method
The paper uses EXP2 with John’s exploration for finite action sets and Online Stochastic Mirror Descent with geometry-specific regularizers for canonical action-set pairs.
Results
The methods obtain √(dn log N) regret for finite action sets, d√n for an efficient hypercube algorithm, and √(dn log n) for an efficient Euclidean-ball algorithm.
Takeaways & Limitations
Without further assumptions on the action set, EXP2 is optimal, while Mirror Descent supplies efficient optimal-regret strategies for the hypercube and Euclidean ball.
Takeaways & Limitations
EXP2 does not establish optimality for every specific action set, and computing a constant-factor John ellipsoid approximation is NP-hard in general.
Abstract
from arXiv · showhide
We address the online linear optimization problem with bandit feedback. Our contribution is twofold. First, we provide an algorithm (based on exponential weights) with a regret of order $\sqrt{d n \log N}$ for any finite action set with $N$ actions, under the assumption that the instantaneous loss is bounded by 1. This shaves off an extraneous $\sqrt{d}$ factor compared to previous works, and gives a regret bound of order $d \sqrt{n \log n}$ for any compact set of actions. Without further assumptions on the action set, this last bound is minimax optimal up to a logarithmic factor. Interestingly, our result also shows that the minimax regret for bandit linear optimization with expert advice in $d$ dimension is the same as for the basic $d$-armed bandit with expert advice. Our second contribution is to show how to use the Mirror Descent algorithm to obtain computationally efficient strategies with minimax optimal regret bounds in specific examples. More precisely we study two canonical action sets: the hypercube and the Euclidean ball. In the former case, we obtain the first computationally efficient algorithm with a $d \sqrt{n}$ regret, thus improving by a factor $\sqrt{d \log n}$ over the best known result for a computationally efficient algorithm. In the latter case, our approach gives the first algorithm with a $\sqrt{d n \log n}$ regret, again shaving off an extraneous $\sqrt{d}$ compared to previous works.
1 Introduction
The paper studies online linear optimization with bandit feedback, where the player observes only incurred losses, and develops regret-optimal algorithms with improved computational efficiency for specific action sets.
- Problem setting: The bandit setting reveals only the incurred loss, while actions and adversarial loss vectors are chosen each round under a bounded dual pairing.The player seeks to minimize expected cumulative loss and regret.
- EXP2 contribution: EXP2 achieves regret of order √(dn log N) for finite action sets with N actions, improving prior dependence on dimension.The result applies to linear bandits with expert advice and matches the minimax order of the basic d-armed bandit with N experts.
- Limitations of exponential weights: Without further assumptions on the action set, EXP2 is optimal, but exponential weights can be suboptimal for particular action-set and loss-set pairs.Prior work establishes a gap for some pairs, motivating geometry-adaptive alternatives.
- Mirror Descent contribution: Mirror Descent provides an efficient alternative for two canonical geometries: the hypercube with crosspolytope constraints and the Euclidean ball with Euclidean-ball constraints.The paper presents optimal regret bounds for both pairs.
- Specific geometries: For the hypercube, the approach gives the first efficient algorithm with regret of order d√n; for the Euclidean ball, it gives the first efficient algorithm with regret of order √(dn log n).The latter improves the d√(n log n) dependence obtained by an earlier barrier-based approach.
- Algorithmic structure: The paper uses EXP2 and Online Stochastic Mirror Descent, presenting general regret bounds before specializing them to exploration and the two canonical action sets.The organization separates the EXP2 analysis from computationally efficient strategies for the hypercube and Euclidean ball.
2 Algorithms
This section introduces EXP2 and OSMD as the paper’s two algorithmic templates for online linear optimization with bandit feedback, each accompanied by a general regret bound.
- EXP2: EXP2 is presented as an algorithmic template for bandit feedback, with learning rate, mixing coefficient, and an action-set distribution as parameters.The supplied description identifies EXP2 as Expanded Exp and states that its general regret bound is given next.
- EXP2: Theorem 1 gives an EXP2 regret bound for a finite action set of N actions under the condition η|a⊤ezt| ≤ 1 for every action.
- OSMD: OSMD is presented for compact action sets with a differentiable Legendre-Fenchel dual regularizer and a perturbation scheme.Its update can be expressed through Follow The Regularized Leader or mirror gradient descent, with projection implicit in ∇F∗.
- OSMD: The OSMD framework uses the Bregman divergence associated with F, defined as DF(x,y) = F(x) − F(y) − (x − y)⊤∇F(y).
- OSMD: OSMD’s stochastic analysis accounts for randomness in both the action and estimated loss, with gradient mappings simplifying computations when F is Legendre.
3 EXP2 with John’s exploration
The paper introduces John’s exploration for EXP2, deriving improved regret bounds and extending the approach to compact action sets and expert advice. It also discusses preprocessing and computational limitations associated with constructing John’s ellipsoids.
- Exploration construction: John’s exploration is constructed from contact points and a distribution supplied by a convex-geometry result for the minimum-volume enclosing ellipsoid.The preprocessing assumes full rank, centers and transforms the action set, then uses the resulting contact points as valid exploration actions.
- Exploration construction: The loss estimator uses an invertible matrix based on the action distribution and is unbiased because the played action and incurred loss are observed.The estimator is adapted to the scalar product induced by John’s ellipsoid.
- Regret bounds: d√(n log n) regret is obtained for any compact action set through a discretization argument.This extends the finite-action result beyond finite action sets.
- Computational issues: Computational efficiency depends on computing John’s ellipsoid: this is polynomial-time approximable for finite point sets but NP-hard in general for half-space intersections.An efficiently computable alternative replaces a d factor by d3/2 and yields a slightly worse dependence on d in the regret bound.
- Regret bounds: √(dn log N) regret is obtained for online linear optimization with bandit feedback and N experts using EXP2 with John’s exploration.The same order is stated for the expert-advice setting, where it is no worse than the minimax regret for d-armed bandits with expert advice.
4 Computationally efficient strategy for the hypercube
For the hypercube, OSMD uses an entropic regularizer and a randomized perturbation to obtain a computationally efficient regret bound of order d√n.
- 4 Computationally efficient strategy for the hypercube: d√n regret is obtained for the hypercube using a computationally efficient OSMD strategy.The action set is A = {x ∈ R^d : ∥x∥∞ ≤ 1}.
- 4 Computationally efficient strategy for the hypercube: The strategy combines an entropic regularizer with a perturbation of an interior point of the action set.The perturbation mixes random signed canonical-basis actions with Rademacher sampling whose parameter depends on the current point.
- 4 Computationally efficient strategy for the hypercube: The resulting theorem studies the hypercube paired with the crosspolytope, corresponding to L∞/L1 constraints.The theorem states the OSMD setting with A = {x : ∥x∥∞ ≤ 1} and Z = {x : ∥x∥1 ≤ 1}.
- 4 Computationally efficient strategy for the hypercube: The regularizer belongs to the class of Legendre functions with exchangeable Hessian.Its convex-conjugate gradient mapping is used as the inverse of the regularizer’s gradient mapping.
- 4 Computationally efficient strategy for the hypercube: The proof controls the initial regularizer term, Bregman divergence, covariance matrix, eigenvalues, and estimator norm under the stated parameter conditions.The argument uses bounds on D_F∗ and the smallest eigenvalue of the sampling matrix, together with η∥e_z_t∥∞ ≤ 1.
5 Improved regret for the Euclidean ball
For the Euclidean ball, the paper uses OSMD with a barrier-like regularizer and an unbiased perturbation scheme to obtain regret of order √(d n log n).
- 5 Improved regret for the Euclidean ball: √(d n log n) regret is obtained for the Euclidean-ball problem using an efficient OSMD algorithm.The result improves the previously described d√(n log n) bound for this problem.
- 5 Improved regret for the Euclidean ball: The method uses F(x) = −log(1 − ∥x∥) − ∥x∥^s together with a randomized perturbation of an interior point.The perturbation selects either a normalized current point or a randomly signed coordinate vector.
- 5 Improved regret for the Euclidean ball: The perturbation and modified estimator preserve the key unbiasedness property required by the OSMD analysis.The passages state that the perturbation is unbiased and that the estimator satisfies the corresponding key unbiasedness property.
- 5 Improved regret for the Euclidean ball: The theorem considers matching Euclidean-ball action and loss sets.OSMD operates on the shrunk set A′ = {x : ∥x∥ ≤ 1 − γ}.
- 5 Improved regret for the Euclidean ball: Playing on the shrunken action set incurs an additional γn regret term, while the regularizer is shown to be Legendre.The proof then bounds regret relative to A′ using the general OSMD theorem.
- 5 Improved regret for the Euclidean ball: The analysis bounds the relevant regularizer and divergence terms using norm inequalities and the assumed learning-rate condition.The proof reduces the needed inequality to a bound involving ∥u − v∥².