Real-time black-box optimization for dynamic discrete environments using embedded Ising machines Authors: Tomoya Kashimata, Yohei Hamakawa, Masaya Yamasaki, Kosuke Tatsumura Published: 2026 ABSTRACT AbstractMany real-time systems require the optimization of discrete variables. Black-box optimization (BBO) algorithms and multi-armed bandit (MAB) algorithms perform optimization by repeatedly taking actions and observing the corresponding immediate rewards without any prior knowledge. Recently, a BBO method using an Ising machine has been proposed to find the best action represented by a combination of discrete values and maximize the immediate reward in static environments. By contrast, real-time systems operate in dynamic environments and necessitate MAB algorithms that maximize the average reward over repeated trials. Due to the enormous number of actions resulting from the combinatorial nature of discrete optimization, conventional MAB algorithms cannot effectively optimize actions for dynamic, discrete environments. Here, we show a heuristic method to maximize the average reward for dynamic discrete environments by extending the BBO method, in which an Ising machine efficiently explores actions while accounting for interactions between variables and environmental changes. We demonstrate the adaptability to dynamic environments of the proposed method in a wireless communication system with moving users.Subject terms: Computer science, Applied mathematics Introduction Real-time systems repeatedly take actions to control environments and receive rewards as a result of those actions. There are two types of rewards: immediate reward and average reward. The former is the reward corresponding to an individual action, while the latter is the average of immediate rewards over all repetitions. Consider problems that aim to maximize either type of reward through sampling cycles, each of which consists of taking an action and observing the corresponding immediate reward, where the reward depends on the action taken in that cycle and not on previous actions. Black-box optimization (BBO) algorithms correspond to immediate reward maximization problems, while Multi-Armed Bandit (MAB) algorithms correspond to average reward maximization problems. In other words, the goal of BBO is to identify high-performing actions under a limited number of sampling cycles, while the goal of MAB is to obtain the highest accumulated reward over repeated sampling, which corresponds to maximizing the average reward. In both algorithms, balancing exploration and exploitation is important for achieving higher rewards. Exploration is the process of searching through untried actions to find better ones, while exploitation is the process of selecting the best action found so far, or actions similar to it, in order to obtain a high reward. MAB and BBO algorithms have been extended to widen their applicable areas for decades. Traditionally, MAB algorithms have focused on discrete problems, and BBO algorithms have been developed mainly for continuous problems. Over time, MAB algorithms have been extended to continuous problems1,2, and BBO algorithms have also been extended to discrete problems3–6. Both algorithms have further been extended to address optimization problems having multiple variables3–11. In BBO, and also in MAB, the environment can be abstracted as a black-box function that maps actions to rewards. Table 1 shows the comparison summary of BBO and MAB algorithms. The table also summarizes the observation requirements and the assumptions on the functional form of black-box functions when these algorithms are applied to multi-variable optimization. To guarantee optimal reward theoretically, some MAB algorithms that optimize multiple variables rely on observing rewards associated with individual variables10,11 or all possible action patterns instead of a single immediate reward2. Other algorithms restrict the functional form of the black-box function, for example, by assuming that it can be represented as a linear combination of predefined functions10. Zimmert and Seldin introduced Factored Bandits9 for MAB problems in environments with many variables using only single-scalar reward observations and place relatively mild restrictions on the reward structure compared with other multi-variable MAB formulations. They assume an identifiability condition under which, for each variable, the optimal atomic action remains invariant to the choices of the other variables. Interactions between variables can influence the reward only within the range where this condition is satisfied. BBO algorithms are applicable to arbitrary black-box functions involving multiple variables and commonly rely only on single immediate reward observations. This property enables BBO algorithms to handle a wide range of discrete and continuous optimization problems. Holland introduced the genetic algorithm (GA)4 for immediate reward maximization, which is one of the classical evolutionary algorithms and has high robustness to complex or nonlinear search spaces. Kitai et al. proposed a BBO algorithm for discrete environments that considers interactions between variables, called Factorization Machine with Quantum Annealing (FMQA)3. In FMQA, a quadratic surrogate model approximates the environment, and a quantum annealer as an Ising machine finds approximate solutions that minimize (or maximize) the model. Ising machines are heuristic solvers to search for approximate solutions expected to yield high immediate reward within a short time, despite the enormous solution space. FMQA and its derivatives have been applied to material discovery3,12–14, hyper-parameter search for simulation15, matrix compression16, and engineering problems17,18. Table 1Comparison of BBO and MAB algorithms for multi-variable optimization, focusing on observation requirements and assumptions on the black-box functionAlgorithm nameDiscrete variablesaMany variablesbObservation typecBlack-box function assumptiondEnvironmental changeeOptimization objectiveRT-BBO (ours)✓✓✓✓✓ dynamicAverage rewardFMQA3✓✓✓✓✗ staticImmediate rewardGenetic Algorithm4,65✓✓✓✓✓ adaptableImmediate rewardTPE5✓✓✓✓✗ staticImmediate rewardREMBO6✓✓✓✓✗ staticImmediate rewardLINEBO7✗✓✓✓✗ staticImmediate rewardCMA-ES8✗✓✗✓✗ staticImmediate rewardPSO66✗Δ✓✓✗ staticImmediate rewardFactored Bandits9✓✓✓Δ✗ staticAverage rewardCombEXP10✓✓✓✗Δ adversarialAverage rewardCUCB11✓✓✗Δ✗ staticAverage rewardESCB10✓✓✗✗✗ staticAverage rewardSliding-window UCB67✓✗✓✗✓ dynamicAverage rewardDiscounted UCB67✓✗✓✗✓ dynamicAverage rewardEXP322✓✗✓✗Δ adversarialAverage rewardBandit Dual Averaging1✗Δ✓✓✓ dynamicAverage rewardFTPL-D/FTPL-A2✗Δ✗Δ✓ dynamicAverage rewardaSuitability for optimization problems with discrete variables. Extensions are not considered.bScalability with respect to the number of variables (more than 50 variables). Extensions are not considered. A triangle mark indicates that the algorithm is expected to degrade in performance as the problem dimensionality increases.cRequired observation type. A check mark indicates bandit feedback (requires only a single scalar reward). A cross mark indicates semi-bandit feedback (requires rewards for each variable) or full-information feedback (requires rewards for all actions).dAssumptions on the black-box (BB) function. A check mark indicates almost no restrictive assumptions on the functional form. A triangle mark indicates weak structural assumptions or mild conditions. A cross mark indicates assumptions that impose a fixed or parametric functional form.eAdaptability to environmental changes. A check mark indicates that the algorithms are designed for dynamic environments. A triangle mark indicates that the algorithms are designed for adversarial environments, where no assumptions are made about how rewards vary over time; however, tracking rapidly changing optima is not their primary objective. A cross mark indicates that the algorithms assume static environments. Note that genetic algorithms (GA) are practically adaptive to environmental changes, even though they are commonly regarded as methods for static environments. Comparison of BBO and MAB algorithms for multi-variable optimization, focusing on observation requirements and assumptions on the black-box function aSuitability for optimization problems with discrete variables. Extensions are not considered. bScalability with respect to the number of variables (more than 50 variables). Extensions are not considered. A triangle mark indicates that the algorithm is expected to degrade in performance as the problem dimensionality increases. cRequired observation type. A check mark indicates bandit feedback (requires only a single scalar reward). A cross mark indicates semi-bandit feedback (requires rewards for each variable) or full-information feedback (requires rewards for all actions). dAssumptions on the black-box (BB) function. A check mark indicates almost no restrictive assumptions on the functional form. A triangle mark indicates weak structural assumptions or mild conditions. A cross mark indicates assumptions that impose a fixed or parametric functional form. eAdaptability to environmental changes. A check mark indicates that the algorithms are designed for dynamic environments. A triangle mark indicates that the algorithms are designed for adversarial environments, where no assumptions are made about how rewards vary over time; however, tracking rapidly changing optima is not their primary objective. A cross mark indicates that the algorithms assume static environments. Note that genetic algorithms (GA) are practically adaptive to environmental changes, even though they are commonly regarded as methods for static environments. Unlike the assumption of stationarity in BBO algorithms, the environment in practical real-time systems may change over time. In such settings, the optimization objective is formulated as the maximization of average reward over repeated trials, and nonstationary MAB formulations are among the suitable choices. Depending on the assumed degree of environmental variability, MAB algorithms are classified as stationary MAB algorithms (not changing), dynamic MAB algorithms (gradually changing)19–21, and adversarial MAB algorithms (with no assumptions about how rewards vary over time)10,22. Studies on dynamic MAB algorithms for complex environments have been conducted1,2, but obtaining strong performance guarantees remains challenging in high-dimensional combinatorial settings. In dynamic environments, only limited sampling data are informative about the current environment, whereas optimizing interacting discrete variables requires a large number of samples. Efficient exploration is therefore required in such settings. In addition to MAB formulations, some BBO algorithms also exhibit adaptability to changing environments. GAs are one such example, updating candidate solutions without maintaining the results of past actions and thereby exhibiting a certain degree of robustness in changing environments. Here, we propose and demonstrate a Real-Time Black-Box Optimization (RT-BBO), a heuristic algorithm for dynamic MAB problems to maximize average reward in which actions are represented by many interacting discrete variables (Fig. 1). BBO refers to the high-dimensional optimization capability inherited from FMQA, while Real-Time reflects both responsiveness to environmental changes and suitability for embedded real-time systems. The method is built on FMQA and replaces the external Ising machine with an embedded one. It is intended for settings where the action space is too large for conventional MAB algorithms and where environmental changes are gradual enough to be tracked by machine learning. RT-BBO extends FMQA to dynamic environments by introducing a dynamic adaptation mechanism. This mechanism consists of a sliding-window dataset, shrink, and an exploration incentive, which together improve responsiveness to environmental changes by maintaining exploration capability. In addition, when multiple immediate rewards are observable, we introduce multi-reward modeling to further improve adaptation. Dynamic discrete environment and real-time black-box optimization algorithm. The dynamic adaptation mechanism enables the quadratic surrogate model to adapt to changes in the discrete environment while also adjusting the exploration-exploitation balance. The embedded Ising machine quickly finds the next action as an approximate solution to maximize the acquisition function that is the sum of the surrogate model and an exploration incentive. The embedded Ising machine broadens the applicability of Ising machines to edge and embedded systems. Instead of the external Ising machine accessed via the internet as seen in FMQA3, we employ a Simulated Bifurcation (SB)-based Ising machine23,24 as the embedded Ising machine. The SB algorithm, which was derived from the classical counterpart of a quantum computer named Quantum bifurcation Machine25, has a high degree of parallelism and enables high-speed implementations using parallel computers26–28. The SB-based embedded Ising machine can find good solutions in a single-shot execution and is fast enough (low latency) to be used for real-time financial trading systems29–31, in-vehicle multiple object tracking systems32, and an iterative optimization algorithm33. We prototype a wireless control system to demonstrate the adaptability of RT-BBO to dynamic environments in practical settings. The assumed wireless cellular network (environment) includes multiple base stations that simultaneously use the same frequency to communicate with their respective users to improve the communication throughput with limited bandwidth. The primary issue in the wireless environment is throughput degradation due to interference between neighboring cells. The control system adjusts beamforming patterns that determine the beam direction and transmission power for each base station (actions represented with interacting discrete variables) and aims to increase the time-averaged total throughput across all base stations (the average reward) by reducing interference. This problem, known as the beamforming coordination problem, has been tackled using deep reinforcement learning34–36 that requires observations of internal states of the environment (environmental observations) other than the rewards. The RT-BBO optimizes the beamforming patterns based solely on the achieved throughputs of all the base stations in spite of the dynamic environment changes due to moving users and the effects of Rayleigh fading. Results Algorithm The main feature of RT-BBO is its adaptability to dynamically changing environments. FMQA3, which forms the basis of RT-BBO, is designed to find semi-optimal actions in static environments. The basic FMQA algorithm builds a quadratic surrogate model that approximates the environment as a black-box function using observed results, and optimizes the variables in the model with an Ising machine to select the next action. To effectively optimize actions in dynamically changing environments, a surrogate model must adapt rapidly to the current environment. Therefore, the core focus of RT-BBO lies in the adaptability of a surrogate model to such environments. RT-BBO heuristically addresses the problem of maximizing average rewards by taking actions and receiving rewards in a dynamically changing environment that requires combinatorial optimization. An example of such a problem is beamforming coordination in wireless cellular networks, where the goal is to determine the optimal beam directions and the transmission power levels of base stations in highly interfering environments (as discussed in Sec. “Demonstration”). Figure 2a illustrates the dataflow of RT-BBO. In each sampling cycle, it takes as input a newly sampled datum, comprising the current action and its corresponding immediate reward, and outputs the next action. As shown in Fig. 1, an immediate reward is represented as a real number (r), and an action in a discrete environment with n control inputs is represented as a vector of discrete values (x1, ..., xn), where each control input xl takes one of dl possible values. This vector (x1, ..., xn) is encoded into, and decoded from, a vector of N spin variables (s1, ..., sN), where N = ∑ldl and si ∈ {−1, 1}, using an encoding/decoding method described in the “Methods” section. A constraint imposed by this encoding/decoding process is incorporated into the acquisition function as a penalty term, Hencoding(s). Dataflow graph of RT-BBO. a RT-BBO for SR (single immediate reward): Shrink is applied to the surrogate model, and then the model is trained to approximate the environment using the sliding-window dataset. The exploration incentive for each spin variable is the square of the number of successive identical values for each spin variable in the sampled data (elapsed sampling cycles since the last change of the spin value). The embedded Ising machine finds the next action that maximizes the acquisition function, which is the sum of the surrogate model, the exploration incentive, and the penalty terms for one-hot encoding. b RT-BBO for MR (multiple immediate rewards): Sub-surrogate models corresponding to each reward are trained independently and then are integrated into one surrogate model. To represent surrogate models, both FMQA and RT-BBO employ a technique known as the factorization machine37, which enables low-rank approximation to prevent overfitting and accelerates training by reducing the number of parameters. The surrogate model r^(s) is defined as: where wi are linear coefficients, and vi∈RK are factor vectors associated with the spin variables si. The factorization machine represents each quadratic coefficient as the inner product 〈vi, vj〉 between the factor vectors associated with si and sj. Each factor vector has dimension K, where K ≪ N, yielding a low-rank approximation. These factorization-machine parameters (the factor vectors vi, the linear coefficients wi, and the bias term w0) are updated through machine learning but are treated as fixed coefficients when passed to an Ising machine. Conversely, the spin variables si are optimized by the Ising machine but serve as input features during model training. As illustrated in Fig. 2a, the parameter updater optimizes the factorization-machine parameters through backpropagation to minimize the prediction error between the surrogate-model outputs and the observed immediate rewards, while the spin variables are optimized separately by the Ising machine. The detailed formulation of the factorization machine and the training procedure is provided in the “Methods” section. We assess the effectiveness of RT-BBO by evaluating its applicability to dynamically changing environments. RT-BBO is designed to be suitable for problems composed solely of discrete variables with a small number of possible values, problems composed solely of discrete variables with a small number of possible values, problems with a sufficiently large number of variables such that exhaustive search is impractical, problems with a sufficiently large number of variables such that exhaustive search is impractical, problems not dominated by excessively high-order interactions, problems not dominated by excessively high-order interactions, problems under a no-context, bandit-feedback setting, where each sampling provides only a single scalar reward without any contextual information, and problems under a no-context, bandit-feedback setting, where each sampling provides only a single scalar reward without any contextual information, and problems in which environments change over time. problems in which environments change over time. The first four conditions are inherited from FMQA, whereas the last condition is specific to RT-BBO. Regarding the limitation on the interaction order, excessively high-order interactions would require an impractically large number of samples in BBO under bandit feedback, and even in white-box settings, such interaction structures remain challenging to optimize using current methods. To examine adaptability under this problem setting, we construct test problems whose black-box functions consist of binary (or spin) variables and change continuously over time. Specifically, each black-box function r(x) is defined as a weighted combination of two D-dimensional polynomial functions, denoted by rA and rB: where the mixing parameter α varies gradually from 0 to 1 across sampling cycles. D represents the interaction order between binary variables. When D is 2 (quadratic), r(x) is an Ising model or a quadratic binary optimization problem. As a baseline, we introduce a simple FMSB method, which combines a factorization machine with an SB-based Ising machine but does not incorporate the dynamic adaptation mechanism. For a fair comparison, the surrogate model of the baseline is trained using randomly selected samples from the cumulative dataset, while the number of training samples per cycle is matched to that of RT-BBO in order to equalize computational cost. Figure 3a illustrates the improvement in adaptability on dynamically changing Ising models (D = 2), where environment changes occur during sampling cycles 2000–4000, as the features of the dynamic adaptation mechanism (sliding-window dataset, shrink, and exploration incentive, which are detailed below) and multi-reward modeling are added sequentially to the baseline. To be consistent with the setting of the multi-reward modeling, both rA and rB are constructed as sums of ten randomly generated Ising models. The Ising energy of each individual model corresponds to one of the multiple immediate rewards in Fig. 2b, whereas the sum of the ten Ising energies corresponds to the single immediate reward in Fig. 2a. To allow comparison between stable and changing environments, the black-box function is fixed to rA during sampling cycles 0–2000 and to rB during cycles 4000–6000. Adaptability of the RT-BBO algorithms (i.e., FMSB with the dynamic adaptation mechanism) in a dynamically changing environment. a Comparison of normalized immediate rewards when features that constitute the dynamic adaptation mechanism (S sliding-window, H shrink, I exploration incentive, MR multi-reward modeling) are added one by one to the baseline (i.e., FMSB without dynamic adaptation mechanism). A black-box function is quadratic (D = 2) and fixed during 0–2000 and 4000–6000 sampling cycles and changing in 2000–4000 sampling cycles. The number of variables is 100 (N = 100). All rewards are normalized with respect to the reward obtained by directly optimizing the target Ising model using the SB-based Ising machine as a white-box solver (100%). Under the coefficient-generation setting adopted in this study, the expected reward of Random selection is 0%. The results are averaged over 50 independent trials for the same problem. The genetic algorithm and the factored bandit are shown as references. b Cumulative proportion (ratios) of the top 100 frequently sampled actions out of 6000 actions selected in a. If a line passes through the lower right (/upper left), it indicates a preference for exploration (/exploitation). In addition, to demonstrate broader applicability, we evaluate RT-BBO on randomly generated polynomial functions with interaction orders (D) ranging from one to five and with 30–2000 variables (N) in Fig. 4. Both rA and rB include all interaction terms up to degree D, with coefficients sampled randomly. In Fig. 4, for larger interaction orders, the maximum number of variables is reduced due to memory requirements for the coefficients and constraints on evaluation time. Each black-box function changes gradually over 0–10000 sampling cycles. Because any finite discrete function can be represented as a polynomial over binary variables while preserving its interaction order, these experiments provide a systematic testbed for evaluating a broad class of discrete optimization problems with varying interaction orders. The code to generate the benchmark problems evaluated in Fig. 4 and the corresponding experimental results are provided as Supplementary Data 1. The implementation details and hyperparameter settings are provided in the “Methods” section and Supplementary Information. Systematic evaluation of RT-BBO for SR (RBS), the baseline method (BL), the factored bandit (FB), the genetic algorithm (GA), and random selection (RND) on dynamic black-box polynomials. Each problem instance consists of two D-dimensional polynomials with n binary (0–1) variables. The coefficients are randomly generated from a Gaussian distribution with mean 0 and variance 1. One polynomial gradually transitions to the other over 10000 sampling cycles in a linear manner. Unlike Fig. 3, the reported values are absolute, not relative, and lower values indicate better performance. Results are averaged over 10 independent runs. Note that near the center of the horizontal axis, where the two polynomials contribute equally, coefficient averaging reduces the effective variance, thereby producing a mound-shaped profile irrespective of optimization quality. The first key mechanism that enables adaptation in RT-BBO is a sliding-window dataset. In FMQA, proposed for static environments (i.e., a static BBO), the surrogate model is trained using a cumulative dataset that records all historical pairs of actions and immediate rewards. In contrast, RT-BBO (Fig. 1) for dynamic environments constructs its surrogate model using a sliding-window dataset, which retains only the most recent data within a fixed window size, discarding older data as new samples arrive. The sliding-window feature improves adaptability as shown in the +sliding-window (B + S) in Fig. 3a, compared with the baseline. However, the optimization performance of the +sliding-window (B + S) degrades compared to the baseline for the static problem (during 0–2000 sampling cycles). This performance degradation arises from insufficient exploration. Figure 3b depicts the cumulative proportions of the top 100 most frequently sampled actions among the 6000 actions selected in Fig. 3a. When the sliding-window dataset is used alone, the system tends to repeatedly sample a limited set of actions. This behavior can be explained as follows: once the surrogate model captures the characteristics of a local solution, it becomes biased toward sampling actions in the vicinity of that solution, thereby missing opportunities to explore potentially better alternatives. To mitigate this issue, we introduce shrink and an exploration incentive, as discussed next. To encourage exploration and enhance adaptability, it is effective to attenuate the influence of previously learned surrogate models. RT-BBO repeats sampling cycles (hereafter, outer loop), each of which includes training iterations to update the surrogate model (hereafter, inner loop). See Box 1 for more details. Shrink, applied once per sampling cycle before the inner-loop training (i.e., once per outer loop), scales the model parameters by a coefficient slightly less than one (cshrink). This operation acts as an explicit forgetting mechanism that reduces model inertia and enhances responsiveness to recent observations, in contrast to conventional weight decay, which is primarily used to prevent overfitting. Shrink is applied only to the quadratic coefficients vik, while exploration in the linear part is instead promoted by the exploration incentive. To encourage exploration, RT-BBO also introduces an incentive mechanism that promotes diverse sampling. In the FMQA framework3, the Ising machine is used to find the minimizer (or maximizer) of the surrogate model, focusing solely on exploitation. In dynamic environments, where the optimal action may change over time, continuous and effective exploration is necessary to adapt to these changes. The proposed exploration incentive mechanism encourages spin flips based on the elapsed sampling cycles since their last change, helping to avoid getting trapped in local optima. The exploration incentive, Hexploration(s), is defined as: where Ii is the incentive intensity for each spin variable (si), and cexploration controls the overall intensity of the exploration incentive. The incentive calculation unit in Fig. 2a computes the intensity (Ii) using counters that track how many consecutive sampling cycles each spin variable has taken the same value repeatedly. Each counter increments if the current spin value matches the previous one, and resets to zero otherwise. The converter in the unit squares each counter value to emphasize longer repetitions, then multiplies each squared value by the corresponding last spin value to determine the direction of the incentive. As a result, the exploration incentive encourages a spin to flip when it has kept the same value for too long. To keep the average number of consecutive identical spin values (i.e., counter values) within a desirable range (a hyperparameter), cexploration is dynamically adjusted: it increases when the average exceeds the upper bound of the range and decreases when it falls below the lower bound. This mechanism improves robustness to variations in the dynamic range of the surrogate model parameters. The acquisition function of RT-BBO (see Fig. 1) is the argmax of the sum of the updated surrogate model, the exploration incentive, and the encoding penalty. The embedded Ising machine finds a spin configuration (s) that maximizes the acquisition function, and the spin configuration is used as the next action. This optimization problem is expressed by: As the embedded Ising machine, we use an SB-based Ising machine, which is particularly suitable for RT-BBO due to its high speed, making it appropriate for real-time applications29–33. The SB algorithm offers greater inherent parallelism than simulated annealing-based methods and can be accelerated using parallel computing26,27. Note that while Eq. (4) is formulated as a maximization problem, Ising machines are typically designed for minimization. To align with the actual RT-BBO implementations, the argmax in Eq. (4) is converted to argmin, and the signs of some terms are adjusted accordingly. In this paper, the FMSB enhanced with the sliding-window dataset, the shrink, and the exploration incentive is referred to as RT-BBO for SR (single immediate reward). Some environments provide not one but multiple observable immediate rewards (r(1), r(2), …, r(M), hereafter sub-rewards). To handle such environments, we further introduce multi-reward modeling, in which these sub-rewards collectively form the total immediate reward to be optimized through a linear combination: where pm denotes the weight of the m-th sub-reward (typically pm = 1). We refer to an RT-BBO equipped with multi-reward modeling as RT-BBO for MR. In RT-BBO for MR, each sub-reward r(m) is independently modeled by a sub-surrogate model r^(m), and the integrated surrogate model is obtained as Fig. 2b illustrates the dataflow of RT-BBO for MR, where sub-rewards are stored in the dataset and used to independently train sub-surrogate models. The multi-reward modeling decomposes a large approximation problem into several smaller ones, improving the overall approximation quality, as shown in Figs. 3 and 5. Experimental results of the prototype wireless control system. a Snapshots showing the situation of moving users and base stations: The users randomly move along the edges of the cells. There are 37 base stations in total. b Average reward improvement with dynamic adaptation mechanism (averaged over the entire sampling cycle): There is little difference in performance between the baseline (FMSB without dynamic adaptation mechanism) and the case where only the sliding-window dataset is introduced. Performance improves with the use of shrink, exploration incentive, and multi-reward modeling. c Beamforming patterns for each base station. Four beam shapes and three transmission power levels yield nine patterns per base station. For 37 base stations, this corresponds to 333 spin variables (N = 333). d Achieved throughput in the environment (single immediate reward) over time: The total throughput across all base stations achieved by RT-BBO for MR (multiple rewards) and for SR (single reward) is compared with that achieved by the baseline, the genetic algorithm, the factored bandit, and the random selection. Each point is averaged over 50 independent trials. Supplementary Movie 1 provides a video of the user movement and the optimization process. Evaluation on randomly generated polynomials Figure 3 shows that introducing shrink and the exploration incentive together with the sliding-window dataset significantly improves both optimization performance and adaptability. Furthermore, multi-reward modeling provides a modest additional improvement. Compared with the SB-based Ising machine, which directly optimizes the target Ising model and is normalized to 100%, RT-BBO for MR achieves approximately 90% of the resulting Ising energy in static environments and maintains around 80% even in dynamic environments. Since the problem does not satisfy the assumptions required by the factored bandit, the factored bandit fails to achieve meaningful optimization under this setting. The GA exhibits relatively strong optimization performance; however, it does not reach the performance level of RT-BBO. Figure 4 presents the evaluation results on varying interaction order and varying number of variables. The results indicate that RT-BBO and the GA exhibit robustness to environmental changes, whereas the baseline does not. The performance of the factored bandit is comparable to that of the random selection, and no clear optimization effectiveness is observed because this problem setting does not meet the assumption of the factored bandit. When the number of variables is small, the GA can demonstrate favorable performance; however, when the number of variables is approximately 200 or more, RT-BBO consistently outperforms the GA. As the number of variables increases further, the performance advantage of RT-BBO over the GA becomes more pronounced. Moreover, the results suggest that RT-BBO remains effective even for problems whose true interaction order (D) exceeds that of the quadratic surrogate model used internally. When the number of sampling cycles is small, the baseline outperforms RT-BBO in some settings, suggesting that the additional mechanisms introduced to enhance tracking may have led to performance degradation in static-environment optimization. Demonstration We demonstrate the adaptability of RT-BBO in optimizing wireless communication by developing an RT-BBO-based beamforming optimizer that interacts with a simulator of a dynamically changing wireless environment. This simulator simulates the internal states of a cellular network, consisting of base stations and mobile users. The actions, represented by discrete variables and determined by RT-BBO, correspond to the control operations of the base stations. After each action, an immediate reward, which is defined as the total communication throughput between the base stations and users, is observed. The function that maps actions to immediate rewards is highly complex and is far from a quadratic discrete function. In RT-BBO, this function is approximated using a quadratic surrogate model. Figure 5 and Supplementary Movie 1 show the problem setting and the experimental results. Figure 5a illustrates a small-cell network in which multiple base stations are located at the centers of cells and are assumed to operate on the same communication frequency to maximize throughput under limited bandwidth. Signals from the base stations interfere with one another. This interference is mitigated using a beamforming technique, which allows each base station to direct radio waves in specific directions by adjusting the amplitude and phase of signals transmitted from a set of antenna elements on a base station. Note that only the one-way transmission of radio waves from the base stations to the users is considered in this demonstration. As shown in Fig. 5c, each base station has nine predefined beamforming patterns, consisting of four directional shapes (a codebook) and three transmission power levels (strong, weak, and no transmission). The variable xi denotes the index of the beamforming pattern selected for the i-th base station. The set of beamforming patterns for all base stations constitutes the action for RT-BBO, represented by n discrete variables (x1, ..., xn), where n is the number of base stations. In our experiment, n = 37, resulting in a total of 937 ≈ 2.03 × 1035 possible actions. As we use nine spin variables for each xi (see the subsection entitled one-hot encoding in the “Methods” section), the total number of spin variables (N) is 333. The number of users is equal to the number of base stations n, and each base station communicates with one user located within its cell. Each pair may experience interference from all other base stations. This setting is used in reinforcement learning studies on beamforming coordination problems35,36. The users continuously move along the edges of the cells, as shown in Fig. 5a. Every 2000 sampling cycles, the user either remains at the current location or moves to an adjacent corner. The choice is determined by a pseudo-random value generated by the simulator and is fixed across each experiment. The communication throughput for each base station-user pair is calculated using a wireless communication model, consistent with the one used in ref. 35. In this model, the amplitude and phase of the signal transmitted by the i-th base station with beamforming pattern xi are represented by a complex vector wi(xi). The channel vector between the i-th base station and the j-th user, which captures propagation effects including Rayleigh fading, is denoted by hi,j. The received signal at the j-th user from the i-th base station is given by hi,j†wi(xi). The throughput of the k-th base station, Ck, is calculated as: where ψk is the signal-to-interference-plus-noise ratio (SINR) for the k-th base station-user pair, and x=(x1,...,xn)T represents the beamforming pattern vector. The SINR is computed as: which is the ratio of the received signal power from the intended base station to the sum of interference from other base stations and background noise (σ2). The per-base-station throughput serves as the sub-rewards for RT-BBO for MR, and the total throughput, ∑kCk(x), serves as the single immediate reward for RT-BBO for SR. The channel vector hi,j accounts for both the effects of user mobility and Rayleigh fading, the latter of which models fluctuations in signal amplitude and phase caused by multipath propagation. For further details on the wireless simulator settings, refer to the “Methods” section. We compare the average rewards, measured as achieved throughput, of RT-BBO-based beamforming optimizers with those of the factored bandit, the GA, and a random selection method. The factored bandit and the GA optimize 37 variables, each taking one of nine possible values (Fig. 5c). Implementation details and hyperparameter settings are provided in Supplementary Information. The random selection method uniformly selects beamforming patterns for each base station from the nine predefined options. We evaluated five FMSB variants, beginning with a baseline and incrementally incorporating the following techniques: sliding-window dataset, shrink, exploration incentive, and multi-reward modeling. Figure 5b shows the time-averaged total throughput across all base stations. All FMSB variants outperform the random selection method. Both RT-BBO for SR and RT-BBO for MR achieve higher throughput than the competing methods. The baseline (B) and +Sliding-window (B + S) variants exhibit similar performance. The benefits of shrink, exploration incentive, and multi-reward modeling are evidenced by the progressive performance improvement obtained as these techniques are added. Figure 5d shows the throughput over sampling cycles. RT-BBO maintains high throughput in this dynamic environment. Although the baseline performs well in the early phase, its performance declines following the environmental change. Consistent with Fig. 3a, RT-BBO for MR outperforms RT-BBO for SR and retains a slight advantage throughout the evaluation. The GA exhibits some adaptability to the environmental change; however, both the RT-BBO variants consistently achieve higher throughput. The factored bandit does not perform well in this environment, likely because its underlying assumptions are not well-matched to the problem setting. Discussion We have proposed RT-BBO, a heuristic algorithm to maximize average reward over time for dynamic environments in which each action is represented by many interacting discrete variables. Our main finding is that RT-BBO is effective in a problem regime that is not well addressed by existing methods: dynamic, high-dimensional discrete optimization under bandit feedback (i.e., only a single scalar reward is observed for each action). RT-BBO extends an existing discrete BBO algorithm for static environments (FMQA3) by incorporating dynamic adaptation mechanisms, namely a sliding-window dataset, shrink, and exploration incentive. These mechanisms enable the quadratic surrogate model to adapt to changes in the discrete environment while adjusting the exploration-exploitation balance. RT-BBO relies on an SB-based low-latency embedded Ising machine to find the next action by maximizing an acquisition function that combines the surrogate model and the exploration incentive. Across both the systematic benchmark problems based on randomly generated polynomial functions over binary variables and the prototyped wireless-control system for a cellular network, RT-BBO demonstrated stronger adaptability than the FMQA-based baseline method and became increasingly advantageous over a GA as the number of variables increased. These results suggest that RT-BBO is a practical approach for real-time optimization in dynamic discrete environments, particularly when actions comprise many interacting variables and only bandit feedback is available. There are two possible directions for future work. The first direction is to apply RT-BBO to various real-time systems to clarify its applicability; for example, recommendation systems for advertisements38 and dynamic pricing systems for online shops39. The second direction is to enhance RT-BBO to consider external context as well. This extension enables the surrogate model to adapt its behavior in response to changes in external conditions, with potential applications in personalized recommendations40 and stock investments41. Methods Ising model and Ising machine Many combinatorial optimization problems can be reduced to the energy minimization problem of the Ising model42. The energy in the Ising model is expressed as Here, the N variables si, called spin variables, take binary values of +1 and −1. A computer specialized for computing a spin configuration that minimizes this energy is called an Ising machine. Ising machines aim to quickly find approximate solutions. Note that calculating the exact solution in a practical (polynomial) time is still not guaranteed with current technology43. Ising-machine algorithms are classified into quantum algorithms44 and classical algorithms45–56. Ising machines based on quantum algorithms are difficult to embed in real-time systems because they require special equipment like refrigerators. Although some Ising machines based on classical algorithms, such as simulated annealing-based Ising machines46–48, could potentially be embedded in real-time systems, there have been few studies on embedded Ising machines. SB algorithms are quantum-inspired classical oscillator-based algorithms. The SB algorithm simulates adiabatic time evolutions of nonlinear Hamiltonian systems having oscillators corresponding to spins in the Ising model. Its Hamiltonian is designed to exhibit bifurcation phenomena. The algorithm used in this paper is ballistic SB24, which performs well at calculating approximate solutions in a short time29–33. The positions xi and momenta yi of oscillators corresponding to the spin variables are updated according to the following equations. where a0, c0, η, and Δt are hyper-parameters, Δt is the time step of simulation of SB, and sgn(x) is the sign function. The parameter atk evolves linearly from 0 to 1. The SB-based Ising machine repeats this update procedure for a predetermined number of iterations (1000 in this work). The output spin values are obtained by binarizing the final positions. The SB algorithm implementation adopted in this study follows ref. 57 and is realized as a hard-coded circuit architecture based on ref. 26. This implementation achieves high-throughput parallel processing, executing 4096 parallel 32-bit floating-point multiply-accumulate operations at 239 MHz. Other FPGA-based implementations can be found in refs. 58,59. Factorization machine Factorization Machines (FMs) are models designed for supervised learning tasks. They effectively capture feature interactions within a feature vector using a low-rank approximation37. While general FMs are capable of modeling arbitrary-order interactions among features, we focus on second-order interactions because the surrogate model employed in this work is quadratic. To efficiently represent these second-order interactions, FMs approximate a square matrix in RN×N using a low-rank decomposition. This is achieved through a matrix of factor vectors, denoted as V = (vik), where V∈RN×K. The compressed representation is then expanded into a square matrix J via the product J=VVT. Each element of J is computed as: where vi is the factor vector corresponding to the i-th feature, and vik is its k-th component. In other words, each pairwise interaction Jij is approximated by the similarity between the i-th and j-th feature vectors. The dimensionality K of the factor vectors determines the rank of the reconstructed matrix J and is typically much smaller than N (e.g., K = 6 in this work). This low-rank factorization reduces the number of parameters required to model quadratic interactions from (N2–N)/2 to NK. Such compression not only accelerates the learning process but also mitigates overfitting, which is an important consideration when working with limited data. One-hot encoding Before and after the core RT-BBO algorithm, one-hot encoding and decoding are applied to extend RT-BBO to handle discrete variables that take more than two values, since Ising machines take spin variables that take either one of +1 or −1. The one-hot encoding converts n discrete values (x1, ..., xn) representing the selected action into N spin values (s1, ..., sN) before adding them to the dataset, and conversely converts the spin values output by Ising machines into discrete values in the original format representing the next action. Here, we assume that the l-th discrete variable (xl) has dl possible values. Under this encoding, the l-th discrete variable (xl) is represented by a set of dl spin variables. Within each set, only one spin variable corresponding to the value of xl is +1 at a time, while the other variables are set to be −1. Thus, N spin variables are used to represent n discrete values (N=∑l=1ndl). To enforce this, penalty terms are added to the acquisition function, following ref. 60. The penalty term is described as where cencoding is a coefficient to control the strength of the constraints. High cencoding prevents Ising machines from outputting solutions that violate the constraints. The coefficient cencoding should be adjusted because too high or too low a coefficient degrades the quality of solution output from Ising machines. The proposed exploration incentive can work with the one-hot encoding; in the scheme of the one-hot encoding, the exploration incentive encourages Ising machines to explore values that have not been selected recently. Model training unit The model training unit updates the parameters of the surrogate model based on the data in the sliding-window dataset. Box 1 outlines the procedure used in the model training unit, which consists of two main parts: shrink and a parameter updater. The parameter updater is based on the original FMQA, with several modifications to improve computational efficiency and robustness against noisy data. First, we adopted the mini-batch method, which uses only a subset of the extracted data in the dataset for gradient calculation (20 data points for our implementations), instead of using all the data in the dataset to reduce computational cost (the sliding-window size is 50). The number of extracted data points (mini-batch size) should be adjusted experimentally, because if it is too large, the computational cost increases, whereas if it is too small, gradient stability is lost. For example, if the noise level in the immediate reward is high or the black-box function is very complex, using more data points can help stabilize the gradient61. During each sampling cycle, the gradient update is repeated Ntrain times (200 for our implementations). While a larger Ntrain increases computational cost, it can also lead to better performance and should be chosen based on the trade-off between sampling frequency and optimization quality. Second, the parameter updater employed the log-cosh loss function62, defined as where r(s) is the immediate reward and r^(s) is the prediction by the model. Compared to the mean squared error used in the original FMQA, the log-cosh loss is more robust to outliers62. The gradients of the loss with respect to the model parameters are given by Note that, for i = 0 in Eq. (16), si is set to +1 so that the bias term w0 can be handled in the same form as the linear coefficients. The gradient expression in Algorithm 1 is a computationally efficient form derived from Eq. (1). Since ∑jvjksj are independent of i, the partial derivatives with respect to vik are calculated efficiently by precomputing zkd. The computational complexity for processing a mini-batch can be reduced to O(LbatchNK) by this precomputing37. The parameters (vik and wi) are updated using a backpropagation method, which updates the parameters according to the gradients. More specifically, the model training unit updates the parameters using the Adam optimizer63 shown in Box 2. The Adam optimizer adjusts its effective learning rate based on estimates of the first- and second-order moments. For the hyperparameters used in the experiments, refer to Supplementary Information. Input: Parameter θ, moment m, velocity v, gradient g, coefficients β1, β2, α, ϵ Output: Updated parameter θ, moment m, velocity v /*The moments and velocities are maintained for each parameter */ /*and initialized to zero at the beginning of the first sampling cycle.*/ m ← β1 ⋅ m + (1 − β1) ⋅ g v ← β2 ⋅ v + (1 − β2) ⋅ g2 m^←m/(1−β1t) v^←v/(1−β2t) Δθ←α⋅m^/(v^+ϵ) θ ← θ − Δθ; /*In the case of weight decay, θ ← cshrinkθ − Δθ */ Implementation The FMSB variants, including the RT-BBO used in our experiments, are implemented on a server equipped with both an FPGA board and a GPU board. The GPU serves as a machine learning accelerator for the model training unit, while the FPGA serves as an embedded Ising machine. Higher sampling rates increase the volume of data used to approximate the surrogate model that reflects the current environment, which is expected to enhance optimization performance. Figure 6 shows the computation time per sampling cycle in the beamforming optimization problem (see Fig. 5). RT-BBO for SR achieves 26.7 ms per sampling cycle (37.4 sampling cycles per second), and RT-BBO for MR achieves 38.5 ms per sampling cycle (26.0 sampling cycles per second) when 37 sub-rewards are used. Note that the original FMQA3 is expected to require more time than the baseline, as it updates parameters using the entire dataset without employing mini-batch techniques. Comparison of computation time per sampling cycle in the Demonstration experiments (Fig. 5). The baseline requires more time than the other methods, except for RT-BBO for MR, because the data used for training are randomly selected from the large dataset, whereas the other FMSB variants use the limited data in the smaller sliding-window dataset in the recorded order. RT-BBO for MR took more time because it incurs roughly 37 times the training cost of RT-BBO for SR, corresponding to the number of sub-rewards. Note that each computation time includes the computation time for the wireless simulation (corresponds to the time of random selection). The computation flow in a single sampling cycle is as follows. First, the CPU receives the latest sampling datum from the environment and stores it in the sliding-window dataset. The CPU also computes the exploration incentive and transfers both the dataset and the incentive to the GPU. The GPU then updates the surrogate model through the model training unit, which applies the shrink followed by parameter updates using the Adam optimizer. In the case of the multi-reward modeling, all sub-surrogate models are trained in parallel and integrated into a single surrogate model. Next, the acquisition function is computed on the GPU as the sum of the surrogate model output, the exploration incentive, and penalty terms for one-hot encoding. This acquisition function is transferred via main memory to the FPGA in the form of an Ising model. The embedded Ising machine on the FPGA computes an approximate solution to the Ising model. Finally, the CPU simulates the environment using the action corresponding to the obtained solution. The hardware includes an NVIDIA GeForce RTX 4060 Ti GPU with 4352 CUDA cores (driver version: 550.90.07), an Intel FPGA Programmable Acceleration Card D5005 with a 2800K-LE Stratix 10 FPGA, and two Intel Xeon E5-2667 v4 CPUs. The model training unit is implemented in CUDA (version 12.4) and runs on the GPU. The conversion between discrete and spin variables, the calculation of constraint terms, and the exploration incentive computations are implemented in Python, while the remaining components are written in C++ and executed on the CPUs. For the SB implementation on FPGA, see Ising Model and Ising machine in this “Methods” section. For the hyperparameters used in the experiments, refer to Supplementary Information. Wireless environment simulator The wireless-environment simulation is based on the equations and descriptions in ref. 35. The self-correlation coefficient ρ, which represents the strength of Rayleigh fading, is set to 0.90, corresponding to a sampling interval of 10 ms, a movement speed of 5 km/h, and a communication frequency of 2 GHz in an ideal environment64. In the cellular network, the cell radius is 200 m, the number of antenna elements per base station is 3, and the number of multipaths (for Rayleigh fading) is 4. The attenuation based on communication distance is set to 120.9+37.6log10d dB, where d is the distance between the user and the base station in km. The environment simulator was written in C++ and runs on the CPU. Supplementary information Supplementary Information Description of Additional Supplementary Files Supplementary Data 1 Supplementary Movie 1 Transparent Peer Review file Acknowledgements The authors would like to thank Daisuke Uchida, Kentaro Taniguchi, and Duckgyu Shin for their advice. Author contributions All authors collaboratively discussed and determined the direction of this work. T.K. and K.T. conceived the idea of extending FMQA to real-time systems. K.T., Y.H., and M.Y. managed this project and advised on the SB-based Ising machine. T.K. devised the algorithm of RT-BBO, implemented RT-BBO and the wireless simulator, and evaluated them. T.K. and K.T. wrote this manuscript. Peer review Peer review information Nature Communications thanks the anonymous, reviewers for their contribution to the peer review of this work. A peer review file is available. Data availability All relevant data are included in the manuscript and the Supplementary Information. To facilitate comparison with Fig. 4, sample code for evaluating optimization algorithms on randomly generated polynomial functions and the corresponding experimental results are provided as Supplementary Data 1. Additional data are available from the corresponding author upon reasonable request. Code availability The extensions made in this work, relative to the baseline method (FMQA3), as well as the hyperparameter settings, are described in the main text using pseudocode and mathematical formulations. The source code used to generate the benchmark instances and perform the evaluation in Fig. 4 is provided as Supplementary Data 1. Competing interests T.K., Y.H., M.Y., and K.T. are listed as inventors on three patent applications related to this work, filed by Toshiba Corporation in Japan (P2024-018133 and P2025-007789) and in the United States (19/044818). Footnotes Publisher’s note Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations. Supplementary information The online version contains supplementary material available at https://doi.org/10.1038/s41467-026-76069-3. References Associated Data Supplementary Materials Supplementary Information Description of Additional Supplementary Files Supplementary Data 1 Supplementary Movie 1 Transparent Peer Review file Data Availability Statement All relevant data are included in the manuscript and the Supplementary Information. To facilitate comparison with Fig. 4, sample code for evaluating optimization algorithms on randomly generated polynomial functions and the corresponding experimental results are provided as Supplementary Data 1. Additional data are available from the corresponding author upon reasonable request. The extensions made in this work, relative to the baseline method (FMQA3), as well as the hyperparameter settings, are described in the main text using pseudocode and mathematical formulations. The source code used to generate the benchmark instances and perform the evaluation in Fig. 4 is provided as Supplementary Data 1.