Source-linked AI summary
On the Impossibility of Learning to Cooperate with Adaptive Partner Strategies in Repeated Games
Robert Loftin, Frans A. Oliehoek
TL;DR
Learning to cooperate is difficult when an unknown partner can adapt to the learner, while existing approaches often rely on restrictive assumptions about partner strategies. The paper proves that guaranteed cooperation is impossible in some repeated games and discusses alternative constraints based on rational adaptation.
Problem
The paper asks whether an agent can reliably cooperate with an unknown partner that adapts to its behavior without restrictive assumptions about that partner’s strategy.
Source: §1 · p. 1Method
Results
In some infinitely repeated matrix games, no adaptive strategy can always match the average payoff available with knowledge of Bob’s strategy.
Source: §1 · p. 1Takeaways & Limitations
The results motivate theoretical frameworks that account for the intentions behind other agents’ adaptive behavior.
Source: §7 · p. 9The proposed cognitive-hierarchy alternative requires bounding the maximum level k of Bob’s strategy.
Source: §6 · p. 9
Abstract
from arXiv · showhide
Learning to cooperate with other agents is challenging when those agents also possess the ability to adapt to our own behavior. Practical and theoretical approaches to learning in cooperative settings typically assume that other agents' behaviors are stationary, or else make very specific assumptions about other agents' learning processes. The goal of this work is to understand whether we can reliably learn to cooperate with other agents without such restrictive assumptions, which are unlikely to hold in real-world applications. Our main contribution is a set of impossibility results, which show that no learning algorithm can reliably learn to cooperate with all possible adaptive partners in a repeated matrix game, even if that partner is guaranteed to cooperate with some stationary strategy. Motivated by these results, we then discuss potential alternative assumptions which capture the idea that an adaptive partner will only adapt rationally to our behavior.
1. Introduction
The paper asks whether an agent can reliably cooperate with an unknown adaptive partner, and argues that existing assumptions are often too restrictive. It proves a limit on guaranteed cooperation and discusses alternative constraints on partner adaptation.
1. Introduction
- The paper argues that existing approaches rely on assumptions too restrictive for many realistic settings and suggests constraints based on partners adapting rationally to the shared goal.The introduction points to rational adaptation as a possible alternative to bounded-horizon assumptions.Source: §1 · pp. 1–2
- When joint tasks have multiple incompatible solutions, choosing one component of an optimal strategy may fail, motivating adaptation to Bob’s observed behavior.That subjective-learning approach is problematic when Bob can also adapt to Alice.Source: §1 · p. 1
- In some infinitely repeated matrix games, no adaptive strategy can always match the average payoff available with knowledge of Bob’s strategy; even fictitious play can violate bounded-horizon assumptions.The paper contrasts this with prior guarantees that assume Alice can evaluate strategies over a bounded time horizon.Source: §1 · pp. 1–2
2. Preliminaries
The paper studies Alice learning to cooperate with an unknown Bob in an infinitely repeated matrix game. It formalizes strategies over histories and evaluates them by Alice’s long-run expected average payoff.
2. Preliminaries
- The setting is an infinitely repeated matrix game with finite action sets, a known payoff matrix for Alice, and an otherwise arbitrary unknown strategy for Bob.Alice’s stage payoff lies in [0, 1], and the main results do not explicitly consider Bob’s payoffs.Source: §2 · p. 2
- Alice’s and Bob’s behavioral strategies map every finite history to a probability distribution over their respective actions.The paper defines strategies for all histories, including histories that occur with probability zero.Source: §2 · p. 2
- Strategies are evaluated using the infinite-time limit inferior of Alice’s expected per-stage payoff, since the average-payoff limit may not exist.The payoff can also be conditioned on a history of play.Source: §2 · p. 2
- The formal probability model uses infinite paths of play and the natural filtration generated by histories up to each stage.Probability measures are induced by the two strategies and may be conditioned on a history.Source: §2 · p. 2
3. Related Work
Prior work spans practical coordination methods, Bayesian models, and single-agent learning against non-stationary partners. These approaches trade off scalability and efficiency against assumptions about partner strategies and their adaptation.
3. Related Work
- Deep reinforcement-learning approaches often assume near-optimal partners, selecting part of an optimal joint solution or strategies effective across synthetic or learned partner models.Other methods address specific coordination challenges such as task symmetries, asymmetric roles, and conventions.Source: §3 · p. 2
- Bayesian and rational-learning approaches model partner strategies through latent states or priors, but specifying priors that include partners’ learning can be difficult and circular.Rational learning may require Alice’s prior to assign positive probability to Bob’s true belief about Alice’s strategy, which depends on Alice’s prior.Source: §3 · pp. 2–3
- Single-agent methods such as non-episodic POMDP learning and strategic experts evaluate strategies over expanding horizons, assuming a fixed or slowly growing evaluation window.The paper notes that this assumption may fail when partners use equally capable learning algorithms.Source: §3 · p. 3
4. Adaptive Regret
The section defines adaptive regret for learning against partners whose actions depend on Alice’s behavior, then examines assumptions that might make no-regret learning possible. It shows that even the weaker open-endedness condition does not guarantee performance matching the best expert.
4. Adaptive Regret
- Adaptive regret compares Alice’s payoff with the best expert played from the beginning, unlike external regret, which assumes Bob’s actions would remain unchanged under that counterfactual.The learning objective is to minimize worst-case adaptive regret over Bob’s possible strategies.Source: §4 · p. 3
- In the grim-trigger example, neither strategy can guarantee payoff 2 against both partner strategies; Alice’s best option is to randomize equally between the two actions.Each partner switches permanently to a punishment action if Alice chooses the other action.Source: §4 · p. 3
4.1. Flexible Strategies
- Flexibility requires a fixed evaluation horizon that estimates each expert’s long-run payoff independently of history, but this excludes fictitious play in some fully cooperative games.Bounded-horizon guarantees also underlie several existing no-regret approaches.Source: §4.1 · p. 4, §4.2 · p. 4
4.2. Open-Ended Strategies
- Open-endedness is weaker than flexibility, covers fictitious play in fully cooperative finite-action games, and guarantees payoff µe if Alice commits to expert e forever.That commitment guarantee alone does not ensure an algorithm can match the best expert against every open-ended partner.Source: §4.2 · p. 4
- For some N×N repeated games with finite expert sets, every learning algorithm can face an open-ended partner that yields lower expected average payoff than the best expert; regret can approach 1/2.The result holds for N ≥ 3 and sufficiently small δ.Source: §4.2 · pp. 4–5
5. Impossibility Results
The section shows that open-ended partners can frustrate no-regret learning in repeated coordination games, even when a learner commits to an expert or keeps exploring. It then extends the analysis to open-ended regret and discusses a computability boundary.
5.3. Proof of Theorem 4.7
- For any learning algorithm, an open-ended partner can prevent Alice from matching the best fixed-action expert in an N×N coordination game.The proof treats passive and active learners separately before addressing the general case.Source: §5 · p. 5, §5.3 · p. 8
5.1. Passive Algorithms
- Passive learners can suffer non-zero regret against a constructed open-ended partner in a coordination game.Passive learners eventually commit to one expert; the partner is constructed to exploit that commitment.Source: §5.1 · p. 5
5.2. Active Algorithms
- Active learners that never stop exploring can suffer positive adaptive regret against an open-ended partner.A partner can exploit the learner’s finite evaluation horizon by withholding information about an expert’s long-term performance.Source: §5.2 · pp. 6–7
5.3. Proof of Theorem 4.7
- The section’s results cover algorithms that randomize between passive and active behavior by combining partner strategies for those cases.The proof uses the probability that Alice fails to converge when facing the uniform random strategy.Source: §5.3 · p. 8
5.4. Open-Ended Regret
- Open-ended regret avoids penalizing initial mistakes by comparing Alice’s payoff with what an expert can guarantee from any history.Its expert-payoff term considers histories that may be unreachable, so open-ended regret can be negative even when the expert’s expected payoff is at least Alice’s.Source: §5.4 · p. 8
5.5. Computability
- For algorithms that can be neither passive nor active almost surely, the predictive partner strategy may be non-computable.The paper leaves open whether a computable learner can guarantee no adaptive regret against all computable open-ended partners.Source: §5.5 · pp. 8–9
6. Rational Adaptation
The section proposes constraining adaptive partners through rationality assumptions about their strategy or beliefs. It outlines computational rationality and bounded cognitive hierarchies as possible models.
6. Rational Adaptation
- Computational rationality makes Bob’s strategy a best response to his belief about Alice, with machine size breaking ties in favor of the simpler strategy.Strategies are represented as finite-state machines or Turing machines in a machine game.Source: §6 · p. 9
- A cognitive hierarchy models level-k strategies as best responses to beliefs over strategies at lower levels.The paper proposes bounding the maximum level rather than Bob’s memory or evaluation horizon.Source: §6 · p. 9
- A bounded hierarchy can admit complex adaptive strategies while potentially ruling out strategies that are not best responses to any plausible Alice strategy.The paper leaves development of regret-guaranteeing algorithms under hierarchical or computational rationality for future work.Source: §6 · p. 9
7. Conclusion
The paper concludes that guaranteed cooperation with an arbitrary repeated-game partner is impossible, even if that partner forgives the learner’s mistakes. It presents this result as a starting point for theoretical frameworks that account for adaptive partners’ intentions.
7. Conclusion
- No algorithm can be guaranteed to learn to cooperate with an arbitrary repeated-game partner, even when the partner forgives the learner’s mistakes.The conclusion frames this as a limit on reliable cooperation under unrestricted partner behavior.Source: §7 · p. 9
- The results are presented as a starting point for frameworks that account for the intentions behind other agents’ adaptive behavior.Source: §7 · p. 9
- The authors hope future algorithms will be robust to adaptive and non-adaptive partners without relying on unrealistic assumptions.Source: §7 · p. 9
A. Proof of Proposition 4.5
The proof concludes that Bob’s strategy is open-ended with respect to the expert set.
A. Proof of Proposition 4.5
- The proof establishes that each expert’s expected payoff under Bob’s strategy, conditional on any history, equals its corresponding value μe.Source: A. Proof of Proposition 4.5 · p. 11
- The argument uses both the forward and reversed inequalities to establish the payoff equality.Source: A. Proof of Proposition 4.5 · p. 11
- That equality implies Bob’s strategy is open-ended with respect to the expert set.Source: A. Proof of Proposition 4.5 · p. 11
B. Proof of Proposition 4.6
The proof shows that against fictitious play, committing to any fixed-action expert eventually gives Alice that expert’s maximum payoff, from any initial history.
B. Proof of Proposition 4.6
- The proof tracks the empirical distribution of Alice’s actions and defines each expert’s maximum payoff against a best response.It also defines the minimum regret of Bob’s suboptimal pure responses to that expert.Source: B. Proof of Proposition 4.6 · p. 11
- Fictitious play chooses a best response to the preceding empirical distribution, so a suboptimal response becomes untenable once the followed expert has enough mass.The proof concludes Bob switches to a best response within a finite number of stages and stays there while Alice continues with the expert.Source: B. Proof of Proposition 4.6 · pp. 11–12
- Fictitious play eventually best-responds to any fixed-action expert Alice follows, and does not switch away while she continues playing it.Thus the expert’s payoff against fictitious play equals its maximum payoff from any history.Source: B. Proof of Proposition 4.6 · pp. 11–12
C. Proof of Lemma 5.2
The proof establishes measurability of Alice’s convergence events, then uses boundedness and dominated convergence to obtain a finite stage bound on non-convergence probability.
C. Proof of Lemma 5.2
- For each stage, an indicator records whether Alice has converged to a fixed action; countable unions and intersections make these events measurable.The limiting event that Alice converges is measurable as well.Source: C. Proof of Lemma 5.2 · p. 12
- Because the convergence indicators are bounded, dominated convergence permits exchanging their limit and expectation when selecting τ.The indicator of non-convergence is one minus the convergence indicator.Source: C. Proof of Lemma 5.2 · p. 12
- The proof shows that the probability Alice has not converged by some finite stage τ is less than γ + δ, for any δ > 0.The bound follows from the convergence indicator construction and dominated convergence.Source: C. Proof of Lemma 5.2 · pp. 12–13
D. Proof of Lemma 5.5
The proof constructs measurable indicators for future action switches and uses boundedness and dominated convergence to obtain a finite horizon satisfying Equation 30.
D. Proof of Lemma 5.5
- The proof first uses measurability of the event that Alice eventually converges, then defines indicators for whether her action changes within the next s stages.The indicator is 1 when a switch occurs in that window and 0 otherwise.Source: D. Proof of Lemma 5.5 · p. 13
- Boundedness of the indicators allows dominated convergence in the conditional argument for histories with positive probability.This yields the finite horizon σ used in the lemma’s Equation 30.Source: D. Proof of Lemma 5.5 · p. 13
- For any positive-probability history h and δ > 0, the proof obtains a finite σ satisfying Equation 30.The argument uses bounded switch indicators and dominated convergence.Source: D. Proof of Lemma 5.5 · p. 13