Rate optimal learning of equilibria from data

Till Freihaut, Luca Viano, Emanuele Nevali, Volkan Cevher, Matthieu Geist, Giorgia Ramponi
Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, PMLR 300:3430-3438, 2026.

Abstract

We close open theoretical gaps in Multi-Agent Imitation Learning (MAIL) by characterizing the limits of non-interactive MAIL and presenting the first interactive algorithm with near-optimal sample complexity. In the non-interactive setting, we prove a statistical lower bound that identifies the \emph{all-policy deviation concentrability coefficient} as the fundamental complexity measure, and we show that Behavior Cloning (BC) is rate-optimal. For the interactive setting, we introduce a framework that combines reward-free reinforcement learning with interactive MAIL and instantiate it with an algorithm, \emph{MAIL-WARM}. It improves the best previously known sample complexity from $\mathcal{O}(\varepsilon^{-8})$ to $\mathcal{O}(\varepsilon^{-2}),$ matching the dependence on $\varepsilon$ implied by our lower bound. Finally, we provide numerical results that support our theory and illustrate, in environments such as grid worlds, cases where Behavior Cloning fails to learn.

Cite this Paper

BibTeX
@InProceedings{pmlr-v300-freihaut26a, title = { Rate optimal learning of equilibria from data }, author = {Freihaut, Till and Viano, Luca and Nevali, Emanuele and Cevher, Volkan and Geist, Matthieu and Ramponi, Giorgia}, booktitle = {Proceedings of The 29th International Conference on Artificial Intelligence and Statistics}, pages = {3430--3438}, year = {2026}, editor = {Khan, Emtiyaz and Li, Yingzhen and Solin, Arno and Ramdas, Aaditya}, volume = {300}, series = {Proceedings of Machine Learning Research}, month = {02--05 May}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v300/main/assets/freihaut26a/freihaut26a.pdf}, url = {https://proceedings.mlr.press/v300/freihaut26a.html}, abstract = { We close open theoretical gaps in Multi-Agent Imitation Learning (MAIL) by characterizing the limits of non-interactive MAIL and presenting the first interactive algorithm with near-optimal sample complexity. In the non-interactive setting, we prove a statistical lower bound that identifies the \emph{all-policy deviation concentrability coefficient} as the fundamental complexity measure, and we show that Behavior Cloning (BC) is rate-optimal. For the interactive setting, we introduce a framework that combines reward-free reinforcement learning with interactive MAIL and instantiate it with an algorithm, \emph{MAIL-WARM}. It improves the best previously known sample complexity from $\mathcal{O}(\varepsilon^{-8})$ to $\mathcal{O}(\varepsilon^{-2}),$ matching the dependence on $\varepsilon$ implied by our lower bound. Finally, we provide numerical results that support our theory and illustrate, in environments such as grid worlds, cases where Behavior Cloning fails to learn. } }
Endnote
%0 Conference Paper %T Rate optimal learning of equilibria from data %A Till Freihaut %A Luca Viano %A Emanuele Nevali %A Volkan Cevher %A Matthieu Geist %A Giorgia Ramponi %B Proceedings of The 29th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2026 %E Emtiyaz Khan %E Yingzhen Li %E Arno Solin %E Aaditya Ramdas %F pmlr-v300-freihaut26a %I PMLR %P 3430--3438 %U https://proceedings.mlr.press/v300/freihaut26a.html %V 300 %X We close open theoretical gaps in Multi-Agent Imitation Learning (MAIL) by characterizing the limits of non-interactive MAIL and presenting the first interactive algorithm with near-optimal sample complexity. In the non-interactive setting, we prove a statistical lower bound that identifies the \emph{all-policy deviation concentrability coefficient} as the fundamental complexity measure, and we show that Behavior Cloning (BC) is rate-optimal. For the interactive setting, we introduce a framework that combines reward-free reinforcement learning with interactive MAIL and instantiate it with an algorithm, \emph{MAIL-WARM}. It improves the best previously known sample complexity from $\mathcal{O}(\varepsilon^{-8})$ to $\mathcal{O}(\varepsilon^{-2}),$ matching the dependence on $\varepsilon$ implied by our lower bound. Finally, we provide numerical results that support our theory and illustrate, in environments such as grid worlds, cases where Behavior Cloning fails to learn.
APA
Freihaut, T., Viano, L., Nevali, E., Cevher, V., Geist, M. & Ramponi, G.. (2026). Rate optimal learning of equilibria from data . Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 300:3430-3438 Available from https://proceedings.mlr.press/v300/freihaut26a.html.

Related Material