Sample-Efficient Multi-Agent RL: An Optimization Perspective

Thanks for your response. We will address your questions below.

1. I think that the paper should make it clearer that MAMEX is not computationally efficient. This is because of (i) the equilibrium computation over the set of pure policies in step 4 of Algorithm 1 is often over combinatorial sets like for example the set of deterministic policies in the tabular setting and (ii) the sup over the function class in the policy evaluation routine. In the tabular case or in the Linear MDP case would there exist an efficient way to implement MAMEX?

(i). The equilibrium computation over the set of pure policies.

The policy evaluation step refers to Lines 3 and 4 in MAMEX (Algorithm 1). If we regard these two lines as an oracle, MAMEX is oracle-efficient. The computational complexity of this oracle depends on the type of equilibrium. For CCE, the oracle can be approximately implemented by mirror descent [1], where the time of calculating $V(\pi)$ depends on $L$ and $L$ is the number of iterations. Hence, the computational complexity of this oracle depends only on the number of iterations rather than the joint pure policy space $|\Pi|$, and MAMEX can be calculated efficiently. However, for Nash Equilibrium, calculating the equilibrium is PPAD-complete. So MAMEX is computationally inefficient for learning NE.

(ii). The sup over the function class in the policy evaluation routine

We believe that it can be solved by using similar techniques in [2], where they alternately update the policy and the hypothesis function (the model parameter in the model-based version or the Q-function in the model-free setting). Particularly, we apply gradient ascent when updating the hypothesis function. In MAMEX, if we use policy iteration or soft policy iteration to solve a CCE, their alternate updates are also available here.

2. Do you think that the MADC are necessary quantity that should appear in lower bounds too?

We think the MADC is a necessary quantity that should appear in lower bounds. However, even for the single-agent DC ([3]), the lower bound is still lacking. We leave it as a future work.

references:

[1]. Wang et al. Breaking the curse of multiagency: Provably efficient decentralized multi-agent rl with function approximation. preprint 2023.

[2]. Liu et al. Maximize to Explore: One Objective Function Fusing Estimation, Planning, and Exploration, NeurIPS 2023.

[3]. Dann et al. A provably efficient model-free posterior sampling method for episodic reinforcement learning. NeurIPS 2021.

Thanks for your response. We will address your questions below.

1. When $n=1$, the problems are reduced to a single agent RL. In this case, is MADC reduced to DC, or is it more general than DC? (since it is not restricted to greedy policy)

It is more general than DC since the policy $\pi^k$ in (2.3) is not restricted to the greedy policy. In other words, the MADC in $n=1$ is not less than DC. A function class of MDP with small DC can also have large MADC for $n=1$.

2. If MADC reduces to DC when $n=1$, does an RL instance with finite DC imply the MG version of the RL instance also has finite MADC (and thus can be solved efficiently?)

There is no nontrivial example in which MADC is infinite since MADC in tabular MG is also finite ($O(|S||A|)$) when states and actions are finite. However, an RL instance with a small DC cannot imply the MG version of the RL instance also has a small MADC, since the policy $\pi^k$ is not restricted to the greedy policy. Hence, it needs to further check whether the multi-agent version of the RL instance satisfies the Equation (2.3) for every policy sequences $\{\pi^k\}_{k \in [K]}$.

3. How should one compare MADC and MADMSO?

In general, we do not see a clear relation between MADC and MADMSO, in the sense that our complexity measures cannot be reduced to theirs and vice versa. However, when applying to some specific examples, the inducing results are comparable. For example, when applying to the linear MG with dimension $d$, the paper [3] achieves a $\widetilde{O}(n^2d^2H^4\max_{i=1}^n \log |\Pi_i|/\varepsilon^2)$ sample complexity, while our paper can achieve a $\widetilde{O}(d^2H^2 + n^2H^2(\max_{i=1}^n\log |\Pi_i|)^2/\varepsilon^2)$ sample complexity. Compared to [3], our result has a higher degree in term $\max_{i=1}^n \log|\Pi_i|$. When $\max_{i=1}^n \log |\Pi_i|$ is relatively small and can be ignored, our $\widetilde{O}((n^2+d^2)H^2/\varepsilon^2)$ sample complexity is smaller than the sample complexity result $\widetilde{O}(n^2d^2H^2/\varepsilon^2)$ in [3]. In addition, our complexity measure also captures model-free settings, while the algorithm and the complexity measure MA-DEC in [3] heavily depend on the model and cannot be directly applied to the model-free setting.

