Infrequent Exploration in Linear Bandits

We sincerely thank the reviewer for the positive evaluation and thoughtful comments. We have carefully considered each point and provide our detailed responses below.

[W1] (f(t) = w(log t) for all t)

As defined in Section 4.1, we only require the asymptotic growth condition $f(t) = \omega(\log t)$ as $t \rightarrow \infty$, not for every $t$. This condition is weaker than requiring the growth condition to hold for all $t$. We will add "as $t \rightarrow \infty$" in the final version for clarity. Further, Theorem 3 in Appendix A.4 shows that $f(t) = \omega(\log t)$ is a necessary condition. Given these points, we believe this should be considered a strength rather than a weakness.

[W2] (Trade-off between regret and exploration)

We would like to clarify that in Theorem 1, $G(T)$ is unaffected by the exploration schedule. As long as the number of executions of the base algorithm is super-logarithmic in $t$, the asymptotic regret of $`INFEX`$ remains the same, regardless of the exploration schedule. Therefore, there is no trade-off between exploration and $G(T)$, which we believe is one of the most interesting findings of the theorem. $G_{\text{const}}$, which is the $T$-independent regret term incurred by the additional greedy selections, is affected by the exploration schedule, and its dependence on some example $f(t)$ is shown in Table 1. A more specific derivation can be found in Appendix A.3.
While infrequent exploration is not free in general in terms of non-asymptotic regret, if the reviewer is curious about the exact closed-form expression of the relationship between $T$ and $d$ where the $T$-dependent terms dominate the constant terms, it is slightly tricky to state it as it also depends on the performance of the base algorithm. Instead, we provide the total regret when the base algorithm $`Alg`$ is LinUCB or LinTS for the examples of $f(t)$ in Table 1, where we omit the $\mathcal{O}(\cdot)$ symbol for simplicity.

We appreciate the reviewer’s time and effort in evaluating our paper and providing valuable feedback. We sincerely thank the reviewer for the supportive and constructive comments. Below, we address each of the comments and questions in detail.

[W] (Practical use)

We are more than happy to have the opportunity to clarify this point.

First of all, we would like to emphasize that there are many practical scenarios in which the possible amount of exploration is constrained due to logistical reasons such as costs, risks, and ethical considerations, as described in the Introduction. Our main contribution lies in showing that even in such scenarios, one can achieve polylogarithmic regret as long as the exploration budget is super-logarithmic in $t$, complemented by showing that such a condition is necessary in Theorem 3 in Appendix A.4. Being able to be combined with any base algorithm without additional computational or implementational burden, we confidently claim that our method IS practical.
In addition, the performance of $`INFEX`$ is not only limited to theoretical growth orders, but also has empirical superiority as shown through numerical simulations. The experiments further show that the performance of $`INFEX`$ is not sensitive to the choice of $f(t)$, showing superior performance in most configurations. Assuming one uses, for example, TS for practical purposes, the experiment shows that it is better to use TS with, say, a few steps intervals mixed with greedy action, rather than running TS at every time step, where a wide range of exploration schedules (from one out of five to one out of one hundred time steps) generally improves performance.

Overall, our proposed method and its theoretical results carry meaningful implication and impact on practical use.

[Q1] ("With high probability")

As mentioned in Section 4.1, "with high probability" means with probability $1 - \delta$ in this paper, and the shown bounds correspond to the case where $\delta = 1 / T$, (or more precisely, the bounds are invariant up to constant factors when $\delta$ is regarded as a constant or when $\delta$ decreases polynomially in $1/T$). $\log \frac{1}{\delta}$ factors can be recovered by replacing some of the $\log T$ factors with $\log \frac{T}{\delta}$ factor. We omitted the dependence on $\delta$ since explicitly writing it out only leads to unnecessarily complicated bounds without providing much additional information; for example, the order of $G(T)$ becomes $\frac{1}{\Delta}(\log \frac{T}{\delta} + d \log \log T + d \log \frac{d}{\Delta})(\log T + d \log \log T + d \log \frac{d}{\Delta})$ instead of $\frac{1}{\Delta}(\log T + d \log \log T + d \log \frac{d}{\Delta})^2$. Note that $`INFEX`$ does not require the value of $\delta$ for its execution, unless required by the base algorithm, which gives us the freedom to choose $\delta = 1/ T$. If the expression causes confusion, we will replace the phrase with another one in the final version.

[Q2] (Constants $a, b,$ and $c$)

The constants $a, b,$ and $c$ quantify the regret performance of the base algorithm, $`Alg`$. They would be large when $`Alg`$ is an inefficient algorithm. For $`LinUCB`$, we have $a = 2, b = 1$, and $c = 2$ (Theorem 5 in Abbasi-Yadkori et al. (2011)). For $`LinTS`$, we have $a = 3, b = 1$, and $c = 3$ (Theorem 2).

