#  $SCORE$: A 1D Reparameterization Technique to Break Bayesian Optimization’s
Curse of Dimensionality

Joseph Chakar
Laboratoire de Physique des Interfaces et des Couches Minces (LPICM)
Ecole Polytechnique, Institut Polytechnique de Paris (IP Paris)
Institut Photovoltaïque d’Île-de-France (IPVF)
Palaiseau, France
<EMAIL_ADDRESS>

###### Abstract

Bayesian optimization (BO) has emerged as a powerful tool for navigating
complex search spaces, showcasing practical applications in the fields of
science and engineering. However, since it typically relies on a surrogate
model to approximate the objective function, BO grapples with heightened
computational costs that tend to escalate as the number of parameters and
experiments grows. Several methods such as parallelization, surrogate model
approximations, and memory pruning have been proposed to cut down computing
time, but they all fall short of resolving the core issue behind BO’s curse of
dimensionality. In this paper, a 1D reparametrization trick is proposed to
break this curse and sustain linear time complexity for BO in high-dimensional
landscapes. This fast and scalable approach named $SCORE$ can successfully
find the global minimum of needle-in-a-haystack optimization functions and fit
real-world data without the high-performance computing resources typically
required by state-of-the-art techniques.

##  1 Introduction

Optimization problems are ubiquitous in various fields, ranging from computer
science and engineering to finance and healthcare. Whether the focus is on
minimizing costs or improving efficiency, these challenges frequently involve
finding the best outcome from a large pool of feasible solutions within
defined constraints. Thanks to its ability to efficiently navigate this search
space, Bayesian Optimization (BO) has emerged as a go-to solution to tackle
these problems [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], especially in cases where
running the objective function is expensive or time-consuming.

In the typical BO setup [11], a surrogate model – often a Gaussian Process
(GP) regression – is leveraged to estimate the target response function from
given input data. An acquisition function is then used to suggest strategic
new test points based on the uncertainty level of this model. If selected
carefully, this sampling strategy allows BO to explore the parameter space to
uncover promising regions with high uncertainty or exploit known favorable
regions to refine the search toward the global optimum.

However, as the dimensionality of the objective function increases and more
data points $N$ are needed, the time required to perform GP regression scales
with $O(N^{3})$ complexity [12, 13, 14] and becomes computationally
intractable. In recent literature, several solutions have been proposed to
lower BO’s computing time and circumvent this curse of dimensionality. A first
set of solutions reduces wall-clock time by executing parallel BO evaluations
[15, 16, 17, 18, 19], but requires specialized hardware and/or software
infrastructure to effectively distribute and coordinate processes across
multiple computing units. Another seeks to replace the standard GP surrogate
with sparse GP regression [12, 13, 20, 21, 22] or other algorithms such as
neural networks [23, 24, 25, 26, 27]. The main drawback of changing the
surrogate model is the potential loss of reliable uncertainty estimation
offered by GP regression, which is crucial for decision-making and
exploration/exploitation trade-offs in BO. A third set of solutions bounds the
search space using trust regions that sample areas more likely to contain the
optimum [28, 29, 30]. However, in complex optimization landscapes, these
regions may not accurately capture the true shape of the objective function
and thus prevent the algorithm from exploring promising regions of the search
space. Additionally, determining the appropriate size and shape of the trust
region is a challenging task that can require costly iterations or heuristics,
which further complicates the optimization process. Similarly, memory pruning
[14] can help reduce memory usage, but it may discard useful information
prematurely and hinder BO’s ability to adapt to changing conditions and
exploit past experiences effectively, while still requiring considerable
computational overhead.

In this work, fast and scalable BO is achieved using a 1D reparametrization
technique named $SCORE$. Instead of applying the surrogate model to the entire
D-dimensional space, GP regression is performed on individual 1D spaces to
keep the computing time in check and speed up convergence. This is akin to
projecting the D-dimensional space onto every parameter, which allows for a
more manageable and efficient optimization process. Besides preventing the
computational load from escalating with each iteration, applying GP regression
on the parameter scale offers several advantages. It first gives the
possibility to evaluate the surrogate model over full parameter ranges. In
contrast, evaluating the model over the entirety of the search space is not
feasible in high-dimensional spaces. This leaves standard BO approaches with
no choice but to iteratively evaluate it on randomly selected points when
suggesting the next set of parameters for objective function testing,
potentially leading to inadequate exploration of the search space. Moreover,
with $SCORE$, the approach presented herein, one can choose the number of
parameter values (and consequently parameter combinations) to evaluate at
every iteration. The same number of objective function evaluations can thus be
split across multiple iterations with an (un)even number of runs per iteration
(rather than just one), which can simultaneously reduce the number of GP
regression calls and allow for faster convergence towards the optimal
solution. Last but not least, all of the techniques proposed in the literature
can be seamlessly integrated into $SCORE$ to further improve its performance.

