Maximizing utility in multi-agent environments by anticipating the behavior of other learners

``While I found that the authors generally explained their approach well, I thought it might have been interesting to give some more explanation, potentially via a concrete example (in the zero-sum case). If this takes up too much space, one could include an example in the appendix.''

We have a few examples (Example 1 in the appendix and the matching pennies game in Proposition 9), and we are happy to include more examples of zero sum games that show what the rewards of the optimizer are.

``Line 106: Should it say $\eta \to \infty$ as $T \to \infty$''

No this is correct as is. Usually the step size is set to be small i.e. $\eta = \frac{1}{\sqrt{T}}$ so increasing $T$ makes $\eta$ go to $0$.

``Typo on line 350: "The details the force the learner"''

Thanks for point that out. It should be "The details of how to force the learner ..."

We thank the reviewer for the useful comments. We answer the main questions below, and move a few minor questions to an official comment, for space considerations.

``It would have been interesting to see some example numerical computations of the optimal strategy in a game and resulting simulated utilities. How much better does the optimal strategy do compared to simple baselines, in some canonical games?''

We are happy to include examples of games and the optimal rewards and strategies of the optimizer for different time horizons $T$ in the new revision of the paper.

``Focusing on MWU and related algorithms makes sense to make the analysis tractable, but it also limits the applicability of the results. Moreover, it would be especially interesting to have an impossibility result for a no regret algorithm.''

Even understanding what happens against specific types of algorithms such as MWU is an elusive open problem (look at paragraph 2 of page 3 of Is learning in games good for the learners), but also understanding what the optimal strategies are against these algorithms will be helpful for the analysis against other no-regret learners. You are right, an impossibility result for no-regret learning algorithms would be extremely interesting, and we leave it open for future work.

``While the computational hardness result is interesting, it does not appear very surprising given typical hardness results in game theory.''

A lot of results in game theory are impossibility results (such as for example computation of several types of equilibria in different games). However, our impossibility result is the first of its kind, as far as we know. That is, our result is the first that states that computing optimal strategies against learners with specific dynamics can be computationally hard, and none of the previous work has talked about any computational issues thus far.

``I wonder whether it would be possible to give a description of the constant optimal strategy in the continuous-time case, in words. How does it relate to the minimax strategy?''

As $\eta T \to \infty$ then the optimal constant strategy will approach a min-max strategy. However, for finite or small $T$ the optimal strategy might be different, depending on the game.

``I assume that even as $T\to \infty$, learners play suboptimally if the temperature $\eta \to \infty$, and so the optimizer would deviate from the minimax strategy somewhat to exploit this. However, is it right that for $\eta \to \infty$, the optimizer strategy would eventually converge to the minimax strategy?''

If $\eta \to \infty$ then the learner is essentially employing fictitious play (best responding to the history). When $\eta \to \infty$, the optimizer is able to take advantage of that by significantly deviating from the min-max strategy. This can also be seen in the way we analyze the computational lower bound and specifically you can view it in the example we provide in the last pages of the paper (p22-23). There, optimizer constantly changes the actions they are playing. The phenomenon where the optimizer has to constantly switch actions can also be seen in the matching pennies example that we also discuss in the paper (Proposition 9). It certainly is the case for matching pennies that the average-time strategy for the optimizer in the scenario where $\eta$ is large will converge to the min-max strategy, however, the per-round strategy is not. It is an interesting question we have not tackled whether the average-time strategy always converges to the minmax strategy.

``Could you say under what conditions the constant $C_A$ in Proposition 4 is small? Does this depend on the inequality in Assumption 1? (i.e., if the two best responses lead to very different utilities, this leads to more possibility of exploitation?)''

Yes, this depends on the inequality in Assumption 1. If the assumption is close to being unsatisfied, then the constant is small. If the assumption is satisfied with a large gap, then the constant is larger, which implies a better lower bound on the utility gained by the optimizer.

``In the related work section, it would be nice to better contrast the discussed related work (especially on no regret learners) to the work in this paper. E.g., MWU is also a no regret learner, but best response isn't? How exactly does this paper extend prior work on exploiting these different learners? E.g., by analyzing computational complexity, or by providing tighter bounds, etc.?''

Thanks for the question. Previous work has introduced the problem of strategizing against no-regret learners, and specifically mean based learners. It has also been shown that in zero sum games against these mean based learners, the best rewards the optimizer can achieve are $T \cdot Val(A) + o(T)$, while in general sum games, it has been shown that the optimizer can get significantly more utility than the one shot game value (which for general sum games is called the Stackelberg value), however no efficient algorithm on how to achieve this value has been found. In our work, we show for zero-sum games what is the exact optimal rewards for the optimizer for Replicator dynamics - one of the most widely used mean base learners. We also show a first computational lower bound for computing the optimal strategy against a learner that is best responding, i.e. MWU with infinite step size. We believe that ultimately the problem of computing an optimal strategy against mean based learners in general sum games is computationally hard, and we give a first result with our lower bound towards that direction. We will add these details in the related work section.

