Risk-aware linear bandits with convex loss

Patrick Saux, Odalric-Ambrym Maillard

Abstract

In decision-making problems such as the multi-armed 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 risk-aware 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

Standard contextual bandit algorithms typically aim to maximize the expected mean reward. However, in high-stakes environments like healthcare or finance, the mean often fails to capture "tail risk"—the potential for rare but catastrophic outcomes. To address this, "risk-aware" decision-making optimizes alternative statistics of the reward distribution, such as expectiles or entropic risk.

The primary challenge lies in the sequential estimation of these complex risk measures. This paper introduces a framework for risk-aware linear bandits where the risk measure is assumed to be a linear function of the context, enabling the use of powerful linear bandit geometries for non-linear reward statistics.

Methodology

The core of the proposed approach is the concept of elicitability. A risk measure is elicitable if it can be expressed as the minimizer of a specific convex loss function.

Examples of elicitable risk measures and their associated potential functions.

As shown in the table above, the mean minimizes squared error, while expectiles minimize an asymmetric least-squares loss. The authors leverage this by assuming the risk measure $\Phi$ is a composition of a linear mapping $\ell^*$ and a risk functional $\varphi$.

Structural mapping of contexts to risk measures via linear functions.

Algorithms

  1. LinUCB-CR (Convex Risk): Extends LinUCB by using Empirical Risk Minimization (ERM) with a convex loss tailored to the risk measure. It constructs optimistic confidence ellipsoids using time-uniform confidence sequences derived from the "method of mixtures" for supermartingales.
  2. LinUCB-OGD-CR: To reduce the computational burden of solving a full optimization problem at each step, this variant uses Online Gradient Descent (OGD) to approximate the solution, maintaining sublinear regret with significantly improved speed.

Key Insights

  • Curvature and Learnability: The statistical difficulty of estimating a risk measure is tied to the curvature of its loss function. Flatter loss functions (often associated with extreme tail risks) require more samples for accurate estimation.
  • Linearity Assumption: By assuming the risk measure itself is linear in the context, the framework can handle non-linear reward statistics while retaining the efficiency of linear models.
  • Efficiency via Approximation: The success of the OGD-based variant demonstrates that perfect optimization is not required at every step to achieve good regret performance.

Experimental Results

The algorithms were tested in three environments: Gaussian bandits with expectile noise, linear bandits with asymmetric noise, and Bernoulli bandits with entropic risk.

  • Theoretical Performance: LinUCB-CR achieves $\mathcal{O}(d\sqrt{T} \log T)$ regret, matching standard linear bandit bounds.
  • Computational Efficiency: The OGD variant was over 13x faster than the exact ERM version in a 1500-step horizon.
  • Risk Mitigation: Unlike standard LinUCB, which was misled by noisy distributions into choosing risky arms, the proposed algorithms successfully identified safer, optimal arms.

Conclusion and Future Work

While this framework provides a robust foundation for risk-aware bandits, it currently requires smooth, twice-differentiable loss functions, excluding measures like quantiles. Future work could explore smoothing techniques for non-smooth losses, higher-order elicitability for measures like CVaR, and non-linear extensions using Kernel or Neural bandits.

Summary updated

Abstract

In decision-making problems such as the multi-armed 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 risk-aware 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.
BibTeX
@inproceedings{saux2023risk,
  author = {Patrick Saux and Odalric-Ambrym Maillard},
  title = {{Risk-aware linear bandits with convex loss}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2023},
  url = {https://openreview.net/forum?id=UGbdJZ8Qah},
}
Figure