Stochastic Online Linear Regression: the Forward Algorithm to Replace
  Ridge
  We consider the problem of online linear regression in the stochastic
setting. We derive high probability regret bounds for online ridge regression
and the forward algorithm. This enables us to compare online regression
algorithms more accurately and eliminate assumptions of bounded observations
and predictions. Our study advocates for the use of the forward algorithm in
lieu of ridge due to its enhanced bounds and robustness to the regularization
parameter. Moreover, we explain how to integrate it in algorithms involving
linear function approximation to remove a boundedness assumption without
deteriorating theoretical bounds. We showcase this modification in linear
bandit settings where it yields improved regret bounds. Last, we provide
numerical experiments to illustrate our results and endorse our intuitions.
