acceptodds
Under review as a conference paper at ICLR 2027

Can Play That Game: Online Fitted -Iteration for Continuous-Action Zero-Sum Markov Games with Convex-Concave Function Approximation

Abstract

Zero-sum Markov games arise in a wide variety of sequential decision-making problems such as adversarial learning and planning against modeled uncertainties. However, prior work on finite-sample guarantees on the learned state-action value function (-function) for zero-sum Markov games is largely restricted to finite-action settings, or to continuous-action games in which agents have linear dynamics and quadratic rewards (i.e. linear-quadratic, or LQ, games). A central challenge in extending such guarantees to more general continuous-action zero-sum Markov games is that the associated Bellman operator involves a minimax problem that need not admit a tractable saddle-point solution. To this end, we first introduce a class of neural network function approximators for the -function that is convex-concave in the players' actions, which guarantees that this minimax problem admits a pure-strategy saddle point. We then study an online variant of fitted -iteration employing this function class and establish, to the best of our knowledge, the first finite-sample guarantees for non-LQ zero-sum Markov games with continuous states and actions.

Primary area:
reinforcement learning
Keywords:
game theory, reinforcement learning, zero-sum Markov games

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_D7hfOpenReview ↗
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
  1. The paper proposes a convex–concave neural QQ-function approximator combining PICNNs with a bilinear interaction and establishes finite-sample QQ-approximation and Nash-gap bounds.

  2. The pursuit-evasion experiment demonstrates stable training behavior of the proposed function approximator.

Critical weaknesses
  1. 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.

  2. 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..

  3. 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
  1. 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?

  2. 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.

  3. 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 Rd\mathbb{R}^d.

