summaries: The authors propose a deterministic policy-gradient algorithm that extends the TD3 algorithm (Fujimoto 2018). The main claim is that it reduces overestimation issues in a more effective way. Two Q-critics are maintained with separate parameters, but updated using the same transitions. Then a convex combination of these critics is used in the deterministic policy gradient update. The mixture parameter is learned on a slower time-scale to minimize this convex combination over states (instead of taking the minimum of the 2 critics per batch as in TD3). Another contribution in the paper is the “Unbiased” variant of the algorithm (UAD3), which addresses the off-policy nature of the replay mechanism of the AD3 algorithm described above. My understanding is that this is simply a version of the algorithm that does not use any replay mechanism and samples the state iid from the on-policy distribution, so it isn’t a novel idea in itself.

summaries: This paper proposes new value-based deep reinforcement learning algorithms (AD3 and UAD3) to address the overestimation bias issue of Q learning. The main contributions of this paper are three folds: 1) The authors propose a weighted sum of two state-action value functions that are trained separately. Then, it is used to update the policy. 2) The mixing weights are updated by the two-step separation method. 3) The original method (AD3) is integrated with the idea of unbiased DRL (Zhang and Huang, 2020).

summaries: The paper presents an approach to mitigate the overestimation issue, which is quite common in RL algorithms whenever computing boostrap target is needed. The key idea is to introduce a weight parameter between two Q values and adopt a dual problem formulation to learn this weight and the policy parameters. The authors propose a two-step method to estimate these parameters and present some experiments to show the proposed algorithm's performance.

abstractText: The overestimation problem has long been popular in deep value learning, because function approximation errors may lead to amplified value estimates and suboptimal policies. There have been several methods to deal with the overestimation problem, however, further problems may be induced, for example, the underestimation bias and instability. In this paper, we focus on the overestimation issues on continuous control through deep reinforcement learning, and propose a novel algorithm that can minimize the overestimation, avoid the underestimation bias and retain the policy improvement during the whole training process. Specifically, we add a weight factor to adjust the influence of two independent critics, and use the combined value of weighted critics to update the policy. Then the updated policy is involved in the update of the weight factor, in which we propose a novel method to provide theoretical and experimental guarantee for future policy improvement. We evaluate our method on a set of classical control tasks, and the results show that the proposed algorithms are more computationally efficient and stable than several existing algorithms for continuous control.

authors:
Jakob Foerster
Nantas Nardelli
Gregory Farquhar
Triantafyllos Afouras
Philip H S Torr
Pushmeet Kohli
Shimon Whiteson

title: Stabilising experience replay for deep multi-agent reinforcement learning

authors:
Scott Fujimoto
Herke Van Hoof
David Meger

title: Addressing function approximation error in actor-critic methods

authors:
Hirotaka Hachiya
Takayuki Akiyama
Masashi Sugiyama
Jan Peters

title: Adaptive importance sampling with automatic model selection in value function approximation

title: Double q-learning

venue: In Advances in neural information processing systems,

authors:
Nan Jiang
Lihong Li

title: Doubly robust off-policy value evaluation for reinforcement learning

authors:
Timothy P Lillicrap
Jonathan J Hunt
Alexander Pritzel
Nicolas Heess
Tom Erez
Yuval Tassa
David Silver
Daan Wierstra

title: Continuous control with deep reinforcement learning

venue: arXiv preprint arXiv:1509.02971,

authors:
A Rupam Mahmood
Hado Van Hasselt
Richard S Sutton

title: Weighted importance sampling for off-policy learning with linear function approximation

authors:
Shie Mannor
Duncan Simester
Peng Sun
John N. Tsitsiklis

title: Bias and variance approximation in value function estimates

venue: Manag. Sci.,

authors:
Alberto Maria Metelli
Matteo Papini
Francesco Faccio
Marcello Restelli

title: Policy optimization via importance sampling

authors:
Volodymyr Mnih
Koray Kavukcuoglu
David Silver
Alex Graves
Ioannis Antonoglou
Daan Wierstra
Martin Riedmiller

title: Playing atari with deep reinforcement learning

venue: arXiv preprint arXiv:1312.5602,

authors:
Volodymyr Mnih
Koray Kavukcuoglu
David Silver
Andrei A Rusu
Joel Veness
Marc G Bellemare
Alex Graves
Martin Riedmiller
Andreas K Fidjeland
Georg Ostrovski

title: Human-level control through deep reinforcement learning

authors:
Volodymyr Mnih
Adria Puigdomenech Badia
Mehdi Mirza
Alex Graves
Timothy Lillicrap
Tim Harley
David Silver
Koray Kavukcuoglu

title: Asynchronous methods for deep reinforcement learning

venue: In International conference on machine learning,

authors:
Doina Precup
Richard S Sutton
Satinder Singh

title: Eligibility traces for off-policy policy evaluation

authors:
Tom Schaul
John Quan
Ioannis Antonoglou
David Silver

title: Prioritized experience replay

venue: arXiv preprint arXiv:1511.05952,

authors:
SATINDER SINGH
TOMMI JAAKKOLA
MICHAEL L. LITTMAN

title: Convergence results for single-step on-policy reinforcement-learning algorithms

title: Algorithms for reinforcement learning

venue: Synthesis lectures on artificial intelligence and machine learning,

authors:
Chen Tessler
Daniel J Mankowitz
Shie Mannor

title: Reward constrained policy optimization

venue: arXiv preprint arXiv:1805.11074,

authors:
Philip S Thomas
Emma Brunskill

title: Data-efficient off-policy policy evaluation for reinforcement learning

authors:
Hado Van Hasselt
Arthur Guez
David Silver

title: Deep reinforcement learning with double q-learning

venue: In Thirtieth AAAI conference on artificial intelligence,

authors:
Ziyu Wang
Tom Schaul
Matteo Hessel
Hado Van Hasselt
Marc Lanctot
Nando De Freitas

title: Dueling network architectures for deep reinforcement learning

venue: arXiv preprint arXiv:1511.06581,

authors:
Ziyu Wang
Victor Bapst
Nicolas Heess
Volodymyr Mnih
Remi Munos
Koray Kavukcuoglu
Nando De Freitas

title: Sample efficient actor-critic with experience

venue: replay. arXiv: Learning,

authors:
Huihui Zhang
Wu Huang

title: Unbiased deep reinforcement learning: A general training framework for existing and future algorithms

heading: INTRODUCTION

text:
The task of deep reinforcement learning (DRL) is to learn good policies by optimizing a discounted cumulative reward through function approximation. Although a variety of control tasks have gained success through DRL Mnih et al. (2013; 2015); Van Hasselt et al. (2016); Wang et al. (2015); Schaul et al. (2015); Lillicrap et al. (2015); Mnih et al. (2016), there still exists biases caused by function approximation errors, studied in prior work Mannor et al. (2007).
Overestimation bias is rooted in Q-learning by consistently maximizing a noisy value estimate, and was originally reported to be present in the algorithms, typically, like deep Q-network (DQN) Mnih et al. (2015) which is aimed for discrete control tasks. Since DQN adopts neural networks to approximate a cumulative future reward, it is unavoidable that the noise evolved from function approximation accompanies the whole training. Besides, DQN updates its policy by choosing the action that maximizes the value function, which may bring the inaccurate value approximation that outweighes the true value, i.e., the overestimation bias. This bias further accumulates at every step via bootstrapping of temporal difference learning, which estimates the value function using the value estimate of a subsequent state.
When the overestimation bias is harmful to a certain task, it will cause instability, divergence and suboptimal policy updates. To solve this, Double deep Q-networks (DDQN) Van Hasselt et al. (2016) alter the policy update strategy by taking actions based on a relatively independent target value function instead of maximizing the original Q network. DDQN not only yields more accurate value estimates, but leads to much higher scores on several games Van Hasselt et al. (2016). However, due to the randomness of approximation errors, DDQN provides no theoretical bounds for the overestimation, and the unresolved overestimation or induced underestimation makes the performance of DDQN worse than DQN in some cases, reported in Van Hasselt et al. (2016).
For the case of high-dimensional, continuous action spaces, Deep Deterministic Policy Gradient (DDPG) Lillicrap et al. (2015) provide a model-free, off-policy actor-critic method using deterministic policy gradients. Due to the slow-changing policy in an actor-critic setting, the current and target value estimates will be too dependent to circumvent bias if the solution of DDQN to overestimation is directly under the continuous control setting. Inspired by Double Q-learning Hasselt (2010)
which employ a pair of independently trained critics to achieve a less biased value estimation, the twin delayed deep deterministic policy gradient algorithm (TD3) Fujimoto et al. (2018) propose a clipped Double Q-learning variant choosing the lower target value as an approximate upper-bound to estimate the true current value, which favors underestimation biases that will not accumulate during training because actions with high value estimation are preferred. However, there are two problems lying in TD3. First, by taking actions towards the maximization of lower action-value (Q-value) at every step, the policy improvement cannot be guaranteed, which may cause potential suboptimal policies and instability. Second, using the same target value to update two critic networks will make them less independent.
The paper has the following contributions. First, we propose a combined value of two independent critics connected by a weight factor, and use it to update the policy instead of serving as a shared target estimate for the two critics, to avoid losing independence. Second, we propose a sign multiplier which determines whether the updated combined value has increased. The objective function for updating the weight factor is the product of the sign and the combined value evaluated by the updated policy. Third, we present a novel algorithm for continuous control, which can minimize the overestimation bias while providing guarantee for future policy improvement. And theoretical proofs show that the proposed algorithm has the property of asymptotical convergence and expected policy improvement. Fourth, we further apply the proposed algorithm to an unbiased framework to create another algorithm, which can remove the systematic bias due to the probability mismatch between the behavior policy and the target policy existing in off-policy methods. Fifth, extensive evaluations are conducted to compare the proposed algorithms with some baseline algorithms, in terms of computational efficiency, convergence rate and stability.

