Patrick Saux

Odalric-Ambrym Maillard

Risk-aware linear bandits with convex loss

In decision-making problems such as the multiarmed bandit, an agent learns sequentially by optimizing a certain feedback. While the mean reward criterion has been extensively studied, other measures that reflect an aversion to adverse outcomes, such as mean-variance or conditional value-at-risk (CVaR), can be of interest for critical applications (healthcare, agriculture). Algorithms have been proposed for such riskaware measures under bandit feedback without contextual information. In this work, we study contextual bandits where such risk measures can be elicited as linear functions of the contexts through the minimization of a convex loss. A typical example that fits within this framework is the expectile measure, which is obtained as the solution of an asymmetric least-square problem. Using the method of mixtures for supermartingales, we derive confidence sequences for the estimation of such risk measures. We then propose an optimistic UCB algorithm to learn optimal risk-aware actions, with regret guarantees similar to those of generalized linear bandits. This approach requires solving a convex problem at each round of the algorithm, which we can relax by allowing only approximated solution obtained by online gradient descent, at the cost of slightly higher regret. We conclude by evaluating the resulting algorithms on numerical experiments.

INTRODUCTION

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 a policy in order to maximize rewards, facing the classical exploitation-exploration dilemma. A prominent example of such models is the linear bandit, which assumes a linear relationship actions and the mean rewards. In this setting, a standard learning strategy consists in estimating the reward model by ridge regression coupled with an appropriate exploration scheme, e.g., optimism (Abbasi-Yadkori et al., 2011), Thompson sampling [START_REF] Agrawal | Thompson sampling for contextual bandits with linear payoffs[END_REF][START_REF] Abeille | Linear thompson sampling revisited[END_REF] or information-directed [START_REF] Russo | Learning to optimize via information-directed sampling[END_REF][START_REF] Kirschner | Asymptotically optimal information-directed sampling[END_REF].

One limitation of this setting is that real-world agents may assess rewards with a different criterion than the mean. While mathematically convenient, the latter is known to equally weight large positive and negative outcomes, possibly leading to risky policies unsuitable to critical applications, and is also sensitive to outliers. In contrast, riskaware measures emphasize different characteristics of the reward distribution, e.g., by stressing out the impact of adverse outcomes [START_REF] Dowd | Measuring market risk[END_REF]. Such measures include the mean-variance [START_REF] Markowitz | portfolio selection[END_REF], conditional Valueat-Risk [START_REF] Rockafellar | Optimization of conditional value-at-risk[END_REF], which is a special case of spectral risk measures [START_REF] Acerbi | Spectral measures of risk: A coherent representation of subjective risk aversion[END_REF], entropic risk [START_REF] Maillard | Robust risk-averse stochastic multi-armed bandits[END_REF] and the expectiles [START_REF] Newey | Asymmetric least squares estimation and testing[END_REF]. These measures, 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 [START_REF] Galichet | Exploration vs exploitation vs safety: Risk-aware multi-armed bandits[END_REF][START_REF] Gopalan | Weighted bandits or: How bandits learn distorted values that are not expected[END_REF][START_REF] Cassel | A general approach to multi-armed bandits under risk criteria[END_REF][START_REF] Tamkin | Distributionally-aware exploration for cvar bandits[END_REF][START_REF] Prashanth | Concentration bounds for cvar estimation: The cases of lighttailed and heavy-tailed distributions[END_REF][START_REF] Pandey | Estimation of spectral risk measures[END_REF][START_REF] Baudry | Optimal thompson sampling strategies for support-aware cvar bandits[END_REF]. In distributional reinforcement learning, quantile regression has been studied for DQN [START_REF] Dabney | Distributional reinforcement learning with quantile regression[END_REF]. Recently, bandits with contextual mean-variance and CVaR have been applied to vehicular communication [START_REF] Wirth | Risk-aware multi-armed bandits for vehicular communications[END_REF]. 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 definition covers quantiles, expectiles and entropic risk, and can be extended to mean-variance and conditional valueat-risk using multivariate risk measures. To our knowledge, this setting is new, although related to existing approaches, such as bandits with regression oracles [START_REF] Foster | Beyond ucb: Optimal and efficient contextual bandits with regression oracles[END_REF] and generalized linear bandits (GLB) [START_REF] Filippi | Parametric bandits: The generalized linear case[END_REF][START_REF] Li | Provably optimal algorithms for generalized linear contextual bandits[END_REF][START_REF] Faury | Improved optimistic algorithms for logistic bandits[END_REF], that go beyond reward linearity while still working under the mean criterion.

Contributions We introduce a generalization of LinUCB to a large class of so-called elicitable risk measures, which includes the expectiles and the entropic risk. In contrast with the standard mean-linear bandit, learning the linear mapping between actions and risk measures cannot be performed sequentially, which presents theoretical and numerical challenges similar to GLB. We derive time-uniform confidence sets (Proposition 1) based on the method of mixtures [START_REF] Peña | Self-normalized processes: Limit theory and Statistical Applications[END_REF] and introduce a geometric condition (Lemma 2) to ensure sublinear regret in this new setting (Theorem 1). Using recent developments on timeuniform matrix concentration, we further strengthen the regret bound in the case of stochastic actions with a known covariance lower bound (Theorem 2). To mitigate the numerical burden, we introduce an episodic version of Lin-UCB with online gradient descent approximation (Theorem 3), inspired by previous works on online regression [START_REF] Korda | Fast gradient descent for drifting least squares regression, with application to bandits[END_REF] and the recent literature on approximate Thompson sampling for GLB [START_REF] Ding | An efficient algorithm for generalized linear bandit: Online stochastic gradient descent and thompson sampling[END_REF].

Notations We consider the Euclidean space R d , •, • and denote by I d the identity matrix of R d . For a positive definite matrix P ∈ S ++ d (R) and a vector x ∈ R d , we define the norm x P =

x, P x . When P = I d , we let • P = • 2 be the L 2 norm. B d

• (x, R) denotes the ball in R d centred on x of radius R with respect to the norm • . A B stands B -A ∈ S d (R) (positive semidefinite matrix). For K ∈ N, [K] denotes the set {1, . . . , K}. For a set E, 2 E denotes the set of all subsets of E.

CONTEXTUAL BANDITS WITH RISK

We consider the standard contextual bandit setting where an agent sequentially observes at time t ∈ N a decision set X t ⊆ R d , then chooses an action X t ∈ X t and receives a stochastic reward Y t , the distribution of which is dependent on X t . More formally, let X = ∪ t∈N X t and Φ : X → P(R) a mapping from actions to reward distributions, so that the agent receives at time t the reward Y t ∼ Φ(X t ). We denote by F t = σ (X 1 , X 1 , Y 1 , . . . , X t-1 , X t-1 , Y t-1 , X t , X t ) the σ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 Φ in order to select actions that induce high rewards. A standard inductive bias in this context is to assume a linear re-lation between rewards and contexts, typically of the form Y t = θ * , X t + η t , where η 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 of the mapping between actions and rewards:

X R p P(R) * ϕ Φ = ϕ • *
where * : X → 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 (ϕ, * ). When the distribution depends on a single parameter (p = 1), we represent the linear form by * : x ∈ X → θ * , x , where θ * ∈ R d , and we use the notation (ϕ, θ * ), or equivalently we say that it is represented by Y ∼ ϕ( θ * , X ). In the following, we also denote by Θ ⊆ R d parameter space.

As an example, let us consider the following Gaussian mapping Φ : x ∈ X → µ(x) + σ(x)N (0, 1). If σ is constant and µ(x) = θ µ , x , we recover a standard linear bandit model, in which the goal is to maximize the cumulative average rewards T t=1 µ(X t ). However, in many applications, the agent may be averse to high reward volatility, which can be encoded by µ(x) -λσ(x) for some λ > 0. We detail in Appendix A how many standard risk measures (entropic, p-expectile) realize this mean-variance tradeoff.

Overview of Risk Measures

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). In most algorithms, the exploitation takes the form of a supervised estimation that consists in learning the mapping ϕ at time t from the past observations {(X s , Y s ), 1 s t-1}. When the expected reward is parametrized by Y t = θ * , X t + η t with E[η t |F t ] = 0, a standard strategy consists in estimating θ * by ridge regression, that is

min θ∈Θ t-1 s=1 (Y s -θ, X s ) 2 + α 2 θ 2 2
, where α > 0 is a regularization parameter. Assuming for now the solution is in the interior of Θ, the solution can be written as

θ t = (V α t ) -1 t-1
s=1 Y s X s , where we define the d × d positive definite matrix V α t := t-1 s=1 X s X s + αI d . This method presents several advantages: it can be computed efficiently via sequential matrix inversion (with complexity O(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 starting from V α 0 = αI d ) and explicit confidence ellipsoids for θ * can be constructed analytically around θ t to tune exploration (Abbasi-Yadkori et al., 2011). The implicit limitation of this procedure is that it can only estimate the expectation

E[Y ] = argmin θ∈Θ E[(Y -θ, X ) 2 ].
We call this standard setting the 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 L : R×R p → R + and define the risk measure associated with loss L for a distribution ν over R as ρ L (ν) = arg min ξ∈R p E Y ∼ν [L(Y, ξ)]. We assume here that the argmin is unique for simplicity (which is the case if L is strongly convex) and will sometimes use the notation ρ L (Y ) instead of ρ L (ν) for a random variable Y with distribution ν. Similarly, we define the conditional risk measure ρ L (ν|G) = arg min

ξ∈R p E Y ∼ν [L(Y, ξ)|G]
for any event G with positive measure. Note that with this definition, ρ L (ν) is a vector in R p . When p = 1, we call these scalar risk measures. The motivation to consider vector-valued risk measures comes from the fact that not every measure of interest can be elicited as a scalar risk measure, which we develop in the next paragraph.

Elicitable Risk Measure Scalar risk measures that can be expressed as minimizers of such loss functions are known as (first-order) elicitable risk measures [START_REF] Ziegel | Coherence and elicitability[END_REF]. 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 ρ

(ν) = E Y ∼ν [T (Y )],
where T : R → R is a ν-integrable mapping, and the entropic risk defined by ρ L (ν) = 1

γ log E Y ∼ν [e γY ] (Maillard, 2013). 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 [START_REF] Fissler | Expected shortfall is jointly elicitable with value at risk-implications for backtesting[END_REF][START_REF] Fissler | Higher order elicitability and osband's principle[END_REF]. However, they are second-order elicitable, in the sense that the pairs (mean, variance) and (VaR, CVaR) are jointly elicitable. We refer to Appendix A for a summary and further interpretation of elicitable risk measures.

We say that the loss L is adapted to the linear bandit (ϕ, * ) if for all x ∈ X , * is a minimizer of E [L (Y, (x))] among all linear forms : X → R p , where Y ∼ ϕ • * (x) denotes the reward random variable of the linear bandit when action x is played. Intuitively, this means that the risk measure ρ L 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.

Remark 1

The above definition is written in the general case of a vector-valued risk measure ρ L . 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 L is adapted to the linear bandit (ϕ, θ * ) if for all x ∈ X , we have that

θ * ∈ arg min θ∈Θ E Y ∼ϕ( θ * ,x ) [L (Y, θ, x )].
Quantile p ∈ (0, 1) (p -I z<0 )z ρ ψ -∞ ν(dy) = p Expectile p ∈ (0, 1) |p -I z<0 |z 2 (1-p) ρ ψ -∞ |y-ρ ψ |ν(dy) = p ∞ ρ ψ |y -ρ ψ |ν(dy)
Convex Potential A special case of interest is when the convex loss L = L ψ derives from a potential ψ, that is when L ψ (y, ξ) = ψ(y-ξ). 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 [START_REF] Newey | Asymmetric least squares estimation and testing[END_REF], we define the p-expectile of ν for p ∈ (0, 1) as

argmin ξ∈R E Y ∼ν [|p -I Y <ξ |(Y -ξ) 2 ].
Expectiles have been studied in particular in the context of risk management [START_REF] Bellini | Risk management with expectiles[END_REF] and risk-aware Bayesian optimization [START_REF] Torossian | Bayesian quantile and expectile optimisation[END_REF]. Furthermore, under some symmetry conditions, quantiles and expectiles are known to coincide [START_REF] Abdous | Relating quantiles and expectiles under weighted-symmetry[END_REF], and thus expectiles can be seen as a smooth (in particular differentiable) generalization of quantiles (see [START_REF] Philipps | Interpreting expectiles[END_REF] for further interpretation of the notion of expectiles). We refer the reader to Table 1 for a summary of risk measures elicited by convex potentials.

In the terminology defined above, the ordinary least square potential is adapted to the mean-linear reward model Y t = θ * , X t + η t with E[η t |F t ] = 0. More generally, such an additive decomposition exists for losses derived from potentials (see Lemma 4 in Appendix B).

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., ρ αL+β = ρ L for all α > 0 and β ∈ R. Other less trivial examples of nonunicity arise even for the simple mean criterion. Theorem 1 in [START_REF] Banerjee | On the optimality of conditional expectation as a bregman predictor[END_REF] shows that

E Y ∼ν [Y ] = ρ B ψ (ν)
where ψ is any strictly convex, differentiable function and B ψ : (y, ξ) → ψ(y)-ψ(ξ)-ψ (ξ)(y-ξ) is the Bregman divergence induced by ψ, which generalizes the quadratic potential. In fact, every continuously differentiable loss that elicits the mean has this form (Theorem 3 and 4 in [START_REF] Banerjee | On the optimality of conditional expectation as a bregman predictor[END_REF]). Similarly, the pairs (mean, variance) and (VaR, CVaR) can be elicited by families indexed by differentiable, strictly convex functions (Table 3, Appendix A).

Contextual Bandits with Elicitable Risk Measures

Regret For a linear bandit (ϕ, θ * ), we define the pseudo-regret associated to a risk mea-sure ρ L and a sequence of actions

(X t ) 1 t T as R T = T t=1 ρ L (ϕ( θ * , X * t )) -ρ L (ϕ( θ * , X t )), where X * t = argmax x∈Xt ρ L (ϕ( θ * , x ))
is the optimal action w.r.t the risk measure ρ L . By definition, if the loss L is adapted to the linear bandit, this notion of regret reduces to R T = T t=1 θ * , X * t -θ * , X t , which is formally the same as the standard regret for mean-linear bandits. What differs though is the meaning of θ * , X t , which now represents an elicitable risk measure for the reward distribution. As an example, this paves a way for expectilelinear bandit of the form Y t = θ * , X t + η t where the conditional expectile of η t is zero and expectile rewards are measured as linear forms of the actions θ * , X t .

Supervised Estimation of θ * Similarly to how ridge regression provides natural estimators of the mean, we define

θ t ∈ argmin θ∈Θ t-1 s=1 L(Y s , θ, X s ) + α 2 θ 2 2
, which corresponds to the empirical risk minimization associated to loss L, with L 2 regularization parameter α > 0. Assuming that L is differentiable and that θ t is in the interior of Θ, this estimator is characterized by the equation α θ t = -t-1 s=1 ∂L(Y s , θ t , X s )X s , where ∂L(y, ξ) stands for the derivative of ξ → L(y, ξ). When θ t is not in the interior of Θ, an additional projection onto Θ is necessary, which we denote by the operator Π (such an operator is detailed in Section 3.1). We also define

H α t (θ) = t-1 s=1 ∂ 2 L (Y s , θ, X s ) X s X s + αI d
the Hessian of the empirical loss at θ of the minimization problem.

We note that when L derives from the quadratic potential ψ(ξ) = ξ 2 /2, it holds that H α t (θ) = V α t and we thus fall back to the mean-linear case. For all other choices of the loss function L, the Hessian H α t depends on θ, and in particular no closed-form expression of θ t in terms of the inverse of H α 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 θ t .

Remark 2 Similar complications arise in the case of generalized linear bandits (GLB) Y t = µ( θ * , X t ) + η t , with E[η t |F t ] = 0 and µ a nonlinear link function. Under parametric assumptions on Y t (typically one-dimensional exponential family), GLB can be seen as a special case of the risk-aware setting with L the negative log-likelihood loss, with the analogy µ ↔ ∂L. Despite this formal similarity, GLB is designed solely to optimize the mean criterion. Another difference with our setting is that regret for GLB is commonly defined as T t=1 µ( θ * , X * t ) -µ( θ * , X t ), which is smaller than R T when µ is contracting.

Extension of LinUCB to Convex Losses

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 Abbasi-Yadkori et al. (2011), Ch.19 in Lattimore and[START_REF] Lattimore | Bandit algorithms[END_REF]), essentially substituting the least-squares estimate with the empirical risk minimizer associated with L. The general idea of such optimistic algorithms is to play at time t the action x ∈ X t with the highest plausible reward. In the mean-linear case with ridge regression, this highest plausible reward takes the form of θ t , x + γ t (x), where γ t (x) is a certain action-dependent quantity also known as the exploration bonus. We write the general structure of our extension of LinUCB (CR for Convex Risk) in Algorithm 1.

