Preprint
An LP-Based Approach for Bilinear Saddle Point Problem with Instance-dependent Guarantee and Noisy Feedback
ArXiv.org
Cornell University
02/13/2026
DOI: 10.48550/arxiv.2602.12513
Abstract
In this work, we study the sample complexity of obtaining a Nash equilibrium (NE) estimate in two-player zero-sum matrix games with noisy feedback. Specifically, we propose a novel algorithm that repeatedly solves linear programs (LPs) to obtain an NE estimate with bias at most$\varepsilon$with a sample complexity of$O\left(\frac{m_1 m_2}{\varepsilon\min\{δ^2,σ_0^2,σ^3\}} \log\frac{m_1 m_2}{\varepsilon}\right)$for general$m_1 \times m_2$game matrices, where$σ$ ,$σ_0$ ,$δ$are some problem-dependent constants. To our knowledge, this is the first instance-dependent sample complexity bound for finding an NE estimate with$\varepsilon$bias in general-dimension matrix games with noisy feedback and potentially non-unique equilibria. Our algorithm builds on recent advances in online resource allocation and operates in two stages: (1) identifying the support set of an NE, and (2) computing the unique NE restricted to this support. Both stages rely on a careful analysis of LP solutions derived from noisy samples.
Details
- Title: Subtitle
- An LP-Based Approach for Bilinear Saddle Point Problem with Instance-dependent Guarantee and Noisy Feedback
- Creators
- Jiashuo JiangMengxiao Zhang
- Resource Type
- Preprint
- Publication Details
- ArXiv.org
- DOI
- 10.48550/arxiv.2602.12513
- ISSN
- 2331-8422
- Publisher
- Cornell University; Ithaca, New York
- Language
- English
- Date posted
- 02/13/2026
- Academic Unit
- Business Analytics
- Record Identifier
- 9985139475602771
Metrics
3 Record Views