Principal-Agent Bandit Games with Self-Interested and Exploratory Learning Agents

We thank the reviewer for the valuable feedback. Below we address your concerns.

W: I understand that the paper is of theoretical nature, but I believe that the paper can benefit from experiments on simulated data and real-world data.

A: Thank you for the suggestion. We do agree that experiments could provide additional value. Please see our response to Reviewer RBF5 (W3 and A3)

Q: I'm confused of the annotation in Table 1 "worst-case bound......enjoys a gap-dependent bound". What are the gap-dependent bounds? Are they logarithmic of $T$ ?

A: The gap-dependent bound we refer to is of the form $O ( \sum_{a \in [K]: \Delta_a>0}\frac{\log T}{\Delta_a})$ where $\Delta_a := \max_{b \in [K]} \\{\theta_b + \mu_b\\} - (\theta_a + \mu_a)$ measures the suboptimality gap of arm $a$ in the oracle-agent setup. As noted in the footnote of Table 1, Scheid et al. (2024b) obtain a similar gap-dependent regret bound, but only under the oracle-agent model. In contrast, for the more general learning agent setting, whether such a bound can be achieved remains an open question (see the discussion below Theorem 3.4). Intuitively, we are pessimistic about this possibility, as it appears necessary for the algorithm to continue sampling suboptimal arms in order to stabilize the agent’s internal estimates and reduce the estimation error of the optimal incentive (see Section 3.3 for a more detailed discussion).

We thank the reviewer for the valuable feedback. Below we address your concerns.

W1: It seems that this paper employs many technics from these papers (Dogan et al., 2023a) and (Scheid et al., 2024b) without bringing a lot novelties from a mathematical point of view (except using online elimination and MSP).

A1: Here, we clarify that our techniques and analysis are significantly different from those in Scheid et al. (2024b), and entirely distinct from those in Dogan et al. (2023a).

• Comparison with Scheid et al. (2024b). While Scheid et al. (2024b) use a standard binary search in an oracle-agent setting, we propose a noise-robust variant (Algorithm 3) specifically designed for the more challenging learning-agent setting. This is a non-trivial extension, as optimal incentives in our setting are time-varying—they depend on the agent’s evolving internal estimates. The search procedure must therefore be robust to fluctuations introduced by the agent’s learning process. Algorithm 3 is carefully designed to address these issues and is supported by a detailed analysis (see Lemma 3.1). We also introduce a novel elimination framework tailored to learning agents. Unlike traditional methods (e.g., Even-Dar et al., 2006), our algorithm does not permanently eliminate suboptimal arms but continues to play them moderately to stabilize the agent’s estimates. This is essential to avoid linear regret, as discussed in Section 3.3. In contrast, Scheid et al. (2024b) do not face these challenges, as agent responses in the oracle model are fixed for a given incentive.

• Comparison with Dogan et al. (2023a). Our algorithms (Algorithms 5 and 6 in Appendices F and G) are fundamentally different from those of Dogan et al. (2023a). Their approach relies on an $\epsilon$-greedy strategy and explicitly estimates the agent’s model by solving an optimization problem at every round. In contrast, our approach is built around a newly developed, novel online elimination framework that does not require estimating the agent’s model. As noted in our response to Reviewer RBF5 (see W3 and A3), such estimation would incur significant computational and memory costs. A key innovation is our probabilistic amplification technique (see Section 4.2, also Algorithms 5 and 6), which ensures robustness to the randomness induced by the agent’s exploratory behavior. This technique supports two central components of our algorithm: incentive testing and trustworthy online elimination. Specifically, incentive testing refers to the process of identifying reliable incentives in the presence of agent learning, while trustworthy elimination ensures that, with high probability, the elimination process is not disrupted by exploratory actions of the agent.

We believe that the techniques developed around probabilistic amplification offer a robust and flexible foundation for principal-agent interactions with learning agents, and may inspire further exploration in related dynamic settings.

W2: Presentation of Algorithm 1 and introducing $\pi^0$ earlier.

A2: Thanks for your suggestions. We will make sure to polish up our presentation according to your suggestions in the next version.

