# Constrained Thompson Sampling for Real-Time Electricity Pricing with Grid
Reliability Constraints

Nathaniel Tucker† Ahmadreza Moradipari† Mahnoosh Alizadeh
†Authors have equal contribution

###### Abstract

We consider the problem of an electricity aggregator attempting to learn
customers’ electricity usage models while implementing a load shaping program
by means of broadcasting dispatch signals in real-time. We adopt a multi-armed
bandit problem formulation to account for the stochastic and unknown nature of
customers’ responses to dispatch signals. We propose a constrained Thompson
sampling heuristic, Con-TS-RTP, as a solution to the load shaping problem of
the electricity aggregator attempting to influence customers’ usage to match
various desired demand profiles (i.e., to reduce demand at peak hours,
integrate more intermittent renewable generation, track a desired daily load
profile, etc). The proposed Con-TS-RTP heuristic accounts for day-varying
target load profiles (i.e., multiple target load profiles reflecting renewable
forecasts and desired demand patterns) and takes into account the operational
constraints of a distribution system to ensure that customers receive adequate
service and to avoid potential grid failures. We provide a discussion on the
regret bounds for our algorithm as well as a discussion on the operational
reliability of the distribution system’s constraints being upheld throughout
the learning process.

###### Index Terms:

Constrained optimization, distribution network, multi-armed bandit, real-time
pricing, demand response, Thompson sampling.

00footnotetext: This work was supported by NSF grants #1847096 and #1737565
and UCOP Grant LFR-18-548175.
N. Tucker, A. Moradipari, and M. Alizadeh are with the Department of
Electrical and Computer Engineering, University of California, Santa Barbara,
CA 93106 USA (email<EMAIL_ADDRESS>
##  I Introduction

In order to integrate the increasing volume of intermittent renewable
generation in modern power grids, aggregators are exploring various methods to
manipulate both residential and commercial loads in real-time. As a result,
various demand response (DR) frameworks are gaining popularity because of
their ability to shape electricity demand by broadcasting time-varying signals
to customers; however, most aggregators have not implemented complex DR
programs beyond peak shaving and emergency load reduction initiatives. One
reason for this is the customers’ unknown and time-varying responses to
dispatch signals, which can lead to economic uncertainty for the aggregator
and reliability concerns for the grid [1]. The aggregator could explicitly
request price sensitivity information from its customers; however, this two-
way negotiation has a large communication overhead and most customers cannot
readily characterize their price sensitivities, and even if they could, they
might not be willing to share this private information. As such, aggregators
prefer the 1-way passive approach because it does not require any real-time
feedback from the customer and it does not require new communication
infrastructure for reporting preferences (e.g., a web portal, phone
application, etc.). With this in mind, future load shaping initiatives for
renewable integration (i.e., more complex objectives than peak shaving) need
to be able to passively learn customers’ response to dispatch signals only
from historical data of past interactions [2].

Recently, much work has been done for aggregators attempting to learn
customers’ price responses whilst implementing peak shaving DR programs. The
authors of [3] present a data-driven strategy to estimate customers’ demands
and develop prices for DR. In [4], the authors use linear regression models to
derive estimations of customers’ responses to DR signals. Similarly, [5]
develops a joint online learning and pricing algorithm based on linear
regression. In [6], the authors present a contract-based DR strategy to learn
customer behavior while broadcasting DR signals. The authors of [7] present an
online learning approach based on piecewise linear stochastic approximation
for an aggregator to sequentially adjust its DR prices based on the behavior
of the customers in the past. In [8], the authors develop a risk-averse
learning approach for aggregators operating DR programs. In [9], a learning
algorithm for customers’ utility functions is developed and it is assumed that
the aggregator acts within a two-stage (day-ahead and real-time) electricity
market. Additionally, the authors of [10] present a learning framework for
forecasting individual loads and DR capabilities and find that users with more
variable consumption patterns are more effective DR participants. Using a
similar framework as in this work, a multi-armed bandit (MAB) formulation is
used in [11, 12] to determine which customers to target in DR programs.

In addition to learning how customers respond to DR signals, an aggregator
must also consider power system constraints to ensure reliable operation
(e.g., nodal voltage, transformer capacities, and line flow limits). In real
distribution systems, it is critical that these constraints are satisfied at
every time step to ensure customers receive adequate service and to avoid
potential grid failures even without sufficient knowledge about how customers
respond to price signals (i.e., in early learning stages) [13, 14]. One paper
similar to ours that considers these realistic constraints, [15], presents a
least-square estimator approach to learn customer sensitivities and implements
DR in a distribution network. The authors of [15] show that their least-square
algorithm’s parameter estimation error converges to zero over time, thus the
algorithm’s regret is sublinear while also accounting for the distribution
network’s constraints.

Similar to the aforementioned papers, the work presented in this manuscript
considers the problem of an aggregator passively learning the customers’ price
sensitivities while running a load shaping program. However, our approach
permits more complex load shaping objectives (e.g., tracking a daily target
load profile) and varies in terms of both load modeling and learning approach
from all the above papers. Specifically, we present a multi-armed bandit (MAB)
heuristic akin to Thompson sampling (TS) to tackle the trade-off between
exploration of untested price signals and exploitation of well-performing
price signals while ensuring grid reliability. It is important to note that
the standard TS heuristic cannot guarantee that grid reliability constraints
are upheld during the learning process. As such, we present two modified
versions of TS while retaining the fundamental principles TS is based on.
Furthermore, we provide discussion on how the constraints are upheld (i.e.,
operational reliability) for the modified heuristics, discussion on the
performance of the heuristics compared to a clairvoyant solution, and
simulation results highlighting the strengths of the method.

In our work, we make use of a load clustering technique in order to exploit
the known physical structure of the problem and make use of our prior
knowledge of how flexible electric appliances behave to lower the problem
dimensionality. We note that grouping (clustering) loads for dimensional
reduction is common in DR literature [16]. Some pertinent examples include
[17] where the authors aggregate heterogeneous thermostatically controlled
loads (TCLs) using an LTI “bin” model, [18] where the authors group EVs into
“classes” depending on their charging availability, [19] where the authors
present a load profile clustering method for load data classification based on
information entropy, piecewise aggregate approximation, and spectral
clustering, [20] where the authors present aggregate models for classes of
TCLs that include statistical information of the population, systematically
deal with heterogeneity, and account for a second-order effects, [21] where
the authors propose a clustering technique for determining natural
segmentation of customers and identification of temporal consumption patterns
in the smart grid domain, and [22] where the authors develop cohorts, or
groups of consumers with similar consumption patterns, from correlations
between daily loads.

The main contributions of this work are as follows:

  * •

We use the multi-armed bandit (MAB) framework to model the stochastic and
unknown nature of customers’ daily aggregate response to electricity prices.

  * •

We make use of an appliance clustering methodology to provide a mesoscopic
model of the price responsive demand of a large population of flexible
appliances and reduce the dimensionality of the learning problem.

  * •

Our learning framework can account for daily variabilities and realistic grid
reliability constraints that are critical for daily operation in spite of
uncertainty about customers’ price response.

  * •

We present two modified heuristics based on Thompson sampling (TS) as
solutions to the constrained learning and pricing problem.

  * •

We provide a performance guarantee in the form of a regret bound and
discussion on the reliability guarantees of the approach as well as a
distribution system case study demonstrating the efficacy of the approach.

The remainder of the paper is organized as follows: Section II presents the
aggregator’s daily objective as well as the customers’ load model. Section III
describes the multi-armed bandit formulation for the electricity pricing
problem, presents the modified TS heuristic, and discusses its performance and
reliability. Section IV presents simulation results that showcase the efficacy
of the approach. The Appendix contains a table of notation and proofs.

##  II Problem Formulation

###  II-A The Aggregator’s Objective

The aggregator’s main goal is to select dispatch signals to manipulate
customer demand according to a given optimization objective that varies daily.
Specifically, we consider the case where the aggregator broadcasts a dispatch
signal $\mathbf{p}_{\tau}=[p(t)]_{t=1,\dots,T}$ to the population of customers
each day (we use $t=1,\dots,T$ to index time of day and
$\tau=1,\dots,\mathcal{T}$ to index days). The set of dispatch signals
available for use by the aggregator is denoted as $\mathcal{P}$. In this
paper, without a loss of generality, we will assume that the dispatch signal
sent to customers for load shaping purposes is a real-time pricing (RTP)
signal111The reader should note that this choice is not fundamental to the
development of the modified learning heuristics we present in this paper. It
only allows us to provide a concrete characterization of the response to
dispatch signals by mathematically modeling the customers as cost-minimizing
agents equipped with home energy management systems in Section II-D..

The aggregator’s cost function could cover a broad range of goals including
(but not limited to) manipulating the population’s load to match a target
profile, minimizing the distribution grid’s electricity cost from the regional
retailer, or solving for the dispatch of multiple generators, if a market is
operated at the distribution system level.

In this work, on each day $\tau$, we assume the aggregator’s cost function is
a fixed and known nonlinear function
$f(\mathbf{D}_{\tau}(\mathbf{p}_{\tau}),\mathbf{V}_{\tau})$ that depends on
the load profile $\mathbf{D}_{\tau}(\mathbf{p}_{\tau})$ of the population in
response to the daily broadcasted price $\mathbf{p}_{\tau}$ and a random
exogenous parameter vector $\mathbf{V}_{\tau}$222We note that the function $f$
need not have a closed form representation and thus can represent the solution
of an economic dispatch problem with multiple generators, which can still be
handled through our framework. However, without loss of generality and purely
for brevity of notation, here we focus on common distribution systems which
usually lack two-sided markets, and thus we focus on load profile manipulation
for renewable integration and distribution system protection.. The
population’s load profile on day $\tau$,
$\mathbf{D}_{\tau}(\mathbf{p}_{\tau})$, is a $T\times 1$ vector with the
$t^{th}$ element corresponding to the population’s power demand during time
period $t$. The exogenous and given $T\times 1$ vector $\mathbf{V}_{\tau}$
varies daily and can correspond to a daily target profile reflecting renewable
generation forecasts, weather predictions, and grid conditions. We consider
the exogenous vectors to be i.i.d. drawn from a distribution defined on a
finite sample space $\mathcal{V}$, with each outcome drawn with a nonzero
probability. We would like the reader to note that this assumption is only
made for convenience for our theoretical regret performance guarantee in
Theorem 1. In a real-world implementation, the daily exogenous parameters
could be correlated across days (e.g., due to weather, seasons,
weekday/weekend, etc.). However, this correlation does not affect the safety
guarantees of our algorithm or its applicability (i.e., it only affects our
formal regret results).

The aggregator must ensure that the broadcasted price signals do not result in
load profiles that violate distribution system reliability constraints (e.g.,
nodal voltage, transformer capacities, or line flow limits). As such, if the
aggregator had full information about how the population responds to price
signals (i.e., full knowledge of $\mathbf{D}_{\tau}(\mathbf{p}_{\tau})$), the
aggregator can solve the following optimization problem on day $\tau$ to
select the optimal price $\mathbf{p}^{\star}_{\tau}$:

$\displaystyle\mathbf{p}_{\tau}^{\star}=\operatorname*{arg\,min}_{\mathbf{p}_{\tau}\in\mathcal{P}}f\big{(}\mathbf{D}_{\tau}(\mathbf{p}_{\tau}),\mathbf{V}_{\tau}\big{)}$
(1) $\displaystyle\text{\hskip 24.0pts.t.\hskip
24.0pt}g_{j}\big{(}\mathbf{D}_{\tau}(\mathbf{p}_{\tau})\big{)}\leq
0,\;\;\forall j=1,\dots,J$ (2)

where $g_{j}(\cdot)_{j=1,\dots,J}$ is used to represent the reliability
constraints for the distribution system. We note that these general
constraints need not be linear for the proposed Thompson sampling approach.

However, as explained in the introduction, knowledge of customers’ price
response is unavailable to the aggregator. Recall, 1) the aggregator does not
want to directly query customers for their price sensitivities, 2) most
customers cannot readily characterize their price sensitivities, and 3)
customers might not be willing to share this private information. Accordingly,
the aggregator needs a method to sequentially choose daily price signals to
simultaneously 1) control their daily incurred cost; 2) learn the customers’
price response models; and 3) ensure the distribution system constraints are
not violated at any time.

###  II-B Distribution System Operational Constraints

As stated previously, there are various operational constraints within a
distribution system that should be met in order to ensure adequate service for
customers and to prevent grid failures. In the aggregator’s daily optimization
in Section II-A, the constraints are formulated as general functions
$g_{j}(\cdot)_{j=1,\dots,J}$. Specifically, these general functions represent
distribution system parameters (i.e., the nodal voltage $u_{\tau}(t)$ and
power flow through distribution lines $f_{\tau}(t)$) that should obey the
following constraints:

