Offline learning algorithm improves strategic games with hidden information
Pessimistic Minimax Learning for Public-Private Information Games under Unilateral Coverage
Machine Learning
Summary
The paper studies how to learn good strategies in games where two players have some shared information and some private hidden information, like auctions or negotiations. The authors find that hidden information affects what kinds of past data can help learn good strategies. They develop new algorithms that can learn effective strategies from offline data with theoretical guarantees on performance. These algorithms work even when the game is complex and uses function approximations. This is the first theoretical framework addressing such games with both public and private information offline.
What this means in practice
- •For auction platform engineers: Design offline training systems to learn bidding strategies accounting for bidder private valuations and public data in auctions.
- •For automated negotiation developers: Build negotiation agents that learn from historical interactions with private and shared information to improve offers and responses.
Authors
Shuze Daniel Liu, Claire Chen, Jiuqi Wang, David Simchi-Levi
Abstract
We study offline learning in two-player zero-sum contextual games with public and private information, motivated by strategic settings such as auctions and negotiations with private valuations. We introduce unilateral prescriptive concentrability and show that asymmetric information can change offline coverage through its effect on equilibrium behavior. For finite state-action spaces, we develop a pessimistic algorithm with an $\tilde{O}(1/\sqrt{n})$ exploitability rate, matching the standard sample-size dependence for fully observed minimax games. We further develop a pessimistic policy mirror descent framework, PPA-PMD, for general function approximation and obtain a unified $\tilde{O}(1/\sqrt{n} + 1/\sqrt{T})$ exploitability rate with no-regret actor updates. Together, these results provide the first theoretical framework for offline equilibrium learning under public-private information constraints.