Online Learning to Transport via the Minimal Selection Principle
This work addresses robust dynamic resource allocation in operations research by extending online learning to infinite-dimensional probability measures, making optimal transport theory practically relevant for non-convex settings.
The paper tackles the Online Learning to Transport (OLT) problem, which involves decision variables as probability measures in infinite-dimensional spaces, by introducing the minimal selection principle to connect online learning, optimal transport, and PDEs, resulting in the MSoE algorithm that ensures optimal cumulative regret bounds in displacement convex settings and extends to non-convex applications.
Motivated by robust dynamic resource allocation in operations research, we study the \textit{Online Learning to Transport} (OLT) problem where the decision variable is a probability measure, an infinite-dimensional object. We draw connections between online learning, optimal transport, and partial differential equations through an insight called the minimal selection principle, originally studied in the Wasserstein gradient flow setting by \citet{Ambrosio_2005}. This allows us to extend the standard online learning framework to the infinite-dimensional setting seamlessly. Based on our framework, we derive a novel method called the \textit{minimal selection or exploration (MSoE) algorithm} to solve OLT problems using mean-field approximation and discretization techniques. In the displacement convex setting, the main theoretical message underpinning our approach is that minimizing transport cost over time (via the minimal selection principle) ensures optimal cumulative regret upper bounds. On the algorithmic side, our MSoE algorithm applies beyond the displacement convex setting, making the mathematical theory of optimal transport practically relevant to non-convex settings common in dynamic resource allocation.