BanditRLlib
Lean gate passed before this site build; local proof declarations are shown as compiled.Lean-verified build · exact declarations linked.

BanditRLwiki case · adversarial-stochastic-best-of-both-worlds

Tsallis-INF best of stochastic and adversarial worlds

One Tsallis-INF algorithm attains the adversarial square-root rate and stochastic gap-dependent logarithmic regret.

← Adversarial and best-of-both-worlds bandits

Audited comparison

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
Open stable case page →Faithful restatement
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. The same Tsallis-INF construction has a minimax-order adversarial bound and a logarithmic gap-dependent stochastic bound.

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. The adversarial minimax and stochastic information lower bounds supply the comparison scales used by the source.

The stochastic lower constant is model dependent; do not identify a generic gap-only upper with the exact Bernoulli information constant.

Open primary source

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

Improve this case

Corrections should preserve the comparison signature and cite a primary theorem, theorem number, source edition, and exact gap being closed. Lean contributions should target one named missing leaf without weakening the mathematical contract.

Propose a sourced update