Herein, the ability of $SCORE$ to efficiently find the global minima of the
10- and 200-D Ackley functions and fit real-world current-voltage data of a
solar panel is demonstrated.

##  2 Bayesian Optimization

Bayesian optimization is a well-established strategy for finding the global
minimum (or maximum) of black-box functions that are expensive to evaluate.

$\begin{array}[]{l}\min f(x)\\\ \end{array}$ (1)

where the input $x\in\Re^{D}$ for values of $D\leq 20$ for most successful
applications [11, 23]. It relies on the construction of a probabilistic (GP
regression) model that serves as a computationally efficient approximation of
the objective function $f(x)$ to predict the performance of unexplored points
based on observed evaluations. Conditioned on a prior (Gaussian) distribution
and a set of $N$ observations, this surrogate model computes a posterior
distribution characterized by its mean and standard deviation. An acquisition
function applied to the posterior mean and variance is then queried to balance
between exploration and exploitation and reason about the next input to
evaluate in the search for the global optimum of the function of interest.

Common BO acquisition functions include the lower confidence bound (LCB),
probability of improvement (PI), expected improvement (EI), and Entropy Search
(ES) [1, 31, 32, 33]. These static techniques only adjust sampling based on
the output of the surrogate model, but active learning-based tuning of their
hyperparameters can be implemented to improve the sampling quality and prevent
entrapment in local optima [14, 34, 35].

While the efficacy of BO is contingent upon the choice of acquisition
function, this study focuses mainly on the EI function. In minimization
problems, EI is defined by:

$EI(x)=(f(x^{*})-\mu-\zeta)\psi(\frac{f(x^{*})-\mu-\zeta}{\sigma(x)})+\sigma(x)\phi(\frac{f(x^{*})-\mu-\zeta}{\sigma(x)})$
(2)

where $\psi(z)$ and $\phi(z)$ denote the cumulative distribution and density
functions of a standard Gaussian distribution, respectively. $\mu(x)$ and
$\sigma(x)$ are the posterior mean and standard deviation at $x$, $f(x^{*})$
is the best-observed value of the objective function so far, and $\zeta$ is a
free parameter to control the degree of exploration.

The rationale behind using a surrogate model in BO lies in its ability to
efficiently approximate the behavior of the true function across the entire
parameter space without necessitating expensive objective function
evaluations. However, this surrogate model itself can become computationally
intractable once the number of observations increases, especially in high
dimensional spaces, which is why a proxy optimization over the acquisition
function is necessary when predicting the next input to evaluate. This can
lead to longer optimization times and resource-intensive computations,
undermining the efficiency gains initially sought through surrogate modeling.

##  3 Methods

Inspired by the concept of separable convolutions [36, 37], $SCORE$ lifts this
curse of dimensionality by decomposing the full $D$-dimensional space into $D$
one-dimensional spaces along each input variable.

As is the case with standard BO, the objective function is first evaluated at
$N_{i}$ initial points. Then, much like deriving the marginal probability
distribution of a single variable from the joint probability distribution
describing the relationship between multiple variables, each parameter is
considered alone while marginalizing out the others. But instead of
integrating over all the possible values of the other parameters, only the
minimum (or maximum) value achieved so far for the objective function is
recorded. This enables fitting the surrogate model to individual (discrete or
continuous) variables and significantly reduces the computational load, which
becomes dependent on the number of input variables and their mesh resolution –
rather than the number of experiments $N$. In this work, only discrete
variables are considered.

Next, the acquisition function is computed to assign a “score” to every
possible parameter value. These individual parameter scores are then
aggregated to identify the most promising parameter combination for objective
function testing. Instead of suggesting just one point (i.e. the parameter
combination with the best score), multiple combinations can alternatively be
selected at every iteration. Therefore, for the same total number of function
evaluations, the number of times the surrogate model is called is greatly
reduced while potentially accelerating convergence toward the global optimum.

##  4 Results

In this section, the computing time and efficiency of $SCORE$ using EI are
benchmarked against BO [38] on two types of optimization problems: the Ackley
function [14, 29, 39], a standard problem for evaluating BO techniques, and
the fitting of experimental current-voltage data, a classical optimization
problem in solar energy research. All experiments described in this study were
carried out on a DELL laptop with 64GB of RAM and an Intel Core i7-12800H
processor. Unlike other state-of-the-art BO methods [14, 29, 40, 41], $SCORE$
seamlessly operates on conventional computing systems without the need for
specialized supercomputing infrastructure. At a later stage, $SCORE$ shall be
evaluated on additional benchmark problems against these cutting-edge
techniques, which often require extensive runtimes (hours if not days) on
powerful supercomputers.

