Policy-Regret Minimization in Markov Games with Function Approximation

Thank you for the positive feedback and the detailed comments.

How close / related is the batching approach followed here, and formally used to get (2), to the one in Arora et al. (2012)? Somehow, I have the feeling that a part of the intuition remains: exploiting the m-bounded memory assumption to get back to standard external regret (for Markov games) on sufficiently long batches, of sizes $K$ proportional to $\sqrt{T}$

Yes, the batching is to exploit the m-bounded memory as in Arora et al 2012. The key technical challenge is, however, how to bound the regret within a batch in our case, while Arora et al 2012 use the worst-cast bound within a batch (and thus obtain T^{⅔} regret).

It would be great to better emphasize where exactly the improvements were made possible. To me, the key point would be Definition 4 vs. Assumption 3, is that correct?

The conditions that enable the improvements are Definition 4 vs Assumption 3 (as you mentioned), and the Eluder conditions in Section 5.1, and bracketing number in Definition 5.

Also, the use of previous techniques (batching as in Arora et al., 2012, and likelihood fitting, as in Nguyen-Tang and Arora, 2024) could be better acknowledged in the comments on Algorithm 1 on page 6.

Thank you. We will be more clear about it in the revision.

The independence of the bound of Theorem 1 in the cardinality of the state and action spaces is a bit of an overstatement: indeed, there are implicit dependencies through the complexity measures introduced. This claim should probably be toned down

Thank you. We will be more clear about it in the revision.

Section 1.1: if the same intuitions for batching as in Arora et al. (2012) apply, you should acknowledge them here

We will acknowledge Arora et. al. (2021) there when we mention batching. It’s worth noticing that Arora et. al. (2021) use the worst-case bound on the in-batch data error while bounding the in-batch data error is a key technical challenge in our setting, thus Section 1.1.

Eq. (1): is the $\ell_1$ in the right-hand side norm the total-variation distance?

Yes.

Line 161, Bellman operator: I think it takes a function as input, and not an element of $\mathbb{R}^{S \times A \times B}$

An element of $\mathbb{R}^{S \times A \times B}$ is a function from $S \times A \times B$ to $\mathbb{R}$

Line 163: what is $z$ I guess a triplet $(s,a,b)$. Then, given the notation introduced right after, it should rather be denoted by $x$.

Yes. It's $x$. Thank you.

Line 163: rather P_{h+1} (not a P with a double bar)

Thank you.

Lines 179-180 (first column): I guess you refer to Theorem 3 of Nguyen-Tang and Arora (2024)? Their result is about a rate $\sqrt{T}$, but with a large constant, which to me is a sublinear policy regret

Yes, you are correct, we meant sample-efficient, rather than sublinear policy regret. We’ve revised it to: “policy regret minimization is not sample-efficient against”

Line 266 (both columns): I think it should be $\Psi_1 \times \ldots \Psi_H$

Yes. We've revised it accordingly.

Thank you for your constructive feedback.

I would like to confirm if adaptive adversary this paper is studying is just the standard adversary in robust RL via adversarial training, where players are modeled as max-min game.

No, the adaptive adversary in our paper adapts to the learner’s past and current strategies, while the adversary in robust RL only adapts to the learner’s current strategy ($m=1$ in our terminology). The settings are also different because we look at policy regret which makes sense in such an adaptive adversary setting. We give a regret bound, not just convergence to equilibrium.

In your introduction, authors mention the prior work that establishes the fundamental barriers for policy regret minimization in Markov games. And then highlighting two motivations of this work: (1) the consistent behavior is restricted (2) large state/action space. Could you elaborate more about (1) compared with your method, explaining the mathematical equations.

For any two sequences of the learner’s policies, if the two sequences agree in a certain step $h$ and state $s$, then the adversary’s responses to the two sequences also agree in step $h$ and state $s$. This enables us to decompose the response into states and steps independently thus enabling sample-efficient learning in the tabular case. The idea of this assumption is to encode that the adversary responds similarly to two similar sequences of policies. But it does not work for large state space problems and is too restrictive. The Lipschitzness assumption is much more relaxed. See line 225-261 for our explanation.

