## 2 Bayesian Optimization
### Acquisition Functions  
So far, the GP framework within which BO operates has been defined. This of course does not constitute a complete optimization algorithm since an iterative solution update rule is yet to be defined. This is where acquisition functions come into play. The main idea is for BO to utilize the posterior GP to determine a new point of high expected value and make an additional valuable observation on that point. Subsequently, the posterior GP is conditioned against the new information, and the procedure is repeated until there is enough confidence that the algorithm has converged to the global optimum.  
BO is specifically tailored to problems where data acquisition is considered computationally intractable. Therefore, BO's goal is to find good sequential acquisition policies which converge to the optimum in as few objective function evaluations as possible. These policies inherently include the exploration-exploitation trade-off. In BO, exploration is related to looking for the next iteration estimate in areas of the solution space where the variance is high, while exploitation is related to searching areas where the current maximum is located and trying to find even better solutions.  
Given a posterior distribution based on \(n\) observed function values, the goal is to find the most valuable point \(\mathbf{x}_{n+1}\) for receiving the next objective function calculation. The proposed solution is founded on the concept of the value of information [61]. Let us assume that a hypothetical new observation at \(\mathbf{x}\) has an objective function value of \(y\). The value of making this observation is denoted by \(v(\mathbf{x},y;f(\mathbf{x}_{1:n}))\). By integrating \(y\) out of the picture by using the point predictive distribution of the posterior GP, we can define the expected value of observing \(\mathbf{x}\) (Equation (10)).  
\[v(\mathbf{x};f(\mathbf{x}_{1:n}))=\mathbb{E}_{y|\mathbf{x},f(\mathbf{x}_{1:n })}[v(\mathbf{x},y;f(\mathbf{x}_{1:n}))] \tag{10}\]  
As a result, the data acquisition policy is defined by solving the optimization problem \(\mathbf{x}_{n+1}=\arg\max_{\mathbf{x}}v(\mathbf{x};f(\mathbf{x}_{1:n}))\), i.e., the next trial point should be the one exhibiting the maximum expected value. A natural stopping criterion for such a policy is to stop when the maximum expected value of the current iteration is smaller than a threshold \(v(\mathbf{x}_{n+1};f(\mathbf{x}_{1:n}))<\epsilon\). There are many choices for the value function but the following three in particular are the most commonly utilized ones:  
1. Probability of improvement (PI) : PI (Equation (11)) picks the point that is most likely to yield an improvement over the current maximum \(\hat{y}_{n}\)[62]. \[v(\mathbf{x};f(\mathbf{x}_{1:n}))=PI(\mathbf{x})=P[f(\mathbf{x})\geq\hat{y}_ {n}]=\Phi\bigg{(}\frac{\hat{y}_{n}-m_{n}(\mathbf{x})}{\sigma_{n}}\bigg{)}\] (11) This is considered to be an exploitation-oriented policy.
2. Expected improvement (EI): EI (Equation (12)) involves computing how much improvement we expect, especially over a highly uncertain domain [63]. It picks the point with the highest expectation of difference between predicted function value and current maximum. \[v(\mathbf{x};f(\mathbf{x}_{1:n}))=EI(\mathbf{x}) =\mathbb{E}[\max(0,y-\hat{y}_{n})]=\] (12) \[=\sigma_{n}(\mathbf{x})\varphi\bigg{(}\frac{m_{n}(\mathbf{x})- \hat{y}_{n}}{\sigma_{n}(\mathbf{x})}\bigg{)}+(m_{n}(\mathbf{x})-\hat{y}_{n}) \Phi\bigg{(}\frac{m_{n}(\mathbf{x})-\hat{y}_{n}}{\sigma_{n}(\mathbf{x})} \bigg{)}\] where \(\varphi\) and \(\Phi\) are the normal density and cumulative distribution.
3. Upper confidence bound (UCB): UCB (Equation (13)) is one of the simplest acquisition functions, with a tunable parameter (\(\lambda\)) designed to favor either exploration or exploitation. \[v(\mathbf{x};f(\mathbf{x}_{1:n}))=UCB(\mathbf{x})=\mu(\mathbf{x})+\lambda \sigma(\mathbf{x})\] (13)