
\section{Introduction}\label{sec:intro}

\IEEEPARstart{M}{ulti-armed} bandit (MAB) problems, introduced by Robbins \cite{robbins1952some} model the exploration and exploitation trade-off of sequential decision making under uncertainty. In its most basic paradigm, at each time step, the decision maker is given $d$ decisions or arms from which he is supposed to select one, and as a response, he observes a stochastic reward after each decision-making. The arm chosen at each time step is based on the information gathered at all the previous time steps. Therefore, in order to maximize the expected cumulative reward, exploitation of the current empirically best arm and exploration of less frequently chosen arms should be balanced carefully.  Stochastic independence of rewards is assumed for different arms in some works like \cite{auer2002finite, lai1985asymptotically, audibert2009exploration, agrawal1995sample, burnetas1996optimal,kangrecomm, Liu2017, KlosneeMueller2018, KanTay:J19}. In other works like \cite{pandey2007multi,presman1990sequential,goldenshluger2009woodroofe,abbasi2011improved,rusmevichientong2010linearly}, reward dependence between arms is assumed, which allows the decision maker to gather information for more than one arm at each time step. One such specific assumption is that arms are vectors containing numeric elements, and the expected reward of choosing each arm is an inner product of the arm vector with an unknown parameter vector \cite{Gai2012, agrawal2013thompson, abbasi2011improved,rusmevichientong2010linearly}. In \cite{abbasi2011improved, rusmevichientong2010linearly}, the authors proposed effective strategies that balance exploration and exploitation based on the \emph{optimism-in-the-face-of-uncertainty} principle. This principle maintains a high probability confidence set for the estimated parameter vector, and at each time step, the decision maker chooses an arm and a parameter vector from the decision set and the confidence set respectively, so that their inner product is maximized. Note that the independent $d$-armed bandit problem can be viewed as a special case of the general linear stochastic bandit problem, where the set of $d$ available decisions serves as a standard orthonormal basis of $\mathbb{R}^d$\cite{abbasi2011improved}.  

The linear stochastic bandit model has been successfully applied to some real-world problems like personalized news article recommendation \cite{li2010contextual}, advertisement selection \cite{abe2003reinforcement}, and information retrieval \cite{yue2011linear}.  For example, in news recommendation applications, typical features, including the news' topic categories, the users' race, gender, location, etc., can be treated as components in each arm or decision vector, while the users' clicks are the rewards. A plausible recommendation scheme is to get as many clicks as possible. Another application is in sequential clinical trials \cite{villar2015multi,dani2008stochastic,kuleshov2014algorithms} whose aims are to balance the correct identification of the best treatment (exploration) and the effectiveness of the treatment during the trials (exploitation). The classical sequential clinical trials containing $d$ different drugs can be modeled as an independent $d$-armed bandit problem. However, this may be impractical as treatments may utilize multiple drugs simultaneously. A more feasible and general way is to model the treatment decision as a set of mixed drugs instead. An arm corresponds to a mixed drugs treatment with specific dosages of each kind. The reward at each time step is the curative efficacy after applying the mixed drug treatment to a patient at each trial. 

However, in some scenarios, the decision maker is more interested in some criterion other than maximizing the cumulative reward in the standard linear stochastic bandit model. One example is a discrimination-aware movie recommendation system. To avoid racially discriminatory recommendations, a user's race should not play any role in the recommendation system. However, the observed reward (number of clicks) may be biased by racial factors. A black user may have a history of following a particular black actor, but it does not mean that he or she should always be recommended movies with black actors.  
For example, Netflix last year angered black subscribers with targeted posters containing black actors no matter how minor their roles in the film are \cite{Black}. In principle, to avoid discrimination, protected or sensitive attributes such as race or gender should not be included in recommendation algorithms. Nonetheless, discarding such attributes directly and modeling the reward as a linear function of the other unprotected attributes may introduce system bias during the learning process. In another example, some clinical trials seek to maximize the curative effect on one disease of a mixed drugs treatment, while at the same time the patients who have this disease may concurrently have another disease. These patients need to take other drugs that have a positive or negative impact on the targeted disease. One typical example is the treatment of hypertension in chronic kidney disease. Hypertension is present in more than $80\%$ of the patients with chronic kidney disease, and drugs like ACEi and ARB targeted for reducing proteinuria may also have an effect on blood pressure\cite{toto2005treatment}. To study the effect of a mixed drug treatment targeted for controlling hypertension, the decision maker is supposed to discount the impact of drugs like ACEi and ARB in the decision process.  

In this paper, we propose a linear stochastic bandit formulation that maximizes the (expected) cumulative reward over a subspace of decision attributes, based on the reward observed for the full space. Specifically, each arm is projected orthogonally onto a target subspace $\mathbb{U}$. The reward is then decomposed into two components, one of which is due to $\mathbb{U}$, and the other is due to $\mathbb{U}^\perp$. We call the first component the \emph{projection reward} and the second component the \emph{corruption}. We develop a strategy that achieves\footnote{For non-negative functions $f(n)$ and $g(n)$, we write $f(n)=O(g(n))$ if $\limsup_{n\to\infty} f(n)/g(n)<\infty$, $f(n) = o(g(n))$ if $\lim_{n\to\infty} f(n)/g(n)=0$, and $f(n) = \Theta(g(n))$ if $0 < \liminf_{n\to\infty} f(n)/g(n) \leq \limsup_{n\to\infty} f(n)/g(n)<\infty$.} $O(|\mathbb{D}|\log n)$ cumulative projection regret when there are finitely many $|\mathbb{D}|$ arms and where $n$ is the number of time steps. In the case where the arms are drawn from an infinite compact set, we achieve a cumulative projection regret of $O(n^{2/3}(\log{n})^{1/2})$. Here, the projection regret at each time step is defined as the difference between the current expected projection reward of making one decision and the oracle best expected projection reward. This algorithm is based on the $\epsilon_t$-greedy policy \cite{auer2002finite}, which is a simple and well-known algorithm for the standard finite multi-armed bandit problem. 

\subsection{Related Work}

Two categories of work are related to our problem of interest: 1)  the linear stochastic bandit model; and 2) the multi-objective Pareto bandit problem.

In the linear stochastic bandit model, the decision maker predicts the reward of an arm in $\mathbb{R}^d$ based on the given context vector of this decision. In \cite{AuerConfidence}, the author proposed an algorithm based on least squares estimation and high probability confidence bounds, and showed that it has $O(\sqrt{dn}\log^{3/2}(n|\mathbb{D}|))$ regret upper bound for the case of finitely many decisions, where $|\mathbb{D}|$ is the number of arms. The work \cite{dani2008stochastic} extended \cite{AuerConfidence}  to the problem with an arbitrary compact set of arms and presented a policy with $O(d\sqrt{n}\log^{3/2}n)$ regret upper bound. References \cite{abbasi2011improved,rusmevichientong2010linearly} further improved the regret upper bound using smaller confidence sets established using martingale techniques. In \cite{wang2016learning}, the authors proposed a linear bandit formulation with hidden features where the reward of choosing one decision is the sum of two components, one of which is a linear function of the observable features, and the other is a linear function of the unobservable features. They applied a upper confidence bound (UCB)-type linear bandit policy with a coordinate descent \cite{uschmajew2012local,friedman2010regularization} algorithm in which estimating the hidden features and the unknown coefficients jointly over time is achieved. Our work is different from the above-mentioned papers in that we seek to maximize only the cumulative projection reward rather than the reward observed for the full space. Furthermore, the projection reward is formed by projecting both the decision arm and context vectors into a subspace.

In the stochastic multi-objective multi-armed bandit (MOMAB) problem \cite{drugan2014pareto,drugan2013designing,yahyaa2014annealing,yahyaa2014scalarized}, the reward of making one decision is a vector rather than the scalar reward in the standard multi-armed bandit problem. Because of the possible conflicting objectives, a set of Pareto optimal arms \cite{drugan2013designing} \cite{zitzler2002performance} is considered in the MOMAB problem instead of a single best arm. Scalarization techniques can be used to transform a MOMAB problem to a single objective MAB, and an arm belonging to the Pareto optimal set is regarded as a best arm in a particular scalarization function. In our work, we consider the decomposition of the reward where the decomposition is similar to a two-objective MAB applied with a linear scalarization function \cite{drugan2013designing}. However, the difference between our model and MOMAB with linear scalarization is that we can only observe the sum of the (desired) projection reward and (undesired) corruption at each time step rather than a reward vector consisting of the two components as in MOMAB. Furthermore, our objective is to minimize the cumulative projection regret rather than minimizing the three types of regret defined in \cite{drugan2013designing}. 

\subsection{Our Contributions}
In this paper, we study the orthogonal projection problem in linear bandits, where our aim is to maximize the expected projection reward, which is an unknown linear function of a projection of the chosen arm onto a target subspace $\mathbb{U} \subseteq \mathbb{R}^d$. In the case where there are finitely many arms, we develop a strategy to achieve $O(|\mathbb{D}|\log n)$ cumulative projection regret, where $n$ is the number of time steps and $|\mathbb{D}|$ is the number of arms. In the case where the arm is chosen from an infinite compact set, our strategy achieves $O(n^{2/3}(\log{n})^{1/2})$ cumulative projection regret. 

In the linear stochastic bandit literature, the best cumulative regret upper bound for the case of a compact decision set is $O(d\sqrt{n}\, \text{polylog}(n))$ \cite{abbasi2011improved, rusmevichientong2010linearly}, where $\text{polylog}(n)$ means a polynomial in $\log n$.  If a further smoothness assumption same as that in \cite{rusmevichientong2010linearly} is made, we show that it is possible to achieve the $O(d\sqrt{n})$ projection regret upper bound in our problem formulation. However, the existence of a policy with $O(d\sqrt{n}\, \text{polylog}(n))$ cumulative projection regret for the general compact decision set remains an open question for our problem. We verify our proposed policies on both synthetic simulations and experiments on a wine quality dataset \cite{cortez2009modeling}.

The rest of this paper is organized as follows. In \cref{sec:model}, we present our system model and assumptions. In \cref{sec:strategy}, we introduce our strategies and prove that they achieve sublinear cumulative projection regret. In \cref{sec:simulation}, we present simulations and experiments to verify the performance of our strategies. \Cref{sec:conclusion} concludes the paper. 

