Self-Play $Q$-Learners Can Provably Collude in the Iterated Prisoner's Dilemma
Authors: Quentin Bertrand
Juan Agustin Duque
Emilio Calvano
Gauthier Gidel
Venue: ICML 2025 poster (2025)
Keywords: iterated prisoner's dilemma
cooperation
Q-learning
self-play
Primary area: theory->game_theory
TL;DR: We show that self-play Q-learners can learn to collude, even if their inital states and policies are always defect

Abstract: A growing body of computational studies shows that simple machine learning agents converge to cooperative behaviors in social dilemmas, such as collusive price-setting in oligopoly markets, raising questions about what drives this outcome. In this work, we provide theoretical foundations for this phenomenon in the context of self-play multi-agent Q-learners in the iterated prisoner’s dilemma. We characterize broad conditions under which such agents provably learn the cooperative Pavlov (win-stay, lose-shift) policy rather than the Pareto-dominated “always defect” policy. We validate our theoretical results through additional experiments, demonstrating their robustness across a broader class of deep learning algorithms.

Self-Play Q-Learners Can Provably Collude in the Iterated Prisoner's Dilemma
Quentin Bertrand Juan Agustin Duque?
Emilio Calvano Gauthier Gidel 24
Abstract
on simulated environments and empiri- cal analyses of real-world pricing- have shown that algorith- mic collusion is a tangible risk, not merely a theoretical con- cemn For instance, Deneckere & Davidson (1985); Waltman & Kaymak (2008); Hansen et al. )) Asker et al. (2022) document that even simple algorithms can lead to higher prices in standard models of price competition. Moreover, Calvano al. (2019; 2020b); Klein (2021) demonstrate that standard machine learning algorithms, such as Q-learning (Watkins & Dayan, 1992), can learn to sustain high prices through soward-uunishmen mechanisms- -patters com- monly characterized as 'collusive' in the antitrust literature; see Calvano et al. 2020a for an in-depth discussion of re- lated policy issues. Assad et al. (2024) go one step further by providing the first empirical evidence of how algorith- mic pricing affects competition: in Germany's 's retail gaso- line market, where machine learning pricing tools spread after 2017, adoption increased profit margins only when multiple competitors used them-consistent with concerns over algorithm- driven collusion. More broadly, cooperation among machine learning algorithms has also been observed in general iterated social dilemmas, owing to the sequential nature of the problems (Lanctot et al., 2017: Leibo et al., 2017).
Prior
A growing body of computational studies shows that simple machine learning agents converge cooperative behaviors in social dilemmas, such as collusive price-setting in oligopoly markets, raising questions about what drives this outcome. In this work, we provide theoretical foundations for this phenomenon in the context of self-play multi-agent Q-learners in the iterated prisoner's s dilemma. We characterize broad conditions under which such agents provably learn the cooperative Pavlov (win-stay, lose-shift) policy rather than the Pareto-dominated "always defect" policy. We val- idate our theoretical results through additional ex- periments, demonstrating their robustness across broader class of deep learning algorithms.
1. Introduction
In recent years, algorithmic pricing has increasingly sup- planted manual pricing, both online-by 2015, one-third of Amazon's 's largest third-party sellers were already using such tools (Chen et al., 2016)-and physical markets, such as gas stations (Schechner, 2017). The growing adoption of machine learning-based pricing systems has raised signifi- cant concerns in both academic (Ezrachi & Stucke, 2015; Mehra, 2015) and institutional (OECD, 2017; Bureau, 2018) circles regarding the potential for tacit collusion. Indeed, if multiple firms competing within the same local market de- ploy learning algorithms to set prices, a natural and pressing question arises:
Theoretically, the emergence of tacit collusion has been studied in highly simplified settings. Even in minimalist co- operative/competiivee games such as the prisoner's 's dilemma (Flood, 1958; Kendall et al., 2007), the dynamics induced by standard machine learning algorithms in multi-agent con- texts are often complex that researchers typically resort to oversimplified versions of these algorithms. In particular, expected-vales formulations of c-greedy Q Q-learning (Seijen et al., 2009; Sutton & Barto, 2018, Sec. 6. 6.10), without memory- that is, without access to previous states- are frequently analyzed (Banchio & Skrzypacz, 2022; Banchio & Mantegazza, 2022). In these prior theoretical results, cooperation does not arise from agents learning equilibrium strategies in the classical game-theoretic sense. Their limited memory prevents them from conditioning on the past actions of others, and thus from learning to implement retaliatory pricing strategies (Calvano et al., 2023). By contrast, learning to sustain high prices through retaliation consistent with a subgame- -erffect equilibrium represents a stronger and more strategic form of cooperation: it captures
Could pricing algorithms autonomously learn to suppress competition, thereby leading to higher prices?
'Equal contribution 'Université Jean Monnet Saint-Etiemne, CNRS, Institut d' d'Optique Graduate School, Inria, Laboratoire Hubert Curien UMR 5516. F-42023, Saint-Etienne, France "Mila, Université de Montréal 'Università LUISS (Rome), Toulouse School of Economics, EIEF and CEPR *Canada AI CIFAR Chair. Correspondence to: Quentin Bertrand mquentin.bertrane @inria.fr..
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Self-play Q-Learners Can Provably Collude in the Iterated Prisoner's Dilemma
equilibrium behavior that is robust unilateral deviations uunlike the limited- memory scenarios, where cooperation can emerge without credible deterrence mechanisms.
Table I. Prisoner's Dilemma Rewards/Payoff Matrix. Typical iter- ated prisoner's is dilemma rewards satisfy rDe > rec > FDD > rCD and 2rec > TCD + TDC.
In this paper, we aim to fill this gap by studying a richer setting that, in principle, allows for collusion in the game- theoretic sense. More precisely, the proposed project seeks to shed light on the learning dynamics of algorithms as they coordinate cooperate-in in contrast to the learning out- comes, which have been the primary focus of prior work. By analyzing the processes that lead to collusion in a mini- malist self-play setting- i.e., where an agent interacts with a copy of itself-we aim to better inform the development of rules and regulations that ensure fair competition and protect consumer interests.
Cooperate
Defect
TCC
TDC
Cooperate
TCC
TCD
TCD
FDD
Defect
DDC
rDD
equation and e-greedy Q-learning. In Section 2.3, we recall the fixed-point policies of the multi-agent Bellman equa- tion: always defect, Lose-ste shift, Pavlov (sum- marized in Table 2). Interestingly, in the iterated prisoner's dilemma, these policies are also subgame perfect equilib- rium, and might be different from al waws defect.
Contributions. In this work, we study the dynamics of two agents playing the iterated prisoner's dilemma and choos- ing their actions according to self-play e-greddy Q-learning policies. Importantly, as opposed to previous work (Banchio & Skrzypacz, 2022; Banchio & Mantegazza, 2022), we the- oretically study the standard stochastic (i.e., not averaged) version of self-play e-greedy Q-learning (Algorithm 1), with a one-step memory. More precisely,
2.1. Iterated Prisoner's Dilemma
In this work, we consider a two-player iterated prisoner's dilemma whose players have one-step memory. At each time step, players choose between cooperate (C) or defect (D), i.e., each player é choose an action a' E AA é ( (C, which yields a reward ri ,a for player i, E (1,2). Ta-
First, we show that without exploration, i.e., self-play e-greedy Q-learning with = 0, if the initialization of the agent is optimistic enough (Even-Dar & Mansour, 2001), then agents can learn to move from an always defect policy, to a cooperative policy (Theorem 3.2 in Section 3.1), referred to as win-stay, lose-shift policy (Nowak & Sigmund, 1993).
ble 1 describes the rewards r2 .a= and r²",a" respectively obtained by each player depending on their respective ac- tion a and a². Note that such a game is symmetric: re at,a² = r at == Tat,a2. For simplicity, in the experi- ments (Section 5), we consider simplified rewards, which are parameterized by single scalar g. 1 < 9 < 2 (see Table 3 in Appendix E, as in Banchio & Mantegazza 2022).
Then, we extend the convergence toward cooperative policy to self-play e-greedy Q-learning with > 0 (Theorem 3.3 in Section 3.2). This is the main technical difficulty, as one needs to prove the convergence of a stochastic process toward a specific equilibrium.
Finally, we empirically show that the collusion proved for standard Q-learning algorithms is also observed for deep Q-learning algorithms (Section 5).
When the prisoner's dilemma is not repeated, joint defec- tion is the only Nash equilibrium: for a fixed decision of the other prisoner, defecting always reaches better rewards than cooperating. This yields the celebrated paradox: even though the rewards obtained in the "defeet defect" state are Pareto dominated by the ones obtained with the "cooperate cooperate" state, the Pareto pureto-suboptimal mutual defection remains the only Nash equilibrium.
The manuscript is organized as follows: recalls on the prisoner's 's dilemma, multi-agent Q-learning, and fixed points of the self-play multi-agent Bellman equation. Section 3 contains our main results: the conver- gence of Q-learning toward the collusive Pavlov strategy (Theorems 3.2 and 3.3). Previous related works on detailed in Section 4. Similar collusive behaviors are also observed for deep Q-learning algorithms in Section 5.
Section 2 provides
the dynamics of multi-agent Q-learning
When the prisoner's dilemma is infinitely repeated, new equilibria can emerge, and a always defect no longer the dominant strategy (Osborne, 2004). We will refer to "collusive" "colluding" strategies, any strategy that differs from the a always defect strategy. Note that infinitely many time steps are essential for such equilibria to exist'.
2. Setting and Background
First, Section 2.1 provides recalls on the iterated prisoner's dilemma. Then, Section 2.2 provides recalls on reinforce- ment learning, and more specifically, multi-agent Bellman
Equivalently, one can consider that the game is finitely repeated with a probability of ending equal to the discount factor at each step (Littman, 1994; Oshorne, 2004, Chap. 15.3).
2

---

Self-play Q-Learners Can Provably Collude in the Iterated Prisoner's Dilemma
Algorithm 1 Multi-agent Self-Play Q-learning
learning applications (Lowe al., 2017; Silver et al., 2018; Baker al., 2019; Tang, 2019):
init :50. Q
param :a, y for l in 1 ,.... Riter do // Compute af and of via Algorithm 2 df = Algorithm 2(Q, (a) (())
2 ~ x-11%) // same Q-table for a and dz- ( oz In the self-play setting, the Bellman Equation (2) writes
a = Algorithm
8: (at-1: 1)
Cn Eagra((lez) (Tat + +2 max Faat
(4)
// Update the Q-value entry in st
Q a += (Fot.et + max, aat.a))) Quiat)
In addition, we study e-greedy Q-learning policies (Algo- rithm 2, < < 1/2), i.e.
return Q
2.2. Q-Learning for Multi-Agent Reinforcement Learning and Self-Play
1 1-c if arg max, Qs,a . {1,2),
T(als) =
clse
Reinforcement learning. At given step, the choice of each player to cooperate or defect is conditioned by the actions S & {CC, DD, CD,DC) played at the previous time step, where the first action stands for the action picked by the first player at the previous time-step. A denotes the space of policies
We say that e-greedy policy is a fixed point of the self- play multi-agent Bellman Equation (4) if the policy is greedy with respect to its own Q-values. In other words, a fixed point Q' of the self-play multi-agent Bellman Equation (4) must satisfy Equation (4), where the policy т is e-greedy with respect to the Q-table Q" Interestingly, in this setting, there exist multiple fixed-point policies Q* of the self-play multi-agent Bellman Equation (4).
S x A [0, 1], such that for all E S. EEEA (als) = 1. Given two policies (i.e., mixed strategies) TT, T2 E A discount factor E (0, 1), and an initial distribution over the state space S, the cumulated reward observed by the agent E {1,2} is given by
In this paper, we study the dynamics of the multi-agent self-play Q-learming (Equation (3)) in the one-step memory case, i.e., A = (C,D) and S = [C, In particular, in Section we show convergence towards a specific cooperative fixed point policy Q* of the multi-agent Bellman Equation (4). In the following Section 2.3, provide recalls the fixed-point policies for the multi-agent Bellman equation Equation (4).
J(( T2) & E somp,t
y r'rat att
(1)
Q-learning. popular approach to maximize the cumula- tive reward function Equation (I) is to find action-value function Q-function, that is fixed point of the Bellman operator (Sutton& & Barto, 2018, Eq. 3.17). Since the reward of the second player is stochastic in the multi-agent case, the fixed-point equation writes, for all (se, at) E x A:
2.3. Fixed Points of the Multi-Agent Bellman Equation
In the iterated prisoner's dilemma with one-step memory, multiple symmetric strategy profiles exist. However, only three of them are fixed points of the self-play multi-agent Bellman operator in Equation (4): always dect,t Pavlov, and grim trigger (Usui Ueda, 2021). summary of these policies provided in Table 2.
= -Eo==aaaaaa (ro..e2 + max (7sta2))0)) (2)
Q-learning (Algorithm 1) consists of stochastic fixed-point iterations on the Bellman Equation (4); with a step-size
In Section 3, we show that one can transition from always defect to Pavlov, passing through the lose-shi ft policy (defined in Table 2). First, we recall below that fixed-point policies of the multi-agent Bellman Equation (4) can define always defect and Pavlov.
e = -
+ a (rd..e8 + max Q (at,a)) Qi Pon.ot)
(3)
Proposition 2.1 (Always Defect). The following Q- table Q Defoct is a fixed point of the Bellman Equation (4) and yields an always defect policy, Vs E {C, ()²
Self-play. Since the game is symmetric, dynamic of Equation (3), where the second agent is a copy of the first agent, i.e., the actions af and af are sampled according to the same policy т. Such a way to model the opponent is referred to as self-play and has been successfully used train agents in deep reinforcement
study the
Q
Defect =
t Defect = Defect ((Zwa(()))) (rD,02 - rC,02)
s,C
3

---

Self-play Q-Learners Can Provably Collude in the Iterated Prisoner's Dilemma
Algorithm 2 e-greedy
Table 2. Summary of the symmetric fixed-point policies of the self- play multi-agent Bellman Equation (4). The table displays the greedy action o, each policy, given the state 32 (ai oz
input s, 0 e 1/2 return argmax, Qs,a' with probability e and arg ming Qs,a' with probability
State St
(D,D) (C, (C, (D,
Fixed Print
Policy
Always defect Lose-shift
D
D
D
D
V
More interestingly, the cooperative Pavlov ov policy (also referred as win-stay, sase-shift) can also be fixed point of the multi-agent Bellman Equation (4). Pavlov can be summarized as cooperate as long the players are synchronized by playing the same action.
C
D
D
D
X
Grim trigger Pavlov
D
C
D
D
V
C
C
D
D
3. Q-Learning Dynamic in the Iterated Prisoner's Dilemma
roc-ree and e is small enough, then there exists a Q-function, Qr.Paooov which is a fixed point of the self-play multi-agent Bellman Equation (4) and yields the Pavlov policy, i.e,
Proposition 2.2 (Pavlov). If
ree-FDD
The complex structure of the multi-agent Q-learning with memory yields multiple fixed-poin policies for the Bell- man Equation (4). In this section, for specific set of Q-value initializations Q", we show convergence of the dy- namics resulting from e-greedy Q-learning with memory updates (i.e., Equation (3)) toward the cooperative fixed point Pavlov policy.
vs e DCC
Pavlov > Q Que
Pavlov
and
ss E {CD,
Q Pawlov Q Q
Pavlov
More precisely, we show that, with "optimistic enough" initialization, the e-greedy policy with small enough learn- ing rate a starts from the al ways defect policy, then moves to the lose-aa sese--hiff ft policy, and finally converges towards the Pavlov policy. The Q-values at initialization are required to be "optimistic enough" in the sense that they are "set to large values, larger than their optimal values" (Even-Dar & Mansour, 2001).
Proofs of Propositions 2.1 and 2.2, the exact Q-values and condition are recalled in Appendices A.1 and A.2 for completeness. In the rest of the manuseript we assume that > "De-ree rec-ron and the exploration c is small enough such that Pavlov policy exists.
The main takeaway from Proposition 2.2 is that there exists fixed point of the self-play ageti Bellman Equa- tion (4) whose associated strategy is cooperative. Interest- ingly, the only other fixed-poin strategy is the (coopera- tive) grim tr trigger policy (Usui & Ueda 2021, Table I; Meylahn & Janssen 2022). On the opposite, tit-for-tat is not a fixed-point policy of the Bellman Equation (4). Ta- ble 2 summarizes the greedy action of each fixed-point pol- icy. Interestingly, always defect, Pavlov, and gr im trigger policies also subgame perfect equilibrium, which is stronger notion of equilibrium than Nash equilib- rium for iterated games (the subgame perfect definition can
For exposition purposes, the greedy case (e = 0 in Algo- rithm 2) is presented Section 3.1, and the general case (0 < 1/2) in Section 3.2.
3.1. Fully Greedy Policy with No Exploration (Algorithm with = 0)
We first show the case e = 0, i.e., with no exploration. We assume that the initial policy is always defect, and we require "optimistic enough" initial Q-values.
Assumption 3.1 (Q-values Initialization).
i) < (D.).. %
be found in Sec. 5.5 of Osborne 2004). For completeness, the proofs of the latter statement are recalled Appendix B.
ii O (.D)J.C
<
Iec
ree-Ton
< Pic.cr.c and
I-
1-7
to DDDDD
(
Propositions 2.1 and 2.2 illustrate challenges multi- agent reinforcement learning for the prisoner's dilemma: multiple equilibria exist that yield outcomes with markedly different levels of cooperation. Thus, one should not only care about convergence toward equilibrium, but one should also care about which type of equilibrium the agents con- verge to. The reached equilibrium will depend on the dy- namics the algorithm used to estimate the policy T": this dynamics studied in Section 3 for Q-learning.
m o (C.O)C
Assumption 3.1 ensures that the algorithm moves from al always defect to lose-shift policy. As- sumption 3.1 ii) ensure that the algorithm shifts from lose shi ft to Pavlov policy, and Assumption 3.1 iii) ensures that the policy sticks to Pavlov.
Q-values Initialization in Practice. How can we ensure

---

Self-play Q-Learners Can Provably Collude in the Iterated Prisoner's Dilemma
(D,D)
(C,C)
s (D,C)
Q.C - QxD
0.2
Always defect policy
Lose-shift policy
0.0
Pavlov policy
-0.2
to 0
11
12
0.5 # iterations
1.0
x102
Figure 1. From always defect to Pavlov policy, Algorithm with exploration (Ée., 0). Evolution of the Q-learning policy as a function the number of iterations in the iterated prisoner's 's dilemma. With a correct (optimistic) initialization, players go from always defect policy the fose-ahite policy (at time f1), and then go the cooperative Pavlov policy (at time fz). The incentive to cooperate and the discount factor are set to g = 1.8 (see Table 3) and 0.6.
that Assumptions 3.1 i) to 3.1 fii) are actually satisfied in practice? For standard Q-learning, the initial Q-values are user-defined parameters of the algorithm (see Algorithm 1). Figure 2 illustrates how the initial Q-values-specificcae Assumptions 3.1 i) and 3.1 ii) in-innfuence the resulting pol- icy. However, in more complex settings such deep Q- learning, the initial Q-values are not explicitly controlled, since they result from randomly initialized neural network weights. In such cases, initializing the weights to directly satisfy Assumption 1.1 is non-trivial.
updates Q(c.C).D and Q(D,D). entries, until Q(C.C),D goes below Q(c.C).c. From this moment, the dynamic changes, and agents start to play the Pavlov policy and do not change.
Proof. (Theorem 3.2) As illustrated in Figure 1, the tra- jectory can be decomposed in phases: first, the pol- iey goes from ways defect lose-shi ft policy (Phase 1). Then, the policy goes from lose-shie ft to Pavlov (Phase 2). Finally, the policy stays in the Pavlov policy (Phase 3).
To address this, we propose practical approach to approx- imate initialization toward an always defect policy, which subsequently shift toward cooperation. Specif- ically, suggest initializing the Q-values using the out- put of Algorithm 1 executed with exploration parameter = 1/2. This corresponds to a uniformly random policy: P(C |) = p(D s) = 1. Vs E {CC, DD, CD, DC). Under this initialization, the self-play multi-agent Bellman Equation (4) admits unique fixed-point policy, which cor- responds to the a always defect strategy.
From always defect to lose-shift (0 S 4)). Ao we have, 80 = DD, and for all [C, Q&DD Q,,0, hence the greedy action is defect, and is always chosen since = 0. Then, the Q-learning update Equation (3) writes
Phase
@D = Q(D.D),
+ (rDD 71ID.D), P(D.D)D) (5)
Theorem 3.2. Suppose the initial policy is a always defect and the initial state so is defect defect: So = DD. Then for all Q-values initializations Q' that satisfy Assumption 3.1, Algorithm I with no exploration 0) moves away from the a 1 wwass defect policy, and learn the cooperative Pavlov policy
Thus, while Q(D.D). > Q(D.D)C. Q(D,D), is the only updated entry and converges linearly towards Dofectt
(D.D), Defeet - a(l1)))) - (Q/D..) - ((DDefee)
= (1- =11
Figure 1 illustrates Theorem 3.2 and shows the evolution of Equation (4) as function of the number of iterations. t t= tu. Q..D Qs,c for all states (C, The greedy action is playing defect, Q(D.D).D C increases and agents progressively learn the lose-sh's ft policy. Once the Lose-shifi Et policy is learned, the greedy actions are "cooperate" when the state is DD and "defect" when the state is CC. Hence, this phase, Algorithm successively
& rD..D(1 Thus, since Q% (DD.).C > where (DDDD) Q+ o A rD.D/ 7) (Assumption 3.1 i)), Q(D,D).D converges linearly towards Q(D.D),D &.D.D..c Hence there exists t such that Q (.D.D.C = ( Q (DDD) Once this time t reached, the policy switches from always defect to lose-shift, and the update in Equation (5) no longer guides the dynamics.
5

---

Self-play Q-Learners Can Provably Collude in the Iterated Prisoner's Dilemma
(D,D)
8= (C,C)
s (D,
None of Ass. i) to iii)
Only Ass. i)
All Ass. 3.3 i) to iii)
QaC - 2DDD
Always defect policy
Lose-shift policy
0.0-
Always defect policy
Always defect policy
Lose-shift policy
Pavlov policy
-0.5
0.0
0.5 # iterations
1.0 x10
0.0
0.5 # iterations
1.0
0.0
0.5 # iterations
1.0 x10
x10*
Figure 2. Inftuence of Assumptions 3.1 i) to 3.1 iii) = 0.6 and 1.8 using the parameterization of Table 3). Evolution of the Q-learning policy as a function of the number of iterations in the iterated prisoner's dilemma, for multiple initializations. If one assumption from Assumptions 3.1 to 3.1 íii) is not satisfied, then the Pavlov policy is not achieved. Except for the initialization, the experimental setting is the same as for Figure 1.
Phase 2 - From lose-shift to Pavlov (6 S I t2). In this phase, players alternate to defect in the CC state and cooperate in the DD state. Hence the only entries successively updated are Q(c.C).D and Q(D.D).C- For all
We have shown that the convergence is linear in each phase (from always defect to lose-shift, from lose-shifi ft to Pavlov, staying in Pavlov). In addition, one can show that the time to go from one policy to another varies as ((1/a) in each phase (see Appendix C.2 for the proof of this result).
t 2 41, Equation (3) becomes
Q2141 (C.C)DD = -1-a) + a (DD + -.D.D.C)
In Section 3.1, showed that agents learned to cooperate with no exploration. In Section 3.2, we investigate coop- eration in the general case, with an exploration parameter > O.
@ = (1 (1- a + a rec + +
Similarly to Phase one can show that ((C,C).D converges linearly towards C.C.ejy. fsteshtt Additionally, one can show that, while the dynamic follows Equations (6) and (7), and ((C.C).D Q(c.c),c. then (DD.DI.C > ((D.D).D (see Lemma C.I in Appendix C.I). Hence, there exists l2 such that (o, < <L'C.cy. and ('D.D). D'D.D) the Pavlov policy is reached.
3.2. e-Greedy Q-Learning with Exploration (Algorithm 2 with >> 0)
In this section, we show that Algorithm 1 with sufficiently small step-size a and exploration parameter e yields a coop- crative policy with high probability.
Theorem 3.3. Let 8 > 0 and 1/2 > > O. sufficiently small such that Pavlov policy is a fixed-point of Equa- tion (4) (as defined in Proposition 2.2). Suppose that As- Clog(1/e) sumption 3.1 holds, and so DD. Then, for < Tog(1/6) where C is a constant that is independent of the discount factor ", the step-size a, the rewards and the initialization of the Q-values, we have that with probability - 5, AI- gorithm I does achieve a cooperative policy: Pavlov or 1 lose-shi ft policy in O(1 /o:) iterations.
Phase 3 - Staying in Pavloy (t 1 tz). In this part of the trajectory, both players cooperate in the state CC, and Equation (3) writes
O Vic.o1.0 + a (roc + -ic..,.--- -ic..,,c)..
The only updated Q-entry is Q(c.)). and Q(c.oy. converges linearly toward Parloo
Theorem 3.3 states that for arbitrarily large probabil- ity, there exist small enough agents following Algorithm 1 converge from an al always defect policy to a Pavlov policy. The full proof of The- orem 3.3 can be found in Appendix D. A proof sketch is provided below.
1 - Pavlor
0 and e > 0 such that
=(1-a(1 ( 7)) (1lc,)))) (oic.o),-Qiicee)) -ic.o1.
Parloy
Since P. A rcc/(1 - > -2C = 1 (C.C).D (Assumption 3.1 üi. right), there is no other change of policy.
Proof sketch. We give the proof sketch for going from
6

---

Self-play Q-Learners Can Provably Collude in the Iterated Prisoner's Dilemma
(D,D)
(C,C)
s 3=(DC))
6
0.01
0.05
= 0.10
0.5
0.0
0
2 x10
2 X10
0
# iterations
# iterations
# iterations
X1I)
Figure 3. From always defect to Pavlov policy, Algorithm I with exploration (g 1.8 and 7 0.6). Evolution of the Q-learning policy as a function of the number of iterations in the iterated prisoner's dilemma. With a correct (optimistic) initialization. players go from always defect policy the lose-shi ft policy and then the cooperative Pavlov policy.
always defect to lose-shift with high probabil-
iv) On the event ΣK,T, the deviation for the Q-value Q(D.D).D is upper-bounded
ity (Step l). The proof for Theorem 3.3 is three-folded: first,
show that the non-greedy actions are chosen at most &
times. This requires controlling the occurring probability of the event
(DD.D) Di-Defect < 21:A,0
--7
(1 a(1 -)) T-2 (Q(D.D).D (DD.D..))
εX,T 2 {either of or at a non-greedy action for at most values of 1,...,777
On the event EK,T, for k
(1-7)aQ 2nd,
with AQ
min Q¹D - Q%90
which is done in Lemma 3.4 i). Using bounds the Q- entries at each iteration (Lemma 3.4 ii)), one can control the maximum deviation of the Q-entries of non-greedy (Lemma 3.4 iii)) and greedy actions (Lemma 3.4 it).. Build- ing on Lemmas 3.4 ii) and 3.4 iii one can find assump- tions i and T such that Q-learners go from always defect to Lose-shift Lemmas 3.4 v) and 3.4 vi).
Q:D > a VI ST,, s + DD
vi) On the event EK,T, if T
2h +
log - Defoat 4hA.a
-log( 2
Q Defect
1-y
(b.D),
log(1 log(1-atya)
then
LDDDY,D < <D..D...
Lemma 3.4. Let O < 1/2, < < and 0 & k < T, k N. Suppose that Assumption 3.1 holds, 80 DD, and both agents are guided by e-greedy Q-learning (Algorithm 1), then
Combining Lemmas 3.4 3.4 vi) yields that agents leam the 1 lose-shift. policy with high probability. Similar arguments hold for learning the Pavlov policy from the lose-shift policy.
i) The probability of the event EN,T is lower bounded
P(Ex.)) 2 1 (2c
Figure 3 shows the evolution of the Q-values function of the number of iterations for multiple values of c. 100 of runs are averaged, and the standard deviation is displayed in the shaded area. For < = 0.01, we almost recover the no exploration case. The larger the exploration parameter e, the less the condition for the P Pavlov policy be fixed point of the multi-agent Bellman Equation (4) is satisfied (see Proposition 2.2).
ii) For all state-action pair (s,a) E S A
A,a 1-7
10th1 Q',al
iil) On the event εR,T, the deviation for the Q-values others than Q(D.D),D is most
4. Related Work
2k4,a V(8, a) + (DD, D)
12:a - 1/aal
1-7-
The question of tacit collusion/cooppration between agents has been studied almost independently in the economics