Algorithm 1 LinUCB-CR Input: regularisation parameter α, projection Π, exploration bonus sequence (γ t ) t∈N .

Initialization: Observe X 1 . for t = 1, . . . , T do θ t ∈ arg min R d t-1 s=1 L(Y s , θ, X s ) + α 2 θ 2 2 ; Empirical risk minimization θt = Π( θ t ) ; Projection X t = arg max x∈Xt θt , x + γ t (x) ;
Play arm Observe Y t and X t+1 .

ANALYSIS OF LinUCB-CR

The goal of this section is to derive an exploration bonus sequence (γ t ) t∈N and a projection operator Π¸that ensure sub-linear regret of the corresponding LinUCB instance. To this end, we introduce the following control on the curvature of the adapted loss L.

Assumption 1 (Bounded Loss Curvature) There exists m and M such that

∀y, ξ ∈ R, m ∂ 2 L(y, ξ) M .
We call the parameter κ = M m the conditioning of L.

Remark 3 This assumption is reminiscent of the standard lower bound on the derivative of the link function µ commonly encountered in the GLB literature.

Martingale Property and Concentration

A key property for the analysis of mean-linear bandits is that the sum process t-1 s=1 η s X s naturally defines a vector-valued martingale in R d with respect to the filtration F t (Abbasi-Yadkori et al., 2011). This is not the case in general for bandits associated with generic convex losses. Instead, for a given loss L, we know that θ * = argmin θ E[L(Y t , θ, X t )|F t ]. Assuming L is differentiable and using the shorthand

∂ j L * t = ∂ j L(Y t , θ * , X t ) for j ∈ N and t ∈ N, this implies E[∂ 1 L * t |F t ] = 0 since X t is measurable with respect to F t . A direct consequence of this is that S t = t-1 s=1 ∂ 1 L * s X s defines a F-martingale.
This process is at the heart of the next proposition, which establishes confidence bounds using the method of mixture (see [START_REF] Peña | Self-normalized processes: Limit theory and Statistical Applications[END_REF] in general and Abbasi-Yadkori et al. (2011);[START_REF] Faury | Improved optimistic algorithms for logistic bandits[END_REF] for specific applications to contextual bandits). To this end, we detail below a helpful transformation of the sum process S into a nonnegative supermartingales (Lemma 1) under a standard sub-Gaussian assumption (Assumption 2) and state the high-probability uniform deviation bound we obtain (Proposition 1), the proof of which is deferred to Appendix C.

Assumption 2 (Sub-Gaussian) ∂ 1 L * is a conditionally sub-Gaussian process, i.e., there exists R > 0 such that

∀t ∈ N, ∀λ ∈ R, log E exp λ∂ 1 L * t |F t λ 2 R 2 2 .
Lemma 1 (Supermartingale Control) Under Assumptions 1-2, there exists σ > 0 such that for any t ∈ N and λ ∈ R d , the following holds:

E exp λ, X t ∂ 1 L * t - σ 2 2 λ, X t 2 ∂ 2 L * t F t 1 .
Proposition 1 (Method of Mixtures with Convex Loss) Let β > 0. Under Assumptions 1-2, with probability at least 1 -δ, for all t ∈ N, it holds that

S t 2 H β t (θ * ) -1 σ 2 2 log 1 δ + log det H β t (θ * ) det βI d .
Discussion on Lemma 1 and Assumption 2 As shown in the proof, Lemma 1 alone implies Proposition 1. While this lemma may be valid in more general settings, we show in Appendix C how it is conveniently implied by Assumption 1 and the sub-Gaussian control of Assumption 2. In the rest of the paper, in particular in the regret bounds of Theorem 1, 2 and 3, σ will refer to the parameter that appears in the supermartingale control of Lemma 1.

Regarding Assumption 2, note that for a mean-linear bandit Y t = θ * , X t + η t with adapted loss L(y, ξ) = 1 2 (y -ξ) 2 , we have that ∂L * t = η t , which is classically assumed to be sub-Gaussian. For other bandits, and thus other adapted losses, it may be more convenient to make assumptions on the distribution of observable quantities such as X t and Y t rather than directly on ∂L * t . 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 our knowledge no complete answer is available, several partial results are available in the concentration literature.

(i) If Z is Gaussian with variance σ 2 and f is M -Lipschitz, the Tsirelson-Ibragimov-Sudakov inequality (Boucheron et al., 2013, Theorem 5.5) shows that f (Z) is M σ-sub-Gaussian. In particular, the Lipschitz assumption holds for ∂L if the loss curvature is bounded from above by M . More generally, if Z can be written as a σ-Lipschitz function of a N (0, 1), then f (Z) is M σ-sub-Gaussian.

(ii) 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 Vershynin (2018, Theorem 5.2.15)).

(iii) 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., Boucheron et al. (2013, Theorem 6.10)). The boundedness assumption can be lifted at the cost of a slightly more stringent condition than the sub-Gaussianity of Z, see Adamczak (2005, Theorem 3).

In short, Assumption 2 holds in a variety of settings, under rather mild assumptions on either X t and Y t or the loss L. Also of note, ∂ 1 L is M -Lipschitz under Assumption 1.

Confidence Set for θ * To help write the above confidence set in terms of θ * and the empirical estimator θ t , we introduce the function

F α t : θ ∈ Θ → t-1 s=1 ∂L (Y s , θ, X s ) X s + αθ ∈ R d . As seen above, F α t ( θ t ) = 0 and F α t (θ * ) = S t + αθ * . Noticing that F α t (θ * ) -F α t ( θ t ) 2 H β t (θ * ) -1 = S t + αθ * H β t (θ * ) -1 S t H β t (θ * ) -1 +α θ * H β t (θ * ) -1
, we immediately derive the following result (note the use of a priori different regularization parameters α and β, which we exploit in the sequel).

Corollary 1 For t ∈ N, δ ∈ (0, 1), α, β > 0, let

Θ δ t = θ ∈ Θ, F α t (θ) -F α t ( θ t ) H β t (θ) -1 σ 2 log 1 δ + log det H β t (θ) det βI d + α θ H β t (θ) -1 .
Then under Assumptions 1-2, it holds that

P ∀t ∈ N, θ * ∈ Θ δ t 1 -δ .
We constantly use this result in the following, in particular to construct the projection operator Π. Indeed, if we define

θt := Π( θ t ) as argmin θ∈Θ F α t (θ) -F α t ( θ t ) H β t (θ) -1
, we have the property that Π( θ t ) ∈ Θ δ t with high probability.

Remark 4 Although we formulated the bounded curvature condition (Assumption 1) globally, we note that we only require it to hold in a convex neighborhood of θ * containing θt , and Corollary 1 shows that with high probability, θ * -θt 2 is bounded (going from the H β t (θ * ) -1 norm to the Euclidean norm can be done by simple positive definite matrix inequalities). Therefore, one could instead assume a local curvature control on ∂L(y, θ, x ) for x ∈ X t and θ in a ball around θ * , in the same spirit as Assumption 1 in [START_REF] Li | Provably optimal algorithms for generalized linear contextual bandits[END_REF] for GLB.

Optimism and 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 = θ * , X * t -θ * , X t the instantaneous regret, where θ * , X * t = max x∈Xt θ * , x is the optimal risk measure associated with L at time for the actions available at time t. Then, simple algebra shows that

r t = θ * -θt , X * t -θ * -θt , X t + θt , X * t -X t = ∆(X * t , θt ) + ∆(X t , θt ) + θt , X * t -X t ,
where we define for x ∈ X and θ ∈ Θ, ∆(x, θ) = | θ * -θ, x | the absolute error made by θ with respect to the true parameter of the linear bandit θ * in the direction of x. If we know a sequence of functions γ t : X → R + such that with high probability, for all t ∈ N and x ∈ X t , ∆(x, θt ) γ t (x), then the principle of optimism recommends the action X t ∈ argmax x∈Xt θt , x + γ t (x), i.e., the one leading to the best plausible reward with respect to the confidence on the prediction error of θt . In this case,

r t ∆(X * t , θt )+∆(X t , θt )+γ t (X t )-γ(X * t ) 2γ t (X t
) with high probability, and hence R T 2 T t=1 γ t (X t ). We detail below how Corollary 1 coupled with standard assumptions provides such a bound.

Bound on the Prediction Error

We follow the standard strategy of decoupling the dependency on θt and x in ∆(x, θt ). By Cauchy-Schwarz's inequality, we have, for some positive definite matrix P to be determined later,

∆(x, θt ) = | P 1 2 (θ * -θt ), P -1 2 x | θ * -θt P x 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 x P -1 can be handled by the elliptical potential lemma (Lemma 11 in Abbasi-Yadkori et al. ( 2011)). To control the remainder term in θ * -θt , we borrow technical tools from the classical approach developed for generalized linear bandits [START_REF] Filippi | Parametric bandits: The generalized linear case[END_REF][START_REF] Faury | Improved optimistic algorithms for logistic bandits[END_REF] and note that

F α t (θ * ) -F α t ( θt ) = Hα t (θ * , θt )(θ * -θt ) ,
where Hα

