Demand response is a key component of existing and future grid systems facing increased variability and peak demands. Scaling demand response requires efficiently predicting individual responses for large numbers of consumers while selecting the right ones to signal. This paper proposes a new online learning problem that captures consumer diversity, messaging fatigue and response prediction. We use the framework of multi-armed bandits model to address this problem. This yields simple and easy to implement index based learning algorithms with provable performance guarantees.