4. It seems that the current framework does not distinguish NE/CCE/CE. It seems that as long as the NE/CCE/CE equilibrium oracle is efficient, it takes the same amount of samples to find NE/CCE/CE? As NE is a much stricter notion of equilibrium than CCE, for example, on might expect more samples to be needed (or in other words, harder) to learn NE. So are the results tight for each of NE/CCE/CE or is it an upper bound for the worst-case regret needed for finding any equilibrium?

The results is not tight for each of NE/CCE/CE. For example, one can use the decentralized function approximation to learn CCE with polynomial sample complexity for tabular general-sum MG ([1]), while any general framework that learns NE/CCE/CE ([2,3,4,5] and our paper) suffers an exponential term $\prod_{i=1}^n |A_i|$ for the tabular general-sum MG due to the intrinsic difficulty of learning NE.

Instead of getting the optimal result in one particular equilibrium, our goal is to provide an unified algorithmic framework that learns NE/CCE/CE for both model-based and model-free RL under the general function approximation.

References:

[1]. Wang et al. Breaking the curse of multiagency: Provably efficient decentralized multi-agent rl with function approximation. preprint 2023.

[2]. Chen et al. Unified algorithms for rl with decision-estimation coefficients: No-regret, pac, and reward-free learning. preprint 2022.

[3]. Foster et al. On the complexity of multi-agent decision making: From learning in games to partial monitoring. COLT 2023.

[4]. Liu et al. Sample-efficient reinforcement learning of partially observable markov games. NeurIPS 2022.

[5]. Jin et al. V-Learning--A Simple, Efficient, Decentralized Algorithm for Multiagent RL. ICLR Workshop 2022.

[6]. Liu et al. Maximize to Explore: One Objective Function Fusing Estimation, Planning, and Exploration, NeurIPS 2023.

6. Why bother with the function approximation of a value function? Why not just deploy the equilibrium policy and be done rather than continue to iterate to learn the best approximation to the value function? In other words, if I have an oracle to solve an NFG of the size you suggest, I can just ask it to return the equilibrium policy assuming the entries in the payoff tensor are the actual Monte-Carlo returns of the pure policies in the Markov game.

Note that the reward functions and transition kernels of the MG are unknown. If we estimate the payoff tensor using Monte-Carlo returns, we need to learn that for all joint policies. In other words, we have to enumerate every joint policy in $\Pi$ and collect Monte Carlo samples. To construct accurate estimators, the sample complexity is proportional to $|\Pi|$, which is usually exponential in non-parameterized case $(O(|A|^{|S|}))$ , making the algorithm sample-inefficient.

In contrast, our algorithm uses function approximation on the value function to derive $V_{f}^\pi$ without estimating the function for all policies, thus leading to a sample complexity that only has the term $O(\log(|\Pi|))$. Such a difference also shows why exploration is necessary. By estimating the value functions smartly, balancing exploration and exploitation, we ensure that the size of $|\Pi|$ only through $\log|\Pi|$.

To avoid estimating the payoff function for all joint pure policy, RSRO try to recursively add the policies into the policy space, and compute the payoff function of the new policy in each iteration. However, they do not provide a theoretical guarantee of the iteration rounds, the final sample complexity and the accuracy of the output.

7. Is there some setting you have in mind where it is cheaper to approximate a value function and avoid calculating returns for every joint pure policy?

MAMEX approximates the value function, calculates the payoff function and derives the equilibrium at Lines 3 and 4. If we regard Lines 3 and 4 in MAMEX as an oracle, MAMEX is oracle efficient. For CCE, the oracle can be approximately implemented by mirror descent [1], where the time of calculating $V(\pi)$ depends on $L$ and $L$ is the number of iterations. Hence, the computational complexity of this oracle depends only on the number of iterations rather than the joint pure policy space $|\Pi|$, and MAMEX can be calculated efficiently.

References:

[1]. Wang et al. Breaking the curse of multiagency: Provably efficient decentralized multi-agent rl with function approximation. preprint 2023.

