Designing Bounded Min-Knapsack Bandits Algorithm for Sustainable Demand Response

Abstract

Recent trends focus on incentivizing consumers to reduce their demand consumption during peak hours for sustainable demand response. To minimize the loss, the distributor companies should target the right set of consumers and demand the right amount of electricity reductions. Almost all the existing algorithms focus on demanding single unit reductions from the selected consumers and thus have limited practical applicability. Even for single unit reductions, none of the work provides a polynomial time constant approximation factor algorithm to minimize the loss to the distributor company. This paper proposes a novel bounded integer min-knapsack algorithm (MinKPDR) and shows that the algorithm, while allowing for multiple unit reduction, also optimizes the loss to the distributor company within a factor of two (multiplicative) and a problem dependant additive constant. The loss is a function of the cost of buying the electricity from the market, costs incurred by the consumers, and compliance probabilities of the consumers. When the compliance probabilities of the consumers are not known, the problem can be formulated as a combinatorial multi-armed bandit (CMAB) problem. Existing CMAB algorithms fail to work in this setting due to the non-monotonicity of a reward function and time varying optimal sets. We propose a novel algorithm (Twin-MinKPDR-CB) to learn these compliance probabilities efficiently. Twin-MinKPDR-CB works for non-monotone reward functions, bounded min-knapsack constraints, and time-varying optimal sets. We theoretically show that Twin-MinKPDR-CB achieves sub-linear regret of $O(\log T)$ with T being the number of rounds for which demand response is run.

A. Singh and P. M. Reddy—contributed equally.