  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 and Component Hedge
to a significantly wider class of combinatorial objects than was possible
before.