\emph{Notations:}  
We use $E^c$ to denote the complement of the event $E$. The indicator function $\indicatore{A}(\omega)=1$ if and only if $\omega\in A$. $\mathbf{I}$ is the identity matrix. For $\mathbf{x}, \mathbf{y}\in\mathbb{R}^d$, let $\mathbf{x}\T$ be the transpose of $\mathbf{x}$ , and $\ip{\mathbf{x}}{\mathbf{y}}=\mathbf{x}\T \mathbf{y}$. We use $\Vert \mathbf{x}\Vert_2$ to denote the $L_2$-norm $\sqrt{\ip{\mathbf{x}}{\mathbf{x}}}$ and $\Vert \mathbf{x}\Vert_\mathbf{A}$ to denote the weighted $L_2$-norm $\sqrt{\ip{\mathbf{x}}{\mathbf{A}\mathbf{x}}}$ for any $\mathbf{A}\in \mathbb{R}^{d\times d}$ is a positive definite matrix. We use  $\mathcal{U}(a,b)$ to denote the continuous uniform distribution whose density function has support $[a,b]$, and $\mathcal{N}(0,\vartheta^2)$ to denote the Gaussian distribution with variance $\vartheta^2$ and mean $0$. 



\section{System Model}
\label{sec:model}
Let $\mathbb{D}\subseteq \mathbb{R}^d$ be a compact set of decisions or arms from which the decision maker has to choose an arm $X_t$ at each time step $t$. The observed return $r_t$ after choosing $X_t$ is given by
\begin{align}
  r_{t} = \ip{X_t}{\bm{\theta}} + \eta_t,
  \label{eq:linear_reward}
\end{align}
where $\bm{\theta}\in\mathbb{R}^d$ is a fixed but unknown parameter and $\eta_t$ is a zero mean \gls{iid} random noise. 

In the standard linear bandit problem, the performance of a policy is measured by the difference between the decision maker's cumulative reward and the cumulative reward achieved by the oracle policy with knowledge of $\bm{\theta}$. Formally, the goal of the decision maker is to minimize the \emph{cumulative regret} over $n$ time steps defined by 
\begin{align}
  R(n) = \sum_{t=1}^{n} \big(\ip{X^*}{\bm{\theta}} - \E[\ip{X_t}{\bm{\theta}}]\big),
  \label{eq:cumregret}
\end{align}
where $X^* = \argmax_{\mathbf{x}\in \mathbb{D}}\ip{\mathbf{x}}{\bm{\theta}}$ is the optimal arm in the standard linear bandit problem.

In our orthogonal projection linear bandit model, we consider a decomposition of the observed return into two components. Let $\mathbb{U}$, whose dimension is not more than $d$, be a subspace of the Euclidean vector space $\mathbb{R}^d$. Let $\mathbb{U}^{\perp}=\{\mathbf{q}\in \mathbb{R}^d: \ip{\mathbf{q}}{\mathbf{p}} = 0, \forall \mathbf{p} \in \mathbb{U}\}$ be the orthogonal complement of $\mathbb{U}$. It is a standard result \cite{linearalgebra} that $\mathbb{R}^d = \mathbb{U} \oplus \mathbb{U}^{\perp}$, and each $\mathbf{w}\in \mathbb{R}^d$ can be written uniquely as a sum $\mathbf{p}+\mathbf{q}$, where $\mathbf{p}\in \mathbb{U}$ and $\mathbf{q}\in \mathbb{U}^{\perp}$. We define the linear orthogonal projection operator as $P_\mathbb{U}:\mathbb{R}^d \mapsto \mathbb{U}$ such that $P_\mathbb{U}(\mathbf{w})= \mathbf{p}$. The operator $P_\mathbb{U}$ can be represented by a $d\times d$ matrix whose rank is the dimension of $\mathbb{U}$. The expected observed return can therefore be decomposed as
\begin{align}
  \ip{X_t}{\bm{\theta}} &= \ip{P_\mathbb{U}(X_t) + P_{\mathbb{U}^{\perp}}(X_t)}{P_\mathbb{U}(\bm{\theta}) + P_{\mathbb{U}^{\perp}}(\bm{\theta})}\nonumber \\ 
  &= \ip{P_\mathbb{U}(X_t)}{P_{\mathbb{U}}(\bm{\theta})} + \ip{P_{\mathbb{U}^{\perp}}(X_t)}{P_{\mathbb{U}^{\perp}}(\bm{\theta})}.
  \label{eq:reward_decomp}
\end{align}
We call $\ip{P_\mathbb{U}(X_t)}{P_\mathbb{U}(\theta)}$ the \emph{projection reward} on the subspace $\mathbb{U}$, which is denoted by $r_{\mathbb{U},t}$. The other part of the observed return, $\ip{P_{\mathbb{U}^{\perp}}(X_t)}{P_{\mathbb{U}^{\perp}}(\bm{\theta})}$, is called the \emph{corruption}. Different from the standard linear bandit model, where the reward can be observed (with random perturbation), in our orthogonal projection linear bandit model, we do not directly observe the projection reward $r_{\mathbb{U},t}$. Furthermore,  the \emph{cumulative projection regret} is defined as  
\begin{align}
  R_\mathbb{U}(n) = \sum_{t=1}^{n}\big( \ip{P_{\mathbb{U}}(X_{\mathbb{U}}^*(\bm{\theta}))}{P_\mathbb{U}(\bm{\theta})} - \E[\ip{P_\mathbb{U}(X_t)}{P_\mathbb{U}(\bm{\theta})}]\big),
  \label{eq:cumprojregret}
\end{align}
where 
\begin{align}\label{eq:XU*}
  X_{\mathbb{U}}^*(\bm{\theta})= \argmax_{\mathbf{x}\in \mathbb{D}}\ip{P_\mathbb{U}(\mathbf{x})}{P_\mathbb{U}(\bm{\theta})}
\end{align} 
is the \emph{best projection arm}. The objective in our model is to minimize the cumulative projection regret $R_\mathbb{U}(n)$ rather than the cumulative regret $R(n)$, base on the observed returns $r_1,\ldots,r_{n-1}$.

For a concrete illustration, consider again the discrimination prevention problem in a movie recommendation system described in \cref{sec:intro}. An arm is a movie to be recommended to a specific set of users and is represented by the features of the movie. The features include the movie genre, movie length, music types used, ages and races of the actors or actresses, etc. Suppose that each arm is a $d$ dimensional vector, where some of its elements like the ages and races may lead to discriminatory recommendations and are ``protected''. To eliminate the effect of those features when performing the recommendations, the system should consider only the non-protected dimensions. In \cite{calders2013controlling}, the authors proposed to control the discrimination effect in a linear regression model, where $P_\mathbb{U}$ in their formulation can also be viewed as a projection matrix.

We use $\text{span}(\mathbb{D})$ to denote the set of finite linear combinations of arms in $\mathbb{D}$. In the ideal case, if at each time step $t$ the return $r_t$ is available without the random noise $\eta_t$, and if $\mathbb{D}$ is specified by linear inequality constraints, the problem then degenerates to a linear programming problem that finds $
\mathbf{x}\in \mathbb{D}$ to maximize
\begin{align}
  & \ip{P_\mathbb{U}(\mathbf{x})}{P_\mathbb{U}(\bm{\theta})} \nonumber \\
  & = \ip{P_\mathbb{U}(\mathbf{x})}{\bm{\theta}} \nonumber \\
  & = \ip{P_\mathbb{U}(\mathbf{x})}{P_{\text{span}(\mathbb{D})}(\bm{\theta})+ P_{\text{span}(\mathbb{D})^\perp}(\bm{\theta})}\nonumber \\
  & = \ip{P_\mathbb{U}(\mathbf{x})}{P_{\text{span}(\mathbb{D})}(\bm{\theta})}+ \ip{P_\mathbb{U}(\mathbf{x})}{P_{\text{span}(\mathbb{D})^\perp}(\bm{\theta})}.
  \label{eq:linear_degenerate}
\end{align}
However, since $P_{\text{span}(\mathbb{D})^\perp}(\bm{\theta})$ is unobservable even in the ideal case, and $\argmax_{\mathbf{x}\in \mathbb{D}}$ $\ip{P_\mathbb{U}(\mathbf{x})}{P_{\text{span}(\mathbb{D})}(\bm{\theta})}$ is not equal to $X_{\mathbb{U}}^*(\bm{\theta})$ in \cref{eq:XU*} when $\ip{P_\mathbb{U}(\mathbf{x})}{P_{\text{span}(\mathbb{D})^\perp}(\bm{\theta})}\ne 0$, a linear cumulative projection regret is therefore inevitable in the worst case. In order to get a sublinear cumulative regret, further assumptions are required. 

A possible assumption is $\ip{P_\mathbb{U}(\mathbf{x})}{P_{\text{span}(\mathbb{D})^\perp}(\bm{\theta})}= 0$ for all $\mathbf{x}$ and $\bm{\theta}$. This is equivalent to saying $\mathbb{U}\subseteq \text{span}(\mathbb{D})$. To see this, note that this assumption means that $P_{\text{span}(\mathbb{D})^\perp}(\bm{\theta})\in \text{kernel}(P_\mathbb{U}) = P_\mathbb{U}^{\perp} = P_{\mathbb{U}^\perp}$. It follows that $\text{span}(\mathbb{D})^\perp \subseteq \mathbb{U}^{\perp}$, which is equivalent to $\mathbb{U} \subseteq \text{span}(\mathbb{D})$. We make the following assumption throughout this paper.

\begin{Assumption}\label{as:as1}
   We have $\mathbb{U}\subseteq \text{span}(\mathbb{D})$, the dimension of $\text{span}(\mathbb{D})$ is $k$, where $\dim(\mathbb{U}) \le k\le d$, and $\|P_{\mathbb{U}}(\bm{\theta})\|_2>0$. Furthermore, the decision maker has access to $k$ linearly independent arms in  $\mathbb{D}$.
\end{Assumption}

We use $\mathbb{D}_k \subseteq \mathbb{D}$ to denote the set containing the $k$ linearly independent arms in  \cref{as:as1}. The condition $\|P_{\mathbb{U}}(\bm{\theta})\|_2>0$ guarantees $\bm{\theta}\notin \mathbb{U}^{\perp}$.  We also make another assumption which is standard in the literature for the linear bandit problem.


\begin{Assumption}\label{as:as2}
 We have $\Vert \bm{\theta} \Vert_2\le S$, and $\max_{\mathbf{x}\in \mathbb{D}} \Vert \mathbf{x}\Vert_2 \le Z$, where $S$ and $Z$ are positive finite constants. The random variables $\eta_t$ are drawn \gls{iid} from a zero-mean sub-Gaussian distribution with parameter $\vartheta$, i.e., $\E[e^{\xi\eta_t}]\le e^{\xi^2\vartheta^2/2}$ for all $\xi\in \mathbb{R}$.
\end{Assumption}








\section{Strategies and Regret Analysis}\label{sec:strategy}
\subsection{Greedy Projection Strategy}\label{ssec:GENTRY}

The decision set $\mathbb{D}$ may contain finitely or infinitely many arms. In this section, we present a strategy with two settings, the first is applicable for the finite-arm case, and the other is applicable for the infinite-arm case. In the following, we use $\hat{\bm{\theta}}_t$ to denote the $L_2$ regularized least square estimate of $\bm{\theta}$ with parameter $\lambda> 0$, after the decision making at time step $t$:
\begin{align}
  \hat{\bm{\theta}}_t =\mathbf{V}_t^{-1}\sum_{i = 1}^{t} r_iX_i,
    \label{eq:estimate}
