Relaxing the i.i.d. assumption: Adaptively minimax optimal regret via root-entropic regularization
放宽独立同分布假设:通过平方根熵正则化实现自适应极小极大遗憾
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…