Learning to Charge More: A Theoretical Study of Collusion by Q-Learning Agents

Cristian Chica; Gilad Lerman; Yinglong Guo

REVIEW 3 major objections 3 minor 26 references

Learning to Charge More: A Theoretical Study of Collusion by Q-Learning Agents

T0 review · 3 major / 3 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Given two inequalities on the Q-function when exploration ends, Q-learning firms lock onto a collusive price forever.

desk verdict A correct conditional convergence theorem sits next to three vacuous support propositions; the paper's headline claim of first theoretical explanation for Q-learning collusion is not established. read the letter →

arxiv 2505.22909 v1 pith:NIPP4REF submitted 2025-05-28 econ.GN cs.AIcs.GTq-fin.EC

Cristian Chica , Yinglong Guo , Gilad Lerman This is my paper

classification econ.GNcs.AIcs.GTq-fin.EC MSC 91A2091A2691B26

keywords StochasticGamesBoundedMemoryQ-LearningCollusionSupracompetitivePricingRepeatedGrimTriggerStrategiesAlgorithmic

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Simulation studies have shown that $Q$-learning agents can drift into charging above-competitive prices, but no theory explained this in infinite repeated games. This paper aims to supply such a theory using stochastic games with bounded memory. Firms explore with a softmax rule for a finite horizon $T$ and then switch permanently to choosing the price with the highest estimated value. The central result is Theorem 4: if at the end of exploration the collusive price $p_C$ has strictly the largest $Q$-value at the two relevant states, and if each firm's one-period profit at $p_C$ is at least the discounted value of any other action, then every firm chooses $p_C$ at every later period from every initial price profile. If true, the result gives a rigorous explanation of algorithmic collusion without coordination or equilibrium computation, together with closed-form limiting $Q$-values and equilibrium support by punishment strategies.

What carries the argument

The load-bearing mechanism is $Q$-learning with bounded experimentation: until period $T-1$ firms randomize among prices with a softmax rule, and from period $T$ onward they switch permanently to the greedy argmax of their learned $Q$-function. What makes the argument work is a self-sustaining gap: condition (ii) of Theorem 4 converts the strict ranking at time $T$ into an invariant inequality, so the state-action pair $(p_C,p_C)$ is the only one updated after $T$, and the $Q$-values there follow a telescoping product whose limit is $\alpha(\delta_i)\pi_i(p_C)$. For the equilibrium part, the paper defines a Bellman-style operator $V_1$ on one-memory policies whose fixed points are subgame perfect values; Algorithm 1 verifies a candidate profile by solving a linear system, checking a maximization, and checking the initial-period condition.

What would settle it

Run Algorithm 3 on a two-firm repeated Bertrand game for a grid of horizons, learning rates, and discount factors, and check at time $T$ whether both inequalities of Theorem 4 hold on each sample path; if collusive pricing appears on paths where the inequalities fail, the theorem's sufficient conditions are not the operative mechanism. Separately, compute $\alpha(\delta_i)$ from the telescoping sum in Assumption 4 for any divergent schedule: the tail product vanishes, so $\alpha(\delta_i)(1-\delta_i)=1$, which means no learning-rate schedule can satisfy the strict inequality on which Propositions 5 through 7 rely.

Watch

Extended reading notes

Core claim

The paper claims that in an infinite repeated game with a one-stage Nash equilibrium price $p^*$ and a strictly more profitable collusive-enabling price $p_C$, $Q$-learning with bounded experimentation can make supracompetitive pricing the stable long-run outcome. The proof turns on two checks at the moment exploration stops: for each firm and every price $p$ other than $p_C$, the $Q$-value of $p_C$ is strictly larger at the last period's price state and at the collusive state, and the one-period profit $\pi_i(p_C)$ is at least $(1-\delta_i)Q_T(p_C,p)$. Once these hold, the greedy update preserves the gap and every firm chooses $p_C$ for all $t \geq T$, with the limiting $Q$-function given in closed form in equation (28). The paper further claims the learned strategies can take the form of naive collusion, grim trigger, or increasing strategies, and that among these naive collusion is an SPE only when $p_C$ is itself a one-stage Nash equilibrium, whereas grim trigger can be.

