Is Knowledge Power? On the (Im)possibility of Learning from Strategic Interactions

Thank you for the positive feedback on our work.

same action spaces for all G in the support of D

Yes, we agree with your point. We do require all the games in the support of D to have the same action spaces for both agents to avoid the issue that you proposed. We will make sure to add this clarification to our model section.

the connection of this work with the real world

We agree that our work is mainly theoretical. At this stage, our focus is on providing a different lens for the line of work on learning through strategic interactions, rather than immediate applicability to real-world algorithms. However, we believe our work opens the door to many interesting questions about algorithms in the real world. As highlighted in the second paragraph of our discussion section, one interesting open direction is to understand what natural class of algorithms are supported in meta-game PNE, and what benchmarks are achievable when both players are restricted to these classes. In addition, relaxing some modeling assumptions, such as introducing costly signals or considering computationally bounded agents, can further improve the real-world applicability of our work.

Thank you for the insightful questions.

further clarification on section 3.2, why cannot thee less-informed player estimate the game for the first o(T) rounds and then use the same strategy as the perfectly informed player for the rest of the rounds

Thank you for the question. We believe this is an important note, and we will explain this in more detail in the revision. In particular, let us explain why your proposed algorithm for P2 may not be supported in any PNE. If P2 attempts to estimate the game in the first o(T) rounds, she would need to gather information about the game through repeated interactions with the informed player P1. However, if P2’s Stackelberg strategy as a “perfectly informed player” is not favorable to P1, P1 would have an incentives to deviate to an alternative algorithm that does not reveal any game information to P2 during these o(T) rounds. For example, P1’s alternative algorithm could behave exactly the same regardless of the true game being played. As a result, P2 is no longer able to accurately estimate the game in the first o(T) rounds. This is also the intuition behind our proof of Theorem 3.2, especially those sketched in Line 274-286.

As a result, for P2’s algorithm to be in equilibrium, either she cannot successfully estimate the game, or, even if she manages to estimate it the first o(T) rounds, she cannot deploy the Stackelberg strategy of the estimated game in the remaining the rounds, as P1 would then deviate. In other words, P2 either cannot learn the game or, if she does, she cannot use her learned knowledge to achieve her Stackelberg value benchmark.

insights into why the change in results from $p_1=1$ to $p_1<1$ is non-smooth

Intuitively, when $p_1=1$, the player P1 already has perfect knowledge about the game, so there is no additional information for P1 to learn through interactions. As a result, whether P2 deviates or not does not impact P1’s ability to implement his Stackelberg strategy. However, when $p_1$ is even slightly smaller than 1, there remains a small amount of information that P1 needs to learn from interactions with P2. In this case, P2 could potentially have (though tiny) incentive to deviate to an alternative algorithm that prevents P1 from learning this remaining information, similar to the scenario described in the previous question. In other words, this non-smoothness is inherently similar to the non-smoothness of Nash equilibria generally, as even minimal incentive to deviate from a strategy can disqualify a pair of strategies from being an equilibrium.

On a technical level, our lower bound proof (Theorem 3.2) for the case when $p_2\to1$ relies on constructing game matrices with utilities that scale inversely to $1-p_2$. Specifically, this lower bound construction would no longer be valid if $p_2=1$ because the game needs to be finite.

Thank you for the feedback.

Reason for using Stackelberg value as a benchmark

Thank you for your question. We agree that more information on choosing Stackelberg value as a benchmark will strengthen the paper. We plan to include more details, as we briefly discuss below.

We view our work as providing a different lens on studying learnability in the presence of strategic interactions that also elucidates the context and subtleties of a vast line of prior work in this space. Therefore, we use the benchmark that is primarily studied in this line of work, which by and large, uses the one-shot game's Stackelberg value as the benchmark for the repeated game. Stackelberg value of the one-shot game forms a particularly compelling benchmark to study because it is both achievable and the tightest under some assumptions in prior work [Brown et al.; Haghtalab et al.; NeurIPS'23].

The Stackelberg value is also unique for general sum games, unlike other equilibria classes (such as NE and CE). Hence, the Stackelberg value provides a clean way to show separation between the benchmarks achievable by informed and less-informed players in the meta-game’s PNE.

