Model selection in the context of bandit optimization is a challenging problem, as it requires balancing exploration and exploitation not only for action selection, but also for model selection. One natural approach is to rely on online learning algorithms that treat different models as experts. Existing methods, however, scale poorly ($\text{poly}M$) with the number of models $M$ in terms of their regret. Our key insight is that, for model selection in linear bandits, we can emulate full-information feedback to the online learner with a favorable bias-variance trade-off. This allows us to develop ALEXP, which has an exponentially improved ($\log M$) dependence on $M$ for its regret. ALEXP has anytime guarantees on its regret, and neither requires knowledge of the horizon $n$, nor relies on an initial purely exploratory stage. Our approach utilizes a novel time-uniform analysis of the Lasso, establishing a new connection between online learning and high-dimensional statistics.
Paper
Similar papers
Peer review
Summary
This paper introduces AlExp, a novel algorithm to address the problem of online model selection in the context of bandit optimization. The algorithm interacts with the environment by randomly choosing a learner (linear bandit regret minimizer) each round, then the chosen learner tries to propose the optimal action. The exploration-exploitation trade-off is dealt with both by randomizing the choice of the learner and by the learner's policy itself. The authors provide theoretical guarantees and empirical validation and compare this approach with the existing literature.
Strengths
+ The paper presents an extensive literature review and a detailed comparison between the proposed approach and the existing ones. + The algorithm's routine is easy to understand, and its logic is well-commented. + The algorithm effectively improves in some dependencies (e.g., the number of learners) w.r.t. to the existing approaches, both theoretically and empirically. + The analysis presents technical novelty.
Weaknesses
- In some points, the presentation is not easy to follow, and it will be nice to have a more intuitive grasp of the theoretical quantities considered. - It will be nice to have more discussion on the computational aspects of the proposed approach: numerically computing some of the quantities seems to be very expensive and prohibitive when the number of learners scales. This contrasts with the main strength of the approach, i.e., the better regret dependency on the number of learners. - The algorithm requires the knowledge of theoretical quantities (e.g., expected values). In practice, this can be bypassed by a Monte Carlo sampling procedure. However, when performing finite sampling, there's the need to explain how quickly the estimator converges to the theoretical quantity and explain the computational consequences (see previous point) or eventual corrections to the algorithm to deal with the estimation error (e.g., adding an upper confidence bound on the quantities) if due to computational reasons only a small number of samples can be generated.
Questions
+ Can you please provide an examination of the computational limitations of this approach? E.g., providing the solving complexity of the optimizations involved. + Due to the strong dependence (on both algorithm and analysis) on quantity C, can you please provide a more intuitive grasp on the magnitude of this quantity w.r.t. other problem-dependent quantities? Is there an available lower/upper bound on it? I feel that the quality of your theoretical results strongly depends on this quantity, and a characterization (at least qualitative) of its magnitude should be discussed.
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
3 good
Presentation
3 good
Contribution
3 good
Limitations
- I feel that the main limitation of this work relies on its application in practice. However, the authors performed a sufficient experimental campaign, validating their approach. Unfortunately, the code for the experimental campaign has not been released, so reproducibility is another limitation of this work (even if they provide details to reproduce the experiments).
Summary
based on the time-uniform analysis of the Lasso, the anytime exponential weighting algorithm based on Lasso reward estimates with the nature of anytime regret guarantees on model selection linear bandits is developed. The result neither requires knowledge of the horizon n, nor relies on an initial purely exploratory stage.
Strengths
the anytime exponential weighting algorithm based on Lasso reward estimates are horizon-independent, explores adaptively without requiring an initial exploration stage.
Weaknesses
1 The dimensionality of the proposed algorithm model will be ultra-high, and the complexity of the algorithm's runtime depends on the efficiency of the sparse regression model algorithm. 2 The results of the algorithm still belong to the class of multiplicative weights Update algorithms.
Questions
1 What is the relationship between the number of models and their final performance? 2 During the entire learning process, for two cases, i.e., the number of models is fixed, and the number of models is changed. Can you consider these situations and discuss them?
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
5: You are absolutely certain about your assessment. You are very familiar with the related work and checked the math/other details carefully.
Soundness
3 good
Presentation
3 good
Contribution
2 fair
Limitations
the authors adequately addressed the limitations.
Summary
The paper uses tackles model selection for linear bandits with $M$ models. In particular, rewards are estimated from the $M$ models using Lasso and then EXP4 is ran on-top of these estimated rewards to update individual model probabilities. The use of Lasso over ridge regression reduces variance, leading to a $\log M$ dependence rather than usual $\text{rm}poly \, M$. The paper extends the usual martingale mixture analysis from ridge to lasso; this is something I thought would be quite tricky. I look forward to reading it in more detail in the future.
Strengths
Model selection is a very important problem. Problem is explained and motivated very well. Paper is very well written and polished to the standard of a camera-ready.
Weaknesses
I'm not an expert on model selection in linear bandits or full information learning. As such, I cannot identify any weaknesses in this work. It took me a couple minutes to see why (1) is indeed (group) Lasso---I was expecting to see a 1-norm. I see that you have a sentence or two explaining this after, but somehow this didn't do the trick for me. Maybe some rewording or an extra comment here could be useful, relating it to the more usual notion of Lasso.
Questions
None
Rating
8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
Confidence
2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
4 excellent
Presentation
4 excellent
Contribution
4 excellent
Limitations
Limitations clearly discussed in text.
Summary
The paper considers the problem of model selection in (lifted) linear bandits. There are M hypothesis models, each of which have a different feature map, and one of these is the true model; it is unknown to the optimizer which of the M models is the correct one. At each timestep, the optimizer chooses one model and obtains instantaneous regret in accordance with the chosen model's selection. The goal is to minimize overall regret across n timesteps. If feedback were obtained for all model's chosen query at each timestep, then the multiplicative weights update could be used to update the probability of any model being the true oracle model. And the guarantees from the literature would apply. However, we have limited information and only observe the reward for the chosen model's query. To get around this obstacle, the authors consider an aggregated model with all M model's features combined together. And they train this aggregated model on all the data using a sparse LASSO estimator. Then, they use this aggregated model to fill in the missing regrets for the unchosen models. And these imputed values are then used for the MW updates. The analysis consists of proving the recovery result on the LASSO, and adjusting the original proof to use the imputed data instead of the original. The authors verify their findings on synthetic data.
Strengths
Clarity: The problem is well presented, and the key difficulties of the problem are clearly identified - namely the missing regret data for unchosen models. The exposition of the solution is geared towards addressing the difficulty by imputing the missing values. The structure of the proof is well-outlined in the main text. I also appreciated the intuitive explanation around introducing bias to reduce overall error as the reasoning behind the success of the algorithm. Quality: The arguments appear correct and the correct tools are used to obtain the desired results. Significance and Originality: As far as I know, this problem has not been considered before, and the improvement in the scaling with M is helpful.
Weaknesses
My main concern is Q1 below. Other weaknesses are mostly minor 1. It would be useful for the authors to highlight more real-world examples where bandits with multiple models would be most applicable. 2. In line with the above, real-data experiments would be useful to verify the applicability of the algorithm. However, the theoretical contributions are already sufficient so I think this can be deferred to future work. 3. Figure 3 is missing label on the vertical axis and is difficult to interpret.
Questions
1. If the LASSO performs well already, then what is the need to use the LASSO to perform model selection. Why can we not just use the LASSO directly? 2. While the rewards for the query point of the unchosen model are not available, the predictions on the chosen $x_t$ are available. So, why can we not use the prediction error on these points for all the models to choose the weights? Instead of using the imputed data. 3. What is special about the LASSO that makes it suitable for the choice of the aggregate model?
Rating
7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Soundness
4 excellent
Presentation
3 good
Contribution
3 good
Limitations
Yes
Summary
This paper considers linear bandit problem given $M$ models, or sets of feature mappings. In this problem, it is necessary to select the appropriate action as well as the model based on the bandit feedback. This paper provides an algorithm with an anytime regret bound of $O(n^{3/4} \sqrt{\log M} + \sqrt{n \log^3 M} + n^{5/8}\sqrt{d \log n})$, where $n$ and $d$ represent the time horizon and the dimensionality of each model.
Strengths
- The motivation for the research is well explained. - Experimental results support the effectiveness of the proposed method.
Weaknesses
- The obtained regret bound includes $O(n^{3/4})$-term, which means that the bound is suboptimal if the number of rounds is large. - The proposed algorithm requires $O(M)$-time computation in each round. This can be a major computational bottleneck. In fact, in the application of sparse linear bandits, $|M|=\binom{p}{s}$, which is exponentially large w.r.t. $s$. Further, we need $M = \Omega(\exp(n^{1/4}))$ to ensure the regret is of $O(n \log^3 M)$ (i.e., to ensure $n^{3/4} \sqrt{\log M}< \sqrt{n \log^3 M}$). This means that the proposed algorithm is effective only when $M$ is exponentially large w.r.t. $n$.
Questions
- Can you add a description of the known regret lower bound and how it compares to the main result? - Line 290: $\{1, ..., p \}$ <- $\{ 0, 1, ..., p \}$ ? - Line 274-275: "the rate conjectured by Agarwal et al. [2017]" Can you tell me where I can find the corresponding description in Agarwal et al. [2017]? - The condition of $\eta_t = O(..)$ and $\gamma_t = O(..)$ in Theorem 1: Do the authors mean $\Theta(..)$? I guess that too small $\eta_t$ and $\gamma_t$ do not work well. - It is difficult to see what figures 1 and 2 refer to.
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
3 good
Presentation
3 good
Contribution
3 good
Limitations
I have no concerns about the limitations and potential negative societal impact.
Since the authors are too polite to put this plainly, I will do so: this reviewer put down a confidence level of 5, yet their review is nonsensical. I would urge the AC to disregard this review completely.
It seemed to me that this paper would be a done deal in terms of acceptance, and hence I have not bothered to write a lengthy review. This appears to have been a mistake. I will try to find the time to provide a more in-depth review shortly.
Rebuttal Follow-up
We hope that our rebuttal has answered your main question about optimality of the bound, in particular your concern about $n^{3/4}$ growth rate being sub-optimal. We emphasize that: the **minimax optimal dependency on horizon is unknown** in this problem setting, and in fact, may not be $\sqrt{n}$. Hao and Lattimore 2020 prove a dimension-independent lower-bound of $\Omega(n^{2/3})$ for *sparse linear bandits* which hints that **going below the $n^{2/3}$ rate might not be possible** for model selection either. We updated the paper and added a short discussion on minimax optimality to sections 5.2. Further, we mentioned the unsolved lower bounds as future work in Section 7. We hope this update lifts the key concern of your review. It is much appreciated if you could please reconsider your assessment, or respond with questions/suggestions so that we can improve the paper in this regard. --- Hao, Botao, Tor Lattimore, and Mengdi Wang. "High-dimensional sparse linear bandits." Advances in Neural Information Processing Systems 33 (2020): 10753-10763.
Thank you very much for your kind reply. I apologize for the delay in responding. Most of my concerns have been addressed and I am convinced of the importance of this study. However, I still have concerns about your assertion "Agarwal et al. [2017] raise an open problem on the feasibility of obtaining a log M dependency for the regret.", "We addressed the open problem of Agarwal et al. [2017]". For details, I would appreciate it if you could check the following: In Section 6 of Agarwal et al. [2017], which was mentioned in the authors' responce, I found the following statement in the section you mentioned: > Another open problem is to improve the dependence on $M$, the number of base algorithms, from polynomial to logarithmic **while keeping the same dependence on other parameters** (or prove its impossibility). **Logarithmic dependence on $M$ can be achieved** by using EXP4 as the master, but as was earlier discussed, this leads to poor dependence on other parameters. From this statement, I have the following concerns: * As long as the dependence on $n$ is worsen, we cannot say that we have addressed the open problem of Agarwal et al. [2017], even if we achieve logarithmic dependence on $M$. * Agarwal et al. [2017] believed that one can achieves logarithmi dependence on $M$ by sacrificing the dependence on other parameters. If my understanding above was correct, then your assertion that "We addressed the open problem of Agarwal et al. [2017]" would be an exaggeration. I would appreciate a response if there is any misunderstanding regarding this concern.
Thank you so much for your response. We are glad that your previous questions are answered and are happy to give clarify a few details, which will hopefully raise the current concerns. **Concern 1.** We do not think that our paper misleads the reader in this regard, as in lines 274-277 we explicitly state that our result matches the conjectured rate of Agarwal et al. only for very large $M$s, and is otherwise suboptimal in $n$. The rest of this paragraph is dedicated to ideas and required assumptions for closing this gap in future work. Nowhere in the paper it is claimed that we resolve the problem of minimax optimal black-box model selection, however we do believe that our work is an important step in this direction (cf. response to concern 2). In our submission, there is one sentence in the Conclusion section, which mentions *“addressing the open problem of Agarwal et al.”*. We have now changed the verb from “address” to “tackle” to remove misinterpretations and repeated the earlier remark that dependency on $n$ may be suboptimal. We do not intend to exaggerate our results, and would be absolutely happy to further reword this sentence in case you have any suggestions. **Concern 2.** As you mentioned, Agarwal et al. claim that using EXP4 can yield a $\log M$ rate at the cost of suboptimal dependency on other parameters. **Despite this statement, adapting EXP4 for sample-efficient model selection in bandits is an unresolved challenge.** In fact, we are not aware of any work prior to ours, which presents $\log M$ rates for model selection over general action domains, *even with a suboptimal dependency of $n$*. We give a brief overview of prior attempts to use EXP4 for model selection. The Exp4 algorithm [Auer et al 2002] was designed for solving $k$-armed bandit problems given the advice of M experts. This algorithm achieves a $\Theta(\sqrt{nk\log M})$ regret w.r.t. the performance of the best-in-hindsight expert, rather than the optimal action $\boldsymbol x^\star$. Moreover, this rate only applies when the experts are static/oblivious and do not adapt to the history $H_t$. Extending this result to 1) learning with *adaptive* agents (which is the case in model selection) and 2) the cumulative regret w.r.t. to $\boldsymbol x^\star$ bears difficulties. Addressing this problem for *finite action sets* Foster et al. [2019] constructed a variant of EXP4 which roughly put, treated each action as an expert and attained a $\mathrm{poly}(M)$ rate. Improving this, Foster and Rakhlin [2020] later presented SquareCB, which could be used for model selection of linearly parameterizable rewards on finite action sets, and satisfies a $\mathcal{O}(\sqrt{nkd\log M})$ regret [Moradipari et al. 2022]. These attempts use a ridge regression oracle, and naively extending them to infinite action sets will result in a $\sqrt{M}$ dependency. Our results hold for (compact) infinite and non-convex sets. **We are not aware of any other work which applies to such general action sets, and successfully employs EXP4 for model selection.** Please let us know if this answer has not lifted your concerns, and if you have suggestions for modifying the text for further transparency. Thank you! --- Auer, Peter, Nicolo Cesa-Bianchi, Yoav Freund, and Robert E. Schapire. "The nonstochastic multiarmed bandit problem." SIAM journal on computing 32, no. 1 (2002): 48-77. Foster, Dylan J., Akshay Krishnamurthy, and Haipeng Luo. "Model selection for contextual bandits." Advances in Neural Information Processing Systems 32 (2019). Foster, Dylan, and Alexander Rakhlin. "Beyond ucb: Optimal and efficient contextual bandits with regression oracles." In International Conference on Machine Learning, pp. 3199-3210. PMLR, 2020. Moradipari, Ahmadreza, Berkay Turan, Yasin Abbasi-Yadkori, Mahnoosh Alizadeh, and Mohammad Ghavamzadeh. "Feature and parameter selection in stochastic linear bandits." In International Conference on Machine Learning, pp. 15927-15958. PMLR, 2022.
Thank you for your response. The authors addressed my concerns, except for the ones on computational complexity. I will keep my score for now.
Thank you for your reply. Is it possible that you have perhaps missed the paragraph titled "On Computational complexity of ALEXP" in our rebuttal? In your review you had asked for "an examination of the computational limitations of this approach". As a response, in our rebuttal we provided runtime curves of our algorithm and the oracle. Moreover, we conjectured that model selection algorithms will require $O(M)$ many operations to converge. We believe this can not be lifted, unless certain correlation/structure is assumed between models. This being said, we would like to highlight that our work is primarily of theoretical nature, and is the first to show that sample-efficient model selection is possible on generic action domains in linear setting.
Thanks for response
I thank the authors for their response. I will keep my score.
Decision
Accept (poster)