Self-Play $Q$-Learners Can Provably Collude in the Iterated Prisoner's Dilemma

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.

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

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.

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

Reference:

Calvano, Emilio, et al. "Artificial intelligence, algorithmic pricing, and collusion." American Economic

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.

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

The notation $Q_{s,D}^{\\star,\\mathrm{Defect}}$ has not been introduced.

$Q_{s,D}^{\star, \mathrm{Defect}}$ is explicitly defined in Proposition 2.1:

$Q_{s, D}^{\star, \mathrm{Defect}} = \mathbb{E}_{a \sim \pi(\cdot | s)} r\_{D, a} / (1 - \gamma)$

$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})$

$Q^{\star, \mathrm{Defect}}$ is a fixed point of the Bellman Equation that yields an always defect policy in the self-play case.

Policies such as always defect, Pavlov, Lose-shift have been used before they get introduced in Table 2 at page 3.

Table 2 is now referenced earlier in the text to ensure clarity and avoid confusion

The use of neural network approximation for such a small-scale problem is not clear.

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

Typos: In (2), \pi must be \pi^2.

The typos have been fixed

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?

We are not sure we understand this question. What exactly are you referring to with "introspective" and "our algorithm"?

Authors would like to thank Reviewer LKws for their in-depth comments and very insightful review.

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.

We would be happy to incorporate additional references to recent work. Does the reviewer have specific papers in mind that they believe are particularly relevant?

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.

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

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

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.

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

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.

Indeed, 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.

Action: We will cite the proposed relevant literature and add additional values of the incentive to cooperate $g$ in the Appendix.

Authors would like to thank Reviewer hUYk for their in-depth comments, which have significantly improved the updated version of the manuscript.

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?

The 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).

• 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:

  • In retrospect, we believe their findings differ because policy gradient methods struggle to discover cooperative policies.
  • Barfuss and Meylahn suggest that the absence of self-play does not inherently prevent cooperation from emerging.

• 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. Our perspective:

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

• Oesterheld et al., 2023: 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.

• Hutter et al., 2020: 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.

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.

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

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.

2. How was Table 1 picked?

This 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}$.

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.

Authors would like to thank Reviewer LKws for their in-depth comments and very insightful review.

1 - The authors prove the convergence results for the case of one-step memory. How is this case motivated?

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

Reference: Banchio, Martino, and Giacomo Mantegazza. 2022. "Artificial Intelligence and Spontaneous Collusion."

2 - In the related work section, they also discuss related results for the memoryless case. But what would change if we assume perfect memory?

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

From 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).

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

Axelrod, Robert. "More effective choice in the prisoner's dilemma." Journal of conflict resolution, 1980a Axelrod, Robert. "Effective choice in the prisoner's dilemma." Journal of conflict resolution, 1980b

Foerster, Jakob N., et al. "Learning with opponent-learning awareness." AAMAS 2018

Khandelwal, Urvashi, et al. "Sharp nearby, fuzzy far away: How neural language models use context." arXiv preprint arXiv:1805.04623 (2018).

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.

Yes! We have clear intuitions about the behavior of Q-learning under different initial conditions. For instance,

• 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.
• 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).

Action: These discussions will be added to the revised manuscript.