Policy Optimization and Statistical Inference for Online Contextual Matrix Games

Liner Xiang; Yixin Wang; Hengrui Cai

stat.MLAug 17, 2026

Policy Optimization and Statistical Inference for Online Contextual Matrix Games

Authors: Liner Xiang, Yixin Wang, Hengrui Cai

Organizations: Department of Statistics, University of California, Irvine · Department of Statistics, University of Michigan

Abstract

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 online contextual matrix games to integrate contextual information into multi-player online games. We further propose 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 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.

Figures & tables

Figure 1: Overview of OnGameLearn. For contextual matrix games (e.g., hotel pricing), at each time step we: (1) observe the arriving customer’s contextual features; (2) update the parameter estimates using historical data from the replay buffer and the payoff matrix; (3) compute the Nash equilibrium strategies and select actions accordingly; and (4) observe the outcome, update the doubly robust value estimate, and proceed to the next step. The multi-arm setting is simpler without contexts.

Figure 2: Panels (a) and (b) illustrate the convergence of the estimated Nash equilibrium components $\widehat{x}_{t1}$ and $\widehat{y}_{t1}$ toward their true values $x_{1}^{\ast}$ and $y_{1}^{\ast}$ , respectively. The red horizontal lines indicate the corresponding true Nash equilibrium values. The curves for OnGameLearn under $\epsilon$ -Greedy and UCB exploration almost completely overlap. Panels (c) and (d) illustrate the $\sqrt{T}$ -consistency of the doubly robust value estimator $\widehat{V}_{T}^{\mathrm{DR}}$ . Panel (c) shows the trajectory of the average estimated value $\widehat{V}_{T}^{\mathrm{DR}}$ , with the red horizontal line indicating the optimal policy value $V_{A}^{\ast}=1.4$ . Panel (d) presents a log–log plot of $|\widehat{V}_{T}^{\mathrm{DR}}-V_{A}^{\ast}|$ . The red line represents the theoretical ${O}_{p}(T^{-1/2})$ convergence rate.

Figure 3: Consistency and asymptotic normality of payoff estimator $\widehat{A}_{t}$ under $\epsilon$ -Greedy exploration. Left panel : the ratio between the standard error and the Monte Carlo standard deviation, with the red line indicating the nominal level of 1. Middle panel : the bias between the $\widehat{A}_{t}$ and $A$ . Right panel : the coverage probabilities of the 95% two-sided Wald-type confidence interval, with the red line indicating the nominal level of 95%.

Figure 4: Convergence of the policy, measured by the distances between estimated mixed strategies $[\tilde{\phi}_{t}]_{1}$ , $[\tilde{\phi}_{t}]_{2}$ , $[\tilde{\nu}_{t}]_{1}$ , $[\tilde{\nu}_{t}]_{2}$ and the true Nash equilibrium $[{\phi}^{\ast}]_{1}$ , $[{\phi}^{\ast}]_{2}$ , $[{\nu}^{\ast}]_{1}$ , $[{\nu}^{\ast}]_{2}$ . The curves for OnGameLearn under $\epsilon$ -greedy and UCB exploration almost completely overlap.

Figure 5: Consistency and asymptotic normality of estimated parameters $\widehat{\bm{\beta}}^{11}_{t}$ , $\widehat{\bm{\beta}}^{12}_{t}$ , $\widehat{\bm{\beta}}^{21}_{t}$ , $\widehat{\bm{\beta}}^{22}_{t}$ under $\epsilon$ -Greedy exploration

Figure 6: $\sqrt{T}$ -consistency of the doubly robust value estimator $\widehat{V}_{T}^{\text{conDR}}$ .

Figure 7: Consistency and asymptotic normality of the estimated parameters for the hotel dataset. Each ray represents a parameter, with dot colors transitioning from light to dark as the time steps increase. Left panel: Average SE/MCSD, with the red circle indicating the nominal level of 1. Middle panel: Average bias, with the red circle indicating the nominal level of 0. Right panel: Coverage probability, with the red circle indicating the nominal level of 95%.

Figure 8: $\sqrt{T}$ -consistency of the doubly robust value estimates for hotel dataset. The y-axis values of the left panel represent profit (scaled by a factor of 10).

Appendix figures & tables13 assets

Supplementary material from the paper’s appendix.

Appendix

Figure C.1 : Convergence of the estimated Nash equilibrium and $\sqrt{T}$ -consistency of the doubly robust value estimator $\widehat{V}_{T}^{\mathrm{DR}}$ when we choose $\eta_{t}=2.0/\sqrt{t+1}$ for Tsallis-INF.

Figure C.2 : Convergence of the estimated Nash equilibrium and $\sqrt{T}$ -consistency of the doubly robust value estimator $\widehat{V}_{T}^{\mathrm{DR}}$ when we choose $\eta_{t}=4.0/\sqrt{t+1}$ for Tsallis-INF.

Figure C.3 : Consistency and asymptotic normality of payoff estimator $\widehat{A}_{t}$ under UCB exploration.

Figure C.4 : Consistency and asymptotic normality of estimated parameters $\widehat{\bm{\beta}}^{11}_{t}$ , $\widehat{\bm{\beta}}^{12}_{t}$ , $\widehat{\bm{\beta}}^{21}_{t}$ , $\widehat{\bm{\beta}}^{22}_{t}$ under UCB exploration.