``Why is so much exposition included in the Introduction? Is there a reason for this?''

In theoretical CS papers it is customary to include an informal version of the results in the introduction. We are happy to change the format of the paper for the sake of clarity. For more details, see our response to the primary concern (of the same author) in the official rebuttal.

``The replicator dynamics is defined as a continuous time analogue of the MWU algorithm, but the MWU algorithm itself is not described until later in the paper. This can be confusing for readers, if MWU is not being used, then it should not be introduced earlier. If Replicator Dynamics needs to be described as a generalization or adaptation of MWU, MWU needs to be described first.''

We defined the replicator dynamics first because it makes sense for the exposition to talk about the continuous time dynamics first, and afterwards talk about the discrete time dynamics. The replicator dynamics can be viewed as the continuous time analogue of MWU and MWU can be viewed as the discrete time analogue of the Replicator Dynamics interchangeably. We mention the MWU above, just because it is a well-known algorithm within the theory community, in order to help readers that are familiar with MWU and not with the Replicator Dynamics to make the connection. We will make it clear that the definition of MWU is not necessary in order to understand the replicator dyanmics.

``It would be helpful if n and m are described explicitly as the cardinality of the action spaces of the two players. As it is right now, it is easy to miss when they are first introduced, and later equations (e.g. Eq. 1) rely on the readers knowing what they stand for.''

We will make sure to add clear references for this.

``Line 164: i1, i2 are not described in Proposition 4.''

This is a typo, they are defined in assumption 1, thanks for pointing that out.

``Can you clarify the undefined notation, e.g. $\Delta(A)$?''

$\Delta(\mathcal{A})$ denotes the set of all probability distributions over the set $\mathcal{A}$, i.e. $\Delta(\mathcal{A}) = \\{(x_1, x_2, \dots, x_n) | x_1 + x_2 + \dots + x_n = 1,~ x_1\ge 0, x_2 \ge 0,\dots,x_n\ge 0 \\}$. More specifically in our setting, that is the set of all the mixed strategies for the optimizer. Similarly $\Delta(\mathcal{B})$ is the set of all mixed strategies for the learner, i.e. $\Delta(\mathcal{B}) = \\{(x_1, x_2, \dots, x_m) | x_1 + x_2 + \dots + x_m = 1 \\}$. We will make sure to add these definitions in our paper.

We thank the reviewer for their feedback. We answer below the main concerns, and we answer additional questions in an official comment, due to the space limitations.

``My primary concern with this paper is in the organization and clarity of presentation...'':

We thank the author for their comment about the presentation. We note that in theory papers it is common to have an informal version of the theorems in the introduction, followed by a longer version in the technical sections. Yet, we will change the format in accordance to the reviewer's comments, and we agree with the reviewer that such a change can benefit the paper. Specifically, after the meta question, we will summarize in bullets the main contributions of the paper. Related work will follow. Then, we will write the preliminaries, and afterwards the results, in two sections: (1) optimizing against MWU and (2) a lower bound for optimizing against Best-Response. These will include results that currently appear both in the introduction and in sections 2 and 3.

``Some important details which could be highlighted are missing from the body. For example, the authors don't clearly state the benefit that can be achieved in a zero-sum game by the optimizer, except for the informal statement of proposition 1. This seems to me one of the main contributions of the paper, other than the hardness proof.''

We state the benefit through theorem 1 and propositions 1 to 4 in the introduction. First of all, theorem 1 states that the optimal rewards for the optimizer can be achieved with a strategy that is constant over time (i.e. $x(t) = x^*, 0\leq t \leq T$). In proposition 1 we state exactly the range of possible rewards the optimizer can achieve and what happens when $\eta T \to \infty$. In propositions 2-4 we explain what happens in the games with discrete time dynamics. First of all, the discrete time analogue of a continuous time game will always give more rewards for the optimizer (Proposition 2). This 'gap' in the rewards cannot be more than $\eta T/2$ and there exists a game that approximately achieves this gap, namely matching pennies (Proposition 3). Lastly, we show that up to constant factors, most games also exhibit this reward gap between the continuous and discrete game analogues (proposition 4).

``Can you justify why MWU and Replicator Dynamics are chosen as the model for the learner?''