heading: BACKGROUND

text:
The task of reinforcement learning (RL) is to learn an optimal policy that maximizes a single return, i.e., the expected discounted cumulative reward of an episode. During an episode, the agent continually receives a sequence of observations by interacting with the environment before encountering an terminated state or the timeout. The return is calculated as the expected sum of future rewards. DRL combines the neural networks with RL so that the return can be approximated by the parameterized function. In DRL, the agent follows a behavior policy to determine future rewards and states, and store these observations in a memory, which will be randomly sampled over to train the network parameters and update the target Q-values. The target updates can be immediate, delayed or ”soft”.
Generally, the Q-value of DRL is represented as the expected discounted cumulative reward, an estimate function with respect to the state and action, which is given by
Qπ(s, a) = Epπ(h|s0,a0) [ ∞∑ t=0 γtr(st, at)|s0 = s, a0 = a ] , (1)
where r(s, a) is the immediate reward which is usually connected to the state-action pair, (s, a) is the value of initial state-action pair, and γ ∈ (0, 1) is the discount horizon factor for future rewards. Under the guidance of behavior policy π, pπ(h|s0, a0) is the joint probability of all state-action pairs during an episode given the initial state-action pair (s0, a0).
When neural networks are used to approximate Q-values, the update of behavior policy π is closely related to the Q network under the setting of Markov Decision Process (MDP). The Q-value function in (1) takes the state-action pair (s, a) as input and maps it to the Q-value. The foundation for updates of network parameters is the Bellman equation. Most of existing DRL algorithms adopt an independent target Q network to approximate an essential part of the target value, which can be set based on Bellman equation and organized to form the general loss function for DRL as Lillicrap et al. (2015)
L(ω) = E(s,a,r,s′) [ (r + γQ(s′, µ(s′|θ′)|ω′)−Q(s, a|ω))2 ] , (2)
where a is the action drawn from a behavior policy based on s, r and s′ are the immediate reward and next state received by interacting with the MDP environment, respectively. Overall, (s, a, r, s′) is the tuple stored in the replay buffer at every step. Besides, µ(s′|θ′) is the target policy mapping s′ to the next action a′ through a target actor network parameterized by θ′ in deterministic actor-critic
methods, instead of taking actions from the replay buffer. Moreover, ω is the parameter of current Q network, which is normally different from the target network parameter ω′.
Once the Q networks are updated, the objective at the current iteration is to optimize the actor parameter θ, which is updated by maximizing the expected return J(θ) = Es [Qπ(s, µ(s|θ)|ω)]. In the case of continuous control, θ can be updated by gradient descent∇θJ(θ).

text:
In TD3, the clipped variant of Double Q-Learning is proposed for actor-critic to reduce the overestimation bias. Instead of using a pair of actors and critics to learn twice, TD3 upper-bounds the less biased value estimate by taking the minimum between two critic networks to offer target estimation for the update of future critics. Inspired by this work, we also adopt two critic networks and their target estimates, which are parameterized by ω, Ω, ω′ and Ω′, respectively. Since we plan to deal with our problem through DRL, we can substitute sampled minibatches into the loss functions of action-values (2), which are given by
L(ω) = 1
N N∑ n=1 (rn + γQ(s ′ n, a ′ n|ω′)−Q(sn, an|ω))2, (3)
L(Ω) = 1
N N∑ n=1 (rn + γQ(s ′ n, a ′ n|Ω′)−Q(sn, an|Ω))2, (4)
where a′n = µ(s ′ n|θ′) is the action taken from the target actor network, and (sn, an, rn, s′n) is the n-th tuple of minibatches stored in replay buffer.
In TD3, the minimum of two critics is employed to serve as the target estimation value. However, updating two Q networks according to the same target estimate will make them less independent, which will further negatively affect the training efficiency. Besides, it is more reasonable to apply the clipped variant of Double Q-Learning to the procedure of actor update. Inspired by the Lagrange relaxation applied in constrained MDP problems Tessler et al. (2018), we propose a dual form of combined value function via a weight factor to determine actions reducing the harmful effect from overestimation. The dual form of combined value function for policy update is given by
π∗ = arg min 0≤λ≤1 max π [(1− λ)Qπ(s|ω) + λQπ(s|Ω)] ,∀s ∈ χ \ χ′. (5)
where Qπ(s|ω) and Qπ(s|Ω) are two critics following policy π, χ′ be the set of transient states in continuous compact state space χ, and the weight factor λ determines the influence of two Q functions. Specifically, (5) will reduce to a normal policy evaluation with one critic when λ = 0 or λ = 1. Generally, (5) needs to be solved by a two-timescale approach that may result in a saddle point problem, i.e., on the faster timescale, the policy π or its parameter is solved by (5) when fixing λ, while on the slower timescale, λ is slowly increased until the overestimation error is minimized without losing the optimal solution to (5). Due to the potential non-convexity of the action-value function, the method may lead to a sub-optimal solution, and even cause instability when the convergence is slow.
To avoid the potential saddle point problem, we first propose a two-step separation method to solve (5) for each policy update, which determines the optimal action to restrain overestimation based on the target weight factor λ′ and then use the up-to-date policy to update λ. Second, although the underestimation bias accompanying the minimization operator is far preferable to overestimation and does not explicitly propagate through the policy update, it indeed negatively affect the policy improvement at every iteration and further brings fluctuation on algorithm convergence. The policy improvement means that the optimized objective function in (5) should steadily increase during training. The insurance of this value improvement lies in the choice of weight factor λ. The process
of this separation method is given by
J(θ) = 1
N N∑ n=1 [(1− λ′)Q(sn, an|ω) + λ′Q(sn, an|Ω)] , (6)
J(λ) = 1
N N∑ n=1 [(1− λ)Q(sn, an|ω) + λQ(sn, an|Ω)] ∗ Sign(λ), (7)
where 0 ≤ λ′ ≤ 1, an = µ(sn|θ), which means actions in (6) and (7) should be taken from the policy of current actor instead of the replay buffer. We provide the guarantee of policy improvement by multiplying the averaged return for λ updating by a sign function, which is given by
Sign(λi) = I
( 1
N N∑ n=1 [ min λi Q̂(sn, an,i|ωi,Ωi, λi)− Q̂(sn, an,i−1|ωi−1,Ωi−1, λi−1) ]) , (8)
where
Q̂(s, a|ω,Ω, λ) = (1− λ)Q(s, a|ω) + λQ(s, a|Ω), (9)
an,i = µ(sn|θi) and an,i−1 = µ(sn|θi−1), which come from actor networks parameterized by current states before and after updating respectively but not from the replay buffer. I(x) produces 1 when x is negative, and vice versa. The sign denoted in (8) is actually the comparison between the minimum updated Q-values in two critics and the old (before the policy update) combined value defined in (9) .
Lemma 1. Denoting the converged values of two critics asQ(s, a|ω?) andQ(s, a|Ω?), respectively, then the convergence of combined value denoted in (9) can be ensured by minimizing (3) and (4).
Different from updating λ in (7), the averaged return for θ updating in (6) adopts the target weight factor λ′. Then (ω′,Ω′, θ′, λ′) are updated adopting the ”soft” target updates Lillicrap et al. (2015) by (ω,Ω, θ, λ), in the way of
ω′i ← τ arg min ωi L(ωi) + (1− τ)ω′i−1, Ω′i ← τ arg min Ωi L(Ωi) + (1− τ)Ω′i−1, θ′i ← τ arg max θi J(θi) + (1− τ)θ′i−1, λ′i ← τ arg min λi J(λi) + (1− τ)λ′i−1, (10)
where τ < 1 is the factor to control the speed of policy updates for the sake of small value error at each iteration, and λ′ updates following θ′. We organize the above procedures as the adaptive delayed deep deterministic policy gradient (AD3) algorithm, whose pseudocode is described by Algorithm 1.
Theorem 1. AD3 algorithm asymptotically converges as the iteration i→∞ with properly chosen learning rate.
Theorem 2. AD3 algorithm has the property of asymptotical expected policy improvement. Specifically, when the critics tend to converge, i.e., ∃K, ∀i ≥ K, ∀ε > 0,∣∣∣E(s,a) [Q̂(s, a|ωi+1,Ωi+1, λi)− Q̂(s, a|ωi,Ωi, λi)]∣∣∣ < ε, (11) then
E(s,a) [ Q̂(s, a|ωi+1,Ωi+1, λi+1) ] ≥ E(s,a) [ Q̂(s, a|ωi,Ωi, λi) ] . (12)
The proof of Theorem 1 and Theorem 2 can be found in the Appendix.
Algorithm 1 AD3 Algorithm 1: Input: The batch size N , the maximum of updates M , the timeout step T , and the soft update
parameter τ . 2: Initialization: Initialize parameters (ω,Ω, θ, λ) ← (ω0,Ω0, θ0, λ0), (ω′,Ω′, θ′, λ′) ←
(ω′0,Ω ′ 0, θ ′ 0, λ ′ 0) randomly; Initialize replay buffer R, the counter i← 0.
3: while i < M do 4: Reset randomly the initial state s1. 5: for t = 1, T do 6: Select action at according to the current behavior policy, i.e., µ(st|θi) added by exploration noise; 7: Execute actions at, get next states st+1, and immediate reward rt; 8: Store transition (st, at, rt, st+1) in R; 9: if R is full then
10: Randomly and uniformly sample the slot (si, ai, ri, si+1) from R; 11: Minimize the Q1 loss function shown in (3) by gradient decent, and then update ωi; 12: Minimize the Q2 loss function shown in (4) by gradient decent, and then update Ωi; 13: Maximize the expected return shown in (6) by gradient ascent, and then update θi; 14: Minimize the product of (7) and (8) by gradient ascent, and then update λi; 15: Execute the ”soft” target updates shown in (10) to update θ′i, ω ′ i, Ω ′ i, and λ ′ i; 16: i← i+ 1; 17: end if 18: end for 19: end while

