Model-Free Deep Inverse Reinforcement Learning by Logistic Regression

Recently, Wulfmeier et al. [29‐31] proposed deep IRL, which combined MaxEnt-IRL with a deep neural network architecture to find nonlinear reward functions. However, their method suffers from the same three problems as MaxEnt-IRL. First, deep MaxEnt-IRL is basically a model-based approach, and therefore, an environmental state transition probability is assumed to be known in advance. Second, MaxEnt-IRL requires a routine to solve forward RL problems with estimated reward functions for every iteration step. This process is usually very time-consuming and computationally expensive, even when a model of the environment is available. Finally, MaxEnt-IRL is data inefficient because it requires a set of trajectories to estimate reward. In general, a dataset consists of different length trajectories before termination, and the estimation process is sensitive to the variation.

To overcome the first and second problems of MaxEnt-IRL, relative entropy-based inverse reinforcement learning (RelEnt-IRL) [4] and Path Integral with LOCal optimality (PI_LOC) [9] introduce a sampling distribution to handle unknown environmental state transition probability. More specifically, RelEnt-IRL uses a uniform sampling distribution while PI_LOC uses the distribution that lies in the vicinity of the demonstration in order to evaluate the partition function of the probability distribution of the demonstration. Finn et al. proposed Guided Cost Learning (GCL) that improves sampling efficiency of deep MaxEnt-IRL [5]. As opposed to RelEnt-IRL and PI_LOC, GCL adapts the sampling distribution using policy optimization. They are model-free MaxEnt-IRL, but they would still suffer from the third problem.

Generative Adversarial Imitation Learning (GAIL) [8] and its model-based version [1] extract a policy directly from data as if it were obtained by reinforcement learning following inverse reinforcement learning. Their formulation is similar to Generative Adversarial Network [6] and the discriminator of GAIL distinguishes between unnormalized distribution of state-action pairs of an optimal and a learned policy. Therefore, GAIL is similar to our method because our method discriminates between data from the optimal and baseline state transition. A potential difficulty is that GAIL should estimate the normalized distribution defined over the state and action space. On the other hand, our method maintains functions defined over the state space, which are usually easier to approximate.

We here show a derivation of the simplified Bellman equation for inverse reinforcement learning. From Eqs. (4) and (5), we obtain the following relation for the discounted reward setting:The above equation shows that the optimal state transition is represented by the baseline state transition, state-dependent reward, and state value function. Taking the logarithm of both sides yields the following critical relation for the discounted reward setting [22]:Equation (6) plays an important role in our IRL algorithms. Similar equations can be derived for average-reward, first-exit, and finite-horizon problems. Note that the right hand side of Eq. (6) is not a temporal difference error because \(q(\mathbf{x})\) is the state-dependent part of the reward function in Eq. (3).

Applying the Bayes rule into Eq. (6) yields the following:Our goal is to estimate \(\beta q(\mathbf{x})\) and \(\beta V(\mathbf{x})\) from the observed data, and we assume two datasets of state transitions. One is \(\mathcal {D}^\pi \) from the controlled probability:where \(N^\pi \) denotes the number of data points. This is called the expert dataset. In the standard IRL setting, \(\mathcal {D}^\pi \) is interpreted as data from experts to be investigated. The other is a dataset from the uncontrolled probability:where \(N^b\) denotes the number of data points. This is called the baseline dataset. We are interested in estimating ratios \(\pi (\mathbf{x}) / b(\mathbf{x})\) and \(\pi (\mathbf{x}, \mathbf{y}) / b(\mathbf{x}, \mathbf{y})\) from \(\mathcal {D}^b\) and \(\mathcal {D}^\pi \). Note that our method solves two density ratio estimation problems while the standard IRL method such as MaxEnt-IRL solve one density estimation problem. In many cases, density ratio estimation is easier than density estimation [19].

