A novel model-based reinforcement learning algorithm for solving the problem of unbalanced reward

Abstract

Reward signal reinforcement learning algorithms can be used to solve sequential learning problems. However, in practice, they still suffer from the problem of reward imbalance, which limits their use in many contexts. To solve this unbalanced reward problem, in this paper, we propose a novel model-based reinforcement learning algorithm called the expected n-step value iteration (EnVI). Unlike traditional model-based reinforcement learning algorithms, the proposed method uses a new return function that changes the discount of future rewards while reducing the influence of the current reward. We evaluated the performance of the proposed algorithm on a Treasure-Hunting game and a Hill-Walking game. The results demonstrate that the proposed algorithm can reduce the negative impact of unbalanced rewards and greatly improve the performance of traditional reinforcement learning algorithms.

Keywords

Reinforcement learning Model-based learning Unbalanced reward Multi-step methods

1 Introduction

Reinforcement learning (RL) is a computational approach for understanding and automating goal-directed learning [1 –3]. Unlike supervised learning, RL agents never receive correct or incorrect labeled data to facilitate learning [4, 5]; instead, agents learn by receiving positive and negative rewards for the behavior they choose. In recent years, RL combined with deep learning has achieved successful results on a wide range of problems in various fields [6, 7].

In prior works, the reward function modeled by the programmer was usually balanced. That is, the reward function at the intermediate state had no local extremum except for the terminal state. This can help to reduce the number of extreme points of the state value function and improve the veracity of the optimal policy. For example, in the environment of a cliff-walking task, such as the windy grid world task [5, 11], the reward function in an intermediate state is usually defined as a constant, such as 0.1, -0.1 or 0. In the terminal state, the reward function has a global extreme point, and the reward is usually defined as 1 or -1, which guarantees that the RL environment has a balanced reward.

However, in practice, the reward function can have various patterns, some of which are unbalanced. An unbalanced reward environment can reduce the performance of traditional reinforcement learning algorithms and even lead to safety risks [12]. For example, reward hacking is a risk that can cause unexpected behavior in practical applications [13 –15]. The problem of reward imbalance hampers the agent’s work. With the ongoing applications of RL, it is worth paying serious attention to the problem of unbalanced rewards, since unbalanced rewards can break traditional RL algorithms in surprising, counterintuitive ways [13 , 17]. The main reason is that in traditional RL algorithms, the return function emphasizes only the immediate reward as the main effect. In an unbalanced reward environment, the RL agent requires a significantly higher number of iterations to obtain the optimal policy.

To avoid the problem of unbalanced rewards, some methods have proposed transforming an unbalanced reward environment into a balanced reward environment [18 , 21], for example, by clipping all positive rewards at 1 and all negative rewards at -1 while leaving 0 rewards unchanged. Although this approach alleviates the negative impact of unbalanced rewards, the performances of the resulting RL methods are degraded because they ignore the magnitude information of different rewards during learning [4]. Therefore, it is particularly important to establish a simple and effective method to solve the unbalanced reward problem.

Thus, in this paper, we propose a novel model-based RL algorithm that combines multistep methods with dynamic programming to solve the unbalanced reward problem. This new algorithm is called the expected n-step value iteration (EnVI). In contrast to the traditional multistep methods, the proposed algorithm uses a new return function composed of n standard return functions. This new return function alters the discount of future rewards while reducing the influence of the current reward, which enables the proposed method to reduce the negative impact of unbalanced rewards and substantially improves RL performance.

The remainder of this paper is organized as follows: The problem definition is introduced in Section 3.1; then, the new return function and the new multistep method are presented in Sections 3.2 and 3.3. In Section 4, the performance of the proposed method is evaluated on the Treasure-Hunting game. Finally, some brief discussions and conclusions are provided in Sections 5 and 6, respectively.

2 Background

RL methods have been effectively applied to solve sequential decision problems, which are often formalized as Markov decision processes (MDPs). An MDP can be described as a tuple (S, A, P, γ, R), where:

•S is a finite state space,

•A is a finite action space,

•P : S × A × S → [0, 1] is a state transition matrix. P (s′|s, a) is a transition probability of an agent taking action a in state s and reaching state s′, and P_π : S × S → [0, 1] is a state transition submatrix under a fixed policy π; when π (s) = a, we define P_π (s′|s) = P (s′|s, a).

•γ ∈ [0, 1) is a discount factor specifying how future rewards are weighted with respect to the immediate reward.

• $R : S \times A \mapsto ℝ$ is a state-action reward function, where R (s, a) is the reward given when an agent takes action a in state s, and $r : S \mapsto ℝ$ is the state reward function. In this study, we set R (s, a) = ∑_s′P_π (s′|s, a) r (s′).

