Wang et al.

*Hao Wang, Department of Data Science and AI, Faculty of Information Technology, Monash University, Melbourne, VIC 3800, Australia.

# Consensus-Based Decentralized Energy Trading for Distributed Energy
Resources

Zhenyu Wang  Xiaoyu Zhang  Hao Wang  Department of Data Science and AI,
Faculty of Information Technology, Monash University, Melbourne, Victoria,
Australia  School of Business and Management, Shanghai International Studies
University, Shanghai, China<EMAIL_ADDRESS>Z. Wang  X. Zhang  H. Wang

(<day> <Month>, <year>; <day> <Month>, <year>; <day> <Month>, <year>)

###### Abstract

[Abstract]In smart grids, distributed energy resources (DERs) have penetrated
residential zones to provide a new form of electricity supply, mainly from
renewable energy. Residential households and commercial buildings with DERs
have become prosumers in the local grids, since they can sell surplus power to
others. Researches have been initiated to integrate and utilize DERs through
better control and communication strategies. With the advances in the Internet
of Things (IoT) technology, unprecedented coordination among DERs can be
achieved to facilitate energy trading and transactive energy management.
However, preventing leakage of users’ information during the optimization
process keeps challenging researchers, which drives them to develop privacy-
preserving energy management systems. In this paper, we develop a fully
decentralized transactive energy management using the consensus-based
algorithm. To be specific, we design a virtual pool for prosumers to trade
energy and exchange information with IoT technologies’ support. The consensus-
based algorithm enables prosumers to obtain the optimal energy schedule
independently in a coordinated manner without revealing any personal data. We
use real-world data to perform simulations and validate our developed
algorithm. The results show that our consensus-based decentralized transactive
energy management strategy is feasible and can significantly reduce the
overall system cost.

, and (2021), Consensus-Based Decentralized Energy Trading for Distributed
Energy Resources, Energy Convers Econ., 2021;00:1–15.

††articletype: Original Article

##  1 Introduction

The smart grid has been trending across the globe to develop grid intelligence
and improve energy efficiency, and distributed energy resources (DERs) have
been promoted to deploy at residential homes and commercial buildings to
provide new types of sustainable energy sources. DERs, such as solar panels
and electric vehicles used locally on the consumption side, transform users
into prosumers providing clean energy more efficiently and reliably. Benefited
from the evolution of two-way power flow 1, prosumers with DERs can save on
electricity bills by selling surplus power to the grid or participating in
energy trading with other prosumers at a relatively lower price. The emergence
of prosumers in the grid also enables a paradigm shift toward transactive
energy 2. To facilitate transactive energy management of DERs, sufficient
information exchange with DERs is often necessary. Due to the nature of low-
rate data transmission between DERs, it has been shown that the Internet of
Things (IoT) technologies (e.g., Narrowband IoT) can outperform other types of
network connection (e.g., WiFi) in DER communication 3. With the development
of IoT technology, the device-to-device (D2D) communications become much more
intelligent 4, and DER devices can be monitored and controlled more
effectively 5. This gives rise to lower latency and more considerable
scalability in various smart grid applications 6. This motivates us to study
the following problem in the paper: what would be a good transactive energy
management strategy that promotes efficient utilization of DERs using IoT
communications?

###  1.1 Literature Review

Existing studies have investigated DERs utilization and coordination at the
local level and holistic levels. At the local level, DERs with other electric
appliances can form an intelligent microgrid or a virtual power plant to
improve the grid’s energy efficiency and reduce energy cost for prosumers 7.
The energy management system can optimize the energy usage schedule of HVAC
and other DERs for each prosumer 8. At the holistic level, transactive energy
management can fully utilize renewable energy and other DERs for the whole
grid network. The management processes typically require users to share their
energy consumption preferences and then schedule cooperatively through a
central optimization system. Luna et al. designed a centralized system to
store and share energy among households, which fully utilizes all DERs in a
coordinated manner 9. Tenti et al. developed a cooperative framework to
enhance the grid efficiency by reducing the distribution loss of DERs via
central control 10. Yi, Hong and Liu proposed an initialization-free
distributed algorithms to eliminate the adaptation work whenever the network
structure is changed 11. However, these centralized management strategies
raise privacy concerns, since users’ private information would be at risk of
leakage when solving a global optimization problem. Particularly for IoT
environments, personal data can be easily exploited 12, 13, and data leakage
may occur 14.

Recent studies on distributed transactive energy management have been widely
developed to address the challenges of privacy preservation. Parisio et al.
validated the distributed coordination algorithm under the model predictive
control framework, which allowed microgrids to perform local optimization
sequentially 15. However, usage information is still disclosed and may be
exploited by outside parties. A better way to preserve privacy is to prevent
personal data from transmitting to the system. Chang et al. employed the
contract net protocol and multi-factor methods to carry out the energy
exchange optimization alone without including any personal consumption
information 16. Ge et al. designed a novel decomposition algorithm to build a
decentralized platform 17, where energy transactions among users can be
settled to preserve local load information. Le et al. adopted a distributed
neurodynamic algorithm to optimize the energy trading by exchanging
information among neighbors 18. Nizami et al. developed a two-stage energy
management system that enables energy trading between users under a separated
transactive market 19. Still, the success of trading bids heavily depends on
users’ inclinations, which would bring ineffectiveness in real-world
applications.

Researchers have also made efforts on adding protection mechanisms to the
information transmission. Aitzhan and Svetinovic 20 attempted to anonymize the
trading transactions using multi-signatures and blockchain technologies. Yang
and Wang 21, 22 developed blockchain systems with smart contracts to implement
distributed optimization algorithms for transactive energy management of smart
homes. Chen et al. considered the blockchain technology in economic dispatch
problems 23 and peer-to-peer energy trading 24 to secure the reliability
without a coordinator. Lu et al. adopted Paillier encryption on the private
information in the transactive energy system 25. Nevertheless, both
anonymization and encryption will require extra time and resources to protect
user privacy, hindering the deployment of transactive energy systems.

###  1.2 Research Gap and Motivation

From the existing studies, we can see that different algorithms and
technologies have their strengths and weaknesses to protect user information.
Most of the proposed systems include central operators to perform the higher-
level optimization process. Yang et al. proposed a consensus-based algorithm
to solve the economic dispatch problem without any reliance on central
controllers 26. Zhao et al. also adopted the consensus-based algorithm to
preserve privacy when obtaining the optimal solutions for smart grid energy
management 27. However, both of the studies focused on generation units other
than prosumers with DERs. Unlike the above studies, we aim to optimize the
energy scheduling for a group of prosumers using the consensus-based
algorithm, which would help promote the installation of DERs in residential
houses. Celik et al. developed a decentralized energy management system for
smart homes by allowing coordinated energy sharing, which isolates the pricing
mechanism from users 28. Wang et al. designed a decentralized mechanism to
incentivize users to share energy through evaluating their contributions 29.
In contrast, our market-like pool allows the trading price to be self-adjusted
based on prosumers’ trading decisions, reflecting the practice of a
transactive market. Thus, the need to improve the management process of a
fully decentralized system still exists to gain flexibility and protect user
privacy at the same time. Our work aims to leverage the advances in IoT
technologies enabling device-to-device communications to design privacy-
preserving decentralized energy management algorithms for DERs.

###  1.3 Contribution and Paper Organization

In this paper, we present a consensus-based decentralized transactive energy
management system with the support of IoT technologies. The main contributions
of this work are summarized as follows.

  1. 1)

Structural Flexibility: Unlike most existing studies of distributed energy
management using a fixed communication topology, we establish a decentralized
transactive energy system and a market-like virtual pool under flexible
communication topology. Our decentralized algorithm enables prosumers to
interact and exchange information to determine the optimal energy trading with
their neighbors under an IoT network with different D2D communication
structures.

  2. 2)

Privacy preservation: We develop a consensus-based decentralized algorithm
that enables users to reach an agreement on energy trading price and quantity
over multiple time slots in the operational horizon. The equilibrium prices
obtained for consecutive periods lead to an optimal solution to the
transactive energy management problem. The consenting process only requires
prosumers to share their energy trading data instead of the complete usage
data, which would preserve users’ privacy.

  3. 3)

Real-world practicability: We validate our designed system and algorithm using
real-world renewable energy and load data. The results show that the system
cost is reduced by $17.30$%, and the cost of individual prosumers can be
reduced by up to $71.54$%. The results also show the nearest-neighbor D2D
communication structure achieves good convergence with much fewer direct
connections among prosumers, compared with the all-connected communication
structure, demonstrating the practical value of IoT technology for the future
decentralized transactive energy system.

The rest of the paper is organized as follows. Section 2 describes the model
of the consensus-based decentralized transactive energy system. Section 3
formulates the optimization problems for both standalone and coordinated
scenarios of the system. Section 4 elaborates on the design of the consensus-
based decentralized algorithm applied to transactive energy management of
prosumers. Section 5 evaluates the proposed system with extensive simulations,
and Section 6 concludes our work.

##  2 SYSTEM MODEL

Our system model consists of a power grid, a group of IoT-aided smart homes as
prosumers with DERs, and a transactive market that connects prosumers, as
shown in Figure 1. We assume that there are $N$ prosumers in the model, which
can be denoted as the set $\mathcal{N}=\left\\{1,2,\ldots,N\right\\}$. We
further assume that the system will operate in multiple time slots, which can
be denoted as $\mathcal{H}=\left\\{1,2,\ldots,H\right\\}$, where $H$ is the
total number of operating window slots. To be aligned with the market
practice, we consider an hour as the operating slot and $H=24$ for each day.

###  2.1 Overall Framework

As shown in Figure 1, we consider that each prosumer is installed with DERs to
generate renewable energy (e.g., solar panel or wind turbine) and other
electric appliances to meet living requirements (e.g., air conditioner,
washing machine, and lights). This is demonstrated by the different icons of
devices surrounding the house icon. Each home is also equipped with an
advanced smart meter and energy management system to monitor and schedule its
own energy use of different types of flexible load. We model it as the
Internal Energy Scheduling Layer. While our energy management system can
optimize the energy schedules for prosumers with different preferences, it can
manage the energy trading among prosumers as well. The power exchange
represented by the green ellipse, which supports prosumers to trade energy
with each other, forms a virtual pool for sharing energy generated from DERs.
The communication required in the pool (e.g., information exchange and
transactive activity) can also be facilitated by the IoT technologies applied
on the smart meters, which together will constitute an External Energy Trading
Layer. With transactive energy management, DERs can be fully utilized in the
designated area in our model.

Figure 1: The transactive energy management system.

###  2.2 Internal Energy Scheduling Layer

We use prosumer and user interchangeably in this paper. As we mentioned
earlier, each user’s house is equipped with DERs and other appliances, which
can be split into two parts: the supply model and the load model. The first
part refers to the electricity supply either purchased from the grid or
generated from the local DERs. The second part refers to the electricity
demand from different appliances in the system.

