We study a model selection problem in the linear bandit setting, where the learner must adapt to the dimension of the optimal hypothesis class on the fly and balance exploration and exploitation. More specifically, we assume a sequence of nested linear hypothesis classes with dimensions $d_1 < d_2 < \dots$, and the goal is to automatically adapt to the smallest hypothesis class that contains the true linear model. Although previous papers provide various guarantees for this model selection problem, the analysis therein either works in favorable cases when one can cheaply conduct statistical testing to locate the right hypothesis class or is based on the idea of ``corralling" multiple base algorithms which often performs relatively poorly in practice. These works also mainly focus on upper bounding the regret. In this paper, we first establish a lower bound showing that, even with a fixed action set, adaptation to the unknown intrinsic 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 also bring new ideas, i.e., constructing virtual mixture-arms to effectively summarize useful information, into the model selection problem in linear bandits. Under a mild assumption on the action set, we design a Pareto optimal algorithm with guarantees matching the rate in the lower bound. Experimental results confirm our theoretical results and show advantages of our algorithm compared to prior work.
pareto_optimal_linear.tex
%%%%%%%% ICML 2021 EXAMPLE LATEX SUBMISSION FILE %%%%%%%%%%%%%%%%%

\documentclass{article}

% Recommended, but optional, packages for figures and better typesetting:
\usepackage{microtype}
\usepackage{graphicx}
\usepackage{subfigure}
\usepackage{booktabs} % for professional tables
\usepackage{mystyle}



\newcommand{\mossplus}{{\tt MOSS++\,}}
\newcommand{\ucb}{{\tt UCB\,}}
\newcommand{\corral}{{\tt Corral\,}}
\newcommand{\smoothCorral}{{\tt Smooth Corral\,}}
\newcommand{\linucb}{{\tt LinUCB\,}}
\newcommand{\linucbOracle}{{\tt LinUCB Oracle\,}}
\newcommand{\suplinucb}{{\tt SupLinUCB\,}}
\newcommand{\linucbPlus}{{\tt LinUCB++\,}}
\newcommand{\kl}{{\tt KL\,}}



