acceptodds
Under review as a conference paper at ICLR 2027

Binding Budgets Destabilize Primal-Dual Learning in Random Games

Abstract

Primal-dual learners raise a Lagrange multiplier while spending exceeds a budget and lower it while under. No prior study measures how often such learners fail to converge in random games, or for which budgets. We measure both in random two-player games with per-action costs and one budget each. Outside zero-sum games, binding budgets make more runs from almost the same start separate, with a peak at intermediate budgets. A Lyapunov exponent confirms this trend for chaos. The peak is intermediate because tighter budgets bind harder but leave fewer games feasible, and infeasible games separate less often. We trace this non-convergence to delay: because the multiplier lags spending, each strategy and its multiplier overshoot and oscillate. We prove for two actions that competitive coupling enlarges the linearized oscillation, averaged over both players' independent phases. Learning the multiplier is the main cause of the added separation: learners instead projecting strategies inside the budget almost never separate on the same feasible games. Damping or a proportional term on the multiplier restores convergence on most feasible games, the latter with far less late-run spending above the budget.

Primary area:
learning on time series and dynamical systems
Keywords:
learning in games, constrained games, primal-dual dynamics, Lyapunov exponents, regime diagram, multi-agent learning

Reviews

Among:
Shape:
1234this paper, Bottom 2%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.33 over 3 reviews, above 2% of the others.
Reviewer_weTUOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
1
Soundness
3
Read review
Paper summary

The paper examines the convergence of primal-dual Lagrangian-based methods in random games. The basic question is how the presence of budgets affects convergence in games, and what's the mechanism that causes non-convergence. One of the findings in the paper is that damping provides a remedy to non-convergence.

Critical strengths

On the positive side, I believe that the paper studies an important and well-motivated problem. There has been a surge of research recently that examines learning in the presence of budgets. This is motivated by a number of central applications, such as autobidding. The paper can be viewed as part of this line of work. It also provides some new insights about the effect of budgets in the convergence of primal-dual methods. To my knowledge, these insights are new and somewhat informative.

Critical weaknesses

I'm afraid the paper has several critical issues:

  • The first issue is that the writing quality is really poor. Even though I'm an expert in this area, I was really struggling to follow the basic logic in each sentence. Among others, the paper casually uses terms that are non-standard (as if a reader is supposed to know them), and the writing is extremely terse. In my opinion, using AI is perfectly fine, but the paper is supposed to be read by humans, experts or otherwise. At the current stage, the writing quality is far below what's expected in a top-tier conference. I strongly recommend revising entirely the writing.
  • The theoretical results do not go far enough and are very preliminary. The main body contains a single mathematical statement, which is a straightforward lemma. The appendix contains more results, but those are not exposed properly and not adequately discussed in the main body. What I expect to see is not a series of mathematical statements, but rather a discussion on their significance and how one should interpret them.
  • The experiments are conducted on random games, which is a major limitation. Random games are by no means indicative of what happens in representative strategic interactions. So the takeaways from the empirical section are brittle and not convincing. I would recommend conducting experiments in benchmark games (see for example the OpenSpiel library). This would make any conclusions far more interesting.

Overall, the authors are examining an interesting question and some of the insights look promising. However, the current manuscript is not in shape for publication. I believe there are concrete steps the authors can take in a resubmission to significantly strengthen the paper.

Questions for authors

Another suggestion would be to elaborate more on autobidding, since that provides strong motivation for the results of this paper. The authors could also consider expanding their discussion on related work in the online learning literature in the presence of budgets.

Reviewer_jxNTOpenReview ↗
Rating
1
Confidence
4
Informativeness
2
Presentation
1
Soundness
1
Read review
Paper summary

The paper studies primal-dual learning over random games, where each player has a budget on their actions. The paper tests the behaviors of the primal-dual-type learning dynamics with multiplicative weights update on randomly generated games, and provides a set of experimental observations. Those observations illustrate how the involvement of the budgets change the dynamics, oscillating behaviors when the dynamics is not converging, and some fixes to the dynamics.

Critical strengths
  • The general problem the paper studies looks interesting to me: how would the budget cap influence the learning dynamics in games.
