When Is Offline Two-Player Zero-Sum Markov Game Solvable?

on YouTube ↗34m

" summary

Shows that single strategy concentration insufficient for offline two‑player zero‑sum Markov games by a simple H=1 bandit counterexample where two different reward matrices produce identical batch data, so Nash equilibria are unidentifiable. Proposes unilateral concentration (coverage of every row and column of the NE pair), proves it is necessary and sufficient, and gives a pessimism algorithm using confidence intervals (Hoeffding/Bernstein) that achieves sample complexity O(A·B·C_unilateral/ε^2) in the bandit case and minimax rates for uniform coverage and turn‑based games.

AI-written summary · about

" chapters (17)

1. 0:00Intro
2. 0:32Acknowledgement
3. 1:20Offline Reinforcement Learning
4. 2:46Single-Agent Reinforcement Learnin
5. 4:32Tabular Markov Decision Process
6. 4:55Offline Single-Agent Reinforcement Lea
7. 7:14Dataset Coverage and Results
8. 9:49Two-Player Zero-Sum Markov Game Zero-Sum Markov Games
9. 11:56Value Function, Best Response and Duali
10. 14:52Offline Two-Player Zero-Sum Markov G
11. 17:27Counter Example for Single Strategy Cov Min Player
12. 20:11Unilateral Coverage Assumption Min Player
13. 22:52Algorithm for Two-Player Zero-Sum Bai
14. 24:38Result for Two-Player Zero-Sum Band
15. 25:56Algorithm for Markov Games
16. 26:29Result for Two-Player Zero-Sum Markov
17. 33:05Summary and Open Problem First theoretical study on two-player zero-sum Markov games Single policy coverage not sufficient separation between single-agent and two player Unilateral coverage: sufficient and cannot be weakened. • Algorithms based on pessimism for both players

" related talks

• 32mMulti-Player Multi-Armed Bandit: Can We Still Collaborate at Homes Without "Zoom"?Yuanzhi Li · Mathematics of Online Decision Making 2020
• 41mSpotlight TalksRashida Hakim, Chhavi Yadav · Agency in Collaborative Learning 2026
• 45mAGT and Machine LearningChristos Papadimitriou · Algorithmic Game Theory and Practice 2015
• 42mRethinking AI Alignment and Evaluation under Heterogeneous PreferencesKunhe Yang · Agency in Collaborative Learning 2026
• 56mOn the Curses of Future and History in Off-policy Evaluation in non-Markov EnvironmentsNan Jiang · Emerging Generalization Settings 2024
• 47mRebel: Combining Deep Reinforcement Learning and Search for Imperfect-Information GamesNoam Brown · Adversarial Approaches in Machine Learning 2022
• 59mPCPs and Global Hyper-contractivity 1Dor Minzer · Analysis and TCS Boot Camp 2023
• 48mLearning by Local Entropy MaximizationRiccardo Zecchina · Random Instances and Phase Transitions (Simons Institute, 2016)