Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposes an algorithm Decentralized Optimistic hypeRpolicy mIrror deScent (DORIS) for decentralized policy learning in Markov games with function approximations. The setting is "policy revealing", where the opponents (could be adversarial) would reveal its previous policies to the agent for making decisions.

To combat non-stationarity, DORIS (Algorithm 1) mains a "hyperpolicy", which is a probability distribution over policies of the agent, and uses Hedge / mirror descent (MD) to update the hyperpolicy, with estimated value functions. The value function is estimated using optimism in LSPE, as shown in Algorithm 2.

To upper bound the value function estimation errors, the authors proposed a new complexity measure called Bellman Evaluation Eluder (BEE) dimension of function classes, with discussions of its relation to existing measures like Eluder dimension.

Under finite policy class Assumptions 1 and 5, and realizability and completeness Assumptions 2, 3 and 4, the authors proved that the proposed DORIS algorithm achieves $\sqrt{K}$ regret comparing to best policy in hindsight in both oblivious and adversarial opponent settings, as shown in Theorems 1 and 2, where $K$ is the number of episodes.

Finally, Corollary shows that if every agent is playing DORIS algorithm simultaneously, then with high probability the uniformly mixed policy can find a $\epsilon$-approximate coarse correlated equilibrium (CCE) in $\mathcal{O}(1/\epsilon^2)$ iterations.

In the appendix, the authors also studied using DORIS in constrained MDPs and vector-valued MDPs, where similar regret bounds can be obtained.
strength_and_weaknesses: **Strength**:

1. DORIS achieves $\sqrt{K}$ regret in terms of Definition 1, using function approximations with low BEE dimensions, which is a stronger result than NEs.
2. The proposed BEE dimension seems a reasonable complexity measure in this setting, and the authors provided calculations to show the BEE dimensions for kernel MGs and generalized linear complete models.
3. Comparison with existing works are also discussed clearly.

**Weaknesses**:

1. The current results are for episodic settings. How do you generalize the techniques to other scenarios like discounted settings?
2. As noted in the paper, computational efficiency could be a problem for Algorithm 2. Is it possible that for some specific models (such as the generalized linear complete models mentioned), Algorithm 2 can be implemented in practice?
3. I found the policy revealing assumption kind of strong. Revealing the opponents' policies seems weaken the results for adversarial settings studied in the paper. I feel this part needs better argument, such as using examples to show that policy revealing does appear in practice.
clarity,_quality,_novelty_and_reproducibility: **Clarity**: The paper is very clear. Problem settings, notations and definitions, and results are clearly presented. The organization and writing are also easy to follow.

**Quality**: The contribution is clear and important to my understanding. The results are technically sound.

**Originality**: The originality is OK. The policy revealing setting has been introduced before, and the BEE dimension is adapted from existing measures. Combining those results together seems non-trivial.
summary_of_the_review: Overall, I found both the results and the technical contributions interesting and sound.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies the decentralized Markov games with possibly adversarial opponents. Specifically, only one agent in the game can be controlled and others are regarded as adversarial opponents. The paper first considers the general function approximation problem in this setting with the bounded Bellman Evaluation Eluder dimension. To deal with the problem, it proposes an algorithm that is a variant of Online Mirror Descent with optimistic estimated V values. The regret bounds for both oblivious and adaptive adversarial settings are provided. When all agents run this algorithm simultaneously, the mixed policy is also an epsilon-CCE with sample complexity 1/epsilon^2. The paper finally discusses the application of the algorithm in the case of constrained MDP (CMDP) and vector-valued MDP (VMDP).
strength_and_weaknesses: Strength:

The paper first studies the general function approximation problem in the decentralized Markov games, which generalizes previous works [33] for the tabular setting. The work provides complete results including regret bounds for oblivious and adaptive adversaries,
guarantee for CCE results, and also discusses other generalizations to CMDP and VMDP.

Weakness:

1. More comparisons on the regret order with previous works for decentralized Markov games in tabular case (when reducing the current setting to the tabular case) and single-agent MDP with bounded BE dimension.

2. Given previous works for decentralized Markov games in tabular settings and MDP with the bounded BE dimension, the theoretical contribution seems to be weak. The authors discussed in Appendix E that the difference between these works lies in the construction of optimism. Though the learner should build confidence sets for each \mu when faced with each \nu_k, the global optimism seems to hold by modifying the complexity with respect to the two policies of the agent itself and adversarial opponents.

