Abstract
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.
Introduction
In the field of adversarial online learning, the standard benchmark for success is the "no-regret" property. Algorithms like the well-known Hedge algorithm are designed to ensure that the average regret—the difference between the player's performance and that of the best fixed action in hindsight—vanishes as the time horizon approaches infinity. However, the no-regret criterion is often a conservative "low bar." It provides asymptotic guarantees but fails to provide optimality for specific, finite time horizons or specific discount factors ($\beta$).
This research addresses the challenge of finding regret-optimal strategies. By focusing on games with discounted losses—where immediate outcomes are weighted more heavily than future ones—the authors provide a framework for decision-making in environments where the "present value" of a choice is critical, such as in financial modeling or real-time systems control.
A Vector-Valued Game Framework
The authors transform the regret minimization problem into a two-player, vector-valued repeated game. In this model, the decision-maker ("Alice") attempts to minimize a vector of regrets relative to $K$ different experts, while an adversary ("Bob") attempts to maximize them.
This formulation highlights a key insight: minimizing regret against multiple experts is fundamentally a multi-objective optimization problem. Improving performance relative to one expert may necessitate a trade-off in performance relative to another. The goal is to find the Pareto frontier—the set of the best possible trade-offs Alice can achieve.
Methodology: Set-Valued Dynamic Programming
The technical core of the paper is the characterization of this Pareto frontier as the unique fixed point of a set-valued dynamic programming (DP) operator.
The Contraction Mapping
To prove that this DP approach is viable, the authors define a metric based on the Hausdorff distance between the "upsets" (the sets of all points dominated by the frontier) of these Pareto sets. They demonstrate that their DP operator is a contraction within this metric space. This ensures that iterative application of the operator will converge toward the optimal frontier, providing a rigorous foundation for computing optimal strategies.
Computational Approximations
Because calculating the exact Pareto frontier is computationally intensive, the authors propose two practical approximation schemes:
- Polytopic Approximation: For problems with a small number of experts, the frontier is approximated using a convex polytope with a finite number of vertices.
- QCLP Heuristic: For higher-dimensional problems (e.g., $K=10$), the authors utilize a Quadratically Constrained Linear Program (QCLP) to find effective "finite-mode" policies. Unlike standard Markov Decision Processes where states are external, the "states" here are endogenous, created by the algorithm to track its own performance guarantees.
Empirical Results
The proposed ADP-based approach was evaluated against classic benchmarks, including the Hedge algorithm and the GPS (Gravin, Peres, and Sivan) algorithm.
- 2-Expert Benchmark: In the classic binary loss prediction problem, the ADP-based policies achieved significantly lower regret guarantees than both Hedge and GPS across a wide range of discount factors.
- High-Dimensional Performance: In tests involving 10 experts and randomly generated game matrices, the QCLP-based heuristic demonstrated remarkable scalability. Even with a limited budget of 11 modes, the ADP-derived policy outperformed an optimally tuned Hedge algorithm in 100% of the 100 random instances tested.
Conclusion and Future Directions
This work demonstrates that standard online learning algorithms are often strictly suboptimal when compared to strategies derived through dynamic programming. By exploiting the specific geometry of loss vectors, ADP-based approaches can provide significantly tighter performance bounds.
However, challenges remain. The polytopic approximation method suffers from the curse of dimensionality as the number of experts increases. Additionally, the current framework is designed for discrete action spaces for the adversary and discounted loss criteria. Extending these methods to continuous action spaces and long-run average loss criteria remains a promising area for future research.
Summary updated