---
title: "Learning to Sparsify Stochastic Linear Bandits"
authors:
  - "Zhengmiao Wang"
  - "Ming Chi"
  - "Zhi-Wei Liu"
  - "Lintao Ye"
  - "Carla Fabiana Chiasserini"
doi: "10.24963/ijcai.2026/560"
url: "https://ijcai.org/proceedings/2026/560"
pdf: "https://ijcai.org/proceedings/2026/0560.pdf"
venue: "Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence"
year: 2026
pages: "5030-5038"
track: "Main Track"
keywords:
  - "Machine Learning: Learning sparse models"
  - "Machine Learning: Reinforcement learning"
  - "Machine Learning: Online learning"
  - "Machine Learning: Multi-armed bandits"
---

# Learning to Sparsify Stochastic Linear Bandits

Zhengmiao Wang, Ming Chi, Zhi-Wei Liu, Lintao Ye, Carla Fabiana Chiasserini

*Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence*, pages 5030-5038. DOI: [10.24963/ijcai.2026/560](https://doi.org/10.24963/ijcai.2026/560)

## Abstract

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 Õ(d √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 Õ(d √T) α-regret; for general compact sets lacking strong convexity, we establish a Õ(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.