---

Self-play Q-Learners Can Provably Collude in the Iterated Prisoner's Dilemma
and reinforcement learning literature. On the one hand, the economics community perceives collusion/ccopperatinn negative feature since collusion between sellers is against the consumer's 's interest and remains illegal, violating anti- trust laws. On the other hand, in reinforcement learning, col- lusion/cooperatiion considered a desired property, which would potentially yield symbiotic behaviors between decen- tralized agents.
1.0
Percentage of runs achieving cooperation
0.03
0.05
0.8
0.1
0.6
0.02
0.1
0.12
0.15
0.18
0.2
Q-learning without Memory. The dynamics of Q-learnig in the iterated prisoner's dilemma has previously been stud- ied without memory. i.e., Equation (4) with S = 9. More precisely, Banchio & Mantegazza (2022) studied the mem- oryless, averaged (Seijen et al., 2009; Sutton & Barto, 2018, 10), and time-continuous dynamies of Equation (3) (i.e., no stochasticity nor discreteness), with p(a") the prob- ability of picking the action a! E (C.D) writes
6
Figure 4. Influence of a and on the cooperation. For each pair (a, c). the probability learning a cooperative strategy estimated with 100 runs. As predicted by Theorem 3.3, coopera- tion is achieved with a high probability for smaller values of the exploration parameter e, and of the step-size a.
2 = p(aa)) (Fal .2)) + y max Qs Qai)
ment, which yields rewards depending on the other player's actions. (iii) The existence of multiple equilibria. While the question of convergence towards a Nash has previously been studied (Hu & Wellman, 1998; Wainwright, 2019; Usui & Ueda, 2021; Meylahn & Janssen, 2022), characterizing towards which equilibrium algorithms converge is much harder, and is usually only studied numerically, via simu- lations or by proposing approximation methods reduce the problem to solving (prefereably smooth) dynamical system which is then analyzed either theoretically or numeri- cally (Kaisers, 2012: Gupta et al., 2017; Barfuss & Meylahn, 2023; Meylahn, 2023; Ding et al., 2023; Cartea et al., 2022).
The main theoretical results from the memoryless are the following: (i) There is no equilibrium corresponding to cooperative policy, i.e., no fixed point of Equation (8) such that Qi < Qe- (ii) There is always an equilibrium corresponding to an always defect policy, í.e., a fixed point of Equation (8) such that Qb > Qè (iii) Depending on the value of the exploration parameter e and the incentive to cooperate 9. additional equilibrium at the discontinuity of the vector field can appear, i.e., an equilibrium where Q Qc- This equilibrium can be seen as partial cooperation and is considered to be an artifact of the memoryless setting.
Multi-agent Reinforcement Learning. The problem of cooperation has also been approached in the mulli-agent reinforcement learning community, which tackles the question of multiple agents' decision-making in shared environment. Depending on the environment and the rewards, agents can either prioritize their interests or promote cooperation. This yielded a vast literature of empirical algorithms aiming at learning cooperative strategies (Whitehead, 1991) in various settings (Lowe et al., 2017; Sunehag et al., 2017; Guan al., 2023), depending on if the agents can synchronize or not (Arslan & Yüksel, 2016; Yongacoglu et al., 2021; Nekoei et al., 2023; Zhao et al., 2023; Yongacoglu et al., 2023).
5. Experiments
Experimental Setup. In all the experiments we consider prisoner's s dilemma with fixed incentive to cooperate g and fixed discount factor y: g = 1.8 and y 0.6. In Figures I to 3 the stepsize a is fixed to a =1
Influence of Step Size and Exploration. Figure shows the percentage of runs that achieve cooperation for multiple values of the exploration parameter and the step-size For each pair (c, a)), Algorithm 1 is run 100 times, for 2000 iterations, with optimistic initialization. The percentage of runs that yields cooperation is displayed as function of and a. As predicted by Proposition 2.2, when is too large (c = 0.2), P Pavlov policy is no longer a stable point of Equation (4), and no cooperation achieved. As predicted by Theorem 3.3, smaller values of and yield larger probability of cooperation. The influence of the incentive to cooperate g is explored in Appendix E.1: similar behavior are observed for multiple values of the influence to cooperate
Multi-agent reinforcement learning has also been ap- proached from the theoretical side: the convergence of al- gorithms has also been analyzed in the case of zero-sum games (Littman, 1994), non-zero-sum with only single Nash equilibrium (Hu & Wellman, 1998). The main diffi- culty of the multi-agent reinforcement learning theoretical analyses (Zhang et al., 2021, $3) comes from (i) The notion of optimalitylcarming goal, i.e., what are the desirable prop- erties of the learned policy. (ii) The non-stationary environ-
Similar Behaviour in Deep Q-learning. We train a deep Q-network agent (Mnih al., 2015) with a Q-function
8

