# Balancing Adaptability and Non-exploitability in Repeated Games

arXiv: https://arxiv.org/abs/2112.10314 · HTML: https://mlsanity.com/paper/2112.10314/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 4 of its 33 references that are in the map.
- First posted on arXiv 20 Dec 2021.

## Builds on (most cited first, 4 of 4)

- [Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processes](https://mlsanity.com/paper/1910.07072/) (2019)
- [Cooperating with Machines](https://mlsanity.com/paper/1703.06207/) (2017)
- [Normative Disagreement as a Challenge for Cooperative AI](https://mlsanity.com/paper/2111.13872/) (2021)
- [Foolproof Cooperative Learning](https://mlsanity.com/paper/1906.09831/) (2019)

## Built on by (most cited first, 1 of 1)

- [Topology Enhanced MARL for Multi-Agent Cooperative Decision-Making of CAVs](https://mlsanity.com/paper/2507.12110/) (2025)

## Abstract (arXiv)

We study the problem of guaranteeing low regret in repeated games against an opponent with unknown membership in one of several classes. We add the constraint that our algorithm is non-exploitable, in that the opponent lacks an incentive to use an algorithm against which we cannot achieve rewards exceeding some "fair" value. Our solution is an expert algorithm (LAFF) that searches within a set of sub-algorithms that are optimal for each opponent class and uses a punishment policy upon detecting evidence of exploitation by the opponent. With benchmarks that depend on the opponent class, we show that LAFF has sublinear regret uniformly over the possible opponents, except exploitative ones, for which we guarantee that the opponent has linear regret. To our knowledge, this work is the first to provide guarantees for both regret and non-exploitability in multi-agent learning.