$\displaystyle u_{\tau}(t)$ $\displaystyle\geq u^{min},\;\;\forall t,\tau,$
(3) $\displaystyle u_{\tau}(t)$ $\displaystyle\leq u^{max},\;\;\forall
t,\tau,$ (4) $\displaystyle f_{\tau}(t)$ $\displaystyle\leq
S^{max},\;\;\forall t,\tau,$ (5)

where $u^{min}$, $u^{max}$, and $S^{max}$ correspond to the lower voltage
limit, upper voltage limit, and power flow limit, respectively, for the
population’s connection to the distribution grid. We note that $u_{\tau}(t)$
and $f_{\tau}(t)$ can be easily derived from the population’s load profile
$\mathbf{D}_{\tau}(\mathbf{p}_{\tau})$ (See Section IV-B). Now that we have
described the aggregator’s objective and the distribution system’s
constraints, we next describe the customers’ load model as well as their price
response model.

###  II-C Load Flexibility Model

It is hard to approach the problem of learning the response of a population of
customers to complex dispatch signals such as RTP as a complete “black box
problem”, i.e., by just observing the broadcasted price and the load response.
There are many reasons for this, including 1) the existence of random or
exogenous parameters which lead to variability in the temporal and
geographical behavior of electricity demand; 2) the variability of the control
objective on a daily basis (e.g., due to randomness in renewable generation
outputs, market conditions, or baseload); and 3) the small size of the set of
observations that one can gather compared to the high dimensional structure of
the load (there are only 365 days in a year, so only 365 sets of prices can be
posted). Hence, in this paper, we will be exploiting the known physical
structure of the problem and making use of our statistical prior knowledge of
how the load behaves to lower the problem dimensionality.

Specifically, to lower the dimensionality for the learning problem, we explore
the fact that flexible loads only show limited number of “load signatures”
(justified due to the automated nature of load response through home energy
management systems, the limited types of flexible appliances, and the common
electricity usage patterns that emerge from electricity customers as shown in
[10, 23]). Let us assume that electric appliances can belong to a finite
number of clusters $c\in\mathcal{C}$. For each cluster $c$, we denote
$\mathcal{D}_{c}$ as the set of feasible daily power consumption schedules
that satisfy the energy requirements of the corresponding appliances. Any
power consumption schedule,
$[d_{c}(t)]_{t=1,\dots,T}=\mathbf{D}_{c}\in\mathcal{D}_{c}$, would satisfy the
daily power needs of an appliance in cluster $c$. For example, consider a
cluster that represents plug-in electric vehicles (EVs) that require $E_{c}$
kWh in the time interval $[t_{1},t_{2}]$ with a maximum charging rate of
$\rho_{c}$ kW. Accordingly, the set $\mathcal{D}_{c}$ of daily feasible power
consumption schedules is given by:

$\displaystyle\mathcal{D}_{c}=\Big{\\{}\mathbf{D}_{c}|\sum_{t=t_{1}}^{t_{2}}d_{c}(t)=E_{c};\;0\leq
d_{c}(t)\leq\rho_{c}\Big{\\}}.$ (6)

Another specific cluster example is that of electric appliances that are
uninterruptible but can perform load shifting (e.g., a dishwasher cannot be
interrupted once it is turned on but the start time of the cycle can be
shifted). Let $\Pi_{c}(\cdot)$ denote the load profile of uninterruptible
cluster $c$ appliances once they are turned on. For example, $\Pi_{c}(\cdot)$
could be a rectangular pulse function that outputs the rated power of the
appliance, $\rho_{c}$ for the duration of the appliance’s cycle and $0$
otherwise. To relay their load flexibility, cluster $c$ users can specify a
time interval $[t_{c,1},t_{c,2}]$ within which the appliance cycle must start
(e.g., a user wants the dishwasher to be finished before dinner). Thus the
home energy management system can calculate the best values for the time
shift, denoted by $t_{c}$, as long as it lies within the interval
$[t_{c,1},t_{c,2}]$. The set $\mathcal{D}_{c}$ of daily feasible power
consumption schedules for appliances in this cluster is given by:

$\displaystyle\mathcal{D}_{c}=\Big{\\{}\mathbf{D}_{c}|$ $\displaystyle
d_{c}(t)=\Pi_{c}(t-t_{c});\;t_{c}\in[t_{c,1},t_{c,2}]\;\Big{\\}}.$ (7)

For discussion on characterizing the sets for other flexible appliances,
including interruptible (Section III.B in [24], non-interruptible (Section
III.D in [24]), and thermostatically controlled loads (Section III.C in [24]),
we refer the reader to reference [24].

By adopting this model, the total power consumption flexibility of a
population of customers can be characterized as a function of how many
appliances belong to each cluster within the population. Let us denote $a_{c}$
as the number of appliances in cluster $c$ (note that this will vary on a day
by day basis as described in the next section). With this notation, we can
write the set of feasible daily power consumption profiles for the population,
$\mathcal{D}$:

$\displaystyle\mathcal{D}=\sum_{c\in\mathcal{C}}a_{c}\mathcal{D}_{c},$ (8)

where the summation and scalar multiplication operations are defined in the
sense of Minkowski addition333For two sets $A$ and $B$ defined on a finite
dimensional Euclidean space, the Minkowski sum is defined as
$A+B=\\{\mathbf{a}+\mathbf{b}~{}|~{}\mathbf{a}\in A,\mathbf{b}\in B\\}$..

We would like to note that choosing the number of clusters in the model is a
control knob that can be tuned by the aggregator as shown in [25]. Using a
higher number of potential appliance clusters will increase the accuracy of
the load model (i.e., reduce the quantization error in the reproduction of the
individual load profiles) and yield better performance in the daily
optimization once the true parameters have been sufficiently learned by the
aggregator. However, increasing the number of load clusters increases the size
of the problem space and increases the randomness in the customers’ daily
loads thus slowing down the learning rate of the algorithm. The number of
clusters will vary depending on the system being analyzed as well as the
aggregator’s preferences.

###  II-D Price Response Model

In this section, we discuss how the total population responds to dynamic
electricity prices given the load flexibility model in (8) and how clustering
is used to reduce the dimensionality of the problem. There are two main ways
dynamic pricing affects the power consumption: 1) Automated per cluster
response: Within each load cluster $c$ (i.e., given pre-specified preferences
such as EV charging deadlines or AC temperature set points), we assume that
the customer chooses the power consumption profile
$\mathbf{D}_{c}\in\mathcal{D}_{c}$ that minimizes their electricity cost
dependent on the daily broadcasted price $\mathbf{p}_{\tau}$. For appliances
in cluster $c$ on day $\tau$, we assume all will choose the same minimum cost
power consumption profile:

$\displaystyle\widetilde{\mathbf{D}}_{c,\tau}(\mathbf{p}_{\tau})=\operatorname*{arg\,min}_{\mathbf{D}_{c}\in\mathcal{D}_{c}}\sum_{t=1}^{T}p(t)d_{c}(t).$
(9)

We assume that each appliance will always choose the cost minimizing power
consumption profile out of the available profile set to combat the fact that
the available profile sets $\mathcal{D}_{c}$ for each cluster can be
infinitely large. Thus, we have effectively reduced the dimensionality of the
problem as we know a priori how each cluster will respond to each price signal
(i.e., each cluster will always select its cost minimizing profile). Due to
the automated nature of home energy management systems, each cluster selecting
its cost minimizing profile is a reasonable assumption once the customers have
defined their flexibility preferences, e.g., the desired charge amounts and
deadlines for EVs [26, 27]. 2) Preference Adjustment: We also consider the
fact that customers may respond to price signals by adjusting their
preferences. Consider the following example: two customers (Customer-A and
Customer-B) live in the same neighborhood but have different sensitivities to
electricity prices. If electricity prices are high on a hot summer day,
Customer-A might shutdown their air conditioner to avoid a large electricity
bill; however, Customer-B prioritizes comfort over cost-savings, and leaves
their air conditioner on, no matter the cost. As shown in the previous
example, the number of appliances in each cluster, i.e., $a_{c}$ in (8), also
depends on the daily posted price vector $\mathbf{p}_{\tau}$, and are now
denoted as $a_{c}(\mathbf{p}_{\tau})$.

Combining the automated per cluster response and preference adjustment, we can
define the population’s load on day $\tau$ in response to the posted price
$\mathbf{p}_{\tau}$ as follows:

$\displaystyle\mathbf{D}_{\tau}^{\star}(\mathbf{p}_{\tau})=\sum_{c\in\mathcal{C}}a_{c}(\mathbf{p}_{\tau})\widetilde{\mathbf{D}}_{c,\tau}(\mathbf{p}_{\tau}).$
(10)

As stated before, if the aggregator has full knowledge of the customers’ price
responses, which reduces to having full knowledge of the preference
adjustments $a_{c}(\mathbf{p}_{\tau})$, then the aggregator can pick the daily
price vector $\mathbf{p}_{\tau}^{\star}$ in order to shape the population’s
power consumption according to (1). However, as we cannot assume this, we
model the $a_{c}(\mathbf{p}_{\tau})$’s as random variables with parameterized
distributions, $\phi_{c}$, based on the posted price signal
$\mathbf{p}_{\tau}$ and an unknown but constant parameter vector
$\boldsymbol{\theta}^{\star}$. Here, $\boldsymbol{\theta}^{\star}$ represents
the true model for the customers’ sensitivity to the price signals. This
allows for the complex response of the customer population to be represented
as a single vector, thus reducing the dimensionality of the problem. We note
that while $a_{c}(\mathbf{p}_{\tau})$ may only take integer values in reality,
we believe it is justified to relax this integrality constraint and allow it
to take continuous values with large enough appliance population size. With
this in mind, we would like to highlight three properties of the price
response model:

  1. 1.

The preference adjustment models $a_{c}(\mathbf{p}_{\tau})$ are stochastic and
their distributions $\phi_{c}$ are parameterized by $\mathbf{p}_{\tau}$ and
$\boldsymbol{\theta}^{\star}$. This is due to exogenous factors outside of the
aggregator’s scope that influence customers’ power consumption profiles
resulting in a level of stochasticity in the responses to prices (i.e.,
customers will not respond to prices in the same fashion each day).

  2. 2.

The probability distributions of $a_{c}(\mathbf{p}_{\tau})$ (i.e., $\phi_{c}$)
are unknown to the aggregator, i.e., the aggregator does not know the true
parameter $\boldsymbol{\theta}^{\star}$ of the stochastic model.

  3. 3.

The realizations of $a_{c}(\mathbf{p}_{\tau})$ are not directly observable by
the aggregator. The aggregator can only monitor the population’s total
consumption profile $\mathbf{D}_{\tau}$ and cannot observe the decomposed
response of each cluster
$a_{c}(\mathbf{p}_{\tau})\widetilde{\mathbf{D}}_{c,\tau}(\mathbf{p}_{\tau})$
independently.

Because we have introduced stochasticity to customers’ price response models,
we appropriately alter the aggregator’s optimization problem for selecting the
price signal on day $\tau$ to account for the distributions $\phi_{c}$:

$\displaystyle\mathbf{p}_{\tau}^{\star}=\operatorname*{arg\,min}_{\mathbf{p}_{\tau}\in\mathcal{P}}\mathbb{E}_{\\{\phi_{c}\\}_{c\in\mathcal{C}}}\big{[}f\big{(}\mathbf{D}_{\tau}(\mathbf{p}_{\tau}),\mathbf{V}_{\tau}\big{)}\big{]}$
(11) $\displaystyle\text{s.t.\hskip
13.0pt}\mathbb{P}_{\\{\phi_{c}\\}_{c\in\mathcal{C}}}\big{[}g_{j}\big{(}\mathbf{D}_{\tau}(\mathbf{p}_{\tau})\big{)}\leq
0\big{]}\geq 1-\mu,\;\;\forall j$ (12)

where $\mu$ is the aggregator’s desired reliability metric for the
distribution system constraints. In (11), the aggregator now considers
minimizing an expected cost and is subject to probabilistic reliability
constraints in (12) that depend on the distributions $\phi_{c}$ of the
preference adjustment models $a_{c}(\mathbf{p}_{\tau})$.

We note that the formulated chance constraints are enforced with respect to
uncertainty in the clusters’ price sensitivity parameters, not to the
exogenous context vector $\mathbf{V}_{\tau}$. In this work, we assume the
daily exogenous vector is fully known each day and does not add uncertainty to
the problem. However, uncertainties in the exogenous vector are important to
real-world systems such as the power grid and can be accommodated by our
approach by adding external noise to these vectors in the same fashion as
noise being added to the population’s load. This, of course, would further
slow down the learning rate of the algorithm due to the added noise reducing
the effectiveness of each posterior update.

