JP7628037B2 - Reinforcement learning device, reinforcement learning method, and program - Google Patents

Description

The present invention relates to a reinforcement learning device, a reinforcement learning method, and a program.

Conventionally, reinforcement learning has been used to achieve a given task. Reinforcement learning is a method of learning an agent's behavior so as to maximize the cumulative value of a series of actions of the agent in an environment in which a task is given. For example, reinforcement learning has been applied to games and motor control, and automatic vehicle driving control (see Patent Documents 1 and 2).

JP 2018-63602 A JP 2020-144483 A

In general reinforcement learning, the agent's actions are selected randomly or probabilistically, and trial and error is repeated. Since it takes a long time for the cumulative value to converge to near the maximum value, there is a need to make learning more efficient.

In particular, learning times are likely to be long in environments where an agent is not rewarded for its actions until it completes a task. The value of an agent's actions is calculated based on the reward given by the environment for that action, and the calculated value serves as a guideline for selecting the agent's subsequent actions. However, if no reward is given during the process of completing a task, the value of the actions during that time does not change, and there is no guideline for selecting an action, leading to increased trial and error.

The present invention aims to improve the learning efficiency of reinforcement learning.

One aspect of the present invention is a reinforcement learning device (10) that repeatedly performs an episode of selecting an agent's behavior until a task is accomplished in a given environment, and learns the agent's behavior so as to maximize the cumulative value of a series of actions in one episode. The reinforcement learning device (10) includes an action selection unit (111) that repeatedly selects an action of the agent, a calculation processing unit (112) that calculates the value (Q) of the selected action using a reward (R) granted to the selected action each time the action is selected, and a task control unit (113) that defines one or more subtasks from the task and defines a second reward (M) to be granted depending on the degree of achievement of the subtask. The calculation processing unit (112) obtains the second reward (M) defined for the selected action and a first reward (r) granted from the environment, and calculates the reward (R) by adding the second reward (M) to the first reward (r).

Another aspect of the present invention is a reinforcement learning method that repeatedly performs an episode of selecting an agent's behavior until a task is accomplished in a given environment, and learns the agent's behavior so as to maximize the cumulative value of a series of actions in one episode. The reinforcement learning method includes a step of repeatedly selecting an action of the agent, a step of calculating a value (Q) of the selected action using a reward (R) granted to the selected action each time the action is selected, and a step of defining one or more subtasks from the task and defining a second reward (M) to be granted according to the degree of achievement of the subtask. The step of calculating the value (Q) includes a step of acquiring the second reward (M) defined for the selected action and a first reward (r) granted from the environment, and a step of calculating the reward (R) by adding the second reward (M) to the first reward (r).

Another aspect of the present invention is a program for causing a computer to execute a reinforcement learning method in which an episode of selecting an agent's behavior is repeatedly performed until a task is accomplished in a given environment, and the agent's behavior is learned so that the cumulative value of a series of actions in one episode is maximized. The reinforcement learning method includes a step of repeatedly selecting an action for the agent, a step of calculating a value (Q) of the selected action using a reward (R) granted to the selected action each time the action is selected, and a step of defining one or more subtasks from the task and defining a second reward (M) to be granted according to the degree of achievement of the subtask. The step of calculating the value (Q) includes a step of acquiring the second reward (M) defined for the selected action and a first reward (r) granted from the environment, and a step of calculating the reward (R) by adding the second reward (M) to the first reward (r).

The present invention can improve the learning efficiency of reinforcement learning.

1 is a block diagram showing a configuration of a reinforcement learning device according to an embodiment of the present invention. 1 is a flowchart showing a reinforcement learning process executed in a reinforcement learning device. FIG. 2 is a diagram showing a game area as an example of an environment. FIG. 13 illustrates an example of a subtask. FIG. 13 is a diagram showing an example of a second remuneration table. FIG. 13 is a diagram showing another example of the second remuneration table. FIG. 13 is a diagram showing an example of a value table. FIG. 13 illustrates an example of a table of values calculated for each subtask.

Below, an embodiment of the reinforcement learning device, reinforcement learning method, and program of the present invention will be described with reference to the drawings. The following description is an example (representative example) of the present invention, and the present invention is not limited thereto.

FIG. 1 shows a configuration of a reinforcement learning device 10 according to an embodiment of the present invention.
The reinforcement learning device 10 includes a CPU (Central Processing Unit) 11 and a storage unit 12. The reinforcement learning device 10 may further include an operation unit 13, a display unit 14, and a communication unit 15.

