We study low regret algorithms for online learning with limited feedback, where there is an additional constraint on the computational power of the learner. Focusing on multi-armed bandit with side information, we demonstrate cases in which there is a trade-off between the regret rate and the computational efficiency of the online learning algorithm. In particular, for the class of linear hypotheses we show that the EXP4 prediction strategy achieves the optimal regret but is not efficient. In contrast, we propose much more efficient strategies, still with a vanishing regret, but a worse regret rate.