This subsection shows how Eq. (7) is used to estimate \(\beta q(\mathbf{x})\) and \(\beta V(\mathbf{x})\). LogReg, which is a density estimation method using logistic regression [3, 19], is appropriate to estimate the log ratio of the following two densities: \(\ln \pi (\mathbf{x})/b(\mathbf{x})\) and \(\ln \pi (\mathbf{x}, \mathbf{y})/b(\mathbf{x}, \mathbf{y})\). First, to estimate \(\ln \pi (\mathbf{x})/b(\mathbf{x})\), assign a selector variable \(\eta = -1\) to the samples from the uncontrolled probability and \(\eta = 1\) to the samples from the controlled probability:The density ratio can be represented by applying the Bayes rule:The first ratio, \(\Pr (\eta = -1)/\Pr (\eta = 1)\), is estimated by \(N^b/N^\pi \), and the second ratio is computed after estimating the conditional probability \(\Pr (\eta \mid \mathbf{x})\) by a logistic regression classifier:where \(\sigma (x) = 1/(1 + \exp (-x))\) is a sigmoid function and \(f_x(\mathbf{x}; \mathbf{w}_x)\) denotes a deep neural network function parameterized by the weight vector \(\mathbf{w}_x\). Note that the logarithm of the density ratio is given byNetwork weights \(\mathbf{w}_x\) can be estimated by the backpropagation whose objective function is given by the following negative regularized log-likelihood.where \(\lambda _x\) is a regularization constant. The closed-form solution is not derived, but it is possible to minimize it efficiently by standard nonlinear optimization methods such as backpropagation. Note that the first density ratio estimation is not necessary if we can assure \(\pi (\mathbf{x}) = b(\mathbf{x})\). In this case, we do not need to evaluate the density ratio network because \(\ln \pi (\mathbf{x}) / b(\mathbf{x}) = 0\).

Next, \(\ln \pi (\mathbf{x}, \mathbf{y}) / b(\mathbf{x}, \mathbf{y})\) is estimated by Eq. (7) in the same way. Nonlinear function approximators for \(\beta q(\mathbf{x})\) and \(\beta V(\mathbf{x})\) are respectively introduced bywhere \(r_\mathrm{est}(\mathbf{x}, \mathbf{w}_r)\) and \(V_\mathrm{est}(\mathbf{x}, \mathbf{w}_V)\) denote the deep neural network of the state dependent reward parameterized by the weights \(\mathbf{w}_r\) and that of the state value function parameterized by \(\mathbf{w}_V\), respectively. By substituting Eqs. (8) and (9) into Eq. (7), we obtain the following relationship:The above equation is also interpreted as a density ratio estimation problem, and network parameters \(\mathbf{w}_r\) and \(\mathbf{w}_V\) are estimated by logistic regression in which the classifier is given byNote that the inverse temperature \(\beta \) is not estimated as an independent parameter. The parameter vectors, \(\mathbf{w}_r\) and \(\mathbf{w}_V\), are optimized by standard logistic regression algorithms in the same way as \(\mathbf{w}_x\).

Figure 1 shows our proposed deep neural network for inverse reinforcement learning. The input consists of current state \(\mathbf{x}\) and next state \(\mathbf{y}\), and the output consists of label \(\eta \) that addresses whether \((\mathbf{x}, \mathbf{y})\) are given from \(\mathcal {D}^\pi \) or \(\mathcal {D}^b\). The network has three sub-networks: density-ratio network \(f_x(\mathbf{x}; \mathbf{w}_x)\), reward network \(r_\mathrm{est}(\mathbf{x}; \mathbf{w}_r)\), and state value function network \(V_\mathrm{est}(\mathbf{x}; \mathbf{w}_V)\). Note that state \(\mathbf{y}\) is given only to the value network. After the sub-networks compute the log of the density ratio, the reward, and the value functions, the log of the density ratio is computed by the Bellman equation (7) and used to compute the classifier’s probability (10).

