Learning to Steer Learners in Games

We thank the reviewer for the careful assessment and constructive critiques, which is essential for us to further improve our work. We give section-wise responses and clarifications to the mentioned issues.

Essential References Not Discussed:

"The authors might also consider referring to 'AN INFORMATION-THEORETIC APPROACH TO MINIMAX REGRET IN PARTIAL MONITORING', Lattimor, Szepesvári, 2019 after Definition 5.1. The idea and analytic purpose of $C_a$ in the reference and of E_i are very similar (identical in definition)."

Thank you for pointing out the references. The definition of $C_a$ is indeed conveying the same information of characterizing the region of point against which a specific action is a best response, and their discussions on the intuition behind $C_a$ and the illustrations in the appendix also work for our definition of facets. We will add this work into citation in our revised version.

Other Strengths And Weaknesses:

"... I find the use of asymptotic notation and early switch to this in the proofs a bit dangerous. There are some steps I can not see/verify from the proofs due to early hiding of the constants or since some dependencies are not shown explicitly. (Please, see question to the authors). I am happy to revise my evaluation if my concerns are addressed."

Here we present the exact bounds for the following theorems, in Theorems 5.4 and 5.15 the learner regret bound is indicated by $Cf(T)$:

Theorem 5.4: $\epsilon>0$ is a constant that depends on $B$, please see our reply to (Comment 1) in Other Comments Or Suggestions section to Reviewer abnn for details.

$$\left(Td_1+\frac{2Cf(T)}{\epsilon d_2}\right)\|A\|_{\max};$$

Theorem 5.15:

$$\left(4(\|d _i(\mathcal{B},\hat{\mathcal{B}})\| _{\infty} T+\sqrt{Tf(T)}) Sen((\mathcal{B} _{i^*}^\circ)^T) +\frac{C\sqrt{Tf(T)}}{\max _{j,k} \|B(e_j-e_k)\| _\infty}\right)\|A\| _{\max};$$

For the two theorems below, we assume the adjusted learner regret rate after the exploration phase is indicated by $Cf(T)$, see response to Reviewer abnn and Lemma E.1 for details.

Theorem 6.2: If there exists a strictly dominated action, let $\epsilon_1=\min_{x\in\Delta_m} x^T B(e_1-e_2)$,

$$\left(4+\frac{C}{\epsilon_1}f(T)\right) \|A\|_{\max};$$

Otherwise, $\epsilon_2>0$ is a constant that depends on $B$ (as a result of Theorem 5.4) and $d$ is a tunable parameter of the algorithm (see Questions For Authors section):

$$\left(-2\log d+5+Td+\frac{2Cf(T)}{\epsilon_2 d}\right)\|A\|_{\max};$$

Theorem 6.3: Here $k=\left(T/g(T)\right)^2 2R^2\log(2mn/\delta)$, $g(T)=o(T)$ is a tunable parameter of the algorithm deciding the length of exploration rounds,

$$\left(m\left(1+k\right)+4(g(T)+\sqrt{Tf(T)})Sen((\mathcal{B} _{i^*}^\circ)^T)+\frac{C\sqrt{Tf(T)}}{\max _{j,k} \|B(e_j-e_k)\| _\infty}\right)\|A\| _{\max}.$$

We will include a version of our theorems in the detailed format with exact bounds in our revision. For the usage of asymptotic notations, please also refer to our reply to (Comment 2) in Other Comments Or Suggestions section to Reviewer abnn for details.

Other Comments Or Suggestions:

"In Appendix E, equation (104) and following, it should be $T$ not $\infty$ ?"

Thank you for pointing out, this is a typo and we will correct this in the revision.

Questions For Authors:

"How is $d$ related to $\epsilon$ in the proof of Theorem 6.2? In particular, how is it ensured that $\epsilon$ is a constant, although $\epsilon$ depends on $d$ and $d$ depends on $T$? ..."

We apologize for causing the confusion. Here $d$ is an accuracy margin that is used as an adjustable input to Algorithm 1 which we didn't mention in the main body. The idea is that we do binary search until we have identified the boundary of the facets by an accuracy level of at most $d$. We then stick to the pessimistic Stackelberg equilibrium for the remaining time steps, paying a total cumulative regret of $dT$. The statement between Lines 1412 and 1414 is indeed confusing, and from which "... the assumption that each facet has length at least $d$ indicates that ..." should be deleted from this sentence. What we are trying to say is that since $e_2$ is strictly dominated, we would have $x^TBe_1-x^TBe_2>0,\forall x\in\Delta_m$, so that such constant $\epsilon$ exists and is only dependent on $B$ instead of $d$.