Figure C.5 : Convergence of the estimated Nash equilibrium and consistency of the doubly robust value estimator $\widehat{V}_{\dagger,T}^{\mathrm{conDR}}$ under model misspecification.

Figure C.6 : Consistency and asymptotic normality of estimated parameters $\widehat{\bm{\beta}}^{11}_{\dagger,t}$ , $\widehat{\bm{\beta}}^{12}_{\dagger,t}$ , $\widehat{\bm{\beta}}^{21}_{\dagger,t}$ , $\widehat{\bm{\beta}}^{22}_{\dagger,t}$ under $\epsilon$ -Greedy exploration and model misspecification.

Figure C.7 : Convergence of the estimated Nash equilibrium and $\sqrt{T}$ -consistency of the doubly robust value estimator $\widehat{V}_{T}^{\mathrm{DR}}$ when $m=k=4$ .

Figure C.8 : Convergence of all the coordinates of the estimated Nash equilibrium when $m=k=4$ . The curves for OnGameLearn under $\epsilon$ -greedy and UCB exploration almost completely overlap.

Figure C.9 : Consistency and asymptotic normality of the payoff matrix estimator $\widehat{A}_{t}$ under $\epsilon$ -Greedy exploration with $m=k=4$ . Each color corresponds to one element of the $4\times 4$ matrix $\widehat{A}_{t}$ . The 16 curves approach the nominal reference line across all three evaluation metrics.

Figure C.10 : Consistency and asymptotic normality of the payoff matrix estimator $\widehat{A}_{t}$ under UCB exploration with $m=k=4$ . Each color corresponds to one element of the $4\times 4$ matrix $\widehat{A}_{t}$ . The 16 curves approach the nominal reference line across all three evaluation metrics.

Figure C.11 : Convergence of the estimated Nash equilibrium when $m=k=4$ . The curves under $\epsilon$ -greedy and UCB exploration almost completely overlap. The curves under $\epsilon$ -greedy and UCB exploration almost completely overlap.

Figure C.12 : $\sqrt{T}$ -consistency of the doubly robust value estimator $\widehat{V}_{T}^{\text{conDR}}$ when $m=k=4$ .

Figure C.13 : Consistency and asymptotic normality of the estimated parameters $\widehat{\bm{\beta}}_{t}^{11},\widehat{\bm{\beta}}_{t}^{12},\dots,\widehat{\bm{\beta}}_{t}^{44}$ under $\epsilon$ -Greedy and UCB exploration with $m=k=4$ . Each curve corresponds to one parameter component, and all $4\times 4\times 2=32$ curves converge to the nominal reference line across the three evaluation metrics. Upper panel: OnGameLearn- $\epsilon$ -Greedy. Lower panel: OnGameLearn-UCB.

Nash Equilibrium Computation

Nash equilibrium computation develops algorithms for finding stable strategies in strategic, stochastic, and imperfect-information games.

See all 69 papers

Regret, equilibrium, and learning in games: A guided tour
Aug 10, 2026Panayotis MertikopoulosNash Equilibrium Adversarial Bandits
Univ. Grenoble Alpes, CNRS, Inria, Grenoble INP, LIG, 38000 Grenoble, France.
Polylogarithmic Nash Regret in Matrix Games with Bandit Feedback
Sep 28, 2026Yuheng ZhangGame Theory Adversarial Bandits
University of Illinois Urbana-Champaign
Pessimistic Minimax Learning for Public-Private Information Games under Unilateral Coverage
Oct 4, 2026Shuze Daniel Liu, Claire Chen, Jiuqi Wang +1Imperfect-Information Games Zero-Sum Games
Massachusetts Institute of Technology · Purdue University · California Institute of Technology +1

Aug 10, 2026J/K move · Enter open · S save

Regret, equilibrium, and learning in games: A guided tour

Panayotis Mertikopoulos

Univ. Grenoble Alpes, CNRS, Inria, Grenoble INP, LIG, 38000 Grenoble, France.

Nash Equilibrium Adversarial Bandits

Open paper AskPDF arXiv

This note aims to serve as an entry point to the literature on learning in games, a topic with significant theoretical appeal and a wide range of applications -- from machine learning and data science to economics and beyond. Our presentation is structured around two complementary viewpoints: We first consider a single agent -- the learner -- engaged in a sequential decision process in an unknown, non-stationary, and possibly adversarial environment. We then examine what happens when the environment is shaped by the decisions of several interacting agents, not necessarily aware of each other's actions or goals, and all seeking to improve their individual rewards. In this general context, we examine a family of regularized learning policies based on best-responding to the past history of play, up to a regularization penalty intended to encourage exploration and prevent over-commitment to suboptimal choices. In the single-agent setting, we present some basic regret bounds for regularized learning in adversarial multi-armed bandits; in the multi-agent setting, we describe an ergodic equilibrium convergence result for zero-sum games in the spirit of classical results on fictitious play, as well as a "folk theorem" linking strategic and dynamic notions of stability -- Nash equilibria and attracting points of regularized learning, respectively. We pay special attention to the information available to the players and, through a unified analysis framework, we study both oracle- and payoff-based (bandit) methods. Our goal is to provide a coherent and comprehensible -- albeit, by necessity, not comprehensive -- account of some recent ideas in the field, and to discuss their implications for the study of rationality.

Abstract

Nash Equilibrium Computation

Explore similar work

Regret, equilibrium, and learning in games: A guided tour

Polylogarithmic Nash Regret in Matrix Games with Bandit Feedback

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