\end{align}
where $\mathbf{V}_t=\lambda \mathbf{I} + \sum_{i=1}^{t} X_iX_i\T$. We propose a Greedy projEctioN sTRategY (GENTRY) that accounts for the corruption in the observed return to achieve sublinear cumulative projection regret. GENTRY is based on the $\epsilon_t$-greedy policy \cite{auer2002finite}, which is a simple and well-known algorithm for the standard finite multi-armed bandit problem. At each time step $t$, the $\epsilon_t$-greedy policy chooses with probability $1-\epsilon_t$ the arm with the highest empirical average reward, and with probability $\epsilon_t$ a random arm. Since in our problem, we focus our attention on the projection reward, GENTRY chooses with probability $1-\epsilon_t$ the arm with the highest empirical average projection reward defined as:
\begin{align}
  \bar{r}_{t-1}(\mathbf{x}) = \ip{P_\mathbb{U}(\mathbf{x})}{P_\mathbb{U}(\hat{\bm{\theta}}_{t-1})},
  \label{eq:finite_empirical}
\end{align}
for each arm $\mathbf{x}\in \mathbb{D}$. Another difference is, at each time step $t$, GENTRY chooses with probability $\epsilon_t$ a random arm from $\mathbb{D}_k$ rather than $\mathbb{D}$.  We define two different settings of $\epsilon_t$ as follows:
\begin{align}
  \epsilon_t^f = \min\left\{1,\frac{\alpha  k}{t}\right\} \text{ and } \epsilon_t^i = \min\left\{1,\frac{\alpha  k}{t^{1/3}}\right\}, 
  \label{eq:epsilont_i}
\end{align}
to handle the finite- and infinite-arm cases, respectively. The hyperparameter $\alpha>0$ is a fixed positive constant. The GENTRY strategy is summarized in \cref{algo:GENTRY}.

\begin{algorithm}[!htb]
\caption{GENTRY}
\begin{algorithmic}[1]
  \label{algo:GENTRY}
  \REQUIRE Set $\epsilon_t$ to $\epsilon_t^f$ or $\epsilon_t^i$ according to whether the problem is finite-arm or infinite-arm. Set hyperparameters $\alpha>0$ and $\lambda>0$. 
\STATE Set $t=1$.
\LOOP
\STATE Set $\epsilon_t$ using \cref{eq:epsilont_i}. 
\STATE With probability $1-\epsilon_t$, choose $\argmax_{\mathbf{x}\in \mathbb{D}} \bar{r}_{t-1}(\mathbf{x})$ and with probability $\epsilon_t$ choose a random arm from $\mathbb{D}_k$.
\STATE Update $\bar{r}(\mathbf{x}_t)$ using \cref{eq:finite_empirical}. 
\STATE Set $t = t + 1$. \\
\ENDLOOP
\end{algorithmic} 
\end{algorithm}
In the following theorems, we give a sufficient condition on the hyperparameter $\alpha$ for the strategy to achieve $O(\log n)$ for the finite-arm case. We also show that our infinite-arm strategy achieves $O(n^{2/3}(\log n)^{1/2})$ regret for the infinite-arm case. The empirical impact of $\alpha$ is further studied in \cref{sec:simulation}. Parameter $\lambda$ can be set as a moderate value like $Z^2$.

\subsection{Regret Analysis}\label{ssec:regret}
\subsubsection{Finitely Many Arms}\label{sssec:finite}
\begin{Theorem}\label{theorem:GENTRY_finite}
Suppose \cref{as:as1,as:as2} hold, $\mathbb{D}$ contains finitely many arms, 
\begin{align}
\alpha >  \max\braces*{\frac{24dZ^2\vartheta^2}{\min_{\mathbf{x}\ne X_\mathbb{U}^*} \Delta_\mathbf{x}^2\delta_{\mathbb{D}_k}},10}
\end{align}
where  $\Delta_\mathbf{x} = \ip{P_{\mathbb{U}}(X_{\mathbb{U}}^*(\bm{\theta}))- P_\mathbb{U}(\mathbf{x})}{P_\mathbb{U}(\bm{\theta})}$, and $\delta_{\mathbb{D}_k}$ is a constant that depends on $\mathbb{D}_k$. Then GENTRY has cumulative projection regret of order $O(|\mathbb{D}|\log n)$, where $n$ is the number of time steps and $|\mathbb{D}|$ is the number of arms.
\end{Theorem}

\cref{theorem:GENTRY_finite} shows that if we choose $\alpha$ to be sufficiently large, GENTRY achieves order optimal regret. 

\begin{IEEEproof} \label{proof1}
For any arm $\mathbf{x}\in \mathbb{D}$, let the random variable $N_t(\mathbf{x})$ denote the total number of time steps within the first $t$ time steps that the arm $\mathbf{x}$ was chosen, i.e., $N_n(\mathbf{x}) = \sum_{t=1}^{n} \indicator{X_t = \mathbf{x}}$. Since 
\begin{align}
  \E[ R_\mathbb{U}(n)]& =\E \sum_{t=1}^{n} \bigg(\ip{P_{\mathbb{U}}(X_{\mathbb{U}}^*(\bm{\theta}))}{P_\mathbb{U}(\bm{\theta})} - \ip{P_\mathbb{U}(X_t)}{P_\mathbb{U}(\bm{\theta})}\bigg)\nonumber \\
   &= \sum_{\mathbf{x}\in \mathbb{D}} \E[N_n(\mathbf{x})]\Delta_\mathbf{x} \nonumber \\
  &= \sum_{\mathbf{x}\in \mathbb{D}}\Delta_\mathbf{x} \sum_{t=1}^{n}\P(X_t = \mathbf{x}), 
  \label{eq:decompose_R}
\end{align}
where $\Delta_\mathbf{x} = \ip{P_{\mathbb{U}}(X_{\mathbb{U}}^*(\bm{\theta}))- P_\mathbb{U}(\mathbf{x})}{P_\mathbb{U}(\bm{\theta})}$ is the projection regret of arm $\mathbf{x}$, it is sufficient to show that the probability $\P(X_t = \mathbf{x})= O(t^{-1})$ for all suboptimal $\mathbf{x}\in \mathbb{D}\backslash\{X_\mathbb{U}^*\}$. We have
\begin{align}
  \P(X_t = \mathbf{x})  \le  \frac{\epsilon_t}{ k} + (1-\epsilon_t)\P(\bar{r}_{t-1}(\mathbf{x}) \ge \bar{r}_{t-1}(X_{\mathbb{U}}^*(\bm{\theta}))),
  \label{eq:PX_t}
\end{align}
and 
\begin{align}
  &\P(\bar{r}_{t-1}(\mathbf{x}) \ge \bar{r}_{t-1}(X_{\mathbb{U}}^*(\bm{\theta})))\nonumber\\
	&= P(\bar{r}_{t-1}(\mathbf{x}) \ge \bar{r}_{t-1}(X_{\mathbb{U}}^*(\bm{\theta})), \bar{r}_{t-1}(\mathbf{x}) \ge \ip{P_\mathbb{U}(\mathbf{x})}{P_\mathbb{U}(\bm{\theta})} + \frac{\Delta_\mathbf{x}}{2}) \nonumber\\
	&\hspace{0.3cm}+ \P(\bar{r}_{t-1}(\mathbf{x}) \ge \bar{r}_{t-1}(X_{\mathbb{U}}^*(\bm{\theta})), \bar{r}_{t-1}(\mathbf{x}) < \ip{P_\mathbb{U}(\mathbf{x})}{P_\mathbb{U}(\bm{\theta})} + \frac{\Delta_\mathbf{x}}{2}) \nonumber\\
  & \le \P(\bar{r}_{t-1}(\mathbf{x}) \ge \ip{P_\mathbb{U}(\mathbf{x})}{P_\mathbb{U}(\bm{\theta})} + \frac{\Delta_\mathbf{x}}{2}) \nonumber \\ 
	&\hspace{0.3cm}+ \P(\bar{r}_{t-1}(X_{\mathbb{U}}^*(\bm{\theta})) \le \ip{P_\mathbb{U}(X_{\mathbb{U}}^*(\bm{\theta}))}{P_\mathbb{U}(\bm{\theta})}-\frac{\Delta_\mathbf{x}}{2}). 
  \label{eq:Pr_t}
\end{align}
We next bound the first term on the right-hand side of \cref{eq:Pr_t}. The analysis for the second term is similar.

From the proof of Theorem $2$ in \cite{abbasi2011improved}, we have that with probability at least $1-\delta$, for all $t\ge 0$ and $\mathbf{x}\in \mathbb{R}^d$, 
\begin{align}
  \left\vert\ip{\mathbf{x}}{\hat{\bm{\theta}}_t - \bm{\theta}}\right\vert \le \|\mathbf{x}\|_{\mathbf{V}_t^{-1}}\left(\vartheta\sqrt{d\log\left( \frac{1+t}{\delta}\right)}+\lambda^{1/2}S\right).
  \label{eq:concentration}
\end{align}

Let $\beta_t = \vartheta \sqrt{3d \log (1+t)}+\lambda^{1/2}S$. Since $\ip{P_\mathbb{U}(\mathbf{x})}{P_\mathbb{U}(\bm{\theta})} = \ip{P_\mathbb{U}(\mathbf{x})}{\bm{\theta}}$ for the orthogonal projection operator $P_\mathbb{U}$, by setting $\delta = \ofrac{t^2}$, we have 