The CPU 11 executes the reinforcement learning process described below by reading and executing a program from the storage unit 12. In the reinforcement learning process, the CPU 11 functions as a behavior selection unit 111, a calculation processing unit 112, and a task control unit 113.

The behavior selection unit 111 selects an agent's behavior in an environment in which a task is given. The calculation processing unit 112 calculates the value of the behavior selected by the behavior selection unit 111 using the reward given for that behavior. The task control unit 113 defines subtasks from the given task.

The storage unit 12 stores programs that can be read by the CPU 11, and tables used to execute the programs. The storage unit 12 can be, for example, a recording medium such as a hard disk.

The operation unit 13 is a keyboard, a mouse, or the like. The operation unit 13 accepts operations by the user and outputs the contents of the operations to the CPU 11.

The display unit 14 is a display or the like. The display unit 14 displays an operation screen, the processing results of the CPU 11, etc., in accordance with display instructions from the CPU 11.

The communication unit 15 is an interface that communicates with external computers via a network.

In the reinforcement learning device 10, the CPU 11 can determine a strategy for accomplishing a given task through reinforcement learning. In this embodiment, an example of Q-learning, which is one type of reinforcement learning, is described.

(General reinforcement learning method)
In Q-learning, an agent is placed in an environment where a task is given. An agent is a subject of action. The agent selects one action (a) from multiple actions (a) that can be taken in a certain state (s _t ) of the environment. The selected action (a) transitions the state (s _t ) of the environment to state (s _t+1 ).

Each action (a) of an agent is associated with a value (Q) that evaluates the action (a). The value (Q) is calculated by an action value function Q expressed by the following formula (10).

In formula (10), s _t represents the state (s) of the environment at time t. _{s t+1} represents the state ( _s ) one step after the transition due to the action (a) in the state (s t ). r _t+1 represents the reward (r) given by the environment in response to the action (a) in the state (s _t ). α represents the learning rate and satisfies 0<α≦1. γ represents the discount rate and satisfies 0<γ≦1. maxQ(s _t+1 , a) represents a function that outputs the maximum value among the values Q(s t _{+ 1} , a) of several actions (a) that can be taken in the state (s t+1 ).

The agent continues to take action (a) until the environment transitions from the initial state (s ₀ ) to the final state (s _e ). This series of actions (a) of the agent from the initial state (s ₀ ) to the final state (s _e ) is called an episode. By repeatedly performing episodes, the value (Q) of the action (a) in each state (s) is calculated and updated in sequence. The series of actions that have the greatest cumulative value after performing a certain number of episodes can be learned as the optimal action for a given environment.

In general Q-learning, episodes must be repeated and trial and error conducted until the cumulative value converges to near the maximum value. This can lead to long learning times. This is particularly true in environments where reward (r) is not granted until the task is accomplished. Value (Q) is weighted by reward (r) and serves as a guide for the agent's selection of subsequent actions (a). However, if the reward (r) granted until the task is accomplished is zero, the value (Q) of action (a) will not change until the task is accomplished, resulting in increased trial and error.

In contrast, the reinforcement learning device 10 of this embodiment defines a subtask that is part of a given task, and grants a reward according to the action (a) that accomplishes the subtask. In other words, the reinforcement learning device 10 uses not only the reward (r) given by the environment but also a reward according to the degree of accomplishment of the subtask to calculate the value (Q). The value (Q), which serves as a guideline for selecting the action (a) even until the task is accomplished, is weighted, thereby reducing trial and error, thereby improving the efficiency of learning. Hereinafter, the conventional reward (r) given by the environment is referred to as the first reward (r), and the reward added to this first reward (r) is referred to as the second reward (M).

(Reinforcement learning method of this embodiment)
2 shows a flow of the reinforcement learning process in the reinforcement learning device 10. This reinforcement learning process is executed by the CPU 11 reading a program from the storage unit 12.
A game will now be described as an example of a task given to the reinforcement learning process. Fig. 3 shows a 6x6 block game area 30 given as the game environment.

In FIG. 3, each block is identified by a block number (ij). i is a number between 0 and 5 that represents the row of the game area 30. j is a number between 0 and 5 that represents the column of the game area 30. For example, the block in the second row and first column is represented as block (10).

