PaperlayerView exact revision on arXiv

Source-linked AI summary

Policy Optimization and Statistical Inference for Online Contextual Matrix Games

Liner Xiang, Yixin Wang, Hengrui Cai

arXiv:2608.17173v1stat.MLcs.LGmath.STstat.ME

TL;DR

The paper addresses online decisions in which strategic interactions and evolving contextual payoffs must be handled together. It introduces online contextual matrix games and OnGameLearn, with inference and policy-value tools for learning equilibria under online feedback. Simulations and a real-world hotel pricing application demonstrate the approach’s effectiveness, while the theoretical development includes guarantees for parameter and equilibrium estimation.

  • Problem

    Existing contextual bandits omit multi-player interactions, whereas online matrix games generally assume fixed payoffs and do not characterize contextual effects on equilibria or provide statistical inference.

  • Method

    The paper introduces online contextual matrix games and OnGameLearn, combining contextual payoff modeling, Nash-equilibrium learning, statistical inference, and doubly robust policy-value estimation.

  • Results

    The paper establishes statistical guarantees for payoff and equilibrium estimation, asymptotic normality, sublinear regret, and policy-value estimation, with simulations and a hotel pricing application demonstrating effectiveness.

  • Takeaways & Limitations

    Online contextual matrix games provide a framework for strategic decision-making when payoff matrices evolve with observable contextual information.

  • Takeaways & Limitations

    The paper’s motivating theoretical setting focuses on two-player zero-sum games, with extension to broader multi-player interactions described as future scope.

Abstract

from arXiv · show

Online decision making often requires navigating a landscape shaped by both dynamic contexts and strategic interactions. In competitive pricing, for example, hotels must account for both dynamic contextual factors and rivals' strategic responses. Existing approaches address only part of this challenge: contextual bandits optimize single-agent decisions using observable features but ignore multi-player interactions, while online matrix games capture strategic behavior through Nash equilibrium but assume fixed payoffs, ignoring contextual information. How should agents act then when strategic payoffs evolve with contextual signals? We introduce \emph{online contextual matrix games} to integrate contextual information into multi-player online games. We further propose \emph{OnGameLearn}, an online learning algorithm that efficiently balances exploration and exploitation across both player actions and contexts. This approach comes with statistical guarantees: tail bounds for the estimated payoff matrix, the convergence of the estimated Nash equilibrium, the asymptotic normality of the parameter estimators, and the sublinear regret bound. We also develop the notion of \emph{policy value} in matrix games and develop a doubly robust, $\sqrt{T}$-consistent estimator for it. Across simulated studies and a real-world hotel pricing application, we find that OnGameLearn effectively navigates the intertwined challenges of strategic and contextual decision-making.

1 Introduction

The paper introduces online contextual matrix games for settings where strategic payoffs evolve with observable contexts, and proposes OnGameLearn to learn equilibria and evaluate policies under this uncertainty. It develops statistical guarantees for payoff parameters, Nash equilibria, policy values, and regret.

  • Problem and framework: Contextual bandits use observable features but omit simultaneous strategic interactions, while online matrix games typically assume time-invariant payoffs.These limitations leave unresolved how strategic agents should act when payoffs evolve with contextual information.
  • OnGameLearn: OnGameLearn updates parameter estimates from historical data, computes Nash equilibrium strategies, selects actions, and updates a doubly robust policy-value estimate.In contextual settings, the payoff matrix adapts to observable features such as party size, booking lead time, and length of stay.
  • Problem and framework: Online contextual matrix games model payoff matrices that depend on contextual information available at each decision time.The framework integrates contextual signals directly into multi-player strategic decision-making and equilibrium analysis.
  • OnGameLearn: The method parameterizes payoff matrices by observed context and uses online learning procedures with regularization and minimax optimization to estimate Nash equilibria.The framework studies the canonical two-player zero-sum case, where equilibrium corresponds to a saddle point.
  • Guarantees and evaluation: Simulations and a real-world hotel pricing application demonstrate the effectiveness of OnGameLearn in contextual and strategic decision-making.The algorithm is presented for both multi-armed and contextual matrix-game settings.
  • Guarantees and evaluation: The paper establishes tail bounds, equilibrium consistency, asymptotic normality, sublinear regret, and a doubly robust policy-value estimator with √T consistency.The inference procedures address adaptively collected, non-i.i.d. data and quantify uncertainty in payoff matrix parameters.

2 Framework

