{'fraction_non_alphanumeric': 0.031927498638998304, 'fraction_numerical': 0.005924360329202293, 'mean_word_length': 4.6064631956912026, 'pattern_counts': {'":': 0, '<': 4, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 1, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
An online learning approach to dynamic pricing for demand response

In this paper, the problem of optimal dynamic pricing for retail electricity with an unknown demand model is considered. Under the day-ahead dynamic pricing (a.k.a. real time pricing) mechanism, a retailer obtains electricity in a twosettlement wholesale market and serves its customers in real time. Without knowledge on the aggregated demand function of its customers, the retailer aims to maximize its retail surplus by sequentially adjusting its price based on the behavior of its customers in the past. An online learning algorithm, referred to as piecewise linear stochastic approximation (PWLSA), is proposed. It is shown that PWLSA achieves the optimal rate of learning defined by the growth rate of cumulative regret. In particular, the regret of PWLSA is shown to grow logarithmically with respect to the learning horizon, and no other on-line learning algorithm can have the growth rate slower than that of PWLSA. Simulation studies are presented using traces of actual day-ahead prices, and PWLSA compares favorably under both static and dynamically changing parameters.


I. INTRODUCTION
As a key feature of a future smart grid, demand response is an effective way to improve power system operation efficiency, hedge the risk of energy supply shortage, and enhance social welfare. Based on characteristics of the interaction between a retailer and its consumers, demand response can be classified into two categories: demand responses with direct control and ones with indirect control; the former refers to programs in which the consumers enjoy lower electricity rate by allowing the retailer to shed load in case of emergency. The latter refers to approaches of influencing the consumers' consumption through dynamic pricing of electricity. In this paper, we focus on the latter.
We assume that the retailer employs a real-time pricing mechanism, referred to as day-ahead dynamic price (DADP), under which the retailer posts the hourly prices of electricity one day ahead. First proposed by Borenstein, Jaske, and Rosenfield [1] and referred to as the real-time pricing (RTP), DADP has been implemented in practice [1], [2]. A key advantage of DADP is that a customer has the short-term price certainty with which it can optimize its consumption. Qing Zhao is with School of Electrical and Computer Engineering, University of California, Davis, CA, USA, 95616. Email: qzhao@ucdavis.edu.
Part of this work was presented at the 51st Annual Allerton Conference on Communication, Control, and Computing, Oct. 2013.
We assume that the retailer obtains electricity from a commonly adopted a two-settlement wholesale market, consisting of a day-ahead market and real-time market. In the dayahead market, both the generators and retailers offer bids for the next day. Based on the submitted bids, the system operator schedules the day-ahead dispatch and clears the market with the day-ahead price. In real-time operations, the system operator adjusts the day-ahead dispatch according to the actual operation condition and sends dispatch signal to all participants to maintain the system balance. The amount of electricity deviated from the day-ahead schedule is settled according to the real-time price.
If the retailer knows how its customers respond to the retail price through their individual demand functions, it can choose the price to optimize a particular objective, e.g., the social welfare or its own profit subject to regulations. Obtaining the demand functions of its customers, however, is nontrivial because a customer is likely to consider such information private; neither the willingness of sharing nor the correctness of the shared information can be assumed.
In this work, we focus on optimal dynamic pricing under unknown demand functions. We take an online learning approach where the retailer learns the behavior of its customers by observing their response to carefully designed prices. The basic principle of online learning is to achieve a tradeoff between "exploration" and "exploitation;" the former represents the need of using sufficiently rich pricing signals to achieve learning accuracy, whereas the latter stands for the need of capturing as much reward as possible based on what has been learned.
In the classical online learning theory, the performance of a learning algorithm is measured by the notion of cumulative regret. For the pricing problem at hand, the regret is defined as the difference between the retail surplus associated with the actual aggregated demand function and the surplus achieved by an online learning algorithm. While the cumulative regret R T grows with the learning horizon T , the rate of growth, R T /T , of a well designed on-line learning algorithm typically diminishes, which implies that, for the infinite horizon problem, the profit achieved per unit time without knowing the demand function matches that when the demand function is known. Therefore, a relevant performance metric is the growth rate of regret R T vs. T .

A. Summary of results
The basic problem setting involves two players: a retailer (an electricity distributor or aggregator) who offers its customer day-ahead hourly dynamic prices and its customers with price responsive demands. We focus on the case when the customer demands are elastic and can be described by a random affine model, which arises naturally for thermal control applications.
The main result of this paper is twofold. First, under the DADP mechanism, we propose a simple online learning algorithm, referred to as piecewise linear stochastic approximation (PWLSA), that has the logarithmic rate of growth in regret, i.e. R T (T ) = Θ(log T ).
On the other hand, we show that no other on-line learning algorithm can have the rate slower than that of PWLSA. Thus PWLSA is order optimal. To achieve the optimal rate of learning, we deviate the standard on-line learning approach by first analyzing the mechanism of the two-settlement wholesale electricity market and calculate the retail surplus of the retailer as a wholesale market participant in a simple set-up. The result shows that the retailer's loss of surplus is proportional to the 2-norm deviation of the real-time consumption from the dayahead schedule.
To demonstrate the learning performance, we also conduct simulations to compare PWLSA with the Greedy Method based on the actual data. In both cases with static and dynamically changing parameters of the demand model, PWLSA outperformed the greedy method and converged fast towards the optimal price.

B. Related work
The problem of dynamic pricing for demand response assuming known demand functions has been extensively studied. See, for example, [1], [3], [2], which adopted a similar pricing scheme as considered in this paper and [4], [5], [6] for more general settings. A precursor of the work presented here is [7] where a parametric form of demand function was obtained. In [8], the tradeoff between retail profit and consumer surplus was characterized under a Stackelberg formulation with known demand functions.
The general problem of online learning for dynamic pricing has been studied extensively in multiple communities. This problem can be formulated as a multi-armed bandit (MAB) problem by treating each possible price as an arm. When the price can only take finite possible values, the problem becomes the classic MAB for which Lai and Robbins showed that the optimal regret growth rate is Θ(log T ) when the arms generate independent reward [9]. When the price takes value from an uncountable set, the dynamic pricing problem is an example of the so-called continuum-armed bandit introduced by Agrawal in [10] where the arms form a compact subset of R. An online learning policy with regret order of O(T 3/4 ) was proposed in [10] for any reward function satisfying Lipschitz continuity. Further development on the continuum-armed bandit under various assumptions of the unknown reward function can be found in [11], [12], [13]. The reason that PWLSA proposed in this paper achieves a much better regret order (Θ(log T )) than in the case of a general continuum-armed bandit is due to the specific linearly parameterized demand which leads to a specific quadratic cost/reward function. A similar message can be found in [14], [15], [16], [17], [18] where different regret orders were shown to be achievable under different classes of demand models for dynamic pricing.
The problem considered in this paper deals with linearly parameterized demand functions, thanks to the closed-form characterization of the optimized demand function for thermal dynamic load obtained in [8]. The learning approach proposed in this paper is rooted from a stochastic approximation problem originally formulated by Lai and Robbins [19], [20] where the authors considered a form of optimal control problem when the model contains unknown parameters and the cost of control is explicitly modeled. For scaler models, Lai and Robbins showed in [19], [20] that the cumulative regret (if translated from our definition) of a simple linear stochastic approximation scheme grows at the rate of O(log T ). However, it is not clear whether such growth rate is the lowest possible. Our result provides a generalization to the vector case with a lower bound for general policies. In addition, our approach also allows the consumers to have variable demand levels whereas the algorithm presented in [19], [20] only allows a single constant demand target.
Also related is the work of Bertsimas and Perakis [21] who tackled the problem as a dynamic program with incomplete state information. The authors showed in numerical simulations that considerable gain can be realized over the myopic policy where the price in the next stage is based on the least squares estimate of the model parameter. When the parameters are assumed to be random, Lobo and Boyd considered the same problem under a Bayesian setting [22] and proposed a randomized policy via a dithering mechanism. In both cases, the rate of learning is not characterized.
Machine learning techniques have been applied to pricing problems in electricity markets, although there seems to be limited literature on discovering real-time price with unknown demand functions at the retail level. While such problems can be viewed as part of the general learning problem discussed above, the nature of electricity market and electricity demand impose special constraints. When the market has multiple strategic generators, Garcia et al. proposed an online learning algorithm which converges to the Markov perfect equilibria [23]. A related learning problem of bidding strategy of a retailer in the wholesale market when the supply functions of the generators are unknown has been studied. See [24], [25], [26] where Q-learning techniques have been applied. Some other research focuses on developing learning methods for optimal demand response. See [27] for index policy by formulating the demand control as a restless bandit problem, and [28] for a reinforcement learning solution to a partially observable Markov decision process (MDP) problem.

II. STRUCTURE OF WHOLESALE ELECTRICITY MARKET
In this section, we discuss a two-settlement system stylized from the deregulated wholesale market in the United States. The market consists of a day-ahead market and a real-time market. The day-ahead market serves as a planning mechanism for participants, and its settlement is financially binding. In the presence of uncertainties, the real-time market, on the other hand, addresses mismatches between the actual generation/consumption and that planned in the day-ahead market.
In the following discussion, we only consider the presence of retailers and generators, without other financial participants, such as virtual bidders.
As a participant in the two-settlement market, a retailer faces uncertainties in the wholesale market and that from the real-time consumptions of its customers. If the quantity of consumption is large, the retailer is not a price taker. Instead, its bidding curve and real-time purchase will affect the wholesale price. Using a simplified model, we argue in this section that it is to the retailer's benefit to match the real time consumption with the day-ahead dispatched value. In particular, we motivate, by algebraic and economic arguments, that minimizing the 2-norm deviation of the realtime consumption maximizes the retail surplus. This result motivates the specific form of the cost used in the regret definition in our online learning formulation of the problem.

A. The day-ahead wholesale market
In the day-ahead market, the independent system operator (ISO) schedules energy dispatch for the next day. Each electricity generator submits a cost curve c(p) that represents the cost of serving p units of electricity, while each retailer (or Load Serving Entity (LSE)) submits a utility curve u(d) that models the benefit of getting served with d units of electricity. Usually, the day-ahead market dispatch is calculated at the hourly time scale. Therefore, both the demand schedule d and the generation schedule p are 24 dimensional vectors.
With all submitted offers and bids, the ISO solves an optimal power flow (OPF) problem to obtain the optimal dispatch under the objective of maximizing the social welfare. In its simplest form without complications of capacity constrained transmission networks and multiple participating agents, the OPF problem is of the following form, The solutions, d DA and p DA , represent the desired day-ahead dispatch of demand and generation. The day-head price is defined as the cost of serving next unit of energy. Therefore, it is the marginal cost of generating p DA , i.e., λ DA = ∂c ∂p (p DA ). The clearing of the day-ahead market is financially binding in the sense that, regardless of the actual consumption in real time, the day-ahead payment from retailer to the system operator is settled as (λ DA ) T d DA . The payment from the system operator to the generator is (λ DA ) T p DA . Since the retailer's utility of using d DA is u(d DA ), the retail surplus is

B. The real-time wholesale market
The actual consumption and generation in real time d RT and p RT , however, are nominally different from the day ahead dispatch. Consequently, the real-time price will deviate from the day-ahead price. In particular, if the cost function of generation in real-time isc(p), the real-time price is calculated as λ RT = ∂c ∂p (d RT ), which stands for the cost of serving the next unit of electricity in real time.
Different from the day-ahead settlement, the real-time settlement only applies to the difference between the dayahead schedule and the real-time consumption. This means that the payment from the retailer to the system operator is Otherwise, this quantity represents the compensation from the system operator to the retailer.
Therefore, if the real-time consumption matches the dayahead dispatch, there is no real-time payment. The total retail surplus is still S DA retail . If the actual consumption d RT is different from d DA , the retail surplus is where the first term is the utility of the retailer from delivering d RT to its consumer, and the second term is the total payment to the wholesale market. Therefore, the surplus loss due to deviation of d RT from d DA is Based on the Taylor expansion of u(d RT ), we can approximate ∆S retail as shown in the following lemma. The complete proof is included in the Appendix.
Lemma 1: Under the assumption that cost c(p) and utility u(d) are twice differentiable, where θ is a constant independent of d RT and d DA Therefore, the objective of maximizing retail surplus is equivalent to minimizing the squared deviation of the realtime demand to the day-ahead dispatch.
The result above can also be illustrated in the Price-Quantity plane as shown in Fig. 1. The demand function presents the optimal quantity of energy required from the retailer given the price. It is actually the derivative of the utility function u(d).
The area below the line is the integration, which is exactly the utility value with quantity d. Similarly, the day-ahead and real-time supply function stand for the optimal quantity of generation to the generator if the price is given. The crossing point (d DA , λ DA ) is the day-ahead equilibrium, the same as calculated from (1). Subtracting the day-ahead payment from the utility, Area I represents the day-ahead retail surplus. In the real-time market, the real-time consumption d RT deviates from d DA , and the real-time price, λ RT , is determined by the real-time supply function. Area III is the additional utility gained by consuming d RT , while the sum of area II and III is the real time payment. Therefore, Area II represents the retail surplus loss, and the loss grows in the order of ||d RT − d DA || 2 2 -the 2-norm deviation between the day-ahead scheduled consumption and the actual real-time consumption.

III. PRICE RESPONSIVE DEMAND
In this section, we characterize the behavior of the consumers in a demand response program offered by a retailer that uses dynamic price to influence consumptions of its customers. To this end, the retailer is particularly interested in parametric models of the demand function that captures the relation between price of electricity and the level of consumption.
Instead of assuming a particular model, we consider an important engineering application for HVAC units * based temperature control, since it makes up most price responsive demand [29]. We establish in this section that the optimal demand response under the day ahead dynamic pricing is has an affine parametric form.

A. Day-ahead dynamic pricing
Following the conclusion in Section II, the retailer's optimal strategy is to minimize the difference between the real-time demand and the day-ahead dispatch. In this paper, we assume that the retailer is to influence the aggregated consumption of its customers via retail pricing. Specifically, we consider a specific form of dynamic pricing, Day-Ahead Dynamic Pricing (DADP), also referred to as Real-Time Pricing (RTP) by Borenstein et al. [1].
DADP works in the following way. In the day-ahead market, the retailer offers the consumer hourly retail price π for the day ahead, according to the prediction of the wholesale market and projected demand response. In real time, knowing the entire price trajectory for the day, a consumer dynamically determines her own energy consumption. The payment from a consumer to the retailer is settled as the product of day-ahead price and real-time consumption. The retailer meets aggregated demand by purchasing electricity from the wholesale market.

B. Optimal demand respose
Given DADP posted one day ahead, the consumer optimizes her energy consumption. Here we assume a general linear dynamic model that captures the relation between the consumer utility and her consumption of electricity. This general model arises from the classical model for HVAC based temperature control where thermal storage is involved [29], [30] and is shown to be reasonably accurate for residential temperature control [31].
For consumer k, let x (k) = (x (k) 1 , ..., x (k) 24 ) and a = (a 1 , ..., a 24 ) denote the average indoor temperature and outdoor temperature in each hour, respectively. The Birdwell model of HVAC is given by  24 ) is the vector of control variable representing the total amount of electricity drawn by the HVAC unit during each hour and ξ (k) = (ξ (k) 1 , ..., ξ (k) 24 ) the process noise. System parameters α (k) (0 < α < 1) and β (k) model the insolation of the building and the efficiency of the HVAC unit in consumer k's house. Note that the above equation applies to both heating and cooling scenarios but not simultaneously. We focus herein the cooling scenario (β (k) > 0) and the results apply to heating (β (k) < 0) as well.
Using a linear combination of total cost and squared deviation of indoor temperature from desired temperature as the objective function to minimize, the consumer k's energy consumption can be modeled by the following stochastic optimization problem, 24 ) the observation noise vector, κ the weight factor and ξ i the desired temperature for hour i.
The solution of the above stochastic optimization can be obtained in closed form via direct backward induction. More significantly, it is shown in [8] that, after aggregation over all consumers, the total demand is an affine function of the retail price.
Theorem 1 ( [8]): Assume that the process noise ξ (k) and ν (k) are Gaussian distributed with zero mean for each consumer k. With the fixed retail price π, the optimal aggregated residential demand response has the following matrix form and properties, where the factor matrix A is positive definite, b and A are deterministic, depending only on the dynamic system parameters, and w is a random vector with zero mean.

A. Pricing policy and regret
As discussed in Section II, minimizing the demand side surplus loss is equivalent, approximately, to minimizing the squared deviation of real-time electricity consumption, d RT , from the day-ahead optimal dispatch, d DA .
Formally, define the t-th day's expected surplus loss as the 2-norm of the deviation of the real-time consumption from the day-ahead dispatch, i.e., L t t are the day-ahead and real-time demands for day t.
Assuming the linear demand function in Theorem 1, for the purpose of obtaining a performance upper bound, we consider the case that the parameters in (8), A and b, are known to the retailer. At day t, the optimal retail price is given by and the corresponding minimum surplus loss is only caused by the exogenous random fluctuations (such as the outdoor temperature). Specifically, the minimized expected loss is where Σ w is the covariance matrix of demand model noise w in (8). Notice that the minimized surplus loss is independent of the day-ahead dispatch d DA t . However, it is nontrivial for the retailer to obtain the exact parameters of the demand functions of its customers because a customer is likely to consider such information private. At day t, the only information available to the retailer is the record of previous electricity consumption up to t − 1 and day-ahead dispatch up to t. Formally, the retail pricing policy is defined as follows, Definition 1: The retail pricing policy µ = (µ t ) is a sequence of mappings where µ t maps the consumption history and day-ahead demand dispatch to the price vector of day t. In particular, letting π µ t be the price vector under policy µ, we have where d DA i , and d RT i are the day-ahead dispatch and real-time electricity consumption for day i.
As for a particular policy µ, the regret R µ t at day t is defined as the increase of surplus loss compared with using the optimal price, π * t , which means that Because maximizing the surplus is equivalent to minimizing the regret, we'll focus next on the increasing rate of the cumulative regret up to day T , T t=1 R µ t .

B. Lower bound on the growth rate of regret
To gain insights into the type of lower bound on the regret, we consider first a simple example when part of the parameters are known. Intuitively, the advantage of knowing partially the parameters should lead to a lower growth rate of regret.
In particular, recall the stochastic affine demand function (8) where we assume parameter A is known but b is unknown. Consider the following dynamic pricing policy,μ, given by whereπ t−1 andd t−1 are the average price and demand up to day t − 1, i.e., According to (12), straight forward calculation gives that the regret for day t is Therefore, the aggregated regret, Therefore, with the knowledge of the demand function parameter A, the policyμ achieves the aggregated regret O(log T ) for any b and any arbitrary sequence of {d DA t }. To establish the actual lower bound on the growth rate of regret, we formulate a game that, after the retailer proposes a deterministic pricing policy µ, there exists an adversary designing parameters of the demand function. The adversary is to create the worst loss to the retailer while the retailer tries to minimize the largest possible loss. In other words, we consider the following the min-max regret as the objective, The following theorem shows that in the min-max sense, the growing rate of the cumulative regret can not be lower than log T .
Theorem 2: For any pricing policy µ as defined in (11), there exist some ..) to make the cumulative regret, T t=1 R µ t , grows at least at the rate of log T . Proof: see the Appendix.

