Online Dynamic Programming
We consider the problem of repeatedly solving a variant of the same dynamic programming problem in successive trials. An instance of the type of problems we consider is to find a good binary search tree in a changing environment. At the beginning of each trial, the learner probabilistically chooses a tree with the n keys at the internal nodes and the n + 1 gaps between keys at the leaves. The learner is then told the frequencies of the keys and gaps and is charged by the average search cost for the chosen tree. The problem is online because the frequencies can change between trials. The goal is to develop algorithms with the property that their total average search cost (loss) in all trials is close to the total loss of the best tree chosen in hindsight for all trials. The challenge, of course, is that the algorithm has to deal with exponential number of trees. We develop a general methodology for tackling such problems for a wide class of dynamic programming algorithms. Our framework allows us to extend online learning algorithms like Hedge [16] and Component Hedge [25] to a significantly wider class of combinatorial objects than was possible before.
The aim of this paper is to extend results in online combinatorial optimization to new combinatorial objects such as $k$-multipaths and binary search trees. Specifically, the authors are interested in extending Expanded-Hedge (EH) and Component Hedge (CH) to online combinatorial games, for which the offline problem can be solved in a bottom-up way using Dynamic Programming. 
Though the results about online optimization with $k$-multipaths are interesting, the overall paper could benefit from more polishing: some definitions and notations are not clearly defined, and some assertions look incorrect. Namely:
In Section 4, the set (of subsets) $\mathcal H_v$ is not clearly defined, so it is very difficult for the reader to capture the family of DP tasks defined according to the recurrence relation (3). In this section, some concrete examples of online optimization problems characterized by this DP family would be helpful.
In Section 5, the notion of Binary Search Tree should be clearly defined. Notably, if the authors are interested by the set of all rooted binary trees with $n + 1$ leaves, the cardinality of this set is indeed the Catalan number of order $n$ (as indicated in Line 268). But, contrary to what is claimed in Lines 250-251, there is a well-known characterization of the polytope specified by the convex hull of all rooted binary trees of order $n$: this is the $n$th dimensional associahedron.  Since this polytope is integral, we can use (at least theoretically) the Component Hedge algorithm for projecting points onto this polytope, and decomposing them (by Caratheodory's theorem) into convex combinations of binary trees.  
Section 5.2 is of particular importance, as it explains how the online BST problem can be solved using previous results obtained for $k$-multipaths. But the translation of this problem into an online $2$-multipath learning task is not clear at all. To this very point, it is important to explain in unambiguous terms how we can learn BSTs using the CH (or EH) technique used for $k$-multipaths. According to the sets $V$, $\Omega$, and $F_{ij}$ defined in Lines 265-266, are we guaranteed that (i) every $k$-multipath of the induced graph encodes a rooted binary tree with $n+1$ leaves (correctness), and (ii) every possible rooted binary tree with $n+1$ leaves can be encoded by a $k$-multipath of this induced graph?