Comparator-Adaptive $\Phi$-Regret: Improved Bounds, Simpler Algorithms, and Applications to Games

Q1: In the fast kernelized algorithm (Algorithm 6), I wonder if the computation of $\phi_t$ can be further reduced to matrix multiplication, thus $d^\omega$ time.

This is an excellent question. In fact, we now realize that each $\\phi\_t$ can be computed in $\\mathcal{O}(d^2)$ time (so better than the $\\mathcal{O}(d^3)$ time we provided in Algorithm 6 and also better than what the reviewer suspected, $\\mathcal{O}(d^{\\omega})$). This makes the computational complexity of our algorithm exactly the same as Blum-Mansour and Lu et al. [2025]. We provide the proof below and will update Algorithm 6 this way in the next version. Thanks again for your comment.

First, note that using the definition of $\\phi\_{t+1}$ in Algorithm 6 and the definition of $\\psi^k$, one can verify that the entry of $\\phi\_{t+1}$ takes the following form: if $i\neq j$,
$

(\phi_{t+1})_{ij}= \begin{aligned} \frac{d-1}{c_{t}d(d-2)}(V_t)_{ij}\left(\frac{d-2}{d-1}(C_t)_{ij}+\frac{1}{d(d-1)}(S_t)_i+\frac{1}{d-1}(C_t)_{i,d+1}\right),\end{aligned}
$

if $i=j$,
$

\begin{aligned} (\phi_{t+1})_{ij}= \frac{d-1}{c_{t}d(d-2)}(V_t)_{ij}\left(\frac{d-2}{d-1}(C_t)_{ij}+\frac{1}{d(d-1)}(S_t)_i+(d-1)(C_t)_{i,d+1}\right), \end{aligned}
$

where

• $V_t\\in\\mathbb{R}^{d\\times d}$ is defined by $(V\_t)\_{ik} = \\frac{\\exp(-\\eta(L\_t)\_{ik})}{\\sum\_{j=1}^d \\exp(-\\eta(L\_t)\_{ij})}$ and can be calculated in $\\mathcal{O}(d^2)$ time.
• $c_{t}\\in \\mathbb{R}$ is defined as $\\frac{1}{d} \\sum\_{k=1}^d\\prod\_{i=1}^d\\left((V\_t)\_{ik}+\\frac{1}{d(d-2)}\\Big) + \\prod\_{i=1}^d\\Big((V\_t)\_{ii}+\\frac{1}{d(d-2)}\\right)$. With $V\_t$, $c\_{t}$ can be computed in $\\mathcal{O}(d^2)$ time.
• $C_t\\in\\mathbb{R}^{d\\times (d+1)}$ is defined as follows: for all $k\\in[d]$, $(C\_t)\_{ik} = \\frac{(v\_{t})\_k}{(V\_t)\_{ik}+\\frac{1}{d(d-2)}}$ and $(C\_t)\_{i,d+1} = \\frac{u\_t}{(V\_t)\_{ii}+\\frac{1}{d(d-2)}}$ where $(v\_{t})\_k = \\prod_{i=1}^d((V\_t)\_{ik}+\\frac{1}{d(d-2)})$ and $u\_t = \\prod\_{i=1}^d((V\_t)\_{ii}+\\frac{1}{d(d-2)})$. Again, with $V\_t$, $v\_t$ and $u\_t$ can be computed in $\\mathcal{O}(d^2)$ time, and then $C\_t$ can be computed in $\\mathcal{O}(d^2)$ time too.
• $S\_t\\in \\mathbb{R}^d$ is defined by $(S\_t)\_i = \\sum\_{k=1}^d (C\_t)\_{ik}$ for $i\\in [d]$. With $C\_t$, $S\_t$ can be computed in $\\mathcal{O}(d^2)$ time too.

Therefore, it is now clear that computing $\\phi\_{t+1}$ also only takes $\\mathcal{O}(d^2)$ time.

Thanks for your positive review and valuable comments. We address the issues mentioned in your review below.