\newcommand{\yinglun}[1]{{\color{blue}{YZ:#1}}}
\newcommand{\rob}[1]{{\color{magenta}{RN:#1}}}


% hyperref makes hyperlinks in the resulting PDF.
% If your build breaks (sometimes temporarily if a hyperlink spans a page)
% please comment out the following usepackage line and replace
% \usepackage{icml2021} with \usepackage[nohyperref]{icml2021} above.
\usepackage{hyperref}

% Attempt to make hyperref and algorithmic work together better:
% \newcommand{\theHalgorithm}{\arabic{algorithm}}

% Use the following line for the initial blind version submitted for review:
% \usepackage[]{icml2021}

% If accepted, instead use the following line for the camera-ready submission:
\usepackage[accepted]{icml2021}

% The \icmltitle you define below is probably too long as a header.
% Therefore, a short form for the running title is supplied here:
\icmltitlerunning{Pareto Optimal Model Selection in Linear Bandits}


\begin{document}

\twocolumn[
\icmltitle{Pareto Optimal Model Selection in Linear Bandits}

% It is OKAY to include author information, even for blind
% submissions: the style file will automatically remove it for you
% unless you've provided the [accepted] option to the icml2021
% package.

% List of affiliations: The first argument should be a (short)
% identifier you will use later to specify author affiliations
% Academic affiliations should list Department, University, City, Region, Country
% Industry affiliations should list Company, City, Region, Country

% You can specify symbols, otherwise they are numbered in order.
% Ideally, you should not use this facility. Affiliations will be numbered
% in order of appearance and this is the preferred way.
\icmlsetsymbol{equal}{*}

\begin{icmlauthorlist}
\icmlauthor{Yinglun Zhu}{uwm}
\icmlauthor{Robert Nowak}{uwm}
\end{icmlauthorlist}

\icmlaffiliation{uwm}{University of Wisconsin-Madison, Wisconsin, USA}


\icmlcorrespondingauthor{Yinglun Zhu}{yinglun@cs.wisc.edu}

% You may provide any keywords that you
% find helpful for describing your paper; these are used to populate
% the "keywords" metadata in the PDF but will not be shown in the document
\icmlkeywords{Machine Learning, ICML}

\vskip 0.3in
]

% this must go after the closing bracket ] following \twocolumn[ ...

% This command actually creates the footnote in the first column
% listing the affiliations and the copyright notice.
% The command takes one argument, which is text to display at the start of the footnote.
% The \icmlEqualContribution command is standard text for equal contribution.
% Remove it (just {}) if you do not need this facility.

\printAffiliationsAndNotice{}  % leave blank if no need to mention equal contribution
% \printAffiliationsAndNotice{\icmlEqualContribution} % otherwise use the standard text.

\begin{abstract}
We study a model selection problem in the linear bandit setting, where the learner must adapt to the dimension of the optimal hypothesis class on the fly and balance exploration and exploitation. More specifically, we assume a sequence of nested linear hypothesis classes with dimensions $d_1 < d_2 < \dots$, and the goal is to automatically adapt to the smallest hypothesis class that contains the true linear model. Although previous papers provide various guarantees for this model selection problem, the analysis therein either works in favorable cases when one can cheaply conduct statistical testing to locate the right hypothesis class or is based on the idea of ``corralling" multiple base algorithms which often performs relatively poorly in practice. These works also mainly focus on upper bounding the regret. In this paper, we first establish a lower bound showing that, even with a fixed action set, adaptation to the unknown intrinsic 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 also bring new ideas, i.e., constructing virtual mixture-arms to effectively summarize useful information, into the model selection problem in linear bandits. Under a mild assumption on the action set, we design a Pareto optimal algorithm with guarantees matching the rate in the lower bound. Experimental results confirm our theoretical results and show advantages of our algorithm compared to prior work.
\end{abstract}



\section{Introduction}
\label{sec:intro}
Model selection considers the problem of choosing an appropriate hypothesis class to conduct learning, and the hope is to optimally balance two types of error: the approximation error and the estimation error. In the supervised learning setting, the learner is provided with a countable sequence of hypothesis classes (usually nested) $\cH_1$, $\cH_2, \dots$, e.g., polynomials of degree at most $d$ and linear classifiers in $\R^d$; and the goal is to learn from a hypothesis class $\cH_\star$ that optimally trades-off approximation error and estimation error. Structure risk minimization \citep{vapnik1974theory, vapnik1995nature, shawe1998structural} provides a principled way to conduct model selection and could automatically adapt to the complexity of the hypothesis class $\cH_\star$, with only additional logarithmic costs. Meanwhile, cross-validation \citep{stone1978cross, craven1978smoothing, shao1993linear} serves as a helpful tool to conduct model selection in practice.

Despite the importance and popularity of model selection in the standard supervised learning setting, only very recently, researchers start to study on model selection problems in interactive/sequential learning setting with bandit feedback. Two additional difficulties are highlighted in such bandit seeting \citep{foster2019model}: (1) decisions/actions must be made online/sequentially without seeing the entire dataset; and (2) the learner's actions influence what data is observed, i.e., we only have partial/bandit feedback. Note that in the simpler online learning setting with full information feedback, model selection results analogous to those in the supervised learning setting are obtained by several parameter-free online learning algorithms \citep{mcmahan2013minimax, orabona2014simultaneous, koolen2015second, luo2015achieving, orabona2016coin, foster2017parameter, cutkosky2017online, cutkosky2018black}.


The model selection problem for linear (contextual) bandits is first introduced by \citet{foster2019model}, where the they consider a sequence of nested linear classifiers in $\R^{d_i}$ as the set of hypothesis classes, with $d_1 < d_2 < \cdots < d_M = d$. The goal is to adapt to the smallest hypothesis class, with a prior \emph{unknown} dimension $d_\star$, that still preserve the linear structure in reward. Equivalently, one can think of the model selection problem as learning the true reward parameter $\theta_\star \in \R^d$, but only with the first $d_\star$ dimension of $\theta_\star$ being non-zero. The goal is to design algorithms that could automatically adapt to the true dimension $d_\star$, rather than suffering from the ambient dimension $d$. In favorable scenarios when one can cheaply test linearity, \citet{foster2019model} provide an algorithm with regret guarantee scales as $\widetilde{O}(K^{1/4} T^{3/4}/\gamma^2 + \sqrt{T K d_{\star}}/\gamma^4)$, where $K$ is the number of arms and $\gamma$ is the smallest eigenvalue of the expected design matrix. The core idea therein is to conduct a sequential test, with sublinear sample complexity, to determine whether to step into a larger hypothesis class on the fly. Although this provides the first guarantee for model selection problem in the linear bandit setting, the regret bound scales inversely proportional to $\gamma$ and the dependence in the number of arms $K$ prevents the application of such algorithm to moderately-large action sets. Recall that, when provided with the optimal hypothesis class, the classical algorithm \linucb \citep{chu2011contextual, auer2002using} for linear bandit achieves a regret bound $\widetilde{O}(\sqrt{d_\star T})$, with only polylogarithmic dependence on $K$ and no dependence on the smallest eigenvalue of the design matrix. 


The model selection problem in linear bandits was later on further studied by many followups papers. We roughly divide these methods into the following two sub-categories:
\begin{enumerate}
    \item \textbf{Testing in favorable cases.} The algorithm in \citet{ghosh2020problem} conducts a sequence of statistical tests to gradually estimate the true support (non-zero entries) of $\theta_\star$, and then apply linear bandit algorithms on supports that are likely to be non-zero. The regret bound of their algorithm scales as $\widetilde{O}(d^2/\gamma^{4.65} + d^{1/2}_{\star}T^{1/2})$ where $\gamma = \min\{|\theta_{\star,i}|:\theta_{\star, i} \neq 0\}$ is the minimum magnitude of non-zero entries in $\theta_\star$. Their regret bound not only depends on the ambient dimension $d$ but also scales inversely proportional to a small quantity $\gamma$. Note that both $d$ and $\gamma$ could be made arbitrarily large so that the bound becomes vacuous. \citet{chatterji2020osom} consider a slightly different model selection problem between a linear model and a $K$-armed bandit. Assumptions needed therein are even stronger than the ones used in \citet{foster2019model}.
    
    
    
    \item \textbf{Corralling multiple base algorithms.} Another type of algorithm maintains multiple base algorithms and design a master algorithm to determine sample allocation among base algorithms. This type of algorithm is initiated by the \corral algorithm \citep{agarwal2017corralling}. Focusing on our model selection setting, these subroutines are usually constructed using standard linear bandit algorithms with respect to different hypothesis classes. As an example, algorithms in \citet{pacchiano2020model} achieves regret guarantees scale as $\widetilde{O}(d_{\star}\sqrt{T})$ or $\widetilde{O}(d^{1/2}_{\star}T^{2/3})$. Similar type of algorithms, including some concurrent work, can be found in \citet{abbasi2020regret, arora2020corralling, pacchiano2020regret, cutkosky2020upper}. 
    

\end{enumerate}

We could notice that above algorithms either only work in favorable cases when $\gamma$ is large enough or have to balance over multiple base algorithms which often hurts its empirical performance (as we will show in \cref{sec:experiment}). They also mainly focus on developing upper bounds for the model selection problem in linear bandits.
In this paper, we explore the fundamental limit of such model selection problem and design algorithms with matching guarantees. We establish a lower bound, using only a fixed action set, indicating that adaptation to the unknown intrinsic 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 also inject new ideas, i.e., constructing virtual mixture-arms to effectively summarize useful information \citep{hadiji2019polynomial, zhu2020regret}, into the model selection problem in linear bandits and design a Pareto optimal algorithm. 



Although the terms adaptivity and interactivity are usually used interchangably in classical sequential decision making settings, we distinguish them here due to the special need to adapt to the optimal hypothesis class. In the reminding of this paper, we use the term \emph{adaptivity} to describe the procedure of automatically adapting to nicer structures and thus avoid paying worst-case price with respect the non-structural case; and use the term \emph{interactivity} to capture the interactive procedure of choosing which arm/action to select next, according to previously collected feedback.




\subsection{Contribution and Outline}
We make the following contribtuions. In \cref{sec:setting}, we review the model selection problem in linear bandits and additionally encode the tension between time horizon and the optimal dimension into a single parameter which we call the hardness level of the problem. Although previous papers provide guarantees for the model selection problem in some favorable scenarios, we establish a lower bound, using only a fixed action set, in \cref{sec:lower_bound} indicating that the model selection problem is strictly harder than the problem with given optimal hypothesis class: there is no algorithm that can achieve the non-adaptive $\widetilde{O}(\sqrt{d_\star T})$ regret bound simultaneously for all values of $d_\star$. In \cref{sec:adaptivity}, under a mild expressive assumption on the action set, which can actually be satisfied in the lower bound construction, we design a Pareto optimal algorithm with guarantees matching the rate derived from the lower bound. We also provide a workaround to remove the assumption. Our algorithm depends on the novel idea of constructing an extended linear bandit problem that also incorporates past information summarized in virtual mixture-arms, which could be of independent interests. Experiments conducted in \cref{sec:experiment} confirm our theoretical results and show advantages of our algorithm over prior work. We conclude our paper in \cref{sec:conclusion} with several open problems. Most of the proofs are deferred to the Appendix due to lack of space.

\subsection{Other Related Work}



\textbf{Bandit with large/infinite action space.} Adaptivity issues natrually raises in bandit problems with large or infinite action space. In continuum-armed bandit problems \citep{agrawal1995continuum}, actions are embedded into a bounded subset $\X \subseteq \R^d$ with a smooth function $f$ governing the mean payoff for each arm. Achievable theoretical guarantees are usually influenced by some smoothness parameters, and an important question is to design algorithms adapting to these \emph{unknown} parameters, as discussed in \citet{bubeck2011lipschitz}. When the goal is pure exploration or simple regret minimization, \citet{grill2015black, bartlett2018simple, shang2019general} achieve near-optimal guarantees with unknown regularities because their objectives trade-off exploitation in favor of exploration. In the case of cumulative regret minimization, however, \citet{locatelli2018adaptivity} shows that no strategy can be optimal simultaneously over all smoothness classes. \citet{hadiji2019polynomial} borrows the concept of Pareto optimality from economics and design algorithms that are Pareto optimal. When the action space is large but with possibly multiple best arms, \citet{zhu2020regret} prove impossible results on adaptivity with the usual minimax guarantees and provide an algorithm that is Pareto optimal. Techniques used in this paper are mainly inspired by \citet{zhu2020regret, hadiji2019polynomial, locatelli2018adaptivity}.


\textbf{High dimensional linear bandit.} As more and more complex data are being used and analyzed, modern applications of linear bandit algorithm usually involves dealing with ultra-high dimensional data, sometimes even larger than the allowed time horizon \citep{deshpande2012linear}. In such high-dimensional regime, one natrual thing to consider is to assume sparsity in the reward vector and try to adapt to the unknown true support (non-zero entries). The sparse bandit problem is strictly harder than the model selection setting considered here due to the absence of the hierarchical structures. However, a lower bound on the regret in the order of $\Omega(\sqrt{d T})$, which scales with the ambient dimension $d$, is indeed unavoidable in such sparse linear bandit problem \citep{abbasi2012online, lattimore2020bandit}. Other papers deal with the sparsity setting with additional feature feedback \citep{oswal2020linear} or further distributional/structual assumptions \citep{carpentier2012bandit, hao2020high} to circumvent the lower bound. These high dimensional linear bandit problems motivate us to study the relation between time horizon and data dimension.



\section{Problem Setting}
\label{sec:setting}

We consider the linear bandit problem with $\theta_\star \in \R^{d}$, but only have its first $d_\star \leq d$ coordinates being non-zero. The model selection problem aims at designing algorithm that could automatically adapt to the intrinsic dimension $d_\star$ in the interactive learning setting with bandit feedback.

We use ${\cal A} \subseteq \R^{d}$ to represent the available action set and let $|{\cal A}| = K$. We assume that $\| a \| \leq 1$ for any action $a \in {\cal A}$, as well as the reward parameter $\| \theta_\star \| \leq 1$. At each time step $t \in [T]$,\footnote{For any positive integer $k$, we let $[k]$ denote the set $\{1, 2, \dots, k\}$.} the algorithm selects an action $A_t \in {\cal A}$ and receives a reward $X_t = \langle A_t, \theta_\star \rangle + \eta_t$ where $\eta_t$ is an independent $1$-sub-Gaussian noise so that that $\E [X_t \, \vert \, A_t] = \langle A_t, \theta_\star \rangle$.\footnote{We say a random variable $X$ is $\sigma$-sub-Gaussian if $\E[\exp(\lambda X)] \leq \exp(\sigma^2 \lambda^2/2)$ for all $\lambda \in \R$. } We define the (random) pseudo regret (due to randomness in $A_t$) over time horizon $T$ as 
\begin{align}
    \widehat{R}_T = \sum_{t=1}^T \left\langle \theta_\star,  a_\star - {A_t} \right\rangle, \nonumber
\end{align}
where $a_\star$ corresponds to the best action in action set, i.e., $a_\star = \argmax_{a \in {\cal A}} \langle a, \theta_\star \rangle$. We measure the performance of any algorithm by its expected regret
\begin{align*}
    R_{T} = \E \left[ \widehat{R}_T \right] = \E \left[ \sum_{t=1}^T \left\langle \theta_\star,  a_\star - {A_t} \right\rangle \right].
\end{align*}
We primarily focus on the high dimensional linear bandit setting with the ambient dimension $d$ is close to or even larger than the allowed time horizon $T$. We make no further restrictions on $d$ (which can be infinite dimensional as well) since our algorithm won't be affected by a large ambient dimension $d$. We use ${\cal R}(T, d_\star)$ to denote the set of regret minimization problems with allowed time horizon $T$ and any bandit instance whose reward vector $\theta_\star \in \R^d$ has intrinsic dimension $d_\star$. Time horizon $T$ is emphasized to be part of the problem, which was largely neglected in previous work focusing on the low dimensional regime where $T \gg d_\star$. To model the tension between the allowed time horizon and the intrinsic dimension, we define
\begin{align*}
    \psi \left({\cal R}(T, d_\star) \right) = \inf \{ \alpha \geq 0: d_\star \leq T^{\alpha}  \} = \log_T d_\star,
\end{align*}
and call it the hardness level of ${\cal R}(T, d_\star)$: $\psi({\cal R}(T, d_\star))$ captures the (worst case) regret over problems in ${\cal R}(T, d_\star)$, as shown later in our review of the \linucb algorithm and the lower bound. Since smaller $\psi({\cal R}(T, d_\star))$ indicates easier problems, we define the family of regret minimization problems with hardness level at most $\alpha$ as 
\begin{align}
	{\cal H}_T(\alpha) = \{ \cup {\cal R}(T, d_\star) : \psi({\cal R}(T, d_\star))\leq \alpha \} \nonumber,
\end{align}
where $\alpha \in [0, 1]$. Although $T$ is needed to define regret minimization problems, the hardness of the problem is encoded into a single parameter $\alpha$: (family of) problems with different time horizons but the same $\alpha$ are equally difficult in terms of the regret achieved by \linucb (the exponent of $T$). We can thus study problems with sufficiently large $T$ and mainly focus on the polynomial dependence on $T$. We are interested in designing algorithms with worst guarantees over ${\cal H}_T(\alpha)$, but \emph{without} the knowledge of $\alpha$. 

We provide a brief review of results regarding linear bandit problems in the following.
 
 \textbf{\linucb and upper bound.} In the standard linear bandit setting where $d_\star$ is known exactly, \linucb \cite{chu2011contextual, auer2002using} achieves $\widetilde{O}(\sqrt{d_\star T})$ regret. For any problem in ${\cal H}_T(\alpha)$ with \emph{known} $\alpha$, one could run \linucb on the first $\floor*{T^{\alpha}}$ coordinates and achieve $\widetilde{O}(T^{(1+\alpha)/2})$ regret. As in previous work \citep{foster2019model}, we aim at adapting to this regret bound yet without the knowledge of $\alpha$.
 
 \textbf{Lower bound.} In the case when $d_\star \leq \sqrt{T}$, \citet{chu2011contextual} prove a $\Omega(\sqrt{d_\star T})$ lower bound for linear bandits. When $d_\star \geq \sqrt{T}$ is the case, a lower bound $\Omega(K^{1/4} T^{3/4})$ is developed by \citet{abe2003reinforcement}.




\section{Lower Bound and Pareto Optimality}
\label{sec:lower_bound}

In this section, we construct a lower bound indicating that adaptation at the usual rate is not possible. We then explore the fundamental limit of the model selection problem in linear bandits, which leads us to the notion of Pareto optimality.


We construct the following lower bound by comparing the regret between two (sets of) problems with different hardness levels. The lower bound is constructed using only a fixed action set.

\begin{restatable}{theorem}{lowerBound}
	\label{thm:lower_bound}
	For any $0 \leq \alpha^\prime < \alpha \leq 1$, assume $T^{\alpha} \leq B$ and $\lfloor T^\alpha/2 \rfloor \geq \max\{ T^\alpha/4, T^{\alpha^\prime}, 2\}$. If an algorithm is such that $\sup_{\omega \in {\cal H}_T(\alpha^\prime)} R_T \leq B$, then the regret of this algorithm on ${\cal H}_T(\alpha)$ is lower bounded as follows:
	\begin{align}
	\sup_{\omega \in {\cal H}_T(\alpha)} R_T \geq 2^{-10} T^{1+\alpha} B^{-1} .\label{eq:lower_bound}
	\end{align}
\end{restatable}




\cref{thm:lower_bound} provides a negative answer to the question of achieving regret guarantees $\widetilde{O}(T^{(1+\alpha)/2})$ simultaneously for all hardness levels $\alpha$. An interpretation is provided in the following.



\textbf{Interpretation.} For any fixed algorithm, we consider two problems with different hardness levels $\alpha^\prime$ and $\alpha$ such that $0 \leq \alpha^\prime < \alpha \leq 1$. On one hand, if the algorithm is such that $\sup_{\omega \in {\cal H}_T(\alpha^\prime)} R_T = \widetilde{\omega}(T^{(1+\alpha^\prime)/2})$, we know that this algorithm is already sub-optimal over problems with hardness level $\alpha^\prime$. On the other hand, suppose that the algorithm achieves the desired regret $\widetilde{O}(T^{(1+\alpha)/2})$ over ${\cal H}_T(\alpha^\prime)$. \cref{eq:lower_bound} then tells us that $\sup_{\omega \in {\cal H}_T(\alpha)} R_T = \widetilde{\Omega}(T^{(1+2\alpha - \alpha^\prime)/2})$, which is clearly larger than the desired regret $\widetilde{O}(T^{(1+\alpha)/2})$ over problems with hardness level $\alpha$.


The construction of lower bound in \cref{thm:lower_bound} relies on bandit instances with $K = O(T)$ arms. As a result, if we aim at providing regret bounds with only polylogarithmic dependence on $K$ in linear bandits,\footnote{As it is usually the case for linear bandit problems with finite action set \citep{auer2002using, chu2011contextual}.} our lower bound also provides a negative answer to the question of achieving a weaker guarantee $\widetilde{O}(T^\gamma d_\star^{1-\gamma}) = \widetilde{O}(T^{\gamma + \alpha(1-\gamma)})$, with $\gamma \in [1/2,1)$ \citep{foster2019model}, simultaneously for all $d_\star$ (or $\alpha$), when there are no additional assumptions. Results regarding model selection in general contextual bandit setting \citep{foster2020open} do not conflict with our lower bound since $\poly(K)$ dependence is allowed there.



To further explore the fundamental limit for model selection in linear bandits, we capture the performance of any algorithm by its polynomial dependence on $T$ in the asymptotic sense. The hardness level of a regret minimization problem is encoded into the parameter $\alpha$.

\begin{definition}
	\label{def:rate}
	Let $\theta:[0,1] \rightarrow [0, 1]$ denote a non-decreasing function. An algorithm achieves the rate function $\theta$ if 
	\begin{align}
		\forall \epsilon > 0, \forall \alpha \in [0, 1], \quad \limsup_{T \rightarrow \infty} \frac{\sup_{\omega \in {\cal H}_T(\alpha)} R_T}{T^{\theta(\alpha)+\epsilon}} < + \infty. \nonumber 
	\end{align}
\end{definition}


A function ${\theta^\prime}$ is strictly smaller than another function $\theta$ in pointwise order if ${\theta^\prime}(\alpha) \leq \theta(\alpha)$ for all values of $\alpha$ and ${\theta^\prime}(\alpha_0) < \theta(\alpha_0)$ for at least one $\alpha_0$.
However, a pointwise ordering over rate functions doesn't always exist. To compare rate functions achieved by different algorithms, following \citet{hadiji2019polynomial, zhu2020regret}, we introduce the notion of Pareto optimality.

\begin{figure}[h]
    \vspace{-10pt}
    \centering
    \includegraphics[width = 0.5\textwidth]{pareto_rate.pdf}
    \vspace{-15pt}
    \caption{Pareto optimal rates for model selection in linear bandits.}
    \label{fig:pareto_rate}
\end{figure}


\begin{definition}
	\label{def:pareto}
	A rate function $\theta(\alpha)$ is Pareto optimal if it is achieved by an algorithm, and there is no other algorithm that can achieve a strictly smaller rate function $\theta^\prime$ in pointwise order. An algorithm is Pareto optimal if it achieves a Pareto optimal rate function.
\end{definition}




\begin{restatable}{theorem}{thmRateLowerBound}
    \label{thm:rate_lower_bound}
Suppose a rate function $\theta$ is achieved by an algorithm, then we have 
\begin{align}
\label{eq:rate_lower_bound}
    \theta(\alpha) \geq \min \{ \max \{ \theta(0), 1 + \alpha - \theta(0) \}, 1 \},
\end{align}
with $\theta(0) \in [1/2, 1]$.
\end{restatable}



\cref{thm:rate_lower_bound} provides lower bounds on the Pareto optimal rate functions, as shown in \cref{fig:pareto_rate}. These lower bounds will be complemented by Pareto optimal algorithms introduced in \cref{sec:adaptivity}.




\section{An Adapative Algorithm: \linucbPlus}
\label{sec:adaptivity}

We provide our algorithm \linucbPlus in this section. The algorithm is analyzed in \cref{section:adaptive_analysis} and further discussed in \cref{sec:remove_assumption}. We introduce additional notations as follows.


For any vector $a \in \R^d$ and $0 \leq d_i \leq d$, we use $a^{(d_i)} \in \R^{d_i}$ to represent the truncated version of $a$ that only keeps its first $d_i$ dimensions. We also use $[a_1; a_2]$ to represent the concatenated vector of $a_1$ and $a_2$. We denote $\A^{(d_i)} \subseteq \R^{d_i}$ as the ``truncated" action (multi-) set, i.e., 
\begin{align}
	{\cal A}^{(d_i)} = \left\{ a^{(d_i)}   \in \R^{d_i}: a \in {\cal A} \right\}. \nonumber
\end{align}
Although we do not really have those ``truncated" arms in a lower dimensional space, one can always manually truncate the action set and \emph{pretend} to work with arms with such feature representations.



\begin{algorithm}[]
	\caption{\linucbPlus}
	\label{alg:linucbPlus} 
	\renewcommand{\algorithmicrequire}{\textbf{Input:}}
	\renewcommand{\algorithmicensure}{\textbf{Output:}}
	\begin{algorithmic}[1]
		\REQUIRE Time horizon $T$ and a user-specified parameter $\beta \in [1/2, 1)$.
		\STATE \textbf{Set:} $p = \lceil \log_2 T^\beta \rceil$, $d_i = \min\{2^{p+2-i}, d\}$ and $\Delta T_i = \min \{ 2^{p + i}, T\}$.
		\FOR {$i = 1, \dots, p$}
		\STATE Operate \linucb with respect to an extended linear bandit problem for $\Delta T_i$ time steps. The set of arms considered includes the ``truncated" action set ${\cal A}^{(d_i)}$ \emph{and} the set of virtual mixture-arms $\{\widetilde{\nu}_j\}_{j < i}$ constructed in previous iterations.
		\STATE Construct a virtual mixture-arm $\widetilde{\nu}_i$ according to the vector $\widehat p_i$ of empirical sampling frequencies of \linucb.
		\ENDFOR 
	\end{algorithmic}
\end{algorithm}

\cref{alg:linucbPlus} operates in iterations with geometrically increasing length, and it applies \linucb with respect to different set of arms in each iteration. To give a better understanding of \linucbPlus, we next explain in detail the construction of virtual mixture-arms and the extended linear bandit problem that \linucbPlus/\linucb operates on in each iteration.

\textbf{The virtual mixture-arm.} Let $\widehat{p}_j$ denote the vector of empirical sampling frequencies over arms played in iteration $j$, i.e., the $k$-th element of $\widehat{p}_j$ is the number of times arm $k$ (could also be a previously constructed virtual mixture-arm) was sampled in iteration $j$ divided by the total number of time steps $\Delta T_j$). The virtual mixture-arm for iteration $j$, denoted by $\widetilde{\nu}_j$, is the $\widehat{p}_j$-mixture of the arms played in iteration $j$. When \linucb samples from the virtual mixture-arm $\widetilde{\nu}_j$, it first draws a real arm $j_t \sim \widehat{p}_j$ with (its true) feature representation $A_t$ (may need to sample multiple times, if first sampled the index of another virtual mixture-arm), then pull the real arm $A_t$ to obtain a reward $X_t = \langle \theta_\star, A_t \rangle + \eta_t$.



Conditioning on information $\F_{j}$ collected up to the end of the $j$-th iteration, the (conditional) expected reward of virtual mixture-arm $\widetilde{\nu}_{j}$ can be expressed as the total pseudo reward obtained in iteration $j$ divided by the corresponding time horizon $\Delta T_j$:
\begin{align}
    \widetilde{\mu}_{j \vert \F_j} 
    & = \E [\widetilde{\nu}_j \vert \F_j] =  \sum_{t  \text{ in iteration $j$}} \angleb{\theta_\star, A_t}   / \Delta T_j \nonumber \\
    & =  \langle \theta_\star, a_\star \rangle - \widehat R_{\Delta T_j}/\Delta T_j \in [-1, 1], \label{eq:expected_reward_virtual} 
\end{align}
where we use $\widehat R_{\Delta T_j}$ to denote the pseudo regret suffered in iteration $j$. Conditioning on $\F_j$, let $X_t$ be the reward obtained by pulling the virtual arm $\widetilde{\nu}_j$ (with $A_t$ being the feature representation of the real arm drawn), we then know that $X_t - \widetilde{\mu}_{j \vert \F_j}$ is $\sqrt{2}$-sub-Gaussian since $X_t - \widetilde{\mu}_j = \left(X_t - \langle \theta_\star, A_t \rangle \right) + \left(\langle \theta_\star, A_t \rangle - \widetilde{\mu}_{j \vert \F_j}  \right) = \eta_t + \left(\langle \theta_\star, A_t \rangle - \widetilde{\mu}_{j \vert \F_j}  \right)$: $\eta_t$ is $1$-sub-Gaussian by assumption and $\left(\langle \theta_\star, A_t \rangle - \widetilde{\mu}_{j \vert \F_j}  \right)$ is $1$-sub-Gaussian due to boundedness $\langle \theta_\star, A_t \rangle \in [-1, 1]$ and $\E [\langle \theta_\star, A_t \rangle \vert \F_j] = \widetilde{\mu}_{j \vert \F_j}$.

Virtual mixture-arms $\widetilde{\nu}_j$ provide a convenient summary of the information collected in the $j$-th iterations so that we don't need to explore arms in the (effectively) $d_j$ dimensional space again. Leveraging virtual mixture-arms is one key aspect in our theoretical analysis. 


\textbf{The extended linear bandit problem.} We consider the linear bandit problem in iteration $i$, where each arm in ${\cal A}^{(d_i)}$ is viewed as a vector in $\R^{d_i}$. Feature representations of arms are lifted into a slightly higher dimensional space to incorporate information of the additional $i-1$ virtual mixture-arms constructed in previous iterations. More specifically, we augment $i-1$ zeros to the feature representation of each (truncated) real arm $a \in \A^{(d_i)}$; we also view each virtual mixture-arm $\widetilde{\nu}_j$ as a $d_i +i-1$ dimensional vector $\widetilde{\nu}^{\langle d_i \rangle }_j$ with its $(d_i + j)$-th entry being $1$ and all other entries being $0$. As a result, \linucb will operate on an extended linear bandit problem with action set ${\cal A}^{\langle d_i \rangle } \subseteq  \R^{d_i + i - 1}$, where
\begin{align}
	{\cal A}^{\langle d_i \rangle } = \left\{ [a^{(d_i)}; 0] \in \R^{d_i + i - 1}:  a \in {\cal A} \right\} \cup \left\{ \widetilde{\nu}_j^{\langle d_i \rangle}: j<i \right\}, \nonumber 
\end{align}
and $\vert {\cal A}^{\langle d_i \rangle } \vert =  K + i-1$.


Suppose the feature representation of arm $a_i \in \A$ is $[a_{i1}, a_{i2}, \dots, a_{id}]^\top \in \R^{d}$. Let $\widetilde{A} \in \R^{(K+i-1 \times d_i + i - 1)}$ denote the matrix whose row vectors are feature representations of arms in $\A^{\angleb{d_i}}$, we then have
\begin{align}
	\widetilde{A} = \begin{bNiceMatrix} 
		a_{11} & a_{12} & \cdots & a_{1d_i} & 0 &  \cdots & 0    \\
		a_{21} & a_{22} & \cdots & a_{2d_i} & 0  &\cdots & 0 \\
		\vdots & \vdots & \ddots & \vdots  & \vdots  & \ddots & \vdots \\
		a_{K1} & a_{K2} & \cdots & a_{Kd_i} & 0  & \cdots & 0 \\
		0 & 0 & \cdots & 0 & 1 &  \cdots & 0    \\
		\vdots & \vdots & \ddots & \vdots  & \vdots & \ddots & \vdots \\
		0 & 0 & \cdots & 0 & 0 &  \cdots & 1    \\
   \end{bNiceMatrix}, \nonumber 
\end{align}
where the top $K$ rows are feature representations of real arms in the extended linear bandit problem, and the bottom $(i-1)$ rows are those for the virtual mixture-arms (the bottom right corner in $\widetilde{A}$ is a $(i-1)\times (i-1)$ identity matrix). 



\subsection{Analysis}
\label{section:adaptive_analysis}


We analyze \linucbPlus with the following assumption to preserve linear structure of rewards for ``truncated" arms. A workaround without this assumption is provided in \cref{sec:remove_assumption}.



\begin{assumption}
	\label{assumption:action_set}
An action set ${\cal A} \subseteq \R^d$ is expressive if we have $a^{[d_i]} = [a^{(d_i)};0] \in {\cal A}$ for any $a \in {\cal A}$ and $d_i < d$.
\end{assumption}

\begin{remark}
    It is worth mentioning that the action set we used to construct the lower bound in \cref{thm:lower_bound} can actually be made expressive, as noted in \cref{rm:expressive_lower_bound} in the Appendix. \cref{assumption:action_set} is mild since there are abundant applications where it actually holds true. As an example, suppose $a \in \R^3$ represents the action of serving a combo of steak, brocolli and roast potato, one could then naturally view $a^{[2]}$ as the action of serving only steak and brocolli. More generally, service providers usually have the freedom to select any combination of services to provide.
\end{remark}



Equipped with \cref{assumption:action_set}, we can replace the ``truncated" action set $\A^{(d_i)}$ with real arms that already exist. As a result, the linear reward structures are actually preserved in the extended linear bandit problem, albeit with a slightly different $d_i +i -1$ dimensional reward vector ${\theta}_\star^{\langle d_i \rangle}$, i.e.,
\begin{align}
    {\theta}_\star^{\langle d_i \rangle } =  \left[\theta_\star^{(d_i)}; \widetilde{\mu}_{1\vert \F_1}; \dots;  \widetilde{\mu}_{i-1\vert \F_{i-1}}\right] \in \R^{d_i + i -1}. \nonumber
\end{align}
In each iteration of \linucbPlus, we can then apply \linucb to learn this ${\theta}_\star^{\langle d_i \rangle}$ and only suffer regret proportional to $d_i + i -1$, rather than the ambient dimension $d$.

For a (possibly random) set of arms $S$, we use $a_{S} = \argmax_{a \in S} \langle \theta_\star, a \rangle$ to denote the arm with the highest expected reward. For an algorithm that only operates with respect to arms in $S$, we decompose its regret into approximation error and learning error as follows:
\begin{align}
\label{eq:regret_decomposition}
R_T = & \underbrace{ \E \left[ T \cdot \langle \theta_\star, a_\star - a_S \rangle  \right] }_{\text{expected approximation error due to the selection of $S$}} \nonumber \\
& + \underbrace{ \E \left[ \sum_{t=1}^T \langle \theta_\star, a_S - A_t \rangle\right]}_{\text{expected learning error due to the sampling rule $\{A_t\}_{t=1}^T$}}.
\end{align}

Since there are at most $O(\log T)$ iterations of \linucbPlus, we only need to upper bound its regret at each iteration. The regret suffered in each iteration is decomposed into approximation error and learning error, which are then bounded separately.


\textbf{The learning error.} In each iteration $i$, \linucbPlus implements \linucb on an equivalent linear bandit problem in $\R^{d_i +i - 1}$ for $\Delta T_i$ time steps, where $d_i$ and $\Delta T_i$ are specifically chosen so that ${d_i \Delta T_i} \leq \widetilde{O}(T^{2\beta})$. Thanks to the the regret bound on \linucb, the learning error will be upper bounded by $\widetilde{O} (\sqrt{d_i \Delta T_i}) = \widetilde{O}(T^\beta)$, as shown in the following lemma. 

\begin{restatable}{lemma}{lmLinucbLearningError}
    \label{lm:linucb_learning_error}
    At each iteration $i \in [p]$, the expected learning error suffered from subroutine \linucb is upper bounded by 
    \begin{align}
        {O} \left(\log^{5/2} \left( KT\log T\right) \cdot T^\beta \right). \nonumber 
    \end{align}
\end{restatable}

\textbf{The approximation error.} Let $i_\star \in [p]$ denote the largest integer such that $d_{i_\star} \geq d_\star$. For iterations $i \leq i_\star$, since $\theta_\star$ only has its first $d_\star \leq d_i$ coordinates being non-zero, we have $\max_{a \in \A^{\angleb{d_i}}} \{ \angleb*{\theta_\star^{\angleb{d_i}}, a} \} = \angleb{\theta_\star, a_\star}$ and the expected approximation error equals zero.\footnote{Expectation is taken with respect to possible randomness in $S$, after virtual mixture-arms are constructed.} As a result, we can upper bound the expected regret for iteration $i \leq i_\star$ by its expected learning error, i.e., $R_{\Delta T_i} \leq \widetilde{O}(T^\beta)$. For iterations $i > i_\star$, we will always have the virtual mixture-arm $\widetilde{\nu}_{i_\star}$ included. Since the expected reward of the mixture-arm $ \widetilde{\nu}_{i_\star}$ is $\widetilde{\mu}_{i_\star} = \E[\widetilde{\mu}_{i_\star \vert \F_{i_\star}}] = \langle \theta_\star, a_\star \rangle -  R_{\Delta T_{i_\star}}/\Delta T_{i_\star}$, according to \cref{eq:expected_reward_virtual}, we further have the expected approximation error upper bounded by $T R_{\Delta T_j}/\Delta T_j = \widetilde{O}(T^{1+\alpha - \beta})$. 

Regret bound of \linucbPlus is formally stated in the following.


\begin{restatable}{theorem}{thmLinucbPlus}
	\label{thm:linucbPlus}
	Run \linucbPlus with time horizon $T$ and an user-specified parameter $\beta \in [1/2, 1)$ leads to the following upper bound on the expected regret:
	\begin{align}
	& \sup_{\omega \in {\cal H}_T(\alpha)} R_T \nonumber \\
    & \leq  O \left(  \log^{7/2} \left( KT\log T\right)  \cdot T^{\min \{\max\{\beta, 1  + \alpha - \beta \},1 \}} \right). \nonumber 
	\end{align} 
\end{restatable}


\begin{remark}
    We primarily focus on polynomial dependence on $T$ in the regret bound. The polylogarithmic term could potentially be made tighter.
\end{remark}

The next theorem shows that operating \linucbPlus with any input $\beta \in [1/2, 1)$ leads to a Pareto optimal algorithm, which then completes the results indicated in \cref{fig:pareto_rate}.



\begin{restatable}{theorem}{pareto}
	\label{thm:pareto}
	The rate function achieved by \linucbPlus with any input $ \beta \in [1/2, 1)$, i.e.,
	\begin{align}
	\theta_{\beta}: \alpha \mapsto \min \{ \max \{ \beta, 1 + \alpha - \beta\}, 1\}, \label{eq:pareto_rate}
	\end{align}
	is Pareto optimal.
\end{restatable}

\begin{remark}
    Naively running \linucb on the first $\ceil*{T^\beta}$ coordinates will not lead to a Pareto optimal algorithm, since a strictly smaller rate function can be achieved by running \linucbPlus with $\beta^\prime = (1+\beta)/2$.
\end{remark}


\subsection{Removing \cref{assumption:action_set}}
\label{sec:remove_assumption}

\cref{assumption:action_set} is used to make sure that the linear structure of rewards are preserved even when we are working with truncated feature vectors. Although there are works dealing with mis-specified linear bandits, they either crucially depend on the ability to cheaply test linearity \citep{ghosh2017misspecified}, or suffer an additive $\epsilon \sqrt{d} T$ term in the regret \citep{lattimore2020learning, foster2020adapting}, where $\epsilon$ is the mis-specification level. In fact, \citet{lattimore2020learning} also provide a lower bound showing that the additive term $\epsilon \sqrt{d} T$ is unavoidable in the worst case.

We don't know how to deal with possible mis-specifications in our setting when \cref{assumption:action_set} does not hold. However, a natural workaround is to leverage the idea of ``corralling" \citep{agarwal2017corralling, pacchiano2020model}. More specifically, in each iteration $i \in [p]$ of \linucbPlus, we apply \smoothCorral \citep{pacchiano2020model} as the master algorithm with two smoothed base algorithms: (1) a \linucb algorithm that works with truncated feature representations in $\R^{d_i}$, with possible mis-specifications; and (2) a \ucb algorithm that works only with the set of virtual mixture-arms, if there exists any. The learning rate of \smoothCorral is always optimally tuned with respect to the \linucb base, i.e., $\eta = 1/\sqrt{d_i \Delta T_i}$. For iterations such that $d_i \geq d_\star$, the \linucb is the optimal base and we incur $\widetilde{O}(\sqrt{d_i \Delta T_i}) = \widetilde{O}(T^\beta)$ regret; a good enough virtual mixture-arm $\widetilde{\nu}_{i_\star}$ is then constructed as before. For later iterations such that $d_i < d_\star$, \smoothCorral incurs regret $\widetilde{O}(\max \{T^{1+\alpha - \beta}, T^{\beta}\})$ thanks to guarantees of the \ucb base: the $\widetilde{O}(T^{1+\alpha - \beta})$ term is due to the approximation error and the $\widetilde{O}(T^\beta)$ term is due to the learning error. Although the learning error of \ucb is enlarged from $\widetilde{O}(\sqrt{T})$ to $\widetilde{O}(T^\beta)$, as \smoothCorral is always tuned with respect to the \linucb base, this won't affect the resulted Pareto optimal algorithm.

The way we remove \cref{assumption:action_set} inevitably applies the idea of ``corralling". Removing the assumption without corralling is left as an important open question, and we defer more discussions to \cref{sec:conclusion}. A $\widetilde{O}(d_\star \sqrt{T})$ regret bound is presented in \citet{pacchiano2020model}, using \smoothCorral with $O(\log d)$ base algorithms, for the model selection problem in linear bandit. Upon inspection of their analysis, we notice that \smoothCorral can actually achieve the rate function in \cref{eq:pareto_rate} by setting the learning rate $\eta = T^{-\beta}$, implying that it too is Pareto optimal. We refer readers to \citet{pacchiano2020model} for details of \smoothCorral and its guarantees. We empirically compare the performance of their algorithm to ours in the next section.





\section{Experiments}
\label{sec:experiment}


In this section, we compare the performance of \linucbPlus to the original \linucb, a \linucbOracle algorithm that operates \linucb with \emph{known} $d_\star$, and the \smoothCorral from \citet{pacchiano2020model}. \smoothCorral is implemented with $M =\lceil \log_2 d \rceil$ base {\tt LinUCB}s working with different dimensions $d_i \in \{2^0, 2^1, \dots, 2^M\}$; and the learning rate is set as $\eta = 1/\sqrt{MT}$. We set $\beta = 1/2$ for \linucbPlus so that it has the same theoretical guarantee as \smoothCorral. The regularization parameter $\lambda$ for least squares in (all subroutines/bases of) \linucb is set as $0.1$. All results are averaged over $100$ trials. Shaded areas represent 2 standard deviations.





We consider a regret minimization problem with time horizon $T = 2500$ and a bandit instance of $K=1000$ arms in the $d=500$ dimensional ambient space. For any intrinsic dimension $d_\star$, the reward parameter $\theta_\star$ is selected as $[1/\sqrt{d_\star}, \dots, 1/\sqrt{d_\star}, 0, \dots, 0]$. Features of arms are generated uniformly at random (fresh randomness for each trial) from the unit sphere in $\R^d$. Arms generated this way tend to have small reward in magnitude (roughly within $[-0.15, 0.15]$ when $d_\star = 12$). To prevent lengthy exploration over exploitation, zero mean Gaussian noise are generated with $0.1$ standard deviation. Although \cref{thm:linucbPlus} holds with an expressive action set, we test \linucbPlus here with a non-expressive action set where mis-specifications could possibly occur. We also test algorithms in a small-scale problem setting (due to computational inefficiency of \linucb with large action set) with an expressive action set.


\begin{figure}[h]%
		\centering
		\subfigure[]{{\includegraphics[width=.23\textwidth]{regret_curve_nonexpressive.pdf} }}
		\subfigure[]{{\includegraphics[width=.23\textwidth]{regret_wrt_alpha_nonexpressive.pdf} }}%
        \caption{Experiments \emph{without} an expressive action set: (a) Illustration of regret curves with $\alpha \approx 0.32$. (b) Regret comparison with respect to different $\alpha$.}
		\label{fig:non_expressive}
\end{figure}


\cref{fig:non_expressive} shows experimental results conducted \emph{without} an expressive action set. \cref{fig:non_expressive}(a) provides an illustration of how regret curves of different algorithms increase. The experiment is run with the intrinsic dimension $d_\star = 12$, which results in a hardness level $\alpha \approx 0.32$. Although with possible mis-specifications, \linucbPlus greatly outperforms both \linucb and \smoothCorral, and enjoys much smaller variance. \linucbPlus has almost flatten its regret curve, while the regret curve of both \linucb and \smoothCorral keep increasing at certain slopes. \cref{fig:non_expressive}(b) demonstrates the performance of algorithms with respect to different intrinsic dimensions. We run experiments with $d_\star \in \{5,10,15,20,25,30, 35\}$, and mark the corresponding $\alpha$ values in the plot. \linucbPlus consistently outperforms \linucb and \smoothCorral across all $\alpha$s and enjoys smaller variance. These results indicate that \linucbPlus can be practically applied without an expressive action set, at least in some natural settings (as those used to generate \cref{fig:non_expressive}). The curve of \linucb is not changing with respect to $\alpha$ since it always works in the ambient dimension. Possible reasons for the relatively poor performance of \smoothCorral include: (1) maintaining multiple base algorithms hurts its overall empirical performance; (2) the algorithm suffers two regrets for each update in order to construct smoothed base algorithms \citep{pacchiano2020model}. 




\begin{figure}[h]%
		\centering
		\subfigure[]{{\includegraphics[width=.23\textwidth]{regret_curve_expressive.pdf} }}
		\subfigure[]{{\includegraphics[width=.23\textwidth]{regret_wrt_alpha_expressive.pdf} }}%
		\caption{Similar experiments as those shown in \cref{fig:non_expressive}, but with an expressive action set.}
		\label{fig:expressive}
\end{figure}


\cref{fig:expressive} shows experimental results conducted \emph{with} an expressive action set. $K=500$ arms are generated uniformly at random from a $d=300$ dimensional unit ball. We then construct an expressive action set (by adding more truncated arms with respect to \linucbPlus) and provide it to all other algorithms. The range of reward among arms are changed (tend to be enlarged) due to the change of ambient dimension, which causes some differences in the regrets. However, the shape of curves appearing in both \cref{fig:non_expressive}(a) and (b) are similar to those in \cref{fig:non_expressive}, and \linucbPlus outperforms both \smoothCorral and \linucb. One slight difference is that, when $\alpha$ gets larger, \linucbPlus has relatively worse performance compared to its curve in \cref{fig:non_expressive}(b): its regret increases at a larger slope. Our guess is that truncated arms tend to have smaller reward in magnitude, and thus working on an expressive action set could empirically hurt the performance. \linucb works better in this lower dimensional space and mostly outperforms \smoothCorral. However, we do not intend to compare the performance of \linucb and \smoothCorral here. In fact, increasing the ambient dimension $d$ tends to worse the performance of \linucb, but generally will not (greatly) affect the performance of other algorithms.


\section{Conclusion and Open Problems}
\label{sec:conclusion}

We study the model selection problem in linear bandits where the goal is to adapt to the \emph{unknown} intrinsic dimension $d_\star$, rather than suffering regret proportional to the ambient dimension $d$. We first establish a lower bound showing that, even with a fixed (and expressive) action set, adaptation to the unknown intrinsic 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$. Under the mild assumption of an expressive action set, we design a Pareto optimal algorithm with guarantees matching the rate in the lower bound. We also provide a workaround to remove the assumption. Experimental results confirm our theoretical results and show advantages of our algorithm over prior work.

We leave open several questions. First off, the current \linucbPlus works with a fixed action set. A fixed action set is needed to construct virtual arms, which are mixtures of previous actions, and to provide guarantees of their expected rewards. Similar guarantees hold under the following assumptions: (1) we have a nested sequence of action sets $\A_t \subseteq \A_{t+1}$ with $|\A_T| \leq K$; and (2) one of the best arm belongs to $\A_1$. Action sets $\A_t$ are allowed to be chosen adversarially (but expressive), since \linucb itself is compatible with adversarial contexts. How to remove/weaken these assumptions is left as an important open question.

Another open problem is to remove the assumption of an expressive action set by dealing with a possibly mis-specidied linear bandit problem (and thus without using the idea of ``corralling"). We make use of the expressiveness to preserve the linear reward structure of truncated real arms. Although we cannot avoid an additive $\epsilon \sqrt{d} T$ term in the regret in the worst case \citep{lattimore2020learning}, our problem do have a special structure, i.e., the reward of virtual mixture-arms are always well-specified.





\clearpage

% Acknowledgements should only appear in the accepted version.
% \section*{Acknowledgements}

% \textbf{Do not} include acknowledgements in the initial version of
% the paper submitted for blind review.

% If a paper is accepted, the final camera-ready version can (and
% probably should) include acknowledgements. In this case, please
% place such acknowledgements in an unnumbered section at the
% end of the paper. Typically, this will include thanks to reviewers
% who gave useful comments, to colleagues who contributed to the ideas,
% and to funding agencies and corporate sponsors that provided financial
% support.


% In the unusual situation where you want a paper to appear in the
% references without citing it in the main text, use \nocite
% \nocite{langley00}

\bibliography{pareto_optimal_linear.bbl}
\bibliographystyle{icml2021}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% DELETE THIS PART. DO NOT PLACE CONTENT AFTER THE REFERENCES!
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\clearpage
\appendix
\onecolumn

\section{Omitted Proofs for \cref{sec:lower_bound}}


\subsection{Proof of \cref{thm:lower_bound}}
We consider $K+1$ bandit instances with a \emph{fixed} common action set but reward vectors $\theta_i \in \R^{d}$, $0 \leq i \leq K$, with different intrinsic dimension $d_\star$ (or equivalently $\alpha$). For a fixed time horizon $T$, these $K+1$ regret minimization problems can be divided into two sub-groups with different hardness levels $0 \leq \alpha^\prime < \alpha \leq 1$. We assume that $T$ is large enough so that $T^\alpha/2 \geq T^{\alpha^\prime}$; and that $d$ is large enough so that $d \geq T^\alpha$. We consider the reward generation process with noise drawn from ${\cal N}(0, 1/4)$.

Explicit constructions of $\{\theta_i\}_{i=0}^{K}$ are provided in the following, with $\Delta \in \R$ to be specified later. 
\begin{enumerate}
    \item Let $\theta_0 \in \R^{d}$ be any vector such that it is only supported on one of its first $\lfloor T^{\alpha^\prime} \rfloor$ coordinates and $\| \theta_0 \|_2 = \Delta/2$. The regret minimization problem with respect to $\theta_0$ belongs to ${\cal H}_T(\alpha^\prime)$ by construction.
    
    \item For any $i \in [K]$, let $\theta_i = \theta_0 + \Delta \cdot e_{\rho(i)}$ where $e_j$ is the $j$-th canonical base and $\rho(i) = \lfloor T^{\alpha}/2 \rfloor + i$. We set $K = \lfloor T^{\alpha}/2 \rfloor = \Theta(T^\alpha)$ so that the regret minimization problem with respect to $\theta_i$ belongs to ${\cal H}_T(\alpha)$.
\end{enumerate}
The common \emph{fixed} action set considered is ${\cal A} = \{a_i\}_{i=0}^K  = \{\theta_0 / \norm*{\theta_0}\} \cup \{ e_{\rho(i)} \}_{i=1}^{K}$, and we set $a_0 = \theta_0 / \norm*{\theta_0}$ and $a_i = e_{\rho(i)}$ for convenience. We use instance $\theta_i$ to refer to the regret minimization problem/bandit instance associated with reward vector $\theta_i$. One can see that $a_0$ is the best arm for instance $\theta_0$, which has expected reward $\Delta/2$; and $a_i$ is the best arm for instance $\theta_i$, which has expected reward $\Delta$.

\begin{remark}
\label{rm:expressive_lower_bound}
    The action set $\A$ can be made expressive by augmenting the action set with an all-zero action. The all-zero action will not affect our analysis since it always has $0$ expected reward.
\end{remark}

We use the tuple of random variables $H_T = (A_1, X_1, \dots, A_T, X_T)$ to represent the outcome of interaction between an algorithm/policy and a bandit instance. A sequence of measurable spaces $\{(\Omega_t, {\cal F}_t)\}_{t=1}^T$ is defined as $\Omega_t = \prod_{i=1}^t (\A \times \R)$ and ${\cal F}_t = \mathfrak{B}(\Omega_t)$. Random variables $A_1, X_1, \dots, A_t, X_t$ that make up the outcome are defined by their coordinate projections:
\begin{align}
A_t(a_1, x_1, \dots, a_t, x_t) = a_t \quad \mbox{and} \quad X_t(a_1, x_1, \dots, a_t, x_t) = x_t. \nonumber
\end{align}
The probability measure $\Prob_{i, T}$ over $(\Omega_T, {\cal F}_T)$, with respect to any fixed algorithm/policy $\pi = (\pi_t)_{t=1}^T$ and bandit instance $\theta_i$ is now constructed. $\pi_t$ is a probability kernel, from $(\Omega_{t-1}, {\cal F}_{t-1})$ to $(\A, 2^{\A})$, used to model the arm selection process (the first probability kernel $\pi_1(\omega, \cdot)$ is defined arbitrarily over $(\A, 2^{\A})$, according to the policy). Another probability kernel $p_{i, t}$, from $(\Omega_{t-1} \times \A, {\cal F}_{t-1} \otimes 2^{\A})$ to $(\R, \mathfrak{B}(\R))$, is used to model the reward generating process: for any $B \in \mathfrak{B}(\R)$, we have
\begin{align}
p_{i, t} \big( (a_1, x_1, \dots, a_t), B\big) =  \bigintssss_B \sqrt{\frac{2}{\pi}} \exp \big( - 2 (x-\theta_i^{\top} a_t ) \big) dx ,\nonumber 
\end{align}
since the reward is distributed according to ${\cal N}(\theta_i^{\top} a_t, 1/4 )$.

The probability measure $\Prob_{i, T}$ over $(\Omega_T, {\cal F}_T)$ is defined recursively by $\Prob_{i, t} = p_{i, t} \big( \pi_{t} \Prob_{i, t-1} \big)$. $\E_i$ is used to denote the expectation taken with respect to $\Prob_{i, T}$. Two supporting statements regarding probability measures are provided as follows.

\begin{proposition}\citep{lattimore2020bandit}
	\label{prop:KL_decomposition}
	The $\kl$ divergence between two (induced) probability measures can be decomposed as follows:
	\begin{align}
	\kl \left( \Prob_{0, T}, \Prob_{i, T} \right) = \E_{0} \left[ \sum_{t=1}^T \kl\left( {\cal N}(\theta_0^{\top} A_t, 1/4), {\cal N} \left( \theta^{\top}_i A_t, 1/4 \right) \right) \right]. \nonumber 
	\end{align}
\end{proposition}
\begin{lemma} \citep{hadiji2019polynomial}
	\label{lm:pinsker}
	Let $\Prob$ and $\Q$ be two probability measures. For any random variable $Z \in [0, 1]$, we have \begin{align}
	|\E_{\Prob}[Z] - \E_{\Q}[Z]| \leq \sqrt{\frac{\kl(\Prob, \Q)}{2}}. \nonumber
	\end{align}
\end{lemma}



\lowerBound*

\begin{proof}
    We consider any fixed algorithm/policy $\pi$. Bandit instances $\{\theta_i\}_{i=0}^K$ with a common action set $\A$ is constructed as before. $N_{i}(T) = \sum_{t=1}^T \mathds{1}\left( A_t = a_i\right)$ is used to denote the number of times arm $a_i$ is selected up to time $T$. We use $R_{i, T}$ to denote the expected regret with respect to bandit instance ${\theta}_i$. Based on the construction of bandit instances and the common action set, we have 
	\begin{align}
	R_{0, T} \geq \frac{\Delta}{2} \sum_{i=1}^K \E_{0} \left[ N_{i}(T) \right], \label{eq:regret_0}
	\end{align}
	and for any $i \in [K]$
	\begin{align}
	R_{i, T} \geq \frac{\Delta}{2} \left( T - \E_{i} [N_{i}(T)] \right) = \frac{T\Delta}{2} \left( 1- \frac{\E_{i} [N_{i}(T)]}{T} \right). \label{eq:regret_i}
	\end{align}
	The $\kl$-divergence between two probability measures can be further written as
	\begin{align}
	\kl(\Prob_{0, T}, \Prob_{i, T}) & = \E_{0} \left[ \sum_{t=1}^T \kl\left( {\cal N}(\theta_0^{\top}A_t, 1/4), {\cal N} \left( \theta_i^{\top}A_t, 1/4 \right) \right) \right] \label{eq:kl_divergence}\\
	& = \E_{0} \left[ \sum_{t=1}^T 2 \left\langle \theta_i - \theta_0, A_t \right \rangle^2 \right] \nonumber \\
	& = 2 \E_{0} \left[ N_{i}(T) \right] \Delta^2, \label{eq:kl_difference}
	\end{align}
	where \cref{eq:kl_divergence} comes from \cref{prop:KL_decomposition}; \cref{eq:kl_difference} comes from the fact that $\theta_i = \theta_0 + \Delta \cdot e_{\rho(i)}$ and the only arm in ${\cal A}$ with non-zero value on the $\rho(i)$-th coordinate is $a_i = e_{\rho(i)}$, with $\angleb*{\theta_i - \theta_0, a_i} = \Delta$. Note that \cref{eq:regret_0}, \cref{eq:regret_i} and \cref{eq:kl_difference} hold true even after an all-zero action is added into the action set, due to the reason mentioned in \cref{rm:expressive_lower_bound}.
	
	The average regret over instances $\{\theta_i\}_{i=1}^K$ can be lower bounded as follows:
	\begin{align}
	\frac{1}{K} \sum_{i=1}^K R_{i, T} &  \geq  \frac{T \Delta}{2} \left(1 - \frac{1}{K} \sum_{i=1}^K \frac{\E_i [N_{i}(T)]}{T} \right) \nonumber \\
	& \geq \frac{T \Delta}{2} \left(1- \frac{1}{K}\sum_{i=1}^K \left(\frac{\E_0 [N_{i}(T)]}{T} + \sqrt{\frac{\kl(\Prob_{i, T}, \Prob_{0, T})}{2}}  \right) \right) \label{eq:ave_regret_pinsker} \\
	& = \frac{T \Delta}{2} \left(1- \frac{1}{K} \frac{\sum_{i=1}^K \E_0 [N_{i}(T)]}{T} - \frac{1}{K}\sum_{i=1}^K \sqrt{{\E_{0} \left[ N_{i}(T) \right] \Delta^2}}   \right) \label{eq:ave_regret_decomposition} \\
	& \geq \frac{T \Delta}{2} \left(1 - \frac{1}{K} - \sqrt{\frac{\sum_{i=1}^K \E_{0} \left[ N_{i}(T) \right] \Delta^2}{K}} \right) \label{eq:ave_regret_concave}\\
	& \geq \frac{T \Delta}{2} \left(1 - \frac{1}{K} - \sqrt{\frac{2 \Delta R_{0, T}}{K}} \right) \label{eq:ave_regret_0} \\
	& \geq \frac{T \Delta}{2} \left(\frac{1}{2} - \sqrt{\frac{2 \Delta B}{K}} \right), \label{eq:ave_regret}
	\end{align}
	where \cref{eq:ave_regret_pinsker} comes from applying \cref{lm:pinsker} with $Z = {N_{i}(T)}/{T}$ and $\Prob = \Prob_{i, T}$ and $\Q = \Prob_{0, T}$; \cref{eq:ave_regret_decomposition} comes from the calculation of $\kl$ divergence in \cref{eq:kl_difference}; \cref{eq:ave_regret_concave} comes from a trivial bounding $\sum_{i=1}^K \E_0 [N_{i}(T)] \leq T$ and a Jensen's inequality using the concavity of $\sqrt{\cdot}$; \cref{eq:ave_regret_0} comes from the lower bound $R_{0, T}$ in \cref{eq:regret_0}; and \cref{eq:ave_regret} comes from the fact that $K = \lfloor T^{\alpha}/2 \rfloor \geq 2$ and $R_{0, T} \leq B$ by construction/assumption.
	
	To further lower bound the average regret in \cref{eq:ave_regret} with a large value, we can maximize $\Delta$ under the constraint that $\sqrt{2 \Delta B/K} \leq 1/4$. Setting $\Delta = 2^{-5}K B^{-1}$ satisfies the constraint, and further leads to 
	\begin{align}
	\frac{1}{K} \sum_{i=1}^K R_{i, T} & \geq 2^{-8} T K B^{-1} \nonumber \\
	& \geq 2^{-10} T^{1 + \alpha} B^{-1}, \label{eq:ave_regret_final}
	\end{align}
	where \cref{eq:ave_regret_final} comes from the fact that $K = \lfloor T^{\alpha}/2 \rfloor \geq T^{\alpha}/4$ by construction/assumption. The worst case regret among $\{R_{i,T}\}_{i=1}^T$ is trivially lower bounded by the average regret above.
	
	It is clear that any action $a \in \A$ satisfies $\norm*{a} \leq 1$ by construction, we only need to make sure that $\norm*{\theta_i} \leq 1$ as well. Notice that $\norm*{\theta_i} \leq \sqrt{5}\Delta/2$ by construction, it is thus suffice to show that $\Delta = 2^{-5}K B^{-1} \leq 2/\sqrt{5}$. Since $K =\lfloor T^{\alpha}/2 \rfloor \leq T^\alpha$ and $T^{\alpha} \leq B$ by construction/assumption, we have $\Delta = 2^{-5} K B^{-1} \leq 2^{-5} < 2/\sqrt{5}$, as desired.
\end{proof}


\subsection{Proof of \cref{thm:rate_lower_bound}}

\begin{lemma} 
	\label{lm:rate_comparison}
	Suppose a rate function $\theta$ is achieved by an algorithm, we then have 
	\begin{align}
	\theta(\alpha) \geq 1 + \alpha - \theta(0), \label{eq:rate_func}
	\end{align}
	for any $0 < \alpha \leq \theta(0)$.
\end{lemma}
\begin{proof}
	We consider any fixed $0 < \alpha \leq \theta(0)$. For any $\epsilon > 0$, according to the definition of the rate function in \cref{def:rate}, there exist constant $c_1$ and $c_2$ such that
	\begin{align}
	\sup_{\omega \in {\cal H}_T(0)} R_T \leq c_1 T^{\theta(0) + \epsilon} \quad \mbox{and} \quad \sup_{\omega \in {\cal H}_T(\alpha)} R_T \leq  c_2 T^{\theta(\alpha) + \epsilon} \nonumber 
	\end{align}
	for sufficiently large $T$. We now consider the two conditions required in \cref{thm:lower_bound}: (1) $T^{\alpha} \leq T^{\theta(0)} \leq B$ holds true for $B = \max\{c_1,1\} \cdot T^{\theta(0) + \epsilon}$; and (2) $\lfloor T^\alpha/2 \rfloor \geq \max\{ T^\alpha/4, T^0, 2\}$ holds true for sufficiently large $T$. \cref{thm:lower_bound} thus implies
	\begin{align}
	c_2 T^{\theta(\alpha) + \epsilon} \geq 2^{-10} T^{1 + \alpha} \left( \max\{c_1,1\} \cdot T^{\theta(0) + \epsilon} \right)^{-1} = 2^{-10} T^{1+\alpha - \theta(0) - \epsilon} /\max\{c_1,1\} ,\nonumber
	\end{align}
	which further leads to
	\begin{align}
	\theta(\alpha) + \epsilon \geq 1 + \alpha - \theta(0) - \epsilon \nonumber
	\end{align}
	for sufficiently large $T$.
	The desired result follows by letting $\epsilon \rightarrow 0$.
\end{proof}



\thmRateLowerBound*

\begin{proof}
We consider any rate function $\theta$ achieved by an algorithm. We first notice that $\theta$ is non-decreasing since ${\cal H}_T(\alpha^\prime) \subseteq {\cal H}_T(\alpha)$. Combined results in \cref{lm:rate_comparison}, we have
\begin{align}
\theta(\alpha) \geq \max \{ \theta(0), 1 + \alpha - \theta(0) \}, \label{eq:rate_comparison}
\end{align}
for any $\alpha \in (0, \theta(0)]$. This indicates $\theta(\theta(0)) = 1$ and \cref{eq:rate_lower_bound} follows by noticing that $R_T \leq O(T)$ is a trivial upper bound. Note that $\theta(0) \in [1/2, 1]$ since the minimax optimal rate among problems in ${\cal H}_T(0)$ is $1/2$ \citep{chu2011contextual}. 
\end{proof}


\section{Omitted Proofs for \cref{sec:adaptivity}}

\subsection{Modifications of \linucb}
\label{appendix:modified_linucb}

Recall that the linear reward structure is preserved in the extended linear bandit problem in \cref{alg:linucbPlus} under \cref{assumption:action_set}. Two main differences in the extended linear bandit problem from the original setting considered in \citet{chu2011contextual} are: (1) we work with $\sqrt{2}$-sub-Gaussian noise while they deal with strictly bounded noise; and (2) the norm of our reward parameter, i.e., $\| {\theta}_\star^{\langle d_i \rangle} \|$, could be as large as $1 + (p - 1) = p = \lceil \log_2(T^\beta) \rceil \leq \log_2(T) + 1 \leq 2 \log T $ when $T \geq 2$. 

To reduce clutters, we consider a $d$ dimensional linear bandit problem with time horizon $T$ and $K$ actions. We consider the reward generating process $X_t = \langle \theta_\star, A_t \rangle + \eta_t$, where $\| \theta_\star\| \leq 2 \log T$, $\| A_t \| \leq 1$ and $\eta_t$ is an independent $\sqrt{2}$-sub-Gaussian noise. The following \cref{thm:modified_linucb} takes care of these differences.

\begin{theorem}
    \label{thm:modified_linucb}
    For the modified setting introduced above, run \linucb with $\alpha = 2\sqrt{ \log (2TK/\delta)}$ leads to the following upper bound on the (random) pseudo regret, with probability at least $1-\delta$,
    \begin{align}
        {O}\left( \log^2\left( K T \log ( T) / \delta \right) \cdot \sqrt{d  T } \right) \nonumber 
    \end{align}
\end{theorem}

\begin{corollary}
	\label{corollary:linucb}
    For the modified setting introduced above, run \linucb with $\alpha = 2\sqrt{ \log (2T^{3/2}K)}$ leads to the following upper bound on the expected regret:
    \begin{align}
        {O}\left( \log^2\left( K T \log ( T)  \right) \cdot \sqrt{d  T } \right) \nonumber 
    \end{align}
\end{corollary}
\begin{proof}
	One can simply combine the result in \cref{thm:modified_linucb} with $\delta = 1/\sqrt{T}$.
\end{proof}

It turns out that in order to prove \cref{thm:modified_linucb}, we mainly need to modify Lemma 1 in \citet{chu2011contextual}, and the rest of the arguments go through smoothly. The changed exponent of the logarithmic term is due to $\| \theta_\star\| \leq 2 \log T$. We introduce the following notations. Let
\begin{align*}
    V_t = V_{t-1} + A_t A_t^\top \quad \text{with} \quad V_0 = I  
\end{align*}
denote the design matrix up to time $t$; and let
\begin{align*}
    \widehat{\theta}_t = V_t^{-1}\sum_{i=1}^t A_i X_i
\end{align*}
denote the estimate of $\theta_\star$ at time $t$. 

\begin{lemma}(modification of Lemma 1 in \citet{chu2011contextual})
    Suppose for any fixed sequence of selected actions $\{A_i\}_{i \leq t}$ the (random) rewards $\{X_i\}_{i\leq t}$ are independent. Then we have 
    \begin{align}
        \Prob \left( \forall A_{t+1} \in \A_{t+1}: \vert \langle \widehat{\theta}_{t} - \theta_\star , A_{t+1} \rangle \vert \leq (\alpha + 2\log T) \sqrt{A_{t+1}^\top V_t^{-1} A_{t+1}} \right) \geq 1-\delta/T. \label{eq:lm_bound} 
    \end{align}
    
\end{lemma}

\begin{remark}
	The requirement of (conditional) independence is guaranted by the more complicated \suplinucb algorithm introduced in \citet{chu2011contextual}, and is not satisfied by the vanilla \linucb: the reveal/selection of a future arm $A_{t+1}$ makes previous rewards $\{X_i\}_{i \leq t}$ dependent.\footnote{See Remark 4 in \citet{han2020sequential} for a detailed discussion.} As a result, regret guarantees hold true for \suplinucb rather than \linucb. However, as recommended by \citet{chu2011contextual}, we use the more practical \linucb as our subroutine. 
\end{remark}


\begin{proof}
    For any fixed $A_t$, we first notice that 
    \begin{align}
        \abs  {\angleb {\widehat{\theta}_{t} - \theta_\star , A_{t+1} } } & = \abs { A^{\top}_{t+1} V_t^{-1}\sum_{i=1}^t A_i X_i - A^{\top}_{t+1} \theta_\star}\nonumber \\
        & = \abs{ A^{\top}_{t+1} V_t^{-1}\sum_{i=1}^t A_i X_i - A^{\top}_{t+1} V_t^{-1} \left( I + \sum_{i=1}^t A_i A_i^\top \right)\theta_\star } \nonumber \\
        & \leq  \abs{ \sum_{i=1}^t A^\top_{t+1} V^{-1}_t A_i \left( X_i - A_i^{\top} \theta_\star \right)} + \abs{A^{\top}_{t+1} V_t^{-1} \theta_\star} \nonumber \\
        & \leq \abs{ \sum_{i=1}^t A^\top_{t+1} V^{-1}_t A_i \left( X_i - A_i^{\top} \theta_\star \right)} +  \norm{A^{\top}_{t+1} V_t^{-1} } \cdot \norm{\theta_\star}. \label{eq:lm_bound_two_terms}
    \end{align}
We next bound the two terms in \cref{eq:lm_bound_two_terms} seperately.

For the first term in \cref{eq:lm_bound_two_terms}, since $\left( X_i - A_i^\top \theta_\star \right)$ is $\sqrt{2}$-sub-Gaussian and $\{X_i\}_{i \leq t}$ are independent, we know that $\sum_{i=1}^t A^\top_{t+1} V^{-1}_t A_i \left( X_i - A_i^{\top} \theta_\star \right)$ is $\left( \sqrt{2 \sum_{i=1}^t \left( A^\top_{t+1} V^{-1}_t A_i \right)^2} \right)$-sub-Gaussian. Since 
\begin{align}
    \sqrt{\sum_{i=1}^t \left( A^\top_{t+1} V^{-1}_t A_i \right)^2}  & 
    = \sqrt{\sum_{i=1}^t A_{t+1}^\top V_t^{-1} A_i A_i^\top V_t^{-1} A_{t+1}} \nonumber \\
    & \leq \sqrt{A_{t+1}^\top V_t^{-1} \left( I + \sum_{i=1}^t A_i A_i^\top \right) V_t^{-1} A_{t+1}} \nonumber \\
    & = \sqrt{A_{t+1}^\top V_t^{-1} A_{t+1}}, \nonumber 
\end{align}
combined with a standard Chernoff-Hoeffding bound, we have 
\begin{align}
    \Prob \left( \abs{ \sum_{i=1}^t A^\top_{t+1} V^{-1}_t A_i \left( X_i - A_i^{\top} \theta_\star \right)} \geq \alpha \sqrt{A_{t+1}^\top V_t^{-1} A_{t+1}} \right) & \leq 2 \exp\left( -\frac{\alpha^2}{4} \right) \nonumber \\
    & = \frac{\delta}{TK}, \label{eq:lm_bound_alpha}
\end{align}
where \cref{eq:lm_bound_alpha} is due to the choice of $\alpha$, i.e., $\alpha = 2\sqrt{\log (2TK/\delta)}$.

For the second term in \cref{eq:lm_bound_two_terms}, we have 
\begin{align}
   \norm{A^{\top}_{t+1} V_t^{-1} } \cdot \norm{\theta_\star} & \leq 2 \log T \, \sqrt{A^\top_{t+1} V^{-1}_t I V^{-1}_t A_{t+1}} \label{eq:lm_bound_norm} \\
   & \leq 2 \log T \, \sqrt{A^\top_{t+1} V^{-1}_t \left(I + \sum_{i=1}^t A_i A_i^\top \right) V^{-1}_t A_{t+1}} \nonumber \\
   & =  2 \log T \,\sqrt{A_{t+1}^\top V_t^{-1} A_{t+1}} . \nonumber 
\end{align}
where \cref{eq:lm_bound_norm} comes from the fact that $\norm{\theta_\star} \leq 2 \log T$.

The desired result in \cref{eq:lm_bound} follows from a union bound argument together with the two upper bounds derived above. 
\end{proof}



\subsection{Notations and Preliminaries for Analysis of \linucbPlus}
\label{app:preliminary_linucbPlus}

We provide some notations and preliminaries for analysis of \linucbPlus that will be used in the following two subsections, i.e., the proofs of \cref{lm:linucb_learning_error} and \cref{thm:linucbPlus}.

We define $T_i = \sum_{j = 1}^{i} \Delta T_j$ so that the $i$-th iteration of \linucbPlus goes from time $T_{i-1} + 1$ to $T_i$. \linucbPlus is a valid algorithm in the sense that it does not terminate before time $T$, i.e., $T_p \geq T$. The inequality clearly holds true if there exists $i \in [p]$ such that $\Delta T_i = \min \{2^{p+i}, T\} = T$; otherwise, the following inequalities hold true for all $\beta \in [1/2, 1]$:
	\begin{align*}
	    T_p  = \sum_{i=1}^p \Delta T_i = 2(2^{2p} - 1) \geq 2^{2p} \geq T.
	\end{align*}
We use ${\cal F}_{i}$ to represent information collected up to the end of iteration $i$. Let $R_{\Delta T_i \vert {\cal F}_{i-1}} = \Delta T_i \cdot \mu_\star - \E [\sum_{t = T_{i-1}+1}^{T_i} X_t \vert \F_{i-1} ]$ denote the expected regret suffered in iteration $i$, conditioned on $\F_{i-1}$. The expected regret in iteration $i$ can be expressed as $R_{\Delta T_i} = \E[R_{\Delta T_i \vert {\cal F}_{i-1}}]$.

In iteration $i$ of \linucbPlus, conditioning on $\F_{i-1}$, we apply \linucb with respect to a $d_i +i -1$ dimensional extended linear bandit problem with an action set $\A^{\angleb{d_i}}$ such that $\abs*{\A^{\angleb{d_i}}} \leq K + i -1$. Let $a^{\langle d_i \rangle }_{\star} = \argmax_{a \in {\cal A}^{\langle d_i \rangle}} \{\langle \theta^{\langle d_i \rangle}_{\star}, a \rangle \}$ denote the best arm in the $i$-th iteration, we can decompose the (conditional) regret as follows (similar to the decomposition in \cref{eq:regret_decomposition}):
\begin{align}
	\label{eq:regret_decomposition_internal}
	R_{\Delta T_i\vert {\cal F}_{i-1}} = \Delta T_i \cdot  \left(\langle \theta_\star, a_\star \rangle - \langle \theta_{\star}^{\langle d_i \rangle}, a_{\star}^{\langle d_i \rangle} \rangle \right) +  \E \left[ \sum_{t=T_{i-1}+1}^{T_i} \langle \theta_{\star}^{\langle d_i \rangle}, a_{\star}^{\langle d_i \rangle} - A_t \rangle \, \bigg\vert \, {\cal F}_{i-1} \right] ,
\end{align}
where $A_t \in {\cal A}^{\langle d_i \rangle}$ and $\langle \theta_{\star}^{\langle d_i \rangle}, A_t \rangle$ represents the expected reward of pulling arm $A_t$.


\subsection{Proof of \cref{lm:linucb_learning_error}}
The proof of \cref{lm:linucb_learning_error} follows the notations and preliminaries introduced in \cref{app:preliminary_linucbPlus}.

\lmLinucbLearningError*

\begin{proof}

    We focus on the second term in the decomposition \cref{eq:regret_decomposition_internal}, i.e., the expected learning error (conditioned on $\F_{i-1}$) in iteration $i$. Since both $\theta^{\langle d_i \rangle}_\star$ and $a_\star^{\angleb{d_i}}$ can be treated as fixed quantities conditioned on $\F_{i-1}$, regret bound of \linucb leads to the following result:
	\begin{align}
	\E \left[ \sum_{t=T_{i-1}+1}^{T_i} \langle \theta_{\star}^{\langle d_i \rangle}, a_{\star}^{\langle d_i \rangle} - A_t \rangle \, \bigg\vert \, {\cal F}_{i-1} \right] 
	& \leq {O} \left( \log^2 \left( (K+i-1) \Delta T_i \log (\Delta T_i) \right) \cdot \sqrt{(d_i +i -1 ) \Delta T_i  } \right) \label{eq:regret_learning_0} \\
	& \leq {O} \left( \log^2 \left( (K+p) \Delta T_i \log (\Delta T_i) \right) \cdot  \sqrt{(d_i+p) \Delta T_i}  \right) \label{eq:regret_learning_1}\\
	& \leq {O} \left(\log^2 \left( (K+p) T \log T \right)  \cdot \sqrt{2^{2p+2} + p T} \right) \label{eq:regret_learning_2} \\
	& \leq {O} \left(\log^2 \left( K T \log T \right)  \cdot \sqrt{T^{2\beta} + \log T \cdot T} \right) \label{eq:regret_learning_3} \\
	& \leq {O} \left(\log^{5/2} \left( KT\log T\right) \cdot T^\beta  \right), \label{eq:regret_learning}
	\end{align}
	where \cref{eq:regret_learning_0} comes from guarantees of \linucb in \cref{corollary:linucb}; \cref{eq:regret_learning_1} comes from the fact that $i \leq p $; \cref{eq:regret_learning_2} comes from the definition of $d_i$ and $\Delta T_i$; \cref{eq:regret_learning_3} comes from the fact that $p = \ceil*{ \log_2 T^\beta}$; and \cref{eq:regret_learning} comes from a trivially bounding $\sqrt{T^{2\beta} + \log T \cdot T} \leq O((\log T)^{1/2} \cdot T^\beta)$.\footnote{One can improve the bound to $\sqrt{T^{2\beta} + \log T \cdot T} \leq O(T^\beta)$ in many cases, e.g., when $\beta > 1/2$ and $T$ is large enough (with respect to $\beta$). However, we mainly focus on the polynomial terms here.} The desired result follows by taking another expectation over randomness in $\F_{i-1}$.
\end{proof}


\subsection{Proof of \cref{thm:linucbPlus}}
The proof of \cref{thm:linucbPlus} follows the notations and preliminaries introduced in \cref{app:preliminary_linucbPlus}.

\thmLinucbPlus*


\begin{proof}
	
    We only analyze the case when $\alpha < \beta$ since otherwise $T^{1 + \alpha - \beta} \geq T$ and \cref{thm:linucbPlus} trivially holds.

	Taking expectation on \cref{eq:regret_decomposition_internal} and combining the result in \cref{lm:linucb_learning_error}, we have
	\begin{align}
	\label{eq:regret_decomposition_internal_expectation}
	R_{\Delta T_i}  \leq  \Delta T_i \cdot  \E \left[ \left( \langle \theta_\star, a_\star \rangle -\langle \theta_{\star}^{\langle d_i \rangle}, a_{\star}^{\langle d_i \rangle} \rangle  \right) \right]  + {O} \left( \log^{5/2} \left( KT\log T\right) \cdot T^\beta \right).
	\end{align}
	We now upper bound the first term, i.e., the expected approximation error in iteration $i$. According to the definition of $\theta^{\langle d_i \rangle}_\star$ and $a^{\langle d_i \rangle}_{\star}$, we have $\langle \theta_{\star}^{\langle d_i \rangle}, a_{\star}^{\langle d_i \rangle} \rangle = \langle \theta_\star, a_\star \rangle$ if $d_i \geq d_\star$, i.e., the optimal arm is contained in the action set $\A^{\angleb{d_i}}$ and the approximation error equals zero. Let $i_\star \in [p]$ be the largest integer such that $d_{i_\star} \geq d_{\star}$ (which must exists when $\beta > \alpha$ since $d_1 = 2^{p+1} \geq T^\beta > T^\alpha \geq d_\star$), we have
	\begin{align}
	 R_{\Delta T_{i}} \leq  {O} \left( \log^{5/2} \left( KT\log T\right) T^\beta\right) \label{eq:regret_i0}
	\end{align}
	for any $i \leq i_\star$, and especially for $i = i_\star$.
	
	There will be no regret in iterations $i \geq i_\star$ when $\Delta T_{i_\star} = \min \{2^{p+i_\star}, T \}=T$ or $i_\star = p$, since \linucbPlus actually stops before the end of iteration $i_\star$ (it reaches time $T$). We thus only need to consider the case when $\Delta T_{i_\star} = 2^{p+i_\star}$ and $i_\star < p$ in the following. To incorporate another possible corner case when $d_{i_\star} = \min\{2^{p+2-i_\star}, d\} = d$, we consider $d_{i_\star + 1} = 2^{p + 1 - i_\star} < d_{i_\star}$. As a result, we have $d_{i_\star} \Delta T_{i_\star} > d_{i_\star + 1} \Delta T_{i_\star} = 2^{2p+1}$, which leads to a lower bound on $\Delta T_{i_\star}$:
	\begin{align}
	\Delta T_{i_\star} > \frac{2^{2p + 1}}{d_{i_\star}} > \frac{2^{2p }}{d_\star} \geq \frac{2^{2p }}{T^{\alpha}}, \label{eq:lower_bound_DeltaT}
	\end{align}
	where we use the fact that $ d_{i_\star} < 2 d_\star$, according to the definition of $i_\star$, and the fact that $d_\star \leq T^\alpha$.\footnote{We will have $\Delta T_{i_\star}  \geq 2^{2p+1}/d_\star > 2^{2p}/T^\alpha$ if $d_{i_\star} = \min\{2^{p+2-i_\star}, d\}  \geq 2^{p+2-i_\star}$.}
	
	Since the virtual mixture-arm $\widetilde{\nu}_{i_\star}$ (its representation $\widetilde{\nu}^{\langle d_i \rangle}_{i_\star}$) is added into the action set ${\cal A}^{\langle d_i \rangle}$, we can upper bound the expected approximation error for iterations $i > i_\star$ as follows:
	\begin{align}
    \Delta T_i \cdot  \E \left[ \left( \langle \theta_\star, a_\star \rangle -\langle \theta_{\star}^{\langle d_i \rangle}, a_{\star}^{\langle d_i \rangle} \rangle \right) \right]  & \leq \Delta T_i \cdot \E \left[\left(\langle \theta_\star, a_\star \rangle - \langle \theta_{\star}^{\langle d_i \rangle}, \widetilde{\nu}^{\langle d_i \rangle}_{i_\star} \rangle \right) \right]  \nonumber  \\
    & = \Delta T_i \cdot \left(\langle \theta_\star, a_\star \rangle -  \widetilde{\mu}_{i_\star} \right) \label{eq:regret_approximation_equivalent_form}  \\
	& = \frac{\Delta T_i}{\Delta T_{i_\star}}\cdot  R_{\Delta T_{i_\star}} \label{eq:regret_approximation_expected_reward} \\
	& < \frac{\Delta T_i}{\frac{2^{2p}}{T^\alpha }} \cdot {O} \left(\log^{5/2} \left( KT\log T\right) \cdot T^\beta  \right)\label{eq:regret_approximation_DeltaT} \\
	& \leq \frac{ {O} \left(  \log^{5/2} \left( KT\log T\right)  \cdot T^{1 + \alpha + \beta} \right) }{{2^{2p}}} \label{eq:regret_approximation_important} \\
	& \leq {O} \left( \log^{5/2} \left( KT\log T\right) \cdot T^{1  + \alpha - \beta} \right), \label{eq:regret_approximation}
	\end{align}
	where \cref{eq:regret_approximation_equivalent_form} comes from the formulation of the extended linear bandit problem; \cref{eq:regret_approximation_expected_reward} comes from that fact that $\widetilde{\mu}_{i_\star} = \E [\widetilde{\mu}_{i_\star \vert \F_{i_\star}}]=\langle \theta_\star, a_\star \rangle -  R_{\Delta T_{i_\star}}/\Delta T_{i_\star}$, according to \cref{eq:expected_reward_virtual}; \cref{eq:regret_approximation_DeltaT} comes from the regret bound for $R_{\Delta T_{i_\star}}$ according to \cref{eq:regret_i0} and the lower bound on $\Delta T_{i_\star}$ in \cref{eq:lower_bound_DeltaT}; \cref{eq:regret_approximation_important} comes from the fact that $\Delta T_i \leq T$; and \cref{eq:regret_approximation} comes from the fact that $p = \lceil \log_2 T^{\beta} \rceil \geq \log_2 T^{\beta}$.
	
	Expected regret for iterations $i > i_\star$ can be upper bounded by combining \cref{eq:regret_approximation} with \cref{eq:regret_decomposition_internal_expectation} as follows:
\begin{align}
    R_{\Delta T_i}  & \leq  {O} \left( \log^{5/2} \left( KT\log T\right) \cdot T^{\max\{\beta, 1  + \alpha - \beta \}} \right), \nonumber 
\end{align}
which also subsume regret bound for iterations $i \leq i_\star$ as shown in \cref{eq:regret_i0}.

The total expected regret, which is non-decreasing in $t$, can then be upper bounded by summing over iterations $i \in [p]$ as follows:
\begin{align}
	R_{T} & \leq \sum_{i=1}^p R_{\Delta T_i} \nonumber \\
	& = \sum_{i=1}^p {O} \left( \log^{5/2} \left( KT\log T\right) \cdot T^{\max\{\beta, 1  + \alpha - \beta \}} \right) \nonumber \\
    & = {O} \left( \log^{7/2} \left( KT\log T\right) \cdot T^{\max\{\beta, 1  + \alpha - \beta \}} \right),\nonumber
\end{align}
where we use the fact that $p = \lceil \log_2(T^\beta) \rceil = O(\log T)$.
\end{proof}

\subsection{Proof of \cref{thm:pareto}}

\pareto*

\begin{proof}
The rate function in \cref{eq:pareto_rate} is actually achieved by \linucbPlus with input $\beta \in [1/2, 1)$, as derived in \cref{thm:linucbPlus}. We only need to show that a strictly smaller (in pointwise order) rate function cannot be achieved by any other algorithms. 

We prove the result by contradiction. Suppose a strictly smaller rate function $\theta^\prime$ is achieved by another algorithm, we then have $\theta^\prime(0) \leq \theta_{\beta}(0) = \beta$. We consider the following two exclusive cases.
 
\textbf{Case 1 $\theta^\prime(0) = \beta$.} We have $\theta^\prime \geq \theta_\beta$ according to \cref{thm:rate_lower_bound}, which leads to a contradiction.

\textbf{Case 2 $\theta^\prime(0) = \beta^\prime < \beta$.} We have $\theta^\prime \geq \theta_{\beta^\prime}$ according to \cref{thm:rate_lower_bound}. However, one can notice that $\theta_{\beta^\prime}$ is \emph{not} strictly smaller than $\theta_{\beta}$ (e.g., $\theta_{\beta^\prime}(2\beta - 1) =  2\beta - \beta^\prime > \beta = \theta_{\beta}(2\beta - 1)$), which also leads to a contradiction.
\end{proof}

\subsection{Analysis for \cref{sec:remove_assumption}}

In each iteration $i \in [p]$ of \linucbPlus, we apply \smoothCorral as the master algorithm with two smoothed base algorithms: (1) a \linucb algorithm that works with truncated feature representations in $\R^{d_i}$, with possible mis-specifications; and (2) a \ucb algorithm that works only with the set of virtual mixture-arms, if there exists any. The learning rate of \smoothCorral is always optimally tuned with respect to the \linucb base, i.e., $\eta = 1/\sqrt{d_i \Delta T_i}$. Since there are at most $p = O(\log T)$ iterations, we only need to bound the expected regret at each iteration $R_{\Delta T_i}$. As before, we use $i_\star \in [p]$ to denote the largest integer such that $d_{i_\star} \geq d_\star$.

For $i \leq i_\star$, the \linucb base works on a well-specified linear bandit problem. Theorem 5.3 in \citet{pacchiano2020model} thus gives the following guarantees:
\begin{align*}
    R_{\Delta T_i} \leq \widetilde{O} \left(\sqrt{\Delta T_i} + \eta^{-1} + \Delta T_i \eta + \Delta T_i d_i \eta \right) = \widetilde{O} \left(\sqrt{d_i \Delta T_i} \right) = \widetilde{O} \left(T^\beta \right).
\end{align*}
A virtual mixture-arm $\widetilde{\nu}_{i_\star}$ that is good enough is then constructed as before and its expected reward conditioning on $\F_{i_\star}$ can be written as $\widetilde{\mu}_{i_\star \vert \F_{i_\star}} = \E [\widetilde{\nu}_{i_\star} \vert \F_{i_\star}] = \langle \theta_\star, a_\star \rangle -  \widehat R_{\Delta T_{i_\star}}/\Delta T_{i_\star}$.

We now analyze the regret incurred for iteration $i > i_\star$. Conditioning on past information $\F_{i-1}$ and let $r(\pi_t)$ denote the (conditional) expected reward of applying policy $\pi_t$, we have 
\begin{align}
    R_{\Delta T_i \vert \F_{i-1}} & = \Delta T_i \cdot   \left( \langle \theta_\star, a_\star \rangle -\widetilde{\mu}_{i_\star \vert \F_{i_\star}} \right) + \E \left[ \sum_{t \text{ in iteration } i} \widetilde{\mu}_{i_\star\vert \F_{i_\star} } - r(\pi_t) \, \bigg\vert \, {\cal F}_{i-1}  \right] \nonumber \\
    & \leq \Delta T_i \cdot   \left( \langle \theta_\star, a_\star \rangle -\widetilde{\mu}_{i_\star \vert \F_{i_\star}} \right) + \widetilde{O} \left(\sqrt{\Delta T_i} + \eta^{-1} + \Delta T_i \eta + \Delta T_i \eta \right) \nonumber ,
\end{align}
where the second term comes from the guarantee of \smoothCorral with respect to the \ucb base. Taking expectation over randomness in $\F_{i-1}$ leads to
\begin{align}
      R_{\Delta T_i }  & \leq \widetilde{O}\left(T^{1+\alpha - \beta} \right) + \widetilde{O}\left( T^\beta \right) \nonumber ,
\end{align}
where the first term follows from a similar analysis as in \cref{eq:regret_approximation}, and the second term comes from by setting $\eta = 1/\sqrt{d_i \Delta T_i}$.

\citet{pacchiano2020model} tackles the model selection problem in linear bandits by applying \smoothCorral with $O(\log d)$ base {\tt LinUCB}s working with different dimensions $d_i \in \{2^0, 2^1, \dots, 2^{\ceil*{\log d}}\}$. Let $d_{i_\star}$ denote the smallest dimension that satisfies $d_{i_\star} \geq d_\star$. With respect to the base \linucb working on the first $d_{i_\star}$ dimensions, \smoothCorral enjoys the following regret guarantee:
\begin{align}
    R_{T} \leq \widetilde{O} \left(\sqrt{T} + \eta^{-1} + T \eta + T d_\star \eta \right).
\end{align}
\smoothCorral can then achieve the rate function in \cref{eq:pareto_rate} by setting the learning rate $\eta = T^{-\beta}$ (and noticing that $d_\star \leq T^{\alpha}$).
% \section{Do \emph{not} have an appendix here}

% \textbf{\emph{Do not put content after the references.}}
% %
% Put anything that you might normally include after the references in a separate
% supplementary file.

% We recommend that you build supplementary material in a separate document.
% If you must create one PDF and cut it up, please be careful to use a tool that
% doesn't alter the margins, and that doesn't aggressively rewrite the PDF file.
% pdftk usually works fine. 

% \textbf{Please do not use Apple's preview to cut off supplementary material.} In
% previous years it has altered margins, and created headaches at the camera-ready
% stage. 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\end{document}


% This document was modified from the file originally made available by
% Pat Langley and Andrea Danyluk for ICML-2K. This version was created
% by Iain Murray in 2018, and modified by Alexandre Bouchard in
% 2019 and 2021. Previous contributors include Dan Roy, Lise Getoor and Tobias
% Scheffer, which was slightly modified from the 2010 version by
% Thorsten Joachims & Johannes Fuernkranz, slightly modified from the
% 2009 version by Kiri Wagstaff and Sam Roweis's 2008 version, which is
% slightly modified from Prasad Tadepalli's 2007 version which is a
% lightly changed version of the previous year's version by Andrew
% Moore, which was in turn edited from those of Kristian Kersting and
% Codrina Lauth. Alex Smola contributed to the algorithmic style files.

pareto_optimal_linear.bbl
\begin{thebibliography}{45}
\providecommand{\natexlab}[1]{#1}
\providecommand{\url}[1]{\texttt{#1}}
\expandafter\ifx\csname urlstyle\endcsname\relax
  \providecommand{\doi}[1]{doi: #1}\else
  \providecommand{\doi}{doi: \begingroup \urlstyle{rm}\Url}\fi

\bibitem[Abbasi-Yadkori et~al.(2012)Abbasi-Yadkori, Pal, and
  Szepesvari]{abbasi2012online}
Abbasi-Yadkori, Y., Pal, D., and Szepesvari, C.
\newblock Online-to-confidence-set conversions and application to sparse
  stochastic bandits.
\newblock In \emph{Artificial Intelligence and Statistics}, pp.\  1--9, 2012.

\bibitem[Abbasi-Yadkori et~al.(2020)Abbasi-Yadkori, Pacchiano, and
  Phan]{abbasi2020regret}
Abbasi-Yadkori, Y., Pacchiano, A., and Phan, M.
\newblock Regret balancing for bandit and rl model selection.
\newblock \emph{arXiv preprint arXiv:2006.05491}, 2020.

\bibitem[Abe et~al.(2003)Abe, Biermann, and Long]{abe2003reinforcement}
Abe, N., Biermann, A.~W., and Long, P.~M.
\newblock Reinforcement learning with immediate rewards and linear hypotheses.
\newblock \emph{Algorithmica}, 37\penalty0 (4):\penalty0 263--293, 2003.

\bibitem[Agarwal et~al.(2017)Agarwal, Luo, Neyshabur, and
  Schapire]{agarwal2017corralling}
Agarwal, A., Luo, H., Neyshabur, B., and Schapire, R.~E.
\newblock Corralling a band of bandit algorithms.
\newblock In \emph{Conference on Learning Theory}, pp.\  12--38. PMLR, 2017.

\bibitem[Agrawal(1995)]{agrawal1995continuum}
Agrawal, R.
\newblock The continuum-armed bandit problem.
\newblock \emph{SIAM journal on control and optimization}, 33\penalty0
  (6):\penalty0 1926--1951, 1995.

\bibitem[Arora et~al.(2020)Arora, Marinov, and Mohri]{arora2020corralling}
Arora, R., Marinov, T.~V., and Mohri, M.
\newblock Corralling stochastic bandit algorithms.
\newblock \emph{arXiv preprint arXiv:2006.09255}, 2020.

\bibitem[Auer(2002)]{auer2002using}
Auer, P.
\newblock Using confidence bounds for exploitation-exploration trade-offs.
\newblock \emph{Journal of Machine Learning Research}, 3\penalty0
  (Nov):\penalty0 397--422, 2002.

\bibitem[Bartlett et~al.(2018)Bartlett, Gabillon, and
  Valko]{bartlett2018simple}
Bartlett, P.~L., Gabillon, V., and Valko, M.
\newblock A simple parameter-free and adaptive approach to optimization under a
  minimal local smoothness assumption.
\newblock \emph{arXiv preprint arXiv:1810.00997}, 2018.

\bibitem[Bubeck et~al.(2011)Bubeck, Stoltz, and Yu]{bubeck2011lipschitz}
Bubeck, S., Stoltz, G., and Yu, J.~Y.
\newblock Lipschitz bandits without the lipschitz constant.
\newblock In \emph{International Conference on Algorithmic Learning Theory},
  pp.\  144--158. Springer, 2011.

\bibitem[Carpentier \& Munos(2012)Carpentier and Munos]{carpentier2012bandit}
Carpentier, A. and Munos, R.
\newblock Bandit theory meets compressed sensing for high dimensional
  stochastic linear bandit.
\newblock In \emph{Artificial Intelligence and Statistics}, pp.\  190--198,
  2012.

\bibitem[Chatterji et~al.(2020)Chatterji, Muthukumar, and
  Bartlett]{chatterji2020osom}
Chatterji, N., Muthukumar, V., and Bartlett, P.
\newblock Osom: A simultaneously optimal algorithm for multi-armed and linear
  contextual bandits.
\newblock In \emph{International Conference on Artificial Intelligence and
  Statistics}, pp.\  1844--1854, 2020.

\bibitem[Chu et~al.(2011)Chu, Li, Reyzin, and Schapire]{chu2011contextual}
Chu, W., Li, L., Reyzin, L., and Schapire, R.
\newblock Contextual bandits with linear payoff functions.
\newblock In \emph{Proceedings of the Fourteenth International Conference on
  Artificial Intelligence and Statistics}, pp.\  208--214, 2011.

\bibitem[Craven \& Wahba(1978)Craven and Wahba]{craven1978smoothing}
Craven, P. and Wahba, G.
\newblock Smoothing noisy data with spline functions.
\newblock \emph{Numerische mathematik}, 31\penalty0 (4):\penalty0 377--403,
  1978.

\bibitem[Cutkosky \& Boahen(2017)Cutkosky and Boahen]{cutkosky2017online}
Cutkosky, A. and Boahen, K.
\newblock Online learning without prior information.
\newblock \emph{arXiv preprint arXiv:1703.02629}, 2017.

\bibitem[Cutkosky \& Orabona(2018)Cutkosky and Orabona]{cutkosky2018black}
Cutkosky, A. and Orabona, F.
\newblock Black-box reductions for parameter-free online learning in banach
  spaces.
\newblock In \emph{Conference On Learning Theory}, pp.\  1493--1529, 2018.

\bibitem[Cutkosky et~al.(2020)Cutkosky, Das, and Purohit]{cutkosky2020upper}
Cutkosky, A., Das, A., and Purohit, M.
\newblock Upper confidence bounds for combining stochastic bandits.
\newblock \emph{arXiv preprint arXiv:2012.13115}, 2020.

\bibitem[Deshpande \& Montanari(2012)Deshpande and
  Montanari]{deshpande2012linear}
Deshpande, Y. and Montanari, A.
\newblock Linear bandits in high dimension and recommendation systems.
\newblock In \emph{2012 50th Annual Allerton Conference on Communication,
  Control, and Computing (Allerton)}, pp.\  1750--1754. IEEE, 2012.

\bibitem[Foster et~al.(2017)Foster, Kale, Mohri, and
  Sridharan]{foster2017parameter}
Foster, D.~J., Kale, S., Mohri, M., and Sridharan, K.
\newblock Parameter-free online learning via model selection.
\newblock In \emph{Advances in Neural Information Processing Systems}, pp.\
  6020--6030, 2017.

\bibitem[Foster et~al.(2019)Foster, Krishnamurthy, and Luo]{foster2019model}
Foster, D.~J., Krishnamurthy, A., and Luo, H.
\newblock Model selection for contextual bandits.
\newblock In \emph{Advances in Neural Information Processing Systems}, pp.\
  14741--14752, 2019.

\bibitem[Foster et~al.(2020{\natexlab{a}})Foster, Gentile, Mohri, and
  Zimmert]{foster2020adapting}
Foster, D.~J., Gentile, C., Mohri, M., and Zimmert, J.
\newblock Adapting to misspecification in contextual bandits.
\newblock \emph{Advances in Neural Information Processing Systems}, 33,
  2020{\natexlab{a}}.

\bibitem[Foster et~al.(2020{\natexlab{b}})Foster, Krishnamurthy, and
  Luo]{foster2020open}
Foster, D.~J., Krishnamurthy, A., and Luo, H.
\newblock Open problem: Model selection for contextual bandits.
\newblock \emph{arXiv preprint arXiv:2006.10940}, 2020{\natexlab{b}}.

\bibitem[Ghosh et~al.(2017)Ghosh, Chowdhury, and
  Gopalan]{ghosh2017misspecified}
Ghosh, A., Chowdhury, S.~R., and Gopalan, A.
\newblock Misspecified linear bandits.
\newblock \emph{arXiv preprint arXiv:1704.06880}, 2017.

\bibitem[Ghosh et~al.(2020)Ghosh, Sankararaman, and
  Ramchandran]{ghosh2020problem}
Ghosh, A., Sankararaman, A., and Ramchandran, K.
\newblock Problem-complexity adaptive model selection for stochastic linear
  bandits.
\newblock \emph{arXiv preprint arXiv:2006.02612}, 2020.

\bibitem[Grill et~al.(2015)Grill, Valko, and Munos]{grill2015black}
Grill, J.-B., Valko, M., and Munos, R.
\newblock Black-box optimization of noisy functions with unknown smoothness.
\newblock In \emph{Advances in Neural Information Processing Systems}, pp.\
  667--675, 2015.

\bibitem[Hadiji(2019)]{hadiji2019polynomial}
Hadiji, H.
\newblock Polynomial cost of adaptation for x-armed bandits.
\newblock In \emph{Advances in Neural Information Processing Systems}, pp.\
  1027--1036, 2019.

\bibitem[Han et~al.(2020)Han, Zhou, Zhou, Blanchet, Glynn, and
  Ye]{han2020sequential}
Han, Y., Zhou, Z., Zhou, Z., Blanchet, J., Glynn, P.~W., and Ye, Y.
\newblock Sequential batch learning in finite-action linear contextual bandits.
\newblock \emph{arXiv preprint arXiv:2004.06321}, 2020.

\bibitem[Hao et~al.(2020)Hao, Lattimore, and Wang]{hao2020high}
Hao, B., Lattimore, T., and Wang, M.
\newblock High-dimensional sparse linear bandits.
\newblock \emph{arXiv preprint arXiv:2011.04020}, 2020.

\bibitem[Koolen \& Van~Erven(2015)Koolen and Van~Erven]{koolen2015second}
Koolen, W.~M. and Van~Erven, T.
\newblock Second-order quantile methods for experts and combinatorial games.
\newblock In \emph{Conference on Learning Theory}, pp.\  1155--1175, 2015.

\bibitem[Lattimore \& Szepesv{\'a}ri(2020)Lattimore and
  Szepesv{\'a}ri]{lattimore2020bandit}
Lattimore, T. and Szepesv{\'a}ri, C.
\newblock \emph{Bandit algorithms}.
\newblock Cambridge University Press, 2020.

\bibitem[Lattimore et~al.(2020)Lattimore, Szepesvari, and
  Weisz]{lattimore2020learning}
Lattimore, T., Szepesvari, C., and Weisz, G.
\newblock Learning with good feature representations in bandits and in rl with
  a generative model.
\newblock In \emph{International Conference on Machine Learning}, pp.\
  5662--5670. PMLR, 2020.

\bibitem[Locatelli \& Carpentier(2018)Locatelli and
  Carpentier]{locatelli2018adaptivity}
Locatelli, A. and Carpentier, A.
\newblock Adaptivity to smoothness in x-armed bandits.
\newblock In \emph{Conference on Learning Theory}, pp.\  1463--1492, 2018.

\bibitem[Luo \& Schapire(2015)Luo and Schapire]{luo2015achieving}
Luo, H. and Schapire, R.~E.
\newblock Achieving all with no parameters: Adanormalhedge.
\newblock In \emph{Conference on Learning Theory}, pp.\  1286--1304, 2015.

\bibitem[McMahan \& Abernethy(2013)McMahan and Abernethy]{mcmahan2013minimax}
McMahan, B. and Abernethy, J.
\newblock Minimax optimal algorithms for unconstrained linear optimization.
\newblock \emph{Advances in Neural Information Processing Systems},
  26:\penalty0 2724--2732, 2013.

\bibitem[Orabona(2014)]{orabona2014simultaneous}
Orabona, F.
\newblock Simultaneous model selection and optimization through parameter-free
  stochastic learning.
\newblock \emph{Advances in Neural Information Processing Systems},
  27:\penalty0 1116--1124, 2014.

\bibitem[Orabona \& P{\'a}l(2016)Orabona and P{\'a}l]{orabona2016coin}
Orabona, F. and P{\'a}l, D.
\newblock Coin betting and parameter-free online learning.
\newblock \emph{Advances in Neural Information Processing Systems},
  29:\penalty0 577--585, 2016.

\bibitem[Oswal et~al.(2020)Oswal, Bhargava, and Nowak]{oswal2020linear}
Oswal, U., Bhargava, A., and Nowak, R.
\newblock Linear bandits with feature feedback.
\newblock In \emph{AAAI}, pp.\  5331--5338, 2020.

\bibitem[Pacchiano et~al.(2020{\natexlab{a}})Pacchiano, Dann, Gentile, and
  Bartlett]{pacchiano2020regret}
Pacchiano, A., Dann, C., Gentile, C., and Bartlett, P.
\newblock Regret bound balancing and elimination for model selection in bandits
  and rl.
\newblock \emph{arXiv preprint arXiv:2012.13045}, 2020{\natexlab{a}}.

\bibitem[Pacchiano et~al.(2020{\natexlab{b}})Pacchiano, Phan, Abbasi-Yadkori,
  Rao, Zimmert, Lattimore, and Szepesvari]{pacchiano2020model}
Pacchiano, A., Phan, M., Abbasi-Yadkori, Y., Rao, A., Zimmert, J., Lattimore,
  T., and Szepesvari, C.
\newblock Model selection in contextual stochastic bandit problems.
\newblock \emph{arXiv preprint arXiv:2003.01704}, 2020{\natexlab{b}}.

\bibitem[Shang et~al.(2019)Shang, Kaufmann, and Valko]{shang2019general}
Shang, X., Kaufmann, E., and Valko, M.
\newblock General parallel optimization a without metric.
\newblock In \emph{Algorithmic Learning Theory}, pp.\  762--788, 2019.

\bibitem[Shao(1993)]{shao1993linear}
Shao, J.
\newblock Linear model selection by cross-validation.
\newblock \emph{Journal of the American statistical Association}, 88\penalty0
  (422):\penalty0 486--494, 1993.

\bibitem[Shawe-Taylor et~al.(1998)Shawe-Taylor, Bartlett, Williamson, and
  Anthony]{shawe1998structural}
Shawe-Taylor, J., Bartlett, P.~L., Williamson, R.~C., and Anthony, M.
\newblock Structural risk minimization over data-dependent hierarchies.
\newblock \emph{IEEE transactions on Information Theory}, 44\penalty0
  (5):\penalty0 1926--1940, 1998.

\bibitem[Stone(1978)]{stone1978cross}
Stone, M.
\newblock Cross-validation: A review.
\newblock \emph{Statistics: A Journal of Theoretical and Applied Statistics},
  9\penalty0 (1):\penalty0 127--139, 1978.

\bibitem[Vapnik \& Chervonenkis(1974)Vapnik and Chervonenkis]{vapnik1974theory}
Vapnik, V. and Chervonenkis, A.
\newblock Theory of pattern recognition, 1974.

\bibitem[Vapnik(1995)]{vapnik1995nature}
Vapnik, V.~N.
\newblock The nature of statistical learning theory, 1995.

\bibitem[Zhu \& Nowak(2020)Zhu and Nowak]{zhu2020regret}
Zhu, Y. and Nowak, R.
\newblock On regret with multiple best arms.
\newblock \emph{arXiv preprint arXiv:2006.14785}, 2020.

\end{thebibliography}
