JP7634222B2 - Optimization device, optimization method, and optimization program - Google Patents

Description

The present invention relates to an optimization device, an optimization method, and an optimization program.

Hidden Markov models, Bayesian estimation, and reinforcement learning are used as approaches to solving the problem.

For example, Patent Document 1 discloses a hidden variable model estimation device that can achieve high-speed model selection even when the number of model candidates increases exponentially along with the number of hidden states and types of observation probabilities. This hidden variable model estimation device has a variational probability calculation unit that calculates the variational probability by maximizing a reference value defined as the lower bound of an approximation obtained by Laplace approximating the marginal log-likelihood function with respect to an estimate for the complete variables. The hidden variable model estimation device also has a model estimation unit that estimates an optimal hidden variable model by estimating the type of observation probability and parameters for each hidden state, and a convergence determination unit that determines whether the reference value used when the variational probability calculation unit calculates the variational probability has converged.

Patent Document 2 also discloses a system for selecting an action to be performed by a reinforcement learning agent that interacts with an environment. The system includes a processing step configured to process according to a current hidden state of a goal regression neural network (NN) to generate an initial goal vector in a goal space for a time step and update the internal state of the goal regression NN.

Reinforcement learning is a method in which the reward and next state are determined for each combination of state and action.

Re-table 2013/179579 publication Special Publication No. 2020-508524

Within the framework of reinforcement learning, a method called Q-learning is typically used. Q-learning is defined for discrete states, but real-world problems often have a huge number of observed states, making learning difficult using standard Q-learning.

In recent years, Deep Q Network (DQN), which combines an advanced version of Q-learning with a multi-layered neural network, has been shown to be effective in a variety of tasks. Although trained DQNs show very high performance, it is unclear how the internal state of the operation is interpreted in a black box given the environment. In addition, although performance after training is high, many iterations are required for learning, and little consideration is given to effectively obtain rewards during learning.

On the other hand, algorithms using Bayesian estimation that effectively learn state transitions while estimating important hidden states from a huge amount of observations are also widely known. However, this method treats reward prediction and state transitions separately, which means that states unrelated to rewards are analyzed in detail, and depending on the problem setting, this can result in a large amount of waste in memory and calculations. In addition, Thompson sampling is known as a general-purpose method that balances learning and reward acquisition in a framework called the multi-armed bandit problem, but it cannot be directly applied to complex problems.

The present invention was made in consideration of the above circumstances, and aims to provide an optimization device, an optimization method, and an optimization program that can improve the efficiency of calculations.

In order to achieve the above object, the optimization device according to the present invention uses a system in which the state transition law, the observation state law, and the reward law are defined, and in a model in which the agent's actions are repeated to learn each of the laws and obtain a reward, the optimization device holds an estimate of a unique hidden state in which the hidden state has been changed to a predetermined state, and a current state in the unique hidden state, and the observation state law uses an observation at time t as a condition for conditional probability to obtain the unique hidden state, and the state transition law uses the unique hidden state at time t and the unique hidden state at time t+1 as conditions for conditional probability to obtain the agent's action. The optimization device includes: a setting unit that defines the state transition law and the observation state law so that the unique hidden state is obtained by using an observation at time t as a condition for conditional probability, and the state transition law defines the state transition law and the observation state law so that the agent's action is obtained by using the unique hidden state at time t and the unique hidden state at time t+1 as conditions for conditional probability; and an update unit that determines the agent's optimal action based on the Bellman equation, assuming a distribution of each parameter representing the probability sampled based on each of the laws, and an estimate of the current state, and repeatedly updates the estimate of the current state and the distribution using each of the laws by a posterior distribution obtained by applying Bayes' theorem to the observation information including the laws, a predetermined prior distribution, and the optimal action.

