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

We thank the reviewer for the valuable feedback.

"The paper is too dense, ... without looking at the appendix."

While two subroutines for Algorithm 3 were put in the appendix, these are fairly standard subroutines and a mere distraction. In fact, we moved it for the sake of better readability – regardless, if one is unfamiliar with them, they can easily find it in the appendix (we give simple embedded hyperlinks for ease of navigation).

We do discuss at length high-level intuitions behind every key result, idea and algorithm in the main text. The intuition and the details for the technical proofs are also presented in the appendix, which are not required for understanding our main results. It is worth noting that other reviewers commended us on the clarity of writing and presentation.

The notion of "consistent adversary"

To be clear, consistency is a sufficient condition for learnability. In fact, we can weaken it to be approximately consistent (see discussion with Reviewer 1MKG). As we say on Lines 255-261, consistency implies that, given any $(h,s,a)$, the response $f([\pi]^m)_h(\cdot|s)$ stays the same across all policies $\pi$ such that $\pi_h(s) = a$. Thus, given any $(h,s)$, there are $A$ possible ways the adversary can play in step h at state s.

Here is what we already say in the paper, but can emphasize it all in one place, per your suggestion.

• (a) Adversary being consistent does not imply that it is sub-optimal. On the contrary, we assume that the adversary is all knowledgeable and has infinite computational power to have figured out the optimal response to any strategy of the learner. So being consistent does not take away any power from the adversary.
• (b) A consistent adversary does not always play the same strategy when the learner adopts the same strategy at (s,h). The adversary’s strategy does not depend only on the learner's strategy at (s,h), but also what the learner played in previous (m-1) episodes.
• (c) We agree that consistency may be too strong to seem necessary for ensuring learnability. We believe that something weaker, e.g., approximate consistency (i.e., small deviations) should still be fine. That could be an avenue for future work. What we have currently is still a very interesting result as it gives an easy to understand notion which is sufficient for learnability.

"The notion of policy regret is very strong ... Hence, this notion of regret feels a bit arbitrary to me."

Regarding “Policy Regret it Arbitrary”, We could not disagree more with the reviewer. We argue that if the environment is adaptive/reactive, i.e., the actions of the opponent depend on learner’s past actions then no other notion of regret even makes sense. This is what has already been argued and settled in numerous papers before us. This is what motivated policy regret in the first place (see the paper by Arora et al. ICML 2012.) So, not the notion of policy regret is not arbitrary. If you want to do counterfactual learning, that is the only notion of regret that even makes sense. Of course, if you are in a setting where the environment is oblivious to your actions (e.g., forecasting weather), then you do not need policy regret – but most real world applications are not like that.

For instance, consider the following scenario: a big investing firm unveils its new trading software, which implements the strategy of switching all of the firm’s investments back and forth between Google and Microsoft on a daily basis. This strategy sets off huge fluctuations in the stock market (the reactive environment), and the market crashes. A post hoc regret analysis reveals that any competing strategy (for instance, buying and holding Apple shares) would have lost all the money, too (as the market crashed), thereby making the regret zero and perhaps concluding that there was nothing wrong with the strategy. It is completely ignored that the market crashed in reaction to the algorithm’s actions and would have reacted differently to a different sequence of actions. Clearly, the notion of regret is misleading in a reactive scenario. In other words, minimizing regret against adaptive adversaries may not lead to learning. Policy regret, on the other hand, is a counterfactual notion of regret, which evaluates a competing strategy on the sequence of events that would have been generated if the competing strategy were followed. This is why policy regret is preferred (and only thing that makes sense) when you are up against a strategic opponent.

Regarding “Hardness of minimizing policy regret”. Yes, minimizing policy regret is harder than standard regret since the adversary is given more power. This is why we ask what restrictions can we impose on the adversary so that it is stronger than oblivious adversaries but not completely arbitrary against whom it is impossible to learn. That is also the point of the hardness results. So, Theorems 1-3 are actually very useful results from a theory perspective. Negative results are as valuable as positive results (if not more), as they tell us what is not even possible, so we can stop wasting our time thinking about the problem in that way.

Hopefully, the reviewer sees our contributions differently in the light of our comments above and will reconsider their evaluation of our work. Thanks!

The impossibility results are also very similar to the one of [37].

Except in proof of Thm2 that benefits from a reduction of any latent MDP to a Markov game constructed by [37], our negative results are of completely different nature, and our paper and [37] also solve two completely different problems. Negative result in [37] is about external regret. Our negative results say that policy regret is linear in T or exponentially large when the adversary has unbounded memory or is non-stationary. Can you be more specific about how exactly similar our impossibility results are to the one of [37]?

We thank the reviewer for the valuable feedback.

Question about "approximate consistency" $D$

