Policy Optimization and Statistical Inference for Online Contextual Matrix Games

• URL: http://arxiv.org/abs/2608.17173v1
• Date: Mon, 17 Aug 2026 22:16:10 GMT
• Title: Policy Optimization and Statistical Inference for Online Contextual Matrix Games
• Abstract summary: We introduce emphonline contextual matrix games to integrate contextual information into online games.<n>We also propose emphOnGameLearn, an online learning algorithm that efficiently balances exploration and exploitation across both player actions and contexts.<n>We find that OnGameLearn effectively navigates the intertwined challenges of strategic and contextual decision-making.
• Score: 33.65008472736867
• License: http://creativecommons.org/licenses/by/4.0/
• 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 \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.

Related papers

• A Hybrid Sampling-Based Trajectory Planner with Game-Theoretic Guidance for Autonomous Racing [41.40585589054522]
  We propose a hybrid architecture that integrates game-theoretic reasoning into a sampling-based motion planner.<n>Our approach successfully induces defensive behaviors like blocking without carrying the computational burden of full dynamic game solvers.
  arXiv  Detail & Related papers  (2026-07-15T00:27:36Z)
• Conservative Equilibrium Discovery in Offline Game-Theoretic Multiagent Reinforcement Learning [6.299504742623642]
  We consider the problem in a mixed-motive multiagent setting, where the goal is to solve a game under the offline learning constraint.<n>We extend Policy Space Response Oracles (PSRO), an online game-solving approach, by quantifying game dynamics uncertainty.<n>We propose a novel meta-strategy solver, tailored for the offline setting, to guide strategy exploration in PSRO.
  arXiv  Detail & Related papers  (2026-02-27T23:24:02Z)
• Ranking Joint Policies in Dynamic Games using Evolutionary Dynamics [0.0]
  It has been shown that the dynamics of agents' interactions, even in simple two-player games, are incapable of reaching Nash equilibria.<n>Our goal is to identify agents' joint strategies that result in stable behavior, being resistant to changes, while also accounting for agents' payoffs.
  arXiv  Detail & Related papers  (2025-02-20T16:50:38Z)
• Multi-Step Alignment as Markov Games: An Optimistic Online Gradient Descent Approach with Convergence Guarantees [91.88803125231189]
  Reinforcement Learning from Human Feedback (RLHF) has been highly successful in aligning large language models with human preferences.<n>While prevalent methods like DPO have demonstrated strong performance, they frame interactions with the language model as a bandit problem.<n>In this paper, we address these challenges by modeling the alignment problem as a two-player constant-sum Markov game.
  arXiv  Detail & Related papers  (2025-02-18T09:33:48Z)
• Blending Data-Driven Priors in Dynamic Games [9.085463548798366]
  We formulate an algorithm for solving non-cooperative dynamic game with Kullback-Leibler (KL) regularization. We propose an efficient algorithm for computing multi-modal approximate feedback Nash equilibrium strategies of KLGame in real time.
  arXiv  Detail & Related papers  (2024-02-21T23:22:32Z)
• Finding mixed-strategy equilibria of continuous-action games without gradients using randomized policy networks [83.28949556413717]
  We study the problem of computing an approximate Nash equilibrium of continuous-action game without access to gradients. We model players' strategies using artificial neural networks. This paper is the first to solve general continuous-action games with unrestricted mixed strategies and without any gradient information.
  arXiv  Detail & Related papers  (2022-11-29T05:16:41Z)
• Provably Efficient Fictitious Play Policy Optimization for Zero-Sum Markov Games with Structured Transitions [145.54544979467872]
  We propose and analyze new fictitious play policy optimization algorithms for zero-sum Markov games with structured but unknown transitions. We prove tight $widetildemathcalO(sqrtK)$ regret bounds after $K$ episodes in a two-agent competitive game scenario. Our algorithms feature a combination of Upper Confidence Bound (UCB)-type optimism and fictitious play under the scope of simultaneous policy optimization.
  arXiv  Detail & Related papers  (2022-07-25T18:29:16Z)
• Decentralized Optimistic Hyperpolicy Mirror Descent: Provably No-Regret Learning in Markov Games [95.10091348976779]
  We study decentralized policy learning in Markov games where we control a single agent to play with nonstationary and possibly adversarial opponents. We propose a new algorithm, underlineDecentralized underlineOptimistic hypeunderlineRpolicy munderlineIrror deunderlineScent (DORIS) DORIS achieves $sqrtK$-regret in the context of general function approximation, where $K$ is the number of episodes.
  arXiv  Detail & Related papers  (2022-06-03T14:18:05Z)
• Efficient Competitive Self-Play Policy Optimization [20.023522000925094]
  We propose a new algorithmic framework for competitive self-play reinforcement learning in two-player zero-sum games. Our method trains several agents simultaneously, and intelligently takes each other as opponent based on simple adversarial rules. We prove theoretically that our algorithm converges to an approximate equilibrium with high probability in convex-concave games.
  arXiv  Detail & Related papers  (2020-09-13T21:01:38Z)
• Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium [116.56359444619441]
  We develop provably efficient reinforcement learning algorithms for two-player zero-sum finite-horizon Markov games. In the offline setting, we control both players and aim to find the Nash Equilibrium by minimizing the duality gap. In the online setting, we control a single player playing against an arbitrary opponent and aim to minimize the regret.
  arXiv  Detail & Related papers  (2020-02-17T17:04:16Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.