\begin{align*}
\vartheta\sqrt{d\log\left( \frac{1+t}{\delta}\right)}+\lambda^{1/2}S 
&= \vartheta\sqrt{d\log\left( t^2(t+1)\right)}+\lambda^{1/2}S \\
&< \beta_t,
\end{align*}
so that for all $\mathbf{x}\in \mathbb{D}\backslash\{X_\mathbb{U}^*\}$, it follows from \cref{eq:concentration} that
\begin{align}
& \P(\bar{r}_t(\mathbf{x})-\ip{P_\mathbb{U}(\mathbf{x})}{P_\mathbb{U}(\bm{\theta})} >\beta_t \|P_\mathbb{U}(\mathbf{x})\|_{\mathbf{V}_t^{-1}}) \nonumber \\
&\le \mathbb{P} \bigg(\ip{P_\mathbb{U}(\mathbf{x})} {\hat{\bm{\theta}}_t} - \ip{P_\mathbb{U}(\mathbf{x})}{\bm{\theta}}>\nonumber \\
&\hspace{2cm}  \left(\vartheta \sqrt{d\log \left( t^2(t+1)\right)} +\lambda^{1/2}S \right)\|P_\mathbb{U}(\mathbf{x})\|_{\mathbf{V}_t^{-1}}\bigg).\nonumber \\
& \le \ofrac{t^2}.\label{eq:concentration2}
\end{align}
We then have
\begin{align}
 &\P(\bar{r}_{t}(\mathbf{x}) \ge \ip{P_\mathbb{U}(\mathbf{x})}{P_\mathbb{U}(\bm{\theta})}+\frac{\Delta_\mathbf{x}}{2}) \nonumber \\
 &= \P(\bar{r}_{t}(\mathbf{x}) \ge \ip{P_\mathbb{U}(\mathbf{x})}{P_\mathbb{U}(\bm{\theta})}+\frac{\Delta_\mathbf{x}}{2}){\frac{\Delta_\mathbf{x}}{2}> \beta_t\|P_\mathbb{U}(\mathbf{x})\|_{\mathbf{V}_t^{-1}}}\nonumber \\
 & \hspace{1cm} \cdot \P(\frac{\Delta_\mathbf{x}}{2}> \beta_t\|P_\mathbb{U}(\mathbf{x})\|_{\mathbf{V}_t^{-1}})\nonumber \\
 & \hspace{0.0cm} + \P(\bar{r}_{t}(\mathbf{x}) \ge \ip{P_\mathbb{U}(\mathbf{x})}{P_\mathbb{U}(\bm{\theta})}+\frac{\Delta_\mathbf{x}}{2}){ \frac{\Delta_\mathbf{x}}{2}\le \beta_t\|P_\mathbb{U}(\mathbf{x})\|_{\mathbf{V}_t^{-1}}} \nonumber \\
 & \hspace{1cm} \cdot \P(\frac{\Delta_\mathbf{x}}{2}\le \beta_t\|P_\mathbb{U}(\mathbf{x})\|_{\mathbf{V}_t^{-1}})\nonumber \\
 & \le \ofrac{t^2} +  \P(\frac{\Delta_\mathbf{x}}{2}\le \beta_t\|P_\mathbb{U}(\mathbf{x})\|_{\mathbf{V}_t^{-1}}).\label{eq:Pr_t_1}
\end{align}

We next show that when the hyperparameter $\alpha$ is sufficiently large, 
\begin{align*}
  \P(\frac{\Delta_\mathbf{x}}{2}\le \beta_t\|P_\mathbb{U}(\mathbf{x})\|_{\mathbf{V}_t^{-1}})= O(t^{-1}).
 \end{align*}


Since
\begin{align*}
  \mathbf{V}_t &=  \lambda \mathbf{I} + \sum_{\mathbf{x}\in \mathbb{D}} N_t(\mathbf{x})\mathbf{x}\bx\T  \\
  &=  \lambda P_{\text{span}(\mathbb{D})^\perp}(\mathbf{I}) +\lambda P_{\text{span}(\mathbb{D})}(\mathbf{I})+ \sum_{\mathbf{x}\in \mathbb{D}} N_t(\mathbf{x})\mathbf{x}\bx\T,
\end{align*}
it can be shown by induction that the eigenvectors of $\mathbf{V}_t$ can be divided into two groups, one in which all the eigenvectors are in $\text{span}(\mathbb{D})$, and another in which all the eigenvectors are in $\text{span}(\mathbb{D})^\perp$. Let $\lambda^\mathbb{D}_{t,\text{min}}$ be the smallest eigenvalue of $\mathbf{V}_t$ in $\text{span}(\mathbb{D})$ and $\lambda^{\mathbb{D}_k}_{t,\text{min}}$ be the smallest eigenvalue of $(\lambda \mathbf{I}+\sum_{\mathbf{x}\in \mathbb{D}_k} N_t(\mathbf{x}) \mathbf{x}\bx\T)$ in $\text{span}(\mathbb{D})$. If we define
\begin{align*}
  \mathbf{y}_1=\argmin_{\mathbf{y}\in \text{span}(\mathbb{D}), \|\mathbf{y}\|^2_2=1}\ip{\mathbf{y}}{\mathbf{V}_t\mathbf{y}},
 \end{align*}
 we then have 
\begin{align}
  \lambda^\mathbb{D}_{t,\text{min}} &= \mathbf{y}_1\T\mathbf{V}_t\mathbf{y}_1\nonumber \\
  &\ge \mathbf{y}_1\T(\lambda \mathbf{I}+ \sum_{\mathbf{x}\in \mathbb{D}_k}N_t(\mathbf{x})\mathbf{x}\bx\T)\mathbf{y}_1  \nonumber \\
  &\ge \min_{\mathbf{y}\in\text{span}(\mathbb{D}),\|\mathbf{y}\|^2_2=1}\mathbf{y}\T(\lambda \mathbf{I} + \sum_{\mathbf{x}\in \mathbb{D}_k} N_t(\mathbf{x})\mathbf{x}\bx\T)\mathbf{y}\nonumber \\
  &= \lambda_{t,\text{min}}^{\mathbb{D}_k}\
 \label{eq:eiginequality}
\end{align}
Because  $P_\mathbb{U}(\mathbf{x}) \in \text{span}(\mathbb{D})$, using \cref{eq:eiginequality}, we obtain
\begin{align}
  &\P(\frac{\Delta_\mathbf{x}}{2} \le \beta_t\|P_\mathbb{U}(\mathbf{x})\|_{\mathbf{V}_t^{-1}}) \nonumber \\
  &\le \P(\left(\frac{\Delta_\mathbf{x}}{2\beta_t}\right)^2 \le \frac{\|P_\mathbb{U}(\mathbf{x})\|^2_2}{\lambda^\mathbb{D}_{t,\text{min}}})\nonumber \\
&=  \P(\lambda_{t,\text{min}}^\mathbb{D} \le \frac{4\beta_t^2\|P_\mathbb{U}(\mathbf{x})\|^2_2}{\Delta_\mathbf{x}^2})\nonumber \\
&\le \P(\lambda_{t,\text{min}}^{\mathbb{D}_k} \le \frac{4\beta_t^2 Z^2}{\min_{\mathbf{x}\ne X_\mathbb{U}^*} \Delta_\mathbf{x}^2}) 
  \label{eq:mineig}
\end{align}

Consider the function
\begin{align}
  f: \{\mathbf{y}:\mathbf{y}\in\text{span}(\mathbb{D}),\|\mathbf{y}\|^2_2=1\}\mapsto \mathbf{y}\T(\sum_{\mathbf{x}\in \mathbb{D}_k} \mathbf{x}\bx\T)\mathbf{y}.
\end{align}
We have $f(\mathbf{y})>0$ since $\mathbb{D}_k$ contains $k$ linearly independent arms.
We also have $\delta_{\mathbb{D}_k} := \inf f(\mathbf{y}) > 0$ since $f(\mathbf{y})$ is a continuous function on a compact set.
Define the event
\begin{align*}
  \left\{ \delta_{\mathbb{D}_k}N_t(\mathbf{x}) > \frac{4\beta_t^2Z^2}{\min_{\mathbf{x}\ne X_\mathbb{U}^*} \Delta_\mathbf{x}^2}, \text{ for all } \mathbf{x}\in \mathbb{D}_k\right\}.
\end{align*}
Under this event, using the last equality in \cref{eq:eiginequality}, we obtain $\lambda_{t,\text{min}}^{\mathbb{D}_k} >\frac{4\beta_t^2Z^2}{\min_{\mathbf{x}\ne X_\mathbb{U}^*}\Delta_\mathbf{x}^2}$. Therefore, we have
\begin{align}
  & \P(\lambda_{t,\text{min}}^{\mathbb{D}_k}\le \frac{4\beta_t^2Z^2}{\min_{\mathbf{x}\ne X_\mathbb{U}^*} \Delta_\mathbf{x}^2})\nonumber \\
 & \le \sum_{\mathbf{x} \in \mathbb{D}_k}\P(N_t(\mathbf{x})\le  \frac{4\beta_t^2Z^2}{\min_{\mathbf{x}\ne X_\mathbb{U}^*} \Delta_\mathbf{x}^2 \delta_{\mathbb{D}_k}})\nonumber \\
 & \le \sum_{\mathbf{x} \in \mathbb{D}_k}\P(\tilde{N}_t(\mathbf{x})\le  \frac{4\beta_t^2Z^2}{\min_{\mathbf{x}\ne X_\mathbb{U}^*} \Delta_\mathbf{x}^2 \delta_{\mathbb{D}_k}}),\label{eq:eigbound}