The supply model for each user $i$ in $\mathcal{N}$ contains two terms
$p_{i,t}^{\text{G}}$ and $p_{i,t}^{\text{RE}}$ in each time slot $t$ in
$\mathcal{H}$, where $p_{i,t}^{\text{G}}$ denotes the amount of energy
purchased from the grid, and $p_{i,t}^{\text{RE}}$ denotes the amount of
renewable energy generated from DERs. Further, we define $P_{i}^{\text{G}}$ to
be the maximum capacity to draw electricity from the grid for user $i$ in any
time slot, and $P_{i,t}^{\text{RE}}$ to be the available renewable energy from
all deployed DERs in user $i$’s home at time $t$. Hence, the two power supply
terms $p_{i,t}^{\text{G}}$ and $p_{i,t}^{\text{RE}}$ should be upper-bounded
by $P_{i}^{\text{G}}$ and $P_{i,t}^{\text{RE}}$ respectively and should always
be non-negative, which can be expressed by the following two constraints:

$\displaystyle 0\leq p_{i,t}^{\text{G}}\leq P_{i}^{\text{G}},\forall\
i\in\mathcal{N},t\in\mathcal{H},$ (1) $\displaystyle 0\leq\
p_{i,t}^{\text{RE}}\leq\ P_{i,t}^{\text{RE}},\ \forall\
i\in\mathcal{N},t\in\mathcal{H}.$ (2)

To promote energy saving and consumption fairness, the grid applies a tiered
tariff scheme for users. For example, Austin Energy 30 has established a five-
tier rate structure to charge higher-load consumers at higher rates, as
illustrated in Figure 2. We apply the linear approximation to the tiered
prices in order to build up our model in more generalized cases, where the
unit electricity price is assumed to increase with the load amount linearly.
The unit energy price is formulated as

$\pi^{\text{G}}=a^{\text{G}}p_{i,t}^{\text{G}}+b^{\text{G}},$ (3)

where the gradient term $a^{\text{G}}$ represents the price increase for each
unit increase in energy load, and the constant term $b^{\text{G}}$ represents
the base price. Hence, user $i$’s grid cost becomes

$C_{i}^{\text{G}}=\sum_{t\in\mathcal{H}}{\pi^{\text{G}}p_{i,t}^{\text{G}}}=\sum_{t\in\mathcal{H}}\left[a^{\text{G}}\left(p_{i,t}^{\text{G}}\right)^{2}+b^{\text{G}}p_{i,t}^{\text{G}}\right].$
(4)

Figure 2: An Example for tiered tariff billing with linear approximation (Data
source: Austin Energy 30).

The load model for each user $i$ in time slot $t$ consists of HVAC load, other
flexible loads, and inflexible loads, which can be denoted as
$p_{i,t}^{\text{AC}}$, $p_{i,t}^{\text{F}}$ and $p_{i,t}^{\text{IL}}$,
respectively. The HVAC load refers to the power consumption of the HVAC unit
in adjusting indoor temperature through heating or cooling processes. We
define $T_{i,t}^{\text{IN}}$ to be the indoor temperature and
$T_{i,t}^{\text{OUT}}$ to be the outdoor temperature for user $i$’s home in
time slot $t$. Then the time-series indoor temperature can be formulated
according to the thermal dynamics for HVAC units 31 as

$\displaystyle
T_{i,t}^{\text{IN}}=T_{i,t-1}^{\text{IN}}-\frac{1}{\phi_{i}^{C}\phi_{i}^{R}}\left(T_{i,t-1}^{\text{IN}}-T_{i,t}^{\text{OUT}}+\eta_{i}\phi_{i}^{R}p_{i,t}^{\text{AC}}\right),$
(5) $\displaystyle\forall\ i\in\mathcal{N},t\in\mathcal{H},$

where $\phi_{i}^{C}$ and $\phi_{i}^{R}$ denote the operating parameters of the
HVAC units, and $\eta_{i}$ denotes the working mode of the HVAC unit. Cooling
gives $\eta_{i}$ a positive value, and heating gives a negative value. In our
simulations, $\phi_{i}^{C}$ and $\phi_{i}^{R}$ are set to 3.3 and 1.35
respectively for all users.

HVAC system operates according to the temperature value set by users, which is
denoted as $T_{i}^{\text{REF}}$. When the indoor temperature deviates from the
setpoint value, it will cause an uncomfortable feeling to users. We consider
such discomfort as the cost in managing HVAC, which is modeled by a quadratic
cost function as

$C_{i}^{\text{AC}}=\beta_{i}^{\text{AC}}\sum_{t\in\mathcal{H}}{\left(T_{i,t}^{\text{IN}}-T_{i}^{\text{REF}}\right)^{2}},\
\forall\ i\in\mathcal{N},$ (6)

where $\beta_{i}^{\text{AC}}$ denotes the sensitivity coefficient for user
$i$.

Also, we define ${\underline{T}}_{i}^{\text{IN}}$ and
${\overline{T}}_{i}^{\text{IN}}$ as the lower and upper bounds of user $i$’s
tolerable indoor temperature. Hence, the following constraint should be
applied to the indoor temperature in time slot $t$:

$\displaystyle{\underline{T}}_{i}^{\text{IN}}\leq
T_{i,t}^{\text{IN}}\leq{\overline{T}}_{i}^{\text{IN}},\ \forall\
i\in\mathcal{N},t\in\mathcal{H}.$ (7)

Other flexible loads, denoted by $p_{i,t}^{\text{F}}$, refers to the loads
that can be shifted over time but cannot be curtailed due to users’ living
requirements, such as cooking and laundry. We define
${\underline{P}}_{i,t}^{\text{F}}$ and ${\overline{P}}_{i,t}^{\text{F}}$ as
the lower and upper bounds of user $i$’s flexible load in time slot $t$, and
thus the following constraint should be satisfied

$\displaystyle{\underline{P}}_{i,t}^{\text{F}}\leq
p_{i,t}^{\text{F}}\leq{\overline{P}}_{i,t}^{\text{F}},\ \ \forall\
i\in\mathcal{N},t\in\mathcal{H}.$ (8)

Usually, users have their own most comfortable schedule for flexible
activities like cooking or doing laundry. We denote $P_{i,t}^{\text{REF}}$ as
the preferred flexible load schedule for user $i$ in time slot $t$. Hence, the
total amount of other flexible loads in energy management should always equal
to the sum of the preferred schedule, which can be expressed by the following
constraint

$\sum_{t\in\mathcal{H}}\ p_{i,t}^{\text{F}}=\sum_{t\in\mathcal{H}}\
P_{i,t}^{\text{REF}},\ \forall\ i\in\mathcal{N}.$ (9)

We also consider the user discomfort occurred when the flexible load is
shifted away from the preferred schedule. This kind of discomfort represents
the cost of managing flexible loads, which can be modeled by the quadratic
cost function below

$C_{i}^{\text{F}}=\beta_{i}^{\text{F}}\sum_{t\in\mathcal{H}}{\left(p_{i,t}^{\text{F}}-P_{i,t}^{\text{REF}}\right)^{2}},\
\forall i\in\mathcal{N},$ (10)

where $\beta_{i}^{\text{F}}$ denotes the sensitivity coefficient of user $i$
towards the flexible load deviation.

Other inflexible loads $p_{i,t}^{\text{IL}}$ include the electricity
consumption of all other appliances that are not adjustable in the system,
such as light.

###  2.3 External Energy Trading Layer

In our aforementioned structure, at the same time as scheduling their internal
energy, users can trade energy with peers via the virtual power exchange pool
using IoT-aided communications. Different from energy-trading studies in 32
that forms energy-trading pairs, out work does not require users to identify
specific trading partners. Specifically, the transactive energy management
system enables users to sell their surplus renewable energy to those having
high power demand. The selling parties can have cash inflows to cover some of
their electricity bills, whereas the buying parties can purchase energy at a
lower price than the regular grid price.

Here, we do not allow prosumers to sell surplus energy to the grid but only to
their neighbors. A study on Australian households 33 has shown that the high
penetration of renewable energy at the consumption end will have large
financial impacts on centralized power generations but minimal impacts on
other consumers who do not have DERs. Therefore, self-consumption is
encouraged in a system with a high DER penetration rate to diminish the
impacts on the grid network.

We denote the amount of power traded by user $i$ in time slot $t$ as
$p_{i,t}^{\text{ET}}$. Here, a positive $p_{i,t}^{\text{ET}}$ represents the
status of purchasing power from the others, and a negative
$p_{i,t}^{\text{ET}}$ represents the status of selling power to the others.
Under the IoT environment, we omit any time lag to process trading information
in our model. We also assume that any amount of power exchange can be
completed instantly and simultaneously, and there is no electricity loss
during the trading, because the geographic distance between any two of the
prosumers’ houses is negligible. Since the transactive energy cannot be stored
for later use in our virtual trading pool, the scheduled trades for all users
should be balanced in any time slot $t$, which can be expressed by

$\sum_{i\in\mathcal{N}}\ p_{i,t}^{\text{ET}}=0,\ \forall t\in\mathcal{H},$
(11)

which means that the sum of energy trading amounts for all users should be
cleared by the end of each time slot.

In addition, users should only sell the surplus energy generated from DERs. It
will become practically inefficient if the user tries to sell the energy
amount over his capacity to generate, because it has to purchase the defective
part from the grid at the same time. Therefore, we apply another constraint to
prevent users from overselling the renewable energy by lower bounding the
energy trading amount $p_{i,t}^{\text{ET}}$.

$-P_{i,t}^{\text{RE}}\leq\ p_{i,t}^{\text{ET}},\ \forall\
i\in\mathcal{N},t\in\mathcal{H},$ (12)

where $-P_{i,t}^{\text{RE}}$ represents the case of selling all the available
renewable energy.

The cost/profit of energy trading will be discussed in later sections when
formulating the coordinated scenario for our transactive energy management
system.

##  3 PROBLEM FORMULATION

In this section, we consider two scenarios by formulating the optimization
problems for both standalone and coordinated energy management of DERs. In the
first scenario, each prosumer’s energy schedule is optimized independently,
where communication and energy trades among users are not required for energy
management. In the second scenario, users can trade renewable energy with
peers in a coordinated manner to achieve a globally optimal solution for
transactive energy management.

###  3.1 Standalone Scenario