t (θ * , θt ) = 1 0 H α t (uθ * + (1 -u) θt )du
is the average of the Hessian matrices along the segment [ θt , θ * ] 1 (this follows from the observation that the differential of

F α t is H α t ). Therefore the choice P = Hα t (θ * , θt ) yields θ * -θt P = F α t (θ * ) -F α t ( θt ) Hα t (θ * , θt) -1 F α t (θ * ) -F α t ( θ t ) Hα t (θ * , θt) -1 + F α t ( θt ) -F α t ( θ) Hα t (θ * , θt) -1 .
1 One could also use Hα

t (θ * , θt) = 1 0 H α t (γu)du where γ : [0, 1] → Θ is smooth, unit speed path connecting θt and θ * .
To conclude, we need to find a way to relate the local metric defined by Hα t (θ * , θt ) -1 to those defined by H β t (θ * ) -1 and H β t ( θt ) -1 , for which we have high confidence bounds. This motivates the following assumption.

Lemma 2 (Transportation of Local Metrics) Under Assumption 1, for α > 0, there exists κ > 0, β > 0 such that

Hα t (θ * , θt ) 1 κ H β t (θ * ) and Hα t (θ * , θt ) 1 κ H β t ( θt ) .
We detail in Appendix D that a suitable choice of parameter is β = κα with κ = M m the conditioning of the loss L, which is a direct consequence of Assumption 1. Again, we keep the formulation fairly generic as Lemma 2 may hold beyond losses with bounded curvature. For instance, in a special case of GLB, namely the logistic bandit, it is shown in [START_REF] Faury | Improved optimistic algorithms for logistic bandits[END_REF] that this lemma holds thanks to selfconcordance properties of the sigmoid link function.

Examples

We conclude this section by discussing examples of standard losses and whether they satisfy the above conditions.

Example 1 (Expectile) The expectile loss is derived from the potential ψ 2 (z) = |p -I z<0 |z 2 , the second derivative of which is ψ 2 (z) = 2|p -I z<0 |. Thus, Assumption 1 holds with m = 2 min(p, 1 -p) and M = 2 max(p, 1 -p).

Example 2 (Quantiles) The quantile loss is derived from the potential ψ 1 (z) = (p -I z<0 )z, which is piecewise linear. In particular, it is not strongly convex and thus does not satisfy Assumption 1. Bandits with quantile regression are therefore outside the scope of this work.

Regret Analysis

We make two additional standard assumptions that prior bounds are known on θ * and on the actions X = t∈N X t , which is standard in the existing literature on linear bandits.

Assumption 3 (Prior Bound on Parameters) All parameters are bounded by S, i.e., Θ ⊆ B d

• 2 (0, S). In particular, this implies that θ *

H β t (θ * ) -1 S √ β for any β > 0.
Assumption 4 (Prior Bound on Actions) All actions are bounded by L, i.e., X ⊆ B d • 2 (0, L).

We now obtain a high probability upper bound on the regret incurred by Algorithm 1 for an explicit choice of exploration bonus sequence (γ t ) t∈N and projection Π. As is standard for contextual bandits, this bound is minimax (worst-case) as it does not depend explicitly on the optimality gaps θ * , X * t -θ * , X t .

Theorem 1 (Regret upper bound for LinUCB-CR -1) Let δ ∈ (0, 1), α max(1, L 2 ) and define for t ∈ N the exploration bonus

γ t : x ∈ X t → c δ t x H κα t ( θt) -1 , c δ t = 2κ σ 2 log 1 δ + d log m α + log det V α m t + α κ S
and the projection operator

Π : θ ∈ R d → argmin θ∈Θ F α t (θ) -F α t ( θ) H κα t (θ) -1 .
Under Assumptions 1-2-3-4, with probability at least 1 -δ, the regret of Algorithm 1 is bounded by

R T 2c δ T max 1 √ m , L √ κα 2T d log 1+ mT L 2 dκα .
In particular, we have

R T = O κσd √ m √ T log T L 2 d .
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 E.

Remark 5 This regret bound scales with κm -1/2 , where m is the minimum curvature of the loss L and κ the coefficient of transportation of local metrics. Under Assumption 1, this scales as m -3/2 . In the limit of flattening loss m → 0, learning with this strategy becomes impossible. We show in Appendix E that a small modification of the exploration sequence reduces this dependency to κ 1/2 m -1/2 , at the cost of loosing local information carried by H κα t ( θt ). An analogous dependency on m -1 was observed for GLB in [START_REF] Filippi | Parametric bandits: The generalized linear case[END_REF]. In the special case of logistic bandit, [START_REF] Faury | Improved optimistic algorithms for logistic bandits[END_REF] obtained a κ independent of m using self-concordance, and even pushed the dependency on m -1/2 to higher order terms in T using a more intricate algorithmic design. We conjecture that a similar construction could apply here but leave this open for future work.

Remark 6 In the mean-linear case, m = M = κ = 1 and H α t = V α t , thus this result is compatible with the minimax lower bound O(d √ T ) for actions in B d • (0, 1) (Lattimore and Szepesvári, 2020, Theorem 24.2) and matches the standard LinUCB upper bound (Abbasi-Yadkori et al., 2011).

Theorem 1 holds for arbitrary (potentially adversarial) sequence of action sets (X t ) t∈N . If these are instead stochastically generated, the regret bound can be further tightened.

Assumption 5 (Stochastic action sets) Let ν X a probability measure on 2 B d • 2 (0,L) (i.e., samples drawn from ν X are sets of vectors of L 2 norm at most L).

(i) For t ∈ N, X t ∼ ν X defines an i.i.d. sequence of random action sets.

(ii) Recall that X t ∈ X t denotes the action selected by the agent at time t

∈ N. Then E X t X t |F t-1 ρ X L 2 I d > 0.
Theorem 2 (Regret upper bound for LinUCB-CR -2) Under Assumptions 1-2-3-4-5, with probability at least 1 -2δ, the regret of Algorithm 1 is bounded by

R T 4c δ T 2T mρ X 1 + C √ T ,
where C is a constant independent of T . In particular, we have

R T = O κσ dT mρ X log T L 2 d .
The lower bound on conditional covariance of actions of Assumption 5 is new, although related to more standard settings. In the case of finite action sets

X t = {X k,t , k ∈ [K]},
1 K k∈[K] X k,t X k,t .
We argue that this assumption is quite mild in the sense that for nondegenerate ν X , the conditioning is essentially irrelevant. At time t, X t is drawn independently of F t-1 , and X t ∈ X t is selected in a F t-1 -measurable fashion. To violate the covariance inequality, there should exist a fixed strict subspace V ⊂ R d such that with some probability X t ∩ V = ∅ (when randomizing over the action set X t ) and X t should be one of the vectors in V; however, if, e.g., ν X spans an open set, this almost surely cannot happen. In other words, Theorem 2 shows that if action sets X t are generated with enough diversity and no adversarial bias, the regret of optimistic strategies can be slightly improved by a factor O(log(T )). Finally, note that Assumption 5 and ρ X do not influence the design of Algorithm 1, only the O (log T ) term in its regret upper bound.

In general, ρ -1 X d and in many cases ρ -1 X = O(d) (see Appendix F), hence the regret upper bound scales linearly with d. Compared to [START_REF] Kim | Double doubly robust thompson sampling for generalized linear contextual bandits[END_REF], our proof relies on line crossing arguments developed in [START_REF] Howard | Time-uniform chernoff bounds via nonnegative supermartingales[END_REF] rather than on a crude union bound, leading to improved constants and higher order terms (even in the mean-linear case). We refer to Appendix F for additional details.

APPROXIMATE STRATEGY 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 θ t needs to be calculated from scratch at each step as

argmin θ∈R d t-1 s=1 L(Y s , θ, X s )+ α 2 θ 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 α t , which can be done efficiently from the knowledge of the inverse of V α t-1 via the Sherman-Morrison formula.

We propose an alternative algorithm that exploits online gradient descent (OGD) to compute a fast approximation of the empirical risk minimizer θ 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 relevant in the meanlinear setting with high dimensional action sets, where computing gradients may be more tractable than inverting a large d × d matrix. For θ ∈ R d , we use the shorthand

∇ α n,h ( θ) = h k=1 ∂L(Y (n-1)h+k , θ, X (n-1)h+k )+α θ.
Algorithm 2 LinUCB-OGD-CR Input: horizon T , regularisation parameter α, projection Π, exploration bonus sequence (γ OGD t,T ) t T , step sequence (ε t ) t∈N , episode length h > 0.

Initialization: Observe X 1 , set θ OGD 0 , t = 1, n = 1. for t = 1, . . . , T do if t = nh + 1 then θ OGD n = θ OGD n-1 -ε n-1 ∇ α n,h ( θ OGD n-1 ) ; OGD θOGD n = 1 n n j=1 Π( θ OGD j ) ; Average n ← n + 1 a X t = arg max x∈Xt θOGD n , x + γ OGD t,T (x)
; Play with same parameter for h steps Observe Y t and X t+1 ;

t ← t + 1 ;
The intuition behind Algorithm 2 is that at time t = nh+1, the approximation error between the OGD estimate θOGD n and the exact minimizer of the empirical risk θ 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 [START_REF] Ding | An efficient algorithm for generalized linear bandit: Online stochastic gradient descent and thompson sampling[END_REF] and is key to ensure sufficient convexity of the aggregate loss ∇ α n,h ( θ). 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, Hazan (2019)) to a weaker sub-Gaussian control at a given parameter. We prove in Appendix G an extension of the following proposition, with an explicit bound on the OGD regret, which we report below in the O notation for the sake of concision.

Proposition 2 (OGD Regret, Sub-Gaussian Gradients) Let C a convex subset of R d and Π the projection operator onto C. For j = 1, . . . , N , let j : C -→ R + a twice differentiable convex function and a, A > 0 such that aI d ∇ 2 j (z) AI d for all z ∈ C. Define the OGD update at step j by z j = Π(z j-1 -ε j-1 ∇ j (z j-1 )) and zn = arg min z∈C n j=1 j (z). Assume that there exists z * ∈ C such that ∇ j (z * ) = g j + α n z * with α 0 and g a centered, R d -valued σ-sub-Gaussian process, and also that C is bounded, i.e., diam(C) = sup z,z ∈C z -z < ∞.

Then with probability at least 1 -δ, the OGD regret with

step size ε j = 3 aj is bounded uniformly in N → +∞ by N j=1 j (z j ) -j (z N ) = O dσ 2 a log 2 N .
Our final result, which we prove in Appendix H, states that the approximation error of OGD induces at most a polylog correction in the regret of LinUCB-OGD-CR.

Theorem 3 (Regret of LinUCB-OGD-CR) Let ε h > 0 and h = 2ε h ρ X L 2 + 8 ρ 2 X log 2 δ . Assume that ∂L(Y t , θ * , X t ) is √ mσ-sub-Gaussian for all t T .
Under Assumptions 1-2-3-4-5, there exists constants C, C > 0 such that with probability at least 1 -(1 + T /h)δ the regret of Algorithm 2 with exploration bonus sequence

γ OGD t,T : x ∈ X t → (c δ t + c OGD,δ t,T ) x H κα t ( θOGD t-1 h ) -1 , c OGD,δ t,T = L 2 + α mM t 2κC dh 2 σ 2 ε 2 h log 2dT hδ log t h ,
and the OGD step sequence of Proposition 2 satisfies

R T = O σ κdT mρ X κ log T L 2 d + h log (dT ) .
The episode length h scales as O(ρ -2 X ), which grows at least as fast as O(d 2 ) in the action dimension d. This is sufficient to bound with high probability the smallest eigenvalue of the Hessian of the aggregate losses ∇ α n,h and thus ensure their strong convexity. However, longer episodes also means less frequent updates of θOGD n , i.e., less learning, which is materialized by the additional dependency on h in the regret. In Appendix H, Lemma 7, we deduce a tighter, more intricate expression for h, although still scaling as O(ρ -2 X ). We only report the simpler expression here to avoid cluttering.

Remark 7

The union bound used in Proposition 2 imposes the knowledge of the horizon T at runtime (in the definition of γ t,T ), thus making Algorithm 2 not anytime.

EXPERIMENTS

We conducted three numerical experiments to illustrate the performance of both risk-aware algorithms, under expectiles and entropic risk criteria. In Figure 1, we considered an expectile-based asymmetric distribution [START_REF] Torossian | Bayesian quantile and expectile optimisation[END_REF] with context-dependent p-expectiles. This distribution is log-concave, thus fitting the scope of the supermartingale control of Lemma 1. As recalled in Section 3.3, the corresponding loss satisfies Assumption 1 with m = 2 min(p, 1-p) and M = 2 max(1-p, p). Note that the more risk-averse (p → 0), the flatter the loss (m → 0) and thus the harder it is to learn. This matches the intuition on risk-aware measures: by focusing on the more extreme events, they require more samples to reach the same statistical accuracy. More details, including the other two experiments, are postponed to Appendix I. As far as we are aware, no algorithm exists for the expectile criterion; for entropic risk, [START_REF] Maillard | Robust risk-averse stochastic multi-armed bandits[END_REF] analyzes a variant of KL-UCB but only for the non-contextual multi-armed bandit problem (and without numerical evidences).

