An LP-Based Approach for Bilinear Saddle Point Problem with Instance-dependent Guarantee and Noisy Feedback
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2602.12513
curl -X POST /api/v1/records/arxiv/2602.12513/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2602.12513/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'