Online Min-Max Optimization: From Individual Regrets to Cumulative Saddle Points

2026-02-11 · Abhijeet Vyas, Brian Bullins arxiv

We propose and study an online version of min-max optimization based on cumulative saddle points under a variety of performance measures beyond convex-concave settings. After first observing the incompatibility of (static) Nash equilibrium (SNE-Reg$_T$) with individual regrets even for strongly convex-strongly concave functions, we propose an alternate \emph{static} duality gap (SDual-Gap$_T$) inspired by the online convex optimization (OCO) framework. We provide algorithms that, using a reduction to classic OCO problems, achieve bounds for SDual-Gap$_T$~and a novel \emph{dynamic} saddle point regret (DSP-Reg$_T$), which we suggest naturally represents a min-max version of the dynamic regret in OCO. We derive our bounds for SDual-Gap$_T$~and DSP-Reg$_T$~under strong convexity-strong concavity and a min-max notion of exponential concavity (min-max EC), and in addition we establish a class of functions satisfying min-max EC~that captures a two-player variant of the classic portfolio selection problem. Finally, for a dynamic notion of regret compatible with individual regrets, we derive bounds under a two-sided Polyak-Łojasiewicz (PL) condition.

📄 PDF Abstract BibTeX arXiv:2602.10565

Code (0)

등록된 구현이 없습니다.

Online Saddle Point Problem and Online Convex-Concave Optimization

2023-12-12 · Qing-xin Meng, Jian-wei Liu

Centered around solving the Online Saddle Point problem, this paper introduces the Online Convex-Concave Optimization (OCCO) framework, which involves a sequence of two-player time-varying convex-concave games. We propos…

The Online Saddle Point Problem and Online Convex Optimization with Knapsacks

2018-06-21 · Adrian Rivera, He Wang, Huan Xu

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 objectiv…

Continuum-Armed Bandits: A Function Space Perspective

2020-10-15 · Shashank Singh

Continuum-armed bandits (a.k.a., black-box or $0^{th}$-order optimization) involves optimizing an unknown objective function given an oracle that evaluates the function at a query point, with the goal of using as few que…

Online and Bandit Algorithms for Nonstationary Stochastic Saddle-Point Optimization

2019-12-03 · Abhishek Roy, Yifang Chen, Krishnakumar Balasubramanian, Prasant Mohapatra

Saddle-point optimization problems are an important class of optimization problems with applications to game theory, multi-agent reinforcement learning and machine learning. A majority of the rich literature available fo…

Multi-agent Reinforcement Learning Reinforcement Learning

Learning in Markov Decision Processes under Constraints

2020-02-27 · Rahul Singh, Abhishek Gupta, Ness B. Shroff

We consider reinforcement learning (RL) in Markov Decision Processes in which an agent repeatedly interacts with an environment that is modeled by a controlled Markov process. At each time step $t$, it earns a reward, an…

reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)