Online Linear Programming: Applications and Extensions

A natural optimisation model that formulates many online learning, resource allocations and dynamic decision-making with uncertainty is online linear programming (OLP) where the noisy constraint column vectors, along with the objective coefficients and decision variables, are revealed and decided sequentially. We review the near optimal algorithms and theories for solving this surprisingly general class of online problems under the assumption of random order of arrivals and/or stationary distributions of the input data. Then we present few recent developments of the model/algorithm, including a fast online algorithm as a pre-solver for solving large-scale offline (binary) LPs, an interior-point online algorithm to address “fairness” for resource allocation, a provable logarithmic regret bound for the Bandits with Knapsacks (BwK) problem, an extension to online Fisher markets with a geometric aggregation of individual utilities, and how to deal with non-stationary data distributions in online learning.