Chapter 6

Profile Swap Regret, Manipulability, and Response-Based Approachability

In this chapter, we introduce the notion of profile swap regret, which lies in between linear swap regret and full swap regret. A key property of profile swap regret is that it guarantees non-manipulability—in a sense that will be formalized soon—against a dynamic optimizer. What’s more, there is an efficient algorithm for minimizing profile swap regret. This notion was recently introduced by Arunachaleswaran, Collina, Mansour, Mohri, Schneider and Sivan [ACM+25[ACM+25] E. R. Arunachaleswaran, N. Collina, Y. Mansour, M. Mohri, J. Schneider and B. Sivan. (2025). Swap Regret and Correlated Equilibria Beyond Normal-Form Games. Conference on Economics and Computation (EC).], who also provided the first efficient algorithm. In what follows, we present the approach of Anagnostides, Farina, Fishelson, Luo and Schneider [AFF+26[AFF+26] I. Anagnostides, G. Farina, M. Fishelson, H. Luo and J. Schneider. (2026). Swap Regret Minimization Through Response-Based Approachability. Conference on Learning Theory (COLT).], which in turn relies on the response-based approachability algorithm of Bernstein and Shimkin [BS15[BS15] A. Bernstein and N. Shimkin. (2015). Response-Based Approachability with Applications to Generalized No-Regret Problems. Journal of Machine Learning Research, 16, 747–773.].¹1We point the interested reader to https://sites.google.com/view/strategic-learning-ec25 for an adjacent workshop at EC ‘25.

6.1 Setup

We operate in the usual online linear optimization setting. The learner picks strategies from a convex and compact strategy set \(\mathcal{X} \subset \mathbb{R}^{d}\). At every round \(t \in [T]\), the learner first selects a strategy \(\boldsymbol{x}^{(t)} \in \mathcal{X}\); the adversary selects a utility vector \(\boldsymbol{u}^{(t)} \in \mathcal{U} \subseteq \mathbb{R}^{d}\); then the learner receives utility \(\left\langle \boldsymbol{x}^{(t)},\boldsymbol{u}^{(t)} \right\rangle\) and observes \(\boldsymbol{u}^{(t)}\) as feedback. We make the standard normalization assumption \(|\left\langle \boldsymbol{x},\boldsymbol{u} \right\rangle | \le 1\) for all \(\boldsymbol{x} \in \mathcal{X}, \boldsymbol{u} \in \mathcal{U}.\) In what follows, for a utility vector \(\boldsymbol{u} \in \mathcal{U}\), we define the best-response map \(b(\boldsymbol{u}) \in \mathop{\operatorname{arg}\hspace{2.83pt}\operatorname*{max}}\limits_{\boldsymbol{x} \in \mathcal{X}} \left\langle \boldsymbol{x},\boldsymbol{u} \right\rangle ,\) with ties broken arbitrarily.

Linear swap regret. We first recall the benchmark of linear swap regret. An affine map \(\phi : \mathcal{X} \to \mathbb{R}^{d}\) is an endomorphism of \(\mathcal{X}\) if \(\phi (\mathcal{X}) \subseteq \mathcal{X}\). We denote by \(\text{End}(\mathcal{X})\) the set of affine endomorphisms. We write each \(\phi \in \text{End}(\mathcal{X})\) as \(\phi (\boldsymbol{x}) = \mathbf{M} \boldsymbol{x} + \boldsymbol{a}.\) The linear swap regret of the learner after \(T\) rounds is

This is a natural relaxation of (full) swap regret: instead of allowing arbitrary maps, the performance of the learner is compared against affine endomorphisms. In this case, the algorithm of Gordon, Greenwald and Marks [GGM08[GGM08] G. J. Gordon, A. Greenwald and C. Marks. (2008). No-regret learning in convex games. International Conference on Machine Learning.] reduces linear swap regret to external regret over the \(d(d+1)\)-dimensional set of deviations. This implies an online algorithm with linear swap regret growing as \(O(d \sqrt{T})\), which is information-theoretically optimal [AFF+26]. On the other hand, the algorithm of Gordon, Greenwald and Marks [GGM08] is computationally inefficient [DFF+25[DFF+25] C. Daskalakis, G. Farina, M. Fishelson, C. Pipis and J. Schneider. (2025). Efficient Learning and Computation of Linear Correlated Equilibrium in General Convex Games. Symposium on Theory of Computing (STOC).]. This lecture will cover an approachability framework that circumvents this computational barrier.

