{"id":"arxiv/2602.12513","url":"https://arxiv.org/abs/2602.12513","tags":["math.OC"],"score":0,"title":"An LP-Based Approach for Bilinear Saddle Point Problem with Instance-dependent Guarantee and Noisy Feedback","domain":"math.OC","source":"arxiv","authors":["Jiashuo Jiang","Mengxiao Zhang"],"reviews":0,"subject":"math.OC","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-02-13","reactions":{}}