Clearly, the aggregator needs to learn the underlying parameters of the
stochastic models $\phi_{c}$ of how customers respond to price signals in
order to select price signals for load shaping initiatives (i.e., the
aggregator needs to learn $\boldsymbol{\theta}^{\star}$). Our proposed
learning approach and pricing strategy for an electricity aggregator is
detailed in the next section.

##  III Real-Time Pricing via Multi-Armed Bandit

###  III-A Multi-Armed Bandit Overview

We utilize the multi-armed bandit (MAB) framework to model the iterative
decision making procedure of an aggregator implementing a daily load shaping
program [28, 29, 30]. The MAB problem can be described as a decision making
problem where an agent has a set of available actions but can only take one
action per round. After an action is taken, the agent experiences a cost that
is dependent on the action taken. The agent can only learn about the
distribution of costs from each action by experimenting. Throughout this
iterative procedure, the agent faces the core dilemma: should the agent
exploit actions that have yielded small costs, or explore actions that have
not been tested thoroughly? The goal in a MAB problem is to develop a strategy
for selecting actions that balance this trade-off and minimize the cumulative
cost over a given time span. More thorough explanation and background of the
MAB problem can be found in [31].

For the electricity pricing problem, the MAB framework exemplifies the
exploration-exploitation trade-off dilemma faced by an aggregator each day.
Namely, should the aggregator choose to broadcast untested prices (i.e.,
explore) to learn more information about the customers? Or should the
aggregator choose to broadcast well-performing prices (i.e., exploit) to
manipulate the daily electricity demand?

To evaluate the performance of an algorithm that aims to tackle the
exploration-exploitation trade-off, one commonly examines the algorithm’s
regret. Formally, regret is defined as the cumulative difference in cost
incurred over $\mathcal{T}$ days between a clairvoyant algorithm (i.e., the
optimal strategy that is aware of the customers’ price responses) and any
proposed algorithm that does not know the customers’ price responses:

$\displaystyle
R_{\mathcal{T}}=\sum_{\tau=1}^{\mathcal{T}}f(\mathbf{D}_{\tau}(\mathbf{p}_{\tau}),\mathbf{V}_{\tau})-f(\mathbf{D}_{\tau}(\mathbf{p}^{\star}),\mathbf{V}_{\tau}).$
(13)

Instead of considering the cumulative difference in objective function value,
an alternative metric for regret is to count the number of times that
suboptimal price signals are selected over the $\mathcal{T}$ days. For this,
we introduce the following notation: let
$\mathbf{p}^{\mathbf{V}_{\tau},\star}$ denote the optimal price signal for the
true model of the population’s price response $\boldsymbol{\theta}^{\star}$
when the daily exogenous parameter $\mathbf{V}_{\tau}$ is observed on day
$\tau$. Any price signal
$\mathbf{p}_{\tau}\neq\mathbf{p}^{\mathbf{V}_{\tau},\star}$ is considered a
suboptimal price. Moreover, we denote $N_{\tau}(\mathbf{p},\mathbf{V})$ as the
number of times up to day $\tau$ that the algorithm simultaneously observes
the exogenous parameter $\mathbf{V}$ and selects the price signal
$\mathbf{p}$. As such, the total number of times that suboptimal price signals
are selected over $\mathcal{T}$ days is:

$\displaystyle\sum_{\mathbf{V}\in\mathcal{V}}\sum_{\mathbf{p}\in\\{\mathcal{P}\setminus\mathbf{p}^{\mathbf{V},\star}\\}}N_{\mathcal{T}}(\mathbf{p},\mathbf{V})=\sum_{\tau=1}^{\mathcal{T}}\mathbbm{1}^{\\{\mathbf{p}_{\tau}\neq\mathbf{p}^{\mathbf{V}_{\tau},\star}\\}},$
(14)

where $\mathbbm{1}^{\\{\cdot\\}}$ is the indicator function that is set equal
to one if the criteria is met and zero otherwise. Subsequently, in an
iterative decision making problem such as this, the question arises: how can
an aggregator learn to price electricity with bounded regret, and what are the
regret bounds we can provide for a proposed algorithm given dynamically
changing grid conditions and reliability constraints? In the following
sections, we present a modified Thompson sampling heuristic for the
electricity pricing problem to simultaneously learn the true model
$\boldsymbol{\theta}^{\star}$ for the population, select the daily price
signals, ensure grid reliability, and provide a regret guarantee.

###  III-B Thompson Sampling

Thompson sampling (TS) is a well-known MAB heuristic for choosing actions in
an iterative decision making problem with the exploration-exploitation dilemma
[31, 32, 33]. Two other well-studied frameworks, greedy algorithms and upper-
confidence bound (UCB) algorithms, have shown promise in this problem area.
However, greedy algorithms are inferior to Thompson sampling in regret
performance and UCB algorithms are restricted to simpler linear optimizations
[34, 35, 36], whereas Thompson sampling can readily handle more general
objective functions such as those adopted in our paper [37]. Additionally, a
novel aspect of our paper is that we have shown how to modify the Thompson
sampling heuristic to account for reliability constraints with a theoretical
guarantee (Proposition 1). There are no other bandit optimization approaches
known to be able to handle general objective functions with safety
constraints. Relevant works here include the analysis of the performance of
the UCB algorithm in the linear MAB setting with linear safety-constraints
[38], and well as linear TS with linear constraints [39]. In the latter work,
it is shown that in the linear case, the presence of linear constraints do not
negatively affect the regret performance of TS, which is remarkable and could
be a preliminary justification as to why TS performs well in our paper in the
presence of general (non-linear) cost and constraint functions.

Simply put, the integral characteristic of Thompson sampling is that the
algorithm’s knowledge on day $\tau$ of the unknown parameter
$\boldsymbol{\theta}^{\star}$ is represented by the prior distribution
$\pi_{\tau-1}$. Each day the algorithm samples
$\boldsymbol{\widetilde{\theta}}_{\tau}$ from the prior distribution, and
selects an action assuming that the sampled parameter is the true parameter.
The algorithm then makes an observation dependent on the chosen action and the
hidden parameter and performs a Bayesian update on the parameter’s
distribution $\pi_{\tau}$ based on the new observation. Because TS samples
parameters from the prior distribution, the algorithm has a chance to explore
(i.e., draw new parameters) and can exploit (i.e., draw parameters that are
likely to be the true parameter) through out the run of the algorithm.

###  III-C Constrained Thompson Sampling

In this section, we present the MAB heuristic titled Con-TS-RTP adopted to the
electricity pricing problem. Con-TS-RTP is a modified Thompson sampling
algorithm where the daily optimization problem is subject to constraints
(standard TS algorithms do not have constraints)[40].

When initializing $\pi_{0}$, the initial distribution on the customers’
unknown parameter can be selected by the aggregator. If the aggregator has
access to prior information regarding the true parameter, then they could
initialize the prior as a distribution of their choice. However, if the
aggregator has no prior knowledge, a uniform distribution among all available
parameters may be used to model the lack of knowledge of the aggregator.

Each day, the algorithm observes the daily target profile $\mathbf{V}_{\tau}$,
draws a parameter $\boldsymbol{\widetilde{\theta}}_{\tau}$ from the prior
distribution, broadcasts a price signal to the customers, observes the load
profile of the population in response to the broadcasted price, and then
performs a Bayesian update on the parameter’s distribution $\pi_{\tau}$ based
on the new observation. We note that there are no restrictions on the class of
optimization problem to be solved each day; however, in order for our regret
guarantee to hold, the aggregator must be able to find the globally optimal
solution and can use any desired solution method to do so. In our experimental
examples, we assume that $\theta$’s and $\mathbf{p}_{\tau}$’s are chosen from
discrete sets in order to be able to guarantee that an enumeration method
could solve for the globally optimal price signals each day in spite of non-
convexities that arise.

The observation on day $\tau$ is denoted as
$\mathbf{Y}_{\tau}=\mathbf{D}_{\tau}^{\star}(\mathbf{p}_{\tau})$ and we assume
that each $\mathbf{Y}_{\tau}$ comes from the observation space $\mathcal{Y}$
that is known a priori. When performing the Bayesian update, the algorithm
makes use of the following likelihood function:
$\ell(\mathbf{Y}_{\tau};\mathbf{p},\boldsymbol{\theta})=\mathbb{P}_{\theta}(\mathbf{D}_{\tau}^{\star}(\mathbf{p}_{\tau})=\mathbf{Y}_{\tau}|\mathbf{p}_{\tau}=\mathbf{p})$.
This function calculates the likelihood of observing a specific load profile
when broadcasting price $\mathbf{p}$ and the true parameter is
$\boldsymbol{\theta}$. The pseudocode for Con-TS-RTP applied to the
constrained electricity pricing problem is presented in Algorithm 1.

Algorithm 1 Con-TS-RTP

Input: Parameter set $\Theta$; Price set $\mathcal{P}$; Observation set
$\mathcal{Y}$; Voltage constraints $u^{min},u^{max}$; Power flow constraint
$S^{max}$, Reliability metrics $\mu$, $\nu$

Initialize $\pi_{0}$ based on aggregator’s available prior knowledge of
customer sensitivity.

1: for Day index $\tau=1...\mathcal{T}$ do

2: Sample the daily hidden parameter
$\boldsymbol{\widetilde{\theta}}_{\tau}\in\Theta$ from the aggregator’s prior
distribution $\pi_{\tau-1}$.

3: Observe the daily exogenous parameter $\mathbf{V}_{\tau}$.

4: Broadcast the daily price signal:
$\displaystyle\hat{\mathbf{p}}_{\tau}=\operatorname*{arg\,min}_{\mathcal{P}}\mathbb{E}_{\\{\phi_{c}\\}_{c\in\mathcal{C}}}\big{[}f(\mathbf{D}_{\tau}(\mathbf{p}_{\tau}),\mathbf{V}_{\tau})|\boldsymbol{\theta}=\boldsymbol{\widetilde{\theta}}_{\tau}\big{]}$
Subject to: Constraint Set A: $\displaystyle\begin{cases}\textit{{A.1:
}}\mathbb{P}_{\\{\phi_{c}\\}_{c\in\mathcal{C}}}[u_{\tau}(t)\geq
u^{min}|\boldsymbol{\theta}=\boldsymbol{\widetilde{\theta}}_{\tau}]\geq
1-\mu,\;\;\forall t\\\ \textit{{A.2:
}}\mathbb{P}_{\\{\phi_{c}\\}_{c\in\mathcal{C}}}[u_{\tau}(t)\leq
u^{max}|\boldsymbol{\theta}=\boldsymbol{\widetilde{\theta}}_{\tau}]\geq
1-\mu,\;\;\forall t\\\ \textit{{A.3:
}}\mathbb{P}_{\\{\phi_{c}\\}_{c\in\mathcal{C}}}[f_{\tau}(t)\leq
S^{max}|\boldsymbol{\theta}=\boldsymbol{\widetilde{\theta}}_{\tau}]\geq
1-\mu,\;\;\forall t\\\ \end{cases}$ Constraint Set B:
$\displaystyle\begin{cases}\textit{{B.1:
}}\mathbb{P}_{\\{\phi_{c}\\}_{c\in\mathcal{C}}}[u_{\tau}(t)\geq
u^{min}|\boldsymbol{\theta}\sim\pi_{\tau-1}]\geq 1-\nu,\;\;\forall t\\\
\textit{{B.2: }}\mathbb{P}_{\\{\phi_{c}\\}_{c\in\mathcal{C}}}[u_{\tau}(t)\leq
u^{max}|\boldsymbol{\theta}\sim\pi_{\tau-1}]\geq 1-\nu,\;\;\forall t\\\
\textit{{B.3: }}\mathbb{P}_{\\{\phi_{c}\\}_{c\in\mathcal{C}}}[f_{\tau}(t)\leq
S^{max}|\boldsymbol{\theta}\sim\pi_{\tau-1}]\geq 1-\nu,\;\;\forall t\\\
\end{cases}$

5: Observe the population’s load response to price $\mathbf{p}_{\tau}$:
$\mathbf{Y}_{\tau}=\mathbf{D}_{\tau}^{\star}(\mathbf{p}_{\tau})$.

6: Update the aggregator’s knowledge of the true parameter in the posterior:
$\displaystyle\forall
S\subseteq\Theta:\pi_{\tau}(S)=\frac{\int_{S}\ell(\mathbf{Y}_{\tau};\hat{\mathbf{p}}_{\tau},\boldsymbol{\theta})\pi_{\tau-1}(d\boldsymbol{\theta})}{\int_{\Theta}\ell(\mathbf{Y}_{\tau};\hat{\mathbf{p}}_{\tau},\boldsymbol{\theta})\pi_{\tau-1}(d\boldsymbol{\theta})}$