Is not "the adversary behavior does not change over time" mentioned in your manuscript a strong assumption in practice? Could you explain more how possible you can get rid of this assumption and whether it is common to limit adversary behavior?

If we get rid of that assumption, policy regret minimization is not sample-efficient anymore, as proven in Nguyen-Tang & Arora 2024. That’s why we consider it in the current paper. Even though the response function does not change over time, it is still powerful as it can remember the learner’s past and current strategies. The adversary is also given unlimited computation power to come up with whatever response function that they can compute using the learner’s past strategies. The simplest example is general-sum games, where given a policy for the learner, the adversary can use any computational power to compute the best-response policy that maximizes its utility given the learner’s policy.

Thank you for your feedback.

Comparisons are carried out against it which is reasonable, but how does this work compares to other literature in Markov games and adversarial-opponent learning is not addressed.

Much of the prior work in Markov games and adversarial-opponent learning focus on regret, while we focus on policy regret. The study of policy regret against adaptive adversaries has been settled in prior work, e.g. extensive body of work building on the work of Arora et al. 2012; see the second paragraph in our introduction section. We also refer the reader to the related work section of Nguyen-Tang & Arora, 2024a for a broader context. Nonetheless, we can expand the discussion of other related work if the reviewer has specific suggestions.

Remark 2 on the tri-level optimization problem makes the algorithm not tractable to be used in practice

Actually, the optimization can be viewed as a bi-level optimization since $\pi$ and $\mu$ can be combined into one optimization variable. Yes, it is intractable in general, but that is the case for any RL problem with general function approximation. However, the optimization problem is tractable in the linear case.

Line 152: I believe (s) in max operator is not meant to be from A but from S

Yes. Thank you for pointing out.

Line 361: should phi be of subscript i instead of t? The same for mu in line 423

No. The preconditions in the Eluder conditions evaluate the current models (associated with subscript $t$) in the past data (associated with subscripts $i < t$).

Line 369: should it be log T?

No. It's $\log t$. But bounding with $\log T$ is also fine.

What is the applicability of the eluder-condition on function approximations in real applications?

Any learning theoretic result needs to define a notion of complexity of the hypothesis class or the task we are learning to give sufficient (and sometimes necessary) conditions for learning. The Eluder dimension is one such measure for online learning and RL problems. The Eluder condition here is used to control (and thus inform) the convergence rate of an optimistic algorithm when function approximation is used. In real applications, if you use optimistic algorithms with a form of function approximation, estimating the eluder condition will provide insight into how quickly your algorithm will converge to an optimal policy.

The paper only mentions linear function approximation, what about the non-linear cases? Does this algorithm scale or not and what are the challenges for extending it?

We mention the linear case as a concrete example. The results in the paper apply to any nonlinear case, as long as the Eluder conditions hold. For computational efficiency, our algorithm is efficient for tabular and linear cases, but it is likely not tractable for general function approximation, as is the case for RL with general function approximation.

I didn’t understand why the adversary derives its policy based on a sequence of learner policies and not just the current one? I understand that this might be a subset of your setting when m=1 but why in general?

In real-world applications, it is almost always the case that the adversary chooses its policy based on a sequence of the learner's policies. In fact that is a general setting in any multi-step game. For example, consider a spam filter that is trained using online learning, updating its model daily based on newly labeled examples. Spammers act as adaptive adversaries: they probe the system by sending test emails and observing which ones evade detection, then evolve their evasion strategies based on the observed sequence of model updates. Importantly, the adversary’s strategy is not fixed—it adapts over time in response to the entire history of the learner’s policies. This interaction cannot be fully captured by assuming a static or memoryless adversary, since the adversary’s behavior depends on trends or patterns in the learner’s updates. Other similar settings appear in personalized recommendation systems, auctions, online dating, political negotiations, finance, drug discovery, etc.

I also didn’t understand the importance of the “warm up” step on line 6 of the algorithm

During the first $m-1$ episodes of each epoch, the adversary responds with possibly $m-1$ different strategies. From episode $m$ onward, the adversary responds with the same strategy, due to being memory-bounded by $m$. There’s nothing the learner can learn about the adversary during the first $m-1$ episodes but the $m^{th}$ episode onward. Thus, the data collected during the first $m-1$ episodes are not helpful for minimizing the policy regret, thus discarded.