Source-linked AI summary
Explore no more: Improved high-probability regret bounds for non-stochastic bandits
Gergely Neu
TL;DR
Non-stochastic bandit algorithms commonly provide expected-regret guarantees, while high-probability actual-regret bounds are harder and have typically relied on costly explicit exploration. This paper uses Implicit eXploration, or IX, to avoid that component and derives improved high-probability guarantees across several bandit settings. The authors conclude that explicit exploration is not necessary, while adaptive high-probability regret bounds remain open under their current analysis.
Problem
High-probability bounds for actual regret are harder than expected pseudo-regret bounds, and common approaches force repeated uniform exploration that can hurt performance.
Method
The paper uses Implicit eXploration, a biased loss-estimation strategy whose estimates are incorporated into an exponential-weights algorithm without explicit exploration.
Results
IX yields high-probability regret bounds for several non-stochastic bandit variants, with tighter bounds, cleaner proofs, and guarantees simultaneous across confidence levels.
Takeaways & Limitations
Explicit exploration is not necessary for high-probability regret bounds in non-stochastic bandit problems.
Takeaways & Limitations
The current analysis permits only deterministic learning-rate and IX-parameter sequences, leaving adaptive high-probability regret bounds as an open challenge.
Abstract
from arXiv · showhide
This work addresses the problem of regret minimization in non-stochastic multi-armed bandit problems, focusing on performance guarantees that hold with high probability. Such results are rather scarce in the literature since proving them requires a large deal of technical effort and significant modifications to the standard, more intuitive algorithms that come only with guarantees that hold on expectation. One of these modifications is forcing the learner to sample arms from the uniform distribution at least $Ω(\sqrt{T})$ times over $T$ rounds, which can adversely affect performance if many of the arms are suboptimal. While it is widely conjectured that this property is essential for proving high-probability regret bounds, we show in this paper that it is possible to achieve such strong results without this undesirable exploration component. Our result relies on a simple and intuitive loss-estimation strategy called Implicit eXploration (IX) that allows a remarkably clean analysis. To demonstrate the flexibility of our technique, we derive several improved high-probability bounds for various extensions of the standard multi-armed bandit framework. Finally, we conduct a simple experiment that illustrates the robustness of our implicit exploration technique.
1 Introduction
The paper studies randomized regret minimization in non-stochastic multi-armed bandits, emphasizing high-probability bounds for actual regret. It challenges the common reliance on repeated uniform exploration by proposing implicit exploration instead.
- Problem setting: The learner selects arms while an environment assigns losses over repeated rounds, forming a sequential non-stochastic bandit game.The environment may be oblivious or adaptive, depending on whether its losses depend on past learner actions.
- Research goal: The paper targets sublinear regret for randomized algorithms because deterministic learners cannot achieve this goal.Randomization makes regret a random variable that must be bounded probabilistically.
- Research gap: High-probability bounds for actual regret are harder than expected pseudo-regret bounds and traditionally require major algorithmic and analytical changes.The established approach commonly forces uniform arm sampling, often Ω(√T) times over T rounds.
- Research gap: Explicit exploration can cause steadily growing regret when many arms have high losses, even after the learner focuses on good arms.The paper notes that such algorithms may perform poorly on simple problems.
- Contribution: The proposed IX strategy removes explicit exploration while supporting high-probability bounds across several non-stochastic bandit extensions.The paper reports cleaner proofs, tighter bounds, and guarantees simultaneous across confidence levels.
2 Explicit and implicit exploration
The section contrasts importance-weighted and explicitly explored estimators with the paper’s implicit-exploration loss estimates. IX uses biased estimates inside an exponential-weights scheme without explicit exploration, yielding lower-confidence control for high-probability analysis.
- Estimation challenge: Standard bandit algorithms replace unobserved losses with estimates computed from the single observed loss, often using an online-learning algorithm as a black box.The central challenge is constructing reliable estimates for every arm from one observation.
- Explicit exploration: Importance-weighted estimates are unbiased when an arm’s selection probability is positive, but their fluctuations can be too large for high-probability actual-regret bounds.The selection probability is conditioned on the learner’s observation history.
- Explicit exploration: Explicit exploration bounds estimator variance by mixing the learner’s distribution with the uniform distribution, but it can harm performance when many arms are poor.This is the rationale behind the exploration parameter in EXP3.P-style methods.
- Implicit exploration: IX adds a positive denominator term to the observed-loss estimator and feeds the resulting estimates into exponential weights without explicit exploration.The strategy was introduced for online learning with side-observations and is adapted here to non-stochastic bandits.
- Implicit exploration: The IX estimates act as lower confidence bounds for true losses, enabling high-probability bounds for multiple bandit variants.The paper applies the approach to bandits with expert advice, tracking the best arm, and side-observations.
3 High-probability regret bounds via implicit exploration
The paper develops high-probability regret guarantees using IX loss estimates, avoiding explicit exploration, and applies the technique across several non-stochastic bandit settings. The resulting bounds improve prior leading constants and, for side-observations, depend on the graph independence number.
- Concentration result: IX provides a concentration result for biased loss estimates, supporting high-probability guarantees under non-increasing parameters and measurable conditions.Lemma 1 assumes γ_t is non-increasing and α_t,i is nonnegative, F_t−1-measurable, and at most 2γ_t; its conclusion holds with probability at least 1 − δ.
- Standard multi-armed bandits: EXP3-IX uses IX estimates in an exponential-weights scheme without explicit exploration.The estimates use a positive denominator adjustment γ_t I{I_t=i}, and the algorithm samples according to weights without mixing an explicit exploration term.
- Bandits with expert advice: EXP4-IX improves the best known leading constant from 6 to 2 for bandits with expert advice, while remaining a factor of 2 worse than EXP4’s pseudo-regret constant.It removes the original algorithm’s explicit exploration component and uses IX estimates to compute expert weights.
- Tracking the best sequence of arms: EXP3-SIX achieves a leading factor of 2 for tracking sequences with switches, improving the previous leading factor of 7.The method adapts Fixed Share and samples arms proportionally to recursively updated weights.
- Bandits with side-observations: For side-observations, EXP3-IX gives a high-probability bound in terms of the graph independence number α and matches the minimax bound up to logarithmic factors.The prior high-probability result scaled with the maximal acyclic subgraph size m, which can be much larger than α.
4 Empirical evaluation
The experiment compares EXP3, EXP3.P, and EXP3-IX in a changing 10-arm Bernoulli bandit environment. EXP3-IX shows stronger empirical performance than EXP3.P and greater robustness than EXP3 in the non-stochastic regime.
- Experimental setting: The experiment uses 10 arms, T = 10^6, and Δ = 0.1, with arm 9 initially best and arm 10 becoming best after T/2.Arms 1–8 have mean loss 1/2; arm 9 has mean loss 1/2 − Δ, while arm 10 changes from 1/2 + Δ to 1/2 − 4Δ.
- Evaluation: Regret is evaluated up to T/2 and T to assess performance before and after the loss-distribution shift.Figure 1 reports empirical means and standard deviations over 50 runs as functions of parameter multipliers.
- Findings: EXP3-IX largely improves empirical performance over EXP3.P and is more robust in the non-stochastic regime than vanilla EXP3.The comparison varies algorithm parameters over a wide multiplier range while using theoretically motivated base learning rates.
5 Discussion
The discussion argues that explicit exploration is unnecessary for high-probability non-stochastic bandit guarantees, while identifying unresolved questions about exploration, adaptivity, and extensions to linear bandits. It also notes alternative estimators that can support most of the presented results.
- Main conclusion: Explicit exploration is not necessary for achieving high-probability regret bounds in non-stochastic bandit problems.The authors nevertheless observe that IX-based algorithms still sample every arm roughly Ω(√T) times without explicitly enforcing this behavior.
- Open questions: Whether pulling every arm Ω(√T) times is necessary for near-optimal guarantees remains an open question.The observed sampling behavior motivates a more complete study of exploration’s role.
- Limitations: The current analysis permits only deterministic learning-rate and IX parameters, leaving high-probability adaptive regret bounds as an open challenge.The paper also notes that tuning the IX parameter may be as difficult in practice as tuning EXP3.P parameters, although γ_t = η_t/2 is recommended.
- Extensions: IX has a natural extension to linear bandits, but whether the resulting estimate is appropriate for that setting remains unresolved.The proposed form uses (P_t + γI)^−1 V_t V_t^T ℓ_t, while the broader question is left for future study.
- Alternative estimators: Alternative loss estimates can achieve the same concentration bound, and all presented results except Theorem 4 can be shown for them as well.One alternative had previously been used for high-probability reward-game bounds, though that proof relied on explicit exploration.
A The proof of Lemma 1
The proof establishes concentration through a supermartingale argument. It bounds the terminal random variable’s expectation and then applies Markov’s inequality to obtain the high-probability statement.
- Bounding the increments: The proof introduces β_t = 2γ_t and bounds the relevant per-round quantity using losses in [0,1].The argument uses the inequality z/(1 + z/2) ≤ log(1 + z) for z ≥ 0.
- Algebraic bounds: A second bound follows from α_t,i ≤ β_t and the inequality x log(1+y) ≤ log(1+xy).The proof also invokes the identity involving Q^K, derived from mutually exclusive arm indicators.
- Supermartingale: The construction forms a supermartingale satisfying E[Z_t | F_{t−1}] ≤ Z_{t−1}, with Z_0 = 1.Consequently, E[Z_T] ≤ 1 after iterating the conditional expectation inequality.
- High-probability conclusion: Markov’s inequality converts E[Z_T] ≤ 1 into a probability bound, and solving exp(−ε) = δ yields the lemma’s statement.The resulting claim holds for any ε > 0 before ε is chosen from δ.
B.1 The proof of Theorem 2
The proof of Theorem 2 combines standard expert-learning bounds with concentration of IX estimates. A union bound provides simultaneous control over experts and yields the theorem’s probability guarantee after parameter substitution.
- Expert comparison: For any fixed expert index m, standard arguments produce an expert-learning inequality involving the distribution π_t(n).The proof introduces π_t(n) = w_t,n divided by the total weight for notational convenience.
- Bounding the remainder: The final term in the bound is controlled using Jensen’s inequality together with p_t,i e^{ℓ_t,i} ≤ 1.These inequalities reduce the contribution of the estimated losses to a tractable expression.
- Simultaneous concentration: Lemma 1 and a union bound give simultaneous validity for all experts with probability at least 1 − δ′.This includes the best expert, which is then inserted into the preceding expert-learning bound.
- Theorem conclusion: The theorem’s bound holds with probability at least 1 − 2δ′, and setting δ′ = δ/2 completes the proof.The final expression uses the prescribed choices of γ and η.
B.2 The proof of Theorem 3
The proof combines prior EXP3-style techniques with concentration bounds, union bounds, and parameter substitutions to establish the theorem with probability at least 1 −δ.
- The argument builds on techniques from Cesa-Bianchi et al. and Auer et al. for the best sequence in C(S).
- A modified theorem from Cesa-Bianchi et al. supplies an intermediate bound for sequences in C(S).
- A union bound combines bounds that hold simultaneously over all sequences J1:T ∈C(S), using a cardinality bound for C(S).
- 1 −2δ′ is the intermediate probability guarantee before setting δ′ = δ/2 and using losses bounded in [0, 1].
- 1 −δ is the resulting probability guarantee after the parameter choice and the remaining theorem-specific bound are combined.
- The concentration step replaces Hoeffding’s inequality with e−z ≤ 1 −z + z2/2 for all z ≥0.
B.3 The proof of Theorem 4
The proof addresses a technical failure of Lemma 1 for this EXP3-IX variant by modifying the concentration argument and tracking the resulting probability and logarithmic terms.
- Lemma 1 does not apply directly to the variant’s loss estimates because of a subtle technical issue.
- The proof’s technical modification changes log(1/δ′) to K log(K/δ′) in the corresponding corollary.
- The proof starts with notation and standard EXP3 analysis, then combines Corollary 1, Hoeffding–Azuma, Lemma 1, and union bounds.
- Freedman’s inequality provides a bound for a martingale-difference sequence with |Xt| ≤K and a conditional-variance control.
- The resulting bound holds with probability at least 1 −δ′ for all ω ≤1/K before being combined with previous bounds.
- 1 −δ is the final stated probability guarantee after invoking a lemma by Kocák et al. and applying the corresponding parameter relation.
- The proof notes that its last term is dominated by the third when T ≥K2/(8α).