  We study model selection in linear bandits, where the learner must adapt to
the dimension (denoted by $d_\star$) of the smallest hypothesis class
containing the true linear model while balancing exploration and exploitation.
Previous papers provide various guarantees for this model selection problem,
but have limitations; i.e., the analysis requires favorable conditions that
allow for inexpensive statistical testing to locate the right hypothesis class
or are based on the idea of "corralling" multiple base algorithms, which often
performs relatively poorly in practice. These works also mainly focus on upper
bounds. In this paper, we establish the first lower bound for the model
selection problem. Our lower bound implies that, even with a fixed action set,
adaptation to the unknown dimension $d_\star$ comes at a cost: There is no
algorithm that can achieve the regret bound $\widetilde{O}(\sqrt{d_\star T})$
simultaneously for all values of $d_\star$. We propose Pareto optimal
algorithms that match the lower bound. Empirical evaluations show that our
algorithm enjoys superior performance compared to existing ones.