The settings of these numerical experiments were designed so that the optimal arms were different depending on the criterion of interest (mean versus risk-aware). Instances of the classical LinUCB algorithm (Abbasi-Yadkori et al., 2011) were indeed deceived and accumulated linear riskaware regret, while Algorithms 1 and 2 exhibited milder sublinear trends. As expected, the LinUCB-OGD variant accumulated slightly more regret and showed higher variability across independent replications compared to Lin-UCB with the exact minimization of the empirical risk, at the benefit of improved runtimes (Table 2).

CONCLUSION

We have introduced a new setting for contextual bandits, building on the recent interest for risk-awareness in multiarmed 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 be- LinUCB-OGD-CR (expectile) 60.2 ± 12.0 yond standard mean-linear bandits. To lift the regret analysis of optimistic algorithms to the setting of scalar risk measures ρ L elicited by a convex loss L, we showed that uniformly bounding the curvature of the loss (Assumption 1) is sufficient to maintain satisfying theoretical guarantees (O( √ T ) worst-case regret, up to polylog terms (Theorem 1 and 2). More precisely, we identified two key conditions, namely a supermartingale control (Lemma 1) and a transportation inequality (Lemma 2), that guarantee sublinear regret; while these are direct consequences of the bounded curvature assumption, they may hold in different settings, as was recently discovered in GLB.

Going further, we believe it would be interesting to extend the linear model between actions and risk measures to generalized linear models (ρ L (Y t ) = µ( θ, X t ) for some link function µ : R → R), kernelized bandits (ρ L (Y t ) = f (X t ) where f belongs to some RKHS) or neural bandits (ρ L (Y t ) = f θ (X t ) where f θ is a neural network with weights θ). Moreover, capturing well-established risk measures such as mean-variance, conditional value-at-risk or quantiles would require to adapt the theory to high-order elicitable measures and to non-smooth losses. Finally, we believe the technical results developed here, in particular the supermartingale control and the transportation inequality, can pave a way for the design and analysis of Thompson sampling strategies in the contextual risk-aware setting.

A SUMMARY AND INTERPRETATION OF ELICITABLE RISK MEASURES

We report in Table 3 an overview of common elicitable risk measures and their associated loss functions. We recall that for a distribution ν over R and a loss function L : R × R p → R, we defined the risk measure elicited by L as ρ L (ν) = arg min ξ∈R p E Y ∼ν [L(Y, ξ)]. 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 ψ 1 and ψ 2 , as well as instances of such losses obtained for the natural choice

ψ 1 (ξ) = ψ 2 (ξ) = ξ 2 /2.
We provide below some intuition about these commonly used measures in risk management.

Mean-Variance Assessing the risk-reward tradeoff of an underlying distribution ν by penalizing its mean by a higher order moment (typically the variance) is perhaps the most intuitive of risk measures. Following [START_REF] Markowitz | portfolio selection[END_REF], the mean-variance risk measure at risk aversion level λ ∈ R is defined by ρ M V1 (ν) = µ -λσ, where µ and σ denote the mean and standard deviation of ν. Alternatively, it can also be defined as ρ M V2 (ν) = µ -λ 2 σ 2 , using the variance rather than the standard deviation in the penalization term. Both measures are especially well-suited for Gaussian distributions as µ and σ fully characterize this family.

VaR and CVaR For a distribution with continuous cdf (i.e., it has no atom), the Value-at-Risk VaR α (ν) at level α ∈ (0, 1) is equivalent to the α quantile, and a simple change of variable reveals that the Conditional Value-at

-Risk CVaR α (ν) is thus E [X | X VaR α (ν)].
Intuitively, a random variable with a high CVaR α distribution takes on average relatively high values in the "α% worst-case" scenario. For α → 1 -, CVaR α (ν) → E Y ∼ν [Y ] and thus the risk measure becomes oblivious to the tail risk; on the contrary, the case α → 0 + emphasizes only the worst outcomes.

In the Gaussian case ν ∼ N (µ, σ), using the notations φ and Φ respectively for the pdf and cdf of the standard normal distribution, simple calculus shows that

VaR α (ν) = µ + σΦ -1 (α) , CVaR α (ν) = µ - σ α √ 2π φ Φ -1 (α) , i.e., CVaR α (ν) = ρ M V1 (ν) with risk aversion level λ = 1 α √ 2π φ Φ -1 (α) .
In particular, increasing the variance σ 2 reduces CVaR α (ν), corresponding to the intuition of higher volatility risk.

Entropic Risk

The non-elicitability of CVaR α motivated the use of the entropic risk as an alternative measure. This measures rewrites as (see [START_REF] Brandtner | Entropic risk measures and their comparative statics in portfolio selection: Coherence vs. convexity[END_REF])

ρ γ (ν) = sup ν probability measure E Y ∼ν [Y ] - 1 γ KL(ν ν) .
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 KL(ν ν) = E Y ∼ν [log dν dν ] instead of the variance. The entropic risk measure can be interpreted as the largest expected value that a mispecified model ν (in place of the true underlying distribution ν) may have, where KL(ν ν) controls the magnitude of the mispecification.

Again, in the Gaussian case, this measure reduces to ρ γ (ν) = µ + γ 2 σ 2 = ρ M V2 (ν) at risk aversion level λ = -γ.

Expectile Beyond their interpretation as generalized, smooth quantiles, expectiles can also be understood in light of the financial risk management literature. Let e p (ν) denote the p-expectile of ν for a given probability p ∈ (0, 1). Then, simple calculus shows that

(1 -p)E Y ∼ν [(e p (ν) -Y ) + ] = pE Y ∼ν [(Y -e p (ν)) + ] ,
where z + = max(z, 0). If ν represents the distribution of a tradeable asset Y at time T , then the p-expectile is the strike K = e p (ν) such that call and put on Y struck at K at maturity T are in proportion 1-p p to each other, where we define the call and put prices (with zero time discounting) by respectively

C(ν, K) = E Y ∼ν [(Y -K) + ] , P (ν, K) = E Y ∼ν [(K -Y ) + ] . Table 3: Example of Elicitable Risk Measures. Name ρ L (ν) Associated loss L(y, ξ) Domain Mean E Y ∼ν [Y ] (y -ξ) 2 Bregman divergence B ψ (y, ξ) ψ(y) -ψ(ξ) -ψ (ξ)(y -ξ), ψ differentiable, strictly convex. ξ ∈ R Derived from potential ψ argmin ξ∈R E Y ∼ν [ψ(Y -ξ)] ψ(y -ξ) ξ ∈ dom(ψ) Generalized moment T : R → R E Y ∼ν [T (Y )] 1 2 ξ 2 -ξT (y) ξ ∈ R Entropic risk, γ = 0 (Example 1, Embrechts et al. (2021)) 1 γ log E Y ∼ν [e γY ] ξ + 1 γ (e γ(y-ξ) -1) ξ ∈ R (mean, variance) (Example 1.23, Brehmer (2017)
) [START_REF] Fissler | Higher order elicitability and osband's principle[END_REF])

µ = E Y ∼ν [Y ] σ 2 = E Y ∼ν [Y 2 ] -µ 2 1 2 ξ 2 1 + 1 2 (ξ 2 + ξ 2 1 ) 2 -ξ 1 y -(ξ 2 + ξ 2 1 )y 2 -ψ 1 (ξ 1 ) -ψ 1 (ξ 1 )(y -ξ 1 ) -ψ 2 (ξ 2 + ξ 2 1 ) -ψ 2 (ξ 2 + ξ 2 1 )(y 2 -ξ 2 -ξ 2 1 )), ψ 1 , ψ 2 differentiable, strictly convex. ξ 1 ∈ R ξ 2 0 (VaR α , CVaR α ), α ∈ (0, 1) (Corollary 5.5,
VaR α = inf{y ∈ R, y -∞ dν α} CVaR α = 1 α α 0 VaR a da (ξ 1 -y) + -αξ 1 +ξ 2 ( 1 α (ξ 1 -y) + -ξ 1 ) + 1 2 ξ 2 2 (I y ξ1 -α)ψ 1 (ξ 1 ) -I y ξ1 ψ 1 (y) +ψ 2 (ξ 2 )(ξ 2 -ξ 1 + 1 α I y ξ1 (ξ 1 -y)) -ψ 2 (ξ 2 ) + c(y), ψ 1 convex, ψ 2 strictly convex and increasing, c : R → R. ξ 1 ξ 2
Risk-aware linear bandits with convex loss Similarly, [START_REF] Keating | A universal performance measure[END_REF] introduced the notion of Omega ratio as a risk-return performance measures. It is defined at level K by

Ω(K) = +∞ K (1 -F (y)) dy K -∞ F (y)dy
, where F is the cdf of ν. This ratio can also be viewed as a call-put ratio, hence another definition of the p-expectile is via the implicit equation Ω(K) = 1-p p for K = e p (ν). Contrary to the previous risk measures, it may not be clear from this definition alone that expectiles do encode a notion of aversion to risk. The next proposition shows that p-expectiles of many distributions, including normal and adjusted lognormal, are decreasing functions of their variances when p < 1 2 , thus penalizing more volatile distributions, making them suitable for risk management. We provide an elementary proof using the tools of the financial mathematics literature, where such risk measures were extensively studied. For p ∈ (0, 1), we let e p (σ) = e p (ν σ ). Then sign d dσ e p (σ) = sign(p -1 2 ).

Before we proceed to the proof, let us note that two classical families of distributions satisfy these assumptions (see (Merton, 1973, Theorem 8) for a a general result).

• Normal:

for µ 0 ∈ R, {ν σ = N (µ 0 , σ 2 ), σ ∈ R * + }, for which E Y ∼νσ [Y ] = µ 0 . • Adjusted lognormal: for µ 0 ∈ R, {ν σ = exp N (µ 0 , σ 2 ) -σ 2 2 , σ ∈ R * + }, for which E Y ∼νσ [Y ] = e µ0 .
In particular in the normal case, it follows from Lemma 3 that e p (ν) = µ 0 + σe p (N (0, 1)) = ρ M V1 (ν σ ) at risk aversion level λ = -e p (N (0, 1)) (positive if p < 1 2 ). Proof We first recall the call-put parity principle, which states that for any distribution ν σ and strike K ∈ R, the following equality holds:

C(σ, K) -P (σ, K) = E Y ∼νσ [Y ] -K ,
where we write C(ν σ , K) = C(σ, K) and P (ν σ , K) = P (σ, K).

Notice that the call-parity principle and the assumption that d dσ E Y ∼νσ [Y ] = 0 implies that ∂ σ C = ∂ σ P . We denote this quantity by V . First, note that σ ∈ I → e p (σ) is differentiable (implicit function theorem). From the equation C(σ, e p (σ)) = (1 -p)/pP (σ, e p (σ)), we deduce that and thus

1 -2p p V + d dσ e p (σ) 1 -p p ∂ K P (σ, e p (σ)) -∂ K C(σ, e p (σ)) = 0 .
Elementary option pricing principles show that V 0, i.e., the call and put prices both increase with higher volatility, as well as ∂ K C 0 and ∂ K P 0. Therefore, we deduce that d dσ e p (σ) 0. 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 = E[Y ], thus giving an alternative derivation of the equivalence between 1/2-expectile and mean.

B PROPERTIES OF CONVEX LOSSES AND POTENTIALS

Before we prove Lemma 4, we write the following technical lemma.

Lemma 3 (Risk Measures ρ ψ Are Additive) Let ψ : R → R be a strongly convex, differentiable function, ν be a distribution over R and c ∈ R. Then ρ ψ (ν + c) = ρ ψ (ν) + c.

Proof For the sake of simplicity, we assume ν admits a density p (with respect to the Lebesgue measure) and that ψ and p are regular enough to allow for differentiation under the following integral. Then the risk measure associated with L ψ reads ρ ψ (ν) = argmin ξ∈R ψ (y -ξ) p(y)dy and the first order condition gives ψ (y -ρ ψ (ν))p(y)dy = 0. Similarly, for any c ∈ R, we have ψ (y -ρ ψ (ν + c))p(y -c)dy = 0 since the density of ν + c is p(• -c). We now deduce from a simple change of variable z = y -c that ψ (z + c -ρ ψ (ν + c))p(z)dz = 0, which shows that ρ ψ (ν + c) -c is also a minimizer of ξ → ψ (y -ξ) p(y)dy. By uniqueness (ψ is strongly convex), we deduce that ρ ψ (ν + c) = ρ ψ (ν) + c.

Noise Additivity for Losses Derived From Potentials

Lemma 4 Assume L ψ is adapted to the linear bandit (ϕ, θ * ) and ψ is strongly convex and differentiable. Then there exists a stochastic process η such that the bandit is represented at time t by Y t ∼ θ * , X t + η t and ρ ψ (η|F t ) = 0.

Proof Define the process η at time t by η t = Y t -θ * , X t . To compute ρ ψ (ν|F t ), note that X t is measurable with respect to F t , therefore by Lemma 3 and the properties of conditional expectation, we have that ρ ψ (η

t |F t ) = ρ ψ (Y t |F t ) - θ * , X t = ρ ψ (ϕ ( θ * , X t ) |F t ) -θ * , X t =
0 by definition of L ψ being adapted to the bandit (ϕ, θ * ).

C PROOF OF LEMMA 1 AND PROPOSITION 1

Lemma 1 (Supermartingale Control) Under Assumptions 1-2, there exists σ > 0 such that for any t ∈ N and λ ∈ R d , the following holds:

E exp λ, X t ∂ 1 L * t - σ 2 2 λ, X t 2 ∂ 2 L * t F t 1 .
Proof Assumption 1 implies that ∂ 2 L * t m, therefore it is sufficient to show that there exists σ > 0 such that

E exp λ, X t ∂ 1 L * t - mσ 2 2 λ, X t 2 F t 1 . Since X t is F t -measurable, this is equivalent to E exp λ, X t ∂ 1 L * t F t exp mσ 2 2 λ, X t 2 ,
which follows from the sub-Gaussian property of the process ∂ 1 L * (Assumption 2).

Proposition 1 (Method of Mixtures with Convex Loss) Let β > 0. Under Assumptions 1-2, with probability at least 1 -δ, for all t ∈ N, it holds that

S t 2 H β t (θ * ) -1 σ 2 2 log 1 δ + log det H β t (θ * ) det βI d .
Proof The proof follows the method of mixture techniques, popularized in bandits by Abbasi-Yadkori et al. (2011).

For λ ∈ R d , we define the process

M λ t = exp λ S t -σ 2 2 λ 2 H 0 t (θ * ) .
We recall the expression of the Hessian

H 0 t (θ) = t-1 s=1 ∂ 2 L (Y s , θ, X s ) X s X s and that in particular λ 2 H 0 t (θ * ) = t-1 s=1 ∂ 2 L (Y s , θ, X s ) λ X s 2 .
This process is nonnegative and defines as supermartingale since

E M λ t+1 F t = E exp λ S t+1 - σ 2 2 λ 2 H 0 t+1 (θ * ) F t = E exp λ S t - σ 2 2 λ 2 H 0 t (θ * ) + ∂L (Y t , θ * , X t ) λ X t - σ 2 2 ∂ 2 L (Y t , θ * , X t ) λ X t 2 F t = exp λ S t - σ 2 2 λ 2 H 0 t (θ * ) E exp ∂L (Y t , θ * , X t ) λ X t - σ 2 2 ∂ 2 L (Y t , θ * , X t ) λ X t 2 F t exp λ S t - σ 2 2 λ 2 H 0 t (θ * ) (Lemma 1) = M λ t .
Now we construct a new supermartingale by mixing all the M λ . More formally, let Λ a R d -valued random variable independent of the rest and define

M t = E M Λ t F ∞ where F ∞ = σ t∈N F t .
M t = (βσ 2 ) d/2 (2π) d/2 R d exp -λ S t + σ 2 2 λ H 0 t (θ * ) + βI d λ dλ = (βσ 2 ) d/2 (2π) d/2 exp σ 2 2 λ H β t (θ * ) λ R d exp - σ 2 2 λ -λ H β t (θ * ) λ -λ dλ = β d det H β t (θ * ) 1 2 exp σ 2 2 λ H β t (θ * ) λ ,
where λ = 1 σ 2 H β t (θ * ) -1 S t and H β t (θ) = H 0 t (θ) + βI d is the regularized Hessian, which is positive definite and hence invertible. This expression further simplifies to

M t = det βI d det H β t (θ * ) 1 2 exp 1 2σ 2 S t 2 H β t (θ * ) -1 .
From there, the argument is standard: M λ is a nonnegative supermartingale, and therefore the pointwise limit M λ ∞ = lim t→+∞ M λ t exists almost surely (Doob's supermartingale convergence theorem, Ch. 11 in [START_REF] Williams | Probability with Martingales[END_REF]). Therefore for any F-stopping time τ , M λ τ is well-defined, and thus so is and M τ . By Fatou's lemma and Doob's stopping theorem, we have that

E[M τ ] = E[lim inf t→+∞ E[M t∧τ | F ∞ ]] lim inf t→+∞ E[E[M t∧τ | F ∞ ]] 1. Finally, the particular choice of τ = inf t ∈ N, S t 2 H β t (θ * ) -1 σ 2 2 log 1 δ + log det βI d det H β t (θ * )
and a straightforward application of Markov's inequality reveals that

P (τ < ∞) = P ∃t ∈ N, M τ 1 δ E[M τ ]δ δ ,
which is exactly the expected result.

D ASSUMPTION 1 =⇒ LEMMA 2

First, we recall the two assumptions of interest.

Assumption 1 (Bounded Loss Curvature) There exists m and M such that

∀y, ξ ∈ R, m ∂ 2 L(y, ξ) M .
We call the parameter κ = M m the conditioning of L.

Lemma 2 (Transportation of Local Metrics) Under Assumption 1, for α > 0, there exists κ > 0, β > 0 such that

Hα t (θ * , θt ) 1 κ H β t (θ * ) and Hα t (θ * , θt ) 1 κ H β t ( θt ) .
Now simple calculations show that:

Hα t (θ * , θt ) = t-1 s=1 1 0 ∂ 2 L(Y s , uθ * + (1 -u) θt , X s )duX s X s + αI d = t-1 s=1 1 0 ∂ 2 L(Y s , θ * , X s ) ∂ 2 L(Y s , uθ * + (1 -u) θt , X s ) ∂ 2 L(Y s , θ * , X s ) duX s X s + αI d m M t-1 s=1 ∂ 2 L(Y s , θ * , X s )X s X s + αI d = 1 κ t-1 s=1 ∂ 2 L(Y s , θ * , X s )X s X s + καI d = 1 κ H κα t (θ * ) ,
which is the desired result if β = κα. The other inequality with Hβ t ( θt ) is derived similarly.

E PROOF OF THEOREM 1

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

Theorem 1 (Regret upper bound for LinUCB-CR -1) Let δ ∈ (0, 1), α max(1, L 2 ) and define for t ∈ N the exploration bonus

γ t : x ∈ X t → c δ t x H κα t ( θt) -1 , c δ t = 2κ σ 2 log 1 δ + d log m α + log det V α m t + α κ S
and the projection operator

Π : θ ∈ R d → argmin θ∈Θ F α t (θ) -F α t ( θ) H κα t (θ) -1 .
Under Assumptions 1-2-3-4, with probability at least 1 -δ, the regret of Algorithm 1 is bounded by

R T 2c δ T max 1 √ m , L √ κα 2T d log 1+ mT L 2 dκα .
In particular, we have

R T = O κσd √ m √ T log T L 2 d .
Proof We will prove the regret bound in two steps. First, we justify the choice of exploration sequence (γ t ) t∈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 3.2, the cumulative regret up to time T , denoted by R T , is upper bounded with probability at least 1 -δ by 2

T t=1 γ t (X t ) provided that P ∀t T, ∆(X t , θt ) γ t (X t ) 1 -δ, where ∆(X t , θ) = | θ * -θ, X t | θ * -θt Hα t (θ * , θt) X t Hα t (θ * , θt) -1 .
Tuning of the Exploration Bonus Sequence The transportation of local metrics (Lemma 2, implied by the curvature bound of Assumption 1) reveals that θ * -θt Hα t (θ * , θt)

F α t (θ * ) -F α t ( θ t ) Hα t (θ * , θt) -1 + F α t ( θt ) -F α t ( θ) Hα t (θ * , θt) -1 √ κ F α t (θ * ) -F α t ( θ t ) H β t (θ * ) -1 + F α t ( θt ) -F α t ( θ) H β t ( θt) -1 .
Thanks to the supermartingale control of Lemma 1, we deduce from Corollary 1 that with probability at least 1 -δ, the following inequalities hold for all t T :

F α t (θ * ) -F α t ( θ t ) H β t (θ * ) -1 σ 2 log 1 δ + log det H β t (θ * ) det βI d + α θ * H β t (θ * ) -1 , F α t ( θt ) -F α t ( θ t ) H β t ( θt) -1 σ 2 log 1 δ + log det H β t ( θt ) det βI d + α θt H β t ( θt) -1 .
The prior bound on parameters (Assumption 3) yields θ

H β t (θ) -1 S √ β for θ ∈ {θ * , θt }. Furthermore, the curvature bound (Assumption 1) implies that H β t (θ) M V β/M t
, and therefore det

H β t (θ) M d det V β/M t
for θ ∈ {θ * , θt }. Combining this together and substituting the expression of β = κα, where κ = M m is the conditioning of the convex loss L, we obtain:

θ * -θt Hα t (θ * , θt) 2 √ κ σ 2 log 1 δ + d log m α + log det V α m t + α κ S .
By the same arguments, it holds that Hα t (θ * , θt ) -1 κH κα t ( θt ) -1 and therefore X t Hα

t (θ * , θt) -1 √ κ X t H κα t ( θt) -1 . This shows that γ t : x ∈ X t → 2κ σ 2 log 1 δ + d log m α + log det V α m t + α κ S =: c δ t x H κα t ( θt) -1
is a valid choice of exploration sequence.

Bounding the Regret Going back to the cumulative regret R T , we notice that (c δ t ) t=1,...,T is a positive, nondecreasing sequence, therefore we have with probability at least 1 -δ that

R T 2 T t=1 γ t (X t ) 2c δ T T t=1 X t H κα t ( θt) -1 .
A priori, the direct analysis of the right-hand side is tedious due to the dependency on θt in the local metric. However, we notice that the curvature bound (Assumption 1) also implies the weaker control

H κα t ( θt ) -1 1 m (V κα m t ) -1 , which translates to X t H κα t ( θt) -1 1 √ m X t (V κα m t
) -1 . This bound is less informative as it looses the local information carried by θ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, Abbasi-Yadkori et al. (2011)) and the Cauchy-Schwarz inequality.

Lemma 8 (Deterministic elliptic potential) Let (x t ) t∈N denote an arbitrary sequence of vectors in

B d • (0, L), ε > 0 and v t = t-1 s=1 x s x s + εI d ∈ S d (R) for t ∈ N. Then t s=1 x s v -1 s max(1, L √ ε ) 2td log 1+ tL 2 dε .
Note that this result holds in our case (with ε = κα m ) thanks to the prior bound on actions (Assumption 4).

Conclusion

With high probability, the regret of LinUCB with convex risk is bounded by

R T 2 T t=1 γ t (X t ) 2c δ T max 1 √ m , L √ κα 2T d log 1+ m¸T L 2 dκα .
Going back to the expression of c δ T , it follows from simple algebra (see e.g., Lattimore and Szepesvári (2020, proof of Lemma 19.4)) that det V

R T = O κσd √ m √ T log T L 2 d .
Impact of using the local Hessian metric H t versus the global metric V t To highlight the benefit of using local metrics, we detail here the regret bound obtained using the above proof with the natural global metric induced by V α/m (independent of the local point θ). Instantiating the positive definite matrix P to V α/m t instead of Hα (θ * , θt ) in the bound on the prediction error of Section 3.2 yields

∆(x, θt ) θ * -θt V α/m t x (V α/m t ) -1 = F α t (θ * ) -F α t ( θt ) Hα t (θ * , θt) -1 V α/m t Hα t (θ * , θt) -1 x (V α/m t ) -1 1 √ m F α t (θ * ) -F α t ( θt ) Hα t (θ * , θt) -1 x (V α/m t ) -1 2 κ m σ 2 log 1 δ + d log m α + log det V α m t + α κ S x (V α/m t ) -1 .
Similarly to the above proof, this shows that

γ global t : x ∈ X t → 2 κ m σ 2 log 1 δ + d log m α + log det V α m t + α κ S x (V α/m t ) -1
is also a valid choice of exploration sequence. Finally, a straightforward application of Lemma 8 shows the regret of the corresponding LinUCB-CR strategy is upper bounded with probability at least 1 -δ by

4 κ m σ 2 log 1 δ + d log m α + log det V α m t + α κ S 2T d log 1 + mT L 2 dα .
Compared to the local analysis, this improves the scaling of the regret in κ by a factor √ κ. However, it forces the use of the global metric

• (V α/m t ) -1 instead of the local one • H κα t ( θt) -1
, thus ignoring the precise shape of the loss function L. Looking at our proof, we see that κ and m fulfil two different roles.

√ κ is the price to pay in order to transport local metrics H α t (θ) between θ = θ * (true parameter) and θ = θt (estimate); it is paid once to bound the prediction error ∆(X t , θ) using the concentration bound of Proposition 1, and it is also paid a second time if local metrics are used in the exploration bonus when moving from Ht (θ * , θt ) -1 to Ht ( θt ) -1 (the former cannot be used directly in the algorithm as it depends on the a priori unknown paramter θ * ). On the other hand, m -1/2 is the price paid in both the local and global analyses to move from H t ( θt ) -1 to V -1 t in order to apply the elliptic potential lemma, which is in general incompatible with local metrics. A similar phenomenon is observed in the analysis of [START_REF] Faury | Improved optimistic algorithms for logistic bandits[END_REF]: the regret of their algorithm Logistic-UCB-1 (global) scales as √ κ while that of Logistic-UCB-2 (local) scales as κ. In addition to local metrics, Logistic-UCB-2 also makes use of an intricate projection step that allows for a new elliptic potential lemma compatible with local metrics, thus removing the factor m -1 (at least from the first order contribution to the regret in T ). We conjecture that a similar analysis could be unlocked in the present risk-aware setting and leave it open for future investigation.

We reiterate that in the logistic setting, κ is derived from self-concordance properties of the link function and is in particular independent of the curvature lower bound represented by m (it is in fact equal to 1 + 2S where S is an upper bound on the parameter space Θ, as in Assumption 3). By analogy with logistic bandits, we argue that the exact scaling in κ is likely not too harmful for the practical performances of Algorithm 1 and we therefore recommend the use of local metrics instead.

F PROOF OF THEOREM 2

In this section, we prove the regret bound of Theorem 2 in the stochastic i.i.d. actions setting of Assumption 5. We first state the full regret bound with an explicit higher order term.

Theorem 4 (Regret of LinUCB-CR with stochastic actions) Let δ ∈ (0, 1) and

t 0 = 8 ρ 2 X log 2 δ -2β mρ X L 2 .
Under Assumptions 1-2-3-4-5, for T t 0 , with probability at least 1 -2δ, the regret of Algorithm 1 is bounded by

R T 4c δ T 2T mρ X 1 + C √ T ,
where

C = 1 L 2 κα -4 mL 2 ρ X log 2 δ 2mρ X - 1 2L t 0 -1 + 2(κα -4mL 2 ρ X log 2 δ ) mρ X L 2 + 1 2 max 1, L m κα ρ X dt 0 log 1 + mL 2 t 0 dκα .
In particular, we have

R T = O κσ dT mρ X log T L 2 d .
The main difference with the proof of Theorem 1 is the use of an alternative stochastic elliptic potential lemma, mirroring the classical result of Lemma 8, that exploits the lower bound on the covariance of actions (Assumption 5). This proof technique is adapted from [START_REF] Kim | Double doubly robust thompson sampling for generalized linear contextual bandits[END_REF], although we use a different, sharper concentration result (Proposition 4 below).

Lemma 5 (Stochastic elliptic potential lemma)

Let β > 0, (θ t ) t∈N a sequence of vectors in Θ ⊆ R d and (X t ) t∈N a sequence of random variables in R d . Recall that H β t (θ t ) = t-1 s=1 ∂ 2 L(Y s , X s , θ t )X s X s +βI d and V β t = t-1 s=1 X s X s +βI d for t ∈ N.
Under Assumptions 4 and 5, let δ ∈ (0, 1) and

t 0 = 8 ρ 2 X log 2 δ -2β mρ X L 2 . For T t 0 , with probability at least 1 -δ, it holds that T t=1 X t H β t (θt) -1 2 2T mρ X 1 + C √ T ,
where

C = 1 L 2 β -4 mL 2 ρ X log 2 δ 2mρ X - 1 2L t 0 -1 + 2(β -4mL 2 ρ X log 2 δ ) mρ X L 2 + √ ρ X 2 max 1, L m β t 0 d log 1 + mL 2 t 0 dβ .
The intuition about this result is the following: if the matrix norms induced by H β t (θ t ) grow at least linearly in t, then the left-hand side should scale like , at the cost of an extra m -1/2 factor (in particular Lemma 5 holds for any sequence (θ t ) t∈N , not just the sequence of estimators used in the bandit algorithms). Because of the stochastic sampling of actions (Assumption 5), it is likely that the sequence (X t ) t∈N spans all directions of R d quite fast; in other words, each new X t X t will contribute at least a fixed amount to the sum that defines V β/m t , leading to the linear growth of the induced norms.

We formalize this intuition in Lemma 6 below, which relies on the following concentration bound in Hilbert spaces.

Proposition 4 (Time-uniform line crossing inequality for martingales with bounded increments in a Hilbert space) Let (H, •, • ) a Hilbert space and (M t ) ∈N a H-valued martingale (with respect to a filtration (F t ) t∈N ) such that M 0 = 0. Assume that there exists a sequence of positive scalars (c t ) t∈N such that M t+1 -M t c t for all t ∈ N, where • denotes the norm induced by the scalar product. Then for any η > 0 and δ ∈ (0, 1), it holds that

P ∃t ∈ N, M t 1 2η log 2 δ + η t s=1 c 2 s δ .
Interestingly, this concentration bound does not depend on the dimension of H, and in particular remains valid even if the ambient space is infinite-dimensional. Moreover, this bound controls the probability that any deviation occurs in the sequence ( M t ) t∈N , which is much stronger than controlling the deviation probability individually at each time t ∈ N. The proof relies on martingale arguments rather than a crude union bound over a finite set of individual deviation probabilities, which yields anytime (t ∈ N rather than t T for some known horizon T ) and typically tighter bounds.

Proof This result is directly taken from [START_REF] Howard | Time-uniform chernoff bounds via nonnegative supermartingales[END_REF]. More precisely, Howard et al. (2020, Theorem 1) shows a variety of equivalent time-uniform line crossing inequalities for martingales, and Howard et al. (2020, Corollary 10) applies this generic result to concentration of norm-like operators in Banach spaces. In order to get the most convenient form for our problem, we derive Proposition 4 from the generic theorem rather than the specific corollary.

The proofs of Pinelis (1992, Theorem 3) and Pinelis (1994, Theorem 3) reveals that for any λ ∈ R, the exponential process Howard et al. (2020, Theorem 1, (a))

L t = cosh (λ M t ) exp(-λ 2 2 t s=1 c s ) is a nonnegative F-supermartingale. Therefore,
shows that for any a, b > 0, P (∃t ∈ N, S t a + bV t ) 2e -aD (b) , In the next lemma, we show that the smallest eigenvalue of H β t (θ t ), which provides a lower bound to the corresponding induced norm, does indeed grow linearly with t on an event of high probability. For a given symmetric matrix A ∈ S d (R), we denote by λ min (A) its smallest eigenvalue.

where S t = M t , V t =
Lemma 6 (Smallest eigenvalue of H β t (θ t ) grows linearly with t with high probability) Under Assumptions 1-4-5, it holds that

P ∃t ∈ N, λ min H β t+1 (θ t+1 ) β - 4mL 2 ρ X log 2 δ + mρ X L 2 2 t δ .
Proof First notice that Assumption 1 implies

λ min H β t+1 (θ t+1 ) mλ min V 0 t+1 + β .
The idea is to relate λ min V 0 t+1 to the norm of some martingale in order to apply Proposition 4. In the stochastic actions setting (Assumption 5), a natural martingale is defined the following sum of random matrices:

M t = t s=1 X s X s -E X s X s |F s-1 = V 0 t+1 -V 0 t+1 ,
where we defined V 0 t+1 = t s=1 E X s X s |F s-1 . We recall that a consequence of Weyl's inequality on eigenvalues is that for any A, B ∈ S d (R), the following inequality holds:

λ min (A) + λ min (B) λ min (A + B) .
Applying this to A = M t and B = V 0 t+1 yields λ min (M t ) + λ min V 0 t+1 λ min V 0 t+1 . Now, notice that λ min (A) = -λ max (A) -A where • is the matrix norm induced by the scalar product A, B = Tr A B (also known as the Frobenius norm). Moreover, the conditional covariance lower bound of Assumption 5 and another application of Weyl's inequality imply that

λ min V 0 t+1 t s=1 λ min E X s X s |F s-1 ρ X L 2 t .
Combining these together, we obtain that for arbitrary a ∈ R and b > 0, the following inequality holds:

P ∃t ∈ N, λ min H β t+1 (θ t+1 ) a + bt P ∃t ∈ N, M t β -a m + ρ X L 2 - b m t . (1) Notice that M t+1 -M t = X t X t -E X t X t |F t-1 2L 2 (Assumption 4). Now if we choose b = 1 2 mρ X L 2 and a = β -4mL 2
ρ X log 2 δ , the bound from Proposition 4 holds with η = ρ X 8L 2 and δ ∈ (0, 1) and c t = 2L 2 , thus proving the result.

We are now ready to prove the stochastic elliptic potential lemma.

Proof of Lemma 5 We fix t 0 ∈ N arbitrarily for now and let T t 0 . We start by splitting the sum in two and by applying the deterministic elliptic potential lemma (Lemma 8) up to time t 0 :

T t=1 X t H β t (θt) -1 = t0 t=1 X t H β t (θt) -1 + T t=t0+1 X t H β t (θt) -1 1 √ m t0 t=1 X t V β/m t -1 + T t=t0+1 X t H β t (θt) -1 (Assumption 1) 1 √ m , L √ β 2t 0 d log 1 + mL 2 t 0 dβ + T -1 t=t0 X t+1 H β t+1 (θt+1) -1 (Assumption 4) . Now let E δ t = ∀t t, λ min H β t+1 (θ t+1 ) > β -4mL 2 ρ X log 2 δ + mρ X L 2 2 t .
It is clear that E δ t0 ⊆ E δ 0 , and thus by Lemma 6, P E δ t0 1 -δ. The choice t 0 = 8 ρ 2 X log 2 δ -2β mρ X L 2 implies that the right-hand side in the definition of E t0 is positive. On this event, we bound the second sum as follows:

T -1 t=t0 X t+1 H β t+1 (θt+1) -1 L T -1 t=t0 1 √ a + bt 2L b a + b(T -1) -a + b(t 0 -1) 2L b √ bT + √ a -a + b(t 0 -1) ,
where we use the shorthand a = β -4mL 2 ρ X log 2 δ and b = 1 2 mρ X L 2 (the penultimate line comes from sum-integral comparison while the last one follows from the inequality √ x + y √ x + √ y). After collecting the dominating term in √ T , the two sums give the following upper bound:

T t=1 X t H β t (θt) -1 2L T b 1 + C √ T with C = a b - a + b(t 0 -1) b + √ b 2L 1 √ m , L √ β 2t 0 d log 1 + mL 2 t 0 dβ .
Substituting a and b with their expressions yields the result.

We finally prove the regret bound in the stochastic i.i.d. actions setting.

Proof of Theorem 4

We follow the exact same steps as with Theorem 1 in order to bound the regret by

R T 2c δ T T t=1 X t -1 H κα t ( θt)
, with probability at least 1 -δ. The sum on the left-hand side is controlled by Lemma 5 also with probability at least 1 -δ.

A simple union argument over both events concludes the proof, resulting in a regret upper bound with probability at least 1 -2δ.

We conclude this section with two remarks.

Remark 9 (Dependency of ρ X on d) We recall that in the stochastic actions setting (Assumption 5), ρ X is a lower bound on the conditional covariance of actions, which can be equivalently formulated as ρ X L 2 λ min E X t X t |F t-1 for all t ∈ N. Following the argument of [START_REF] Kim | Doubly robust thompson sampling with linear payoffs[END_REF] in the case of unconditional covariance control, we obtain the following bound on ρ X :

dρ X L 2 dλ min E X t X t |F t-1 λ∈St λ = Tr E X t X t |F t-1 = E Tr X t X t |F t-1 L 2 ,
where S t denotes the spectrum of the symmetric matrix E X t X t |F t-1 and Tr the trace operator. Therefore ρ X d -1 . Moreover, [START_REF] Bastani | Mostly exploration-free algorithms for contextual bandits[END_REF]; [START_REF] Kim | Doubly robust thompson sampling with linear payoffs[END_REF][START_REF] Kim | Double doubly robust thompson sampling for generalized linear contextual bandits[END_REF] identified two families of examples where ρ X = O(d -1 ) in the unconditional case:

• If the distribution of X ∈ X t (marginal distribution of a each action) admits a density p with respect to the Lebesgue measure supported in B d • 2 (0, L) and such that p(x)

p min > 0 for all x ∈ B d • 2 (0, L), then ρ X = pmin (d+2) vol B d • 2 (0, 1
) is a suitable choice (Kim et al., 2022, Lemma C.1). In general, the volume of the Euclidean unit ball in

R d is vol B d • 2 (0, 1) = π d/2 Γ( d 2 +1) ∼ 1 √ dπ 2πe d d 2
, which goes to 0 when d → +∞. In certain cases though, such as the uniform and truncated Gaussian distributions, p min is proportional to vol B d • 2 (0, 1) , thus leading to ρ X = O(d -1 ).

• If the covariance matrix E XX exhibits a certain structure, for instance AR(1), tridiagonal or block diagonal, then ρ X = O(d -1 ), regardless of the marginal distributions.

Remark 10 (Previous results about the growth of the smallest eigenvalue) [START_REF] Kim | Doubly robust thompson sampling with linear payoffs[END_REF][START_REF] Kim | Double doubly robust thompson sampling for generalized linear contextual bandits[END_REF] prove similar results on the linear growth of the smallest eigenvalues of a different sequence of Hessian matrices. More precisely, they consider a fixed number K of arms, i.e., action sets of the form X t = {X k,t , k ∈ [K]} and Hessian matrices constructed from all actions

V [K] t+1 = k∈[K] t s=1 X k,s X k,
s , instead of using only the actions played at previous time steps. This is made possible in their analyses by resorting to a doubly robust imputation of unobserved rewards associated to unplayed actions, which is significantly different from our approach. One theoretical benefit of their method is that the sequence (V

[K]

t+1 ) t∈N can be more easily transformed into a F-martingale using only the unconditional lower bound on the covariance, as opposed to the conditional one of Assumption 5.

Of note, [START_REF] Li | Provably optimal algorithms for generalized linear contextual bandits[END_REF] also questions the feasibility of a linear lower bound on the smallest eigenvalue of V 0 t+1 but concludes that it requires more stringent assumption as Lai and Wei (1982, Example 1) seemingly provides a counterexample of sublinear growth in the context of a regression problem. However, this counterexample studies autoregressive actions instead of i.i.d. action sets, which leads to E X t X t |F t-1 → 0 when t → +∞. Therefore, this is different from what we consider in Assumption 5 and does not invalidate our analysis.

G PROOFS OF OGD CONCENTRATION

We reformulate below Proposition 2 in full details and provide a proof of the OGD regret.

Proposition 5 (OGD Regret, Sub-Gaussian Gradients) Let C a convex subset of R d and Π the projection operator onto C. For j = 1, . . . , N , let j : C -→ R + a twice differentiable convex function and a, A > 0 such that aI d ∇ 2 j (z) AI d for all z ∈ C. Define the OGD update at step j by z j = Π(z j-1 -ε j-1 ∇ j (z j-1 )) and zn = arg min z∈C n j=1 j (z). Assume that there exists z * ∈ C such that ∇ j (z * ) = g j + α n z * with α 0 and g a centered, R d -valued σ-sub-Gaussian process, and also that C is bounded, i.e diam(C) = sup z,z ∈C z -z < ∞. Then with probability at least 1-δ, the OGD regret with step size ε j = 3 aj is bounded for all n N by

n j=1 j (z j ) -j (z n ) 9 2a 2dσ 2 log 2dN δ + A 2 diam(C) 2 + α 2 n 2 z * 2 (1 + log n) .
This can be written more concisely as N j=1 j (z j )j (z N ) = O( dσ 2 a log 2 N ) when N → +∞. In addition, if g is uniformly bounded by a constant G > 0, the regret with step size ε s = 1 aj can be reduced to the almost sure bound:

n j=1 j (z j ) -j (z n ) G 2 2a (1 + log n) .

Sub-Gaussian Gradients

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

Notice that ∇ j (z j ) = g j + α n z * +∇ j (z j )-∇ j (z * ) and that there exists zn ∈ [z j , z * ] ⊂ C such that ∇ j (z j )-∇ j (z * ) = ∇ 2 j (z n ) (z j -z * ) thanks to the mean value theorem and the convexity of C. This yields

∇ j (φ j ) 2 3 g j 2 + 3α 2 n 2 z * 2 + 3 ∇ j (z j ) -∇ j (z * ) 2 3 g j 2 + 3α 2 n 2 z * 2 + 3A 2 j -z * 2 , since ∇ j is A-Lipschitz.
Combining this with the above yields

∇ j (z j ), z j -zn 3 2 z j -zn 2 -z j+1 -zn 2 ε j + 3 2 ε j g j 2 + 3 2 ε j α 2 n 2 z * 2 + 3 2 ε j A 2 z j -z * 2 3 2 z j -zn 2 -z j+1 -zn 2 ε j + 3 2 ε j g j 2 + α 2 n 2 z * 2 + 3 2 ε j A 2 diam(C) 2 .
The online regret of OGD is therefore

n j=1 j (z j ) -j (z n ) 3 2 n j=1 z j -zn 2 -z j+1 -zn 2 ε j - a 3 z j -zn 2 + 3 2 A 2 diam(C) 2 n j=1 ε j + 3 2 n j=1 ε j g j 2 + α 2 n 2 z * 2 .
As in the bounded case, the choice ε j = 3 aj makes the first sum vanish. Moreover, a simple union argument over the Chernoff bound for the σ-sub-Gaussian random variables (g j ) j=1,...,n reveals that

E n = ∀j = 1, . . . , n, g j σ 2d log 2dn δ
holds with probability at least 1 -δ for δ ∈ (0, 1). Therefore, the following holds with probability at least 1 -δ:

n j=1 ε j g j 2 n j=1 ε j g j 2 I En 2dσ 2 log 2dn δ n j=1 ε j .
Therefore, with probability at least 1 -δ, we obtain the following online regret:

n j=1 j (z s ) -j (z n ) 3 2 2dσ 2 log 2dn δ + A 2 diam(C) 2 + α 2 n 2 z * 2 n j=1 ε j = 9 2a 2dσ 2 log 2dn δ + A 2 diam(C) 2 + α 2 n 2 z * 2 n j=1 1 j 9 2a 2dσ 2 log 2dn δ + A 2 diam(C) 2 + α 2 n 2 z * 2 (1 + log n) .

H PROOFS OF THEOREM 3

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.

Theorem 3 (Regret of LinUCB-OGD-CR) Let ε h > 0 and h

= 2ε h ρ X L 2 + 8 ρ 2 X log 2 δ . Assume that ∂L(Y t , θ * , X t ) is √ mσ-sub-Gaussian for all t T .
Under Assumptions 1-2-3-4-5, there exists constants C, C > 0 such that with probability at least 1 -(1 + T /h)δ the regret of Algorithm 2 with exploration bonus sequence

γ OGD t,T : x ∈ X t → (c δ t + c OGD,δ t,T ) x H κα t ( θOGD t-1 h ) -1 , c OGD,δ t,T = L 2 + α mM t 2κC dh 2 σ 2 ε 2 h log 2dT hδ log t h ,
and the OGD step sequence of Proposition 2 satisfies

R T = O σ κdT mρ X κ log T L 2 d + h log (dT ) . Proof Let j (θ) = h k=1 L(Y (j-1)h+k , θ, X (j-1)h+k ) + α 2N θ 2 2 , where N = T -1 h
denotes the total number of episodes of length h. For simplicity, we assume that θt = θ t for all t T , i.e., the empirical risk minimizer is always in the stable set of the projection operator Π. We recall that n j=1 ∇ j ( θt ) = 0 for n = t-1 h (i.e., after episode n, when θ OGD n is updated). In the general case, replacing θ t by θt induces an extra correction factor in the inequalities below which is at most polylogarithmic in T (a consequence of Corollary 1), and hence does not change the conclusion. Again, we point out that, similarly to the generalized linear bandit setting [START_REF] Filippi | Parametric bandits: The generalized linear case[END_REF][START_REF] Faury | Improved optimistic algorithms for logistic bandits[END_REF], θ t is often in the stable set of Π in practice.

We use the notations of Proposion 2 and define:

z j = θ OGD j , zn = θt , z * = θ * .
We also denote by zn = θOGD n = 1 n n j=1 z j the average of the past n OGD updates.

Bound on zn -zn 2 Without loss of generality, we assume here that ∂L * is a √ mσ sub-Gaussian process (this follows in variety of settings from the discussion of Assumption 2 and Lemma 1; the conclusions are essentially unchanged when assuming only Assumption 2, at the cost of slightly heavier notations).

We first note that ∇ j (θ * ) = g j (θ * ) + α N θ * , where g j (θ * ) = h k=1 ∂L * (j-1)h+k and j ∈ [N ], is √ hmσ-sub-Gaussian (sum of h random variables, each of them being drawn from a √ mσ-sub-Gaussian distribution). Setting the episode length to

h = 2ε h ρ X L 2 + 8 ρ 2 X log 2
δ makes the one-step losses j mε h -strongly convex with high probability. Indeed, let us define for

h ∈ N the function f (h ) = ρ X L 2 2 h -4L 2 ρ X log 2 δ and the event E j,h = λ min h k=1 X (j-1)h +k X (j-1)h +k > f (h ) .
First, notice that E j,h ⊇ h ∈N E j,h and that h k=1 X (j-1)h +k X (j-1)h +k has the same distribution as V 0 h +1 by Assumption 5.

We deduce from Lemma 6 applied to V 0 h+1 (that is with β = 0 and m = 1), that

P (E j,h ) P( h ∈N E j,h ) = P ∀h ∈ N, λ min V 0 h +1 > - 4L 2 ρ X log 2 δ + ρ X L 2 2 h 1 -δ .
In particular for the value of h defined above, we have E j,h ⊆ λ min h k=1 X (j-1)h +k X (j-1)h +k ε h , which gives the mε h -strong convexity of j by the usual minoration ∂ 2 L m (Assumption 1). In the rest of this proof, we assume to be on the event

j∈[N ]
E j,h , the probability of which is at least 1 -N δ by a simple union argument. Now, we apply the bound on the OGD regret of Proposition 5 with a = mε h , A = hM L 2 , namely that the good event

∀n N, n-1 j=1 j (z j ) -j (z n ) C dhσ 2 ε h log 2dN δ log(n) ,
holds with probability at least 1 -δ, for some constant C > 0 (in which we hide the dependency on h, M, L, α and S to avoid further cluttering). We assume to be on this event in the rest of the proof, which we combine to the previous events with a union argument, leading to a probability ot at least 1 -(N + 1)δ.

The crux of the argument is similar to the proof of Lemma 2 in [START_REF] Ding | An efficient algorithm for generalized linear bandit: Online stochastic gradient descent and thompson sampling[END_REF] and exploits the strong of the losses j to relate the online regret to a control on the distance zn -zn . By Jensen's inequality, we have

n j=1 j (z n ) -j (z n ) Cdhσ 2 ε h log 2dN δ log(n) .
Strong convexity also implies the following inequality:

j (z n ) -j (z n ) ∇ j (z n ), zn -zn + mε h 2 zn -zn 2 2 .
Summing over j = 1, . . . , n and exploiting the fact that the sum of gradients vanishes at zn , we obtain after some simple algebra:

zn -zn ) -1 using an elliptical potential lemma (since we operate under Assumption 5 for the strong convexity of the episodic losses j , we use the strong regret guarantee provided by Lemma 5; note that the high probability event on which this lemma applies is already included in the above events, for a total probability of at least 1 -(N + 1)δ).

