An Approximate Dynamic Programming Approach to Adversarial Online Learning
This work addresses the challenge of regret minimization in adversarial environments for decision-making systems, representing an incremental advancement by applying ADP to a known bottleneck.
The paper tackles the problem of computing optimal strategies and minimal guaranteed losses in discounted repeated games with vector-valued losses, which arise in adversarial online learning, and demonstrates that their approximate dynamic programming approach yields algorithms with markedly improved performance bounds compared to existing methods like Hedge.
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.