\section{Contextual bandits with convex risk}

We consider the standard contextual bandit setting where an agent sequentially observes at time $t\in\bN$ a decision set $\cX_t\subseteq \bR^d$, then chooses an action $X_t\in\cX_t$ and receives a stochastic reward $Y_t$, the distribution of which is dependent on $X_t$. More formally, let $\cX=\cup_{t\in\bN} \cX_t$ and $\Phi\colon \cX \rightarrow \cP(\bR)$ a mapping from actions to reward distributions, so that the agent receives at time $t$ the reward $Y_t\sim \Phi(X_t)$. We denote by $\cF_t=\sigma\left(\cX_1, X_1, Y_1, \dots, \cX_{t-1}, X_{t-1}, Y_{t-1}, \cX_t, X_t\right)$ the $\sigma$-algebra corresponding to the information available to the agent at time $t$ (that is after choosing the action $X_t$ but before observing the reward $Y_t$). Loosely speaking, the goal of the agent is to learn a representation of the mapping $\Phi$ in order to select actions that induce high rewards. A standard inductive bias in this context is to assume a linear relation between rewards and contexts, typically of the form $Y_t=\left\langle \theta^*, X_t\right\rangle + \eta_t$, where $\eta$ is a stochastic noise process. In this work, we consider a slightly more general notion of linearity by assuming instead the existence of a factorization
\begin{center}
\begin{tikzpicture}[node distance=0.15\textwidth]
\node (a)  {$\cX$};
\node (b) [right of=a] {$\bR^p$};
\node (c) [right of=b] {$\cP(\bR)$};

\draw[->] (a) -- node[above] {$\ell^*$} (b);
\draw[->] (b) -- node[above] {$\varphi$} (c);
\draw [->] (a) to [out=-15,in=-165] node[below] {$\Phi = \varphi\circ \ell^*$} (c);
\end{tikzpicture}
\end{center}
where $\ell^*\colon \cX\rightarrow \R^p$ denotes a linear map. In other words, the reward distribution (but not necessarily its mean) is linearly parametrized by the chosen action. We denote such a linear bandit by $(\varphi, \ell^*)$. When the distribution depends on a single parameter ($p=1$), we represent the linear form by $\ell^*\colon x\in\cX\mapsto \langle \theta^*, x\rangle$, where $\theta^*\in\R^d$, and we use the notation $(\varphi, \theta^*)$, or equivalently we say that it is represented by $Y\sim \varphi(\langle \theta^*, X\rangle)$. In the following, we also denote by $\Theta\subseteq \R^d$ a subset of possible values for the parameter $\theta^*$ (and assume for convenience that $\theta^*$ is in the interior of $\Theta$).

As an example, let us consider the following Gaussian mapping $\Phi\colon x\in\cX \mapsto \mu(x) + \sigma(x) \cN(0, 1)$.
If $\sigma$ is constant and $\mu(x) = \langle \theta_{\mu}, x\rangle$, we recover a standard linear bandit model, in which the goal is to maximize the cumulative average rewards $\sum_{t=1}^{T}\mu(X_t)$. However, in many applications, the agent may exhibit a preference for actions leading to lower volatility of rewards or higher $5\%$ quantile, in order to mitigate extreme events. This risk aversion can be encoded for instance by $\mu(X_t) - 1.64 \sigma(X_t)$, where $-1.64$ is approximately the $5\%$ quantile of the standard Gaussian.

\subsection{Overview of risk measures}

\paragraph{Convex loss}
In the bandit setting, the agent faces the classical dilemma between exploitation (playing the most promising actions) and exploration (playing other actions to gain information). For most contextual bandit algorithms, the exploitation takes the form of supervised estimation that consists in learning the mapping $\varphi$ at time $t$ from the past observations $\lbrace (X_s, Y_s),\ 1\leq s \leq t\!-\!1\rbrace$. When the expected reward is parametrized by $Y_t = \langle \theta^*, X_t\rangle + \eta_t$ with $\bE[\eta_t\lvert \cF_t]=0$, a standard strategy consists in estimating $\theta^*$ by ridge regression $\min_{\theta\in\Theta}\sum_{s=1}^{t-1} \left(Y_s - \langle \theta, X_s\rangle\right)^2 + \frac{\alpha}{2}\lVert \theta\rVert^2_2$, where $\alpha>0$ is a regularization parameter. Assuming for now the solution is in the interior of $\Theta$, the solution can be written as $\wh{\theta}_t=\left(V^{\alpha}_t\right)^{-1}\sum_{s=1}^{t-1}Y_sX_s$, where $V^{\alpha}_t \coloneqq \sum_{s=1}^{t-1} X_s X_s^\top + \alpha I_d$ is a $d\times d$ positive definite matrix. This method presents several advantages: it can be computed efficiently via sequential matrix inversion (with complexity $\cO(d^2)$ at each step thanks to the Sherman-Morrison formula for the rank-one update $V_{t+1} = V_t + X_t X_t^\top$ starting from $V_0 = \alpha I_d$) and explicit confidence ellipsoids for $\theta^*$ can be constructed analytically around $\wh{\theta}_t$ to tune exploration \citep{abbasi_yadkori2011}. The implicit limitation of this procedure is that it can only estimate the expectation $\bE[Y] = \argmin_{\theta\in\Theta} \bE[(Y-\langle\theta, X\rangle)^2]$. We call this setting the \textit{mean-linear} bandit.

As motivated by the example above, we aim to estimate other statistics than the mean of the reward distribution. Drawing inspiration from this simple case, we consider an arbitrary convex loss function $\cL \colon \R\times\R^p \rightarrow \R_+$ and define the \textit{risk measure} associated with loss $\cL$ for a distribution $\nu$ over $\R$ as $\rho_{\cL}(\nu) = \arg\min_{\xi\in \R^p}\bE_{Y\sim\nu}\left[ \cL(Y, \xi)\right]$. We assume here that the $\argmin$ is unique for simplicity (which is the case if $\cL$ is strongly convex) and will sometimes use the notation $\rho_{\cL}(Y)$ instead of $\rho_{\cL}(\nu)$ for a random variable $Y$ with distribution $\nu$. Similarly, we define the conditional risk measure $\rho_{\cL}(\nu\lvert \cG) = \arg\min_{\xi\in \R^p}\bE_{Y\sim\nu}\left[ \cL(Y, \xi)\lvert \cG\right]$ for any event $\cG$ with positive measure. Note that with this definition, $\rho_{\cL}(\nu)$ is a vector in $\R^p$. When $p=1$, we call these \textit{scalar} risk measures. The motivation to consider vector-valued risk measures in this framework comes from the fact that not every measure of interest can be \textit{elicited} as a scalar risk measure, which we develop in the next paragraph.

\paragraph{Elicitable risk measure} Scalar risk measures that can be expressed as minimizers of such loss functions are known as  (first-order) \textit{elicitable} risk measures \citep{ziegel2016coherence}. Examples of such measures include the mean, the median, and more generally any quantile and expectile, which we further discuss below as special cases of risk measures associated with convex potentials. Other examples are any generalized moments $\rho(\nu)=\bE_{Y\sim\nu}[T(Y)]$, where $T\colon\R\rightarrow\R$ is a $\nu$-integrable mapping, and the entropic risk defined by $\rho_{\cL}(\nu) = \frac{1}{\gamma}\log\bE_{Y\sim\nu}[e^{\gamma Y}]$ \citep{maillard2013robust}. Unfortunately, not all measures commonly encountered in the risk literature are first-order elicitable. In particular, neither the variance nor the CVaR can be expressed as scalar risk measures with respect to a convex loss \citep{fissler2015expected, fissler2016higher}. However, they are second-order elicitable, in the sense that the pairs (mean, variance) and (VaR, CVaR) are jointly elicitable. We refer to Appendix~\ref{app:elicitable} for a summary and further interpretation of elicitable risk measures.

We say that the loss $\cL$ is adapted to the linear bandit $(\varphi, \ell^*)$ if for all $x\in\cX$, $\ell^*$ is a minimizer of $\bE\left[ \cL\left(Y, \ell(x)\right) \right]$ among all linear forms $\ell\colon \cX\rightarrow \R^p$, where $Y\sim\varphi\circ \ell^*(x)$ denotes the reward random variable of the linear bandit when action $x$ is played. Intuitively, this means that the risk measure $\rho_{\cL}$ of the reward distribution is linearly parametrized by the actions, the same way the expected reward is a linear form of the action in the standard mean-linear bandit.

\begin{remark}
	The above definition is written in the general case of a vector-valued risk measure $\rho_{\cL}$. In the rest of this paper, we only consider scalar risk measure and leave the extension to measures like CVaR for further work. We say that $\cL$ is adapted to the linear bandit $(\varphi, \theta^*)$ if for all
	$x\in\cX$, we have that $\theta^* \in \arg\min_{\theta\in\Theta} \bE_{Y\sim \varphi(\langle\theta^*, x\rangle)}\left[ \cL\left(Y, \langle \theta, x\rangle\right) \right]$.
\end{remark}

\paragraph{Convex potential} A special case of interest is when the convex loss $\cL=\cL_{\psi}$ derives from a potential $\psi$, that is when $\cL_{\psi}(y,\xi) = \psi(y\!-\!\xi)$. This includes the ordinary least square potential associated to the mean, as well as quantiles and expectiles. We assume the reader to be familiar with the former, but perhaps less so with the latter. Following \citet{newey1987asymmetric}, we define the $p$-expectile of $\nu$ for $p\in(0, 1)$ as $\argmin_{\xi\in\R} \bE_{Y\sim\nu}[\lvert p - \ind_{Y<\xi}\rvert (Y-\xi)^2]$. Expectiles have been studied in particular in the context of risk management \citep{bellini2017risk} and risk-aware Bayesian optimization \citep{torossian2020bayesian}. Furthermore, under some symmetry conditions, quantiles and expectiles are known to coincide \citep{abdous1995relating}, and thus expectiles can be seen as a smooth (in particular differentiable) generalization of quantiles (see \cite{philipps2022interpreting} for further interpretation of the notion of expectiles). We refer the reader to Table~\ref{table:potential} for a summary of risk measures elicited by convex potentials.

\begin{small}
	\begin{table}
		\caption{Example of risk measures elicited by convex potentials.}
		\label{table:potential}
		\centering
		\begin{tabular}{lll}
			\toprule
			Name     & Potential $\psi(z)$     & Risk measure $\rho_{\psi}(\nu)$ \\
			\midrule
			Mean & $z^2/2$  & $\rho_{\psi}(\nu) = \int y\nu(dy)$\label{eqn:OLS_potential}\\[1.0ex]
			Quantile, $p\in(0,1)$ & $(p-\ind_{z<0})z$  & $\int_{-\infty}^{\rho_{\psi}(\nu)} \nu(dy) = p$\label{eqn:quantile_potential}\\[1.0ex]
			Expectile, $p\in(0,1)$ & $\lvert p-\ind_{z<0}\rvert z^2$  & $(1-p)\int_{-\infty}^{\rho_{\psi}(\nu)} \lvert y-\rho_{\psi}(\nu)\rvert \nu(dy) = p\int_{\rho_{\psi}(\nu)}^{\infty} \lvert y-\rho_{\psi}(\nu)\rvert \nu(dy)$ \label{eqn:expectile_potential}\\[1.0ex]
			\bottomrule
		\end{tabular}
		\vskip -5mm
	\end{table}
\end{small}

In the terminology defined above, the ordinary least square potential is adapted to the mean-linear reward model $Y_t=\langle \theta^*, X_t\rangle + \eta_t$ with $\bE[\eta_t\lvert \cF_t]=0$. More generally, such an additive decomposition exists for losses derived from potentials (see Proposition~\ref{prop:linearity_psi} in Appendix~\ref{app:convex_potentials}).

\paragraph{Non-unicity of adapted loss} In general, a risk measure can be described by multiple different adapted losses. First, the set of losses that elicit a given risk measure is a cone invariant by scalar translation, i.e. $\rho_{\alpha\cL + \beta} = \rho_{\cL}$ for all $\alpha>0$ and $\beta\in\R$. Other less trivial examples of non-unicity arise even for the simple mean criterion. Indeed, Theorem~1 in \cite{banerjee2005optimality} shows that $\bE_{Y\sim\nu}\left[Y\right]=\rho_{\cB_{\psi}}(\nu)$ where $\psi$ is any strictly convex, differentiable function and $\cB_{\psi}\colon (y, \xi)\mapsto \psi(y) - \psi(\xi) - \psi'(\xi)(y-\xi)$ is the Bregman divergence associated to $\psi$, which generalizes the quadratic potential. In fact, every continuously differentiable loss $\cL$ that elicits the mean has this form (Theorem~3 and 4 in \citet{banerjee2005optimality}). Similarly, the pairs (mean, variance) and (VaR, CVaR) can be elicited by families of differentiable, strictly convex functions (see Table~\ref{table:elicitable} in Appendix~\ref{app:elicitable}).

\subsection{Contextual bandits with linear elicitable risk measures}
\paragraph{Regret} For a linear bandit $(\varphi, \theta^*)$, we define the pseudo-regret associated with a loss $\cL$ and a sequence of actions $\left(X_t\right)_{1\leq t\leq T}$ as $\cR_T = \sum_{t=1}^T \rho_{\cL}\left(\varphi(\langle \theta^*, X^*_t\rangle)\right) - \rho_{\cL}\left(\varphi(\langle \theta^*, X_t\rangle)\right)$, where $X^*_t = \argmax_{x\in\cX_t} \rho_{\cL}\left(\varphi(\langle \theta^*, x\rangle)\right)$ is the optimal action w.r.t the risk measure $\rho_{\cL}$. By definition, if the loss $\cL$ is adapted to the linear bandit, this notion of regret reduces to $\cR_T = \sum_{t=1}^T \langle \theta^*, X^*_t\rangle - \langle \theta^*, X_t\rangle$, which is formally the same as the standard regret for mean-linear bandits. What differs though is the meaning of $\langle \theta^*, X_t\rangle$, which can now represent any elicitable risk measure for the reward distribution. As an example, this framework paves the way for expectile-linear bandit of the form $Y_t = \langle \theta^*, X_t\rangle + \eta_t$ where the conditional expectile of $\eta_t$ is zero and expectile rewards are measured as linear forms of the actions $\langle \theta^*, X_t\rangle$.

