Stochastic continuum armed bandit problem of few linear parameters in high dimensions

2013/12/01 by Hemant Tyagi, Tyagi, Hemant, Sebastian U. Stich +3
Computer Science · Decision Sciences · Engineering · #Advanced Bandit Algorithms Research #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Optimization and Control (math.OC) #Optimization and Search Problems #Sparse and Compressive Sensing Techniques

paper · pdf · doi:10.48550/arxiv.1312.0232

openalex publication_date 2013/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We consider a stochastic continuum armed bandit problem where the arms are indexed by the ℓ₂ ball B_d(1+ν) of radius 1+ν in ℝ^d. The reward functions r :B_d(1+ν) → ℝ are considered to intrinsically depend on k ≪ d unknown linear parameters so that r(x) = g(A x) where A is a full rank k × d matrix. Assuming the mean reward function to be smooth we make use of results from low-rank matrix recovery literature and derive an efficient randomized algorithm which achieves a regret bound of O(C(k,d) n^(1+k)/(2+k) (log n)^(1)/(2+k)) with high probability. Here C(k,d) is at most polynomial in d and k and n is the number of rounds or the sampling budget which is assumed to be known beforehand.

Citations

• Laplacian Eigenmaps for Dimensionality Reduction and Data Representation
• Bandit Theory meets Compressed Sensing for high dimensional Stochastic Linear Bandit
• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization

Related

• Continuum armed bandit problem of few variables in high dimensions
• Bandit Theory meets Compressed Sensing for high dimensional Stochastic Linear Bandit
• Linearly Parameterized Bandits
• Sparse Stochastic Bandits
• Bandits with many optimal arms