PaperlayerView exact revision on arXiv

Source-linked AI summary

Pessimistic Minimax Learning for Public-Private Information Games under Unilateral Coverage

Shuze Daniel Liu, Claire Chen, Jiuqi Wang, David Simchi-Levi

arXiv:2610.04997v1cs.LG

TL;DR

Offline learning for two-player zero-sum games with public and private information remains unexplored, although these games require accounting for both distribution shift and beliefs about hidden types. The paper introduces unilateral prescriptive concentrability and develops pessimistic methods for finite games and general function approximation that respect decentralized information constraints. For finite games, PPA-Exact achieves an ˜O(1/√n) exploitability rate, while PPA-PMD is a policy mirror descent framework for general function approximation.

  • Problem

    Offline learning for two-player zero-sum games with public and private information remains unexplored, although these games require accounting for both distribution shift and beliefs about hidden types.

    Source: §1 · pp. 1–2

  • Method

    The paper introduces unilateral prescriptive concentrability and develops pessimistic methods for finite games and general function approximation that respect decentralized information constraints.

    Source: §1 · p. 2

  • Results

    For finite games, PPA-Exact achieves an ˜O(1/√n) exploitability rate, while PPA-PMD is a policy mirror descent framework for general function approximation.

    Source: §7 · p. 10

  • Takeaways & Limitations

    Public-private information can change offline coverage by changing equilibrium behavior, a relationship captured by unilateral prescriptive concentrability.

    Source: §1 · p. 2

    The results concern contextual games; extending them to multi-stage games with dynamic beliefs and strategic signaling is left for future work.

    Source: §7 · p. 10

Abstract

from arXiv · show

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.

1 INTRODUCTION

Offline learning in games with private information remains unexplored, although such settings occur in auctions and negotiations. The paper analyzes how information constraints affect coverage and presents pessimistic learning guarantees for finite games and general function approximation.

1 INTRODUCTION

  • Offline reinforcement learning uses pre-collected data to learn policies without further interaction, but behavior-target distribution shift can cause value overestimation for poorly represented actions.Pessimistic methods address this with lower confidence bounds or conservative value estimates.Source: §1 · p. 1
  • Offline learning in public-private games must address both distribution shift and equilibrium identification, since an opponent may exploit poorly covered regions.Existing two-player offline-game work typically assumes both players fully observe the state.Source: §1 · p. 1
  • Asymmetric information changes which policies form an equilibrium, so required dataset coverage depends on induced equilibrium behavior.The paper introduces unilateral prescriptive concentrability to formalize this effect.Source: §1 · p. 2
  • PPA-Exact achieves an exploitability rate of ~O(1/√n), matching fully observed minimax games' sample-size dependence.The algorithm is for finite state-action spaces.Source: §1 · p. 2
  • PPA-PMD provides a pessimistic policy mirror descent framework for general function approximation, with a unified exploitability rate of ~O(1/√n + 1/√T).The rate combines statistical estimation from n samples and optimization regret over T iterations.Source: §1 · p. 2

2 PRELIMINARIES

The preliminaries specify the finite public and private state structure, feasible decentralized policies, and the common belief used to evaluate contextual games. They also set out the centralized-training assumption and the exploitability objective.

2 PRELIMINARIES

  • The game has a latent state comprising a shared public context and two player-specific private types, with a zero-sum reward structure.The public context and private type spaces, as well as the action spaces, are finite.Source: §2 · p. 2

2.1 INFORMATION CONSTRAINTS AND PRESCRIPTIVE POLICIES

  • Because each player observes only the public context and their own private type, feasible strategies are prescriptive policies based on local observations.Each player's policy maps the public context and that player's private type to a distribution over actions.Source: §2.1 · pp. 2–3

2.2 THE PUBLIC BELIEF AND CONTEXTUAL VALUE

  • For each public context, the public belief gives the conditional distribution of private types used to evaluate the Bayesian game.The global game value averages contextual values over the marginal distribution of public contexts.Source: §2.2 · p. 3

2.3 OFFLINE DATA AND THE CTDE PARADIGM

  • The offline learner trains centrally from n full-state logged interactions generated by an unknown behavior-policy pair, while deployed policies remain decentralized.The setup is described as centralized training with decentralized execution.Source: §2.3 · p. 3

