# Online Learning Algorithms for the Real-Time Set-Point Tracking Problem
## 2 Mathematical Framework of Online Decision Making  
The online decision-making framework can be simply explained with a brief example. Imagine a merchant having a small section in a flea market. He owns a few items that need to be sold by the end of the day. Customers approach the rented space one by one asking about the cost of the available commodities. A price is provided by the merchant, and they decide whether to purchase anything or not. The objective here should be to maximize the profit by the end of the day. However, there are some insights about the offered prices to the customers, and they cannot be too high or low. Indeed, if proper valuations are not chosen regarding the customer behavior, the merchant may end up with either unsold goods or all sold-out with low prices leading to an unsatisfying profit. Meaning that considering uncertainty toward the future in terms of coming customers and their will to buy, there is a need to design an algorithm that learns and evolves the pricing strategy each time a new customer wants to buy a commodity. The aforementioned situation depicts an online decision-making problem that is also shown in Figure 1. Indeed, through the day, the merchant learns and evolves the decision-making to maximize the total profit. Formally and with mathematical notation an online decision-making problem is given in Figure 2.  
When online optimization is considered, decision-making is conducted in a limited number of consecutive rounds. At each round, the optimization variables are decided without relying on future information. After assigning specific values to the decision variables, the uncertain parameters are realized. Based on the new information (i.e., a loss function), the previous round's performance can be measured, and the decision for the next round can be updated accordingly. In a classical optimization setting, since only one objective function exists, the goal is to minimize this function. For instance, the utilization of iterative algorithms and their performance is measured by the convergence rate, which shows whether they could converge to the optimal point. A linear convergence is a favorable one in the context. However, in the online optimization setting, at each interval, a new function is observed. Figure 1: Online decision-making framework for flea-market merchandise [20]. Figure 2: Online optimization decision-making framework. Thus, a new performance measured is defined in this setting that is called dynamic regret, \(Reg_{T}\), which is the difference between the accumulation of instantaneous cost and the best performance at each period [23], as depicted in (1). \[Reg_{T}=\sum_{l=1}^{T}f_{l}(x_{l})-\sum_{l=1}^{T}f_{l}(x_{t}^{*}) \tag{1}\]  
Here, \(f_{t}\) is the cost function at time period \(t\), \(T\) is the final time period, \(x_{t}\) is the decision made by the online algorithm, and \(x_{t}^{*}\) is the best decision at time \(t\). An online algorithm performance is measured by regret, and a good online algorithm should achieve sub-linear regret meaning that the average regret would tend to zero when the number of rounds increases. Note that, if the loss function \(f\) and the decision-making set are convex, the online decision-making optimization is called online convex optimization (OCO) [24]. A well-known online algorithm is called online gradient descent and was first introduced in [25]. There are several algorithms developed based on the OGD and applied to many problems in theory and practice [26; 27]. The OGD is given in Algorithm 1. In this algorithm, the input parameters are \(x_{0}\), which are similar to other values of decision belonging to the decision-set \(\mathcal{K}\). Parameter \(\eta\) is the step-size and is assumed to be a fixed value through the whole process of decision-making. The algorithm utilizes gradient descent with the step size of \(\eta\) at each step after observing \(f(x_{t})\). However, this value is required to be in the bound defined by the decision-making set.