Critical weaknesses
  • Based on my understanding, the paper mainly provides some empirical observations on a set of randomly-generated games with budget caps, and some theoretical results on small instances. This can provide some insights but lack the main contribution (e.g., explicit characterization of the behaviors of the dynamics) that supports the paper in my perspective.
  • The wordings in the paper are not accurate. For example, both “random games” and “primal-dual learning” can refer to various setups in my opinion, and widely using them in the paper without clearly defining them makes it difficult to say how this work stands in the literature.
  • The presentation of the paper is poor and I found it difficult to follow, and I think that will block many readers from understanding what the paper delivers.
Questions for authors
  • Could you summarize your theoretical results in the appendix, and how those results help us understand the behaviors of the learning dynamics with the budget caps?
Reviewer_UD1BOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper studies two player random games with an applied budget and the effect this restriction holds. The players in those games run multiplicative weight updates on a Lagrangian. The results are three-fold: 1) binding budgets make learning more often chaotic, 2) the authors attribute this to an oscillation between a strategy and its own multiplier and 3) they show that a proportional term on the multiplier restores convergence. The empirical findings are interesting and thorough, however the theory does not fully cover the experimental setup, and the experiments leave out settings the paper gives as motivation.

Critical strengths

As far as I am aware, this is the first study to add a budget axis to the regime diagram of learning in random games. When players have independent payoffs (p=0), binding budgets raise the chaotic function from 0.04 to 0.375 fraction of feasible games and this holds through 10710^7 steps. I also liked that the effect is tied to how hard the budget binds, not just the budget ratio with 0.79 of games labelled as separating where the budget binds strongly against 0.03 to 0.08 where it does not.

Critical weaknesses

As the authors acknowledge (Table 1), the theoretical results and the experimental findings only partly overlap. The authors describe such differences when they mention the energy-drop check in Remark 4 covers only 275 of 20,000 games or when they mention that restricting games to two actions cuts the chaotic fraction from 0.32 to 0.056. The introduction motivates the work with advertisers adjusting bids under budget and constrained RL. The paper does not focus on structures that define those settings. In auctions, spending depends on rivals’ bids. Comparing the methods of this paper with similar objectives and adapting to those settings would serve to strengthen the conclusions. Budget-constrained auctions have been studied in papers like Balseiro & Gur, where bidders pace their spending with a dual multiplier and Gaitonde et al., whose guarantees would be interesting to explore.

Santiago R. Balseiro, Yonatan Gur. Learning in Repeated Auctions with Budgets: Regret Minimization and Equilibrium. Management Science 65(9): 3952–3968 (2019).

Jason Gaitonde, Yingkai Li, Bar Light, Brendan Lucier, Aleksandrs Slivkins. Budget Pacing in Repeated Auctions: Regret and Efficiency Without Convergence. ITCS 2023: 52:1–52:1.

Questions for authors
  1. The separation test renormalizes the logits “not the multipliers”, and only 0.41 of separating games are chaotic. How do the separating fractions change if the full state, multipliers included, is renormalized?

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of the author response and of the changes in the revised PDF

We thank the three reviewers. This comment summarizes our replies and lists the changes in the revised PDF, where new text is in blue.

(a) Points the reviewers state

  • Reviewer UD1B: "As far as I am aware, this is the first study to add a budget axis to the regime diagram of learning in random games." and "The empirical findings are interesting and thorough".
  • Reviewer jxNT: "The general problem the paper studies looks interesting to me: how would the budget cap influence the learning dynamics in games."
  • Reviewer weTU: "I believe that the paper studies an important and well-motivated problem." and "It also provides some new insights about the effect of budgets in the convergence of primal-dual methods."