In the standalone scenario, the smart meter equipped in each prosumer’s house
will schedule the internal energy consumption directly without considering any
external factors. For each user $i$ in $\mathcal{N}$, power can be supplied
either from the grid $p_{i,t}^{\text{G}}$ or local DERs $p_{i,t}^{\text{RE}}$
to different types of consumption including HVAC load $p_{i,t}^{\text{AC}}$,
other flexible load $p_{i,t}^{\text{F}}$ and the inflexible load
$p_{i,t}^{\text{IL}}$. To shorten the notation, we redefine the following
variables as $\bm{p}_{i}^{\text{RE}}{=}\\{p_{i,t}^{\text{RE}},\forall
t{\in}\mathcal{H}\\}$, $\bm{p}_{i}^{\text{G}}{=}\\{p_{i,t}^{\text{G}},\forall
t{\in}\mathcal{H}\\}$,
$\bm{p}_{i}^{\text{AC}}{=}\\{p_{i,t}^{\text{AC}},\forall
t{\in}\mathcal{H}\\}$, $\bm{p}_{i}^{\text{F}}{=}\\{p_{i,t}^{\text{F}},\forall
t{\in}\mathcal{H}\\}$, and
$\bm{p}_{i}^{\text{IL}}{=}\\{p_{i,t}^{\text{IL}},\forall
t{\in}\mathcal{H}\\}$.

During the energy management process, user $i$’s power supply and demand must
be equal in each time slot, which leads to the constraint

$\displaystyle
p_{i,t}^{\text{RE}}+p_{i,t}^{\text{G}}=p_{i,t}^{\text{AC}}+p_{i,t}^{\text{F}}+P_{i,t}^{\text{IL}},\
\forall i\in\mathcal{N},t\in\mathcal{H}.$ (13)

The left-hand side of (13) represents the total power supply, and the right-
hand side of (13) denotes the total demand from the HVAC load
$p_{i,t}^{\text{AC}}$, the other flexible load $P_{i,t}^{\text{F}}$ and the
inflexible load $P_{i,t}^{\text{IL}}$.

For the standalone energy management, the overall operating cost of user $i$
over the entire time slots $\mathcal{H}$ is

$\displaystyle
C_{i}^{\text{O}}(\bm{p}_{i}^{\text{G}},\bm{p}_{i}^{\text{AC}},\bm{p}_{i}^{\text{F}})\triangleq
C_{i}^{\text{G}}(\bm{p}_{i}^{\text{G}})+C_{i}^{\text{AC}}(\bm{p}_{i}^{\text{AC}})+C_{i}^{\text{F}}(\bm{p}_{i}^{\text{F}}),$
(14)

where $C_{i}^{\text{G}}(\bm{p}_{i}^{\text{G}})$ denotes the electricity bill
from the grid, $C_{i}^{\text{AC}}(\bm{p}_{i}^{\text{AC}})$ denotes the user’s
discomfort cost of HVAC, and $C_{i}^{\text{F}}(\bm{p}_{i}^{\text{F}})$ denotes
the user’s discomfort cost for shifting other flexible load.

The energy management system aims to minimize users’ total cost in (14).
Therefore, User $i$’s Cost Minimization Problem (UCMPi) for the whole
operating period $\mathcal{H}$ can be formulated as follows.

$\displaystyle\textbf{UCMP}_{i}\text{:}$ $\displaystyle\min$ $\displaystyle
C_{i}^{\text{O}}(\bm{p}_{i}^{\text{G}},\bm{p}_{i}^{\text{AC}},\bm{p}_{i}^{\text{F}})$
subject to $\displaystyle\text{\eqref{constraint-
grid}},\text{\eqref{constraint-renewable}},\text{\eqref{constraint-
temperature}},\text{\eqref{constraint-hvac}},\text{\eqref{constraint-
flexible}},\text{\eqref{constraint-flexible2}},\text{\eqref{constraint-
balance}}$ variables:
$\displaystyle\left\\{\bm{p}_{i}^{\text{RE}},\bm{p}_{i}^{\text{G}},\bm{p}_{i}^{\text{AC}},\bm{p}_{i}^{\text{F}}\right\\}.$

Based on our analysis, user $i$ can locally solve the optimization problem in
UCMPi since it is a standard convex optimization. We denote the optimal total
cost in problem UCMPi by $\bar{C}_{i}^{\text{O}}$ and let this value serve as
a benchmark cost for the comparison with the costs in the coordinated
scenario.

###  3.2 Coordinated Scenario

Unlike the standalone scenario, users not only schedule their internal power
supply and demand but also exchange energy externally with other users when
needed in the coordinated scenario. Users with surplus renewable energy can
sell their energy to other users via the grid; also, users can purchase energy
from their neighbors other than the grid to lower the total costs. The energy
trading is taken into account, and the load balance constraint becomes

$\displaystyle
p_{i,t}^{\text{RE}}{+}p_{i,t}^{\text{G}}{+}p_{i,t}^{\text{ET}}{=}p_{i,t}^{\text{AC}}{+}p_{i,t}^{\text{F}}{+}P_{i,t}^{\text{IL}},\forall
i{\in}\mathcal{N},t{\in}\mathcal{H}.$ (15)

Study has shown that the dynamic Lagrangian multiplier can achieve a fast
convergence in economic dispatch problems 34. We introduce the Lagrange
multiplier $\lambda_{t}$ for the constraints (11). The Lagrangian function for
our optimization problem should be

$\displaystyle\mathcal{L}=\sum_{i\in\mathcal{N}}\left[C_{i}^{\text{O}}(\bm{p}_{i}^{\text{G}},\bm{p}_{i}^{\text{AC}},\bm{p}_{i}^{\text{F}})\right]+\sum_{t\in\mathcal{H}}\left[\lambda_{t}\sum_{i\in\mathcal{N}}p_{i,t}^{\text{ET}}\right].$
(16)

As we assume that the users can trade energy at any price that they are
willing to pay, and such a trading pool can be seen as a perfect market.
Hence, the Lagrange multiplier $\lambda_{t}$ can be considered as the
equilibrium price, where the energy trading costs over the entire time slots
$\mathcal{H}$ can be defined as:

$C_{i}^{\text{ET}}(\bm{p}_{i}^{\text{ET}})=\sum\nolimits_{t\in\mathcal{H}}\lambda_{t}p_{i,t}^{\text{ET}}.$
(17)

In the coordinated energy management system, the system overall cost consists
of user’s individual operating cost
$C_{i}^{\text{O}}(\bm{p}_{i}^{\text{G}},\bm{p}_{i}^{\text{AC}})$ and the
trading cost $C_{i}^{\text{ET}}(\bm{p}_{i}^{\text{ET}})$. Therefore, we
formulate the Coordinated Cost Minimization Problem (CCMP) for the platform
over the whole operating period $\mathcal{H}$ as

CCMP: $\displaystyle\min$
$\displaystyle\sum_{i\in\mathcal{N}}\left[C_{i}^{\text{O}}(\bm{p}_{i}^{\text{G}},\bm{p}_{i}^{\text{AC}},\bm{p}_{i}^{\text{F}})+C_{i}^{\text{ET}}(\bm{p}_{i}^{\text{ET}})\right]$
subject to $\displaystyle\text{\eqref{constraint-
grid}},\text{\eqref{constraint-renewable}},\text{\eqref{constraint-
temperature}},\text{\eqref{constraint-hvac}},\text{\eqref{constraint-
flexible}},\text{\eqref{constraint-flexible2}},\text{\eqref{constraint-
trade}},\text{\eqref{constraint-trade2}},\text{\eqref{constraint-balance2}}$
variables:
$\displaystyle\\{\bm{p}_{i}^{\text{RE}},\bm{p}_{i}^{\text{G}},\bm{p}_{i}^{\text{AC}},\bm{p}_{i}^{\text{F}},\bm{p}_{i}^{\text{ET}},~{}i\in\mathcal{N}\\}.$

We see that Problem CCMP jointly solves the optimal internal energy scheduling
(of renewable and HVAC load) and the optimal external energy trading for all
the users. However, solving CCMP in a centralized manner may cause severe
privacy concerns because the users have to reveal all their parameters to the
platform. To preserve users’ privacy and enable coordinated energy management,
we aim to solve Problem CCMP in a decentralized manner in Section 4.

##  4 DECENTRALIZED ALGORITHM DESIGN

Consensus-based algorithms can achieve decentralized coordination through
finding a certain variable value that is agreed among agents or players 26.
Since the Problem CCMP is to find the global optimization for all residential
users, consensus-based algorithms can be applied to avoid a central
coordinator along with its higher-level calculation and its vulnerability in
preventing data leakage. As most of the relevant papers have adopted the
electricity prices as the consensus variable 27, 35, we can use the trading
prices among users to achieve consensus in our Problem CCMP. We assume that
the energy trading market among users is perfectly competitive, which means
the trading prices at any single point of time should be public and at
equilibrium. We assume rational prosumers who aim to minimize the expected
energy costs under a perfect market, as we aim to automate the optimization
process for the energy trading without personal interventions. Since all
optimizations will be conducted independently by each user, they do not need
to share their personal consumption data with others. The only information to
be exchanged among neighbors is the estimated trading price and the estimated
energy mismatch, which represents the imbalance in the trading pool.

First of all, we initialize each user by setting up two exchanging parameters,
$\lambda_{i,t}\left[0\right]$ and $e_{i,t}\left[0\right]$, which denote the
trading price and energy mismatch in time slot $t$ estimated by user $i$
respectively. The initial values can be chosen arbitrarily, because these two
parameters are adjusted along the iteration process.

Also, we further set up a communication matrix $W$, where each element
$w_{i,j}$ represents the weight that user $i$ put on user $j$’s estimation.
Thus, different structures of the communication network can be represented by
different matrices. Taking examples of a neighborhood with $5$ users, we
illustrate three types of communication network structures represented by
$W_{1}$, $W_{2}$, and $W_{3}$, as shown in Figure 3. Type 1 refers to a one-
to-many structure where only one user is connected with all the other users.
Type 2 refers to a nearest-two structure where all users are only connected
with their nearest two neighbors. Type 3 refers to the all-linked structure
where all users are connected with each other.

Figure 3: Three types of communication network structures with sample
communication matrices.

Then for each iteration $r$, each user updates its trading price estimates
based on its neighbours’ estimates according to the communication matrix $W$,
where each element $w_{i,j}$ represents the weight that user $i$ put on user
$j$’s estimation. They will adjust this weighted average estimation by a
correction term that equals to its energy mismatch estimates multiplied by a
learning rate constant $\epsilon$. It means if the energy demand in the
trading pool is higher than the energy supply (i.e., the energy mismatch is
positive), the trading price should go up, and vice versa, according to the
microeconomic principles. Hence, this price update step can be formulated as

$\lambda_{i,t}\left[r\right]=\sum_{j\in\mathcal{N}}{w_{i,j}\lambda_{j,t}\left[r-1\right]}+\epsilon
e_{i,t}\left[r-1\right],\forall i\in\mathcal{N},t\in\mathcal{H}.$ (18)

With the new estimated trading price $\lambda_{i,t}\left[r\right]$, each user
can determine its energy trading schedule by independently finding the optimal
solution of its own Cost Minimization Problem, which refers to the individual
part of the Problem CCMP, i.e., the overall costs plus the energy trading
costs. Specifically, the individual-level problem (ILPi) for the whole
operating period $\mathcal{H}$ is formulated as