2.4 MINIMAX OBJECTIVE AND THE EXPLOITABILITY GAP

  • The learner seeks a decentralized policy minimizing exploitability, measured by the gap between the minimax value and value against the opponent's best feasible response.That opponent is assumed to know the learner's policy but remains within the feasible policy class.Source: §2.4 · p. 3

3 INFORMATION ASYMMETRY AND COVERAGE ANALYSIS

The section develops coverage analysis for public-private games, where information constraints affect equilibrium behavior and thus the state-action regions that offline data must cover. It establishes contextual game values and compares prescriptive coverage with fully observed coverage.

3 INFORMATION ASYMMETRY AND COVERAGE ANALYSIS

  • Asymmetric information can change coverage requirements through its effect on equilibrium behavior, with the comparison depending on the logged behavior policy.The equilibrium-induced coverage gap can scale with the number of private types, and under other logging policies the comparison can reverse.Source: §3 · p. 3, §3.3 · pp. 4–5

3.1 EXISTENCE OF CONTEXTUAL VALUE

  • Each public context defines an independent Bayesian game with a unique value and a Nash equilibrium pair.The contextual value has equal max-min and min-max characterizations.Source: §3.1 · p. 4

3.2 UNILATERAL PRESCRIPTIVE COVERAGE

  • Unilateral prescriptive coverage measures whether logged data cover state-action regions needed for a learner's policy to withstand adversarial responses.The induced state-action density uses strategies conditioned on each player's local observation, while the logged dataset supplies the reference density.Source: §3.2 · p. 4

3.3 INFORMATION STRUCTURE AND OFFLINE COVERAGE

  • The coverage comparison with fully observed games can reflect different equilibria, but at a common reference policy the pointwise deviation coefficients are equal.The equality also holds for an integrated coverage criterion under decentralized logging.Source: §3.3 · pp. 4–5

4 OFFLINE LEARNING FOR FINITE ASYMMETRIC GAMES

For finite public-private games, the section presents pessimistic offline learning and analyzes its exploitability. It also describes an iterative alternative that combines statistical estimation with optimization regret.

4.2 SAMPLE COMPLEXITY ANALYSIS

  • PPA-Exact achieves an exploitability rate of ˜O(1/√n), matching the standard sample-size dependence for fully observed minimax games.The guarantee is stated under Assumption 3.2.Source: §4 · p. 5, §4.2 · pp. 6–7

4.1 EMPIRICAL ESTIMATORS AND PESSIMISTIC OBJECTIVE

  • PPA-Exact estimates rewards and public beliefs from logged data, then solves a pessimistic minimax problem over prescriptive policies for each public context.Its conservative value estimates are designed to protect the resulting decentralized policy against adversarial exploitation in sparsely covered regions.Source: §4.1 · pp. 5–6

4.2 SAMPLE COMPLEXITY ANALYSIS

  • The finite-game analysis bounds exploitability by controlling pessimism error, contextual gaps, and uncertainty bonuses through unilateral prescriptive concentrability.The proof integrates contextual bounds over public contexts and applies count concentration and Cauchy-Schwarz.Source: §4.2 · pp. 6–7
  • PPA-Learning uses decentralized no-regret dynamics to obtain a unified exploitability gap of ˜O(1/√n + 1/√T), combining statistical estimation and optimization regret.The framework is presented as the foundation for the general-function-approximation extension.Source: §4.2 · p. 7

5 GENERAL FUNCTION APPROXIMATION

The section extends pessimistic offline learning to general function approximation, replacing count-based estimation with supervised learning and using policy mirror descent for decentralized optimization.

5 GENERAL FUNCTION APPROXIMATION

  • The framework targets large-scale settings where finite-game methods face polynomial dependence on state-action cardinality, replacing counting-based estimators with supervised learning.It also uses policy mirror descent for decentralized optimization.Source: §5 · p. 7

5.1 OFFLINE ESTIMATION AND VERSION SPACE PESSIMISM

  • The learner estimates public beliefs by maximum likelihood and rewards by empirical risk minimization, then uses the lower envelope of a version space as its pessimistic reward predictor.The version space contains reward functions with near-optimal empirical risk.Source: §5.1 · p. 7

5.2 ASYMMETRIC POLICY MIRROR DESCENT

  • PPA-PMD updates decentralized actors by mirror descent using conditional expected local Q-values against the opponent's current strategy.Updates satisfying the stated external-regret condition are admissible.Source: §5.2 · p. 7

