Adaptive largest-surviving-coordinate adversary
DefinitionAltRegret_Supplement_IsHarmonicAdversaryalgorithmic-game-theoryonline-convex-optimizationonline-learningp2o-gran-per-chapterp2o-plan-paperp2o-v1regret
Starting from , on round the adversary observes the current simplex action , removes a coordinate , and assigns cost to the surviving coordinates and to all removed coordinates. From round onward it repeats .
The predicate records the surviving sets, maximizing coordinates, updates, and costs, so the dependence on the currently observed action—and the absence of dependence on future actions—is explicit.
Definition code
import Mathlib
import Definitions.Def_AltRegret_altRegretAgainst
namespace AltRegret.Supplement
/-- The adaptive adversary used in Theorem 6: after seeing `x_t`, it removes a largest-mass
surviving coordinate and assigns `-1` to survivors and `+1` to removed coordinates. -/
def IsHarmonicAdversary {d : ℕ} (x : ℕ → Fin d → ℝ) (c : ℕ → Fin d → ℝ) : Prop :=
∃ (S : ℕ → Finset (Fin d)) (j : ℕ → Fin d),
S 0 = Finset.univ ∧
(∀ t, 1 ≤ t → t ≤ d - 1 →
j t ∈ S (t - 1) ∧
(∀ i ∈ S (t - 1), x t i ≤ x t (j t)) ∧
S t = (S (t - 1)).erase (j t) ∧
∀ i, c t i = if i ∈ S t then -1 else 1) ∧
(∀ t, d ≤ t → c t = c (d - 1))
end AltRegret.Supplement
Source
Tao, Zheng, Optimal Alternating Regret for Online Learning and Games, arXiv:2608.24731, proof of Theorem 6, p.9