{'fraction_non_alphanumeric': 0.04072031434461614, 'fraction_numerical': 0.008034817542684968, 'mean_word_length': 4.388208487610368, 'pattern_counts': {'":': 0, '<': 6, '<?xml version=': 0, '>': 10, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 10, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Optimal Demand Response Using Device Based Reinforcement Learning

Demand response (DR) for residential and small commercial buildings is estimated to account for as much as 65% of the total energy savings potential of DR, and previous work shows that a fully automated Energy Management System (EMS) is a necessary prerequisite to DR in these areas. In this paper, we propose a novel EMS formulation for DR problems in these sectors. Specifically, we formulate a fully automated EMS's rescheduling problem as a reinforcement learning (RL) problem, and argue that this RL problem can be approximately solved by decomposing it over device clusters. Compared with existing formulations, our new formulation (1) does not require explicitly modeling the user's dissatisfaction on job rescheduling, (2) enables the EMS to self-initiate jobs, (3) allows the user to initiate more flexible requests and (4) has a computational complexity linear in the number of devices. We also demonstrate the simulation results of applying Q-learning, one of the most popular and classical RL algorithms, to a representative example.


Introduction
Demand response (DR) systems [Borenstein et al., 2002, Braithwait and Eakin, 2002, Barbose et al., 2004 dynamically adjust electrical demand in response to changing electrical energy prices or other grid signals. DR offers several benefits. By suitably adjusting energy prices, load can be shifted from peak energy consumption periods to other times. This, in turn, can improve operational efficiency, reduce operating costs, improve capital efficiency, and reduce harmful emissions and risk of outages. The variability of renewables can create an additional need to shift energy consumption in order to better match energy demand with unforecasted changes in electrical energy generation. The benefit is a reduction in backup (ancillary) generation frequently used to hedge renewable sources.
There are several types of DR. In direct DR a utility or other entity directly modifies the energy consumption of users by adjusting the operation of user's equipment. Interruptible tariffs allow a utility to interrupt the supply of power to a company under predefined conditions. Price driven DR uses pricing mechanisms to attempt to modulate energy demand. DR has been extensively investigated for larger energy users and has been implemented in many areas (e.g., [Roos andLane, 1998, Piette et al., 2005]). Residential and small commercial building DR [Herter, 2007b,a, Faruqui and George, 2005, Koch and Piette, 2007 offers similar potential benefits. DR for residential and small commercial buildings was estimated to account for as much as 65% of the total energy savings potential of DR. However, DR in the residential and small commercial building sector faces several challenges.
Technical challenges include deploying an infrastructure supplying real-time pricing information to energy consumers 1 in a useful way, ensuring security, and implementing advanced metering and networking devices [Koch andPiette, 2007, LeMay et al., 2008]. In addition to all these technical challenges, another challenge vital to the success of DR in the residential and small commercial building sectors is that it requires a fully automated Energy Management System (EMS) [Koch and. This is because with price driven DR, consumers face a continuing sequence of decisions to either use a particular device now and consume energy at current (known) prices or to defer using the device until later at possibly unknown prices. Each decision requires the consumer to weigh the cost differential against his dissatisfaction due to rescheduling device usage. This is particularly burdensome when the consumer must also estimate future energy prices. Further many of these decisions have limited financial impact on the consumer [ONeill et al., 2010], and, as a result, many rational consumers in the residential and small commercial building sectors may not be sufficiently incentivized to make these decisions over the long run (known as "decision fatigue" in [ONeill et al., 2010]).
To be effective, an EMS system needs to automatically make energy consumption decisions that are consistent with the cost delay trade-offs of energy users, in this way acting as an energy agent. It is often difficult to cost-effectively model the behaviors of the idiosyncratic consumers and the temporal variations of the energy prices, a successful DR EMS needs to learn to make optimal decisions for consumers from interacting with the consumers and energy prices. Recently, [ONeill et al., 2010] proposed a fully-automated EMS algorithm based on reinforcement learning (RL), which learns how to make optimal decisions for consumers. To the best of our knowledge, this is the first paper to apply RL to DR in residential and small commercial building sector. The authors adopt a request inventory model for the system dynamics and use Q-learning, a classical RL algorithm, to learn how to make the optimal decisions for energy consumers. In this approach, users make energy requests to the EMS system (e.g. pushing a button on a device that a user wants to run) and the system schedules the time of operation by calculating the user's trade-offs between delay and energy prices. It learns these trade-offs by observing energy consumer's behaviors and observing the patterns of energy pricing. Over time the EMS learns to make the best decisions for energy users in the sense that it balances energy cost and the delay in energy usage in the same way that the customer optimally would, but without the consumer having to make the decision. The authors explicitly assume that (1) consumers' dissatisfaction with delay can be modeled by known disutility functions, and (2) that consumers explicitly initiate all energy usage. This approach has several limitations: • Finding specific disutility functions for a particular residence or small business can be difficult and costly. In [ONeill et al., 2010], the authors assume these functions have particular mathematical properties, but do not address how these functions might be determined. These functions are likely to be idiosyncratic and are specific to energy price vs. time delay tradeoffs.
• Many energy consuming activities occur without the consumer directly initiating them. HVAC in office buildings and pool heaters in residential settings are obvious examples. A useful EMS would self-initiate jobs for these and similar devices without explicit user requests or reservations. For example, if it is unexpectedly hot in a summer afternoon and the current energy price is expected to be cheaper than that in the evening, then the EMS should be allowed to turn on AC without an explicit request/reservation from the consumer.
• The computational complexity of this approach grows exponentially as the number of devices. Known as the "curse-of-dimensionality" in dynamic programming (DP) and RL literature, this problem limits the approach to fairly small numbers of devices.
In this paper, we propose a novel EMS formulation that addresses the limitations of [ONeill et al., 2010] described above. Our proposed algorithm also uses RL, but adopts a device centric point of view, and, as we will discuss in detail in Section 3, under reasonable assumptions, the RL problem decomposes over devices and it is sufficient to apply an RL algorithm to each individual device. Specifically, the algorithm addresses these issues: 1. Our EMS formulation does not require a pre-specified disutility function modeling the consumer's dissatisfaction on job rescheduling. Instead, under this formulation, the EMS is able to learn the consumer's dissatisfaction by sampling his evaluations on completed/canceled jobs. In other words, our new RL formulation has eliminated the impractical assumption in [ONeill et al., 2010] that consumers' dissatisfactions with delay can be captured by known disutility functions.
2. Our approach allows both user-initiated jobs and EMS-initiated jobs. The EMS-initiated jobs use a probing/feedback mechanism to find the best way to anticipate future energy usage.
3. Our EMS algorithm also enables more flexible user-initiated jobs, specifically • A consumer request's target time can be different from its request time, where the request time is the time when the EMS receives this consumer request, and the target time is the time when the consumer prefers this request to be satisfied.
• Consumer requests/reservations can have different priorities, whereas in [ONeill et al., 2010], all the consumer requests have the same priority.
• Energy requests can be canceled by the consumer, reflecting the behavior of real energy users.
4. The computational complexity of our approach grows linearly with the number of devices, and thus many classical RL algorithms can be applied even when there are a large number of devices.
In this paper, we also propose several new performance metrics for any RL algorithm applied to this problem. In particular, we suggest methods of measuring performance relative to the user's current pattern of behavior and relative to a prescient optimal pattern of behavior.
The remainder of this paper is organized as follows. In Section 2, we briefly describe how a practical fully-automated EMS should interact with the consumer and the grid signals. In Section 3, we pose the optimal demand response problem faced by an EMS as an infinite horizon discounted Markov decision process (MDP), and decompose this high-dimensional MDP into a collection of low-dimensional device based MDPs under appropriate assumptions. Then, in Section 4, we propose the device based RL problem and discuss several performance metrics for RL algorithms applied to this problem. In Section 5, we demonstrate the simulation results on a representative example when the classical Q-learning is applied. We conclude in Section 6.

Description of fully-automated EMS
A fully-automated EMS (henceforth referred to as EMS) is a necessary prerequisite to DR in the residential and small commercial building sectors. Furthermore, an EMS needs to learn how to make the optimal decisions for the user while interacting with them and the real-time grid signals. In this section, we describe how a fully-automated EMS should interact with the user and the grid signals.
Generally speaking, a fully-automated EMS observes the grid signals, receives requests and evaluations from the user, and schedules the jobs over the devices (Figure 1). We detail the interaction mechanisms in the remainder of this subsection.

Grid Signals
The EMS observes the grid signals through a communication network, where the "communication network" refers to the infrastructure that supplies grid signals to the EMS. Any exogenous information that is effectively delivered by the communication network and is useful for the EMS to make the scheduling decisions can be regarded as a grid signal. The most common grid signal is the real-time energy price; other grid signals might include the expected future energy prices, the real-time temperature and weather condition, and other useful exogenous information.
In this paper, we assume that (1) the only available grid signal is the real-time energy price, and (2) the energy price is exogenous in the sense that the EMS's actions will not influence it (i.e. the EMS is a price-taker ). Notice that the second assumption is reasonable since in the residential and small commercial building sectors, the market power of an individual EMS (or equivalently, of an individual consumer) is so small that the impact of its actions on energy prices is negligible. On the other hand, the first assumption is proposed mainly to simplify the exposition and does not incur loss of generality. Specifically, both the model and the algorithm proposed in this paper can be applied to the cases with more general grid signals (e.g. the case in which the grid signals are energy price and temperature), as long as the grid signals are exogenous.

User-Initiated Jobs and EMS-Initiated Jobs
A fully-automated EMS should perform the following functions: • The EMS receives requests from the consumers, and then schedules when to fulfill the received requests. We henceforth refer to this case as a user-initiated job.
• If a smart device managed by the EMS is idle (i.e. currently there is no request for that device), the EMS could speculatively power that device. We henceforth refer to this case as an EMSinitiated job. For instance, in a small commercial building, the EMS might speculatively turn on the building's air conditioning in advance of the tenant's arrival to capture early morning lower energy costs or to mask the latency of cooling the building. Notice that we should not allow the EMS to do speculative jobs on all the smart devices (such as dishwashers).
We assume time is discrete t = 0, 1, · · · and that there are N smart devices managed by the EMS and numbered n = 1, 2, · · · , N . To simplify exposition, we assume that all the jobs done by device n are standardized and hence they can be completed in one time step and consume a constant energy C n , which only depends on the type of the smart device. This assumption can be readily relaxed to devices with different operating periods. We further assume that the EMS will ignore all the user requests to device n if device n currently has an uncompleted request, but the EMS allows a consumer to cancel an existing uncompleted request. Specifically, if the consumer wants to replace an existing request with a new request, he must cancel the existent request first, and then start the new request. Notice under this assumption, at each time a smart device has at most one uncompleted request.

Interaction between user and EMS
We now describe how the EMS interacts with the consumer (user) in a user-initiated job and an EMS-initiated job. Specifically, as its name suggests, a user-initiated job starts with a user sending a request to the EMS. Specifically, each consumer request is represented by a four-tuple J = (n, τ r , τ g , g), where • n denotes the requested device; • τ r is the request time and denotes when the EMS receives this request; • τ g is the target time and denotes when the user prefers this requested job to be completed; • g denotes the priority of this request, with higher priority implying the "stronger preference" of the user that they want the requested job to be completed at a time close to the target time τ g .
Notice that the target time τ g is not necessarily equal to the request time τ r ; instead, the user might request to use a device in a later time (i.e. τ g ≥ τ r ). On the other hand, for a request J = (n, τ r , τ g , g), it is unreasonable to assume that τ g − τ r , the difference between the target time and the request time, can be arbitrarily large. Thus, in this paper, we assume that (1) for any request J = (n, τ r , τ g , g), its target time τ g must satisfy τ r ≤ τ g ≤ τ r + W n , and (2) if the request J = (n, τ r , τ g , g) is not fulfilled by time τ g + W n , then it will be canceled by the user, where W n is a known time window and only depends on the type of device. We also assume that an unsatisfied consumer request can be canceled by the user. Furthermore, we assume that when a consumer request is completed or canceled, the user will send an evaluation on the completed/canceled request to the EMS. As we will see later, the EMS can use such evaluations to learn the user's dissatisfaction on the rescheduling of the user-initiated jobs.
On the other hand, an EMS-initiated job is started by the EMS, without receiving a request from the user. The only interaction between the EMS and the user for such jobs is that once an EMS-initiated job is completed, the user will send an evaluation on it to the EMS. As is in the user-initiated jobs, the EMS also exploits such evaluations to learn user's dissatisfaction with the EMS-initiated jobs.
In summary, the interaction between user and EMS is as follows: for user-initiated jobs, the possible interactions include (1) the user sends requests to the EMS, (2) the user can choose to cancel the unsatisfied requests and (3) the user evaluates the completed/canceled requests. On the other hand, for EMS-initiated jobs, the only interaction between user and EMS is that the user evaluates the completed EMS-initiated jobs.
To complete the description of the user-EMS interaction, we need to specify the "user-EMS interaction timeline" in a single time period (i.e. whether the EMS receives the user requests/cancellations/evaluations before or after it schedules jobs in that time period). Without loss of generality, in this paper, we consider the user-EMS interaction timeline illustrated in Figure 2.

Device Based DR Model
This section proceeds as follows. We first motivate and define the dissatisfaction function and the instantaneous cost function for a rational consumer in Subsection 3.1 and 3.2, respectively. Explicit dissatisfaction functions are not required in practice, but in this section we assume they are known to facilitate easy exposition. Then, Subsection 3.3 formulates the optimal demand response problem as a collection of device-based MDPs under suitable assumptions.

Dissatisfaction Function and Rational Consumers
To formalize the notion of optimal demand response, in this subsection, we define the dissatisfaction function for a consumer (user) that captures their preferences (dissatisfaction) over job rescheduling. We also motivate and propose a specific class of functional forms for the dissatisfaction functions of the rational consumers. Let us start by defining some useful notation. Specifically, for each time t, we define the sets of smart devices D(t), C(t) ⊆ {1, 2, · · · , N } as D(t) = {devices that do a job at time t} C(t) = {devices for which an unsatisfied request is canceled at time t} .
Note that D(t) C(t) = ∅, since if device n does a job in time period t, then there is no unsatisfied request for device n at the end of time period t (recall that at any time, device n has at most one unsatisfied request, and see Figure 2 for the timeline of time period t). Furthermore, we use J (t) to denote the set of unsatisfied requests right after the requests in time period t have been received. Since at any time device n has at most one unsatisfied request, thus, if J (t) contains one unsatisfied request for device n, then we use J(t, n) to denote this particular request; otherwise, we set J(t, n) = NULL. Notice that H t = {(D(s), C(s), J (s)) , ∀0 ≤ s ≤ t} completely specifies the "history" of device operations, consumer requests/cancellations and the EMS decisions until the end of time period t.
Generally speaking, the user's dissatisfaction on rescheduling at time t should be a function of H t , and we denote this function as (1) Obviously, directly working withŪ (t) [H t ] defined in Eqn(1) will result in a computationally intractable problem. To overcome this challenge, in the remainder of this subsection, we make some assumptions on the functional form ofŪ (t) [H t ]. All such assumptions are motivated by observations of the preferences and behaviors of the rational consumers. Generally speaking, we think a rational consumer's preferences and behaviors should have the following characteristics: 1. A rational consumer prefers low electricity price to high electricity price.
2. For a consumer request sent to the EMS, a rational consumer prefers that job is completed at a time close to the target time, and the higher the request's priority is, the "stronger" this preference is.
3. For an EMS-initiated job, a rational consumer will be "happy" if the EMS does this job at a "right" time, and will be "unhappy" if it does this job at a "wrong" time.
4. When a rational consumer decides to cancel an unsatisfied consumer request, he is usually "unhappy" if the target time has already passed.

5.
A rational consumer generally discounts future costs and benefits. 6. A rational consumer's preference over job rescheduling changes slowly over time and is reflected in his evaluations on completed/canceled jobs. 7. A rational consumer's preference over job rescheduling on smart devices is weak compared to his preferences in other aspects of life.
We now motivate and propose a specific class of functional forms for the dissatisfaction function U (t) [H t ] of the rational consumers. To formalize the idea, we define the "history" for device n at time t as H where 1(·) is the indicator function and J(s, n) is defined above. First, we make the following simplifying assumption: 2 Assumption 1 For any t ≥ 0, the dissatisfaction functionŪ (t) is additive over the devices, that is whereŪ (t,n) captures the consumer's dissatisfaction at time t for device n and H (n) t is the "history" for device n by time t.
Furthermore, since a rational consumer's preference over job rescheduling is weak compared to his preferences in other aspects of life, and changes slowly over time, we assume that • If there is no job completed/cancelled at time t on device n, we assume thatŪ (t,n) • If there is a job completed/cancelled at time t on device n, we assume thatŪ (t,n) (H (n) t ) only depends on the job completed/canceled. That is,Ū (t,n) (·) is time-invariant and does not depend on the previously completed/canceled jobs.
Finally, based on the assumptions above and the characteristics (2)-(4) of a rational consumer's preferences over job rescheduling, we assume the dissatisfaction functionŪ (t,n) (H (n) t ) takes the following forms: • If device n satisfies consumer request J(t, n) = (n, τ r , τ g , g) at time t, we assumē where the subscript "r" denotes that it is the dissatisfaction incurred when a request is satisfied, and g is the priority of the request. Note t − τ g captures not only the distance between the current time t and the request's target time τ g , but also whether or not the target time has passed. For rational consumers,Ũ (n) r should be small when t − τ g is close to 0 and increases as t − τ g deviates from 0; furthermore, the higher the priority g, the higher this increase rate will be.
• Similarly, if the request J(t, n) = (n, τ r , τ g , g) is cancelled by the consumer at time t, we assumeŪ where the subscript "c" denotes that it is the dissatisfaction incurred when a request is cancelled. In practice,Ũ should be very small if t < τ g , and it will increase with t when t ≥ τ g ; furthermore, the higher the priority g, the higher this increase rate will be.
• If EMS initiates a job on device n at time t, we assume that where the subscript "e" denotes that it is the dissatisfaction incurred when an EMS-initiated job is done, and τ p − 1 is the time when the previous job on device n (either user-initiated or EMS-initiated) is completed or cancelled. In practice,Ũ (n) e should decrease as t−τ p increases; the largeŨ (n) e for small t − τ p prevents too frequent EMS-initiated jobs.
• Otherwise, we assume thatŪ Note that the dissatisfaction function class described in Equations (3-6) is still quite general, and it is very challenging to proceed to derive the specific functional forms ofŨ As we will see in Section 4, there is no actual need to estimateŨ based on the consumer's evaluations on completed/canceled jobs.

Instantaneous Cost Function
We assume the instantaneous cost function of the consumer at time t has the following form: where P t is the electricity price at time t andŪ is a dissatisfaction function capturing the consumer's dissatisfaction on job rescheduling at time t. Specifically, notice that n∈D(t) C n is the total electricity energy consumed at time t, and hence P t n∈D(t) C n is the electricity bill the consumer pays at time t. We assume the consumer's dissatisfaction on rescheduling at time t depends on the "rescheduling history" H t and γ > 0 represents the tradeoff between the electricity bill paid and the consumer's dissatisfaction on rescheduling.
Note that from the EMS's perspective, both the electricity price and the consumer behavior are exogenous and stochastic; thus, in this paper, we assume that EMS aims to minimize the expected infinite-horizon discounted cost: where 0 < α < 1 is the discrete-time discount and captures the assumption that a rational consumer generally discounts future costs and benefits. Notice that in this problem formulation, the state at time t is (P t , H t−1 , J (t)), and the action is D(t) (i.e. the EMS chooses which devices to power on).
Under Assumption 1, the dissatisfaction function is decomposable and the infinite-horizon discounted cost function can be written as

Device Based MDP Model
In this subsection, we first propose a dynamic model for the energy price P t . Then, we motivate an assumption on user behavior (Assumption 3), and show that under the proposed assumptions, the EMS's decision-making (job scheduling) problem is decomposed over devices. Finally, we formulate the job scheduling problem on each device as a Markov Decision Process (MDP), which we henceforth refer to as the device based MDP model. Let us start by proposing a dynamic model for the energy price P t . As discussed in Section 2, P t is exogenous in the sense that the EMS's actions will not influence it. Furthermore, recent literature (e.g. [ONeill et al., 2010]) shows that P t can be modeled as a Markov process. Thus, throughout this paper, we make the following assumption: Assumption 2 Energy price P t follows an exogenous finite-state ergodic Markov chain.
We use P to denote the set of states of this Markov chain, and use |P| to denote the number of states.
In this paper, we assume that the user is rational and the user's dissatisfaction function has the functional form specified by Eqn(3-6). Thus, to complete the description of the user behavior, we only need to model when the user sends requests/cancellations to the EMS. Similarly as P t , we model the consumer requests/cancellations as stochastic processes and make the following assumption on them throughout this paper: Assumption 3 (A) The consumer request/cancellation processes are statistically independent of the energy price process P t ; and (B) consumer requests/cancellations to different devices are statistically independent.
Assumption 3 is a key assumption in this paper. Thus, we briefly motivate it before proceeding: first, we claim that Assumption 3(A) is reasonable since • On one hand, as we have discussed in Section 2, in the residential and small building sector, the market power of an individual consumer is so small that the impact of their behavior on P t is negligible.
• On the other hand, as we have discussed in Section 1, due to "decision fatigue", most rational consumers are not incentivized to reference current and expected future energy prices before sending requests/cancellations to the EMS. Thus, for such consumers, their requests/cancellations are independent of current and expected future energy prices.
Consequently, it is reasonable to assume Assumption 3(A). We now briefly motivate Assumption 3(B). One observation about devices is that they can be classified into categories such that for most consumers, their requests to devices in different categories are weakly dependent. For instance, in a residential household, we can classify the airconditioner, electric vehicle, laundry machine and dryer into three categories: category 1 includes the air-conditioner; category 2 includes the laundry machine and dryer; and category 3 includes the electric vehicle. Under this classification, it is observed that for most residential consumers, the statistical dependence between their requests to devices in different categories are weak. Thus, it is reasonable to assume that consumer requests/cancellations to different device categories are statistically independent. To simplify, we assume each category has only one device and hence propose Assumption 3(B). Of course, a category might have multiple devices (e.g. laundry machine and dryer), and usually the consumer requests to devices in the same category are statistically dependent. We discuss how to extend the results of this paper to that scenario in Section 6.
Recall that the EMS's objective is to find an optimal scheduling policy to minimize (8), which decomposes over devices under Assumption 1. Assumption 3 states that the consumer requests/cancellations to different devices are statistically independent, thus, we have the following proposition: Proposition 1 Under Assumptions 1 and 3, the EMS's decision-making problem is decomposed over devices.
In the remainder of this paper, we focus on deriving the optimal scheduling policy for a single device and drop the subscript n to simplify the exposition. For example, we will use W instead of W n to denote the time window and represent a request as J = (τ r , τ g , g). We also use the term "smart device" and "EMS" interchangably henceforth, since due to the decomposition of the problem, one can think each smart device has its own EMS.
We further assume that the timeline for a smart device can be divided into "episodes". Specifically, we assume that whenever the smart device completes a job (either initiated by the user or by the EMS) or the current unsatisfied request is canceled by the user, the current episode terminates. In the next time step, the smart device "regenerates" its state according to a fixed distribution π 0 and a new episode starts. The notion of episode is illustrated in Figure 3.

Start of Episode k
A Job is Done Or Cancelled at 8me t, Episode k Ends State Regenera8on at 8me t+1 Start of Episode k+1 8me Figure 3: Illustration of the notion of episode We now propose an MDP model for a single smart device (the device based MDP model). The state of the MDP at time t is x t = [P t , s t , g t ] T ∈ S, where P t is the exogenous electricity price at time t, s t is the elapsed time at time t, g t is the priority of request at time t and S is the state space. Specifically, we define where τ p is the start time of the current episode and τ g is the target time of the received request. Furthermore, we use g t = 0 to denote that no request has yet been received in the current episode; once a request is received in the current episode, we assume its priority g t ∈ {1, 2, · · · , g max }.
Since the electricity price is exogenous, we can partition the state x t = [P t , s t , g t ] T as the "price portion" P t and "device portion" [s t , g t ] T . The "device portion" of the MDP state transition model is summarized in Figure 4; notice that there are (2W + 1)g max +Ŵ + 1 "device portion" states. Recall that we use P to denote the set of states of the price Markov chain, so the price Markov chain has |P| states, and the cardinality of the state space for the device based MDP is |S| = |P| (2W + 1)g max +Ŵ + 1 , which is affine in |P|, W ,Ŵ and g max .
Note that the action space at each state x ∈ S is A = {off, on}, where action "on" means the smart device completes a job 3 at the current time and "off" means the smart device does nothing at the current time. We use Φ (x t , a t , x t+1 ) to denote the instantaneous cost at state-action-state triple (x t , a t , x t+1 ).
Based on the above discussion, the device based MDP model is detailed below: • P t follows an exogenous Markov Chain with |P| states. The transition probability from P t to P t+1 is denoted as Pr(P t+1 |P t ).
2. On the other hand, if action "on" is selected, then the smart device completes an EMSinitiated job at time t. Thus, the current cost is Φ (x t , a t , x t+1 ) = P t C + γŨ e (s t ), whereŨ e (s t ) is defined in (5) and C is the constant energy consumed by a standardized job. Then the current episode terminates and the smart device regenerates the "device portion" state based on distribution π 0 .
Note that the transition probability p st,t+1−τg,g and the dissatisfactionŨ e (s t ) depend on s t . To ensure the state space is finite, we assume p st,t+1−τg,g = pŴ ,t+1−τg,g andŨ e (s t ) =Ũ e (Ŵ ) for any s t ≥Ŵ . 4 • If the smart device has already received a consumer request in the current episode but has 4 That is, when st ≥Ŵ and action "off" is selected, with probability 1 − t+1+W τg =t+1 gmax g=1 pŴ ,t+1−τg ,g , the smart device will stay at the same state.
not satisfied this request, recall we set s t = t − τ g , where τ g is the target time of this request. Notice that: 1. If action "off" is selected, then with probability 1−p st,gt , the user will cancel this request at the end of time period t. In this case, the current episode terminates and the smart device regenerates the "device portion" state based on distribution π 0 at time t + 1. The cost associated with this transition is Φ (x t , a t , x t+1 ) = γŨ c (s t , g t ), whereŨ c is defined in (4). On the other hand, with probabilityp st,gt , the "device portion" state transits to [s t+1 = s t + 1, g t+1 = g t ] T at time t + 1 and the cost associated with this transition is Φ (x t , a t , x t+1 ) = 0. Notice that we assumep st,gt = 0 if s t = W .
2. If action "on" is selected, the current cost is Φ (x t , a t , x t+1 ) = P t C + γŨ r (s t , g t ), wherẽ U r (s t , g t ) is defined in (3) and C is the constant energy consumed by a standardized job. Then the current episode terminates and the smart device regenerates the "device portion" state based on distribution π 0 at time t + 1.
Note that if the transition model of the device based MDP and the dissatisfaction function of the consumer are known, the device based MDP can be solved by dynamic programming (DP). Following ideas in classical DP, it is straightforward to derive the Bellman equation (see Appendix A) from which we can compute the optimal Q-function Q * . Specifically, many DP algorithms, such as value iteration and policy iteration, can be used to compute Q * (see [Bertsekas, 2005]). We observe that for many DP algorithms, computing Q * is tractable since the cardinalities of the state space S and action space A in a device based MDP are usually small. Once Q * is available, one optimal policy µ * is µ * (x t ) ∈ argmin a∈A Q * (x t , a).

Reinforcement Learning Formulation
However, as we discussed in Section 1, in most practical cases, the transition probabilities and the dissatisfaction function of the user are initially unknown. Thus, the EMS must learn how to make optimal decisions for the user based on the incrementally gathered data from the user and the realtime energy price. Reinforcement learning (RL) is a collection of techniques for a decision-maker to learn how to make optimal decisions while interacting with an unknown "environment" [Sutton and Barto, 1998]. RL tries to strike a balance between learning (exploration) and optimization (exploitation), and has been extensively used in many other fields, such as artificial intelligence and robotics [Coates et al., 2010]. As has been discussed in [ONeill et al., 2010], it is natural to use RL to solve EMS's learning problem since EMS needs to learn to make decisions while interacting with the user and the real-time energy price. As is shown in Figure 5, under the RL formulation of the optimal DR problem, the agent is the EMS, and the environment includes both the energy price and consumer behavior. We refer to this RL problem as the device based RL problem.
As in the RL literature, we assume the EMS (decision-maker) initially knows the state space S and the action space A = {off, on}. Furthermore, we also assume it knows the discrete-time discount α, and the price-rescheduling trade-off parameter γ. Note that the second assumption is reasonable since before the user starts to use the smart device, they can manually set up an α reflecting their discount on future costs, as well as a γ indicating their tradeoff between the electricity bill and rescheduling. With experience, the user can also tune these parameters.
However, as is discussed above, in theory the EMS (the decision-maker) needs to learn the transition model and the dissatisfaction function of the user based on its experience. Obviously, We now discuss how the EMS learns the user's dissatisfaction function. Note that under our proposed device based MDP model, the user's dissatisfaction function is non-zero only when a job is completed or canceled. Furthermore, notice that as has been discussed in Section 2, once a job is completed/canceled, the EMS will receive an evaluation from the user. In the remainder of this paper, we make the following assumption: Assumption 4 The user's dissatisfaction on the rescheduling of a completed/canceled job is equal to their evaluation on this job. 5 We now briefly motivate Assumption 4: for a rational user, their evaluation on a completed/canceled job mainly reflects their dissatisfaction on this job, and this dissatisfaction is either due to the (high) energy price or the (undesirable) rescheduling of the job. As we have discussed in Section 1, due to "decision fatigue", most rational users will not reference the current energy price or any expected future energy prices before they send their evaluations to the EMS. Thus, their evaluations will mainly reflect their dissatisfactions on job rescheduling. Thus, it is reasonable to assume Assumption 4. In summary, in our proposed device based RL problem, the EMS initially knows the state space S, the action space A, the discount α, the trade-off parameter γ and the per-job energy consumption C; but it does not know the state transition model or the user's dissatisfaction function. It observes the state transitions and the user's evaluations (which are equal to the user's dissatisfactions on rescheduling under Assumption 4) as it interacts with the user and the real-time energy price. At each time step, it aims to make good decisions based on its initial information, past observations and current state.

Baseline and Demand Response Potential
In order to justify a RL algorithm achieves satisfactory performance, we need to compare its experimental performance with respect to a reasonable baseline. In this subsection, we propose a reasonable baseline and define the notion of the demand response (DR) potential.
Let's start by defining some useful notation: we use µ : S × A → [0, 1] to denote a (randomized and stationary) policy of a device based MDP. Specifically, under (randomized) policy µ, at any state x = [P, s, g] T ∈ S, action a ∈ A is chosen with probability µ(x, a). As is classical in DP and RL, we use Q µ to denote the Q-function of the device based MDP under policy µ (see [Sutton and Barto, 1998]). Note that under Assumption 2, the energy price P t follows an exogenous ergodic Markov chain; thus, we use π P to denote the unique stationary distribution of this price Markov chain. Moreover, recall that once an episode terminates, the "device portion" state is regenerated according to distribution π 0 . Recall that state x = [P, s, g] T , thus, we use x ∼ π P × π 0 to denote P ∼ π P , [s, g] T ∼ π 0 , and P and [s, g] T are statistically independent. We define the performance of a policy µ as follows: Since this paper focuses on how demand response (DR) can potentially reduce a user's (expected infinite-horizon discounted) cost, we choose the baseline policy as the one without job rescheduling and denote it as µ base . Specifically, under µ base , the EMS never self-initiates a job, and all the jobs initiated by the user are scheduled to be completed at their target times. We are interested in how much a proposed RL algorithm can reduce the user's cost with respect to V µ base . Recall that we use µ * to denote the optimal policy. We define the demand response (DR) potential as By definition, DR potential is the maximum expected cost reduction that can be achieved by DR.
Obviously, in the case when the transition model and the dissatisfaction function are known, µ * can be derived beforehand and hence DRP is achieved. However, in the practical cases when the EMS needs to learn µ * through some RL algorithm, DRP is generally not achievable. As we will see, performance loss with respect to DRP is one performance metric for RL algorithms. We define the relative DR potential (RDRP) as Of course, DRP and RDRP depend on the problem instance. We are particularly interested in how DRP and RDRP vary with γ, since γ specifies the consumer's tradeoff between job rescheduling and the electricity bill paid. To simplify the expositions of the result, we make the following assumption in the remainder of the paper: Assumption 5 (A) Energy price is always strictly positive; (B) the user's dissatisfaction function satisfies Eqn(3-6) and is always non-negative; (C) if a user's request is satisfied at its target time, the user's dissatisfaction is 0; and (D) if the user cancels their request before the target time, their dissatisfaction is 0.
Note that Assumption 5(C) and 5(D) are reasonable since for a rational user, it is proper to assume their dissatisfaction is minimal if their request is satisfied at the target time, or canceled by them before the target time. Then Assumption 5(B) can be achieved by shifting the dissatisfaction function by a constant. Assumption 5(A) follows from the daily observation. Under Assumption 5, we have the following result: Theorem 1 Under Assumption 5, we have that: 1. V µ base does not depend on γ.
3. DRP and RDRP are non-increasing functions of γ.
Please refer to Appendix B for the proof of Theorem 1.

Performance Metrics
In this subsection, we propose several performance metrics for a RL algorithm applied to our proposed device based RL problem. We start by defining some notation: for any t = 0, 1, · · · , usẽ µ t to denote the policy under which the RL algorithm chooses the action a t at the beginning of time period t. We define the performance of the RL algorithm as note that the expectation is not only taken with respect to the initial state (similarly as Eqn (9), we assume x 0 = [P 0 , s 0 , g 0 ] T ∼ π P × π 0 in Eqn (12)), but also with respect to the subsequent stochastic transitions, noisy evaluations and possible randomizations in the RL algorithm. Note that by definition, we have V µ * ≤Ṽ . The first performance metric of an RL algorithm is its relative improvement (RI) with respect to the baseline, which is defined as RI captures the normalized expected cost reduction the user will benefit from an RL algorithm. Note that since V µ * ≤Ṽ , we have RI ≤ RDRP. That is, the relative DR potential is an upper bound on the relative improvement. The second performance metric of an RL algorithm is its relative realized DR potential (RRDRP), which is defined as if RDRP > 0. Intuitively, RRDRP captures how much DR potential is realized by an RL algorithm. Since V µ * ≤Ṽ , we have RRDRP ≤ 1. We briefly comment on RI and RRDRP before proceeding. First, notice that both RI and RRDRP can be negative, since there is no guarantee thatṼ ≤ V µ base . Specifically, under Assumption 5, it is likely thatṼ > V µ base when γ is sufficiently large. This is because V µ base ↓ V µ * as γ → ∞, and whatever γ is, an RL algorithm is likely to incur a non-trivial performance loss before it learns an optimal policy. Second, we observe that RRDRP also serves as an indicator on whether or not it is worthy to explicitly model the user behavior/dissatisfaction and the energy price. Specifically, if DRP is large but RRDRP is small for many widely used RL algorithms, then it might be worthy to explicitly model the user behavior/dissatisfaction and the energy price, as long as the cost of such modeling is smaller thanṼ − V µ * .
We also note that it is important for our proposed RL algorithm to achieve satisfactory performance quickly, since otherwise the consumer will not be incentivized to use it. The third performance metric focuses on this aspect. Specifically, ∀j = 0, 1, · · · , we use t j to denote the end time of episode j. 6 We define Thus, V µ base (j) is the user's expected total discounted cost in the first j + 1 episodes (from episode 0 to episode j) under the baseline policy. Similarly, we definẽ whereμ t is the policy under which the RL algorithm chooses the action a t at the beginning of time period t. Similarly,Ṽ (j) is the user's expected total discounted cost in the first j + 1 episodes under the RL algorithm.
We define the third performance metric, the baseline crossing time, as Note that BCT is measured in the number of episodes instead of the number of time periods. This is because measuring time in episodes is more meaningful in our problem: each episode corresponds to one usage of the device, and hence the number of episodes corresponds to how many times the consumer has used the device. Thus, measuring time in episodes avoids the problem that the consumer might sometimes use the device more frequently, while at other times use it less frequently.

Simulation
In this section, we first briefly review the classical Q-learning algorithm in Subsection 5.1. Then we discuss a representative simulation example in Subsection 5.2. Finally, the simulation results are demonstrated in Subsection 5.3.

The Q-Learning Algorithm
As we have discussed in Section 4, many RL algorithms can be applied to our proposed device based RL problem. In this subsection, we implement one of the most popular and classical RL algorithms, known as Q-learning [Watkins, 1989]. Q-learning is an off-policy learning algorithm; that is, it allows the learning agent to follow an exploratory policy while learning about an optimal policy. Another desirable features of Q-learning is that it is online, incremental and is easy to implement on real-time data. Q-learning works based on temporal-difference learning [Sutton and Barto, 1998]. At each time-step t the learning algorithm receives an input data in the form of (x t , a t , Φ t , x t+1 ), where Φ t def = Φ (x t , a t , x t+1 ) is the observed instantaneous cost after taking action a t from state x t and arriving at state x t+1 . Then the Q-learning algorithm updates the action-value function Q t (x t , a t ) according to and Q t+1 (x, a) := Q t (x, a) if (x, a) = (x t , a t ). Note Q t ∈ |S||A| is the state-action value function (Q-function) estimate in time period t, and β t > 0 denotes step-size in time period t. If the step-size sequence satisfies +∞ t=0 β t = +∞ and +∞ t=0 β 2 t < +∞, then Q-learning is guaranteed to converge to the optimal solution if all states are visited infinitely often (see [Sutton and Barto, 1998]).
To complete the description of a Q-learning algorithm, we also need to specify a behavioral policy µ b under which the algorithm chooses actions. The choice of µ b will affect data and thus would help the algorithm to learn an optimal policy faster. One main ingredient of µ b is that is it has to be exploratory policy during the learning process. One of standard, but crude, suggestions for how to select µ b is as follows: for a small 0 < < 1, with probability (henceforth referred to as the "exploration probability"), the algorithm chooses action a t from state x t according to a randomized policy, and with probability 1 − , the algorithm chooses a t ∈ argmin a∈A Q t (x t , a), where Q t refers to the state-action value function estimate at time t. Here, we consider a randomized policy in the form of Boltzmann exploration where η > 0 is a tuning parameter and is referred to as the "temperature" of the Boltzmann exploration. The Q-learning algorithm that we implement in this paper is illustrated in Algorithm 1.
Algorithm 1 The Q-Learning Algorithm 1: Initialize Q 0 arbitrarily 2: Repeat for each episode j: 3: Choose a small constant step-size β j > 0 for each episode 4: for each time period t in episode j do

5:
Take action a t at state x t according to the behavioral policy µ b

6:
Observe the instantaneous cost Φ t and new state x t+1

7:
Compute the TD error

Simulation Setup
In this subsection, we propose a representative example to which we apply the Q-learning algorithm detailed in Algorithm 1. Specifically, in this example, we assume that the exogenous price Markov chain has state space P = {10, 12, 15, 20}, and the consumer requests have two different priorities, "high" and "normal". We set the time windows W = 4 andŴ = 5, the discrete-time discount α = 0.9995 and the per job energy consumption C = 1. Thus, there are |S| = 96 states in this example. The dissatisfaction functionsŨ r ,Ũ c andŨ e are illustrated in Figure 6(a), 6(b) and 6(c). Notice that these dissatisfaction functions satisfy the characteristics of the rational consumer preferences discussed in Subsection 3.1, as well as Assumption 5. As to the transition model, we assume that if the smart device has not received a consumer request in the current episode, then under action "off", it will receive a consumer request in the next time step with probability p st . Notice that p st is chosen to be an increasing function of the elapsed time s t (see Figure 6(d)). We further notice that there are (W + 1)g max = 10 types of consumer requests (with different target times and priorities), for simplicity, we assume these 10 types of requests are equally likely. Furthermore, if the smart device has received a consumer request in the current episode, then under action "off", the unsatisfied request will be canceled with probabilitŷ p st . In this example, we assume the "cancellation probability"p only depends on the elapsed time s t and is independent of the priority g t . We choosep st as an increasing function of s t (see Figure  6(e)). Finally, we assume that when the smart device regenerates its state, with probability 1, the regenerated "device portion" state is [s t+1 = 0, g t+1 = 0] T .
We plot the RDRP of this example as a function of the trade-off parameter γ (see Figure 7). Since this example satisfies Assumption 5, thus, as Theorem 1 indicates, the RDRP is a non-increasing function of γ. Furthermore, when γ = 0, RDRP = 1, and RDRP → 0 as γ → ∞.

Performance
In this subsection, we present the simulation results of the Q-learning algorithm on the representative example detailed in Subsection 5.2. We start by describing how we implement the Q-learning algorithm. We choose the "exploration probability" = 0.05 and the "temperature" of the softmin policy η = 0.1. For episode j, we choose the step-size β j = 10 20+j . We initialize the Q-learning algorithm by setting Q 0 = 0.
For each trade-off parameter γ = 0, 0.1, 0.2, · · · , we run the Q-learning algorithm for 2 1−α = 4, 000 episodes, and repeat the simulation for 200 times. Then we approximateṼ andṼ (j), ∀j = 0, 1, · · · by their corresponding sample means, i.e., by averaging the simulation results in these 200 simulations. Note that both V µ base and V µ base (j), ∀j = 0, 1, · · · , can be analytically derived based on the Bellman equation under policy µ base . Thus, RI, RRDRP and BCT can be (approximately) computed based on V µ base , V µ base (j) and the sample means ofṼ andṼ (j). The simulation results are summarized in Figure 8-10, where we plot the RI, RRDRP and BCT as functions of the trade-off parameter γ. Note that we only plot the simulation results for 0 ≤ γ ≤ 4.3, since for γ ≥ 4.4, we haveṼ > V µ base . Consequently, for γ ≥ 4.4, RI and RRDRP are negative, and BCT = ∞.
We conclude this section by briefly discussing about the simulation results. Notice that Figures  8-10 show that in this representative example, RI and RRDRP are decreasing functions of γ, while BCT is an increasing function of γ. This implies that with all the other parameters fixed, the more the user prefers "no rescheduling" to "low energy price", the harder for the Q-learning algorithm to (1) achieve a significant improvement compared with the baseline, (2) realize a large fraction of the DR potential, and (3) quickly outperform the baseline policy.
We also observe that BCT = 0 for γ ≤ 2.1. This implies that for such γ's, by initializing Q 0 = 0, the Q-learning algorithm outperforms the baseline policy from episode 0. Furthermore, as γ ↑ 4.4, V ↑ V µ base and hence BCT → ∞.

Conclusion
We have motivated and proposed a novel EMS formulation for the DR problem in the residential and small commercial building sectors, which we refer to as the device based RL problem. Specifically, we have shown that under appropriate assumptions, our proposed EMS formulation does not require a pre-specified disutility function modeling the consumer's dissatisfaction on job rescheduling, and has a computational complexity that grows linearly with the number of devices. Our new EMS formulation also enables the EMS to self-initiate jobs and allows the users to the initiate more flexible requests.
We have also motivated and proposed several performance metrics for RL algorithms applied to the device based RL problem, and demonstrated the simulation results when the classical Qlearning algorithm is applied to a representative example. Simulation results suggest that for a broad range of trade-off parameter γ, the Q-learning algorithm outperforms the baseline policy without any job rescheduling.
Finally, it is worth pointing out that many assumptions on the device based MDP model discussed in this paper are proposed to simplify the exposition, and we can easily relax some of these assumptions to obtain a more general device based MDP model. In Appendix C, we discuss two relaxations that are of particular interest: stacking request and dependent devices.
From the classical DP theory, the optimal Q-function Q * is the unique solution of the above-derived Bellman equation. Furthermore, many DP algorithms, such as value iteration and policy iteration, can be used to compute Q * . We observe that for many DP algorithms, computing Q * is tractable since the cardinalities of the state space S and action space A in a device based MDP are usually small. Once Q * is available, one optimal policy µ * is µ * (x t ) ∈ argmin a∈A Q * (x t , a).

Appendix B Proof for Theorem 1
Proof for Theorem 1: Note that ∀µ : S × A → [0, 1], V µ can be expressed as where A µ is the expected infinite-horizon discounted electricity bill, and B µ is the expected infinitehorizon discounted user dissatisfaction on rescheduling. Furthermore, neither A µ nor B µ depends on γ.
First, we prove that V µ base does not depend on γ. Note that under policy µ base , the EMS will never initiate a job; furthermore, any job initiated by the user is either completed at its target time or canceled by the user before its target time. Thus, under Assumption 5, we have B µ base = 0. So we have V µ base = A µ base , which does not depend on γ.
Second, we prove that there exists a γ * > 0 s.t. µ base is an optimal policy when γ > γ * . Note that under Assumption 5, µ base , which is a deterministic policy, minimizes B µ , since B µ ≥ 0 for any µ and B µ base = 0. Note that there are finite deterministic policies, and we use ∆B to denote the "second best" B µ under deterministic policies ∆B = min deterministic µ:Bµ>0 B µ .
Finally, we prove that RDRP = 1 when γ = 0. Note when γ = 0, the EMS does not care about the user's dis-satisfaction on job rescheduling. Consider a policy µ under which • The EMS will never initiate a job.
• The EMS ignores all the jobs initiated by the user; it just waits for the user to cancel the requested job.
Obviously, when γ = 0, we have V µ = 0. Thus we have V µ * ≤ V µ = 0. On the other hand, from Assumption 5, we have V µ * ≥ 0 (since the energy price is always strictly positive and and the user's dissatisfaction function is always non-negative). Thus we have V µ * = 0 and Q.E.D.
Obviously, allowing τ g to be a vector will make the device based MDP model more complicated; however, it does not fundamentally change the problem and all the existent results still apply after proper modifications. For computational tractability, one should also upper bound the length of the target time vector.

Dependent devices
In Assumption 3, we assume that consumer requests/cancellations to different devices are statistically independent. As we have discussed after Assumption 3, it should be relaxed for some devices: specifically, devices can be classified into categories, and requests to devices in the same category (such as laundry machine and dryer) are statistically dependent.
One way to overcome this problem is to combine all the devices in the same category as a "super device". After such combinations, the requests/cancellations to different "super devices" can be assumed to be statistically independent. Obviously, allowing "super devices" will make the device based MDP model more complicated; however, it also does not fundamentally change the problem and all the existent results still apply after proper modifications.