Load-bearing premise

The load-bearing premise is that the softmax exploration phase ends with $Q$-values that already rank the collusive price strictly above every other price at the two relevant historical states, and that the one-period collusive profit is large enough relative to the discounted $Q$-values of deviation; the paper assumes this rather than deriving it from the learning rates or horizon.

Editorial extensions

If this is right

If Theorem 4's inequalities hold, supracompetitive pricing is the unique long-run outcome of the learning dynamics from every starting price profile, so algorithmic collusion is not dependent on initial conditions.
At the collusive state the limiting $Q$-value is $\alpha(\delta_i)\pi_i(p_C)$, which under the paper's example learning rates equals the discounted value of permanent grim-trigger collusion, meaning the learned high price has a punishment-backed value.
Grim trigger policies can be verified as one-memory subgame perfect equilibria using the linear-system check of Algorithm 1, so credible punishment threats are compatible with decentralized $Q$-learning.
In standard Bertrand and two-sided-market games where $p_C$ is not a one-stage Nash equilibrium, naive collusion cannot be an SPE; the theory predicts observed collusion is enforced by reward-and-punishment structures rather than by unconditional high pricing.
The SPE existence and verification results apply to general stochastic games, extending the same analysis beyond repeated games to markets with persistent demand or cost states.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The theorem is conditional on the $Q$-values at time $T$ already ranking $p_C$ first at two states; the paper does not prove that any horizon or temperature produces this, so a natural next step is a probabilistic bound on softmax exploration reaching that configuration.
Telescoping the sum in Assumption 4 forces $\alpha(\delta_i)=1/(1-\delta_i)$ for any divergent learning-rate schedule, so the strict condition $\alpha(\delta_i)(1-\delta_i)>1$ used in Propositions 5 through 7 cannot hold; the paper's own Appendix A.9 example is the general case rather than a special construction, leaving those three support results with no instances under the paper's assumptions.
Because only two states are constrained at time $T$, the same proof strategy should certify other bounded-memory punishment schemes that preserve the $Q$-gap on the states visited, such as finite-horizon punishment followed by re-escalation to $p_C$.
An empirical check on a Bertrand simulation is straightforward: record whether the two Theorem 4 inequalities hold during the exploration phase; if collusion emerges reliably without them, the conditions are sufficient but not necessary.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Here's the short version: the paper contains one solid conditional convergence theorem for Q-learning in infinite repeated games, but its three supporting propositions are vacuous because they assume α(δ_i)(1−δ_i) > 1, and the paper's own Assumption 4 forces α(δ_i) = 1/(1−δ_i). I checked the telescoping: (1−δ_i)S_t = 1−Π_{l=T+1}^{t}(1−α_l(1−δ_i)) → 1 when Σα_t diverges. The paper's own example in Section 4.3 confirms this. So Propositions 5–7 have empty hypotheses. That kills the headline characterizations of learned collusion as naive, grim-trigger, or increasing.

What is actually valuable: Theorem 4 is a genuine discrete-time result, not an ODE approximation, with a closed-form limit for the Q-function. Given its explicit conditions on Q_T, the proof is correct. The one-memory SPE theory (Theorems 1–3) is a careful reworking of Fink's fixed-point argument and appears sound. Proposition 2 (grim trigger as SPE) is standard but correctly verified in this framework. So the paper is not a waste; it has a working core.

The soft spots are proportionate to the vacuity of the support results. The paper's first-page claim—that it provides the first theoretical explanation for supracompetitive pricing by Q-learning—does not follow from Theorem 4, because Theorem 4 is conditional on an unobserved internal Q-function at the end of experimentation. No argument shows that softmax exploration produces a Q_T satisfying the inequalities. So the paper proves an invariance result, not a statement about the learning process per se. That is a serious gap, though not a circularity. The fixed-point theory does not rescue the Q-learning collusion claim.