\end{align}
where $\tilde{N}_t(\mathbf{x}) \leq N_t(\mathbf{x})$ is the number of times that arm $\mathbf{x}\in \mathbb{D}_k$ was chosen \emph{randomly} during the first $t$ time steps. From the proof of Theorem 3 in \cite{auer2002finite} (where Bernstein's inequality \cite{Pollard} was used), we have
\begin{align}
  \P(\tilde{N}_t(\mathbf{x}) \le \ofrac{2 k}\sum_{i = 1}^{t}\epsilon_i)\le \exp{ \left(-\frac{1}{10 k}\sum_{i = 1}^{t}\epsilon_i\right)} \label{eq:bernstein}
\end{align}
For $t\ge t' = \ceil{\alpha k}$, $\epsilon_t=\epsilon_t^f  = \frac{\alpha  k}{t}$, we then obtain 
\begin{align}
\ofrac{2 k}\sum_{i = 1}^{t}\epsilon_i 
& = \ofrac{2 k} \sum_{i=1}^{t'} \epsilon_i+\ofrac{2 k} \sum_{i= t'+1}^{t}\epsilon_i \nonumber\\
& \ge \frac{\alpha}{2} + \ofrac{2 k}\int_{t'+1}^{t+1} \frac{\alpha  k}{t} \mathrm{d} x \nonumber\\
&\ge \frac{\alpha}{2} + \frac{\alpha}{2}\log \frac{t+1}{\alpha k+2} \nonumber\\
&=  \frac{\alpha}{2}\log \frac{(t+1)e}{\alpha k+2}, \label{eq:sumepsilon}
\end{align}
where $e$ is Euler's number. If $\frac{\alpha}{2}\log \frac{(t+1)e}{\alpha k+2}\ge  \frac{4\beta_t^2Z^2}{\min_{\mathbf{x}\ne X_\mathbb{U}^*} \Delta_\mathbf{x}^2 \delta_{\mathbb{D}_k}}$, from \cref{eq:eigbound}, we have 
\begin{align}
&  \P(\lambda_{t,\text{min}}^{\mathbb{D}_k}\le \frac{4\beta_t^2Z^2}{\min_{\mathbf{x}\ne X_\mathbb{U}^*} \Delta_\mathbf{x}^2})\nonumber\\
&\le \sum_{\mathbf{x}\in \mathbb{D}_k} \P(\tilde{N}_t(\mathbf{x})\le  \frac{4\beta_t^2Z^2}{\min_{\mathbf{x}\ne X_\mathbb{U}^*} \Delta_\mathbf{x}^2 \delta_{\mathbb{D}_k}}) \nonumber \\
&\le \sum_{\mathbf{x}\in \mathbb{D}_k} \P(\tilde{N}_t(\mathbf{x})\le   \frac{\alpha}{2}\log \frac{(t+1)e}{\alpha k+2}) \nonumber\\
& \le \sum_{\mathbf{x}\in \mathbb{D}_k}  \P(\tilde{N}_t(\mathbf{x})\le  \ofrac{2 k}\sum_{i = 1}^{t}\epsilon_i)\nonumber\\
& \le \sum_{\mathbf{x}\in \mathbb{D}_k}  \exp\left(-\ofrac{10 k}\sum_{i = 1}^{t}\epsilon_i\right) \nonumber\\
& \le k \left(\frac{\alpha k+2}{(t+1)e}\right)^{\frac{\alpha}{10}},\label{eq:Ot}
\end{align}
where the third inequality follows from \cref{eq:sumepsilon}, the penultimate inequality follows from \cref{eq:bernstein}, and the last inequality from \cref{eq:sumepsilon}.

Recall that $\beta_t = \vartheta \sqrt{3d \log (t+1)}+\lambda^{1/2}S$. Therefore, if $\alpha > \max\{\frac{24dZ^2\vartheta^2}{\min_{\mathbf{x}\ne X_\mathbb{U}^*} \Delta_\mathbf{x}^2\delta_{\mathbb{D}_k}},10\}$, when $t$ is sufficiently large, the condition $\frac{\alpha}{2}\log \frac{(t+1)e}{\alpha k+2}\ge  \frac{4\beta_t^2Z^2}{\min_{\mathbf{x}\ne X_\mathbb{U}^*} \Delta_\mathbf{x}^2 \delta_{\mathbb{D}_k}}$ is satisfied. We have
\begin{align}
 &\P(\bar{r}_{t}(\mathbf{x}) \ge \ip{ P_\mathbb{U}(\mathbf{x})}{P_\mathbb{U}(\bm{\theta})}+\frac{\Delta_\mathbf{x}}{2}) \nonumber\\
 & \le \ofrac{t^2} +  \P(\frac{\Delta_\mathbf{x}}{2}\le \beta_t\|P_\mathbb{U}(\mathbf{x})\|_{\mathbf{V}_t^{-1}})\nonumber\\
 &\le \ofrac{t^2}+ \P(\lambda_{t,\text{min}}^{\mathbb{D}_k} \le \frac{4\beta_t^2 Z^2}{\min_{\mathbf{x}\ne X_\mathbb{U}^*} \Delta_\mathbf{x}^2})\nonumber\\
 & \le \ofrac{t^2} + k \left(\frac{\alpha k+2}{(t+1)e}\right)^{\frac{\alpha}{10}}\nonumber\\
 & = o(t^{-1}),
 \label{eq:Pr_t_2}
\end{align}
where the first inequality follows from \cref{eq:Pr_t_1}, the second inequality from \cref{eq:mineig} and the last inequality from \cref{eq:Ot}.

A similar argument shows that $\P(\bar{r}_{t}(\mathbf{x}) \le \ip{P_\mathbb{U}(X_\mathbb{U}^*)}{P_\mathbb{U}(\bm{\theta})}-\frac{\Delta_\mathbf{x}}{2})= o(t^{-1})$.
Then, using \cref{eq:PX_t,eq:Pr_t}, we have
\begin{align}
  \P(X_t = \mathbf{x}) & \le \frac{\alpha}{t}+o(t^{-1}) = O(t^{-1}),
  \label{eq:PX_t_2}
\end{align}
From \cref{eq:decompose_R}, we conclude that 
\begin{align*}
\E[R_\mathbb{U}(n)] = O(|\mathbb{D}|\log n).
\end{align*}
The proof of \cref{theorem:GENTRY_finite} is now complete. 
\end{IEEEproof}

\subsubsection{Infinitely Many Arms}\label{sssec:infinite}

\begin{Theorem}\label{theorem:GENTRY_infinite}
Suppose \cref{as:as1,as:as2} hold, and $\mathbb{D}$ is a compact set containing infinitely many arms. Then, GENTRY has cumulative projection regret of order $O\left(\max\left\{k,\sqrt{d}\right\}n^{2/3}(\log n)^{1/2}\right)$, where $n$ is the number of time steps.
\end{Theorem}
\begin{IEEEproof}
The contribution to the projection regret at time step $t$ comes from two cases: 1) when $X_t$ is chosen randomly, or 2) when $X_t$ is chosen as $\argmax_{\mathbf{x}\in \mathbb{D}}\bar{r}_{t-1}(\mathbf{x})$. We denote these two event as $E_t$ and $E_t^{c}$ respectively.
\begin{align}
  & \E[R_\mathbb{U}(n)] \nonumber \\
 & = \E[\sum_{t=1}^{n} \ip{P_{\mathbb{U}}(X_\mathbb{U}^*)-P_\mathbb{U}(X_t)}{P_\mathbb{U}(\bm{\theta})}] \nonumber \\
 & = \sum_{t=1}^{n}\big( \epsilon_t \E[\ip{P_{\mathbb{U}}(X_\mathbb{U}^*) - P_\mathbb{U}(X_t)}{P_\mathbb{U}(\bm{\theta})}]{ E_t}\nonumber \\
 & \hspace{0.3cm}+(1-\epsilon_t) \E[\ip{P_{\mathbb{U}}(X_\mathbb{U}^*) - P_\mathbb{U}(X_t)}{P_\mathbb{U}(\bm{\theta})}]{E_t^c} \big)\nonumber \\
 & \le\sum_{t=1}^{n}\left(2ZS \epsilon_t +\E[\ip{P_{\mathbb{U}}(X_\mathbb{U}^*) - P_\mathbb{U}(X_t)}{P_\mathbb{U}(\bm{\theta})}]{ E_t^c}\right),
  \label{eq:R_inf}
\end{align}
where the inequality follows from \cref{as:as1}, $\|P_\mathbb{U}(\mathbf{x})\|_2\le \|\mathbf{x}\|_2$ for all $\mathbf{x}$, and the Cauchy-Schwarz inequality.

We next derive an upper bound for the second term $\E[\ip{P_{\mathbb{U}}(X_\mathbb{U}^*) - P_\mathbb{U}(X_t)}{P_\mathbb{U}(\bm{\theta})}]{ E_t^c}$ in the sum on the right-hand side of \cref{eq:R_inf}.

Under the event $E_t^c$, we have
\begin{align}
  & \ip{P_{\mathbb{U}}(X_\mathbb{U}^*) - P_\mathbb{U}(X_t)}{P_\mathbb{U}(\bm{\theta})} \nonumber \\
  & = \ip{P_{\mathbb{U}}(X_\mathbb{U}^*) - P_\mathbb{U}(X_t)}{P_\mathbb{U}(\hat{\bm{\theta}}_{t-1})}\nonumber \\
  & \hspace{0.3cm} + \ip{P_{\mathbb{U}}(X_\mathbb{U}^*) - P_\mathbb{U}(X_t)}{P_\mathbb{U}(\bm{\theta})- P_\mathbb{U}(\hat{\bm{\theta}}_{t-1})} \nonumber \\
  &\le \ip{P_{\mathbb{U}}(X_\mathbb{U}^*) - P_\mathbb{U}(X_t)}{P_\mathbb{U}(\bm{\theta})- P_\mathbb{U}(\hat{\bm{\theta}}_{t-1})}, 
  \label{eq:regret2pro}
\end{align}
where the inequality follows from $X_t = \argmax_{\mathbf{x}\in \mathbb{D}} \bar{r}_{t-1}(\mathbf{x})$.

We use the same $\beta_t$ defined in the proof of \cref{theorem:GENTRY_finite}. For any $t\ge 2$, let the event  
\begin{align}
  F_t = \left\{ \ip{P_{\mathbb{U}}(X_\mathbb{U}^*-X_t)}{P_\mathbb{U}(\bm{\theta})}\nonumber \ge \|P_{\mathbb{U}}(X_\mathbb{U}^*-X_t)\|_{\mathbf{V}_{t-1}^{-1}}\beta_{t-1} \right\}.
\end{align}
From \cref{eq:regret2pro,eq:concentration}, since $\ip{P_\mathbb{U}(\mathbf{x})}{P_\mathbb{U}(\bm{\theta})} = \ip{P_\mathbb{U}(\mathbf{x}) }{\bm{\theta}}$ for the orthogonal projection operator $P_\mathbb{U}$,  we have 
\begin{align}

  & \P(F_{t+1}) \nonumber\\
  &  \le \P\bigg( \ip{P_\mathbb{U}\left(X_\mathbb{U}^*-X_{t+1}\right)}{\bm{\theta}-\hat{\bm{\theta}}_{t}}\ge  \|P_{\mathbb{U}}(X_\mathbb{U}^*- X_{t+1})\|_{\mathbf{V}_{t}^{-1}}\beta_{t}\bigg) \nonumber \\
& \le \P\bigg(  \ip{P_\mathbb{U}\left(X_\mathbb{U}^*-X_{t+1}\right)}{\bm{\theta}-\hat{\bm{\theta}}_{t}} \nonumber \\ &\hspace{0.5cm}\ge  \| P_\mathbb{U}\left(X_\mathbb{U}^*-X_{t+1}\right)\|_{\mathbf{V}_{t}^{-1}}\bigg(\vartheta\sqrt{d\log\left( \frac{1+t}{t^2}\right)}+\lambda^{1/2}S\bigg)\bigg)\nonumber \\
  &\le \ofrac{t^2},\label{eq:useconcentration}
\end{align}
where the final inequality follows from the concentration inequality \cref{eq:concentration} with $\delta = \ofrac{t^2}$. We then have 
\begin{align}
  & \E[\ip{P_{\mathbb{U}}(X_\mathbb{U}^*) - P_\mathbb{U}(X_{t+1})}{P_\mathbb{U}(\bm{\theta})}]{E_{t+1}^c}\nonumber \\
  & = \E[\ip{P_{\mathbb{U}}(X_\mathbb{U}^*-X_{t+1})}{P_\mathbb{U}(\bm{\theta})}]{E_{t+1}^c, F_{t+1}}\P(F_{t+1})\nonumber \\
  &\hspace{0.2cm} +\E[ \ip{P_{\mathbb{U}}(X_\mathbb{U}^*-X_{t+1})}{P_\mathbb{U}(\bm{\theta})}\indicatore{F_{t+1}^c}]{E_{t+1}^c}\nonumber \\
  & \le \frac{2ZS}{t^2}+ \E[ \|P_{\mathbb{U}}(X_\mathbb{U}^*-X_{t+1})\|_{\mathbf{V}_t^{-1}}\beta_t]{E_{t+1}^c}\label{eq:bounddifference_0} \\
  & \le \frac{2ZS}{t^2}+\E [2Z\beta_t\sqrt{\frac{1}{\lambda_{t,\text{min}}^\mathbb{D}}}]{E_{t+1}^c}\label{eq:bounddifference_1}\\