[Q3] (Empirical superiority)

We conjecture that $`INFEX`$ empirically reduces the regret by avoiding unnecessary exploration. Once the estimator becomes accurate enough to distinguish the optimal arm, a greedy selection would incur less instantaneous regret than exploratory ones. Indeed, LinUCB explores fully adaptively, but is based on the worst-case confidence bounds. Even when the estimator correctly identifies the optimal arm, LinUCB conservatively chooses other arms as long as they have a certain amount of probabilities of being optimal in the worst cases. We believe $`INFEX`$ benefits when such "worst cases" do not occur, allowing it to successfully exploit the optimal arm for most time steps.

[Q4] (Performance of LinTS)

LinTS theoretically requires a $\sqrt{d}$-factor inflation in its perturbation, which results in a multiplicative $\sqrt{d}$ factor in its minimax regret [Agrawal and Goyal, 2013, Abeille and Lazaric, 2017], and a $d$ factor in its instance dependent regret (Theorem 2), compared to LinUCB. Since larger perturbation in LinTS corresponds to excessive exploration, this additional factor is reflected in the empirical results as well. We believe that $`INFEX`$ significantly improves the performance of LinTS in the numerical simulation since it naturally limits excessive exploration.

[Q5] (Budget constraints)

We thank the reviewer for this question, and we would like to further highlight the significance of our paper.

Yes, our work can be directly applied in such settings. The exploration budget -- or even more generally, the whole exploration schedule -- may be given by external sources, and we do not assume that the agent has the freedom to adjust it. Our algorithm and theoretical results remain perfectly valid even in such cases, where we only require the exploration budget $f(t)$ to be superlogarithmic in $t$. We also show that this condition is necessary in Theorem 3 in Appendix A.4, showing that if the allowed exploration budget does not exceed the logarithmic barrier, then there exists an instance where no algorithm succeeds. In the budget-constrained setting, this lower bound could be of independent interest.

We sincerely thank the reviewer for the positive evaluation and thoughtful comments. We deeply appreciate your recognition of our contributions.

We are more than happy to elaborate further on this question by the reviewer.

In the linear contextual bandit setting, the "strong distributional assumptions" required for the greedy policy to work well [Kannan et al., 2018, Sivakumar et al., 2020, Bastani et al., 2021, Raghavan et al., 2023, Kim and Oh, 2024] refer to the assumptions that the context distribution of the arms is sufficiently diverse to allow the greedy policy to automatically explore and achieve small regret. While the greedy policy does not explore explicitly, varying the arm set at each time step can lead it to select arms in diverse directions, possibly spanning the full $R^d$ space, and thus gain information. The cited works formalize the conditions under which the greedy policy benefits from such diversity and achieves low regret.

Specifically,

• Kannan et al. [2018], Sivakumar et al. [2020], and Raghavan et al. [2023] assume that the context vectors are perturbed by a multivariate Gaussian distribution at each time step, forcing the context distribution to be diverse.
• Bastani et al. [2021] directly assume covariate diversity (Assumption 3 in their paper), assuming a positive minimum eigenvalue of the covariate matrix of the selected feature vector, which guarantees linear increase of the minimum eigenvalue of the empirical covariate matrix.
• Kim and Oh. [2024] propose a more general condition on the context distribution under which the greedy policy achieves polylogarithmic regret.

However, all of these assumptions rely on the arm set being randomly changed over time. None of these analyses apply when the arm set is fixed across time steps. In fact, it is not the matter of the analysis as there are counterexamples with fixed arm sets where the greedy policy fails (Example 1 in Jedor et al. (2021)) and insufficient exploration fails (Theorem 3 in Appendix A.4). Therefore, the "bad cases" that $`INFEX`$ handles well are those with fixed arm sets, achieving polylogarithmic regret even in such settings. We will add more details about this point in the final version of the paper.

We appreciate the reviewer’s time and effort in evaluating our paper and providing valuable feedback. We are grateful for the recognition of our contributions and the detailed comments. Below, we address each of the comments and questions in detail.

[W1] (On the choice of exploration schedule)

We are more than happy to have the opportunity to clarify this point.

First of all, we would like to clarify that our main focus is not specifying the ``proper'' exploration schedule or frequency per se. As stated in the Introduction, there are many practical scenarios in which the possible amount of exploration is already constrained due to logistical reasons such as costs, risks, and ethical considerations. In such cases, one does not even have the freedom to choose $f(t)$. Our main contribution lies in showing that even in such scenarios, one can achieve polylogarithmic regret as long as the exploration budget is super-logarithmic in $t$, complemented by showing that such a condition is necessary in Theorem 3 in Appendix A.4.

