Using Proposition 1 of Mourtada and Gaïffas [42]: max µ∈∆ A E ∑⟨ct, ˆµt −µ⟩ ≤ p TlogA and consequently we have that E[Rhedge]≤max µ∈∆ A E ∑⟨ct, ˆµt −µ⟩ +O( √ T)≤ p TlogA+O( √ T)

Adversarial Setting:Assumption A1 ensures the gap isO( √ T)