Relaxing the I.I.D. Assumption: Adaptively Minimax Optimal Regret via Root-Entropic Regularization

Understand

We consider prediction with expert advice when data are generated from distributions varying arbitrarily within an unknown constraint set.

• This semi-adversarial setting includes (at the extremes) the classical i.i.d.
• setting, when the unknown constraint set is restricted to be a singleton, and the unconstrained adversarial setting, when the constraint set is the set of all distributions.
• The Hedge algorithm -- long known to be minimax (rate) optimal in the adversarial regime -- was recently shown to be simultaneously minimax optimal for i.i.d.