The reason why we leave $d$ in the big $O(\cdot)$ notation is that we want to leave some freedom for choosing $d$ as a function of $T$ for different $f(T)$. For example if we choose $d=\sqrt{f(T)/T}$ the regret bound would be $O(2\sqrt{Tf(T)}+\frac{1}{2}\log\left(\frac{T}{f(T)}\right))$. Here we omit the result $O(f(T))$ obtained in the case where one facet is empty because $O(\frac{f(T)}{d}+dT-\log d)$ is always $\Omega(f(T))$ as long as $f(T)$ is $O(T)$ no matter what $d$ is chosen.

Thank you for recognizing and pointing this out. We will make the above point clear in the revision.

We sincerely appreciate the great amount of time and thought the reviewer has invested in evaluating our manuscript. We are grateful for the precise recognition of our contribution and novelty, and the insightful feedbacks allowing us to refine and improve our work. We address each concern section-wise below:

Essential References Not Discussed:

"(Minor weakness 1)..."

Thank you for mentioning the related works and your interpretation. While both mentioned works considered potential suboptimal learner responses, neither considers unknown (or up to a small error) learner utility. We would especially like to highlight the difference between our work and Gan et al., 2023, which also considered a region of $\delta$-optimal response, where the learner's action is with suboptimality at most $\delta$. Although being in a similar to the definition of pessimistic facet in Definition 5.7, their definition relies on the real underlying payoff matrix $B$ when defining the region, compared to our definition that uses the estimated payoff matrix. This is saying, that the boundary of their $\delta$-optimal region would be parallel to the real underlying $0$-optimal response region, making their bound easier and more straightforward compared to that in our work. The mismatch in boundary direction in our work requires us to come up with a novel proof of Lemma 5.14 in Appendix C.4, which links the optimistic/pessimistic value difference to the real underlying learner payoff through Definition 5.13, which in our opinion is both a conceptual and technical contribution of our work. We will cite these works and provide further discussion in the revision.

Other Strengths And Weaknesses:

"(Minor weakness 2) ..."

We impose the assumption $n=2$ because only in this case can we apply binary search on facet estimation. For $n>2$ case, our method wouldn't directly apply because there could be infinitely many ascent direction for $n>2$, and thus the difference between $y_{t+1}$ and $y_t$ no longer fits the binary search algorithm. This is the main reason why we neede more structure in the follower's algorithm as in the section on Mirror Descent. For the assumption of knowing the regularizer, please refer to Questions for Authors part of our reply to Reviewer r9Wp for details.

Other Comments Or Suggestions:

"(Comment 1) ..."

Thank you for raising this point. First, we would like to specify that $\epsilon>0$ is encoded within the condition $\inf_{x\in E_{i}^-,x'\in E_j} \Vert x-x'\Vert_1 \geq d_2$, which essnetially suggests that each point in $E_i^-$ is at least $d_2$ away from other facets. More specifically, this means in line 795, $x^-$ is not in $E_j$ for all $j\neq i^-$, and by definition of $E_j$, $\exists j'$, s.t. $(x^-)^TBe_j<(x^-)^TBe_{j'}$. Since such existence of $j'$ holds for all $j\neq i^-$, we can deduce that $(x^-)^TB e_{i^-}-(x^-)^T B e_j>0, \forall j\neq i^-$. For those $j$ where $E_j=\emptyset$, since here $d_2$ satisfies $d_2\leq 2$, we can take $\epsilon_1=\frac{1}{2}\min_{x\in\Delta_m,j\neq i^-}\{x^TB e_{i^-}-x^T B e_j\}$ such that equation (44) holds, which is indeed similar to the inducibility gap defined in Definition 5.9 but we are only taking minimum over those $j$ with empty $E_j$, automatically satisfying $\epsilon_1>0$. For other $j$ since $x^-$ is at least $d_2$ away from $E_j$, there must be a constant $\epsilon_2> 0$ such that $(x^-)^TB e_{i^-}-(x^-)^T B e_j\geq \epsilon_2 d_2$. We proceed the proof by taking $\epsilon=\min \{\epsilon_1,\epsilon_2\}$.