(b) Concerns raised by more than one reviewer

  1. Scope and place of the theory (UD1B, jxNT, weTU). Section 4.2 states that the frequency formula (Lemma 1) holds for any number of actions, with the payoff-cost covariance and the cost variance frozen at their fixed-point values. On eight-action cycling runs, with no fitted constant, the median ratio of measured to predicted frequency is 1.03 at τ=1\tau = 1, 1.02 at τ=10\tau = 10 and 1.53 at τ=0.1\tau = 0.1 (Section 5.2). Propositions 2 and 3 are now stated in the body. New Proposition 5 (Appendix A.8): at any number of actions, inside the multiplier bounds, our update has the Jacobian determinant of unconstrained multiplicative weights at the same strategies; in a zero-sum game it exceeds one unless Aij=ai+bjA_{ij} = a_i + b_j, so no fixed point or periodic orbit inside the multiplier bounds is attracting. The reply to jxNT lists all 13 lemmas, propositions and corollaries and what each establishes. Replies: UD1B, comments 1 and 2; jxNT, comments 1 and 2; weTU, comment 2.
  2. Settings beyond random games (UD1B, weTU). In a repeated two-bidder second-price auction with budgets (Appendix D.3), the separating fraction of our learner has no intermediate-budget peak: it is largest at the tightest budget (0.52) and falls broadly as the budget loosens. Its cycling fraction has maxima at intermediate budget ratios. There the lowest bid pays nothing, so every budget can be met and the feasibility structure behind the peak is absent. The revision therefore states the peak for the random games we study. In the ten two-player matrix games of OpenSpiel with budgets we add (Appendix D.12), five games converge in all 2,000 runs without budgets, while 0.4026 to 0.9929 of their runs in which the budget binds and is feasible do not converge. In the four games that never converge without budgets (Matching Pennies and the three Rock-Paper-Scissors games), 0.2674 to 0.4293 of the budgeted runs converge. Replies: UD1B, comments 2 and 3; weTU, comments 1 and 2.
  3. Budget pacing (UD1B, weTU). Section 2 now discusses Balseiro & Gur, who prove convergence when every bidder paces, under a strong monotonicity condition and with step sizes that vanish as the horizon grows; there a bidder's spending depends on the competing bids. Gaitonde et al. show liquid-welfare guarantees that do not need convergence. Replies: UD1B, comment 3; weTU, comment 2.
  4. Writing and definitions (jxNT, weTU). Section 1 now defines "random games" and "primal-dual learning" at first use. Section 4.1 and Appendix C.1 describe the separation test as run, and Sections 4.2 and 6 state what the proofs assume. Replies: jxNT, comments 1 and 2; weTU, comment 2.

(c) Changes in the revised PDF

  1. Abstract and Section 1, pp. 1 and 2: the two definitions; the peak is stated for these random games (UD1B, jxNT, weTU).
  2. Section 2, p. 2: on OpenSpiel, Balseiro & Gur and Gaitonde et al. (UD1B, jxNT, weTU).
  3. Section 4.1, p. 4, and Appendix C.1, p. 33: the separation test as run (UD1B).
  4. Section 4.2, pp. 5, 7 and 8: the scope of the proofs (p. 5); Propositions 2 and 3, and a sentence on Proposition 5 (p. 7); the population of Remark 4 (p. 8) (UD1B, jxNT, weTU).
  5. Table 1, p. 6: "any KK" in bold in two rows (UD1B, jxNT, weTU).
  6. Section 5.1, pp. 8 and 9: "random" in the heading; four variants of the separation test; the chaotic fraction over all games, 0.338 against 0.044 (UD1B).
  7. Section 6, p. 10: a paragraph on what the proofs assume (jxNT, weTU).
  8. Appendix A.4, pp. 20 to 22: Proposition 1 at any number of actions; the steps Remark 4 counts (UD1B, jxNT).
  9. New Appendix A.8, pp. 31 and 32: Proposition 5 (UD1B, jxNT, weTU).
  10. Appendix D.2, pp. 34 and 35: costs correlated with payoffs (Table A40, p. 71) (weTU).
  11. New Appendix D.3, pp. 35 to 37: the budgeted auction (Table A1, p. 36) (UD1B, weTU).
  12. Appendix D.10.8, pp. 53 and 54: the full-state check corrected to 0.0005 to 0.151 (UD1B).
  13. New Appendix D.10.9, p. 54: four variants of the separation test (Table A16) (UD1B).
  14. New Appendix D.12, pp. 69 to 71: ten OpenSpiel matrix games (Table A39, p. 70) (weTU).

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.