Learning to Incentivize in Repeated Principal-Agent Problems with Adversarial Agent Arrivals

We thank the reviewer for their review. We now address their concerns.

Typo regarding $L$: Thanks for pointing out this typo. This should be $L \ge 1$.

Regarding the parameter $\Delta$ in our linear-regret lower bound: In the principal-agent problem, the incentives provided to any arm lie within the range $[0,1]$. In our lower bound instance, the optimal incentive to provide to arm $1$ is $\Delta$; any deviation above or below this value results in linear regret for the algorithm. We select $\Delta \in [0.7, 0.71]$, which is relatively large on the $[0,1]$ scale.

Response to reviewer's question: Our upper bound applies to all scenarios; the tie-breaking assumption is made only for simplicity of presentation. We have addressed all possible tie-breaking scenarios in the appendix. In contrast, our lower bound is a worst-case bound. Thus, analogous to multi-armed bandit problems, establishing instance-dependent upper and lower bounds in this setting would be an interesting direction for future research.

We thank the reviewer for their review. We now address their concerns.

On instance-dependent Algorithm for the smooth setting:

For the smooth setting, after establishing the minimax regret bounds, we directly apply the Zooming algorithm from [1] in Section 4.3 of our paper. The instance-dependent regret bound then follows from Theorem 3.1 in [1], which characterizes the regret in terms of the zooming dimension. We agree that a clearer presentation would benefit the reader; thus, if space permits, we will include a pseudocode outline of the Zooming algorithm along with a precise statement of the associated regret bound, citing Theorem 3.1 of [1] for completeness.

[1] Podimata, C. and Slivkins, A. Adaptive Discretization for Adversarial Lipschitz Bandits. In Proceedings of the Thirty-Fourth Conference on Learning Theory, vol. 134, pp. 3788–3805, 2021.

Comparison with Zhu et al.

Since both papers consider settings where the agent best responds to the incentive, a key technical challenge in both is that the principal’s utility function is not Lipschitz continuous with respect to the incentive. That is, small changes in incentives can lead to abrupt shifts in agent behavior. However, the approaches for handling this non-smoothness differ significantly. Zhu et al. (2022) identify directions in the incentive space along which the utility function is continuous and construct a discretization based on spherical codes to cover these directions.

In contrast, our approach leverages structural knowledge of agent behavior: for any given incentive, we know exactly which arm each agent type will choose. This allows for a more tailored discretization strategy. For instance, in the single-arm incentive setting, we enumerate threshold points across agent types and prune the incentive set by retaining only the most rewarding vectors, making the discretization independent of $N$. In the general incentive setting, we again use the knowledge of agents’ best responses to characterize the incentive space as a polytope, and the algorithm only needs to consider the extreme points of that polytope.

On the Prevalence of the Regret Definition in the literature:

As we highlight in the paper, our work initiates a new problem setting that combines elements of the principal-agent framework with adversarially ordered arrivals. In this setting, the regret notion we adopt arises naturally, and closely related definitions have been studied in the context of Stackelberg games. For instance, the following works—one of which was also cited by Reviewer QVD9—explicitly consider this form of regret:

References

1. Harris et al. Regret Minimization in Stackelberg Games with Side Information, NeurIPS 2024.
2. Balcan, Maria-Florina, et al. Commitment without regrets: Online learning in Stackelberg security games. Proceedings of the Sixteenth ACM Conference on Economics and Computation, 2015.

Although this exact regret formulation may not have been explored in the contract design literature to our knowledge, we believe it is a natural and principled objective in our setting. As such, it may help inspire new directions in principal-agent and contract-design problems under adversarial settings.

On the case when the principal receives only noisy feedback:

Under stochastic bandit feedback, our upper-bound results for single-arm incentives under the greedy model extend naturally to the case where the principal’s rewards are unknown, as follows. We retain the current discretization of the incentive vector space and run Tsallis-INF over these discretized points, incurring a regret of $\sqrt{KNT}$. However, in contrast to the known principal-reward setting, the dependence on $N$ cannot be improved to achieve a regret bound of $\min\left(\sqrt{KT\log N}, K\sqrt{T}\right)$. This is because an $N$-armed stochastic multi-armed bandit problem can easily be reduced to our principal-agent problem, and it is known that an $N$-armed stochastic multi-armed bandit problem has a regret lower bound of $\Omega\left(\sqrt{NT}\right)$.

We thank the reviewer for their review. We now address their concerns.

On Presentation suggestions: We thank the reviewer for the helpful suggestions regarding presentation. We will carefully incorporate them to improve clarity and readability in the next version.

Comparison with Harris et al.

We thank the reviewer for referring us to the recent NeurIPS paper by Harris et al. (2024) and the follow up concurrent arXiv preprint by Balcan et al. (2025). While these works share similarities with our framework—such as a principal-agent setup (which corresponds to the leader-follower formulation in their paper), with unknown agent types appearing each round—their settings differ in several important ways that prevent them from subsuming our problem:

1. Action Space: In our setting, the principal chooses an incentive vector from the hypercube $[0,1]^N$. In contrast, in the work by Harris et al., the leader selects a mixed strategy from a probability simplex defined over a finite set of actions $\mathcal{A}$.