###  4.1 Ackley Function

The Ackley function, which is characterized by a needle-in-a-haystack
landscape with multiple local minima and one global minimum of 0, is first
considered in 10D in the domain [-5, 10].

Starting with 20 random initial points (twice the number of dimensions), BO
becomes trapped in a local minimum after roughly 100 iterations, whereas
$SCORE$ successfully finds the global minimum in two different configurations,
as shown in Figure 1.

Figure 1: Convergence plots of Bayesian Optimization and two $SCORE$
configurations on the 10D Ackley function.

It’s important to acknowledge that the initialization process and choice of
hyperparameters significantly influence the outcomes of both approaches.
However, the primary focus of the results presented here is to demonstrate
that, using a simple configuration, $SCORE$ can efficiently identify the
global minimum at a fraction of BO’s computational cost. Moreover, for the
same total number of function evaluations, $SCORE$ can perform either one
evaluation per iteration or multiple evaluations simultaneously. Even though
testing 10 combinations per iteration does not reduce the final number of
function evaluations needed to find the global minimum (in this case), it
reduces the number of times the GP surrogate model is called by a factor of
10, which further decreases the computing time, as depicted in Figure 2.

Figure 2: Average computing times of Bayesian Optimization and two $SCORE$
configurations on the 10D Ackley function.

Most notably, $SCORE$ lifts BO’s curse of dimensionality and keeps the
computing time in check, even with increasing iterations, as shown in Figure
3.

Figure 3: Computing times of Bayesian Optimization and $SCORE$ as a function
of the number of iterations on the 5D Ackley function.

This is particularly beneficial for high-dimensional problems, which often
require a higher number of initial points and iterations to find the optimal
solution. Aside from limiting the number of GP regression calls and reducing
computing time, the ability to choose the number of parameter combinations to
assess per iteration can also expedite $SCORE$’s discovery of the global
optimum, as illustrated in Figure 4 with the 200D Ackley function.

Figure 4: Convergence plots of two $SCORE$ configurations on the 200D Ackley
function.

In a matter of minutes and with fewer than 500 objective function evaluations,
$SCORE$ identifies the global minimum of the 200D Ackley function, a task that
state-of-the-art BO techniques struggle to achieve even after running
thousands of iterations for hours on powerful supercomputers [29]. Even though
the computing time of $SCORE$ is proportional to dimensionality, this is
largely offset by $SCORE$’s ability to reduce both the time needed to perform
GP regression and the number of times this process is called (by evaluating
multiple parameter combinations per iteration).

###  4.2 Experimental Data

In solar energy research, established physical models exist to mimic solar
cell behavior, but fitting their intricately correlated parameters can be
challenging when limited information is available. A relatively simple example
is the single-diode model (SDM), which is commonly used to simulate the
current-voltage (IV) curve of solar cells and panels, a crucial indicator of
photovoltaic (PV) performance. The SDM is described by the following equation:

$I=I_{L}-I_{o}[exp(\frac{V+IR_{s}}{a})-1]-\frac{V+IR_{s}}{R_{sh}}$ (3)

In this equation, five parameters are used to establish the relationship
between a solar panel’s output current $I$ and its operating voltage $V$ under
defined operating conditions: the light-induced current $I_{L}$, saturation
current $I_{o}$, series resistance $R_{s}$, shunt resistance $R_{sh}$, and
modified ideality factor $a$.

In real-life scenarios, only a few IV curve points are available – often the
short-circuit current, maximum power point, and open-circuit voltage (the
black dots in Figure 5, from left to right, respectively). Fitting the SDM
thus becomes a challenging multi-solution problem, especially due to the
strong correlations between the parameters, which span different orders of
magnitude. Herein, we demonstrate $SCORE$’s ability to fit the SDM to these
three data points, which are taken from the datasheet of a commercial solar
panel.

Figure 5: Measured data vs. fits obtained by Bayesian Optimization and two
$SCORE$ configurations.

Starting with one random initial point, $SCORE$ can successfully fit the
measured data in under 10 function evaluations and at a fraction of the time
needed by BO. However, despite the seemingly adequate fits of the IV
properties, it is essential to recognize that an infinite number of solutions
exist to this problem. This complexity arises because above or below certain
thresholds, some SDM parameters (e.g. $R_{sh}$) start having little to no
impact on the shape of the IV curve. The multi-solution nature of such real-
world optimization problems highlights the importance of thoroughly navigating
the parameter space and displaying more than just the optimal fit with the
lowest residual error. Even though $SCORE$ optimizes in 1D, the chosen GP or
probabilistic surrogate model can be called to approximate the objective
function and construct probability distributions over the possible outcomes,
based on the evaluated parameter combinations.

