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

BanditRLwiki case · delayed-adversarial-bandit

Adversarial bandits with delayed feedback

Known-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.

← Delayed and nonstationary bandits

Audited comparison

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
Open stable case page →Faithful restatement
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. A delayed exponential-weights algorithm has expected regret controlled by the sum of the ordinary bandit term and total delay.

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. For fixed delay d, the regret is square-root in A plus d times T, up to log A and an additive delay term.

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. The fixed-delay problem has a square-root lower scale in A plus delay times T.

Compare only to upper theorems with the same fixed-delay feedback contract.

Open primary source

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

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