Learning in Markov Games with Adaptive Adversaries: Policy Regret, Fundamental Barriers, and Efficient Algorithms

Summary

This paper provides upper and lower bound on the complexity of learning Markov games. The authors focus on the notion of "policy regret", which already exist in bandit and repeated games and adapt this notion to the general case of episodic Markov games. The first results of the authors are negative results: The authors shows that, in the general case, there are no algorithm achieveing a small regret (Theorem 1, 2 and 3 of the paper, for different variants of the problem). Given these negative results, in a second part, the authors introduce a notion of "consistent adversaries" (Definition 3) and dervive an algorithm that has a small regret against this weak adversary.

Strengths

Markov games are notoriously hard to learn. This paper presents some results to show how hard they are to learn in some specific settings. The paper contains both negative and positive results on classes of problems that can be learned.

Weaknesses

The paper is too dense, at the point that it hurts readability: - the proofs of all results are only in the appendix and no intuition is give in the paper - the algorithms are very hard to read because their presentation is too compact - some parts of the algorithms are only given in appendix As a result, the paper is essentially impossible to understand without looking at the appendix. The notion of "consistent adversary" deserves more discussion: given that a policy is supposed to exploit future, I do not understand why it is consistent for the response of the adversary should essentially only depend on the action in a given state (which is sort of what this assumption implies). The notion of policy regret is very strong, which illustrated by the fact that it is essentially impossible to have an algorithm with a low regret (Theorem 1, 2, 3) unless imposing very strong assumption on the learner (Theorem 4). Hence, this notion of regret feels a bit arbitrary to me. The impossibility results are very similar to the one of [37].

Questions

Please justify the regret notion and the notion of "constistent adversary".

Rating

5

Confidence

2

Soundness

3

Presentation

2

Contribution

3

Limitations

NA.

Summary

This paper studies learning in a dynamically evolving environment modeled as a Markov game (MG) and the adversarial is allowed to be adaptive. Authors focus on the policy regret rather than external regret commonly used by many existing work, and further investigate the fundamental limits on learning MG with different memory size. Finally, authors restrict adversary’s behavior and propose efficient algorithms achieving sublinear policy regret bounds.

Strengths

- Studying how the power (w.r.t. memory and other behaviors characterized by stationarity and consistency) of adversary impacts the learnability is very interesting. - Show statistically hardness for unbounded memory adversary and further show that even if the adversary is stationary, the hardness cannot be alleviated. - Consistency of adversary is introduced and algorithms with sublinear policy regret are proposed for special case m=1 and general case m. - The connections between existing results and related ones are clearly presented.

Weaknesses

No major weaknesses. Other minor points have been well discussed in the paper.

Questions

Apart from imposing additional constraints on the adversary, I am curious whether the proposed algorithm can smoothly degrade with the increase of inconsistency. Specifically, in definition 3, given two sequence of policies $\pi$ and $v$ with the same policy mapping, if we do not assume $f_t(\pi)$ and $f_t(v)$ are exactly the same, but assume the difference is denoted as $D_t$ and let $D=\sum_{t=1}^T D_t$ be the inconsistency. I’d appreciate if authors can discuss this.

Rating

7

Confidence

3

Soundness

4

Presentation

3

Contribution

3

Limitations

Yes

Summary

This paper addresses the problem of designing optimal strategies in Markov Games against adaptive adversaries. Specifically, the paper proposes the notion of $\textit{policy regret}$ which admits the adversary's ability to adaptively change their policies according to the policies applied by the learner. This work demonstrates statistically hardness results for the learner to achieve no-policy-regret when the adversary has unbounded memory or is non-stationary w.r.t different episodes. Further more, under the $\textit{consistent adversary}$ assumption, this work designs $O(\sqrt{T})$-regret algorithms respectively to the scenario when the memory bound for the adversary is 1 or some constant $m$. The algorithms proposed are some optimistic variants of upper confidence bound value iteration.

Strengths

1. This paper move a step further from the previous results in [1] by introducing novel analysis w.r.t. policy regret. 2. Hardness results are shown when assumptions are not met, indicating the necessity of such assumptions. 3. Two proposed algorithms achieve $O(\sqrt{T})$ regret. 4. In general the paper is well-organized and theorems are well-supported by the proof. [1] Qinghua Liu, Yuanhao Wang, and Chi Jin. Learning markov games with adversarial opponents: Efficient algorithms and fundamental limits. In International Conference on Machine Learning, pages 14036–14053. PMLR, 2022

Weaknesses

My concerns and questions mainly focuses on the consistent adversary assumption. 1. While I understand the necessity of proposing some assumptions about the adversary in order for the learner to efficiently learn the adversarial strategy mapping function $f(\pi)$, this assumption doesn't not seem to be a favorable one. Firstly, looking from a game theoretical perspective, it makes sense even for a self-interested adversary to utilize previous information and play differently even when the learner adopts the same strategy at $(s, h)$. For example in a two-player zero-sum game, if the adversary observes that the learner behaves poorly at some certain state $s'$, then it is reasonable for the adversary to play certain strategy which leads to $(s', h+1)$ from $(s, h)$. 2. Furthermore, when the policy space for the learner includes all the deterministic strategies and when the adversary is consistent. The cardinality for the strategy space for the adversary is also finite, this is in sharp contrast with the results in [1] where only one of the two needs to be finite. 3. When the adversary is consistent, is it the case that the transition probability solely depends on the state and the learner? In other words, is this setting equivalent to the setting of single-controller Markov games where the controller is always the learner? 4. When the memory bound for the adversary is greater than 1, this paper proposed an algorithm which is a variant of [2] in order to achieve optimal global switching cost. However, under the consistent adversary assumption, would it be better to consider minimizing local switching cost instead? [1] Qinghua Liu, Yuanhao Wang, and Chi Jin. Learning markov games with adversarial opponents: Efficient algorithms and fundamental limits. In International Conference on Machine Learning, pages 14036–14053. PMLR, 2022 [2] Dan Qiao, Ming Yin, Ming Min, and Yu-Xiang Wang. Sample-efficient reinforcement learning with loglog (t) switching cost. In International Conference on Machine Learning, pages 18031–18061. PMLR, 2022

Questions

See weakness.

Rating

6

Confidence

3

Soundness

4

Presentation

4

Contribution

2

Limitations

N/A

Summary

The paper studies the learning problem in a Markov game against the adaptive adversary. The adversary's policy can depend on all the learner's past strategies. The paper first shows that if the adversary can be fully adaptive, then sublinear policy regret cannot be obtained for the learner. The paper then characterizes the fundamental barriers for the learner to achieve the sublinear regret. The paper shows that if the adversary is $m$-memory bounded, i.e., the adversary's strategy depends at most on the $m$ past strategies of the learner, then the sublinear policy regret is achievable. The paper provides both the lower bound and the efficient algorithm that achieves a regret upper bound at the tight $O(\sqrt{T})$ order.

Strengths

1. Strong lower bounds are established to illustrate how hard it is to minimize policy regret against the adaptive adversary in the Markov game setting, which is fundamentally different from the bandit learning setting. 2. Efficient algorithms are presented in the paper with strong theoretical guarantees.

Weaknesses

1. For the general $m$-memory bounded adversary, the algorithm developed in the paper requires prior knowledge of $m$.

Questions

1. If the adversary is $m$-memory bounded, could we regard the system state as the combination of $(s_t, \pi_t, \dots, \pi_{t-m+1})$ and then reduce everything to the $0$-memory bounded case?

Rating

6

Confidence

2

Soundness

3

Presentation

3

Contribution

3

Limitations

As discussed in the weakness part.