On the other hand, there may be cases where there is no constraint on the amount of exploration, and it is true that our paper does not suggest speicific exploration schedule in this case. Yet, theoretical bounds are still greatly meaningful in that they provide the principled ground on how often the exploration algorithm should be executed in order to achieve polylogarithmic regret. In addition, the numerical experiments show that the performance of $`INFEX`$ is not sensitive to the choice of $f(t)$. The simulated exploration schedule significantly varies from at least 100 total exploratory time steps to at most 2000 total exploratory time steps, and most configurations show superior performance compared to their base algorithms and the pure greedy policy. Being able to be combined with any base algorithm without additional computational or implementational burden, we confidently claim that our method IS easy to use in practice. For example, it is better to use TS with, say, a few steps intervals mixed with greedy action (rather than running TS at every time step), and the exact specification of $f(t)$ is not even needed to achieve a favorable practical performance. Overall, our proposed method and its theoretical results carry meaningful implications and impact on practical use.

[W2/Q2] (Minimax regret)

Providing the worst-case minimax regret bound for $`INFEX`$ would indeed be an interesting problem, however it is beyond the scope of our paper, and we believe that not providing it should not be considered as a weakness. The main reason we focus on instance-dependent bounds is to show how the regret changes depending on the exploration schedule for a fixed instance. Furthermore, minimax bounds might be too conservative for practical purposes, as they only focus on the worst-case regret and guarantee nothing more about the other instances which are more likely to be encountered in practice. As to the question of whether infrequent exploration can hurt the minimax bound, although we cannot provide theoretical guarantees or counterexamples at the moment, we agree that overly insufficient exploration is likely to lead to higher worst-case minimax bounds. However, we speculate that it will be sublinear in $T$ for some (or all) exploration schedules considered in this paper given that the instance-dependent bounds are polylogarithmic.

[W3/Q1] (Fixed and finite arm set)

We are glad to have the opportunity to discuss this point.

We first clarify that Theorem 2 only requires the positivity of the minimum gap $\Delta$ and can be applied to arbitrary, time-varying arm sets. Finiteness is only assumed to naturally induce the definition of $\Delta$, so as long as $\Delta$ is well-defined and positive, the finiteness of the arm set is not required. This applies to Theorem 1 as well.

As for the requirement of a fixed arm set in Theorem 1, there are some possible generalizations. First, our analysis only requires the optimal arm to be fixed across time, rather than the entire arm set. The conditions for Theorem 1 are exactly the same as those for Theorem 5 in Abbasi-Yadkori et al. [2011] (although not explicitly mentioned, the proof requires -- and only requires -- the optimal arm to be fixed). In addition, we note that, counterintuitively, the greedy policy performs worse with fixed arm sets than with time-varying arm sets. Under certain diversity assumptions on the context distribution, the varying arm sets automatically offer exploration even if the agent acts greedily [Kannan et al., 2018, Sivakumar et al., 2020, Bastani et al., 2021, Raghavan et al., 2023, Kim and Oh, 2024], allowing the pure greedy policy to achieve small regret. In this case, $`INFEX`$ naturally inherits the guarantees provided by the cited works in their respective settings. On the other hand, there are examples with fixed arm sets where the greedy policy fails (Example 1 in Jedor et al. [2021]) and insufficient exploration fails (Theorem 3 in Appendix A.4). Therefore, it should be surprising that $`INFEX`$ achieves polylogarithmic regret even when the arm set is fixed, despite performing greedy selections at most of the time steps.

Yet, we admit that the setting where $`INFEX`$ is guaranteed to work well is not fully general, and generalizing Theorem 1 even further seems challenging for now. Please refer to Appendix E for more discussion on the possibility of extending the analysis to the time-varying arm sets.

[Q3] (Higher standard deviation)

Since the greedy policy has a high standard deviation, we believe it is natural that more greedy selections lead to a higher standard deviation. However, our simulations demonstrate that even when the greedy policy is deployed at most of the time steps, for instance, 99% of the time steps, the standard deviations of the regret are significantly smaller than the one by the purely greedy policy, being roughly 50% instead of 99%, which should be considered as a strength of $`INFEX`$. While we agree that high standard deviation may be undesired in practice, we do not find the observed values to be critically high in the experiment. Additionally, we hope that having a higher standard deviation does not obscure the fact that $`INFEX`$ achieves small average regret, which is highly desired in practice.

Thank you to the authors for the detailed response and answering my questions.

I have some follow-up comments:

W1: I agree that if the exploration budget is very tight, then there is no room for choosing $f(t)$. However, most scenarios would be that we have some range of possible $f(t)$s and need to configure a proper schedule among these candidates for the algorithm. In this case, it is not immediately clear how to choose a proper $f(t)$.

W2: It can be helpful to add a remark on the minimax regret as this appears to be an interesting open problem.

W3: Thanks for the detailed explanation. Can the authors also comment on where the assumption about the fixed optimal arm is needed?

Thank you for the detailed response that address my questions. I do not have any further inquiry. I look forward to seeing these improvements and discussions incorporated into the final version.