BanditRLwiki case · nonstationary-variation-budget

Variation-budget nonstationary stochastic bandits

Restarted EXP3 is near minimax for dynamic regret under a known total-variation budget.

Audited comparison

nonstationary-variation-budget Variation-budget nonstationary stochastic banditsRestarted EXP3 is near minimax for dynamic regret under a known total-variation budget. Near minimaxPartial local route

Open stable case page →Exact source theorem

nonstationaryvariation budgetRexp3dynamic regretrestart

Reward model: Time-varying stochastic arm means
Variation: V_T equals the sum of roundwise maximum mean changes
Comparator: Roundwise best arm dynamic oracle
Target scale: (A V_T)^(1/3) T^(2/3)

Comparison judgment

Near minimax

The published upper and lower exponents match. The local drifting-mean Tsallis theorem is related but is not the V_T minimax theorem.

Known gap. Rexp3 has a (log A)^(1/3) factor and assumes variation-budget tuning.

Local Lean boundary

Partial local route

A drifting-mean half-Tsallis dynamic-regret envelope compiles, but it is not a formal variation-budget Rexp3 theorem and does not close the minimax comparison.

Upper bound

Rexp3 variation-budget upper bound

Stochastic Multi-Armed-Bandit Problem with Non-stationary Rewards

Omar Besbes, Yonatan Gur, and Assaf Zeevi · 2014 · Theorem 2

Upper bound guarantee. Formula renderer unavailable; readable fallback: Rexp3 has dynamic regret of order cube root A log A times variation, multiplied by T to the two thirds.\[R_T=O\!\left((A\log A\,V_T)^{1/3}T^{2/3}\right).\]

The block length uses the source's known variation budget and parameter range.

Open primary source

Lower bound

Variation-budget dynamic-regret lower bound

Stochastic Multi-Armed-Bandit Problem with Non-stationary Rewards

Omar Besbes, Yonatan Gur, and Assaf Zeevi · 2014 · Theorem 1

Lower bound guarantee. Formula renderer unavailable; readable fallback: Every policy incurs dynamic regret at the cube-root variation-budget scale on some admissible nonstationary environment.\[\inf_\pi\sup_{\nu:\,V_T(\nu)\le V}\mathbb E R_T(\pi,\nu)=\Omega\!\left((AV)^{1/3}T^{2/3}\right).\]

Use the source's variation class and horizon/variation range.

Open primary source

Local Lean evidence

Exact declarations

BanditRLProof.Tsallis.integral_sampledScheduledHalfTsallisFiniteArmIndependentDriftingMeanDynamicRegret_le_allRegimes

Not yet proved here

Missing steps

Define the formal variation budget and block restart policy.
Prove the dynamic-oracle decomposition for Rexp3.
Optimize the block length and compile the matching V_T rate.

formalization frontier

Can the current dynamic-regret envelope be specialized to the exact variation-budget Rexp3 theorem?

A related drifting-mean theorem compiles, but its contract and rate are not the source minimax V_T result.

Variation measure
restart construction
oracle decomposition
rate optimization
Named formalization leaf: VARIATION-BUDGET-DEFINITION
Named formalization leaf: REXP3-BLOCK-RESTART
Named formalization leaf: REXP3-DYNAMIC-REGRET

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