cs.LGNov 1, 2026

Near-Optimal K\sqrt{K}-Regret for Online Learning in Uninformed Markov Games

Authors: Junyan Liu, Haipeng Luo, Lillian J. Ratliff, Zihan Zhang

Organizations: University of Washington · University of Southern California · Hong Kong University of Science and Technology

Abstract

We study online learning in two-player uninformed Markov games, where the opponent may follow an arbitrary, unknown policy in each episode and the learner does not observe the opponent's actions. [TWYS21] showed that achieving sublinear external regret requires an exponential dependence on the episode length HH. Motivated by this limitation, they studied the weaker notion of Nash-value regret and obtained an O~(K2/3)\widetilde{O}(K^{2/3}) regret bound, where KK is the number of episodes. More recently, [LLZR26] introduced a stronger notion called empirical Nash-value regret and achieved an O~(K)\widetilde{O}(\sqrt{K}) bound when the opponent's non-stationarity is moderate, including the case where the opponent follows a fixed policy. However, whether the K\sqrt{K} rate is achievable in the worst case remained open. In this paper, we resolve this open question by developing an algorithm that achieves O~(H3/2SAK)\widetilde{O}(H^{3/2}S\sqrt{AK}) empirical Nash-value regret against arbitrary opponent policies, where SS is the number of states and AA is the number of learner's actions. Specifically, our algorithm combines global and local planning by maintaining a collection of candidate predictions of future losses, each associated with a policy. Global planning learns which candidates to favor across episodes, while local planning combines their policies differently at each state to make decisions. A key ingredient is to coordinate these two components to control the discrepancy between local loss estimates and the total loss of the executed policy, using only the learner's observed trajectories.

Figures & tables

Explore similar work

Sep 14, 2026

High-Probability Nash Regret for Decentralized Learning in Markov αα-Potential Games: Episodic and Fully Online Asynchronous Algorithms with Applications to Markov Congestion Games

We study decentralized learning of Nash equilibria (NE) in infinite-horizon discounted Markov games under bandit feedback, focusing on Markov αα-potential games. We develop KL-projected natural policy gradient (NPG) algorithms in two settings: an episodic setting with frozen policies during sampling and a fully online setting in which players receive a single realized cost sample per time step and update their policies asynchronously along a continuing trajectory. We establish finite-time high-probability NE regret bounds of order O~(T−1/4)\widetilde O(T^{-1/4}) and O~(T−2/15)\widetilde O(T^{-2/15}) for the episodic and fully online settings, respectively, up to fixed approximation terms. Crucially, our bounds eliminate the distribution-mismatch coefficient, which can scale prohibitively with the size of the state space, while accommodating potential approximation, estimation-oracle bias, and transition sensitivity. We further identify a state-wise potential structure that yields sharper guarantees with additive dependence on the potential approximation error αα. We specialize the framework to independent-resource Markov congestion games (IMCGs), establish their approximate-potential and transition-sensitivity properties, and construct decentralized estimation oracles from realized costs. As an application, we introduce strategic online job scheduling on stochastic machines and obtain a scalable decentralized algorithm for learning stable dispatching policies. Overall, our results provide the first finite-time high-probability NE regret guarantees for fully online asynchronous decentralized learning in Markov αα-potential games, remove distribution-mismatch coefficients from the regret bounds, accommodate fixed estimation-oracle bias, and provide scalable decentralized learning with finite-time guarantees for IMCGs.
Sep 18, 2026

Multiplicative Optimism for Constant Regret in Games

We introduce Multiplicatively Optimistic Regret Matching (MORM), an uncoupled learning rule for finite general-sum games. Under simultaneous full-information self-play, every player achieves external regret O(nlog⁡d)O(\sqrt n\log d) uniformly over all horizons, using only one-step optimism. The analysis combines a potential-based regret-matching argument with multiplicative stability and Hellinger control of strategy movement. A learning-rate safeguard additionally gives O(Tlog⁡d)O(\sqrt{T\log d}) regret in the face of adversarial utilities.
May 13, 2026

Offline Two-Player Zero-Sum Markov Games with KL Regularization

We study the problem of learning Nash equilibria in offline two-player zero-sum Markov games. While existing approaches often rely on explicit pessimism to address distribution shift, we show that KL regularization alone suffices to stabilize learning and guarantee convergence. We first introduce Regularized Offline Sequential Equilibrium (ROSE), a theoretical framework that achieves a fast O~(1/n)\widetilde{\mathcal{O}}(1/n) convergence rate under unilateral concentrability, improving over the standard O~(1/n)\widetilde{\mathcal{O}}(1/\sqrt{n}) rates in unregularized settings. We then propose Sequential Offline Self-play Mirror Descent (SOS-MD), a practical model-free algorithm based on least-squares value estimation and iterative self-play updates. We prove that the last iterate of SOS-MD attains the same O~(1/n)\widetilde{\mathcal{O}}(1/n) statistical rate up to a vanishing optimization error of order O~(1/T)\widetilde{\mathcal{O}}(1/\sqrt{T}) in the number of self-play iterations TT.