C. PWLSA: a rate optimal learning policy
In this section, we propose a policy that achieves the lower bound on the regret growth rate; it is thus optimal in the sense of having the lowest rate of growth. Referred to as piecewise linear stochastic approximation (PWLSA) policy, the proposed policy is an extension of the stochastic approximation approach of Lai and Robin [20] for scaler processes with a single desired optimal price.
If the day-ahead demand is the same for all days, stochastic approximation will use the previous average price as the nominal value and previous average demand as the feedback signal to calculate the next price, as shown below, where d DA is the constant day-ahead dispatch level, and the feedback factor γ is a positive scalar. For multiple day-ahead dispatch levels, we build adaptively a dictionary of day-ahead dispatch levels that have appeared before. Denote the dictionary at day t as D t .
we keep a separate stochastic approximation to calculate the retail price, in a feedback control fashion similar as (17).
Therefore, for different d DA t , we have a different linear function to calculate the next retail price. The policy is piecewise linear. Formally, the PWLSA policy, µ PWLSA , is defined as, Definition 2 (PWLSA): Assume for all t ∈ N + , d DA t ∈ D and D is countable.
whereπ j is an arbitrary predetermined price.
The following theorem shows that PWLSA can achieve the optimal logarithmic regret order.
Theorem 3: Assume that day-ahead dispatch d DA t 's are from a finite set, i.e., |D| < ∞. If γ ≥ 1 2λmin(A) , where λ min (A) is the minimum eigenvalue of A, then we have, Proof: see the Appendix.
Since log T is shown to be the optimal rate achievable, PWLSA is already the best in the sense of asymptotic growing rate of the regret. The conditions in the theorem are quite general. In practice, the cost functions from the generator and the utility functions from the retailer won't change often and are usually chosen from a few alternatives. Therefore, we can assume the total number of possible day-ahead dispatch levels, |D|, to be finite. On the other hand, the consumers' demand function is from real data, which can be constrained by a compact set. Therefore, the bound of the minimum eigenvalue of A is not hard to get with reasonable assumption.