7: end for

###  III-D Discussion on Regret Performance of Con-TS-RTP

The regret analysis of Con-TS-RTP is inspired by the results in [37] for TS
with nonlinear cost functions. The authors in [41] extended the regret results
from [37] by analyzing the effects of an objective function that is dependent
on exogenous parameters such as $\mathbf{V}_{\tau}$. The analysis in the
aforementioned papers provides bounds on the total number of times that
suboptimal price signals selected by the algorithm over $\mathcal{T}$ days as
specified in equation (14). The regret guarantee we provide in this work
extends the result further, allowing for constraints in the daily optimization
that are dependent on the sampled $\boldsymbol{\widetilde{\theta}}_{\tau}$. As
such, our regret guarantee applies to the Con-TS-RTP algorithm with
constraints as formulated in Constraint Set A in Algorithm 1. We refer the
reader to the appendix as well as [41] and [37] for further discussion on the
derivation of Theorem 1.

######  Assumption 1.

(Finitely many price signals, observations).
$|\mathcal{P}|,|\mathcal{Y}|<\infty$.

######  Assumption 2.

(Finite Prior,“Grain of truth”) The prior distribution $\pi$ is supported over
finitely many particles: $|\Theta|<\infty$. The true parameter exists within
the parameter space: $\boldsymbol{\theta}^{\star}\in\Theta$. The initial
distribution $\pi_{0}$ has non-zero mass on the true parameter
$\boldsymbol{\theta}^{\star}$ (i.e.,
$\mathbb{P}_{\pi_{0}}[\boldsymbol{\theta}^{\star}]>0$).

######  Assumption 3.

(Unique optimal price signal). There is a unique optimal price signal
$\mathbf{p}^{\mathbf{V},\star}$ for each exogenous parameter
$\mathbf{V}\in\mathcal{V}$.

######  Theorem 1.

Under assumptions 1-3 and Constraint Set A in Algorithm 1, for
$\delta,\epsilon\in(0,1)$, there exists $\mathcal{T}^{\star}\geq 0$ s.t. for
all $\mathcal{T}\geq\mathcal{T}^{\star}$, with probability $1-\delta$:

$\displaystyle\sum_{\mathbf{V}\in\mathcal{V}}\sum_{\mathbf{p}\in\\{\mathcal{P}\setminus\mathbf{p}^{\mathbf{V},\star}\\}}N_{\mathcal{T}}(\mathbf{p},\mathbf{V})\leq
B+C(\log\mathcal{T}),$ (15)