##  5 Perspectives

The technique outlined in this paper shows promising results through its
ability to overcome BO’s curse of dimensionality and drastically reduce the
computing time of complex optimization problems. Nonetheless, more tests are
needed to fully understand $SCORE$’s robustness and evaluate its performance
against state-of-the-art techniques on different benchmark problems. As for
classical BO, $SCORE$ is sensitive to the initialization process as well as
the choice of surrogate model, acquisition function, and hyperparameters,
indicating the need for further testing.

In addition, tailoring the surrogate model and acquisition function to each
parameter may offer $SCORE$ heightened flexibility and expedite convergence
toward the optimal solution. Parallelizing this sequential process could also
further speed up $SCORE$’s execution time. Alternatively, when proposing the
next set of parameter combinations for objective function evaluation, it may
be worth computing the score of all feasible parameter combinations (based on
the scores of the individual parameter values) to identify the most promising
candidates. While not viable in continuous and high-dimensional spaces, this
strategy can prove successful in low-dimensional discrete spaces where
achieving optimal solutions does not necessitate a highly precise parameter
mesh, or if it is applied iteratively to gradually refine the search space
boundaries.

##  6 Conclusion

In short, a 1D reparametrization technique named $SCORE$ is proposed to break
BO’s curse of dimensionality. By projecting the objective function evaluations
onto each parameter – akin to obtaining marginal distributions from the joint
distribution – $SCORE$ partitions the BO process and executes the surrogate GP
model in 1D spaces instead of the full search space. It assigns a score to the
most likely values of each parameter, from which the most likely parameter
combinations are prioritized for subsequent testing. This drastically reduces
BO’s computational complexity and allows multiple parameter combinations to be
evaluated at the same time, which further reduces the total computing time and
possibly speeds up convergence. This working paper showcases $SCORE$’s ability
to tackle both a complex needle-in-a-haystack optimization problem and a real-
world challenge, but additional efforts are needed to assess its robustness
and generalizability.

A Python implementation of $SCORE$ is currently under development and
available at: https://github.com/hi-paris/SCORE.

## Acknowledgments

I would like to express my gratitude to my supervisors Yvan Bonnassieux and
Jean-Baptiste Puel for their support. I initially designed $SCORE$ to solve
solar energy research problems after realizing that BO was taking more time to
run than my simulation models (i.e. my objective function evaluation), thus
defeating its purpose. I expanded the scope of this approach to encompass more
generic problems and drafted this working paper to demonstrate $SCORE$’s
capabilities before the fast-approaching end of my PhD journey. I would also
like to thank Pierre-Antoine, Machine Learning Engineer at Hi! PARIS, for
developing the Python package for $SCORE$, which I hope will undergo thorough
testing and benchmarking to enhance its public utility. This research work is
also supported by Hi! PARIS, the Center on Data Analytics and Artificial
Intelligence for Science, Business and Society created by Institut
Polytechnique de Paris (IP Paris) and HEC Paris and joined by Inria (Centre
Inria de Saclay).

