Abstract
This work addresses the classic machine learning problem of online predictionwith expert advice. We consider the finite-horizon version of this zero-sum,two-person game. Using verification arguments from optimal control theory, weview 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 certainpartial differential equations (PDEs). These sub- and supersolutions serve asthe potentials for player and adversary strategies, which lead to thecorresponding bounds. To get explicit bounds, we use closed-form solutions ofspecific PDEs. Our bounds hold for any given number of experts and horizon; incertain regimes (which we identify) they improve upon the previous state of theart. For two and three experts, our bounds provide the optimal leading orderterm.