In this section, we apply prop:kpieceregression and the approach of [1]} to the setting of contextual bandits with contexts drawn from a smooth distribution, considered in [2]}. Unlike in that work, however, we will realize regret bounds achievable by an oracle-efficient algorithm that are polynomially improved both in the horizon and the number of actions in the particular case of noiseless rewards that are piecewise linear.