Correlated strategy profiles. A basic object in the approachability formulation is the correlated strategy profile (CSP). Specifically, for a realized pair \((\boldsymbol{x}^{(t)}, \boldsymbol{u}^{(t)})\), we define \(κ^{(t)} \coloneqq (\boldsymbol{u}^{(t)} ⊗ \boldsymbol{x}^{(t)}, \boldsymbol{u}^{(t)}) \in \mathbb{R}^{d \times (d+1)}.\) The average CSP is

For a CSP \(κ = (\mathbf{K}, \boldsymbol{q})\) and an affine map \(\phi (\boldsymbol{x})=\mathbf{M} \boldsymbol{x} + \boldsymbol{a}\), we use the shorthand notation \(\left\langle (\mathbf{M}, \boldsymbol{a}),κ \right\rangle \coloneqq \left\langle \mathbf{M},\mathbf{K} \right\rangle + \left\langle \boldsymbol{a},\boldsymbol{q} \right\rangle .\) With this notation at hand, linear swap regret can be rewritten as

Using this reformulation, we will shortly see how to reduce minimizing linear swap regret to a suitable approachability problem.

6.2 Profile swap regret and non-manipulability

We now define the notion of profile swap regret and discuss its non-manipulability properties. To do so, we define the instantaneous regret as \(R(\boldsymbol{x}, \boldsymbol{u}) \coloneqq \operatorname*{max}_{\boldsymbol{x}^{∗} \in \mathcal{X}} \left\langle \boldsymbol{x}^{∗} - \boldsymbol{x},\boldsymbol{u} \right\rangle .\) Equivalently, we can write \(R(\boldsymbol{x}, \boldsymbol{u}) = \left\langle b(\boldsymbol{u}) - \boldsymbol{x},\boldsymbol{u} \right\rangle .\) A valid decomposition of \(\overline{κ}^{(T)}\) can be written as

where \(\lambda_{j} \ge 0\), \(\sum_{j=1}^{m} \lambda_{j} = 1\), \(\boldsymbol{x}_{j} \in \mathcal{X}\), and \(\boldsymbol{u}_{j} \in \mathcal{U}\).

The definition is admittedly somewhat cumbersome, but as we shall see it unlocks certain powerful properties. This is a good time to discuss the notion of non-manipulability due to Deng, Schneider and Sivan [DSS19[DSS19] Y. Deng, J. Schneider and B. Sivan. (2019). Strategizing against no-regret learners. Neural information processing systems (NeurIPS).].

6.2.1 Manipulability against a dynamic optimizer

We consider a two-player game between a learner and an optimizer. The learner follows some learning algorithm, whereas the optimizer may choose its actions strategically over time after observing how the learner updates. We let \(u_{ℓ}\) be the learner’s utility function and \(\mathcal{X}\) its strategy set. Similarly, we let \(u_{o}\) be the optimizer’s utility function and \(\mathcal{Y}\) its strategy set.

The key relevant benchmark in this setting is the optimizer’s Stackelberg value, which is the best utility the optimizer can guarantee by committing to a fixed strategy \(\boldsymbol{y} \in \mathcal{Y}\), while the learner best-responds to that strategy (with ties broken in favor of the optimizer):

