Contextual Linear Bandits with Delay as Payoff

Thanks for your valuable comments. We address the issues mentioned in your review below.

• Q1: The reliance on mature techniques, such as the spanner method and phased arm elimination, limits the novelty of the proposed approach.

While we agree that neither volumetric spanner or phased arm elimination is new, combining them to solve the issues that other standard ideas for linear bandits do not seem to be able to solve in our model is a significant contribution in our opinion. In fact, we are not aware of algorithms using similar ideas even for standard linear bandit models.

• Q2: The algorithm requires actions and parameters to lie in $\mathbb{R}^n_+$.

As mentioned in Footnote 1, we enforce both the action $a$ and the underlying parameter $\theta$ to lie in $\mathbb{R}^n_+$ in order to make sure that the payoff $\langle a,\theta\rangle$, and hence the delay, is non-negative. It is just an important restriction to properly define our model, instead of an assumption to make the analysis work.

• Q3: An alternative way of estimating LCB of action $a$ using $V_t^{-1} = (\sum_{\tau=1}^ta_{\tau}a_{\tau}^\top)^{-1}$.

There is a critical issue in your proposal and reasoning. Specifically, you argued that for $a'\neq a$, we have $a^\top V_t^{-1} a' \geq 0$ since all actions are in $\mathbb{R}^n_+$. This is just simply wrong since $V_t^{-1}$ can have negative entries even though $V_t$ does not (for a simple example, consider $V_t=a_1a_1^\top+a_2a_2^\top$ where $a_1=[1;1]$ and $a_2=[1;0]$; then direct calculation shows that $V_t^{-1}=[1,-1;-1,2]$ and $a_2^\top V_t^{-1}a_3= -1<0$ for $a_3=[0;1]$). Therefore, ignoring these actions as you proposed does not lead to an LCB. We hope that this convinces the reviewer that constructing LCB in our problem is nontrivial and that there is clear novelty in our spanner-based approach.

Thanks for your valuable comments. We address the issues mentioned in your review.

• Q1: It is not clear why it is hard to construct a lower bound equivalent to Eq.(2). In particular, why we cannot minimize over an appropriately defined confidence set.

We emphasize again the difficulty of obtaining a lower bound similar to Eq.(2) using classic LinUCB estimator $\hat{\theta}_{t}$. When the delay is payoff-independent, Theorem 1 of [Vernade et al., 2020] indeed shows that certain construction of $\hat{\theta}_{t}$ ensures that the norm of $\hat{\theta}_{t} - \theta$ under $V_t^{-1}$ is controlled (where $V_t\approx\sum_{\tau=1}^ta_ta_t^\top$). However, their proof heavily relies on the independence between the delay and payoff. In our model, the payoff and the delay are dependent, and we do not see a way to construct or even approximate a similar confidence set, so we resolve this issue by proposing a novel arm-elimination algorithm that constructs UCB/LCB based on volumetric-spanners.

• Q2: Can the results be relaxed to hold for sub-Gaussian rewards? Can the results be extended to capture more realistic noise models?

Since delay is essentially the same as payoff in our model, it does not make sense to have negative payoff, which is why we only consider bounded noise. In other words, allowing sub-Gaussian rewards would require a different delay model, which might be an interesting future direction.

• Q3: How $\lambda_{m,i}^{(a)}$ being random affects the analysis?

We are not sure we fully understand this question. Yes, the coefficients $\lambda_{m,i}^{(a)}$ are random, but this does not really introduce any complication to the analysis, and we only use the property $||\lambda_{m}^{(a)}||_2\leq 1$ to control the scale of the confidence range.

• Q4: More experiment settings.