A. Simulation set-up
In this section, we conducted simulations based on the actual temperature records in Hartford, CT, from July 1st, 2012 to July 30th, 2012. The day-head price was also for the same period from ISO New England. The HVAC parameters for the simulation were set as: α = 0.5, β = 1, µ = 10. The desired indoor temperature was set to be 18 • C for all hours. The size of aggregation was assumed to be 100.

B. Learning static parameters
First, we examined PWLSA's ability to identify the correct price if the parameters of the demand model remain the same. To make the comparison, we used the Greedy Method [32], [22] as a benchmark. At each day, the Greedy Method makes maximum likelihood estimate of the parameters and uses the result as the correct parameters to calculate the "optimal" price. Fig. 2 shows the average performance of PWLSA and Greedy Method over 10,000 Monte Carlo runs. In Fig. 2a, the induced cumulative regrets of the two policies are compared. We could identify the logarithmic growth of the cumulative regret under PWLSA and significant cumulative regret increase by the Greedy Method. Fig. 2b shows the absolute percentage deviation of the prices under the two polices from the optimal price. We can see that Greedy Method performed extremely bad at the very beginning due to insufficient learning. After some days, the two policies both produced prices pretty close to the optimal one.  After carefully investigating the simulated data, we found two typical scenarios as shown in Fig. 3. We used the ratio of the calculated price to the optimal price as y-axis, to show the fluctuation. In most of the cases as in Fig. 3a, the two polices gave similar performance and both converged to the optimal price fast. On the other hand, Fig. 3b shows one extreme scenario that Greedy Method run into the condition that is close to singularity, which leads to an abnormal price. Although this kind of scenarios happened rarely, it caused the wide performance gap between the Greedy Method and PWLSA.