## References

  * [1] Jasper Snoek, Hugo Larochelle, and Ryan P Adams.  Practical bayesian optimization of machine learning algorithms.  In F. Pereira, C.J. Burges, L. Bottou, and K.Q. Weinberger, editors, Advances in neural information processing systems, volume 25. Curran Associates, Inc., 2012.
  * [2] Bobak Shahriari, Kevin Swersky, Ziyu Wang, Ryan P. Adams, and Nando de Freitas.  Taking the Human Out of the Loop: A Review of Bayesian Optimization.  Proceedings of the IEEE, 104(1):148–175, January 2016.  Conference Name: Proceedings of the IEEE.
  * [3] Tsuyoshi Ueno, Trevor David Rhone, Zhufeng Hou, Teruyasu Mizoguchi, and Koji Tsuda.  COMBO: An efficient Bayesian optimization library for materials science.  Materials Discovery, 4:18–21, June 2016.
  * [4] Aaron Klein, Stefan Falkner, Simon Bartels, Philipp Hennig, and Frank Hutter.  Fast Bayesian Optimization of Machine Learning Hyperparameters on Large Datasets.  In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, pages 528–536. PMLR, April 2017.  ISSN: 2640-3498.
  * [5] Ahmed Alaa and Mihaela Schaar.  AutoPrognosis: Automated Clinical Prognostic Modeling via Bayesian Optimization with Structured Kernel Learning.  In Proceedings of the 35th International Conference on Machine Learning, pages 139–148. PMLR, July 2018.  ISSN: 2640-3498.
  * [6] Jia Wu, Xiu-Yun Chen, Hao Zhang, Li-Dong Xiong, Hang Lei, and Si-Hao Deng.  Hyperparameter Optimization for Machine Learning Models Based on Bayesian Optimization.  Journal of Electronic Science and Technology, 17(1):26–40, March 2019.
  * [7] Sait Cakmak, Raul Astudillo Marban, Peter Frazier, and Enlu Zhou.  Bayesian Optimization of Risk Measures.  In Advances in Neural Information Processing Systems, volume 33, pages 20130–20141. Curran Associates, Inc., 2020.
  * [8] Qiaohao Liang, Aldair E. Gongora, Zekun Ren, Armi Tiihonen, Zhe Liu, Shijing Sun, James R. Deneault, Daniil Bash, Flore Mekki-Berrada, Saif A. Khan, Kedar Hippalgaonkar, Benji Maruyama, Keith A. Brown, John Fisher III, and Tonio Buonassisi.  Benchmarking the performance of Bayesian optimization across multiple experimental materials science domains.  npj Computational Materials, 7(1):1–10, November 2021.  Number: 1 Publisher: Nature Publishing Group.
  * [9] Mohamed Loey, Shaker El-Sappagh, and Seyedali Mirjalili.  Bayesian-based optimized deep learning model to detect COVID-19 patients using chest X-ray image data.  Computers in Biology and Medicine, 142:105213, March 2022.
  * [10] Bhaskar Tripathi and Rakesh Kumar Sharma.  Modeling Bitcoin Prices using Signal Processing Methods, Bayesian Optimization, and Deep Neural Networks.  Computational Economics, 62(4):1919–1945, December 2023.
  * [11] Peter I. Frazier.  A Tutorial on Bayesian Optimization, July 2018.  arXiv:1807.02811 [cs, math, stat].
  * [12] Edward Snelson and Zoubin Ghahramani.  Sparse Gaussian Processes using Pseudo-inputs.  In Advances in Neural Information Processing Systems, volume 18. MIT Press, 2005.
  * [13] Thang D. Bui, Josiah Yan, and Richard E. Turner.  A unifying framework for Gaussian process pseudo-point approximations using power expectation propagation.  The Journal of Machine Learning Research, 18(1):3649–3720, January 2017.
  * [14] Alexander E. Siemenn, Zekun Ren, Qianxiao Li, and Tonio Buonassisi.  Fast Bayesian optimization of Needle-in-a-Haystack problems using zooming memory-based initialization (ZoMBI).  npj Computational Materials, 9(1):1–13, May 2023.  Number: 1 Publisher: Nature Publishing Group.
  * [15] Asim Munawar, Mohamed Wahib, Masaharu Munetomo, and Kiyoshi Akama.  Theoretical and Empirical Analysis of a GPU Based Parallel Bayesian Optimization Algorithm.  In 2009 International Conference on Parallel and Distributed Computing, Applications and Technologies, pages 457–462, December 2009.  ISSN: 2379-5352.
  * [16] Chaitanya Talnikar, P. Blonigan, J. Bodart, and Qiqi Wang.  Parallel optimization for large eddy simulations.  October 2014.
  * [17] Margarita Rebolledo, Frederik Rehbach, A. E. Eiben, and Thomas Bartz-Beielstein.  Parallelized bayesian optimization for problems with expensive evaluation functions.  In Proceedings of the 2020 Genetic and Evolutionary Computation Conference Companion, GECCO ’20, pages 231–232, New York, NY, USA, July 2020. Association for Computing Machinery.
  * [18] Jialei Wang, Scott C. Clark, Eric Liu, and Peter I. Frazier.  Parallel Bayesian Global Optimization of Expensive Functions.  Operations Research, 68(6):1850–1865, November 2020.  Publisher: INFORMS.
  * [19] Mickael Binois, Nicholson Collier, and Jonathan Ozik.  A portfolio approach to massively parallel Bayesian optimization, April 2023.  arXiv:2110.09334 [math, stat].
  * [20] Michalis Titsias.  Variational Learning of Inducing Variables in Sparse Gaussian Processes.  In Proceedings of the Twelth International Conference on Artificial Intelligence and Statistics, pages 567–574. PMLR, April 2009.  ISSN: 1938-7228.
  * [21] Biao He, Shuhan Zhang, Fan Yang, Changhao Yan, Dian Zhou, and Xuan Zeng.  An Efficient Bayesian Optimization Approach for Analog Circuit Synthesis via Sparse Gaussian Process Modeling.  In 2020 Design, Automation & Test in Europe Conference & Exhibition (DATE), pages 67–72, March 2020.  ISSN: 1558-1101.
  * [22] Henry B. Moss, Sebastian W. Ober, and Victor Picheny.  Inducing Point Allocation for Sparse Gaussian Processes in High-Throughput Bayesian Optimisation.  In Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, pages 5213–5230. PMLR, April 2023.  ISSN: 2640-3498.
  * [23] Jasper Snoek, Oren Rippel, Kevin Swersky, Ryan Kiros, Nadathur Satish, Narayanan Sundaram, Md. Mostofa Ali Patwary, Prabhat Prabhat, and Ryan P. Adams.  Scalable bayesian optimization using deep neural networks.  In Proceedings of the 32nd International Conference on International Conference on Machine Learning - Volume 37, ICML’15, page 2171–2180. JMLR.org, 2015.
  * [24] Jost Tobias Springenberg, Aaron Klein, Stefan Falkner, and Frank Hutter.  Bayesian optimization with robust bayesian neural networks.  In D. Lee, M. Sugiyama, U. Luxburg, I. Guyon, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 29. Curran Associates, Inc., 2016.
  * [25] Shibo Li, Wei Xing, Robert Kirby, and Shandian Zhe.  Multi-Fidelity Bayesian Optimization via Deep Neural Networks.  In Advances in Neural Information Processing Systems, volume 33, pages 8521–8531. Curran Associates, Inc., 2020.
  * [26] Yee-Fun Lim, Chee Koon Ng, U.s. Vaitesswar, and Kedar Hippalgaonkar.  Extrapolative Bayesian Optimization with Gaussian Process and Neural Network Ensemble Surrogate Models.  Advanced Intelligent Systems, 3(11):2100101, 2021.  _eprint: https://onlinelibrary.wiley.com/doi/pdf/10.1002/aisy.202100101.
  * [27] Yucen Lily Li, Tim G. J. Rudner, and Andrew Gordon Wilson.  A study of bayesian neural network surrogates for bayesian optimization, 2023.
  * [28] Rommel G. Regis.  Trust regions in Kriging-based optimization with expected improvement.  Engineering Optimization, 48(6):1037–1059, June 2016.  Publisher: Taylor & Francis _eprint: https://doi.org/10.1080/0305215X.2015.1082350.
  * [29] David Eriksson, Michael Pearce, Jacob Gardner, Ryan D Turner, and Matthias Poloczek.  Scalable Global Optimization via Local Bayesian Optimization.  In Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
  * [30] Youssef Diouane, Victor Picheny, Rodolophe Le Riche, and Alexandre Scotto Di Perrotolo.  TREGO: a trust-region framework for efficient global optimization.  Journal of Global Optimization, 86(1):1–23, May 2023.
  * [31] Adam D. Bull.  Convergence Rates of Efficient Global Optimization Algorithms.  Journal of Machine Learning Research, 12(88):2879–2904, 2011.
  * [32] Philipp Hennig and Christian J. Schuler.  Entropy Search for Information-Efficient Global Optimization.  Journal of machine learning research, 2011.
  * [33] Michael A. Gelbart, Jasper Snoek, and Ryan P. Adams.  Bayesian optimization with unknown constraints.  In Proceedings of the Thirtieth Conference on Uncertainty in Artificial Intelligence, UAI’14, pages 250–259, Arlington, Virginia, USA, July 2014. AUAI Press.
  * [34] Hao Wang, Bas van Stein, Michael Emmerich, and Thomas Back.  A new acquisition function for Bayesian optimization based on the moment-generating function.  In 2017 IEEE International Conference on Systems, Man, and Cybernetics (SMC), pages 507–512, October 2017.
  * [35] Umberto Noè and Dirk Husmeier.  On a New Improvement-Based Acquisition Function for Bayesian Optimization, August 2018.  arXiv:1808.06918 [cs, stat].
  * [36] Francois Chollet.  Xception: Deep Learning With Depthwise Separable Convolutions.  pages 1251–1258, 2017.
  * [37] Joseph Chakar, Rayan Al Sobbahi, and Joe Tekli.  Depthwise Separable Convolutions and Variational Dropout within the context of YOLOv3.  In Advances in Visual Computing: 15th International Symposium, ISVC 2020, San Diego, CA, USA, October 5–7, 2020, Proceedings, Part I, pages 107–120, Berlin, Heidelberg, October 2020. Springer-Verlag.
  * [38] Aki Vehtari, Alan Saul, Andreas Damianou, Andrei Paleyes, Fela Winkelmolen, Huibin Shen, James Hensman, Javier Gonzalez, Jordan Massiah, Josh Fass, Neil Lawrence, Rasmus Berg Palm, Rodolphe Jenatton, Simon Kamronn, and Zhenwen Dai.  GPyOpt: A Bayesian Optimization framework in python, 2016.
  * [39] Jian Tan and Niv Nayman.  Two-stage Kernel Bayesian Optimization in High Dimensions.  In Proceedings of the Thirty-Ninth Conference on Uncertainty in Artificial Intelligence, pages 2099–2110. PMLR, July 2023.  ISSN: 2640-3498.
  * [40] Zi Wang, Clement Gehring, Pushmeet Kohli, and Stefanie Jegelka.  Batched Large-scale Bayesian Optimization in High-dimensional Spaces.  In Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics, pages 745–754. PMLR, March 2018.  ISSN: 2640-3498.
  * [41] Alexander I. Cowen-Rivers, Wenlong Lyu, Rasul Tutunov, Zhi Wang, Antoine Grosnit, Ryan Rhys Griffiths, Alexandre Max Maraval, Hao Jianye, Jun Wang, Jan Peters, and Haitham Bou Ammar.  HEBO Pushing The Limits of Sample-Efficient Hyperparameter Optimisation, May 2022.  arXiv:2012.03826 [cs, math].