heading: UNBIASED ADAPTIVE DELAYED DEEP DETERMINISTIC POLICY GRADIENT

text:
To further improve the performance of proposed AD3 algorithm, we employ AD3 under the framework of unbiased DRL (UDRL) Zhang & Huang (2020). UDRL attempts to solve the systematic bias induced by the approximation of MDP samples. This systematic bias happens in the experience replay mechanism without importance sampling (IS) Precup et al. (2000); Hachiya et al. (2008); Mahmood et al. (2014); Thomas & Brunskill (2016); Jiang & Li (2016); Wang et al. (2016); Foerster et al. (2017); Metelli et al. (2018), because there exists mismatch between distributions of the target policy and the behavior policy. Without IS to weight the tuples with different probabilities in commonly applied off-policy methods, the experience replay that memorizes the past observations for random samples will accumulate the systematic errors and lower the convergence performance. When applying UDRL, the independently and identically distributed (IID) initial states are parallelly sampled to start respective tuples at the beginning of each iteration. Then the parallel virtual agents follow the same behavior policy to complete their tuples, which serve as the observations to synchronously train and update the shared network parameters.
In the case of unbiased AD3 (UAD3) method, the parallelly sampled IID observations should be used to train the two critic networks, an actor network and a weight factor. At each iteration, the actions are taken following the same behavior to receive rewards and next states, so that the achieved four-tuple transition slots are independent and follow the same joint probability. By this means, no IS is required in the approximations of (3), (4), (6), (7) and (8). The pseudocode of UAD3 is organized as Algorithm 2.

heading: EXPERIMENTS

heading: CONTINUOUS MAZE

text:
One of the benchmark tasks we choose is the continuous maze which is filled with obstacles. The environment of the continuous maze problem includes infinite states and actions which is shown in Fig. 1(a). At every step, the agent is able to move towards all directions with its step size. Since the state-action space is continuous, the agent may travel through the obstacles represented by the gray grids if no effective guide is provided during the whole training. The dark solid line at the edge of Fig. 1(a) is represented as the wall to show the maze is closed except for the goal. The task of
Algorithm 2 UAD3 Algorithm 1: Input: The batch size N , the maximum of updates M , and the soft update parameter τ . 2: Initialization: Initialize parameters (ω,Ω, θ, λ) ← (ω0,Ω0, θ0, λ0), (ω′,Ω′, θ′, λ′) ←
(ω′0,Ω ′ 0, θ ′ 0, λ ′ 0) randomly.
3: for i = 1,M do 4: Sample Si = (si,1, si,2, · · · , si,N ) IID; 5: Choose actions Ai = (ai,1, ai,2, · · · , ai,N ) for Si according to the current actor network µ(Si|θi) added by exploration noise; 6: Execute actions Ai, get next states S′i = (s ′ i,1, s ′ i,2, · · · , s′i,N ) and immediate rewards Ri = (ri,1, ri,2, · · · , ri,N ); 7: Minimize the Q1 loss function shown in (3) by gradient decent, and then update ωi; 8: Minimize the Q2 loss function shown in (4) by gradient decent, and then update Ωi; 9: Maximize the expected return shown in (6) by gradient ascent, and then update θi;
10: Minimize the product of (7) and (8) by gradient ascent, and then update λi; 11: Execute the ”soft” target updates shown in (10) to update θ′i, ω ′ i, Ω ′ i, and λ ′ i; 12: end for
this experiment is move the agent from the start to the goal colored yellow with no block. This goal can be achieved by setting scores for the agent at every step. Specifically, the agent receives negative if it encounters any jam. If the agent reaches the goal, it will be rewarded 100 score. In other blank areas, the reward is set as the minus distance from the agent to the goal for the purpose of stimulating the agent to fulfill the task as soon as possible.
In this experiment, we evaluate the performance of AD3 and UAD3 algorithms, using the baseline algorithms DDPG and TD3. The hyperparameters are shown in Table 1. Every 500 iterations (update periods), an evaluation procedure is launched, which records 100 episodes and averages their results to improve accuracy, i.e., the average reward, where each episode observes the agent from the start to the goal and adds up the rewards without discount along the path. Similar evaluation procedures are shared by all experiments in the context with the same cycle.
Figure 2 illustrates the average reward versus update periods of the continuous maze with barriers of different lines plotted in Fig. 1(a). Fig. 2(a) shows that AD3 converges faster than DDPG and TD3. From Figs. 2(b)-2(c), we see UAD3 robustly converges so that the agent can reach the goal and receives a positive reward, however, other algorithms diverges and fails in their missions. The better performance is mainly due to the policy improvement clarifies in Theorem 2. Besides, adaptive λ provides a superior way to reduce overestimation.

heading: ROBOT ARM

text:
The ”robot arm” experiment is a move and grasp task which is shown in Fig. 1(b). In this figure, we just show three sections to represent a general arm that may contain several more sections. The aim of this task is to move the finger represented by the end of the arm to catch the goal. Specifically, the finger should get into the yellow ”goal box”, and then hold on to the moving goal for required steps to fulfill the grasp task. In the experiment setting, the goal is randomly moving, so the state representation includes both the positions of joints represented by the green circles and their relative positions to the goal. Besides, the number of sections determines the dimension of action space which contains the rotation angle of each section. The reward is set as the negative distance from the finger to the goal outside the ”goal box”. If the finger is located within the ”goal box”, the reward is set as 1.
We also evaluate our proposed algorithms using the baseline algorithms DDPG and TD3 based on the hyperparameters in Table 1. Fig. 3 shows the computational performance of the robot arm with 2− 7 sections by fitting scatterplots run for 800 thousand iterations. Notably, one more section will raise the state dimension by 4, including the 2-dimensional coordinates of joints and their relative coordinates to the goal. Increased state dimension needs more time for convergence and produces lower converged average reward. Throughout Fig. 3, we observe UAD3 can robustly converge to a value much higher than other algorithms, which shows the best performance because higher converged average reward means the agent can react more promptly to the moving goal. From Figs. 3(a)-3(b), AD3 converges faster and more robustly to a higher value compared with DDPG and TD3 under the same circumstance. In Fig. 3(c), AD3 converges above the zero line with a value higher than DDPG for 6 sections, however, TD3 diverges for both 6 and 7 sections. Overall, UAD3 and AD3 have better performance than their counterparts DDPG and TD3.