This section explains how the result of inverse reinforcement learning is used to find an optimal policy by forward reinforcement learning. Because our IRL method estimates the state value function, it should be used to initialize a part of the deep neural networks for forward reinforcement learning. We adopt the dueling network that represents state values and state-dependent action advantages separately [27]. Using the definition of the advantage function (1), the state-action value function is decomposed into two functions:However, we cannot utilize the decomposition because V and A are not recovered from Q uniquely. Therefore, Wang et al. [27] propose to impose a constraint on the advantage function. Since the advantage function measures whether or not the action is better or worse than the policy’s average action, it is represented bywhere \(P(\mathbf{x}, a)\) is the preference function and \(|\mathcal {A} |\) denotes the number of actions. Note that the second term in the right hand side of Eq. (12) is the average preference value under a uniformly random policy. As noted by Wang et al. [27], the advantage function computed by Eq. (12) is slightly different from Eq. (1), but it is reported that using Eq. (12) increases the stability of the optimization. Figure 2 shows the deep neural network for forward reinforcement learning. The input is the current state \(\mathbf{x}\) and the output consists of the state action value function. The network has three sub-networks: reward network \(r_\mathrm{est}(\mathbf{x}; \mathbf{w}_r)\), state value function network \(V_\mathrm{est}(\mathbf{x}; \mathbf{w}_V)\) and the preference network. To optimize the state value and preference function networks, many algorithms such as SARSA, Deep Q Network (DQN) [13], Double DQN [26] can be used and we adopt DQN for simplicity.

To validate our method, we selected Atari 2600 games provided by the Arcade Learning Environment [2], which has been a popular benchmark for evaluating reinforcement learning progress in recent years [7, 13, 27]. In particular, we chose six games: Boxing, Breakout, Enduro, Pong, Seaquest, and Space Invaders.

To collect the expert dataset, we generated 1.5 million frames of human gameplay experiences in the format ofwhere \(a_{i, t}^{\mathrm {human}}\) is an action executed by a subject. We collected the data from three subjects. Then, we selected the state transition data \(\{ (\mathbf{x}_{i,t}^\pi , \mathbf{x}_{i,t+1}^\pi ) \}\) to construct \(\mathcal {D}^\pi \). On the other hand, we found that a policy that selects actions uniformly at random did not explore the environment efficiently because the game was over at the early stage of game plays. Therefore, for every state \(\mathbf{x}_t\) in \(\mathcal {D}^\pi \) a uniformly random action \(a_t^{\mathrm {random}}\) is executed, and sample the next state. In other words, the baseline dataset is constructed byIn this sampling method, we assured \(\pi (\mathbf{x}) = b(\mathbf{x})\) and we removed the density ratio network from the entire networks shown in Fig. 1. Although this sampling method is not always possible for real-world applications, a similar method is used in PI_LOC [9] that is interpreted as a sampling-based MaxEnt-IRL.

We follow the basic setup of previous studies [7, 13, 26, 27] to implement the deep neural networks of inverse reinforcement learning. In each sub-network, there are three convolutional layers followed by two fully-connected layers. The first convolutional layer has 32 \(8 \times 8\) filters with stride 4, the second 64 \(4 \times 4\) filters with stride 2, and the third and final convolutional layer has 64 \(3 \times 3\) filters with stride 1. The deep neural networks of forward reinforcement learning has the same low-level convolutional structure of that of inverse reinforcement learning. The preference function network has a fully connected layer with 512 units. The final hidden layers of the preference function are both fully-connected with \(|\mathcal {A} |\) neurons.

Since IRL is an ill-posed problem and the reward function is not uniquely determined, we cannot compare the estimated reward function with the original reward function of the game. However, we could not compare our method with deep MaxEnt-IRL [29‐31] because deep MaxEnt-IRL has to find an optimal policy for every iteration and it took enormous time on the games of Atari 2600. Therefore, we selected PI_LOC [9] for comparison because \(\mathcal {D}^b\) can be used to evaluate the partition function. Instead of solving forward reinforcement learning, PI_LOC evaluates the partition function from a set of trajectories generated by the baseline state transition given by \(\mathcal {T}^b = \{ \tau _j \}_{j=1}^{\tilde{N}^b}\), where \(\tau _j = \mathbf{x}_{j, 0}^b, \mathbf{x}_{j, 1}^b, \ldots , \mathbf{x}_{j, T_j}^b\). The log likelihood is formulated byWe used \(\mathcal {D}^b\) to construct \(\mathcal {T}^b\). This is reasonable because trajectories in \(\mathcal {T}^b\) should be noisy trajectories around the optimal state transitions. Note that \(|\mathcal {T}^\pi |\) is much smaller than \(|\mathcal {D}^\pi |\) because an element in \(\mathcal {T}^\pi \) is a trajectory. To evaluate the quality of the estimated reward and state value function, we computed an optimal policy by forward reinforcement learning with them and compared the learning speed. We considered four learning settings illustrated in Fig. 3:To train the deep neural networks of forward reinforcement learning, we use the identical learning algorithm, experience replay, clipping the gradient used by Wang et al. [27]. The major difference is an action selection strategy and we adopted softmax action selection in which a stochastic policy is calculated by \(\pi (a \mid \mathbf{x}) \propto \exp (Q(\mathbf{x}, a)/T)\), where T is a temperature that controls the randomness. According to the previous studies [26, 27], we start the game with up to 30 no-op actions to provide random starting positions for the agent. The discount factor is set to 0.99.