Remark 11 (The importance of strong convexity) The key argument behind the proof of Theorem 3 is that the aggregated loss over an episode n : θ ∈ Θ → Scaling of episode length h As shown in the proof, non-vanishing strong convexity of n can be deduced from a fixed lower bound on the smallest eigenvalue of the Hessian of n . By Lemma 6, this holds with high probability provided the episode length h is high enough, which translates to h = 2ε h ρ X L 2 + 8 ρ 2 X log 2 δ . Using the typical bound ρ X = O(d -1 ), we see that h scales like O(d 2 ) in the action dimension. By comparison, the only similar OGD scheme for generalized linear bandit scales like O(d 3 ) [START_REF] Ding | An efficient algorithm for generalized linear bandit: Online stochastic gradient descent and thompson sampling[END_REF], Lemma 2 and Remark 2), thus suffering to a greater extent from the curse of dimensionality. Note the practical tradeoff on h faced by the agent running Algorithm 2: the higher h, the more likely it is that the OGD estimator θOGD well approximates the true empirical risk minimizer θ (because of stronger convexity of the episodic losses); however, it also means longer episodes and thus less frequent updates of θOGD , i.e., less learning.

Note that the value of h is derived from a concentration bound that is uniform in h (Lemma 6). However, since h is kept constant throughout the run of the algorithm, a similar, non-uniform result would actually be sufficient (we chose to use Lemma 6 mainly for the sake of convenience, since we already assumed to be on the corresponding good event in order to mirror the regret analysis of Theorem 4). It is actually possible to tighten the lower bound on h using a finer, non-uniform concentration result, which we state below.