$\displaystyle\textbf{ILP}_{i}\text{:}$ $\displaystyle\min$ $\displaystyle
C_{i}^{\text{O}}(\bm{p}_{i}^{\text{G}},\bm{p}_{i}^{\text{AC}},\bm{p}_{i}^{\text{F}})+C_{i}^{\text{ET}}(\bm{p}_{i}^{\text{ET}})$
subject to $\displaystyle\text{\eqref{constraint-
grid}},\text{\eqref{constraint-renewable}},\text{\eqref{constraint-
temperature}},\text{\eqref{constraint-hvac}},\text{\eqref{constraint-
flexible}},\text{\eqref{constraint-flexible2}},\text{\eqref{constraint-
trade2}},\text{\eqref{constraint-balance2}}$ variables:
$\displaystyle\\{\bm{p}_{i}^{\text{RE}},\bm{p}_{i}^{\text{G}},\bm{p}_{i}^{\text{AC}},\bm{p}_{i}^{\text{F}},\bm{p}_{i}^{\text{ET}}\\}.$

After solving ILP, user $i$ will obtain its energy trading decision
$\bm{p}_{i}^{\text{ET}}$. Each user will then update its energy mismatch
estimates based on its neighbours’ estimates according to $W$ and a correction
term, which is equal to the difference between current and previous energy
trading schedules. The energy mismatch update step can be formulated as

$e_{i,t}\left[r\right]=\sum_{j\in\mathcal{N}}{w_{i,j}e_{j,t}\left[r-1\right]}+p_{i,t}^{ET}\left[r\right]-p_{i,t}^{ET}\left[r-1\right],\forall
i\in\mathcal{N},t\in\mathcal{H}.$ (19)

The above process will iteratively update users’ estimations and optimizations
until the consensus is reached. Theoretically, this consensus algorithm’s
convergence is guaranteed as long as there is a valid trading price
corresponding to the minimized cost function 36. Hence, the iteration loop
will be terminated when the two most recent iterations’ trading prices have a
tolerable difference, and the energy mismatches are tolerably small for all
users, e.g.,

$\left\|\lambda_{i}[r]-\lambda_{i}[r-1]\right\|_{2}\leq\varepsilon^{\lambda}\text{AND}\left\|e_{i}[r]\right\|_{2}\leq\varepsilon^{e},\forall
i\in\mathcal{N}.$ (20)

Also, Liu et al.’s work has proved that the converged results of consensus
variable is the unique and optimal solution to the original problem 37.
Therefore, when all the users reach an agreement for the trading price
according to (20), their energy schedules will converge to the optimal
solution of Problem CCMP. The flow chart shown in Figure 4 illustrates the
process of our designed consensus-based algorithm.

Figure 4: The consensus-based algorithm for our transactive energy management
system.

##  5 Simulation Results and Discussions

In this section, we evaluate the transactive energy management system under
both standalone and coordinated scenarios through extensive numerical
simulations with real data of renewable generation 38, 39 and load from homes
40. The simulation data include users’ daily electricity usage, renewable
energy generation, and outdoor temperature.To validate the consensus-based
decentralized optimization algorithm developed in Section 4, we simulate a
group of 10 users, and their corresponding smart homes are equipped with DERs
and other appliances according to the system model we set up in Section 2.

###  5.1 Algorithm Convergence

We firstly evaluate the performance of the decentralized optimization
algorithm in Section 4 with 10 users. The convergence test of the consensus-
based decentralized algorithm mainly targets two aspects: the trading price
consensus and the trading balance in the trading pool.

The trading price consensus means that all users will agree to the same energy
trading price in any time slot. In the designed algorithm, the convergence of
trading price can be observed directly by the changes to users’ estimations
(i.e., $\lambda_{i,t}$) throughout the iteration process. As shown in Figure
5, we randomly select 6 time slots in the Day 1 simulation and plot the
estimated trading price for each user with respect to the number of
iterations. We can see that the trading price estimated by each user can
always converge to an equilibrium value after around $30$ iterations through
IoT-aided communications.

Figure 5: The consensus process of trading prices $\lambda_{i,t}$ in selected
time slots in the Day 1 simulation.

To further evidence the flexibility of our proposed model, we attempted to
validate it under different kinds of communication network structures and
larger user scales. As shown in Figure 6, we similarly plot the estimated
trading price for two selected time slots for three scenarios: (a) 10 users
under the one-to-many structure, (b) 10 users under the nearest-four
structure, and (c) 50 users under the all-linked structure. We can observe
that the convergence still holds under different types of communication
networks and different scales of the user group. However, when there are
insufficient links between users, it will cost more iterations, e.g., over
$150$ times under scenario (a), which is reasonable since coordination works
better with more links.

Figure 6: The convergence of models with different users and communication
networks.

The other aspect, trading balance, refers to the supply-and-demand balance of
users’ optimal energy exchange in any time slot. In microeconomic theories,
the total supply amount should be equal to the total demand amount for a
commodity at equilibrium under the perfectly competitive market. Hence, the
supply energy should be equal to the demand energy within our virtual trading
pool when the algorithm converges. This can be tested by calculating the total
amount of actual mismatch in the power exchange for all users and in all time
slots (i.e.,
$\sum_{t\in\mathcal{H}}\sum_{i\in\mathcal{N}}p_{i,t}^{\mathrm{ET}}$)
throughout the iteration process. As shown in Figure 7, we plot the sum of
actual mismatches for all time slots with respect to the number of iterations
in the Day 1 simulation under the four scenarios we obtained previously.
Figure 7(a) can compare the convergence among three types of communication
networks. The one-to-many structure requires the longest time to converge,
whereas the all-linked structure is the fastest. Again, it illustrates that
more links among the network will help speed up the convergence process given
the same number of users. Figure 7(b) shows it takes much more iterations if
we have more users in the network, e.g., $50$ users will need about $500$
times of iterations.

Figure 7: The sum of actual mismatch for all time slots in the Day 1
simulation under different networks.

Regarding the time for transmitting data through IoT communication, our model
only requires prosumers to request two data values (i.e., the estimated
trading price and the estimated energy mismatch) from linked neighbors. Hence,
the time spent to complete one iteration will relate to the number of links in
the networks. In other words, a more complex network will take a longer time
to process each iteration. In our simulation, $30$ iterations take around $3$
seconds for $10$ users under an all-linked network.

###  5.2 Optimal Energy Management

Secondly, we illustrate the optimal solution obtained from the model
simulation for both internal and external layers under the coordinated
scenario.

For Internal Energy Scheduling Layer, as shown in Figure 8, we plot the final
energy scheduling outputs for all $10$ users when the convergence is achieved.
We can see that the Grid Usage, which represents the amount of energy
purchased from the grid, is managed to be much stable at most of time for all
users. In comparison with Renewable Energy, which indicates the utilization of
DERs, the patterns for these two energy sources show a complementary
relationship throughout the simulation week. It suggests that the
stabilization in the grid is mostly benefited from the optimum use of
renewable energy generated from DERs. The plot for HVAC Load has similar peak
hours to the Renewable Energy, which demonstrates that the energy management
system can adjust the undulation of electricity consumption according to the
effectiveness of DER generation.

Figure 8: The optimal energy schedule under coopertative management in one-
week simulation.

For the External Trading Layer, as shown in Figure 9, we plot the final energy
trading arrangements for selected users in the one-week simulation, where the
orange bars with positive value represent the buying parties in the trading
and the purple bars with negative value represents the selling parties. We can
observe that there are $3$ typical types of users in energy trading. The first
type refers to those who are buying a lot of energy from other peers most of
the time, such as User 4 shown in Figure 9(a). It means that their DERs cannot
generate enough renewable energy to cover their own demand. The second type
refers to those who mostly behave as energy sellers, such as User 3 shown in
Figure 9(b). They often have surplus renewable energy for sale, because they
have a high DER capacity to cover their daily load. The rest of the users who
have mixed positions as buyers and sellers throughout the scheduling period
are classified as the third type like User 10 shown in Figure 9(c). They can
exchange power with others as they needed, such that all renewable energy will
be fully utilized locally in the neighborhood.

Figure 9: The optimal energy trading history for selected users under
coopertative management in one-week simulation.

###  5.3 Energy and Cost Reduction

Lastly, we evaluate the cost reduction for users after implementing our
transactive energy management system by comparing the standalone and
coordinated scenarios.

As shown in Figure 10, the blue line indicates the scheduled amount of grid
energy purchased by User 6 under standalone management. The red line shows his
new schedule after joining the coordinated trading with his peers. We can see
that the electricity purchased from outside power plants has been
significantly reduced during the entire simulated week, given that the
consumptions are not much affected. Hence, the goal of energy-saving can be
well achieved under our coordinated strategy.

Figure 10: The comparison of grid power purchased by User 4 under standalone
and coordinated scenarios.

As shown in Figure 11, we plot the overall costs for each user under the two
scenarios (orange bars for the standalone scenario and purple bars for the
coordinated scenario) and compute their percentage changes (the number above
bars). The results show that the coordinated management system can lower the
overall cost for all participated users. The cost reduction for individual
producers can be reduced from 8.00% to 71.54% at most, and clearly, users who
sell more in energy trade can benefit more. The system’s total cost can be
reduced by 17.30%, which demonstrates a remarkable economic advantage for our
transactive energy management system.

Figure 11: The overall costs for all 10 users under standalone and coordinated
scenarios. (The percentage number above bars refers to the cost reduction.)

##  6 Conclusion

This paper presented a consensus-based decentralized transactive energy
management strategy that enables prosumers with DERs to trade energy with each
other in an automated manner. We adopted a consensus-based algorithm to
achieve decentralized coordination and hence to improve the utilization of
local DERs.

  * •

Our designed algorithm does not require any central coordinator, because it
can be completely set up with D2D communication supported by IoT technologies.
Also, our model will be maneuverable to different types of D2D communication
network structures.

  * •

Information transmitted between the IoT-aided smart meters only involves
individual estimations on trading prices and energy mismatch during
iterations, which means personal usage information will not be shared with
others, and users’ privacy can be well preserved.

  * •

Our simulation results showed that our system is feasible under different
network structures and scalable to different sizes of grids. The costs for
both the gird and all users can be significantly reduced under our model.

  * •

For future work, we will improve the iteration process of the consensus-based
algorithm when implementing it in a larger community with more homes. Also, we
will attempt to integrate our transactive energy management system with
blockchain technology (e.g., smart contract) to further enhance the automation
process and secure personal transactive information during energy trading.

