Classical usage of regret minimization algorithms for learning equilibria in games has typically weighted each iteration equally.
In this paper, we demonstrate empirically faster convergence, while still guaranteeing the same worst-case regret bound, by greedily weighing each new iteration to minimize the regret minimizer's potential function: a measure the current distance to the set of desired equilibria. Recent work such as CFR+ [1]} and Linear CFR [2]} have also shown that faster performance is achievable by weighing iterates non-uniformly. However, in all previous algorithms, iterates were weighed according to a fixed, pre-determined schedule. In contrast, we introduce greedy weights, the first equilibrium-finding regret minimization algorithm where iterates are weighed dynamically using information available at runtime.
<FIGURE>