On the Exploitability of FTRL Dynamics

A new theoretical paper from researchers Yiheng Su and Emmanouil-Vasileios Vlatakis-Gkaragkounis, titled 'On the Exploitability of FTRL Dynamics,' delivers a significant finding for AI safety and game theory. The work proves that Follow-the-Regularized-Leader (FTRL), a foundational algorithm family used for online learning and multi-agent training, has an inherent and quantifiable vulnerability to exploitation. Contrary to prior belief that exploitability was an artifact of specific implementations, the authors show it is a fundamental property of the FTRL framework itself when facing a strategic, clairvoyant opponent.

The analysis establishes two key exploitation bounds. First, against a fixed optimizer, the exploitable surplus scales as Ω(N/η), where N is the number of the learner's suboptimal actions and η is the learning rate. Second, in random games against an alternating optimizer, a surplus of Ω(ηT/poly(n,m)) can be guaranteed with high probability over T rounds. The paper further identifies a sharp geometric dichotomy: non-steep regularizers allow an opponent to quickly eliminate suboptimal actions for maximum gain, while steep regularizers only delay the inevitable exploitation.

This research has immediate implications for the design and deployment of AI systems that learn through interaction, such as those trained via self-play (like AlphaGo) or deployed in competitive environments like trading or security. The authors propose a 'susceptibility measure' to quantify which regularizers are most vulnerable, providing a tool for practitioners to audit and harden their learning algorithms against strategic manipulation by adversarial agents.