heading: CLASSICAL CONTROL ENVIRONMENT

text:
In this part, we adopt a series of classical control experiments including Pendulum, Acrobat, continuous mountain car and Cartpole as the benchmark tasks to evaluate the proposed AD3 and UAD3 algorithms based on the hyperparameters in Table 1.
It is noteworthy that we revised the rewards of Cartpole environment to make them more challenging. Specifically, the distance and average velocity of the cart are added to the rewards to stimulate the cart to go farther and faster because staying at the origin trading for stability is not enough to tell the robustness of algorithms. The results of the average reward, average velocity and distance versus update periods for Cartpole are given by Fig. 4. From Fig. 4(a), we see UAD3 and AD3 can converge much faster and more stably than DDPG and TD3. Besides, UAD3 and AD3 are able to simulate the cart to move faster and farther according to Figs. 4(b) and 4(c), respectively. Figs. 5(a)-5(c) present the results of average reward versus update periods for Pendulum, Acrobat and continuous mountain car, which further show the advantages of UAD3 and AD3 over DDPG and TD3. Moreover, we reproduce the results of UDDPG Zhang & Huang (2020) for a fair comparison with UAD3. From Figs. 4 and 5, we see that UAD3 is even better than UDDPG in higher convergence speed, converged average reward, and stability.

heading: CONCLUSION

text:
In this paper, we proposed the combined value of two independent critics connected by a weight factor to update the policy, which will in turn to update the combined value. We also proposed the objective function for updating the weight factor by multiplying the updated combined value by a sign, which compares the minimum updated Q-value in two critics with the combined value before updating. Based on the above two components, we present AD3 to reduce the overestimation bias and ensure future policy improvement at the same time. Furthermore, we apply AD3 to UDRL framework to eliminate the systematic bias caused by the probability mismatch between the behavior policy and the target policy in experience replay, and present UAD3. The proposed AD3 algorithm is theoretically proved to possess the property of asymptotical convergence and expected policy
improvement. Evaluation results show that our proposed algorithms can boost and stabilize the convergence. Although we represent the weight factor as a variable in the context, it can be formulated as a function of states. It can be seen that all theorems and proofs can apply to it when lambda is state-dependent, and all the experimental results are based on the model of state-dependent weight factor λ(s). The network architecture of weight factor concerning states is clarified in Appendix.

heading: APPENDIX

heading: PROOF OF LEMMA 1

heading: Proof

text:
E(s,a) [ (Q̂(s, a|ω,Ω, λ)− Q̂(s, a|ω?,Ω?, λ))2 ] ,
=E(s,a) [ ((1− λ)(Q(s, a|ω)−Q(s, a|ω?)) + λ(Q(s, a|Ω)−Q(s, a|Ω?)))2 ] ,
≤E(s,a) { [(1− λ)(Q(s, a|ω)−Q(s, a|ω?))]2 + [λ(Q(s, a|Ω)−Q(s, a|Ω?))]2 } ,
→0, (13)
where the converged combined value Q̂(s, a|ω?,Ω?, λ) = (1− λ)Q(s, a|ω?) + λQ(s, a|Ω?).

heading: PROOF OF THEOREM 1

text:
Proof This proof is based on Lemma 1 of SINGH et al. (2000), which is moved originally below for convenience.
Lemma 1 of SINGH et al. (2000): Consider a stochastic process (αt,∆t, Ft), t ≥ 0, where αt,∆t, Ft : X → R, which satisfies the equations
∆t+1(x) = (1− αt(x))∆t(x) + αt(x)Ft(x), x ∈ X, t = 0, 1, 2, · · · (14)
Let Pt be a sequence of increasing σ-fields such that α0,∆0 are P0-measurable and αt,∆t and Ft−1 are Pt-measurable, t = 1, 2, · · · Assume that the following hold:
1. the set of possible states X is finite. 2. 0 ≤ αt(x) ≤ 1, ∑ t αt(x) =∞, ∑ t α 2 t (x) <∞ w.p.1. 3. ‖E{Ft(·)|Pt}‖ ≤ γ‖∆t‖+ ct, where γ ∈ [0, 1) and ct converges to zero w.p.1. 4. V ar{Ft(x)|Pt} ≤ K(1 + ‖∆t‖)2, where K is some constant.
Then ∆t converges to zero with probability one (w.p.1).
Within the scope of this paper, the MDP state space is finite, satisfying condition 1 in Lemma 1 of SINGH et al. (2000), and Lemma condition 2 holds by proper selection of learning rate. According to Szepesvári (2010), even the commonly used constant learning rate can make algorithms converge in distribution.
We apply Lemma 1 of SINGH et al. (2000) with Pt = {Q(·, ·|ω0), Q(·, ·|Ω0), s0, a0, r1, s1, · · · , st, at}. Following the update rule for optimizing (3) and (4) and using the current policy to produce the action at+1 = µ(st+1|θ), we have
Q(st, at|ωt+1) = (1− αt)Q(st, at|ωt) + αt [rt + γQ(st+1, at+1|ωt)] , (15) Q(st, at|Ωt+1) = (1− αt)Q(st, at|Ωt) + αt [rt + γQ(st+1, at+1|Ωt)] . (16)
Under the setting of our proposed algorithm, we denote ∆t = Q̂(·, ·|ωt,Ωt, λ) − Q?(·, ·), which is the difference between the combined value of weighted critics denoted in (9) and optimal value function. Then we have
∆t+1(st, at) = Q̂(st, at|ωt+1,Ωt+1, λ)−Q?(st, at), =(1− λ)Q(st, at|ωt+1) + λQ(st, at|Ωt+1)−Q?(st, at),
=(1− αt) [ Q̂(st, at|ωt,Ωt, λ)−Q?(st, at) ] + αtFt,
=(1− αt)∆t(st, at) + αtFt(st, at), (17)
where the third equality is due to the substitution of (15) and (16), and Ft(st, at) = rt + γ [ Q̂(st+1, at+1|ωt,Ωt, λ) ] −Q?(st, at). (18)
Since the reward is bounded within the scope of this paper, the action-values are also bounded, then condition 4 in Lemma 1 of SINGH et al. (2000) holds. According to the proof in Theorem 2 of SINGH et al. (2000), there is ‖E [Ft(st, at)|Pt] ‖ ≤ γ‖∆t‖, which satisfies condition 3 in Lemma 1 of SINGH et al. (2000).
Finally, it can be concluded that Q̂(·, ·|ωt,Ωt, λ) converges to Q?(·, ·) with probability 1.

heading: PROOF OF THEOREM 2

text:
Proof If signi+1 ≥ 0, then E(s,a) [ Q̂(s, a|ωi+1,Ωi+1, λi+1) ] = Es [ Q̂(s, µ(s|θi+1)|ωi+1,Ωi+1, λi+1)
] ≈ 1 N N∑ n=1 Q̂(sn, µ(sn|θi+1)|ωi+1,Ωi+1, λi+1)
≥ 1 N min
( N∑
n=1
Q(sn, µ(sn|θi+1)|ωi+1), N∑
n=1
Q(sn, µ(sn|θi+1)|Ωi+1)
)
≥ 1 N N∑ n=1 [ Q̂(sn, µ(sn|θi)|ωi,Ωi, λi) ] ≈ E(s,a) [ Q̂(s, a|ωi,Ωi, λi) ] , (19)
where the approximations the mean average is statistically equal to the expectation (or unbiased approximation for UAD3), the first inequality holds based on (9), and the second inequality holds because (8) is no less than 0.
Otherwise, if signi+1 ≤ 0, then E(s,a) [ Q̂(s, a|ωi+1,Ωi+1, λi+1) ] = Es [ Q̂(s, µ(s|θi+1)|ωi+1,Ωi+1, λi+1)
] ≈ 1 N N∑ n=1 Q̂(sn, µ(sn|θi+1)|ωi+1,Ωi+1, λi+1)
≥ 1 N N∑ n=1 Q̂(sn, µ(sn|θi+1)|ωi+1,Ωi+1, λi)
= 1
N N∑ n=1 Q̂(sn, µ(sn|θi+1)|ωi+1,Ωi+1, λ′i)
≥ 1 N N∑ n=1 Q̂(sn, µ(sn|θi)|ωi+1,Ωi+1, λ′i)
= 1
N N∑ n=1 Q̂(sn, µ(sn|θi)|ωi+1,Ωi+1, λi)
≈ Es [ Q̂(s, µ(s|θi)|ωi,Ωi, λi) ] = E(s,a) [ Q̂(s, a|ωi,Ωi, λi) ] , (20)
where the first inequality holds due to the fact that the update of λ is to maximize (7) given a negative sign, the second inequality holds because the update of θ is to maximize (6). Although (19) and (20) are done for immediate target updates, the same conclusions can be achieved under the condition of delayed or ”soft” target updates if the Q network is linear with respect to the actor and critic parameters.