\paragraph{Supervised estimation of $\theta^*$} Similarly to how ridge regression provides natural predictors of the mean, we define the estimator $\wh{\theta}_t \in \argmin_{\theta\in\Theta} \sum_{s=1}^{t-1} \cL\left(Y_s, \langle \theta, X_s\rangle\right) + \frac{\alpha}{2}\lVert \theta \rVert^2_2$, which corresponds to the empirical risk minimization associated to an adapted loss $\cL$, with $L^2$ regularization parameter $\alpha>0$. Assuming that $\cL$ is differentiable and that $\wh{\theta}_t$ is in the interior of $\Theta$, this estimator is characterized by $\alpha \wh{\theta}_t = -\sum_{s=1}^{t-1} \partial \cL\left(Y_s, \langle \wh{\theta}_t, X_s\rangle\right)X_s$, where $\partial\cL(y, \xi)$ stands for the derivative of $\xi\mapsto \cL(y, \xi)$, i.e the partial derivative of $\cL$ with respect to the second coordinate. When $\wh{\theta}_t$ is not in the interior of $\Theta$, an additional projection onto $\Theta$ is necessary, which we denote by the operator $\Pi$. We also define by $H^{\alpha}_t(\theta) = \sum_{s=1}^{t-1}\partial^2 \cL\left(Y_s, \langle \theta, X_s\rangle\right)X_sX_s^\top + \alpha I_d$ the Hessian of the empirical loss at $\theta$ of the minimization problem, with $I_d$ the identity matrix of $\R^d$ and $\partial^2$ the second order derivative with respect to the second coordinate, and denote by $\lVert x\rVert_{P}=\sqrt{\langle x, Px\rangle}$ the norm associated with a positive definite matrix $P$ (typically $P=H^\alpha_t(\theta)$ or $P=V^\alpha_t$).

We note that when $\cL$ derives from the quadratic potential $\psi(\xi) = \xi^2 /2$, it holds that $H^\alpha_t(\theta) = V^{\alpha}_t$ and we thus fall back to the mean-linear case. For all other choices of the loss function $\cL$, the Hessian $H^\alpha_t$ depends on $\theta$, and in particular no closed-form expression of $\wh{\theta}_t$ in terms of the inverse of $H^\alpha_t$ is available. As we detail in the next sections, this introduces technical challenges to the analysis of linear bandit algorithms and forces the use of convex programming algorithms to numerically evaluate $\wh{\theta}_t$.

\begin{remark}
	Similar complications arise in the case of generalized linear bandits (GLB) $Y_t = \mu(X_t) + \eta_t$, with $\bE[\eta_t\lvert \cF_t]=0$ and $\mu$ the link function between actions and expected rewards. In fact, GLB can be seen as a special case of the risk-aware setting with $\cL$ the negative log-likelihood loss. While formally similar, we point out that GLB is designed solely to maximize the mean reward criterion. Another difference with our setting is that the use of maximum likelihood estimation requires a parametric assumption on the dsitribution of $Y_t$, typically that it belongs to a one-dimensional exponential family.
\end{remark}

\paragraph{Extension of LinUCB to linear bandits with convex loss} The main benefit of the formulation of risk-awareness in terms of convex losses is that it suggests a transparent generalization of the standard LinUCB algorithm (OFUL in \citet{abbasi_yadkori2011}, chapter 19 in \citet{lattimore2020bandit}), essentially substituting the least-squares estimate with the empirical risk minimizer associated with $\cL$. The general idea of such optimistic algorithms is to play at time $t$ the action $x\in\cX_t$ with the highest plausible reward. In the mean-linear case with ridge regression, this highest plausible reward takes the form of $\langle\wh{\theta}_t, x\rangle + \gamma_t(x)$, where $\gamma_t(x)$ is a certain action-dependent quantity also known as the \textit{exploration bonus}. We write the general structure of our extension of LinUCB in Algorithm~\ref{algo::UCB_convex_risk}.

