\section{Assessing Data For Local Reconstruction}
\label{sec:ratedistortion}

The core challenge we are facing is developing a predictor $\hat u_i$ that can \emph{reconstruct} the optimal action $u_i^*$ (which depends on the whole network state $x$), based on solely local information $d_i$ (a subset of $x_i$ as defined in Equation \eqref{eqn:state}). 
Traditional machine learning methods do not provide a straight-forward way to assess how well a predictor performs in an absolute sense.
To provide such a measure, we formulate our approach as a \emph{data compression} problem.
Analogue to reducing the number of pixels in a JPG photo, we reduce the number of states that a predictor has access to, from all states $x$ (that fully describe the optimal action $u_i^*$) to the local exogenous state variables $d_i$ (that inherently only hold limited information about $u_i^*$).


\begin{figure*}[t]
\centering
  \includegraphics[width=0.75\textwidth]{rbic_figs/flow_diagram_ud.pdf}
  \caption{A flow diagram explaining the key steps of the decentralized regression method. We first collect data from a multi-agent system, and then solve the centralized optimization problem using all the data. The data is then split into smaller training and test sets for all agents to develop individual decentralized policies $\hat \pi_i(x_i)$ (or $\hat \pi_i(d_i)$ as proposed in the context of OPF) that approximate the optimal solution of the centralized problem. These policies are then implemented in the multi-agent system to collectively achieve a common global behavior.}
  \label{fig:flow_diagram}
\end{figure*}

\subsection{Rate Distortion Framework}

With \emph{rate distortion} theory~\cite[Chapter 10]{cover_elements_2012}, a branch of information theory, we cast this problem formally to understand the inherent distortion that comes with compressing the data produced by an information source into a specified \emph{encoding rate}. In our case, this rate is equivalent to the \emph{mutual information} $I(d_i,u_i^*)$ between accessible variables $d_i$ and the optimal action $u_i^*$, both treated as random variables. 


For our problem, the theoretical minimum distortion given the encoding rate is
\begin{align}
\label{eqn:rate_distortion_formulation}
D^* = \min_{p(\hat u | u^*)} \, & \quad \Ebb \left[\pmb{d}(\hat u, u^*) \right] \,, \\
\textnormal{s.t. } \, & \quad I(\hat u_i; u_j^*) \le I(d_i; u_j^*) \triangleq \gamma_{ij} \,, \nonumber\\
& \quad I(\hat u_i; \hat u_j) \le I(d_i; x_j) \triangleq \delta_{ij}, \forall i, j \in \C \,, \nonumber
\end{align}


where $I(\cdot,\cdot)$ denotes mutual information and $\pmb{d}(\cdot,\cdot)$ an arbitrary non-negative distortion measure. 
For the remainder of this paper, we will measure distortion it as the mean square error (MSE) deviation between $\hat u_i$ and $u_i^*$, which is a common \emph{loss function} in supervised learning. 
The minimum distortion between random variable $u^*$ and its reconstruction $\hat u$ hold over \emph{any} conditional distributions $p(\hat u | u^*)$.
Note that this result holds for any non-negative distortion measure. 

Solving for all conditional distributions $p(\hat u | u^*)$ is not feasible nor is it necessary for our purpose.
We are strictly interested in finding the best parameterized Markov control policy $\hat u_i = \hat \pi_i(d_i)$ among a \emph{finite set} of available supervised learning techniques.
As such, we do not need to compute $D^*$, and use \eqref{eqn:rate_distortion_formulation} to provide us with two practical tools to assess the quality of the data set. 

Firstly, regardless of the distortion measure~$\pmb{d}(\cdot,\cdot)$, minimum distortion~$D^*$ is monotonically decreasing in the encoding rate $I(d_i; u_j^*)$.
Equivalently, policies $\hat u_i$ that have a higher mutual information $I(\hat u_i; u_i^*)$ also yield lower distortion rates, with the minimum occurring for $I(\hat u_i; u_i^*) = I(d_i; u_i^*)$. 
Therefore, we can use $I(d_i; u_i^*)$ as a benchmark for assessing various policies. 
Mutual information cannot be computed exactly but can be approximated numerically. To do this, the data sets for all three quantities, $\{\hat u_i(t)\}_{t=1}^T, \{ u_i^*(t)\}_{t=1}^T, \{ d_i(t)\}_{t=1}^T$, are discretized into even buckets, allowing the use of an estimation algorithm to compute mutual information~\cite{jiao_minimax_2015}.
Note that a finer discretization yields a better estimate, but also requires more memory. Depending on the available computational resources, a feasible tradeoff should be made. Explicit results of these computations are included in~\cite{dobbe_fully_2017}.