Who should read this: anyone working on algorithmic collusion theory will want to know the discrete-time convergence result, but they should not cite the support propositions as established. It deserves a serious referee, because the error is subtle and a revision might fix the framing by removing Propositions 5–7 or reworking the learning-rate assumption. My recommendation: reject in current form, but invite resubmission with the vacuous results removed and the gap between experimentation and the Q_T conditions addressed.

Referee Report

3 major / 3 minor

Summary. The paper develops a one-memory stochastic-game framework, proves existence of one-memory subgame perfect equilibria by rewriting Fink's fixed-point argument, and then studies Q-learning with bounded experimentation. Its main theorem (Theorem 4) gives sufficient conditions on the Q-function at the end of experimentation under which firms charge the collusive-enabling price forever, together with a characterization of the limiting Q-function. Propositions 5-7 claim that the induced limiting strategy is naive collusion, grim trigger collusion, or an increasing strategy, and the abstract presents the result as the first theoretical explanation of collusion by Q-learning agents in infinite repeated games.

Significance. The one-memory SPE existence results (Theorems 1-3 and Proposition 2) are a careful formal extension of Fink (1964), and Proposition 3's identification of fixed-point Q-values with conditional value functions under induced policies is a useful observation. However, the paper's distinctive claim that Q-learning agents learn supracompetitive prices is not established. The support theorems rest on an impossible inequality, and Theorem 4 is a conditional certificate rather than a convergence result, with no reachability analysis for its key premise. If the paper were limited to the conditional theorem and the one-memory SPE theory, it would be a sound but modest contribution; as written, its central advertised result is unsupported.

major comments (3)

[This concerns Section 4.2, Assumption 4 and Propositions 5-7.] The hypotheses of Propositions 5, 6, and 7 are empty. Under Assumption 4(ii), with β_l := 1−α_l(1−δ_i), the partial sums S_t := Σ_{k=T+1}^t (Π_{l=k+1}^t β_l)α_k satisfy the telescoping identity (1−δ_i)S_t = 1−Π_{l=T+1}^t β_l. Since Σ_{t=T}^∞ α_t = ∞ and 0<α_t<1, the product tends to zero, so α(δ_i)=1/(1−δ_i) for every admissible learning-rate sequence. Hence α(δ_i)(1−δ_i)=1, and the strict inequality α(δ_i)(1−δ_i)>1 assumed in each of the three propositions can never hold. The sequence constructed in Section 4.3 and Appendix A.9 confirms the identity (equation (31)). The characterizations of naive collusion, grim trigger collusion, and increasing strategies are therefore vacuous, and the paper's answer to its Question (ii) is unsupported.
[This concerns Section 4.2, Theorem 4 and Algorithm 3.] Theorem 4 is a conditional statement about an unobserved internal quantity Q_T, and the paper does not show that the softmax experimentation phase of Algorithm 3 can produce a Q_T satisfying inequalities (i)-(ii) from any model primitives. No assumptions on the temperature schedule β_t, the experimentation horizon T, the profit functions, or the discount factors are given that would imply these inequalities, and no probabilistic bound on the event that they hold is provided. Consequently the theorem does not establish that Q-learning agents learn supracompetitive pricing; at most it describes an invariance property of states that already satisfy the inequalities. Given the abstract's claim to provide 'the first theoretical explanation' of the experimental observations, this reachability gap is load-bearing.
[This concerns Section 4.2, Theorem 4, regarding the role of p_{T−1}.] The theorem's conclusion quantifies over all initial price profiles and all t≥T, but its condition (i) is stated only for the single state s=p_{T−1}, where p_{T−1} is itself a random outcome of the experimentation phase. For the conclusion to follow for every initial p_0 and every realized path, condition (i) would need to hold for all states in A^n that are reachable from any p_0 under Algorithm 3. The statement and proof do not address this; they treat p_{T−1} as fixed while drawing a 'for any initial price profile' conclusion.

minor comments (3)

