Search papers, labs, and topics across Lattice.
This paper introduces online contextual matrix games to address the complexities of multi-player decision-making in dynamic contexts, particularly in competitive pricing scenarios like hotel bookings. The authors propose OnGameLearn, an innovative online learning algorithm that adeptly balances exploration and exploitation while providing robust statistical guarantees, including convergence to Nash equilibrium and sublinear regret bounds. Empirical results demonstrate that OnGameLearn successfully integrates contextual information with strategic interactions, outperforming existing methods in both simulated environments and real-world applications.
OnGameLearn not only navigates the complexities of strategic interactions but also adapts to evolving contextual signals, achieving superior performance in competitive pricing scenarios.
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.
