Bandit Optimal Transport
This addresses a novel sequential learning challenge in OT, extending bandit methods to infinite-dimensional spaces, which is incremental as it builds on linear bandits but applies to a new problem setting.
The paper tackles the problem of sequential learning for Optimal Transport (OT) with unknown costs, providing regret algorithms with bounds of \tilde{\mathcal O}(√T) for Kantorovich and entropic OT problems, interpolating to \tilde{\mathcal O}(T) based on cost regularity.
Despite the impressive progress in statistical Optimal Transport (OT) in recent years, there has been little interest in the study of the \emph{sequential learning} of OT. Surprisingly so, as this problem is both practically motivated and a challenging extension of existing settings such as linear bandits. This article considers (for the first time) the stochastic bandit problem of learning to solve generic Kantorovich and entropic OT problems from repeated interactions when the marginals are known but the cost is unknown. We provide $\tilde{\mathcal O}(\sqrt{T})$ regret algorithms for both problems by extending linear bandits on Hilbert spaces. These results provide a reduction to infinite-dimensional linear bandits. To deal with the dimension, we provide a method to exploit the intrinsic regularity of the cost to learn, yielding corresponding regret bounds which interpolate between $\tilde{\mathcal O}(\sqrt{T})$ and $\tilde{\mathcal O}(T)$.