We thank the reviewer for an interesting suggestion. Our approach estimates the version space of the response function of the adversary using the adversary’s actions. The MLE analysis (Lemma B.1 and B.2) readily enables us to incorporate an inconsistency measure of D into the radius of the version space. Thus, our final policy regret bound should scale linearly with D as a result. We will discuss this extension in more detail in our revision. But we are happy to provide a more detailed analysis here, if the reviewer is interested.

We thank the reviewer for the valuable feedback.

"Weakness 1."

There are three points we would like to make.

• (a) The assumption that the adversary’s behavior is consistent does not imply that it is sub-optimal. On the contrary, we assume that the adversary is all knowledgeable and has infinite computational power to have figured out the optimal response to any strategy of the learner. So being consistent does not take away any power from the adversary.

• (b) A consistent adversary does not always play the same strategy when the learner adopts the same strategy at (s,h). The adversary has memory; that is, the adversary’s strategy does not only depend on the learner’s strategy at (s,h), but also what the learner has adopted in the previous (m-1) episodes.

• (c) We agree with the reviewer that consistent behavior may be too strong to seem necessary for ensuring learnability. In fact, we firmly believe that something weaker, for e.g., approximate consistency (i.e., small deviations) should still be fine. That seems far from trivial and could be an avenue for future work. What we have currently is still a very interesting result as it gives an easy to understand notion which is sufficient for learnability.

"Weakness 2."

Actually, the policy space for the learner can be infinite with appropriate assumptions on its bounded complexity and the response function, but dealing with that largely deviates from the main points we want to convey in this paper. We assumed the learner’s policy space of all deterministic strategies for the sake of simplicity of presentation. More importantly, our paper and [1] are solving two completely different problems (policy regret minimization vs external regret minimization), making the two results incomparable. To be clear, we discussed [1] in our paper only to contrast the differences of the two settings, not to compare the two results.

"Weakness 3."

No. The transition probability still depends on the adversary’s actions. Even when the adversary is consistent, the adversary’s (possibly non-memoryless) response function f can still be arbitrary in any state. The learner does not know and cannot control the response function.

"Weakness 4."

Thank you for the interesting question. However, we argue a low local switching cost algorithm would not be suitable for this case. The consistent behavior assumption has more to do with enabling an efficient estimation of the adversary’s response function, and less to do with the local switching cost behavior. That said, sample efficient algorithms could also be possible for a different structural assumption other than the consistent behavior assumption, as long as it is not necessary to visit all possible policies that the learner can take in order to learn about the adversary’s response behavior (as an extreme example, when $f$ maps all of the learner’s strategies to the same policy, which reduces the problem to single-agent MDP).

We can, more formally, argue that low local switching cost cannot obtain low policy regret in general. Recall that the goal is to achieve low (policy) regret against the benchmark $\max_{\pi} V_1^{\pi, f([\pi]^m)}$. A low local switching cost algorithm would only guarantee that a sequence of consecutive policies $\pi^1, …., \pi^{m-1}$ can be very similar “locally” (e.g., they agree in many but all states and steps) but they are not guaranteed to be identical “globally”. So, even in the episode $m$ that the learner happens to play the optimal policy $\pi^* = arg \max_{\pi} V_1^{\pi, f([\pi]^m)}$, the learner only gets to see the data for playing $\pi^*$ and $f(\pi^1, …, \pi^{m-1}, \pi^*)$. This data can be completely non informative for the purpose of estimating $V_1^{\pi^*, f([\pi^*]^m)}$ in the worst case, since $f(\pi^1, …, \pi^{m-1}, \pi^*)$ can be arbitrarily different from $f([\pi^*]^m)$, even when each $\pi^1, …, \pi^{m-1}$ might be similar to $\pi^*$ locally. For example, let’s say $m-1 \leq H$ and $\pi^i$ agrees with $\pi^*$ in all steps $h \neq i$. In this case, the consistent adversary places no restriction whatsoever in his response $f(\pi^1, …, \pi^{m-1}, \pi^*)$, i.e., $f(\pi^1, …, \pi^{m-1}, \pi^*)$ can literally be anything and disagree with $f([\pi^*]^m)$ in every single state and step.

We thank the reviewer for the valuable feedback.

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?

Thank you for your interesting suggestion. If we augment the past policies as states, the state space will be as large as $S |\Pi|^m$. Since our bound for 1-memory bounded adversary scales polynomially with the number of states, a simple reduction from general $m$ to $m=1$ will not be sample-efficient.

the algorithm developed in the paper requires prior knowledge of $m$

While our algorithms do require some knowledge of $m$, we would like to clarify that it does not need an exact knowledge of $m$. Any upper bound on $m$ is sufficient for our algorithms.