Figure 4 compares the learning speed, in which the performance is evaluated by the score of the game. A training epoch is 250,000 frames and for every 10 epochs we evaluate the network of forward reinforcement learning with a testing epoch that lasts 125,000 frames. The horizontal solid and dotted lines represent the performance of human experts and CLONING, respectively. The error bars in each panel shows one standard deviation from the mean scores of CLONING and those of forward reinforcement learning methods, respectively.

In all of the six game environments, the best learning performance was achieved by the setting \((r_\mathrm{original}, V_\mathrm{est})\). That is, we found the best performance when the state value function of forward reinforcement learning was initialized by the result of inverse reinforcement learning and the original game reward was used. As compared with the standard forward reinforcement learning setting \((r_\mathrm{original}, 0)\), the learning speed was significantly improved. On the other hand, the policies trained with the estimated reward \(r_\mathrm{est}\) was poorer than those trained with the original reward \(r_\mathrm{original}\) at the final performance at the end of training. This is not surprising, because the expert datasets provided by the subjects were not optimal. However, we also found that the setting \((r_\mathrm{est}, V_\mathrm{est})\) achieved slightly better scores than the human plays on the games of Enduro and Seaquest. This suggests that our proposed method retrieved more useful information from the dataset. In addition, the learning speed was improved by initializing the state value function when we compared the speed of \((r_\mathrm{est}, V_\mathrm{est})\) with that of \((r_\mathrm{est}, 0)\). The performance of PI_LOC was extremely poor in this experiment. One possible reason is that PI_LOC is sensitive to the trajectory length and its variation. \(\sum _t \gamma ^t r_\mathrm{est}(\mathbf{x}_{i,t}; \mathbf{w}_r)\) is a Monte Carlo estimate of the value of the trajectory \(\tau _i\) and it has large variance for small \(\tilde{N}^\pi \) and large \(T_i\).

Reversi (a.k.a. Othello), which is a deterministic, perfect information, zero-sum game for two players, has been studied by the AI community [11, 12, 20, 24, 25, 32]. The game’s goal is to control a majority of the pieces at the end of the game by forcing as many of your opponent’s pieces to be turned over on an \(8 \times 8\) board as possible. A single move might change up to 20 pieces, and an average of 60 moves are needed to complete the game. Although reinforcement learning has been successfully applied to the game of GO, which is much more complicated than Reversi, it took a huge amount of computing time to find an optimal policy [18]. This provides motivation for finding a dense reward structure by IRL.

To prepare \(\mathcal {D}^\pi \), we used three stationary policies: the first policy is RANDOM, which always selects a random action from available actions. The other players are HEUR and COEV that take an action based on the following evaluation functionwhere \(x_i\) is 1 when the square i is occupied by the player’s own disc, \(-1\) when it is occupied by an opponent’s disc and 0 when it is not occupied, and \(w_i\) is the weight. Notice that n is a random variable that is sampled from a uniform distribution U(a, b) on the interval (a, b). Adding a noise to the evaluation is for the reason that we would like to collect a variety of game trajectories. The weight \(w_i\) of HEUR is determined manually while that of COEV is optimized by a co-evolutionary computation method [11]. Every policy repeatedly played against every other, and then the state transitions were retrieved from the game trajectories of the winners. On the other hand, the baseline dataset \(\mathcal {D}^b\) was constructed by retrieving the state transitions from the trajectories in which two RANDOM policies played the game. The numbers of samples are \(|\mathcal {D}^\pi |= |\mathcal {D}^b |= 10^5\).