## References

  * [1] Manusov VZ, Khasanzoda N, Atabaeva LS. Two-Way Energy Flow Optimization Based on Smart Grid Concept. In: 2018 International Conference on Industrial Engineering, Applications and Manufacturing (ICIEAM), May 15-18; 2018; Moscow, Russia: 1-6
  * [2] Yaghmaee Moghaddam MH, Leon-Garcia A. A fog-based internet of energy architecture for transactive energy management systems. IEEE Internet of Things Journal 2018; 5(2): 1055-1069.  doi: 10.1109/JIOT.2018.2805899
  * [3] Chen M, Miao Y, Hao Y, Hwang K. Narrow Band Internet of Things. IEEE Access 2017; 5: 20557-20577.  doi: 10.1109/ACCESS.2017.2751586
  * [4] Nauman A, Jamshed MA, Ahmad Y, Ali R, Zikria YB, Won Kim S. An Intelligent Deterministic D2D Communication in Narrow-band Internet of Things. In: 2019 15th International Wireless Communications Mobile Computing Conference (IWCMC), Jun. 24-28; 2019; Tangier, Morocco: 2111-2115
  * [5] Choi M, Lee I. Distributed energy resources monitoring and control based on IoT protocol. In: 2017 International Conference on Information and Communication Technology Convergence (ICTC), Oct. 18-20; 2017; Jeju Island, Korea: 1115-1117
  * [6] Li Y, Cheng X, Cao Y, Wang D, Yang L. Smart Choice for the Smart Grid: Narrowband Internet of Things (NB-IoT). IEEE Internet of Things Journal 2018; 5(3): 1505-1515.  doi: 10.1109/JIOT.2017.2781251
  * [7] Vasquez JC, Guerrero JM, Miret J, Castilla M, de Vicuña LG. Hierarchical Control of Intelligent Microgrids. IEEE Industrial Electronics Magazine 2010; 4(4): 23-29.  doi: 10.1109/MIE.2010.938720
  * [8] Fukuta M, Matsui K, Ito M, Nishi H. Proposal for home energy management system to survey individual thermal comfort range for HVAC control with little contribution from users. In: 2015 IEEE 13th International Conference on Industrial Informatics (INDIN), Jul. 22-24; 2015; Cambridge, UK: 658-663.
  * [9] Luna AC, Diaz NL, Graells M, Vasquez JC, Guerrero JM. Cooperative energy management for a cluster of households prosumers. IEEE Transactions on Consumer Electronics 2016; 62(3): 235-242.  doi: 10.1109/TCE.2016.7613189
  * [10] Tenti P, Costabeber A, Caldognetto T, Mattavelli P. Improving microgrid performance by cooperative control of distributed energy sources. In: 2013 IEEE Energy Conversion Congress and Exposition, Sep. 15-19; 2013; Denver, CO, USA: 1647-1654
  * [11] Yi P, Hong Y, Liu F. Initialization-free distributed algorithms for optimal resource allocation with feasibility constraints and application to economic dispatch of power systems. Automatica 2016; 74: 259–269.
  * [12] Psychoula I, Singh D, Chen L, Chen F, Holzinger A, Ning H. Users’ Privacy Concerns in IoT Based Applications. In: 2018 IEEE SmartWorld, Ubiquitous Intelligence Computing, Advanced Trusted Computing, Scalable Computing Communications, Cloud Big Data Computing, Internet of People and Smart City Innovation, Oct. 7-11; 2018; Guangzhou, China: 1887-1894
  * [13] Eibl G, Engel D. Influence of Data Granularity on Smart Meter Privacy. IEEE Transactions on Smart Grid 2015; 6(2): 930-939.  doi: 10.1109/TSG.2014.2376613
  * [14] Cha S, Hsu T, Xiang Y, Yeh K. Privacy Enhancing Technologies in the Internet of Things: Perspectives and Challenges. IEEE Internet of Things Journal 2019; 6(2): 2159-2187.  doi: 10.1109/JIOT.2018.2878658
  * [15] Parisio A, Wiezorek C, Kyntäjä T, Elo J, Strunz K, Johansson KH. Cooperative MPC-Based Energy Management for Networked Microgrids. IEEE Transactions on Smart Grid 2017; 8(6): 3066-3074.  doi: 10.1109/TSG.2017.2726941
  * [16] Chang L, Wang X, Mao M. Transactive energy scheme based on multi-factor evaluation and contract net protocol for distribution network with high penetration of DERs. In: 2017 Chinese Automation Congress (CAC), Oct. 20-22; 2017; Jinan, China: 7139-7144
  * [17] Ge Y, Ye H, Loparo KA. Agent-Based Privacy Preserving Transactive Control for Managing Peak Power Consumption. IEEE Transactions on Smart Grid 2020; 11(6): 4883-4890.  doi: 10.1109/TSG.2020.2997314
  * [18] Le X, Chen S, Yan Z, et al. Enabling a transactive distribution system via real-time distributed optimization. IEEE Transactions on Smart Grid 2018; 10(5): 4907–4917.
  * [19] Nizami MSH, Hossain MJ, Fernandez E. Multiagent-Based Transactive Energy Management Systems for Residential Buildings With Distributed Energy Resources. IEEE Transactions on Industrial Informatics 2020; 16(3): 1836-1847.  doi: 10.1109/TII.2019.2932109
  * [20] Aitzhan NZ, Svetinovic D. Security and Privacy in Decentralized Energy Trading Through Multi-Signatures, Blockchain and Anonymous Messaging Streams. IEEE Transactions on Dependable and Secure Computing 2018; 15(5): 840-852.  doi: 10.1109/TDSC.2016.2616861
  * [21] Yang Q, Wang H. Blockchain-Empowered Socially Optimal Transactive Energy System: Framework and Implementation. IEEE Transactions on Industrial Informatics 2021; 17(5): 3122–3132.  doi: 10.1109/TII.2020.3027577
  * [22] Yang Q, Wang H. Privacy-Preserving Transactive Energy Management for IoT-aided Smart Homes via Blockchain. IEEE Internet of Things Journal 2021: 1–13.  doi: 10.1109/JIOT.2021.3051323
  * [23] Chen S, Zhang L, Yan Z, Shen Z. A distributed and robust security-constrained economic dispatch algorithm based on blockchain. IEEE Transactions on Power Systems 2021\.
  * [24] Chen S, Shen Z, Zhang L, et al. A trusted energy trading framework by marrying blockchain and optimization. Advances in Applied Energy 2021; 2: 100029.
  * [25] Lu Y, Lian J, Zhu M. Privacy-Preserving Transactive Energy System. In: 2020 American Control Conference (ACC), Jul. 1-3; 2020; Denver, CO, USA: 3005-3010
  * [26] Yang S, Tan S, Xu J. Consensus Based Approach for Economic Dispatch Problem in a Smart Grid. IEEE Transactions on Power Systems 2013; 28(4): 4416-4426.  doi: 10.1109/TPWRS.2013.2271640
  * [27] Zhao C, He J, Cheng P, Chen J. Privacy-preserving consensus-based energy management in smart grid. In: 2017 IEEE Power & Energy Society General Meeting, July 16-20; 2017; Chicago, Illinois, USA: 1-5
  * [28] Celik B, Roche R, Bouquain D, Miraoui A. Decentralized Neighborhood Energy Management With Coordinated Smart Home Energy Sharing. IEEE Transactions on Smart Grid 2018; 9(6): 6387-6397.  doi: 10.1109/TSG.2017.2710358
  * [29] Wang J, Zhong H, Wu C, Du E, Xia Q, Kang C. Incentivizing distributed energy resource aggregation in energy and capacity markets: An energy sharing scheme and mechanism design. Applied Energy 2019; 252: 113471.  doi: 10.1016/j.apenergy.2019.113471
  * [30] Residential Electric Rates & Line Items. .  Austinenergy.com accessed Dec. 2, 2020.  Available: https://austinenergy.com/ae/rates/residential-rates/residential-electric-rates-and-line-items/.
  * [31] Cui S, Wang Y, Xiao J. Peer-to-Peer Energy Sharing Among Smart Energy Buildings by Distributed Transaction. IEEE Transactions on Smart Grid 2019; 10(6): 6491-6501.  doi: 10.1109/TSG.2019.2906059
  * [32] Wang H, Huang J. Incentivizing energy trading for interconnected microgrids. IEEE Transactions on Smart Grid 2018; 9(4): 2647–2657.  doi: 10.1109/TSG.2016.2614988
  * [33] Passey R, Watt M, Bruce A, MacGill I. Who pays, who benefits? The financial impacts of solar photovoltaic systems and air-conditioners on Australian households. Energy Research & Social Science 2018; 39: 198-215.  doi: 10.1016/j.erss.2017.11.018
  * [34] Lai X, Xie L, Xia Q, Zhong H, Kang C. Decentralized multi-area economic dispatch via dynamic multiplier-based Lagrangian relaxation. IEEE Transactions on Power Systems 2014; 30(6): 3225–3233.
  * [35] Li J, Ye Y, Papadaskalopoulos D, Strbac G. Consensus-Based Coordination of Time-Shiftable Flexible Demand. In: 2019 International Conference on Smart Energy Systems and Technologies (SEST), Sep. 9-11; 2019; Porto, Portugal: 1-6
  * [36] Zhang Z, Chow M. Convergence Analysis of the Incremental Cost Consensus Algorithm Under Different Communication Network Topologies in a Smart Grid. IEEE Transactions on Power Systems 2012; 27(4): 1761-1768.  doi: 10.1109/TPWRS.2012.2188912
  * [37] Liu XK, Yan J, Xing L, Wen C. Constrained Consensus-based Iterative Algorithm for Economic Dispatch in Power Systems. In: The 46th Annual Conference of the IEEE Industrial Electronics Society, Oct. 19-21; 2020; Singapore: 3537-3542
  * [38] Wang H, Huang J. Hybrid renewable energy investment in microgrid. In: 2014 IEEE International Conference on Smart Grid Communications (SmartGridComm); 2014: 602–607.
  * [39] Wang H, Huang J. Joint investment and operation of microgrid. IEEE Transactions on Smart Grid 2017; 8(2): 833–845.  doi: 10.1109/TSG.2015.2501818
  * [40] Dataport. .  Website, Pecan Street Inc. accessed Oct. 1, 2019.  Available: https://www.pecanstreet.org/dataport/.


# Stochastic Contextual Bandits with Graph-based Contexts

Jittat Fakcharoenphol Email<EMAIL_ADDRESS>Department of Computer
Engineering, Kasetsart University, Bangkok, Thailand, 10900. Supported by the
Thailand Research Fund, Grant RSA-6180074. Chayutpong Prompak Email:
<EMAIL_ADDRESS>Department of Computer Engineering, Kasetsart
University, Bangkok, Thailand, 10900.

###### Abstract

