- Rating
- 3(+1)
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The paper studies fitted Q-iteration for discounted two-player zero-sum Markov games with continuous states and actions. It constructs a Q-network from two partially input convex networks and a state dependent bilinear interaction, making each learned action value function convex-concave and its Bellman backup amenable to saddle point optimization. Under mild assumptions, Theorem 1 bounds Q-function error and Corollary 1 converts this into a Nash gap bounds. A pursuit-evasion experiment reports stable training performance of the proposed architecture.
Critical strengths
-
The paper proposes a convex–concave neural -function approximator combining PICNNs with a bilinear interaction and establishes finite-sample -approximation and Nash-gap bounds.
-
The pursuit-evasion experiment demonstrates stable training behavior of the proposed function approximator.
Critical weaknesses
-
The PICNN architecture and bilinear structure used in the proposed function approximator are not individually novel. The architecture itself is also restrictive, since the cross-player action interactions are bilinear.
-
The practical advantage of the proposed approximator is insufficiently established. The theory does not characterize when its approximation error is small, and neither theoretical nor empirical comparisons with alternative approximators are provided. Consequently, the implications of its expressiveness restrictions remain unclear..
-
The empirical evaluation is limited. It only covers one synthetic pursuit–evasion setting and reports only the normalized mean absolute TD error.
Questions for authors
-
How does the proposed function approximator compare with other function approximation architectures? Could the authors provide theoretical or empirical evidence clarifying its advantages and limitations?
-
Could the authors evaluate the performance of the learned policies to demonstrate the proposed approximator’s practical effectiveness? Additional experiments in larger, more realistic environments would also be helpful.
-
The authors claim to provide the first finite-sample analysis for neural network function approximation in zero-sum Markov games with continuous state–action spaces beyond the LQ setting. Could the authors clarify how their analysis compares with Qiu et al. (2021), On Reward-Free RL with Kernel and Neural Function Approximations: Single-Agent MDP and Markov Game, which also provides finite-sample guarantees for neural function approximation in zero-sum Markov games? Qiu et al.’s formulation also places the joint state–action input in .
2 comments
Replying to Question 3, on comparison with Qiu et al.
Question 3
Thank you for pointing us to this previous work. Qiu et al. do not clarify whether their method applies to continuous state-action spaces, and our reading is that it would not without strong assumptions, namely without assuming the ability to compute exact min-max equilibria of over the action sets. On the other hand, our convex-concave function approximation covers this gap. Their planning phase computes Nash equilibria of matrix games over the action sets, (Algorithm 4, lines 7-8, and Section 4.1 of Qiu et al., where for computing equilibria they refer to Koller et al., 1994, which solves finite-action-set games and not continuous-action-set ones). To be able to compute this Nash equilibria reliably over continuous sets, one would require to adopt a convex-concave structure and introduce associated network architectures, which we do in our work. Further, they discuss tabular/finite state-action-set settings (Section 4.3, after Theorem 4.2 and Appendix A of Qiu et al. in the paragraph titled "Linear and Tabular Cases" ), but they give no continuous-action example and no way of solving the inner min-max problem when is a general kernel/neural function over a continuous action set, where pure saddle points need not exist without additional structure. Finally, our setting also differs: they study reward-free exploration in episodic finite-horizon games under a realizability assumption on the transition, which amounts to assuming that the approximation error of the function class is zero (up to the NTK linearization term in the neural case, Theorem 4.2). In contrast, we study infinite-horizon discounted online fitted Q-iteration with pure-strategy security strategies, where the approximation error associated with the convex-concave class enters explicitly through . If the reviewer deems fit, we are happy to cite this work and add the comparison to our related work.
References:
Qiu et al. (2021). On Reward-Free RL with Kernel and Neural Function Approximations: Single-Agent MDP and Markov Game.
Koller et al. (1994). Fast Algorithms for Finding Randomized Strategies in Game Trees
Replying to Questions 1/2 and Weaknesses 1/2/3
Thank you for your review and comments! We have replied to your questions/weaknesses raised by clubbing them as appropriate. We are happy to revise our manuscript to reflect this discussion. Looking forward to your comments.
Question 1 and Weaknesses 1, 2.
We agree with you that PICNNs and bilinear terms are not new individually, and we do not claim the architecture as our main contribution. Our contribution instead is using these networks to guarantee a convex-concave structure which satisfies Assumption 6 and makes the Bellman min-max well posed (a pure-strategy saddle point exists and can be computed by standard solvers). The theoretical analysis of our main result of theorem 1 crucially depends on this convex-concave behavior. For an unstructured network on the other hand, the min-max problem inside the Bellman operator is non-convex-non-concave, so a pure-strategy saddle point is not guaranteed to exist and a min-max solver need not compute a saddle point that minimax FQI given in Algorithm 1 needs. Assumptions 6/7 and hence Theorem 1 do not apply for a unconstrained network architecture. As for the limited expressivity of the bilinear cross-term of equation 3's architecture, while true for equation 3, as we note in Section 3 lines 178-181, our analysis is not exclusive to this architecture we propose in equation 3, one can make more expressive architectures depending on the problem. The point of proposing such an architecture in the paper is to instill confidence that the architecure-related Assumption 6 we make in the paper can be realized in practice and is not just a theoretical artifact. Please see our reply to reviewer BygB where we give an example architecture that has more expressive coupling compared to bilinear terms, and satisfies the convex-concave assumption we require. Further, δapprox is the inherent Bellman error of the class, which is game/architecture dependent and does not have a problem-independent closed form that we can provide. Please see our reply to reviewer BygB for a non-LQ game/architecture for which δapprox can be made arbitrarily small by increasing network capacity/width. Please see our response to Q2 below to see empirical evidence of the advantage of our proposed architecture.
Weakness 3/ Question 2
Empirically, we have now compared the PICNN architecture described in equation 3 with a standard MLP Q-network architecture as a baseline, using the same inner solver, sample budget per iteration, number of iterations and other experimental parameters. The MLP network has same size and activations like the PICNN for a fair comparison. In addition to the TD error, as you suggested, to evaluate the performance of the learned policies, we now empirically find the Nash gap of the learnt policies which measures how close they are to Nash equilibrium policies (lower Nash gap is better) and report the mean ± standard deviation Nash gap averaged over 10 seeds for each architecture method, using n=32 samples per iteration.
In the existing pursuit-evasion game in the paper, our PICNN Q-network recorded a lower Nash gap of 2.05×10−3±0.94×10−3 compared to the baseline unconstrained Q-network Nash gap of 3.22×10−3±0.66×10−3. Further, we repeated this experiment in a 3-dimensional environment, resulting in a increased-dimension state (12 dimensions from 8 earlier) and action spaces (3 dimensions per player to 2/player earlier), with similar costs and linear dynamics and keeping all experimental parameters/network sizes the same. We found that on this increased dimension pursuit-evasion experiment our PICNN Q-network again recorded a lower Nash gap of 0.82×10−3±0.29×10−3 compared to the baseline unconstrained Q-network Nash gap of 1.23×10−3±0.19×10−3.
On experimental section
We respectfully emphasize that this is primarily a theoretical paper. The experiments are intended to show that the structure required by our assumptions can be realized and trained in practice and is not only a theoretical artifact. Thus, we defer larger scale experiments to future application-oriented work.