A brush 20 is placed in the game area 30. The brush 20 can move one block at a time from the current block (ij) up, down, left, or right, and clean the block (ij) after the movement. The color of the cleaned block (ij) changes from black to white.

The task of this game is to change the color of all blocks (ij) from black to white. The shorter the total distance traveled by the brush 20, the more efficiently the task can be accomplished. The first reward (r) awarded from the game area 30 when all blocks (ij) have turned white is 100 points. As long as there are black blocks (ij), the first reward (r) awarded for any action (a) is 0 points. Information on the first reward (r) is given together with the game area 30 and is stored in the memory unit 12.

In this task, the game area 30 is a given environment. In the initial state (s ₀ ) of the environment, the number of white blocks is 0 and the number of remaining black blocks is 36. The action (a) of moving the brush 20 causes a transition in the state (s) of the environment, i.e., the color state (s) of the block (ij). Since the game ends when the task is accomplished, the final state (s _e ) of the environment is a state in which all blocks are white, i.e., the number of white blocks is 36 and the number of remaining black blocks is 0.

The reinforcement learning device 10 repeatedly selects an action (a) of an agent that moves the brush 20 as a game player and calculates its value (Q). In this way, the reinforcement learning device 10 searches for an action (a) that maximizes the cumulative value of the value (Q) calculated for a series of actions (a) until the color of all blocks (ij) changes from black to white.

First, the task control unit 113 of the CPU 11 defines one or more subtasks from a given task (hereinafter referred to as the main task) (step S1). A subtask is part of the main task. In other words, part of the main task is achieved by achieving a subtask.

FIG. 4 shows an example of a subtask.
In this example, the task control unit 113 defines three subtasks from a main task of changing the color of a game area 30 of 6×6 blocks, and assigns IDs 01, 02, and 03 to the subtasks. The subtask with ID=01 is to change the color of an area 31 of 4×2 blocks. The subtask with ID=02 is to change the color of an area 32 of 2×4 blocks. The subtask with ID=03 is to change the color of an area 33 of 3×4 blocks.

A part of each subtask may overlap with a part of another subtask. In the example of FIG. 4, area 32 of subtask ID=02 partially overlaps with area 33 of subtask ID=03. Note that multiple subtasks without overlaps may be defined by dividing the main task into several parts.

According to the definition of the subtasks, the environment has a state (s) in the main task and a state (m) in each subtask. The state (s) has a plurality of elements that represent the state of the main task, and is expressed as s = { _x1 , _x2 , ..., _xn }. The state (m) has a plurality of elements that represent the state of the subtask, and is expressed as m = { _y1 , _y2 , ..., _yn }. Each element can be determined arbitrarily. For example, the element _xn of the state (s) of the main task includes the block number (ij) that has changed to white by the movement of the brush 20 in the game area 30, the remaining number of black blocks, etc. Furthermore, the element _yn of the state (m) of the subtask includes the block number (ij) that has changed to white in the area of each subtask, the remaining number of black blocks, etc.

For example, in the game area 30 shown in FIG. 4, the main task has block numbers 00 and 01 that have changed to white, and the number of remaining black blocks is 34 (s). The subtask with ID=01 has no block numbers that have changed to white in area 31, and the number of remaining black blocks is 8 (m). The subtask with ID=03 has no block numbers that have changed to white in area 33, and the number of remaining black blocks is 12 (m). The subtask with ID=02 has block numbers 00 and 01 that have changed to white in area 32, and the number of remaining black blocks is 6 (m).

Next, the task control unit 113 defines a second reward (M) to be given to the agent's action (a) according to the degree of achievement of the subtask (step S2). The task control unit 113 stores the defined second reward (M) in the memory unit 12.

The task control unit 113 can define the second reward (M) independently for each subtask. The second reward (M) for each subtask may be the same or differently defined.

Fig. 5 shows an example of a table T31 that holds a second reward (M) defined for a subtask with ID = 01. In Fig. 5, the items of state (s _t , m) and (s _t+1 , m) indicate only the remaining number of black blocks in the area 31 among the elements indicating the state.

In table T31, an action (a) of transitioning from a state (s _t , m) to a state (s _t+1 , m) and changing the color of a block is associated with a second reward (M) of 3 points. For example, an action (a) of transitioning from a state (s _t , m) in which the remaining number of black blocks in the area 31 is 8 to a state (s _t+1 , m) in which the remaining number of black blocks is 7 is associated with a second reward (M) of 3 points.