We naturally generalize the on-line graph prediction problem to a version of
stochastic contextual bandit problems where contexts are vertices in a graph
and the structure of the graph provides information on the similarity of
contexts. More specifically, we are given a graph $G=(V,E)$, whose vertex set
$V$ represents contexts with unknown vertex label $y$. In our stochastic
contextual bandit setting, vertices with the same label share the same reward
distribution. The standard notion of instance difficulties in graph label
prediction is the cutsize $f$ defined to be the number of edges whose end
points having different labels. For line graphs and trees we present an
algorithm with regret bound of $\tilde{O}(T^{2/3}K^{1/3}f^{1/3})$ where $K$ is
the number of arms. Our algorithm relies on the optimal stochastic bandit
algorithm by Zimmert and Seldin [AISTAT’19, JMLR’21]. When the best arm
outperforms the other arms, the regret improves to $\tilde{O}(\sqrt{KT\cdot
f})$. The regret bound in the later case is comparable to other optimal
contextual bandit results in more general cases, but our algorithm is easy to
analyze, runs very efficiently, and does not require an i.i.d. assumption on
the input context sequence. The algorithm also works with general graphs using
a standard random spanning tree reduction.

##  1 Introduction

Side information for many learning problems can be represented as a graph. For
example, since a “type” of a social network user is typically highly
correlated with the user’s friends, social network service providers, with
full knowledge of the social network graph, can use the graph structure to
help making decision on which advertisement to show to the user. It can also
use the graph structure to infer various properties of its users, e.g., their
life styles, social statuses, and marketing values.

User type prediction can be modeled as follows. Given an $n$-vertex graph
$G=(V,E)$, a label set ${\mathcal{L}}$, and an unknown vertex labels
$y:V\rightarrow{\mathcal{L}}$ representing certain vertex classification, the
on-line label prediction problem, studied in Herbster, Pontil, and Wainer [1];
Herbster and Pontil [2]; Herbster, Lever, and Pontil [3]; and Cesa-Bianchi,
Gentile, and Vitale [4], works in rounds, for each round, a vertex is queried,
and the learning algorithm predicts the label of that particular vertex. The
available graph structure provides clues to the learner by promising that
adjacent vertices usually have the same label. The measure of complexity of
the problem instance is the cutsize $f=f_{G}(y)$ defined as the number of
edges $(u,v)\in E$ such that $y(u)\neq y(v)$. We note that while the notion of
cutsize is very natural when the graph is a tree, in a general graph the
cutsize can be large, e.g., for dense graph the cutsize can be
$\Omega(n^{2})$. Previous results on graph prediction guarantee mistake bounds
that depend linearly on $f$ and logarithmically on the size of the graph $n$.

In most case, we have no access to vertex real labels and more importantly,
our goal is to make decisions instead of figuring out the labels. Also, the
problem itself may have elements of uncertainty. For example, the same user
may give different responses when asked many times.

With this motivation, we generalize the label prediction to a version of
stochastic contextual bandit problems where contexts are vertices in a graph
and the structure of the graph provides information on the similarity of
contexts. More specifically, the unknown label $y$ defines the context group
and vertices from the same context group share the same reward behavior (as
modeled by a bandit problem).

We are interested in the case where the reward behavior is represented as a
stochastic multi-armed bandit problem with $K$ arms. Given graph $G=(V,E)$
(with unknown vertex label $y$), the algorithm proceeds in $T$ rounds and, for
each round $t$, receives a context $u\in V$. The algorithm has to pick an arm
$I_{t}$ to maximize the total rewards. The rewards stochastically depend on
the unknown vertex label $y(u)$ and the arm $I$. Unlike the label prediction
problem, a single vertex $u$ can be queried multiple times. We only consider
the case of $[0,1]$ rewards.

Essentially we deal with line graphs. Given the algorithm for line graphs, a
simple reduction by Herbster, Lever, and Pontil [3] allows us to work with a
tree with $f$ cut edges using a line graph with $2\cdot f$ cut edges. For
general graphs, we work with their random spanning tree representation as in,
e.g., [4, 3, 5]. We state relevant results in Section 4.

Our main result on line graphs (and trees) is the following.

######  Theorem 1.

Consider a line graph or a tree with $n$ vertices and $f$ cut edges. There is
an efficient bandit algorithm that has a regret bound of
$\tilde{O}(T^{2/3}\cdot K^{1/3}\cdot f^{1/3})$, where $T$ is the number of
rounds and $K$ is the number of arms.

Our algorithm is a very simple divide-and-conquer algorithm that
hierarchically decompose the contexts into many levels. Originally, our
algorithm relies heavily on the best-arm identification algorithm, called
Successive Rejects, of Audibert, Bubeck, and Munos [6] with regret bound of
$\tilde{O}(T^{3/4}\cdot K^{1/4}\cdot f^{1/4})$. The simpler and better version
using an optimal bandit subroutine by Zimmert and Seldin [7] presented here
has been suggested by Anonymous Reviewer # 2 from ALT’21.

It still requires the prior knowledge of the total number of rounds $T$. We
note that there are dependencies between $T$ and $K$, i.e., $K\leq T$ so that
the bound does not implies an upper bound better than $\Omega(\sqrt{KT})$. The
above bound is distribution independent, i.e., it works for any reward
distribution.

However, in an easy case, where the best arm outperforms the other arms, the
Tsallis-INF algorithm has a better regret bound and, in turn, we also have an
improved bound of $\tilde{O}(\sqrt{KT\cdot f})$.

One notable property of the algorithm is that it does not aim to identify the
cut edges, so there is no need for a requirement that different context groups
should behave differently.

Also, the parameter $f$ is actually the “observable” cutsize, i.e., if some
vertex $u$ does not appear as contexts we are free to assume its label $y(u)$
to be anything and the observable cutsize is the minimum cutsize obtainable
after some label renaming.

As our work is very simple (after the suggestion from an anonymous reviwer),
we defer the discussion and comparison with related work to Section 5. Section
2 gives formal settings. The algorithm for line graphs and its analysis is
presented in Section 3. We briefly discuss how to extend the line-graph result
to trees and general graphs in Section 4.

##  2 Preliminaries

###  2.1 Settings

We are given a context set $S=\\{c_{1},c_{2},c_{3},...,c_{N}\\}$ and arms
$1,2,\ldots,K$. At each time step $t=1,2,\ldots,$ the player receives a
context $c\in S$ and has to play an arm $I_{t}\in\\{1,\ldots,K\\}$ then incurs
reward $X_{I_{t},t}\in[0,1]$. The goal is to maximize reward. For contextual
stochastic bandits strategy, the reward $X_{I_{t},t}$ is drawn independently
from the past from an unknown distribution $\nu_{I_{t}}^{c}$ that depends only
on the context $c$ and the arm $I_{t}$. In this work we consider losses,
defined as $\ell_{I_{t},t}=1-X_{I_{t},t}$ rather than rewards.

The learning problem proceeds in $T$ rounds. For each round, the algorithm is
to map contexts to arms and minimizes the loss. The total losses after $T$
rounds is $\sum_{t=1}^{T}\ell_{I_{t},t}$.

For context $c$ and arm $i$, let $\mu_{i}^{c}$ be the mean reward from
distribution $\nu_{i}^{c}$. Let $i^{*}_{c}$ be the best arm for context $c$,
i.e., $i^{*}_{c}=\arg_{i}\max_{i=1}^{K}\mu_{i}^{c}$. Thus for context $c$, the
minimum expected loss, denoted by $loss^{*}_{c}$, is

$1-\mu_{i^{*}_{c}}^{c}.$

Thus, given a sequence of contexts $s_{1},s_{2},\ldots,s_{T}$, the minimum
expected loss, denoted as $loss^{*}$, is

$loss^{*}=\sum_{t=1}^{T}loss^{*}_{s_{t}}.$

We are also given a graph $G=(S,E)$ with an unknown vertex label
$y:S\rightarrow L$ for some label set $L$. We sometimes refer to a context in
$S$ as a vertex. Every context with the same label share the same reward
distribution, i.e., for every pair of context $c,c^{\prime}\in S$ such that
$y(c)=y(c^{\prime})$, for every arm $i$, the distribution
$v_{i}^{c}=v_{i}^{c^{\prime}}$. Note that we have no access to the labels $y$.
The labels $y$ partition contexts into context groups. When context $c$ and
$c^{\prime}$ share the same label, we say that $c$ and $c^{\prime}$ are from
the same group. Contexts from the same group share the same best arm.

Given the graph $G=(S,E)$ and vertex label $y$, an edge $(u,v)\in E$ is a cut
edge if $y(u)\neq y(v)$. Let $f$ be the number of cut edges.

In this work, we mostly work with line graphs. The result extends to trees and
general graphs using standard techniques (see Section 4).

###  2.2 The multi-armed bandit problem

Since the underlying problem for a specific context $c$ is the stochastic
version of the multi-armed bandit, we start by reviewing the problem and
algorithms for solving it in this section. In this problem, there are $K$
arms; each arm $i$ corresponds to an unknown probability distribution
$\nu_{i}$. For each round $t=1,\ldots,T$, the algorithm picks an arm
$I_{t}\in\\{1,\ldots,K\\}$ and receives rewards $X_{I_{t},t}$ drawn from
$\nu_{i}$. Let $\mu_{i}$ be the mean of arm $i$; the best arm $i^{*}$ is
$\arg_{i}\max_{i}\mu_{i}$. Let $\mu^{*}=\mu_{i^{*}}$. The pseudo-regret for
the algorithm is

$T\mu^{*}-{\mathbbm{E}}\left[\sum_{t=1}^{T}\mu_{I_{t}}\right].$

Since the learning becomes harder when the expected rewards of other arms are
close to $\mu_{i}$, we define $\Delta_{i}=\mu^{*}-\mu_{i}$ to represent how
close arm $i$ to the best arm. As in [7], we assume that there is a unique
best arm $i^{*}$ where $\Delta_{i^{*}}=0$ and $\Delta_{i}>0$ for all $i\neq
i^{*}$. We let $\Delta_{\mathrm{min}}=\min_{\Delta_{i}>0}\Delta_{i}$.

Our main subroutine is the Tsallis-INF algorithm by [7], which is an algorithm
based on online mirror descent with Tsallis entropy regularization with power
$\alpha=1/2$. The algorithm uses an unbiased estimator for the loss
$\hat{\ell}_{i,t}$ for arm $i$ at time $t$, such that
${\mathbbm{E}}_{I_{t}}[\hat{\ell}_{i,t}]=\ell_{i,t}$ internally. While [7]
proposed two alternatives for these estimators, we focus on the one based on
importance-weighted sampling referred to as (IW) estimators and only state
their result for this type of estimators below.

######  Theorem 2 ([7]).

The pseudo-regret of Tsallis-INF with $\alpha=1/2$ using (IW) estimators is at
most

$4\sqrt{KT}+1,$

where $K$ is the number of arms and $T$ is the number of rounds. Also if
$\Delta_{\min}$ is a constant, the pseudo-regret can be bounded by

$O(K\log T).$

We refer to the case where $\Delta_{\min}=\Omega(1)$ as an easy case. This
case is discussed in Section 3.2.

##  3 An algorithm for line graphs and its analysis

We start by describing a divide-and-conquer algorithm111 We remark again that,
originally, the algorithm is more complex than the one presented here based on
Tsallis-INF as suggested by an anonymous referee from ALT’21. We really
appreciate the suggestion.  for line graphs, where, for $1\leq i<n$, vertex
(context) $c_{i}$ is adjacent to vertex $c_{i+1}$. For simplicity, assume that
$n$ is a power of two, i.e., let $n=2^{L}$.

