BanditRLwiki setting
Delayed and nonstationary bandits
Delayed observations, variation budgets, switch budgets, dynamic comparators, and adaptive detection.
← All settings
Comparison signature
- Problem class. Delayed adversarial or time-varying stochastic bandits
- Feedback. Delayed selected-action feedback
- Objective. External or dynamic regret
- Parameters. Total delay D, variation V_T, switches S, actions A, rounds T
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.
3 cases
delayed-adversarial-bandit
Adversarial bandits with delayed feedbackKnown-delay algorithms attain square-root dependence on rounds and total delay up to logs; local work currently compiles accounting and source-audit interfaces, not a regret endpoint.
Near minimaxPartial local route
delayed feedbackDEXP3DEWDelayed SAPOtotal delayoutstanding feedback
- Loss model
- Adversarial bounded losses
- Delay model
- Per-round delays d_t with total D, or a fixed delay d
- Regret
- Expected external regret
- Target scale
- sqrt((A T + D) log A), with fixed-delay variants
Comparison judgment
Near minimax
The literature has strong delayed-feedback rates. Local declarations prove causal views and accounting identities but not the cited algorithm theorem.
Known gap. Logarithmic factors and the distinction between total-delay and fixed-delay contracts remain visible.
Local Lean boundary
Partial local route
Observed/outstanding partition identities, causal action-time views, active allocation, a nonnegative-domain D.11 core, Algorithm-5 line-10 eliminated-arm initialization, and several Delayed SAPO audit surfaces compile. The central generated delayed process and stochastic/adversarial regret endpoints do not.
Upper bound
Known-delay DEXP3/DEW upper bound
Nonstochastic Multiarmed Bandits with Unrestricted Delays
Tobias Thune, Nicolò Cesa-Bianchi, and Yevgeny Seldin · 2019 · Theorem 1 and Corollary 4
Upper bound guarantee. Formula renderer unavailable; readable fallback: A delayed exponential-weights algorithm has expected regret controlled by the sum of the ordinary bandit term and total delay.\[R_T\le 2\sqrt{(eAT/2+D)\log A}\]Swipe to read the full formula →
Use the source's known-delay or skipping contracts and parameter choice.
Open primary source ↗
Upper bound
Fixed-delay regret upper bound
Delay and Cooperation in Nonstochastic Bandits
Nicolò Cesa-Bianchi, Claudio Gentile, and Yishay Mansour · 2019 · Corollary 15
Upper bound guarantee. Formula renderer unavailable; readable fallback: For fixed delay d, the regret is square-root in A plus d times T, up to log A and an additive delay term.\[R_T=O\!\left(d+\sqrt{(A+d)T\log A}\right).\]Swipe to read the full formula →
Fixed-delay feedback under the source's protocol.
Open primary source ↗
Lower bound
Fixed-delay minimax comparison
Delay and Cooperation in Nonstochastic Bandits
Nicolò Cesa-Bianchi, Claudio Gentile, and Yishay Mansour · 2019 · Fixed-delay minimax comparison
Lower bound guarantee. Formula renderer unavailable; readable fallback: The fixed-delay problem has a square-root lower scale in A plus delay times T.\[R_T=\Omega\!\left(\sqrt{(A+d)T}\right).\]Swipe to read the full formula →
Compare only to upper theorems with the same fixed-delay feedback contract.
Open primary source ↗
Local Lean evidence
Exact declarations
Not yet proved here
Missing steps
- Extend the line-10 initializer into the source EAP/BSC phase transitions and one recursive delayed trajectory that supports out-of-order feedback revelation.
- Resolve the source width-direction audit and instantiate its snapshot hypotheses.
- Prove a source-compatible stochastic or adversarial regret terminal.
formalization frontier
Can the delayed accounting layer be connected to one generated algorithm law and a paper-level regret terminal?
The bookkeeping, causal-view, active-allocation, and conditional source-audit surfaces compile; no algorithm regret theorem is claimed.
- Out-of-order reveal law
- state machine
- width audit
- regret terminal
- Named formalization leaf: DELAYED-TRAJECTORY-LAW
- Named formalization leaf: DELAYED-SAPO-D10-D12
- Named formalization leaf: DELAYED-REGRET-TERMINAL
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
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).\]Swipe to read the full formula →
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).\]Swipe to read the full formula →
Use the source's variation class and horizon/variation range.
Open primary source ↗
Local Lean evidence
Exact declarations
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
nonstationary-best-arm-switch-budget
Unknown best-arm-identity switch budgetArmSwitch is near the square-root best-arm-switch scale, while the current Lean theorem assumes an oracle schedule built from all global mean changes.
Near minimaxPartial local route
piecewise stationaryswitch budgetArmSwitchchange detectionoracle restart
- Reward model
- Nonstationary stochastic means
- Changes
- The identity of the optimal arm changes at most S times, unknown to the learner
- Comparator
- Best arm within each stationary segment
- Target scale
- sqrt(A (S+1) T) up to polylogarithmic factors
Comparison judgment
Near minimax
The upper depends on changes in best-arm identity, not changes in the full reward vector. The local oracle schedule uses every global population-mean change and is therefore only related evidence.
Known gap. ArmSwitch has a polylogarithmic factor. The displayed lower is obtained from a stationary-segment hard family, so the class embedding and its K/horizon conditions remain explicit rather than being called an identical assumption contract.
Local Lean boundary
Partial local route
A generated oracle-restart half-Tsallis theorem with 8 sqrt(A) sqrt(S+1) sqrt(T+1) compiles, but its S counts true global population-mean changes, not only changes in best-arm identity.
Upper bound
ArmSwitch best-arm-switch upper bound
A New Look at Dynamic Regret for Non-Stationary Stochastic Bandits
Yasin Abbasi-Yadkori, András György, and Nevena Lazić · 2023 · Theorem 1
Upper bound guarantee. Formula renderer unavailable; readable fallback: ArmSwitch adapts to an unknown number of changes with square-root switch dependence up to a polylogarithmic factor.\[\mathbb E R_T\le C\sqrt{A(S+1)T}\,[\log(AT\log T)]^{3/2}.\]Swipe to read the full formula →
Use the source's piecewise-stationary model and initialization.
Open primary source ↗
Lower bound
Piecewise-stationary minimax lower bound
A Near-Optimal Change-Detection Based Algorithm for Piecewise-Stationary Combinatorial Semi-Bandits
Zhou, Wang, Varshney, and Lim · 2020 · Theorem 5.1
Lower bound guarantee. Formula renderer unavailable; readable fallback: A piecewise-stationary hard family with N segments forces square-root N A T regret; ordinary multi-armed bandits are a special case of the source model.\[\inf_\pi\sup_\nu\mathbb E R_T(\pi,\nu)=\Omega\!\left(\sqrt{NAT}\right),\qquad N=S+1.\]Swipe to read the full formula →
Use the theorem's A at least 3 and horizon conditions. Mapping N segments to S plus one best-arm regimes is a faithful comparison step, not a verbatim identity of model classes.
Open primary source ↗
Local Lean evidence
Exact declarations
Not yet proved here
Missing steps
- Define a measurable observed-reward change detector and adaptive restart state.
- Control detection delay and false alarms before claiming the unknown-S rate.
- Bridge—or explicitly separate—the best-arm-identity switch contract from the local global-mean-change schedule.
formalization frontier
Can oracle global-mean restarts be replaced by an observed-reward detector under the broader best-arm-identity switch contract?
The local theorem has the desired square-root expression only under a true global-change schedule; ArmSwitch is adaptive under a different, broader change count.
- Assumption bridge
- detector measurability
- false-alarm control
- delay charge
- Named formalization leaf: BEST-ARM-SWITCH-CONTRACT
- Named formalization leaf: OBSERVED-CHANGE-DETECTOR
- Named formalization leaf: ADAPTIVE-RESTART-REGRET