where $B\equiv B(\delta,\epsilon,\mathcal{P},\mathcal{Y},\Theta)$ is a
problem-dependent constant that does not depend on $\mathcal{T}$, and
$C(\log\mathcal{T})$ depends on $\mathcal{T}$, the sequence of selected price
signals, and the Kullback-Leibler divergence properties of the bandit problem
(i.e., the marginal Kullback-Leibler divergences of the observation
distributions
$\text{KL}\big{[}\ell(\mathbf{Y};\mathbf{p},\boldsymbol{\theta}^{\star}),\ell(\mathbf{Y};\mathbf{p},\boldsymbol{\theta})\big{]}$
(The complete description of the $C(\log\mathcal{T})$ term is left to the
appendix).

Proof. The proof is in the appendix.

In the next section, we discuss the distribution system reliability issue that
arises from how the Con-TS-RTP algorithm handles the distribution system
constraints (i.e., Constraint Set A) and a modification to the Con-TS-RTP
algorithm to ensure the constraints are enforced (i.e., Constraint Set B).

###  III-E Con-TS-RTP with Improved Reliability Constraints

In order for the aggregator to ensure safe operation of the distribution grid
while running the Con-TS-RTP algorithm, the reliability constraints need to
hold for the true price response model $\boldsymbol{\theta}^{\star}$ each day.
However, with the constraints formulated as in Algorithm 1’s Constraint Set A,
the distribution system constraints are only enforced for the sampled
$\boldsymbol{\widetilde{\theta}}_{\tau}$ and not necessarily the true
parameter $\boldsymbol{\theta}^{\star}$. This entails that the distributions
$\\{\phi_{c}\\}_{c\in\mathcal{C}}$ are parameterized by the sampled
$\boldsymbol{\widetilde{\theta}}_{\tau}$; therefore, they are inaccurate if
any parameter
$\boldsymbol{\widetilde{\theta}}_{\tau}\neq\boldsymbol{\theta}^{\star}$ is
sampled. This could potentially lead to many constraint violations throughout
the run of the algorithm resulting in inadequate service for the customers and
grid failures.

Due to the importance of reliable operation of the distribution system, we
present a modification to the Con-TS-RTP algorithm (i.e., replacing Constraint
Set A with Constraint Set B in Algorithm 1) to increase the reliability of the
selected prices and resulting load profiles with respect to the grid
constraints. Specifically, we propose alternate constraints that depend on the
algorithm’s current knowledge of the true parameter, instead of the sampled
parameter. In other words, instead of depending on
$\boldsymbol{\widetilde{\theta}}_{\tau}$, the proposed alternate constraints
depend on the prior distributions $\pi_{\tau-1}$ as follows:

$\displaystyle\mathbb{P}_{\\{\phi_{c}\\}_{c\in\mathcal{C}}}[u_{\tau}(t)\geq
u^{min}|\boldsymbol{\theta}\sim\pi_{\tau-1}]\geq 1-\nu,\;\;\forall t$ (16)
$\displaystyle\mathbb{P}_{\\{\phi_{c}\\}_{c\in\mathcal{C}}}[u_{\tau}(t)\leq
u^{max}|\boldsymbol{\theta}\sim\pi_{\tau-1}]\geq 1-\nu,\;\;\forall t$ (17)
$\displaystyle\mathbb{P}_{\\{\phi_{c}\\}_{c\in\mathcal{C}}}[f_{\tau}(t)\leq
S^{max}|\boldsymbol{\theta}\sim\pi_{\tau-1}]\geq 1-\nu,\;\;\forall t$ (18)

where $\nu$ is a small constant (detailed in Proposition 1). When considering
constraints (16)-(18) in the Con-TS-RTP algorithm, the algorithm will select
more conservative price signals each day that can guarantee the distribution
system’s constraints are met with high probability by using the information in
the updated prior distributions. Before analyzing the modified algorithm’s
reliability, we make the following assumption:

######  Assumption 4.

There exists $\xi^{\star}>0$ and $\lambda\geq 0$, such that for all
$\boldsymbol{\theta}\neq\boldsymbol{\theta}^{\star},\text{
KL}\big{[}\ell(\mathbf{Y};\mathbf{p},\boldsymbol{\theta}^{\star}),\ell(\mathbf{Y};\mathbf{p},\boldsymbol{\theta})\big{]}\geq\xi^{\star}$,
where

$\displaystyle\xi^{\star}_{\boldsymbol{\;\theta},\mathbf{p}}=\max_{x\in\mathbb{Z}^{>0}}\Bigg{\\{}\frac{-\lambda}{x}-\frac{4}{\sqrt{x}}\sqrt{\frac{\log{|\mathcal{Y}||\mathcal{P}|}}{\delta}+\frac{\log{x}}{2}}$
$\displaystyle\times\sum_{\mathbf{Y}\in\mathcal{Y}}\Big{|}\log{\frac{\ell(\mathbf{Y};\mathbf{p},\boldsymbol{\theta}^{\star})}{\ell(\mathbf{Y};\mathbf{p},\boldsymbol{\theta})}}\Big{|}\Bigg{\\}}$

and

$\displaystyle\xi^{\star}=\max_{\boldsymbol{\theta}\in\Theta,\mathbf{p}\in\mathcal{P}}\xi^{\star}_{\boldsymbol{\;\theta},\mathbf{p}}.$

Assumption 4 ensures that as the aggregator performs the steps in Algorithm 1,
the algorithm’s Bayesian updates of the prior distribution $\pi_{\tau}$ will
likely never decrease the mass of the true parameter
$\boldsymbol{\theta}^{\star}$ below a certain threshold. Specifically, with
Assumption 4, it can be shown (as in [37]) that with probability
$1-\delta\sqrt{2}$ the following holds for all $\tau\geq 1$:

$\displaystyle\pi_{\tau}(\boldsymbol{\theta}^{\star})\geq\pi_{0}(\boldsymbol{\theta}^{\star})e^{-\lambda|\mathcal{P}|},$
(19)

where $\lambda\geq 0$ is a chosen parameter (from Assumption 4) that dictates
the minimum reachable mass of the true parameter via Bayesian updating. With
the modified constraints (16)-(18) and the minimum mass of the true parameter
specified in (19), the reliability of Con-TS-RTP can be characterized as
follows:

######  Proposition 1.

Under assumptions 1-4, with $\nu$ in equations (16)-(18) chosen such that
$\nu\leq\mu\pi_{0}(\boldsymbol{\theta}^{\star})e^{-\lambda|\mathcal{P}|}$,
with probability $1-\delta\sqrt{2}$, the Con-TS-RTP algorithm with Constraint
Set B will uphold the probabilistic distribution system constraints as
formulated in (12) for each day $\tau=1,\dots,\mathcal{T}$.

Proof. The proof is in the appendix.
Remark: The novelty of Con-TS-RTP is that we can ensure with high probability
an unsafe price signal is never selected. We can tune the safety parameter to
determine what level of risk is acceptable to the aggregator. We note that the
selection of an unsafe price signal has no effect on the learning capability
of the algorithm. The Con-TS-RTP algorithm will learn regardless of
safe/unsafe price signals. The algorithm will never crash/stop prematurely due
to the selection of an unsafe price signal; however, the local distribution
grid might surpass safety limits on transformers or line flow limits due to an
unsafe price selection on select very limited days, at which points protective
measures (e.g., relays) should be used to ensure physical grid safety. We note
that this is natural for any learning algorithm dealing with stochastic
conditions and unknown system parameters. Contingencies can never be avoided
100%, similar to other grid operation paradigms that deal with uncertain
conditions (e.g., wholesale market dispatch with renewables or possible
transmission system contingencies). They could only be avoided with a certain
high probability when making dispatch decisions. However, it is understood
that other protective measures should always be put in place to avoid physical
system damage in case of contingencies.

##  IV Experimental Evaluation

###  IV-A Test Setup: Radial Distribution System

In this section we describe the power distribution system and the
corresponding network parameters for the test case. We consider an actual
radial distribution system from the ComEd service territory in Illinois, USA
(adopted from [42] and shown in Fig. 1) represented by the undirected graph
$\mathcal{G}$ which includes a set of nodes (vertices) $\mathcal{N}$ and a set
of power lines (edges) $\mathcal{L}$.

Figure 1: Radial distribution system.

In this work, we consider each node as one population with its own daily load
profile; however, each node could be an aggregation of smaller entities
downstream of the local distribution connection point. The undirected graph is
organized as a tree, with the root node representing the distribution system’s
substation where it is connected to the regional transmission system. We
denote $N$ as the total number of nodes in the network excluding the root
node. The nodes are indexed as $i=0,\dots,N$, and the node corresponding to
$i=0$ (i.e., the root node) is the substation. The power lines are indexed by
$i=1,\dots,N$ where the $i$-th line is directly upstream of node $i$ (i.e.,
line $i$ feeds directly to node $i$). In the following, we denote the parent
vertex of node $i$ as $\mathcal{A}_{i}$ and the set of children vertices of
node $i$ as $\mathcal{K}_{i}$.

Furthermore, we assume the aggregator has access to measurement data at each
node’s local connection point. Specifically, the aggregator measures the
active power demands at each node $i$ at time $t$ on day $\tau$ denoted as
$d_{i,\tau}^{P}(t)$. In order to ensure the delivered power is suitable for
the electricity customers, the aggregator also monitors node $i$’s local
voltage at time $t$ on day $\tau$ denoted as $v_{i,\tau}(t)$. In the
following, we denote the active power daily load profile of node $i$ on day
$\tau$ as $\mathbf{D}_{i,\tau}^{P}=[d_{i,\tau}^{P}(t)]_{t=1,\dots,T}$.
Additionally, the aggregator records the active power flows
$f_{i,\tau}^{P}(t)$ on each line $i\in\mathcal{L}$. We note that reactive
power should also be monitored in distribution systems, even though it is
generally not priced and customers do not consider it in determining their
optimal load response to prices. As such, we use the superscript $Q$ for the
reactive power at a node, $d_{i,\tau}^{Q}(t)$, and for reactive power flow on
a line, $f_{i,\tau}^{Q}(t)$. Each line in the distribution system has its own
internal resistance denoted as $R_{i}$, reactance denoted as $X_{i}$, and
power limit denoted as $S_{i}^{max}$. The parameters for the distribution
system are listed in Table I.

Line |  R |  X |  Smax |  Line |  R |  X |  Smax
---|---|---|---|---|---|---|---
|  ($10^{-3}\Omega$) |  ($10^{-3}\Omega$) |  (KVA) |  |  ($10^{-3}\Omega$) |  ($10^{-3}\Omega$) |  (KVA)
1 |  24.2 |  48.2 |  54 |  20 |  129.5 |  30.9 |  10.8
2 |  227.3 |  743.5 |  84 |  21 |  15.1 |  5.4 |  14.4
3 |  76.3 |  18.2 |  10.8 |  22 |  50.8 |  12.1 |  10.8
4 |  43.6 |  142.7 |  84 |  23 |  69.1 |  16.5 |  10.8
5 |  25.8 |  84.4 |  84 |  24 |  31.6 |  11.2 |  14.4
6 |  10.5 |  10.7 |  40.2 |  25 |  96.3 |  23 |  10.8
7 |  23.2 |  23.6 |  40.2 |  26 |  110.7 |  112.6 |  40.2
8 |  75.1 |  26.7 |  14.4 |  27 |  2.1 |  0.7 |  14.4
9 |  114.4 |  27.3 |  10.8 |  28 |  242.1 |  86.2 |  14.4
10 |  110.8.3 |  67.7 |  14.4 |  29 |  27.3 |  27.8 |  40.2
11 |  63.7 |  22.7 |  14.4 |  30 |  174.6 |  62.1 |  16.2
12 |  278.7 |  99.2 |  14.4 |  31 |  43 |  15.3 |  10.8
13 |  254.2 |  10.8.5 |  14.4 |  32 |  207.8 |  74 |  10.8
14 |  21.8 |  5.2 |  10.8 |  33 |  109.4 |  38.9 |  14.4
15 |  57.3 |  20.4 |  14.4 |  34 |  50.5 |  18 |  14.4
16 |  126.7 |  45.1 |  14.4 |  35 |  165.2 |  58.8 |  14.4
17 |  48.6 |  11.6 |  10.8 |  36 |  49.5 |  17.6 |  14.4
18 |  95.1 |  22.7 |  10.8 |  37 |  5.8 |  2.1 |  14.4
19 |  137.3 |  32.8 |  10.8 |  |  |  |
TABLE I: Distribution system parameters.

###  IV-B Power Flow Model

In order to solve for the power flow and nodal voltages of the power
distribution system, we make use of the LinDistFlow model[43], which is a
linear approximation for the AC power flow model444The reader should note that
the proposed learning approach is not limited to the LinDistFlow model. There
are other power flow models that can be utilized such as [44].. The
LinDistFlow model has been extensively studied and verified to be competitive
to the nonlinear AC flow model on many realistic feeder topologies including
radial [45, 46, 47, 48]. The LinDistFlow model reduces computational
complexity by making use of the following linear power flow and voltage
equations:

$\displaystyle
d_{i,\tau}^{P}(t)+\sum_{j\in\mathcal{K}_{i}}f_{j,\tau}^{P}(t)=f_{\mathcal{A}_{i},\tau}^{P}(t);\;\;$
$\displaystyle\forall t,\tau,i,$ (20) $\displaystyle
d_{i,\tau}^{Q}(t)+\sum_{j\in\mathcal{K}_{i}}f_{j,\tau}^{Q}(t)=f_{\mathcal{A}_{i},\tau}^{Q}(t);\;\;$
$\displaystyle\forall t,\tau,i,$ (21) $\displaystyle
u_{\mathcal{A}_{i},\tau}(t)-2\big{(}f_{i,\tau}^{P}(t)R_{i}+f_{i,\tau}^{Q}(t)X_{i}\big{)}=u_{i,\tau}(t);\;$
$\displaystyle\forall t,\tau,i$ (22)

where (20) accounts for active power and (21) accounts for reactive power. In
(22) we make use of the operator
$u_{i,\tau}(t)=\big{(}v_{i,\tau}(t)\big{)}^{2}$ to provide a linear voltage
drop relationship across the distribution system. For the scope of this work,
we assume that the substation connection to the regional transmission system
(node $i=0$) is regulated and has a fixed voltage
$v_{0,\tau}(t)={\color[rgb]{0,0,0}12.5\textrm{kV}},\forall t,\tau$.

###  IV-C Distribution System Operational Constraints

The nodal voltages and line flows calculated in (20)-(22) should obey the
following constraints for reliable operation:

$\displaystyle u_{i,\tau}(t)$ $\displaystyle\geq u_{i}^{min},$
$\displaystyle\forall t,\tau,i\in\mathcal{N},$ (23) $\displaystyle
u_{i,\tau}(t)$ $\displaystyle\leq u_{i}^{max},$ $\displaystyle\forall
t,\tau,i\in\mathcal{N},$ (24) $\displaystyle
f_{i,\tau}^{P}(t)^{2}+f_{i,\tau}^{Q}(t)^{2}$
$\displaystyle\leq(S_{i}^{max})^{2},$ $\displaystyle\forall
t,\tau,i\in\mathcal{L},$ (25)

where (23)-(24) are the nodal voltage constraints and (25) corresponds to the
power constraints for each distribution line.

Figure 2: The 5 plots above portray the evolution of the aggregator’s
knowledge of the population’s hidden parameter at node 10 throughout the
learning procedure. The true parameter is parameter 4. From left to right: Day
1 (initialized to uniform distribution, i.e., no knowledge of the true
parameter), Day 15 prior, Day 30 prior, Day 90 prior, and Day 180 prior. At
day 180, the aggregator is about 95% certain that parameter 4 is the true
parameter.

###  IV-D Load Model and Multi-armed Bandit Formulation

In this test case, we consider 6 time slots each day, each 4 hours long. We
consider 10 unique target load profile vectors, with the daily target profile
$\mathbf{V}_{\tau}$ for day $\tau$ drawn from a uniform distribution each
morning. Each of the 10 target load profile vectors corresponds to a desired
load curve to accommodate different levels of forecasted renewable generation.
Furthermore, the aggregator transmits daily price signals
$\mathbf{p}_{i,\tau}$ to each node within the system. The aggregator has a
high and low price for each of the 6 time slots resulting in $2^{6}$ possible
daily price signals. Since the aggregator is shaping the electricity demand at
each node within the distribution system, each node has its own cost
$f\big{(}\mathbf{D}_{i,\tau}(\mathbf{p}_{i,\tau}),\mathbf{V}_{\tau}\big{)}$
that is dependent on the node’s daily demand and the target profile. In this
test case, we assume the cost function for each node is the squared deviation
of the node’s electricity demand from the target profile:
$f\big{(}\mathbf{D}_{i,\tau}(\mathbf{p}_{i,\tau}),\mathbf{V}_{\tau}\big{)}=|\mathbf{D}_{i,\tau}(\mathbf{p}_{i,\tau})-\mathbf{V}_{\tau}|^{2}$,
thus equally penalizing over-usage and under-usage of electricity. We note
that the units are KW2 and if the aggregator had a converting function for the
squared deviation (KW2) to $\$$U.S.D., then we could calculate the monetary
losses of the system. In our experimental examples, we make use of discrete
sets for the available $\theta$’s and $\mathbf{p}_{\tau}$’s to guarantee that
an enumeration-based method could solve for the globally optimal price signals
each day in spite of problem non-convexities.

We consider 20 unique load flexibility clusters in this test case. Each
cluster’s parameters represent the varying start/stop times, total energy
demands, and power limitations common to EV loads in residential areas and are
of the form presented in equation (6). We note that we generated the
population’s load price response directly using the same clustering model
(i.e., the actual load response in the simulation is at the level of 20
clusters and can be well represented by the 20 clusters plus additive noise.
For a discussion on the effects of poor clustering, we refer the reader to
Section IV-F). Each node in the distribution system is comprised of these 20
load clusters with its own unique sensitivities $a_{i,c}(\mathbf{p}_{\tau})$
for each cluster. Each sensitivity parameter is selected as
$a_{i,c}(\mathbf{p}_{i,\tau})\sim\mathcal{N}(\frac{\beta_{c}}{\boldsymbol{\theta}_{i}^{\star}\mathbf{p}_{i,\tau}},\sigma^{2})$
each day where $\beta_{c}$ is a cluster specific constant known by the
aggregator (we note that $\beta_{c}$ represents a priori knowledge of
customers’ preferences and could come from behavioral studies; however, our
framework does not require this and $\beta_{c}$ can be completely omitted in
cases where prior information is unavailable). Each node’s price sensitivity,
i.e., parameter to be learned, $\boldsymbol{\theta}_{i}^{\star}$, is a vector
of length 6 and the set of possible parameters, $\Theta$, contains 10 unique
vectors. Unless noted, the reliability parameter chosen for the Con-TS-RTP
algorithm is $\nu=0.1$.

Note on reactive power: We note that reactive power is generally price
insensitive; however, reactive power is present in a distribution system and
affects the constraints of the system. Reactive power flows alter how the
price sensitive loads are limited by the operational constraints of the system
(i.e., active and reactive flows on lines affect the capacity available for
the price responsive loads). Due to the lack of data as to how much reactive
power is present in the distribution system due to our appliance clusters and
otherwise, for our numerical examples, we omit the inclusion of reactive power
to only view the appliance clusters’ active load profiles within the
distribution system. For further discussion on this, we refer the reader to
papers that fully capture the effects of reactive power in such problems such
as [49] and [50] in which the authors showcase techniques to handle
distribution systems with chance constraints.

In the following sections, without loss of generality, we assume that reactive
power is not responsive to the pricing signals. We note that our proposed
learning approach can accommodate reactive power flows (LinDistFlow can as
well); however, our goal was to show proof of concept of our learning/pricing
approach with active customer loads, thus reactive power flow will be examined
in future work.

###  IV-E Results

We simulated the Con-TS-RTP algorithm for 365 days for an aggregator
attempting to learn the sensitivities of the nodes in the system and shape
their demands. In the following, we highlight the results of the simulation at
node 10 of the radial distribution system. Figure 2 presents the evolution of
the prior distribution for node 10’s hidden parameter. On day 1, the prior was
initialized to a uniform distribution among the candidate parameters, and by
day 180 the weight on the true parameter exceeded $0.95$.

Figure 3 presents the regret performance of Con-TS-RTP at node 10. As seen in
Figure 3, the regret curve flattens after day 130 as the algorithm never
chooses a suboptimal price signal after this day.

Figure 3: Regret performance of Con-TS-RTP at node 10 with $\nu=0.1$. Note
that the y-axis (left) units are KW2 for the squared load deviation from the
target profile.

Figure 4 presents node 10’s deviation from a specific daily target profile. On
days 2, 3, 4, 53, and 365 the same target profile (i.e.,
$\mathbf{V}_{2}=\mathbf{V}_{3}=\mathbf{V}_{4}=\mathbf{V}_{53}=\mathbf{V}_{365}$)
was drawn and the aggregator selected different price signals to shape the
node’s demand. As seen in Fig. 4, the deviation from the target profile on day
365 is less than the deviation on the other days as the algorithm has learned
the true parameter and selects the optimal price signal to shape the load.

Figure 4: Deviation of node 10’s demand from a specific daily target profile.

In Figure 5, we present the distribution system constraint violations that
were avoided by using Con-TS-RTP instead of an unconstrained TS algorithm.
Clearly, in the early learning stages, the unconstrained TS algorithm does not
have accurate knowledge of the hidden parameters and violates the distribution
system constraints often. Con-TS-RTP is more conservative with its exploration
of untested price signals and avoids the constraint violations made by the
unconstrained TS algorithm. Last, we note that the simulation was implemented
in Matlab and CVX on an i7 processor with 16gb of RAM. The 365 day simulations
were run in less than 5 minutes.

Figure 5: Top: Distribution system constraint violations at node 10 avoided by
using Con-TS-RTP instead of an unconstrained TS. Bottom: Distribution system
constraint violations across the entire system avoided by using Con-TS-RTP
instead of an unconstrained TS.

###  IV-F Effects of Clustering

In this section, we portray the effects of selecting different numbers of
clusters to represent a true load as well as the effects of selecting too few
clusters on the performance of our Con-TS-RTP algorithm. First, in Figure 6,
we perform a simple demonstration. We considered a population of 100 EVs with
random charging requests and then constructed clusters to view the accuracy of
the clustered load profiles versus the actual load profile. As shown in Figure
6, using 1, 5, or 10 clusters to represent the EV population results in load
profiles quite different from the actual; however, with 20 clusters, the load
profile begins to match the actual profile.

Figure 6: Effects of changing the number of clusters to model an actual load.
Specifically, load profiles for 4 cluster models compared to the actual load
profile for a population of 100 charging EVs.

Furthermore, in Figure 7 we show the effects of reducing the number of
clusters in the load model on the regret performance of our Con-TS-RTP
algorithm. Specifically, we focus on the same setup as Section IV-D with the
exception that we have the Con-TS-RTP algorithm use a 10 cluster model instead
of the 20 cluster model for the population to see the effects of an inaccurate
cluster model. As shown in Figure 7, the regret curve for this case never
flattens and the algorithm is never able to select the optimal price signal.
This is because the algorithm’s model of the load (i.e., the 10 clusters) is
unable to accurately model the population’s response and causes the algorithm
to select incorrect prices every day.

Figure 7: Effects of using too few clusters for the population’s load model.
We show the regret performance of Con-TS-RTP at node 10 with $\nu=0.1$ for a
10 cluster model instead of the 20 cluster model as previously shown in Fig.
3. Due to the inaccuracies of the 10 cluster model, the algorithm is never
able to select the optimal price signals.

###  IV-G Evolving Price Sensitivity

In this section, we show an example of what happens when customers’
sensitivities change over time and how a Bayesian learning approach can
naturally adapt and account for these dynamic changes. Specifically, we
simulated the same system as in Figure 3, but on day 250, we altered the true
$\boldsymbol{\theta}^{\star}_{i}$ parameter. As seen in Figure 8, the regret
curves first flatten around day 125, then increase at day 250, and then
flatten again near day 325. This shows that Con-TS-RTP was able to
successfully learn the first and second true parameter without any
modifications to the algorithm. The algorithm naturally shifts its belief
about the true parameter as it observes outputs that do not match its current
belief.

Figure 8: Regret performance of Con-TS-RTP at node 10 with $\nu=0.1$. Note
that on day 250, the hidden parameter was altered.

###  IV-H Non-repeating Target Profiles

In the previous case study, we assumed a low number of target profiles (10
profiles) to satisfy the assumptions we have made for our theoretical results.
In this section, we demonstrate how extending the number of target profiles to
365 does not negatively affect the performance of the algorithm in practice.
Furthermore, we ensure that once a target profile has been viewed by the
aggregator, it is never drawn again. Thus, each day the aggregator is posting
a price to shape the population’s load to match a target profile that it has
never seen before. As shown in Figure 9, enlarging the set of target profiles
does not slow down the learning process. Note that in Figure 9 the regret
flattens near trial 100 which matches the duration of the learning period seen
in Figure 3 (i.e., in simulation, the aggregator is still able to learn the
true parameter when the number of target profiles is increased from 10 to 365,
resulting in similar regret curves).

Figure 9: Regret performance of Con-TS-RTP at node 10 with $\nu=0.1$. Note
that on each day, the sampled $\mathbf{V}_{\tau}$ has never been seen by the
aggregator.

###  IV-I Effects of Varying the System Reliability Metric

In this section, we discuss the effects of varying the system reliability
parameters in the daily optimization’s constraints (i.e., altering the value
of $\nu$ for the system constraints formulated as in (16)-(18)). As described
in Sections II-D and III-E, the reliability metric dictates the aggregator’s
allowable probability of a constraint violation under its current belief
distribution about the unknown parameter. Decreasing $\nu$ is restricting the
algorithm to avoid violations and setting $\nu=1$ is equivalent to solving the
daily optimization without the constraints altogether. In Figure 10, we
simulated the system with varying reliability parameters. Specifically, each
curve shown is the average regret at node 10 over 20 independent simulations.
As shown in Figure 10, the regret increases as the desired reliability
increases (smaller $\nu$). This is because the aggregator is forced to select
more conservative prices during the learning procedure to ensure that the
constraints are met with higher probability.

Figure 10: Regret curves for various system reliability metrics. Each curve is
an average of 20 independent simulations.

###  IV-J Comparison with Two-Stage Learning

In this section, we present a comparison of the Con-TS-RTP approach versus a
2-stage “learn” and then “optimize” algorithm, where the first stage consists
of pure exploration and the second stage purely exploits the knowledge gained
in the first stage. The simulation setup is the same as the setup used in
Section IV-D. A description of the 2-stage algorithm used is as follows: The
aggregator decides the duration of the learning stage a priori, (in Figure 11,
we present regret curves for learning stages with durations of 5, 15, and 25
days) and during this learning stage, the aggregator randomly selects price
signals from a predetermined safe set of prices (i.e., prices high enough such
that constraints cannot be violated), observes the populations’ responses, and
performs posterior updates. Then, after the learning stage is complete, for
the remainder of time the aggregator broadcasts the best price signals with
respect to the knowledge of the unknown parameter at the end of the learning
stage (the selected price signal will ensure safety but might be potentially
suboptimal depending on the duration of the learning stage). Clearly, the two
most significant shortcomings of the 2-stage approach are: 1) arbitrarily bad
performance during the learning stage due to random price selection; and 2)
difficulty selecting a sufficient duration of the learning stage. As seen in
Figure 11, this 2-stage myopic algorithm results in linear regret in the 5 day
and 15 day learning stage curves. Due to an insufficient number of posterior
updates, the aggregator is forced to post suboptimal price signals to ensure
safety given its noisy knowledge of the unknown parameter after the learning
stage is over. On the other hand, the 25 day learning stage is able to
converge to the optimal price signals, but the performance during the learning
stage causes fast growth of regret whereas Con-TS-RTP is able to avoid all of
the aforementioned shortcomings.