---

Self-play Q-Learners Can Provably Collude in the Iterated Prisoner's Dilemma
Probability of Cooperation s(
6. Conclusion and Limitation
DD
To understand the empirical collusion phenomenon of ma- chine learning algorithms observed in the economics com- munity (Calvano et al., 2020b), we theoretically studied multi-agent Q-learning in the minimalist setting of the iter- ated prisoner's dilemma. We showed that two agents guided by the usual Q-learning Algorithm 1 could learn the coop- erative Pavlov policy, even when both agents start from an a always defect policy. In addition, we provided ex- plicit conditions (Assumption 3.1) for convergence towards such cooperative strategy in the fully greedy case (e O. Section 3.1), and in the e-greedy case (e 0, Section 3.2).
DC
The major limitation of our analysis is the self-play assump- tion, which is currently crucial in the proof of Theorems 3.2 and 3.3. Empirically, relaxing the self-play assumplion still yields cooperation "most of the time" (Barfuss & Meylahn, 2023, Fig. la): in this setting, players alternate between mul- tiple strategies but on average mostly play the Pavlov strat- egy. Hence, relaxing the self-play assumption would require analyzing the stationary distribution of the process (as done in Xu & Zhao 2024 in the memoryless case), which is sig- nificantly harder and left as future work. Finally, we also plan to study the extension of the emergence of collusion in other reinforcement learning algorithms and more complex environments, such as policy gradient or Bertrand games.
1
11
0
2000
4000
6000
# iterations
Figure Extension deep Q-learning, Evolution of the prob- ability to cooperate conditioned on the state, ie.. the previous actions, as function of the number of iterations in the iterated prisoner's 's dilemma. Multiple runs corresponding to multiple seeds are displayed, as well as their mean. Agents are trained against random agent for the initialization and go from an al ways de fect policy to the cooperative Pavl ov policy.
parameterized by neural network with two linear layers and ReLu activation function to play the iterated prisoner's s dilemma. First, the network is initialized by playing against a random agent for 500 iterations. As discussed in the previous paragraph, this corresponds to Algorithm with an exploration parameter of 1/2. Then the agent is playing against itself, with decreasing exploration going from 1/2 to c 10-2. Details and hyperparameters can be found in Appendix E.2.
Comments on Figure 5. A batch of actions is drawn at each iteration, and we compute the empirical probability of choos- ing the 'cooperate' action given a specific state p(C]s), for all the previous possible states, s E {CC, CD, DC, DD). The procedure is repeated for multiple seeds and the mean across the seed is displayed as thick line. Figure 5 displays the probability of cooperation as function of the number of iterations. Players start to cooperate in the CD states, then successively in the DD and CC states. Finally, around iteration 6000 players start to defect in the CD state and reach the Pavlov ov policy.
9

---

Self-play Q-Learners Can Provably Collude in the Iterated Prisoner's Dilemma
Acknowledgements
Calvano, E., G.Calzolari, Denicolò, V., and Pastorello, S. Algorithmic pricing what implications for competition policy? Review of industrial organization, 55:155-171, 2019.
Q.B. would like to thank Samsung Electronics Co., Ldt. for partially funding this research. GG partially funded by Canada CIFAR AI chair and and NSERC discovery grant. E.C. acknowledges funding by the European Union (ERC grant AI-Comp, 101098332) and PRIN 2022 grant 'Algo- rithms and economic choices', codice Cineca 2022S5RC7R, CUP E53DD2306420001. This research project was initi- ated during the research program "Learning and Games" semester at the Simons Institute for the Theory of Comput- ing.
Calvano, E., Calzolari, G., Denicolò. V., Harrington Jr, J. E., and Pastorello, S. Protecting consumers from collusive prices due to ai. Science, 370(6520); 1040-1044, 2020a.
Calvano, E.,, Calzolari, G., Denicolo, V., and Pastorello, S. Artificial intelligence, algorithmic pricing, and collusion. American Economic Review, 110(10):326-33297, 2020b.
Impact Statement
Calvano, E., Calzolari, G., Denicolò, V., and Pastorello, S. Algorithmic collusion: Genuine or spurious? Interna- tional Journal of Industrial Organization, pp. 102973, 2023.
This paper presents work whose goal is mainly theoretical advances in the field of machine learning. The findings stress the importance of proactive ethical considerations and regulatory frameworks for responsible machine learning de- ployment, influencing policy-making and industry practices to ensure fair competition and societal benefit.
Cartea, A., Chang, P., Penalva, J., and Waldon, H. The algorithmic learning equations: Evolving strategies in dynamic games. Available at SSRN 4175239, 2022.
Chen, L., Mislove, A., and Wilson, C. An empirical analysis algorithmic pricing on amazon marketplace. In Pro- ceedings of the 25th international conference on World Wide Web, pp. 1339-1344 1349, 2016
References
Arslan, G. and Yüksel, S. Decentralized Q-learning for stochastic teams and games. IEEE Transactions on Auto- matic Control, 62(4): 1558, 2016.
Deneckere, R. and Davidson, C. Incentives to form coali- tions with Bertrand competition. The RAND Journal of economics, pp. 473 1733-86,.1 1985.
Asker, J., Fershtman, C., and Pakes, Artificial intelli- gence, algorithm design, and pricing. In AEA Papers and Proceedings, volume 112, pp. 452-56, 2022.
Ding, Z.- Zheng, G.-Z., Cai, C.-R., Cai, W.-R., Chen, L., Zhang, J.-Q., and Wang. X.-M. Emergence of cooperation in two-agent repeated games with reinforeement learning. Chaos, Solitons & Fractals, 2023.
Assad, S., Clark, R., Ershov, D., and Xu, L. Algorithmic pricing and competition: empirical evidence from the ger- man retail gasoline market. Journal of Political Economy, 132(3):723 7711 2024.
Even-Dar, E. and Mansour, Y. Convergence of optimistic and incremental Q-learning. NeurIPS, 14, 2001.
Baker, B., Kanitscheider, I., Markov, T., Wu, Y., Pow- ell, G., McGrew, B., and Mordatch, I. Emergent tool use from multi-agent autocurricula. arXiv preprint woXiv:1909.07528. 2019.
Ezrachi, A. and Stucke, M. E. The curious case of competi- tion and quality. Journal of Antitrust Enforcement, 3(2): 227-257, 2015.
Banchio, M. and Mantegazza, G. Adaptive algorithms and collusion via coupling. arXiv preprint arXiv, 2202, 2022.
Flood, M. M. Some experimental games. Management Science, 5(1):5-26, 1958.
Banchio, M. and Skrzypaez, A. Artificial intelligence and auction design. arXiv preprint arXiv:2202.05944,, 2022.
Guan, C., Chen, F., Yuan, L.,, Zhang, Z., and Yu, Y. Efficient communication via self- self-supervised information aggre- gation for online and offline multi-agent reinforcement learning, arXiv preprint wwXiiv2302.09600) 2023.
Barfuss, W. and Meylahn, J. M. Intrinsic fluctuations of
reinforcement learning promote cooperation. Scientific reports, 13(1):1309, 2023.
Bureau, C. Big data and innovation: Implications for com- petition policy in CANADA. https://ised-int e. oranadd..cc//ttteccmmmettttttorr o
Gupta, J. K., Egorov, M., and Kochenderfer, M. Cooperative multi-agent control using deep reinforcement learning, Autonomous Agents and Multiagent Systems: AAMAS 2017 Workshops, Best Papers, São Paulo, Brazil, May 8-12, 2017, Revised Selected Papers 16, 2017.
ancdd//sttee/eeaaat///Leee/tttt
2018. 2018.
10