Q1: The construction of the prior is interesting, but the paper lacks a clear motivation for introducing it, and it is unclear whether this prior (and the resulting c_\phi) is the best possible choice. While the results presented are fairly comprehensive, the paper would benefit from a more thorough justification of the complexity measure c_\phi. It indeed interpolates between external and swap regret, but it is unclear what precise middle ground it captures. Moreover, c_\phi is defined as the minimum of two complexities, which seems somewhat ad hoc. It would strengthen the paper to provide a justification showing that c_\phi is inherent: for example, demonstrating that for some reasonable class of comparators (lying between \Phi-external/internal and \Phi-best), c_\phi is in fact the best complexity measure achievable.

While we also do not believe that our $c_\phi$ is the ``best'' complexity measure (in the sense that any reasonable algorithms must incur $\mathrm{Reg}(\phi)=\Omega(\sqrt{c_\phi T\log d})$ for all $\phi$), we note that we can at least say that for any integer $k \in [d]$ and any algorithm, there exists a $d$-expert problem and a $\phi$ with $c_\phi \leq k+1$, such that $\mathrm{Reg}(\phi)$ is at least $\Omega(\sqrt{c_\phi T\log c_\phi})$ for this algorithm.

To see this, simply let $d-k$ experts be dummy experts who always have maximum loss $1$, while the other $k$ experts follow the swap regret lower bound construction of Ito [2020] scaled by $1/2$. We then define $\phi$ in this way. First, for a non-dummy expert, $\phi$ maps it to another non-dummy expert optimally (to minimize the total loss after swap). Then, to define $\phi$'s behavior for dummy experts, we consider two cases: in the case where the algorithm picks dummy experts for more than $\sqrt{kT\log k}$ times, we let $\phi$ map all dummy experts to a fixed non-dummy expert (in which case $d_\phi^{\text{unif}} \geq d-k$); otherwise, all dummy experts are mapped to themselves (in which case $d_\phi^{\text{self}} \geq d-k$). Note that in both cases, we have $c_\phi \leq k+1$. Moreover, in the first case, $\mathrm{Reg}(\phi)$ is at least $\frac{1}{2}\sqrt{kT\log k}$ since whenever the algorithm picks a dummy expert $i$, it gets loss $1$ while expert $\phi(i)$ gets loss at most $1/2$ (and the rest of the regret is non-negative by construction). In the second case, $\mathrm{Reg}(\phi)$ is essentially the swap regret of the algorithm for a $k$-expert problem that lasts for at least $T-\sqrt{kT\log k}$ rounds, and since the instance comes from the lower bound construction of Ito [2020], we also have $\mathrm{Reg}(\phi)=\Omega(\sqrt{k\log(k)(T-\sqrt{kT\log k})}) = \Omega(\sqrt{kT\log k})$.

Thank you for your positive review and comments. We address your questions below.

Q1: Given the focus on upper bounds for comparator-adaptive $\Phi$-regret, is it possible to provide a lower bound analysis to establish the optimality of the proposed bounds, especially in relation to the complexity measure $c\_{\phi}$?

We already mentioned in the paper that our bound is optimal for the special case of external/internal/swap regret. In fact, by a simple argument, one can establish the following stronger lower bound as well: for any integer $k \in [d]$ and any algorithm, there exists a $d$-expert problem and a $\phi$ with $c\_\phi \leq k+1$, such that $\mathrm{Reg}(\phi)$ is at least $\Omega(\sqrt{c\_\phi T\log c\_\phi})$ for this algorithm.