Lemma 7 (Tighter bound on the episode length h) Under Assumptions 4 and 5, let ε h > 0, δ ∈ (0, 1) and define

h =      1 4ρ 2 X    2(1 + γ δ ) log 2 δ 1 + 1 γ δ + 2(1 + γ δ ) log 2 δ 1 + 1 γ δ + ρ X ε h L 2    2     
,

where γ δ = -1 1+W-1(-δ 2 4e )
and W -1 is the first lower branch of the Lambert W function, i.e., the smallest real solution for z = [-1 e , 0) of the equation W -1 (z)e W-1(z) = z. It holds that

P λ min V 0 h+1 ε h δ .
Proof The idea is similar to that of the proof of Lemma 6, i.e., relate the deviation of the smallest eigenvalue to that of a matrix martingale. The difference lies in the choice of the concentration bound for this martingale. .

In particular, we have

P   M h c 2h(1 + γ δ ) log 2 δ 1 + 1 γ δ   δ .
Following the steps of Lemma 6, we have that

P λ min V 0 h+1 ε h P M h ρ X L 2 h -ε h δ ,
with M h = V 0 h+1 -E V 0 h+1 , which is a martingale with increments bounded by c = 2L 2 . Equating both bounds on M h yields

ρ X L 2 h -2L 2 2h(1 + γ δ ) log 2 δ 1 + 1 γ δ -ε h = 0 .
This expression is a quadratic equation in H = √ h. Let a = ρ X L 2 and b = L 2 2h(1 + γ δ ) log 2 δ 1 + 1 γ δ . Notice that both a and b are positive and that the discriminant of aH 2 + 2bH -ε h = 0 is 4b 2 + 4aε h , which is also positive. The only positive solution is thus given by