5.3 THEORETICAL ANALYSIS

  • Under realizability, prescriptive uniform function-approximation concentrability, and actor no-regret assumptions, Theorem 5.4 provides an exploitability guarantee for finite reward and belief classes.The supplied theorem passage gives the tolerance choice but not the full bound.Source: §5.3 · p. 8
  • The stochastic optimization error of the parameterized minibatch implementation is not analyzed.The theoretical guarantee applies when its actor updates satisfy the external-regret condition.Source: §5.3 · p. 8

6 RELATED WORK

Prior offline game-learning work largely studies fully observed settings, while Bayesian-game research has established strategic foundations for hidden information. This paper addresses offline equilibrium learning with asymmetric information and logged full-state data.

RELATED WORK

  • Offline RL uses pessimism to address distribution shift, and prior offline game work requires coverage of equilibrium paths and unilateral deviations.Prior work formalizes unilateral concentrability as necessary and sufficient for solvability in offline Markov games.Source: §6 · p. 9
  • Existing offline game-learning approaches largely assume fully observed states, while planning work characterizes strategies in hidden-information games.The latter settings include Bayesian games and incomplete-information games.Source: §6 · p. 9
  • The paper presents a statistical framework for recovering minimax-optimal decentralized policies from fixed, full-state historical logs under asymmetric information.Its analysis introduces unilateral prescriptive concentrability and relates information structure to coverage through induced equilibrium behavior.Source: §6 · p. 9

7 CONCLUSION

The paper studies offline learning in zero-sum contextual games with public and private information and introduces a coverage notion for prescriptive policies. It develops pessimistic methods with finite-game and function-approximation exploitability guarantees.

7 CONCLUSION

  • For finite games, PPA-Exact achieves an ˜O(1/√n) exploitability rate, matching the standard sample-size dependence for fully observed minimax games.Source: §7 · p. 10
  • The paper introduces unilateral prescriptive concentrability, a coverage notion defined over the prescriptive policy space.The methods account for statistical uncertainty and the information constraints of decentralized execution.Source: §7 · p. 10
  • Extending the results to multi-stage games with dynamic beliefs and strategic signaling is identified as a direction for future work.Source: §7 · p. 10

AI USE STATEMENT

The appendix describes an iterative no-regret solver and its local policy updates, alongside a statement limiting the stated use of generative AI to grammar correction.

AI USE STATEMENT

  • Generative AI tools were used solely for grammar correction, and the authors reviewed the AI-assisted work and take responsibility for the final content.Source: AI USE STATEMENT · p. 10

A.1 ITERATIVE MINIMAX OPTIMIZATION

  • PPA-Exact uses linear programming, while the iterative alternative uses no-regret dynamics and multiplicative-weights updates conditioned on each player's private observation.The public-private structure decomposes the minimax objective into local decision problems, yielding an O(T −1/2) optimization guarantee.Source: §A.1 · p. 14

A.2 LOCAL Q-VALUES AND MINIMAX DECOMPOSITION

  • The iterative solver computes each player's local Q-values against the opponent's policy and updates policies at each private state.Time-averaged iterates provide an approximate saddle point of the empirical pessimistic objective without explicitly constructing the full prescriptive LP.Source: §A.2 · p. 14

A.3 OPTIMIZATION GUARANTEE AND UNIFIED EXPLOITABILITY BOUND

The results combine iterative optimization with statistical analysis and examine how deviation classes and logging distributions affect coverage coefficients. The comparison depends on the coverage setting, with equality under decentralized logging for the integrated criterion.

A.3 OPTIMIZATION GUARANTEE AND UNIFIED EXPLOITABILITY BOUND

  • The iterative solver's O(T −1/2) optimization guarantee combines with PPA-Exact's statistical analysis to yield a unified exploitability bound.Source: §A.3 · p. 14

B.1.1 PROOF OF LEMMA 3.4

  • For a fixed reference policy, the prescriptive and fully observed deviation classes have the same pointwise coverage coefficient.The stated argument applies to prescriptive or fully observed reference policies.Source: §B.1.1 · p. 15

B.1.2 AN INTEGRATED COVERAGE CRITERION

  • When logged behavior is decentralized, the integrated coverage coefficients for the two deviation classes coincide.The appendix presents this as a robustness check beyond the pointwise criterion.Source: §B.1.2 · p. 16
  • For the integrated criterion, arbitrary logged behavior can produce a ratio approaching min{|X1|, |A2|}, and this factor cannot be improved.Source: §B.1.2 · p. 16

