- Rating
- 3
- Confidence
- 3
- Informativeness
- 3
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
The paper studies games where players privately receive random subsets of available actions. Under independence across players, it reduces equilibrium computation to implementable action marginals and shows that these marginals admit approximate proportional-weight representations, Additional results establish polynomial-bit approximate-equilibrium representations and a separation when availability is corrected.
CAT-FTPL achieves expected hindsight ranking regret of , yielding convergence of averaged marginals to Nash equilibrium in two-player zero-sum games. A stochastic approximation procedure recovers compact playable strategies, with a slower finite-time guarantee. Experiments examine convergence and compare runtime against expanded LP and Bayesian-game methods.
Critical strengths
- Quantitative compactness and its limits. Polynomial-bit approximate equilibria provide a meaningful improvement over explicitly storing a policy for every availability subset. The correlated-availability lower bound complements this result by identifying a genuine limitation of compact representation
- A learning guarantee suitable for adaptive self-play. The analysis controls the expected hindsight maximum over ranking policies, rather than only regret against a comparator fixed outside the expectation. Connecting this guarantee to averaged equilibrium marginals and then recovering a playable weight vector provides a useful computational framework.
Critical weaknesses
- Several central ingredients has substantial precedents. Azrieli and Rehbeck(2026) already related positive luce weights to the relative interior of feasible marginals sets, supplying much of Therorem 4.5's existience result. Neu and Valko already obtain the same expected regret order using FTPL and counting-asleep estimators. The stronger hindsight guarantee and quantitative bit results remain valuable. but the presentation should distinguish these additions explicitly.
- The runtime comparison does not evaluate the complete output pipeline at matched accuracy. Figure 1 reports CAT-FTPL's final-run runtime for obtaining low empirical marginal residual, excluding compact extraction and preceding doubling runs, while the LP baseline solves an expanded game. Moreover, Theorem 5.8 gives approximately residual for the final compact strategy, compared with marginal convergence, Figure 3b fixes the input marginals across extraction horizons, so it isolates extraction rather than testing the complete procedure under varying total budgets.
Questions for authors
- Please explicitly separate the representation and regret results inherited from prior work from the new bit-complexity, hindsight-regret, and extraction guarantees. What is the precise additional guarantee relative to each closet predecessor?
- Can you report the total runtime and availability-simulator calls required to produce final compact strategies at a common verified equilibrium tolerance, including learning, extraction, stopping, and residual evaluation?
2 comments
Thank you for the detailed response, the clarification separating inherited results(the qualitative representation from Azrieli and Rehbeck; the regret order from Neu &Valko) from the new contributions(quantitative bit-complexity bounds, the impossibility result without independence, the stronger guarantee, and compact recovery) addresses my first concern. Please keep this distinction explicit in the main text. The added end to end runtimes in Figure 1 and Table 3 answer my second question. I still see the recovery rate and the lack of an accuracy-matched baseline comparison as limitation. Overall I maintain my positive assessment and keeping my rating of 3.
Response to Review
We thank the reviewer for their thoughtful comments and positive assessment of our paper. Please see our responses below. We have updated our submission PDF accordingly. Throughout, updates are highlighted in blue.
Weaknesses
We agree that the relationship to prior work should be made clearer. We would like to clarify that our main contribution is a complete procedure for computing compact, playable approximate Nash equilibria in GSAS. The qualitative representation result follows by approximation from Azrieli and Rehbeck. However, our alternative proof allows us to establish quantitative bit-complexity bounds beyond existence: an ϵ-NE can be represented using O(∣Ai∣log(∣Ai∣/ϵ)) bits per player under independence (Theorem D.2 and Corollary D.4). Theorem D.5 shows that a general guarantee of this kind is not possible without independence.
Our learning algorithm builds on Neu and Valko and achieves the same regret bound, while strengthening their stated guarantee from maxτE[GT,i(τ)] to E[maxτGT,i(τ)]. The latter controls the best ranking for each realized learning trajectory and is the guarantee required for our equilibrium analysis, which requires additional technical machinery. This additional estimator analysis is given in Appendix B.10.
Finally, our recovery procedure converts the learned marginals into compact strategies with a finite-time equilibrium-gap bound (Theorem 5.8). Learning a marginal distribution alone does not provide this playable representation, as stated in lines 380-382.
Regarding Figure 1, we stated in Section 6 (lines 430-431) that “the computed solutions are not directly comparable in terms of output quality, but only in runtime.” The purpose of this experiment is to demonstrate the scalability problem caused by the expanded LP representation. With regards to scalability, note the LP runtime clearly exhibits exponential behavior, and a line-of-best-fit in logspace on the mean runtime for sizes ≥8 predicts that solving a 15×15 game would take around 17 days, and the 150×150 game our approach solves would take approximately 10131 seconds, which are far beyond feasible. Appendix C.2.1 (lines 1679-1684) specifies that the reported CAT-FTPL time is for the final run. The reviewer is therefore correct that this figure excludes preceding doubling runs and compact recovery.
Figure 3b does evaluate compact strategies recovered from CAT-FTPL marginals, following the procedure described in Section 5.2 (lines 402-404). As specified in Appendix C.2.2 (lines 1719-1724), the input marginals are obtained from CAT-FTPL with T=120,000 and held fixed while the recovery horizon varies. This isolates the recovery error. Figures 2b and 3b together corroborate Theorem 5.8. We have clarified this in lines 497-498 of the updated PDF.
To give a better idea of the end-to-end runtime of our method, we have modified Figure 1 to additionally include the wallclock time of a final run of CAT-FTPL followed by the compact recovery (Algorithm 3), stopping when the estimated SPR of the compact vector is below 0.05. We have modified the corresponding text to reflect this change, both in Section 6 and Appendix C.2.1. We have further added Table 3 in Appendix C.2.1, with the total runtime and availability samples across all runs (i.e., including preceding doubling runs). Tables 1 and 2 provide similar data for the final run only.
Questions
Q1: Please see our response to Weakness 1 above.
Q2: Please see our response to Weakness 2 above, particularly the addition of Table 3 in Appendix C.2.1. For instance, the mean total runtime (i.e., including all doubling runs) of CAT-FTPL followed by Alg. 3 to reach an estimated SPR≤0.05 for the 100×100 GSAS used in Figure 1 was 203 s. For a 300×300 GSAS, the mean total runtime was 707 s. In comparison, the final runtime (i.e., excluding non-final doubling runs) for CAT-FTPL followed by Alg. 3 was 117 s for the 100×100 GSAS and 380 s for the 300×300 GSAS.