where \(\text{BR}(\boldsymbol{y}) \coloneqq \mathop{\operatorname{arg}\hspace{2.83pt}\operatorname*{max}}\limits_{\boldsymbol{x} \in \mathcal{X}} u_{ℓ} (\boldsymbol{x}, \boldsymbol{y}).\) The Stackelberg value is what the optimizer can guarantee by means of a static commitment. Informally speaking, a learning algorithm is said to be manipulable if the optimizer can do strictly better than its Stackelberg value by using a dynamic strategy: instead of playing a fixed strategy \(\boldsymbol{y}\), the optimizer chooses a sequence \(\boldsymbol{y}^{(1)}, \boldsymbol{y}^{(2)}, \dots\) so as to steer the learner’s future play toward more favorable outcomes. (It’s interesting to note that this steering problem can be computationally intractable [ADD24[ADD24] A. Assos, Y. Dagan and C. Daskalakis. (2024). Maximizing utility in multi-agent environments by anticipating the behavior of other learners. Neural Information Processing Systems (NeurIPS).].) Equivalently, even if the optimizer fully understands the learner’s algorithm and chooses its strategies dynamically to influence future play, it cannot asymptotically obtain more than what it could already obtain by committing to a fixed strategy.

A beautiful connection crystallized by Arunachaleswaran, Collina, Mansour, Mohri, Schneider and Sivan [ACM+25] reassures us that a learning algorithm that has vanishing profile swap regret cannot be manipulated by a dynamic optimizer.

6.3 Reducing to an approachability problem

Having introduced and motivated the notion of profile swap regret, we now reduce it to an approachability instance. We define \(\mathcal{K} \coloneqq \operatorname{conv} \{(\boldsymbol{u} ⊗ \boldsymbol{x}, \boldsymbol{u}) : \boldsymbol{u} \in \mathcal{U}, \boldsymbol{x} \in \mathcal{X}\}\) and \(\mathcal{S} \coloneqq \operatorname{conv} \{(\boldsymbol{u} ⊗ b(\boldsymbol{u}), \boldsymbol{u}) : \boldsymbol{u} \in \mathcal{U}\}.\) We measure approachability loss by

We first point out that minimizing linear swap regret reduces to this approachability instance.

What’s more, the same target set also captures profile swap regret. The following lemma follows essentially by the definition of profile swap regret.

The profile swap distance of a CSP \(\overline{κ}^{(T)}\) is the infimum Euclidean distance of \(\overline{κ}^{(T)}\) from a CSP with zero profile swap regret. As a result, we conclude that minimizing the approachability loss simultaneously circumscribes both linear swap regret and profile swap regret.

6.4 Response-based approachability

The key observation now is that the induced approachability problem can be solved efficiently through the response-based approachability framework of Bernstein and Shimkin [BS15]. This was recently leveraged by Anagnostides, Farina, Fishelson, Luo and Schneider [AFF+26].

The algorithm proceeds by maintaining the accumulated displacement

At every round \(t\), it solves the bilinear zero-sum game

Let \((\boldsymbol{x}^{(t)}, \boldsymbol{u}_{∗}^{(t)})\) be a pair of minimax strategies for this game. The algorithm then sets

Finally, it plays the strategy \(\boldsymbol{x}^{(t)}\), whereupon it observes the utility \(\boldsymbol{u}^{(t)}\), forms the induced \(κ^{(t)}\), and updates the cumulative displacement \(\mathbf{U}^{(t)}\). All steps can be efficiently implemented through oracle access to \(\mathcal{X}\).

The proof of correctness crucially relies on the minimax theorem, as we formalize below.

The invariant implies approachability by the usual Pythagorean argument.

Applying Lemma 6.6 with \(\boldsymbol{z}^{(t)} = \boldsymbol{s}^{(t)} - κ^{(t)}\) gives

where \(B \coloneqq \operatorname*{max}_{\boldsymbol{x} \in \mathcal{X}, \boldsymbol{u} \in \mathcal{U}} \Vert (\boldsymbol{u} ⊗ \boldsymbol{x}, \boldsymbol{u})\Vert_{F}.\) We thus arrive at the following theorem.

Through suitable preconditioning, it can be shown that this algorithm guarantees optimal linear swap regret [AFF+26]. We further remark that this response-based framework can be extended to nonlinear deviations; we refer the interested reader to Anagnostides, Farina, Fishelson, Luo and Schneider [AFF+26].