We chose the MWU algorithm for the learner for several reasons. First of all, it is one of the most well-studied no-regret algorithms due to its optimal regret but also as its continuous time analogue, the replicator dynamics, is extremely well studied in the literature. MWU is also an algorithm that is widely used in online learning settings, therefore knowing how robust or manipulable it can be against strategic players in online settings is an interesting question. We also believe that our view of the problem as a continuous time problem, provides a new perspective on how to view the problem of strategizing against mean based learners (as introduced by [1]).

``Can you clearly state what the novel contribution of the paper is? My current understanding is that the hardness proof is novel, and the polynomial time algorithm for Zero-sum games is novel, and that is all.''

All of the results in our paper are novel, and are the following:

(1) The first set of results concerns zero-sum games where the learner is employing Replicator dynamics (for the coninuous case) and MWU (for the discrete case), as summarized in (1a) and (1b) below:

(1a) We show what is the exact best strategy for the optimizer against a replicator dynamics learner in the continuous time setting by presenting a closed form solution (Theorem 1). We show that this strategy can be efficiently computatble using optimization methods (Proposition 5) and we give a range of possible values that this optimal reward can take (Proposition 6). We also examine what happens in the limit when $\eta T \to \infty$ (proposition 4 and 7).

(1b) For discrete-time games, we show that the optimizer can always get more than the analogous continuous-time game (Proposition 2 / Proposition 8). This gap in the reward cannot be larger than $\eta T/2$ (Proposition 10) and we show a game that achieves that gap almost exactly (Proposition 9). Finally we show that under a condition, there is a large class of games that exhibits this gap between the continuous and discrete time games (Proposition 3 / Proposition 11).

(2) The final result we show is a first computational lower bound for computing the optimal strategy against learners and specifically, against Fictitious play.

We thank the reviewer and respond to the points raised by the review below:

``The authors show that this algorithm, when extended to the discrete-time setting, results in an algorithm that guarantees the optimizer the value of the corresponding one-shot game.''

This is not exactly true. We show that for both the discrete and continuous time settings the optimizer can achieve on average more than the one-shot game. For the continuous time regime we show a closed-form solution (Theorem 3) for the rewards of the optimizer that is always more than $T \cdot Val(A)$ (Proposition 1 / Proposition 6). Moreover, in the discrete game the optimizer can always achieve more rewards than in the analogous continuous game (Proposition 2 / Proposition 8) and we show that for a large class of games the 'gap' is $\Omega(\eta T)$ (Proposition 4 / Proposition 11).

``The informal statements of results in Section 1 could have been made clearer. The current presentation does not allow an easy comparison of results in different settings.''

We will rewrite the statements more clearly and compare them to previous related work in the new revision.

``The results only apply to an MWU learner, not general mean-beased learners, and it relies on the knowledge of $\eta$''

We believe that our result could be extended to the case where $\eta$ is not known in advance -- by an algorithm that learns $\eta$ on-the-go. This was not the focus of our paper and it is left for future work. For optimizing against arbitrary mean-based learners, we do not know if there is a clean solution, and devising an optimal strategy against any mean-based learner might be a very hard research problem (as also discussed by Brown et al., ``Is Learning in Games Good for the Learners?'')

``In the discrete-time setting, the algorithm only guarantees a lower bound. There is no matching negative result.''

We do provide upper and lower bounds, which are tight up to constant factors. Proposition 4 proves that in discrete games, the optimizer cannot obtain more than $\eta T/2$ reward compared to the continuous time analogue (Proposition 3 / Proposition 10). For the positive result, we show that there exists a game where this gain is optimal up to a multiplicative $1+o(1)$ (Proposition 3 / Proposition 9) factor. Furthermore, for a class of games satisfying a mild condition, we show that the optimizer can gain $\Omega(\eta T)$ more reward than the Value of the game in the discrete-time setting (Proposition 4).

``The negative result for the general-sum case only implies it is hard to get reward T-1, so it doesn't preclude the optimizer from obtaining sublinear regret overall. Moreover, fictitious play is a bit simplisitc as it is not no-regret. (However, I think the reduction itself is quite interesting.)''

Both of your observations are correct; our reduction does not prove hardness of approximation of the optimal rewards, and also it is based on the assumption that the learner employs fictitious play (where $\eta \to \infty$). However, we see this lower bound as a first step to possibly unlocking the mystery of the strategization against MWU, that was first introduced by [1] 5 years ago. Many other works (inclduing [2], [3]) have this left as an open problem, and we believe that this problem is computationally hard. Our hardness result is the first in this line of work and we are hopeful that in the future we will be able to prove hardness of approximation and relax the $\eta \to \infty$ assumption.

``It may be clearer to state Assumption 1 as a condition or a property. Stating it as an assumption may make it sound like your result requires additional assumption, while I think the purpose of Proposition 4 is more about showing the existence of games with a utility gap.''

