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.
Delft Center for Systems and Control, Delft University of Technology, Delft, The Netherlands · Jio Institute, Navi Mumbai, India · University of Toronto, Toronto, Canada