Sparse Optimistic Information Directed Sampling

The authors thank the reviewer for their insightful comments and questions.

Regarding the comment about the motivation for the greedy SO-IDS algorithm, could the reviewer please provide us with more detail about what they mean by the greedy SO-IDS algorithm?

Regarding the comments about how the framework generalizes to structured or infinite action spaces, such as linear or contextual bandits, the setup we consider directly extends to linear bandits without sparsity and contextual bandits (see Neu, Papini and Schwartz, 2024 for instance). The definition of the information ratio naturally extends to contextual bandits by replacing all losses by their contextual counterparts. For linear bandits, the 2-information ratio can be shown to be bounded by $d$. The other difference is the choice of the prior and the maximum likelihood estimator. In the absence of sparsity, a uniform prior is suitable, and for the MLE analysis, the same type of covering number argument will apply.

The framework we develop in this work builds upon the analysis of the optimistic posterior and the OIDS algorithm from Neu, Papini and Schwartz (2024). The main differences are as follows:

• We specialize their result to the sparse linear bandit settings. This requires the adaptation of some of the arguments (choice of the priors, covering of the sparse parameter space). In this setting we are able to match the performance of Bayesian SIDS and get the first frequentist algorithm that get the best worst-case regret in both the data-rich and data-poor regime.
• We replace the Best-loss-gap by the difference between the regret and the surrogate regret. Conceptually, it reflects the fact that we are not interested in our posterior placing a lot of mass on parameters with high potential rewards but on making sure that the surrogate regret is an upper bound on the true regret. Moreover, this simplifies the analysis and allows us to more easily prove data-dependent bounds.
• We provide an analysis of the optimistic posterior valid with time dependent(and data-dependent) learning rates. This is one of the main limitations of the work of Neu, Papini and Schwartz (2024) (and Zhang, 2022), which we remove. While the results presented here are specialized to sparse linear bandits, this analysis is very general and can easily be extended to contextual bandits or even to decision-making with side observations.

Would the reviewer be able to provide us with more details regarding the last question about the size of the subset of arms considered at each round? The algorithm considers all possible arms at each round. On the computational side, it is known that the IDS policy is supported on at most 2 actions so a search algorithm can identify the IDS policy with a computational complexity $O(K^2)$. Moreover, one can approximately optimize the IDS policy by playing a mixture of an informative and a greedy action which only requires $O(K)$ complexity to compute.

The authors thank the reviewer for their insightful comments and questions.

It is true that our bound on the 3-information ratio requires the sparse optimal action property. We will make this clear in the main text of the paper. It might be the case that the sparse optimal action condition is actually not necessary for obtaining dimension-independent bounds on the 3-information ratio. However, as far as we are aware, it is not known whether this is an artifact of the current analysis or a fundamental property of the 3-information ratio.

Thank you for pointing out the sub-optimal scaling in $s$ in the data-poor regime. We have inherited this scaling from the work of Hao, Lattimore and Deng (2021), and in particular, from their $s^2$ bound on the 3-information ratio. Note that this is also where the sparse optimal action property is required. This leads to a data-poor regret bound scaling with $s$ rather than $s^\frac{2}{3}$. Since the initial submission of our work, we were able to obtain a tighter bound of order $s$ for the 3-information ratio. This directly translates to a $(sT)^\frac{2}{3}$ regret bound by setting lambda accordingly (not only improving the results in the present paper but also the rates for the Bayesian algorithm of Hao, Lattimore and Deng). We will update the paper accordingly for the final version.