Thanks for your response. We will address your questions below.

1. Comparison between MAMEX and PSRO

The PSRO learns the equilibrium in the following way: At first, every player chooses a uniform policy as their strategy. The algorithm then calculates the equilibrium by a meta-solver, and trains an oracle that outputs the best response $\pi_i$ of the equilibrium for player $i$. After that, the algorithm adds $\pi_i$ into the strategy space of the player $i$. Last, the algorithm simulates all the new joint policy and construct a new normal-form game for the next iteration. The algorithm can finally converge to an equilibrium. However, in each iteration, it should simulate all the new joint policies and estimate the return. Consequently, the sample complexity increases exponentially as the iteration rounds increase.

Different from PSRO, MAMEX utilizes the function approximation technique to the value function. The precise characterization of the structure of the value function can help us to evaluate the policy without actually simulating the environment with more samples. To be more specific, at each round, instead of simulating the environment and getting a Monte-Carlo return of each joint policy, MAMEX only needs to solve a regularized optimization problem over the function space of the value function. The solution of the optimization problem is used to be a payoff for the normal-form game. Since solving this optimization subproblem does not need additional samples, MAMEX bypasses the requirement for exponential samples to simulate the environment and estimate the value for each joint policy $\pi$. This characteristic enhances its sample efficiency in comparison to PSRO.

2. Pure Policy set:

The pure policy $\Pi_i$ for each player $i$ is a concrete policy set, so an agent can follow any mixture of the pure policy $\Delta(\Pi_i)$. The equilibrium is defined over the mixture of these pure policies. That is, each pure policy can be viewed as a pure strategy of the normal form game, and each joint policy can be viewed as a mixed strategy.

For example, if the pure policy set is the deterministic policy set, the agent can execute any mixture of the deterministic policy. The equilibrium is then defined on the mixture of the deterministic policy, which reduces to the standard equilibrium defined in a normal-form game.

If the pure policy set for each player only consists of the log linear policy $\Pi_i = \\{\pi_\theta: \pi_\theta(\cdot \mid s) = \text{Softmax}(\theta^T\phi(s,\cdot)), \theta \in \mathbb{R}^d, \|\theta\|_2 \le 1\\}$, then one agent can only execute the mixture of the log linear policy. Now the equilibrium is defined in a $|\Pi_1| \times |\Pi_2| \times \cdot \times |\Pi_n|$ multi-player normal-form game, where each log linear policy in $\Pi_i$ is a strategy for player $i$, and each joint log linear policy has a payoff.

3. Can you state somewhere that $\eta > 0$ is a hyperparameter that you are introducing?

In Theorem 3.1, we choose $\eta = 4/\sqrt{K}$.

4. Can you please bring Algorithm 1 into the main body?

Thanks for your reminder. We will put Algorithm 1 in the main body in our revised version.

5. You say "We prove that MAMEX achieves a sublinear regret for learning NE/CCE/CE in classes with small MADCs", but haven't you proven sublinear regret regardless of how large the MADC is (as long as it is finite, Assumption 2.7)? Do you have an interesting example in which MADC is infinite?

Thanks for your reminder. It is better to say "We prove that MAMEX achieves a sublinear regret for learning NE/CCE/CE, and the regret is smaller when the MADC of the function class is smaller." In other words, the bound becomes vacuous when MADC is infinity.

There is no nontrivial example in which MADC is infinite since MADC in tabular MG is also finite ($O(|S||A|)$). Of course, an MG with infinite states and no structure has infinite MADC.

References:

[1]. Wang et al. Breaking the curse of multiagency: Provably efficient decentralized multi-agent rl with function approximation. preprint 2023.

[2]. Chen et al. Unified algorithms for rl with decision-estimation coefficients: No-regret, pac, and reward-free learning. preprint 2022.

[3]. Foster et al. On the complexity of multi-agent decision making: From learning in games to partial monitoring. COLT 2023.

[4]. Jiang et al. Offline congestion games: How feedback type affects data coverage requirement, ICLR 2023.

[5]. Sliver et al. Mastering the game of Go with deep neural networks and tree search. Nature 2016.

[6]. Liu et al. Sample-efficient reinforcement learning of partially observable markov games. NeurIPS 2022.

