  We describe an approximate dynamic programming (ADP) approach to compute
approximations of the optimal strategies and of the minimal losses that can be
guaranteed in discounted repeated games with vector-valued losses. Such games
prominently arise in the analysis of regret in repeated decision-making in
adversarial environments, also known as adversarial online learning. At the
core of our approach is a characterization of the lower Pareto frontier of the
set of expected losses that a player can guarantee in these games as the unique
fixed point of a set-valued dynamic programming operator. When applied to the
problem of regret minimization with discounted losses, our approach yields
algorithms that achieve markedly improved performance bounds compared to
off-the-shelf online learning algorithms like Hedge. These results thus suggest
the significant potential of ADP-based approaches in adversarial online
learning.
