RECORD
Online Learning in Unknown Markov Games
Machine Learning · Submitted 28 Oct 2020
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim We then consider a weaker notion of regret by competing with the \emph{minimax value} of the game, and present an algorithm that achieves a sublinear $\tilde{\mathcal{O}}(K^{2/3})$ regret after $K$ episodes.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
We study online learning in unknown Markov games, a problem that arises in episodic multi-agent reinforcement learning where the actions of the opponents are unobservable. We show that in this challenging setting, achieving sublinear regret against the best response in hindsight is statistically hard. We then consider a weaker notion of regret by competing with the \emph{minimax value} of the game, and present an algorithm that achieves a sublinear $\tilde{\mathcal{O}}(K^{2/3})$ regret after $K$ episodes. This is the first sublinear regret bound (to our knowledge) for online learning in unknown Markov games. Importantly, our regret bound is independent of the size of the opponents' action spaces. As a result, even when the opponents' actions are fully observable, our regret bound improves upon existing analysis (e.g., (Xie et al., 2020)) by an exponential factor in the number of opponents.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | We study online learning in unknown Markov games, a problem that arises in episodic multi-agent reinforcement learning where the actions of the opponents are unobservable. | background 0.91 | 0.18 | 0.03 | asserted 0.96 |
| s1 | We show that in this challenging setting, achieving sublinear regret against the best response in hindsight is statistically hard. | result 0.94 | 0.89 | 0.19 | asserted 1.00 |
| s2 | We then consider a weaker notion of regret by competing with the \emph{minimax value} of the game, and present an algorithm that achieves a sublinear $\tilde{\mathcal{O}}(K^{2/3})$ regret after $K$ episodes. | result 0.51 | 0.96 | 0.62 | asserted 1.00 |
| s3 | This is the first sublinear regret bound (to our knowledge) for online learning in unknown Markov games. | contribution 0.47 | 0.88 | 0.38 | asserted 0.95 |
| s4 | Importantly, our regret bound is independent of the size of the opponents' action spaces. | result 0.91 | 0.92 | 0.13 | asserted 1.00 |
| s5 | As a result, even when the opponents' actions are fully observable, our regret bound improves upon existing analysis (e.g., (Xie et al., 2020)) by an exponential factor in the number of opponents. | interpretation 0.73 | 0.80 | 0.13 | asserted 1.00 |
What was examined, and what was not
- arXiv listing abstract v2
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original abstract
We study online learning in unknown Markov games, a problem that arises in episodic multi-agent reinforcement learning where the actions of the opponents are unobservable. We show that in this challenging setting, achieving sublinear regret against the best response in hindsight is statistically hard. We then consider a weaker notion of regret by competing with the \emph{minimax value} of the game, and present an algorithm that achieves a sublinear $\tilde{\mathcal{O}}(K^{2/3})$ regret after $K$ episodes. This is the first sublinear regret bound (to our knowledge) for online learning in unknown Markov games. Importantly, our regret bound is independent of the size of the opponents' action spaces. As a result, even when the opponents' actions are fully observable, our regret bound improves upon existing analysis (e.g., (Xie et al., 2020)) by an exponential factor in the number of opponents.
Human review
How the literature uses it
10 arXiv papers cite this in 16 sentences
Papers citing it · 10 sentences without a confident label
Compares with it 2 papers
-
[ref] focused on the exploration aspect for finite-horizon settings, and focused on minimizing a weak notion of regret without providing convergence guarantees under self-play.[Note that the same update rule with different stepsize and bonus choices and a certified policy technique, however, can return a non-Markovian approximate Nash equilibrium policy pair in the self-play setting; see [ref] for more details.] [ref] presented an optimistic variant of the gradient descent-ascent method that shares similar desired properties with our learning dynamics, with a strong guarantee of last-iterate convergence rates.
Decentralized Q-Learning in Zero-sum Markov Games · Introduction · 1.00
-
A concurrent work [ref] studies zero-sum games under a different online agnostic setting with PO methods and achieves an $(K^2/3)$ regret.
Provably Efficient Fictitious Play Policy Optimization for Zero-Sum Markov Games with Structured Transitions · Related Work · 0.96
Cites it as background 4 papers
-
In the online setting [ref] , the goal is to achieve low regret in presence of an adversarial opponent.
Provably Efficient Algorithms for Multi-Objective Competitive RL · Related Work · 0.90
-
Centralized MARL Sample-efficient learning of Markov Games has been studied extensively in a recent surge of work [ref] .
Breaking the Curse of Multiagency: Provably Efficient Decentralized Multi-Agent RL with Function Approximation · Related work · 0.98
-
The work of [ref] develops an algorithm for multi-player general-sum that is agnostic of other agents' actions.
Taming Equilibrium Bias in Risk-Sensitive Multi-Agent Reinforcement Learning · Related Work · 0.94
What it cites · 23 sentences without a confident label
Uses the method or tool of 1 paper
-
In this paper, we study online learning in unknown Markov games using , which is based on the algorithm of [ref] . achieves $(K^2/3)$ regret after $K$ episodes.
Near-Optimal Reinforcement Learning with Self-Play · Conclusion and Future Work · 0.88
Compares with 2 papers
-
If the other player also adopts the new $√(H logB/B t)$ policy update parameter, then the sample complexity of can actually be improved upon [ref] by an $√(H)$ factor to $(H^5S(A+B) / ϵ^2)$.
Near-Optimal Reinforcement Learning with Self-Play · The algorithm · 0.80
-
In this setting, the regret bound in [ref] becomes $(√(H^3 S^3 ∏_i=1^m A_i^3 T))$, which depends exponentially on $m$.
Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium · Multi-player general-sum games · 0.83
Cites as support 1 paper
-
However, even in the informed setting, achieving sublinear regret in this form is computationally hard [ref] .
Near-Optimal Reinforcement Learning with Self-Play · Problem setup · 0.99
Cites as background 6 papers
-
The idea of Nash V-learning first appears in [ref] .
Near-Optimal Reinforcement Learning with Self-Play · Introduction · 0.89
-
There is a recent line of work focusing on achieving near-optimal sample complexity in offline two-player zero-sum MGs [ref] .
Provable Self-Play Algorithms for Competitive Reinforcement Learning · Related work · 0.99
-
There is a recent line of work focusing on achieving near-optimal sample complexity in offline two-player zero-sum MGs [ref] .
A Sharp Analysis of Model-based Reinforcement Learning with Self-Play · Related work · 0.99
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.