Online Non-Additive Path Learning under Full and Partial Information

We consider the online path learning problem in a graph with non-additive gains/losses. Various settings of full information, semi-bandit, and full bandit are explored. We give an efficient implementation of EXP3 algorithm for the full bandit setting with any (non-additive) gain. Then, focusing on the large family of non-additive count-based gains, we construct an intermediate graph which has equivalent gains that are additive. By operating on this intermediate graph, we are able to use algorithms like Component Hedge and ComBand for the first time for non-additive gains. Finally, we apply our methods to the important application of ensemble structured prediction.