& \le \frac{2ZS}{t^2} + \E[2Z\beta_t\sqrt{\frac{1}{\lambda_{t,\text{min}}^\mathbb{D}}}] \nonumber\\
& \le \frac{2ZS}{t^2} + 2Z\beta_t\sqrt{\E[\frac{1}{\lambda_{t,\text{min}}^\mathbb{D}}]}\label{eq:bounddifference_3}\\\
& \le \frac{2ZS}{t^2} + 2Z\beta_t\sqrt{\E[\frac{1}{\lambda_{t,\text{min}}^{\mathbb{D}_k}}]},
\label{eq:bounddifference}
\end{align}
where 
\begin{itemize}
	\item \cref{eq:bounddifference_0} follows from \cref{eq:useconcentration};
	\item \cref{eq:bounddifference_1} follows because $\|P_{\mathbb{U}}(X_\mathbb{U}^*-X_t)\|^2_{\mathbf{V}_t^{-1}} \le \|P_\mathbb{U}(X_\mathbb{U}^*-X_t)\|^2_2/\lambda^\mathbb{D}_{t,\text{min}}$;

	\item \cref{eq:bounddifference_3} follows from Jensen's inequality; and
	\item \cref{eq:bounddifference} follows from \cref{eq:eiginequality}.
\end{itemize}

We next show that $ \E[\frac{1}{\lambda_{t,\text{min}}^{\mathbb{D}_k}}] =O(t^{-2/3})$. We first show $\P(\lambda_{t,\text{min}}^{\mathbb{D}_k} < t^{2/3}) \le O(e^{-t^{2/3}})$. 
  Similar to what we have done in \cref{eq:eigbound}, define the following event:
\begin{align*}
\left\{ N_t(\mathbf{x}) > \frac{\alpha}{2}t^{2/3}, \text{ for all } \mathbf{x}\in \mathbb{D}_k\right\}.
\end{align*}
Under this event, from the last equality in \cref{eq:eiginequality}, we get $\lambda_{t,\text{min}}^{\mathbb{D}_k} >\frac{\alpha}{2}t^{2/3}\delta_{\mathbb{D}_k}$. Therefore, we have
\begin{align}
  & \P(\lambda_{t,\text{min}}^{\mathbb{D}_k}\le \frac{\alpha}{2}t^{2/3}\delta_{\mathbb{D}_k})\nonumber \\
 & \le \sum_{\mathbf{x} \in \mathbb{D}_k}\P(N_t(\mathbf{x})\le   \frac{\alpha}{2}t^{2/3})\nonumber \\
 & \le \sum_{\mathbf{x} \in \mathbb{D}_k}\P(\tilde{N}_t(\mathbf{x})\le  \frac{\alpha}{2}t^{2/3}),\label{eq:infeigbound}
\end{align}
where $\tilde{N}_t(\mathbf{x})$ is the number of times that arm $\mathbf{x}\in \mathbb{D}_k$ was chosen \emph{randomly} during the first $t$ time steps. Recall from \cref{eq:bernstein} that 
\begin{align}
  \P(\tilde{N}_t(\mathbf{x}) \le \ofrac{2 k}\sum_{i = 1}^{t}\epsilon_i)\le \exp{ \left(-\frac{1}{10 k}\sum_{i = 1}^{t}\epsilon_i\right)}
  \label{eq:temp}
\end{align}
For $t\ge t' =\ceil{( \alpha  k)^3}$, $\epsilon_t =\epsilon_t^i = \frac{\alpha  k}{t^{1/3}}$ and we obtain
\begin{align}
\ofrac{2 k}\sum_{i = 1}^{t}\epsilon_i & = \ofrac{2 k} \sum_{i=1}^{t'} \epsilon_i+\ofrac{2 k} \sum_{i= t'+1}^{t}\epsilon_i \nonumber\\
& \ge \ofrac{2 k}t' + \ofrac{2 k}\int_{t'+1}^{t+1} \frac{\alpha  k}{t^{1/3}} \mathrm{d} x \nonumber\\
& \ge  \frac{\alpha^3 k^2}{2} + \frac{3\alpha}{4}t^{2/3}-\frac{3\alpha}{4}(\alpha^3 k^3+2)^{2/3}. \nonumber\\
& \ge \frac{\alpha}{2}t^{2/3},
\label{eq:infsumepsilon}
\end{align}
when $t$ is sufficiently large.
It follows from \cref{eq:infeigbound,eq:temp,eq:infsumepsilon} that
\begin{align}
  & \P(\lambda_{t,\text{min}}^{\mathbb{D}_k}\le \frac{\alpha}{2}t^{2/3}\delta_{\mathbb{D}_k})\nonumber \\
  & \le \sum_{\mathbf{x} \in \mathbb{D}_k}\P(\tilde{N}_t(\mathbf{x})\le  \frac{\alpha}{2}t^{2/3}),\nonumber \\
  & \le \sum_{\mathbf{x} \in \mathbb{D}_k}\P(\tilde{N}_t(\mathbf{x}) \le \ofrac{2 k}\sum_{i = 1}^{t}\epsilon_i), \nonumber \\
  & \le k \exp\left(-\frac{\alpha}{10}t^{2/3}\right)
  \label{eq:infeig}
\end{align}
Now, we can conclude that when $t$ is sufficiently large,
\begin{align}
  &\E[\ofrac{\lambda_{t,\min}^{\mathbb{D}_k}}]\nonumber\\
  &=\E[\ofrac{\lambda_{t,\min}^{\mathbb{D}_k}}]{\lambda_{t,\text{min}}^{\mathbb{D}_k}> \frac{\alpha}{2}t^{2/3}\delta_{\mathbb{D}_k}}\P(\lambda_{t,\text{min}}^{\mathbb{D}_k}> \frac{\alpha}{2}t^{2/3}\delta_{\mathbb{D}_k})\nonumber \\
  & \hspace{0.3cm} +\E[\ofrac{\lambda_{t,\min}^{\mathbb{D}_k}}]{\lambda_{t,\text{min}}^{\mathbb{D}_k}\le \frac{\alpha}{2}t^{2/3}\delta_{\mathbb{D}_k}}\P(\lambda_{t,\text{min}}^{\mathbb{D}_k}\le \frac{\alpha}{2}t^{\frac{2}{3}}\delta_{\mathbb{D}_k})\nonumber \\
  &\le \frac{2t^{-2/3}}{\alpha\delta_{\mathbb{D}_k}}\P(\lambda_{t,\text{min}}^{\mathbb{D}_k}> \frac{\alpha}{2}t^{2/3}\delta_{\mathbb{D}_k})+ \frac{k}{\lambda}\exp\left(-\frac{\alpha}{10}t^{2/3}\right)\nonumber\\
  &\le  \frac{3t^{-2/3}}{\alpha\delta_{\mathbb{D}_k}}, 
  \label{eq:almostdone}
\end{align}
where the penultimate inequality follows from \cref{eq:eiginequality}.

From \cref{eq:bounddifference,eq:almostdone}, when $t$ is sufficiently large, we have
\begin{align}
  & \E[\ip{P_{\mathbb{U}}(X_\mathbb{U}^*) - P_\mathbb{U}(X_{t+1})}{P_\mathbb{U}(\bm{\theta})}]{E_{t+1}^c}\nonumber \\
& \le \frac{2ZS}{t^2} +2Z\beta_t\sqrt{\E[\frac{1}{\lambda_{t,\text{min}}^{\mathbb{D}_k}}]}\nonumber \\ 
&\le \frac{2ZS}{t^2}+2Z\beta_t\sqrt{\frac{3}{\alpha\delta_{\mathbb{D}_k}}}t^{-\ofrac{3}}
  \label{eq:onemorestep}
\end{align}
Finally, from \cref{eq:R_inf}, we have
\begin{align}
  &\E[R_\mathbb{U}(n)]\nonumber \\
  & \le\sum_{t=1}^{n} \left(2ZS \epsilon_t +\E[\ip{P_{\mathbb{U}}(X_\mathbb{U}^*) - P_\mathbb{U}(X_t)}{P_\mathbb{U}(\bm{\theta})}]{ E_t^c} \right)\nonumber \\
  &\le \sum_{t=1}^{n}  \left(\frac{2ZS\alpha k}{t^{1/3}}+ 2Z\beta_t\sqrt{\frac{3}{\alpha\delta_{\mathbb{D}_k}}}t^{-\ofrac{3}}\right) + C_1\nonumber \\
  &\le \int_{1}^{n} \left(\frac{C_2 k}{x^{1/3}}+ 6Z\vartheta\sqrt{\frac{d\log x}{\alpha\delta_{\mathbb{D}_k}}}x^{-\ofrac{3}}\right) \mathrm{d} x+C_3\nonumber \\
& = O\left(\max\left\{k,\sqrt{d}\right\}n^{2/3}(\log n)^{1/2}\right),
  \label{eq:final}
\end{align}
where $C_1$, $C_2$ and $C_3$ are constants. The proof of \cref{theorem:GENTRY_infinite} is now complete.  
\end{IEEEproof}



\subsection{Additional Smoothness Assumption}\label{sec:smoothness}

In this subsection, we show that if an additional smoothness assumption similar to that in \cite{rusmevichientong2010linearly} is made, we can achieve better cumulative projection regret order than $O(n^{2/3}(\log n)^{1/2})$ for the infinite-arm case. 

\begin{Assumption}\label{as:as3}
There exists $J \in \mathbb{R}^{+}$ such that for all $\bm{\theta}_1$, $\bm{\theta}_2\in \mathbb{R}^d$, 
\begin{align}\label{eq:sbar}
&\left\|P_\mathbb{U}\left(X_\mathbb{U}^*(\bm{\theta}_1) -X_\mathbb{U}^*(\bm{\theta}_2)\right)\right\|_2 \le J\left\|\frac{P_\mathbb{U}(\bm{\theta}_1)}{\|P_\mathbb{U}(\bm{\theta}_1)\|} - \frac{P_\mathbb{U}(\bm{\theta}_1)}{\|P_\mathbb{U}(\bm{\theta}_1)\|} \right\|_2.
\end{align}
\end{Assumption}
This is to say the projection of the decision set $\mathbb{D}$ and all $\bm{\theta} \in \mathbb{R}^d$ onto the subspace $\mathbb{U}$ satisfies the $\text{SBAR}(J)$ condition \cite{rusmevichientong2010linearly,polovinkin1996strongly}. For example, if the decision set $\mathbb{D}$ is a ball or an elliposid, it satisfies the condition \cref{eq:sbar}. In the proof of \cref{theorem:GENTRY_infinite}, we bound \cref{eq:regret2pro} with $O\left(\beta_t(\E[1/\lambda_{t,\text{min}}^{\mathbb{D}_k}])^{1/2}]\right) =O(t^{-1/3}\log t)$. 
With the additional \cref{as:as3}, we can improve this bound, and further get a tighter upper bound for the cumulative projection regret in the following result.