Which learning classes are used?

We believe there may be a misunderstanding about our setting, as described by the reviewer’s summary. We do not restrict either player to specific learning classes, such as no-regret or no-swap regret algorithms. Instead, we allow both players to choose any algorithm from the entire space of all possible algorithms, as long as they form best responses to each other. In Line 161-163 we define algorithms as sequences of mappings from the player’s information about the game and the historical observations to the (randomized) strategies in the next round. We are intentional in this choice because, as this (see Appendix C) and some prior work show, a pair of no-regret algorithms cannot form an equilibrium with each other. Therefore, to model the long-term behaviors of both agents, we need a much larger and more expressive space of algorithms.

Do the agents' sets of strategies need to be the same?

We interpret the “set of strategies” in your question as referring to the strategies in the meta-game, ie., the long-term strategies or algorithms. Indeed, the set of long-term strategies (i.e., algorithms) is semantically the same for both agents, which is the space of all possible algorithms. In Lines 161-163 of our paper, all algorithms can be written as sequences of mappings from the signal $s_i$ and the historical observations to the strategies that the agents want to use in the next round. The only difference between the two agent’s set of algorithms is that their input signals $s_1$ and $s_2$ may carry different amounts of information.

If your question refers to whether both agents’ sets of pure strategies are the same for all one-shot games G in the support of D, the answer is also yes. This is implicit in our paper, and we will clarify it in future versions.

Technical novelty compared to previous work on strategizing against no-regret learners

Our main contribution is conceptual, providing a framework for interpreting previous work on strategizing against algorithm classes like no-regret, rather than introducing new tools. Our framework results in the following key takeaways:

Takeaway 1: In settings with informational asymmetry, informational advantage can persist throughout repeated interactions. We show this by constructing an instance where no PNE of the meta-game allows the less-informed player to achieve her Stackelberg value. This contrasts previous works that show that it is always possible to learn unknown information and achieve the Stackelberg value when interacting with agents employing specific classes of algorithms. This difference is due to the pair of algorithms considered in previous works not being a PNE of the meta-game and hence having differing levels of rationality.

Takeaway 2: The persistence of informational advantage is because learning and acting based on the learned knowledge are intertwined. We argue that this is not due to the less-informed player being unable to learn the game, but because if she uses this learned information to achieve her Stackelberg value, her opponent would benefit from deviating to a different algorithm that does not reveal knowledge of the game to prevent her from learning.

On the technical front, in our lower bound construction showing that no PNE allows the less-informed player to achieve her Stackelberg value (Theorem 3.2), we use the concept of correlated strategy profiles (CSP) introduced by [Arunachaleswaran, 2024] as a simple sufficient statistic for the average utilities resulting fromdue to pairs of arbitrary algorithms. By using CSPs, we can greatly simplify the analysis, reducing the complexity of the problem from high-dimensional distributions over trajectories to the lower-dimensional distributions over stage game strategy pairs. This simplification enables us to conduct a careful case analysis of the lower-dimensional distribution, identifying the conditions and structures of distributions that can correspond to PNEs in the meta game. Our results provide further evidence that such techniques can be valuable for understanding the trajectories of strategic repeated interactions.

Does the meta-game always admit a PNE?