The optimization method according to the present invention uses a system in which the state transition law, the observation state law, and the reward law are defined, and in a model in which the agent's actions are repeated to learn each of the laws and obtain a reward, the system holds an estimate of a unique hidden state in which the hidden state has been changed to a predetermined state, and an estimate of the current state in the unique hidden state, the observation state law uses an observation at time t as a condition for conditional probability to obtain the unique hidden state, the state transition law defines the state transition law and the observation state law so as to obtain the agent's action using the unique hidden state at time t and the unique hidden state at time t+1 as conditions for conditional probability, and determines the agent's optimal action based on the Bellman equation, assuming a distribution of each parameter representing the probability sampled based on each of the laws and an estimate of the current state, and causes a computer to execute the following process: updating the estimate of the current state and the distribution using each of the laws using a posterior distribution obtained by applying Bayes' theorem to the observation information including each of the laws, a predetermined prior distribution, and the optimal action.

The optimization device, optimization method, and optimization program of the present invention have the effect of making it possible to improve the efficiency of calculations.

FIG. 13 is a diagram showing an example of a transition diagram of a conventional method and a transition diagram of the method of the present embodiment regarding estimation of states and rules. FIG. 2 is a diagram illustrating the functional configuration of an optimization device according to an embodiment of the present invention. FIG. 2 is a block diagram showing a hardware configuration of the optimization device. FIG. 4 is a diagram showing an optimization processing routine of the optimization device according to the embodiment of the present invention. 11 is a graph showing an example of experimental results of the method of this embodiment and other methods. This is a table showing the number of hidden states at convergence in an experiment.

The following describes an embodiment of the present invention in detail with reference to the drawings.

First, we will explain the principles of the embodiment of the present invention.

FIG. 1 is a diagram showing an example of a transition diagram of a conventional method and a transition diagram of the method of this embodiment regarding the estimation of states and rules. First, as a basic principle, the estimation of states and rules of the conventional method will be described. The conventional method and the method of this embodiment have in common an internal model that uses a system (transition diagram) in which each rule is defined by the state transition rule, the observation state rule, and the reward rule, and repeats the actions of the agent to learn each rule and obtain a reward. The upper part of FIG. 1 is a transition diagram of the estimation of states and rules of the conventional method. Assume that an environment is given in which an observation o _t is obtained at time t, and when an action a _t is selected, a reward r _t and a next observation o _t+1 are obtained. In this case, it is desired to make a selection such that the long-term reward Σ _τ=0 ^∞ γ ^τ r _t+τ for the discount rate γ is as large as possible. In addition, it is assumed that a hidden state exists in the background of the observation o _t , the hidden state changes probabilistically depending on the action, and the reward is also determined probabilistically. Typically, a system is assumed in which the hidden state is s _t and the state transition law p(s _t+1 | _{s t} , a _t ), the observed state law p(o _t | _{s t} ), and the reward law p(r _t | _{s t} , a _t ) are defined. Hereinafter, these are referred to as the transition law, the observation law, and the reward law. However, these laws are unknown to the algorithm (agent) for achieving the goal. It is necessary to repeat actions to learn the laws while simultaneously earning a high reward.

On the other hand, in the principle according to the embodiment of the present invention, the agent holds its own hidden state s _t ' and an estimate q(s _t ') of the current state as an internal model for the environment. Here, s _t ' is assumed to be a simplification focusing on elements related to the reward of s _t . However, although the existence of s _t itself and transition rules are assumed, they are not actually estimated. Assuming that there are some complex states and transition rules, s _t ' is obtained by eliminating unnecessary states from the perspective of reward without directly considering them.

The method of this embodiment has internal models for the transition law, observation law, and reward law, but is characterized in that it uses the formats p(s _t '|o _t ) and p(a _t | _{s t} ', s _t+1 ') for the observation law and transition law, which differ from the actual law. The reward law p(r _t | _{s t} ', a _t ) is the same as the actual law. With this format, the transition diagram of the state and law estimation of this embodiment can be made as shown in the lower part of Figure 1. The agent holds the parameters of each law as a probability distribution and learns according to the observation results. Specifically, the parameters M'(s _t ', s _t+1 ', a _t ) = p( a t | _{s t} ', s _t+1 '), N'(s _t ', o _t ) = p( o _t | s _t '), L(s _t ', a _t , r _t ) = p( r _t | _{s t} ', a _t ) are set as probability parameters, and the parameter predictions q(M'), q(N'), and q(L) are set. q(M') and q(N') can be easily converted to q(M) and q(N) that correspond to the actual laws.

