Φ-Regret Minimization under Corrupted Learning Dynamics

Tsuchiya et al. (2024) pioneered corrupted learning dynamics, showing how equilibrium convergence adapts to players' deviations from prescribed algorithms. However, their work focuses on traditional regret measures (external/swap regret). Meanwhile, Piliouras et al. (2022) and Zhang et al. (2025) demonstrate that Φ-regret—generalizing regret to partitions of mixed strategies—captures richer forms of rationality. This idea bridges these gaps: What if deviations are not just from prescribed strategies but from mixed-strategy partitions? For example, a player might deviate by randomizing over actions in unforeseen ways, breaking Φ-regret assumptions. We’d develop algorithms that bound Φ-regret under corruption, perhaps using adaptive learning rates (as in Tsuchiya et al.) but applied to polynomial deviation maps (à la Zhang et al.). This would be the first work to handle corrupted Φ-equilibria, with applications in markets where agents exploit loopholes in mixed-strategy spaces (e.g., ad auctions with bid-shading).

References:

1. Corrupted Learning Dynamics in Games. Taira Tsuchiya, Shinji Ito, Haipeng Luo (2024). Annual Conference Computational Learning Theory.
2. Evolutionary Dynamics and Phi-Regret Minimization in Games. G. Piliouras, Mark Rowland, Shayegan Omidshafiei, R. Élie, Daniel Hennes, Jerome T. Connor, K. Tuyls (2022). Journal of Artificial Intelligence Research.
3. Learning and Computation of Φ-Equilibria at the Frontier of Tractability. B. Zhang, I. Anagnostides, Emanuel Tewolde, Ratip Emin Berker, Gabriele Farina, Vincent Conitzer, T. Sandholm (2025). ACM Conference on Economics and Computation.