Patent Publication Number: US-11645574-B2

Title: Recording medium, reinforcement learning method, and reinforcement learning apparatus

Description:
CROSS REFERENCE TO RELATED APPLICATIONS 
     This application is based upon and claims the benefit of priority of the prior Japanese Patent Application No. 2017-177970, filed on Sep. 15, 2017, the entire contents of which are incorporated herein by reference. 
     FIELD 
     The embodiments discussed herein relate to a recording medium, a reinforcement learning method, and a reinforcement learning apparatus. 
     BACKGROUND 
     A technique of reinforcement learning has traditionally been present according to which, based on an immediate cost or an immediate reward given to a controlled object corresponding to an input for the controlled object (environment), a control law to minimize or maximize a value function that represents an accumulated cost or an accumulated reward given to the controlled object is learned and an input value for the controlled object is determined. 
     For example, a technique is present as a prior art. According to the technique, a value of a gradient of a first value function that is a temporal derivative of a first value function as a learning result and that is determined corresponding to a first reward acquired from a controlled object (environment) is utilized for evaluation of a second reward and an action policy is determined based on the second reward (see, for example, Japanese Laid-Open Patent Publication No. 2010-134907). 
     SUMMARY 
     According to an aspect of an embodiment, a non-transitory, computer-readable recording medium stores therein a reinforcement learning program that uses a value function and causes a computer to execute a process comprising: estimating first coefficients of the value function represented in a quadratic form of inputs at the times in the past than a present time and outputs at the present time and the times in the past, the first coefficients being estimated based on inputs at the times in the past, the outputs at the present time and the times in the past, and costs or rewards that corresponds to the inputs at the times in the past; and determining second coefficients that defines a control law, based on the value function that uses the estimated first coefficients and determining input values at the times after estimation of the first coefficients. 
     The object and advantages of the invention will be realized and attained by means of the elements and combinations particularly pointed out in the claims. 
     It is to be understood that both the foregoing general description and the following detailed description are exemplary and explanatory and are not restrictive of the invention. 
    
    
     
       BRIEF DESCRIPTION OF DRAWINGS 
         FIG.  1    is an explanatory diagram of an EXAMPLE of a reinforcement learning method according to an embodiment; 
         FIG.  2    is a block diagram depicting an example of a hardware configuration of a reinforcement learning apparatus  100 ; 
         FIG.  3    is a block diagram of an example of a functional configuration of the reinforcement learning apparatus  100 ; 
         FIG.  4    is an explanatory diagram of a specific example of a controlled object  110 ; 
         FIG.  5    is an explanatory diagram of a specific example of the controlled object  110 ; 
         FIG.  6    is a flowchart of an example of a procedure for a reinforcement learning process in a batch processing form; and 
         FIG.  7    is a flowchart of an example of a procedure for a reinforcement learning process in a sequential processing form. 
     
    
    
     DESCRIPTION OF THE INVENTION 
     First, problems associated with the traditional techniques will be described. The state of the controlled object may not be directly observed and what affects the immediate cost or the immediate reward corresponding to the input for the controlled object may be unknown. In this case, with the traditional technique, it is difficult to accurately determine the input value for the controlled object. 
     Embodiments of a recording medium storing a reinforcement learning program, a reinforcement learning method, and a reinforcement learning apparatus according to the present disclosure will be described in detail with reference to the accompanying drawings. 
       FIG.  1    is an explanatory diagram of an EXAMPLE of a reinforcement learning method according to an embodiment. A reinforcement learning apparatus  100  is a computer that controls a controlled object  110  by determining an input value for the controlled object  110 . The reinforcement learning apparatus  100  is, for example, a server, a personal computer (PC), or a microcontroller. 
     The controlled object  110  is a certain object and is, for example, a physical system that actually exists. The controlled object is also referred to as “environment”. The controlled object  110  is, for example, a server room or an electric generator. The input is an operation for the controlled object  110 . The input is also referred to as “action”. The state of the controlled object  110  is varied corresponding to the input for the controlled object  110 , and an output of the controlled object  110  is observed. 
     For example, a first control approach to a fifth control approach and the like may be considered as control approaches each of controlling the controlled object  110 . 
     For example, the first control approach may be considered using as a reference, S. J. Bradtke, B. E. Ydstie and A. G. Barto, “Adaptive linear quadratic control using policy iteration”, In Proc. of the 1994 American Control Conference, pp. 3475-3479, Baltimore, USA, 1994. The first control approach is a control approach in which the controlled object  110  is controlled by reinforcement learning method for which the variation of the controlled object  110  is represented by a discrete-time linear time-invariant state equation and the immediate cost of the controlled object  110  is represented in a quadratic form; and a situation is assumed where the state of the controlled object  110  is directly observed. 
     For example, the second control approach may be considered. The second control approach is a control approach in which a situation is assumed where coefficient matrices of the state equation, the output equation, and the immediate cost equation in the quadratic form, of the controlled object  110  are known. With the second control approach, the controlled object  110  is controlled by estimating the state of the controlled object  110  based on the output of the controlled object  110 . 
     For example, the third control approach may be considered using as a reference, Mita, Pang, and Liu, “A New Optimal Digital Output Feedback Control and Its Application to the Control of Mechanical Systems”, Journal of Society of Instrument and Control Engineers, Vol. 22, No. 12, pp. 20-26, 1986. The third control approach is a control approach in which the controlled object  110  is controlled based on inputs and outputs of the controlled object  110  at times in the past, assuming a situation where coefficient matrices of the state equation, the output equation, and the immediate cost equation in the quadratic form, of the controlled object  110  are known. 
     For example, the fourth control approach may be considered using as a reference, Steven Joseph Bradtke, “Incremental Dynamic Programming for On-Line Adaptive Optimal Control”, Ph.D. Dissertation, University of Massachusetts, Amherst, Mass., USA, UMI Order No. GAX95-10446, 1995. The fourth control approach is a control approach in which the controlled object  110  is controlled by reinforcement learning method for which the variation of the controlled object  110  is represented by a discrete-time linear time-invariant state equation and the immediate cost of the controlled object  110  is represented in the quadratic form; and a situation is assumed where the state of the controlled object  110  is not directly observed. With the fourth control approach, an input value at the present time is derived based on outputs at k times in the past and inputs at l times in the past. 
     For example, the fifth control approach may be considered using as a reference, F. L. Lewis and K. G. Vamvoudakis, “Reinforcement Learning for Partially Observable Dynamic Processes: Adaptive Dynamic Programming Using Measured Output Data”, IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), Vol. 41, No. 1, pp. 14-25, 2011. The fifth control approach is a control approach in which the controlled object  110  is controlled by reinforcement learning method for which the variation of the controlled object  110  is represented by a discrete-time linear time-invariant state equation, and a situation is assumed where a coefficient matrix in the immediate cost equation in the quadratic form with respect to the input for the controlled object  110  is known. With the fifth control approach, an input value at the present time is derived based on outputs at times in the past and the present, inputs at the times in the past, and a coefficient matrix in the immediate cost equation in a quadratic form with respect to the input for the controlled object  110 . 
     As depicted in  FIG.  1   , as to the controlled object  110 , a situation is present where the coefficient matrices of the state equation, the output equation, and the immediate cost equation in the quadratic form, of the controlled object  110  are unknown and the state of the controlled object  110  is not directly observed. Control of the controlled object  110  is desired also for the case where the controlled object  110  is in the situation depicted in  FIG.  1   . 
     It is however difficult for the first to the fifth control approaches to efficiently learn the control law and accurately determine the input value for the controlled object  110  in a case where the controlled object  110  is in a situation such as that depicted in  FIG.  1   . The control law is also referred to as “policy”. 
     For example, a situation is assumed for the first control approach where the state of the controlled object  110  is directly observed, and it is difficult to apply the first control approach to the situation as depicted in  FIG.  1   . Even when the first control approach is applied to a situation such as that depicted in  FIG.  1    by handling the output of the controlled object  110  directly observed as a substitute of the state of the controlled object  110 , the control law cannot be learned efficiently and an input value for the controlled object  110  cannot be determined accurately. 
     For example, a situation is assumed for each of the second control approach and the third control approach where the coefficient matrices of the state equation, the output equation, and the immediate cost equation in the quadratic form, of the controlled object  110  are known, and it is difficult to apply these control approaches to a situation such as that depicted in  FIG.  1   . 
     With the fourth control approach, for example, it is difficult to identify advantageous values to be set as k and l when the input value at the present time is derived based on outputs at the k times in the past and inputs at the l times in the past. With the fourth control approach, when values relatively greater than the values advantageous to be set as k and l are set, the control law cannot be learned efficiently. 
     With the fourth control approach, when values smaller than the values advantageous to be set as k and l are set, it is difficult to efficiently learn the control law and accurately determine the input value for the controlled object  110 . With the fourth control approach, when the input value at the present time is determined, no output at the present time is used and it is therefore difficult to efficiently learn the control law and accurately determine the input value for the controlled object  110 . 
     With the fifth control approach, for example, the coefficient matrix in the immediate cost equation in the quadratic form with respect to the input for the controlled object  110  is used as a part of the control law, and the input value at the present time cannot therefore be determined unless in the situation where the coefficient matrix in the immediate cost equation in the quadratic form with respect to the input for the controlled object  110  is used is known. It is therefore difficult to apply the fifth control approach to a situation such as that depicted in  FIG.  1   . 
     In the present embodiment, a reinforcement learning method will be described that is also applicable to a situation where the state of the controlled object  110  is not directly observed and what affects the immediate cost or the immediate reward corresponding to the input for the controlled object  110  is unknown. 
     In the example of  FIG.  1   , the state equation, the output equation, and the immediate cost equation in the quadratic form, of the controlled object  110  are defined and the problem setting is executed for a case where the controlled object  110  is in a situation such as that depicted in  FIG.  1   . A specific example of the problem setting will be described later in EXAMPLE. 
     The reinforcement learning apparatus  100  handles this problem setting as a problem setting that is equivalent to the problem setting for which observation is full observation regarding the inputs at times further in the past than the present time and the outputs at the present time and the times further in the past than the present time, and executes the following operations. 
     The reinforcement learning apparatus  100  estimates the coefficients of the value function based on the inputs at the times in the past, the outputs at the present time and the times in the past, and the cost or the reward corresponding to the inputs at the times in the past. The value function is represented by the quadratic form of the inputs at the times in the past and the outputs at the present time and the times in the past. A specific example of the estimation of the coefficients of the value function will be described later in EXAMPLE. 
     Based on the value function that uses the estimated coefficients, the reinforcement learning apparatus  100  determines the input value at a time after the estimation. For example, based on the value function that uses the estimated coefficients, the reinforcement learning apparatus  100  identifies the coefficients of the control law and, based on the control law, determines the input value at the time after the estimation. A specific example of the determination of the input value will be described later in EXAMPLE. 
     For a case where the controlled object  110  is in a situation such as that depicted in  FIG.  1   , the reinforcement learning apparatus  100  may also efficiently learn the control law and accurately determine the input value for the controlled object  110  based on the reinforcement learning. “Efficiently learning the control law” refers to sequentially updating the control law so that the value function is efficiently optimized. 
     For the case where the controlled object  110  is in the situation as depicted in  FIG.  1   , the reinforcement learning apparatus  100  may also realize the reinforcement learning and may expand the scope of the object that may be set as the controlled object  110 . For example, even when the coefficient matrices of the state equation, the output equation, and the immediate cost equation in the quadratic form, of the controlled object  110  are unknown, the reinforcement learning apparatus  100  may realize reinforcement learning. Even when the state of the controlled object  110  is not directly observed, the reinforcement learning apparatus  100  may realize reinforcement learning. 
     With the fourth control approach, it is difficult to efficiently learn the control law and accurately determine the input value for the controlled object  110  because it is difficult to set advantageous values as k and l. In contrast, because the reinforcement learning apparatus  100  does not use k and l, the reinforcement learning apparatus  100  enables efficient learning of the control law and the accurate determination of the input value for the controlled object  110  to be facilitated. 
     With the fifth control approach, because the coefficient matrix in the immediate cost equation in the quadratic form with respect to the input for the controlled object  110  is used as a part of the control law, the situation is assumed where the coefficient matrix in the immediate cost equation in the quadratic form with respect to the input for the controlled object  110  is known. In contrast, the reinforcement learning apparatus  100  may handle the problem setting to be equivalent to a problem setting for which observation is full observation, and the coefficient matrix in the immediate cost equation in the quadratic form with respect to the input for the controlled object  110  needs not be used. The reinforcement learning apparatus  100  is therefore applicable to the case where the coefficient matrix in the immediate cost equation in the quadratic form with respect to the input for the controlled object  110  is unknown, and may expand the scope of the object that may be set as the controlled object  110 . 
     An example of a hardware configuration of the reinforcement learning apparatus  100  depicted in  FIG.  1    will be described using  FIG.  2   . 
       FIG.  2    is a block diagram depicting an example of a hardware configuration of the reinforcement learning apparatus  100 . In  FIG.  2   , the reinforcement learning apparatus  100  includes a central processing unit (CPU)  201 , a memory  202 , a network interface (I/F)  203 , a recording medium I/F  204 , and a recording medium  205 , respectively connected by a bus  200 . 
     Here, the CPU  201  governs overall control of the reinforcement learning apparatus  100 . The memory  202  includes, for example, read only memory (ROM), random access memory (RAM), a flash ROM, etc. In particular, for example, the flash ROM and the ROM store therein various types of programs; and the RAM is used as a work area of the CPU  201 . The programs stored by the memory  202  are loaded onto the CPU  201 , whereby encoded processes are executed by the CPU  201 . 
     The network I/F  203  is connected to a network  210  through a communications line and is connected to another computer through the network  210 . The network I/F  203  administers an internal interface with the network  210  and controls the input and output of data from the other computer. A modem, a LAN adapter, etc., for example, may be adopted as the network I/F  203 . 
     The recording medium I/F  204 , under the control of the CPU  201 , controls the reading and writing of data with respect to the recording medium  205 . The recording medium I/F  204  is, for example, a disk drive, a solid state drive (SSD), a universal serial bus (USB) port, etc. The recording medium  205  is non-volatile memory storing therein data written thereto under the control of the recording medium I/F  204 . The recording medium  205  is, for example, a disk, a semiconductor memory, a USB memory, etc. The recording medium  205  may be detachable from the reinforcement learning apparatus  100 . 
     The reinforcement learning apparatus  100  may include, for example, a keyboard, a mouse, a display, a touch panel, a printer, a scanner, etc. in addition to the components above. Further, the reinforcement learning apparatus  100  may omit the recording medium I/F  204  and the recording medium  205 . 
     An example of a functional configuration of the reinforcement learning apparatus  100  will be described with reference to  FIG.  3   . 
       FIG.  3    is a block diagram of an example of the functional configuration of the reinforcement learning apparatus  100 . The reinforcement learning apparatus  100  includes a storage unit  300 , an observing unit  301 , an estimating unit  302 , a determining unit  303 , and an output unit  304 . 
     The storage unit  300  is realized by, for example, a storage area such as the memory  202  or the recording medium  205  depicted in  FIG.  2   . The components from the observing unit  301  to the output unit  304  are functions constituting a control unit. Functions of the components from the observing unit  301  to the output unit  304  are realized by, for example, executing on the CPU  201 , the programs stored in a storage area such as the memory  202  or the recording medium  205  depicted in  FIG.  2    or by the network I/F  203 . Processing results of the functional units are stored to a storage area such as the memory  202  or the recording medium  205  depicted in  FIG.  2   . 
     The storage unit  300  accumulates the inputs, the outputs, and the immediate cost or the immediate reward of the controlled object  110 . The storage unit  300  may thereby enable the estimating unit  302  and the determining unit  303  to refer to the inputs, the outputs, and the immediate cost or the immediate reward of the controlled object  110 . 
     The observing unit  301  observes the outputs, and the immediate cost or the immediate reward of the controlled object  110 , and outputs these items to the storage unit  300 . The observing unit  301  may thereby enable the storage unit  300  to accumulate therein the inputs, the outputs, and the immediate cost or the immediate reward of the controlled object  110 . 
     The estimating unit  302  estimates the coefficients of the value function based on the inputs at times further in the past than the present time, the outputs at the present time and the times in the past, and the immediate cost or the immediate reward corresponding to the input at the times in the past. The value function is a function to evaluate the controlled object  110  and is a function that represents the accumulated cost acquired by accumulating the costs that are each a loss of the controlled object  110  or the accumulated reward acquired by accumulating the rewards that are each a benefit of the controlled object  110 . The estimating unit  302  may thereby estimate the coefficients of the value function and may identify the estimation function of the value function that uses the estimated coefficients. 
     The value function is represented in the quadratic form of, for example, the inputs at the times in the past and the outputs at the present time and the times in the past. The value function is, for example, a state-value function. The value function is represented by, for example, equation (19) described later in EXAMPLE. The estimating unit  302  may thereby use the state-value function. 
     The value function is represented in the quadratic form of, for example, the inputs at the present time and the times in the past, and the outputs at the present time and the times in the past. The value function is represented by, for example, equation (20) described later in EXAMPLE. The estimating unit  302  may thereby use a state-action-value function. 
     The estimating unit  302  estimates the coefficients of the value function for the control problem that uses the value function for which observation is the full observation regarding the inputs at the times in the past and the outputs at the present time and the times in the past. The estimating unit  302  estimates the coefficients of the value function for the control problem for which observation is the full observation for, for example, a vector z t  described later in EXAMPLE. For the control problem, the coefficient that indicates the degree of the influence from the input on the cost or the reward may be unknown. The estimating unit may repeat the estimation of the coefficients of the value function plural times. 
     The determining unit  303  determines the input value at times after the estimation based on the value function that uses the estimated coefficients. The determining unit  303  calculates the coefficients in the control law based on, for example, the relation between the estimated coefficients in the value function that uses the estimated coefficients and the coefficients in the control law that calculates the input value. The determining unit  303  uses the calculated coefficients to determine the input value. The determining unit  303  may thereby accurately determine the input value. 
     The determining unit  303  determines the input value at a time after the estimation using the output at a time after the estimation based on the value function using the estimated coefficients. After the estimation, the determining unit  303  determines the input value at the present time using the inputs at the times in the past and the outputs at the present time and the times in the past. The determining unit  303  may thereby accurately determine the input value. 
     The output unit  304  outputs the determined input value to the controlled object  110 . The output unit  304  outputs the determined input value to the storage unit  300 . The output unit  304  may thereby store the input value to the storage unit  300  and enable the estimating unit  302  and the determining unit  303  to refer to the input value. 
     EXAMPLE of the reinforcement learning will be described. In EXAMPLE, the state equation, the output equation, and the immediate cost equation in the quadratic form, of the controlled object  110  are defined by equations (1) to (9) below and the problem setting is executed. In EXAMPLE, the state of the controlled object  110  is not directly observed.
 
 x   t+1   Ax   t   Bu   t   (1)
 
     Equation (1) is the state equation of the controlled object  110 . “t” is the time indicated as a multiple of a unit time period. “t+1” is the next time when the unit time period elapses from the time t. “x t+1 ” is the state at the next time t+1. “x t ” is the state at the time t. “u t ” is the input at the time t. “A” and “B” are each a coefficient matrix. Equation (1) represents that a relationship of the state x t+1  with the state x t  at the time t is determined by the input u t  at the time t. The coefficient matrices A and B are unknown.
 
 y   t   =Cx   t   (2)
 
     Equation (2) is the output equation of the controlled object  110 . “y t ” is the output at the time t. “C” is a coefficient matrix. Equation (2) represents that the output y t  at the time t is in a relationship determined by the state x t  at the time t. The coefficient matrix C is unknown.
 
 x   0 ∈   n   (3)
 
     Equation (3) represents that the state x o  is n-dimensional. “n” is known.
 
 u   t ∈   m   ,t= 0,1,2,  (4)
 
     Equation (4) represents that the input u t  is m-dimensional.
 
 A∈     n×n   ,B∈     n×m   ,C∈     p×n   (5)
 
     Equation (5) represents that the coefficient matrix A is n×n-dimensional (has n rows and n columns), that the coefficient matrix B is n×m-dimensional (has n rows and m columns), and that the coefficient matrix C is p×n-dimensional (has p rows and n columns). (A, B) is stabilizable.
 
 c   t   =c ( x   t   ,u   t )= {tilde over (c)} ( y   t   ,u   t )= y   t   T   Qy   t   +u   t   T   Ru   t   (6)
 
     Equation (6) is the immediate cost equation of the controlled object  110 . “c t ” is the immediate cost that is generated after a unit time period corresponding to the input u t  at the time t. The superscript “T” represents transposition. Equation (6) represents that the immediate cost c t  is in a relationship determined by the quadratic form of the output y t  at the time t and the input u t  at the time t. The coefficient matrices Q and R are unknown.
 
 Q∈     p×p   ,Q=   T ≥0  (7)
 
     Equation (7) represents that the coefficient matrix Q is p×p-dimensional (has p rows and p columns). “≥0” represents a positive semi-definite symmetric matrix.
 
 R∈     m×m   ,R=R   T &gt;0  (8)
 
     Equation (8) represents that the coefficient matrix R is m×m-dimensional (has m rows and m columns). “&gt;0” represents a positive definite symmetric matrix. 
     
       
         
           
             
               
                 
                   
                     rank 
                     [ 
                     
                       
                         
                           C 
                         
                       
                       
                         
                           CA 
                         
                       
                       
                         
                           
                             CA 
                             2 
                           
                         
                       
                       
                         
                           ⋮ 
                         
                       
                       
                         
                           
                             CA 
                             
                               n 
                               - 
                               1 
                             
                           
                         
                       
                     
                     ] 
                   
                   = 
                   n 
                 
               
               
                 
                   ( 
                   9 
                   ) 
                 
               
             
           
         
       
     
     Equation (9) represents that (A, C) is observable and the rank of the observability matrix thereof is n. 
     In EXAMPLE, the control law to determine the input u t  at the time t is defined in accordance with equation (10) below based on an advantageous control law in a situation where the coefficient matrices of the state equation, the output equation, and the immediate cost equation in the quadratic form are known.
 
 u   t   =F   0,t   y   y   t   +F   1,t   y   y   t−1   + . . . +F   n−1,t   y   y   t−(n−1)   +F   1,t   u   u   t−1   +F   2,t   u   u   t−2   + . . . +F   n−1,t   u   u   t−(n−1) +ε t   (10)
 
     “F y   it ” is the coefficient matrix at the time t and represents the coefficient matrix regarding the output y t−i . “F u   it ” is the coefficient matrix at the time t and represents the coefficient matrix regarding the input u t−i . Equation (10) is an equation to determine the input at the time t based on the outputs and the inputs from the time t to n−1 unit time periods, using the situation where the dimensions of the state of the controlled object  110  is known. “ε t ” is an exploration term at the time t. When an observable index is known, this observable index may be used. 
     Equation (11) below is set in a situation where the immediate cost c t  is in the quadratic form of the output y t  and the input u t , and (C,A) is observable. 
     
       
         
           
             
               
                 
                   
                     z 
                     t 
                   
                   = 
                   
                     [ 
                     
                       
                         
                           
                             y 
                             t 
                           
                         
                       
                       
                         
                           
                             y 
                             
                               t 
                               - 
                               1 
                             
                           
                         
                       
                       
                         
                           ⋮ 
                         
                       
                       
                         
                           
                             y 
                             
                               t 
                               - 
                               
                                 ( 
                                 
                                   n 
                                   - 
                                   2 
                                 
                                 ) 
                               
                             
                           
                         
                       
                       
                         
                           
                             
                               y 
                               
                                 t 
                                 - 
                                 
                                   ( 
                                   
                                     n 
                                     - 
                                     1 
                                   
                                   ) 
                                 
                               
                             
                             
                               u 
                               
                                 t 
                                 - 
                                 1 
                               
                             
                           
                         
                       
                       
                         
                           
                             u 
                             
                               t 
                               - 
                               2 
                             
                           
                         
                       
                       
                         
                           ⋮ 
                         
                       
                       
                         
                           
                             u 
                             
                               t 
                               - 
                               
                                 ( 
                                 
                                   n 
                                   - 
                                   2 
                                 
                                 ) 
                               
                             
                           
                         
                       
                       
                         
                           
                             u 
                             
                               t 
                               - 
                               
                                 ( 
                                 
                                   n 
                                   - 
                                   1 
                                 
                                 ) 
                               
                             
                           
                         
                       
                     
                     ] 
                   
                 
               
               
                 
                   ( 
                   11 
                   ) 
                 
               
             
           
         
       
     
     “z t ” is a vector formed by collecting the inputs u t−1  to u t−(n−1)  from one unit time period before the time t to n−1 unit time periods and the outputs y t  to y t−(n−1)  from the time t to n−1 unit time periods. 
     When equation (11) is set, equation (12) below is derived.
 
 z   t+1   =A   z   z   t   +B   z   u   t   (12)
 
     The reinforcement learning apparatus  100  may thereby handle the controlled object  110  as a fully observed control problem regarding a vector z t  that is directly observed. The reinforcement learning apparatus  100  updates the coefficient matrix F t  defined in accordance with equation (13) below based on the vector z t  and the immediate cost c t  using equation (12).
 
 F   t =[ F   0,t   y   ,F   1,t′   y    . . . ,F   n−1,t   y   |F   1,t   u   ,F   2,t   u   , . . . ,F   n−1,t   u ]  (13)
 
     “F t ” is the coefficient matrix formed by collecting the coefficient matrices F y   it  and F u   it  in equation (10). F t  represents, for example, the coefficient matrix after the updating at the time t. The reinforcement learning apparatus  100  determines the input u t  in accordance with equation (10) based on the updated coefficient matrix F t  at the time t thereafter. 
     In the following description, the coefficient matrix F t  may be written simply as “coefficient matrix F” without distinguishing the time t of update. A specific example will be described where the coefficient matrix F defined in accordance with equation (13) is updated. 
     A nature of the problem setting in accordance with equations (1) to (9) will be described that enables this problem setting to be handled equivalently to the problem setting that is fully observed regarding the vector z t . 
     When equation (1) is substituted in equation (2), an equation is produced that has the outputs y t  to y t−n  respectively at the times t to t−n and a mathematical expression using the coefficient matrices A, B, C, and the like in the state equation and the output equation, connected therein to each other by an equal sign. The output y t  at the time t is connected by an equal sign to, for example, a mathematical expression that uses the coefficient matrices A, B, and C, the inputs u t−1  to u t−n  at the times further in the past than the time t, and the state x t−n  at the time t−n. 
     The output y t−1  at the time t−1 is connected by an equal sign to, for example, a mathematical expression that uses the coefficient matrices A, B, and C, the inputs u t−2  to u t−n  further in the past than the time t−1, and the state x t−n  at the time t−n. Similarly, the outputs y t−2  to y t−(n−1)  at the times t−2 to t−(n−1) are connected by an equal sign to a mathematical expression that uses the coefficient matrices A, B, and C, the inputs further in the past than this time, and the state x t−n  at the time t−n. The output y t−n  at the time t−n is connected by an equal sign to, for example, a mathematical expression that uses the coefficient matrix C and the state x t−n  at the time t−n. 
     When the equations regarding the times t−2 to t−(n−1) are combined with each other, an equation is produced regarding a vector including the outputs y t−1  to y t−n , a vector including the inputs u t−2  to u t−n , and the state x t−n . Because (C,A) is observable, a left inverse matrix is present for the coefficient matrix that includes C, CA, . . . , CA n−1  regarding the state x t−n . 
     Using this left inverse matrix, the state x t−n  is represented by the vector z t−1  multiplied by the coefficient matrix using the vector z t . The equation formed by connecting the output y t  at the time t to the mathematical expression that uses the coefficient matrices A, B, and C, the inputs u t−1  to u t−n  at the times further in the past than the time t, and the state x t−n  at the time t−n is transformed as equation (14) below. 
     
       
         
           
             
               
                 
                   
                     
                       z 
                       
                         t 
                         + 
                         1 
                       
                     
                     = 
                     
                       
                         
                           A 
                           z 
                         
                         ⁢ 
                         
                           z 
                           t 
                         
                       
                       + 
                       
                         
                           B 
                           z 
                         
                         ⁢ 
                         
                           u 
                           t 
                         
                       
                     
                   
                   ⁢ 
                   
 
                   
                     
                       
                         A 
                         z 
                       
                       = 
                       
                         [ 
                         
                           
                             
                               
                                 A 
                                 z 
                                 11 
                               
                             
                             
                               
                                 A 
                                 z 
                                 12 
                               
                             
                           
                           
                             
                               
                                 A 
                                 z 
                                 21 
                               
                             
                             
                               
                                 A 
                                 z 
                                 22 
                               
                             
                           
                         
                         ] 
                       
                     
                     , 
                     
 
                     
                       
                         A 
                         z 
                         11 
                       
                       = 
                       
                         [ 
                         
                           
                             
                               
                                 
                                   Ξ 
                                   ~ 
                                 
                                 1 
                                 y 
                               
                             
                             
                               
                                 
                                   Ξ 
                                   ~ 
                                 
                                 2 
                                 y 
                               
                             
                             
                               ⋯ 
                             
                             
                               
                                 
                                   Ξ 
                                   ~ 
                                 
                                 
                                   n 
                                   - 
                                   1 
                                 
                                 y 
                               
                             
                             
                               
                                 
                                   Ξ 
                                   ~ 
                                 
                                 n 
                                 y 
                               
                             
                           
                           
                             
                               I 
                             
                             
                               O 
                             
                             
                               ⋯ 
                             
                             
                               O 
                             
                             
                               O 
                             
                           
                           
                             
                               O 
                             
                             
                               I 
                             
                             
                                 
                             
                             
                               O 
                             
                             
                               O 
                             
                           
                           
                             
                               ⋮ 
                             
                             
                                 
                             
                             
                               ⋱ 
                             
                             
                                 
                             
                             
                               ⋮ 
                             
                           
                           
                             
                               O 
                             
                             
                                 
                             
                             
                                 
                             
                             
                               I 
                             
                             
                               O 
                             
                           
                           
                             
                               O 
                             
                             
                               O 
                             
                             
                               ⋯ 
                             
                             
                               O 
                             
                             
                               I 
                             
                           
                         
                         ] 
                       
                     
                     , 
                     
 
                     
                       
                         A 
                         z 
                         12 
                       
                       = 
                       
                         [ 
                         
                           
                             
                               
                                 
                                   Ξ 
                                   ~ 
                                 
                                 2 
                                 u 
                               
                             
                             
                               
                                 
                                   Ξ 
                                   ~ 
                                 
                                 3 
                                 u 
                               
                             
                             
                               ⋯ 
                             
                             
                                 
                             
                             
                               
                                 
                                   Ξ 
                                   ~ 
                                 
                                 n 
                                 u 
                               
                             
                           
                           
                             
                               I 
                             
                             
                               O 
                             
                             
                               ⋯ 
                             
                             
                                 
                             
                             
                               O 
                             
                           
                           
                             
                               O 
                             
                             
                               O 
                             
                             
                               
                                 … 
                                   
                               
                             
                             
                                 
                             
                             
                               O 
                             
                           
                           
                             
                               ⋮ 
                             
                             
                                 
                             
                             
                               ⋱ 
                             
                             
                                 
                             
                             
                               ⋮ 
                             
                           
                           
                             
                                 
                             
                             
                                 
                             
                             
                                 
                             
                             
                                 
                             
                             
                                 
                             
                           
                           
                             
                               O 
                             
                             
                               O 
                             
                             
                               ⋯ 
                             
                             
                                 
                             
                             
                               O 
                             
                           
                         
                         ] 
                       
                     
                     , 
                     
 
                     
                       
                         A 
                         z 
                         21 
                       
                       = 
                       
                         [ 
                         
                           
                             
                               O 
                             
                             
                               O 
                             
                             
                               ⋯ 
                             
                             
                               O 
                             
                             
                               O 
                             
                           
                           
                             
                               O 
                             
                             
                               O 
                             
                             
                               ⋯ 
                             
                             
                               O 
                             
                             
                               O 
                             
                           
                           
                             
                               O 
                             
                             
                               O 
                             
                             
                               
                                 ⋯ 
                                   
                               
                             
                             
                               O 
                             
                             
                               O 
                             
                           
                           
                             
                               ⋮ 
                             
                             
                               
                                 ⋮ 
                                   
                               
                             
                             
                               ⋱ 
                             
                             
                               
                                 ⋮ 
                                   
                               
                             
                             
                               ⋮ 
                             
                           
                           
                             
                               O 
                             
                             
                               O 
                             
                             
                               ⋯ 
                             
                             
                               O 
                             
                             
                               O 
                             
                           
                         
                         ] 
                       
                     
                     , 
                     
 
                     
                       
                         A 
                         z 
                         22 
                       
                       = 
                       
                         [ 
                         
                           
                             
                               O 
                             
                             
                               O 
                             
                             
                               ⋯ 
                             
                             
                                 
                             
                             
                               O 
                             
                           
                           
                             
                               I 
                             
                             
                               O 
                             
                             
                               ⋯ 
                             
                             
                                 
                             
                             
                               O 
                             
                           
                           
                             
                               O 
                             
                             
                               I 
                             
                             
                                 
                             
                             
                               O 
                             
                             
                               O 
                             
                           
                           
                             
                               ⋮ 
                             
                             
                                  
                             
                             
                               ⋱ 
                             
                             
                                 
                             
                             
                               ⋮ 
                             
                           
                           
                             
                               O 
                             
                             
                               O 
                             
                             
                               ⋯ 
                             
                             
                               I 
                             
                             
                               O 
                             
                           
                         
                         ] 
                       
                     
                     , 
                     
 
                     
                       
                         B 
                         z 
                       
                       = 
                       
                         
                           [ 
                           
                             
                               
                                 B 
                                 T 
                               
                               ⁢ 
                               
                                 C 
                                 T 
                               
                             
                             , 
                             O 
                             , 
                             … 
                             , 
                             
                               O 
                               ❘ 
                               I 
                             
                             , 
                             O 
                             , 
                             … 
                             , 
                             O 
                             , 
                             O 
                           
                           ] 
                         
                         T 
                       
                     
                   
                 
               
               
                 
                   ( 
                   14 
                   ) 
                 
               
             
           
         
       
     
     “A z ” and “B z ” are coefficient matrices. Equation (14) represents that the vector z t+1  at the next time t+1 has a relation with the vector z t  at the time t determined by the input u t  at the time t. The coefficient matrices A z  and B z  are unknown. When equation (15) below is applied to equation (14), equation (16) below is derived.
 
 u   t   =Fz   t   (15)
 
 z   t+1 =( A   z   +B   z   F ) z   t   (16)
 
     Based on equation (16), equations (17) and (18) are defined.
 