The framework models two-player zero-sum matrix games with unknown payoffs, noisy bandit feedback, and strategic policies defined by Nash equilibria. It extends this setting by making each payoff matrix depend on an observed context, so strategies and policy values can also vary with context.

  • Online matrix games: The baseline setting is a repeated two-player zero-sum game with unknown payoff matrix A and simultaneous actions from finite action spaces.The row player pays the observed outcome while the column player receives it.
  • Online matrix games: Bandit feedback reveals only the stochastic reward for the selected action pair, leaving rewards for other action pairs unobserved.The observed reward follows a sub-Gaussian noise model and is recorded with the interaction history.
  • Online matrix games: A Nash equilibrium is a pair of mixed strategies satisfying the matrix-game saddle-point inequalities over both players’ probability simplexes.Under strong convexity and concavity, the corresponding saddle point is unique.
  • Online matrix games: The policy value under strategies x and y is x⊤Ay, while the optimal policy value is attained under the strategic equilibrium.The minimax theorem supports exchanging the players’ optimization order.
  • Online contextual matrix games: Online contextual matrix games reveal context z_t before play and model the payoff matrix M(z_t) as context-dependent while preserving both action spaces.The framework uses a linear parameterization for each action pair and permits more flexible consistent parameterizations.
  • Online contextual matrix games: Context-dependent mixed strategies ϕ(z_t) and ν(z_t) yield expected outcome ϕ(z_t)⊤M(z_t)ν(z_t), with optimal strategies defined by the contextual Nash equilibrium.The contextual policy value is evaluated under the distribution of observed contexts.

3 Proposed Method: OnGameLearn

OnGameLearn iteratively estimates payoffs, computes regularized Nash strategies, explores with bandit policies, and estimates game value doubly robustly. Its contextual version applies the same pipeline to context-dependent payoff parameters and strategies.

  • Core algorithm: OnGameLearn combines payoff-matrix estimation, Nash-equilibrium optimization, bandit exploration, and doubly robust policy-value estimation.The algorithm alternates these components throughout the online interaction.
  • Core algorithm: Regularization convexifies the objective and produces a unique estimated Nash equilibrium used as the players’ strategies.The equilibrium is computed from the estimated payoff matrix.
  • Exploration: UCB, Thompson Sampling, and ϵ-Greedy provide exploration, with clipping or uniform mixing ensuring positive action-selection probabilities.ϵ-Greedy follows the estimated equilibrium with probability 1 − ϵ_t and explores uniformly with probability ϵ_t.
  • Value estimation: The doubly robust estimator combines estimated payoff and strategy models with observed rewards to estimate the matrix-game value.Its consistency can hold when either the propensity-score model or outcome-regression model is correctly specified.
  • Contextual extension: In the contextual algorithm, each action-pair parameter is estimated by ordinary least squares and used to construct a context-dependent payoff matrix.The resulting contextual strategies are computed after the context is sampled.
  • Contextual extension: The contextual version extends UCB, Thompson Sampling, and ϵ-Greedy while clipping exploratory equilibria or mixing with uniform exploration.These mechanisms ensure the positivity condition required for estimation and inference.

4 Theoretical Results

The theoretical results establish estimation, equilibrium-convergence, asymptotic-normality, policy-value, and regret guarantees for online matrix and contextual matrix games.

  • Payoff-matrix estimation: The analysis begins with tail bounds and consistency results for estimating payoff matrices under online exploration.These results cover both the online matrix-game setting and its contextual extension.
  • Equilibrium and strategy convergence: Estimated Nash equilibria and behavior strategies converge to their corresponding true or limiting strategies under the stated assumptions.Contextual behavior strategies converge in ℓ2-norm when the exploration rate converges and the regularization condition holds.
  • Statistical inference: Asymptotic normality results characterize the limiting distributions of payoff-matrix and parameter estimators, with variance depending on exploration and equilibrium behavior.The analysis links conditional action-selection probabilities and optimal strategies to estimator variance.
  • Policy-value inference: The saddle value and doubly robust policy-value estimator achieve convergence rates based on payoff-estimator accuracy and regularization decay.The optimal rate is constrained by the O(t^-1/2) decay of η_t, while the contextual value estimator is described as T-consistent.
  • Contextual extension: In contextual games, the convergence rate matches the online matrix-game result when the context space is bounded.The contextual proof replaces the fixed payoff matrix with the context-dependent matrix M(z_t).
  • Regret: With ϵ_t ≍ t^-1/4, the method obtains a sublinear cumulative Nash-gap regret bound under each of three exploration strategies.The regret analysis does not require uniqueness or positive equilibrium probabilities, allowing multiple Nash equilibria and zero equilibrium probabilities.