\begin{Theorem}\label{theorem:GENTRYsmooth}
Suppose \cref{as:as1,as:as2,as:as3} hold and $\mathbb{D}$ is a compact set with infinitely many arms. Then, GENTRY with $\epsilon_t = \epsilon_t^s := \min\left\{1,\frac{\alpha  k}{\sqrt{t}}\right\}$ has cumulative projection regret of order $O(d\sqrt{n})$, where $n$ is the number of time steps.
\end{Theorem} 
\begin{proof}
The inequalities \cref{eq:R_inf,eq:regret2pro} from the proof of \cref{theorem:GENTRY_infinite} still hold. We have 
  \begin{align}
    & \E[ \ip{P_{\mathbb{U}}(X_\mathbb{U}^*) - P_{\mathbb{U}}(X_t)}{P_{\mathbb{U}}(\bm{\theta})}\mid E_t^c] \nonumber \\ 
    & \le\E[\ip{P_{\mathbb{U}}(X_\mathbb{U}^*) - P_\mathbb{U}(X_t)}{P_{\mathbb{U}}(\bm{\theta})- P_{\mathbb{U}}(\hat{\bm{\theta}}_{t-1})}]{E_t^c}\nonumber \\ 
    & \le\E[\left\Vert P_{\mathbb{U}}(X_\mathbb{U}^*) - P_{\mathbb{U}}(X_t) \right\Vert_2 \left\Vert P_{\mathbb{U}}(\bm{\theta})- P_{\mathbb{U}}(\hat{\bm{\theta}}_{t-1}) \right\Vert_2]{E_t^c} \nonumber \\ 
    & \le \E[J \left\|\frac{P_{\mathbb{U}}(\bm{\theta})}{\|P_{\mathbb{U}}(\bm{\theta})\|} - \frac{P_{\mathbb{U}}(\hat{\bm{\theta}}_{t-1})}{\|P_{\mathbb{U}}(\hat{\bm{\theta}}_{t-1})\|}\right\|_2\left\Vert P_{\mathbb{U}}(\bm{\theta})- P_{\mathbb{U}}(\hat{\bm{\theta}}_{t-1}) \right\Vert_2]{E_t^c} \nonumber \\  
    &\le  \E[\frac{2J\left\Vert P_{\mathbb{U}}(\bm{\theta})- P_{\mathbb{U}}(\hat{\bm{\theta}}_{t-1}) \right\Vert_2^2}{\|P_{\mathbb{U}}(\bm{\theta})\|}]{E_t^c} \nonumber \\ 
    &=  \E[\frac{2J\left\Vert P_{\mathbb{U}}(\bm{\theta}-\hat{\bm{\theta}}_{t-1}) \right\Vert_2^2}{\|P_{\mathbb{U}}(\bm{\theta})\|}]
\end{align}
where the first inequality follows from \cref{eq:regret2pro}, the second inequality follows from Cauchy-Schwarz inequality, the third inequality follows from \cref{as:as3}, the penultimate inequality follows from Lemma 3.5 in \cite{rusmevichientong2010linearly}, and  the last equality follows from independence.

We next bound  $\E[\left\Vert P_{\mathbb{U}}(\bm{\theta}-\hat{\bm{\theta}}_{t}) \right\Vert_2^2]$. From \cref{eq:estimate},  we have,
\begin{align}
    \hat{\bm{\theta}}_t & = \parens*{\lambda \mathbf{I}+\sum_{i = 1}^{t}X_iX_i\T}^{-1}\sum_{i = 1}^{t} r_iX_i \nonumber \\
    & =  \parens*{\lambda \mathbf{I}+\sum_{i = 1}^{t}X_iX_i\T}^{-1}\sum_{i = 1}^{t} ( \ip{X_i}{\bm{\theta}} + \eta_i)X_i,\nonumber
\end{align}
which yields
\begin{align}
  &\E[\left\Vert P_{\mathbb{U}}(\bm{\theta}-\hat{\bm{\theta}}_{t}) \right\Vert_2^2]\nonumber \\
  &\le \E[\left\Vert P_{\mathbb{U}}(\lambda \mathbf{V}^{-1}_t\bm{\theta}) \right\Vert_2^2 + \left\Vert  \sum_{i = 1}^{t}P_{\mathbb{U}}(\mathbf{V}^{-1}_t X_i) \eta_i \right\Vert_2^2]  \nonumber \\
  &\le \lambda^2S^2\E[\ofrac{(\lambda_{t,\text{min}}^\mathbb{D})^2}] + \zeta \E[\sum_{i = 1}^{t}P_{\mathbb{U}}(\mathbf{V}^{-1}_t X_i)\T P_{\mathbb{U}}(\mathbf{V}^{-1}_t X_i)] \nonumber \\
  &\le \lambda^2S^2\E[\ofrac{(\lambda_{t,\text{min}}^\mathbb{D})^2}] + \zeta \E[\sum_{i = 1}^{t}\tr\left(P_{\mathbb{U}}(\mathbf{V}^{-1}_t)\mathbf{V}^{-1}_t(X_iX_i\T)\right)] \nonumber \\
  &\le \lambda^2S^2\E[\ofrac{(\lambda_{t,\text{min}}^\mathbb{D})^2}] + \zeta \E[\tr\left(P_{\mathbb{U}}(\mathbf{V}^{-1}_t)\mathbf{V}^{-1}_t (\sum_{i = 1}^{t}X_iX_i\T\right)] \nonumber \\
    &\le \lambda^2S^2\E[\ofrac{(\lambda_{t,\text{min}}^\mathbb{D})^2}] + \zeta \E[d\lambda_{\text{max}}(P_{\mathbb{U}}(\mathbf{V}^{-1}_t))] \nonumber \\
   &\le \lambda^2S^2\E[\ofrac{(\lambda_{t,\text{min}}^\mathbb{D})^2}] + d\zeta \E[\frac{1}{\lambda_{t,\text{min}}^\mathbb{D}}] \nonumber \\
   &\le \lambda^2S^2\E[\ofrac{(\lambda_{t,\text{min}}^{\mathbb{D}_k})^2}] + d\zeta \E[\ofrac{\lambda_{t,\text{min}}^{\mathbb{D}_k}}],\label{eq:expect}
\end{align}
where the second inequality has used the condition that $\eta_t$ are \gls{iid} and the standard result that $\E[\eta_t^2] \le \zeta$ where $\zeta$ is a constant depending on $\vartheta$ since $\eta_t$ has the zero-mean sub-Gaussian distribution with parameter $\vartheta$. 

Using a similar argument as that in the proof of \cref{theorem:GENTRY_infinite}, we can show
\begin{align}
  \E[\frac{1}{\lambda_{t,\text{min}}^{\mathbb{D}_k}}]= O(t^{-1/2}), \text{   and  }
  \E[\ofrac{(\lambda_{t,\text{min}}^{\mathbb{D}_k})^2}]= O(t^{-1}).
  \label{eq:order_as3}
\end{align}
The proof steps are skipped here for brevity. Finally, using \cref{eq:R_inf,eq:R_inf,eq:expect}, we have
\begin{align}
  &\E[R_\mathbb{U}(n)]\nonumber \\
  & \le\sum_{t=1}^{n}2ZS \epsilon_t^s +\E[\ip{P_{\mathbb{U}}(X_\mathbb{U}^*) - P_\mathbb{U}(X_t)}{P_\mathbb{U}(\bm{\theta})}]{E_t^c}\nonumber \\
  &\le \sum_{t=1}^{n} dO(t^{-1/2})\nonumber \\
  & = O(d\sqrt{n}).
  \label{eq:final_s}
\end{align}
The proof of \cref{theorem:GENTRYsmooth} is now complete.  
\end{proof}


\section{Simulations and Performance Evaluation}\label{sec:simulation}
In this section, we verify the efficiency of our strategy by performing simulations on synthetic data and a wine quality dataset\cite{cortez2009modeling}. We compare against the following strategies:
\begin{enumerate}[1)]
\item the Uncertainty Ellipsoid (UE) policy \cite{rusmevichientong2010linearly}, 
  which chooses \[\argmax_{\mathbf{x}\in \mathbb{D}} \bar{r}_{t-1}(\mathbf{x}) +\alpha\sqrt{\log t\min\{d\log t,|\mathbb{D}|\}} \|\mathbf{x}\|_{\mathbf{V}_{t-1}^{-1}}\] at each time step $t$;  
\item the CorrUpted GReedy StratEgy (CURSE) by replacing $\argmax_{\mathbf{x}\in \mathbb{D}} \bar{r}_{t-1}(\mathbf{x})$ with $\argmax_{\mathbf{x}\in \mathbb{D}} \ip{\mathbf{x}}{\hat{\bm{\theta}}_{t-1}}$ in GENTRY, i.e., the corruption in the observed return is not accounted for; and
\item the caRelEss GReEdy sTrategy (REGRET) where the $X_i$ in GENTRY are all replaced by $P_\mathbb{U}(X_i)$. To avoid any doubts, the full REGRET is shown in \cref{algo:REGRET}.
\end{enumerate}
 
\begin{algorithm}[!htp]
\caption{REGRET}
  \label{algo:REGRET}
\begin{algorithmic}[1]
  \REQUIRE Set $\epsilon_t$ to $\epsilon_t^f$ or $\epsilon_t^i$ according to the number of arms; set hyper parameter $\alpha>0$ and $\lambda>0$.
\LOOP
\STATE Update $\epsilon_t$. 
\STATE With probability $1-\epsilon_t$, choose 
\begin{align*}
\argmax_{\mathbf{x}\in \mathbb{D}} \ip{P_\mathbb{U}(\mathbf{x})}{P_\mathbb{U}(\tilde{\bm{\theta}}_{t-1})},
\end{align*}
where
\begin{align*}
\tilde{\bm{\theta}}_t = \left(\sum_{i=1}^{t}P_\mathbb{U}(X_i)P_\mathbb{U}(X_i)\T+\lambda \mathbf{I}\right)^{-1}\sum_{i=1}^{t}r_iP_\mathbb{U}(X_i),
\end{align*}
and with probability $\epsilon_t$ choose a random arm from $\mathbb{D}_k$.
\STATE  Update $\ip{P_\mathbb{U}(\mathbf{x})}{P_\mathbb{U}(\tilde{\bm{\theta}}_{t-1})}$. Set $t = t + 1$.\\
\ENDLOOP
\end{algorithmic} 
\end{algorithm}
In each simulation, we perform $2000$ trials, each with $10^4$ time steps. To compare the projection regret performance of different strategies, we compute the average empirical cumulative projection regret over all the trials. For convenience, this average is referred to as the \emph{average cumulative projection regret}.


