New Potential-Based Bounds for Prediction with Expert Advice
This work addresses a classic online learning problem with incremental theoretical improvements to regret bounds.
The paper tackles the problem of online prediction with expert advice by deriving new lower and upper bounds on regret using potential-based methods from optimal control theory and PDEs. The results improve upon previous state-of-the-art bounds in certain regimes and provide optimal leading-order terms for two and three experts.
This work addresses the classic machine learning problem of online prediction with expert advice. We consider the finite-horizon version of this zero-sum, two-person game. Using verification arguments from optimal control theory, we view the task of finding better lower and upper bounds on the value of the game (regret) as the problem of finding better sub- and supersolutions of certain partial differential equations (PDEs). These sub- and supersolutions serve as the potentials for player and adversary strategies, which lead to the corresponding bounds. To get explicit bounds, we use closed-form solutions of specific PDEs. Our bounds hold for any given number of experts and horizon; in certain regimes (which we identify) they improve upon the previous state of the art. For two and three experts, our bounds provide the optimal leading order term.