Following your (and Reviewer B3d9's) suggestion, we further tested our algorithm in a setting with a larger $K=70$ and $u_t$ drawn from the beta distribution with $\alpha=\mu_{a_t}$ and $\beta=1-\mu_{a_t}$. Moreover, we also added two baselines: OTFLinUCB and OTFLinTS in [Vernade et al., 2019], which are linear bandit algorithms with payoff-independent delay. The results (presented in https://anonymous.4open.science/r/PaperID-8852) show that our algorithm consistently outperforms all baselines in both the payoff-as-reward and payoff-as-loss settings.

• Q5: The optimality of the $D\Delta_{\max}$ terms in the regret penalty. In the case where the delays are independent of the reward, the delay penalty can be reduced to the expected delay, why can we not get some sort of average appearing here? Can the dependence on the maximum delay be reduced to something more reasonable and more interpretable?

Note that while $D$ represents the maximum per-round delay, the term $D\Delta_{\max} = \max_{a}D\mu_a - \min_aD\mu_a$ by definition is the gap of the expected delay between the best and the worst arms. Therefore, $D\Delta_{\max}$ already represents some kind of ``expected delay'' mentioned by the reviewer. Whether the exact term $D\Delta_{\max}$ is necessary in the regret bound is indeed unclear though.

Thanks for the additional references you suggest and we will incorporate these in our next revision.

Thanks for your valuable comments. We address the issues mentioned in your review below.

• Q1: Why assume the delay as a linear function of payoff; other general models?

Our goal is to extend the same delay-as-payoff model of Schlisselberg et al. (2024) from MAB to contextual linear bandits, and as mentioned in the 2nd paragraph of our introduction (as well as in Schlisselberg et al.), there are indeed many applications where this model is valid. For example, in medical domains, the delay in observing progression-free survival (reward) or postoperative length of stay (loss) is exactly the metric itself; in advertising, the delay in observing average time on page (reward) or the time to re-engagement (loss) is also the metric itself. The analysis of both our work and Schlisselberg et al. (2024) does heavily rely on this model. That said, we agree that extending the results to more general models is definitely an interesting direction (as also pointed out in the conclusion of our paper).

• Q2: Is there an optimality result (lower bound) as well?

As also mentioned in the conclusion section, we do not know whether our bounds are optimal and leave this as future directions. In fact, the optimal bounds in the simpler MAB case is also unknown.

• Q3: In practice, there could be infinite scale of delay, which is actually discussed in paper such as Gael et al (2020). Is there a way to treat for example long delay vs short delay to generalize the analysis?

While this is indeed an interesting case, it unfortunately does not fit into the delay-as-payoff model since infinite scale of delay also implies infinite scale of payoff, in which case no sublinear regret should be possible.

• Q4: Is there any quantification for the performance of LinUCB to show it is theoretically worse or completely fail in certain delay-as-payoff setting?

To the best of our knowledge, this question is indeed still open even for the simpler MAB setting. Our conjecture is that since these algorithms do not take into account the delay-as-payoff structure, they indeed could completely fail in some worst-case environments.

Thanks for your valuable and positive comments and your acknowledgment on our initiation to study linear contextual bandits with payoff-dependent delay. We address the issues mentioned in your review below.

• Q1: There is no comparison with other delayed linear bandit methods, even those assuming delays are independent of payoffs.

Following your (and Reviewer ddMd's) suggestion, we conducted extra experiments where we added two other baselines: OTFLinUCB and OTFLinTS in [Vernade et al., 2019], which are linear bandit algorithms with payoff-independent delay. The results (presented in https://anonymous.4open.science/r/PaperID-8852) show that our algorithm consistently outperforms all baselines in both the payoff-as-reward and payoff-as-loss settings.

• Q2: No discussion of the scalability/computational cost of this approach for when $n$ (and $K$) is large.

We apologize for not discussing time complexity in the paper. However, we emphasize that our algorithm is in fact even more computationally efficient than the classic LinUCB algorithm. More specifically, the time complexity of our algorithm over $T$ rounds is $O(nT+Kn^3\log n\log(T/n))$ in total since we only compute the volumetric spanner at the beginning of each epoch, and the total number of epoch is $\log(T/n)$. On the other hand, LinUCB's time complexity is $O(Kn^2T)$ since computing the UCB of each action requires $O(n^2)$ time. Therefore, our algorithm is in fact more efficient. We will add this discussion in the next revision. Thanks for pointing this out.

• Q3: Why expected pseudo regret?

This is standard in the stochastic bandit literature (such as the UCB paper), especially when the goal is to derive logarithmic regret. This is because if one were to consider expected regret, then even if the algorithm always picks the optimal arm, the derivation in the stochastic losses still contributes to $\sqrt{T}$ regret.

• Q4: The reduction from contextual linear bandits to non-contextual linear bandits using Hanna et al. (2023) is unclear; assumption on the misspecification level $\epsilon_a\leq \epsilon$.

Note that the reason we consider the misspecified setting is mostly to enable the use of the contextual-to-non-contextual reduction proposed by [Hanna et al., 2023], and in that reduction, the misspecification level of each arm is indeed uniformly bounded by a known value. To be clear, we explain the high-level idea of the reduction and why it requires a misspecifed model below, and we will add more discussion to the paper: at a high level, their reduction treats each model parameter $\theta$ as an action and goes in epochs. Since the distribution of the action set $\mathcal{A}_t$ at each round $t$ is unknown, at epoch $m$, they can only estimate each action $g(\theta) = E_{\mathcal{A} \sim \mathcal{P}} \left[ \arg\min_{a \in \mathcal{A}} \langle a, \theta \rangle \right]$ using historical data (denoted as $g^{(m)}(\theta)$ in Line 1 of Algorithm 2). This leads to a misspecified model since the true expected loss of picking $a_t$ is $\langle g(\theta_t), \theta\rangle$ while the algorithm considers the loss model of $\langle g^{(m)}(\theta_t), \theta\rangle$. According to Lemma C.1, the gap between $\langle g(\theta_t), \theta\rangle$ and $\langle g^{(m)}(\theta_t), \theta\rangle$ is indeed bounded by a known value $O(\sqrt{1/2^m})$, which is the reason why we only require an algorithm with a uniform and known misspecification level.

• Q5: How does one check if the delays actually scale with payoffs in real life?

As mentioned in our introduction, for some applications, this is true by definition: in medical domains, the delay in observing progression-free survival (reward) or postoperative length of stay (loss) is exactly the metric itself; in advertising, the delay in observing average time on page (reward) or the time to re-engagement (loss) is also the metric itself. In other applications where this is less obvious, one possibility is to collect historical data and apply a linear regression on delays versus payoff to see if this is a good model.

• Q6: Can you take into account contextual information in your framework?

We assume that reviewer is asking whether we can also allow context-dependent delay. However, note that our payoffs depend on the context, so the delay, essentially being the same as the payoff in our model, already depends on the context.

Thanks for pointing out other references. We will incorporate these into our next revision.