3. Minor: The notation is not easy to follow. The paper uses \mu_i and \mu_{-i} to represent the policy of agent i and the joint policy of other agents while using \pi to represent the joint policy of all agents. Why not use \mu to represent the joint policy? I think it will be more consistent. The paper uses t to represent the index of both epoch and step in Section 2. Perhaps it would be better only use it to represent epoch but use h to represent step. Algorithm 1 shows “run \pi_t =\mu_t \times \nu_t” to collect data. In fact \nu_t is not run by
the controlled agent. 

Question:
Since the paper regards all of other agents as adversarial opponents whose actions cause the non-stationarity of the transition, I am wondering whether such a technique can deal with single-agent MDP with adversarial transitions. Could the authors give some intuitions?
clarity,_quality,_novelty_and_reproducibility: The quality is good. The paper is clear to follow overall. The technique seems to be a combination of previous decentralized Markov games in the tabular case and the general function approximation with low BE dimension but is tailored to the multi-agent case.
summary_of_the_review: In general, this paper generalizes previous works for decentralized Markov games in tabular case to general function approximation with bounded Bellman Evaluation Eluder dimension. Though the technique is not novel, the results are good compliments of existing literature.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper investigates Markov games with adversarial opponents with general function approximation. It proposes provably efficient algorithm $\mathsf{DORIS}$ and a new complexity measure called Bellman Evaluation Eluder (BEE) dimension to aid its analysis. Finally, this algorithm is also extended to Constrained MDPs and Vector-valued MDPs.
strength_and_weaknesses: ### Strengths
This paper extends algorithms for Markov games under adversarial opponents from tabular MDPs to thos with general function approximation, which is considered to be significant. Meanwhile, it proposes the novel Distributional Eluder dimension and corresponding BEE dimension to aid its regret analysis, which may be of independent intereest. Meanwhile, the proposed algorithm $\mathsf{DORIS}$ also has wide application including self-play scenario, CMDPs and VMDPs.

### Weaknesses
It would be idea to have infinite policy class by imposing more assumptions. However, from my perspective, it is okay to leave it as future work for now.
clarity,_quality,_novelty_and_reproducibility: The paper is well-written and highly novel as discussed before. As a side note, it may be better to add a conclusion section to summarize and discuss some potential future work.

### Questions
- What is the motivation to define DE dimension and corresponding BEE dimension?
- Intuitively, what information does BEE dimension captures more compared to BE dimension (or distributional Eluder dimension compared to Eluder dimension)?
- Is that possible to modify $\mathsf{DORIS}$ (or add more assumptions to the Markov games) such that when all players adopt it, their average policy converge to a Nash equilibrium?
- The lower bound in [Liu et al. (2022)] indicates an impossibility result only when both $\Pi$ and $\Pi'$ are large. Therefore, will it be possible to have infinite $\Pi$ if we assume $\Pi'$ to be small?

```
[Liu et al. (2022)] Liu, Q., Wang, Y., and Jin, C. (2022). Learning markov games with adversarial opponents: Efficient algorithms and fundamental limits. arXiv preprint arXiv:2203.06803.
```
summary_of_the_review: This paper proposes the first provably efficient algorithm for Makrov games under adversarial opponents with general function approximation. This algorithm has wide application and its analysis also contains novel tools called BEE dimension.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: ## Paper Summary

This paper considers decentralized (i.e. control over a single agent) learning in Markov games with adversarial multiple opponents.  At a high level, the fundamental goal is to design a no-regret learning policy, i.e. sublinear regret to converge towards the best fixed policy in hindsight.  This is complicated in this model for two reasons (1) the system is non-stationary since the opponents are adversarial and can change over time (2) the algorithm still needs to efficiently generalize through the use of a function class.  The authors tackle this problem by designing a decentralized multi-agent reinforcement learning algorithm with function approximation which has provably sublinear no-regret learning guarantees.  The algorithm, coined DORIS, uses a technical combination of Hedge (for adapting over the adversarial nature of the problem) alongside a novel value function estimation step within the multi-agent environment.  The authors show sublinear regret guarantees with respect to a new complexity measure, the Bellman Evaluation Eluder dimension, which generalizes to multi-agent problems.  The complement these results with special guarantees for the constrained MDP and vector-valued MDP setup (although these results are not discussed in the main paper).