[This concerns Section 4.2, proof of Lemma 1, base case.] The sentence 'In view of what we proved and Assumption 3-(i), (s_T,p^i_T)=(p_{T−1},pC)' refers to Assumption 3, which is not assumed in Theorem 4; it should refer to condition (i) of Theorem 4.
[This concerns Appendix A.9, Case 3.] The expression 'Q_i^{ϵ→0}(p_{T−1},pC)' appears to be a typo; it should presumably read 'Q_i^*(p_{T−1},pC)' or 'Q_i^T(p_{T−1},pC)'.
[This concerns Section 4.3, discussion of Assumption 4.] The discussion says the example sequence 'satisfies Assumption 4' and gives α(δ_i)=1/(1−δ_i), but this is not a special feature of the example: as shown above, every sequence satisfying Assumption 4 has this property, so the example should not be presented as illustrating a nontrivial choice of α(δ_i).

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the main Q-learning theorem is conditional on assumed Q_T inequalities and is not a fitted-input prediction; Propositions 5–7 have an internally inconsistent extra hypothesis, but vacuity is a correctness defect, not circularity.

full rationale

The paper's central derivation chain is not circular. Theorem 4 assumes explicit inequalities on the Q-function at the end of experimentation, (i) Q_i^T(s,pC)>Q_i^T(s,p) and (ii) pi_i(pC) >= (1-delta_i)Q_i^T(pC,p), and then proves by induction in Lemma 1 that pC is chosen forever and that the limiting Q-function satisfies equation (28). These assumptions are not defined in terms of the conclusion; they are conditions on an unmodeled internal state Q_T, and the limits in (28) follow from the learning-rate telescoping in Assumption 4 rather than from the target statement. There is no parameter fitted to observable outcomes and then renamed as a prediction. The one-memory SPE existence theory (Theorems 1–3) is a self-contained rewriting of Fink's proof, and the self-citations to Chica et al. (2024, 2025) are used only for motivation or illustrative models, not as load-bearing evidence. The skeptic's substantive objection is correct but is not circularity: Assumption 4(ii), combined with sum alpha_t=infinity, forces alpha(delta_i)=1/(1-delta_i) by the telescoping identity (1-delta_i)S_t = 1 - product of (1-alpha_l(1-delta_i)), so the extra hypothesis alpha(delta_i)(1-delta_i)>1 in Propositions 5–7 is impossible and those propositions are vacuous. An empty hypothesis is a serious mathematical weakness, but it does not make the theorem's conclusion equivalent to its premises or reduce a prediction to a fit. Overall, the derivation is conditional and incomplete, not circular.

Assumptions & free parameters 2 free parameters · 7 assumptions · 0 invented entities

The central claim rests on the one-memory policy restriction, the existence of a collusive-enabling price, and especially on unproven conditions about the Q-function at the end of experimentation. No new physical or economic entity is introduced.

free parameters (2)

Experimentation horizon T
Algorithm design parameter; theorem is stated for any T>0, so not fitted to data.
Softmax temperature schedule β_t
Part of Algorithm 3, not specified beyond being positive; the Q_T conditions implicitly depend on it.

assumptions (7)

domain assumption Assumption 1: firms use one-memory policies that are time-invariant after t=0.
Restricts strategy space to one-memory policies; stated in Section 2.
domain assumption Assumption 2: |S|=1 (repeated game) and existence of one-stage NE p* and collusive-enabling pC with π(pC)>π(p*).
Reduces the stochastic game to a repeated game; used throughout Section 4.
domain assumption Assumption 3: discount factors satisfy (πm,i−π_i(pC))/(πm,i−π_i(p*)) ≤ δ_i < 1.
Lower bound on patience for grim trigger SPE; used in Proposition 2 and 6.
ad hoc to paper Assumption 4: learning rates satisfy 0<α_t<1, sum α_t = ∞, and the limit α(δ_i) exists in (0,∞).
Part (ii) is nonstandard; the paper does not motivate it from standard Q-learning convergence theory. In fact, part (i) already forces α(δ_i)=1/(1−δ_i).
domain assumption Assumption 5: existence of a price ladder p* = p0 < p1 < ... < pk+1 = pC with certain Q_T ranking conditions.
Imposes a monotone price path; used only in Proposition 7.
ad hoc to paper Conditions (i) and (ii) of Theorem 4 on the Q-function at time T.
These are assumptions on the algorithm's internal state, not derived from game primitives. The paper gives no guarantee that softmax exploration reaches such a state.
standard math Fink's fixed-point theorem, Kakutani's fixed-point theorem, Gershgorin circle theorem.
Background results used for existence of one-memory SPEs and uniqueness of value functions.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Learning to Charge More: A Theoretical Study of Collusion by Q-Learning Agents." pith.science (2026). https://pith.science/paper/NIPP4REF

