Covariance-adapting algorithm for semi-bandits with application to sparse rewards

Pierre Perrault; Vianney Perchet; Michal Valko

stat.MLApr 15, 2026

Covariance-adapting algorithm for semi-bandits with application to sparse rewards

Authors: Pierre Perrault, Vianney Perchet, Michal Valko

Organizations: Inria Lille & ENS Paris-Saclay · ENSAE & Criteo AI Lab · DeepMind Paris

Abstract

We investigate stochastic combinatorial semi-bandits, where the entire joint distribution of outcomes impacts the complexity of the problem instance (unlike in the standard bandits). Typical distributions considered depend on specific parameter values, whose prior knowledge is required in theory but quite difficult to estimate in practice; an example is the commonly assumed sub-Gaussian family. We alleviate this issue by instead considering a new general family of sub-exponential distributions, which contains bounded and Gaussian ones. We prove a new lower bound on the expected regret on this family, that is parameterized by the unknown covariance matrix of outcomes, a tighter quantity than the sub-Gaussian matrix. We then construct an algorithm that uses covariance estimates, and provide a tight asymptotic analysis of the regret. Finally, we apply and extend our results to the family of sparse outcomes, which has applications in many recommender systems.

Figures & tables

Panel of Figure 1 — Figure 1: Confidence regions build by escb-c (the pseudo-ellipse), and cucb-kl (the rectangle), for $\mathopen{}\mathclose{{\left\|\cdot}}\right\|_{1}$ constrained outcomes. Notice that cucb-kl has slightly better confidence intervals along the axis, but that escb-c is better in the direction ${\bf e}_{\mathopen{}\mathclose{{\left\{1,2}}\right\}}$ .

(A_{t},{\boldsymbol{\mu}}_{t})\in\argmax_{A\in\mathcal{A},~{\boldsymbol{\mu}}\in\mathcal{C}_{t}(A)}{\bf e}_{A}^{\mathsf{\scriptscriptstyle T}}{\boldsymbol{\mu}}.

Algorithm 1 escb-c (Efficient Sampling for Combinatorial Bandits with Covariance estimate )

(A_{t},{\boldsymbol{\mu}}_{t})\in\argmax_{A\in\mathcal{A},~{\boldsymbol{\mu}}\in\mathcal{C}_{t}}{\bf e}_{A}^{\mathsf{\scriptscriptstyle T}}{\boldsymbol{\mu}}.

Algorithm 2 escb-c modified for the case of

\mathopen{}\mathclose{{\left\|\cdot}}\right\|_{1}

-constrained outcomes

Panel of Figure 2 — Figure 2: Left : Correlation matrix of the dataset, right : Cumulative regret, averaged over $36$ independent simulations

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 3 — Figure 3: Confidence regions build by escb-c (the pseudo-ellipse), and cucb-kl (the rectangle), for $\mathopen{}\mathclose{{\left\|\cdot}}\right\|_{1}$ constrained outcomes. Notice that cucb-kl has slightly better confidence intervals along the axis, but that escb-c is better in the direction ${\bf e}_{\mathopen{}\mathclose{{\left\{1,2}}\right\}}$ .

Multi-Armed Bandits

Multi-Armed Bandits study how to choose among uncertain actions over time while balancing immediate rewards with learning.

See all 338 papers

Learning to Sparsify Stochastic Linear Bandits
May 11, 2026Zhengmiao Wang, Ming Chi, Zhi-Wei Liu +2Multi-Armed Bandits Exploration-Exploitation Tradeoff
School of Artificial Intelligence and Automation, Huazhong University of Science and Technology, Wuhan 430074, China · Department of Electronics and Telecommunications, Politecnico di Torino, 10129 Torino, Italy
Optimal and Efficient Contextual Combinatorial Semi-bandits with General Function Approximation
Jul 15, 2026Hao Qin, Chicheng ZhangContextual Bandits Combinatorial Multi-Armed Bandits
The University of Arizona
Semi-Bandit Learning for Monotone Stochastic Optimization
Dec 24, 2023Arpit Agarwal, Rohan Ghuge, Viswanath Nagarajan +1Stochastic Optimization Multi-Armed Bandits
Department of Computer Science & Engineering, Indian Institute of Technology Bombay, Mumbai, India. · Department of Information, Risk, and Operations Management, University of Texas at Austin, Austin, USA. · Department of Industrial and Operations Engineering, University of Michigan, Ann Arbor, USA.

May 11, 2026J/K move · Enter open · S save

Learning to Sparsify Stochastic Linear Bandits

Zhengmiao Wang, Ming Chi, Zhi-Wei Liu, Lintao Ye+1

School of Artificial Intelligence and Automation, Huazhong University of Science and Technology, Wuhan 430074, China · Department of Electronics and Telecommunications, Politecnico di Torino, 10129 Torino, Italy

Multi-Armed Bandits Exploration-Exploitation Tradeoff Contextual Bandits

Open paper AskPDF arXiv

This paper addresses the problem of learning to sparsify stochastic linear bandits, where a decision-maker sequentially selects actions from a high-dimensional space subject to a sparsity constraint on the number of nonzero elements in the action vector. The key challenge lies in minimizing cumulative regret while tackling the potential NP-hardness of finding optimal sparse actions due to the inherent combinatorial structure of the problem. We propose an adaptively phased exploration and exploitation algorithmic framework, utilizing ordinary least squares for parameter learning and specialized subroutines for sparse action selection. When the action set is a Euclidean ball, optimal sparse actions can be efficiently computed, enabling us to establish a

\tilde{\mathcal{O}}(d\sqrt{T})

regret, where

d

is the dimension of the action vector and

T

is the time horizon length. For general convex and compact action sets where finding optimal sparse actions is intractable, we employ a greedy subroutine. For general strongly convex action sets, we derive a

\tilde{\mathcal{O}}(d \sqrt{T})

α

-regret; for general compact sets lacking strong convexity, we establish a

\tilde{\mathcal{O}}(d T^{2/3})

α

-regret, where

α

pertains to the approximation ratio of the greedy algorithm. Finally, we validate the performance of our algorithms using extensive experiments including an application to recommendation system.

Abstract

Multi-Armed Bandits

Explore similar work

Learning to Sparsify Stochastic Linear Bandits

Optimal and Efficient Contextual Combinatorial Semi-bandits with General Function Approximation

Semi-Bandit Learning for Monotone Stochastic Optimization