2. Agent/Follower Rewards: In our model, if agent $j$ selects arm $i$, they obtain a reward of $\mu_i^j + \pi_i$, where $\pi$ is the incentive vector chosen by the principal. Conversely, in the leader-follower mode of Harris et al., the follower's reward for choosing action $a_f$ is $\sum_{a_\ell \in \mathcal{A}} x[a_\ell] u_j(z, a_\ell, a_f)$, where $x$ is the mixed strategy chosen by the leader and $z$ represents contextual information.

3. Principal/Leader Rewards: In our setting, if arm $i$ is chosen, the principal’s reward is $v_i - \pi_i$. On the other hand, in Harris et al., if the follower chooses action $a_f$, the leader’s reward is $\sum_{a_\ell \in \mathcal{A}} x[a_\ell] u(z, a_\ell, a_f)$, where $x$ is the mixed strategy chosen by the leader and $z$ is contextual information.

These distinctions—particularly in the action spaces and the reward structures—mean that the Stackelberg game setting of Harris et al. (2024) does not subsume our principal-agent formulation. Nonetheless, we will clarify this comparison in our paper and emphasize that extending our principal-agent framework to a contextual setting, akin to theirs, would be a promising direction for future work.

On concrete applications of our problem setting: While we briefly discussed motivating examples in the introduction, we are happy to expand on them here to further clarify how the studied problems apply to real-world scenarios.

Adversarial arrival of agents. In practice, agent arrivals often deviate from fixed stochastic patterns due to factors like non-stationarity, strategic behavior, or external influences. For instance, in online shopping, discount ads are shown to all users, but only some choose to act—often in response to timing, personal context, or even social trends. The sequence of users who respond may not follow any stable distribution. Modeling arrivals adversarially allows us to account for such unpredictable and potentially strategic participation without assuming a specific arriving distribution.

Agent response models. For additional motivating examples of the best response and smooth response models, please refer to our detailed response to Reviewer LMoE.

On the case when the principal receives only bandit feedback:

Under stochastic bandit feedback, our upper-bound results for single-arm incentives under the greedy model extend naturally to the case where the principal’s rewards are unknown, as follows. We retain the current discretization of the incentive vector space and run Tsallis-INF over these discretized points, incurring a regret of $\sqrt{KNT}$. However, in contrast to the known principal-reward setting, the dependence on $N$ cannot be improved to achieve a regret bound of $\min\left(\sqrt{KT\log N}, K\sqrt{T}\right)$. This is because an $N$-armed stochastic multi-armed bandit problem can easily be reduced to our principal-agent problem, and it is known that an $N$-armed stochastic multi-armed bandit problem has a regret lower bound of $\Omega\left(\sqrt{NT}\right)$.

We thank the reviewer for their review. We now address their concerns.

On technical breakthrough: While we respect the reviewer’s opinion, we believe our work includes notable technical breakthroughs. We develop novel lower bound techniques tailored to the greedy model setting—methods that, to the best of our knowledge, are new and have the potential to extend to other related problems like regret minimization in linear bandits and stackelberg games. Additionally, we develop a new discretization approach and provide a reduction to linear bandits, which together yield near-optimal regret bounds. To the best of our knowledge, this reduction strategy is novel and has not been explored in prior work.

Real world motivation of the two models:

While we briefly discussed motivating examples in the introduction, we are happy to expand on them here to further clarify the relevance of the two models to real-world scenarios.

Best response model. A natural example arises in online shopping, where customers make purchase decisions based on visible discounts (i.e., incentives). Customers often wait until a discount reaches a historical low or crosses a personal threshold before making a purchase (Gunadi & Evangelidis, 2022). Similarly, in online labor markets, crowdworkers frequently accept tasks only if the offered payment exceeds a minimum expected amount (Horton & Chitoni, 2010). These behaviors reflect a threshold-based decision process, motivating our use of the best response model. In this model, the agent plays an arm only when the incentive on that arm exceeds a predefined threshold.

Smooth response model. In contrast, consider routine purchases such as daily necessities. Here, small changes in discounts do not lead to abrupt changes in behavior but instead gradually affect the probability of purchase (Bijmolt et al., 2005). A similar pattern is observed in ad click-through behavior, where users’ likelihood of clicking on an ad increases with the attractiveness of the offer—such as a better discount or a more personalized promotion—but does so in a smooth, probabilistic manner rather than through sharp thresholds (Bleier & Eisenbeiss, 2015). These scenarios motivate the need for a more flexible response model in which decisions vary smoothly with the incentive.

References:

Gunadi, M. P., & Evangelidis, I. (2022). The impact of historical price information on purchase deferral. Journal of Marketing Research, 59(3), 623–640.

Horton, J. J., & Chilton, L. B. (2010). The labor economics of paid crowdsourcing. In Proceedings of the 11th ACM conference on Electronic commerce (pp. 209-218).

Bijmolt, T. H., Van Heerde, H. J., & Pieters, R. G. (2005). New empirical generalizations on the determinants of price elasticity. Journal of marketing research, 42(2), 141-156.

Bleier, A., & Eisenbeiss, M. (2015). Personalized online advertising effectiveness: The interplay of what, when, and where. Marketing Science, 34(5), 669-688.