To see this, simply let $d-k$ experts be dummy experts who always have maximum loss $1$, while the other $k$ experts follow the swap regret lower bound construction of Ito [2020] scaled by $1/2$. We then define $\phi$ in this way. First, for a non-dummy expert, $\phi$ maps it to another non-dummy expert optimally (to minimize the total loss after swap). Then, to define $\phi$'s behavior for dummy experts, we consider two cases: in the case where the algorithm picks dummy experts for more than $\sqrt{kT\log k}$ times, we let $\phi$ map all dummy experts to a fixed non-dummy expert (in which case $d_\phi^{\text{unif}} \geq d-k$); otherwise, all dummy experts are mapped to themselves (in which case $d_\phi^{\text{self}} \geq d-k$). Note that in both cases, we have $c_\phi \leq k+1$. Moreover, in the first case, $\mathrm{Reg}(\phi)$ is at least $\frac{1}{2}\sqrt{kT\log k}$ since whenever the algorithm picks a dummy expert $i$, it gets loss $1$ while expert $\phi(i)$ gets loss at most $1/2$ (and the rest of the regret is non-negative by construction). In the second case, $\mathrm{Reg}(\phi)$ is essentially the swap regret of the algorithm for a $k$-expert problem that lasts for at least $T-\sqrt{kT\log k}$ rounds, and since the instance comes from the lower bound construction of Ito [2020], we also have $\mathrm{Reg}(\phi)=\Omega(\sqrt{k\log(k)(T-\sqrt{kT\log k})}) = \Omega(\sqrt{kT\log k})$.

Q2: Regarding the kernelized MWU algorithm (Section 4), the paper mentions an $\mathcal{O}(d^3)$ complexity per iteration. How does this complexity impact the algorithm’s scalability for large $d$? Are there practical optimizations considered to handle high-dimensional scenarios?

First, we point out that in response to Review zKH9's comment, we have in fact further improved the time complexity of Algorithm 6 from $\mathcal{O}(d^3)$ to $\mathcal{O}(d^2)$ (see proof therein). So the final per-round complexity of our algorithm is $\mathcal{O}(d^2)+\textrm{FP}_d$ where $\textrm{FP}_d$ is the complexity of computing the fixed point of a $d\times d$ stochastic matrix, which is $\mathcal{O}(d^\omega)$ in theory with $\omega \approx 2.37$, but can be much faster in practice using e.g., power method, as also pointed out by Review zKH9. Importantly, our algorithm is thus computationally as efficient as the classic Blum-Mansour algorithm and also the Lu et al. [2025] algorithm (while enjoying strictly better and more adaptive regret bounds).

Q3: Can the framework be extended to handle heterogeneous agents with different action spaces and loss functions, as encountered in real-world games, and if so, how would the current analysis need to be adapted to accommodate such heterogeneity?

First, we point out that we definitely do not require the same loss functions for different agents, since we are considering general-sum games. Second, as pointed out in our Footnote 4, we assume that the action set size is the same for all players, but that is completely for notational conciseness, and our analysis can be directly extended to games with different action set sizes, with $d$ now representing the maximum action set size among the agents.

Thank you for the very positive review. We address your questions below.

Q1: What are the limitations of extending your results for general sum normal form games?

We use the key nonnegative-social-external-regret assumption to establish a small path-length bound $\mathcal{O}(N\log d)$ of the entire learning dynamic (see Theorem D.7). Without this assumption, in principle, we could also use the fact that swap regret is by definition nonnegative to establish another path-length bound, but it would be larger than $\mathcal{O}(N\log d)$ by some factors of poly$(d)$, making the final bound on $\mathrm{Reg}\_n(\phi)$ at least as large as the best existing bound for swap regret [Anagnostides et al., 2022a,b] even for a $\phi$ with small $c\_\phi$ (and thus vacuous for our purpose).

Q2: Can you elaborate more on the class of games satisfying Assumption~6.3?

While there is no obvious intuitive explanation for this assumption, as argued by Anagnostides et al. [2022c], this class of games is intricately connected with the admission of a minimax theorem. They show (in their Proposition A.10) that all the following standard and well-studied games satisfy this property:

1. Two-player zero-sum game;
2. Polymatrix zero-sum games;
3. Constant-sum Polymatrix games;
4. Strategically zero-sum games;
5. Polymatrix strategically zero-sum games;
6. Convex-concave (zero-sum) games;
7. Zero-sum games with objective $f(x,y)$ such that $$\min\_{x\in \mathcal{X}}\max\_{y\in \mathcal{Y}} f(x,y)=\max\_{y\in \mathcal{Y}} \min\_{x\in \mathcal{X}}f(x,y)$$
8. Quasiconvex-quasiconcave (zero-sum) games;
9. Zero-sum stochastic games.

Thank you very much for your prompt repsonse. I maintain my positive impression of the paper and I keep my score.