Figure 11: Regret performance of Con-TS-RTP and a 2-Stage algorithm at node 10
with $\nu=0.1$. Note that the 5 day (blue) and 15 day (red) learning
algorithms were unable to converge to the optimal price signals. The blue and
red curves never flatten because their learning stages were too brief to
adequately learn the customers’ preferences and are unable to select the
optimal price signals, resulting in a linearly growing regret. However, the 25
day (yellow) learning stage algorithm is able to adequately learn the
population’s parameters and select optimal prices after that.

##  V Conclusion

In this paper, we presented a multi-armed bandit problem formulation for an
electricity aggregator attempting to run a real-time pricing program for load
shaping (e.g., to reduce demand at peak hours, integrate more intermittent
renewables, track a desired daily load profile, etc). We made use of a
constrained Thompson sampling heuristic, Con-TS-RTP, as a solution to the
exploration/exploitation problem of an aggregator passively learning
customers’ price sensitivities while broadcasting price signals that influence
customers to alter their demand to match a desired load profile. The proposed
Con-TS-RTP algorithm permits day-varying target load profiles (i.e., multiple
target load profiles reflecting renewable forecasts and desired demand
patterns) and takes into account the actual operational constraints of a
distribution system to ensure that the customers receive adequate service and
to avoid potential grid failures. Additionally, our setup accounts for complex
electricity usage patterns of the customers by classifying different load
clusters based on electricity demand and load flexibility. We discussed a
regret guarantee for the proposed Con-TS-RTP algorithm which bounds the total
number of suboptimal price signals broadcasted by the aggregator. Furthermore,
we discussed an operational reliability guarantee that ensures the power
distribution system constraints are upheld with high probability throughout
the run of the Con-TS-RTP algorithm.

## References

  * [1] C. Eid, E. Koliou, M. Valles, J. Reneses, and R. Hakvoort, “Time-based pricing and electricity demand response: Existing barriers and next steps,” _Utilities Policy_ , vol. 40, pp. 15 – 25, 2016.
  * [2] V. Gomez, M. Chertkov, S. Backhaus, and H. J. Kappen, “Learning price-elasticity of smart consumers in power distribution systems,” in _2012 SmartGridComm_. IEEE, 2012, pp. 647–652.
  * [3] Z. Xu, T. Deng, Z. Hu, Y. Song, and J. Wang, “Data-driven pricing strategy for demand-side resource aggregators,” _IEEE Transactions on Smart Grid_ , vol. 9, no. 1, pp. 57–66, 2016.
  * [4] P. Li and B. Zhang, “Linear estimation of treatment effects in demand response: An experimental design approach,” _arXiv preprint arXiv:1706.09835_ , 2017.
  * [5] P. Li, H. Wang, and B. Zhang, “A distributed online pricing strategy for demand response programs,” _IEEE Transactions on Smart Grid_ , vol. 10, no. 1, pp. 350–360, 2017.
  * [6] K. Khezeli, W. Lin, and E. Bitar, “Learning to buy (and sell) demand response,” _IFAC-PapersOnLine_ , vol. 50, no. 1, pp. 6761–6767, 2017.
  * [7] L. Jia, L. Tong, and Q. Zhao, “An online learning approach to dynamic pricing for demand response,” _arXiv preprint arXiv:1404.1325_ , 2014.
  * [8] K. Khezeli and E. Bitar, “Risk-sensitive learning and pricing for demand response,” _IEEE Transactions on Smart Grid_ , vol. 9, no. 6, pp. 6000–6007, 2017.
  * [9] L. Jia, Q. Zhao, and L. Tong, “Retail pricing for stochastic demand with unknown parameters: An online machine learning approach,” in _2013 51st Allerton_. IEEE, 2013, pp. 1353–1358.
  * [10] D. Zhou, M. Balandat, and C. Tomlin, “Residential demand response targeting using machine learning with observational data,” in _2016 IEEE 55th Conference on Decision and Control (CDC)_. IEEE, 2016, pp. 6663–6668.
  * [11] Y. Li, Q. Hu, and N. Li, “Learning and selecting the right customers for reliability: A multi-armed bandit approach,” in _2018 IEEE Conference on Decision and Control (CDC)_. IEEE, 2018, pp. 4869–4874.
  * [12] D. Kalathil and R. Rajagopal, “Online learning for demand response,” in _2015 53rd Annual Allerton Conference on Communication, Control, and Computing (Allerton)_. IEEE, 2015, pp. 218–222.
  * [13] E. Dall’Anese, K. Baker, and T. Summers, “Chance-constrained ac optimal power flow for distribution systems with renewables,” _IEEE Transactions on Power Systems_ , vol. 32, no. 5, pp. 3427–3438, 2017.
  * [14] R. Mieth and Y. Dvorkin, “Data-driven distributionally robust optimal power flow for distribution systems,” _IEEE Control Systems Letters_ , vol. 2, no. 3, pp. 363–368, 2018.
  * [15] ——, “Online learning for network constrained demand response pricing in distribution systems,” _arXiv:1811.09384_ , 2018.
  * [16] Yi Wang, Qixin Chen, Chongqing Kang, Mingming Zhang, Ke Wang, and Yun Zhao, “Load profiling and its application to demand response: A review,” _Tsinghua Science and Technology_ , vol. 20, no. 2, pp. 117–129, April 2015.
  * [17] J. L. Mathieu, S. Koch, and D. S. Callaway, “State estimation and control of electric loads to manage real-time energy imbalance,” _IEEE Transactions on Power Systems_ , vol. 28, no. 1, pp. 430–440, 2012.
  * [18] J. M. Foster and M. C. Caramanis, “Optimal power market participation of plug-in electric vehicles pooled by distribution feeder,” _IEEE Transactions on power systems_ , vol. 28, no. 3, pp. 2065–2076, 2013.
  * [19] S. Lin, F. Li, E. Tian, Y. Fu, and D. Li, “Clustering load profiles for demand response applications,” _IEEE Transactions on Smart Grid_ , vol. 10, no. 2, pp. 1599–1607, March 2019.
  * [20] W. Zhang, J. Lian, C. Chang, and K. Kalsi, “Aggregated modeling and control of air conditioning loads for demand response,” _IEEE Transactions on Power Systems_ , vol. 28, no. 4, pp. 4655–4664, Nov 2013.
  * [21] C. Chelmis, J. Kolte, and V. K. Prasanna, “Big data analytics for demand response: Clustering over space and time,” in _2015 IEEE International Conference on Big Data (Big Data)_ , Oct 2015, pp. 2223–2232.
  * [22] Y. Zhang, W. Chen, R. Xu, and J. Black, “A cluster-based method for calculating baselines for residential loads,” _IEEE Transactions on Smart Grid_ , vol. 7, no. 5, pp. 2368–2377, Sep. 2016.
  * [23] J. Kwac, J. Flora, and R. Rajagopal, “Household energy consumption segmentation using hourly data,” _IEEE Transactions on Smart Grid_ , vol. 5, no. 1, pp. 420–430, 2014.
  * [24] M. Alizadeh, A. Scaglione, A. Applebaum, G. Kesidis, and K. Levitt, “Reduced-order load models for large populations of flexible appliances,” _IEEE Transactions on Power Systems_ , vol. 30, no. 4, 2015.
  * [25] M. Alizadeh, A. Scaglione, R. J. Thomas, and D. Callaway, “Information infrastructure for cellular load management in green power delivery systems,” in _2011 SmartGridComm_. IEEE, pp. 13–18.
  * [26] T.-H. Chang, M. Alizadeh, and A. Scaglione, “Coordinated home energy management for real-time power balancing,” in _2012 IEEE Power and Energy Society General Meeting_. IEEE, 2012, pp. 1–8.
  * [27] M. Alizadeh and A. Scaglione, “Least laxity first scheduling of thermostatically controlled loads for regulation services,” in _2013 IEEE GlobalSIP_. IEEE, 2013, pp. 503–506.
  * [28] A. Krishnamurthy, Z. S. Wu, and V. Syrgkanis, “Semiparametric contextual bandits,” _arXiv preprint arXiv:1803.04204_ , 2018.
  * [29] D. J. Foster, A. Agarwal, M. Dudík, H. Luo, and R. E. Schapire, “Practical contextual bandits with regression oracles,” _arXiv preprint arXiv:1803.01088_ , 2018.
  * [30] T. Xu, Y. Yu, J. Turner, and A. Regan, “Thompson sampling in dynamic systems for contextual bandit problems,” _arXiv preprint arXiv:1310.5008_ , 2013\.
  * [31] D. J. Russo, B. Van Roy, A. Kazerouni, I. Osband, Z. Wen _et al._ , “A tutorial on thompson sampling,” _Foundations and Trends® in Machine Learning_ , vol. 11, no. 1, pp. 1–96, 2018\.
  * [32] D. Russo and B. Van Roy, “Learning to optimize via posterior sampling,” _Mathematics of Operations Research_ , vol. 39, no. 4, pp. 1221–1243, 2014\.
  * [33] S. Agrawal and N. Goyal, “Analysis of thompson sampling for the multi-armed bandit problem,” in _Conference on Learning Theory_ , 2012, pp. 39–1.
  * [34] P. Auer, “Using confidence bounds for exploitation-exploration trade-offs,” _Journal of Machine Learning Research_ , vol. 3, no. Nov, pp. 397–422, 2002\.
  * [35] V. Dani, T. P. Hayes, and S. M. Kakade, “Stochastic linear optimization under bandit feedback,” 2008.
  * [36] Y. Abbasi-Yadkori, D. Pál, and C. Szepesvári, “Improved algorithms for linear stochastic bandits,” in _Advances in Neural Information Processing Systems_ , 2011, pp. 2312–2320.
  * [37] A. Gopalan, S. Mannor, and Y. Mansour, “Thompson sampling for complex online problems,” in _International Conference on Machine Learning_ , 2014, pp. 100–108.
  * [38] S. Amani, M. Alizadeh, and C. Thrampoulidis, “Linear stochastic bandits under safety constraints,” in _Advances in Neural Information Processing Systems_ , 2019, pp. 9252–9262.
  * [39] A. Moradipari, S. Amani, M. Alizadeh, and C. Thrampoulidis, “Safe linear thompson sampling,” _arXiv preprint arXiv:1911.02156_ , 2019.
  * [40] V. Saxena, J. Jaldén, J. E. Gonzalez, I. Stoica, and H. Tullberg, “Constrained thompson sampling for wireless link optimization,” _arXiv preprint arXiv:1902.11102_ , 2019.
  * [41] A. Moradipari, C. Silva, and M. Alizadeh, “Learning to dynamically price electricity demand based on multi-armed bandits,” in _2018 IEEE GlobalSIP_ , Nov 2018, pp. 917–921.
  * [42] P. Andrianesis, M. Caramanis, R. Masiello, R. Tabors, and S. Bahramirad, “Locational marginal value of distributed energy resources as non-wires alternatives,” _IEEE Transactions on Smart Grid_ , 2019.
  * [43] M. E. Baran and F. F. Wu, “Optimal capacitor placement on radial distribution systems,” _IEEE Transactions on Power Delivery_ , vol. 4, no. 1, pp. 725–734, Jan 1989.
  * [44] M. D. Sankur, R. Dobbe, E. Stewart, D. S. Callaway, and D. B. Arnold, “A linearized power flow model for optimization in unbalanced distribution systems,” _arXiv preprint arXiv:1606.04492_ , 2016.
  * [45] H. J. Liu, “Decentralized optimization approach for power distribution network and microgrid controls,” Ph.D. dissertation, University of Illinois at Urbana-Champaign, 2017.
  * [46] H. Zhu and H. J. Liu, “Fast local voltage control under limited reactive power: Optimality and stability analysis,” _IEEE Transactions on Power Systems_ , vol. 31, no. 5, pp. 3794–3803, 2016.
  * [47] P. Šulc, S. Backhaus, and M. Chertkov, “Optimal distributed control of reactive power via the alternating direction method of multipliers,” _IEEE Transactions on Energy Conversion_ , vol. 29, no. 4, 2014.
  * [48] M. Farivar, L. Chen, and S. Low, “Equilibrium and dynamics of local voltage control in distribution systems,” in _52nd IEEE Conference on Decision and Control_. IEEE, 2013, pp. 4329–4334.
  * [49] M. Lubin, Y. Dvorkin, and L. Roald, “Chance constraints for improving the security of ac optimal power flow,” _IEEE Transactions on Power Systems_ , vol. 34, no. 3, pp. 1908–1917, 2019.
  * [50] R. Mieth and Y. Dvorkin, “Distribution electricity pricing under uncertainty,” _IEEE Transactions on Power Systems_ , pp. 1–1, 2019.

