| Title: |
The Online Saddle Point Problem and Online Convex Optimization with Knapsacks. |
| Authors: |
Rivera Cardoso, Adrian1 (AUTHOR) adrian.riv@hotmail.com, Wang, He2 (AUTHOR) he.wang@isye.gatech.edu, Xu, Huan3 (AUTHOR) huan.xu@alibaba-inc.com |
| Source: |
Mathematics of Operations Research. Feb2025, Vol. 50 Issue 1, p1-39. 39p. |
| Subject Terms: |
*Nash equilibrium, *Time-based pricing, *Game theory, Knapsack problems, Online education |
| Abstract: |
We study the online saddle point problem, an online learning problem where at each iteration, a pair of actions needs 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 saddle point regret (SP-Regret). The problem generalizes the online convex optimization framework, but here, we must ensure that 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 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 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(T) regret using a primal-dual algorithm. [ABSTRACT FROM AUTHOR] |
|
Copyright of Mathematics of Operations Research is the property of INFORMS: Institute for Operations Research and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) |
| Database: |
Business Source Complete |
