IEEE International Conference on Quantum Control, Computing and Learning (qCCL)
An Efficient Quantum Algorithm for Sparse Linear Bandits via Smoothed Exploration
Jiarui Hu, Wenzhi Chen, Shipra Singh, Lijun Chen
Abstract
Stochastic linear bandits are an important model for sequential decision-making, for which classical algorithms typically incur a regret scaling of $\tilde {\mathcal{O}}(d\sqrt T )$. Recent quantum linear bandit algorithms use quantum mean estimation to reduce the dependence on the time horizon T, achieving O(d2poly(logT)) regret, but they do not exploit sparsity inherent in many systems and still retain polynomial dependence on the ambient dimension d. We propose Q-Lasso-OFU, a two-phase quantum algorithm for sparse linear bandits. With sparsity s, our regret bound depends logarithmically on the ambient dimension d and polynomially on the sparsity s. Suppose that the nonzero components of θ⋆are lower bounded in magnitude by γ0. Once the horizon exceeds a finite identification time, the algorithm commits to an optimal action and achieves horizon-independent problem-dependent regret $\tilde {\mathcal{O}}\left( {{s^4}\log d\log \left( {1/{\gamma _0}} \right)} \right) + \tilde {\mathcal{O}}\left( {{s^4}\log d/{\gamma _0}} \right)$. Specifically, during the exploration phase, the regret from estimation error is $\tilde {\mathcal{O}}\left( {{s^4}\log d\log T} \right)$, logarithmic in both T and d, and after that the regret is zero. Compared with prior works in quantum bandits, our bound has a logarithmic dependence on d under sparsity. Numerical experiments support our theoretical results.