In traditional RL algorithms, the return function G_t is defined as the discounted sum of the rewards observed after time step t, $G_{t} = \sum_{j = 0}^{\infty} γ^{j} r_{t + j} = r_{t} + γ G_{t + 1} .$ (1)

The goal of the agent is to maximize the expected return by finding an optimal policy π^*, which is a mapping function from state s to action a. Under a given policy π, the state value function at state s is defined as follows: $V^{π} (s) = 𝔼_{π} [G_{t} | s_{t} = s],$ (2) where $𝔼_{π} [\cdot]$ is an expectation function. According to the Markov property that the future is independent of the past given the present state [19], the state value function can be computed recursively using dynamic programming:

$V^{π} (s) = 𝔼_{s_{t + 1} \in S} [r_{t} + γ V^{π} (s_{t + 1}) | s_{t} = s, π] .$ (3)

The optimal state value function is $V^{*} (s) = max_{π} V^{π} (s),$ (4) where the optimal policy is the best choice to enable an agent to obtain the maximum state value function in state s.

To estimate the optimal state value function, the value iteration (VI) algorithm, a classic learning method, was proposed in [1]. The update rule is given as $V (s_{t}) \leftarrow max_{a_{t} \in A} \sum_{s_{t + 1} \in S} P (s_{t + 1} | s_{t}, a_{t}) [r_{t} + γ V (s_{t + 1})] .$ (5) For any state s ∈ S, the state value function converges to V^* (s) through the update rule. At the same time, we can obtain the optimal policy π^*. We refer to the above method as a one-step value iteration because only a one-step reward is used immediately at each update.

3 Methodology

3.1 Problem Definition

In practice, the reward functions of some RL tasks are unbalanced. That is, except for the terminal state, the reward function at intermediate states has some local extreme points. In traditional one-step RL algorithms, such as VI, unbalanced rewards cause data inefficiency problems and degrades the learning performance. This result mainly occurs because in traditional RL algorithms, the return function emphasizes only the immediate reward as the main influence. Consequently, in an unbalanced reward environment, an RL agent requires a significantly higher number of iterations to obtain the optimal policy. Moreover, unbalanced rewards can even change the action tendency of the RL agent, moving it far away from the target state. Although the optimal policy obtained by traditional RL algorithms ensures that the agent has an optimal state value function, it does not ensure that the agent can achieve the goal. This type of behavior can undermine the designer’s intentions, therefore, it is particularly important to establish a simple and effective method to solve the unbalanced reward problem.

In this paper, we propose the novel model-based EnVI method. In contrast to traditional dynamic programming methods, the proposed method uses a new return function that effectively weakens the adverse effects of unbalanced rewards and improves RL performance.

3.2 New return function

First, we present a new return function, which is defined as follows: ${\hat{G}}_{t}^{(n)} = \frac{1}{n} \sum_{k = 1}^{k = n} G_{t + k - 1};$ (6) i.e., the new return function is the average of n standard return functions G_t, G_t+1, …, G_t+n-1. In the new algorithms, the goal of the agent is to maximize the expected value of the new return function, which is consistent with the goals of the traditional algorithms. When G_t, G_t+1, …, G_t+n-1 reaches its maximum value, ${\hat{G}}_{t}^{(n)}$ also reaches its maximum value. Through mathematical manipulation, (6) can be expressed as follows: $\begin{matrix} {\hat{G}}_{t}^{(n)} & = & \frac{1}{n} \sum_{k = 1}^{k = n} G_{t + k - 1} \\ = & \frac{1}{n} [[r_{t} + γ r_{t + 1} + γ^{2} r_{t + 2} + \dots] \\ + [r_{t + 1} + γ r_{t + 2} + \dots] \\ + \dots \\ + [r_{t + n - 1} + γ r_{t + n} + \dots]] \\ = & \frac{1}{n (1 - γ)} \sum_{k = 1}^{k = n} (1 - γ^{k}) r_{t + k - 1} \\ + \frac{1 - γ^{n}}{n (1 - γ)} \sum_{k > n} γ^{k - n} r_{t + k - 1} \\ = & {\hat{g}}_{1} + {\hat{g}}_{2} \end{matrix}$ (7) where ${\hat{g}}_{1} = \frac{1}{n (1 - γ)} \sum_{k = 1}^{k = n} (1 - γ^{k}) r_{t + k - 1}$ and ${\hat{g}}_{2} = \frac{1 - γ^{n}}{n (1 - γ)} \sum_{k > n} γ^{k - n} r_{t + k - 1}$ . According to (7), the new return function can be decomposed into two parts. The first part is ${\hat{g}}_{1}$ , which contains the first n future rewards. The reward at time step t + k - 1 is discounted by ${\hat{h}}_{t + k - 1} = \frac{1 - γ^{k}}{n (1 - γ)}$ , where k = 1, 2, …, n. As the parameter k increases, the value of ${\hat{h}}_{t + k - 1}$ gradually increases. In a standard return function G_t, the discount of the reward at time step t + k - 1 is h_t+k-1 = γ^k-1, which gradually decreases as the parameter k increases. This is the essential difference between our proposed new return function and the traditional return function. The proposed new return function changes the reward discount form so that the current reward is no longer the primary factor influencing the state action, which helps solve the unbalanced reward problem.