√ h = H = b+2 √ b 2 +aε h 2a
, which concludes the proof.

The value of h recommended by Lemma 7 scales with ρ -2 X at the first order, and thus h = O(d 2 ), just like in Theorem 4. However, it is typically smaller, and thus more practical (allows for more frequent OGD updates with the same theoretical guarantees). We report in Figure 2 the numerical values for both expressions of h for typical choices of the parameters L, ε h and δ as a function the dimension d. In practice, even smaller values of h may ensure enough convexity of the episodic losses to observe sublinear regret, which we empirically witnessed in the experiments (see Appendix I). For the practitioner, h may be viewed as a hyperparameter to be tuned manually, potentially on an instance-dependent basis, with Theorem 4 and Lemma 7 giving only worst-case guarantees.

I EXPERIMENTS

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

  Proceedings of the 26 th International Conference on Artificial Intelligence and Statistics (AISTATS) 2023, Valencia, Spain. PMLR: Volume 206. Copyright 2023 by the author(s).

Figure 1 :

 1 Figure 1: Two-armed linear 10%-expectile bandit with R 3 contexts and expectile-based asymmetric noises. 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.

Proposition 3

 3 Let I ⊆ R * + an open set and {ν σ , σ ∈ I} a family of probability distributions such that (i) the expectation mapping σ ∈ I → E Y ∼νσ [Y ] is constant, (ii) both the call and put mappings C(•, K): σ ∈ I → E Y ∼νσ (Y -K) + and P (•, K) : σ ∈ I → E Y ∼νσ (K -Y ) +are differentiable and nondecreasing, for any K ∈ R.

  e p (σ)) = ∂ σ C(σ, e p (σ)) + ∂ K C(σ, e p (σ)) e p (σ)) = ∂ σ P (σ, e p (σ)) + ∂ K P (σ, e p (σ)) d dσ e p (σ) ,

  c δ T = O κσ d log T L 2 d when T → +∞. A simpler asymptotic bound on the regret is therefore

  without the extra O( √ log T ) factor present in Lemma 8. The lower curvature bound of Assumption 1 shows that it is enough to look at the norms induced by V β/m t

  and D(b) = 2b. Equating the right-hand side to δ and letting b = η concludes the proof, with a = 1 2η log 2 δ .

  (n-1)h+k , θ, X (n-1)h+k ) + α 2N θ 2 2 is mε h strongly convex. With simple convexity only, the online regret guarantee of the OGD approximation scales like O( √ T ) instead of logarithmically. This would only guarantee θOGDn -θt 2 = O( √ t), resulting in linear O(T ) bandit regret after multiplying this term with the contribution of the elliptic potential lemma. Moreover, although n is always trivially at least α N -strongly convex, it is necessary to ensure non-vanishing strong convexity when T → +∞ (we recall that N = T -1 h ). Indeed, substituting ε h with α N in the regret bound above gives R T O(ε -1 h ) = O(T ).