Now let us explain the parameters. For example, in p(r|s,L), if the possible values of r in state s1 are r1, r2, and r3, then L(s1,r1) represents the probability that r1 is obtained, and L can be expressed as a matrix, L(s1,r1) + L(s1,r2) + L(s1,r3) = 1. M is a tensor that takes the indices of s, s', and a, and the sum over a is 1.

The agent operates in the following procedure. [1] Sample M, N, and L according to the probability distributions q(M), q(N), and q(L). [2] Determine and output the optimal action a _t based on the Bellman equation assuming that the sampled M, N, and L and the state estimate q(s _t ') are correct. As a result of outputting the optimal action a _t , obtain r _t , o _t+1 as new information. [3] Apply Bayes' theorem to the rules p(a _t | _{s t} ',s _t+1 '), p(o _t | _{s t} '), p(r _t | _s t ',a _t ), the prior distributions q(s _t '), q(M'), q(N), and q(L), and the observed information o _t , a _t , r _t , and o _t+1 . Update the obtained posterior distribution as new knowledge q(s _t+1 '), q(M'), q(N), and q(L). [4] Then, return to [1] and repeat.

The Bellman equation calculates the expected long-term reward q when action a is taken, so we simply take the action that maximizes q. Applying Bayes' theorem means calculating the posterior distribution p(s,s',L,M,N|o,o',r,r') using each rule p(a|s,s',M), p(s|o,L), p(r|s,N) and the prior distribution p(L,M,N). An example of applying the calculation of the posterior distribution is shown below.

p(s, s', L, M, N | o, o', r, r', a)
∝p(r, r', a, s, s', L, M, N | o, o')
=p(r|s,N)p(r'|s',N)p(a|s,s',M)p(s|o,L),p(s'|o',L)p(L,M,N)

In addition, the calculation method uses variational Bayes to calculate the posterior distribution until it converges each time, but in conventional methods, the posterior distribution is not calculated until it converges each time, and only one step of variational Bayes is updated. Also, although the amount of calculation required by the method of this embodiment is greater, it is expected to greatly improve online performance.

The features of the above procedures will be described. In procedure [1], the conventional method does not attempt to apply Thompson sampling to state transitions. Conventional methods mainly predict q using a neural network by combining [1] and [2]. In procedure [2], it is a standard method to obtain q when M, N, and L are known, and it is a standard method to determine an action probabilistically using softmax based on Q. In contrast, the method of this embodiment is characterized in that sampling is performed in [1], so that softmax is not used and the action with the largest q is simply selected. As for procedure [3], the conventional method assumes probability models p(s _t+1 |s _t , a _t ), p(o _t |s _t ), while the method of this embodiment assumes and formulates p(a _t |s _t ', s _t+1 '), p(s _t '|o _t ), which is a major difference. Furthermore, in the conventional method, the observation o _t is assumed to have a simple categorical distribution, whereas in the method of this embodiment, it is expanded to a direct product of categorical distributions.

In the above example, variational Bayesian calculations are used, but variational Bayesian calculations are not required for the procedure itself, and other calculation methods may be used.

<Configuration of the optimization device according to the embodiment of the present invention>
Next, the configuration of the optimization device according to the embodiment of the present invention will be described.

Figure 2 is a diagram showing the functional configuration of the optimization device 100 according to an embodiment of the present invention. As shown in Figure 2, the optimization device 100 functionally comprises a setting unit 110, an update unit 112, and a storage unit 120.

The setting unit 110 sets the state transition rules and the definition of the observed state rules, and stores the settings in the storage unit 120. Hereafter, the settings are read out as appropriate for each rule and processing is performed.

As shown in the above principle, the setting holds the unique hidden state s _{t '} obtained by changing the hidden state s _t in a predetermined manner, and the estimate q(s _t ') of the current state in the unique hidden state. The setting holds the law of the observation state to obtain the unique hidden state s _t ' using the observation o _t at time t as a condition of the conditional probability (p(s _t ' | _{o t} )). The setting holds the law of the state transition to obtain the agent's action a _t using the unique hidden state s _t ' at time t and the unique hidden state s _t+1 ' at time t+1 as a condition of the conditional probability (p(a _t | _{s t} ', s _t+1 ')).

The update unit 112 repeatedly determines the optimal action a _t of the agent and updates the distribution. The update may be repeated until a predetermined condition is satisfied. The optimal action a _t of the agent is determined by first sampling each parameter M, N, and L representing a probability based on each rule according to the above-mentioned procedure [1] of the agent's operation. Next, according to procedure [2], assuming each sampled parameter M, N, and L and an estimate q(s _t ') of the current state, determining and outputting the optimal action a _t of the agent based on the Bellman equation. As a result of outputting the optimal action a _t , new information r _t and o _t+1 are obtained. According to procedure [3], Bayes' theorem is applied to each rule p(a _t |s _t ',s _t+1 '), p(o _t | _{s t} '), p(r _t | _s t ',a _t ), predetermined prior distributions q(s _t '), q(M'), q(N), q(L), and observation information o _t , a _t , r _t , o _t+1 including optimal actions to obtain a posterior distribution. Then, the update unit 112 repeats the estimation of the current state and the updating of the distributions q(s _t+1 '), q(M'), q(N), q(L) using each rule using the obtained posterior distribution, thereby outputting a finally converged distribution.

The memory unit 120 stores the settings related to each rule set by the setting unit 110, the calculation data of the calculation process by the update unit 112, and the calculation results.

Figure 3 is a block diagram showing the hardware configuration of the optimization device 100.

As shown in FIG. 3, the optimization device 100 has a CPU (Central Processing Unit) 11, a ROM (Read Only Memory) 12, a RAM (Random Access Memory) 13, a storage 14, an input unit 15, a display unit 16, and a communication interface (I/F) 17. Each component is connected to each other via a bus 19 so as to be able to communicate with each other.

The CPU 11 is a central processing unit that executes various programs and controls each part. That is, the CPU 11 reads a program from the ROM 12 or the storage 14, and executes the program using the RAM 13 as a working area. The CPU 11 controls each of the above components and performs various calculation processes according to the program stored in the ROM 12 or the storage 14. In this embodiment, an optimization program is stored in the ROM 12 or the storage 14.

The ROM 12 stores various programs and various data. The RAM 13 temporarily stores programs or data as a working area. The storage 14 is composed of a storage device such as an HDD (Hard Disk Drive) or SSD (Solid State Drive), and stores various programs including an operating system, and various data.

The input unit 15 includes a pointing device such as a mouse and a keyboard, and is used to perform various input operations.

The display unit 16 is, for example, a liquid crystal display, and displays various information. The display unit 16 may also function as the input unit 15 by adopting a touch panel system.

The communication interface 17 is an interface for communicating with other devices such as terminals, and uses standards such as Ethernet (registered trademark), FDDI, and Wi-Fi (registered trademark).

<Function of the optimization device according to the embodiment of the present invention>
Next, a description will be given of the operation of the optimization device 100 according to the embodiment of the present invention. As one of the components of the optimization device 100, the CPU 11 executes an optimization processing routine shown in FIG.

In step S100, the CPU 11 sets the state transition rules and the definition of the observed state rules, and stores the settings in the memory unit 120.

In step S102, the CPU 11 samples the M, N, and L parameters according to the agent's operation procedure [1].

In step S104, the CPU 11 determines the optimal action at of the agent based on the Bellman equation, assuming the sampled parameters M, N, and L and the current state estimate q(s _t ') in accordance with procedure [ ₂ ].

In step S105, the CPU 11 outputs the optimal action a _t , and as a result, obtains r _t and o _t+1 as new information.

In step S106, the CPU 11 obtains a posterior distribution by applying Bayes' theorem to the observed information including each rule, a predetermined prior distribution, and the optimal action a _t , according to procedure [3].

In step S108, the CPU 11 determines whether the update conditions are met. If it is determined that the conditions are met, the process proceeds to step S110. If it is determined that the conditions are not met, the process returns to step S102 and repeats the process ("Procedure [4]").

In step S110, the final distribution obtained is output and the process ends.

According to the embodiment of the present invention described above, it is possible to improve the efficiency of calculations. Furthermore, there are three main key points of the technology. The first point is that state estimation using a probabilistic model is integrated with the decision-making problem, the second point is that the observation rules and transition rules are in a unique format rather than the usual format, and the third point is the use of sampling in the procedure.

The first point, the integration of state estimation using a probabilistic model and the decision-making problem, will be explained. Various methods have been proposed so far for estimating models of hidden states from observations, such as the Kalman filter. There has also been a great deal of research on decision-making problems in state transition environments, typified by Q-learning. However, despite being an important problem in reality, only limited efforts have been made on the problem of integrating the two. In terms of the first point, the technology of this embodiment is a method of integrating state estimation and the decision-making problem.

The second point is that the law is in a unique format. In this embodiment, the observation law and the transition law are in the format of p(s _t '|o t) and p(a _t | _{s t} ',s _t+1 '). This formulation allows the observation o _t to be treated as a decision that has already been given, rather than as a value to be estimated, on the probabilistic model. When formulated in a normal form, the observation o _t is treated as something completely separate, regardless of the reward, and the entire true transition law is estimated. On the other hand. In the method of this embodiment, since it is sufficient to predict the reward, not the observation o _t , the transition rule is reconstructed only by the hidden state s _t ' required for predicting the reward, not the true transition rule. This reduces the number of hidden states, making it possible to perform learning efficiently. In human cognition, for example, there are a large number of observations such as vision and hearing, and only a small number of states are truly required for decision-making. By using this law, such advanced mechanisms can be effectively realized with a simple model.

The third point is the use of sampling in the procedure. The important issue is whether to use an uncertain internal model to obtain as much reward as possible based on the current estimation, or to explore to obtain information for future rewards. In this embodiment, the procedure (2) and (3) described in the principle are used for utilization, but since the uncertainty of the original estimation is taken into account in the sampling in (1), the most effective exploration can be performed. Therefore, what is new is the efficiency achieved by combining decision-making based on a state estimation model and sampling.

As described above, the technology of the embodiment of the present invention makes it possible to improve the efficiency of calculations. In other words, for a hidden Markov model in which the hidden state transitions depending on the state and action and the observed state is generated, and a reward is added to the model, an algorithm is provided that correctly estimates state transitions in a small number of iterations while reducing opportunity loss and that provides high explainability of the results.

Opportunity loss is the loss associated with an agent's actions. For example, if taking action a1 would earn r1 reward, but taking action a2 earns r2, then r1-r2 is the opportunity loss. If information is incomplete at the initial state, it is not possible to reduce opportunity loss to zero, so opportunity loss tends to be large when acting based on incomplete information or when taking exploratory action despite having sufficient information. It is important to have a low average opportunity loss when an algorithm is repeatedly executed over a long period of time, and reducing opportunity loss is roughly the same as increasing the total reward obtained.

[Experimental Results]
The experimental results of the method of this embodiment will be described. FIG. 5 is a graph showing an example of the experimental results of the method of this embodiment and other methods. FIG. 5 shows the cumulative reward for each number of trials for each estimation method. The method proposed in this embodiment is O _mul →S→R. The method proposed in this embodiment can obtain the optimal reward the fastest. FIG. 6 is a table showing the number of hidden states at the time of convergence in the experiment. In the method of this embodiment, it is possible to estimate 8 types of hidden states related to the reward for 32 types of observed states. This is the reason why learning can be performed at high speed.

Note that we will provide some additional information regarding the laws of this embodiment. The laws shown in Figure 1 are "true laws" that are not known to the agent, and in these laws, observations are generated from hidden states. Normally, in a probabilistic model, it is common to seek true laws, but in the problem setting assumed in this embodiment, it is not necessarily necessary to estimate all of the complex true laws. In particular, for the part where observation o is obtained from state s, the law of what observation will be obtained next time is learned, but since state o can actually be observed, prediction is not necessary; it is sufficient to only predict the hidden state s and reward r. Therefore, the method of this embodiment is the result of considering a formulation that does not require the deliberate prediction of o.

For example, in the law of truth, four states {s0, s1, s2, s3} correspond one-to-one to observations {o0, o1, o2, o3}, but if we consider the case where the four states are equivalent from the viewpoint of reward, any observation can be said to be equivalent for the purpose of obtaining reward. In the conventional method, it was learned that o0 is generated from state s0, and o2 is generated from state s1, and therefore a large number of states were required. In the method of this embodiment, it is learned that when o0, o1, o2, and o3 are observed, they are a common state. The law of truth is not necessarily fixed to one view, and it can also be interpreted as the same state and observations are generated probabilistically. In that sense, in this example, s and s' correspond completely equivalently.

In general, agents using conventional methods always construct a state and its transition model that can explain the observation o. On the other hand, the method of this embodiment reconstructs the state simply from the perspective of reward, without being caught up in seemingly diverse and complex observations, which may have various interpretations. Since p(o|s) can be found from p(s|o) and p(o) using Bayes' theorem, s and s' can be said to be equivalent models.

The technology of the embodiment of the present invention can be applied to a wide range of problem settings in which observed states and rewards are given, and can learn faster than conventional methods, so a wide range of applications are conceivable. In particular, it is expected to be used in the field of robotics and to improve the performance of agent systems using AI.

The present invention is not limited to the above-described embodiment, and various modifications and applications are possible without departing from the spirit of the invention.

100 Optimization device 110 Setting unit 112 Update unit 120 Storage unit

Claims (4)

In a model in which a system is used in which each law is defined based on a state transition law, an observed state law, and a reward law, and an agent repeats actions to learn each of the laws and obtain a reward,
maintaining a unique hidden state in which the hidden state has been modified in a predetermined manner, and an estimate of the current state in the unique hidden state;
The law of the observation state is such that, using the observation at time t as the condition of the conditional probability to obtain the unique hidden state,
The state transition rule uses the unique hidden state at time t and the unique hidden state at time t+1 as the condition of the conditional probability to obtain the agent's action:
A setting unit that defines a transition rule of the state and a rule of the observed state;
determining an optimal action for the agent based on a Bellman equation assuming a distribution of each parameter representing a probability of sampling based on each of the laws and an estimate of the current state;
an update unit that repeats estimating the current state and updating the distribution using each of the laws based on a posterior distribution obtained by applying Bayes' theorem to observation information including each of the laws, a predetermined prior distribution, and the optimal action;
An optimization device comprising: The optimization device according to claim 1, wherein the update unit selects an action that maximizes the long-term reward q based on the Bellman equation by sampling each parameter in the agent's action procedure. In a model in which a system is used in which each law is defined based on a state transition law, an observed state law, and a reward law, and an agent repeats actions to learn each of the laws and obtain a reward,
maintaining a unique hidden state in which the hidden state has been modified in a predetermined manner, and an estimate of the current state in the unique hidden state;
The law of the observation state is such that, using the observation at time t as the condition of the conditional probability to obtain the unique hidden state,
The state transition rule uses the unique hidden state at time t and the unique hidden state at time t+1 as the condition of the conditional probability to obtain the agent's action:
defining transition laws for said states and laws for said observed states;
determining an optimal action for the agent based on a Bellman equation assuming a distribution of each parameter representing a probability of sampling based on each of the laws and an estimate of the current state;
repeating the estimation of the current state and updating the distribution using each of the laws based on a posterior distribution obtained by applying Bayes' theorem to the observed information including each of the laws, a predetermined prior distribution, and the optimal action;
An optimization method for having a computer execute a process. A program for causing a computer to function as each part of the optimization device according to claim 1 or claim 2.