On the other hand, an action (a) that leaves no change to the number of remaining blocks is associated with a second reward (M) of 0 points. According to this definition, each time the number of remaining black blocks in area 31 is reduced by 1 due to action (a) of moving brush 20, 3 points of second reward (M) are awarded.

In this embodiment, the definition of the second reward (M) for the subtask with ID=02 is the same as that for the subtask with ID=01. Therefore, the configuration of table T32 for the second reward (M) for the subtask with ID=02 is the same as that of table T31.

Fig. 6 shows an example of a table T33 that holds a second reward (M) defined for a subtask with ID = 03. In Fig. 6, the items of state (s _t , m) and (s _t+1 , m) indicate only the remaining number of black blocks in the area 33 among the elements indicating the state of the subtask.
In table T33, a second reward (M) of 36 points is associated with an action (a) that transitions the remaining number of black blocks in area 33 from a state (s _t , m) where the number is 1 to a state (s _t+1 , m) where the number is 0. A second reward (M) of 0 points is associated with other actions (a).

According to this definition, the second reward (M) awarded for the action (a) of changing part of area 33 to white is 0 points. The second reward (M) of 36 points is awarded for the action (a) of changing the last black block to white. In other words, the second reward (M) is not awarded each time the color of each block changes, but rather when all the blocks change color, the second reward (M) is awarded all at once.

Note that Figures 5 and 6 show an example of the definition of the second reward (M), and the method of defining the second reward (M) is not limited to this. Other definition methods can be adopted depending on the content of the task.

After the subtask and the second reward (M) are defined, the action selection unit 111 initializes the game and starts the episode (step S3). The initialization resets the environment to the initial state (s ₀ ). That is, the color of all blocks is changed from white to black, and the number of remaining black blocks is reset to 36.

The action selection unit 111 selects one action (a) from among the actions (a) that the agent can take in the current state (s _t , m) (step S4). The selected action (a) changes the game area 30 from state (s _t , m) to state (s _t+1 , m).

3, in the initial state (s ₀ ), the action (a) of placing the brush 20 in the block (00) is selected. As the color of the block (00) changes to white, the environment changes from a state (s ₀ , m) in which the number of remaining black blocks is 36 to a state (s ₁ , m) in which the number of remaining black blocks is 35.

In this embodiment, the selection of the action (a) is performed probabilistically by the ε-greedy method. Specifically, the action selection unit 111 randomly selects one of the actions (a) that can be taken in the state (s _t , m) with a certain probability ε. Furthermore, the action selection unit 111 selects, with a probability (1-ε), the action (a) that has the largest value (Q) of the action in the next state (s _t+1 , m) from among the actions (a) that can be taken in the state (s _t , m). In other words, the action (a) that obtains maxQ(s _t+1 , m, a) is selected.

If an action (a) that gives maxQ(s _t+1 , m, a) is always selected, learning may stagnate. This is because eliminating an action (a) with low value (Q) may result in failure to select a subsequent action (a) with higher value (Q). The ε-greedy method deliberately selects random actions (a) including actions (a) with low value (Q) with a certain probability. This expands the possibilities for selecting actions, making learning more efficient.
The method for selecting the action (a) is not limited to the above-mentioned ε-greedy method, but other methods such as the softmax method can be adopted depending on the purpose.

When the action (a) is selected, the calculation processing unit 112 calculates the value (Q) of the selected action (a) in the state (s _t , m) (step S5).
The following formula (1) shows an action value function Q used to calculate value (Q) in this embodiment. R in formula (1) represents a reward given to the action (a) selected in state (s _t , m). The following formula (2) shows a reward function used to calculate reward (R).

In formula (2), r _t+1 represents the first reward (r) associated with the action (a) in the state (s _t ). M(s _t+1 , m) represents the second reward (M) associated with the action (a) in the state (s _t ). τ represents a coefficient that satisfies 0≦τ≦1. The definitions of γ, α, and max are the same as those in formula (10).

First, the calculation processing unit 112 obtains the first reward (r) and the second reward (M) to be used in calculating the value (Q). The calculation processing unit 112 calculates the reward (R) by adding the second reward (M) to the obtained first reward (r). When second rewards (M) are granted from multiple subtasks, the calculation processing unit 112 adds them together and uses them to calculate the reward (R).