[7]. Jin et al. V-Learning--A Simple, Efficient, Decentralized Algorithm for Multiagent RL. ICLR Workshop 2022.

[8]. Liu et al. When Is Partially Observable Reinforcement Learning Not Scary? COLT 2022.

Thanks for your response. We will address your questions below.

1. Motivation to study equilibrium learning in a centralized manner

Centralized or decentralized learning is a separate question from whether the game is cooperative or competitive. For example, in a noncooperative game, each agent might first run a centralized RL algorithm on a game environment to learn the equilibrium policy $\hat \pi$, and then deploy her component $\hat \pi^{(i)}$. Here this environment takes the joint policy as the input and outputs the trajectory. Therefore, it is crucial to investigate the equilibrium for a multi-agent RL problem, which has been also studied in recent years ([1,2,3,4,6,7]).

To be more specific, there are three motivations for learning the equilibrium in a centralized manner:

• AlphaZero ([5]): It learns a Nash equilibrium in a two-player zero-sum Markov Game to learn how to compete with the opponent. The centralized RL algorithm is deployed to the two-player zero-sum Markov game and a policy $\pi^{(1)}$ and $\pi^{(2)}$ are learned. After the algorithm converges, the policy $\pi^{(1)}$ is deployed to play against human.

• Financial Market: When $n$ market participants choose the best strategies based on the equilibrium, the market may reach a relatively stable state. So they have enough motivation to learn an equilibrium $(\pi^{(1)},\cdots,\pi^{(n)})$ by following a centralized algorithm, and the $i$-th market participants take the policy $\pi^{(i)}$.

Furthermore, if the goal of the agents is to achieve social welfare, our algorithm can be modified to learn the policy with optimal social welfare. In particular, we only need to change the equilibrium-solving oracle to an oracle that maximizes the social welfare

2. comparisons in the "sample complexity" side and relations between several complexity measures

• Compared to the previous works that study the general function approximation of the general-sum MGs ([1,2,3]).

[2] and [3] both study the model-based RL problem with centralized function approximation. Since [2] only studies the PAC learning setting with sample complexity results instead of the regret result, to compare with them, we use our sample complexity result in Corollary D.4 to give a comparison. To learn a $\varepsilon$-NE/CCE/CE, both our results and their results have the form $O(\text{poly}(d_{\text{parameter}},\log |\Pi|, \log |M|)/\varepsilon^2)$, where $M$ is the model and $d_{\text{parameter}}$ is the complexity measure (MADC in our paper, MADEC in [2,3]). When applying to the tabular MG, both our work and their works suffer an exponential term $\prod_{i=1}^n A_i$, due to the centralized function approximation. When applying to the linear MG with dimension $d$, the paper [2] achieves a $\widetilde{O}(dH^2\log |M|/\varepsilon^2)$ sample complexity, the paper [3] achieves a $\widetilde{O}(n^2d^2H^4\max_{i=1}^n \log |\Pi_i|/\varepsilon^2)$ sample complexity, while our paper can achieve a $\widetilde{O}(d^2H^2 + n^2H^2(\max_{i=1}^n\log |\Pi_i|)^2/\varepsilon^2)$ sample complexity. Compared to [2], the term $\log|M| \ge\Omega( A)$ (using an appropriate discretization ([8])) usually suffers the curse of multi-agency, while our result avoids this term and does not suffer the curse of multi-agency. Compared to [3], our result has a higher degree in term $\max_{i=1}^n \log|\Pi_i|$. When $\max_{i=1}^n \log |\Pi_i|$ is small and can be ignored, our $\widetilde{O}((n^2+d^2)H^2/\varepsilon^2)$ sample complexity is smaller than the result $\widetilde{O}(n^2d^2H^2/\varepsilon^2)$ in [3].

When applying to the linear mixture MG, the work [2] derives a $\widetilde{O}(d^2H^3/\varepsilon^2)$ sample complexity, our paper achieves a smaller $\widetilde{O}((n^2+d^2)H^2/\varepsilon^2)$ sample complexity, and [3] does not derive an accurate result.