## Appendix

###  V-A Table of Notation

$\displaystyle{\tau}$ Day index $\displaystyle\mathcal{T}$ Total number of
days $\displaystyle t$ Time of day index $\displaystyle T$ Number of time
epochs in a day $\displaystyle\mathbf{p}_{\tau}$ Daily dispatch signal
$\displaystyle\mathcal{P}$ Set of available dispatch signals $\displaystyle
f(\cdot)$ Aggregator’s fixed daily cost function
$\displaystyle\mathbf{D}_{\tau}(\mathbf{p}_{\tau})$ Population’s daily load
response $\displaystyle\mathbf{V}_{\tau}$ Daily exogenous parameter
$\displaystyle\mathcal{V}$ Set of exogenous parameters $\displaystyle
g(\cdot)$ General reliability constraint $\displaystyle u_{\tau}(t)$
$\displaystyle\text{Nodal voltage at time }t\text{ on day }\tau$
$\displaystyle f_{\tau}(t)$ $\displaystyle\text{Power flow at time }t\text{ on
day }\tau$ $\displaystyle c$ Flexible appliance cluster index
$\displaystyle\mathcal{C}$ Set of flexible appliance clusters
$\displaystyle\mathbf{D}_{c}$ $\displaystyle\text{Load profile for cluster }c$
$\displaystyle\mathcal{D}_{c}$ $\displaystyle\text{Set of load profiles for
cluster }c$ $\displaystyle E_{c}$ $\displaystyle\text{Total energy required by
cluster }c$ $\displaystyle\rho_{c}$ $\displaystyle\text{Maximum power rating
for cluster }c$ $\displaystyle a_{c}(\mathbf{p}_{\tau})$
$\displaystyle\text{Preference adjustment model for cluster }c$
$\displaystyle\mathcal{D}$ Set of load profiles for entire population
$\displaystyle\widetilde{\mathbf{D}}_{c,\tau}(\mathbf{p}_{\tau})$
$\displaystyle\text{Minimum cost load profile of cluster }c$
$\displaystyle\mathbf{D}_{\tau}^{\star}(\mathbf{p}_{\tau})$
$\displaystyle\text{Population's realized load profile on day }\tau$
$\displaystyle\phi_{c}$ $\displaystyle\text{Preference adjustment distribution
for cluster }c$ $\displaystyle\boldsymbol{\theta}^{\star}$ True customer
sensitivity model $\displaystyle\Theta$ Set of candidate sensitivity models
$\displaystyle\mu$ Aggregator’s desired reliability metric $\displaystyle\nu$
Alternate reliability metric $\displaystyle R_{\mathcal{T}}$
$\displaystyle\text{Cumulative regret after day }\mathcal{T}$ $\displaystyle
N_{\tau}(\mathbf{p},\mathbf{V})$ $\displaystyle\text{Number of times price
}\mathbf{p}\text{ selected in response }$ $\displaystyle\text{to vector
}\mathbf{V}\text{ up to day }\tau$ $\displaystyle\pi_{\tau}$
$\displaystyle\text{Prior distribution (aggregator's belief on
}\boldsymbol{\theta}^{\star})$
$\displaystyle\widetilde{\boldsymbol{\theta}}_{\tau}$
$\displaystyle\text{Sampled parameter on day }\tau$
$\displaystyle\mathbf{Y}_{\tau}$ $\displaystyle\text{Observed load profile on
day }\tau$ $\displaystyle\mathcal{Y}$ Observation space $\displaystyle N$
Number of nodes in distribution system $\displaystyle\mathcal{A}_{i}$
$\displaystyle\text{Parent vertex of node }i$ $\displaystyle\mathcal{K}_{i}$
$\displaystyle\text{Set of children vertices of node }i$ $\displaystyle R_{i}$
$\displaystyle\text{Internal resistance of line }i$ $\displaystyle
S_{i}^{max}$ $\displaystyle\text{Maximum power limit of line }i$
$\displaystyle d_{i,\tau}(t)$ $\displaystyle\text{Power demand at node
}i\text{ at time }t\text{ on day }\tau$ $\displaystyle\beta_{c}$
$\displaystyle\text{Prior knowledge of preferences of cluster }c$

###  V-B Discussion on Regret Performance

In this section, we describe the necessary background for Theorem 1 and then
present the full version of the Theorem. Recall,
$\mathbf{p}^{\mathbf{V}_{\tau},\star}$ denotes the optimal price signal for
the true model of the population’s price response
$\boldsymbol{\theta}^{\star}$ when the daily exogenous parameter
$\mathbf{V}_{\tau}$ is observed on day $\tau$. Any price signal
$\mathbf{p}_{\tau}\neq\mathbf{p}^{\mathbf{V}_{\tau},\star}$ is considered a
suboptimal price.

We now briefly explain how the posterior updates affect the regret
performance. When price ${\bf p}$ is posted on day $\tau$, the prior density
is updated as

$\pi_{\tau}(d\boldsymbol{\theta})\propto\exp\left(-\log\frac{l(\mathbf{Y}_{\tau};{\bf
p},\boldsymbol{\theta}^{\star})}{l(\mathbf{Y}_{\tau};{\bf
p},\boldsymbol{\theta})}\right)\pi_{\tau-1}(d\boldsymbol{\theta}).$ (26)

Now, denote by $\textit{KL}(\boldsymbol{\theta}_{\bf
p}^{\star}||\boldsymbol{\theta}_{\bf p})$ the marginal Kullback-Leibler
divergence between the distribution $\\{l(Y;{\bf
p},\boldsymbol{\theta}^{\star}):Y\in\mathcal{Y}\\}$ and $\\{l(Y;{\bf
p},\boldsymbol{\theta}):Y\in\mathcal{Y}\\}$. As in [37], we can approximately
write (26) as:

$\displaystyle\pi_{\tau}(d\boldsymbol{\theta})\propto\exp\bigg{(}-\sum_{\mathbf{p}\in\mathcal{P}}N_{\tau}({\bf
p})\textit{KL}(\boldsymbol{\theta}_{{\bf
p}}^{\star}||\boldsymbol{\theta}_{{\bf
p}})\bigg{)}\pi_{\tau-1}(d\boldsymbol{\theta}),$ (27)

where $N_{\tau}({\bf p})=\sum_{{{\bf V}}\in\mathcal{V}}N_{\tau}({\bf p},{\bf
V})$, and $N_{\tau}({\bf p},{\bf V})$ is the number of times up to day $\tau$
that the algorithm simultaneously observes a daily target load profile ${\bf
V}$ and posts a price ${\bf p}$. As such, the total number of times that
suboptimal price signals are selected over $\mathcal{T}$ days is:

$\displaystyle\sum_{\mathbf{V}\in\mathcal{V}}\sum_{\mathbf{p}\in\\{\mathcal{P}\setminus\mathbf{p}^{\mathbf{V},\star}\\}}N_{\mathcal{T}}(\mathbf{p},\mathbf{V})=\sum_{\tau=1}^{\mathcal{T}}\mathbbm{1}^{\\{\mathbf{p}_{\tau}\neq\mathbf{p}^{\mathbf{V}_{\tau},\star}\\}},$
(28)

where $\mathbbm{1}^{\\{\cdot\\}}$ is the indicator function that is set equal
to one if the criteria is met and zero otherwise.

Furthermore, we define ${\bf N}_{\tau}=[N_{\tau}({\bf p})]_{{\bf
p}\in\mathcal{P}}$ as a vector consisting of the number of times each price is
posted up to day $\tau$. We can consider the quantity in the exponent of (27)
as a loss suffered by model $\boldsymbol{\theta}$ up to day $\tau$. Since the
term in the exponent of (27) is equal to 0 when
$\boldsymbol{\theta}=\boldsymbol{\theta}^{\star}$, we can see that Thompson
sampling samples $\boldsymbol{\theta}^{\star}$ and hence posts the optimal
price with at least a constant probability at each day, i.e.,
$N_{\tau}(\mathbf{p}^{\mathbf{V},\star},{\bf V})$ grows linearly with $\tau$
for all ${\bf V}$.

For each price, we define $S_{{\bf p}}({\bf
V}):=\\{\boldsymbol{\theta}\in\Theta:{\bf p}_{\tau}={\bf p}|{\bf
V}_{\tau}={\bf V}\\}$ to be the set of parameters
$\boldsymbol{\theta}\in\Theta$ whose optimal price when observing a daily
target load profile $\bf V$ is ${\bf p}$. Furthermore, define
$S_{\textbf{p}}^{{}^{\prime}}({\bf V}):=\\{\boldsymbol{\theta}\in
S_{\textbf{p}}({\bf V}):\textit{KL}(\boldsymbol{\theta}_{{\bf p}^{{\bf
V,\star}}}^{\star}\|\boldsymbol{\theta}_{{\bf p}^{{\bf V,\star}}})=0\\}$ which
is the set of models $\boldsymbol{\theta}$ that exactly match
$\boldsymbol{\theta}^{\star}$ in marginal distribution of $Y$ when the true
model $\boldsymbol{\theta}^{\star}$ is selected and the optimal price ${\bf
p}^{{\bf V,\star}}$ is posted, and $S_{{\bf p}}^{{}^{\prime\prime}}({\bf
V}):=S_{{\bf p}}({\bf V})\backslash S_{\textbf{p}}^{{}^{\prime}}({\bf V})$.

For each of the models $\boldsymbol{\theta}$ in $S_{{\bf
p}}^{{}^{\prime\prime}}({\bf V})$, ${\bf p}\neq{\bf p}^{{\bf
V,\star}},\textit{KL}(\boldsymbol{\theta}_{{\bf p}^{{\bf
V,\star}}}^{\star}\|\boldsymbol{\theta}_{{\bf p}^{{\bf
V,\star}}})>\varepsilon>0$. As we have assumed that the probability of
observing any target profile ${\bf V}\in\mathcal{V}$ is bounded away from
zero, $N_{\tau}({\bf p}^{{\bf V,\star}})$ grows linearly with $\tau$ for all
${\bf V}\in\mathcal{V}$. Hence, any such model $\boldsymbol{\theta}$ is
sampled with probability exponentially decaying in $\tau$ in (27) and the
regret from such $S_{{\bf p}}^{{}^{\prime\prime}}({\bf V})$-sampling is
negligible. We define the set of all such models as
$\boldsymbol{\theta}\in\Theta^{\prime\prime}=\cup_{{\bf
V}\in\mathcal{V}}S_{{\bf p}}^{{}^{\prime\prime}}({\bf V})$.

A model $\boldsymbol{\theta}\in S_{{\bf p}}^{{}^{\prime}}({\bf V})$ will only
face loss whenever the algorithm posted a suboptimal price ${\bf p}$ for which
$\textit{KL}(\boldsymbol{\theta}_{{\bf p}}^{\star}\|\boldsymbol{\theta}_{{\bf
p}})>0$. For ${\bf V}$, a suboptimal price ${\bf p}_{k}^{{\bf V}}\neq{\bf
p}^{{\bf V,\star}}$ may still be posted if any of the set of models in
$S_{{\bf p}_{k}^{{\bf V}}}^{{}^{\prime}}({\bf V})$ may still be drawn with
non-negligible probability. Hence, a price will be eliminated after the
probability of drawing all $\boldsymbol{\theta}\in S_{{\bf p}_{k}^{{\bf
V}}}^{{}^{\prime}}({\bf V})$ is negligible. For each ${\bf V}$, suboptimal
prices are eliminated one after the other at times $\tau_{k}^{\bf
V},k=1,\ldots,|\mathcal{P}|-1$. We refer the reader to [37] for a full
discussion of when a suboptimal price ${\bf p}$ is considered statistically
eliminated, which is used to write constraints in (29) below.

######  Theorem 1.

(Expanded Version) Under assumptions 1-3 and Constraint Set A in Algorithm 1,
for $\delta,\epsilon\in(0,1)$, there exists $\mathcal{T}^{\star}\geq 0$ s.t.
for all $\mathcal{T}\geq\mathcal{T}^{\star}$, with probability $1-\delta$:

$\displaystyle\sum_{\mathbf{V}\in\mathcal{V}}\sum_{\mathbf{p}\in\\{\mathcal{P}\setminus\mathbf{p}^{\mathbf{V},\star}\\}}N_{\mathcal{T}}(\mathbf{p},\mathbf{V})\leq
B+C(\log\mathcal{T}),$

where $B\equiv B(\delta,\epsilon,\mathcal{P},\mathcal{Y},\Theta)$ is a
problem-dependent constant that does not depend on $\mathcal{T}$, and
$C(\log\mathcal{T})$ depends on $\mathcal{T}$, the sequence of selected price
signals, and the Kullback-Leibler divergence properties of the bandit problem
(i.e., the marginal Kullback-Leibler divergences of the observation
distributions
$\text{KL}\big{[}\ell(\mathbf{Y};\mathbf{p},\boldsymbol{\theta}^{\star}),\ell(\mathbf{Y};\mathbf{p},\boldsymbol{\theta})\big{]}$.
Specifically, the $C(\log\mathcal{T})$ term is defined as follows:

$\displaystyle C(\log\mathcal{T})\equiv$ (29)
$\displaystyle\max\sum_{\mathbf{V}\in\mathcal{V}}\sum_{k=1}^{|\mathcal{P}|-1}N_{\tau_{k}^{\mathbf{V}}}(\mathbf{p},\mathbf{V})$
$\displaystyle\text{ s.t. }\forall\;\mathbf{V}\in\mathcal{V},\;\forall
j>1,\;\forall 1\leq k\leq|\mathcal{P}|-1:$
$\displaystyle\min_{\boldsymbol{\theta}\in\Big{\\{}S^{{}^{\prime}}_{\mathbf{p}_{k}^{\mathbf{V}}}(\mathbf{V})-\Theta^{{}^{\prime\prime}}\Big{\\}}}\langle\mathbf{N}_{\tau_{k}^{\mathbf{V}}},\text{KL}_{\boldsymbol{\theta}}\rangle\geq\frac{1+\epsilon}{1-\epsilon}\log{\mathcal{T}},$
$\displaystyle\min_{\boldsymbol{\theta}\in\Big{\\{}S^{{}^{\prime}}_{\mathbf{p}_{k}^{\mathbf{V}}}(\mathbf{V})-\Theta^{{}^{\prime\prime}}\Big{\\}}}\langle\mathbf{N}_{\tau_{k}^{\mathbf{V}}}-e^{(j)},\text{KL}_{\boldsymbol{\theta}}\rangle<\frac{1+\epsilon}{1-\epsilon}\log{\mathcal{T}},$

where $e^{(j)}$ denotes the j-th unit vector in finite-dimensional Euclidean
space. The last two constraints ensure that price
$\mathbf{p}_{k}^{\mathbf{V}}$ is eliminated at time $t_{k}^{\mathbf{V}}$ (no
earlier and no later).

###### Proof.

In Con-TS-RTP with Constraint Set A, the aggregator’s daily objective and
constraints are dependent on the sampled parameter
$\boldsymbol{\widetilde{\theta}}_{\tau}$. The only difference between Con-TS-
RTP and the daily optimization in [41] is the added constraints. Since the
constraints are only enforced for the sampled parameter, each sampled
parameter $\boldsymbol{\widetilde{\theta}}_{\tau}$ still has a unique optimal
price signal, and more importantly, the constraints do not prohibit the
algorithm from selecting the optimal price for the sampled parameter. As such,
the addition of constraints that depend only on the daily sampled parameter
does not alter the bandit problem, and the regret analysis follows from [41],
which depends heavily on [37]. ∎

###  V-C Discussion on Operational Reliability

######  Proposition 1.

(Repeated) Under assumptions 1-4, with $\nu$ in equations (16)-(18) chosen
such that
$\nu\leq\mu\pi_{0}(\boldsymbol{\theta}^{\star})e^{-\lambda|\mathcal{P}|}$,
with probability $1-\delta\sqrt{2}$, the Con-TS-RTP algorithm with Constraint
Set B will uphold the probabilistic distribution system constraints as
formulated in (12) for each day $\tau=1,\dots,\mathcal{T}$.

###### Proof.

In [37], it is shown that with probability $1-\delta\sqrt{2}$ the mass of the
true parameter never decreases below
$\pi_{0}(\boldsymbol{\theta}^{\star})e^{-\lambda|\mathcal{P}|}$ in the prior
distribution during the entire learning process. As such, the desired
reliability metric on the RHS of the constraints (16)-(18), i.e., $1-\nu$, can
be selected such that the constraints must hold for the true parameter. Let
$\pi_{min}^{\star}=\pi_{0}(\boldsymbol{\theta}^{\star})e^{-\lambda|\mathcal{P}|}$
be the minimum reachable mass of the true parameter in the prior distribution.
Furthermore, we abuse notation and denote
$\mathbb{P}_{j}^{safe}=\mathbb{P}_{\\{\phi_{c}\\}_{c\in\mathcal{C}}}\big{[}g_{j}\big{(}\mathbf{D}_{\tau}(\mathbf{p}_{\tau})\big{)}\leq
0\big{]}$ as the probability that constraint $j$ is upheld. Now, assuming the
aggregator only has knowledge of the true parameter given by the prior
distribution $\pi_{\tau}$ on day $\tau$, the aggregator can calculate the
probability of satisfying the constraint:

$\displaystyle\sum_{\boldsymbol{\hat{\theta}}\in\Theta}\pi_{\tau}(\boldsymbol{\hat{\theta}})(\mathbb{P}_{j}^{safe}|\boldsymbol{\theta}=\boldsymbol{\hat{\theta}}).$
(30)

This can be split into two terms for the true parameter
$\boldsymbol{\theta}^{\star}$ and all other parameters
$\boldsymbol{\theta}\neq\boldsymbol{\theta}^{\star}$:

$\displaystyle\pi_{\tau}(\boldsymbol{{\theta}^{\star}})(\mathbb{P}_{j}^{safe}|\boldsymbol{\theta}=\boldsymbol{\theta}^{\star})+(1-\pi_{\tau}(\boldsymbol{{\theta}^{\star}}))(\mathbb{P}_{j}^{safe}|\boldsymbol{\theta}\neq\boldsymbol{\theta}^{\star}).$
(31)

Now, we can rewrite the probability assuming that
$\boldsymbol{\theta}^{\star}$ has reached the minimum mass $\pi_{min}^{\star}$
in the prior distribution:

$\displaystyle\pi_{min}^{\star}(\mathbb{P}_{j}^{safe}|\boldsymbol{\theta}=\boldsymbol{\theta}^{\star})+(1-\pi_{min}^{\star})(\mathbb{P}_{j}^{safe}|\boldsymbol{\theta}\neq\boldsymbol{\theta}^{\star}).$
(32)

Recall, the aggregator wants constraint $j$ to hold with probability at least
$1-\mu$ for the true parameter $\boldsymbol{\theta}^{\star}$, so we can
replace
$(\mathbb{P}_{j}^{safe}|\boldsymbol{\theta}=\boldsymbol{\theta}^{\star})$ with
$1-\mu$. Furthermore,
$(\mathbb{P}_{j}^{safe}|\boldsymbol{\theta}\neq\boldsymbol{\theta}^{\star})\leq
1$ and we replace it accordingly yielding:

$\displaystyle\pi_{min}^{\star}(1-\mu)+(1-\pi_{min}^{\star}).$ (33)

Now, we want this probability to be the minimum allowable probability across
the prior $\pi$ for constraint $j$ to hold so we set it equal to the
reliability metric:

$\displaystyle\pi_{min}^{\star}(1-\mu)+(1-\pi_{min}^{\star})=1-\nu,$ (34)

which yields

$\displaystyle\nu=\mu\pi_{min}^{\star}.$ (35)

Moreover, by selecting $\nu\leq\mu\pi_{min}^{\star}$ the aggregator ensures
that constraint $j$ will be upheld with probability at least $1-\mu$ for the
true parameter $\boldsymbol{\theta}^{\star}$. (i.e., the total mass of the
incorrect parameters $\boldsymbol{\theta}\neq\boldsymbol{\theta}^{\star}$ in
the prior distribution $\pi_{\tau}$ can never be large enough to satisfy the
constraint’s inequality without the true parameter also satisfying the
constraint). ∎