# The Power of Human-Algorithm Collaboration in Solving Combinatorial Optimization Problems
## 4 Human-Algorithm Collaboration in Bayesian Optimization  
In this section, we refer to a recent paper [27], where the authors showed that any ratio between expected global optimum and expected optimum found by their Bayesian optimization (BO) algorithms (UCB2 or EI2) can be found in the functions with finite domains in exponential time. We complement their results to show that for a specific type of problems, their results can be extended to a polynomial time human-algorithm collaboration procedure. Here, we stress that the algorithm is merely theoretical and is required to query Gaussian priors multiple times from an external expert. The key ingredient of their work that we use is that instead of the standard simple regret used in BO they provided proof for the expected approximation ratio--the multiplicative ratio between the expected best value found by the function and expected global optimum (normregret in Equation (5)). Also, their bound of the regret ratio is tight for an arbitrary constant. That is, their UCB2 or EI2 are optimal to the worst case bound. This means that the upper bound equals the lower bound in their algorithms up to some constant \(\epsilon\). Furthermore, their regret ratio is not asymptotic--which is crucial in our analysis. The upper and lower bounds, respectively, for their algorithms are  
\[normregret\leq 1-(1-T^{\frac{1}{2\epsilon}})\cdot\frac{\sqrt{\log_{2}(T)-\log _{2}(3\log_{2}^{\frac{3}{2}}(T))}}{\sqrt{\log_{2}(N)}} \tag{6}\]  
and  
\[normregret\geq 1-\frac{\sqrt{\log_{2}(T)}}{\sqrt{\log_{2}(N)}}-\epsilon \tag{7}\]  
where \(T\) is the number of function evaluations, \(N\) is the domain size, and \(\epsilon\) is any constant with \(\epsilon>0\). The pseudocode of their UCB2 algorithm, which is quite similar to the ordinary UCB algorithm can be seen in Algorithm 2. The main difference between UCB2 and a standard UCB is that it is symmetrical: flipping the sign of the function has no any effect on the found values: instead, UCB2 optimizes both the highest and lowest function values. \[x_{t}=argmax\ max\{-Y_{t}+M_{t}^{n}+\sqrt{C_{t}^{mn}\cdot 2\cdot logN},Y_{t}-M_{t }^{n}+\sqrt{C_{t}^{mn}\cdot 2\cdot logN}\} \tag{8}\]  
where \(M\) is the posterior mean, \(C\) is the given covariance,  
Figure 6: Geometric presentation of the MAX SAT problem with 3 variables, where the order of the variables is (\(x=0,y,z\)) (The numbers on the bottom imply the clauses are satisfied by the assignment)\[C_{t}:=COV(F|A_{t,t},T_{iT}), \tag{9}\]  
and A is the domain \(A:=[1,D]\). As such, their work cannot be extended to polynomial time algorithms to achieve a constant factor approximation in polynomial time due to the fact that their bounds are only _expectations_ (as in standard BO). Hence, to obtain the strict ratio provided by their algorithm, one would have to evaluate the arbitrary number of different functions. We overcome this constraint by narrowing down the scope of the functions to the type of functions, where the function can be changed almost arbitrarily many times, but still depends on the same problem instance (see Algorithm 1). ```
1:inputs:D (domain), \(\mu\), \(\Sigma\), \(T\) (number of iterations)
2:for\(t:=0,1,2,...\) to \(T\)do
3:\(x_{t}:=\text{argmax max}\left\{-Y_{t}+M_{t}^{n}+\sqrt{C_{t}^{nn}\cdot 2\cdot \log_{2}(N)},Y_{t}-M_{t}^{n}+\sqrt{C_{t}^{nn}\cdot 2\cdot\log_{2}(N)}\right\}\)
4: sample \(y_{t}:=\text{F}(x_{t})\)
5: perform Bayesian update on posterior
6:endfor
```  
**Algorithm 2** UCB2 algorithm. Without a loss of generality, we assume, once again, that the combinatorial problems here have a combinatorial complexity of \(O(2^{n})\). In Algorithm 1, we showed that any combinatorial problem with a combinatorial complexity of \(O(2^{n})\), can be reduced to a black-box univariate function with a finite domain. By running the Algorithm 1 multiple times for a single instance with different scaling factors, it produces different functions from the same problem instance.