For the main setting we studied (one player is fully informed), the meta game always admits a PNE. In the proof of Theorem 3.1, we have explicitly constructed a PNE. When both players are partially informed, we suspect that the existence of PNE can be formally established similar to the extensions of the Folk Theorem [Wiseman, Econometrica'05]. We will add a remark to future versions of our paper.

Missing references

Thank you for pointing out these references. We have already cited the first reference, but we will add the second one and any other missing citations to future versions of our paper.

Thank you for your comments and questions.

While the paper discusses the inability of uninformed players to achieve their Stackelberg values, it could provide more insight into the learning dynamics and the rate at which players converge (or fail to converge) to these values.

In our paper, we study the interactions between the informed and uninformed players across a wide range of algorithms, rather than analyzing a specific or parameterized class of algorithms. Because we consider such a broad set of algorithms, we treat the agents’ choices of algorithms as black-boxes. As a result, our primary focus is on determining whether certain benchmarks can be achieved at all, rather than on the learning dynamics or convergence rates.

Nonetheless, when it comes to specific types of interactions that our work addresses, we can provide convergence guarantees using the techniques and results from past work. For example, in demonstrating that the more informed agent can always achieve their Stackelberg value at some PNE (Theorem 3.1), we constructed a pair of algorithms where the informed player (P1) plays strategies close to the Stackelberg strategy and the less informed player (P2) uses a no swap regret algorithm. Implicitly in our proof (see line 627), we show that P1’s convergence rate depends on P2’s swap regret. For example, when P2’s swap regret is of order $\sqrt{T}$, P1’s convergence rate is $O(T^{3/4})$. On the other hand, our negative results show that in no PNE a sublinear convergence to P2’s Stackelberg value is possible.

We will clarify this point further in the revision by adding a remark about the convergence rate after Theorem 3.1.

Main contribution, significance of results, and relation to previous work.

We view our work as providing a different lens on studying learnability in the presence of strategic interactions that also elucidate the context and subtleties of a vast line of prior work in this space. By and large, prior work in this space has attempted to establish the following message: “An uninformed player can always learn to achieve/surpass its Stackelberg value through repeated strategic interactions alone.” At a high level, our work demonstrates the opposite, that “In some cases, an uninformed player cannot learn, through repeated interactions alone, to achieve its Stackelberg value”. Of course, these messages, while both technically sound, are contrary to each other. So, what accounts for this difference?

Our work elucidates that the results of prior work (i.e., that learning does happen) hinge on an asymmetry in the rationality levels of the two agents that interact with each other. That is, the dynamics that are studied in prior work involve pairs of agent algorithms that are not best-response to each other. This lack of rationality confounds the takeaway message of prior work, leaving one to wonder whether it was the lack of rationality of the second agent or some genius of the first agent’s algorithm that enabled the first player to learn from strategic interactions.

The starting point of our work is therefore to consider agents that are rational in their choice of algorithm, which we capture by studying the pure Nash Equilibria (PNEs) of the meta-game that is the repeated interactions between two agents. Through this lens, we show that an uninformed agent may not be able to learn to achieve her Stackelberg value (Theorem 3.2), which is what she could have achieved if she was fully informed (Theorem 3.1).

Let us expand on the above by discussing our paper’s takeaways:

Takeaway 1: In settings with informational asymmetry, informational advantage can persist throughout repeated interactions. We show this by constructing an instance where no PNE of the meta-game allows the less-informed player to achieve her Stackelberg value. This stands in contrast to results from previous work that show that it is always possible to learn unknown information and achieve the Stackelberg value when interacting with agents from specific classes of algorithms. This difference is due to the pair of algorithms considered in previous work not being a PNE of the meta-game, that is, at least one of the agents was not rational in her choice of the algorithm.

Compared to prior work that also argues that the more-informed player can prevent the less-informed player from realizing her Stackelberg value by misrepresenting her private information, we show this in a stronger sense, without making behavioral assumptions on the more-informed player, and instead analyzing the PNE of the meta-game. Therefore, we show that it is the inherent nature of information asymmetry and not any limit on agent rationality that drives the persistence of the informational advantage throughout repeated interactions.

Takeaway 2: The persistence of informational advantage is due to the processes of learning and acting based on the learned knowledge being intertwined. This demonstrates the nuances of why informational advantage persists. We argue that this is not due to the less-informed player being unable to learn the unknown information alone. In fact, in our construction in Theorem 3.2 where the less-informed player is unable to achieve her Stackelberg value, she still does fully learn the game matrix. However, if she deviated to using this learned information to obtain her Stackelberg value, the other player would benefit from deviating to a different algorithm that does not depend on informed player’s knowledge and hence prevents learning the game.

In this work we used the meta-game’s PNE as a way to reflect on the interpretations of previous work on repeated strategic interactions. We hope this framework will be useful for future work to also shed light on natural algorithms that may be used and how this depends on the structure of the game and the forms of information available to each agent.