For example, the action (a) of moving the brush 20 from block (00) to block (01) results in a first reward (r) of 0 points given by the environment. On the other hand, this action (a) changes the remaining number of black blocks in area 32 from 7 to 6, and a second reward (M) of 3 points is obtained from table T31. The second reward (M) obtained from the subtasks in areas 32 and 33, where the color of the blocks does not change, is 0 points. Therefore, the reward (R) is calculated as 3 points.

Next, the calculation processing unit 112 uses the calculated reward (R) to calculate the value (Q) as shown in formula (1). The calculation processing unit 112 stores the calculated value (Q) in the memory unit 12.

FIG. 7 shows an example of a table Tq that holds a value (Q) in the storage unit 12.
In table Tq, a calculated value (Q) is associated with each action (a). Also, each action (a) is associated with the block number (ij) that has turned white and the remaining number n of black blocks in the game area 30 as the state (s _t+1 ) after the transition due to that action (a). These are written in each time an action (a) is selected and the value (Q) is calculated.

If the environment has not reached the final state (s _e ) by the selected action (a) (step S6: NO), the action selection unit 111 sets the state (s _t+1 , m) to which the environment transitioned by the action (a) as the current state (s _t , m) (step S7). Then, the processes of steps S4 and S5 are repeated. That is, the selection of the action (a) and the calculation of the value (Q) of the action are repeated until the final state (s _e ). As a result, the calculated values (Q) are stored in the table Tq in sequence.

When the environment reaches the final state (s _e ) by the selected action (a) (step S6: YES), one episode ends. When a certain number of episodes have been performed (step S8: YES), the reinforcement learning process ends. The certain number can be set arbitrarily.

On the other hand, if the certain number of episodes has not been performed (step S8: NO), the process returns to step S3 and a new episode is started. In other words, the process of steps S3 to S7 is repeated until the certain number of episodes has been performed, and the value (Q) is updated based on the series of actions during the performed episodes.

In this way, the second reward (M) that is granted according to the degree of completion of the subtask increases the reward (R) and the calculated value (Q) also increases. While the value (Q) does not change due to the first reward (r), the value (Q) changes due to the second reward (M), and the action (a) can be evaluated. This reduces trial and error and makes it possible to efficiently learn the action (a) that can complete the task.

When calculating the reward (R), the calculation processing unit 112 can adjust the rate (τ) at which the second reward (M) is added by changing the value of the coefficient τ. The larger the rate (τ), the greater the rate of the second reward (M) added to the first reward (r). The calculation processing unit 112 can increase the rate (τ) when prioritizing the efficiency of learning using the second reward (M), and can decrease the rate (τ) when prioritizing learning by trial and error.

It is preferable that the calculation processing unit 112 reduces the ratio (τ) as the number of times an episode is performed increases. The granting of the second reward (M) induces the agent's action (a) to accomplish the subtask, but the selection of new actions (a) decreases, and the agent's actions (a) tend to be biased toward actions (a) to which the second reward (M) is granted. Therefore, while the number of episodes is small, the learning can be made more efficient by increasing the ratio (τ) of the second reward (M). After a certain number of episodes have been performed, the ratio (τ) of the second reward (M) can be reduced and the agent can act randomly, making it possible to learn actions (a) with higher value (Q), and improving the efficiency of learning.

The calculation processing unit 112 can eventually reduce the ratio (τ) to 0. This allows the ratio to converge to a result similar to that of normal Q-learning. The calculation processing unit 112 may monotonically reduce the ratio (τ), or may temporarily increase it during the reduction process.

As described above, according to this embodiment, episodes are repeatedly performed to learn the agent's behavior (a) so that the cumulative value of the series of actions of the agent in one episode is maximized. In such reinforcement learning, the behavior selection unit 111 repeatedly selects the agent's behavior (a). Each time behavior (a) is selected, the calculation processing unit 112 calculates the value (Q) of behavior (a) using the reward (R) granted to the selected behavior (a).

In normal Q-learning, the reward (R) used to calculate value (Q) is only the first reward (r) as shown in equation (10). The first reward (r) is a constant that is predefined in the environment. In an environment where a high first reward (r) is awarded only when the color of all blocks has changed, the first reward (r), which is an indicator of action (a), cannot be obtained until that point. Since trial and error must be repeated until the color of all blocks has changed, the number of episodes required to maximize value (Q) increases, and learning takes time.

