{'fraction_non_alphanumeric': 0.04017857142857143, 'fraction_numerical': 0.019782913165266106, 'mean_word_length': 4.854214706635921, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Can Global Optimization Strategy Outperform Myopic Strategy for Bayesian Parameter Estimation?

Bayesian adaptive inference is widely used in psychophysics to estimate psychometric parameters. Most applications used myopic one-step ahead strategy which only optimizes the immediate utility. The widely held expectation is that global optimization strategies that explicitly optimize over some horizon can largely improve the performance of the myopic strategy. With limited studies that compared myopic and global strategies, the expectation was not challenged and researchers are still investing heavily to achieve global optimization. Is that really worthwhile? This paper provides a discouraging answer based on experimental simulations comparing the performance improvement and computation burden between global and myopic strategies in parameter estimation of multiple models. The finding is that the added horizon in global strategies has negligible contributions to the improvement of optimal global utility other than the most immediate next steps (of myopic strategy). Mathematical recursion is derived to prove that the contribution of utility improvement of each added horizon step diminishes fast as that step moves further into the future.


Introduction
In the context of Bayesian design with nonlinear models and non-Gaussian posteriors, rigorous information-theoretic criteria have been proposed (Lindley, 1956). Bayesian adaptive inference was first applied in the landmark development of the QUEST method by Watson and Pelli (1983). Kontsevich and Tyler (1999) introduced this new Bayesian adaptive method to estimate both threshold and slope of the psychometric function and update posterior probabilities. Bayesian adaptive inference is now widely used in psychophysics to estimate psychometric parameters to explore the connection between physical stimuli and observer's response (Kujala & Lukka，2006, Lesmes, Lu, Baek & Albright, 2010, Lindley, 1956). In addition, Zhu and Zhang (2015) applied Bayesian adaptive inference to estimate the parameters of gap acceptance function in driving behavior field. By taking advantage of Bayesian adaptive inference, Kandasamy et al. (2017) estimated the posterior distribution of the unknown parameters (e.g. cosmological constants) in bounded continuous cosmological parameter space based on Gaussian Process. Besides, Cavagnaro et al. (2010) extended the methodology of parameter estimation to model selection of multiple memory retention models by treating the model index as a parameter for estimation.
Generally speaking, Bayesian adaptive parameter estimation aims to reduce the uncertainty about parameters in a function, by minimizing the expected entropy, or equivalently, maximizing the mutual information (or information gain) between experimental observations and unknown parameters. This strategy is known as greedy or myopic, which only optimizes the utility of the immediate step at each trial. Since global strategy considers forecasted information in the possible scenarios in the future (Truong, 2014, Jiang, Chai, Gonzalez & Garnett, 2020, it is usually assumed that there can be substantial room for improvement of performance (Wu & Frazier, 2019) by adopting global optimization strategy for sequential decisions. However, computing a globally optimal policy requires solving Bellman equations, which are generally intractable and therefore hindering wider application (Cashore, Kumarga & Frazier, 2016). Most existing work resorts to severe approximations of future information (Bertsekas, 2012, Jiang, Chai, Gonzalez & Garnett, 2020, Powell, 2011, Wu & Frazier, 2019, which can sabotage performance due to accumulated errors (Yue & Kontar, 2020). Most applications for global optimization are usually addressed by specific assumptions such as one-dimensional, looking-ahead over short horizon or simply defined utility function. For example, Wu and Frazier (2019) presented practical twostep ahead approach for Bayesian optimization problem. Garnett et al. (2011Garnett et al. ( , 2012 defined a unique and simple utility instead of mutual information (Kontsevich & Tyler, 1999, Kujala & Lukka, 2006, Lesmes, Lu, Baek & Albright, 2010 and implemented active searching by looking 2 (or 3) step ahead in the simulations..
Given the expectation of the superiority of global optimization, there has not been much research that successfully quantifies such superiority over myopic strategies in a generalizable manner for Bayesian parameter estimation. In addition, there has not been much research that looks at this issue from the perspective of the tradeoff between the performance improvement and the incremental computational and algorithmic burden that global optimization requires. This study aims to strike for these goals to truly bring an ease of mind to researchers who are still wondering whether it is worthwhile to achieve global optimization.
We approached this question by first comparing 2-trial global strategy without any approximation and myopic strategy on three models from different fields. The utilities of two successive future steps are separated to study on their contributions to the optimal global utility based on experiments. To generalize this insight to more than 2trials, mathematical recursion is derived for the utility analysis of -trial (T≥ 2) global strategy. In order to make the conclusion sound, the algorithm in the experiments did not conduct any approximation which may bring reduced effects on the global expected utility. The experimental simulations and mathematical recursion proof offer a discouraging answer for the superiority of global optimization strategy.
The next section reviews the mathematical foundations of the myopic and global optimization strategies for Bayesian parameter estimation. Readers who are less interested in this part can skip this section.

Myopic Bayesian inference for parameter estimation
Suppose empirical heterogeneous psychological function ( | , ) is given by the probability that the participant takes response given experimental design , where is the parameter vector to be estimated for the individual participant. The basic idea of the myopic strategy is to minimize the uncertainty about , which can be formulated as the expected entropy of parameter prior distribution (Θ) = [ ( )] ∈Θ for theth experimental trial (Kontsevich & Tyler, 1999, Kuss, Jkel & Wichmann, 2005, where Θ is the space of parameter vector . The mutual information (Θ, | ) after design can be defined as the utility for (Θ) describing the uncertainty reduction.
( | (Θ) ) = (Θ, | , (Θ) ) = ∬ ∈ , ∈ ( , | ) where is the space of response . The strategy is to choose design that minimizes the expected entropy by maximizing the gain of information after completion of theth trial, i.e., * = argmax ∈ ( | (Θ) ). In terms of Bayes rule, the parameter prior distribution regarding the participant's response ∈ can be updated as for each ∈ Θ. This strategy considers to only optimize the utility of the immediate step at each trial, i.e., one-step ahead, so it is myopic and greedy.

Global expected utility for global optimization strategy
Without loss of generality, assume that at the onset we will be allowed to look ahead in the future trails, which entails successively calculating the expected utility of next trials. According to dynamic programming, the global expected utility for looking trials in the future at the beginning of trial can be written as where ∈ (0,1] is the discount factor and is the set of possible policies (Bertsekas, 2012). For convenience, we call it -trial global strategy. Each element ∈ corresponds to a policy. The notation + represents the decision rule that determines the design decision + under policy for future + -th trial, given prior probability distribution + (Θ). In other words, the objective is to find the best decision rule to solve Eq.(2). By backward dynamic programming, Eq.(2) can be reformulated as Bellman's equation (Bertsekas, 2012, Jiang, Chai, Gonzalez & Garnett, 2020, Powell, 2011. (4) ( + | + (Θ)) is the utility for design + given prior + (Θ) and + ( + (Θ)) is the value of prior distribution + (Θ). + +1 ( + +1 (Θ| + (Θ), + ) is the value of prior + +1 (Θ) transited from prior + (Θ) given design + ( = 0,1 … , − 2). Let design sequence { * , +1 * , … , + −1 * } be the optimal solution of Eq.(3-4). Therefore, the objective of dynamic programming Eq.(2) with Bayesian mutual information as the reward function is essentially to find decision policy to maximize the global expected utility over finite experimental trials. Thus, -trial global strategy tries to reduce the global uncertainty about the individual's parameters by maximizing the global expected mutual information (information gain) over the finite horizon.

Three Models for Parameter Estimation
Three models from different areas are applied for parameter estimation in the following simulations to compare global and myopic strategies. This section briefly introduces the three models.

Heterogenous Gap Acceptance Model
Heterogenous gap acceptance model is used to describe the behavior of a vehicle driver (or a bicycle rider) when deciding whether to merge to the next traffic lane. Empirical Miller's model (Zhu & Zhang, 2015) of gap acceptance function is defined as where (•) is the standard cumulative normal probability function to describe the probability that the driver would merge to the next lane given a distance, or gap , from a car driving ahead in that lane. Parameter is the driver's critical gap when facing the first gap and is the disturbance parameter (Zhu & Zhang, 2015).In an experiment, when a driver encounters the situation with a particular , the driver's response is binary, either merge to the next lane or stay in the current lane. With these responses, heterogenous parameters and can be estimated for each driver.

Visual Psychometric Model
Most experimental psychophysics deals with measuring sensitivity thresholds that specify the intensity at which the stimulus is detectable (Kontsevich & Tyler, 1999). One example is contrast sensitivity function that models the probability of detecting a given luminance contrast. The function ( | , ) = Ψ (10 10 ( − ) ) = 1 √2 ∫ − 2 2 10 10 ( − ) −∞ describes the probability of correct detection of a stimulus intensity , where the intensity is the controllable experimental design and slope and threshold are two parameters to be estimated. The psychometric function (•) is a cumulative function for Gaussian distribution. At each experimental trial, the binary response of whether a given intensity is detected is collected.

Memory Retention Model
The rate of forgetting over time is one of central issues in memory research. Many different models have been developed to describe the probability of correct recall of words given a certain lag time (Cavagnaro, Myung, Pitt & Kujala, 2010). Exponential memory retention function is one model, defined as where and are model parameters to be estimated and d is the stimulus, lag time. In a typical experiment, each trial consists of 'study phase,' in which a participant is given a list of words to memorize, followed by a 'test phase,' in which retention is assessed by testing how many words the participant can correctly recall from the study list (Cavagnaro, Myung, Pitt & Kujala, 2010). The lag time is the length of time between the study phase and the test phase, which can be controlled by the experimenter.

Simulation Exploration for Potential Gain from 2 -trial Global Strategy
This section applies two approaches of global strategy and one myopic approach to perform parameter estimation for the three models introduced in Section 3. As mentioned in Section 2, two approaches for global strategy are global 2-step approach and 2-step ahead approach, and the myopic approach is one-step ahead approach. The objectives of both global approaches are computed based on 2-trial global strategy, but the designs are assigned in different way, which may generate different performance results in the simulations. No approximation of the parameter distribution space is involved for the global strategies so that the performance of global strategies is not compromised.
Simulations are run on the laptop with configuration in Tab.1 and GPU is used to speed up the computation of matrix. The algorithms are conducted on discretized grids with discount factor = 1 . All parameter ranges and grid settings are selected from references (Cavagnaro, Myung, Pitt & Kujala, 2010, Kontsevich & Tyler, 1999, Zhu & Zhang, 2015 as shown in Tab.2. We use non-informative uniform prior while initializing an experiment, with the acknowledgement that the choice of priors can usefully influence the testing strategy (Cavagnaro, Myung, Pitt & Kujala, 2010, Kontsevich & Tyler, 1999, Zhu & Zhang, 2015. For each specific true parameter vector , the experiment is replicated to take the average ̂ for the posterior probability +1 (Θ) as the estimated parameter values. To compare the performance of different approaches, the mean squared error (MSE) of the estimated parameters is used as one criterion, which can be quantified by MSE(̂) = [(̂− ) 2 . The second criterion for information gain is defined as the entropy difference between initial prior and posterior from each trial, since maximizing global expected mutual information corresponds to maximizing global expected information gain.

Performance Investigation of Two Strategies
For each model, simulations are run with different sets of true parameter values and with different grid settings for parameters and designs to avoid idiosyncratic results. In what follows, we only present the results using one particular set of true parameter values and only one grid setting for each model. However, the same pattern is observed for different parameter values and different grid settings.
In the simulations, the true driver's gap acceptance function is (    (c) depicts the information gain with trials. Fig.1 regarding gap acceptance mode turn out that MSE of global 2-step approach outperforms 2-step ahead approach slightly, MSE of 2-step ahead approach outperforms myopic approach slightly and three information gain curves almost overlap. Fig.2 for visual psychometric model and Fig.3 for memory retention model display that three MSE curves for three approaches intersect with each other and three information gain curves overlap too.
Overlapping of information gain curves of three approaches in three cases turns out that no approach performs apparently better than another. MSE curves in Fig.1-3 demonstrate that the superiority of 2-trial global strategy is so marginal over myopic strategy that we can even ignore it. Simple 2-trial global strategy implemented for three cases from different fields couldn't apparently outperform myopic approach under rigorous mathematical inference. These results trigger us to deeply investigate how the mechanism of global optimization strategy works on the expected utilities by the backward computation of dynamic programming.
In order to explore the intrinsic source behind mathematical formulas, we investigate how the utilities are transferred between two successive trials in terms of 2-trial global strategy and figure out which trial plays the most important role in the computation of optimal global expected utility in the simulations. For each specific true parameter setting, the experiment for utility investigation is replicated 500 times to take average for the randomness of observation. The utility ranges for two successive trials as well as difference of utilities between two strategies are studied, according to the backward dynamic programming in Eq.(3-4).
The other statistic, utility difference ratio, is to calculate the relative difference of utilities between two strategies, as the ratio of absolute utility difference relative to max ∈ ( | (Θ)) , where max ∈ ( | (Θ)) is the maximal utility of the -th trial from myopic strategy. This utility difference ratio can assess how much percentage of myopic max ∈ ( | (Θ)) the utility improvement would take, which can display clearly which trial will decide the value of optimal global expected utility.

Utility Investigation for Heterogenous Gap Acceptance Function
For the true driver's function ( −7 2.004 ), Fig.4 presents trials = 5,25,55,85,115,145 for instance to display the average utility for the -th trial (in blue) and average expected utility curve for the +1-th trial (in red). For example, the first figure of Fig.4 considers at the starting point of 5-th trial about the average utility for the 5-th trial and the average expected utility for the 6-th trial over design space. The remaining figures in Fig.4 and figures in Fig.6 and Fig. 8 can be explained in the same way.
In Fig.4, the average expected utility curve for the +1-th trial (in red) is much flatter than the average utility curve for the -th trial (in blue) for all . Compared with blue curves, red curves tend more and more flat while the trials move on with . In Fig.5(a), the range width of red curves (of Fig.4) is always far smaller than the range of width of blue curves (of Fig.4) over trial and the range width of average expected utility for +1-th trial converges to 0. According to Eq.(6), Fig.5(b) shows that the maximal utility difference is 4*10 −5 and the utility difference curve converges to zero. In Fig.5(c), the maximal utility difference ratio is around 1.05*10 −3 and the ratio curve drops dramatically after around 25-th trial and converges to zero, according to Eq.(7). Figure 4 Utility investigation for gap acceptance model at the beginning of each -th trial ( = 5,25,55,85,115,145). The blue curve is the average utility for -th trial and the red curve is the average expected utility for +1-th trial.

Utility Investigation of Visual Psychometric Function
For the true model with = 0.6312 and = 2.3643 , Fig.6 presents trials = 5,25,55,95,125,165. Similarly, the red curves are much flatter than the blue curves for all -th trial in Fig.6 and the range of average -th trial utility is far wider than the average +1-th trial expected utility as shown in Fig.7(a). In Fig.7(b), the maximal utility difference between two strategies is 8.5*10 −4 and the utility difference curve drops quickly after around the 5-th trial and converges to zero. In Fig.7(c), the maximal ratio of utility difference to the maximal myopic utility is around 5.5*10 −3 . And the ratio curve drops dramatically after around 5-th trial and keeps stable around 2.5*10 −3 after the 100-th trial.   Fig.8 presents trials = 5,15,25,35,45,65 for true memory retention model 0.7103 −.0833 . Similarly, the red curves are much flatter than the blue curves for all trials in Fig.8 and the range of average -th trial utility is wider than the average +1-th expected utility as shown in Fig.9(a). In Fig.9(b), the maximal utility difference between two strategies is less than 6.5*10 −3 and the utility difference drops quickly after around the 5-th trial and converges to zero. As shown in Fig.9 (c), the maximal utility difference ratio is around 0.014, and then the curve drops after around the 17-th trial. Figure 8 Utility investigation for memory retention model at the beginning of each -th trial ( = 5,15,25,35,45,65). The blue curve is the average utility for -th trial and the red curve is the average expected utility for +1-th trial. Based on Fig. 4-9, we can summarize the utility investigations from the above three models as follows.

Utility Investigation of Memory Retention Function
1) The contribution space of +1-th expected utility to the optimal global expected utility ( (Θ)) is so narrow that the maximal -th average utility from myopic strategy almost decides the value of optimal ( (Θ)) for all trials, according to Eq.(3). This is because the red curve is much flatter than the blue curve, i.e., the range of +1th average expected utility curve is much narrower than the range of the -th average utility curve in Fig.4,6,8. With the trials moving on, the red curve is getting even flatter and the contribution space is even narrower. The underlying theoretic cause is that the +1-th expected utility is computed on the term max +1 ∈ { ( +1 | +1 (Θ| , ))} in Eq.(5). It is the maximization operation on the +1-th trial that results in the narrow range of +1-th expected utility.
2) The utility difference between two strategies is rather minor so that the performance improvement from myopic strategy is marginal. Fig.5 ,7,9(b) show the scales of the utility difference are 10 −4 , 10 −5 , 10 −3 and the curve of improvement converges to zero after the narrow peak. This can explain why the information gain curves from three approaches almost overlap as shown in Fig.1-3(c), such that we can even ignore the information gain difference between two strategies.
3) The utility difference ratio is so minor, which indicates the utility difference between two strategies is negligible compared with value of the maximal -th utility of myopic strategy. As shown in Fig.5, 7,9(c), the scales of the ratio of utility difference to the myopic -th maximal utility are 10 −3 , 10 −3 , 10 −2 and the room for performance improvement of 2-trial global strategy over myopic strategy is at most 1.4% of max ∈ ( | (Θ)) (of myopic strategy) only for memory retention model but less than 0.6% for the remaining two models. The experimental data deviate far from our assumption that there is substantial room for performance improvement by adopting global optimization strategy for parameter estimation. This can also explain why there is no apparent performance improvement in MSE curves and information gain curves in Fig.1-3 if we use the maximization of the global expected utility (mutual information) as the objective of 2-trial global strategy. 4) Furthermore, computing a globally optimal policy requires solving Bellman equations, which are generally intractable. In our simulations, we sample over all possible ∈ and ∈ to solve the Bellman equations to get the optimal solution for 2-trial global strategy, which is (| || |) times of computing time of myopic strategy. Therefore, it is not worthy trying 2 -trial global strategy which couldn't substantially increase global expected utility but needs cumbersome computation.

Mathematical Recursion for -trial Global Strategy
Previous simulations turn out that 2-trial global strategy couldn't substantially and fundamentally improve the MSE of estimated parameters and information gain, because the expected utility of the 2 nd step ahead contributes marginally compared to the 1 st step ahead in the optimal global utility. According to Eq.(5), 3-trial global strategy would be rewritten recursively by backward dynamic programming as Eq.(8-10).