# Demo Paper: A Game Agents Battle Driven by Free-Form Text Commands Using
Code-Generation LLM

Ray Ito  Faculty of Engineering,
The University of Tokyo
Tokyo, Japan
<EMAIL_ADDRESS>Junichiro Takahashi  Faculty of Engineering,
The University of Tokyo
Tokyo, Japan
<EMAIL_ADDRESS>
###### Abstract

This paper presents a demonstration of our monster battle game, in which the
game agents fight in accordance with their player’s language commands. The
commands were translated into the knowledge expression called behavior
branches by a code-generation large language model. This work facilitated the
design of the commanding system more easily, enabling the game agent to
comprehend more various and continuous commands than rule-based methods. The
results of the commanding and translation process were stored in a database on
an Amazon Web Services server for more comprehensive validation. This
implementation would provide a sufficient evaluation of this ongoing work, and
give insights to the industry that they could use this to develop their
interactive game agents.

###### Index Terms:

Game AI, Character AI, LLM, Game Agent, Knowledge Expression, Human-Computer
Interaction, Entertainment Computing

##  I Introduction

Game players’ desire to control their trained monsters has led to the success
of games such as Pokémon, Digimon, and Monster Rancher. Still, players were
only able to choose from a limited set of options to command their monsters in
these games. This led to attempts, including [1, 2, 3, 4], to make game
monsters understand and react to language commands, but these implementations
were rule-based, which was not easy for developers to hard-code a sufficient
interaction. Therefore, [5] proposed a method to translate player language
commands without limitations into the game agent’s action. The language
command was passed to the code-generation large language model (LLM) model,
which generated the knowledge expression called behavior branches. This method
enabled the game agent to comprehend a wider range of content and expressions
of the player’s commands. The concept of using code-generation LLM was
originated from [6]. While [6] intended to handle independent tasks for
robotics, [5] extended this to the game agents, allowing for the execution of
more continuous and rapidly changing commands.