B.1.3 PROOF OF PROPOSITION 3.3

The construction compares prescriptive and fully observed equilibria and their coverage under symmetric, type-independent logging. The relative coverage can favor either information setting depending on the logger.

B.1.3 PROOF OF PROPOSITION 3.3

  • For every K ≥3, a constructed game has unique prescriptive and fully observed equilibria that do not depend on the logged behavior.Source: §B.1.3 · p. 17
  • Depending on the symmetric logger, prescriptive coverage can be better or worse than fully observed coverage by a factor K.The two logger choices yield opposite orderings, so neither ordering holds universally.Source: §B.1.3 · pp. 17–18
  • The prescriptive equilibrium uses action 0, while under full information each player chooses the other player's type.In the construction, action 0 is strictly dominant under prescriptive execution, while the observed opposing type determines the strictly dominant action under full information.Source: §B.1.3 · p. 18

B.2 PROOF OF THEOREM 4.1

The proof combines belief estimation, deterministic reward pessimism, and behavior-coverage conditions to bound exploitability. Unobserved contexts use a fallback belief and a trivial error bound.

B.2 PROOF OF THEOREM 4.1

  • Equilibrium and unilateral-deviation distributions are supported by the logged behavior distribution under Pres.The global bound restricts sums to the support of dρ and uses count concentration there.Source: §B.2 · pp. 18, 21, 22
  • The proof combines conditional empirical-belief concentration across contexts with a separate error bound for contexts having no samples.For N(c) = 0, the fallback belief gives the trivial L1 bound of 2.Source: §B.2 · p. 19
  • Clipped reward estimates are surely pessimistic and their underestimation error is at most 2β(s, a) when rewards are deterministic.Because rewards are deterministic, no reward-concentration event is needed.Source: §B.2 · p. 20
  • The statistical failure budget is allocated entirely to belief estimation because deterministic rewards require no reward-estimation failure event.The proof assigns δ/2 to belief estimation and δ/2 to count concentration.Source: §B.2 · pp. 19–20

B.3 PROOF OF THEOREM A.1

The proof lifts local mirror-descent regret bounds to a global saddle-point guarantee and establishes convergence for the iterative asymmetric bandit solver. It also gives a parameterized, minibatched PPA-PMD implementation whose theorem applies under a no-regret actor-update condition.

B.3 PROOF OF THEOREM A.1

  • Local mirror-descent regret bounds are aggregated over private-state beliefs to obtain global regret and a saddle-point optimality bound.The argument uses the bilinearity of the empirical objective and compact, convex policy spaces.Source: §B.3 · p. 23
  • The final exploitability guarantee establishes convergence for the iterative asymmetric bandit solver.The proof combines the optimization error with the statistical expectation term.Source: §B.3 · p. 24

B.4 PARAMETERIZED PPA-PMD IMPLEMENTATION

  • Algorithm 3 uses offline belief and reward estimation followed by minibatched actor updates, with Theorem 5.4 applying when updates satisfy the external-regret condition.The implementation alternates critic evaluation and policy mirror descent over sampled public contexts.Source: §B.4 · pp. 24–25

B.5 PROOF OF THEOREM 5.4

The proof establishes offline reward and belief estimation guarantees, then combines estimation, pessimism, and optimization errors to bound exploitability. Reward regression is controlled under the behavior distribution before a concentrability assumption transfers its guarantee to target distributions.

B.5 PROOF OF THEOREM 5.4

  • The reward version space contains the true reward with probability at least 1 − δ, and its members satisfy the stated risk guarantee.The reward-estimation argument uses realizability, a version-space tolerance, and a uniform fast-rate ERM bound; it does not require concentrability for this stage.Source: §B.5 · pp. 25–26
  • The MLE belief error is bounded through squared Hellinger distance and converted to an L1 error bound.The conversion uses that the true and estimated joint distributions share the public-context marginal.Source: §B.5 · pp. 25–27

2 H(P, Q) then gives

  • The pessimistic critic underestimates the true reward, with its pointwise error controlled by the reward version-space diameter.The true reward belongs to the version space under the offline estimation guarantee.Source: §B.5 · p. 25, §2 · p. 27
  • The final proof combines belief and reward estimation errors with the no-regret optimization error to obtain an exploitability guarantee.The reward error is transferred from the behavior distribution using the uniform-ratio assumption.Source: §2 · pp. 28–29
Loading 2610.04997v1…