φ +s ( z:F ):=( A   z   +B   z   F ) s   z   (17)
 
     “s” is a non-negative integer.
 
( A   z   +B   z   F ) 0   :=I   (18)
 
     “ϕ+s(z:F)” is the state after s time units of a system starting to vary from z under the feedback control using the coefficient matrix F. Referring to equation (6), using equation (18), equation (19) below is defined as the state-value function.
 
 V ( z:F )=Σ s=0   ∞ γ s   c (φ +s ( z:F ), Fφ   +s ( z:F ))  (19)
 
     “γ” is a discount rate. γ is between 0 to 1. Equation (20) below is defined as the state-action-value function. 
     
       
         
           
             
               
                 
                   
                     
                       
                         
                           Q 
                           ⁡ 
                           ( 
                           
                             z 
                             , 
                             
                               u 
                               : 
                                  
                               F 
                             
                           
                           ) 
                         
                         = 
                         
                           
                             c 
                             ⁡ 
                             ( 
                             
                               z 
                               , 
                               u 
                             
                             ) 
                           
                           + 
                           
                             γ 
                             ⁢ 
                             
                               V 
                               ⁡ 
                               ( 
                               
                                 
                                   A 
                                   z 
                                 
                                 , 
                                 
                                   
                                     B 
                                     z 
                                   
                                   : 
                                      
                                   F 
                                 
                               
                               ) 
                             
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                         
                           
                             c 
                             ⁡ 
                             ( 
                             
                               z 
                               , 
                               u 
                             
                             ) 
                           
                           + 
                           
                             γ 
                             ⁢ 
                             
                               Q 
                               ⁡ 
                               ( 
                               
                                 
                                   
                                     
                                       A 
                                       z 
                                     
                                     ⁢ 
                                     z 
                                   
                                   + 
                                   
                                     
                                       B 
                                       z 
                                     
                                     ⁢ 
                                     u 
                                   
                                 
                                 , 
                                 
                                   
                                     F 
                                     ⁡ 
                                     ( 
                                     
                                       
                                         
                                           A 
                                           z 
                                         
                                         ⁢ 
                                         z 
                                       
                                       + 
                                       
                                         
                                           B 
                                           z 
                                         
                                         ⁢ 
                                         u 
                                       
                                     
                                     ) 
                                   
                                   : 
                                      
                                   F 
                                 
                               
                               ) 
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   20 
                   ) 
                 
               
             
           
         
       
     
     The problem setting based on equations (1) to (9) thereby becomes equivalent to the problem setting that is fully observed regarding the vector z t  and that uses equation (14) and equation (19) or (20). The reinforcement learning apparatus  100  updates the coefficient matrix F using equation (19) or (20). 
     For example, the reinforcement learning apparatus  100  expresses the function Q of equation (20) using the quadratic form of u and z, and produces an equation formed by connecting the function Q by an equal sign to the immediate cost. The reinforcement learning apparatus  100  calculates the coefficient matrix for u and z of this equation using, as teacher data, the observed inputs u t , u t−1 , . . . , u t−n−1 , the vectors z t , z t−1 , . . . , z t−n−1 , and the immediate costs c t−1 , c t−2 , . . . , c t−n−2 . 
     When the reinforcement learning apparatus  100  calculates the coefficient matrix, the reinforcement learning apparatus  100  may use, for example, a batch least squares method, a sequential least squares method, a batch LSTD algorithm, or a sequential LSTD algorithm. For the batch least squares method, the sequential least squares method, the batch LSTD algorithm, and the sequential LSTD algorithm, Y. Zhu and X. R. Li, “Recursive Least Squares with Linear Constraints”, Communications in Information and Systems, Vol. 7, No. 3, pp. 287-312, 2007; and C. Dann and G. Neumann and J. Peters, “Policy Evaluation with Temporal Differences: A Survey and Comparison”, Journal of Machine Learning Research, Vol. 15, pp. 809-883, 2014 may be referred to. 
     The reinforcement learning apparatus  100  updates the coefficient matrix F based on the calculated coefficient matrix and an equation for which the result of differentiation of the function Q with respect to u is zero. For the updating of the coefficient matrix F, S. J. Bradtke, B. E. Ydstie and A. G. Barto, “Adaptive linear quadratic control using policy iteration”, In Proc. of the 1994 American Control Conference, pp. 3475-3479, Baltimore, USA, 1994, may be referred to. 
     The reinforcement learning apparatus  100  determines the input value at the present time based on equation (10) using the updated coefficient matrix F. While a case where the reinforcement learning apparatus  100  uses the immediate cost has been described, the item used is not limited hereto. For example, the reinforcement learning apparatus  100  may use the immediate reward. 
     The reinforcement learning apparatus  100  may thereby accurately determine the input value for the controlled object  110  and may also efficiently minimize the accumulated cost because the reinforcement learning apparatus  100  uses the output at the present time when the reinforcement learning apparatus  100  determines the input value at the present time. The reinforcement learning apparatus  100  may therefore facilitate reduction of the time period for establishing the state where the state of the controlled object  110  is advantageous. Even when the state of the controlled object  110  is varied due to an external factor, the reinforcement learning apparatus  100  may efficiently control the controlled object  110  in a relatively short time period from the variation. 
     Specific examples of the controlled object  110  will be described with reference to  FIGS.  4  and  5   . 
       FIGS.  4  and  5    are explanatory diagrams each of a specific example of the controlled object  110 . In the example of  FIG.  4   , the controlled object  110  is a server room  400  that includes a server  401  to be a heat source, and a cooler  402  such as a CRAC or a chiller. 
     The input is a set temperature or a set air volume for the cooler  402 . The output is sensor data from a sensor device disposed in the server room  400  and is, for example, a temperature. The output may be data regarding the controlled object  110  acquired from any object other than the controlled object  110  and may be, for example, the atmospheric temperature or the weather. The state is, for example, the temperature in the server room  400  that includes a temperature that is not observable as an output. The immediate cost is, for example, the power consumption for 5 minutes of the server room  400 . The value function is, for example, the accumulated power consumption of the server room  400 . 
     In the example of  FIG.  4   , analysis of the influence of the set temperature and the set air amount for the cooler  402  acting on the power consumption of the server room  400  tends to be difficult and the influence may be unknown. In other words, a case is present where the influence of the input on the immediate cost is unknown and a case is present where the coefficient matrix for the input of the immediate cost equation in the quadratic form is unknown. Even in these cases, the reinforcement learning apparatus  100  may control the controlled object  110 . 
     With the fourth control approach, because it is difficult to set any advantageous values as k and l, it is difficult in the example of  FIG.  4    to efficiently learn the control law and accurately determine the input value for the controlled object  110 . In contrast, because the reinforcement learning apparatus  100  does not use k and l, the reinforcement learning apparatus  100  enables efficient learning of the control law and accurate determination of the input value for the controlled object  110  to be facilitated even in the example of  FIG.  4   . 
     For example, with the fourth control approach, because the output at the present time is not used when the input value at the present time is determined, it is difficult in the example of  FIG.  4    to efficiently learn the control law and accurately determine the input value for the controlled object  110 . In contrast, because the reinforcement learning apparatus  100  uses the output at the present time when the reinforcement learning apparatus  100  determines the input value at the present time, the reinforcement learning apparatus  100  may accurately determine the input value for the controlled object  110  even in the example of  FIG.  4   . 
     With the fifth control approach, because the coefficient matrix in the immediate cost equation in the quadratic form with respect to the input for the controlled object  110  is used as the part of the control law, a situation is assumed where the coefficient matrix in the immediate cost equation in the quadratic form with respect to the input for the controlled object  110  is assumed to be known and thus, the control law cannot be learned in the example of  FIG.  4   . In contrast, the reinforcement learning apparatus  100  may expand the scope of the object that may be set as the controlled object  110  because the coefficient matrix in the immediate cost equation in the quadratic form with respect to the input for the controlled object  110  may be unknown. 
     In the example of  FIG.  5   , the controlled object  110  is an electric generator  500 . The input is a command value for the electric generator  500 . The output is sensor data from a sensor device disposed in the electric generator  500 . The state is, for example, the rotation amount of a turbine of the electric generator  500 . The immediate reward is, for example, the generated electric power amount for 5 minutes of the electric generator  500 . The value function is, for example, the accumulated generated electric power amount of the electric generator  500 . 
     In the example of  FIG.  5   , a case is present where the influence of the command value for the electric generator  500  acting on the generated electric power amount of the electric generator  500  is unknown. In other words, a case is present where the influence of the input on the immediate reward is unknown and a case is present where the coefficient matrices for the input in the immediate cost equation in the quadratic form are unknown. Even in these cases, the reinforcement learning apparatus  100  may control the controlled object  110 . The controlled object  110  may be, for example, a chemical plant, an autonomous mobile robot, or an industrial robot. 
     An example of a procedure for a reinforcement learning process will be described with reference to  FIGS.  6  and  7   . 
       FIG.  6    is a flowchart of an example of the procedure for the reinforcement learning process in a batch processing form. In the example of  FIG.  6   , a case will be described where the reinforcement learning apparatus  100  uses the state-action-value function as the value function. 
     In  FIG.  6   , the reinforcement learning apparatus  100  first initializes the coefficient matrix F, determines the inputs u 0 , u 1 , . . . , and u n−2 , and observes the outputs y 0 , y 1 , and y n−2 , and the immediate costs c 0 , c 1 , . . . , and c n−3  (step S 601 ). 
     The reinforcement learning apparatus  100  observes the output y t  and the immediate cost c t−1  that correspond to the previous input u t−1 , and calculates the input u t =Fz t ε t  (step S 602 ). The reinforcement learning apparatus  100  determines whether the reinforcement learning apparatus  100  has repeated step S 602  N times (step S 603 ). 
     When the reinforcement learning apparatus  100  determines that the reinforcement learning apparatus  100  has not repeated step S 602  N times (step S 603 : NO), the reinforcement learning apparatus  100  returns to the process at step S 602 . On the other hand, when the reinforcement learning apparatus  100  determines that the reinforcement learning apparatus  100  has repeated step S 602  N times (step S 603 : YES), the reinforcement learning apparatus  100  moves to the process at step S 604 . 
     The reinforcement learning apparatus  100  calculates the estimation function of the value function, based on the inputs u t , u t−1 , . . . , u t−n−t , the vectors z t , z t−1 , . . . , z t−n−1 , and the immediate costs c t−1 , c t−2 , . . . , c t−n−2  (step S 604 ). 
     The reinforcement learning apparatus  100  updates the coefficient matrix F, based on the estimation function of the value function (step S 605 ). The reinforcement learning apparatus  100  returns to the process at step S 602 . The reinforcement learning apparatus  100  may thereby control the controlled object  110 . When the reinforcement learning apparatus  100  uses the state-value function and not the state-action-value function, the reinforcement learning apparatus  100  needs not use the input u t  in each of the above processes. 
       FIG.  7    is a flowchart of an example of a procedure for a reinforcement learning process in a sequential processing form. In the example of  FIG.  7   , a case will be described where the reinforcement learning apparatus  100  uses the state-action-value function as the value function. 
     In  FIG.  7   , the reinforcement learning apparatus  100  first initializes the coefficient matrix F and the estimation function of the value function, determines the inputs u 0 , u 1 , . . . , u n−2 , and observes the outputs y 0 , y 1 , . . . , y n−2  and the immediate costs c 0 , . . . , u n−2  (step S 701 ). 
     The reinforcement learning apparatus  100  observes the output y t  and the immediate cost c t−1  that correspond to the previous input u t−1 , and calculates the input u t =Fz t +ε t  (step S 702 ). The reinforcement learning apparatus  100  updates the estimation function of the value function, based on the inputs u t  and u t−1 , the vectors z t  and z t−1 , and the immediate cost c t−1  (step S 703 ). 
     The reinforcement learning apparatus  100  determines whether the reinforcement learning apparatus  100  has repeated step S 703  N times (step S 704 ). When the reinforcement learning apparatus  100  determines that the reinforcement learning apparatus  100  has not repeated step S 703  N times (step S 704 : NO), the reinforcement learning apparatus  100  returns to the process at step S 702 . On the other hand, when the reinforcement learning apparatus  100  determines that the reinforcement learning apparatus  100  has repeated step S 703  N times (step S 704 : YES), the reinforcement learning apparatus  100  moves to the process at step S 705 . 
     The reinforcement learning apparatus  100  updates the coefficient matrix F, based on the estimation function of the value function (step S 705 ). The reinforcement learning apparatus  100  returns to the process at step S 702 . The reinforcement learning apparatus  100  may thereby control the controlled object  110 . When the reinforcement learning apparatus  100  uses the state-value function and not the state-action-value function, the reinforcement learning apparatus  100  needs not use the input u t  in each of the above processes. 
     As described, according to the reinforcement learning apparatus  100 , the coefficients of the value function may be estimated based on the inputs at the times in the past, the outputs at the present time and the times in the past, and the cost or the reward corresponding to the inputs at the times in the past. According to the reinforcement learning apparatus  100 , the input value at the time after the estimation may be determined based on the value function that uses the estimated coefficients. The reinforcement learning apparatus  100  may thereby efficiently learn the control law and accurately determine the input value. 
     According to the reinforcement learning apparatus  100 , the function that is represented by the quadratic form of the inputs at the present time and the times in the past, and the outputs at the present time and the times in the past may be used as the value function. The reinforcement learning apparatus  100  may thereby use the state-action-value function. 
     According to the reinforcement learning apparatus  100 , the input value at the time after the estimation may be determined using the outputs at the times after the estimation based on the value function. The reinforcement learning apparatus  100  may thereby facilitate improvement of the precision for determining the input value. 
     According to the reinforcement learning apparatus  100 , the coefficients of the value function may be estimated for the control problem using the value function that is fully observed regarding the inputs at the times in the past and the outputs at the present time and the times in the past. The reinforcement learning apparatus  100  may thereby learn the control law and determine the input value even for the case where the coefficient that indicates the degree of the influence of the input acting on the cost or the reward is unknown. 
     The reinforcement learning method described in the present embodiment may be realized by causing a computer such as a personal computer, a work station, or a microcontroller to execute the programs prepared in advance. The reinforcement learning program described in the present embodiment is recorded in a computer-readable recording medium such as a hard disk, a flexible disk, a CD-ROM, an MO, or a DVD, and is executed by being read by a computer from the recording medium. The reinforcement learning program described in the present embodiment may be distributed through a network such as the Internet. 
     According to an aspect of the present invention, an effect is achieved in that accurate determination of the input value for the controlled object may be facilitated. 
     All examples and conditional language provided herein are intended for pedagogical purposes of aiding the reader in understanding the invention and the concepts contributed by the inventor to further the art, and are not to be construed as limitations to such specifically recited examples and conditions, nor does the organization of such examples in the specification relate to a showing of the superiority and inferiority of the invention. Although one or more embodiments of the present invention have been described in detail, it should be understood that the various changes, substitutions, and alterations could be made hereto without departing from the spirit and scope of the invention.