BanditRLwiki setting
Adversarial and best-of-both-worlds bandits
External regret for bounded adversarial losses and algorithms that adapt to stochastic structure.
← All settings
Comparison signature
- Problem class. Finite action adversarial or self-bounding loss sequences
- Feedback. Bandit loss feedback
- Objective. Expected or high-probability external regret
- Parameters. A actions, T rounds, optional gaps Delta
Matching rule. A rate is called matched only when the upper and lower theorem contracts agree on the fields above; every remaining mismatch is named in the case.
2 cases
adversarial-exp3
EXP3 expected regret versus the adversarial minimax rateClassical EXP3 is near minimax but carries a square-root log A factor relative to the adversarial lower bound.
Near minimaxPartial local route
EXP3adversarialexternal regretexpected regretnear minimax
- Loss model
- Oblivious or predictable losses in [0,1]
- Feedback
- Selected-action bandit loss
- Regret
- Expected external regret to the best fixed action
- Target scale
- sqrt(A T)
Comparison judgment
Near minimax
The source contains both the EXP3 upper route and an adversarial lower bound. The local generated expected EXP3 endpoint compiles.
Known gap. EXP3 has a multiplicative square-root log A gap; removing it requires a different regularizer such as INF/Tsallis-INF, not a relabeling of EXP3.
Local Lean boundary
Partial local route
The generated predictable EXP3 process compiles an explicit 4 sqrt(A T log A) expected bound under its tuning condition, together with several separately scoped tail routes. The adversarial minimax lower terminal is not compiled.
Upper bound
EXP3 expected-regret upper bound
The Nonstochastic Multiarmed Bandit Problem
Peter Auer, Nicolò Cesa-Bianchi, Yoav Freund, and Robert Schapire · 2002 · EXP3 expected-regret theorem
Upper bound guarantee. Formula renderer unavailable; readable fallback: EXP3 achieves expected regret of order square root A T log A against bounded adversarial rewards.\[\mathbb E R_T=O\!\left(\sqrt{AT\log A}\right).\]Swipe to read the full formula →
Finite actions and the source's learning-rate tuning.
Open primary source ↗
Lower bound
Adversarial minimax lower bound
The Nonstochastic Multiarmed Bandit Problem
Peter Auer, Nicolò Cesa-Bianchi, Yoav Freund, and Robert Schapire · 2002 · Section 5 lower bound
Lower bound guarantee. Formula renderer unavailable; readable fallback: Every bandit algorithm suffers expected regret of order at least square root A T on some adversarial loss sequence.\[\inf_\pi\sup_\ell\mathbb E R_T(\pi,\ell)=\Omega\!\left(\sqrt{AT}\right).\]Swipe to read the full formula →
Finite actions under the source's horizon range.
Open primary source ↗
Local Lean evidence
Exact declarations
Not yet proved here
Missing steps
- Pair the corrected high-probability lower terminal with the upper route under one exact regret contract.
- Keep fixed-horizon, all-positive-prefix, and horizon-free tuning contracts distinct.
- Use a minimax-optimal algorithm route if the log A factor is to be removed.
formalization frontier
Can the local adversarial upper route be paired with a compiled minimax lower terminal under one exact regret contract?
The EXP3 upper compiles; corrected Chapter 17 Theorem 17.4 now passes focused compilation with δ ≤ 1/32, c=1/160 and C=64; full local gates pass.
- matched upper/lower regret contract; corrected Chapter 17 high-probability construction is compiled
- Named formalization leaf: CH17-CLIPPED-NORMAL-LAW
- Named formalization leaf: CH17-CLAIM-17-6
- Named formalization leaf: CH17-CLAIM-17-7
- Named formalization leaf: CH17-THM-17-4
adversarial-stochastic-best-of-both-worlds
Tsallis-INF best of stochastic and adversarial worldsOne Tsallis-INF algorithm attains the adversarial square-root rate and stochastic gap-dependent logarithmic regret.
Near minimaxPartial local route
Tsallis-INFbest of both worldsFTRLself boundingstochastic gaps
- Loss model
- Bounded adversarial losses or a stochastic/self-bounding gap condition
- Algorithm identity
- The same Tsallis-INF estimator and scheduler across regimes
- Regret
- Expected pseudo-regret/external regret as stated by the source
- Target scales
- sqrt(A T) adversarial and sum log(T)/Delta_a stochastic
Comparison judgment
Near minimax
The source theorem is genuinely best-of-both-worlds at the displayed rate scale. This card does not claim asymptotic instance optimality or an exact stochastic information constant; the local paper-identity and unified paired terminal remain open.
Known gap. The adversarial branch is minimax-rate optimal within universal constants, while the self-bounding stochastic branch is gap-log rate optimal within constants and is not an exact Lai–Robbins leading-constant result. The local routes also lack identity with the paper's single algorithm across both regimes.
Local Lean boundary
Partial local route
BanditRLlib compiles half-Tsallis IID logarithmic, corruption, drifting-mean, and oracle-restart terminals. It does not claim that one local generated policy is definitionally the paper algorithm with both optimal source guarantees.
Upper bound
Tsallis-INF best-of-both-worlds upper bounds
Tsallis-INF: An Optimal Algorithm for Stochastic and Adversarial Bandits
Julian Zimmert and Yevgeny Seldin · 2021 · Theorem 1
Upper bound guarantee. Formula renderer unavailable; readable fallback: The same Tsallis-INF construction has a minimax-order adversarial bound and a logarithmic gap-dependent stochastic bound.\[R_T\le 4\sqrt{AT}+1\quad\text{and}\quad R_T=O\!\left(\sum_{a\ne *}\frac{\log T}{\Delta_a}\right).\]Swipe to read the full formula →
The exact constants and lower-order terms depend on the importance-weighted or reduced-variance estimator variant.
Open primary source ↗
Lower bound
Rate-optimality comparison used by the Tsallis-INF analysis
Tsallis-INF: An Optimal Algorithm for Stochastic and Adversarial Bandits
Julian Zimmert and Yevgeny Seldin · 2021 · Lower-bound comparisons summarized with Theorem 1
Lower bound guarantee. Formula renderer unavailable; readable fallback: The adversarial minimax and stochastic information lower bounds supply the comparison scales used by the source.\[R_T=\Omega(\sqrt{AT})\quad\text{and}\quad \liminf\frac{R_T}{\log T}\ge \sum_{a\ne *}\frac{\Delta_a}{\mathrm{kl}(\mu_a,\mu_*)}.\]Swipe to read the full formula →
The stochastic lower constant is model dependent; do not identify a generic gap-only upper with the exact Bernoulli information constant.
Open primary source ↗
Local Lean evidence
Exact declarations
Not yet proved here
Missing steps
- Prove the exact estimator, regularizer, and learning-rate identity with the source algorithm.
- Package the stochastic and adversarial guarantees for the same generated policy.
- Audit paper-sharp constants and high-probability or realized-regret variants separately.
formalization frontier
Can one local generated half-Tsallis policy be shown identical to paper Tsallis-INF and carry both source guarantees?
Several strong local endpoints compile, but they are not yet a unified source-identity theorem.
- Estimator identity
- scheduler identity
- same-policy paired theorem
- constant audit
- Named formalization leaf: TSALLIS-INF-PAPER-IDENTITY
- Named formalization leaf: TSALLIS-INF-SAME-POLICY-BOBW