---

Self-play Q-Learners Can Provably Collude in the Iterated Prisoner's Dilemma
Hansen, K. T., Mísra, K., and Pai, M. Frontiers: Algorith- mic collusion: Supra-competitive prices via independent algorithms. Marketing Science, 40(1):1-12, 2021.
Nekoei, H., Badrinaaraayanan, A., Sinha, A., Amini, M., Rajendran, J., Mahajan, A., and Chandar, S. Dealing with non-stationarity in decentralized cooperative multi-agent deep reinforcement learning via multi-timescale learning. arXiv preprint arXiv:2302.02792. 2023.
Hu, J. and Wellman, M. P. Multiagent reinforcement learn- ing: theoretical framework and an algorithm. In ICML, volume 98, pp. 242-2422222 250, 1998.
Nowak, M. and Sigmund, K. A strategy of win-stay, lose- shift that outperforms tit-for-tat the prisoner's dilemma game. Nature, 364:56-58, 1993.
Kaisers, M. Learning against learning: Evolutionary dy- namics of reinforcement learning algorithms in strategic interactions. 2012.
OECD, Collusion: Competition policy in the digital age.
https: https://www..edd...rrrff///ooooe /ttp:///aatt///////////////////r / AAtpeittmm--nnd--oollloooooooooo on-policy-ing inrpollcy-i--the-iiiiaa-e-
Kendall, G., Yao, X., and Chong, S. Y. The iterated prison- ers' dilemma: 20 years on, volume 4. World Scientific, 2007.
2017.
Osbome,, M. An introduction to game theory, volume 3.
Klein, T. Autonomous algorithmic collusion: Q-learning un- der sequential pricing. The RAND Journal of Economics, 52(3):538-558, 2021.
Oxford university press New York, 2004.
Schechner, S. Why do gas station prices constantly change?
blame the algorithm. Wall Street Journal, 2017.
Lanctot, M., Zambaldi, V., Gruslys, A., Lazaridou, A., Tuyls, K., Pérolat, J., Silver, D., and Graepel, A uni- fied game-theoretic approach to multiagent reinforcement learning. Advances in neural information processing systems, 30, 2017.
Seijen, H. V., Hasselt, H. V., Whiteson, S., and Wiering, M. A theoretical and empirical analysis of expected sarsa. In 2009 ieee symposium adaptive dynamic programming and reinforcement learning, pp. 177-184. IEEE, 2009.
Silver, D., Hubert, T., Schrittwieser, J., Antonoglou, I., Lai, M., Guez, A., Lanctot, M., Sifre, I.., Kumaran, D., and Graepel, T. A general reinforcement learning algorithm that masters chess, shogi, and go through self-play. Sci- 2018.
Leibo, J. Z., Zambaldi, V., Lanctot, M., Marecki, J., and Graepel, Multi-agent reinforcement learning in sequen- tial social dilemmas. Conference on Autonomous Agents and Multiagent System, 2017.
ence, (626641))1114--11
Littman, M. L. Markov games as a framework for multi- agent reinforcement learning. In Machine learning pro- ceedings 1994, pp. 157-163. Elsevier, 1994.
Sunehag, P., Gruslys, G. L. A., Czarnecki, W. M., Zam- baldi, V., Jaderberg, M., Lanctot, M., Sonnerat, N., Leibo, J. Z., Tuyls, K., and Graepel, T. Value-decoomposition networks for cooperative multi-agent learning. arXiv preprint
Lowe, R., Wu, Y., Tamar, A., Harb, J., Abbeel, O, P., and Mordatch, I. Multi-agent actor-critic for mixed cooperative-ccopeiiiie environments. NeurlPS, 2017.
2017.
Sutton, R. S. and Barto, A. G. Reinforcement learning: An introduction. MIT press, 2018.
Mehra, S. K. Antitrust and the roho-seller: Competition in the time of algorithms. Minn. L. Rev, 100:1323, 2015.
Tang, Y. Towards learning multi-agent negotiations via self-play. In Proceedings of the IEEE/CVF International Conference on Computer Vision Workshops, 2019.
Meylahn, M. Does intermediate price facilitate algo- rithmic collusion? Available SSRN 4594415, 2023.
Usui, Y. and Ueda, M. Symmetric equilibrium of multi- agent reinforcement learning in repeated prisoner's dilemma. Applied Mathematics and Computation, 409: 126370, 2021.
Meylahn, J. M. and Janssen, L. Limiting dynamics for Q-learning with memory one in symmetric two-player, two-action games. Complexity, 2022(1):4830491, 2022.
Mnih, V., Kavukcuoglu, K., Silver, D., Rusu, A. A., Ve- ness, J., Bellemare, M. G., Graves, A., Riedmiller, M., Fidjeland, A. K., Ostrovski, G., Petersen, S., Beattie, C., Sadik, A., Antonogiou, I., King, H., Kumaran, D., Wier- stra, D., Legg. S., and Hassabis, D. Human-level control through deep reinforcement learning. Nature, 518(7540):
Wainwright, M. J. Stochastic approximation with cone- contractive operators: Sharp foc -boudss for Q-learning. arXiv preprint arXiv:1905.062: 2019.
Waltman, L. and Kaymak, U. Q-learning agents in a Cournot oligopoly model. Journal of Economic Dynamics and Control, 32(10):3255-3293 2008
229-533. 2015.

---

Self-play Q-Learners Can Provably Collude in the Iterated Prisoner's Dilemma
Watkins, C. and Dayan, P. Q-learning Machine learning, 8: 279-292, 1992.
Whitchead, S. D. A complexity analysis of cooperative mechanisms in reinforcement learning. In AAAI, pp. 607- 613, 1991.
Xu, Z. and Zhao, W. On mechanism underlying algorithmic collusion. arXiv preprint arXiv:2409.01147, 2024.
Yongacoglu, B., Arslan, G., and Yüksel, S. Decentralized learning for optimality in stochastic dynamic teams and games with local control and global state information. IEEE Transactions on Automatic Control, 62(10):5230- 5245, 2021.
Yongacoglu, B., Arslan, G., and Yüksel, S. Asynchronous decentralized Q-learning: Two timescale analysis by per- sistence. arXiv preprint arXiv:2308.03239, 2023.
Zhang, K., Yang, Z., and Başar, T. Multi-agent reinforce- ment learning: A selective overview of theories and algo- rithms. Handbook of reinforcement learning and control,
pp. 321-384, 2021.
Zhao, X., Pan, Y., Xiao, C., Chandar, S., and Rajendran, J. Conditionally optimistic exploration for cooperative deep mueti-agent reinforcement learning, arXiv preprint arXiv:2303.09032 2023.
12

---