In contrast, the task control unit 113 in this embodiment defines subtasks from the main task and a second reward (M) that is granted depending on the degree of achievement of the subtask. The calculation processing unit 112 obtains the reward (R) by adding the second reward (M) to the first reward (r). The reward (R) weighted by the addition of such a second reward (M) increases the value (Q) of a series of actions that achieve the subtask. Therefore, it is possible to guide the agent to an action (a) that ultimately achieves the main task while achieving the subtask.

Inducing action (a) reduces trial and error. It also accelerates the maximization of value (Q). This shortens the learning time, thereby improving the learning efficiency of reinforcement learning.

The reinforcement learning device 10 can be used to determine various strategies, and its technical field is not particularly limited. For example, the reinforcement learning device 10 can be used for automatic driving control that determines a vehicle's driving route while avoiding hazards, motor drive control, game character control, etc.

Although preferred embodiments of the present invention have been described above, the present invention is not limited to these embodiments. Various modifications are possible within the scope of the present invention, and some modifications are listed below. Each modification may be combined.

(Variation 1)
The task control unit 113 can select whether to enable or disable each subtask. The task control unit 113 can switch between enabling and disabling the subtask for each episode, and can also switch between enabling and disabling the subtask within one episode depending on the environmental state (s).

For example, the task control unit 113 can select to disable the subtask with ID 02 and enable the subtasks with IDs 01 and 03 until half of the game area 30 has changed color in one episode. In this case, in the first half of the game, action (a) of changing the color of areas 31 and 33 is more likely to be selected than the block in area 32. This is because action (a) of changing the color of areas 32 does not result in the second reward (M), and action (a) of changing the color of areas 31 and 33, which results in the second reward (M), has a higher value (Q). Therefore, action (a) can be scheduled to change the color of areas 31 and 33 first, and then change the color of area 32.

When enabling or disabling a subtask is selected, the calculation processing unit 112 may calculate a reward (R) by adding up all of the second rewards (M) of each enabled subtask, and use the reward (R) to calculate the value (Q).

Alternatively, the calculation processing unit 112 may first calculate the value (Q) for each subtask, and then calculate the average value of the values (Q) of each activated subtask as the value (Q) of the action (a). Specifically, the calculation processing unit 112 calculates the value (Q) when only the subtask with ID=01 is activated, the value (Q) when only the subtask with ID=02 is activated, and the value (Q) when only the subtask with ID=03 is activated. In other words, the three values (Q) are calculated using only the second reward (M) granted from each subtask.

FIG. 8 shows examples of tables Tq1 to Tq3 of values (Q) calculated for each subtask.
Table Tq1 holds a value (Q) calculated using only the second reward (M) of the subtask with ID=01. Similarly, table Tq2 holds a value (Q) calculated using only the second reward (M) of the subtask with ID=02. Table Tq3 holds a value (Q) calculated using only the second reward (M) of the subtask with ID=03.

The calculation processing unit 112 calculates the average value of the values (Q) of the activated subtasks among the three values (Q). For example, if subtasks with IDs 01 and 02 are activated and subtask with ID 03 is deactivated, the calculation processing unit 112 calculates the average value of the values (Q) stored in tables Tq1 and Tq2. This average value is associated with the selected action (a) and stored in table Tq.

(Variation 2)
The behavior selection unit 111 may select the activation or deactivation of the subtask as one of the agent's behaviors (a), thereby making it possible to learn a schedule of the behavior (a) for accomplishing the subtask.

The task control unit 113 can define a second reward (M) for the action (a) of selecting whether to enable or disable each subtask. The second reward (M) makes it possible to learn the schedule of the action (a) more efficiently.

(Variation 3)
The task control unit 113 can define the second reward (M) based on information about the environment given in advance.
For example, if the environmental state (s) to be avoided or the state (s) to be passed through is known in advance, the calculation processing unit 112 can define the second reward (M) based on that information.

An example will be described in which traps are placed in some blocks (ij) of the game area 30. If the brush 20 reaches a trap, the game ends and the task fails. When the position information of this trap is given in advance, the task control unit 113 can define a second reward (M) for the action (a) of moving the brush 20 to the block (ij) in which this trap is placed that is lower than other actions (a), such as -100 points.

When such a low-value second reward (M) is defined, the reward (R) calculated by formula (2) when the action (a) that leads to the state (s) is selected becomes smaller, and as a result, the value (Q) also becomes smaller. This makes it possible to guide the agent's action (a) so as to avoid traps.

