arXiv preprint ·
Near-Optimal $\sqrt{K}$-Regret for Online Learning in Uninformed Markov Games
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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 $\widetilde{O}(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 $\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 $\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 $\widetilde{O}(H^{3/2}S\sqrt{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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Machine Learning
Variational learning of energy-stable macroscopic flow equations from microscopic laws
On Stochastic Continuous-Time Linear System Identification for Adaptive Stabilization
Transport for Conditional Sampling: Foundations and Applications
Efficient Proper Agnostic Learning of Halfspaces
Correctness and Predictive Uncertainty in Bayesian TSK Fuzzy Regression: A Reproducible Evaluation on Tabular and Building-Meter Data
Get the few papers worth your time in Machine Learning every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.