\subsection{Experiments on Synthetic Data}\label{ssec:synthetic}
In this section, we compare the performance of different strategies using synthetic data.
We use three settings in the simulations:
\begin{enumerate}[(a)]
  \item \label{it:settinga}
    For the finite-arm case, in each trial, we generate the decision set $\mathbb{D}\subseteq \mathbb{R}^d$ containing $K$ arms, in which each arm is associated with a $d$-dimension feature vector. Each dimension of the feature vector is drawn \gls{iid} from the uniform distribution $\mathcal{U}(-1,1)$. Each dimension of the ground-truth parameter $\bm{\theta}$ is also drawn from $\mathcal{U}(-1,1)$. We next generate the orthogonal projection matrix $P_\mathbb{U} = \mathbf{A}(\mathbf{A}\T\mathbf{A})^{-1}\mathbf{A}\T$, where $\mathbf{A}$ is a $d\times u$ ($u<d$) matrix whose elements are generated randomly from $\mathcal{U}(-1,1)$. The noise $\eta_t$ at each time step is drawn \gls{iid} from the Gaussian distribution $\mathcal{N}(0,\vartheta^2)$ with variance $\vartheta^2$. The decision set $\mathbb{D}$, parameter $\bm{\theta}$ and projection matrix $P_\mathbb{U}$ are fixed in each trial.
  \item \label{it:settingb}
      We use the same setting as in setting \ref{it:settinga} except that the projection matrix $P_\mathbb{U}$ in this setting is a diagonal matrix whose $(i,i)$ entry is $1$ for $i=1,\cdots,u$ and $0$ otherwise. This means that the last $d-u$ dimensions of $\bm{\theta}$ are the protected features.
  \item \label{it:settingc}
    For the infinite-arm case, in each trial, the decision set $\mathbb{D}$ is limited to a convex set for ease of computation. Specifically, we use the convex set $\mathbb{D}$:
    \begin{align}\label{eq:convexD}
      \mathbb{D} = \left\{\mathbf{x}: \sum_{i=1}^{d} \mathbf{x}(i)\log \mathbf{x}(i) \le 5 \text{ and } \mathbf{x}(i) \ge 0\ \forall\ i  \right\},
\end{align}
where $\mathbf{x}(i)$ is the $i$-th entry of $\mathbf{x}$, $0\log 0 := 0$, and $\bm{\theta}$, $P_\mathbb{U}$ and $\eta_t$ are generated the same way as in setting \ref{it:settinga}.

  \end{enumerate}

In the following, GENTRY, CURSE, and REGRET use the setting $\epsilon = \epsilon_t^f$ described in \cref{sec:strategy} when in setting \ref{it:settinga} and \ref{it:settingb} for the finite-arm case. Accordingly, $\epsilon = \epsilon_t^i$ is used when in setting \ref{it:settingc} for the infinite-arm case. In all simulations, the parameter $\lambda$ is set to $1$.

\subsubsection{Varying \texorpdfstring{$\alpha$}{alpha}}\label{sssec:vary_alpha}

\begin{figure}[!htb]
    \centering
    \begin{subfigure}[b]{0.9\columnwidth}
        \centering
	\includegraphics[width=\linewidth]{./regret_syn_para}
	\caption{Using setting \ref{it:settinga} with $d=10$, $K=45$, and $u = 5$}
        \label{fig:parameter}
    \end{subfigure}\\
    \begin{subfigure}[b]{0.9\columnwidth}
        \centering
	\includegraphics[width=\linewidth]{./regret_syn_inf_para}
        \caption{Using setting \ref{it:settingc} with  $d=4$, and $u = 2$}
        \label{fig:parameter_inf}
    \end{subfigure}
    \caption{Regret comparison between different strategies with $\vartheta=0.5$ and varying $\alpha$.}
\end{figure}


All the strategies depend on the hyperparameter $\alpha$, with a larger $\alpha$ corresponding to more exploration on average. We do simulations using setting \ref{it:settinga} with $d=10$, $K=45$, $\vartheta = 0.5$, $u = 5$, and setting \ref{it:settingc} with $d=4$, $\vartheta = 0.5$, $u = 2$. \cref{fig:parameter,fig:parameter_inf} show how the average cumulative projective regret at time step $10^4$ changes with different $\alpha$ in each strategy. We observe the following:
\begin{itemize}
  \item We note that a moderate $\alpha$ is optimal for each strategy. When $\alpha$ is too large, the strategy explores too frequently, leading to a large projection regret as expected. On the other hand, a small $\alpha$ results in little exploration, and good arms cannot be found efficiently. 
  \item In \cref{fig:parameter}, GENTRY with $\alpha = 1$ outperforms all the other benchmark strategies. This is because the other strategies do not achieve an asymptotically unbiased estimation of the projection reward. \cref{fig:parameter_inf} shows similar results. 

\end{itemize}
In the following simulations, for a fair comparison, we tune the parameter $\alpha$ for each strategy to achieve the best average asymptotic cumulative projection regret for that strategy. Specifically, we set $\alpha=1$ for all the strategies except UE, which is given a $\alpha=0.1$ when using setting \ref{it:settinga} and \ref{it:settingb}. When using setting \ref{it:settingc}, we set $\alpha=0.01$ for all the strategies except REGRET, which is given a $\alpha=0.1$.

\subsubsection{Results and Analysis}

\begin{figure}[!htb]
    \centering
    \begin{subfigure}[b]{0.9\columnwidth}
        \centering
	\includegraphics[width=\linewidth]{./regret_syn_45f}
        \caption{Average cumulative projection regret}
        \label{fig:regreta}
    \end{subfigure}\\
    \begin{subfigure}[b]{0.9\columnwidth}
        \centering
	\includegraphics[width=\linewidth]{./bar_syn_45f}
        \caption{Percentage of trials where the best decision is found}
        \label{fig:n_besta}
    \end{subfigure}
    \caption{Performance comparison between different strategies using setting~\ref{it:settinga} with $d=10$, $K=45$, $\vartheta=0.5$ and $u = 5$. }\label{fig:result_a}
\end{figure}
\begin{figure}[!htb]
    \centering
    \begin{subfigure}[b]{0.9\columnwidth}
        \centering
	\includegraphics[width=\linewidth]{./regret_syn_45bias}
        \caption{Average cumulative projection regret}
        \label{fig:regretb}
    \end{subfigure}\\
    \begin{subfigure}[b]{0.9\columnwidth}
        \centering
	\includegraphics[width=\linewidth]{./bar_syn_45bias}
        \caption{Percentage of trials where the best decision is found}
        \label{fig:n_bestb}
    \end{subfigure}
    \caption{Performance comparison between different strategies using setting~\ref{it:settingb} with $d=10$, $K=45$, $\vartheta=0.5$ and $u = 5$. }\label{fig:result_b}
\end{figure}

In the simulations for the finite-arm case using settings~\ref{it:settinga} and \ref{it:settingb}, we set $d=10$, $K=45$, $\vartheta=0.5$ and $u = 5$. The simulation results are shown in \cref{fig:result_a,fig:result_b}. We observe the following:
\begin{itemize}
  \item The average cumulative projection regrets of different strategies are shown in \cref{fig:regreta,fig:regretb}.  We see that GENTRY has obvious sublinear cumulative projection regret performance. The other benchmark strategies all suffer from a linearly increasing cumulative projection regret. This verifies that if our objective is to maximize the cumulative projection reward instead of the cumulative return (including the corruption), GENTRY is more appropriate. 
  \item \cref{fig:n_besta,fig:n_bestb} show the percentage of trials in which the optimal arm is chosen for more than $90\%$ of the time in the last $200$ time steps. We see that GENTRY finds the optimal arm in most trials, and outperforms the other strategies by a significant margin.
\end{itemize}

In the simulations for the infinite-arm case using setting~\ref{it:settingc}, we set $d=4$, $\vartheta=0.5$ and $u = 2$. From \cref{fig:regretc}, we also observe that GENTRY has obvious sublinear cumulative projection regret performance. The other benchmark strategies have linearly increasing cumulative projection regret. This verifies the efficiency of GENTRY for the infinite-arm case.

\begin{figure}[!htpb]
        \centering
	\includegraphics[width=\linewidth]{./regret_syn_inf}
        \centering	
	\caption{Average cumulative projection regret using setting \ref{it:settingc} with $d=4$, $u = 2$ and $\vartheta=0.5$.}       
    \label{fig:regretc}
\end{figure}

\subsection{Experiments on Wine Quality Dataset}\label{ssec:real_data}
We next compare the performance of different strategies using the wine quality dataset, which contains $11$-dimension description vectors of $4898$ white wines and their ratings (scores between $0$ and $10$). In each trial, we randomly select $200$ wines with ratings $4$, $5$, $6$, $7$ and $8$, as the decision set $\mathbb{D}$, since among all the wines there are only $5$ wines with ratings larger than $8$ and $20$ wines with ratings less than $4$. Each dimension of the wine description vector is a physicochemical characteristic like volatile acidity, chlorides, or density. Due to privacy and logistic issues\cite{cortez2009modeling}, only the physicochemical characteristics and ratings are available (e.g., there is no data about grape types, wine brand, wine selling price, etc.). We add one additional feature drawn \gls{iid} from $\mathcal{U}(0,1)$ as the protected feature. The corresponding rating of each wine is then corrupted by subtracting $4$ times this protected feature value from the original rating. In this experiment, we take the original rating as the projection reward. Finally, we add a constant $1$ as the constant feature to each description vector. If we put the protected feature as the final dimension of each wine, then $d=13$, and the projection matrix $P_\mathbb{U}$ is defined as a diagonal matrix whose $(i,i)$ entry is 1 for $i=1,\cdots,12$, and $0$ for $i=13$. As there are finitel many arms, we use $\epsilon = \epsilon_t^f$ in this experiment. The results are shown in \cref{fig:regret_wine}, from which we observe that GENTRY outperforms all the other strategies.


\begin{figure}[!htpb]
  \centering
  \includegraphics[width=\linewidth]{./regret_wine}
 \centering
 \caption{Average cumulative projection regret using the wine quality dataset.}
		\label{fig:regret_wine}
\end{figure}


\section{Conclusion} \label{sec:conclusion}

We have formulated the orthogonal projection problem in the linear stochastic bandit model, where the objective is to maximize the cumulative projection reward over a subspace of decision attributes based on observed returns that consist of the projection reward with corruption. Our proposed GENTRY achieves sublinear projection regret for the finite- and infinite-arm cases. Experiments verify the efficiency of our strategy. Our formulation and strategy are useful in avoiding discrimination in recommendation systems and in mixed drug treatment trials.

In this paper, we have assumed that the target subspace is known beforehand when decomposing the reward. However, in practice, we may not know what is a suitable projection subspace \emph{a priori}. It is of interest in future research to develop methods to learn this subspace in conjunction with the best arm using possibly additional side-information. 


\bibliographystyle{IEEEtran}