Depending on the control content using reinforcement learning, not only is an action (a) that can accomplish a task efficiently, but also an action (a) with low risk is required. For example, even if an action (a) accomplishes a task via the shortest route, it is better to avoid an action (a) that approaches a high-risk point. In this case, the risk of the learned action can be reduced by defining the second reward (M) as described above.

(Variation 4)
The second reward (M) in the above embodiment is a constant defined together with the subtask. However, the second reward (M) may be a variable that is updated according to an expected value of the reward (R) to be granted by the future action (a).

The following formula (3) shows an example of a reward function M(s,m) used to calculate the updated second reward (M). In formula (3), R _e represents the expected value of the reward (R) granted when a subtask is accomplished. The expected value (R _e ) is calculated by formula (4). The calculation processing unit 112 can calculate the updated second reward (M) and update tables T31 to T33 every time one or more actions (a) are selected. The updated second reward (M) is used to calculate the reward (R).

式（３）において、λは０＜λ≦１を満たす係数である。式（４）において、Ｅ[]は、[]内の期待値を出力する関数を示す。

In formula (3), λ is a coefficient that satisfies 0<λ≦1. In formula (4), E[ ] denotes a function that outputs the expected value in [ ].

For example, the current environment is in a state (s) where the color of all blocks in area 31 has changed, but the colors of areas 32 and 33 have not changed. Whatever action (a) is selected in this state (s), the first reward (r) obtained is 0 points. In addition, since the subtask with ID 01 has already been achieved, the expected value (R _e ) of the reward (R) obtained in the future by achieving the subtask is 0 points.

On the other hand, by accomplishing the subtasks with IDs 02 and 03, the cumulative value of the second reward (M) defined for each subtask is expected as the reward (R). According to formulas (3) and (4), the second reward (M) given to the action (a) of accomplishing the subtasks with IDs 02 and 03 is higher than that of the subtask with ID 01. As a result, the value (Q) of the action (a) increases, and the agent's action (a) can be induced to accomplish the subtasks with IDs 02 and 03.

When calculating the updated second reward (M), the calculation processing unit 112 can adjust the ratio (λ) of the expected value (R _e ) of the reward (R) in the updated second reward (M) by changing the value of the coefficient λ. The larger the ratio (λ), the more accelerated the shift from the original second reward (M) to the expected value (R _e ) of the reward (R). Therefore, by increasing the ratio (λ), the calculation processing unit 112 can more quickly reflect the results of the actual action (a) in the subsequent action (a).

(Variation 5)
The second reward (M) may be calculated by a reward function M _γ (s, m) shown in the following formula (5) instead of formula (3). According to formula (5), the updated second reward (M) is an expectation value (E) of the reward (R) obtained until each action (a) selected in one episode is reached, and is calculated by adding up each reward (R). Here, the reward (R) given to each action (a) is discounted by a coefficient γ _E.

式（５）において、E[]は、[]内の期待値を出力する関数を表す。

In equation (5), E[ ] represents a function that outputs the expected value in [ ].

γ _E represents the discount rate of the reward (R) given to each action (a) and satisfies 0<γ _E ≦1. Since the discount rate γ _E is raised to the power of (e-t), the closer to the initial state (s ₀ ) from the final state (s _e ), the smaller the discount rate of the reward (R). According to this reward function M _γ (s, m), it is easier to induce past actions closer to the final state (s _e ) than to the initial state (s ₀ ). Therefore, it is suitable for an environment in which the first reward (r) is given to the last action (a) that achieves the main task. In addition, when γ _E ^(e-t) is smaller than 1, an action (a) with a high expected value (E) is more likely to be selected among a small number of actions (a). Therefore, γ _E can be set in consideration of the time average until the cumulative reward (R _e ) is obtained.

For example, when transitioning from state (s _t , m) to state (s _t+3 , m), the expected value (E) of each reward (R) until each action (a) is reached is calculated as follows.
M _γ (s, m) = γ _E ³ R (s _t , m) + γ _E ² R (s _t+1 , m)
+γ _E R (s _t+2 , m) + R (s _t+3 , m)

(Variation 6)
The task control unit 113 may set a difference in the second reward (M) between each subtask. This makes it easier to control the order in which the subtasks are completed. For example, the task control unit 113 can define the second reward (M) for each subtask so that the second reward (M) for the subtask with ID 01 is greater than the subtasks with IDs 02 and 03. In this case, the action (a) is induced so that the subtask with ID 01 is completed before the subtasks with IDs 02 and 03.