@misc{pith2026250522909,
  author       = {Pith},
  title        = {Pith review of: Learning to Charge More: A Theoretical Study of Collusion by Q-Learning Agents},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/NIPP4REF}},
  note         = {Machine review of arXiv:2505.22909}
}

abstract

There is growing experimental evidence that $Q$-learning agents may learn to charge supracompetitive prices. We provide the first theoretical explanation for this behavior in infinite repeated games. Firms update their pricing policies based solely on observed profits, without computing equilibrium strategies. We show that when the game admits both a one-stage Nash equilibrium price and a collusive-enabling price, and when the $Q$-function satisfies certain inequalities at the end of experimentation, firms learn to consistently charge supracompetitive prices. We introduce a new class of one-memory subgame perfect equilibria (SPEs) and provide conditions under which learned behavior is supported by naive collusion, grim trigger policies, or increasing strategies. Naive collusion does not constitute an SPE unless the collusive-enabling price is a one-stage Nash equilibrium, whereas grim trigger policies can.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

26 extracted references · 25 canonical work pages

[1]

Assad, S., Clark, R., Ershov, D., and Xu, L. (2024). Algorithmic pricing and competition: Empirical evidence from the German retail gasoline market. Journal of Political Economy, 132(3):000–000. (Cited in page

work page 2024
[3]

Aumann, R. J. and Sorin, S. (1989). Cooperation and bounded recall. Games and Economic Behavior, 1(1):5–39. (Cited in page 2,

work page 1989
[4]

Barlo, M., Carmona, G., and Sabourian, H. (2009). Repeated games with one-memory.Journal of Economic Theory, 144(1):312–336. (Cited in page 2, 3,

work page 2009
[5]

Barlo, M., Carmona, G., and Sabourian, H. (2016). Bounded memory Folk theorem. Journal of economic theory, 163:728–774. (Cited in page

work page 2016
[6]

Bhatia, R. (2013). Matrix analysis, volume

work page 2013
[7]

Calvano, E., Calzolari, G., Denicolo, V ., and Pastorello, S. (2020). Artificial intelligence, algorithmic pricing, and collusion. American Economic Review, 110(10):3267–97. (Cited in page 1, 3, 13, 15,

work page 2020
[9]

Chica, C., Guo, Y ., and Lerman, G. (2025). Competition and collusion in two-sided markets with an outside option. arXiv preprint arXiv:2505.06109. (Cited in page 2, 10, 15,

work page Pith review arXiv 2025
[10]

Jaakkola, T., Jordan, M., and Singh, S. (1993). Convergence of stochastic iterative dynamic programming algorithms. Advances in neural information processing systems,

work page 1993

Show all 26 references

[11]

and Tirole, J

Fudenberg, D. and Tirole, J. (1991). Game Theory. MIT Press. (Cited in page

1991
[12]

Friedman, J. W. (1985). Cooperative equilibria in finite horizon noncooperative supergames. Journal of Economic Theory, 35(2):390–398. (Cited in page

1985
[14]

and Wellman, M

Hu, J. and Wellman, M. P. (2003). Nash Q-learning for general-sum stochastic games.Journal of machine learning research, 4(Nov):1039–1069. (Cited in page 3,

2003
[15]

Fink, A. M. (1964). Equilibrium in a stochastic n-person game. Journal of Science of the Hiroshima University, Series A-I (Mathematics), 28(1):89 –

1964
[16]

Chica, C., Guo, Y ., and Lerman, G. (2024). Artificial intelligence and algorithmic price col- lusion in two-sided markets. arXiv preprint arXiv:2407.04088 . (Cited in page 3, 13, 15,

2024 arXiv
[17]

Dewenter, R., Haucap, J., and Wenzel, T. (2011). Semi-collusion in media markets. Interna- tional Review of Law and Economics, 31(2):92–98. (Cited in page 2, 10,

2011
[18]

36 Klein, T. (2021). Autonomous algorithmic collusion: Q-learning under sequential pricing. The RAND Journal of Economics, 52(3):538–558. (Cited in page 3, 13,

2021
[19]

Lehrer, E. (1988). Repeated games with stationary bounded recall strategies. Journal of Eco- nomic Theory, 46(1):130–144. (Cited in page 2,

1988
[20]

Nash, J. F. (1950). Equilibrium points in n-person games.Proceedings of the national academy of sciences, 36(1):48–49. (Cited in page 10,

1950
[21]

Algorithms and collusion: Competition policy in the digital age

OECD (2017). Algorithms and collusion: Competition policy in the digital age. Technical Report. (Cited in page

2017
[22]

Ok, E. A. (2007). Real analysis with economic applications, volume

2007
[23]

Possnig, C. (2023). Reinforcement learning and collusion. Department of Economics, Univer- sity of Waterloo. (Cited in page

2023
[24]

Rubinstein, A. (1986). Finite automata play the repeated prisoner’s dilemma. Journal of Eco- nomic Theory, 39(1):83–96. (Cited in page 2,

1986
[25]

Tirole, J. (1988). The theory of industrial organization. MIT press. (Cited in page 2, 10,

1988
[26]

and Kaymak, U

Waltman, L. and Kaymak, U. (2008). Q-learning agents in a cournot oligopoly model. Journal of Economic Dynamics and Control, 32(10):3275–3293. (Cited in page

2008
[27]

Watkins, C. J. and Dayan, P. (1992). Q-learning. Machine learning, 8(3):279–292. (Cited in page 3, 11,

1992
[31]

Brown, Z. Y . and MacKay, A. (2023). Competition in pricing algorithms.American Economic Journal: Microeconomics, 15(2):109–156. (Cited in page

2023
[32]

Osborne, M. J. (1994). A course in game theory. MIT Press. (Cited in page

1994

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.

[1] [1]

Assad, S., Clark, R., Ershov, D., and Xu, L. (2024). Algorithmic pricing and competition: Empirical evidence from the German retail gasoline market. Journal of Political Economy, 132(3):000–000. (Cited in page

work page 2024

[2] [3]

Aumann, R. J. and Sorin, S. (1989). Cooperation and bounded recall. Games and Economic Behavior, 1(1):5–39. (Cited in page 2,

work page 1989

[3] [4]

Barlo, M., Carmona, G., and Sabourian, H. (2009). Repeated games with one-memory.Journal of Economic Theory, 144(1):312–336. (Cited in page 2, 3,

work page 2009

[4] [5]

Barlo, M., Carmona, G., and Sabourian, H. (2016). Bounded memory Folk theorem. Journal of economic theory, 163:728–774. (Cited in page

work page 2016

[5] [6]

Bhatia, R. (2013). Matrix analysis, volume

work page 2013

[6] [7]

Calvano, E., Calzolari, G., Denicolo, V ., and Pastorello, S. (2020). Artificial intelligence, algorithmic pricing, and collusion. American Economic Review, 110(10):3267–97. (Cited in page 1, 3, 13, 15,

work page 2020

[7] [9]

Chica, C., Guo, Y ., and Lerman, G. (2025). Competition and collusion in two-sided markets with an outside option. arXiv preprint arXiv:2505.06109. (Cited in page 2, 10, 15,

work page Pith review arXiv 2025

[8] [10]

Jaakkola, T., Jordan, M., and Singh, S. (1993). Convergence of stochastic iterative dynamic programming algorithms. Advances in neural information processing systems,

work page 1993