C. Learning dynamic parameters
In the real world, the parameters of the demand model usually do not stay constant. They may follow some cycles or drifts. In this subsection, we tested the learning ability and robustness of PWLSA under dynamic unknown parameters. Besides the set of parameters above, we used 1.5A instead of A to make the alternative set of parameters. We assumed the parameters followed a Markov Chain with these two sets as states. The transition probability to the other set was assumed to be 0.25. Fig. 4 shows the average performance comparison of PWLSA and the Greedy Method under dynamic unknown demand model. We can see that PWLSA still outperformed the Greedy Method. According to Fig. 4a, the cumulative regret under PWLSA grew linearly. Intuitively, when a sequence of observation is given, a policy will produce a fixed price or a fixed probability distribution over candidate prices (for randomized policy). However, since the next optimal price is random, there always exists a fixed addition to the expected cumulative regret. Therefore, the linear order achieved by PWLSA is already the best. Fig. 4b shows that the error at the very beginning was the cause of the performance gap between PWLSA and the Greedy Method.
We also conducted the scenario analysis similar to the static parameter case as shown in Fig. 5. Each changing point stands Method under dynamic parameters for a incident that the state jumps to the other set. In Fig. 5a, we can see that the two policies had similar performance and both tracked the optimal prices well. In few extreme cases, the Greedy Method lost track on the optimal prices wildly at the beginning a few days, as shown in Fig. 5b.

VI. CONCLUSION
We present in this paper an online learning approach to the dynamic pricing of electricity of a retailer whose customers have price responsive dynamic load with unknown demand function. We exploit the linear form of the demand function for thermal dynamic load, and cast the problem of online learning as tracking day-ahead dispatch. This approach leads to a simple learning algorithm with the growth rate of cumulative regret at the order of log T , which is the best rate achievable for any dynamic pricing policies.