Recently, [1]}, [2]} generalized [3]} to allow for continuous labels and, more importantly, provided oracle-efficient algorithms for achieving vanishing regret in the smoothed setting. These papers also showed that the dependence on \(\sigma \)  in the regret bounds of their oracle-efficient algorithms, which was polynomial, could not in general be reduced to the logarithmic dependence achievable by the inefficient algorithms, thereby exposing a statistical-computational gap. Unlike other recent works such as [1]}, [2]}, we do not use the coupling approach [3]} to prove our regret bounds.