In this experiment, each sub-network of IRL is implemented by a feedforward neural network with two hidden layers [24, 25] with rectified linear units and one linear output layer. As opposed to the previous experiment, the density ratio network is important because we cannot assume \(\pi (\mathbf{x}) = b(\mathbf{x})\). The input is given by a 64-node vector \(\mathbf{x}\in \{ -1, 0, +1 \}^{64}\), where 0 represents an empty square, and \(+1\) and \(-1\) respectively represent the black and white pieces. Every hidden layer has 100 nodes. Since the computational cost of finding an optimal policy on the game of Reversi is much cheaper than that on the Atari 2600 games, we can evaluate the model-based Wulfmeier’s method that computes the partition function with dynamic programming. Table 1 compares the approximate computing time for estimating reward between the proposed method, Wulfmeier’s model-based deep MaxEnt-IRL, and PI_LOC, where the code is written in python and executed on a Ubuntu Linux 14.04 LTS AMD64 systems, using Intel Xeon E5-1620V30 CPU with 32 GB RAM and Tesla K40C. PI_LOC needed less computing time than the proposed method because PI_LOC does not need to estimate the state value function as well as the density ratio. Apparently, the computing time was much shorter than that of Wulfmeier’s method because our method and PI_LOC did not solve forward reinforcement learning.

As we did in the previous Sect. 4.1, we evaluated seven policies optimized by the following settings (1) \((r_\mathrm{original}, V_\mathrm{est})\), (2) \((r_\mathrm{est}, V_\mathrm{est})\), (3) \((r_\mathrm{original}, 0)\), (4) \((r_\mathrm{est}, 0)\), (5) \((r_{\mathrm {Wulfmeier}}, 0)\),(6) \((r_\mathrm{PI\_LOC}, 0)\), and (7) CLONING, where the fifth setting means that the value function is initialized by zero while the reward function estimated by Wulfmeier’s method was used to train the deep networks of forward reinforcement learning. Notice that a policy obtained by CLONING is interpreted as a mixed policy of RAND, HEUR, and COEV. The original reward associated with a terminal state is 1, 0, and \(-1\), respectively, for win, tie, and lose. The discount factor is set to 0.99.

Figure 5 illustrates how the win rate develops during training when tested versus fixed stationary policies RANDOM, HEUR, COEV, and CLONING. Interestingly, the best learning speed and the best win rate were achieved by the setting \((r_\mathrm{est}, V_\mathrm{est})\). The policy trained with the setting \((r_\mathrm{original}, V_\mathrm{est})\) outperformed all of the four policies, but it took about \(3 \times 10^4\) plays to defeat HEUR and COEV and \(5.5 \times 10^4\) plays to defeat CLONING. A comparison between (a) and (c) and that between (b) and (d) revealed that initializing a state value function by the proposed method was quite effective for faster learning. In fact, CLONING outperformed the policy trained with the setting \((r_\mathrm{original}, r_\mathrm{est})\) because a poor policy at the early stage of learning failed to collect good experiences. There were no significant difference between (d) and (e), and it suggests that the reward estimated by the proposed method was similar to that by Wulfmeier’s method from a viewpoint of learned policies at the end. On the contrary, Fig. 5f shows that the performance of model-free PI_LOC was slightly worse than that of the model-based Wulfmeir’s method. This is not surprising because it was relatively easy to construct the state transition dynamics of the Reversi even though the opponent was not modeled explicitly.

Figure 6 depicts how the win rate develops during training when tested versus learning agents. We did not show the result of learning from self-play because the win rate was always 100%. Note that these experiments do not satisfy the Markovian assumption because two learning agents interacted at the same time. Even if the opponent was a learning agent, the best learning speed and the best win rate were achieved by the setting \((r_\mathrm{est}, V_\mathrm{est})\). Figure 6c shows that the agent trained with the original reward could not win the agents trained with the reward estimated by the IRL methods. Since the same learning algorithm was used, the results should be explained by the difference of reward functions. One possible reason is that \(r_\mathrm{est}\), \(r_{\mathrm {Wulfmeier}}\), and \(r_\mathrm{PI\_LOC}\) had a dense structure that provides more information about the game. Consequently, the agents trained with those reward functions learned faster than the agent with \(r_{\mathrm {original}}\). There were no significant difference between (d) and (e) as we observed in Fig. 5.