Moreover, both [2] and [3] cannot be easily extended to the model-free settings since (a) their algorithms involve an optimization subproblem (Line 4 of Algorithm 9 in [2], Line 5 of Algorithm 1 in [3]) or a sampling procedure (Line 6 of Algorithm 9 in [2]) over the model space, and (b) their essential complexity measures (MDEC in [2], MA-DEC in [3]) heavily depends on the model. In contrast, our complexity measure MADC is flexible to be applied to both model-free RL and model-based RL.

The recent work [1] uses a decentralized function approximation, so they provide a polynomial sample complexity result for learning CCE for the tabular general-sum MG. However, they do not provide a regret result, and the function approximation results are not directly comparable due to the different decentralized function approximation.

• Relations

We do not see a clear relation in general, in the sense that our complexity measures cannot be reduced to theirs and vice versa. However, when applying to some specific examples, the regret of our work and previous works is comparable. In addition, our complexity measure also captures model-free settings.

4. How do the authors compare the regret results with previous SotA algorithms?

• Compared to the previous papers that study the general function approximation of the general-sum MGs ([1,2,3]).

Two papers [2] and [3] both study the model-based RL problem with centralized function approximation. Since [2] only studies the PAC learning setting with sample complexity results instead of the regret result, to compare with them, we use our sample complexity result in Corollary D.4 to give a comparison. To learn a $\varepsilon$-NE/CCE/CE, both our results and their results have the form $O(\text{poly}(d_{\text{parameter}},\log |\Pi|, \log |M|)/\varepsilon^2)$, where $M$ is the model and $d_{\text{parameter}}$ is the complexity measure (MADC in our paper, MADEC in [2,3]). When applying to the tabular MG, both our work and their works suffer an exponential term $\prod_{i=1}^n A_i$, due to the centralized function approximation. When applying to the linear MG with dimension $d$, the paper [2] achieves a $\widetilde{O}(dH^2\log |M|/\varepsilon^2)$ sample complexity, the paper [3] achieves a $\widetilde{O}(n^2d^2H^4\max_{i=1}^n \log |\Pi_i|/\varepsilon^2)$ sample complexity, while our paper can achieve a $\widetilde{O}(d^2H^2 + n^2H^2(\max_{i=1}^n\log |\Pi_i|)^2/\varepsilon^2)$ sample complexity. Compared to [2], the term $\log|M| \ge\Omega( A)$ (using an appropriate discretization ([8])) usually suffers the curse of multi-agency, while our result avoids this term and does not suffer the curse of multi-agency. Compared to [3], our result has a higher degree in term $\max_{i=1}^n \log|\Pi_i|$. When $\max_{i=1}^n \log |\Pi_i|$ is relatively small and can be ignored, our $\widetilde{O}((n^2+d^2)H^2/\varepsilon^2)$ sample complexity is smaller than the result $\widetilde{O}(n^2d^2H^2/\varepsilon^2)$ in [3].

When applying to the linear mixture MG, the work [2] derives a $\widetilde{O}(d^2H^3/\varepsilon^2)$ sample complexity, our paper achieves a smaller $\widetilde{O}((n^2+d^2)H^2/\varepsilon^2)$ sample complexity, and [3] does not derive an accurate result.

Moreover, both [2] and [3] cannot be easily extended to the model-free settings since (a) their algorithms involve an optimization subproblem (Line 4 of Algorithm 9 in [2], Line 5 of Algorithm 1 in [3]) or a sampling procedure (Line 6 of Algorithm 9 in [2]) over the model space, and (b) their essential complexity measures (MDEC in [2], MA-DEC in [3]) heavily depends on the model. In contrast, our complexity measure MADC is flexible to be applied to both model-free RL and model-based RL.

• Compared to the previous SoTA algorithm for specific examples.

For zero-sum linear MG, the previous work [4] provides a $\widetilde{O}(d^{3/2}H^2\sqrt{K})$ regret when $\sum_{h=1}^H r_h \in [0,H]$, while MAMEX achieves a $\widetilde{O}(dH^3\sqrt{K}+H^3\sqrt{K}\log |\Pi|)$ regret. When the pure policy class for each player is the log linear policy class with dimension $d_\pi$, MAMEX yields a $\widetilde{O}((d+nd_\pi)H^3\sqrt{K})$ regret.