5 Empirical Studies

Empirical studies evaluate OnGameLearn in online matrix games and contextual matrix games, finding convergence, valid statistical inference, and consistent policy-value estimation. The experiments compare its exploration variants and regret-based baselines under simulated settings.

  • Online Matrix Games: OnGameLearn's estimated Nash equilibrium converges steadily and remains stable after exploration, while baselines converge more slowly with larger fluctuations.The ϵ-greedy and UCB variants almost completely overlap in the convergence plots.
  • Online Matrix Games: The payoff estimator's SE/MCSD ratio converges to 1, bias approaches zero, and 95% Wald-interval coverage reaches the nominal 95% level for all Aij parameters.The evaluation uses standard-error calibration, parameter-estimation bias, and confidence-interval coverage.
  • Online Matrix Games: The doubly robust value estimator converges to the optimal policy value with the theoretical 1/√T rate.Baseline estimates show larger fluctuations, slower stabilization, or persistent finite-sample bias over the observed horizon.
  • Online Contextual Matrix Games: In contextual simulations, parameter estimates are stable and accurate, while estimated mixed strategies progressively approach the true Nash equilibrium.The contextual results cover three inference metrics and decreasing distances to equilibrium; EXP4 and LC-Tsallis-INF generally do not provide last-iterate equilibrium convergence or statistical inference.
  • Online Contextual Matrix Games: In the contextual value experiment, the doubly robust estimator follows the theoretical convergence rate, whereas LC-Tsallis-INF shows a visible gap from the optimal value.The benchmark slope closely matches the nominal rate established in Theorem 15.

6 Real Data Application

The real-data application models competitive pricing between Hotel 2 and Hotel 4 using contextual features and evaluates OnGameLearn's inference and doubly robust value estimates. Across the reported metrics, estimates approach nominal targets and the value estimator retains the theoretical convergence rate.

  • Data and Model: The hotel model uses advance purchase days, length of stay, and party size as contextual features, with a binary pricing action for each hotel.Hotel 2 is treated as the row player and Hotel 4 as the column player; the lowest observed nightly rate proxies room cost.
  • Statistical Inference: OnGameLearn steadily approaches the nominal SE/MCSD, bias, and coverage levels for hotel-pricing parameter estimates.Figure 7 tracks parameter rays over time, with nominal targets of 1, 0, and 95%.
  • Policy Value: The doubly robust value estimator retains a T^-1/2 convergence rate under bounded equilibrium probabilities.A small fixed lower bound is imposed on estimated equilibrium probabilities to stabilize inverse-probability weights.
  • Competitive Pricing: The expected zero-sum-game value is approximately $29.4, corresponding to an expected loss for Hotel 2 and equal gain for Hotel 4 per transaction.The reported equilibrium value suggests Hotel 4 is more likely to be chosen when both hotels use Nash-equilibrium strategies.

7 Conclusion

The paper presents a policy-learning and evaluation framework for online contextual matrix games, combining contextual payoff modeling, Nash-equilibrium learning, exploration, and statistical inference. It also identifies extensions involving confidence intervals and more general multi-agent settings.

  • Framework and method: OnGameLearn balances exploration and exploitation by extending bandit exploration schemes to online and contextual matrix games.The behavior policy can use UCB, Thompson Sampling, or ϵ-greedy exploration, with clipping or randomization to ensure action coverage.
  • Theoretical guarantees: The framework provides consistency and convergence guarantees for payoff estimates and estimated Nash equilibria.The results include an explicit convergence-rate theorem for the estimated equilibrium and extensions to contextual games under an additional realized error-bound condition.
  • Theoretical guarantees: A doubly robust estimator supports policy-value estimation under the Nash equilibrium, while parameter estimation enables statistical inference with quantified uncertainty.The paper discusses confidence intervals based on parameter estimates and establishes inference procedures for adaptively collected, non-i.i.d. data.
  • Evaluation and future work: Numerical experiments and a real-world application demonstrate the effectiveness of the proposed approach.The conclusion also proposes bootstrap-based Wald confidence intervals for optimal value and extension from two players to more general multi-agent settings.
  • Computation: The contextual implementation constructs each estimated payoff matrix in O(mkd) time and adds O(Nmk) for N gradient descent–ascent iterations.Warm-starting from the previous optimizer can reduce the number of inner iterations when payoff estimates change gradually.