To examine if this method worked, [5] only implemented a single controllable
game agent against a single unmoving agent. However, the effectiveness of this
approach in the context of actual player battles remained unexamined. In this
paper, we demonstrate a system that enables two players to fight each other at
a distance under this commanding system, and the command and translation
results are stored in the database on our backend server. Therefore, we aimed
to contribute to the advancement of knowledge and entertainment technology in
the following ways:

  * •

To give practical validation to this ongoing work.

  * •

To demonstrate to the industry and researchers that they could use or extend
our method to develop their interactive game systems.

##  II System Overview

###  II-A The Entire System

Figure 1: Overview of the entire system.

The system consists of the following components as shown in Fig. 1. Each
description is as follows:

  * •

Unity (2022.3.15f1): Unity computed the game environment and provided the game
environment to the players.

  * •

Photon PUN2 (2.45): PUN2 was used for the real-time network synchronization
between both Unity clients.

  * •

AWS Server: The server was used to generate the behavior branches from the
player’s commands and to store the translation logs. Each players were
identified using Cognito, and the logs were stored in DynamoDB. Lambda did the
API control including accessing the LLM model. The latency was all together
1.8 seconds on average.

  * •

Fireworks AI: The API of Fireworks AI was used for utilizing the default
‘llama-v2-34b-code’ model. Fireworks AI was chosen for its rapid latency. The
latency was 0.9 seconds on average.