More concretely the authors consider an n-agent MDP $(S, A_i, r_i, P, H)$ where $S$ is the state space, $A_i$ the actions for player $i$, $r_i$ the individual reward function, $P$ the global transition distribution, and $H$ is the horizon.  Policies are decentralized (i.e. agent $i$ observes state and picks only action in $A_i$.  The authors consider the decentralized setting which means that the player only controls (let's say the first action sets $A_1$) and the rest are chosen by potential adversary.  However, the authors consider the policy revealing setting, meaning that at the end of an episode the algorithm observes the policies that were played by the other agents (i.e. distribution over actions instead of just the observed action selected).  The goal is to achieve sublinear regret guarantees, where regret is measured as:

$R(K) - \max_{\pi} \sum_k V_1^{\pi} - V_1^{\pi^k}$

where I have omitted the dependence on the policy for the other agents.  Note that this is fundamentally different from prior settings which just hope to converge to a Nash policy, this is instead attempting to compete against the best fixed policy in hindsight.

The algorithm works as follows.  First we maintain a distribution $p_t$ over the space of all possible policies $\Pi$ which is updated with exponential weights via Hedge.  The estimates or "losses" which are used in the Hedge updates are collected via an optimistic policy estimation technique, which is novel to this work over prior literature, which uses advances in optimistic policy estimation over general function classes.

The authors complement the algorithm formulation with several regret bounds under different adversarial assumptions on the problem.

## Questions
- Can you comment on the assumption that the function class for other agents is required for the algorithm? It seems a bit strange - especially since the reward functions could be modelled with different features for different agents?
- Can you comment more on the computational feasibility of the algorithm? Or are some of these issues avoided with the assumption of finite policy class?

## Minor Comments
- The hardness results in [33] are cited frequently with no formal description.  It is relatively easy to understand form context, but it would be helpful to describe that result more thoroughly
- Space before citation [44] in introduction
- On page 2 the discussion before the bolded question makes it seem as though your paper does not consider policy revealing - but that is exactly the model which is studied
- On page 8 before Adaptive Opponent maybe add some signaling for $\Pi$ being policy for controlled agent and $\Pi'$ being other agents - found the assumptions a bit hard to keep track of

EDIT: Thanks to the authors for addressing all of my comments. I have no further concerns, but still suggest that the hardness results be expanded in the revisions.
strength_and_weaknesses: ## Strengths
1. The authors study a novel model for learning in Markov Games - providing the first study of no-regret learning (i.e. benchmarking against best fixed policy in hindsight) with general function approximation.
2. The theoretical contributions include developing a novel problem complexity measure similar to the Eluder dimension extended to the multi-player setting


## Weaknesses
1. The authors include no discussion on the computational complexity of the algorithm.
2. There are no theoretical matching lower bounds (or discussion along this point)
3. The authors provide no empirical results of their algorithm's performance
4. The theoretical contributions and algorithm design seems like a straightforward extension of the algorithm presented in [33] with prior mechanisms for estimating the value function with general function approximation techniques.

clarity,_quality,_novelty_and_reproducibility: ## Clarity

The paper is extremely well written and easy to follow.  I listed some small comments on writing earlier up in the review.  The two most useful clarifications which should be included in the revision would be:
1. Comment on computational tractability of the algorithm
2. Discuss the lower bound listed in [33]
3. Move some of discussion in Appendix on the relationship between [33] and this paper to the main paper

## Quality + Novelty

The paper provides novel theoretical contributions for developing an algorithm for no-regret learning in decentralized Markov Games.  This allows the algorithm to only manage a single player, than a centralized algorithm that is normally studied in the prior literature.  The theoretical results are strong (although no matching lower bounds are included), but seem to be correct based on lower bounds established in the simpler single agent settings.
summary_of_the_review: The paper provides strong theoretical contributions for understanding no-regret learning in decentralized Markov Games.  The paper is extremely well written, highlighting the main differences and contributions between the paper and the related work.  However, the paper offers no empirical results (or discussion on computational tractability of their algorithm).
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper studies decentralized policy learning in Markov games with function approximations under the "policy revealing" setting. An algorithm with regret bounds is provided for both oblivious and non-oblivious opponents. The paper is well written and the analysis is sound, with a new complexity measure being introduced. The weaknesses of the paper include the assumption that the policy of the other agents is revealed, the extension from the tabular case to the function approximation case is not very novel (but definitely sufficiently novel for publication), and the algorithm is not computationally efficient (although it is for the linear case).
justification_for_why_not_higher_score: The weaknesses listed above, as well as the strength of the support from the reviewers (weak accept on average), suggest that a poster presentation is the most appropriate for the paper, although depending on the quality of other papers, a spotlight presentation may also be considered.
justification_for_why_not_lower_score: The paper presents novel results which are worthy of publication.
Decision: Accept: poster