B.3 Extension to Model Misspecification

Under model misspecification, the estimated contextual game converges to a pseudo-payoff game rather than necessarily the game defined by the true conditional mean functions. The section reports consistency results and corresponding simulation analyses.

  • Model misspecification: The analysis considers settings where the working linear contextual payoff model is misspecified.The observed payoff is represented using the true conditional mean together with an error term, while exploration and regularity conditions remain relevant.
  • Policy convergence: Estimated contextual Nash policies converge to the Nash-equilibrium policies of the pseudo-payoff game.Behavior policies converge to clipped or randomized versions of the limiting policies, depending on the exploration strategy.
  • Statistical properties: The payoff estimator admits an asymptotic normal approximation under the misspecified model.The stated results concern parameter estimation under adaptive data collection and model misspecification.
  • Statistical properties: The value estimator converges to the value of the pseudo-true contextual game induced by the Nash equilibrium of M†(z).It does not generally converge to the value of the game induced by the true conditional mean functions φij(z).
  • Additional analyses: The supplementary experiments include misspecification, UCB exploration, larger action spaces, and contextual matrix-game settings.The misspecification results are reported as part of the additional simulation analyses.

C.1 Additional Results for Online Matrix Games

Additional experiments evaluate OnGameLearn under alternative exploration and tuning choices in online matrix games. Under UCB exploration, the reported inference procedure performs well across all three evaluation metrics, consistent with the corresponding theoretical guarantee.

  • UCB exploration: The supplementary results include statistical inference for OnGameLearn under UCB exploration in non-contextual online matrix games.These results are presented alongside the additional Tsallis-INF and contextual-game analyses.
  • UCB exploration: OnGameLearn continues to perform well under UCB across all three evaluation metrics.The findings indicate that the inference procedure is not limited to ϵ-greedy exploration and are reported as consistent with Theorem 5.
  • Contextual UCB results: In the contextual matrix-game setting, OnGameLearn also performs well under UCB across all evaluation metrics.These findings support applicability beyond the original ϵ-greedy strategy and are reported as consistent with Theorem 13.

C.3 Simulation Results under Model Misspecification

Simulations under model misspecification examine OnGameLearn’s estimation and equilibrium behavior, including larger action spaces and multiple exploration strategies. The results support convergence of estimated equilibria, payoff matrices, parameters, and policy values.

  • Model misspecification: Under misspecification, the estimated Nash equilibrium converges to its target and the doubly robust estimator accurately estimates the least-false game value.These findings are reported as consistent with Theorems 20 and 22.
  • Model misspecification: The WLS estimator for the least-false parameters exhibits asymptotic normality, consistent with Theorem 21.Figure C.6 provides the corresponding empirical evidence.
  • Larger action spaces: In the m = k = 4 setting, OnGameLearn provides consistent Nash-equilibrium estimates under both ϵ-greedy and UCB exploration.The two OnGameLearn curves are very close and nearly overlap across all equilibrium coordinates.
  • Larger action spaces: EXP3 and Tsallis-INF do not yield stable or consistent estimates of the Nash equilibrium in the larger action-space experiments.This contrasts with the stability reported for both OnGameLearn exploration strategies.
  • Larger action spaces: The 4 × 4 payoff matrix estimator approaches the nominal reference line across all three evaluation metrics under both exploration strategies.Figures C.9 and C.10 assign one curve to each of the 16 matrix elements.
  • Larger action spaces: OnGameLearn continues to perform well with more actions and significantly outperforms the baselines, while OnGameLearn-UCB converges slightly more slowly.The comparison is reported for the larger-action contextual setting.

D.3.3 Proof of TS

The TS analysis establishes convergence of sampled payoff matrices and their induced behavior strategies, then controls importance ratios and payoff perturbations for value estimation. These steps support the corresponding asymptotic results under the stated equilibrium and margin conditions.

  • Sampled-game convergence: The Thompson-sampled payoff matrix converges in probability to the true payoff matrix entrywise.The proof combines posterior sampling error convergence with consistency of the estimated payoff entries.
  • Sampled-game convergence: Behavior strategies induced by the Nash equilibrium of the Thompson-sampled game converge in probability to the target strategies.The argument uses convergence of the sampled payoff matrix and analogous equilibrium-continuity arguments.
  • Importance-ratio control: Across the exploration strategies, the target-to-behavior importance ratio is eventually bounded uniformly over action pairs.The proof obtains a finite constant after establishing equilibrium convergence and support or positivity conditions.
  • Importance-ratio control: Under the stated margin conditions, the importance ratio is eventually zero for action pairs outside the true equilibrium support.Local support stability keeps those actions outside the estimated equilibrium support for sufficiently large t.