Q1: Is assumption in definition 2.1 satisfied by classic bandit routines, such as UCB or Thompson sampling?

A: Thank you for the insightful question. UCB does not satisfy Definition 2.1, as it continues to explore suboptimal arms indefinitely rather than decaying exploration over time. Whether Thompson Sampling satisfies the definition is unclear and may warrant further study. Since our focus is on designing principal algorithms for agents satisfying Definition 2.1, characterizing which other bandit algorithms meet this condition is beyond the scope of this work.

Q2: Unclear why considering a vector of incentives rather than just a scalar incentive on one arm at each round (just as in Scheid 2024b) is better. What are the advantages of this approach, given that the agent only pulls one arm at a time?

A: Incentivizing multiple arms is critical for our online elimination process as detailed in Section 3.4 (and its robust version for exploratory agent). Specifically, when conducting elimination at round $t$, the principal needs to compare $\hat{\theta}_a(t)+\hat{\mu}_a(t)+\epsilon$ against the empirical maximum $\max_b \hat{\theta}_b(t)+\hat{\mu}_b(t)$ over all active arm $a$, where $\epsilon>0$ is an error specified by the algorithm, $\hat{\theta}_a(t)$ is the principal's estimate and $\hat{\mu}_a(t)$ is the agent's estimate. Since the agent's estimates are unknown to the principal, the principal is unaware of which active arm achieves empirical maximum. To address this, the algorithm incentivizes every active arm $a$ by $\hat{\theta}_a(t)$ at round $t$. By doing this, the algorithm indirectly compares $\hat{\theta}_a(t)+\hat{\mu}_a(t)+\epsilon$ against empirical maximum by observing the played arm.

We thank the reviewer for the valuable feedback. Below we address your concerns.

W1: I think the outperformance of soft $O(T^{11/12})$ is not a fair comparison, since their regret is defined with respect to different behavior models, i.e., true mean versus empirical mean.

A1: We would like to clarify that the comparison with the $O(T^{11/12})$ regret bound (Dogan et al., 2023a), as well as others in Table 1, is indeed fair because they can all be evaluated under the same behavior model and regret definition. Specifically, our behavior model generalizes theirs: by letting the agent always receive the constant reward equal to the true mean (as noted in Remark 2.2), our model reduces to theirs. In this case, the empirical mean becomes the true mean, ensuring that the regret definitions and behavior models align. Thus, our comparisons are fair.

W2: If we compare regret under different models, then it seems the proposed Algorithm 7 performs worse than C-IPA Scheid et al. (2024b) under the linear reward model.

A2: As mentioned in A1, regret bounds can be fairly compared when the models and regret definitions align, particularly when one model strictly generalizes another. Our setting is strictly more general than that of Scheid et al. (2024b), as their oracle-agent model is a special case of our learning agent framework. While our regret bound is indeed worse when restricted to this special case, our algorithm is designed to work in the broader and more challenging learning agent setting which is not addressed in Scheid et al. (2024b).

W3: The "significantly improve" claim remains unsubstantiated in practice without empirical comparisons.

A3: We thank the reviewer for this suggestion. Our primary focus in this work is on theoretical improvements in the order of the regret bound (improving from $O(T^{11/12})$ to $O(\sqrt{T})$ in exploratory oracle-agent setup). As such, this version does not include experiments. We do agree that empirical evaluation is a valuable direction and plan to pursue it in future work.

Nonetheless, we would like to highlight several practical advantages of our algorithm compared to Dogan et al. (2023a), particularly in terms of implementation:

• Computational efficiency. Their algorithm solves a linear program at each round, with the number of constraints growing linearly in $t$, leading to increasing runtime. In contrast, our Algorithms 5 and 6 only require simple arithmetic operations per round, resulting in much greater efficiency.

• Memory usage. Their method stores all past incentives and actions, resulting in memory usage that scales with $t$. Our algorithms avoid this by maintaining only a few counters or estimates, ensuring constant or sublinear memory usage.

• Hyperparameter tuning. Their algorithm requires two hyperparameters that must be carefully tuned. Our algorithms, by contrast, only require a standard confidence parameter $\delta \in (0,1)$, which typically does not require fine-tuning in practice.