Near-Optimal √K-Regret for Online Learning in Uninformed Markov Games
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 H. Motivated by this limitation, they studied the weaker notion of Nash-value regret and obtained an Õ(K2/3) regret bound, where K is the number of episodes. More recently, [LLZR26] introduced a stronger notion called empirical Nash-value regret and achieved an Õ(√K) bound when the opponent's non-stationarity is moderate, including the case where the opponent follows a fixed policy. However, whether the √K rate is achievable in the worst case remained open. In this paper, we resolve this open question by developing an algorithm that achieves Õ(H3/2S√(AK)) empirical Nash-value regret against arbitrary opponent policies, where S is the number of states and A 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.
Related
- Online tensor learning: Computational and statistical trade-offs, adaptivity and optimal regret
- High-Probability Nash Regret for Decentralized Learning in Markov α-Potential Games: Episodic and Fully Online Asynchronous Algorithms with Applications to Markov Congestion Games
- Dimension-Optimal Dynamic Regret in Exp-Concave Online Learning
- Optimal Multiclass Online Regret with Arbitrary Label Spaces
- Optimal Regret for Online Storage Control via Cumulative Policies
BibTeX
@misc{liu2026nearoptimal,
title = {{Near-Optimal $\sqrtK$-Regret for Online Learning in Uninformed Markov Games}},
author = {Junyan Liu and Haipeng Luo and Lillian J. Ratliff and Zihan Zhang},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.01649},
eprint = {2611.01649},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.01649},
}
RIS
TY - UNPB
TI - Near-Optimal √K-Regret for Online Learning in Uninformed Markov Games
AU - Junyan Liu
AU - Haipeng Luo
AU - Lillian J. Ratliff
AU - Zihan Zhang
PY - 2026
DA - 2026/11/01
PB - arXiv
DO - 10.48550/arxiv.2611.01649
UR - https://arxiv.org/abs/2611.01649
AB - 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 H. Motivated by this limitation, they studied the weaker notion of Nash-value regret and obtained an Õ(K^2/3) regret bound, where K is the number of episodes. More recently, [LLZR26] introduced a stronger notion called empirical Nash-value regret and achieved an Õ(√K) bound when the opponent's non-stationarity is moderate, including the case where the opponent follows a fixed policy. However, whether the √K rate is achievable in the worst case remained open. In this paper, we resolve this open question by developing an algorithm that achieves Õ(H^3/2S√(AK)) empirical Nash-value regret against arbitrary opponent policies, where S is the number of states and A 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.
ER -