E.5 Asymptotic Normality of Online Estimator (Theorem 13)

Theorem 13 derives asymptotic normality for the online estimator by controlling its martingale score, conditional variance, and weighted design matrix. The resulting rate analysis also establishes convergence of the contextual saddle value.

  • Asymptotic normality: The estimator’s asymptotic normality is established using the Cramer-Wold device and a martingale central limit theorem.The proof verifies conditional Lindeberg and covariance conditions before applying continuous mapping and Slutsky arguments.
  • Variance control: The conditional variance is analyzed through its second-moment limit, with dominated convergence and the law of iterated expectations controlling the contextual terms.These steps identify the limiting covariance needed for the central limit theorem.
  • Variance control: The asymptotic variance estimator is shown to be consistent by combining convergence of its component terms with the continuous mapping theorem.The proof decomposes the variance expression and controls each component separately.
  • Value convergence: The doubly robust value analysis decomposes the error into terms of order Op(T^-1/2) and Op(T^-1), yielding the square-root rate.The second term is asymptotically negligible relative to the first.

F Analysis of Contextual Matrix games under Model Misspecification

The misspecification analysis develops tail, convergence, asymptotic-normality, and value-estimation results for contextual WLS and the induced game. It also identifies conditions needed for square-root-consistent policy-value estimation.

  • Estimator guarantees: Theorem 18 provides a tail bound for the contextual WLS estimator under model misspecification.The result is used to establish consistency of the contextual WLS estimator.
  • Equilibrium and strategy convergence: Theorem 20 establishes convergence of contextual behavior strategies to strategies associated with the least-false contextual game.The theorem assumes that the least-false game has a unique Nash equilibrium for every context.
  • Estimator guarantees: Theorem 21 establishes asymptotic normality of the contextual WLS estimator under model misspecification.The result relies on the conditions stated for the convergent contextual behavior strategies and approximation error.
  • Policy value: Theorem 22 establishes consistency of the contextual value estimator under model misspecification.The proof uses convergence of the target strategies, bounded features, and control of importance ratios and approximation error.
  • Policy value: Under misspecification, the pseudo-value uses pseudo-optimal strategies but evaluates value under the true contextual payoff matrix.Because pseudo-target strategies need not be saddle-point optimal for the true matrix, plug-in value error contains first-order policy-estimation terms.
  • Policy value: A sqrt(T) rate for the value estimator requires an additional orthogonality condition or sufficiently fast policy convergence.Policy consistency alone yields consistency of the value estimator.

G Auxiliary Results

The auxiliary results establish concentration tools for adaptive scalar, matrix, and contextual-martingale quantities, together with continuity properties for equilibria and saddle values. These lemmas provide probability bounds and parameter-stability results used in the paper’s analysis.

  • Concentration bounds: P(St ≤ (1−c)µt) ≤ exp{−µ[c + (1−c) log(1−c)]} gives an adaptive lower-tail bound.The bound uses c ∈ (0,1) and the positivity of c′ = (1−c) log(1−c)+c.
  • Concentration bounds: Matrix Chernoff analysis bounds the lower-tail probability by d exp{−[g(θ)−θ(1−δ)]µt}.The proof constructs a trace-exponential nonnegative supermartingale for adapted positive semidefinite matrices bounded by RId.
  • Concentration bounds: Self-normalized concentration lemmas control adaptive samples and contextual martingales under conditional sub-Gaussian noise and bounded covariates.The contextual result assumes ∥z∥2 ≤ Lz and σij-sub-Gaussian noise for the selected action pair.
  • Equilibrium continuity: If parameter sequences converge and the limiting game has a unique saddle point, every corresponding sequence of saddle points converges to that point.The continuity framework uses the payoff function f over compact strategy simplices and assumptions ensuring attained extrema.
  • Saddle-value continuity: The saddle-value difference is bounded between directional-gradient expressions evaluated at cross-combinations of optimal strategy sets.The bound follows under compact strategy sets, a continuous payoff function, and a continuous parameter gradient.
Loading 2608.17173v1…