Motivated by a number of real-world applications from domains like healthcare and sustainable transportation, in this paper we study a scenario of repeated principal-agent games within a multi-armed bandit (MAB) framework, where: the principal gives a different incentive for each bandit arm, the agent picks a bandit arm to maximize its own expected reward plus incentive, and the principal observes which arm is chosen and receives a reward (different than that of the agent) for the chosen arm. Designing policies for the principal is challenging because the principal cannot directly observe the reward that the agent receives for their chosen actions, and so the principal cannot directly learn the expected reward using existing estimation techniques. As a result, the problem of designing policies for this scenario, as well as similar ones, remains mostly unexplored. In this paper, we construct a policy that achieves a low regret (i.e., square-root regret up to a log factor) in this scenario for the case where the agent has perfect-knowledge about its own expected rewards for each bandit arm. We design our policy by first constructing an estimator for the agent's expected reward for each bandit arm. Since our estimator uses as data the sequence of incentives offered and subsequently chosen arms, the principal's estimation can be regarded as an analogy of online inverse optimization in MAB's. Next, we construct a policy that we prove achieves a low regret by deriving finite-sample concentration bounds for our estimator. We conclude with numerical simulations demonstrating the applicability of our framework to personalized adherence-improving incentive design for long-term statin treatments.
Figures & tables
Figure 1: Realized estimation gaps compared with scaled theoretical tolerances, illustrating the rate, conservativeness, and coverage of the concentration bound. Shaded areas indicate regions where the realized gaps lie below the scaled tolerance.
Figure 2: The provider’s log-cumulative regret averaged across iid patients with exploration rates m∈{13,19,26} . The shaded regions represent the standard error over all replications.
Figure 3: Cumulative percentage of weeks in which the algorithm steers the patient toward i) the estimated best adherence level, and ii) the true best level.
Appendix figures & tables2 assets
Supplementary material from the paper’s appendix.
Appendix
a
NON
LOW
MED
HIGH
\theta^{0}_{a}(\)$
214.564
213.517
203.471
195.588
\sigma^{\text{provider}}_{a}(\)$
134.173
133.521
127.241
122.309
Appendix
Table 1: Provider’s true distributional parameters by adherence arm.
Patient
r0=(rNON0,rLOW0,rMED0,rHIGH0)
1
(0, 2, 4, 5)
2
(0, -3, -10, -16)
3
(0, 1, 3, 4)
4
(1, 6, 1, 19)
5
(0, 0, -1, -3)
6
(1, 6, 15, 22)
Appendix
Table 2: The true expected reward vectors for the generated iid patients.
In practice, incentive providers (i.e., principals) often cannot observe the reward realizations of incentivized agents, which is in contrast to many principal-agent models that have been previously studied. This information asymmetry challenges the principal to consistently estimate the agent's unknown rewards by solely watching the agent's decisions, which becomes even more challenging when the agent has to learn its own rewards. This complex setting is observed in various real-life scenarios ranging from renewable energy storage contracts to personalized healthcare incentives. Hence, it offers not only interesting theoretical questions but also wide practical relevance. This paper explores a repeated adverse selection game between a self-interested learning agent and a learning principal. The agent tackles a multi-armed bandit (MAB) problem to maximize their expected reward plus incentive. On top of the agent's learning, the principal trains a parallel algorithm and faces a trade-off between consistently estimating the agent's unknown rewards and maximizing their own utility by offering adaptive incentives to lead the agent. For a non-parametric model, we introduce an estimator whose only input is the history of principal's incentives and agent's choices. We unite this estimator with a proposed data-driven incentive policy within a MAB framework. Without restricting the type of the agent's algorithm, we prove finite-sample consistency of the estimator and a rigorous regret bound for the principal by considering the sequential externality imposed by the agent. Lastly, our theoretical results are reinforced by simulations justifying applicability of our framework to green energy aggregator contracts.
Ilgin Dogan, Zuo-Jun Max Shen, Anil Aswani
Department of Industrial Engineering and Operations Research, University of California, Berkeley, Berkeley, California 94720
Incentive design studies how a central authority can influence strategic agents through payments, subsidies, or taxes, so that individual objectives align with collective welfare. This paper introduces a No-Regret Adaptive Incentive Design (RAID) framework for nonlinear games with continuous action spaces and private agent costs. In this framework, the authority (planner) designs incentives that regulate the Nash equilibrium toward a socially optimal action profile, while simultaneously learning agents' unknown preferences from repeated strategic responses. We formulate the RAID problem and construct a least-squares estimator whose strong consistency requires only diminishing excitation. Leveraging this weak excitation requirement, we propose a switching incentive policy that alternates between probing (exploration) and estimate-based (exploitation) incentives. The resulting policy achieves an O(t−0.5) parameter estimation rate and accumulates O(t0.5logt) squared social-cost regret, almost surely. We further extend the framework to an endogenous-noise response model, where standard least-squares estimation is biased due to an error-in-variables correlation between the noise and agent responses. We utilize a repeated-sampling estimator and corresponding switching policy that retain the same almost-sure convergence and regret rates. Numerical experiments validate the effectiveness and predicted convergence rates of the method.
Georgios Vasileiou, Lantian Zhang, Silun Zhang
Department of Mathematics, KTH Royal Institute of Technology, Stockholm, 10044, Sweden.
We consider the dynamic principal-agent problem under asymmetric information, wherein a principal sequentially designs contracts to incentivize an agent with unknown preferences and hidden actions. A fundamental bottleneck in the existing literature is the assumption of deterministic agent utility, which renders the principal's expected utility discontinuous and forces computationally intractable discretizations of the contract space. In this paper, we address this limitation by introducing a stochastic counterpart into the agent's utility model, capturing the inherent physical and behavioral variations in realistic subsystems. We formally prove that this stochastic formulation restores the continuity of the principal's expected utility. Leveraging this continuous geometric structure, we formulate the interaction as a structured multi-armed bandit problem subject to heteroscedastic noise. We propose a Heteroscedastic GP-UCB algorithm that utilizes a Neural Network (Arcsin) kernel, chosen to capture the non-stationary, sigmoidal geometry of the utility landscape. For an m-dimensional compact contract space, we establish a high-probability cumulative regret bound of O(T(logT)m+1). Finally, we demonstrate the practical efficacy of our theoretical framework by formulating the Vehicle-to-Grid (V2G) incentive design problem, proving its equivalence to a dynamic principal-agent problem, and showing superior economic performance for grid aggregators.
Arghya Mallick, Anuj S. Vora, Sergio Grammatico +1
Delft Center for Systems and Control, Delft University of Technology, Delft, The Netherlands · Jio Institute, Navi Mumbai, India · University of Toronto, Toronto, Canada