We will try to highlight here the independent contribution of this work. One of our main contributions is to allow the use of time-varying learning rates and data-dependent learning rates for the optimistic posterior. This is not possible in Neu, Papini and Schwartz (2024) or Zhang (2022). All existing bounds derived from the analysis of the optimistic posterior require prior knowledge of the time horizon (or the best loss in hindsight). This result is not a direct application of the methods highlighted in the Adagrad paper and requires additional work. One could think that the regular analysis of FTRL could be applied to allow for time varying learning rates by using the monotonicity of the dual to perform the usual telescoping of the potential. Unfortunately this is not possible as only some part of the loss is scaled by the time varying learning rate (compared to the whole loss in the usual analysis). This seemingly simple fact completely breaks the analysis and makes it unclear how to proceed. Our solution is to replace the monotonicity of the dual (which doesn't hold here) by Lemma 9 which will still allow the telescoping of the potential. To apply Lemma 9, we need one of the losses to be non-negative. To ensure that this is the case, we introduce the Maximum likelihood Estimator at every time step. None of those results are standard and they required significant work to prove. We completely agree with the reviewer that going from Theorem 2 to Theorem 3 relies on setting up the learning rate to scale with the information ratio in a way that is similar to the analysis of AdaGrad. We note that this step is only possible because we are able to use time-dependent and data-dependent learning rates.

The analysis of Lemma 3 doesn't require previous knowledge of the sparsity and the result continues to hold even if we don't restrict the prior to a given sparsity level. As such, if we only had an upper bound on the sparsity level, we could use it to compute the prior and still adapt to the true sparsity. The true sparsity is only needed in computing the 3-information ratio, which is why we restrict the prior to s-sparse parameters. If we only wished to use the 2-information ratio, we could use the prior without any sparsity level restriction. We agree with the reviewer that the bound of Lemma 3 would continue to hold with a uniform prior on the sparsity level $s$ but we would lose the nice properties pointed out before.

Thank you for the great catch on line 245, this likelihood term is indeed controlled by Lemma 4 as can be seen in its proof in Appendix B but the term is missing from the statement of Lemma 4, we'll update it for the final submission.

Thank you for the detailed explanation.

Presenting the current work as a frequentist version of Hao et al. (2021) would indeed be valid and meaningful. I also see that the improvement to the 3-IR is already in the paper, and only the final bound was loose for no reason. I am satisfied with the answers have no questions left about the paper. The authors agreed with me that a fundamental shift of perspective is necessary in the presentation, and fortunately, the technical results and proofs remain intact and solid.

I would like to make one more remark. (Please note that this is not a request for additional clarification; the authors have sufficiently addressed these points during the discussion period, and my point is that including them in the paper would be highly necessary.)
If the paper had originally been submitted with the explained presentation, I think I -- and probably most of the other reviewers -- would have been curious about the difficulty involved in extending the Bayesian guarantee of IDS to the frequentist guarantee of OIDS under the same problem setting. In other words, the authors would have had to explain that the work is more than simply replacing the IDS analysis in Hao et al. (2021) with the OIDS analysis of Neu et al. (2024). In addition, I don't think the original manuscript makes it clear that many parts of the analysis come from Hao et al. (2021) (e.g., using both 2- and 3-IRs, bounding the 3-IR, etc.), but it would become inevitable to clarify this if the authors revise the presentation as described in their last comment.

I will update my score after the discussion, assuming that the paper's independent contribution will be clearly explained in the revised version.

The authors thank the reviewer for their insightful comments and questions.

Thank you for pointing out the sub-optimal scaling in $s$ in the data-poor regime. We have inherited this scaling from the work of Hao, Lattimore and Deng (2021), and in particular, from their $s^2$ bound on the 3-information ratio. This leads to a data-poor regret bound scaling with $s$ rather than $s^\frac{2}{3}$. Note that the data-poor regret bound in Hao, Lattimore and Deng (2021) also scales with $s$ whenever the number of actions is large or infinite, which is arguably the most interesting situation. Though the lower bound in Hao, Lattimore and Wang (2020) indeed scales with $s^{1/3}$, the best achievable scaling is $s^{2/3}$. This follows from the lower bound in Jang, Zhang and Jun (2022). Since the initial submission of our work, we were able to obtain a tighter bound of order $s$ for the 3-information ratio. This directly translates to a $(sT)^\frac{2}{3}$ regret bound by setting lambda accordingly (not only improving the results in the present paper but also the rates for the Bayesian algorithm of Hao, Lattimore and Deng). We will update the paper accordingly for the final version.

We will comment on the fact that the dependence of the data-poor regret bound on $C_{\min}$ can introduce undesirable dimension-dependence.

Regarding the instance-dependent bounds that we provide, it is well known that an algorithm tuned to optimize a worst-case regret bound might perform poorly in practice, since worst-case bounds are often very conservative. Conversely, a bound scaling with the actual information ratio might yield a more practical algorithm. Thought it is not the subject of the present work, it can be shown that OIDS with data-dependent learning rates enjoys first-order bounds for contextual bandits without prior knowledge of the best cumulative loss. In the contextual bandit setting, it is known from the work of Neu, Papini and Schwartz (2024) that the information ratio scales with the surrogate loss of the selected action, and adapting to that scaling will give a first-order bound in which the time horizon is replaced by the cumulative loss of the best action. This can lead to significant improvements in "easy" instances in which the cumulative best loss is small. Previous work requires knowledge of this quantity to tune the learning rate. On the contrary, with our instance-dependent analysis we can adapt to this quantity on the fly without prior knowledge.

There is indeed a typo on line 94, It should be $C_{\min}^{-1/3}$. Thank you for spotting this.

The new adjustment to the optimistic posterior allows us to deal with the "Bellman error/Underestimation error" and the "Feel-good term/ Best loss gap" in a unified manner. For the data-independent bound (Theorem 2), it is possible to directly bound the underestimation error as in Neu, Papini and Schwartz (2024), which would lead to the same scaling as obtained here (and allow us to drop the requirement that the learning rate should be smaller than $\frac{1}{2}$). For the instance-dependent version, it might be possible to get a similar bound without this adjustment to the optimistic posterior, but we don't know for sure. In any case, we find it quite insightful to frame everything this way, so that Theorem 1 directly relates the true regret to the surrogate regret.

The assumption of known sparsity can be relaxed somewhat. If there is a known upper bound on the sparsity, then the sparsity level can be replaced this upper bound, and the regret bounds would then scale with this upper bound. If there is no known upper bound on the sparsity, the best regret bound that we are aware of is of the order $s\sqrt{dT}$ (Jin, Jang and Cesa-Bianchi, 2024). We can match this regret bound by making two modifications to SOIDS. First, the subset selection prior can be modified such that it has support for subsets of all sizes and does not require knowledge of $s$. This can be achieved by replacing the sum in the denominator by $\sum_{k=1}^d2^{-k}$ and verifying that Lemma 3 still holds. The only other place in which our $\sqrt{sdT}$ regret bound requires knowledge of the sparsity is in the value of $\lambda_t$. If one chooses $\lambda_t = 1/\sqrt{dT}$, then we no longer require knowledge of $s$, and get a regret bound of the order $s\sqrt{dT}$. The situation for the $(sT)^{2/3}$ regret bound is more complicated. If the subset selection prior is extended to have support for subsets of all sizes, then samples from the prior are no longer $s$-sparse with probability 1, and so the sparse optimal action property might not be satisfied. Since samples from the "full" prior are still sparse with high probability, one can perhaps adapt our bounds on the 3-information ratio such that when $\lambda_t$ is set independently of $s$, one has a regret bound of the order $sT^{2/3}$. The situation is the same for the Bayesian version of sparse IDS (Hao, Lattimore and Deng, 2021).

The authors thank the reviewer for their insightful comments and questions.

Regarding known sparsity: this is a common assumption to make in this setting. The sparsity level could be replaced by a known upper bound on the sparsity, and the bounds would then scale with this upper bound. If there is no known upper bound on the sparsity, the best regret bound that we are aware of is of the order $s\sqrt{dT}$ (Jin, Jang and Cesa-Bianchi, 2024). We can match this regret bound by making two modifications to SOIDS. First, the subset selection prior can be modified such that it has support for subsets of all sizes and does not require knowledge of $s$. One can simply replace the sum in the denominator by $\sum_{k=1}^d2^{-k}$ and verify that Lemma 3 still holds. The only other place in which our $\sqrt{sdT}$ regret bound requires knowledge of the sparsity is in the value of $\lambda_t$. If one chooses $\lambda_t = 1/\sqrt{dT}$, then we no longer require knowledge of $s$, and get a regret bound of the order $s\sqrt{dT}$. The situation for the $(sT)^{2/3}$ regret bound is more complicated. If the subset selection prior is extended to have support for subsets of all sizes, then samples from the prior are no longer $s$-sparse with probability 1, and so the sparse optimal action property might not be satisfied. Since samples from the "full" prior are still sparse with high probability, one can perhaps adapt our bounds on the 3-information ratio such that when $\lambda_t$ is set independently of $s$, one has a regret bound of the order $sT^{2/3}$. The situation is the same for the Bayesian version of sparse IDS (Hao, Lattimore and Deng, 2021).

Regarding the specific choice of the switching mechanism, the basic idea can be understood intuitively as follows. The optimal learning rate for the data-rich regime ($T >> \mathrm{poly}(\frac{d}{s})$) is $\lambda_t^{(2)}$ and the optimal learning rate for the data-poor regime is $\lambda_t^{(3)}$. Therefore, for rounds $t$ such that $t >> d/s$, we should use $\lambda_t^{(2)}$ and for all other rounds we should use $\lambda_t^{(3)}$. Using the expressions for $\lambda_t^{(2)}$ and $\lambda_t^{(3)}$ in Theorem 2, the inequality $\lambda_t^{(2)} \geq \lambda_t^{(3)}$ can be rearranged to obtain (roughly) $t \geq d^3/s$. This means that if we take $\lambda_t = \max(\lambda_t^{(2)}, \lambda_t^{(3)})$, we will be using the correct learning rate for each regime.

For a more technical explanation, the following might help. The idea is that we want our regret bound to adapt to each possible regime. In the data poor regime, we want to obtain the rate $R_T^{(3)} \propto (sT)^ \frac{2}{3}$, and in the data rich regime, we want to match the $R_T^{(2)} \propto\sqrt{sdT}$ rate. The bound obtained at the beginning of the analysis of Theorem 2 (Equation (12) line 258) scales with both the 3 information-ratio and the 2-information ratio. The tricky part is now to chose the learning rate. If we choose the learning rate $\lambda^{(2)} \propto \frac{1}{\sqrt{sdT}}$ to optimize the term with the 2-information ratio, we would obtain the data-rich rate of $R_T^{(2)} \propto \sqrt{sdT}$. If we choose the learning rate $\lambda^{(3)} \propto \left(\frac{1}{sT}\right)^\frac{2}{3}$ to optimize the term with the 3-information ratio, we would obtain the data-poor rate of $R_T^{(3)} \propto (sT)^\frac{2}{3}$ . The relevant question is now whether or not there is a way to chose the learning rate to get both rates at the same time. The essential observation now is that the bigger learning rate always matches the best regret rate. More specifically we have that $\lambda^{(2)} \lessapprox \lambda^{(3)}$ if and only if $R_T^{(2)} \gtrapprox R_T^{(3)}$. This can be seen by comparing the ratios of the learning rates and the regret rates. As a result, if we're trying to obtain the best regret rate, we should always pick the bigger learning rate out of $\lambda^{(2)}$ and $\lambda^{(3)}$ which is done by picking the maximum. When a time varying learning rate is used, the story is similar with a slightly more complicated analysis of the regret coming from having used the wrong learning rate in the past.

The question of a unified instance-dependent bound is extremely interesting. The analysis of Theorem 2 relied on using the fact that the learning rates only switch once, starting with the learning rate $\lambda_t^{(3)}$ and then at some point switching to $\lambda_t^{(2)}$. Such a behavior cannot be guaranteed when $\lambda_t^{(2)}$ and $\lambda_t^{(3)}$ are data-dependent, because the information ratios might behave differently than their respective upper bounds. It turns out that this switching argument is not necessary and can be replaced by considering the last time that either of the two learning rates is used. Using this approach, one can simplify the proof of Theorem 2 and prove a unified instance-dependent bound that smoothly interpolates between the two regimes. We discovered this technique shortly after submission and will include it in the final version.