2 comments
AuthorsOpenReview ↗

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\delta_{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\delta_{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 ±\pm standard deviation Nash gap averaged over 10 seeds for each architecture method, using n=32n=32 samples per iteration.

In the existing pursuit-evasion game in the paper, our PICNN QQ-network recorded a lower Nash gap of 2.05×10−3±0.94×10−32.05\times 10^{-3}\pm0.94\times 10^{-3} compared to the baseline unconstrained QQ-network Nash gap of 3.22×10−3±0.66×10−33.22\times10^{-3}\pm 0.66\times 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 QQ-network again recorded a lower Nash gap of 0.82×10−3±0.29×10−30.82\times 10^{-3}\pm0.29\times 10^{-3} compared to the baseline unconstrained QQ-network Nash gap of 1.23×10−3±0.19×10−31.23\times10^{-3}\pm 0.19\times 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.

AuthorsOpenReview ↗

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 Q(s,⋅,⋅)Q(s,\cdot,\cdot) 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 Q(s,⋅,⋅)Q(s,\cdot,\cdot) 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 QQ 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 δapprox\delta_{approx}. 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

Reviewer_jxR1OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This work studies minimax Q-learning for zero-sum Markov games with continuous state and action spaces. The authors introduce neural Q-function approximators that are convex-concave. Using this architecture, they establish finite-sample error bounds for batched minimax Q-learning relative to the Bellman fixed point, assuming that the fixed point admits pure-strategy saddle points. The analysis extends neural function approximation guarantees beyond the linear–quadratic setting.

Critical strengths
  1. The paper is clearly written and presents the problem formulation and main results effectively.

  2. The proofs appear technically sound.

Critical weaknesses
  1. The analysis relies on many assumptions. I understand that some may be necessary to establish theoretical guarantees for neural network function approximation. However, the authors should explain when these assumptions can be satisfied and provide concrete examples to clarify their practical relevance.

  2. The algorithmic and technical novelty is unclear. Based on my reading, the method appears to combine standard DQN with the Markov Games. The authors should identify the specific innovations in the algorithm and analysis and explain which challenges require new ideas beyond a direct combination of existing methods.

Questions for authors
  1. Could the authors provide an explicit bound on the approximation error δapprox\delta_{\mathrm{approx}} in terms of neural network depth and other relevant architectural parameters? The discussion should also clarify whether the Markov game setting introduces additional approximation challenges compared with the single-agent setting and how these challenges affect the bound.

  2. The connection between the simulation results and the theoretical guarantees is unclear. The authors should explain which theoretical predictions the experiments are intended to examine and how the reported results relate to those predictions.

2 comments
AuthorsOpenReview ↗

Reply to all Questions/Weaknesses

Thank your for your review! We will reply to your questions/weaknesses raised in order, looking forward to your response!

Question 1

  • On δapprox\delta_{approx}: δapprox\delta_{approx} is the inherent Bellman error of the function class, and it depends on the game and the class and has no problem-independent closed form in terms of depth or width. Thus it is not possible for us to give a general bound as such . Instead, we kindly request the reviewer to look in our response to reviewer BygB, where we show a concrete non-LQ class of games and a convex-concave QQ-network class for which δ_approx is provably arbitrarily small by increasing network capacity.

  • Difficulty in the games setting beyond single agent: The Markov game setting adds one difficulty: the Bellman operator T\mathcal{T} involves a min-max rather than a single max, this brings with it min-max equilibrium (saddle point) existence issues which we currently highlight in Remark 1 (lines 125-135) that are not there in the single-agent setting. This difficulty is what motivates us to explore the convex-concave structure in our manuscript.

We are happy to revise the mansucript to reflect this discussion.

Question 2

As we state in Section 5 lines 375-380, the experiments are not meant to verify the constants of Theorem 1. Theorem 1 studies the FQI algorithm which assumes exact regression which is not possible to implement exactly and is of theoretical interest only. The experiments study the practical variant where regression is replaced by a gradient step, as stated in lines 375-380. The purpose of the experiment is actually two examine two things the theory relies on: that the convex-concave architecture we propose together with the minimax oracle can be trained stably in a non-LQ game, and that the error decreases with the per-iteration sample size nn, consistent on a high level with the statistical terms in Theorem 1 that decay with nn.

Weakness 1

Assumptions 1–5 and 8 are the standard conditions of the fitted Q-iteration literature, also commonly made in the references we mention in the paper: compactness, Lipschitz rewards and transitions, an exploratory sampling distribution, and concentrability. These standard assumptions are used to model and design several RL algorithms across the fields of control, robotics etc. Our simulation game is a concrete example of a setting meeting these assumptions. Assumption 6 is enforced by the architecture we propose, Assumption 7 is met by existing minimax solvers that one can use, and Assumption 9 is only the existence of a pure saddle point. Currently, we discuss the feasability/acceptability of our assumptions in lines 268-269, 278-282, 292-296, 302-303, and 313-319 of our paper. We are happy to enrich this discussion in accordance with the reviewer's comments.

Weakness 2

On novelty: we would like to reiterate that our novel contribution is theoretical and not algorithmic: the error decomposition bound of Theorem 1, and we do not claim that our novelty is to combine DQN algorithm with Markov games as such. It is common to theoretically analyze the performance/tractability of popular existing algorithmic schemes. Further, the novel technical aspects are

  • Main challenge we tackle: In continuous action spaces a generic QQ need not have a pure saddle point, so the Bellman minimax is not even well posed; we address this with a convex-concave function class that we introduce, which also makes the inner problem Bellman minimax problem tractable.
  • Results for non-LQ continuous state-action space games The above insight we have makes it possible for us to provide the error decompoition bound of Theorem 1 for zero sum Markov games with continuous state-action spaces that are not necessarily LQ. Prior work either only handled discrete action spaces, or in the continuous action setting, handled only LQ games.

Thank you for your response. I will decide my final score after discussing with other reviewers and AC.

Reviewer_BygBOpenReview ↗
Rating
2
Confidence
2
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

The paper consider two-player zero-sum discounted Markov games with continuous state and action spaces and the problem of learning the minimax Q-function from samples. The authors argue that the main obstacle in going beyond the finite-action and the linear-quadratic (LQ) setting is the min-max problem inside the Bellman operator. With pure strategies, a saddle-point need not exist for an arbitrary QQ, while mixed-strategy saddle-points over continuous action spaces are infinite-dimensional objects that are hard to compute.

To this end, the authors restrict the Q-function class to networks that are convex in the minimizer's action and concave in the maximizer's action: Qθ(s,u,v)=Nθ1(s,u)−Nθ2(s,v)+u⊤Mθ3(s) v,Q_\theta(s,u,v) = N_{\theta_1}(s,u) - N_{\theta_2}(s,v) + u^\top M_{\theta_3}(s)\, v, where Nθ1,Nθ2N_{\theta_1}, N_{\theta_2} are partially input convex neural networks (PICNN, Amos et al. 2017) and Mθ3M_{\theta_3} is an unconstrained matrix-valued network. By Sion's theorem, every network in the class has a pure saddle-point at every state and it can be computed up to ϵ\epsilon-accuracy with off-the-shelf convex-concave solvers.

The algorithm (Algorithm 1) is a minimax fitted Q-iteration. At every iteration kk:

  • a fresh batch of nn i.i.d. tuples (si,ui,vi)(s_i,u_i,v_i) is drawn from a fixed exploratory distribution σ\sigma and the next states are drawn as si′∼P(⋅∣si,ui,vi)s_i' \sim P(\cdot|s_i,u_i,v_i),
  • a minimax oracle returns an ϵ\epsilon-approximate saddle-point (u~i,v~i)(\tilde u_i, \tilde v_i) of Qk(si′,⋅,⋅)Q_k(s_i',\cdot,\cdot),
  • the targets yi=r(si,ui,vi)+γQk(si′,u~i,v~i)y_i = r(s_i,u_i,v_i) + \gamma Q_k(s_i',\tilde u_i,\tilde v_i) are formed and Qk+1Q_{k+1} is the exact least-squares minimizer over the function class.

The main result (Theorem 1) is a high-probability bound on Es∼ρ[sup⁡u,v∣QK−Q⋆∣]E_{s\sim\rho} [\sup_{u,v}|Q_K - Q^\star| ].

The bound decomposes into a term that decays as γK\gamma^K, an oracle error term linear in ϵ\epsilon, the inherent Bellman error δapprox\delta_{\rm approx} of the function class (Eq. 6), and statistical terms that depend on the covering number of the function class and an inverse volume factor of the joint action space. The analysis assumes that the fixed point Q⋆Q^\star admits a pure saddle-point at every state (Assumption 9) together with the usual concentrability coefficients. Corollary 1 turns the bound into a Nash gap bound for the security strategies induced by QKQ_K. In the appendix, the authors bound the Lipschitz constant and the covering number of the proposed architecture. Finally, they run a TD-style version of Algorithm 1 (a single gradient step per iteration) on a planar pursuit-evasion game with double integrator dynamics and report that the training error does not diverge.

Critical strengths
  • The idea of a convex-concave Q-network is simple and natural. It makes the inner min-max problem of the Bellman operator tractable for every network of the class and the pure security strategies come "for free".
  • The paper clearly identifies three sources of error (oracle, approximation, statistical) and Theorem 1 keeps them separated. This makes it easy to read what each component of the algorithm costs.
  • The authors provide explicit Lipschitz and covering-number bounds for the particular architecture they propose rather than leaving them as abstract quantities (although see my comments on the proofs below).
  • The main text is well-written and easy to follow.
Critical weaknesses

Convex-concavity buys tractability, not approximation. In my opinion, this is the main weakness of the paper. The convex-concave structure guarantees that the min-max problem on each fitted network has a pure saddle-point that can be computed. It does not guarantee that the network class can represent Q⋆Q^\star or the Bellman updates of its members. All of this is pushed into δapprox\delta_{\rm approx}, which is the worst case over all Q∈FQ \in \mathcal{F} of the best fit to T~Q\tilde{T}Q, i.e., an inherent Bellman error. Sure, this term is standard in the FQI literature (Munos & Szepesvári 2008), but here it is exactly the quantity that decides whether the result goes "beyond LQ".

Assumption 9 (pure saddle-point of Q⋆Q^\star) does not imply that Q⋆Q^\star is close to convex-concave. A simple example: take U=V=[−1,1]U=V=[-1,1], action-independent and state-independent transitions, and reward r(u,v)=g(u)−g(v)r(u,v) = g(u) - g(v) with g(t)=(t2−1/4)2g(t) = (t^2 - 1/4)^2. The value is zero, there are pure saddle-points at u,v∈{−1/2,1/2}u,v \in \{-1/2, 1/2\}, so Assumption 9 holds, and since the continuation value is zero, Q⋆=rQ^\star = r. At v=1/2v=1/2, Q⋆(⋅,1/2)Q^\star(\cdot, 1/2) takes the values 0,1/16,00, 1/16, 0 at u=−1/2,0,1/2u=-1/2, 0, 1/2. By midpoint convexity, any convex f(⋅,1/2)f(\cdot,1/2) within uniform distance dd of these values needs 1/16−d≤d1/16 - d \le d, i.e., d≥1/32d \ge 1/32. Thus every QK∈FQ_K \in \mathcal{F} has worst-action error at least 1/321/32 at every state, regardless of nn, KK, or ϵ\epsilon, and δapprox\delta_{\rm approx} is also bounded away from zero.

The paper does not offer any class of non-LQ games for which δapprox\delta_{\rm approx} is provably small. Line 349 says that δapprox\delta_{\rm approx} is zero "when the underlying game satisfies Bellman completeness", but for which non-LQ games is the convex-concave class Bellman complete? Without such a class, the claim of the "first finite-sample guarantees for non-LQ zero-sum Markov games" (abstract, lines 78-80 and 359-360) is a conditional error decomposition whose right-hand side may exceed the trivial bound 2Qmax⁡2Q_{\max}. On top of that, Assumption 1 requires compact action spaces and bounded Q-functions, so the result does not even recover the standard unconstrained LQ games it claims to go beyond. (With unbounded actions, an arbitrarily small error in a quadratic coefficient, e.g., Q⋆=u2−v2Q^\star = u^2 - v^2 vs. QK=(1+d)u2−v2Q_K = (1+d)u^2 - v^2, makes sup⁡u,v∣QK−Q⋆∣\sup_{u,v}|Q_K - Q^\star| infinite.)

What is proven is a finite-KK bound, not convergence. Lines 317-318 state that Assumption 9 is needed "so that Algorithm 1 converges towards a meaningful equilibrium". Theorem 1 does not show that the iterates Q0,Q1,…Q_0, Q_1, \dots converge to anything as K→∞K \to \infty for a fixed batch size. The exact operator TT contracts, but the fitted update (sampled targets, approximate oracle, projection onto a nonconvex neural network class) need not. The γK\gamma^K term forgets the initialization while the remaining terms form an error floor, and the statistical terms even grow with KK through the union bound (log⁡(3K/δ)\log(3K/\delta), log⁡(6KN(η1)/δ)\log(6K N(\eta_1)/\delta)). I would ask the authors to rephrase these claims.

The setting is not really "online". Algorithm 1 draws i.i.d. state-action tuples from a fixed σ\sigma at every iteration and needs a transition sample for each of them. This is a generative model (or reset) assumption, rather than learning from trajectories generated by behavior policies. Assumption 4 further requires the conditional action density of σ\sigma to be bounded below on the whole joint action space. "Online" here only means that the batches are not reused, which can mislead the reader.


Gu, S., Lillicrap, T., Sutskever, I. and Levine, S., 2016. Continuous deep Q-learning with model-based acceleration. ICML.

Li, S., Wu, Y., Cui, X., Dong, H., Fang, F. and Russell, S., 2019. Robust multi-agent reinforcement learning via minimax deep deterministic policy gradient. AAAI.

Kamalaruban, P., Huang, Y.T., Hsieh, Y.P., Rolland, P., Shi, C. and Cevher, V., 2020. Robust reinforcement learning via adversarial training with Langevin dynamics. NeurIPS.

Huang, B., Lee, J.D., Wang, Z. and Yang, Z., 2022. Towards general function approximation in zero-sum Markov games. ICLR.

Jin, C., Liu, Q. and Yu, T., 2022. The power of exploiter: Provable multi-agent RL in large state spaces. ICML.

Chen, J. and Jiang, N., 2019. Information-theoretic considerations in batch reinforcement learning. ICML.

Antos, A., Szepesvári, C. and Munos, R., 2008. Learning near-optimal policies with Bellman-residual minimization based fitted policy iteration and a single sample path. Machine Learning.

Questions for authors
  • Can you give a substantive class of non-LQ games and a network class for which δapprox\delta_{\rm approx} is provably small (or zero)? For example, would games with action-linear dynamics and convex-concave rewards suffice, or does the continuation value break convex-concavity eitherway?
  • Do you claim convergence of the iterates for a fixed batch size or only the finite-KK bound of Theorem 1? If the latter, please revise lines 317-318.
  • Is the intended data model a generative simulator / reset distribution? Would you be able to extend the analysis to correlated trajectory data generated by behavior policies, e.g., under a β\beta-mixing assumption as in Antos et al. 2008?
  • Can you provide the corrected calculations of Appendices B, C.1 and C.3 and the updated constant of Theorem 3?
  • For the pursuit-evasion game, what is the numerical value of the right-hand side of Theorem 1 compared to the trivial bound 2Qmax⁡2Q_{\max}?
  • What is the Nash gap of the learned policies in your experiments and how does it compare to an unconstrained Q-network baseline?
3 comments
AuthorsOpenReview ↗

Reply to Questions 1,2,3,4/Weakness 1,2,3

Thank you for your insightful review! We really appreciate your comments and will reply to each question/weakness in order. Looking forward to your comments!

Question 1/ Weakness 1

On claims of beyond LQ: An example of a concrete class of non-LQ games for which δapprox\delta_{approx} is small:

  • Dynamics: Consider affine decoupled dynamics given by game state s=(x1,x2)s=(x^1,x^2), where player ii has its state xix^i evolving with affine dynamics xi′=Aixi+Biui+wix^{i'}=A^ix^i+B^iu^i+w^i, (with u1=u,u2=vu^1=u,u^2=v), the noise wiw^i is independent of (s,u,v)(s,u,v). The state/action sets are compact, convex and state is invariant under the dynamics.
  • Reward: A bounded, Lipschitz function jointly convex in (x1,u)(x^1,u) and jointly concave in (x2,v)(x^2,v), for example r=a(x1,u)−b(x2,v)+x1⊤Cx2+u1⊤Du2r=a(x^1,u) - b(x^2,v) + x^{1\top}Cx^2 + u^{1\top}Du^2, where aa and bb are functions convex in their inputs. This can be non-LQ whenever we choose a,ba,b to be non-quadratic convex functions appropriately.
  • Architecture Class: As you correctly point out in your review, the continuation value needs to be handled carefully and the network architecture needs to have mixed curvature that depends on the players actions uu and vv, unlike equation 3 in the manuscript. An example of such an architecture form is the convex conjugate form Q~(s,u,v)=max⁡p∈Bp(p⊤z1−Nθ(p,z2))\tilde Q(s,u,v)=\max_{p\in B_p}\left(p^\top z^1 - N_{\theta}(p, z^2)\right), where z1=(x1,u)z^1=(x^1,u) and z2=(x2,v)z^2=(x^2,v), NθN_{\theta} is a fully input convex neural net and BpB_p is a ball whose size we can choose. Note that Q is convex in (x1,u)(x^1,u), concave in (x2,v)(x^2,v) and has mixed curvature that also depends on the players controls. δ_approx is small for this class (for BpB_p large enough and NθN_\theta sufficiently wide) because (i) the minimax Bellman operator maps block convex-concave, Lipschitz functions to the same set, since the next-state value is convex in x1x^1 and concave in x2x^2, the dynamics are affine and decoupled, and the noise is independent of the actions; and (ii) the conjugate-form net Q~\tilde Q can approximate these targets because its mixed curvature ∇uv2Q~\nabla^2_{uv}\tilde Q is not independent of (u,v)(u,v) (unlike Eq. (3) in the current manuscript, where it is the matrix M(s)M(s)). It can therefore capture the continuation value for non-LQ games, whose mixed curvature varies with the controls. Moreover, every continuous Lipschitz function that is convex in (x1,u)(x^1,u) and concave in (x2,v)(x^2,v) can be written in this conjugate form with pp in a ball and a jointly convex function, which input-convex networks approximate. Note that it is also possible to train a network with this choice of Q~\tilde Q by taking the required gradients using techniques involving the envelope and implicit function theorems from calculus. We are happy to revise our mansucript to include this non-LQ game example for which δapprox\delta_{approx} is small to instill more confidence in the beyond LQ setting claim.

Further, we would like to reiterate that another reason of our beyond LQ claim is that the current LQ-focused work we mention in the manuscript cannot be practically applied to non-LQ problems as they require LQ specific inputs such as affine policy matrix, quadratic cost matrices etc. As for unconstrained LQ games, we can apply our current algorithm on unconstrained LQ games by clipping the state/action strajectories.

On the Reviewer's example in weakness 1 and Assumption 9 Thank you for the interesting example. We fully agree that our convex-concave formulation is bringing about tractability and does not necessarily imply approximability and are happy to revise our manuscript to reflect this.

Question 2/ Weakness 2

We fully agree with the reviewer and will revise any claims of convergence that currently exist in our manuscript to instead stating that we present a finite-K sample bound that provides an error decomposition.

Question 3 / Weakness 3

Yes, the intended data model is a generative simulator / reset distribution, we used the term online to distinguish it from the setting where FQI is performed on fixed trajectory data collected offline with a behavior policy. We will make this more clear in the manuscript. As for extending the analysis to correlated trajectory data generated by behavior policies, we strongly suspect that our analysis can carry over to such data settings with the β\beta-mixing assumption pointed out by the reviewer. Though an exact analysis is out of scope for our current manuscipt, and we defer it for future work.

Question 4

We believe the part of the review relevant to this question of the reviewer is missing from the review posted by the reviewer. Regardless, we will carefully check all calculations and update any erroneous constants in the final manuscript.

AuthorsOpenReview ↗

Questions 5, 6

Question 5 / Looseness of Bound of Theorem 1

For the pursuit-evasion game, by optimistically assuming the theorem 3 term BθΓ=1B_\theta \Gamma=1, and by doing a grid search and setting η1≈0.86,η2=4\eta_1\approx0.86,\eta_2=4, we get the RHS of theorem 1 for the PE game as ≈2173\approx 2173. While this is surely a loose statement and looser than 2Qmax2Q_{max}, we would like to iterate that the main point of such analysis is to under the error decomposition of the numerous quantities like n,Kn,K, architecture choice, etc, and that previous FQI related work we cite in the paper also suffer from such looseness. Further, if the reviewer agrees, we can revise the theorem 1 RHS to state min⁡(2Qmax\min(2Q_{max}, current RHS bound$)$.

Question 6

We trained an unconstrained QQ-network baseline, keeping the same size and activation as our PICNN QQ-network in the manuscript for a fair comparison. We kept other choices the same as well, only swapping the PICNN with the unconstrained QQ-net and trained over 10 seeds and keep the number of samples n=32n=32. We state the mean$\pm$standard deviation Nash gap. Testing at the end of 100100 learning iterations, our PICNN QQ-network recorded a lower Nash gap of 2.05×10−3±0.94×10−32.05\times 10^{-3}\pm0.94\times 10^{-3} compared to the baseline unconstrained QQ-network Nash gap of 3.22×10−3±0.66×10−33.22\times10^{-3}\pm 0.66\times 10^{-3}. We are happy to include this additional result in the manuscript.

Looking forward to your response!

AuthorsOpenReview ↗

Additional Experiment for Question 6

We have done another experiment. We repeated the pursuit-evasion experiment in a 3D environment (as opposed to 2D planar environment before), 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 QQ-network again recorded a lower Nash gap of 0.82×10−3±0.29×10−30.82\times 10^{-3}\pm0.29\times 10^{-3} compared to the baseline unconstrained QQ-network Nash gap of 1.23×10−3±0.19×10−31.23\times10^{-3}\pm 0.19\times 10^{-3}.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of Main Points of Rebuttal

Dear reviewers and chairs, thank you for your service. We have now addressed all concerns raised by reviewers and give a brief summary of the major points brought up in the reviews. We will revise the final manuscript to reflect all our discussions/feedback with sufficient details.

  1. (Reviewer BygB) Is there a concrete non-LQ class of games/convex-concave function approximation architecture for which δapprox\delta_{approx} is small? Yes, and we have given an example of such game/architecture classes in our response to reviewer BygB.

  2. (Reviewers BygB, D7hf) Experimental metrics that evaluate learnt policy performance and comparison with unconstrained QQ network. We evaluate the Nash gap, which quantifies how close learnt policies are to Nash equilibrium, and find that our convex-concave architecture given by equation 3 yields more favorable (lower) Nash gap values compared to unconstrained QQ network baseline. Details are in responses to Reviewers BygB and D7hf.

  3. (Reviewer D7hf) Additional experiment. We conducted an additional 3D version of the pursuit evasion game and found that our convex-concave architecture again yields more favorable Nash gap values compared to unconstrained QQ network baseline in the 3D game case as well. Details are in responses to Reviewer D7hf.

All other points brought up by reviewers have also been addressed in the respective replies.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.