heading: NETWORK ARCHITECTURE

text: We construct the critic network using a fully-connected MLP with two hidden layers. The input is composed of the state and action, outputting a value representing the Q-value. The ReLU function is adopted to activate the first hidden layer. The setting of actor network is similar to that of the critic network, except that the input is the state and the output is multiplied by the action supremum after tanh nonlinearity. The network of weight factor λ is constructed similar to the actor network except replacing the tanh nonlinearity by clipping λ in [0, 1]. The architecture of networks are plotted in Fig. 6.

heading: HYPERPARAMETERS

text: Table 1 lists the common hyperparameters shared by all experiments and their respective settings.

heading: ESTIMATE OF Q-VALUE

text: We uniformly sample 10000 states from the replay buffer every 500 update periods, and average the computed Q-values based on the newly-updated current policy. The averaged Q-value can be seen as the estimate of discounted cumulative return (value estimate). The value estimates of Cartpole, Robotarm of 2 sections and Pendulum experiments are plotted in Fig. 7. From these figures, we can see the converged value function Q(s, a|ω?) denoted in Lemma 1.

title: DEEP REINFORCEMENT LEARNING WITH ADAPTIVE COMBINED CRITICS


summaries: The authors proposed inverse reinforcement learning (IRL) algorithm based on Monte Carlo expectation-maximization (MCEM) that maximizes the predictive distribution of trajectories given the reward distribution parameter (eq (1)). In my understanding, the knowledge of the environment dynamics is assumed. The authors tried to validate the proposed idea on objectworld (Levine et al., 2011)

summaries: The authors propose an approach to model-based inverse reinforcement learning which estimates a Gaussian mixture model over reward-function parameters. The method uses MCEM and samples reward functions from a current estimate of the GMM, updates them via a gradient-descent based maximum likelihood approach and then updates the GMM to fit the updated parameters. The authors evaluate the approach on objectworld.

summaries: The paper proposes a novel method for inverse reinforcement learning: inferring a (distribution over) reward functions from a set of expert demonstrations. Prior work has either learned a point-estimate, notably maximum entropy IRL, or used Bayesian methods to learn a probability distribution over reward functions. Maximum entropy IRL has scaled to complex environments with unknown dynamics and non-linear rewards (with methods such as AIRL), but do not learn a probability distribution. By contrast, Bayesian IRL is more theoretically principled, but has not scaled to complex environments or non-linear rewards. This paper performs maximum likelihood estimation of a parameter for a *generative model* over probability distributions, using a Monte-Carlo expectation-maximization (MCEM) method. It therefore still outputs a probability distribution like Bayesian IRL, but is able to learn non-linear rewards unlike prior Bayesian methods.

abstractText: The goal of the inverse reinforcement learning (IRL) problem is to recover the reward functions from expert demonstrations. However, the IRL problem like any ill-posed inverse problem suffers the congenital defect that the policy may be optimal for many reward functions, and expert demonstrations may be optimal for many policies. In this work, we generalize the IRL problem to a well-posed expectation optimization problem stochastic inverse reinforcement learning (SIRL) to recover the probability distribution over reward functions. We adopt the Monte Carlo expectation-maximization (MCEM) method to estimate the parameter of the probability distribution as the first solution to the SIRL problem. The solution is succinct, robust, and transferable for a learning task and can generate alternative solutions to the IRL problem. Through our formulation, it is possible to observe the intrinsic property for the IRL problem from a global viewpoint, and our approach achieves a considerable performance on the objectworld.

authors:
Pieter Abbeel
Andrew Y Ng

title: Apprenticeship learning via inverse reinforcement learning

venue: In Proceedings of the twenty-first international conference on Machine learning,

authors:
Pieter Abbeel
Dmitri Dolgov
Andrew Y Ng
Sebastian Thrun

title: Apprenticeship learning for motion planning with application to parking lot navigation

venue: In 2008 IEEE/RSJ International Conference on Intelligent Robots and Systems,

authors:
Andrew G Barto
Richard S Sutton
Charles W Anderson

title: Neuronlike adaptive elements that can solve difficult learning control problems

venue: IEEE transactions on systems, man, and cybernetics,

authors:
James G Booth
James P Hobert

title: Maximizing generalized linear mixed model likelihoods with an automated monte carlo em algorithm

venue: Journal of the Royal Statistical Society: Series B (Statistical Methodology),

authors:
Brian S Caffo
Wolfgang Jank
Galin L Jones

title: Ascent-based monte carlo expectation– maximization

authors:
KS Chan
Johannes Ledolter

title: Monte carlo em estimation for time series models involving counts

venue: Journal of the American Statistical Association,

authors:
Jaedeug Choi
Kee-Eung Kim

title: Map inference for bayesian inverse reinforcement learning

venue: In Advances in Neural Information Processing Systems,

authors:
Chelsea Finn
Paul Christiano
Pieter Abbeel
Sergey Levine

title: A connection between generative adversarial networks, inverse reinforcement learning, and energy-based models

venue: arXiv preprint arXiv:1611.03852,

authors:
Chelsea Finn
Sergey Levine
Pieter Abbeel

title: Guided cost learning: Deep inverse optimal control via policy optimization

authors:
Gersende Fort
Eric Moulines

title: Convergence of the monte carlo expectation maximization for curved exponential families

venue: The Annals of Statistics,

authors:
Justin Fu
Katie Luo
Sergey Levine

title: Learning robust rewards with adversarial inverse reinforcement learning

venue: arXiv preprint arXiv:1710.11248,

authors:
Karol Hausman
Yevgen Chebotar
Stefan Schaal
Gaurav Sukhatme
Joseph J Lim

title: Multi-modal imitation learning from unstructured demonstrations using generative adversarial nets

authors:
Jonathan Ho
Stefano Ermon

title: Generative adversarial imitation learning

authors:
Jonathan Ho
Jayesh Gupta
Stefano Ermon

title: Model-free imitation learning with policy optimization

venue: In International Conference on Machine Learning,

authors:
William Kruskal
Frederick Mosteller

title: Representative sampling, iii: The current statistical literature

venue: International Statistical Review/Revue Internationale de Statistique,

authors:
Sergey Levine
Zoran Popovic
Vladlen Koltun

title: Nonlinear inverse reinforcement learning with gaussian processes

authors:
Yunzhu Li
Jiaming Song
Stefano Ermon

title: Infogail: Interpretable imitation learning from visual demonstrations

authors:
Bernard Michini
Jonathan P How

title: Improving the efficiency of bayesian inverse reinforcement learning

venue: In 2012 IEEE International Conference on Robotics and Automation,

title: Efficient memory-based learning for robot control

authors:
Philipp Moritz
Robert Nishihara
Stephanie Wang
Alexey Tumanov
Richard Liaw
Eric Liang
Melih Elibol
Zongheng Yang
William Paul
Michael I Jordan

title: Ray: A distributed framework for emerging {AI} applications