(Variation 7)
If there is a part of a subtask that should be completed first, the task control unit 113 can define this part so that it overlaps with a part of another subtask.
For example, when the color of a block where the areas of multiple subtasks overlap changes, such as blocks (12) and (13) in Fig. 4, the second reward (Q) of each subtask is used to calculate the value (Q). As a result, the value (Q) of the action (a) of moving the brush 20 to a block where the areas overlap is likely to be higher than the action (a) of moving to a block where there is no overlap. Therefore, it is possible to induce the action (a) so that the color of the block where the areas overlap changes first.

In the above embodiment, the storage unit 12 stores the tables T31 to T33, Tq, and Tq1 to Tq3, but these may be stored in an external device such as a server. By communicating with the external device via the communication unit 15, the tables T31 to T33, Tq, and Tq1 to Tq3 can be downloaded or uploaded.

Although an example of Q-learning has been described, the present invention can be applied to any reinforcement learning that uses rewards to calculate the value of an agent's actions. For example, the present invention can also be applied to SARSA, Markov decision processes (MDPs), and Deep Q-Networks (DQNs).

A recording medium may be provided on which a program for causing a computer to execute the reinforcement learning method of the present invention is recorded. The recording medium is not particularly limited as long as it is a recording medium that can be read by a computer such as a CPU, and semiconductor memory, magnetic disks, optical disks, etc. can be used.

10: Reinforcement learning device, 11: CPU, 111: Action selection unit, 112: Calculation processing unit, 113: Task control unit, 12: Storage unit

Claims (8)

A reinforcement learning device (10) that repeatedly performs an episode of selecting an agent's behavior until the agent accomplishes a task in a given environment, and learns the agent's behavior so as to maximize a cumulative value of a series of actions in one episode,
an action selection unit (111) for repeatedly selecting an action of the agent;
a calculation processing unit (112) that calculates a value (Q) of the selected action using a reward (R) given to the selected action each time the action is selected;
A task control unit (113) that defines one or more subtasks from the task and defines a second reward (M) to be granted according to the degree of achievement of the subtask;
The computation processing unit (112) obtains the second reward (M) defined for the selected action and a first reward (r) provided from the environment, and calculates the reward (R) by adding the second reward (M) to the first reward (r). The reinforcement learning device (10) according to claim 1 , wherein the calculation processing unit (112) adjusts a rate (τ) of adding the second reward (M). The reinforcement learning device (10) according to claim 2, wherein the calculation processing unit (112) decreases a rate (τ) of adding the second reward (M) as the number of times the episode is performed increases. The reinforcement learning device (10) according to any one of claims 1 to 3, wherein the task control unit (113) defines the second reward (M) independently for each of the subtasks. The reinforcement learning device (10) according to any one of claims 1 to 4, wherein the task control unit (113) selects whether to enable or disable the subtask. The reinforcement learning device (10) according to any one of claims 1 to 4, wherein the action selection unit (111) selects enabling or disabling the subtask as one of the actions of the agent. A reinforcement learning method for repeatedly selecting an action for an agent in a given environment until the agent accomplishes a task, the method comprising:
Iteratively selecting an action for the agent;
Each time the action is selected, a value (Q) of the selected action is calculated using a reward (R) given to the selected action;
defining one or more subtasks from the task and defining a second reward (M) to be given according to the degree of achievement of the subtask;
The step of calculating the value (Q) comprises:
Obtaining the second reward (M) defined for the selected behavior and a first reward (r) provided by the environment;
and calculating the reward (R) by adding the second reward (M) to the first reward (r). A program for causing a computer to execute a reinforcement learning method for repeatedly executing an episode of selecting an action of an agent until the agent accomplishes a task in a given environment, and learning the action of the agent so as to maximize a cumulative value of a series of actions in one episode, comprising:
The reinforcement learning method includes:
Iteratively selecting an action for the agent;
Each time the action is selected, a value (Q) of the selected action is calculated using a reward (R) given to the selected action;
defining one or more subtasks from the task and defining a second reward (M) to be given according to the degree of achievement of the subtask;
The step of calculating the value (Q) comprises:
Obtaining the second reward (M) defined for the selected behavior and a first reward (r) provided by the environment;
and calculating the reward (R) by adding the second reward (M) to the first reward (r).

Images