The Online Saddle Point Problem and Online Convex Optimization with Knapsacks

Abstract

We study the online saddle point problem, an online learning problem where at each iteration a pair of actions need to be chosen without knowledge of the current and future (convex-concave) payoff functions. The objective is to minimize the gap between the cumulative payoffs and the saddle point value of the aggregate payoff function, which we measure using a metric called "SP-Regret". The problem generalizes the online convex optimization framework but here we must ensure both players incur cumulative payoffs close to that of the Nash equilibrium of the sum of the games. We propose an algorithm that achieves SP-Regret proportional to $\sqrt{\ln (T)T}$ in the general case, and $\log (T)$ SP-Regret for the strongly convex-concave case. We also consider the special case where the payoff functions are bilinear and the decision sets are the probability simplex. In this setting we are able to design algorithms that reduce the bounds on SP-Regret from a linear dependence in the dimension of the problem to a \textit{logarithmic} one. We also study the problem under bandit feedback and provide an algorithm that achieves sublinear SP-Regret. We then consider an online convex optimization with knapsacks problem motivated by a wide variety of applications such as: dynamic pricing, auctions, and crowdsourcing. We relate this problem to the online saddle point problem and establish $O(\sqrt{T})$ regret using a primal-dual algorithm.

References in corpus (11)

• Trading Regret for Efficiency: Online Convex Optimization with Long Term Constraints
• The Mechanics of n-Player Differentiable Games
• Online convex optimization for cumulative constraints
• Online Convex Optimization with Time-Varying Constraints
• Algorithms with Logarithmic or Sublinear Regret for Constrained Contextual Bandits
• Algorithms for stochastic optimization with functional or expectation constraints
• Faster Rates for Convex-Concave Games
• An optimal algorithm for bandit convex optimization
• Risk-Averse Stochastic Convex Bandit
• A Low Complexity Algorithm with $O(\sqrt{T})$ Regret and $O(1)$ Constraint Violations for Online Convex Optimization with Long Term Constraints
• Adaptive Algorithms for Online Convex Optimization with Long-term Constraints

Cited by in corpus (3)

• Online and Bandit Algorithms for Nonstationary Stochastic Saddle-Point Optimization
• Online DR-Submodular Maximization with Stochastic Cumulative Constraints
• Proximal Point Method for Online Saddle Point Problem