Figure 2 :

 2 Figure 2: Recommended episode length h= 2ε h ρ X L 2 + 8 ρ 2 X log 2δ for LinUCB-OGD-CR (Algorithm 2) according to Theorem 3 and Lemma 7 as a function of d = ρ -1 X , for typical values L = 1, ε h = 0.1 and δ = 5%.

Table 1 :

 1 Example of Risk Measures Elicited by Convex Potentials.

	Name	Potential ψ(z) Risk measure ρ ψ
	Mean	z 2 /2	ρ

ψ = yν(dy)

  [START_REF] Li | Provably optimal algorithms for generalized linear contextual bandits[END_REF];[START_REF] Kim | Double doubly robust thompson sampling for generalized linear contextual bandits[END_REF] considered a lower bound on the unconditional average covariance across arms E

Table 2 :

 2 Runtimes for the Classical LinUCB and Algorithms 1 (LinUCB for Convex Risk) and 2 (LinUCB-OGD for Convex Risk), Reported in Seconds as Mean ± Standard Deviation, Estimated Across 500 Independent Replications with Time Horizon T = 1500.

	Algorithm	Runtime
	LinUCB (mean)	37.2 ± 4.9
	LinUCB-CR (expectile)	814.8 ± 88.3

  If Λ has density p with respect to the Lebesgue measure, this means that M t = R d M λ t p(λ)dλ. For the choice Λ ∼ N (0, 1 βσ 2 I d ) with β > 0, we have, by completing the square in the exponential:

  The first term can be controlled by transportation of local metrics in the same way as in the proof of Theorem 1, i.e.,θ * -θt Hα ) -F α t ( θ t ) H β t (θ * ) -1 + F α t ( θt ) -F α t ( θ) H β t ( θt) -1 ,and thus this term adds the same contribution to the design of the exploration bonus sequence and to the regret bound. For the second term, we apply the previous bound on zn -zn 2 = θOGDThe rest of the proof is now identical to that of Theorem 4, i.e., we use the exploration bonus sequence γ OGD t,T : x ∈ X t → (c δ t + c OGD,δ

							t,T		) x H κα t ( θOGD t-1	) -1 ,
										h
		T
	and control	t=1	X t H κα t ( θOGD t-1 h
					2 2	2Cdhσ 2 mε 2 h n	log	2dN δ	log(n) .
										α
										m
										t
					θ α m	θOGD n	-θt 2 .
			t (θ * , θOGD n )	√	κ F α t (θ n	-θt 2 . Combining these two inequalities results
	in the following control:
	θ c δ t	+	L 2 +	α mM t	2κCdh 2 σ 2 ε 2 h	log	2dT hδ	log	t h
				same as in
				the proof of
				Theorem 1

Regret Analysis of LinUCB-OGD Mirroring the regret proof of LinUCB, we see that we need ∀t T, ∆(X t , θOGD n ) γ t (X t ) to hold with high probability, for a certain exploration sequence (γ t ) t∈N . This amount to controlling the following norm:

θ * -θOGD n Hα t (θ * , θOGD n ) θ * -θt Hα t ( θt, θOGD n ) + θOGD n -θt Hα t ( θt, θOGD n ) θ * -θt Hα t (θ * , θOGD n ) + √ M θOGD n -θt V * -θt Hα t (θ * , θOGD n ) + M L 2 t + * * -θOGD n Hα t (θ * , θOGD n ) =: c OGD,δ t,T = O(σL √ κd log T )

.

Acknowledgements

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). We also thank the organizers and attendees of the European Workshop on Reinforcement Learning (EWRL) 2022, where this work was initially presented.

Proof Let j n. The uniform lower bound on the Hessian of j makes it a-strongly convex, which implies j (z j )j (z) ∇ j (z j ), z j -zn -a 2 z -z j 2 .

By definition of the OGD scheme, the following holds: z j+1 -zn 2 = Π (z j -ε j ∇ j (z j )) -zn 2 z j -ε j ∇ j (z j ) -zn 2 (projection onto a convex set) z j -zn 2 + ε 2 j ∇ j (z j ) 2 -2ε j ∇ j (z j ), z j -zn , from which we deduce

Bounded Gradients

This case is covered by Theorem 3.3 in [START_REF] Hazan | Introduction to online convex optimization[END_REF]. We reproduce the proof here for reference and as a first step toward the more general setting of sub-Gaussian gradients.

Let G > 0 be such that ∇ j (z j ) G for all j = 1, . . . , n. This allows to upper bound the above equation, leading to

The online regret of OGD is therefore

The first sum can be rewritten after a simple index shift and the convention 1/ε 0 := 0:

for the choice ε j = 1 aj . Consequently, the online regret can be simplified as

Computing Expectiles We detail two cases of distributions for which expectiles are known. For p ∈ (0, 1), we denote by e p (ν) the p-expectile of distribution ν.

• If ν = N (0, 1), then, letting φ and Φ be the pdf and cdf of ν respectively, we obtain after simple calculus and the identity φ (y) = -yφ(y) the following fixed point equation:

from which one can estimate the value of e p (ν) using a fast iterative scheme. The general Gaussian case ν = N µ, σ 2 is then easily deduced from the relation e p (ν) = µ + σe p (N (0, 1)). Expectile calculations for a few other classical distributions are covered in [START_REF] Philipps | Interpreting expectiles[END_REF].

• If ν is the so-called expectile based distribution [START_REF] Torossian | Bayesian quantile and expectile optimisation[END_REF][START_REF] Arbel | Multivariate expectile-based distribution: properties, bayesian inference, and applications[END_REF] with asymmetric density (with respect to the Lebesgue measure) given by

then e p (ν) = µ. 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).

We recall that the p-expectile can be elicited by the convex potential

The second derivative of this potential is given by ψ (z) = 2(1 -p)I z<0 + 2pI z>0 , which is bounded between 2p and 2(1 -p). In particular, Assumption 1 holds with conditioning

Note that the two classes of distributions considered above are Gaussian or log-concave, which fits the scope of the supermartingale control of Lemma 1.

Computing Entropic Risk For a distribution ν, the entropic risk at level γ > 0 takes the form ρ γ (ν) = 1

γ log E Y ∼ν e γY and corresponds to the loss L : (y, ξ) → ξ + 1 γ (e γ(y-ξ) -1). Derivatives of this loss satisfy the following identities, where ∂ represents the differentiation operator with respect to the second coordinate ξ:

and is thus in particular strictly convex.

For a Bernoulli-like distribution ν = pδ a + (1 -p)δ b , with p ∈ (0, 1), a, b ∈ R, the entropic risk takes the simple form ρ γ (ν) = 1 γ log pe γa + (1 -p)e γb . If ν has a bounded support with diameter D, then it is clear that the Hessian of the loss is controlled by m = γe -γD ∂ 2 L γe γD = M , and therefore the conditioning number of the loss κ can be bounded by e 2γD . Finally, ν being bounded also fits the scope of the supermartingale control of Lemma 1.

General Case If a density p and a loss function L are known, one may resort to numerical integration to approximate the following quantity up to arbitrary precision:

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 ξ → i w i L(y i , ξ)p(y i ) to estimate ρ L (ν).

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

k , with µ k and σ k chosen such that the expectile of the corresponding noise is zero for k ∈ {1, 2}. This can be achieved with e.g., µ 1 ≈ 0.44, σ 1 = 0.5 and µ 2 ≈ 2.62, σ 2 = 3, which was the setup for this experiment. Note that for a given expectile level p ∈ (0, 1) and standard deviation σ, finding the unique mean µ such that N µ, σ 2 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.

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 X t = {X 1 t , X 2 t } ⊂ R 3 where:

• We set the action noise to an arbitrary value σ x = 0.1.

• (Z 1 t , Z 2 t ) t∈N are all independent random variables.

This construction results in bounded, anisotropic actions. We chose θ * = [0.9 0 1] , so that θ * , X 1 t is likely higher than θ * , X 2 t , thus favoring X t = X 1 t in the expectile model Y t = θ * , X t + η t . To model the zero p-expectile noise η t with p = 10%, we used the expectile based distribution presented above with µ 1 = µ 2 = 0 and σ 1 = 0.5 if action X 1 t is played, and σ 2 = 1.5 otherwise, resulting in different mean noise E[η t |F t ] ≈ 1.8 and E[η t |F t ] ≈ 3.3 respectively. As in the previous example, this setting was designed to deceive the mean criterion by inverting the order of optimal actions. Experiment 3: Multi-armed Bernoulli Bandit with Entropic Risk Noise The last experiment consisted of K = 2 Bernoulli-like arms ν 1 = 1 2 δ 1 + 1 2 δ -1 and ν 2 = 1 4 δ 2 + 3 4 δ -2 , which corresponds to means µ 1 = 0, µ 2 = -1 and entropic risk ρ γ (ν 1 ) ≈ 0.43 and ρ γ (ν 2 ) ≈ 0.67 at level γ = 1. Again, this setting was designed so that the best optimal arm is different under the mean and entropic risk criteria.

Results On each of the three settings, we ran an instance of Algorithm 1, i.e., LinUCB (convex risk), and Algorithm 2, i.e., LincUCB-OGD (convex risk). We also ran a standard LinUCB algorithm for the mean criterion (Abbasi-Yadkori et al., 2011). Hyperparameters m, M and κ were tuned according to the analysis above. Regularization was fixed at λ = 0.1. As is customary in bandit experiments, the parameter σ, 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 σ = 0.1 in experiments 1 and 2 and at σ = 1 in experiment 3. For the LinUCB-OGD variant, the step size for the OGD scheme was set to ε n = 0.1/n, following the linear decay suggested by Proposition 2, 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 θ.

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 3 reproduces the results of each experiments across 500 independent replications. Finally, average runtimes for each algorithm are reported in Table 4. 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 × 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. LinUCB-OGD-CR (convex risk) 20.4 ± 3.9 60.2 ± 12.0 25.7 ± 4.9