Self-play Q-Learners Can Provably Collude in the Iterated Prisoner's Dilemma
A. Proofs of Q-values at Convergence
A.I. Always defect Policy
Proposition 2.1 (Always Defect). The following Q-table Qr.Defoct is a fixed point of the Bellman Equation (4) and yields an always defect policy, vs {C.D)²
Q = [s)" -7)
aD
Defect Q
= Q2
D. (a2ma(11)) (FD,a² rC,a2)
Proof of Proposition 2./ (always defect). The greedy action of the a ways defect policy is to defect all the time. For all states 8; [C, at E DJ, the self-play multi-agent Bellman equation writes
D = 7(1 - -c) (a).D),D + yeQ Defect + Eatatia
Defect
(a..).D
(9)
i.., for all state 8t E [C,
2 Defort
- 71 (iDD).D
D FDDDa (DC),D
(10)
Q - 7 (C.D).
Defect
Defect
ycQ (C.C),D
7cQ2.Dofec
Defocct Earc,a
(11)
Evaluating Equation (10) in = (D, C) and
= (DD) yields
- D D.fooct 7(1 (DDD),
Defect
DoDooot EorDa
(12)
Defect DDe
+ (1 (1-7(1 Q)D
Defect LoDD,
(13)
One can see that a solution to the linear system. Plugging Equation (14) into Equation (10) yields
D
LiD.Dfoo E.rDDa/(1 7)
(14)
De.Defeet Defect QCD,D EarD,a/(1 (1-7)
(15)
Plugging Equation (15) into Equation (11) yields
vs E D), QrDDefect
Defect ErrC, + 7 EarDa
(16)
1-7
1 EarD,a - (FarD. - Earc,a)
(17)
1-7
Q - (EarD,a - Earc,)
(18)
This means that these Q values imply greedy always defect policy if and only if
EarD. > EarC, ,ie.
(19)
c)rD + orce > (1 - c)rcD + cree
(20)
which is always true since rDD > TCD and PDC > TCC.
A.2. Q-values at convergence for the Pavlov Policy
Proposition 2.2 (Pavlov), If me- and is small enough, then there exists Q-function, Q* which is a fixed point of the self-play multi-agent Bellman Equation (4) and yields the Pavlov policy, i.e,
ree- Frn
Vs E (CC,DD)
Q
Pavlov
> Q
Pavlov
and
E (CD,
Q.
Pavlov
Q
Pavlov
13

---

Self-play Q-Learners Can Provably Collude in the Iterated Prisoner's Dilemma
Proof of Q-values convergence for the Pavlov Policy.
at
Pavlov = = (a), (x.), (c),a + yeQ Pavlov (1) + Ea-a()le) Catio
(21)
Qt Pavlov
CC.ff
71 e)Q² 1 (
Pavlov
yeQ 2 Paaloov
(a) (at.DD + Ea~r(-100) Tal.a
(22)
Q Pavlov
7(1 c) e (a),0),a((a,.o)
Pavlov
y 2 Pavlovv
(a) "e." D) ( Tataa
(23)
DD
Q
Pavlov CD,a!
711 c) 2 a Pavlov
().
+ 7 Q Pavlov
(a) (a,
+ Ea Tatia
(24)
Q @ Pavlov
7(1 e) Q Pavlov
+ t *. Pawlov
+ (DC)
(25)
(d)
(a) (a,,0)
Hence
Q
Pavlov (C,C),C
- 7(1 e) ec,0).c
Pavlov
(D.
Parlov
(CCC TC
(26)
Q
Pavlov (C,C),D
7(1 e) e
Pavlov
(D.D). = (CC)) TD,a
(27)
Q
P.Pallov (D,D).C
T(1 c) e
Pavloy
(C.DD) = Ea (IDD) TC,a
(28)
Q *.Paallov (D.D).D
- T(1 c (D,C),
(D.D). = F aaaa( "Daa
(29)
..Pavlov
- >(1 e (C.D).D
(c. = Eawn(-ICD) TC,a
(30)
(C.D).C
Q P.Pvlov
(C.D).D
- 7(1 e (
Parlov
= (CDD 7D,a
(31)
Q (D,C).C
Pavloo
-
7(1 e) 2) (C.D).D
(C,C).C
= (a)C() TC,a
(32)
Q @ Pavlov
7(1 e) (D.D).C y = (1DO) 7D,
(D.C),D
(33)
One can observe that
Pi 2 (D.D).C
Pavloo
(34)
P. Qt Pavlov
(35)
(D.D).D
(.D.j.CC
Q Pavlov
(36)
(D.C).C
((DD)
Pavlov
Q (D,C).D
Pavlov
(37)
and the system of equations rewrites
Q Pawlov (C.C).C
- 7(1 Q Pavlov
7e02 (C.D). = CaCr()(CC) TC.a
PPalovv
(38)
Q + Pavloov (D.D).D
-
7(1 e)
(C.D).D
Pavlov
7
Pavlov (C,C).C
= (a>D(:IDD) TD,a
(39)
t Pavlov
(C,D).C
7(1 (
ycQ Pavlov
(C,C),C
= Eawa(-(CD) TC,a
(40)
Q QrPooloor
Pavlov
- 7(1 (0 Qt Pavlov
(C.D).D
= (a I'Da
(41)
For Q Pawlov and Q (CDD) on needs to solve the following linear system:
(c,C).
( ( (->(1-e) 1 1-7
(Qieer Pavloo
1 11 (1- -7e
(Fowx(-ICC) TC,a
(42)
(aDD()ICD) TD,a)
which yields
(1 - 7 (awT()(CC) rc,a + yelf (elFawx(((CC) TD,a
Pawloo [(C.C).
(43)
1-
7(1 - -) (-CC) TC,a + (1- - c)) E (-ID) TD.a
PtPaaoor = Parloo
(44)
1-y
14

---

Self-play Q-Learners Can Provably Collude in the Iterated Prisoner's Dilemma
2 Pavlov (C.D),D (CDD).C (DD.C,.D P (D,C).C
(45)
7111-
(C,CC. + (C,D). + (a-x(-ICD) rD,e
Pavlov
(46)
Pavlor -7(1 e) ((,,)) eoyllo (CC
(aN((ICD) TC,a
(47)
= 7(1 2c) 2 Pooylor - -(1_ Pavloo + EawT(-ICD) "DDa - (()D()ICD) TC,a
- 2)) (C.D),D
(48)
= 7(1 2e)(Q(C,0),c Paylor Q(C,D), + (-DD()ICD) TD,a - (/DD( TC,a
(49)
y(1 -2c) ((Ex) TC,a ((CD(( TD,a) + (ICD) "D, (a-r(((OD) TC,a
(50)
depends on
>0
= 711 2ee) ((1 (rco (DD) + -(rcn-rDc)) - Eawa(-ICD VD I (awx(-ICD) TC,a
(51)
depends on
>0
= 7(1 - 2c) 1) 2gc) + (2- g)
(52)
Which is positive. In addition
Pavloo DDD.).C P.
(53)
= 7(1 - 2e) (Eawa(-1CC) TC - Ea (CD) rD,a) + Eawa( LawD(-IDD) (re,a TD,a)
(54)
depends
(11 - 26) ((1 - (roc - rDD) <(rCD rDc)) + (1 () rDC) + <(CD TDD)
(55)
depends
= 2y(1 - 2c) ((lg - 1) - ge)) +g
(56)
depends on
which is positive for e small enough.
B. Propositions B.1 and B.2
Proposition B.1 (Always defect), For all y E 1), the always defect policy, i.e., π Defect (D|s) 1, Vs E S, is subgame perfect equilibrium.
Proof. Regardless of the state, given that the opponent is always defecting, the best response at each time step is to defect since rC, < DD.
Proposition B.2 (Pavlov). 1f > 7 2 2-9 then the Pavlow policy, i.e., π Pavlov (D|s) 1, Vs E (CD, DC) and n. Pawlov (C|s)= = 1, Vs E (DD, CC), is subgame perfect equilibrium.
Proof. Let us assume that our opponent plays according to Pavlov and show that the best response to also adopt this strategy. By the one deviation principle (Osborne, 2004. Prop 438.1), one only needs to show that for the four possible starting states the best response against Pavlov is to follow Pavlov.
we start in 8u E {CD, DCJ, the opponent will defect and the best response is to defect since, if we cooperate, we end up in CD which leads to worse payoff that going straight to DD by defecting, FCD +YrDD & ? which is always the case since TCD < FDD < TCC-
If we start in so = CC, we should show that is better to cooperate than to defect. It is the case if, rCD + YDDD + +rec S rec + yrcc + rrrc, which is true if and only if y 2 rpe-ree
rec-rDp 20-11
Finally, if we start in so = DD, it is better to cooperate than to defect as the opponent is cooperating. Hence, the best response to the Pavlos ov policy is to play according to Pavlov.
15

---

Self-play Q-Learners Can Provably Collude in the Iterated Prisoner's Dilemma
C. Proof the Fully Greedy Case (Theorem 3.2)
C.1. Lose-shift to Pavlov
Equations (6) and (7) that govern the dynamics of Q(C.C).D and Q(D.D), from the Lose-shift policy to Pavlov policy are recalled below:
1 (C,O),D = =11-a) +a (TDD+t + +
(6)
(DD.). = (1-a) t Tec + +10(0.0)
(7)
Plugging Equation (6) in Equation (7) yields:
(DD.).c = (1 (1- (1-a)Q + a (rec + +1 ta ya (DDD ((D.D).)) ,ie.
(57)
(DDD).C an a + (1 -1-a+
(1-a+or2)Qpp.) + a (ree + yarDD)
(58)
Following Equations (6) and (58), the dynamics of ((C,C),D and Q(D.D).C governed by the linear system
dicci
1 1-a (-ar(11a) a) 1 a (
-ay
)
(
Píc.C).D +b, (-Q ((.
(59)
(m.D).cc
for given b. Let (-Qrrloo-shhif (C,C),
@r-oos--hhift) be the fixed point of this linear system, it writes V.D.D).C
Qt (CCO),D (C.C). - (Q++ Qx-less-nnittty QTD.D).C
Otllos-shhift
--
1-a ao)
-07 1 1- a (az)2
( (C,C),
los0-s-st
(60)
((Q) -
Q.D.D).C
Standard computations yield the eigenvalues of the matrix
(
1 1- (ay -a) 1- 1 a
-ay
(61)
a7 + V 11-a 2
(a7)2 a
4 = =1-ator
(62)
4
Thus for < a < 1 and 0 < < we have < d < and thus (eiC.O)DD: V (DD.).)) converges linearly towards
Then using Lemma C.I, we have that (/C,OL, will get below O/C before Q (D. getting below Q (DD.D).D
Lemma C.1. In the phase from lose-shift to Pavlov, if Ton A (C.C),C PCC.DDD Oi ('D.D). > DDD.D..
<00,00 S 1= then while
Proof. (Lemma C.I) phase 2, (CC,C) > C Using Equation (7)
Q+11 @DD.C (1 (l-a)Qip.).cta +al
rCc 7
+++
(C,C).D
H+1
(63)
2 L.D. = Assumpiioo 3.1
hence
DDD.D
(64)
For phases? 2 and 3, the convergence is also linear, and similar arguments hold.
16

---

Self-play Q-Learners Can Provably Collude in the Iterated Prisoner's Dilemma
C.2. O(1/a) convergence rate
The convergence of the Q-values is linear in each phase (1 to 3). For instance, in phase the convergence is linear with rate (1 - (1-a(1- ,)), more specifically,
L'D.D). - (DDD),DD = (1 - a(1 - (Q) (DD)..
(iD.D.D)
(65)
With the later decrease, the policy switches, i.e.
D R.D.bfes < (DD.)..C (D.D).
Defect
will require number of steps
T (log(Q(DD).c Q ((..)).D)) log(Q - Q (DD.),.)))) /olpn/////o/l111 a(1 7))
(66)
-a-0 (log(Q ((D.D).D))) log log(Q (.D.b /a 17))
(67)
= -(1/a)
(68)
For phases 2 and 3, the convergence is also linear, and similar arguments hold. To summarize, the convergence is linear in the three phases (from a always defect to Lose-shift, from Lose-shife to Pavlov, staying in Pavlov), and done in (11/a) in each phase.
D. Proof of the c-Greedy Case (Theorem 3.3)
Let us start with the proof of Lemma 3.4.
D.1. Proof of Lemma 3.4: from always defect to lose-shift
Lemma 3.4. Let 0 1/2. 0 < and 0 < T, e N. Suppose that Assumption 3.1 holds, so DD, and both agents are guided by c-greedy Q-learning (Algorithm 1), then
i) The probability of the event εN,T is lower bounded
P(Ex,T) 2 1-
1-22 2" (2e))+t11
ii) For all state-action pair (s, E SXX
Dpa
10tt1 -
iii) On the event T,, the deviation for the Q-values others than Q(D.D),D is
2k4,a
10' - Q00 I
V(s,a) (DD,D)
1-7
iv) On the event E,,T, the deviation for the Q-value Q(D.D),D upper-bounded
2kA,a
0+1
(.D... V.D.D <
1-7
+ a(1 (1-a(1-1) a(1-7))TT- T-28 - Q(D.D)).)
v) On the event T, for k <
(1-))QQ
with AQ e min Q% - Q
2nd,
Q:D C.cc, VI V 8 + DD
log 2o
4kA.0 1-7
log ( 20 - Defecs
vi) On the event Tr.T, ifT 2k
then
log(1 aa1a))
of PDDDD.D < &.D.DICc
17

---

Self-play Q-Learners Can Provably Collude in the Iterated Prisoner's Dilemma
1.1.1. PROOF OF LEMMA 3.4
Proof of Lemma 3.4 i). The proof of this result relies on the fact that
The probability of the greedy action is
Each agent picks their action independently of the other.
Thus, either both agents take greedy action with probability (1-))², --2 or at least one of them picks a non-greedy action with probability 2e - e².
P(ExTT)
Σ P(a non-greedy action has been picked exactly times in T steps)
(69)
(1 201 ()
(2c -)
2²
(70)
5(26)'5(26)* ()((-)))
=1- Σ
(2c -2)
(because 0 < 1
(71)
Si -2)=2
2 1 - (2E) k+1
(1 - c))2(()-)
(72)
i=++1
2 - (2c)
(73)
i.e,
P(E,T) 21 2 (2c)
(74)
We will then use this lemma in steps 1 and 2. The idea of the proof will be to leverage this lower bound to show that the e-greedy dynamic behaves similarly to the fully greedy policy.
D.1.2. PROOF OF LEMMA 3.4 ii)
Proof of Lemma 3.4 ii). For all state, action pair (s, a) E S x A, the Q-learning update rule writes
Q Q' + +a (re (re ymx Q2,a' Q%,aa
(
(75)
In addition, since Q = Ere rr, then the Q values cannot go above (resp. below) the maximal (resp. minimal) reward. In other words
Tmin
<Qa. <
Tiax 1-7
which yields
(76)
Tmin + 7
Tmin
F mmax
<ri + 7 max l' Q², Tmax + 7 1
Tmax
Tmin
(77)
7
Fmin
Tmax
<r' + +/ max Qr Qiaa 5 Tmax Tmin
(78)
Plugging Equation (78) in Equation (75) yields the desired result
D Q44t1 Qa,al S
(79)
with A, A Tmax Tmin the difference between the maximal and the minimal reward.
18

---

Self-play Q-Learners Can Provably Collude in the Iterated Prisoner's Dilemma
1.1.3. PROOF OF LEMMA 3.4 iii)
Proof of Lemma 3.4 ii). Conditioning on Êx,T, for all state-action pair (s, A (DD, D). Qa,a updated 2k times. Since Qa,a is updated most 2k times, Lemma 3,4 fi) repeatedly applied 2k times yields
2kA,a V(s,a) + (DD,D)
10t
Q% S
(80)
1 1-7
D.1.4. PROOF OF LEMMA 3.4 iv)
Proof of Lemma 3.4 Let us consider the first step, from always defect to Lose-ssifft We start from the always defect region, i.e., the greedy action is to defect regardless of the state. When the greedy action D is picked in the state DD, the entry ((D.D).D updated as follows. In other words, conditioning on &
The defect action D the state DD is played least T 2k times. When it is the case, Q(D.D).D updated least T 2k times according to
(DDD),D ((D +a (TDD + (1( Q(D.D).)
(81)
(D.)).D (D.D). (1 a a (1)D,)). Defect
(82)
with Dofeer
mpp I--"
Otherwise Q(D.D), update is bounded 24: times using Lemma 3.4 ii):
(DD.). (DDD). S QDD.D). - V.D.Dy +
Defort
A,a
(83)
1-
Combining Equation (82) for at least T - 2k steps, and Equation (83) for at most 2k steps yields
VDDD),D Defect I a1-a + 2h (DDDD)) ((D.D).D) + 2k
(84)
1-7
D.1.5. PROOF OF LEMMA 3.4
Proof. Let E S\DD, < T, on the event Σg,T
ØDDD -'
Q'DD - Qr
- -
@ Q
(85)
2 2h- (using Lemma 10))
2t (using 3.4 mi)
2minggnd 2% 220 AAQ
4k
7 + =A
(86)
Hence, if
k > (1 (1-1) -)-")
(87)
4Ar
then the event Exr for all E SADD,
QTD - -T. 2 0
(88)
Note that AQ"o A mDD 0%0 240 since one starts from the always defect policy.
19

---

Self-play Q-Learners Can Provably Collude in the Iterated Prisoner's Dilemma
1.1.6. PROOF OF LEMMA 3.4 vi)
Proof. Using Lemma 3.4 iv), the event T, one has
2k 1 1-7
( (1 ar) T2
(.D.pfoce (DiD.D).D
(D.D).D
Defect
(89)
2ka
v 1-9 + DDD.
(90)
log (DD.D). (D.D). 1kA.a log ( I-7
(QDDD),D
Q
Defect
T> 2k
(91)
log(1 a + 700
Remark D.I. (D..D).c - VDD.D
4k..a 1-7
needs to positive.
In addition, using Lemma 3.4 iii) ε yields
2koAr
+ *DDDC S Qbn
(92)
1 1-7
Combining Equations (90) and (92), yields that on εK,T, if
Defectt log ((D (D.D). 1-y
14S,a - log (QD,,),, - (D.D).D
T > 2k +
(93)
log(1 a
then
(DD.).D < &.D.DY.C
(94)
D.2. Proof of Theorem 3.3
Proof of Theorem 3.3. To conclude, if we set k = 0(1/a), such that Ag(1-7) and the total number of steps such
2ad,
log m - P.D.D),
48A.0
loR (. ((D.pp.
Difecc))
that T 2k
1-7 1-7
one that with the probability of at least - 2T T
log(1 (ag(1_)+7a)
there exists & such that (.D.D).D ((D.D).C
The proof can be concluded as follows: in order to hold with probability at least 1 8, must satisfy
T log(2) + k log 2e < log
(95)
T
log(e)
log(d)
log(2)
(96)
:=Caa
:=Cy
where the constant C depends on the constants of and &e but is independent of alpha. Indeed, as both T and grow as 1/a, the ration T/k can be chosen independent of ac: this ensures that the event holds with high probability, and does not contradict & < Aq 2n4
(1-7) = O(1/a) from Theorem 3.3. More formally, the number of steps needed T, varies as function
of 1/o: T ~ C Ca, and & ~ C2/a, for given C₁, C2 E IR. The choice of k in Theorem 3.3 requires as well a growth as 1/0: & A1 (2a = (1/a).
To summarize, we proved that with high probability, there exists time step 1 such that
LDDDDDD < DDD.).
(97)
(98)
DDD., L'b.
(99)
Q dCDD) > Q (DDD).D
(100)
20

---

Self-play Q-Learners Can Provably Collude in the Iterated Prisoner's Dilemma
and for all 1 < 1
LDD.D). (DD.).C
(101)
( CCC.C
(102)
Q/D.C), DDD.)).
(103)
C(C.D). C(DDD
(104)
In plain words, the Q-values went from the a ways defect to the lose-shi ft region.
D.3. From lose-shift to Pavlov
In this section, we show similar results to Lemma 3.4. For simplicity, we considered that in Equations (6) and (7) one-time step was performing two e-greedy updates.
1. We can lower-bound P(E,TT
2. Under the event ε we will observe at least (1 11-4M / pair of updates following Equations (6) and (7) are performed and at most 4k greedy updates.
3. Thus the Q-values for the greedy actions Q(c.C),D and Q(D.D).C will converge linearly and can be bounded.
4. The Q-entries of the non-greedy actions can be bounded.
Similarly Lemma 3.4, one can control the Q-values in the greedy and non-greedy states.
Lemma D.2. Let us consider Algorithm with e < 1/2, 7 > 0 and 0. If both agents act according to an e-greed lose-shi ft policy then,
i) On the event &K, for all (8,a) ESXA
A,a 1-7
Q D'aal S
ii) On the event Tx, for all t 2 4 the deviation for the Q-values others than Q(D.D).C and Q(C,C),D is at most
2kA,a 1-
10 - 0 S
V(s,a) & ((DDC)) C), (CC, D)}
iii) On the event Σ,, the deviation for the Q-value Q(C.C),D is upper-bounded
Pic.CyD -0.-ese-shire <G - C22 + 2k (C,C).D
(105)
1 1-7
where Cj and C2 are defined Equation (123). (1-7)AQ
iv) On the event Ex,r, for & < 2nd, with aQ a min 2 QQ2
@tDD Qyc;; VIS 8 + (DD, CC}
v) If (C O'c.
akA.a 1-7
for all t < t tz
AD,a
+ -CC,o
- QiC.CY 2
(106)
1 1-7
In other words, this ensures that the agents either go to the Pavlov policy or oscillate between always defect and Hose-shifi but do not directly go from always defect to Pavlov.
The proof of Lemmas D.2 i) to D.2 iv) are the same as for Lemma 3.4.
21

---

o Self-play Q-Learners Can Provably Collude in the Iterated Prisoner's Dilemma
Final proof of Theorem 3.3. Once we reached the Lose-shife policy, using Lemmas D.2 iii) and D.2 iv), either
Cic.c). < Ci and the policy changes for the Pavlovpolig
Either non-greedy actions are taken, and we go to the always a awwass defect policy, i.e. we back the previous situation, Lemma 3.4, but at this time-step, l'c,C), might be closer ((C, In this situation
Either greedy actions are taken and we achieve again the lose-shift region
Either non-greedy actions taken, and C(C.Cy. might become smaller than (cC,),C which yield win win-stay policy.
Proof of Lemma D.2 v).
Qt+1
(C,C).D
shift) (D.D),C
Q(C.C).
- ( aa) 1 - a + (17)3) )
1 1-a
ay
0 Poc.,,, - (.C.).D shift)
(107)
@ (D.D).C
Q (DD.).
(D.D).C
which yields
24'
Mr
(108)
0r)
20
with
M
- -ab a+ 12
a
(109)
1-a
(110)
b a7
(111)
u' = l - -ie0,00. -o.
(112)
of (Vi.Di.c-0/blpe Q.plps
(113)
The matrix M can be diagonalized:
M
2ah
2ab
A1
0
V4u E
2[1
(114)
1
A2
ab
/4n24h4
4
2(
=
P: 1i (Ws)
with \1 +
+++bb+o 2
A2
62
Let
50
8
p-1
v0
=
v4a2+6
ve ab
+ 1.0
+ 1
2
2[
64
4h
(115)
74a2+84
2[
be the decomposition of
in the basis wi, w2!
10
=
50 w1 + 69 U2
(116)
Combining Equations (108) and (116) yields
16 o
89
8926us w1 + 821bu2
(117)
22

---

Self-play Q-Learners Can Provably Collude in the Iterated Prisoner's Dilemma
and
W1 -1 )
1
w - 1²
01
1
+
02
X2
1222
-1
(118)
>0
>0
b + v 44a + b
b²
v 44a² + b4
6
1
02
1
1
(119)
2ab
2ab
>0
>0
Since A1 > X2, then if t of 0, then u² - r² > 4 611 > 0.
In other words, in order to show that C/C,C).D icC,,). + U/D.DD.C ((D,D).. == u' - that th n Cste
06 2 Csle, then it is sufficient
Hence one only needs to show
kA,a
- + 0 (C,C), Q
(C,0). 2
(120)
1-7
21:A,0
0 C 2
(121)
1-9
4h:A,
0 (c,O).c 2
(122)
1 1-9
Proof. Lemma D.2 iii). Using Equation (116) one has
CCC.DDD -ddse--shiit
(C.O),
< 80
12
44
+
bt
21
52
b²
v 4 + b
N1 1-
2h 0
(123)
2ab
2ab
7
==
E. Additional Experimental Details
Table Prisoner's dilemma rewards parameterization used in the experiments, <
Cooperate
Defect
2g
2 + g
Cooperate
2g
2
Defect
2
2
E.1. Influence of the Incentive to Cooperate
Comments on Figure 6.. Figure 6 displays the evolution of Q-values difference as function of the number of iterations in the iterated prisoner's s for a self-play evolution of Algorithm in the fully greedy case = 0. As the incentive to cooperate increase, the time when the lose-shifi policy and then the Pavlov policy are reached (green zone) decrease, in other words, cooperation is achieved faster.
E.2. Hyperparameter for the Deep Q-Learning Experiments
The hyperparameters used for the deep Q-learning experiments are summarized in Table 4. runs are displayed in Figure 5, each run takes hours to train on single GPU RT'8000.
23

---

Self-play Q-Learners Can Provably Collude in the Iterated Prisoner's Dilemma
(D,D)
(C, C)
(D, C)
02
011
1.8
014-
1.85
022
iterations
X30
Figure 6. Influence of the incentive to cooperate Evolution of the Q-learning policy as a function of the number of iterations the iterated prisoner's dilemma. With correct (optimistic) initialization, players go from an always fece policy the lose-shi ft policy (at time f1), and then go to the cooperative Pavlov policy (at time t2). The discount factor is set to = 0.6. The incentive to cooperate g varies from 1.75 g 1.9 (see Table 3).
Table List of hyperparameters used in the deep Q-learing experiment (Figure 5).
Hyperparameter
Value
tau
0.01
seed
8
gamma
0.8
buffer_capacity
1000000
decay_eps
true
eps_decay_steps
600
eps_start
0.5
eps_end
0.01
loss_type
Huber Loss
optimizer_typpe
SGD
hidden_sizz
32
num actions
2
num iters
10000
batch size
16384
do self play
true
pretrain iters
600
pretrain_yy vs random
true
24


Reviews:
[{"review_id": "iFjFFJqnbB", "reviewer": "Reviewer_LKws", "summary": "This paper shows that in the Prisoner's dilemma, Q-learning agents can learn to collude to a collaborative policy.\nThe authors clearly identify the underlying assumption to such behaviours.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Authors would like to thank Reviewer LKws for their in-depth comments and very insightful review.\n\n> 1 - The authors prove the convergence results for the case of one-step memory. How is this case motivated?\n\n\nThe primary motivation for this work stems from the findings of Banchio and Mantegazza (2022), who showed that in the memoryless case with averaged updates, cooperative equilibria do not emerge—agents consistently learn the always defect equilibrium, or an equilibrium residing at the boundary of the cooperate-defect regions (see Figure 5 of their paper). We hypothesized that this lack of cooperation was specific to the no-memory setting and that introducing even a minimal, one-step memory could facilitate convergence toward cooperation. Our results confirm this hypothesis.\n\nReference:\n Banchio, Martino, and Giacomo Mantegazza. 2022. \"Artificial Intelligence and Spontaneous Collusion.\"\n\n> 2 - In the related work section, they also discuss related results for the memoryless case. But what would change if we assume perfect memory?\n\nThe choice to focus on one-step memory is motivated both conceptually and practically. Axelrod (1980a, 1980b) demonstrated in his repeated Prisoner's Dilemma tournament that the most effective human-crafted strategy (TIT FOR TAT) relied on short-term memory, was forgiving, and was the simplest among the submitted policies. This suggests that minimal memory is sufficient for cooperative behavior to emerge.\n\n\n\nFrom a theoretical point of view, going beyond the one-step memory is significantly much more complex to analyze and quickly becomes computationally intractable: for instance, with a two-step memory, the state space is of size $2^4 = 16$, which yields a number of $2^{2^4} > 6 \\cdot 10^4$ possible policies, which would be significantly more challenging to analyze theoretically (and potentially for only marginal conceptual gains). \n\nFrom a practical point of view, reinforcement learning models for the Iterated Prisoner's Dilemma often employ GRUs or LSTMs (e.g., in LOLA [Foerster et al., 2018]), but these architectures are still constrained in their memory capabilities—LSTMs, for instance, can typically recall only up to 150 steps (Khandelwal et al., 2018). Similarly, transformer-based approaches are limited by context window length. However, such deep-learning considerations fall outside the scope of our study.\n \n\nAxelrod, Robert. \"More effective choice in the prisoner's dilemma.\" Journal of conflict resolution, 1980a\nAxelrod, Robert. \"Effective choice in the prisoner's dilemma.\" Journal of conflict resolution, 1980b\n\nFoerster, Jakob N., et al. \"Learning with opponent-learning awareness.\" AAMAS 2018\n\nKhandelwal, Urvashi, et al. \"Sharp nearby, fuzzy far away: How neural language models use context.\" arXiv preprint arXiv:1805.04623 (2018).\n\n\n> 3 The authors provide their results based on Assumption 3.1 and motive such assumption. Nonetheless, do the authors have any intuition about the behaviour of Q-learning for other initial conditions.\n\nYes! We have clear intuitions about the behavior of Q-learning under different initial conditions. For instance,\n- If Assumption i) is not satisfied, then one can show that the agents learn the always defect policy. As for the proof of Thm 3.2, one can study the evolution of Equation (4), and show that $Q_{(DD), D}^t$ converges to $Q_{(DD), D}^{\\text{always defect}}$, and always stay larger than $Q_{(DD), C}^t = Q_{(DD), C}^{t_0}$, hence the policy remains always defect. This is also illustrated on the left plot of Figure 3. \n- If Assumption i) holds but Assumption ii) does not, the learned policy follows a lose-shift strategy. This can be established using similar arguments by analyzing the evolution of the system of Equations (5-6).\n\n**Action:**  These discussions will be added to the revised manuscript.", "claims_and_evidence": "The main contributions of the paper is to prove that both with (Theorem 3.3) and without exploration (Theorem 3.2), agents can learn a cooperative policy.\nProofs and proof outlines are provided for the main results, which seem to be correct.", "methods_and_evaluation_criteria": "Yes, the methods are sound and the experimental evaluation appropriate.", "theoretical_claims": "Proofs of the main results are provided in the body of the paper. They appear to be correct.\nProofs of other results are given in the appendix. I did not check them.", "experimental_designs_or_analyses": "The experimental analysis appears to be correct. This is most a theory paper, experiments are used to back the theoretical claims in the case of deep Q-learning.", "relation_to_broader_scientific_literature": "As opposed to (Banchio and Skrzypacz, 2022; Banchio and Mantegazza, 2022), the authors consider the standard stochastic (i.e., not averaged) version of \\epsilon-greedy Q-learning with memory.\n\nThe paper cites (Banchio and Mantegazza, 2022) at various times, as there converge of Q-learning in the prisoner's dilemma is considered for the memoryless case.\nStill, the results obtained are quite distinct from (Banchio and Mantegazza, 2022) -- where a cooperative strategy does not exists -- to justify a separate analysis and contribution.", "essential_references_not_discussed": "Related works are discussed at a suitable length.", "other_strengths_and_weaknesses": "This paper shows an interesting convergence result of Q-learning in the prisoner's dilemma, which might find applications in markets.\nStill, the contributions is mainly theoretical. Also, a number of assumptions are made on initial conditions and the behaviour of agents. So, the results are rather tailored to the particular setting in hand.\nIt would be interesting if the authors discussed the broader implications of their results.", "other_comments_or_suggestions": "The Pavlov policy has long been known as an optimal policy for the repeated prisoner's dilemma. What is nice in this paper is the proof that this policy can actually be learnt by using Q-learning.\nThis is interesting and useful information, as there exist several strategies which are fixed points of the Bellman equation and could theoretically be learnt by Q-learning, as the authors point out. This paper shows convergence to a specific equilibrium.", "questions_for_authors": "1) The authors prove the converge results for the case of one-step memory. \nHow is this case motivated?\n\n2) In the related work section, they also discuss related results for the memoryless case. \nBut what would change if we assume perfect memory?\n\n3) The authors provide their results based on Assumption 3.1 and motive such assumption. Nonetheless, do the authors have any intuition about the behaviour of Q-learning for other initial conditions.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "AmZc1MPj3k", "reviewer": "Reviewer_hUYk", "summary": "The paper studies Q-learning in the Iterated Prisoner’s Dilemma with memory 1. It shows by formal proof that under some condition, Q-learning results in the so-called Pavlov strategy, which forms a cooperative equilibrium. The paper also conducts some experiments, including experiments with Deep Q-learning on the same Iterated PD.\n\n\n## update after rebuttal\n\nGiven that this paper received mixed scores and that I know this area reasonably well and am quite interested in it, I spent relatively much time looking at the paper again during rebuttal.\n\nI'm sticking with my \"weak accept\" recommendation. If anything, I'm now torn between \"weak accept\" and \"accept\". I think this is a solid paper and it should be accepted.\n\nThat said, my recommendation is made under the assumption that the authors will use the extra page in the camera-ready version to clarify some things and better relate the paper to prior findings with somewhat different results. See my previous review, my response to the rebuttal, and the below comments for details.\n\n\nMore in-the-weeds comments from re-reading some parts:\n\nI looked at the proof of Theorem 3.2 again in some detail to better understand the underlying dynamics.\n\nIt seems to me that self-play is at least somewhat important for this step of the proof. In particular, when you switch to playing C in (D,D), it seems important that your opponent also switches at the same time. This way, you will now learn that C in (D,D) is quite good (it gets you the (C,C) payoff), even though from a \"counterfactual\" perspective it's actually worse (if you could switch to D while having your opponent stick to C, that would be better). If the time of switching from D to C was very out of sync (because the two players have separate Q functions, etc.), then once the first player switches to C, they would very quickly learn that C is even worse than D, while the other player would start receiving more positive results again with D, because they would get the (D,C) \"temptation\" payoff.\n\nIn principle, this dynamic used in the proof even applies to training in a one-shot Prisoner's Dilemma: If you switch very discontinuously from (almost) always always defecting to (almost) always cooperating ((epsilon-)greedy) and you train via self-play, then cooperation is (somewhat) stable, because you only (mostly) ever cooperate when your opponent also cooperates. IIRC, these kinds of dynamics were studied by https://proceedings.neurips.cc/paper/2021/file/b9ed18a301c9f3d183938c451fa183df-Paper.pdf I think this says that in the one-shot PD setup with self-play, epsilon-greedy allows convergence to mostly cooperating (in terms of frequencies, not iterates) due to this dynamic or at least their results don't rule it out. Generally the self-play setting of the present paper can be viewed as a special case of the setting of that paper (I think). But I think the only result from that paper that somewhat directly applies to this paper just says that one can only converge to Nash equilibria.\n \n\n\nAnd another request for clarification: In the Deep Q-learning setup in Section 5, is there anything akin to optimistic initialization happening? (More minor: \"As discussed in the previous paragraph\" -- I don't understand which part of the previous paragraph this refers to. Maybe a paragraph was deleted here at some point?)", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Authors would like to thank Reviewer hUYk for their in-depth comments, which have significantly improved the updated version of the manuscript.\n\n> I’d like to know what the relevant differences are to this paper. E.g., is it the slightly increased complexity of the environment? Or not using self-play?\n\nThe key distinction between our work and all the papers cited in the review is that they adopt an empirical approach, mostly introducing new algorithms/settings to promote cooperation. For ourselves, we establish theoretical results on achieving cooperation for an existing algorithm: $Q$-learning. Below, we clarify the differences between our algorithm and those considered in the cited papers, as well as why we believe they report divergent findings (i.e., that cooperation is difficult to achieve).\n\n- **Sandholm and Crites, 1996**: This study examines the same setting as ours but employs a policy gradient method instead of Q-learning and does not consider self-play. Given their experimental findings, our theoretical results are somewhat surprising. Notably, empirical evidence suggests that relaxing the self-play assumption still leads to cooperation “most of the time” (see Barfuss and Meylahn, 2023, Fig. 1a). **Our perspective**:\n  - In retrospect, we believe their findings differ because policy gradient methods struggle to discover cooperative policies.\n  - Barfuss and Meylahn suggest that the absence of self-play does not inherently prevent cooperation from emerging.\n\n- **Foerster et al., 2018; Letcher et al., 2019**: These works build on Sandholm and Crites (1996) by introducing opponent shaping, where updates account for the opponent’s learning process using first-order methods. Their approach aims to address the shortcomings of standard policy gradient methods. While they apply their methods to slightly more complex games, tabular Q-learning would still be feasible in such settings.\n**Our perspective**:\n   - Their conclusions differ from ours because they focus on policy gradient methods, which, as shown by Sandholm and Crites (1996), struggle to find cooperative policies.\n   - They consider a slightly larger game (the coin game) and relax the self-play assumption. It would be interesting to test whether tabular Q-learning can still identify cooperative strategies in this setting.\n\n- **Oesterheld et al., 2023**:\n This work investigates the one-shot Prisoner’s Dilemma, a setting where cooperation is known to be unattainable in equilibrium. They circumvent this limitation by introducing transparency, allowing agents to share information about their similarities. While their problem setup is more constrained than ours, it introduces distinct challenges.\n\n- **Hutter et al., 2020**:\n This study integrates ideas from Foerster et al. (2018) and Letcher et al. (2019), along with transparency mechanisms similar to those in Oesterheld et al. (2023). Thus, their conclusions diverge from ours for similar reasons.\n\n> 1 Since Pavlov is a fixed point of the Q function, it’s, I assume, relatively easy to show that there are some initializations under which the Q-learner starts out and sticks with Pavlov.\n\nYes Indeed! If the Q-values are initialized exactly at one of the equilibria, e.g., the Q-values corresponding to the Pavlov policy, then the policy sticks to Pavlov. This is also true for the always defect policy.\n\n *The paper's goal is to show that one can initialize the Q-values such that the initial policy is always defect*, but still converge toward a cooperative policy. This is not obvious because one has to show convergence towards a specific equilibrium, which is non trivial.\n\n\n\n> 2) How was Table 1 picked?\n\nThis table comes from Bancio and Mantegazza, a work we directly build upon; that´s why we chose this parameterization to begin. Intuitively, $g$ controls the incentive to cooperate; the larger the $g$, the larger the cooperation is incentivized. In this setting, $g$ can vary between 1 and 2. We would like to stress that all the results are derived with general rewards $r_{a^1, a^2}$ (as it can be seen in Appendicies B, C or D) and the 1D parameterization is mostly used for clarity of the presentation (e.g., the existence of the Pavlov policy, Prop. 2.2). We will remove this parameterizationand keep the general reward formulation $r_{a^1, a^2}$. \n\n**Action**: We clarified these discussions in the manuscript and adopted the general reward parameterization. All the comments from the Comments or Suggestions section have been addressed in the updated manuscript, however, we chose not to answer them for the conciseness of the rebuttal.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "I tried to read the proof of Theorem 3.2, but didn’t verify the details.", "experimental_designs_or_analyses": "I didn’t check anything beyond what’s written in the main text.", "relation_to_broader_scientific_literature": "There are a bunch of papers on whether agents trained with RL or the like can learn to cooperate in various Prisoner’s Dilemma-type games. I mostly view this paper as a contribution to this literature.", "essential_references_not_discussed": "There are more papers on learning agents in the iterated Prisoner’s Dilemma or very similar games. (The authors already cite some of these papers.)\n\nI’d be especially interested in a discussion of related papers that have found something more like the opposite result, i.e., that training typically doesn’t find cooperative strategies. E.g., https://www.sciencedirect.com/science/article/pii/0303264795015515 \nhttps://arxiv.org/pdf/1709.04326 https://arxiv.org/abs/2211.14468 https://arxiv.org/pdf/1811.08469 https://arxiv.org/abs/2012.02671 All of these papers use somewhat different methods on somewhat different games. But they all find that if one just does some kind of “naive best response” learning, one doesn’t learn to cooperate. I’d like to know what the relevant differences are to this paper. E.g., is it the slightly increased complexity of the environment? Or not using self-play?\n\nSomewhat relatedly (and less importantly): Quite a few papers have proposed methods for finding more cooperative equilibria. In principle, the results in the paper could also be used to this end. This is very briefly discussed in Sect. 3.1. It would be interesting to see a more detailed discussion of how this would relate to these other methods, though I think the authors view their project mostly as descriptive rather than prescriptive. So, perhaps it’s not that interesting to talk about how various other methods for achieving cooperation are better/worse.", "other_strengths_and_weaknesses": "I like how the paper uses theoretical perspectives (talk of subgame-perfect equilibrium), while also engaging with the practice of multi-agent ML.\n\nI haven’t checked the proofs, but I’ve thought about this sort of issue enough to understand that it is difficult and very tedious to prove this sort of result. So, although the contribution could be viewed as small (in that it is about a specific, simple game, etc.), the amount of effort necessary to obtain this sort of result is, I believe, quite large.\n\nThe question of whether/when cooperation can emerge in RL is important.\n\nIn my mind, the main weakness of the paper is that it is a little hard to understand, both at the micro level – see the detailed suggestions below – and at the level of motivation and interpretation for the results. From more to less central:\n\n1) Since Pavlov is a fixed point of the Q function, it’s, I assume, relatively easy to show that there are some initializations under which the Q-learner starts out and sticks with Pavlov. (Right? E.g., take whatever Q values you get in Phase 3 and just initialize it to those.) \n\nI take it that the paper is interesting in large part because it doesn’t just do this. Instead, it considers initializations that are quite far from Pavlov and show that there’s a robust-enough-to-prove path from these initializations to Pavlov. It gives more interesting starting conditions under which the players learn to play Pavlov.\n\nBut then the paper doesn’t really say all that much about these conditions, about why they’re more interesting than the trivial conditions, etc. Even the characterization of the Q values as “optimistic” isn’t really explained.\n2) How was Table 1 picked. It’s natural to pick a single-parameter version of the PD (rather than a fully parameterized one). For instance, a simple one is: playing D gives you 1 and cooperating gives the other player y>1. but the specific parameterization is quite odd. What does g control, intuitively? Also, wouldn’t it be good to be able to arbitrarily control the ratio of gains from cooperation to gains from defection? (y in the above) That way one could think about what happens if this ratio goes to infinity?", "other_comments_or_suggestions": "In cases like the below, it’s nicer, in my view, to give seminal rather than textbook references.\n\n>When the prisoner’s dilemma is infinitely repeated, new equilibria can emerge, and always defect is no longer the dominant strategy (Osborne, 2004).\n\n>A popular approach to maximize the cumulative reward function Equation (1) is to find an action-value function or Q-function, that is a fixed point of the Bellman operator (Sutton and Barto, 2018, Eq. 3.17).\n\n\n>the usual way to deal with multiple agents in reinforcement learning applications (Lowe et al., 2017; Silver et al., 2018; Baker et al., 2019; Tang, 2019).\n\nIt might be worth noting here that this requires symmetry of the game. Also, is this really the usual way to deal with multiple agents in _general-sum_ games?\n\nWhy not write the second math line in the Prop. 2.1 in the same way as the first? Isn’t that shorter and easier to read?\n\n>The main takeaway from Proposition 2.2 is that there exists a fixed point of the Bellman Equation (2) whose associated strategy is cooperative. Interestingly, tit-for-tat\n\nIt would be nice to say something here about the relation between SPE and being a fixed point.\n\n>In this section, we show convergence of the dynamics resulting from ϵ-greedy Q-learning with memory updates (i.e., Equation (3)) toward the cooperative fixed point Pavlov policy.\n\nThe next sentence spells it out, but this sentence alone reads quite weird. Obviously, you can also converge to the “always defect” policies.\n\n>distribution ρ over the initial state space S\n\nThis is a bit awkward, because S is just the regular state space, right?\n\nIn Theorem 3.2, I find this a little confusing:\n>Suppose the initial policy is always defect\nThe version of Q-learning considered here doesn’t take a policy as input. Is this implicitly a constraint on the Q values?\n\nRelatedly in the proof: Why is $Q_{s,D} > Q_{s,C}$ in Phase 1?  This doesn’t follow from Assumption 3.1, right?\n\nIn Algorithm 1: I assume s_t is updated and Alg. 2 is called with the current s_t?\n\n>As opposed to the vanilla Q-learning cases, in which the agents learn to cooperate is not the same, but the resulting policy is.\n\nI’m unable to parse this sentence.\n\nIn the references:\n>Competition Bureau. Big data and innovation: Implications for competition policy in canada.\nCanada should be capitalized!", "questions_for_authors": "1. See item 1 from the “Other Strengths And Weaknesses” section.\n2. See item 2 from the “Other Strengths And Weaknesses” section.\n3. (The second paragraph from “Essential References Not Discussed” also asks questions, but not ones that I expect the authors to answer in the short amount of available time.)", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "fTrIduI9jx", "reviewer": "Reviewer_J2GP", "summary": "This paper studies whether Q-learning algorithm with self-play and one-step memory can lead to collusion in iterated prisoner's dilemma game. The authors characterize the conditions on the initializations, rewards, and discount factor to guarantee that the agents would shift from always defect to Pavlov strategies.", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> Such an approach leads to the claimed Bellman equation (2), which depends on opponent policy \\pi^2. This causes ambiguity due to its dependence on opponent policy. \n\nWe are confused by this statement, as dependence on the opponent's strategy is inherent to multi-agent games—the $Q$-values necessarily depend on the opponent's policy.\n\n> The paper resolves this ambiguity with self-play. However, the self-play causes further issues: -- Both agent has the same Q-function estimate all the time. This is made possible through the update of Q-function only for agent 1. For example, agent 2 does not update Q_{s_t,a_t^2} based on its own action a_t^2 and its own reward r_2. Such an update is not justifiable for a non-cooperative environment such as markets. \n\nWe strongly push back against this claim. Markets are often modeled as cooperative/competitive environments, such as Bertrand games, where the Prisoner’s Dilemma serves as a minimalistic setting. See Calvano et al., Section 3.\n\nReference:\n\n Calvano, Emilio, et al. \"Artificial intelligence, algorithmic pricing, and collusion.\" American Economic\n\n> Assumption 3.1 uses different initializations for different states and actions. This is also difficult to justify if the agents do not know the model. -- If the agents know the model, then it is not justifiable to use Q-learning since they can compute the fixed point directly via dynamic programming.\n\nWe would like to push back against this statement: we explicitly provide a practical way to initalize the $Q$-values to satisfy Assumption 3.1. In this case, all the $Q$-values are the same. The reviewer can refer to the **Q-values Initialization in Practice** paragraph following Assumption 3.1 for further clarification.\n\n> The notation $Q_{s,D}^{\\\\star,\\\\mathrm{Defect}}$ has not been introduced.\n\n\n\n**$Q_{s,D}^{\\star, \\mathrm{Defect}} $ is explicitly defined in Proposition 2.1**:\n\n$ Q_{s, D}^{\\star, \\mathrm{Defect}} =  \\mathbb{E}_{a \\sim \\pi(\\cdot | s)}   r\\_{D, a} /  (1 -  \\gamma)$\n\n$ Q_{s, C}^{\\star, \\mathrm{Defect}} = Q_{s, D}^{\\star, \\mathrm{Defect}} -  \\mathbb{E}_{a \\sim \\pi(\\cdot | s)}  ( r\\_{D, a} -  r\\_{C, a})$\n\n$Q^{\\star, \\mathrm{Defect}} $ is a fixed point of the Bellman Equation that yields an always defect policy in the self-play case.\n\n> Policies such as always defect, Pavlov, Lose-shift have been used before they get introduced in Table 2 at page 3.\n\nTable 2 is now referenced earlier in the text to ensure clarity and avoid confusion\n\n> The use of neural network approximation for such a small-scale problem is not clear.\n\nThe idea of this paper is not to provide large-scale deep RL experiments. The goal of the deep Q-learning experiment part is to see how our findings extend to more complex settings. We think it is especially interesting to see how behaviour transfers from a controlled experiment to a larger, more complex setting.\n\n> Typos: In (2), \\pi must be \\pi^2.\n\nThe typos have been fixed\n\n> Can the authors explain whether agents can follow such an algorithm in non-cooperative environments? Or is this algorithm for introspective computation of a policy to play in non-cooperative environments?\n\nWe are not sure we understand this question. What exactly are you referring to with \"introspective\" and \"our algorithm\"?", "claims_and_evidence": "The paper makes an implicit claim that agents would follow Q-learning algorithm with self-play and one-step memory in the iterated matrix games. However, this claim has not been supported by clear and convincing evidence. Below, I highlight the problematic parts:\n-The algorithm structure shows that agents can observe the state and the state is the previous joint actions of the players. This implies that the agents can observe the opponent actions. Then, it is not clear why they construct the Q-function over their local actions only as if they do not observe the opponent actions. Such an approach leads to the claimed Bellman equation (2), which depends on opponent policy \\pi^2. (The equation has \\pi yet it must be a typo.) This causes ambiguity due to its dependence on opponent policy. The paper resolves this ambiguity with self play. However, the self-play causes further issues: \n-- Both agent has the same Q-function estimate all the time. This is made possible through the update of Q-function only for agent 1. For example, agent 2 does not update Q_{s_t,a_t^2} based on its own action a_t^2 and its own reward r_2. Such an update is not justifiable for a non-cooperative environment such as markets.\n-- Assumption 3.1 uses different initializations for different state and actions. This is also difficult to justify if the agents do not know the model. \n-- If the agents know the model, then it is not justifiable to use Q-learning since they can compute the fixed point directly via dynamic programming.\nIn summary, the algorithm studied is not well-justified from the multi-agent learning perspective. Therefore, the claims drawn are likely to be induced by the artifacts of this not well-designed algorithm rather than an emerging phenomenon for multi-agent learning algorithms.", "methods_and_evaluation_criteria": "The paper provides experimental analysis for the iterated prisoner dilemma with specific reward functions. The paper also includes simulations using deep Q-learning. However, it is not clear why neural network approximation would be necessary for such a small scale problem (with four states and 2x2 actions per state) that can be solved in the tabular form.", "theoretical_claims": "I have not checked the correctness of the proofs but they are intuitive given the carefully crafted initialization and the single-sided update of Q-functions. Indeed, I am more concerned on the justification of these assumptions. For example, why would agents use different initializations for different state-action values. Since agents update their actions based on Q-function estimates with \"small enough\" exploration, carefully crafted initializations can cause bias towards certain action profiles such that the agents play these action profiles only through exploration and therefore they cannot learn their values accurately.", "experimental_designs_or_analyses": "Use of deep Q-learning does not sound for this simple setup.", "relation_to_broader_scientific_literature": "This is a niche problem for the ICML community. This paper would fit better to more specialized domains such as ACM EC.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "The algorithm must be well-justified from a multi-agent learning perspective.\nThe paper needs to improve its problem formulation and notation. \n-For example, the model knowledge and information structure of agents are not clear. \n-The notation Q_{s,D}^{*,Defect} has not been introduced. Is it the fixed point of (2) given that \\pi=defect? Then, (2) should have been defined accordingly. \n-Policies such as always defect, Pavlov, Lose-shift have been used before they get introduced in Table 2 at page 3.\nThe use of neural networks approximation for such a small scale problem is not clear.", "other_comments_or_suggestions": "In (2), \\pi must be \\pi^2.", "questions_for_authors": "- Can the authors explain whether agents can follow such an algorithm in non-cooperative environments? Or is this algorithm for introspective computation of a policy to play in non-cooperative environments?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "WNTX4Xis8z", "reviewer": "Reviewer_t2Hj", "summary": "In this work, The authors prove that multi-agent Q-learners playing the iterated prisoner’s dilemma can learn to collude. The complexity of the cooperative multi-agent setting yields multiple fixed-point policies for Q-learning: the main technical contribution of this work is to characterize the  convergence towards a specific cooperative policy. More precisely, in the iterated prisoner’s dilemma, the results show that with optimistic Q-values, any self-play Q-learner can provably learn a cooperative policy called Pavlov, also known as win-stay, lose-shift policy, which strongly differs from the vanilla Pareto dominated always defect policy.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Authors would like to thank Reviewer LKws for their in-depth comments and very insightful review.\n\n> 1 In recent years, there has been significant progress in algorithmic collusion research, but the authors cited less relevant work from the past year in their literature review. It is recommended that the authors add a review of recent literature to provide a comprehensive picture of the latest research advances in the current field to highlight the innovative nature of this study. In addition, the authors should clearly indicate the differences and innovations of this study from existing studies.\n\nWe would be happy to incorporate additional references to recent work. Does the reviewer have specific papers in mind that they believe are particularly relevant?\n\n> 2 The paper demonstrates that the Q-learning algorithm can converge to a collusive strategy (Pavlov strategy). However, the stability of this collusive strategy in the long run has not been discussed, especially in the presence of external disturbances.\n\n- In the fully greedy case ($\\epsilon = 0$), the $Q$-values ($Q_{CC, D}$ and $Q_{DD, C}$) converge exactly to those corresponding to the Pavlov strategy at equilibrium.\n\n- In the $\\epsilon$-greedy case, we demonstrated convergence with high probability. However, there is still a small, exponentially decaying probability (as $\\alpha$ increases) that the system may deviate from the Pavlov strategy. Specifically, for a fixed horizon $T$, there exists a set of parameters $\\alpha$, $\\epsilon$, and $\\delta$, such that the Pavlov strategy is reached with probability $1 - \\delta$. However, for fixed values of these parameters, there exists a horizon $T$ for which the policy deviates from the Pavlov strategy.\n\n> 3 The paper presents experimental results showing that the Q-learning algorithm converges to the Pavlov strategy and validates the theoretical analysis. However, the experiments only consider a single payoff parameter 𝑔. To enhance the reliability and generalizability of the results, the authors are encouraged to explore variations in the payoff parameters in the experiments.\n\nThe trends for multiple values of $g$ were indeed similar, so we initially reported the results for only one value of $g$ for simplicity. However, to enhance clarity and transparency, we have added graphs with additional values of the incentive to cooperate ($g$) in the Appendix of the revised manuscript. Note that $g$ needs to be large enough for the Pavlov and Lose-shift policies to exist (i.e., $g > 4/3$). Additionally, following Reviewer hUYk's suggestion, we plan to remove the $g$ parameterization in favor of a more general reward parameterization.\n\n> 4 The paper focuses on theoretical proofs, but it does not sufficiently address the potential challenges of applying the algorithm in real-world economic scenarios. Additionally, detecting or preventing collusive strategies in practice is an important issue, and the authors are advised to provide more insights on this topic. Practical value and application prospects.\n\nIndeed, we view this work as an initial step toward understanding collusion in more complex environments, such as Bertrand games, and ultimately developing methods for detecting collusion. However, we believe that addressing these practical challenges is particularly challenging and goes beyond the scope of this paper. We hypothesize that increasing the number of players could make collusion more difficult, although providing a full theoretical analysis of this is currently out of reach.\n\n**Action**: We will cite the proposed relevant literature and add additional values of the incentive to cooperate $g$ in the Appendix.", "claims_and_evidence": "The claims made in the submission are generally well-supported by clear and convincing evidence. The authors provide a thorough theoretical analysis and empirical validation to support their main claims regarding the collusion behavior of multi-agent Q-learners in the iterated prisoner's dilemma.", "methods_and_evaluation_criteria": "The proposed methods and evaluation criteria in this submission can solve the problem of collusion in multi-agent Q-learning within the iterated prisoner's dilemma to a certain extent.", "theoretical_claims": "Yes, I checked the correctness of the proofs for the main theoretical claims, specifically Theorem 3.2 (fully greedy case) and Theorem 3.3 (ϵ-greedy case). The proofs appear to be correct and well-structured. The authors provide detailed derivations and supporting lemmas to demonstrate the convergence of Q-learning to the Pavlov policy. The arguments for the linear convergence rate (Appendix C.2) and the bounds on Q-value deviations (Lemma 3.4) are well-explained and support the main claims effectively.", "experimental_designs_or_analyses": "I checked the soundness of the experimental designs and analyses. The experiments are well-designed to test the theoretical claims, specifically focusing on the convergence of Q-learning to the Pavlov policy in the iterated prisoner's dilemma. The authors use a combination of standard Q-learning and deep Q-learning to demonstrate the robustness of their findings. The experimental setup, including the choice of hyperparameters and the initialization process, is clearly described and appears to be valid. The results are presented in a clear and consistent manner, with multiple runs and seeds used to ensure reliability. The parameter selection in the experiment was relatively single, and the impact of different parameter changes on the results was not shown. Overall, the experimental designs and analyses are sound.", "relation_to_broader_scientific_literature": "The findings relate to economic concerns about algorithmic collusion, extending empirical studies by Calvano et al. (2020) and OECD (2017). The paper provides theoretical evidence that Q-learning agents can learn collusive strategies, contributing to the understanding of tacit collusion in algorithmic pricing. However, the significance of the conclusions obtained in the article in terms of practical applications is not yet clear, and the authors have failed to fully elaborate on their practical value and application prospects. This is a point of improvement in the article.", "essential_references_not_discussed": "In recent years, there has been significant progress in algorithmic collusion research, but the authors cited less relevant work from the past year (2024) in their literature review.", "other_strengths_and_weaknesses": "Strengths:\n1.\tThe paper provides a novel theoretical analysis of collusion in multi-agent Q-learning, specifically in the iterated prisoner's dilemma. It removes restrictive assumptions from prior work (e.g., memoryless settings) and characterizes the dynamics leading to collusion.\n2.\tBy providing a theoretical foundation for observed empirical phenomena, the paper contributes to the broader discussion on algorithmic collusion and its impact on market competition.\n\nWeaknesses\n1.\tWhile the theoretical contributions are strong, the paper could benefit from more discussion on how these findings translate to real-world applications.\n2.\tThe conditions for convergence to the Pavlov policy (e.g., optimistic initialization) may seem restrictive. While the authors provide a detailed analysis, it would be helpful to explore the robustness of these conditions and whether they can be relaxed without compromising the results.\n3.\tThe relevant literature of recent years has not been fully explored; the innovations of the study are not sufficiently prominent.", "other_comments_or_suggestions": "The paper mentions that the self-play assumption is an important premise for proving the convergence of the Q-learning algorithm. However, self-play may lead to agents learning only a single strategy, which may not fully reflect real-world scenarios. In the real world, agents may encounter opponents adopting different strategies. Therefore, if the self-play assumption is neglected, can the algorithm still achieve collusive behavior?", "questions_for_authors": "1.\tIn recent years, there has been significant progress in algorithmic collusion research, but the authors cited less relevant work from the past year in their literature review. It is recommended that the authors add a review of recent literature to provide a comprehensive picture of the latest research advances in the current field to highlight the innovative nature of this study. In addition, the authors should clearly indicate the differences and innovations of this study from existing studies.\n2.\tThe paper demonstrates that the Q-learning algorithm can converge to a collusive strategy (Pavlov strategy). However, the stability of this collusive strategy in the long run has not been discussed, especially in the presence of external disturbances.\n3.\tThe paper presents experimental results showing that the Q-learning algorithm converges to the Pavlov strategy and validates the theoretical analysis. However, the experiments only consider a single payoff parameter 𝑔. To enhance the reliability and generalizability of the results, the authors are encouraged to explore variations in the payoff parameters in the experiments.\n4.\tThe paper focuses on theoretical proofs, but it does not sufficiently address the potential challenges of applying the algorithm in real-world economic scenarios. Additionally, detecting or preventing collusive strategies in practice is an important issue, and the authors are advised to provide more insights on this topic.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This submission received four expert reviews, with an initial disagreement on whether the paper properly addresses the multi-agent setting that it studies. All reviewers acknowledged the rebuttal and most engaged in a very lively and creative discussion about it. After receiving the authors' responses on multiple queries, the panel concluded that the paper will make a useful contribution to the MARL literature provided that some ambiguities are clarified which is expected to be the case for the camera-ready. The main confusion stemmed from the way in which the initial version of the paper motivated and, subsequently, resolved the tension between independent MARL, collusion incentives and self-play. In the process, some other minor issues were fixed (e.g., missing assumptions in certain statements) which were also addressed during the reviewing period.

In sum, the paper benefited from useful comments and suggestions from four expert reviewers who went above and beyond to discuss the paper and reach a fair evaluation. While the initial version had some important flaws, mainly in presentation, the panel is confident that the post-review version addresses these issues and will make a solid contribution - which was already present in the initial, submitted version - to the MARL literature.
Decision: Accept (poster)