You are right, the point is to show that a certain category of games have a utiity gap between their discrete and continuous time analogues. We will phrase the assumption as a condition instead, for the utility gap to exist.

``Line 362: closed form''

Thanks for pointing the typo out.

``Does the reduction rely on a specific tie-breaking rule, or can the tie-breaking assumption be relaxed?''

Yes, the reduction does rely on the specific tie breaking rule, that is only used however in the first round of the game where the historical rewards of the learner for each action is 0. We did not see a simple way to relax this tie breaking rule, and we leave relaxing this assumption for future work.

``Is there any intuition why the result in Proposition 1 relies on the cardinality of BR(x)?''

The less best responses for the learner there are the longer it will take for the learner to converge from the uniform distribution to that best response. Imagine a game where every action of the learner is a best response; in that scenario the rewards for the optimizer will be exactly $T \cdot Val(A)$. In comparison, in the case where there is only a single best response, the optimizer will gain extra utility because of the time it takes for the learner to learn that best response. The less best responses, the more time it takes to concentrate all the probability for the learner in the best responses and therefore the more utility for the optimizer.

We thank the reviewer and respond to the points raised by the review below:

``In section 1.2 Related Work, authors point out prior work in contracts and auction design, which could also be broadly categorized as mechanism design. Some recent related papers (eg. [1],[2] ) have proposed experimental frameworks to analyze interactions in similar optimizer-learner frameworks, which could be referred to for similar experiment design with repeated games and bandit agents.''

Thank you for pointing out these papers. We will include them in the related work section in the new revision of our paper.

``The connection to optimal control could perhaps be better motivated and explained.''

The optimal control paragraph is explaining how Theorem 1 can be derived using the HJB equation. The problem of strategizing against MWU can be viewed as a control problem where the system has some dynamics (in this case the dynamics of MWU), a utility function (the rewards of the optimizer), and the control which is the strategy of the optimizer. The HJB equation gives a partial differential equation that when solved gives the closed-form solution of Theorem 1. We included it because we think it might be helpful for thinking about the general sum case. The connection of optimizing against learners and control has already been discussed in prior work [24], yet from a different angle and they did not discuss the HJB equation. We will definitely include a more detailed explanation in the new revision of the paper.

``Line 255 and 256: Should it be $R_{cont}(x, h(0), T, A, -A)$ and $R_{cont}^*(h(0), T, A, -A)$?''

You are right, this is a typo. We will fix it in the new revision.

``Line 308: "for each node $v_i$ of the graph, the learner has two associated actions $v_i$ and $v_i'$" - the overloaded use of $v_i$ is confusing.''

We will use a different notation for the actions, thank you for pointing this out.

``I might have missed it, but what is the relation between $h_i(t)$ and $h(t)$? Is it explicitly defined somewhere in the paper?''

$h(t)$ is an $m$-dimensional vector and thus $h_i(t)$ is the $i$-th coordinate of that vector. We will make sure to include it in the definitions.

``Line 164: $i_1,i_2$ are defined in Proposition 4. - Should this instead be $b_1, b_2$ defined in Assumption 1" ?''

You are right, this is a typo. It should be " ... where $i_1, i_2$ are defined in Assumption 1 ...", not in Proposition 4.

``If I understand correctly, the reason why "the learner would have to change actions frequently" (line 153) for the optimizer to get a higher optimal utility, is so that the optimizer can exploit the gain by playing an optimal strategy at every time step? In this paper, for the discrete time dynamics, the learner's strategy is therefore assumed stochastic to ensure that the learner frequently changes actions. What would be the effect of assuming a stochastic learner in the continuous time case?''

First of all there is a typo in that line (153). It should be "the optimizer would have to change actions frequently". Both in the discrete and the continuous dynamics the learner and the optimizer are allowed to play stochastically. To better understand what we mean by the optimizer having to change actions frequently take a look at Proposition 9, which exemplifies the main difference between the continuous and discrete time dynamics. It studies the game of Matching Pennies, both in discrete and continuous-time. For the continuous-time dynamics, the best value the optimizer can get is $0$. This is a consequence of Theorem 3. However, for the discrete time dynamics, it is possible to get $\Omega(\eta T)$ reward for the optimizer. This is achieved when the optimizer switches actions all the time, and then it is possible to gain positive reward, as presented in the proof. Essentially, the main difference between the continuous time dynamics and the discrete time dynamics is that in the continuous case the learner changes the strategy smoothly and therefore cannot be exploited as we can exploit the discrete time dynamics. Intuitively, the learner is ``slower to respond'' in the discrete setting, hence a frequent change of actions from the optimizer could benefit the latter.