Regret Minimization in Stackelberg Games with Side Information

[“The regret bounds for the bandit case are not tight. However I believe the paper provides interesting first results for an interesting problem.”]

We would like to point out that it is actually unclear whether or not an algorithm exists for the bandit settings which achieves better than O(T^{2/3}) regret. While we hypothesize that getting O(T^{1/2}) regret should be possible, the algorithmic ideas used to get O(T^{1/2}) regret in the online Stackelberg setting without side information do not extend to our setting in a straightforward way.

[“What are the main challenges of extending your results in infinite action games with convex structure?”]

Since the leader’s strategy is a probability distribution over actions, one could view the leader as picking from infinitely-many actions. If you are asking about how one would extend our results to settings in which the leader’s strategy is not a probability simplex but is instead some general convex set, the problem becomes more tricky. To generalize to this setting, one would need to be able to reason about how different follower types would best-respond to different leader strategies. One could then hope to leverage the structure of this best-response in order to derive a computationally-tractable algorithm (i.e. in a way analogous to how we use Lemma 4.4).

[“The main impossibility result appears to reply on the fact that the context space is infinite and the model is non-linear w.r.t. the context.” and “Would the impossiblity result change if the context space is finite, or if the players' utility functions are linear w.r.t. the context.”]

We would like to emphasize that most work on learning in contextual settings focuses on the setting where the context space is infinite or large. With that being said, our impossibility result should carry over to the setting where the number of contexts is finite, but exponential-in-T. (This is because the impossibility result for no-regret learning in online linear thresholding carries over to the setting where the adversary can only select from an exponentially-large grid of uniformly-spaced points in [0, 1].)

We would like to clarify that the leader’s utility function is not non-linear with respect to the context in our impossibility result. While we allow non-linear relationships in all of our positive results, the leader and follower utility functions actually have no explicit dependence on the context in our lower bound (see line 518). The intuition for the lower bound is that while the leader’s utility may not explicitly depend on the context, the adversary can “hide” information in the context about the receiver’s type. This ability to “hide” information makes it hard for the leader to compete with the best-in-hindsight policy.

[“The analysis of the relaxed cases (stochastic follower type, or stochastic context) looks fairly standard and the results are expected. So overall the paper is more like an application of existing techniques to a problem motivated by a new context.”]

We would like to clarify that our positive results do not follow from existing techniques. We will update the paper to better explain the technical innovation based on the reviewer’s feedback. There are several reasons why this is not the case. The setting of Section 4.1 (and its bandit analogue) have not been studied in the literature on non-contextual Stackelberg games. As such, there is no existing technique to apply in this setting. Our algorithm in Section 4.2 plays Hedge over a finite set of policies, while previous work on non-contextual Stackelberg games plays Hedge over a finite set of mixed strategies. While the two ideas may seem similar at this level of abstraction, showing that it suffices to consider a finite set of policies (each of which map to a finite set of context-dependent actions) is non-trivial and requires bounding a discretization error which does not appear in the setting without side information. We will update the final version to better explain the technical innovation.

[[On limitations]: “The authors didn't seem to have addressed this explicitly, but the work is theoretical anyway, so this is minor.”]

We discuss (what we view as) the most important limitations of our work (allowing intermediate forms of adversary, better regret rates in the bandit setting) in the Conclusion as directions for future work. However, we would be happy to add further discussion on other limitations in our next revision.

[“The paper would definitely benefit from the addition of numerical experiments or case studies.”]

We hope our numerical simulations address your concerns regarding the lack of experimental results.

[“Could the authors provide more clarity on how the adversarial model for context selection was validated? Are there empirical data or specific scenarios where this model reflects real-world conditions?”]

The common motivation for studying adversarial models in online learning is not that we believe that the data-generating process is adversarial, but that we believe it is not i.i.d. If an algorithm can handle adversarially-generated data, then it can also handle data which is not i.i.d. in some way, while being agnostic as to how the data is generated. In Stackelberg games with side information, there are many examples of settings in which the contexts would not be i.i.d. In the wildlife protection and patrol boat examples, weather conditions for each day are not sampled i.i.d. from some distribution; instead, there is some dependence from day-to-day.

[“How would the author compare the results with existing methods for handling contextual information in game theory, such as...”]

We would like to emphasize that existing methods for handling contextual information (e.g. contextual bandit algorithms, online learning with expert advice) are usually not studied in strategic settings where there is more than a single agent. In general, such single-agent methods would perform poorly in game-theoretic settings, since they do not take the other strategic agents into consideration when making decisions. While our problem may be viewed as a special case of online contextual adversarial learning, applying algorithms for this problem out-of-the-box to our setting generally results in worse regret rates and would require more stringent assumptions on the data-generating process than what we require. (See line 485 for more details.)

Others have also studied various forms of side information in different game settings. We include a discussion on these works in Appendix A.

[“Can the authors comment on how their approach compares to existing methods in terms of computational efficiency...”]

The computational complexity of our algorithms essentially match those for no-regret learning in Stackelberg game settings without contexts (up to small differences in polynomial factors). While both contextual and non-contextual algorithms for no-regret learning in Stackelberg games have exponential per-round complexity, this is unavoidable due to an existing hardness result for the non-contextual setting (see Li et al. [23]). With that being said, we believe that studying special cases of both the contextual and non-contextual settings where efficient learning is possible is an interesting and important direction for future research.

[“How does the proposed algorithm perform if the model of side information is mis-specified? For instance...”]

Thanks for the interesting question. While our impossibility result of Section 3 rules out the ability to learn when the distributions are arbitrarily misspecified, no-regret learning may still be possible under other, intermediary, forms of adversary (such as the one you propose). We highlight this as an interesting direction for future work in Section 6 (Conclusion).

[“Several theoretical assumptions are crucial and well presented in the paper. How sensitive are the main results to these assumptions?”]

The assumptions made through Section 4 (e.g. known utility functions, follower being one of K types, finite leader/follower actions, full feedback) are standard in the literature on no-regret learning in (Stackelberg) games and are reasonable under many settings.

If you are referring to the assumptions which are unique to Section 5, the results are mixed. We believe that our results in Section 5 could be extended to handle adaptive adversaries by using a more clever exploration strategy. However, our algorithmic ideas in Section 5 do not readily extend to the setting in which the follower’s utility also depends on the context. We view relaxing this assumption as an interesting direction for future research.

[“The paper could benefit from a deeper discussion on the limitations regarding the scalability of the algorithms when the number of contexts or follower types is large. What are the computational implications?”]

We are happy to add a deeper discussion on computational runtime in our next revision. In short, our runtimes have no dependence on the number of contexts, and we inherit the exponential-in-K runtime from the non-contextual Stackelberg game setting (where K is the number of follower types). The implication of this is that while our results scale well to settings with a large (or infinitely-many) number of contexts, the number of different follower types should be small/constant.

[“The authors have not explicitly addressed limitations or potential negative societal impacts of their work. A clearer identification of..”]

We discuss (what we view as) the most important limitations of our work (allowing intermediate forms of adversary, better regret rates in the bandit setting) in the Conclusion as directions for future work. However, we would be happy to add additional discussions on the topics you propose.

We chose not to discuss the societal implications of our work because our results are largely theoretical. With that being said, we anticipate that any societal implications of our work will be positive, since algorithms for learning in Stackelberg games are usually deployed in socially-beneficial domains. For example, in airport security, patrol strategies for drug-sniffing dogs could be modified to take factors such as the time of year, airport congestion, etc. into consideration. In wildlife protection domains, park rangers’ patrol schedules can be informed by things like observed tire tracks, or the current weather conditions.

I really appreciate your detailed response to my questions and additional experiments. After reading the authors' responses and other reviewers' comments, I will keep my score.

[”This paper lacks experimental results to verify the theoretical analysis.”]

We hope our numerical simulations address your concerns regarding the lack of experimental results.