The relative weight is an important parameter that can serve as an indicator for estimating the relative contribution of the reward signal. For the first n steps, the relative weights of the discount factor of the reward at time step t + k - 1 are calculated by ${\begin{matrix} {\hat{ψ}}_{t + k - 1} = \frac{{\hat{h}}_{t + k - 1}}{\sum_{k = 1}^{k = N} {\hat{h}}_{t + k - 1}} = \frac{1 - γ^{k}}{\sum_{k = 1}^{k = N} (1 - γ^{k})} \\ ψ_{t + k - 1} = \frac{h_{t + k - 1}}{\sum_{k = 1}^{k = N} h_{t + k - 1}} = \frac{γ^{k - 1}}{\sum_{k = 1}^{k = N} γ^{k - 1}} \end{matrix}$ (8) Clearly, when k = 1, we have ${\hat{ψ}}_{t} < ψ_{t}$ , and when k = N, we have ${\hat{ψ}}_{t + N - 1} > ψ_{t + N - 1}$ . Hence, according to the monotonicity of the functions, there must exist a k_m ∈ [1, N] that satisfies ${\begin{matrix} {\hat{ψ}}_{t + k - 1} \leq ψ_{t + k - 1} if k \leq k_{m} \\ {\hat{ψ}}_{t + k - 1} \geq ψ_{t + k - 1} if k > k_{m} \end{matrix} .$ (9)

This is an important characteristic that can help us solve the unbalanced reward problem. Consider the following Markov Chain: $s_{t}, a_{t}, r_{t}, \dots, s_{t + k_{n} - 1}, a_{t + k_{n} - 1}, r_{t + k_{n} - 1}, \dots .$ (10)

In our study, we randomly determine a set of parameters, i.e., n = 5, γ = 0.8, r_i = -1, i ∈ {t, …, t + k_n - 2, t + k_n, …}. In particular, we assume that r_{t+k_n-1} = 0, which shows that the robot has an unbalanced reward case (the reward function has a local extremum in state s_{t+k_n}). According to Eq. (9), we calculate that the value of k_m is 2. For diverse values of k_n ∈ [1, 5], Table 1 shows the changes in relative weights ${\hat{ψ}}_{t + k - 1}$ and ψ_t+k-1. When k_n > k_m, we have ${\hat{ψ}}_{t} (k_{n}) > ψ_{t} (k_{n})$ , which can help to adapt the unbalanced reward or to move rapidly away from an unbalanced point. If k_n ≤ k_m, we have ${\hat{ψ}}_{t} (k_{n}) \leq ψ_{t} (k_{n})$ , which can help to weaken the impact of the unbalanced reward and prevent the state value function from having a local extremum.

Table 1

The changes in the relative weight $\hat{ψ}$ and ψ

k _n	1	2	3	4	5
${\hat{ψ}}_{t + k - 1}$	0.086	0.156	0.211	0.256	0.291
ψ _t+k-1	0.298	0.238	0.19	0.152	0.122

Moreover, the results of Table 2 also support this conclusion. Table 2 shows the changes in the return function ${\hat{g}}_{1}$ and g₁. When the agent approaches state s_{t+k_n}, the traditional return function g₁ has a higher value. Thus, an agent using a traditional RL algorithm will be more inclined to converge to the state s_{t+k_n}, and the value function at a state around s_{t+k_n} is likely to have a local extremum, which can alter the agent’s action tendency and drive it far away from the target state. In contrast, when using the new return function ${\hat{g}}_{1}$ , the changes are opposite to g₁. This alteration not only enables an unbalanced reward to be detected early but also helps to reduce the number of local extrema of the state value function at an intermediate state.

Table 2

The changes in the return function ${\hat{g}}_{1}$ and g₁

k _n	1	2	3	4	5
${\hat{g}}_{1}$	-2.1107	-1.9507	-1.8227	-1.7203	-1.6384
g ₁	-2.3616	-2.5616	-2.7216	-2.846	-2.952

Note that the second part of the new return function is ${\hat{g}}_{2}$ , which is composed of the rewards after the first n steps. The discount of these rewards gradually decreases, which ensures that the new return function still maintains the basic properties of traditional RL [1].

3.3 Expected N-step value iteration

Under a given policy π, for an agent in state s, the new state value function ${\hat{V}}^{π} (s)$ is modified as follows: ${\hat{V}}^{π} (s) = 𝔼_{π} [{\hat{G}}_{t}^{(N)} | s_{t} = s] .$ (11)

According to the Markov Property, the new return function ${\hat{G}}_{t}^{(n)}$ can be transformed into ${\hat{G}}_{t}^{(n)} = {\hat{r}}_{t}^{(n)} + γ {\hat{G}}_{t + 1}^{(n)},$ (12) where ${\hat{r}}_{t}^{(n)} = \frac{1}{n} \sum_{k = 1}^{k = n} r_{t + k - 1}$ . Hence, the new state value function ${\hat{V}}^{π} (s)$ in (10) can be computed recursively with dynamic programming as follows: ${\hat{V}}^{π} (s) = 𝔼_{π} [{\hat{r}}_{t}^{(n)} + γ {\hat{V}}^{π} (s_{t + 1}) | s_{t} = s, π] .$ (13) Similar to VI, the new optimal state value function can be estimated with dynamic programming using $\hat{V} (s) \leftarrow max_{π (s) \in A} \sum_{s^{'} \in S} ρ^{π} (s^{'}) r (s^{'}) + γ \sum_{s^{'} \in S} P (s^{'} | s, π (s)) \hat{V} (s^{'}),$ (14) where $ρ^{π} (s^{'}) = \frac{1}{n} \sum_{k = 1}^{k = n} p (s \to s^{'}, k, π)$ and p (s → s′, k, π) is the probability of transitioning from the starting state s to state s′ in the kth step under policy π. The detailed calculation of ρ^π (s′) is shown in Appendix A. In this paper, the algorithm using (14) is called the expected n-step value iteration. Compared with traditional RL algorithms, the new algorithm substitutes the reward ${\hat{r}}_{t}^{(n)}$ for the immediate reward r_t. Clearly, when n = 1, the proposed method is identical to the traditional VI algorithm. Algorithm 1 shows the pseudocode for the EnVI algorithm.

Initialize π arbitrarily

Given the model tuple (S, A, P, γ, R)

Initialize n

Repeat

For each state s ∈ S

Calculate P_π and {ρ^π (s′)}

L^π (s) = ∑_s′∈Sρ^π (s′) r (s′) $+ γ \sum_{s^{'} \in S} P (s^{'} | s, π (s)) \hat{V} (s^{'})$ $\hat{V} (s) \leftarrow max_{π (s) \in A} L^{π} (s)$ $π (s) \leftarrow \arg max_{π (s) \in A} L^{π} (s)$ Until ${{\hat{V}}^{π} (s)}$ is stable

4 Evaluation

In Section 3, we presented the proposed method EnVI. In this section, a series of experiments are conducted to evaluate the performance of EnVI. First, a simple Treasure-Hunting game, which has a sparse reward function, is used as the test platform. Then, a more complicated Hill-Walking game is used to verify the scalability of the algorithm. All the experiments were conducted using the hardware and software environment of a desktop computer with an Intel-i7 3.6 Ghz CPU, 16 GB of DDR3 RAM, Windows 7, Python 3.5.2 and Sublime Text 3.

4.1 Treasure Hunting Game

As shown in Fig. 1(a), the Treasure-Hunting game has 23 grid squares, each of which represents a robot state s. The goal of the game is to train the agent to find the treasure, which is located in state s²². In states s²¹ and s²³, there are two pirates, which can "eat" the agent. In this game, states {s²¹, s²², s²³} are terminal states; the game will end when the agent either encounters a pirate or finds the treasure. In each episode, the agent can start in any intermediate state sⁱ, i = {1, 2, …, 20}. The thick black line on the outer boundary represents a wall, which restricts the robot’s movement.

Fig. 1

Treasure Hunting Game. (a) shows the state distribution of the game.

For each intermediate state sⁱ, the robot action space is A = {right, up, left, down}. The agent moves one square in the corresponding direction, unless it encounters a wall in that direction. When the agent bumps into a wall, it stays in the same position. Each step results in a reward of -0.1, except when the agent encounters a pirate or finds the treasure. The agent obtains a reward of 1 when it finds the treasure; however, if the agent encounters a pirate, it is penalized 1.

The purpose of this study is to evaluate the performance of the RL algorithm under an unbalanced reward scenario. Hence, we specifically modified the reward function in Fig. 1(b) to ensure that the game has an unbalanced reward environment. As shown in Fig. 2, there are two versions of unbalanced reward environments. In the first version, the reward at state s³ is 0.5, while in the other version, the reward at state s⁸ is -0.5. The rewards remain the same for the other states. These two environments provide two typical unbalanced reward problems because the reward function at state s³ has a local maximum and that at state s⁸ has a local minimum.

Fig. 2

The reward function of the two unbalanced rewards environments. We modify the reward function in Fig. 1. In the first one, we assume the reward at state s³ is 0.5, and in the second one we assume the reward in state s⁸ is -0.5.

4.2 Treasure-hunting game results

In this study, we adopt the accuracy rate of the optimal policy as the performance evaluation index since it can evaluate whether the optimal policy is satisfactory. The accuracy rate is defined as $δ = \frac{n_{b}}{n_{a}},$ (15) where n_a is the total number of states, and n_b is the number of states associated with correct policy actions.

Tables 3 and 4 present the accuracy rate results in the two unbalanced reward environments. As γ and n increase, the accuracy rate of the optimal policy improves. This result illustrates that we can reduce the adverse effect of an unbalanced reward by increasing the values of the discount factor γ and n. However, during training, a large γ will cause the number of iterative loops to increase, resulting in longer learning times. With a small γ, EnVI can still obtain a better optimal policy than does the traditional VI algorithm.

Table 3

The results for the accuracy rate δ in an unbalanced reward environment, r (s³) =0.5

γ	0.1	0.2	0.3	0.4	0.5	0.6	0.7	0.8	0.9
n = 1	0.8	0.8	0.8	0.8	0.8	0.9	0.9	0.95	1
n = 2	0.8	0.8	0.8	0.8	0.8	0.9	0.9	0.95	1
n = 3	0.8	0.8	0.8	0.8	0.8	0.9	0.85	1	1
n = 4	0.8	0.8	0.8	0.8	0.8	0.85	0.95	1	1
n = 5	0.85	0.9	0.9	0.85	0.85	0.85	1	1	1
n = 8	0.95	0.95	0.95	1	1	1	1	1	1

Table 4

The results for the accuracy rate δ in an unbalanced reward environment, r (s⁸) = -0.5

γ	0.1	0.2	0.3	0.4	0.5	0.6	0.7	0.8	0.9
n = 1	0.65	0.75	0.85	0.85	0.95	0.95	0.95	1	1
n = 2	0.65	0.75	0.85	0.85	0.95	1	1	1	1
n = 3	0.65	0.75	0.95	0.95	1	1	1	1	1
n = 4	0.75	1	1	1	1	1	1	1	1
n = 5	1	1	1	1	1	1	1	1	1
n = 8	1	1	1	1	1	1	1	1	1

Figure 3 shows the smallest number of iterations that the agent needs to obtain the best accuracy rate. Clearly, as the value of n increases, the proposed method requires fewer iterative loops to obtain the best optimal policy.

Fig. 3

The results of iterative loop for an agent at least needed to obtain the best accuracy rate.

4.3 Hill-walking game

In Section 4.1, we designed a grid world simulation to evaluate the performance of our proposed method. In the game, the reward functions in most intermediate states are equal. To fully evaluate the performance of our proposed method, we designed a new simulation, the Hill-Walking game, in which the reward functions in each state are dissimilar.

In the Hill-Walking game, the agent gradually moves stepwise from an intermediate state to a terminal state. As shown in Fig. 6(a), the state space is discretized and can be expressed as S = {s_x,y|x = i, y = j}, where x and y are the coordinate values of the robot and i ∈ 1, 2, …, 8, j ∈ 1, 2, …, 7. In the game, the state s_8,7 = (8, 7) is the terminal state. For any state s_i,j, the reward function is r (s_i,j) = exp (-0.07 (s - s_8,7) ²). Thus, the agent obtains a greater reward as it approaches the terminal state. However, in this experiment, we specifically changed the reward function in states s_3,3, s_6,3, s_3,5 and s_6,5 to ensure that the game has a complex unbalanced reward environment by setting r (s_3,3) =0.4, r (s_6,3) =0.7, r (s_3,5) =0.5 and r (s_6,5) =0.8. As shown in Fig. 6(b), the reward function has several local maxima. The action space of this new game is the same as that in the Treasure-Hunting game. The robot arm can move to an adjacent state by manipulating the joystick.

Fig. 6

The Hill-Walking game: (a) the state distribution of the game. Here, s_8,7 is the terminal state. At each time step, the robot can move one grid space in any direction until it reaches a terminal state; (b) the distribution of the reward function. At states s_3,3,s_6,3,s_3,5 and s_6,5, the reward function has several local maxima.

4.4 Hill-walking game results

Table 5 shows the number of iterative loops that the robot spends completing the learning process across a range of γ and n values. As the discount factor γ increases, the robot requires a larger number of iterative loops to obtain the optimal value function. For a fixed γ, the results for various values of n are similar. Table 5 shows the accuracy rate results in the unbalanced reward environment. As γ and n increase, the accuracy rate of the optimal policy improves.

Table 5
The number of iterative loops the robot requires to complete the learning process in the Hill-Walking game

γ 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9

n = 1 8 11 14 19 25 34 49 79 168

n = 2 8 11 14 19 25 34 49 79 168

n = 3 8 11 14 19 25 34 49 79 168

n = 4 8 11 14 19 25 34 49 79 168

n = 5 8 11 14 19 25 34 49 79 168

n = 8 8 11 14 19 25 34 49 79 168

γ	0.1	0.2	0.3	0.4	0.5	0.6	0.7	0.8	0.9
n = 1	8	11	14	19	25	34	49	79	168
n = 2	8	11	14	19	25	34	49	79	168
n = 3	8	11	14	19	25	34	49	79	168
n = 4	8	11	14	19	25	34	49	79	168
n = 5	8	11	14	19	25	34	49	79	168
n = 8	8	11	14	19	25	34	49	79	168

Table 6

The results for the accuracy rate δ in the Hill-Walking game5

γ	0.1	0.2	0.3	0.4	0.5	0.6	0.7	0.8	0.9
n = 1	0.93	0.95	0.95	0.95	1	1	1	1	1
n = 2	1	1	1	1	1	1	1	1	1
n = 3	1	1	1	1	1	1	1	1	1
n = 4	1	1	1	1	1	1	1	1	1
n = 5	1	1	1	1	1	1	1	1	1
n = 8	1	1	1	1	1	1	1	1	1

5 Discussion

As shown by the results presented in Sections 4.2 and 4.4, the proposed EnVI method outperforms the traditional VI algorithm when solving unbalanced reward problems. The reason for this outcome is that the proposed algorithm uses a new return function that changes the discount of future rewards while reducing the influence of the current reward. The changes in the discount factor of the reward not only enable the unbalanced reward to be perceived early but can also help to reduce the number of local extreme points of the state value function in an intermediate state. As shown in Figs. 4, 5 and 7, as the value of n increases, the number of local extreme points is reduced, and the policy also improves.

Fig. 4

The results of state value function in the unbalanced rewards environment, r (s³) =0.5. When the parameters n = 1 and γ = 0.1, the state value function has a local extreme point at state s³. With the γ and n increasing, the number of local extreme points is reduced and the state value function becomes more smoothness.

Fig. 5

The results of state value function in the unbalanced reward environment, r (s⁸) = -0.5. When the parameters n = 1 and γ = 0.1, The state value function has two local extreme points at states s¹ and s⁵. With the γ and n increasing, the number of local extreme points is reduced and the state value function becomes more smoothness.

Fig. 7

The results of state value function in the Hill-Walking Game. When the parameters n = 1 and γ = 0.1, The state value function has several local extreme points. With the γ and n increasing, the number of local extreme points is reduced and the state value function becomes more smoothness.

Moreover, as shown by the results presented in Sections 4.2 and 4.4, we find that with as γ increases, the accuracy rate of the optimal policy also improves. The reason is that as γ increases, the relative weight of the immediate reward r_t for the state value function decreases. This weakens the effect of the unbalanced reward function and reduces the number of local extreme points of the state value function. However, as shown above, a larger γ will lead to more iterative loops and a greater learning time, because as γ increases, the optimal state value function becomes larger, as shown in Fig. 8. Fortunately, the proposed method can reduce the dependence of the algorithm’s performance on a large γ. Even when using a small γ, EnVI still obtains a better optimal policy than does the traditional VI algorithm.

Fig. 8

The results of the sum of absolute state value function on the Treasure Hunting game and Hill-Walking Game. In the both games, as the γ increasing, the value function becomes more large.

Note that in this study, the proposed EnVI method can only be applied in model-based learning, and the agent must know the environment precisely; however, it is very difficult to guarantee this in real-world situations. Hence, in our next study, we plan to improve EnVI and propose a new method of learning in a model-free environment. Additionally, the value n can be viewed as a reward-scaling parameter. We argue that a better understanding of its use is an important area for future research.

6 Conclusion

In this paper, we proposed a new learning method called EnVI by adopting a new return function. In EnVI, we changed form of the discount of future rewards and no longer treat the immediate reward as the primary influencing factor. We evaluated the proposed method on a Treasure-Hunting game and the results demonstrate that EnVI not only weakens the adverse effects of unbalanced reward problems but also significantly improves the optimal policy.

Footnotes

Appendix.A

In the first, we define: (16) $λ_{n} = [λ_{1}^{(n)} λ_{2}^{(n)} \dots λ_{m}^{(n)}]^{T}$ as the probability distribution of state in n - step MDP, $λ_{i}^{(n)}$ is the probability of state sⁱ, m is the size of state space. When the initial state s is given, the probability distribution $λ_{0} = [λ_{1}^{(0)} λ_{2}^{(0)} \dots λ_{m}^{(0)}]^{T}$ is a unit directional vector.

In this study, we have a theorem:

Theorem 1 In a MDP, for a fixed initial state s and policy π, the probability of state in n - step can be obtained through initial probability distribution λ₀ and state transition submatrix P_π.

Assume we have a Markov chain {s_t, π (s_t) : t ≥ 0}, where π is a fixed policy and a_t = π (s_t). We define the probability of state sⁱ in n - step later is: (17) $P_{π}^{(n)} (s^{i} | s) = P_{π} (s_{t + n} = s^{i} | s_{t} = s) .$ The transition probabilities do not depend on the time t, at which the initial state s is chose. Without loss of generality, we choose t = 0 and write (18) $P_{π}^{(n)} (s^{i} | s) = P_{π} (s_{n} = s^{i} | s_{0} = s) .$ According to the Markov property, we have $P_{π}^{(1)} = P_{π}$ . According to the Chapman - Kolmogorov equations, for any n ≥ 1, sⁱ ∈ S, s ∈ S we can get: (19) $\begin{matrix} P_{π}^{(n)} (s^{i} | s) & = & P_{π} (s_{n} = s^{i} | s_{0} = s) \\ = & \sum_{k} P_{π} (s_{N} = s^{i}, s_{n - 1} = s^{k}) | s_{0} = s) \\ = & \sum_{k} \frac{P_{π} (s_{n} = s^{i}, s_{n - 1} = s^{k}, s_{0} = s)}{P_{π} (s_{0} = s)} \\ = & \sum_{k} \frac{P_{π} (s_{n} = s^{i} | s_{n - 1} = s^{k}, s_{0} = s) P_{π} (s_{n - 1} = s^{k}, s_{0} = s)}{P_{π} (s_{0} = s)} \\ = & \sum_{k} \frac{P_{π}^{(1)} (s^{i} | s^{k}) P_{π} (s_{n - 1} = s^{k}, s_{0} = s)}{P_{π} (s_{0} = s)} \\ = & \sum_{k} P_{π}^{(1)} (s^{i} | s^{k}) P_{π}^{(n - 1)} (s^{k} | s), \end{matrix}$

where, in the second to last equality we used the Markov property to conclude that (20) $\begin{matrix} P_{π} (s_{n} = s^{i} | s_{n - 1} = s^{k}, s_{0} = s) \\ = P_{π} (s_{n} = s^{i} | s_{n - 1} = s^{k}) \\ = P_{π} (s_{1} = s^{i} | s_{0} = s^{k}) \\ = P_{π}^{(1)} (s^{i} | s^{k}) . \end{matrix}$

When n = 2 we can get (21) $P_{π}^{(2)} (s^{i} | s) = \sum_{k} P_{π} (s^{i} | s^{k}) P_{π} (s^{k} | s),$ which can be presented as matrix form $P_{π}^{(2)} = P_{π}^{2}$ . Similarly when n = 3 we can get $P_{π}^{(3)} = P_{π} \times P_{π}^{(2)} = P_{π} \times P_{π}^{2} = P_{π}^{3}$ . By analogy, we can get (22) $P_{π}^{(n)} = P_{π}^{n} .$

Combining with our definition in the beginning, we have (23) $\begin{matrix} λ_{i}^{(n)} & = & P_{π} (s_{n} = s^{i} | s_{0} = s) \\ = & P_{π}^{(n)} (s^{i} | s) \\ = & P_{π}^{n} (s^{i} | s) \\ = & \sum_{s^{k} \in S} λ_{k}^{(0)} P_{π}^{n} (s^{i} | s^{k}), \end{matrix}$ where (24) $λ_{k}^{(0)} = {\begin{matrix} 1 if s^{k} = s \\ 0 else . \end{matrix}$

The Eq. 23 can be written as the form of vector (25) $λ_{n} = (P_{π}^{n})^{T} λ_{0} .$

Hence, if policy π and initial state s are given, we can obtain the probability distribution of state in n - step. The total probability of state sⁱ in n steps is (26) $ρ^{π} (s^{i}) = \frac{1}{n} \sum_{k = 1}^{k = n} p (s \to s^{i}, k, π) = \frac{1}{n} \sum_{k = 1}^{k = n} λ_{i}^{(k)}$

References

Sutton

and Barto

, Introduction to rinforcement learning, MIT Press, 2017.

Mohsen

, Wang

and Al-Sabahi

, A hierarchical self-attentiveneural extractive summarizer via reinforcement learning, Applied Intelligence 2 (2020), 1–14.

Zhou

, Wang

, Li

and Lian

, Bench calibration method forautomotive electric motors based on deep reinforcement learning,1–, Journal of Intelligent and Fuzzy Systems 39 (2020), 1–20.

Mnih

, Kavukcuoglu

, Silver

, Graves

, Antonoglou

, Wierstra

, Riedmiller

, Playing atari with deep reinforcement learning, arXiv preprint arXiv:1312.5602 (2013).

Van

S.H.

, Van

H.H.

, Whiteson

, Wiering

, A theoretical and empirical analysis of expected sarsa, in: IEEE Symposium on Adaptive Dynamic Programming Reinforcement Learning, IEEE (2009), 177–184.

Lecun

, Bengio

and Hinton

, Deep learning, Nature 521 (2015), 436–444.

Schmidhuber

, Deep learning in neural networks: an overview, Neural Networks 61 (2015), 85–117.

Wang

, Elfwing

and Uchibe

, Modular deep reinforcementlearning from reward and punishment for robot navigation, Neural Networks 135 (2020), 115–126.

Silver

, Huang

, Maddison

C.J.

, Guez

, Sifre

, Van

d.D.G.

, Schrittwieser

, Antonoglou

, Panneershelvam

and Lanctot

, Mastering the game of go with deep neural networks and tree search, Nature 529 (2016), 484–489.

10.

, Gong

, Su

, Zhang

and Venkatesan

, An adaptiveasynchronous wake-up scheme for underwater acoustic sensor networksusing deep reinforcement learning, IEEE Transactions onVehicular Technology 70 (2021), 1851–1865.

11.

Sutton

R.S.

, Generalization in reinforcement learning: successfulexamples using sparse coarse coding, Annual Conference onNeural Information Processing Systems, Curran Associates (1996), 1038–1044in.

12.

Leike

, Martic

, Krakovna

, Ortega

P.A.

, Everitt

, Lefrancq

, Orseau

, Legg

Ai safety gridworlds, arXiv preprint arXiv:1711.09883 (2017).

13.

Amodei

, Olah

, Steinhardt

, Christiano

, Schulman

, Mané

, Concrete problems in ai safety, arXiv preprint arXiv:1606.06565 (2016).

14.

Hadfield-Menell

, Milli

, Abbeel

, Russell

, Dragan

, Inverse reward design, in: Annual Conference on Neural Information Processing Systems, Curran Associates (2017), 6765–6774.

15.

Yuan

, Yu

Z.L.

, Gu

, Deng

and Li

, A novel multi-stepreinforcement learning method for solving reward hacking, Applied Intelligence 49 (2019), 2874–2888.

16.

Aslund

, Mhamdi

E.M.E.

, Guerraoui

, Maurer

, Maurer, Virtuously safe reinforcement learning, arXiv preprint arXiv:1805.11447 (2018).

17.

Laurent

, Stuart

, Safely interruptible agents, in Uncertainty in Artificial Intelligence: 32nd Conference (2016), 557–C566.

18.

Hasselt

H.V.

, Guez

, Silver

Deep reinforcement learning with double q-learning, in: AAAI Conference on Artificial Intelligence (2015), 2094–2100.

19.

Marco

, Markov random processes are neither bandlimited norrecoverable from samples or after quantization, IEEETransactions on Information Theory 55 (2009), 900–905.

20.

Mnih

, Badia

A.P.

, Mirza

, Graves

, Lillicrap

T.P.

, Harley

, Silver

, Kavukcuoglu

, Asynchronous methods for deep reinforcement learning, in: International Conference on Machine Learning (2016).

21.

Mnih

, Kavukcuoglu

, Silver

, Rusu

A.A.

, Veness

, Bellemare

M.G.

, Graves

, Riedmiller

, Fidjeland

, Ostrovski

, et al., Human-level control through deep reinforcement learning, Nature 518 (2015), 529–533.