###  II-B Game Environment

In the game environment, two game agents were placed in the plain 3D space.
The game agents could move in the 3D space, and use the following
attacks111These were inspired by Creatures Inc. “Poképark Wii: Pikachu’s
Adventure.”:

  * •

Thunderbolt: The game agent shoots a thunderbolt (implemented as a sphere) to
the opponent.

  * •

Iron Tail: The game agent swings its tail to the opponent.

  * •

Tackle: The game agent rushes and hit the opponent.

Figure 2: The visual interface of the game.

The interface of the game is shown in Fig. 2. The players could command their
game agent by typing the command in the text box. The translation when the
enter key was pressed. The game would be paused while the players were typing.

###  II-C Command-Action Translation

Language commands were translated into the actionable knowledge expression
called behavior branches proposed by [5]. Behavior branches were tree
structures consisting of the following nodes:

  * •

Action node: Specified the action to be executed.

  * •

Condition node: This connected to two nodes, and the satisfaction of this node
determined which node to be executed next.

  * •

Control node: Specified the controling of the execution flow.

This followed the concept of structural programming, and appending different
behavior branches could dynamically edit the action flow. As the game agent
followed these nodes, [5] has shown that the game agent could understand and
follow the commands freely written under the static experiment222Static
experiment refers that only one game agent was playable and the other stayed
still. Thus, the performance under the actual battle, which was the aim of
this paper, remained unknown. For more details of the behavior branches, refer
to [5].

As similar to [6], the prompt for the LLM presented the intended format and
the examples of the translations in Python. The inference code was streamed
back from the LLM API333It started to process it as soon as the closing
bracket in the generated Python code referring to the behavior branch was
detected. This early stopping made the translation 1.1 seconds faster than
[5]..

###  II-D Logs in the Database

Figure 3: The screenshot of the table in DynamoDB. Note that any personal
information is not shown.

Fig. 3 shows a clip of recorded data. There was one row for each command,
including the ID of the battle session, the timestamp of the command in Unix
time, the player’s Cognito ID, the original command text, and the translated
behavior branch in JSON format.

##  III Demonstration

During the demonstration, two attendees will play the game with two laptops
prepared. The demonstrator will explain the game rules and what moves the game
agent able to do. The attendees will play the game by typing the command in
the text box, and try to defeat the opponent’s game agent. The game will take
approximately 3 minutes. In short, the required facilities for this demo
include a table to put the laptops and keyboards, and the internet connection.

##  IV Conclusions and Future Works

In this paper, we demonstrated a battle game system where the game characters
flexibly follow the player’s directions. The method proposed by [5],
translating player’s commands into Behavior Branches using code-generation
LLM, has become available for actual battle gaming. For future work, we plan
to conduct a quantitative and qualitative experiment to evaluate using the
record and improve our suggested method so as to make it more practical and
useful for the game industry.

## References

  * [1] Hobonichi Co. Ltd., “Pikachu decides that the mushroom in front of him is more important,” Hobo Niccan Itoi Shinbun, Feb. 1999. https://www.1101.com/nintendo/nin3/nin3-2.htm (accessed Apr. 25, 2024).
  * [2] M. Yoshida, H. Bizen, M. Kambe, and Y. Kawai, “Voice Manipulation System on Virtual Space Using Synonyms,” Proc. of the Inf. Process. Soc. of Jpn. Annu. Conv., Mar. 2021, pp. 137–138.
  * [3] Q. Mehdi, X. Zeng, and N. Gough, “An interactive speech interface for virtual characters in dynamic environments,” in Proc. ISAS 04, 10th Int. Conf. on Inf. Syst. Anal. and Systhesis, Jul. 2004, pp. 243-248.
  * [4] D. M. Waqar, T. S. Gunawan, M. Kartiwi and R. Ahmad, “Real-Time Voice-Controlled Game Interaction using Convolutional Neural Networks,” in 2021 IEEE 7th Int. Conf. on Smart Instrum., Meas. and Appl., 2021, pp. 76-81
  * [5] R. Ito and J. Takahashi, “Game Agent Driven by Free-Form Text Command: Using LLM-based Code Generation and Behavior Branch (in press),” The 38th Annu. Conf. of the Jpn. Soc. for Artif. Intell., May 2024, Available: https://arxiv.org/abs/2402.07442.
  * [6] J. Liang et al., “Code as Policies: Language Model Programs for Embodied Control,” in 2023 IEEE Int. Conf. on Robot. and Automat., May 2023, pp. 9493-9500.