Abstract:
A method and system for deciding an optimal action in consideration of risk. The method includes the steps of: generating sequentially, by way of a Markov decision process based on a Monte Carlo method, a series of data objects having states on a memory of a computer; computing a risk measure of a data object by tracking generated data from opposite order to generation order, where the risk measure is calculated from a value at risk or an exceedance probability that is derived from risk measures of a plurality of states transitionable from a state of the data object; and executing the step of computing the risk measure while tracking back to starting data, where at least one of the steps is carried out using a computer device.

Description:
CROSS-REFERENCE TO RELATED APPLICATION 
       [0001]    This application is a continuation application of commonly-owned U.S. patent application Ser. No. 13/371,513, filed Feb. 13, 2012, which application claims priority under 35 U.S.C. §119 from Japanese Patent Application No. 2011-029660 filed Feb. 15, 2011, the entire contents of which are incorporated herein by reference. 
     
    
     BACKGROUND OF THE INVENTION 
       [0002]    1. Field of the Invention 
         [0003]    The present invention relates to a technique of deciding an optimal action in consideration of risk. More specifically, the present invention relates to a technique of deciding an action using Markov decision process (MDP). 
         [0004]    2. Description of Related Art 
         [0005]    A simulation system and simulation method of integrally evaluating interest risk and credit risk of a portfolio are described in Japanese Unexamined Patent Publication No. 2002-230280. The technique provides that: (1) a large number of scenarios from a present time to a risk horizon are generated based on a default-free interest process model and a default process model; (2) a price of a portfolio and a price of an individual asset in the risk horizon are computed for each of the generated scenarios; and (3) a future price distribution of the portfolio and/or a future price distribution of the individual asset are determined based on the computed prices. As a result, the technique integrally evaluates interest risk and credit risk of the portfolio. 
         [0006]    Research is also conducted on a risk computation technique that uses a Markov process. The Markov process has a Markov property, where its future state transition depends only on its present state and independently of its past state. Research is further conducted on an action decision technique that uses a Markov decision process, which is an extension of the Markov process. For example, for a target capable of undergoing state transitions, a Markov decision process problem is a problem to find a rule for deciding an action to be executed in each state in order to maximize an expected cumulative reward obtained from the target. 
         [0007]    To provide a credit portfolio control method used for selecting an optimal policy in credit control to enable situations of external factors such as an economic environment and a set credit line to be reflected on a future credit rating transition probability, Japanese Patent No. 4400837 discloses a technique of creating a graph in which transitions of combinations of each state of an existing credit and each state of an external factor from the first to T-th years are represented. The technique provides: (1) for the first year, a node including an existing credit&#39;s initial state and the external factor&#39;s initial state and; and (2) for the second to T-th years, nodes indicating patterns of combinations of each state of the existing credit and each state of the external factor. The aforementioned technique corresponds to finding an optimal policy that, by way of solving a Markov decision process problem of T years by dynamic programming (DP), maximizes an expected total gain for T years while tracking back from a terminal T-th year node. 
         [0008]    In addition, an iterated risk measure is recently receiving attention as a risk measure based on which a financial institution determines its capital. A (conditional) value at risk is also called a CTE (conditional tail expectation), but has no time consistency. However, the iterated risk measure has time consistency. This is described in M. R. Hardy and J. L. Wirch, “The iterated CTE: A dynamic risk measure”, The North American Actuarial Journal, 62-75, 2004. 
         [0009]    However, a backward-computed iterated CTE (ICTE) is considered to be difficult to implement, because ICTE requires a large computation load. Furthermore, a typical Monte Carlo method cannot handle ICTE. 
         [0010]    The iterated risk measure can represent risk preference that is rational but cannot be represented by expected utility, discounted expected utility, or the like. Accordingly, Japanese Patent Application No. 2010-211588 discloses a technique of optimizing a Markov decision process so as to minimize the iterated risk measure using dynamic programming. 
         [0011]    However, the technique described in the specification of Japanese Patent Application No. 2010-211588 requires an extremely long computation time when the number of possible states or actions increases. Thus, the technique can actually solve only limited problems, and as a result the technique is constrained. 
       SUMMARY OF THE INVENTION 
       [0012]    Accordingly, one aspect of the present invention provides a method for computing an iterated risk measure, the method including the steps of: generating sequentially, by way of a Markov decision process based on a Monte Carlo method, a series of data having states on a memory of a computer; computing a risk measure of a present data by tracking generated data from opposite order to generation order, where the risk measure is calculated from a value at risk or an exceedance probability that is derived from risk measures of a plurality of states transitionable from a state of the present data; and executing the step of computing the risk measure while tracking back to starting data, where at least one of the steps is carried out using a computer device. 
         [0013]    Another aspect of the present invention provides a method for computing an action that minimizes an iterated risk measure, the method including the steps of: generating, during postdecision, data including combinations of a predetermined state and a possible action on a memory of the computer; selecting a state-action combination data from generated data of the combinations of the state and the action, based on a value associated with each of the combinations; generating, during predecision, a state from selected state-action combination data, by way of a Markov decision process based on a Monte Carlo method; generating a state data sequence by iterating the step of generating a state and the step of generating data including combinations; computing, based on risk measures of a plurality of states transitionable from a present predecision state, a risk measure of an immediately preceding postdecision state by tracking generated states in opposite order to order of the generation, where the risk measure is calculated from a value at risk or an exceedance probability; and setting a value of a state having a minimum value in a present postdecision state to an immediately preceding predecision state, by tracking the generated states in the opposite order to the order of the generation, where at least one of the steps is carried out using a computer device. 
         [0014]    Another aspect of the present invention provides a system for computing an iterated risk measure, the system including: a generating module for generating sequentially, by way of a Markov decision process based on a Monte Carlo method, a series of data having states on a memory of a computer; a risk measure module for computing a risk measure of a present object by tracking generated data from opposite order to generation order, where the risk measure is calculated from a value at risk or an exceedance probability that is derived from risk measures of a plurality of states transitionable from a state of the present object; and an executing module for executing the risk measure module while tracking back to starting object. 
         [0015]    Another aspect of the present invention provides a system for computing an action that minimizes an iterated risk measure, the system including: a postdecision module for generating, during postdecision, data including combinations of a predetermined state and a possible action on a memory of the computer; a selecting module for selecting a state-action combination data from generated data of the combinations of the state and the action, based on a value associated with each of the combinations; a predecision module for generating, during predecision, a state from selected state-action combination data, by way of a Markov decision process based on a Monte Carlo method; a state data sequence module for generating a state data sequence by iterating the step of generating a state and the step of generating data including combinations; a risk measure module for computing, based on risk measures of a plurality of states transitionable from a present predecision state, a risk measure of an immediately preceding postdecision state by tracking generated states in opposite order to order of the generation, where the risk measure is calculated from a value at risk or an exceedance probability; and a value module for setting a value of a state having a minimum value in a present postdecision state to an immediately preceding predecision state, by tracking the generated states in the opposite order to the order of the generation. 
         [0016]    According to the present invention, it becomes possible to provide a technique of approximately obtaining an iterated risk measure at high speed using a probabilistic method such as a Monte Carlo method, where a typical iterated risk measure normally requires considerable time when precisely computed. 
         [0017]    It is also possible to provide a technique of obtaining an action sequence that minimizes an iterated risk measure at high speed, using the above-mentioned technique of approximately obtaining an iterated risk measure at high speed. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0018]      FIG. 1  is a block diagram showing a hardware structure as an example for implementing the present invention. 
           [0019]      FIG. 2  is a functional block diagram of a logical structure for a process of computing an iterated risk measure according to an embodiment of the present invention. 
           [0020]      FIG. 3  is a flowchart of the process of computing an iterated risk measure according to an embodiment of the present invention. 
           [0021]      FIG. 4  is a flowchart of a process of a SAMPLE_POLICY routine in the process of computing an iterated risk measure. 
           [0022]      FIG. 5  is a diagram showing correspondence between states and reaching probabilities referenced to in the SAMPLE_POLICY routine. 
           [0023]      FIG. 6  is a flowchart of a process of an UPDATE_VALUE routine in the process of computing an iterated risk measure. 
           [0024]      FIG. 7  is a diagram showing correspondence between states, values, and reaching probabilities referenced to in the UPDATE_VALUE routine. 
           [0025]      FIG. 8  is a diagram schematically showing the process of computing an iterated risk measure. 
           [0026]      FIG. 9  is a functional block diagram of a logical structure for a process of deciding an action that minimizes an iterated risk measure according to the present invention. 
           [0027]      FIG. 10  is a flowchart of the process of deciding an action that minimizes an iterated risk measure according to the present invention. 
           [0028]      FIG. 11  is a flowchart of a process of an EXPLORATION_POLICY routine in the process of deciding an action that minimizes an iterated risk measure. 
           [0029]      FIG. 12  is a diagram showing correspondence between postdecision states, values, and counters referenced to in the EXPLORATION_POLICY routine. 
           [0030]      FIG. 13  is a flowchart of a process of an UPDATE_VALUE_MIN routine in the process of deciding an action that minimizes an iterated risk measure. 
           [0031]      FIG. 14  is a diagram showing correspondence between postdecision states and values referenced to in the UPDATE_VALUE_MIN routine. 
           [0032]      FIG. 15  is a diagram schematically showing the process of deciding an action that minimizes an iterated risk measure. 
       
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS 
       [0033]    The following describes an embodiment of the present invention based on drawings. The same reference numerals designate the same elements throughout the drawings, unless otherwise stated. Note that the following merely describes one embodiment of the present invention, and the scope of the present invention is not limited to this embodiment. 
         [0034]    It is an object of the present invention to provide a technique of computing an iterated risk measure at high speed using a Monte Carlo method, in a Markov process. 
         [0035]    It is another object of the present invention to provide a technique of approximately deciding an action that minimizes an iterated risk measure by applying the above-mentioned technique of computing an iterated risk measure at high speed, in a Markov decision process of such a size that cannot be precisely optimized. 
         [0036]    In a first aspect of the present invention, a state sequence (S1, S2, . . . , Sn) is generated by sequential sampling based on a Markov process, by processing of a computer. A (iterated risk measure provisional) value (V(Sn), . . . , V(S2), V(S1)) of each state is then updated in opposite order (Sn, . . . , S2, S1) to the generation order. 
         [0037]    A value V(Si) of each state Si is updated according to a risk measure (especially computed using a value at risk or an exceedance probability or partially using them) of a random variable defined from a transition probability p(Si+1(j)|Si) to a state (Si+1(1), Si+1(2), . . . , Si+1(m)) reachable from the state by one transition and a value V(Si+1(j)) of the transition destination. Iterating this process of a predetermined duration yields an iterated risk measure approximate value. Hereafter, the iterated risk measure provisional value is also simply referred to as a “value”. 
         [0038]    In a second aspect of the present invention, a technique of approximately deciding an action that minimizes an iterated risk measure in a specific state through the use of the above-mentioned technique of approximately computing a risk measure is provided. In this technique, states are generated so that a predecision state and a postdecision state appear alternately in the above-mentioned technique of the first aspect. 
         [0039]    A (iterated risk measure provisional) value of a postdecision state is computed using a value of a next reachable predecision state, as in the above-mentioned technique of the first aspect. A (iterated risk measure provisional) value of a predecision state is updated using a minimum iterated risk measure provisional value of a next reachable postdecision state. As a result of iteration, an action sequence that minimizes an iterated risk measure is selected. 
         [0040]      FIG. 1  is a block diagram of computer hardware for realizing a system structure and process according to an embodiment of the present invention. In  FIG. 1 , a CPU  104 , a main memory (RAM)  106 , a hard disk drive (HDD)  108 , a keyboard  110 , a mouse  112 , and a display  114  are connected to a system path  102 . The CPU  104  is preferably based on a 32-bit or 64-bit architecture. For example, Pentium™ 4, Core™ 2 Duo, or Xeon™ by Intel Corporation, Athlon™ by AMD, or the like can be used for the CPU  104 . The main memory  106  preferably has a capacity of 4 GB or more. The hard disk drive  108  desirably has a capacity of, for example, 500 GB or more, to allow a large amount of data to be stored. 
         [0041]    The hard disk drive  108  stores an operating system beforehand, though not shown. The operating system can be an arbitrary operating system compatible with the CPU  104 , such as Linux™, Windows XP™ or Windows™ 7 by Microsoft Corporation, or Mac OS™ by Apple Inc. 
         [0042]    The hard disk drive  108  also stores data and parameters for probability computation of a Markov decision process, processing routines for the process according to the present invention, and so on. These parameters and processing routines will be described in detail later, with reference to  FIG. 2 . 
         [0043]    The keyboard  110  and the mouse  112  are used to activate the operating system or a program (not shown) which is loaded from the hard disk drive  108  into the main memory  106  and displayed on the display  114 , or enter characters. 
         [0044]    The display  114  is preferably a liquid crystal display, and can have, for example, an arbitrary resolution such as XGA (1024×768 in resolution) or UXGA (1600×1200 in resolution). The display  114  is used to display an operation window for starting the process according to the present invention, a computation result of a selected action, risk, and the like, though not shown. 
         [0045]    The following describes processing routines for executing especially a process of approximately computing an iterated risk measure according to the present invention, with reference to a functional block diagram in  FIG. 2 . These processing routines are generated in an existing programming language such as C, C++, or Java® beforehand, held in the hard disk drive  108  in an executable form, and loaded into the main memory  106  and executed according to the operating system. 
         [0046]    In this embodiment, a process of selecting a stock in which a user is to invest in each term with predetermined money in possession is described as the process according to the present invention, though the present invention is not limited to such. The following scenario is assumed. A stock in which the user is to invest in each term is selected, starting from predetermined money in possession. A state is represented by a combination of (money in possession, stock in which the user invests, time). There are action candidates as many as stock types. In each term, there are action candidates as many as stock types, and which stock the user is to invest in is decided. A return as a result of taking an action in each state is determined by a return for a period of a corresponding stock. 
         [0047]    A main routine  202  is a program for an overall operation according to the present invention, and has a function of displaying an operation window on the display  114 , receiving a user operation and starting a process, and the like, though not shown. 
         [0048]    A parameter  204  includes parameters and data for computing probability of a Markov decision process indicating performance of various stocks, and the like. 
         [0049]    A SAMPLE_POLICY routine  206  is a routine for performing a process of generating a state with a predetermined probability by a generated random number, according to a Monte Carlo method. 
         [0050]    An UPDATE_VALUE routine  208  is a routine for computing a risk measure by referencing to a set of directly transitionable states. 
         [0051]    An output routine  210  is a routine for outputting a risk value as a computation result. The computation result is displayed on the display  114  according to need. 
         [0052]    The following describes the process of approximately computing an iterated risk measure according to the present invention, with reference to a flowchart in  FIG. 3 . For example, this process is started by an operator operating a menu of a window screen displayed on the display  114  using the keyboard  110  or the mouse  112 . 
         [0053]    In this embodiment, it is assumed that a series of data objects for storing states are already loaded into the main memory  106  prior to the process described below. The data objects are, for example, instances of a class in Java® or C++.  FIG. 8  schematically shows such data objects. A series of data objects  802 ,  804 ,  806 , and  808  is shown in  FIG. 8 . 
         [0054]    In step  302 , the main routine  202  sets an initial value of a variable s indicating a state, from the parameter  204 . The variable s is set to an attribute value of the data object  802  which is the first data object in  FIG. 8 . For example, the state is represented by a combination of (money in possession, stock in which the user invests, time). 
         [0055]    In step  304 , the main routine  202  pushes the state s onto a stack. Such pushing the state s onto the stack is performed for later popping and backtracking of the state. 
         [0056]    Next, in step  306 , the main routine  202  calls the SAMPLE_POLICY routine  206  by SAMPLE_POLICY(s) using s as an argument. 
         [0057]      FIG. 4  shows a detailed process of the SAMPLE_POLICY routine  206 . In  FIG. 4 , the SAMPLE_POLICY routine  206  generates, for i=1, . . . , n, a random number so that i occurs with a probability p i , in step  402 . The generated random number is denoted by m (1≦m≦n). The probability p i  mentioned here is a probability of transiting from the state s to a state s i , in a Markov process context. 
         [0058]      FIG. 5  shows a transition probability of each state s i  from s. Such correspondence information is prepared beforehand for each different s, in the parameter  204 . 
         [0059]    The SAMPLE_POLICY routine  206  outputs a state s m  corresponding to the random number m in step  404 . 
         [0060]    Returning to step  306  in  FIG. 3 , such a returned value s m  is assigned to s. This corresponds to a situation where a transition is made to a state S2 of the data object  804  in  FIG. 8 . 
         [0061]    In step  308 , the main routine  202  pushes the state s onto the stack. In step  310 , the main routine  202  determines whether or not to stop forward sampling. A criterion for stopping forward sampling is, for example, whether or not states are generated for a predetermined number of stages. In the example in  FIG. 8 , the state  802  is the first stage, the state  804  is the second stage, the state  806  is the third stage, and the state  808  is the fourth stage. Alternatively, the criterion for stopping forward sampling can be whether or not a predetermined time elapses from the start of the process. 
         [0062]    In the case where the main routine  202  determines that the criterion for stopping forward sampling is not met, the main routine  202  returns to step  306  and calls the SAMPLE_POLICY routine  206 . 
         [0063]    On the other hand, in the case where the main routine  202  determines that the criterion for stopping forward sampling is met in step  310 , the main routine  202  goes to step  312 , and pops the state s from the stack. 
         [0064]    Next, in step  314 , the main routine  202  calls the UPDATE_VALUE routine  208  by UPDATE_VALUE(s). 
         [0065]      FIG. 6  shows a detailed process of the UPDATE_VALUE routine  208 . Step  602  is a definition block. In step  602 , the UPDATE_VALUE routine  208  sets {s 1 , s 2 ,  . . . , s n } as a set of states directly transitionable from s (i.e. having a transition probability more than 0), where n is the number of directly transitionable states from s. In the example in  FIG. 8 , states  806   a,    806   b,  and  806   c  are directly transitionable states from the state S2 designated by reference numeral  804   c.  The UPDATE_VALUE routine  208  also sets, for i=1, . . . , n, p i  as a probability of transitioning from s to s i , and v i  as a value (iterated risk measure provisional value) of s i .  FIG. 7  shows this correspondence. In  FIG. 7 , the fields of the state and the reaching probability from s are based on values stored in the parameter  204  beforehand, but the field of the value can initially store 0. This being the case, values are sequentially stored as a result of computation. Alternatively, the value can be initially set as the money in possession in the state. The present invention can be realized with other initial value settings. 
         [0066]    In step  604 , the UPDATE_VALUE routine  208  computes, for i=1, . . . , n, a α% value at risk of a random variable X that takes the value v i  with the probability p i , according to the following expression. The computation result is denoted by V α . 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       VaR 
                       α 
                     
                      
                     
                       % 
                        
                       
                         [ 
                         X 
                         ] 
                       
                     
                   
                   = 
                   
                     
                       inf 
                       
                         x 
                         ∈ 
                         R 
                       
                     
                      
                     
                       { 
                       
                         
                           
                             ∑ 
                             
                               
                                 i 
                                  
                                 
                                   : 
                                 
                                  
                                 
                                     
                                 
                                  
                                 
                                   v 
                                   i 
                                 
                               
                               &gt; 
                               x 
                             
                           
                            
                           
                               
                           
                            
                           
                             p 
                             i 
                           
                         
                         ≤ 
                         
                           1 
                           - 
                           
                             α 
                             100 
                           
                         
                       
                       } 
                     
                   
                 
               
               
                 
                   [ 
                   
                     Math 
                     . 
                     
                         
                     
                      
                     1 
                   
                   ] 
                 
               
             
           
         
       
     
         [0067]    An exceedance probability can be computed instead of V α , according to the following expression. 
         [0000]    
       
         
           
             
               
                 
                   
                     Pr 
                      
                     
                       ( 
                       
                         X 
                         &gt; 
                         x 
                       
                       ) 
                     
                   
                   = 
                   
                     
                       ∑ 
                       
                         
                           i 
                            
                           
                             : 
                           
                            
                           
                               
                           
                            
                           
                             v 
                             i 
                           
                         
                         &gt; 
                         x 
                       
                     
                      
                     
                         
                     
                      
                     
                       p 
                       i 
                     
                   
                 
               
               
                 
                   [ 
                   
                     Math 
                     . 
                     
                         
                     
                      
                     2 
                   
                   ] 
                 
               
             
           
         
       
     
         [0068]    In step  606 , the UPDATE_VALUE routine  208  computes a risk measure v of X, using V α  or the exceedance probability. For example, this computation is performed as v=E[X|X&gt;V α ]. As an alternative, the risk measure v can be computed by the following expression partially using the exceedance probability. 
         [0000]        p   n   [Y]=E[Y]−c ( Pr ( Y≦ 0)−α) I{Pr ( Y≦ 0)≧α}  [Math. 3]
 
         [0069]    In this expression, I{} is a function that returns 1 when the expression in {} is true, and 0 when the expression in {} is false. 
         [0070]    In step  608 , the UPDATE_VALUE routine  208  stores the computed v as a value corresponding to the state s. In the example in  FIG. 8 , the risk measure v computed based on the states  806   a,    806   b,  and  806   c  is stored in association with the state S2. 
         [0071]    Returning to the process of the flowchart in  FIG. 3 , after step  314  of calling UPDATE_VALUE(s), the main routine  202  determines whether or not the stack is empty in step  316 . In the case where the stack is not empty, the main routine  202  returns to step  312 . 
         [0072]    In the case where the main routine  202  determines that the stack is empty in step  316 , the main routine  202  determines whether or not a stopping condition is met in step  318 . The stopping condition mentioned here is any of whether or not a predetermined time elapses from the start of the process shown in the flowchart in  FIG. 3 , whether or not a loop of steps  302  to  318  is performed a predetermined number of times, or whether or not a risk measure computed value at the starting point designated by S1 in  FIG. 8  eventually has only a change of a threshold or below from a value computed in the immediately preceding loop of steps  302  to  318 , though the present invention is not limited to such. 
         [0073]    In the case where the main routine  202  determines that the stopping condition is not met in step  318 , the main routine  202  returns to step  302 , to resume computation from the first state S1 in  FIG. 8 . At this time, the previously computed risk measure values (the values in the value field in  FIG. 7 ) are maintained, so that the intermediate risk measure values which were initially mostly 0 are gradually changed to nonzero values as the loop of steps  302  to  318  is repeated. 
         [0074]    In the case where the main routine  202  determines that the stopping condition is met in step  318 , the process ends, and the output routine  210  outputs a risk measure value corresponding to the first state S1 in  FIG. 8 . 
         [0075]    The following describes processing routines for executing a process of approximately deciding an action that minimizes an iterated risk measure in a specific state according to the present invention, with reference to a functional block diagram in  FIG. 9 . These processing routines are also generated in an existing programming language such as C, C++, or Java® beforehand, held in the hard disk drive  108  in an executable form, and loaded into the main memory  106  and executed according to the operating system. 
         [0076]    The process of approximately deciding an action that minimizes an iterated risk measure uses the routine for approximately computing an iterated risk measure shown in  FIG. 2 , and so there are some common processing routines. However, the processing routines in  FIG. 9  are given different reference numerals from those in  FIG. 2 . 
         [0077]    In this embodiment, too, a process of selecting a stock in which the user is to invest in each term with predetermined money in possession is described as the process according to the present invention. The following scenario is assumed. A stock in which the user is to invest in each term is selected, starting from predetermined money in possession. A state is represented by a combination of (money in possession, stock in which the user invests, time). There are action candidates as many as stock types. In each term, there are action candidates as many as stock types, and which stock the user is to invest in is decided. A return as a result of taking an action in each state is determined by a return for a period of a corresponding stock. 
         [0078]    A main routine  902  is a program for an overall operation according to the present invention, and has a function of displaying an operation window on the display  114 , receiving a user operation and starting a process, and the like, though not shown. 
         [0079]    A parameter  904  includes parameters and data for computing probability of a Markov decision process indicating performance of various stocks, and the like. 
         [0080]    A SAMPLE_POLICY routine  906  is a routine for performing a process of generating a state with a predetermined probability by a generated random number, according to a Monte Carlo method. The SAMPLE_POLICY routine  906  can be the same as the SAMPLE_POLICY routine  206  in  FIG. 2 . 
         [0081]    An EXPLORATION_POLICY routine  908  is a routine for selecting a postdecision state. 
         [0082]    An UPDATE_VALUE routine  910  is a routine for computing a risk measure by referencing to a set of directly transitionable states. The UPDATE_VALUE routine  910  can be the same as the UPDATE_VALUE routine  208  in  FIG. 2 . 
         [0083]    An UPDATE_VALUE_MIN routine  912  is a routine for returning a minimum value in the set of directly transitionable states. 
         [0084]    An output routine  914  is a routine for outputting an action sequence as a computation result. The computation result is displayed on the display  114  according to need. 
         [0085]    The following describes the process of approximately deciding an action that minimizes an iterated risk measure according to the present invention, with reference to a flowchart in  FIG. 10 . For example, this process is started by an operator operating a menu of a window screen displayed on the display  114  using the keyboard  110  or the mouse  112 . 
         [0086]    In this embodiment, it is assumed that a series of data objects for storing states are already loaded into the main memory  106  prior to the process described below. The data objects are, for example, instances of a class in Java® or C++.  FIG. 15  schematically shows such data objects. A series of data objects  1502 ,  1504 ,  1506 ,  1508 ,  1510 ,  1512 ,  1514 , and  1516  is shown in  FIG. 15 . In this embodiment, two states that are a predecision state and a postdecision state are used. In  FIG. 15 , the data objects  1502 ,  1506 ,  1510 , and  1514  correspond to predecision states, and the data objects  1504 ,  1508 ,  1512 , and  1516  correspond to postdecision states. 
         [0087]    In step  1002 , the main routine  902  sets an initial value of a variable s indicating a state, from the held parameter  904 . The variable s is set to an attribute value of the data object  1502  which is the first data object in  FIG. 15  and corresponds to a predecision state. For example, the state is represented by a combination of (money in possession, stock in which the user invests, time). 
         [0088]    In step  1004 , the main routine  902  pushes the state s onto a stack. Such pushing the state s onto the stack is performed for later popping and backtracking of the state. 
         [0089]    In step  1006 , the main routine  902  calls the EXPLORATION_POLICY routine  908  by EXPLORATION_POLICY(s) using s as an argument. 
         [0090]      FIG. 11  shows a detailed process of the EXPLORATION_POLICY routine  908 . As shown in definition step  1102 , the EXPLORATION_POLICY routine  908  sets {a 1 , a 2 , . . . , a n } as a set of actions that can be taken in the state s. The EXPLORATION_POLICY routine  908  also sets, for i=1, . . . , n, s′ i =(s, a i ) as a postdecision state when a i  is taken in s, v i  as a value of s′ i , and c i  as the number of visits to s′ i . The value mentioned here is the same as that described with reference to  FIG. 7 . The number of visits to s′ i  is denoted by c i . The number of visits c i  is recorded in order to select a balanced action sequence by avoiding a postdecision state with a large number of visits as much as possible.  FIG. 12  shows an example of correspondence between postdecision states, values, and counters. 
         [0091]    In step  1104 , the EXPLORATION_POLICY routine  908  computes i that minimizes a function f(v i , c i ). 
         [0092]    For example, the function f is an expression such as f(v, c)≡v+α(β/c) 0.6 , though the present invention is not limited to such. That is, the function f has a requirement of monotonically increasing with v and monotonically decreasing with c. α and β are positive constants, and parameters that can be arbitrarily set. 
         [0093]    The EXPLORATION_POLICY routine  908  sets the computed i as i* in step  1104 . The EXPLORATION_POLICY routine  908  increments c i * as c i *=c i +1 in step  1106 , and outputs s i * in step  1108 . 
         [0094]    The output of s i * can be understood more easily with reference to  FIG. 15 . Though postdecision states  1504   a,    1504   b,  and  1504   c  can be reached from the predecision state  1502  by possible different actions, the postdecision state  1504   c  is selected according to the computation in step  1104 . 
         [0095]    Returning to step  1006  in  FIG. 10 , after the EXPLORATION_POLICY routine  908  is completed and s′ is output in step  1006 , the main routine  902  pushes s′ onto the stack in step  1008 . 
         [0096]    Next, in step  1010 , the main routine  902  calls the SAMPLE_POLICY routine  906  by SAMPLE_POLICY(s) using s′ as an argument. 
         [0097]    The SAMPLE_POLICY routine  906  performs a process of selecting one transitionable state based on the combination of a Monte Carlo method and a Markov decision process, in the same manner as the SAMPLE_POLICY routine  206 . Since this process is the same as that shown in the flowchart in  FIG. 4 , its description is omitted here. This state selection corresponds to selecting a state  1506   b  in the predecision state  1506  from the state (S1)  1504   c  in the postdecision state  1504  in  FIG. 15 . 
         [0098]    After the SAMPLE_POLICY routine  906  selects s from s′ in step  1010 , the main routine  902  pushes s onto the stack in step  1012 . 
         [0099]    Next, in step  1014 , the main routine  902  determines whether or not to stop forward sampling. A criterion for stopping forward sampling is, for example, whether or not states are generated for a predetermined number of stages. Alternatively, the criterion for stopping forward sampling can be whether or not a predetermined time elapses from the start of the process. 
         [0100]    In the case where the main routine  902  determines that the criterion for stopping forward sampling is not met, the main routine  902  returns to step  1006  to call the EXPLORATION_POLICY routine  908 . 
         [0101]    On the other hand, in the case where the main routine  902  determines that the criterion for stopping forward sampling is met in step  1014 , the main routine  902  goes to step  1016 , and pops the state s from the stack. 
         [0102]    Next, the main routine  902  calls the UPDATE_VALUE_MIN routine  912  by UPDATE_VALUE_MIN(s) using the popped state s. The following describes a process of the UPDATE_VALUE_MIN routine  912 , with reference to a flowchart in  FIG. 13 . 
         [0103]    In  FIG. 13 , step  1302  is a definition step. In step  1302 , the UPDATE_VALUE_MIN routine  912  sets {s′ 1 , s′ 2 , . . . , s′ n } as a set of postdecision states directly reachable from s. The UPDATE_VALUE_MIN routine  912  also sets, for i=1, . . . , n, v i  as a value of s′ i .  FIG. 14  shows correspondence between postdecision states and values. 
         [0104]    In next step  1304 , the UPDATE_VALUE_MIN routine  912  computes, for i=1, . . . , n, a minimum value of v i  as v, according to v=min i  v i . In step  1306 , the UPDATE_VALUE_MIN routine  912  stores the computed v as a value of s. In the example in  FIG. 15 , supposing that the popped state s is a predecision state (S4)  1514   c,  actions  1516   a,    1516   b,  and  1516   c  are actions that can be taken in the state  1514   c.  When the minimum value among the values associated with the actions  1516   a,    1516   b,  and  1516   c  is the value associated with the action  1516   c,  this value is stored in the state  1514   c.    
         [0105]    Returning to the flowchart in  FIG. 10 , the main routine  902  determines whether or not the stack is empty in step  1020 . In the case where the stack is empty, the main routine  902  determines whether or not a stopping condition is met in step  1026 . The stopping condition mentioned here is any of whether or not a predetermined time elapses from the start of the process shown in the flowchart in  FIG. 10 , whether or not a loop of steps  1002  to  1014  is performed a predetermined number of times, or whether or not a value at the starting point designated by S1 in  FIG. 15  eventually has only a change of a threshold or below from a value computed in the immediately preceding loop of steps  1002  to  1014 . 
         [0106]    In the case where the main routine  902  determines that the stopping condition is met, the process ends. Otherwise, the main routine  902  returns to step  1002 , to resume the process from the first step. At this time, the values set in the states in the previous loop are maintained, and put to use in the next computation. 
         [0107]    In the case where the main routine  902  determines that the stack is not empty in step  1020 , the main routine  902  pops the state s′ from the stack in step  1022 . The main routine  902  then calls the UPDATE_VALUE routine  910  by UPDATE_VALUE(s′) in step  1024 , to update the value of s′. The process of the UPDATE_VALUE routine  910  is substantially the same as the process of the UPDATE_VALUE routine  208 , which is shown in detail in the flowchart in  FIG. 6 . In the example in  FIG. 15 , a value of a postdecision state (S3)  1512   b  is computed from predecision states  1514   a,    1514   b , and  1514   c.    
         [0108]    After step  1024 , the main routine  902  returns to step  1016 . As a result, an action sequence of actions  1504   c,    1508   a,    1512   b,  and  1516   c  is obtained. The main routine  902  calls the output routine  914  to output, for each predecision state, an action a associated with a postdecision state (s, a) having a minimum value among postdecision states directly transitionable from the predecision state. The output result is preferably displayed on the display  114  or written to a file. 
         [0109]    Though the above embodiment of the present invention is described using an example of applying to a process of selecting a stock in which the user is to invest in each term with predetermined money in possession, the present invention is not limited to this, and is applicable to any decision making process that involves probabilistic risk computation performed sequentially in time series. 
         [0110]    The present invention is not limited to a specific hardware and software platform of a computer, and can be implemented with any platform. 
         [0111]    The above and other features of the present invention will become more distinct by a detailed description of embodiments shown in combination with attached drawings. Identical reference numbers represent the same or similar parts in the attached drawings of the invention. 
         [0112]    As will be appreciated by one skilled in the art, aspects of the present invention can be embodied as a system, method or computer program product. Accordingly, aspects of the present invention can take the form of an entirely hardware embodiment, an entirely software embodiment (including firmware, resident software, micro-code, etc.) or an embodiment combining software and hardware aspects that can all generally be referred to herein as a “circuit,” “module” or “system.” Furthermore, aspects of the present invention can take the form of a computer program product embodied in one or more computer readable medium(s) having computer readable program code embodied thereon. 
         [0113]    Any combination of one or more computer readable medium(s) can be utilized. A computer readable storage medium can be, for example, but not limited to, an electronic, magnetic, optical, electromagnetic, infrared, or semiconductor system, apparatus, or device, or any suitable combination of the foregoing. More specific examples (a non-exhaustive list) of the computer readable storage medium can include the following: an electrical connection having one or more wires, a portable computer diskette, a hard disk, a random access memory (RAM), a read-only memory (ROM), an erasable programmable read-only memory (EPROM or Flash memory), an optical fiber, a portable compact disc read-only memory (CD-ROM), an optical storage device, a magnetic storage device, or any suitable combination of the foregoing. In the context of this document, a computer readable storage medium can be any tangible medium that can contain, or store a program for use by or in connection with an instruction execution system, apparatus, or device. 
         [0114]    Computer program code for carrying out operations for aspects of the present invention can be written in any combination of one or more programming languages, including an object oriented programming language such as Java, Smalltalk, C++ or the like and conventional procedural programming languages, such as the “C” programming language or similar programming languages. The program code can execute entirely on the user&#39;s computer, partly on the user&#39;s computer, as a stand-alone software package, partly on the user&#39;s computer. 
         [0115]    Aspects of the present invention are described below with reference to flowchart illustrations and/or block diagrams of methods, apparatus (systems) and computer program products according to embodiments of the invention. It will be understood that each block of the flowchart illustrations and/or block diagrams, and combinations of blocks in the flowchart illustrations and/or block diagrams, can be implemented by computer program instructions. These computer program instructions can be provided to a processor of a general purpose computer, special purpose computer, or other programmable data processing apparatus to produce a machine, such that the instructions, which execute via the processor of the computer or other programmable data processing apparatus, create means for implementing the functions/acts specified in the flowchart and/or block diagram block or blocks. 
         [0116]    These computer program instructions can also be stored in a computer readable medium that can direct a computer, other programmable data processing apparatus, or other devices to function in a particular manner, such that the instructions stored in the computer readable medium produce an article of manufacture including instructions which implement the function/act specified in the flowchart and/or block diagram block or blocks. 
         [0117]    The computer program instructions can also be loaded onto a computer, other programmable data processing apparatus, or other devices to cause a series of operational steps to be performed on the computer, other programmable apparatus or other devices to produce a computer implemented process such that the instructions which execute on the computer or other programmable apparatus provide processes for implementing the functions/acts specified in the flowchart and/or block diagram block or blocks. 
         [0118]    The flowchart and block diagrams in the Figures illustrate the architecture, functionality, and operation of possible implementations of systems, methods and computer program products according to various embodiments of the present invention. In this regard, each block in the flowchart or block diagrams can represent a module, segment, or portion of code, which includes one or more executable instructions for implementing the specified logical function(s). It should also be noted that, in some alternative implementations, the functions noted in the block can occur out of the order noted in the figures. For example, two blocks shown in succession can, in fact, be executed substantially concurrently, or the blocks can sometimes be executed in the reverse order, depending upon the functionality involved. It will also be noted that each block of the block diagrams and/or flowchart illustration, and combinations of blocks in the block diagrams and/or flowchart illustration, can be implemented by special purpose hardware-based systems that perform the specified functions or acts, or combinations of special purpose hardware and computer instructions. 
         [0119]    The terminology used herein is for the purpose of describing particular embodiments only and is not intended to be limiting of the invention. As used herein, the singular forms “a”, “an” and “the” are intended to include the plural forms as well, unless the context clearly indicates otherwise. It will be further understood that the terms “includes” and/or “including,” when used in this specification, specify the presence of stated features, integers, steps, operations, elements, and/or components, but do not preclude the presence or addition of one or more other features, integers, steps, operations, elements, components, and/or groups thereof. 
         [0120]    The corresponding structures, materials, acts, and equivalents of all means or step plus function elements in the claims below are intended to include any structure, material, or act for performing the function in combination with other claimed elements as specifically claimed. The description of the present invention has been presented for purposes of illustration and description, but is not intended to be exhaustive or limited to the invention in the form disclosed. Many modifications and variations will be apparent to those of ordinary skill in the art without departing from the scope and spirit of the invention. The embodiment was chosen and described in order to best explain the principles of the invention and the practical application, and to enable others of ordinary skill in the art to understand the invention for various embodiments with various modifications as are suited to the particular use contemplated.