This algorithm hierarchically decomposes the context set into $O(\log n)$
levels. For each level, we partition the context set into a set of the same
size, and treat contexts in the same set as if they are from the same unknown
context group. At the top level, we have only two context sets, each of size
$n/2$. As the level decreases, the size of each context set decreases
exponentially. We start by running bandit subroutines on the highest level.
When an active subroutine for context set $C^{\prime}$ runs for a number of
rounds, we terminate it, pretend to split the context $C^{\prime}$ by going
down a level, and start running two new bandit subroutines.

We now formally describe the algorithm. Recall that $n=2^{L}$. We maintain
stochastic bandit subroutines, each executes the Tsallis-INF algorithm, in $L$
levels. For level $p$, where $1\leq p\leq L$, there are $n/2^{L-p}$ bandit
subroutines, denoted by $B_{p}(1),\ldots,B_{p}(n/2^{L-p})$. Bandit subroutine
$B_{p}(j)$, essentially, deals with contexts

$\\{c_{2^{(L-p)(j-1)}},\ldots,c_{2^{(L-p)j}}\\}$

as if they are from the same group. We also say that bandit subroutine
$B_{p}(j)$ is responsible for contexts

$\\{c_{2^{(L-p)(j-1)}},\ldots,c_{2^{(L-p)j}}\\}.$

For level $1\leq p<L$, for subroutine $B_{p}(j)$, we call $B_{p+1}(j_{l})$ and
$B_{p+1}(j_{r})$, where $j_{l}=2j-1$ and $j_{r}=2j$, children of $B_{p}(j)$.
Note that they are responsible for contexts
$\\{c_{2^{(L-p)(j-1)}},\ldots,c_{2^{(L-p)j}/2}\\}$ and
$\\{c_{2^{(L-p)j}/2+1},\ldots,c_{2^{(L-p)j}}\\}$, respectively. (See figure
1).

Contexts
---
1
---
2
---
3
---
Levels
---
$B_{1}(1)$
---
$B_{1}(2)$
---
$B_{2}(1)$
---
$B_{2}(2)$
---
$B_{2}(3)$
---
$B_{2}(4)$
---
$B$
---
1
---
2
---
3
---
4
---
5
---
6
---
7
---
8
---
Figure 1: Subroutines and contexts. $B_{1}(1)$ is responsible for context set
{1,2,3,4}. $B_{2}(1)$ and $B_{2}(2)$ are children of $B_{1}(1)$.

There is a parameters $D$ that defines the number of rounds a bandit
subroutine handles requests on its responsible contexts. Each subroutine
$B_{p}(j)$ not on level $L$ would runs the Tsallis-INF algorithm for $D$
rounds, after that it deactivates itself and activates its children
$B_{p+1}(j_{l})$ and $B_{p+1}(j_{r})$.

###  3.1 Analysis of pseudo-regret for line graphs

We essentially analyze the case for line graphs. The analysis for the general
cases (for trees and general graphs) follows from standard reductions (see
Section 4).

For each bandit subroutine $B_{p}(j)$, we say that the subroutine is in good
situation if its responsible contexts are from the same context group.
Otherwise, we say that it is in a bad situation. (See figure 2).

Contexts
---
1
---
2
---
3
---
Levels
---
Bad
---
Bad
---
Good
---
Good
---
Bad
---
Good
---
B
---
1
---
2
---
3
---
4
---
5
---
6
---
7
---
8
---
G
---
G
---
group 1
---
group 2
---
group 3
---
Figure 2: Subroutines in good and bad situations.

Let $\mathcal{C}$ be the set of every context set that some bandit subroutine
is responsible for.

We first bound the number of bandit subroutines in bad situations. A
subroutine $B_{p}(j)$ is in a bad situation when the subgraph of $G$
corresponding to the contexts that $B_{p}(j)$ is responsible for contains a
cut edge. Recall that our decomposition contains $O(\log n)$ levels; thus, a
single cut edge may appear in $O(\log n)$ context sets in $\mathcal{C}$ and
contributes to $O(\log n)$ subroutines in bad situations. Since there are $f$
cut edges, the number of subroutines in bad situations is $O(f\cdot\log n)$,
yielding the following lemma.

######  Lemma 1.

The number of subroutines in bad situations is at most $O(f\cdot\log n)$.

We are ready to prove the main theorem (which is a restatement of Theorem 1).

######  Theorem 3.

If the cutsize of a line graph is $f$, the pseudo-regret is at most
$\tilde{O}(T^{2/3}K^{1/3}f^{1/3})$.

###### Proof.

Since only two new subroutines are activated after their parent deactivates
and each subroutine deactivates after handling $D$ requests, the number of
subroutines activated is at most $2T/D$.

From Lemma 1, the number of subroutines in bad situations is at most
$O(f\cdot\log n)$. Each of these subroutines can make at most $D$ regret, a
total of $O(D\cdot f\cdot\log n)$.

From Theorem 2, each subroutine in a good situation contributes to at most

$4\sqrt{KD}+1,$

since it runs for at most $D$ rounds.

Combining both bounds, we have that the regret incurred by the algorithm is at
most

$O(D\cdot f\cdot\log n)+2T/D\cdot O(\sqrt{KD})=O(D\cdot f\log n+T\sqrt{K/D}).$

Choosing $D=\tilde{\Theta}(T^{2/3}K^{1/3}/f^{2/3})$, we have that the pseudo-
regret is at most

$\tilde{O}(T^{2/3}K^{1/3}f^{1/3}),$

as claimed. ∎

###  3.2 When the best arm is easy to identify

In this section, we assume that $\Delta_{\min}$ is a constant. In this case,
the second part of Theorem 2 ensures that the pseudo-regret for subroutines in
good situations after $D$ rounds is at most $O(K\log D)$.

Using the same analysis as in Theorem 3, we have that the pseudo-regret can be
bounded by

$O(D\cdot f\log n+(T/D)\cdot K\log D).$

Choosing $D=\Omega(\sqrt{TK/f})$, the pseudo-regret becomes

$\tilde{O}(\sqrt{KT\cdot f}).$

##  4 General graphs

###  4.1 Reduction from trees to line graphs

As in the graph label prediction problem, Herbster, Lever, and Pontil [3] show
that we can reduce the problem when the graph is a tree to the case when the
graph is a line graph (called a spine) while paying a factor of 2 for the
cutsize. The spine graph can be constructed using depth-first search on the
tree. We state the following lemma from Section 4 in [3].

######  Lemma 2 ([3]).

Given a tree $T=(V,E)$ with vertex label $y$, there exists a path graph
$G=(V^{\prime},E^{\prime})$, a mapping $g:V\rightarrow V^{\prime}$, and a
natural extension of vertex label $y^{\prime}$ to $V^{\prime}$ such that the
cutsize of $G$ under $y^{\prime}$ is at most twice the cutsize of $T$ under
$y$.

###  4.2 Random spanning tree method

To deal with general graphs, we simply use random spanning tree method as
described in Cesa-Bianchi, Gentile, and Vitale [4]; Herbster, Lever, and
Pontil [3]; and Cesa-Bianchi, Gentile, Vitale, and Zappella [5]. The cutsize
parameter of the learning problem in this case becomes the expected cutsize of
a random spanning tree.

##  5 Related work

The work present in this paper can be compared to results from standard
contextual bandit that deals with large number of policies. There are also a
number of results dealing directly with a set of related bandit problems that
either can be clustered in an online fashion or can be partitioned into
equivalence classes.

###  5.1 Comparison to other contextual bandit algorithms

When considering bandit performance, it is useful to clearly specify the set
for which its performance is compared against. In the contextual bandit
settings, for a given context set $\mathcal{S}$, a policy
$g:{\mathcal{S}}\rightarrow\\{1,\ldots,K\\}$ is a mapping from the context set
to the set of arms. Let $\Pi$ be the set of possible policies and $N=|\Pi|$.
We would like the regret bound to be sublinear in $T$ and logarithmic in $N$
because the set of policies can be very large. Note that in the context of
graph prediction, if the cutsize is $f$, the number of possible policies $N$
can be as large as ${n-1\choose f}=\Omega(n^{f})$. Under this settings, the
contextual bandit algorithms in the adversarial settings such as Exp4 by Auer,
Cesa-Bianchi, Freund, and Schapire [8] and Exp4.P by Beygelzimer, Langford,
Li, Reyzin, and Schapire [9], have regret bound of $O(\sqrt{KT\log
N})=O(\sqrt{KT\cdot f\log n})$ (in expectation for [8] and with high
probability in [9]).

Since our more general result (in Theorem 1) has a regret bound that depends
on $T^{2/3}$, it is likely to be suboptimal. However, when we assume that that
the best arm is much better than the other arms (in Section 3.2), our regret
bound is of the right order, i.e., $\tilde{O}(\sqrt{KT\cdot f})$.

While the adversarial bandit algorithms Exp4 [8] and Exp4.P [9], in the
general case, perform better than the one presented here, these algorithms
have to process weight vector of size $N=\Omega(n^{f})$, which can be very
large. Beygelzimer et al [9] also present algorithm VE that competes against
policies with finite VC dimension $d$ in an i.i.d case. This algorithm, in our
case, is again inefficient as it has to run against a policy set of size
$\Omega(\sqrt{T}^{f})$, because the VC dimension is at least $f$.

More recent works such as Langford and Zhang [10], Dudik et al [11], and
Agarwal et al [12] aim to reduce the dependency on $N$ on the running time and
memory requirements. Instead of keeping a large weight vector, they make calls
to a hypothesis searching oracle. Agarwal et al [12] achieves the optimal
regret bound of $O(\sqrt{T\log(|\Pi|)})$, while making only
$O(\sqrt{T/\log(|\Pi|)})$ calls. The drawback is that they all work under the
i.i.d. assumption, i.e., they assume that the context and reward for each
round is independently sampled from a fixed distribution. While our work
assumes the stochastic model, i.e., the reward is independently sampled for a
given context, the contexts given to the algorithm can be generated by an
adversary.

###  5.2 Comparison to other clustering results for bandit problems

