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, 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 xt1 and yt1 toward their true values x1∗ and y1∗ , respectively. The red horizontal lines indicate the corresponding true Nash equilibrium values. The curves for OnGameLearn under ϵ -Greedy and UCB exploration almost completely overlap. Panels (c) and (d) illustrate the T -consistency of the doubly robust value estimator VTDR . Panel (c) shows the trajectory of the average estimated value VTDR , with the red horizontal line indicating the optimal policy value VA∗=1.4 . Panel (d) presents a log–log plot of ∣VTDR−VA∗∣ . The red line represents the theoretical Op(T−1/2) convergence rate.
Figure 3: Consistency and asymptotic normality of payoff estimator At under ϵ -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 At 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 [ϕ~t]1 , [ϕ~t]2 , [ν~t]1 , [ν~t]2 and the true Nash equilibrium [ϕ∗]1 , [ϕ∗]2 , [ν∗]1 , [ν∗]2 . The curves for OnGameLearn under ϵ -greedy and UCB exploration almost completely overlap.
Figure 5: Consistency and asymptotic normality of estimated parameters βt11 , βt12 , βt21 , βt22 under ϵ -Greedy exploration
Figure 6: T -consistency of the doubly robust value estimator VTconDR .
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: 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 T -consistency of the doubly robust value estimator VTDR when we choose ηt=2.0/t+1 for Tsallis-INF.
Figure C.2 : Convergence of the estimated Nash equilibrium and T -consistency of the doubly robust value estimator VTDR when we choose ηt=4.0/t+1 for Tsallis-INF.
Figure C.3 : Consistency and asymptotic normality of payoff estimator At under UCB exploration.
Figure C.4 : Consistency and asymptotic normality of estimated parameters βt11 , βt12 , βt21 , βt22 under UCB exploration.
Figure C.5 : Convergence of the estimated Nash equilibrium and consistency of the doubly robust value estimator V†,TconDR under model misspecification.
Figure C.6 : Consistency and asymptotic normality of estimated parameters β†,t11 , β†,t12 , β†,t21 , β†,t22 under ϵ -Greedy exploration and model misspecification.
Figure C.7 : Convergence of the estimated Nash equilibrium and T -consistency of the doubly robust value estimator VTDR 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 ϵ -greedy and UCB exploration almost completely overlap.
Figure C.9 : Consistency and asymptotic normality of the payoff matrix estimator At under ϵ -Greedy exploration with m=k=4 . Each color corresponds to one element of the 4×4 matrix At . 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 At under UCB exploration with m=k=4 . Each color corresponds to one element of the 4×4 matrix At . 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 ϵ -greedy and UCB exploration almost completely overlap. The curves under ϵ -greedy and UCB exploration almost completely overlap.
Figure C.12 : T -consistency of the doubly robust value estimator VTconDR when m=k=4 .
Figure C.13 : Consistency and asymptotic normality of the estimated parameters βt11,βt12,…,βt44 under ϵ -Greedy and UCB exploration with m=k=4 . Each curve corresponds to one parameter component, and all 4×4×2=32 curves converge to the nominal reference line across the three evaluation metrics. Upper panel: OnGameLearn- ϵ -Greedy. Lower panel: OnGameLearn-UCB.
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.
We study Nash regret minimization in unknown finite matrix games with bandit payoff feedback and observed opponent actions. We develop Optimistic Payoff Balancing (OPB), which achieves instance-dependent O(log2T) Nash regret against arbitrary adaptive opponents, including games with nonunique equilibria. This resolves the open problem posed by Maiti et al. (2025), extending their polylogarithmic guarantee under bandit feedback from 2×2 games to arbitrary finite dimensions. To handle nonunique equilibria, we construct a reference strategy that leaves room for local adjustments. We order independent payoff differences by estimation accuracy and scale these adjustments by uncertainty, allowing the learner to exploit the opponent's imbalance to offset estimation costs. Our result thus shows that observing opponent actions suffices for polylogarithmic Nash regret in general finite matrix games.
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 O~(1/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 O~(1/n+1/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.
Shuze Daniel Liu, Claire Chen, Jiuqi Wang +1
Massachusetts Institute of Technology · Purdue University · California Institute of Technology +1