What if the rewards are not random at all, but chosen by an adversary who knows your algorithm? Remarkably, a randomized learner can still compete with the best fixed arm in hindsight. Chapters 11–12 of Lattimore–Szepesvári develop the adversarial -armed bandit: rewards are an arbitrary fixed matrix, the learner samples , and regret is measured against . The exponential-weights algorithm Exp3, fed by importance-weighted loss estimates , achieves — the goal theorem. The companion Exp3-IX, which deliberately biases its estimator, upgrades this to a bound holding with high probability rather than only in expectation. These results are the foundation of all adversarial online learning with partial feedback.
theorem BanditAlgorithm.adversarial_bandit_exp3_regret_bound
{k : ℕ} (hk : 1 < k) (n : ℕ) (hn : 0 < n)
(x : ℕ → Fin k → ℝ) (hx : ∀ t : ℕ, ∀ i : Fin k, x t i ∈ Set.Icc (0 : ℝ) 1)
(π : BanditPolicy k)
(hπ : IsExp3Policy (Real.sqrt (2 * Real.log k / (n * k))) π) :
adversarialRegret n x π ≤ Real.sqrt (2 * n * k * Real.log k) := by
sorry
(Exp3, improved bound, GOAL) Let be an adversarial bandit with arms and horizon , and let be Exp3 with learning rate . Then
No open leaves. Every sub-goal is proved or awaiting decomposition.