There are results that consider online clustering of linear bandits, e.g.,
[13, 14, 15, 16]. Cesa-Bianchi, Gentile, and Zappella [13] consider a linear
bandit problem with social relationship modeled as an undirected graph
$G=(V,E)$ where $V$ represents a set of $n$ users, each with an unknown
parameter vector $u_{i}\in{\mathbbm{R}}^{d}$. The graph provides structures to
the parameters $u_{i}$, i.e., they assume that $\sum_{(i,j)\in
E}\|u_{i}-u_{j}\|^{2}$ are small compared to $\sum_{i\in V}\|u_{i}\|^{2}$. The
learning proceeds in rounds. For each round $t$, the user index $i_{t}$ and a
set of arbitrary context vectors $C_{i_{t}}=\\{x_{t,1},\ldots,x_{t,c_{t}}\\}$
is presented and the learner has to pick one action $\bar{x_{t}}\in C_{i_{t}}$
and receives a reward of $u_{i}^{T}\bar{x_{t}}$ with an additional sub-
Gaussian noise. Cesa-Bianchi et al [13] maintain a set of $n$ linear bandit
algorithms and an inverse correlation matrix $M_{t}$ for feedback sharing
between bandit algorithms. They obtain a regret bound that depends on
$\sqrt{nT}$ and log determinant of the matrix $M_{t}$, which can be $O(n)$.
Gentile, Li, and Zappella [14] consider a more structured setting, where users
can be partitioned into $m$ unknown clusters and the context vectors $C_{t}$
in each round $t$ are generated i.i.d. (where the size can be arbitrary). We
note that this setting is closely related to our work where $m=f+1$. Gentile
et al [14] give a regret bound that depends on $\sqrt{mT}$ with additional
$O(n+m)$ terms that are constant with $T$. A recent result by Gentile et al
[15] considers various data-dependent assumptions to obtain sharper bounds
that depend on $\sqrt{Tm}$ and $n\cdot\mathrm{polylog}(nT)$.

Another line of work, by Maillard and Munos[17] and Hong et al [18], considers
latent bandits where there is a partition of context types ${\mathcal{B}}$
into $C$ clusters $\mathcal{C}=\\{{\mathcal{B}}_{c}\\}$, each with known
reward distribution. However, the learner, when receiving the context type
$b\in{\mathcal{B}}$, does not know the cluster ${\mathcal{B}}_{c}$ containing
$b$. This is a much harder problem. Our setting provides more structures, in
forms of graphs, that guides the clustering of vertices. We, however, do not
know the reward distributions before hand.

###  5.3 Other related works

There are other works on contextual bandit problems with some structure. See,
for example, [19, 20], and [21] that consider similarity between contexts and
arms.

There are numerous extensions to the graph label prediction problems, see,
e.g., [1, 2, 3, 4, 22], and [23].

Alon et al [24] consider a multi-armed bandit problem when the feedback is
constrained with a feedback graph.

##  6 Acknowledgements

We would like to thanks reviewers from COLT’19, ALT’22, and IPL for many
useful comments. Especially, reviewers from ALT’22 who suggested a simpler and
better algorithm presented here. Both authors are supported by the Thailand
Research Fund [Grant number RSA-6180074].

## References

  * [1] M. Herbster, M. Pontil, L. Wainer, Online learning over graphs, in: Machine Learning, Proceedings of the Twenty-Second International Conference (ICML 2005), Bonn, Germany, August 7-11, 2005, 2005, pp. 305–312.  doi:10.1145/1102351.1102390.
URL https://doi.org/10.1145/1102351.1102390

  * [2] M. Herbster, M. Pontil, Prediction on a graph with a perceptron, in: Advances in Neural Information Processing Systems 19, Proceedings of the Twentieth Annual Conference on Neural Information Processing Systems, Vancouver, British Columbia, Canada, December 4-7, 2006, 2006, pp. 577–584.
URL http://papers.nips.cc/paper/3100-prediction-on-a-graph-with-a-perceptron

  * [3] M. Herbster, G. Lever, M. Pontil, Online prediction on large diameter graphs, in: Advances in Neural Information Processing Systems 21, Proceedings of the Twenty-Second Annual Conference on Neural Information Processing Systems, Vancouver, British Columbia, Canada, December 8-11, 2008, 2008, pp. 649–656.
URL http://papers.nips.cc/paper/3475-online-prediction-on-large-diameter-
graphs

  * [4] N. Cesa-Bianchi, C. Gentile, F. Vitale, Fast and optimal prediction on a labeled tree, in: COLT 2009 - The 22nd Conference on Learning Theory, Montreal, Quebec, Canada, June 18-21, 2009, 2009.
URL http://www.cs.mcgill.ca/%7Ecolt2009/papers/015.pdf#page=1

  * [5] N. Cesa-Bianchi, C. Gentile, F. Vitale, G. Zappella, Random spanning trees and the prediction of weighted graphs, in: Proceedings of the 27th International Conference on Machine Learning (ICML-10), June 21-24, 2010, Haifa, Israel, 2010, pp. 175–182.
URL http://www.icml2010.org/papers/298.pdf

  * [6] J. Audibert, S. Bubeck, R. Munos, Best arm identification in multi-armed bandits, in: A. T. Kalai, M. Mohri (Eds.), COLT 2010 - The 23rd Conference on Learning Theory, Haifa, Israel, June 27-29, 2010, Omnipress, 2010, pp. 41–53.
URL http://colt2010.haifa.il.ibm.com/papers/COLT2010proceedings.pdf#page=49

  * [7] J. Zimmert, Y. Seldin, Tsallis-inf: An optimal algorithm for stochastic and adversarial bandits, Journal of Machine Learning Research 22 (28) (2021) 1–49.
URL http://jmlr.org/papers/v22/19-753.html

  * [8] P. Auer, N. Cesa-Bianchi, Y. Freund, R. E. Schapire, The nonstochastic multiarmed bandit problem, SIAM J. Comput. 32 (1) (2003) 48–77.  doi:10.1137/S0097539701398375.
URL https://doi.org/10.1137/S0097539701398375

  * [9] A. Beygelzimer, J. Langford, L. Li, L. Reyzin, R. Schapire, Contextual bandit algorithms with supervised learning guarantees, in: G. Gordon, D. Dunson, M. Dudík (Eds.), Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, Vol. 15 of Proceedings of Machine Learning Research, PMLR, Fort Lauderdale, FL, USA, 2011, pp. 19–26.
URL http://proceedings.mlr.press/v15/beygelzimer11a.html

  * [10] J. Langford, T. Zhang, The epoch-greedy algorithm for contextual multi-armed bandits, in: Proceedings of the 20th International Conference on Neural Information Processing Systems, NIPS’07, Curran Associates Inc., USA, 2007, pp. 817–824.
URL http://dl.acm.org/citation.cfm?id=2981562.2981665

  * [11] M. Dudik, D. Hsu, S. Kale, N. Karampatziakis, J. Langford, L. Reyzin, T. Zhang, Efficient optimal learning for contextual bandits, in: Proceedings of the Twenty-Seventh Conference on Uncertainty in Artificial Intelligence, UAI’11, AUAI Press, Arlington, Virginia, United States, 2011, pp. 169–178.
URL http://dl.acm.org/citation.cfm?id=3020548.3020569

  * [12] A. Agarwal, D. Hsu, S. Kale, J. Langford, L. Li, R. E. Schapire, Taming the monster: A fast and simple algorithm for contextual bandits, in: Proceedings of the 31st International Conference on International Conference on Machine Learning \- Volume 32, ICML’14, JMLR.org, 2014, pp. II–1638–II–1646.
URL http://dl.acm.org/citation.cfm?id=3044805.3045075

  * [13] N. Cesa-Bianchi, C. Gentile, G. Zappella, A gang of bandits, in: Proceedings of the 26th International Conference on Neural Information Processing Systems - Volume 1, NIPS’13, Curran Associates Inc., Red Hook, NY, USA, 2013, p. 737–745.
  * [14] C. Gentile, S. Li, G. Zappella, Online clustering of bandits, in: E. P. Xing, T. Jebara (Eds.), Proceedings of the 31st International Conference on Machine Learning, Vol. 32 of Proceedings of Machine Learning Research, PMLR, Bejing, China, 2014, pp. 757–765.
URL https://proceedings.mlr.press/v32/gentile14.html

  * [15] C. Gentile, S. Li, P. Kar, A. Karatzoglou, G. Zappella, E. Etrue, On context-dependent clustering of bandits, in: D. Precup, Y. W. Teh (Eds.), Proceedings of the 34th International Conference on Machine Learning, Vol. 70 of Proceedings of Machine Learning Research, PMLR, 2017, pp. 1253–1262.
URL https://proceedings.mlr.press/v70/gentile17a.html

  * [16] S. Li, W. Chen, S. Li, K.-S. Leung, Improved algorithm on online clustering of bandits, in: Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI-19, International Joint Conferences on Artificial Intelligence Organization, 2019, pp. 2923–2929.  doi:10.24963/ijcai.2019/405.
URL https://doi.org/10.24963/ijcai.2019/405

  * [17] O.-A. Maillard, S. Mannor, Latent bandits., in: E. P. Xing, T. Jebara (Eds.), Proceedings of the 31st International Conference on Machine Learning, Vol. 32 of Proceedings of Machine Learning Research, PMLR, Bejing, China, 2014, pp. 136–144.
URL https://proceedings.mlr.press/v32/maillard14.html

  * [18] J. Hong, B. Kveton, M. Zaheer, Y. Chow, A. Ahmed, C. Boutilier, Latent bandits revisited, in: H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, H. Lin (Eds.), Advances in Neural Information Processing Systems, Vol. 33, Curran Associates, Inc., 2020, pp. 13423–13433.
URL
https://proceedings.neurips.cc/paper/2020/file/9b7c8d13e4b2f08895fb7bcead930b46-Paper.pdf

  * [19] R. Agrawal, The continuum-armed bandit problem, SIAM J. Control Optim. 33 (6) (1995) 1926–1951.  doi:10.1137/S0363012992237273.
URL http://dx.doi.org/10.1137/S0363012992237273

  * [20] R. Kleinberg, A. Slivkins, E. Upfal, Multi-armed bandits in metric spaces, in: Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, STOC ’08, ACM, New York, NY, USA, 2008, pp. 681–690.  doi:10.1145/1374376.1374475.
URL http://doi.acm.org/10.1145/1374376.1374475

  * [21] A. Slivkins, Contextual bandits with similarity information, J. Mach. Learn. Res. 15 (1) (2014) 2533–2568.
  * [22] C. Gentile, M. Herbster, S. Pasteris, Online similarity prediction of networked data from known and unknown graphs, in: COLT 2013 - The 26th Annual Conference on Learning Theory, June 12-14, 2013, Princeton University, NJ, USA, 2013, pp. 662–695.
URL http://jmlr.org/proceedings/papers/v30/Gentile13.html

  * [23] S. Pasteris, F. Vitale, C. Gentile, M. Herbster, On similarity prediction and pairwise clustering, in: Algorithmic Learning Theory, ALT 2018, 7-9 April 2018, Lanzarote, Canary Islands, Spain, 2018, pp. 654–681.
URL http://proceedings.mlr.press/v83/pasteris18a.html

  * [24] N. Alon, N. Cesa-Bianchi, C. Gentile, S. Mannor, Y. Mansour, O. Shamir, Nonstochastic multi-armed bandits with graph-structured feedback, SIAM J. Comput. 46 (6) (2017) 1785–1826.  doi:10.1137/140989455.
URL https://doi.org/10.1137/140989455