2021/11/02 by Reda Ouhamma, Ouhamma, Reda, Odalric Maillard +3 · 1 citation
Decision Sciences · Computer Science · #Advanced Bandit Algorithms Research #Cognitive Radio Networks and Spectrum Sensing #Distributed Sensor Networks and Detection Algorithms
paper · pdf · doi:10.48550/arxiv.2111.01602
We consider the problem of online linear regression in the stochastic\nsetting. We derive high probability regret bounds for online ridge regression\nand the forward algorithm. This enables us to compare online regression\nalgorithms more accurately and eliminate assumptions of bounded observations\nand predictions. Our study advocates for the use of the forward algorithm in\nlieu of ridge due to its enhanced bounds and robustness to the regularization\nparameter. Moreover, we explain how to integrate it in algorithms involving\nlinear function approximation to remove a boundedness assumption without\ndeteriorating theoretical bounds. We showcase this modification in linear\nbandit settings where it yields improved regret bounds. Last, we provide\nnumerical experiments to illustrate our results and endorse our intuitions.\n