For zero-sum linear mixture MG, the previous work [5] provides a minimax-optimal $\widetilde{O}(dH\sqrt{K})$ regret, while MAMEX yields a $\widetilde{O}(dH^5\sqrt{K})$ regret. Thus our regret matches their results in terms of $d$ and $K$, with an additional factor $H^4$.

5. typos and appendix

Thanks for your reminder. We will fix them in our next version. If we have additional space, we will move the definition of $\ell$ and the algorithm code into the main body.

References:

[1]. Wang et al. Breaking the curse of multiagency: Provably efficient decentralized multi-agent rl with function approximation. preprint 2023.

[2]. Chen et al. Unified algorithms for rl with decision-estimation coefficients: No-regret, pac, and reward-free learning. preprint 2022.

[3]. Foster et al. On the complexity of multi-agent decision making: From learning in games to partial monitoring. COLT 2023.

[4]. Xie et al. Learning zero-sum simultaneousmove markov games using function approximation and correlated equilibrium. COLT 2020.

[5]. Chen et al. Almost optimal algorithms for two-player zerosum linear mixture markov games. ICALT 2022.

Thanks for your response. We will address your questions below.

1. The main weakness of the paper is how to perform the policy evaluation step. It seems to me that it will be computationally expensive to construct an estimator for each pure strategy for each player. Can the authors explain this more in detail?

The policy evaluation step refers to Lines 3 and 4 in MAMEX (Algorithm 1). If we regard these two lines as an oracle, MAMEX is oracle-efficient. The computational complexity of this oracle depends on the type of equilibrium. For CCE, the oracle can be approximately implemented by mirror descent [1], where the time of calculating $V(\pi)$ depends on $L$ and $L$ is the number of iterations. Hence, the computational complexity of this oracle depends only on the number of iterations rather than the joint pure policy space $|\Pi|$, and MAMEX can be calculated efficiently. For Nash Equilibrium, calculating the equilibrium is PPAD-complete. So MAMEX is computationally inefficient for learning NE.

2. How big is the policy space of the pure strategy?

It depends on the selection of the pure strategy. If we consider all deterministic policies, the cardinality of the policy space of player $i$ is $|\Pi_i| = |A_i|^{|S|}$. Moreover, if we use the parameterized policy class, the size of the policy space can be smaller. For example, if we consider a $1/K$-cover of the log linear policies, the policy space is $K^d$, where $d$ is the dimension of the log linear policy class.

3. If we are replacing the set with a 1/K-cover how much are we losing?

We take the Nash equilibrium in the example below. If we consider a $1/K$-cover $\widetilde{\Pi}\_i$ for the policy space $\Pi_i$, then for any $\pi' \in \widetilde{\Pi}\_i$, there exists a policy $\pi \in \Pi_i$ such that $||\pi(\cdot \mid s) - \pi'(\cdot \mid s)||\_1\le 1/K$. Then for an policy $\Gamma$ in $\otimes_{i=1}^n \widetilde{\Pi}\_i$, then for each player, $i$, the regret
$\max_{\pi_i \in \Delta(\Pi_i)}V_{1,i}^{\pi_i\times \Gamma_{-i}}(\rho) - V_{1,i}^{\Gamma}(\rho) \le V_{1,i}^{\widetilde{\pi}\_i\times \Gamma_{-i}}(\rho) - V_{1,i}^{\Gamma}(\rho) + O(1/K)\le \max_{\pi' \in \Delta(\widetilde{\Pi}\_i)}V_{1,i}^{\pi_i'\times \Gamma_{-i}}(\rho) - V_{1,i}^{\Gamma}(\rho).$ The inequality holds by denoting $\pi_i^* = \arg\max_{\pi \in \Delta(\pi_i)}V_{1,i}^{\pi_i'\times \Gamma_{-i}}(\rho)$, then there exists a $\widetilde{\pi}\_i \in \widetilde{\Pi}\_i$ such that $V_{1,i}^{\pi_i^* \times \Gamma_{-i}}(\rho) \le V_{1,i}^{\widetilde{\pi}\_i\times \Gamma_{-i}}(\rho) + O(1/K).$ Thus the difference between the regret defined on the original policy space and the regret defined on the $1/K$-cover is $O(1/K)*nK = O(n)$, which can be dominated by other terms.