"(Comment 2) ..." "Regarding both comments..."

The purpose of allowing a constant scale is that we want to:

1). Focus on the asymptotic behaviour of the learner's algorithm;

2). Highlight the rate at which the regret is growing in the bound;

3). Keep the $f$-no-regret property invariant when dealing with the same interaction sequence in the same equivalence class.

Our purpose 2) requires the definition of $f$-no-regret itself does not contain any asymptotic notation, and our purpose 1) requires any optimizer's exploration phase that is of length $O(f(T))$ won't affect the overall $f$-no-regret property of the learner (see Lemma E.1), which is essential to our proofs of Theorems 6.2 and 6.3. Even if we modify the definition to $Reg_2\leq f(T)$ without the constant, the exploration phase would still induce another constant $C'>C$ which will appear in the final bounds in Section 6 since we have to use Lemma E.1.

"(Typo)(Small issue 1)(Small issue 2)"

Thanks for pointing out the typo and these issues. We will fix them in the revision.

Questions For Authors

"(Q1) Can you clarify what important constants are hidden in the big $O(\cdot)$ notation in Theorem 5.4, Theorem 5.15, Theorem 6.2, and Theorem 6.3?"

Please refer to our reply in Other Strengths And Weaknesses section to reviewer 2TDF for a more detailed bound without the big $O(\cdot)$ notation.

We would first like to thank the reviewer for thoughtful review and recognition of the novelty in the research topic we proposed. Please find our response listed section-wise below:

Other Strengths And Weaknesses:

"...I find the contribution of Section 6 unclear, where learning to steer to the Stackelberg equilibrium with non-sublinear regret... " "... One could apply an efficient learning algorithm from the literature to infer the follower’s type and then leverage the strategy outlined by Deng et al. (2019) to address the problem... This alternative approach would likely achieve similar performance and theoretical properties..."

There may be some confusion in how we presented our results and we are happy to clarify/simplify the presentation in the revision. We show in Section 6 that the Stackelberg regret is vanishing in both cases. In Theorem 6.2, $d$ is a tunable parameter in our algorithm, indicating the binary search accuracy level. Choosing $d=\sqrt{f(T)/T}$ would yeild a $\sqrt{Tf(T)}$ regret overall. In Theorem 6.3, $g(T)=o(T)$ and thus the regret vanishes asymptotically there as well. We tried to keep our results general but can clarify/instantiate these quantities in the revision to highlight our results.

The goal of section 6 was to give sufficient conditions under which steering a learning agent to a Stackelberg equilibrium is possible (in the sense that the Stackelberg regret is vanishing in time). Our impossibility results hints that this is a hard goal against arbitrary no-regret learers, and so we wanted to understand what further restrictions we could make on the follower for the leader to succeed. To that end, we identified two sub-classes of no-regret algorithms in which our problem can be efficiently addressed: (1). ascending learners in games with two actions, and (2). general mirror descent learners (with known regularizers) in general games. While the class in (1). is quite broad, we could only prove that efficient steering is possible in a limited case. For the class of follower algorithms in (2). we based the case on the observation that by far the most common no-regret algorithm for games in Hedge or multiplicative weights which is an instantiation of mirror descent with a negative entropy regularizer. Our results in this section are positive in the sense that it is possible to exploit learning agents in games under some (often realistic) assuption on their algorithm.

Unfortunately in both of these cases the approach of learning the type and then using results from Deng et al., 2019 is not straighforward. The follower's type is actually their payoff matrix, and learning the follower's mayoff matrix through interaction is highly non-trivial--especially if one would like to do this efficiently and not wait for the follower to converge. Our solution is to make further assumptions on the type of algorithm the follower is using, and then use the strucure to help us learn the payoff matrix. Even this is nontrivial as can be seen in our results in Section 6. Furthermore, even if the optimizer has an approximation of the learner payoff matrix, since the method proposed in Deng et al., 2019 is pessimistic by a unadjustable constant $\alpha$, as long as the learner's payoff structure is not recovered in an absolutely accurate way, directly applying the method in Deng et al., 2019 would either be not pessimistic enough, such that the regret budget of the learner allows it to deviate from the Stackelberg equilibrium far enough to incur a huge Stackelberg regret, or be overly pessimistic, such that the pessimism itself brings a linear Stackelberg regret to the optimizer.

Questions For Authors:

"Can you elaborate on the contribution of non-sublinear Stackelberg regret in Section 6?"

