Abstract: We extend the classic regret minimization framework for approximating equilibria in matrix games by greedily weighing iterates based on the regrets observed at runtime. Theoretically, our method retains all previous convergence rate guarantees. Empirically, experiments on large random matrix games and normal-form subgames of the AI benchmark Diplomacy show that greedy weights outperforms previous methods whenever sampling is used, sometimes by several orders of magnitude.