venue: In 13th {USENIX} Symposium on Operating Systems Design and Implementation ({OSDI}

authors:
Andrew Y Ng
Stuart J Russell

title: Algorithms for inverse reinforcement learning

venue: In Icml,

authors:
Deepak Ramachandran
Eyal Amir

title: Bayesian inverse reinforcement learning

venue: In IJCAI,

authors:
Nathan D Ratliff
J Andrew Bagnell
Martin A Zinkevich

title: Maximum margin planning

venue: In Proceedings of the 23rd international conference on Machine learning,

title: Learning agents for uncertain environments

venue: In Proceedings of the eleventh annual conference on Computational learning theory,

authors:
Umar Syed
Robert E Schapire

title: A game-theoretic approach to apprenticeship learning

authors:
Emanuel Todorov
Tom Erez
Yuval Tassa

title: Mujoco: A physics engine for model-based control

venue: In 2012 IEEE/RSJ International Conference on Intelligent Robots and Systems,

authors:
Ziyu Wang
Josh S Merel
Scott E Reed
Nando de Freitas
Gregory Wayne
Nicolas Heess

title: Robust imitation of diverse behaviors

authors:
Greg CG Wei
Martin A Tanner

title: A monte carlo implementation of the em algorithm and the poor man’s data augmentation algorithms

venue: Journal of the American statistical Association,

authors:
Markus Wulfmeier
Peter Ondruska
Ingmar Posner

title: Maximum entropy deep inverse reinforcement learning

venue: arXiv preprint arXiv:1507.04888,

title: Modeling purposeful adaptive behavior with the principle of maximum causal entropy

authors:
Brian D Ziebart
Andrew L Maas
J Andrew Bagnell
Anind K Dey

title: Maximum entropy inverse reinforcement learning

venue: In Aaai,

heading: 1 INTRODUCTION

text:
The IRL problem addresses an inverse problem that a set of expert demonstrations determines a reward function over a Markov decision process (MDP) if the model dynamics are known Russell (1998); Ng et al. (2000). The recovered reward function provides a succinct, robust, and transferable definition of the learning task and completely determines the optimal policy. However, the IRL problem is ill-posed that the policy may be optimal for many reward functions and expert demonstrations may be optimal for many policies. For example, all policies are optimal for a constant reward function. In a real-world scenario, experts always act sub-optimally or inconsistently, which is another challenge.
To overcome these limitations, two classes of probabilistic approaches for the IRL problem are proposed, i.e., Bayesian inverse reinforcement learning (BIRL) Ramachandran & Amir (2007) based on Bayesians’ maximum a posteriori (MAP) estimation and maximum entropy IRL (MaxEnt) Ziebart et al. (2008); Ziebart (2010) based on frequentists’ maximum likelihood (MLE) estimation. BIRL solves for the distribution of reward functions without an assumption that experts behave optimally, and encode the external a priori information in a choice of a prior distribution. However, BIRL also suffers from the practical limitation that a large number of algorithmic iterations is required for the procedure of Markov chain Monte Carlo (MCMC) in a sampling of posterior over reward functions. Advanced techniques, for example Kernel technique Michini & How (2012) and gradient method Choi & Kim (2011), are proposed to improve the efficiency and tractability of this situation.
MaxEnt employs the principle of maximum entropy to resolve the ambiguity in choosing demonstrations over a policy. This class of methods, inheriting the merits from previous non-probabilistic IRL approaches including Ng et al. (2000); Abbeel & Ng (2004); Ratliff et al. (2006); Abbeel et al. (2008); Syed & Schapire (2008); Ho et al. (2016), imposes regular structures of reward functions in a combination of hand-selected features. Formally, the reward function is a linear or nonlinear combination of the feature basis functions which consists of a set of real-valued functions {φi(s, a)}i=1 hand-selected by experts. The goal of this approach is to find the best-fitting weights of feature basis functions through the MLE approach. Wulfmeier et al. (2015) and Levine et al. (2011) use deep neural networks and Gaussian processes to fit the parameters based on demonstrations respectively but still suffer from the problem that the true reward shaped by the changing environment dynamics.
Influenced by the work of Finn et al. (2016a;b), Fu et al. (2017) propose a framework called adversarial IRL (AIRL) to recover robust reward functions in a changing dynamics based on adversarial learning and achieves superior results. Compared with AIRL, another adversarial method called generative
adversarial imitation learning (GAIL) Ho & Ermon (2016) seeks to directly recover the expert’s policy rather than reward functions. Many follow-up methods enhance and extend GAIL for multipurpose in various application scenarios Li et al. (2017); Hausman et al. (2017); Wang et al. (2017). However, GAIL is in a lack of an explanation of expert’s behavior and a portable representation for the knowledge transfer which are the merits of the class of the MaxEnt approach, because the MaxEnt approach is equipped with the "transferable" regular structures over reward functions.
In this paper, under the framework of the MaxEnt approach, we propose a generalized perspective of studying the IRL problem called stochastic inverse reinforcement learning (SIRL). It is formulated as an expectation optimization problem aiming to recover a probability distribution over the reward function from expert demonstrations. The solution of SIRL is succinct and robust for the learning task in the meaning that it can generate more than one weight over feature basis functions which compose alternative solutions to the IRL problem. Benefits of the class of the MaxEnt method, the solution to our generalized problem SIRL is also transferable. Since of the intractable integration in our formulation, we employ the Monte Carlo expectation-maximization (MCEM) approach Wei & Tanner (1990) to give the first solution to the SIRL problem in a model-based environment. In general, the solutions to the IRL problem are not always best-fitting in the previous approaches because a highly nonlinear inverse problem with the limited information is very likely to get trapped in a secondary maximum in the recovery. Taking advantage of the Monte Carlo mechanism of a global exhaustive search, our MCEM approach avoids the secondary maximum and theoretically convergent demonstrated by pieces of literature Caffo et al. (2005); Chan & Ledolter (1995). Our approach is also quickly convergent because of the preset simple geometric configuration over weight space in which we approximate it with a Gaussian Mixture Model (GMM). Hence, our approach works well in a real-world scenario with a small and variability set of expert demonstrations.
In particular, the contributions of this paper are threefold:
1. We generalize the IRL problem to a well-posed expectation optimization problem SIRL.
2. We provide the first theoretically existing solution to SIRL by the MCEM approach.
3. We show the effectiveness of our approach by comparing the performance of the proposed method to those of the previous algorithms on the objectworld.

heading: 2 PRELIMINARY

text:
An MDP is a tupleM := 〈S,A, T , R, γ〉, where S is the set of states, A is the set of actions, and the transition function (a.k.a. model dynamics) T := P(st+1 = s′ ∣∣st = s, at = a) for s, s′ ∈ S and a ∈ A is the probability of being current state s, taking action a and yielding next state s′. Reward functionR(s, a) is a real-valued function and γ ∈ [0, 1) is the discount factor. A policy π : S → A is deterministic or stochastic, where the deterministic one is written as a = π(s), and the stochastic one is as a conditional distribution π(a|s). Sequential decisions are recorded in a series of episodes which consist of states s, actions a, and rewards r. The goal of reinforcement learning aims to get optimal policy π∗ for maximizing the expected total reward, i.e.
π∗ := arg max π E [ ∞∑ t=0 γt · R(st, at) ∣∣∣π].
Given an MDP without a reward functionR, i.e., MDP\R=〈S,A, T 〉, and m expert demonstrations ζE := {ζ1, · · · , ζm}. Each expert demonstration ζi is a sequential of state-action pairs. The goal of the IRL problem is to estimate the unknown reward functionR(s, a) from expert demonstrations ζE and the reward functions compose a complete MDP. The estimated complete MDP yields an optimal policy that acts as closely as the expert demonstrations.

heading: 2.1 REGULAR STRUCTURE OF REWARD FUNCTIONS

text:
In this section, we provide a formal definition of the regular (linear/nonlinear) structure of reward functions. The linear structure Ng et al. (2000); Ziebart et al. (2008); Syed & Schapire (2008); Ho
et al. (2016) is an M linear combination of feature basis functions, written as,
R(s, a) := M∑ i αi · φi(s, a),
where φi : S ×A 7−→ Rd are a d-dimensional feature functions hand-selected by experts. The nonlinear structure Wulfmeier et al. (2015) is of the form as follows,
R(s, a) := N ( φ1(s, a), · · · , φM (s, a) ) ,
where N is neural networks of hand-crafted reward feature basis functions {φi(s, a)}Mi=1. In the following section, we propose an optimization problem whose solution is a probability distribution over weights of basis functions {φi(s, a)}i=1.

heading: 2.2 PROBLEM STATEMENT

text:
Given an MDP\R := (S,A, T , γ) with a known transition function T := P(st+1 = s′ ∣∣st = s, at = a) for s, s′ ∈ S and a ∈ A and a hand-crafted reward feature basis function {φi(s)}Mi=1. A stochastic regular structure on the reward function assumes weightsW of the reward feature functions φi(s), which are random variables with a reward conditional probability distributionDR(W|ζE) conditional on expert demonstrations ζE . Parametrizing DR(W|ζE) with parameter Θ, our aim is to estimate the best-fitting parameter Θ∗ from the expert demonstrations ζE , such that DR(W|ζE ,Θ∗) more likely generates weights to compose reward functions as the ones derived from expert demonstrations, which is called stochastic inverse reinforcement learning problem.
Suppose a representative trajectory class CE satisfies that each trajectory element set O ∈ CE is a subset of expert demonstrations ζE with the cardinality at least · |ζE |, where is a preset threshold and |ζE | is the number of expert demonstrations, written as,
CE := { O ∣∣∣O ⊂ ζE with |O| ≥ · |ζE |}.
Integrate out unobserved weightsW , and the SIRL problem is formulated to estimate parameter Θ on an expectation optimization problem over the representative trajectory class as follows:
Θ∗ := arg max Θ EO∈CE [ ∫ W fM(O,W|Θ)dW ] , (1)
where trajectory element set O assumes to be uniformly distributed for the sake of simplicity in this study, and fM is the conditional joint probability density function of trajectory element O and weightsW for reward feature functions conditional on parameter Θ.

heading: 2.2.1 NOTE:

text:
• Problem 1 is well-posed and typically not intractable analytically. • Trajectory element set O is usually known from the rough estimation of the statistics in
expert demonstrations in practice.
• We introduce representative trajectory class to overcome the limitation of the sub-optimality of expert demonstrations ζE Ramachandran & Amir (2007), which is also called a lack of sampling representativeness in statistics Kruskal & Mosteller (1979), e.g., driver’s demonstrations encode his own preferences in driving style but may not reflect the true rewards of an environment. With the technique of representative trajectory class, each subset of driver’s demonstrations (i.e. trajectory element set O) constitutes a subproblem in Problem 1.

heading: 3 METHODOLOGY

text: In this section, we propose a novel approach to estimate the best-fitting parameter Θ∗ in Problem 1, which is called the two-stage hierarchical method, a variant of MCEM method.

heading: 3.1 TWO-STAGE HIERARCHICAL METHOD

text:
The two-stage hierarchical method requires us to write parameter Θ in a profile form Θ := (Θ1,Θ2). The conditional joint density fM(O,W|Θ) in Equation 1 can be written as the product of two conditional densities gM and hM as follows:
fM(O,W|Θ1,Θ2) = gM(O|W,Θ1) · hM(W|Θ2). (2)
Take the log of both sides in Equation 2, and we have
log fM(O,W|Θ1,Θ2) = log gM(O|W,Θ1) + log hM(W|Θ2). (3)
We maximize the right side of Equation 3 over the profile parameter Θ in the expectationmaximization (EM) update steps at the t-th iteration independently as follows,
Θt+11 : = arg max Θ1
E ( log gM(O|W,Θ1) ∣∣∣CE ,Θt); (4)
Θt+12 : = arg max Θ2
E ( log hM(W|Θ2) ∣∣∣Θt). (5)

heading: 3.1.1 INITIALIZATION

text:
We randomly initialize profile parameter Θ0 := (Θ01,Θ 0 2) and sample a collection of N0 rewards weights {WΘ01 , · · · ,WΘ 0 N } ∼ DR(W|ζE ,Θ02). The reward weightsWΘ 0
i compose reward RWΘ0i in each learning taskM0i := (S,A, T , RWΘ0i , γ) for i = 1, · · · , N0.

heading: 3.1.2 FIRST STAGE

text:
In the first stage, we aim to update parameter Θ1 in the intractable expectation of Equation 4. Specifically, we take a Monte Carlo method to estimate model parameters Θt+11 in an empirical expectation at the t-th iteration,
E [ log gM(O|W,Θt+11 ) ∣∣∣CE ,Θt] := 1Nt · Nt∑ i=1 log gMti(O t i |WΘ t i ,Θ t+1 1 ), (6)
where reward weights at the t-th iterationWΘti are randomly drawn from the reward conditional probability distribution DR(W|ζE ,Θt) and compose a set of learning tasksMti := (S,A, T , RWΘti , γ) with a trajectory element set Oti uniformly drawn from representative trajectory class CE , for i = 1, · · · , Nt.
The parameter Θt+11 in Equation 6 hasNt coordinates written as Θ t+1 1 := ( (Θt+11 )1, · · · , (Θ t+1 1 )Nt ) .
For each learning taskMti, the i-th coordinate (Θ t+1 1 )i is derived from maximization of a posteriori,
(Θt+11 )i := arg max θ log gMti ( Oti |WΘ t i , θ ) ,
which is a convex formulation maximized by a gradient ascent method.
In practice, we move m steps uphill to the optimum in each learning taskMti. The update formula of m-step reward weightsWmΘ t
i is written as
WmΘ t i :=WΘ t i + m∑ i=1 λti · ∇(Θ1)i log gMti ( Oti |WΘ t i , (Θ1)i ) ,
where the learning rate λti at the t-th iteration is preset. Hence, the parameter Θ t+1 1 is represented as Θt+11 := ( WmΘ t 1 , · · · ,Wm Θt Nt ) .

heading: 3.1.3 SECOND STAGE

text:
In the second stage, we aim to update parameter Θ2 in the intractable expectation of Equation 5. Specifically, we consider the empirical expectation at the t-th iteration as follows,
E ( log hM(W|Θt+12 ) ∣∣∣Θt) := 1 Nt · Nt∑ i=1 log hMti(W mΘ t i |Θt+12 ), (7)
where hM is implicit but fitting a set of m-step reward weights {WmΘ t i } Nt i=1 in a generative model yields a large empirical expectation value. The reward conditional probability distribution DR(W|ζE ,Θt+12 ) is a generative model formulated as a Gaussian Mixture Model (GMM), i.e.
DR(W|ζE ,Θt+12 ) := K∑ k=1 αk · N (W|µk,Σk),
where αk ≥ 0 and ∑K k=1 αk = 1, and parameter set Θ t+1 2 := {αk;µk,Σk}Kk=1.
We estimate parameter Θt+12 in GMM by EM approach and initialize GMM with the t-th iteration parameter Θt2 with the procedure as follows:
For i = 1, · · · , Nt, we have
• Expectation Step: Compute responsibility γij for m-step reward weightWmΘ t i ,
γij := αj · N (WmΘ
t i |µj ,Σj)∑K k=1 αk · N (Wm Θt i |µk,Σk) .
• Maximization Step: Compute weighted mean µj and variance Σj by,
µj :=
∑Nt i=1 γij · Wm Θt
i∑Nt i=1 γij ; αj := 1 Nt · Nt∑ i=1 γij ; Σj := ∑Nt i=1 γij · (Wm Θt i − µj) · (Wm Θt i − µj)T∑Nt i=1 γij .
After EM converges, Θt+12 := {αk;µk,Σk}Kk=1 and profile parameter Θt+1 := (Θ t+1 1 ,Θ t+1 2 ).
Finally, when the two-stage hierarchical method converges, parameter Θ2 of profile parameter Θ is our desired best-fitting parameter Θ∗ for DR(W|ζE ,Θ∗).

heading: 3.2 TERMINATION CRITERIA

text:
In this section, we discuss the termination criteria in our algorithm. EM terminates usually when the parameters do not substantively change after enough iterations. For example, one classic termination criterion in EM terminates at the t-th iteration satisfying as follows,
max |θt − θt−1| |θt|+ δEM < EM ,
for user-specified δEM and EM , where θ is the model parameter in EM.
However, the same termination criterion for MCEM has a risk of early terminating because of the Monte Carlo error in the update step. Hence, we adopt a practical method in which the following stopping criterion holds in three consecutive times,
max |Θt −Θt−1| |Θt|+ δMCEM < MCEM ,
for user-specified δMCEM and MCEM Booth & Hobert (1999). Other stopping criteria for MCEM refers to Caffo et al. (2005); Chan & Ledolter (1995).

heading: 3.3 CONVERGENCE ISSUE

text:
The convergence issue of MCEM is more complicated than EM. In light of model-based interactive MDP\R, we can always increase the sample size during each iteration of MCEM. In practice, we require the Monte Carlo sample size satisfy the following inequality,∑
t
1
Nt <∞.
Additional requirement for the convergence property is a compact assumption over that parameter space. A comprehensive proof refers to Chan & Ledolter (1995); Fort et al. (2003).
The pseudocode is given in Appendix.

heading: 4 EXPERIMENTS

text:
We evaluate our approach on a classic environment objectworld introduced by Levine et al. (2011) which is a particularly challenging environment with a large number of irrelevant features and the highly nonlinearity of the reward functions. Note that since almost only objectworld provides a tool that allows analysis and display the evolution procedure of the SIRL problem in a 2D heat map, we skip the typical invisible physics-based control tasks for the evaluation of our approach, i.e. cartpole Barto et al. (1983), mountain car Moore (1990), MuJoCo Todorov et al. (2012), and etc.
We employ the expected value difference (EVD) proposed by Levine et al. (2011) to be the metric of optimality as follows:
EVD(W) := E [ ∞∑ t=0 γt ·R(st, at) ∣∣∣π∗]− E[ ∞∑ t=0 γt ·R(st, at) ∣∣∣π(W)],
which is a measure of the difference between the expected reward earned under the optimal policy π∗, given by the true reward, and the policy derived from the rewards sampling from our reward conditional probability distribution D(W|ζE ,Θ∗), where Θ∗ is the best estimation parameter in our approach.

heading: 4.1 OBJECTWORLD

text:
The objectworld is a learning environment for the IRL problem. It is an N × N grid board with colored objects placed in randomly selected cells. Each colored object is assigned one inner color and one outer color from C preselected colors. Each cell on the grid board is a state, and stepping to four neighbor cells (up, down, left, right) or staying in place (stay) are five actions with a 30% chance of moving in a random direction.
The ground truth of the reward function is defined in the following way. Suppose two primary colors of C preselected colors are red and blue. The reward of a state is 1 if the state is within 3 steps of an outer red object and 2 steps of an outer blue object, -1 if the state is within 3 steps of an outer red object, and 0 otherwise. The other pairs of inner and outer colors are distractors. Continuous and discrete versions of feature basis functions are provided. For the continuous version, φ(s) is a 2C-dimensional real-valued feature vector. Each dimension records the Euclidean distance from the state to objects. For example, the first and second coordinates are the distances to the nearest inner and outer red object respectively, and so on through all C colors. For the discrete version, φ(s) is a (2C ·N)-dimensional binary feature vector. Each N -dimensional vector records a binary representation of the distance to the nearest inner or outer color object with the d-th coordinate 1 if the corresponding continuous distance is less than d.

heading: 4.2 EVALUATION PROCEDURE AND ANALYSIS

text:
In this section, we design three tasks to evaluate the effectiveness of our generative model reward conditional probability distribution D(W|ζE ,Θ∗). For each task, the environment setting is as follows. The instance of a 10 × 10 objectworld has 25 random objects with 2 colors and a 0.9 discount factor. 20 expert demonstrations are generated according to the given optimal policy for the
recovery. The length of each expert demonstration is 5-grid size trajectory length. Four algorithms for the evaluation includes MaxEnt, DeepMaxEnt, SIRL, and DSIRL, where SIRL and DSIRL are implemented as Algorithm 2 in Appendix. The weights are drawn from reward conditional probability distribution D(W|ζE ,Θ∗) as the coefficients of feature basis functions {φi(s, a)}i=1. In our evaluation, SIRL and DSIRL start from 10 samples and double the sample size per iteration until it converges for the convergence issue, refer to Section 3.2. In the first stage, the epochs of algorithm iteration are set to 20 and the learning rates are 0.01. The parameter in representative trajectory set OE is preset as 0.95. In the second stage, 3-component GMM for SIRL and DSIRL is set with at most 1000 iterations before convergence. Additionally, the architecture of neural networks in DeepMaxEnt and DSIRL are implemented as 3-layer fully-connected with the sigmoid function.

heading: 4.2.1 EVALUATION PLATFORM

text: All the methods are implemented in Python 3.5 and Theano 1.0.0 with a machine learning distributed framework Ray Moritz et al. (2018). The experiments are conducted on a machine with Intel(R) Core(TM) i7-7700 CPU @ 3.60GHz and Nvidia GeForce GTX 1070 GPU.

heading: 4.2.2 RECOVERY EXPERIMENT

text:
In the recovery experiment, we compare the true reward function, the optimal policy, and the optimal value with ones derived from expert demonstrations under the four methods. Since our approach is an average of all the outcomes which are prone to imitate the true optimal value from expert demonstrations, we use the mean of reward conditional probability distribution for SIRL and DSIRL as a comparison.
In Figure 1, the EVD of the optimal values in the last row are 48.9, 31.1, 33.7 and 11.3 for four methods respectively, and the covariances of GMM model for SIRL and DSIRL are limited up to 5.53 and 1.36 on each coordinate respectively. It yields that in a highly nonlinear inverse problem, the recovery abilities of SIRL and DISRL are better than MaxEnt’s and DeepMaxEnt’s respectively. The reason is mainly because Monte Carlo mechanism in our approach alleviates the problem of getting stuck in local minima by allowing random exit from it.

heading: 4.2.3 ROBUSTNESS EXPERIMENT

text:
In the robustness experiment, we evaluate the robustness of our approach that solutions generated by D(W|ζE ,Θ∗) are effective to the IRL problem. To capture the robust solutions, we design the following generative algorithm with the pseudocode in Algorithm 1.
In the right generative algorithm, we use Frobenius norm to measure the distance between weights drawn fromD(W|ζE ,Θ∗) as follows,
||W||F := √ Tr(W ·WT ).
We also constrain that each drawn weight W ∼ D(W|ζE ,Θ∗) in the solution set G satisfies as follows,
||W −W ′||F > δ and EVD(W) < ,
whereW ′ represents any member in the solution set G. δ, are the preset thresholds in the generative algorithm.
Algorithm 1: Generative Algorithm Input: D(W|ζE ,Θ∗), required solution set size N , and preset thresholds and δ. Output: Solution set G := {Wi}Ni=1.
while i < N do W ∼ D(W|ζE ,Θ∗) ; for anyW ′ ∈ S do
if ||W −W ′||F > δ and EVD(W) < then G ← W;
end end i← i+ 1;
end
In Figure 2, the right column figures are generated from weights in the solution set G whose EVD values are around 10.2. Note that the recovered reward function in the first row has a similar but different pattern appearance. The optimal value derived from these recovered reward functions has a very small EVD value with the true reward. It yields the effectiveness of our robust generative model which can generate more than one solutions to the IRL problem.

heading: 4.2.4 HYPERPARAMETER EXPERIMENT

text: In the hyperparameter experiment, we evaluate the effectiveness of our approach under the influence of different preset quantities and qualities of expert demonstrations. The amount of information carried in expert demonstrations composes a specific learning environment, and hence it has an impact on the effectiveness of our generative model. We verify three hyperparameters including the number of expert demonstrations in Figure 3, the trajectory length of expert demonstrations in Figure 4 and the portion size in representative trajectory class CE in Figure 5 on the objectworld. The shadow of the line in the figures represents the standard error for each experimental trail. Notice that the EVDs for SIRL and DSIRL are both decreasing as the number and the trajectory length of expert demonstrations, and the portion size in the representative trajectory class are increasing. A notable point in Figure 3 is that very few expert demonstrations (less than 200) for our approach also yields a small EVDs, which manifests the merit of Monte Carlo mechanism in our approach.

heading: 5 CONCLUSION

text: In this paper, we propose a generalized problem SIRL for the IRL problem to get the distribution of reward functions. The new problem is well-posed and we employ the method of MCEM to give the first succinct, robust, and transferable solution. In the experiment, we evaluate our approach on the objectworld and the experimental results confirm the effectiveness of our approach.

heading: A APPENDIX

text:
The pseudocode of SIRL in Section 3 is as follows.
Algorithm 2: Stochastic Inverse Reinforcement Learning Input: Model-based environment (S,A, T ) and expert demonstrations ζE , Monte Carlo sample size N0, and preset thresholds δMCEM and MCEM . Output: Reward conditional probability distribution DR(W|ζE ,Θ∗).
Initialization: Randomly initialization of profile parameter Θ0 := (Θ01,Θ02); while stopping criteria not satisfied (refer to Section 3.2) do
Draw Nt reward weightsWΘ t i ∼ DR(W|ζE ,Θt2) to compose learning taskMti with uniformly drawn trajectory element set Oti ; # First Stage: Monte Carlo estimation of weights for reward function; for Mti do
Evaluate∇(Θ1)i log gMti ( Oti |WΘ t i , (Θ1)i )
; Compute updated weight parameter WmΘ t
i ←WΘ t i + ∑m i=1 λ t i · ∇(Θ1)i log gMti ( Oti |WΘ t i , (Θ1)i )
; end Update Θt+11 ← {Wm Θt i } Nt i=1 ; # Second Stage: Fit GMM with m-step reward weight {WmΘ t
i } Nt i=1 with EM parameter
initialization Θt2 ; while EM not converge do
Expectation Step: γij ← αj ·N (W mΘt i |µj ,Σj)∑K k=1 αk·N (WmΘ t i |µk,Σk) ; Maximization Step:
µj ← ∑Nt i=1 γij · Wm Θt
i∑Nt i=1 γij ; αj ← 1 Nt · Nt∑ i=1 γij ;
Σj ← ∑Nt i=1 γij · (Wm Θt i − µj) · (Wm Θt
i − µj)T∑Nt i=1 γij ;
end Update Θt+12 and profile parameter Θ t+1 ← (Θt+11 ,Θ t+1 2 );
end