Thank you for raising this question. We would like to emphasize that we are still assuming the learner to be no-regret in both parts in Section 6. More specifically, in Section 6.1, while Definition 6.1 does not imply an ascent algorithm being no-regret itself, we still need the no-regret property for the learner to drive it to an approximate best-response after having learned its paryoff structure. Meanwhile, many online ascent algorithms, e.g. online gradient ascent with proper step size, are themselves no-regret. In Section 6.2, stochastic mirror ascent with proper step size is no-regret as long as its regularizer is strongly convex. We will make a clear statement regarding this in our revision.

Before addressing the concerns, we would like to thank the reviewer for carefully reading the paper, providing insightful feedbacks and pointing out related empirical fields, all being really helpful for improving our work. Pleas find our response listed section-wise below:

Methods and Evaluation Criteria:

"There doesn't seem to be much comparison to other methods..."

To the best of our knowledge, our work is among the earliest to consider the problem of steering a no-regret learner to Stackelberg equilibrium without knowing its payoff structure. The only work close to this setting is Brown et al., 2023 but their method is only able to learn an approximate Stackelberg equilibrium efficiently when the learner is no-adaptive-regret, i.e. the learner regret between arbitrary time intervals should be bounded. Since we are considering a more general setting, establishing a fair comparison between our method and other methods can be challenging.

Experimental Designs Or Analyses:

"There is no empirical evaluation (which I think is a major weakness). It also seems unusual to have knowledge of the regularizer..."

We focus on the theoretical perspective of this problem and our main contribution is both the impossability result and---in light of this--- a few sufficient conditions under which no-Stackelberg regret is possible with provable upper bounds. We are happy to include empirical evaluation to illustrate the effectiveness of our result in the revision. Preliminary results seem to be in keeping with our theory. For the assumption of knowing the regularizer, please refer to Question For Authors part.

Relation To Broader Scientific Literature:

"... it would strengthen the paper to include more big-picture results beyond m = n = 2."

Indeed similar result holds for arbitrary $m$ as long as $n=2$. The idea is to separately treat each edge of the simplex as a special instance of the $2\times 2$ case. See Page 8, Line 428-439 and Appendix E.1 for more discussion. Please also refer to Other Strengths And Weaknesses section of our reply to reviewer abnn for the hardness when $n>2$.

Essential References Not Discussed:

"I would have expected some references to the machine learning communities work on opponent shaping..."

Thank you for pointing out these references. This is a relavant set of ideas that is related, though focuses on a different goal/situation.

For the reference "Foerster, Jakob N., et al. (2017).", they studied 2-player stochastic games with one learner provides conventional policy gradient while the other iterates in a one-step lookahead manner. The reference focus on convergence to equilibria, and assumes the learner has knowledge of the update rule, value functions and gradients of both agents at the current time step, while our work focus on steering the learner to Stackelberg Equilibria only assuming the optimizer knows the regularizer of the learner.

For the reference "Lu, Christopher, et al. 2022.", which considered learning to play against other learning agents strategically, they formulated the meta games of partially observable stochastic games and designed a model-free algorithm that does meta-learning on the constructed MDP. Their work requires resetting the underlying POSG environment, while in our work we assume an online learning process where the optimizer minimizes its Stackelberg regret based on one single gameplay trajectory.

Questions For Authors:

"...whether knowing the opponent's regularizer is a reasonable assumption, or if this can be relaxed..."

This is a very interesting question and something we thought about but were unable to circumvent. Our results give sufficient conditions when steering a learning agent is possible (which in view of our impossibility result is a hard problem in general). To do so we decided to focus on classes of algorithms for the follower that were commonly analyzed and used for learning in matrix games. Towards this we identified that most common algorithms for matrix games are based around the idea of multiplicative weights (or Hedge/exponentiated gradients) which is the result of using the negative entropy as a regularizer. The second other common class is projected gradient descent which results from the use of the $L_2$ Euclidean norm. Against both of these algorithms we showed that efficient steering is indeed possible.

The requirement of knowing the geometry in which the follower optimizes is strong but seems to be crucial for efficiently learning to steer them, since it allows the leader to glean information about $B$ from observation of their consecutive actions (and not have to wait for the follower to converge as in other papers). We believe it is a very interesting open problem whether the follower using mirror descent with arbitrary regularizers inadvertently reveals information about their payoff B in such a fine grained manner.