OnGameLearn algorithm blends context and game theory for adaptive pricing

Online decision-making has long faced a split: contextual bandits optimize single-agent choices using features like demand or seasonality, but ignore that competitors also react; while online matrix games model strategic interactions through Nash equilibrium, yet assume fixed payoffs that never adapt to context. In a new arXiv paper (2608.17173), researchers Liner Xiang, Yixin Wang, and Hengrui Cai close this gap by formally defining online contextual matrix games, where payoffs depend on both player actions and observable context. They then propose OnGameLearn, an algorithm that jointly explores and exploits across actions and contexts, learning the payoff matrix and equilibrium strategy online.

OnGameLearn comes with rigorous statistical guarantees: tail bounds on the estimated payoff matrix, convergence of the estimated Nash equilibrium to the true one, asymptotic normality of parameter estimators, and a sublinear regret bound that ensures near-optimal decisions over time. The team also defines a novel policy value for matrix games and builds a doubly robust estimator that converges at the optimal √T rate, even when parts of the model are misspecified. In simulated environments and a real-world hotel pricing setting, OnGameLearn outperforms baselines that consider only single-agent context or only strategic play, demonstrating practical gains in dynamic competitive pricing.