Secondly, if the policy that attains the highest possible mutual information does not provide good performance, the rate distortion framework provides a ready extension to determine the optimal nodes to communicate with, thereby increasing the mutual information benchmark (and decreasing the minimally achievable distortion~$D^*$), which is discussed next. 


\subsection{Allowing Restricted Communication}
Suppose that a decentralized policy $\hat \pi_i (d_i)$ suffers from the fact that the data set with local measurements $\{ d_i[t] \}_{t=1}^T$ does not contain enough information to make an accurate reconstruction of the optimal action $u^*_i$ that generalizes well across power flow scenarios. 
An example of such a scenario is when the optimal set points do not correlate with any local process, instead responding more to behaviors elsewhere in the network. We simulate such an example in Section~\ref{sec:results_case2} and discuss it further in Section~\ref{subsec:communication}.
Such a deficiency in local information can be determined by estimating the mutual information $I(d_i,u_i^*)$ or by inspecting the prediction accuracy of resulting machine learning models.
Since $u^*_i$ depends on all states in the network $x$, we would like to quantify the potential benefits of communicating with other nodes $j \neq i$ in order to reduce the distortion limit $D^*$ from \eqref{eqn:rate_distortion_formulation} and thereby improving the reconstruction $\hat u_i = \hat \pi_i (d_i,d_j)$ as compared to $\hat u_i = \hat \pi_i(d_i)$.


\begin{lemma} (Restricted Communication~\cite{dobbe_fully_2017})
\label{thm:restricted_communication}

If $\Sc_i$ is the set of $k$ nodes $j \ne i \in \N$ which $\hat u_i$ is allowed to observe in addition to $d_i$, then setting 
\begin{align}
\label{eqn:restricted_communication}
\Sc_i = \arg \max_{\Sc} \ I(u_i^*; d_i, \{d_j : j \in \Sc\}) \ : \ |\Sc| = k \,,
\end{align}
minimizes the best-case expectation of \textit{any} distortion measure. That is, this choice of $\Sc_i$ yields the smallest lower bound $D^*$ from \eqref{eqn:rate_distortion_formulation} of any possible choice of $\Sc$.
\end{lemma}


Lemma \ref{thm:restricted_communication} provides a means of choosing a subset of the state $\{d_j : j \ne i\}$ to communicate to policy $\hat \pi_i$ that minimizes the corresponding best expected distortion $D^*$. Practically speaking, this result may be interpreted as formalizing the following intuition: ``the best thing to do is to transmit the most information.'' In this case, ``transmitting the most information'' corresponds to allowing $\hat \pi_i$ to observe the set $\Sc$ of nodes $\{d_j : j \ne i\}$ which contains the most additional information about~$u_i^*$. Likewise, by ``best'' we mean that $\Sc_i$ minimizes the best-case expected distortion~$D^*$, for any distortion metric~$\pmb{d}$. 
Following the logic above of an example where there is little local information about $u_i^*$, the resulting nodes $\Sc_i$ are likely to exhibit behaviors that $u^*_i$ responds to in the considered OPF problem.

We determine $\Sc_i$ by evaluating the mutual information for all possible sets $\{d_j : j \in \Sc\}) \ : \ |\Sc| = k$.
In addition, in the case of selecting multiple nodes to communicate with, one may encounter the estimation to require significant memory and slow down. In such cases, a greedy approach, selecting one node at a time, may prove useful. This approach has near-optimal properties due to the submodular nature of mutual information~\cite{sharma_greedy_2015}.
{"config": "arxiv", "file": "1806.06790/ratedistortion.tex"}