\begin{algorithm}[]
	\caption{LinUCB for convex risk \label{algo::UCB_convex_risk}}
	\SetKwInput{KwData}{Input}
	\KwData{horizon $T$, loss function $\cL$, regularisation parameter $\alpha$, projection $\Pi$, exploration bonus sequence $(\gamma_t)_{t\in\N}$.}
	\SetKwInput{KwResult}{Initialization}
	\SetKwComment{Comment}{$\triangleright$\ }{}
	\SetKwComment{Titleblock}{// }{}
	\KwResult{Observe $\cX_1$.}
	\For{$t=1, \dots, T$}{
		$\widehat{\theta}_t \in \arg\min_{\R^d} \sum_{s=1}^{t-1} \cL(Y_s, \langle \theta, X_s\rangle) + \frac{\alpha}{2}\lVert \theta \rVert^2_2$ \Comment*[r]{Empirical risk minimization}
		$\bar{\theta}_t = \Pi(\wh{\theta}_t)$ \Comment*[r]{Projection}
		$X_t = \arg\max_{x\in\cX_t} \langle\bar{\theta}_t, x\rangle + \gamma_t(x)$ \Comment*[r]{Play arm}
		Observe $Y_t$ and $\cX_{t+1}$.
	}
\end{algorithm}

\section{Analysis of risk-aware LinUCB}

The goal of this section is to derive an exploration bonus sequence $(\gamma_t)_{t\in\N}$ and a projection operator $\Pi¸$ that ensure sub-linear regret of the corresponding LinUCB instance.

\subsection{Martingale property and concentration}\label{subsec:martingale}
A key property for the analysis of mean-linear bandits is that the sum process $\sum_{s=1}^{t-1} \eta_s X_s$ naturally defines a vector-valued martingale in $\R^d$ with respect to the filtration $\cF_t$ \citep{abbasi_yadkori2011}. This is not the case in general for bandits associated with generic convex losses. For a given loss $\cL$, we know that $\theta^* = \argmin_{\theta}\bE[\cL(Y_t, \langle\theta, X_t\rangle)\lvert\cF_t]$, which implies $\bE[\partial\cL(Y, \langle\theta^*, X_t\rangle)\lvert \cF_t]=0$ if $\cL$ is differentiable, since $X_t$ is measurable with respect to $\cF_t$. A direct consequence of this is that $S_t=\sum_{s=1}^{t-1} \partial\cL(Y_s, \langle \theta^*, X_s\rangle) X_s$ defines a $\cF$-martingale. This process is at the heart of the next proposition, which establishes confidence bounds using the method of mixture (see \citet{delapena_self_normalized} in general and \citet{abbasi_yadkori2011, faury2020improved} for specific applications to contextual bandits). We detail below a helpful assumption to transform the sum process $S$ into a nonnegative supermartingales and state the high-probability uniform deviation bound we obtain, the proof of which is deferred to Appendix~\ref{app:proof_conf}.

\begin{restatable}[Supermartingale control]{assumption}{assumptionone}\label{ass:1} There exists $\sigma>0$ such that for any $t\in\N$ and $\lambda\in\R^d$, we have
\[\bE\left[\exp\left(\partial\cL\left(Y_t, \langle \theta^*, X_t\rangle\right)\lambda^\top X_t - \frac{\sigma^2}{2}\partial^2\cL\left(Y_t, \langle \theta^*, X_t\rangle\right)\left(\lambda^\top X_t\right)^2 \right)\middle| \cF_t\right] \leq 1\,.\]
\end{restatable}

\begin{restatable}[Method of mixtures for convex loss regression]{proposition}{proptwo}\label{prop:conf}
	Let $\beta>0$. Under Assumption~\ref{ass:1}, it holds that
	\[\bP\left(\exists t\in\N,\ \lVert S_t \rVert^2_{H^\beta_t(\theta^*)^{-1}} \geq \sigma^2\left(2\log\frac{1}{\delta} + \log\frac{\det H^\beta_t(\theta^*)}{\det \beta I_d}\right) \right) \leq \delta\,.\]
\end{restatable}

\paragraph{Discussion on Assumption~\ref{ass:1}} This assumption may look like an ad hoc attempt to mimic the sub-Gaussian method of mixtures, however we argue that it comes rather naturally if we impose some mild restrictions to the loss function. First, if the curvature of $\cL$ is bounded away from zero, i.e there exists $m>0$ such that $\partial^2 \cL \geq m$ uniformly, then it is sufficient to ask that $\partial\cL(Y_t, \langle \theta^*, X_t\rangle)$ is $\sqrt{m}\sigma$-sub-Gaussian. Note in the standard mean-linear setting $Y_t = \langle \theta^*, X_t\rangle + \eta_t$ with $\cL(y, \xi) = \frac{1}{2}(y-\xi)^2$, we have that $\partial\cL(Y_t, \langle \theta^*, X_t\rangle) = \eta_t$, which is classically assumed to be sub-Gaussian. For other losses, it may be more convenient for the modeler to make assumptions on the distribution of observable quantities such as $X_t$ and $Y_t$ rather than directly on $\partial\cL(Y_t, \langle \theta^*, X_t\rangle)$. Formally, this raises the question of how the sub-Gaussian property of a random variable $Z$ transfers to $f(Z)$ for a given mapping $f$. While to the best of our knowledge no complete answer is available, several partial results exist:
\begin{enumerate}[(i)]
	\item If $Z$ is Gaussian with variance $\sigma^2$ and $f$ is $M$-Lipschitz, the Tsirelson-Ibragimov-Sudakov inequality (Theorem~5.5 in \citet{boucheron2013concentration}) shows that $f(Z)$ is $M\sigma$-sub-Gaussian. In particular, the Lipschitz assumption holds for $\partial\cL$ if the loss curvature is bounded from above by $M$ uniformly. More generally, if $Z$ can be written as a $\sigma$-Lipschitz function of a standard Gaussian random variable, then $f(Z)$ is $M\sigma$-sub-Gaussian.
	\item If the density of $Z$ is strongly log-concave, then $f(Z)$ is sub-Gaussian (with parameter related to the largest eigenvalue of the Hessian of the log-density, see Theorem~5.2.15 in \citet{vershynin2018high}).
	\item If $Z$ is bounded (i.e actions and rewards are bounded) and $f$ is Lipschitz and separately convex, then $f(Z)$ is sub-Gaussian (application of the entropy method, see e.g Theorem~6.10 in \citet{boucheron2013concentration}). The boundedness assumption can be lifted at the cost of a slightly more stringent condition than the sub-Gaussianity of $Z$, see Theorem~3 in \cite{adamczak2005logarithmic}.
\end{enumerate}

\paragraph{Confidence set for $\theta^*$} To help write the above confidence set in terms of $\theta^*$ and the empirical estimator $\wh{\theta}_t$, we introduce the function $F^{\alpha}_t\colon \theta\in\Theta \mapsto \sum_{s=1}^{t-1}\partial\cL\left(Y_s, \langle\theta, X_s\rangle\right)X_s + \alpha\theta\in\R^d$.
As seen above, $F^{\alpha}_t(\wh{\theta}_t)=0$ and $F^{\alpha}_t(\theta^*)=S_t+\alpha\theta^*$. Noticing that $\lVert F^{\alpha}_t(\theta^*) - F^{\alpha}_t(\wh{\theta}_t)\rVert^2_{H^\beta_t(\theta^*)^{-1}} = \lVert S_t + \alpha\theta^*\rVert_{H^\beta_t(\theta^*)^{-1}} \leq \lVert S_t\rVert_{H^\beta_t(\theta^*)^{-1}} + \alpha\lVert \theta^*\rVert_{H^\beta_t(\theta^*)^{-1}}$, we immediately derive the following result.

\begin{restatable}[]{corollary}{corrone}\label{corr:conf}
For $t\in\N$, $\delta\in(0,1)$, $\alpha, \beta>0$, let
\[\wh{\Theta}^\delta_t = \left\lbrace \theta\in\Theta,\ \lVert F^{\alpha}_t(\theta) - F^{\alpha}_t(\wh{\theta}_t)\rVert_{H^\beta_t(\theta)^{-1}} \leq \sigma\sqrt{2\log\frac{1}{\delta} + \log\frac{\det H^\beta_t(\theta)}{\det \beta I_d}} + \alpha\lVert \theta\rVert_{H^\beta_t(\theta)^{-1}} \right\rbrace\,.\]
Then under Assumption~\ref{ass:1}, it holds that $\bP\left(\forall t\in\N,\ \theta^* \in \wh{\Theta}^\delta_t\right) \geq 1 - \delta$.
\end{restatable}

We constantly use this result in the following, in particular to construct the projection operator $\Pi$. Indeed, if we define $\bar{\theta}_t\coloneqq\Pi(\wh{\theta}_t)$ as  $\argmin_{\theta\in\Theta} \lVert F^{\alpha}_t(\theta) - F^{\alpha}_t(\wh{\theta}_t)\rVert_{H^\beta_t(\theta)^{-1}}$, we have the property that $\Pi(\wh{\theta}_t)\in\wh{\Theta}^\delta_t$ with high probability.

\section{Summary and interpretation of elicitable risk measures}\label{app:elicitable}

We report in Table~\ref{table:elicitable} an overview of common elicitable risk measures and their associated loss functions. We recall that for a distribution $\nu$ over $\R$ and a loss function $\cL\colon \R\times \R^p\rightarrow \R$, we defined the risk measure elicited by $\cL$ as $\rho_{\cL}(\nu) = \arg\min_{\xi\in \R^p}\bE_{Y\sim\nu}\left[ \cL(Y, \xi)\right]$. Note that the pairs (mean, variance) and (VaR, CVaR) are second-order elicitable but neither the variance nor the CVaR are first-order elicitable. For these pairs, we report the generic form of elicitation losses, which depend on arbitrary convex functions $\psi_1$ and $\psi_2$, as well as instances of such losses obtained for the natural choice $\psi_1(\xi)=\psi_2(\xi)=\xi^2/2$.

\begin{small}
	\begin{table}
		\caption{Example of elicitable risk measures.}
		\label{table:elicitable}
		\centering
		\begin{tabular}{llll}
			\toprule
			Name     & $\rho_{\cL}(\nu)$     & Associated loss $\cL(y, \xi)$ & Domain \\
			\midrule
			Mean & $\bE_{Y\sim\nu}[Y]$ & \makecell[l]{$(y-\xi)^2$\\ \\Bregman divergence $\cB_{\psi}(y, \xi)$\\$\psi(y) - \psi(\xi)-\psi'(\xi)(y-\xi),$\\$\psi$ differentiable,\\strictly convex.\\ \\ \\} & $\xi\in \R$\\[5.0ex]
			Derived from potential $\psi$& $\argmin_{\xi\in\R}\bE_{Y\sim\nu}[\psi(Y-\xi)]$ & $\psi(y-\xi)$ & $\xi\in dom(\psi)$\\[5.0ex]
			\makecell[l]{Generalized moment\\$T\colon \R\rightarrow \R$} & $\bE_{Y\sim\nu}[T(Y)]$ & $\frac{1}{2}\xi^2 - \xi T(y)$ & $\xi\in\R$\\[5.0ex]
			\makecell[l]{Entropic risk, $\gamma\neq 0$\\ (Example 1,\\ \citet{embrechts2021bayes})\\ \\ }& $\frac{1}{\gamma}\log\bE_{Y\sim\nu}[e^{\gamma Y}]$ & $\xi + \frac{1}{\gamma}(e^{\gamma(y-\xi)}-1)$ & $\xi\in\R$\\[5.0ex]
			\makecell[l]{(mean, variance)\\ (Example 1.23,\\ \citet{brehmer2017elicitability})}& \makecell[l]{$\mu=\bE_{Y\sim\nu}[Y]$ \\$\sigma^2=\bE_{Y\sim\nu}[Y^2] - \mu^2$} & \makecell[l]{$\frac{1}{2}\xi_1^2 + \frac{1}{2}(\xi_2 + \xi_1^2)^2$\\$- \xi_1 y - (\xi_2 + \xi_1^2)y^2$\\ \\$-\psi_1(\xi_1)-\psi'_1(\xi_1)(y-\xi_1)$\\$- \psi_2(\xi_2+\xi_1^2)$\\$- \psi'_2(\xi_2+\xi_1^2)(y^2-\xi_2-\xi_1^2))$,\\ $\psi_1, \psi_2$ differentiable,\\strictly convex.\\ \\ \\ \\ } & \makecell[l]{$\xi_1\in\R$\\ $\xi_2\geq 0$}\\[5.0ex]
			\makecell[l]{$(\text{VaR}_{\alpha}, \text{CVaR}_{\alpha})$,\\$\alpha\in(0, 1)$\\ (Corollary 5.5,\\ \citet{fissler2016higher})}& \makecell[l]{$\text{VaR}_{\alpha}=\inf\lbrace y\in\R, \int_{-\infty}^{y} d\nu \geq \alpha \rbrace$ \\$\text{CVaR}_{\alpha} = \frac{1}{\alpha} \int_{0}^{\alpha} \text{VaR}_a da$} & \makecell[l]{$(\xi_1-y)_+ - \alpha \xi_1$ \\ $+ \xi_2( \frac{1}{\alpha}(\xi_1-y)_+ - \xi_1 )$\\$+\frac{1}{2}\xi_2^2$\\ \\ $(\ind_{y\leq\xi_1} -\alpha) \psi'_1(\xi_1)$\\$- \ind_{y\leq \xi_1}\psi'_1(y)$ \\ $+ \psi'_2(\xi_2)(\xi_2\!-\!\xi_1\!+\!\frac{1}{\alpha}\ind_{y\leq\xi_1}(\xi_1\!-\!y))$\\$- \psi_2(\xi_2) + c(y)$,\\ $\psi_1$ convex,\\ $\psi_2$ strictly convex and increasing,\\ $c\colon \R \rightarrow \R$.\\ \\ } & $\xi_1\geq \xi_2$\\[5.0ex]
			\bottomrule
		\end{tabular}
		\vskip -5mm
	\end{table}
\end{small}

We provide below some intuition about these commonly used measures in risk management.

\paragraph{Mean-Variance}
Assessing the risk-reward tradeoff of an underlying distribution $\nu$ by penalizing its mean by a higher order moment (typically the variance) is perhaps the most intuitive of risk measures. Following \citet{markowitz1952march}, the mean-variance risk measure at risk aversion level $\lambda\in\R$ is defined by $\rho_{MV_1}(\nu) = \mu - \lambda\sigma$, where $\mu$ and $\sigma$ denote the mean and standard deviation of $\nu$. Alternatively, it can also be defined as $\rho_{MV_2}(\nu) = \mu - \frac{\lambda}{2}\sigma^2$, using the variance rather than the standard deviation in the penalization term. Both measures are especially well-suited for Gaussian distributions as $\mu$ and $\sigma$ fully characterize this family.

\paragraph{VaR and CVaR}
For a distribution with continuous cdf (i.e. it has no atom), the Value-at-Risk $\text{VaR}_{\alpha}(\nu)$ at level $\alpha\in(0, 1)$ is equivalent to the $\alpha$ quantile, and a simple change of variable reveals that the Conditional Value-at-Risk $\text{CVaR}_{\alpha}(\nu)$ is thus $\bE\left[X\mid X\leq \text{VaR}_\alpha(\nu)\right]$. Intuitively, a random variable with a high $\text{CVaR}_{\alpha}$ distribution takes on average relatively high values in the "$\alpha\%$ worst-case" scenario. For $\alpha\rightarrow 1^-$, $\text{CVaR}_{\alpha}(\nu) \rightarrow \bE_{Y\sim\nu}[Y]$ and thus the risk measure becomes oblivious to the tail risk; on the contrary, the case $\alpha\rightarrow 0^+$ emphasizes only the worst outcomes.

In the Gaussian case $\nu\sim\cN(\mu, \sigma)$, using the notations $\phi$ and $\Phi$ respectively for the pdf and cdf of the standard normal distribution, simple calculus shows that
\begin{align*}
	\text{VaR}_{\alpha}(\nu) &= \mu + \sigma\Phi^{-1}(\alpha)\,,\\
	\text{CVaR}_{\alpha}(\nu) &= \mu - \frac{\sigma}{\alpha\sqrt{2\pi}}\phi\left(\Phi^{-1}(\alpha)\right)\,,\\
\end{align*}
i.e. $\text{CVaR}_{\alpha}(\nu) = \rho_{MV_1}(\nu)$ with risk aversion level $\lambda=\frac{1}{\alpha \sqrt{2\pi}}\phi\left(\Phi^{-1}(\alpha)\right)$. In particular, increasing the variance $\sigma^2$ reduces $\text{CVaR}_{\alpha}(\nu)$, corresponding to the intuition of higher volatility risk.

\paragraph{Entropic risk}

The non-elicitability of $\text{CVaR}_{\alpha}$ motivated the use of the entropic risk as an alternative measure. This measures rewrites as (see \citet{brandtner2018entropic})
\[\rho_{\gamma}(\nu) = \sup_{\nu' \text{ probability measure}} \left\lbrace \bE_{Y\sim\nu'}[Y] - \frac{1}{\gamma}\text{KL}(\nu' \lVert \nu)\right\rbrace\,.\]

The intuition here is similar to the mean-variance measure, i.e penalizing the expected value by a measure of uncertainty, but differs by the use of the Kullback-Leibler divergence $\text{\KL}(\nu'\lVert \nu) = \bE_{Y\sim\nu'}[ \log\frac{d\nu'}{d\nu}]$ instead of the variance. The entropic risk measure can be interpreted as the expected value that a mispecified model $\nu'$ (in place of the true underlying distribution $\nu$) would have, where $\text{\KL}(\nu'\lVert \nu)$ controls the magnitude of the mispecification.

Again, in the Gaussian case, this measure reduces to $\rho_{\gamma}(\nu) = \mu + \frac{\gamma}{2}\sigma^2=\rho_{MV_2}(\nu)$ at risk aversion level $\lambda=-\gamma$.

\paragraph{Expectile}
Beyond their interpretation as generalized, smooth quantiles, expectiles can also be understood in light of the financial risk management literature.
Let $e_p(\nu)$ denote the $p$-expectile of $\nu$ for a given probability $p\in(0, 1)$. Then, simple calculus shows that
\[(1-p) \bE_{Y\sim\nu}[(e_p(\nu) - Y)_+] = p \bE_{Y\sim\nu}[(Y-e_p(\nu))_+]\,,\]
where $z_+ = \max(z, 0)$. If $\nu$ represents the distribution of a tradeable asset $Y$ at time $T$, then the $p$-expectile is the strike $K=e_p(\nu)$ such that call and put on $Y$ struck at $K$ at maturity $T$ are in proportion $\frac{1-p}{p}$ to each other, where we define the call and put prices (with zero time discounting) by respectively
\begin{align*}
C(\nu, K) = \bE_{Y\sim\nu}[(Y-K)_+]\,,\\
P(\nu, K) = \bE_{Y\sim\nu}[(K-Y)_+]\,.
\end{align*}
Similarly, \citet{keating2002universal} introduced the notion of Omega ratio as a risk-return performance measures. It is defined at level $K$ by
\[\Omega(K) = \frac{\int_{K}^{+\infty} \left(1 - F(y)\right) dy}{\int_{-\infty}^{K} F(y)dy}\,,\]
where $F$ is the cdf of $\nu$. This ratio can also be viewed as a call-put ratio, hence another definition of the $p$-expectile is via the implicit equation $\Omega(K)=\frac{1-p}{p}$ for $K=e_p(\nu)$.

We now derive an elementary proof of the sensitivity of the expectile with respect to the standard deviation $\sigma$ of $\nu$, based on the call-put parity principle, which states that for any distribution $\nu$ and strike $K$,
\[C(\nu, K) - P(\nu, K) = \bE_{Y\sim\nu}[Y] - K\,.\]
Assuming $\nu$ is a normal or lognormal distribution (i.e. essentially a distribution parametrized by its variance, as in the Bachelier or Black-Scholes models), we write $C(\nu, K)=C(\sigma, K)$, $P(\nu, K)=P(\sigma, K)$ and $e_p(\sigma)$. Notice that the call-parity principle implies that $\partial_{\sigma}C = \partial_{\sigma}P$. We call this quantity Vega and denote it by $V$. From the relation $C(\sigma, e_p(\sigma)) = (1-p)/p P(\sigma, e_p(\sigma))$, we deduce that
\begin{align*}
\frac{d}{d\sigma} C(\sigma, e_p(\sigma)) &= \partial_{\sigma}C(\sigma, e_p(\sigma)) + \partial_K C(\sigma, e_p(\sigma)) \frac{d e_p(\sigma)}{d\sigma}\,,\\
\frac{d}{d\sigma} P(\sigma, e_p(\sigma)) &= \partial_{\sigma}P(\sigma, e_p(\sigma)) + \partial_K P(\sigma, e_p(\sigma)) \frac{d e_p(\sigma)}{d\sigma}\,,
\end{align*}
and thus
\begin{align*}
\frac{1-2p}{p} V + \frac{d e_p(\sigma)}{d\sigma} \left(\frac{1-p}{p}\partial_K P(\sigma, e_p(\sigma)) - \partial_K C(\sigma, e_p(\sigma))\right) = 0\,.
\end{align*}
Elementary option pricing principles show that $V\geq 0$, i.e. the call and put prices both increase with higher volatility, as well as $\partial_K C \leq 0$ and $\partial_K P \geq 0$. Therefore, we deduce that $\frac{d e_p(\sigma)}{d\sigma}\leq 0$, i.e. the $p$-expectile decreases with higher volatility, thus making it suitable for risk management purposes.

In particular for $p=1/2$, the $p$-expectile corresponds to the strike $K$ at which call and put have equal prices, which by the call-put parity principle (with zero discounting) implies that $K=\bE[Y]$, thus giving an alternative derivation of the equivalence between $1/2$-expectile and mean.

\section{Properties of convex losses and potentials}\label{app:convex_potentials}

Before we prove Proposition~\ref{prop:linearity_psi}, we write the following technical lemma.

\begin{lemma}[Risk measures $\rho_{\psi}$ are additive]\label{lemma:add_psi} Let $\psi\colon \R\rightarrow \R$ be a strongly convex, differentiable function, $\nu$ be a distribution over $\R$ and $c\in\R$. Then
$\rho_{\psi}(\nu+c) = \rho_{\psi}(\nu) + c$.
\end{lemma}

\proof{
For the sake of simplicity, we assume $\nu$ admits a density $p$ (with respect to the Lebesgue measure) and that $\psi$ and $p$ are regular enough to allow for differentiation under the following integral. Then the risk measure associated with $\cL_{\psi}$ reads $\rho_{\psi}(\nu) = \argmin_{\xi\in\R} \int \psi\left(y - \xi \right)p(y) dy$ and the first order condition gives $\int \psi'(y - \rho_{\psi}(\nu))p(y)dy=0$. Similarly, for any $c\in\R$, we have $\int \psi'(y - \rho_{\psi}(\nu+c))p(y-c)dy=0$ since the density of $\nu+c$ is $p(\cdot - c)$. We now deduce from a simple change of variable $z=y-c$ that $\int \psi'(z + c - \rho_{\psi}(\nu+c))p(z)dz=0$, which shows that $\rho_{\psi}(\nu+c) - c$ is also a minimizer of $\xi\mapsto \int\psi\left(y - \xi \right)p(y) dy$. By uniqueness ($\psi$ is strongly convex), we deduce that $\rho_{\psi}(\nu+c) = \rho_{\psi}(\nu) + c$.
$\hfill\blacksquare$
}

\paragraph{Noise additivity for losses derived from potentials}

\begin{restatable}[]{proposition}{propone}\label{prop:linearity_psi}
	Assume $\cL_{\psi}$ is adapted to the linear bandit $(\varphi, \theta^*)$ and $\psi$ is strongly convex and differentiable. Then there exists a stochastic process $\eta$ such that the bandit is represented at time $t$ by $Y_t\sim\langle \theta^*, X_t\rangle + \eta_t$ and $\rho_{\psi}(\eta\lvert \cF_t)=0$.

\end{restatable}

\proof{
Define the process $\eta$ at time $t$ by $\eta_t=Y_t - \langle\theta^*, X_t\rangle$. To compute $\rho_{\psi}(\nu\lvert \cF_t)$, note that $X_t$ is measurable with respect to $\cF_t$, therefore by Lemma~\ref{lemma:add_psi} and the properties of conditional expectation, we have that $\rho_{\psi}(\eta_t\lvert \cF_t) = \rho_{\psi}\left(Y_t\lvert \cF_t\right)- \langle\theta^*, X_t\rangle=\rho_{\psi}\left(\varphi\left(\langle \theta^*, X_t \rangle\right)\lvert \cF_t\right)-\langle \theta^*, X_t \rangle=0$ by definition of $\cL_{\psi}$ being adapted to the bandit $(\varphi, \theta^*)$.

$\hfill\blacksquare$
}

\section{Approximate convex risk minimisation with online gradient descent}

So far, we have shown that the standard LinUCB principle can be extended to the convex loss setting with similar regret guarantees under some curvature assumption. However, this comes at the cost of a significant computational overhead since the estimator $\wh{\theta}_t$ needs to be calculated from scratch at each step as $\argmin_{\theta\in \R^d} \sum_{s=1}^{t-1} \cL(Y_s, \langle \theta, X_s\rangle) + \frac{\alpha}{2}\lVert \theta \rVert_2^2$. As a reminder, in the standard mean-linear case, this estimator has an analytical expression that amounts to incrementally inverting the matrix $V^\alpha_t$, which can be done efficiently from the knowledge of the inverse of $V^{\alpha}_{t-1}$.

We propose an alternative algorithm that relies on online gradient descent (OGD) to compute a fast approximation of $\wh{\theta}_t$. This may be of practical interest to deploy risk-aware linear bandits in time-sensitive environments, such as in real-time online recommendation systems. Moreover, it can also be used in the mean-linear setting with high dimensional action sets, where computing gradients may be more tractable than inverting a large $d\times d$ matrix.

\begin{algorithm}[]
	\caption{LinUCB-OGD for convex risk \label{algo::UCB-OGD_convex_risk}}
	\SetKwInput{KwData}{Input}
	\KwData{horizon $T$, loss function $\cL$, regularisation parameter $\alpha$, projection $\Pi$, exploration bonus sequence $(\gamma^{\text{OGD}}_{t, T})_{t\leq T}$, gradient descent step sequence $(\epsilon_t)_{t\in\N}$, episode length $h>0$.}
	\SetKwInput{KwResult}{Initialization}
	\SetKwComment{Comment}{$\triangleright$\ }{}
	\SetKwComment{Titleblock}{// }{}
	\KwResult{Observe $\cX_1$, set $\wh{\theta}^{\text{OGD}}_0$, $t=1$, $n=1$.}
	\For{$t=1, \dots, T$}{
		\If{$t=nh+1$}{
				$\widehat{\theta}^{\text{OGD}}_{n} = \widehat{\theta}^{\text{OGD}}_{n-1} - \epsilon_{n-1} \left(\sum_{k=1}^{h} \partial\cL(Y_{(n-1)h+k}, \langle \widehat{\theta}^{\text{OGD}}_{n-1}, X_{(n-1)h+k}\rangle) + \alpha \widehat{\theta}^{\text{OGD}}_{n-1}\right)$ \Comment*[r]{OGD}
			$\bar{\theta}^{\text{OGD}}_{n} =  \frac{1}{n}\sum_{j=1}^n\Pi(\wh{\theta}^{\text{OGD}}_j)$ \Comment*[r]{Average over previous OGD steps}
			$n \leftarrow n+1$\,
		}
		$X_t = \arg\max_{x\in\cX_t} \langle\bar{\theta}^{\text{OGD}}_{n}, x\rangle + \gamma^{\text{OGD}}_{t, T}(x)$ \Comment*[r]{Play with same parameter for $h$ steps}
		Observe $Y_t$ and $\cX_{t+1}$\,;\\
		$t \leftarrow t + 1$\,;
	}
\end{algorithm}

The intuition behind Algorithm~\ref{algo::UCB-OGD_convex_risk} is that at time $t=nh\!+\!1$, the approximation error between the OGD estimate $\bar{\theta}^{\text{OGD}}_n$ and the exact minimizer of the empirical risk $\widehat{\theta}_t$ induces additional exploration, which translates into an increased regret compared to LinUCB. In other words, LinUCB-OGD trades off accuracy for computational efficiency. The episodic structure is borrowed from \cite{ding2021efficient} and is key to ensure sufficient convexity of the aggregate loss $\sum_{k=1}^{h} \partial\cL(Y_{(n-1)h+k}, \langle \widehat{\theta}^{\text{OGD}}_{n-1}, X_{(n-1)h+k}\rangle)$. This allows to leverage the strong approximation guarantees of OGD, which we extend in the following proposition by relaxing the standard boundedness requirement of the gradient (Theorem~3.3, \citet{hazan2019introduction}) to a weaker sub-Gaussian control at a given parameter (proof in Appendix \ref{appendix:proof_sgd}).

\begin{restatable}[OGD regret with sub-Gaussian gradients]{proposition}{propogd}\label{prop:ogd}
Let $\cC$ a convex subset of $\R^d$ and $\Pi$ the projection operator onto $\cC$. For $j=1, \dots, N$, let $\ell_j\colon \cC \longrightarrow \R_+$ a twice differentiable convex function and $a, A >0$ such that $a I_d \preccurlyeq \nabla^2 \ell_j(z) \preccurlyeq A I_d$ for all $z\in\cC$. Define the OGD update at step $j$ by $z_j=\Pi(z_{j-1} - \epsilon_{j-1}\nabla \ell_j(z_{j-1}))$ and $\bar{z}_n=\arg\min_{z\in\cC} \sum_{j=1}^n \ell_j(z)$. Assume that there exists $z^*\in\cC$ such that $\nabla \ell_j(z^*) = g_j + \frac{\alpha}{n} z^*$ with $\alpha\geq 0$ and $g$ a centered, $\R^d$-valued $\sigma$-sub-Gaussian process, and also that $\cC$ is bounded, i.e $\text{diam}(\cC) = \sup_{z,z'\in\cC} \lVert z-z'\rVert<\infty$.
Then with probability at least $1\!-\!\delta$, the OGD regret with step size $\epsilon_j\!=\!\frac{3}{aj}$ is bounded for all $n\leq N$ by
\[\sum_{j=1}^n \ell_j(z_j) - \ell_j(\bar{z}_n) \leq \frac{9}{2a}\left(2d\sigma^2\log \frac{2dN}{\delta} + A^2 \text{diam}(\cC)^2 + \frac{\alpha^2}{n^2}\lVert z^*\rVert^2\right) \left(1 + \log n\right)\,.\]
This can be written more concisely as $\sum_{j=1}^N \ell_j(z_j) - \ell_j(\bar{z}_N) = \cO(\frac{d\sigma^2}{a}\log^2 N)$ when $N\rightarrow +\infty$. In addition, if $g$ is uniformly bounded by a constant $G>0$, the regret with step size $\epsilon_s\!=\!\frac{1}{aj}$ can be reduced to the almost sure bound:
\[ \sum_{j=1}^n \ell_j(z_j) - \ell_j(\bar{z}_n) \leq \frac{G^2}{2a}\left( 1+ \log n\right)\,.\]
\end{restatable}

Our final result, which we prove in Appendix~\ref{appendix:proof_ucb-ogd}, states that the approximation error of OGD induces at most a polylog correction in the regret of LinUCB-OGD.

\begin{restatable}[Regret of LinUCB-OGD for convex risk]{theorem}{theoremtwo}\label{thm:regret_ucb-ogd}
	In addition to the conditions of Theorem~\ref{thm:regret_ucb}, assume that there exists $\epsilon_h>0$ such that for all $j\leq T/h$, $\sum_{k=1}^{h} X_{(j-1)h+k} X_{(j-1)h+k}^\top \succcurlyeq \epsilon_h I_d$, and also that $\partial \cL(Y_t, \langle\theta^*, X_t\rangle)$ is $\sqrt{m}\sigma$-sub-Gaussian for all $t\leq T$. Let $C>0$ and define the exploration bonus sequence by:
	\begin{align*}
 	&\gamma^{\text{OGD}}_{t, T}\colon x\in\cX_t \mapsto c^{\text{OGD},\delta}_{t, T} \lVert x \rVert_{H^{\kappa \alpha}_t(\bar{\theta}^{\text{OGD}}_{\lfloor\!\frac{t\!-\!1}{h} \!\rfloor})^{-1}}\text{\quad and \quad} c^{\text{OGD},\delta}_{t, T}=c^{\delta}_t + 2L\sqrt{\frac{C\kappa m dh^2\sigma^2}{\epsilon_h t} \log\left(\frac{2dT}{h\delta}\right)\log\left(\frac{t}{h}\right)}\,.
	\end{align*}
	Then if $C>0$ is large enough, with probability at least $1-2\delta$, the regret of Algorithm~\ref{algo::UCB-OGD_convex_risk} with the $OGD$ step sequence of Proposition~\ref{prop:ogd} is bounded $\tilde{\cO}\left(\sqrt{T}\right)$, where $\tilde{\cO}$ hides polylogarithmic terms in $T$.
\end{restatable}

\begin{remark}
	The lower bound in $\epsilon_h$ is here to enforce strong convexity of the agregate episodic loss, together with Assumption~\ref{ass:3}. For i.i.d actions, it is known to hold with high probability provided the episode length $h$ is large enough, (Proposition~1, \citet{li2017provably}). Also, note that the union bound used in Proposition~\ref{prop:ogd} imposed the knowledge of the time horizon $T$ during the run of the algorithm (in the definition of $\gamma_{t,T}$), making Algorithm~\ref{algo::UCB-OGD_convex_risk} not anytime.
\end{remark}

\section{Proofs of OGD concentration}\label{appendix:proof_sgd}

\propogd*

\proof{
Let $j\leq n$. The uniform lower bound on the Hessian of $\ell_j$ makes it $a$-strongly convex, which implies
\[ \ell_j(z_j) - \ell_j(\bar{z}) \leq \langle\nabla \ell_j(z_j), z_j - \bar{z}_n \rangle - \frac{a}{2}\lVert \bar{z} - z_j\rVert^2. \]

By definition of the OGD scheme, the following holds:
\begin{align*}
    \lVert z_{j+1} - \bar{z}_n \rVert^2 &= \lVert \Pi\left(z_j - \epsilon_j \nabla \ell_j(z_j)\right) - \bar{z}_n \rVert^2\\
    &\leq \lVert z_j - \epsilon_j \nabla \ell_j(z_j) - \bar{z}_n \rVert^2 \quad\text{(projection onto a convex set)}\\
    &\leq \lVert z_j - \bar{z}_n\rVert^2 + \epsilon_j^2 \lVert \nabla \ell_j(z_j) \rVert^2 - 2\epsilon_j \langle\nabla \ell_j(z_j), z_j - \bar{z}_n\rangle\,,\\
\end{align*}

from which we deduce

\[ \langle \nabla \ell_j(z_j), z_j - \bar{z}_n\rangle \leq \frac{\lVert z_j - \bar{z}_n \rVert^2 - \lVert z_{j+1} - \bar{z}_n \rVert^2}{2\epsilon_j} + \frac{\epsilon_j}{2}\lVert\nabla \ell_j(z_j) \rVert^2\,.\]

\paragraph{Bounded gradients}\ \\
This case is covered by Theorem 3.3 in \citet{hazan2019introduction}. We reproduce the proof here for reference and as a first step towards the more general setting of sub-Gaussian gradients.

Let $G>0$ be such that $\lVert \nabla \ell_j(z_j)\rVert \leq G$ for all $j=1, \dots, n$. This allows to upper bound the above equation, leading to

\[\langle \nabla \ell_j(z_j), z_j - \bar{z}_n\rangle \leq \frac{\lVert z_j - \bar{z}_n \rVert^2 - \lVert z_{j+1} - \bar{z}_n \rVert^2}{2\epsilon_j} + \frac{\epsilon_j}{2}G^2.\]

The online regret of OGD is therefore

\[\sum_{j=1}^n \ell_j(z_j) - \ell_j(\bar{z}_n) \leq \frac{1}{2}\sum_{j=1}^n \frac{\lVert z_j - \bar{z}_n \rVert^2 - \lVert z_{j+1} - \bar{z}_n \rVert^2}{\epsilon_j} - a \lVert z_j - \bar{z}_n \rVert^2 + \frac{G^2}{2} \sum_{j=1}^n \epsilon_j. \]

The first sum can be rewritten after a simple index shift and the convention $1/\epsilon_0\coloneqq 0$:
\begin{align*}
\frac{1}{2}\sum_{j=1}^n \frac{\lVert z_j - \bar{z}_n \rVert^2 - \lVert z_{j+1} - \bar{z}_n \rVert^2}{\epsilon_j} - a \lVert z_j - \bar{z}_n \rVert^2 &= \frac{1}{2}\sum_{j=1}^n \lVert z_j - \bar{z}_n \rVert^2\left(\frac{1}{\epsilon_j} - \frac{1}{\epsilon_{j-1}} - a \right) - \frac{1}{\epsilon_n} \lVert z_{n+1} - \bar{z}_n \rVert^2\\
&\leq \frac{1}{2}\sum_{j=1}^n \lVert z_j - \bar{z}_n \rVert^2\left(\frac{1}{\epsilon_j} - \frac{1}{\epsilon_{j-1}} - a \right)\\
&= 0\\
\end{align*}
for the choice $\epsilon_j = \frac{1}{aj}$. Consequently, the online regret can be simplified as

\begin{align*}
    \sum_{j=1}^n \ell_j(z_j) - \ell_j(\bar{z}_n) &\leq \frac{G^2}{2} \sum_{j=1}^n \epsilon_j\\
    &=\frac{G^2}{2a} \sum_{j=1}^n \frac{1}{j}\\
    &\leq \frac{G^2}{2a}\left(1+\log n\right)\,.\\
\end{align*}

\paragraph{Sub-Gaussian gradients}\ \\

We do not assume here that $\nabla \ell_j(z_j)$ is uniformly bounded, but instead rely on the weaker assumption that $\nabla \ell_j(z^*)$ is sub-Gaussian. The strategy is to control the variation between $\nabla \ell_j(z_j)$ and $\nabla \ell_j(z^*)$ on the one hand, and bound in high probability $\nabla \ell_j(z^*)$ on the other hand.

Notice that $\nabla \ell_j(z_j) = g_j + \frac{\alpha}{n} z^* + \nabla \ell_j(z_j) - \nabla \ell_j(z^*)$ and that there exists $\bar{z}_n\in [z_j, z^*]\subset \cC$ such that $\nabla \ell_j(z_j) - \nabla \ell_j(z^*) = \nabla^2 \ell_j(\bar{z}_n) \left(z_j - z^*\right)$ thanks to the mean value theorem and the convexity of $\cC$. This yields
\begin{align*}
    \lVert \nabla \ell_j(\phi_j)\rVert^2 &\leq 3\lVert g_j \rVert^2 + \frac{3\alpha^2}{n^2} \lVert z^* \rVert^2 + 3 \lVert \nabla \ell_j(z_j) - \nabla \ell_j(z^*)\rVert^2\\
    &\leq 3\lVert g_j \rVert^2 + \frac{3\alpha^2}{n^2} \lVert z^* \rVert^2 + 3 A^2 \lVert z_j - z^*\rVert^2\,,\\
\end{align*}
since $\nabla \ell_j$ is $A$-Lipschitz. Combining this with the above yields
\begin{align*}
    \langle \nabla \ell_j(z_j), z_j - \bar{z}_n\rangle &\leq \frac{3}{2}\frac{\lVert z_j - \bar{z}_n \rVert^2 - \lVert z_{j+1} - \bar{z}_n \rVert^2}{\epsilon_j} + \frac{3}{2}\epsilon_j \lVert g_j\rVert^2 + \frac{3}{2}\epsilon_j \frac{\alpha^2}{n^2} \lVert z^* \rVert^2 + \frac{3}{2}\epsilon_j A^2 \lVert z_j - z^* \rVert^2\\
    &\leq \frac{3}{2}\frac{\lVert z_j - \bar{z}_n \rVert^2 - \lVert z_{j+1} - \bar{z}_n \rVert^2}{\epsilon_j} + \frac{3}{2}\epsilon_j \left(\lVert g_j \rVert^2 + \frac{\alpha^2}{n^2} \lVert z^*\rVert^2 \right) + \frac{3}{2}\epsilon_j A^2 \text{diam}(\cC)^2 \,.\\
\end{align*}

The online regret of OGD is therefore

\begin{align*}\sum_{j=1}^n \ell_j(z_j) - \ell_j(\bar{z}_n) \leq &\frac{3}{2}\sum_{j=1}^n \frac{\lVert z_j - \bar{z}_n \rVert^2 - \lVert z_{j+1} - \bar{z}_n \rVert^2}{\epsilon_j} - \frac{a}{3} \lVert z_j - \bar{z}_n \rVert^2 \\
&+ \frac{3}{2} A^2 \text{diam}(\cC)^2 \sum_{j=1}^n\epsilon_j + \frac{3}{2}\sum_{j=1}^n \epsilon_j \left(\lVert g_j \rVert^2 + \frac{\alpha^2}{n^2} \lVert z^*\rVert^2 \right)\,.
\end{align*}

As in the bounded case, the choice $\epsilon_j = \frac{3}{aj}$ makes the first sum vanish. Moreover, a simple union argument over the Chernoff bound for the $\sigma$-sub-Gaussian random variables $(g_j)_{j=1, \dots, n}$ reveals that

\[ \cE_n = \left\lbrace \forall j=1, \dots, n,\ \lVert g_j \rVert \leq \sigma\sqrt{2d\log \frac{2dn}{\delta}} \right\rbrace \]
holds with probability at least $1 -\delta$ for $\delta\in(0, 1)$. Therefore, the following holds with probability at least $1-\delta$:

\begin{align*}
    \sum_{j=1}^n \epsilon_j \lVert g_j \rVert^2 \leq \sum_{j=1}^n \epsilon_j \lVert g_j \rVert^2 \ind_{\cE_n} \leq 2d\sigma^2\log \frac{2dn}{\delta}\sum_{j=1}^n \epsilon_j \,.
\end{align*}

Therefore, with probability at least $1-\delta$, we obtain the following online regret:
\begin{align*}
    \sum_{j=1}^n \ell_j(z_s) - \ell_j(\bar{z}_n) &\leq\frac{3}{2}\left(2d\sigma^2\log \frac{2dn}{\delta} + A^2 \text{diam}(\cC)^2 + \frac{\alpha^2}{n^2}\lVert z^*\rVert^2\right) \sum_{j=1}^n \epsilon_j\\
     &= \frac{9}{2a}\left(2d\sigma^2\log \frac{2dn}{\delta} + A^2 \text{diam}(\cC)^2 + \frac{\alpha^2}{n^2}\lVert z^*\rVert^2 \right) \sum_{j=1}^n \frac{1}{j}\\
     &\leq \frac{9}{2a}\left(2d\sigma^2\log \frac{2dn}{\delta} + A^2 \text{diam}(\cC)^2 + \frac{\alpha^2}{n^2}\lVert z^*\rVert^2\right) \left(1 + \log n\right)\,.
\end{align*}
$\hfill\blacksquare$
}

\section{Proofs of Theorem~\ref{thm:regret_ucb-ogd}}\label{appendix:proof_ucb-ogd}

In this section, we adapt the regret analysis of LinUCB to the LinUCB-OGD variant that relies on online gradient approximation of the empirical risk minimizer.

\theoremtwo*

\proof{

Let $\ell_j(\theta) = \sum_{k=1}^{h} \cL(Y_{(j-1)h+k}, \langle \theta, X_{(j-1)h+k}\rangle)+\frac{\alpha}{2n}\lVert \theta \rVert^2$. For simplicity, we assume that $\bar{\theta}_t = \wh{\theta}_t$ for all $t\leq T$, i.e the empirical risk minimizer is always in the stable set of the projection operator $\Pi$. We recall that $\wh{\theta}_t$ satisfies $\sum_{j=1}^{n} \nabla \ell_j(\bar{\theta}_t) = 0$ for $n=\frac{t-1}{h}$ (i.e after episode $n$, when $\wh{\theta}^{\text{OGD}}_n$ is updated). In the general case, replacing $\wh{\theta}_t$ by $\bar{\theta}_t$ induces an extra correction factor in the inequalities below which is at most polylogarithmic in $T$ (a consequence of Corollary~\ref{corr:conf}), and hence does not change the conclusion. Again, we point out that, similarly to the generalized linear bandit setting \citep{filippi2010parametric, faury2020improved}, $\wh{\theta}_t$ is often in the stable set of $\Pi$ in practice.

We use the notations of Proposion~\ref{prop:ogd} and define:
\begin{align*}
	&z_j = \wh{\theta}^{\text{OGD}}_j\,,\\
	&\bar{z}_n = \bar{\theta}_{t}\,,\\
	&z^* = \theta^*\,.
\end{align*}

We also denote by $\tilde{z}_n = \bar{\theta}^{\text{OGD}}_n = \frac{1}{n}\sum_{j=1}^n z_j$ the average of the past $n$ OGD updates.

\paragraph{Bound on $\lVert \tilde{z}_{n} - \bar{z}_{n}\rVert$}

We first note that $\nabla \ell_j(\theta^*) = g_j + \frac{\alpha}{n}\theta^*$, where $g_j = \sum_{k=1}^h \partial\cL(Y_{(j-1)h+k}, \langle \theta^*, X_{(j-1)h+k}\rangle)$ is $\sqrt{hm}\sigma$-sub-Gaussian (sum of $h$ terms, each of them being $\sqrt{m}\sigma$-sub-Gaussian). The assumption on $\epsilon_h$ makes the one-step losses $\ell_j$ $m\epsilon_h$ strongly convex. Under Assumption~\ref{ass:3}, we can then apply the bound on the OGD regret of Proposion~\ref{prop:ogd} with $a=m\epsilon_h$, $A=hML^2$, namely that the \textit{good event}
\begin{align*}
	\forall n\leq N,\ \sum_{j=1}^{n-1} \ell_j(z_j) - \ell_j(\bar{z}_n) \leq \frac{Cd h\sigma^2}{\epsilon_h} \log\left(\frac{2dN}{\delta}\right)\log(n)\,,
\end{align*}
holds with probability at least $1-\delta$, for some constant $C>0$ (in which we hide the dependency on $h, M, L, \alpha$ and $S$ to avoid further cluttering) and $N=\lceil \frac{T-1}{h}\rceil$ the maximum number of episodes. We assume to be on this event in the rest of the proof.

The crux of the argument is similar to the proof of Lemma~2 in \citep{ding2021efficient} and exploits the strong convexity of the losses $\ell_j$ to relate the online regret to a control on the distance $\lVert \tilde{z}_n - \bar{z}_n\rVert$. By Jensen's inequality, we have
\[\sum_{j=1}^{n} \ell_j(\tilde{z}_n) - \ell_j(\bar{z}_n) \leq \frac{Cd h\sigma^2}{\epsilon_h} \log\left(\frac{2dN}{\delta}\right)\log(n)\,.\]

Strong convexity also implies the following inequality:
\begin{align*}
\ell_j(\tilde{z}_n) - \ell_j(\bar{z}_n) \geq \langle \nabla \ell_j(\bar{z}_n), \tilde{z}_n - \bar{z}_n\rangle + \frac{m\epsilon_h}{2} \lVert \tilde{z}_n - \bar{z}_n\rVert^2\,.
\end{align*}
Summing over $j=1, \dots, n$ and exploiting the fact that the sum of gradients vanishes at $\bar{z}_n$, we obtain after some simple algebra:
\[\lVert \tilde{z}_n - \bar{z}_n\rVert \leq \frac{Cd h\sigma^2}{\epsilon_h} \log\left(\frac{2dN}{\delta}\right)\log(n)\,.\]

\paragraph{Regret analysis of LinUCB-OGD} Mirroring the regret proof of LinUCB, we see that we need
\[\forall t\leq T,\ \Delta(X_t, \bar{\theta}^{\text{OGD}}_t) \leq \gamma_t(X_t)\]
holds with high probability, for a certain exploration sequence $(\gamma_t)_{t\in\N}$. This amount to controlling the norm
\begin{align*}
\lVert \theta^* - \bar{\theta}^{\text{OGD}}_t\rVert_{\bar{H}^{\alpha}_t(\theta^*, \bar{\theta}^{\text{OGD}}_t)} &\leq \lVert \theta^* - \bar{\theta}_t\rVert_{\bar{H}^{\alpha}_t(\bar{\theta}_t, \bar{\theta}^{\text{OGD}}_t)} + \lVert \bar{\theta}_t - \bar{\theta}^{\text{OGD}}_t\rVert_{\bar{H}^{\alpha}_t(\bar{\theta}_t, \bar{\theta}^{\text{OGD}}_t)}\\
&\leq \lVert \theta^* - \bar{\theta}_t\rVert_{\bar{H}^{\alpha}_t(\theta^*, \bar{\theta}^{\text{OGD}}_t)} + \sqrt{M}\lVert \bar{\theta}_t - \bar{\theta}^{\text{OGD}}_t\rVert_{V^{\frac{\alpha}{m}}_t}\\
&\leq \lVert \theta^* - \bar{\theta}_t\rVert_{\bar{H}^{\alpha}_t(\theta^*, \bar{\theta}^{\text{OGD}}_t)} + L\sqrt{M}\lVert \bar{\theta}_t - \bar{\theta}^{\text{OGD}}_t\rVert\,.
\end{align*}
Therefore, on the good event, the OGD approximation of $\bar{\theta}_t$ induces an additional factor of at most
\[2L\sqrt{\frac{C\kappa m dh^2\sigma^2}{\epsilon_h t} \log\left(\frac{2dT}{h\delta}\right)\log\left(\frac{t}{h}\right)}\]
in the exploration bonus sequence compared to the factor $c^\delta_t$ used in LinUCB. Finally, we invoke a standard union bound argument to ensure both the good event and the regret bound hold with probability at least $1-2\delta$.
}
\subsection{Optimism and local metrics}\label{subsec:optimism_local_metrics}

We recall here the principle of optimism in the face of uncertainty and adapt it to the framework of elicitable risk measures. We denote by $r_t = \langle \theta^*, X^*_t\rangle - \langle \theta^*, X_t\rangle$ the instantaneous regret, where $\langle \theta^*, X^*_t\rangle = \max_{x\in\cX_t} \langle \theta^*, x\rangle$ is the optimal risk measure associated with $\cL$ at time for the actions available at time $t$. Then, simple algebra shows that
\begin{align*}
	r_t
	= \langle \theta^* - \bar{\theta}_t, X^*_t\rangle - \langle \theta^* - \bar{\theta}_t, X_t\rangle + \langle \bar{\theta}_t, X^*_t - X_t\rangle
	= \Delta(X^*_t, \bar{\theta}_t) + \Delta(X_t, \bar{\theta}_t) + \langle \bar{\theta}_t, X^*_t - X_t\rangle\,,
\end{align*}
where we define for $x\in\cX$ and $\theta\in\Theta$, $\Delta(x, \theta) = \lvert \langle \theta^*-\theta, x\rangle\rvert$ the absolute error made by $\theta$ with respect to the true parameter of the linear bandit $\theta^*$ in the direction of $x$. If we know a sequence of functions $\gamma_t\colon \cX\rightarrow \R_+$ such that with high probability, for all $t\in\N$ and $x\in\cX_t$, $\Delta(x, \bar{\theta}_t) \leq \gamma_t(x)$, then the principle of optimism recommends the action $X_t\in\argmax_{x\in\cX_t} \langle \bar{\theta}_t, x\rangle + \gamma_t(x)$, i.e the one leading to the best plausible reward with respect to the confidence on the prediction error of $\bar{\theta}_t$. In this case, $r_t\leq \Delta(X^*_t, \bar{\theta}_t) + \Delta(X_t, \bar{\theta}_t) + \gamma_t(X_t) - \gamma(X^*_t)\leq 2\gamma_t(X_t)$ with high probability, and hence $\cR_T \leq 2\sum_{t=1}^T \gamma_t(X_t)$. We detail below how Corollary~\ref{corr:conf} coupled with standard assumptions provides such a bound.

\paragraph{Bound on the prediction error}

We follow the standard strategy of decoupling the dependency on $\bar{\theta}_t$ and $x$ in $\Delta(x, \bar{\theta}_t)$. Indeed, we have by Cauchy-Schwarz's inequality that, for some positive definite matrix $P$ to be determined later,
\[\Delta(x, \bar{\theta}_t) = \lvert \langle \theta^* - \bar{\theta}_t, x\rangle\rvert = \lvert \langle P^{\frac{1}{2}}(\theta^*-\bar{\theta}_t), P^{-\frac{1}{2}}x\rangle\rvert \leq \lVert \theta^* - \bar{\theta}_t\rVert_{P} \lVert x \rVert_{P^{-1}}\,.\]
As we see below, a natural choice for $P$ is the (average) Hessian of the empirical risk minimization problem, and therefore the term $\lVert x \rVert_{P^{-1}}$ can be handled by the elliptical potential lemma (Lemma 11 in \citet{abbasi_yadkori2011}). To control the remainder term in $\theta^* - \bar{\theta}_t$, we borrow technical tools from the classical approach developed for generalized linear bandits \citep{filippi2010parametric, faury2020improved} and note that
\[F^{\alpha}_t(\theta^*) - F^{\alpha}_t(\bar{\theta}_t) = \bar{H}^{\alpha}_t(\theta^*, \bar{\theta}_t)(\theta^* - \bar{\theta}_t)\,,¸\]
where $\bar{H}^{\alpha}_t(\theta^*, \bar{\theta}_t) = \int_{0}^1 H^{\alpha}_t (u\theta^* + (1-u)\bar{\theta}_t)du$ is the average of the Hessian matrices along the segment $[\bar{\theta}_t, \theta^*]$ (this follows from the observation that the differential of $\nabla F^{\alpha}_t$ is  $H^{\alpha}_t$). Therefore the choice $P=\bar{H}^{\alpha}_t(\theta^*, \bar{\theta}_t)$ yields
\[\lVert \theta^* - \bar{\theta}_t\rVert_{P} = \lVert F^{\alpha}_t(\theta^*) - F^{\alpha}_t(\bar{\theta}_t)\rVert_{\bar{H}^{\alpha}_t(\theta^*, \bar{\theta}_t)^{-1}} \leq \lVert F^{\alpha}_t(\theta^*) - F^{\alpha}_t(\wh{\theta}_t)\rVert_{\bar{H}^{\alpha}_t(\theta^*, \bar{\theta}_t)^{-1}} + \lVert  F^{\alpha}_t(\bar{\theta}_t) - F^{\alpha}_t(\wh{\theta})\rVert_{\bar{H}^{\alpha}_t(\theta^*, \bar{\theta}_t)^{-1}}\,.\]
To conclude, we need to find a way to relate the local metric defined by $\bar{H}^{\alpha}_t(\theta^*, \bar{\theta}_t)^{-1}$ to those defined by $H^{\beta}_t(\theta^*)^{-1}$ and $H^{\beta}_t(\bar{\theta}_t)^{-1}$, for which we have high confidence bounds. This motivates the following assumption.

\begin{restatable}[Transportation of local metrics]{assumption}{assumptiontwo}\label{ass:2}
	For any $\alpha>0$, there exists $\kappa>0$ and $\beta>0$ such that
	\[\bar{H}^{\alpha}_t(\theta^*, \bar{\theta}_t) \succcurlyeq \frac{1}{\kappa} H^{\beta}_t(\theta^*) \quad \text{and}\quad \bar{H}^{\alpha}_t(\theta^*, \bar{\theta}_t) \succcurlyeq \frac{1}{\kappa} H^{\beta}_t(\bar{\theta}_t)\,.\]
\end{restatable}

In a special case of generalized linear bandit, namely the logistic bandit, it is shown in \citep{faury2020improved} that a similar assumption can be satisfied thanks to self-concordance properties of the link function. As detailed below, we will show that in our case it is sufficient to bound the extreme curvature of the loss function $\cL$.

\subsection{Regret analysis}

So far, we have kept the assumptions on supermartingale control (Assumption~\ref{ass:1}) and transportation of local metrics (Assumption~\ref{ass:2}) fairly general. The condition below is easy to check in practice and implies both.

\begin{restatable}[Bounded loss curvature]{assumption}{assumptionthree}\label{ass:3}
	There exists $m, M>0$ such that
	\[\forall y, \xi\in\R,\ m\leq \partial^2\cL(y, \xi)\leq M\,.\]
	We call the parameter $\kappa=\frac{M}{m}$ the \textit{conditioning} of the convex loss $\cL$.
\end{restatable}

We detail in Appendix~\ref{app:C} how this control implies Assumption~\ref{ass:2} for $\beta = \kappa\alpha$. It also implies that Assumption~\ref{ass:1} relaxes to a Lipschitz sub-Gaussian property as discussed in Section~\ref{subsec:martingale}.

\begin{remark} This assumption is reminiscent of the standard lower bound on the derivative of the link function $\mu'$ commonly encountered in the GLB literature. Moreover, although we formulate this bounded curvature assumption globally, we note that we only require it to hold in a convex neighborhood of $\theta^*$ containing $\bar{\theta}_t$, and Corollary~\ref{corr:conf} shows that with high probability, $\lVert \theta^* - \bar{\theta}_t \rVert_2$ is bounded (going from the $H^{\beta}_t(\theta^*)^{-1}$ norm to the Euclidean norm can be done by simple positive definite matrix inequalities). Therefore, one could instead assume a \textit{local} curvature control on $\partial\cL(y, \langle \theta, x\rangle)$ for $x\in\cX_t$ and $\theta$ in a ball around $\theta^*$, in the same spirit as Assumption~1 \citep{li2017provably} for GLB.
\end{remark}

In addition, we make two additional standard assumptions that prior bounds are known on $\theta^*$ and on the action set $\cX$, which is standard in the existing literature on linear bandits.

\begin{restatable}[Prior bound on parameters]{assumption}{assumptionfour}\label{ass:4} All parameters are in the Euclidean ball of radius $S$, i.e $\Theta \subseteq \cB_{\lVert \cdot \rVert_2}(0, S)$. In particular, this implies that $\lVert \theta^*\rVert_{H^{\beta}_t(\theta^*)^{-1}}\leq \frac{S}{\sqrt{\beta}}$ for any $\beta>0$.
\end{restatable}

\vspace*{-3mm}

\begin{restatable}[Prior bound on actions]{assumption}{assumptionfive}\label{ass:5} All actions are in the Euclidean ball of radius $L$, i.e $\cX \subseteq \cB_{\lVert \cdot \rVert_2}(0, L)$.
\end{restatable}

We now obtain a high probability upper bound on the regret incurred by Algorithm~\ref{algo::UCB_convex_risk} for an explicit choice of exploration bonus sequence $(\gamma_t)_{t\in\N}$ and projection $\Pi$.

\begin{restatable}[Regret of LinUCB for convex risk]{theorem}{theoremone}\label{thm:regret_ucb}
	Let $\delta\in(0, 1)$, $\alpha\geq \max(1, L^2)$ and define for $t\in\N$ the exploration bonus
	\begin{align*}
	&\gamma_t\colon x\in\cX_t \mapsto c^\delta_t \lVert x \rVert_{H^{\kappa \alpha}_t(\bar{\theta}_t)^{-1}} \text{\quad and \quad} c^\delta_t=2\kappa\left(\sigma\sqrt{2\log\frac{1}{\delta} + d\log\frac{m}{\alpha} + \log\det V^{\frac{\alpha}{m}}_t} + \sqrt{\frac{\alpha}{\kappa}}S\right)
	\end{align*}
	and the projection operator $\Pi\colon \wh{\theta}\in\R^d \mapsto \argmin_{\theta\in\Theta} \lVert F^{\alpha}_t(\theta) - F^{\alpha}_t(\wh{\theta})\rVert_{H^\beta_t(\theta)^{-1}}$.

	Under Assumptions~\ref{ass:1}, \ref{ass:3}, \ref{ass:4} and \ref{ass:5}, with probability at least $1-\delta$, the regret of Algorithm~\ref{algo::UCB_convex_risk} is bounded by
\[\cR_T \leq 2c^\delta_T \sqrt{\frac{2Td}{m}\log\left(\!1\!+\!\frac{T L ^2}{d\alpha}\right)}\,. \]
	In particular, we have $\cR_T = \cO\left(\frac{\kappa\sigma d}{\sqrt{m}}\sqrt{T}\log \frac{TL^2}{d}\right)$ when $T\rightarrow +\infty$.
\end{restatable}

The proof of this result follows the standard regret analysis of LinUCB, up to the modification detailled in the previous sections. We report the detailed arguments in Appendix~\ref{app:proof_linucb}.

\begin{remark}
	We note that the regret bound scales with the conditioning $\kappa$, a phenomenon already observed for generalized linear bandits in \citep{filippi2010parametric}. It was also conjectured in this work that the scaling could be reduced to $\sqrt{\kappa}$. In our proof, the extra $\sqrt{\kappa}$ is due to transportation of local metrics using the curvature bound of Assumption~\ref{ass:3}. In the special case of logistic bandits, this extra factor was removed by \citep{faury2020improved} using self-concordance of the sigmoid. In our case, a sharper assumption on the transportation of local metrics may improve the scaling similarly.
\end{remark}

\section{Proof of Proposition~\ref{prop:conf}}\label{app:proof_conf}

\assumptionone*

\proptwo*

\proof{The proof follows the method of mixture techniques, popularized in bandits by \cite{abbasi_yadkori2011}. For $\lambda\in\R^d$, we define the process $M^\lambda_t = \exp\left(\lambda^\top S_t -\frac{\sigma^2}{2}\lVert \lambda\rVert^2_{H^0_t(\theta^*)}\right)$. We recall the expression of the Hessian $H_t^0(\theta) = \sum_{s=1}^{t-1}\partial^2 \cL\left(Y_s, \langle \theta, X_s\rangle\right)X_sX_s^\top$ and that in particular $\lVert \lambda\rVert^2_{H^0_t(\theta^*)} = \sum_{s=1}^{t-1} \partial^2 \cL\left(Y_s, \langle \theta, X_s\rangle\right)\left(\lambda^\top X_s\right)^2$. This process is nonnegative and defines as supermartingale since
\begin{align*}
	\bE\left[ M^\lambda_{t+1}\middle|\cF_t\right] &= \bE\left[ \exp\left(\lambda^\top S_{t+1} -\frac{\sigma^2}{2}\lVert \lambda\rVert^2_{H^0_{t+1}(\theta^*)}\right) \middle|\cF_t\right]\\
	&=\bE\left[ \exp\left(\lambda^\top S_{t} -\frac{\sigma^2}{2}\lVert \lambda\rVert^2_{H^0_{t}(\theta^*)} + \partial\cL\left(Y_t, \langle\theta^*, X_t\rangle\right)\lambda^\top X_t - \frac{\sigma^2}{2}\partial^2\cL\left(Y_t, \langle\theta^*, X_t\rangle\right)\left(\lambda^\top X_t\right)^2 \right) \middle|\cF_t\right]\\
	&= \exp\left(\lambda^\top S_{t} -\frac{\sigma^2}{2}\lVert \lambda\rVert^2_{H^0_{t}(\theta^*)}\right) \bE\left[ \exp\left(\partial\cL\left(Y_t, \langle\theta^*, X_t\rangle\right)\lambda^\top X_t - \frac{\sigma^2}{2}\partial^2\cL\left(Y_t, \langle\theta^*, X_t\rangle\right)\left(\lambda^\top X_t\right)^2 \right) \middle|\cF_t\right]\\
	&\leq \exp\left(\lambda^\top S_{t} -\frac{\sigma^2}{2}\lVert \lambda\rVert^2_{H^0_{t}(\theta^*)}\right) \quad\text{(Assumption~\ref{ass:1})}\\
	&= M^{\lambda}_t\,.
\end{align*}

Now we construct a new supermartingale by mixing all the $M^\lambda$. More formally, let $\Lambda$ a $\R^d$-valued random variable independent of the rest and define $M_t=\bE\left[M^\Lambda_t \middle| \cF_{\infty}\right]$ where $\cF_{\infty} = \sigma\left(\bigcup\limits_{t\in\N}\cF_t\right)$. If $\Lambda$ has density $p$ with respect to the Lebesgue measure, this means that $M_t = \int_{\R^d} M^\lambda_t p(\lambda)d\lambda$. For the choice $\Lambda\sim \cN(0, \frac{1}{\beta\sigma^2}I_d)$ with $\beta>0$, we have, by completing the square in the exponential:
\begin{align*}
	M_t &= \frac{(\beta\sigma^2)^{d/2}}{(2\pi)^{d/2}}\int_{\R^d} \exp\left(-\lambda^\top S_t +\frac{\sigma^2}{2}\left(\lambda^\top\left(H^0_t(\theta^*) + \beta I_d\right)\lambda\right)\right)d\lambda\\
	&= \frac{(\beta\sigma^2)^{d/2}}{(2\pi)^{d/2}} \exp\left(\frac{\sigma^2}{2}\bar{\lambda}^\top H^\beta_t(\theta^*) \bar{\lambda}\right) \int_{\R^d} \exp\left(-\frac{\sigma^2}{2}\left(\lambda-\bar{\lambda}\right)^\top H^\beta_t(\theta^*) \left(\lambda-\bar{\lambda}\right)\right)d\lambda\\
	&= \left(\frac{\beta^d}{\det H_t^\beta(\theta^*)}\right)^{\frac{1}{2}} \exp\left(\frac{\sigma^2}{2}\bar{\lambda}^\top H^\beta_t(\theta^*) \bar{\lambda}\right)\,,
\end{align*}
where $\bar{\lambda} = \frac{1}{\sigma^2}H^\beta_t(\theta^*)^{-1}S_t$ and $H^\beta_t(\theta) = H^0_t(\theta) + \beta I_d$ is the regularized Hessian, which is positive definite and hence invertible. This expression further simplifies to $M_t=\left(\frac{\det \beta I_d}{\det H_t^\beta(\theta^*)}\right)^{\frac{1}{2}} \exp\left(\frac{1}{2\sigma^2}\lVert S_t \rVert^2_{H^\beta_t(\theta^*)^{-1}}\right)$.

From there, the argument is standard: $M^\lambda$ is a nonnegative supermartingale, and therefore the pointwise limit $M^\lambda_{\infty} = \lim_{t\rightarrow+\infty}M^\lambda_t$ exists almost surely (Doob's supermartingale convergence theorem, Chapter 11 in \citep{williams1991probability}). Therefore for any $\cF$-stopping time $\tau$, $M^\lambda_\tau$ is well-defined, and thus so is and $M_\tau $. By Fatou's lemma and Doob's stopping theorem, we have that $\bE[M_\tau]= \bE[\liminf_{t\rightarrow+\infty}\bE[M_{t\wedge\tau}\mid\cF_{\infty}]]\leq \liminf_{t\rightarrow+\infty}\bE[\bE[M_{t\wedge\tau}\mid\cF_{\infty}]]\leq 1$. Finally, the particular choice of $\tau=\inf\left\lbrace t\in\N,\ \lVert S_t \rVert^2_{H^\beta_t(\theta^*)^{-1}} \geq \sigma^2\left( 2\log\frac{1}{\delta} + \log \frac{\det \beta I_d}{\det H_t^\beta(\theta^*)}\right) \right\rbrace$ and a straightforward application of Markov's inequality reveals that
\[\bP\left(\tau < \infty\right) = \bP\left(\exists t\in\N,\ M_\tau \geq \frac{1}{\delta}\right)\leq \bE[M_\tau]\delta \leq \delta \,,\]
which is exactly the expected result.
$\hfill\blacksquare$
}

\section{Assumption~\ref{ass:3} $\implies$ Assumption~\ref{ass:2}}\label{app:C}

First, we recall the two assumptions of interest.

\assumptiontwo*

\assumptionthree*

Now simple calculations show that:

\begin{align*}\bar{H}^{\alpha}_t(\theta^*, \bar{\theta}_t) &= \sum_{s=1}^{t-1}\int_{0}^1 \partial^{2}\cL(Y_s, \langle u\theta^* + (1-u)\bar{\theta}_t, X_s\rangle)du X_s X_s^\top + \alpha I_d \\
&= \sum_{s=1}^{t-1}\int_{0}^1 \partial^{2}\cL(Y_s, \langle \theta^*, X_s\rangle)\frac{\partial^{2}\cL(Y_s, \langle u\theta^* + (1-u)\bar{\theta}_t, X_s\rangle)}{\partial^{2}\cL(Y_s, \langle \theta^*, X_s\rangle)}du X_s X_s^\top + \alpha I_d\\
&\succcurlyeq \frac{m}{M} \sum_{s=1}^{t-1} \partial^{2}\cL(Y_s, \langle \theta^*, X_s\rangle)X_s X_s^\top + \alpha I_d\\
&= \frac{1}{\kappa}\left(\sum_{s=1}^{t-1} \partial^{2}\cL(Y_s, \langle \theta^*, X_s\rangle)X_s X_s^\top + \kappa\alpha I_d\right)\\
&= \frac{1}{\kappa}H^{\kappa \alpha}_t(\theta^*)\,,
\end{align*}
which is the desired result if $\beta=\kappa\alpha$. The other inequality with $\bar{H}^{\beta}_t(\bar{\theta}_t)$ is derived similarly.

\section{Proof of Theorem~\ref{thm:regret_ucb}}\label{app:proof_linucb}

In this section, we prove the main regret theorem for LinUCB with convex risk, which we restate below.

\theoremone*

\proof{We will prove the regret bound in two steps. First, we justify the choice of exploration sequence $(\gamma_t)_{t\in\N}$, which naturally derives from the optimistic principle and the analysis of local metrics. Then, we use a somewhat crude bound on the Hessian to simplify the analysis and reduce it to the so-called elliptic potential lemma.

Indeed, as established in Section~\ref{subsec:optimism_local_metrics}, the cumulative regret up to time $T$, denoted by $\cR_T$, is upper bounded with probability at least $1-\delta$ by $2\sum_{t=1}^T \gamma_t(X_t)$ provided that $\bP\left(\forall t\leq T,\ \Delta(X_t, \bar{\theta}_t) \leq \gamma_t(X_t) \right) \geq 1 - \delta$, where \[\Delta(X_t, \theta) = \lvert \langle \theta^*-\theta, X_t\rangle\rvert \leq \lVert \theta^* - \bar{\theta}_t\rVert_{\bar{H}^{\alpha}_t(\theta^*, \bar{\theta}_t)} \lVert X_t \rVert_{\bar{H}^{\alpha}_t(\theta^*, \bar{\theta}_t)^{-1}}\,.\]

\paragraph{Tuning of the exploration bonus sequence}
The transportation of local metrics (Assumption~\ref{ass:2}, implied by the curvature bound of Assumption~\ref{ass:3}) reveals that
\begin{align*}
\lVert \theta^* - \bar{\theta}_t\rVert_{\bar{H}^{\alpha}_t(\theta^*, \bar{\theta}_t)} &\leq \lVert F^{\alpha}_t(\theta^*) - F^{\alpha}_t(\wh{\theta}_t)\rVert_{\bar{H}^{\alpha}_t(\theta^*, \bar{\theta}_t)^{-1}} + \lVert  F^{\alpha}_t(\bar{\theta}_t) - F^{\alpha}_t(\wh{\theta})\rVert_{\bar{H}^{\alpha}_t(\theta^*, \bar{\theta}_t)^{-1}}\\
&\leq \sqrt{\kappa}\left(\lVert F^{\alpha}_t(\theta^*) - F^{\alpha}_t(\wh{\theta}_t)\rVert_{H^{\beta}_t(\theta^*)^{-1}} + \lVert  F^{\alpha}_t(\bar{\theta}_t) - F^{\alpha}_t(\wh{\theta})\rVert_{\bar{H}^{\beta}_t(\bar{\theta}_t)^{-1}}\right)\,.
\end{align*}

Thanks to the supermartingale control of Assumption~\ref{ass:1}, we deduce from Corollary~\ref{corr:conf} that with probability at least $1-\delta$, the following inequalities hold for all $t\leq T$:
\begin{align*}
&\lVert F^{\alpha}_t(\theta^*) - F^{\alpha}_t(\wh{\theta}_t)\rVert_{H^{\beta}_t(\theta^*)^{-1}} \leq \sigma\sqrt{2\log\frac{1}{\delta} + \log\frac{\det H^\beta_t(\theta^*)}{\det \beta I_d}} + \alpha\lVert \theta^*\rVert_{H^\beta_t(\theta^*)^{-1}}\,,\\
&\lVert F^{\alpha}_t(\bar{\theta}_t) - F^{\alpha}_t(\wh{\theta}_t)\rVert_{H^{\beta}_t(\bar{\theta}_t)^{-1}} \leq \sigma\sqrt{2\log\frac{1}{\delta} + \log\frac{\det H^\beta_t(\bar{\theta}_t)}{\det \beta I_d}} + \alpha\lVert \bar{\theta}_t\rVert_{H^\beta_t(\bar{\theta}_t)^{-1}}\,.
\end{align*}
The prior bound on parameters (Assumption~\ref{ass:4}) yields $\lVert \theta\rVert_{H^{\beta}_t(\theta)^{-1}}\leq \frac{S}{\sqrt{\beta}}$ for $\theta\in\lbrace \theta^*, \bar{\theta}_t\rbrace$. Furthermore, the curvature bound (Assumption~\ref{ass:3}) implies that $H^{\beta}_t(\theta) \preccurlyeq M V^{\beta/M}_t$, and therefore $\det H^{\beta}_t(\theta) \leq M^d \det V^{\beta/M}_t$ for $\theta\in\lbrace \theta^*, \bar{\theta}_t\rbrace$. Combining this together and substituting the expression of $\beta=\kappa \alpha$, where $\kappa=\frac{M}{m}$ the conditioning of the convex loss $\cL$, we obtain:
\begin{align*}
\lVert \theta^* - \bar{\theta}_t\rVert_{\bar{H}^{\alpha}_t(\theta^*, \bar{\theta}_t)} &\leq 2\sqrt{\kappa}\left(\sigma\sqrt{2\log\frac{1}{\delta} + d\log\frac{m}{\alpha} + \log\det V^{\frac{\alpha}{m}}_t} + \sqrt{\frac{\alpha}{\kappa}}S\right)\,.
\end{align*}

Finally, the same arguments show that $\bar{H}^{\alpha}_t(\theta^*, \bar{\theta}_t)^{-1}\preccurlyeq \kappa H^{\kappa\alpha}_t(\bar{\theta}_t)^{-1}$, therefore $\lVert X_t \rVert_{\bar{H}^{\alpha}_t(\theta^*, \bar{\theta}_t)^{-1}} \leq \sqrt{\kappa} \lVert X_t \rVert_{H^{\kappa\alpha}_t(\bar{\theta}_t)^{-1}}$. This shows that
\[\gamma_t(X_t) \coloneqq \underbrace{2\kappa\left(\sigma\sqrt{2\log\frac{1}{\delta} + d\log\frac{m}{\alpha} + \log\det V^{\frac{\alpha}{m}}_t} + \sqrt{\frac{\alpha}{\kappa}}S\right)}_{\eqqcolon\ c^\delta_t} \lVert X_t \rVert_{H^{\kappa\alpha}_t(\bar{\theta}_t)^{-1}}\]
is a valid choice of exploration sequence.

\paragraph{Bounding the regret} Going back to the cumulative regret $\cR_T$, we notice that $(c^\delta_t)_{t=1,\dots, T}$ is a positive, nondecreasing sequence, therefore we have with probability at least $1-\delta$ that
\begin{align*}
	\cR_T \leq 2\sum_{t=1}^T \gamma_t(X_t) \leq 2 c^\delta_T \sum_{t=1}^T \lVert X_t \rVert_{H^{\kappa\alpha}_t(\bar{\theta}_t)^{-1}}\,.
\end{align*}
A priori, the direct analysis of the right-hand side is tedious due to the dependency on $\bar{\theta}_t$ in the local metric. However, we notice that the curvature bound (Assumption~\ref{ass:3}) also implies the weaker control $H^{\kappa\alpha}_t(\bar{\theta}_t)^{-1} \preccurlyeq \frac{1}{m} (V^{\frac{\kappa \alpha}{m}}_t)^{-1}$, which translates to $\lVert X_t \rVert_{H^{\kappa\alpha}_t(\bar{\theta}_t)^{-1}} \leq \frac{1}{\sqrt{m}} \lVert X_t \rVert_{(V^{\frac{\kappa \alpha}{m}}_t)^{-1}}$. This bound is less informative as it looses the local information carried by $\bar{\theta}_t$, but still sufficient to obtain sublinear regret growth. We recall the following result, which is a direct consequence of the deterministic elliptic potential lemma (Lemma~11, \citet{abbasi_yadkori2011}) and the Cauchy-Schwarz inequality.

\begin{lemma}\label{lemma:elliptical_potential_revisited}
Let $(x_t)_{t\in\N}$ denote an arbitrary sequence of vectors in Euclident ball of $\R^d$ with radius $L$, $\alpha \geq \max(1, L^2)$ and $v_{t} = \sum_{s=1}^{t-1} x_s x_s^\top + \alpha I_d \in \R^{d\times d}$ for $t\in \N$. Then
\[\sum_{s=1}^t \lVert x_s \rVert_{v^{-1}_s} \leq \sqrt{2td\log\left(\!1\!+\!\frac{t L ^2}{d\alpha}\right)}\,.\]
\end{lemma}

Note that this result holds in our case thanks to the prior bound on actions (Assumption~\ref{ass:5}).

\paragraph{Conclusion} With high probability, the regret of LinUCB with convex risk is bounded by
\begin{align*}
\cR_T \leq 2\sum_{t=1}^T \gamma_t(X_t) \leq 2c^\delta_T \sqrt{\frac{2Td}{m}\log\left(\!1\!+\!\frac{T L ^2}{d\alpha}\right)}\,.
\end{align*}
Going back to the expression of $c^\delta_T$, it follows from simple algebra (see e.g proof of Lemma 19.4, \citet{lattimore2020bandit}) that $\det V^\frac{\alpha}{m}_t \leq \left(\frac{\alpha}{m} + \frac{TL^2}{d}\right)^d$, and thus $c^\delta_T=\cO\left(\kappa\sigma \sqrt{d\log \frac{T L^2}{d}}\right)$ when $T\rightarrow +\infty$. A simpler asymptotic bound on the regret is therefore
\[\cR_T = \cO\left(\frac{\kappa\sigma d}{\sqrt{m}}\sqrt{T} \log \frac{T L^2}{d}\right)\,.\]
$\hfill\blacksquare$
}
\section{Experiments}

We conducted three numerical experiments to illustrate the performance of the two risk-aware algorithms, which are reported in Figure~\ref{fig:xp_expectile}. In the first two, we considered arms with respectively Gaussian and expectile-based asymmetric distributions \citep{torossian2020bayesian} with context-dependent expectiles. In the last one, we considered Bernoulli-like arms under the entropic risk criterion. These settings were designed so that the optimal arms were different when considering the mean or the corresponding risk-aware criterion. Instances of the classical LinUCB algorithm \citep{abbasi_yadkori2011} were indeed deceived and accumulated linear risk-aware regret, while Algorithms~\ref{algo::UCB_convex_risk} and \ref{algo::UCB-OGD_convex_risk} exhibit milder sublinear trends. Compared to LinUCB with the exact minimization of the empirical risk, the LinUCB-OGD variant accumulated slightly more regret and showed higher variability across independent replications, at the benefit of an improved runtime. Further details of the experiments are reported in Appendix~\ref{app:xp}.

\begin{figure}
	\centering
	\begin{subfigure}[b]{0.33\textwidth}
		\centering		\includegraphics[width=0.99\textwidth]{expectile_ucb.pdf}
	\end{subfigure}
	\begin{subfigure}[b]{0.33\textwidth}
		\centering
		\includegraphics[width=0.99\textwidth]{expectile_linucb.pdf}
	\end{subfigure}
	\begin{subfigure}[b]{0.33\textwidth}
		\centering
		\includegraphics[width=0.99\textwidth]{entropic_ucb.pdf}
	\end{subfigure}
	\caption{Left: two-armed Gaussian expectile bandit. Center: two-armed linear expectile bandit with $\bR^3$ contexts and expectile-based asymmetric noises. Right: two-armed Bernoulli entropic risk bandit. Thick lines denote median cumulative regret over 500 independent replications. Dotted lines denote the 25 and 75 regret percentiles. Shaded areas denote the 5 and 95 percentiles.}
	\label{fig:xp_expectile}
\end{figure}

\section{Intro}

Contextual bandits are sequential decision-making models where at each time step an agent observes a set of possible actions, or contexts, plays one of them and receives a stochastic reward, the distribution of which is a function of the selected action. The goal of the agent is to learn an action policy in order to maximize the sum of rewards, facing the classical exploitation-exploration dilemma. A prominent example of such models is the linear bandit, which assumes a linear relationship between the action and the \textit{mean} of the reward distribution. In this setting, a standard learning strategy consists in estimating the linear reward model by ridge regression coupled with an appropriate exploration scheme, such as the optimistic LinUCB \citep{abbasi_yadkori2011}, Thompson sampling \citep{agrawal2013thompson, abeille2017linear} or information-directed sampling \citep{russo2014learning, kirschner2021asymptotically}.

One limitation of this setting is that real-world agents may have a preference for other reward criterion than the mean. Indeed, while mathematically convenient, the mean is known to equally weights large positive and negative outcomes, which may lead to risky policies unsuitable to critical applications, and is also sensitive to outliers. In contrast, \textit{risk-aware} measures emphasize different characteristics of the reward distribution, e.g by stressing out the impact of adverse outcomes \citep{dowd2007measuring}. Such measures include the mean-variance \citep{markowitz1952march}, conditional Value-at-Risk \citep{rockafellar2000optimization}, entropic risk \citep{maillard2013robust} and the expectiles \citep{newey1987asymmetric}. These risk measures, and in particular the conditional Value-at-Risk (CVaR), have been studied as alternatives to the mean criterion in classical multi-armed bandits, that is without contextual information
\citep{galichet2013exploration, cassel2018general, tamkin2019distributionally, prashanth2020concentration, baudry2021optimal}. In distributional reinforcement learning, quantile regression has been studied for DQN \citep{dabney2017distributional}. Recently, bandits with contextual mean-variance and CVaR have been applied to vehicular communication \cite{wirth2022risk}. Despite promising empirical results, these contributions are largely devoid of theoretical regret guarantees.

In this work, we investigate an extension of the linear bandit where a given risk measure, rather than the mean, is linearly parametrized by the chosen actions. Specifically, we consider the case of convex risk measures which can be elicited as minimizers of certain loss functions, which naturally extends the standard ridge regression. This definiton covers quantiles, expectiles and entropic risk, and can be extended to mean-variance and conditional value-at-risk using multivariate risk measures. To the best of our knowledge, this setting is new, although related to existing approaches, in particular bandits with regression oracles \citep{foster2020beyond}, which contrary to the present work considers finite action sets, and generalized linear bandits (GLB) \citep{filippi2010parametric, li2017provably, faury2020improved}.

In contrast with the standard mean-linear bandit, learning the linear mapping between actions and risk measures cannot be performed sequentially and presents similar theoretical challenges to GLB. We introduce a variant of LinUCB designed to maximize the risk measure of rewards, with sublinear regret guarantees. To do so, we derive time-uniform confidence sets based on the method of mixtures \citep{delapena_self_normalized} and introduce a condition on the curvature of the convex loss. To mitigate the numerical burden of this algorithm, which requires to solve a convex minimization problem at each time step, we also introduce an episodic version with online gradient descent (OGD) approximation, directly inspired by the recent literature on approximate Thompson sampling for GLB \citep{ding2021efficient}.

\section{Conclusion}
We have introduced a new setting for contextual bandits, building on the recent interest for risk-awareness in multi-armed bandits. We reviewed the literature on risk measures, in particular the notion of elicitability, that allows to extend the risk minimization framework of ridge regression beyond standard mean-linear bandits. We detailed a set of generic assumptions to lift the regret analysis of optimistic algorithms in the setting of scalar risk measures $\rho_{\cL}$ elicited by a convex loss $\cL$, and showed that uniformly bounding the curvature of the loss is sufficient to maintain similar theoretical guarantees ($\cO(\sqrt{T})$ worst-case regret, up to polylog terms). Going further, we believe it would be interesting to extend the linear model between actions and risk measures to generalized linear models ($\rho_{\cL}(Y_t) = \mu(\langle \theta, X_t\rangle)$ for some link function $\mu\colon \R\rightarrow \R$), kernelized bandits ($\rho_{\cL}(Y_t) = f(X_t)$ where $f$ belongs to some RKHS) or neural bandits ($\rho_{\cL}(Y_t) = f_{\theta}(X_t)$ where $f_{\theta}$ is a neural network with weights $\theta$). Moreover, capturing well-established risk measures such as mean-variance and conditional value-at-risk would require to develop the theory of high-order elicitable measures. Finally, we believe an extended empirical study would be valuable, e.g by testing the proposed algorithms on real-world data collected by risk-averse agents.

\newpage

\acks{The authors acknowledge the funding of the French National Research Agency, the French Ministry of Higher Education and Research, Inria, the MEL and the I-Site ULNE regarding project R-PILOTE-19-004-APPRENF and Bandits For Health (B4H). We thank the anonymous reviewers for their careful reading of the paper and their suggestions for improvements. Experiments presented in this paper were carried out using the Grid’5000 testbed, supported by a scientific interest group hosted by
	Inria and including CNRS, RENATER and several Universities as well as other organizations (see https://www.grid5000.fr).
}

\vskip 0.2in

\bibliographystyle{abbrvnat}

\subsubsection*{\bibname}}

\begin{document}

\onecolumn
\aistatstitle{Instructions for Paper Submissions to AISTATS 2021: \\
Supplementary Materials}

\section{FORMATTING INSTRUCTIONS}

To prepare a supplementary pdf file, we ask the authors to use \texttt{aistats2021.sty} as a style file and to follow the same formatting instructions as in the main paper.
The only difference is that the supplementary material must be in a \emph{single-column} format.
You can use \texttt{supplement.tex} in our starter pack as a starting point, or append the supplementary content to the main paper and split the final PDF into two separate files.

Note that reviewers are under no obligation to examine your supplementary material.

\section{MISSING PROOFS}

The supplementary materials may contain detailed proofs of the results that are missing in the main paper.

\subsection{Proof of Lemma 3}

\textit{In this section, we present the detailed proof of Lemma 3 and then [ ... ]}

\section{ADDITIONAL EXPERIMENTS}

If you have additional experimental results, you may include them in the supplementary materials.

\subsection{The Effect of Regularization Parameter}

\textit{Our algorithm depends on the regularization parameter $\lambda$. Figure 1 below illustrates the effect of this parameter on the performance of our algorithm. As we can see, [ ... ]}

\vfill

\end{document}

\section{Experiments}\label{app:xp}

We report three simple experiments, two in the expectile setting and one in the entropic risk setting.

\paragraph{Computing expectiles} We detail two cases of distributions for which expectiles are known. For $p\in(0, 1)$, we denote by $e_p(\nu)$ the $p$-expectile of distribution $\nu$.
\begin{itemize}
	\item If $\nu=\cN\left(0, 1\right)$, then, letting $\phi$ and $\Phi$ be the pdf and cdf of $\nu$ respectively, we obtain after simple calculus and the identity $\phi'(y) = -y\phi(y)$ the following fixed point equation:
	\[e_p(\nu) = \frac{2p\phi(e_p(\nu)) - 1}{(1-2p)\Phi(e_p(\nu)) + p}\,,\]
	from which one can estimate the value of $e_p(\nu)$ using a fast iterative scheme. The general Gaussian case $\nu=\cN\left(\mu, \sigma^2\right)$ is then easily deduced from the relation $e_p(\nu) = \mu + \sigma e_p(\cN\left(0, 1\right))$. Expectile calculations for a few other classical distributions are covered in \citet{philipps2022interpreting}.
	\item If $\nu$ is the so-called expectile based distribution \citep{torossian2020bayesian, arbel2021multivariate} with asymmetric density (with respect to the Lebesgue measure) given by
	\[f_{\mu, \sigma, p}(y) = \frac{\sqrt{2p(1-p)}}{\sigma\sqrt{\pi}(\sqrt{p} + \sqrt{1-p})} \exp\left(-\frac{\lvert p - \ind_{y<\mu}\rvert (y-\mu)^2}{2\sigma^2}\right)\,,\]
	then $e_p(\nu) = \mu$. In other words, these distributions offer a family parametrized directly by their expectile, generalizing the family of Gaussian distributions parametrized by their mean (for a given variance).
\end{itemize}

We recall that the $p$-expectile can be elicited by the convex potential $\psi(z) = \lvert p-\ind_{z<0}\rvert z^2$. The second derivative of this potential is given by $\psi''(z) = (1-p)\ind_{z<0} + p\ind_{z>0}$, which is bounded between $p$ and $1-p$. In particular, Assumption~\ref{ass:3} holds with conditioning $\kappa=\frac{M}{m}=\frac{1-p}{p}$ if $p\leq\frac{1}{2}$ and $\kappa=\frac{M}{m}=\frac{p}{1-p}$ otherwise. Note that the two classes of distributions considered above are Gaussian or simple, log-concave transforms of Gaussian distributions, which fits the scope of the supermartingale control of Assumption~\ref{ass:1}.

\paragraph{Computing entropic risk} For a distribution $\nu$, the entropic risk at level $\gamma>0$ takes the form $\rho_{\gamma}(\nu) = \frac{1}{\gamma}\!\log \bE_{Y\sim\nu}\!\left[e^{\gamma Y}\right]$ and corresponds to the loss $\cL\colon (y, \xi)\mapsto \xi + \frac{1}{\gamma}(e^{\gamma(y-\xi)}-1)$. Derivatives of this loss satisfy the following identities, where $\partial$ represents the differentiation operator with respect to the second coordinate $\xi$:
\begin{align*}
\partial \cL(y, \xi) &= 1 - e^{\gamma(y-\xi)},\\
\partial^2 \cL(y, \xi) &= \gamma e^{\gamma(y-\xi)},
\end{align*}
and is thus in particular strictly convex.

For a Bernoulli-like distribution $\nu = p\delta_a + (1-p)\delta_b$, with $p\in(0, 1)$, $a, b\in \R$, the entropic risk takes the simple form $\rho_{\gamma}(\nu) = \frac{1}{\gamma}\log\left(p e^{\gamma a} + (1 - p)e^{\gamma b}\right)$. If $\nu$ has a bounded support with diameter $\cD$, then it is clear that the Hessian of the loss is controlled by $m=\gamma e^{-\gamma \cD}\leq \partial^2 \cL \leq \gamma e^{\gamma \cD}=M$, and therefore the conditioning number of the loss $\kappa$ can be bounded by $e^{2\gamma \cD}$. Finally, $\nu$ being bounded also fits the scope of the supermartingale control of Assumption~\ref{ass:1}.

\paragraph{General case} If a density $p$ and a loss function $\cL$ are known, one may resort to numerical integration to approximate the following quantity up to arbitrary precision:
\[\bE_{Y\sim\nu}\left[ \cL(Y, \xi) \right] = \int \cL(y, \xi)p(y)dy \approx \sum_{i} w_i \cL(y_i, \xi)p(y_i),\]
where the weights $(w_i)$ and knots $(y_i)$ depend on the approximation routine. Then, one may simply run a minimization algorithm on the function $\xi\mapsto \sum_i w_i \cL(y_i, \xi)p(y_i)$ to estimate $\rho_{\cL}(\nu)$.

\paragraph{Experiment 1: multi-armed Gaussian bandit with expectile noise}
We considered $K=2$ Gaussian arms with expectiles at level $p=10\%$ equal to $1$ and $0$ respectively. This bandit can be represented by constant orthonormal actions $\cX_t = \lbrace [1\ 0]^\top,\ [0\ 1]^\top\rbrace$, parameter $\theta^* = [1\ 0]^\top$ and noise distributions $\cN\left(\mu_k, \sigma_k^2\right)$, with $\mu_k$ and $\sigma_k$ chosen such that the expectile of the corresponding noise is zero for $k\in\left\{1, 2\right\}$. This can be achieved with e.g. $\mu_1\approx 0.44$, $\sigma_1=0.5$ and $\mu_2\approx 2.62$, $\sigma_2=3$, which was the setup for this experiment. Note that for a given expectile level $p\in(0, 1)$ and standard deviation $\sigma$, finding the unique mean $\mu$ such that $\cN\left(\mu, \sigma^2\right)$ has zero $p$-expectile can be easily done via a numerical root search, using the formula for Gaussian expectiles described above.

The optimal arm with respect to the expectile criterion is the first one by definition. However, the expectations of these arms are in reversed order, making the second one optimal with respect to the mean criterion.

\paragraph{Experiment 2: linear bandit with expectile asymmetric noise}

We considered a second example with non-Gaussian noise and non-orthogonal features. We defined the action set at time $t$ by $\cX_t = \lbrace X^1_t, X^2_t\rbrace\subset \R^3$ where:
\begin{itemize}
	\item $X^1_t=\frac{Z^1_t}{\lVert Z^1_t\rVert}$ with $Z^1_t\sim\cN([1\ 0\ 0]^\top, \sigma_x I_3)$,
	\item $X^2_t=\frac{Z^2_t}{\lVert Z^2_t\rVert}$ with $Z^1_t\sim\cN([0\ 1\ 0]^\top, \sigma_x I_3)$,
	\item We set the action noise to an arbitrary value $\sigma_x=0.1$.
	\item $(Z^1_t, Z^2_t)_{t\in\N}$ are all independent random variables.
\end{itemize}

This construction results in bounded, anisotropic actions. We chose $\theta^* = [0.9\ 0\ 1]^\top$, so that $\langle \theta^*, X^1_t\rangle$ is likely higher than $\langle \theta^*, X^2_t\rangle$, thus favoring $X_t = X^1_t$ in the expectile model $Y_t = \langle \theta^*, X_t\rangle + \eta_t$. To model the zero $p$-expectile noise $\eta_t$ with $q=10\%$, we used the expectile based distribution presented above with $\mu_1=\mu_2=0$ and $\sigma_1=0.5$ if action $X^1_t$ is played, and $\sigma_2=1.5$ otherwise, resulting in different mean noise $\bE[\eta_t\lvert \cF_t] \approx 1.8$ and $\bE[\eta_t\lvert \cF_t] \approx 3.3$ respectively. As in the previous example, this setting was designed to deceive the mean criterion by inverting the order of optimal actions.

\paragraph{Experiment 3: multi-armed Bernoulli bandit with entropic risk noise}

The last experiment consisted of $K=2$ Bernoulli-like arms $\nu_1=\frac{1}{2}\delta_{1} + \frac{1}{2}\delta_{-1}$ and $\nu_2=\frac{1}{4}\delta_{2} + \frac{3}{4}\delta_{-2}$, which corresponds to means $\mu_1=0$, $\mu_2=-1$ and entropic risk $\rho_\gamma(\nu_1)\approx 0.43$ and $\rho_\gamma(\nu_2)\approx 0.67$ at level $\gamma=1$. Again, this setting was designed so that the best optimal arm is different under the mean and entropic risk criteria.

\paragraph{Results}
On each of the three settings, we ran an instance of Algorithm~\ref{algo::UCB_convex_risk}, i.e. LinUCB (convex risk), and Algorithm~\ref{algo::UCB-OGD_convex_risk}, i.e. LincUCB-OGD (convex risk). We also ran a standard LinUCB algorithm for the mean criterion \citep{abbasi_yadkori2011}. Hyperparameters $m, M$ and $\kappa$ were tuned according to the analysis above. Regularization was fixed at $\lambda=0.1$. As is customary in bandit experiments, the parameter $\sigma$, which in the formal analysis is derived from the supermartingale control of the noise, was considered a degree of freedom to control the amount of exploration; we arbitrarily fixed it at $\sigma=0.1$ in experiments 1 and 2 and at $\sigma=1$ in experiment 3. For the LinUCB-OGD variant, the step size for the OGD scheme was set to $\epsilon_n = 0.1/n$, following the linear decay suggested by Proposition~\ref{prop:ogd}, and the frequency of OGD update to $h=5$. In addition, all algorithms went through an initial warmup phase where each arm was played $5$ times, in order to ensure better stability of the initial estimations of $\theta$.

In all three examples, the mean criterion algorithm was deceived and accumulated linear expectile and entropic risk regret, while both risk-aware algorithms exhibited sublinear trends. Interestingly, the LinUCB-OGD variant showed higher regrets due to the approximate minimization of the loss criterion by OGD, but remained below the mean criterion LinUCB benchmark. Figure~\ref{fig:xp_expectile2} reproduces the results of each experiments across 500 independent replications. Finally, average runtimes for each algorithm are reported in Table~\ref{table:runtime1}. Calculations were performed on a distributed infrastructure comprised of 80 CPUs. While the values themselves are not indicative, as they would vary on a different system, their relative magnitudes illustrate the computational gain of the OGD scheme over solving the empirical risk minimization problem at each step as required in LinUCB (convex risk). Note also that the standard LinUCB with mean criterion is faster due to the sequential nature of the ridge regression estimator. Indeed, this procedure involves inverting at each step a $d\times d$ matrix subject to rank one updates, which can be calculated efficiently via the Sherman-Morrison formula. By contrast, other convex losses than the one derived from the quadratic potential loose this sequential form and require solving the corresponding regression problem from scratch at each time step.

\begin{figure}
	\centering
	\begin{subfigure}[b]{0.49\textwidth}
		\centering
		\includegraphics[height=0.4\textheight]{expectile_ucb.pdf}
	\end{subfigure}
	\begin{subfigure}[b]{0.49\textwidth}
		\centering
		\includegraphics[height=0.4\textheight]{expectile_linucb.pdf}
	\end{subfigure}\\
	\begin{subfigure}[b]{0.49\textwidth}
		\centering
		\includegraphics[height=0.4\textheight]{entropic_ucb.pdf}
	\end{subfigure}
	\caption{Left: two-armed Gaussian expectile bandit. Center: two-armed linear expectile bandit with $\bR^3$ contexts and expectile-based asymmetric noises. Right: two-armed Bernoulli entropic risk bandit. Thick lines denote median cumulative regret over 500 independent replications. Dotted lines denote the 25 and 75 regret percentiles. Shaded areas denote the 5 and 95 percentiles.}
	\label{fig:xp_expectile2}
\end{figure}

\begin{small}
	\begin{table}[!ht]
		\caption{Runtimes for the classical LinUCB and Algorithms~\ref{algo::UCB_convex_risk} (LinUCB for convex risk) and \ref{algo::UCB-OGD_convex_risk} (LinUCB-OGD for convex risk) in each experiments. Runtimes are reported in seconds as mean $\pm$ standard deviation, estimated across 500 independent replications with time horizon $T=1500$.}
		\label{table:runtime1}
		\centering
		\begin{tabular}{llll}
			\toprule
			Algorithm     & Experiment 1 & Experiment 2 & Experiment 3 \\
			\midrule
			LinUCB (mean) & $0.4 \pm 0.0$ & $37.2 \pm 4.9$ & $0.6 \pm 0.0$  \\[1.0ex]
			LinUCB (convex risk) & $231.0 \pm 21.7$ & $814.8 \pm 88.3$ & $519.1 \pm 33.3$ \\[1.0ex]
			LinUCB-OGD (convex risk) & $20.4 \pm 3.9$& $60.2 \pm 12.0$ & $25.7 \pm 4.9$ \\[1.0ex]
			\bottomrule
		\end{tabular}
		\vskip -5mm
	\end{table}
\end{small}