- Rating
- 3(+1)
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
In this work, the authors study the computational limitations of sample-based algorithms for multi-agent reinforcement learning (MARL). Under assumptions similar to those commonly adopted in the existing literature, the paper proposes an algorithm that achieves an improved complexity–accuracy tradeoff by relaxing the approximation error bound by a quadratic factor. The resulting approach reduces the computational complexity required to obtain an approximately optimal solution while maintaining theoretical performance guarantees.
Critical strengths
-Quadratic improvement on an factor is provided for the required sample complexity. -The paper seems to have an extensive bibliography on the topic.
Critical weaknesses
- By scaling the reward/cost function, one can define an equivalent problem in which the desired error rate can be chosen as arbitrarily, as long as the error rate is available over an interval of the form [0, a] for some “a”. In particular, the result of Shi et al. (2024a) can be extended to [0, H] by shrinking the objective function, then applying the available result on the full interval, and then removing the scaling. Thus, the improvement on the burn in cost does not seem to be a significant improvement at all.
- The present sample complexity is close to the optimal one, as argued in this work. However, the arguments employed to achieve this improved rate seem rather standard.
Questions for authors
-I am certain that the result of Shi et al. (2024) can be expanded to the whole interval presented in this work using the technique that I mentioned above. Is there any inherent advantage of having error rate available on the whole interval [0, H]? -What are the main technical advancements made in the current manuscript compared to previous work?
3 comments
I thank the authors for their detailed responses. Some further comments:
An argument for an improved burn-in region: The authors have to apply the result to the reward function r′ = ρr when ε is greater than the given threshold but ρε is within the feasible threshold. Then, just use the fact that the desired gap obtained under r′ is just that of r but obtained under the factor ρ.
A sketch of the argument would be as follows. If r is the reward function, let ρ be a positive number and let r′ := ρr. Then, by Gap(r), denote the gap between the learned policy and the equilibrium. We have Gap(r′) = ρGap(r). For ε′ = ρε, when ε′ ≤√(min(H, 1/R) and ε >√︁(min(H, 1/R), from Shi et al., we obtain N = Õ (H6S (Σ︂i Ai) min(H, 1/R)/(ε′)4) for ρ Gap(r) by applying the result to Gap(r′). Such a ρ always exists. In fact, since we can take ρ ≤ 1, we have ρ∗(ε) = min (︃1, (1/ε)√min(H,1/R))︃ as the optimal factor ρ. For all 0 < ε < H, we then should obtain Õ (H6S (Σ︂i Ai) min(H, 1/R)/ min(ε,√︁min(H, 1/R))4).
However, it seems that when we have low uncertainty and a small horizon length, this approach leads to a worse asymptotic bound than the original result of Shi et. al. in the extended range. Since this trick gives relatively worse results in certain regimes, I am convinced that the authors had a non-trivial addendum (in that case, we have a factor of H7 inside Õ).
Updated assessment: Hoping that the authors will further update the paper in view of the above comments, and given the responses they have provided to the other earlier comments, I have updated my score to “weak accept”.
Thank you for your follow-up and for raising your score. We have revised the manuscript to clarify that the resulting sample complexity bound obtained by rescaling has a worse dependency in the extended range.
We sincerely thank the reviewer for the careful reading. Our point-by-point response is as follows.
Reward scaling does not work. Reward scaling cannot extend the stated sample complexity guarantee to the full accuracy range. The key observation is that both the admissible accuracy range and the full value range change proportionally in different reward scales, leaving their ratio unchanged (see detailed explanation below). If we have misunderstood the proposed argument, could you please clarify how scaling and rescaling work?
Specifically, for rewards in [0,1], Shi et al. (2024a) establish the following sample complexity bound, up to log factors: ε4H6S∑iAiminH,R1,0<ε≤minH,R1. Scaling rewards by ρ>0 changes the full value range from [0,H] to [0,ρH] and expresses the same guarantee as
\qquad 0<\varepsilon'\le\rho \sqrt{\min\\{H,\frac{1}{R}\\}}.$$ To obtain accuracy $\varepsilon$ in the original problem, the scaled problem must be solved to accuracy $\varepsilon'=\rho\varepsilon$. Removing the scaling therefore gives $$\frac{\rho^4H^6S\sum_iA_i}{(\rho\varepsilon)^4}\min\\{H,\frac{1}{R}\\} = \frac{H^6S\sum_iA_i}{\varepsilon^4}\min\\{H,\frac{1}{R}\\}, \qquad 0<\varepsilon\le\frac{1}{\rho} \rho \sqrt{\min\\{H,\frac{1}{R}\\}}=\sqrt{\min\\{H,\frac{1}{R}\\}}.$$ This recovers the original guarantee. The admissible accuracy range covers the same fraction $\rho \sqrt{\min\\{H,1/R\\}}/(\rho H)=\sqrt{\min\\{H,1/R\\}}/H$ of the full value range. Prior literature also shows that full-range sample optimality is nontrivial. [R1-R3] establish it in generative model, online, and offline single-agent RL, respectively, improving [R5-R7], whose sample optimality holds only over restricted accuracy ranges. See Table 1 and Section 3.3 of [R1], Table 1 and Section 1.1 of [R2], and Table 1 and the discussion titled ``Full $\varepsilon$-range and no burn-in cost'' following Theorem 4 in [R3]. Similarly, [R4] highlights full-range minimax optimality in finite-horizon MARL, whereas [R8] requires a restrictive accuracy range in discounted games. Despite the different horizon formulations, they further demonstrate that full-range guarantees are a recognized consideration in MARL theory. We have discussed this in Section 3.2 (line 417-423) and Appendix (line 1130-1145). **Advantages of full range optimal.** Achieving minimax sample complexity throughout $\varepsilon\in(0,H]$ provides optimal error guarantees across sample sizes, without an additional burn-in requirement. As discussed in our response to your previous comment, eliminating such requirements has received considerable attention. In addition, beyond removing burn-in cost, our main contribution is to establish minimax sample complexity for robust MARL under the R-contamination model. **Technical advancements.** Thank you for your question. It is challenging to establish minimax sample complexity for robust MARL. We clarify the key technical differences through comparisons with Shi et al. (2024a,c), the most closely related works. Shi et al. (2024a) use $N=\Omega(H^2\min\\{H,1/R\\}\varepsilon^{-2})$ samples per state--individual-action pair in each iteration, whereas we use only one. Our analysis must therefore control the weighted cumulative estimation error without accurate transition estimates at each iteration. We also reduce the number of iterations $K$ in each stage $h$ by a factor of $H/\min\\{H,1/R\\}$, which requires refined control of the span and variance of $\widehat{V}_{i,h}$. This is nontrivial because the bounds for $\widehat{V}_{i,h}$, $\beta_{i,h}$ and $q_{i,h,s}^k$ must be established jointly. Shi et al. (2024c) estimate $Q$-functions over the joint action space. Our approach instead uses estimates indexed by individual actions and avoids explicitly solving for equilibria at each stage. This yields a dependence on $\sum_i A_i$ rather than $\prod_i A_i$. We have highlighted these technical steps and their differences from prior analyses in Section 3.2 (line 425-431). [R1] Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model. NeurIPS 2020 [R2] Settling the Sample Complexity of Online Reinforcement Learning. COLT 2024 [R3] Settling the Sample Complexity of Model-Based Offline Reinforcement Learning. AoS 2024 [R4] Minimax-Optimal Multi-Agent RL in Markov Games With a Generative Model. NeurIPS 2022 [R5] Model-Based Reinforcement Learning with a Generative Model is Minimax Optimal. COLT 2020 [R6] UCB momentum Q-learning: Correcting the bias without forgetting. ICML 2021 [R7] Pessimistic Q-learning for offline reinforcement learning: Towards optimal sample complexity. ICML 2022 [R8] Model-based reinforcement learning with a generative model is minimax optimal. COLT 2020