In-Trajectory Inverse Reinforcement Learning: Learn Incrementally From An Ongoing Trajectory

Authors: shicheng  liu
minghui  zhu
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-08 16:05:23

Abstract: Inverse reinforcement learning (IRL) aims to learn a reward function and a corresponding policy that best fit the demonstrated trajectories of an expert. However, current IRL works cannot learn incrementally from an ongoing trajectory because they have to wait to collect at least one complete trajectory to learn. To bridge the gap, this paper considers the problem of learning a reward function and a corresponding policy while observing the initial state-action pair of an ongoing trajectory and keeping updating the learned reward and policy when new state-action pairs of the ongoing trajectory are observed. We formulate this problem as an online bi-level optimization problem where the upper level dynamically adjusts the learned reward according to the newly observed state-action pairs with the help of a meta-regularization term, and the lower level learns the corresponding policy. We propose a novel algorithm to solve this problem and guarantee that the algorithm achieves sub-linear local regret $O(\sqrt{T}+\log T+\sqrt{T}\log T)$. If the reward function is linear, we prove that the proposed algorithm achieves sub-linear regret $O(\log T)$. Experiments are used to validate the proposed algorithm.

Main paper: 
 introduction: 
 Inverse reinforcement learning (IRL) aims to learn a reward function and a corresponding policy that are consistent with the demonstrated trajectories of an expert. In recent years, several IRL methods are proposed to help learn the reward and policy, including maximum margin methods [1, 2] , maximum entropy methods [3, 4] , maximum likelihood methods [5, 6] , and Bayesian methods [7, 8] .The aforementioned IRL works learn from pre-collected demonstration sets and do not improve the learned model during deployment. Online IRL [9, 10, 11] instead can learn from sequentially arrived demonstrated trajectories and continuously improve the learned reward and policy from the newly observed complete trajectories. However, recent applications of IRL motivate the need to learn incrementally from an ongoing trajectory before it terminates. For example, inferring a moving shooter's intention from its ongoing movement in order to evacuate the hiding victims [12] before the shooter finds them. In this case, we need to quickly update the inference about the shooter's intention once a new movement of the shooter is observed, so that we can use the latest inference to plan a rescue strategy as soon as possible. We cannot wait until the shooter trajectory ends, in case the shooter has found the victims. Another example is learning a target customer's investment preference from its daily updated investment trajectory in a stock market [13] in order to recommend appropriate stocks [14, 15] before other competitors get this customer. However, current IRL works cannot learn from an ongoing trajectory because they have to wait to collect at least one complete trajectory to learn from. To bridge the gap, this paper proposes in-trajectory IRL, a new type of IRL that learns a reward function and a corresponding policy at the initial state-action pair of an ongoing trajectory, and keeps updating the learned reward and policy once a new state-action pair of the ongoing trajectory is observed. We summarize our contributions as follows:Contribution statement. This paper proposes the first in-trajectory IRL framework, termed metaregularized in-trajectory inverse reinforcement learning" (MERIT-IRL), to learn a reward function and a corresponding policy from an ongoing trajectory. Our contributions are twofold.First, we formulate this in-trajectory learning problem as an online bi-level optimization problem where the upper level continuously updates the learned reward according to the newly observed state-action pairs and the lower level computes the corresponding policy. We develop a novel online learning algorithm (MERIT-IRL) to solve this problem. The major novelty of the proposed algorithm is that we propose a novel reward update mechanism specially designed for the in-trajectory learning setting. This special reward update not only aims to explain the expert trajectory observed so far, but also aims to consider for the future. Moreover, since the data is lacking as there is only one ongoing trajectory, we introduce a meta-regularization term to embed prior knowledge and avoid overfitting.Second, we theoretically guarantee that MERIT-IRL achieves sub-linear local regret O(√ T + log T + √ T log T ).If the reward function is linear, we prove that MERIT-IRL achieves sub-linear regret O(log T ). The major novelty of the theoretical analysis is to address the difficulty that the input data is not identically independent distributed (i.i.d.) but temporally correlated, i.e., the data (s t , a t ) at each time t is affected by the data (s t-1 , a t-1 ) at last time.Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? Answer: [Yes] Justification: The abstract summarizes our contributions, and the introduction has a "contribution statement" part which elaborates our contributions and mentions the consistency with theoretical and experiment results. The assumptions and limitations are included in "theoretical analysis" (Subsection 4.2) and Appendix F. Guidelines:• The answer NA means that the abstract and introduction do not include the claims made in the paper. • The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 
related works: 
 Due to the space limit, we only discuss the related works on learning from incomplete trajectories here, and we include the discussion on more related works in Appendix A.Papers [16, 17] use partial trajectories to update the learned reward function by comparing the expert trajectories after the expert states and the trajectories starting from those expert states rolled out by the learned policy. However, given the current expert state, they use expert trajectory suffix (i.e., future trajectory) to compare while we can only access expert trajectory prefix (i.e., previous trajectory) from an ongoing trajectory. Papers [18, 19, 20] use imitation learning to learn from incomplete demonstrations. In specific, paper [18] uses a discounted sum along the future trajectory as the weight for weighted behavior cloning and works effectively even if only portions of trajectories are observed. Papers [19, 20] extend GAIL [21] to solve for the case where the action sequences are not complete. However, these works all require a pre-collected set of demonstrations so that they are not in-trajectory learning since the trajectory in their cases is not ongoing.Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes] Justification: The limitation is mentioned in Appendix F. Under the assumptions, i.e., Assumptions 1 and 2, we have a justification of either the assumption is widely used in literature or the assumption can be satisfied by real scenarios. Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
problem formulation: 
 In this section, we formulate the problem of in-trajectory IRL. In in-trajectory IRL, there is an expert whose decision-making is based on a Markov decision process (MDP). An MDP is a tuple (S, A, γ, r E , P 0 , P ) which consists of a state set S, an action set A, a discount factor γ ∈ [0, 1), a reward function r E : S × A → R, and the initial state distribution P 0 (•). The state transition probability (density) function is denoted by P (•|•, •) such that P (s ′ |s, a) denotes the probability (density) of state transition to s ′ from s by taking action a. The expert is using its policy π E to demonstrate an ongoing trajectoryζ E = S E 0 , A E 0 , S E 1 , A E 1 ,• • • and at each time t, only the stateaction pair (S E t , A E t ) is observed. We want to learn a reward function and a corresponding policy from the ongoing trajectory and update the learned reward function and policy at each time t.Many IRL algorithms [5, 6, 11, 22, 23] employ a bi-level learning structure. In this structure, the upper level learns a reward function while the lower level aims to find an associated policy by solving an RL problem under the current learned reward function. Inspired by their bi-level learning structure, we formulate the in-trajectory IRL problem as an online non-convex bi-level optimization problem. In specific, we aim to learn a reward function r θ (parameterized by θ) in the upper level and a policy corresponding to r θ in the lower level. The loss function at time t is defined as:EQUATIONNote that L t (θ; (S E t , A E t )) is defined using π θ and θ is the parameter of the reward function r θ , here the policy π θ is also parameterized by θ because it is computed by solving an RL problem (in the lower level) under the reward function r θ , and thus is indirectly parameterized by θ. Maximum likelihood IRL (ML-IRL) [5] has a similar bi-level formulation with (1), however, ML-IRL only solves an offline optimization problem and its analysis does not hold for non i.i.d. input data and continuous state-action space. We discuss our distinctions from ML-IRL in Appendix A. 1 .The upper-level loss function L t has two terms. The first term -γ t log π θ (A E t |S E t ) is the discounted negative log-likelihood of the state-action pair (S E t , A E t ) at time t and the second term λγ t 2 ||θ -θ|| 2 is the discounted meta-regularization term [24] where λ is a hyper-parameter. The likelihood function is commonly used in IRL [5, 6] to learn a reward function. Basically, the upper-level loss function at time t encourages to find a reward function r θ that makes the observed state-action pair (S E t , A E t ) most likely and meanwhile, the reward parameter θ should not be too far from the prior experience, i.e., the meta-prior θ. Note that θ is a pre-trained meta-prior that embeds the information of "relevant experience". We will introduce the training of θ in Subsection 4.3 and Appendix C.The lower-level problem is used to compute π θ using the current reward function r θ . It proposes to find a policy π θ that maximizes the entropy-regularized cumulative reward J θ (π) + H(π). The cumulative reward of a policy π under the reward function r θ is J θ (π) ≜ E π S,A [ ∞ t=0 γ t r θ (S t , A t )] where the initial state is drawn from P 0 . The causal entropy of a policy π is defined asH(π) ≜ E π S,A [- ∞ t=0 γ t log π(A t |S t )].Since the expert demonstrates {(S E t , A E t )} t≥0 sequentially, we have a sequence of loss functions {L t (θ; (S E t , A E t ))} t≥0 . We use this sequence of loss functions (1) to formulate an online learning problem. A typical online learning problem is to minimize the regret:T -1 t=0 L t (θ t ; (S E t , A E t )) - min θ T -1 t=0 L t (θ; (S E t , A E t )). However, it is too challenging to minimize the regret in our case because the loss function L t could be non-convex. Therefore, we aim to minimize the local regret which is widely adopted in online non-convex optimization [25, 26] and online IRL [11] . The local regret quantifies the general stationarity of a sequence of loss functions under the learned parameters. In specific, given a sequence of loss functions {f t (x)} t≥0 , the local regret [11, 25, 26] at time t is defined as || 1 t+1 t i=0 ∇f i (x t )|| 2 which quantifies the gradient norms of the average of all the previous loss functions under the current learned parameter x t . The total local regret is defined as the sum of the local regret at each time t, i.e., T -1 t=0 || 1 t+1 t i=0 ∇f i (x t )|| 2 . In our case, we replace {f t } t≥0 with the loss function {L t } t≥0 defined in (1) and thus formulate the local regret (2)- (3) which has a bi-level formulation. We aim to minimize the following local regret:EQUATIONEQUATIONwhere(S E t , A E t ) ∼ P π E t (•, •) means that (S E t , A E t ) is drawn from the state-action distribution P π E t (•,•), and P π t (•, •) is the state-action distribution induced by π at time t in the MDP. Difficulties of solving problem (2)- (3) . We want to design a fast algorithm to solve problem (2)-(3) since we need to finish the update of θ and π before the next state-action pair is observed and the time between two consecutive state-action pairs can be short. However, designing and analyzing such a fast algorithm is difficult due to the following challenges:(i) First and foremost, current state-of-the-arts [25, 26] on online non-convex optimization use followthe-leader-based algorithms which solve min θ t i=0 L i (θ; (S E i , A E i )) to near stationarity at each time t. This is time-consuming because they require multiple gradient descent updates of θ. One way to alleviate this problem is to use online gradient descent (OGD) which only updates θ by one gradient descent step at each time t. However, since OGD does not solve the problem to near stationarity at any time t, it is extremely difficult to quantify the overall stationarity after T iterations. While OGD has been well studied in online convex optimization, it is rarely studied in online non-convex optimization. The recent work [11] uses OGD to quantify the local regret, however, its analysis can only hold when the input data is i.i.d. In contrast, the input data in our problem is not i.i.d. In specific, the input data at time t (i.e., (S E t , A E t )) is actually affected by the input data at last step (i.e.,(S E t-1 , A E t-1 )). This correlation between any two consecutive input data makes it difficult to analyze the growth rate of the local regret.(ii) Second, it is time-consuming if we fully solve the lower-level problem (3) to get π θ because this requires multiple policy updates to solve an RL problem. Therefore, we use a "single-loop" method which only requires one-step policy update for a given r θ . However, since the policy is only updated once, the updated policy can be far from π θ and thus making the analysis difficult. Single-loop methods are widely adopted to solve hierarchical problems, including bi-level optimization [27, 28] , game theory [29, 30] , min-max problems [31, 32] , etc. Recently, single-loop methods are applied to IRL [5] , however, the paper [5] only solves an offline optimization problem and its analysis does not hold for non i.i.d. input data and continuous state-action space. We include a section in Appendix A.1 to discuss our distinctions from [5] .• The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
algorithm and theoretical analysis: 
 This section has three parts. The first part presents a novel online learning algorithm that solves the problem (2)-( 3) and tackles the aforementioned two difficulties. The second part proves that Algorithm 1 achieves sub-linear local regret. If the reward function is linear, we prove that Algorithm 1 achieves sub-linear regret. The third part introduces a meta-learning method to get the meta-prior θ.In practice, the expert will demonstrate a specific trajectorys E 0 , a E 0 , s E 1 , a E 1 , • • • .For distinction, we use the capital letters (e.g., S) to represent random variables and the lower-case letters (e.g., s) to represent specific values. To design a fast algorithm, we propose an online-gradient-descent-based single-loop algorithm. In specific, at each time t, the algorithm updates both policy π and reward parameter θ only once. The policy update is to solve the lower-level problem (3) and the reward update is to solve the upper-level problem (2). In the following, we elaborate the procedure of policy update and reward update. Roll out policy π t+1 twice: one starting froms E 0 to get s E 0 , a ′ 0 , s ′ 1 , a ′ 1 , • • • , and the other starting from (s E t , a E t ) to get s ′′ t+1 , a ′′ t+1 , • • • 6: Compute g t = ∞ i=0 γ i ∇ θ r θt (s ′ i , a ′ i ) - ∞ i=0 γ i ∇ θ r θt (s ′′ i , a ′′ i ) + λ(1-γ t+1 ) 1-γ (θ t -θ) where s ′ 0 = s E 0 and (s ′′ i , a ′′ i ) = (s E i , a E i ) for 0 ≤ i ≤ t 7:Update θ t+1 = θ t -α t g t 8: end for Policy update (lines 3-4 of Algorithm 1). At each time t, we only partially solve the lower-level problem (3) via one-step soft policy iteration [5, 33] . In specific, the soft policy iteration contains two steps: policy evaluation and policy improvement. Policy evaluation aims to compute the soft Q-function Q soft θt,πt (see the expression in Appendix B.1) under the current learned reward function r θt and learned policy π t . Policy improvement aims to update policy according to π t+1 (s, a) ∝ exp(Q soft θt,πt (s, a)) for any (s, a) ∈ S × A. In practical implementations, π t+1 can be obtained by one-step policy update in soft Q-learning [33] or one-step actor update in soft actor-critic [34] .Reward update (lines 5-7 of Algorithm 1). At each time t, the algorithm observes (s E t , a E t ) and aims to leverage all the previously observed data to update the reward parameter. In specific, as L t (θ; (s E t , a E t )) = -γ t log π θ (a E t |s E t )+ λγ t 2 ||θ -θ|| 2EQUATIONNote that the gradient (4) holds for continuous state-action space. Since the gradient (4) has expectation terms under the policy π θ , we can only approximate it. In specific, we roll out the policy π t+1 twice: one starting from s E 0 to get a trajectory {(s ′ i , a ′ i )} i≥0 where s ′ 0 = s E 0 , and the other one starting from(s E t , a E t ) to get a trajectory {(s ′′ i , a ′′ i )} i≥0 where (s ′′ i , a ′′ i ) = (s E i , a E i ) for 0 ≤ i ≤ t. Then we use the empirical estimate g t = ∞ i=0 γ i ∇ θ r θt (s ′ i , a ′ i ) - ∞ i=0 γ i ∇ θ r θt (s ′′ i , a ′′ i ) + λ(1-γ t+1 ) 1-γ (θ t -θ) to approximate ∇ t i=0 L i (θ t ; (s E i , a E i )).With the gradient approximation g t , we utilize stochastic online gradient descent θ t+1 = θ t -α t g t to update the reward parameter.Discussion on our special design of the reward update. The right subfigure in Figure 1 visualizes our reward update (modulo the meta-regularization term). The green trajectory (i.e., {(s E t , a E t )} t≥0 ) is the expert trajectory, and the red trajectories (i.e., {(s ′ t , a ′ t )} t≥0 and {(s ′′ i , a ′′ i )} i>t ) are the trajectories generated by the learned policy. Given the expert trajectory prefix (i.e., the incomplete trajectory {(s E i , a E i )} t i=0 observed so far), our method completes the expert trajectory by rolling out the learned policy starting from (s E t , a E t ) and filling the trajectory suffix {(s ′′ i , a ′′ i )} i>t . The combined complete trajectory includes the expert trajectory prefix {(s E i , a E i )} t i=0 and the learner-filled trajectory suffix {(s ′′ i , a ′′ i )} i≥t . We update the reward function by comparing this combined trajectory to a complete trajectory {(s ′ t , a ′ i )} t≥0 generated by the learned policy starting from the expert's initial state s E 0 . A more straightforward way for the reward update is to directly compare the trajectory prefixes (visualized in the middle of Figure 1 ) at each time t. However, this naive method can be problematic. We explain the issue of this naive method and the advantage of our method in the following context. Figure 1 visualizes the reward update for standard IRL (left), the naive method (i.e., directly run standard IRL algorithms on the expert trajectory prefix) (middle), and our method (right). The standard IRL (left) updates the reward function by comparing the complete expert trajectory and the complete trajectory generated by the learned policy. This case is ideal, however, it is infeasible when the trajectory is ongoing and we can only observe an incomplete expert trajectory {(s E i , a E i )} t i=0 at each time t. The naive method (middle) updates the reward function by simply comparing the expert trajectory prefix{(s E i , a E i )} t i=0and the incomplete trajectory {(s ′ i , a ′ i )} t i=0 with the same length generated by the learned policy starting from the expert's initial state s E 0 . This kind of reward update is myopic as it does not consider for the future. Since it runs standard IRL on the trajectory prefix observed so far, it will always regard the current state-action pair as the terminal state-action pair and thus has no ability to consider the state-action pairs in the future. In contrast, our special design gives the algorithm the ability to consider for the future. Instead of only comparing incomplete trajectory prefixes, our method compares complete trajectories just as the standard IRL. In specific, we compare the combined complete trajectory {{(s E i , a E i )} t i=0 , {(s ′′ i , a ′′ i )} i>t } and the complete trajectory {(s ′ i , a ′ i )} i≥0 solely generated by the learned policy. The comparison between the learner prefix {s ′ i , a ′ i } t i=0 and expert prefix {s E i , a E i } t i=0 encourages the learned reward function to explain the expert's demonstrated behaviors so far, and the comparison between the suffixes ({s ′ i , a ′ i } i>t and {s ′′ i , a ′′ i } i>t ) encourages that we are learning a reward function that is useful for predicting the future. Note that as t increases, the expert trajectory prefix weights more and more in the combined complete trajectory, and eventually we will recover the standard IRL reward update when t goes to infinity. In Theorems 1 and 2, we theoretically guarantee that the proposed reward update can achieve sub-linear (local) regret. This shows the perfect consistency between the intuition and theory.To quantify the local regret of Algorithm 1, we have two challenges: (i) Since we only update π by one step at each time t, we have π t+1 instead of the optimal solution π θt of the lower-level problem (3) . The policy π t+1 can be far away from π θt and thus the empirical gradient estimate g t can be a bad approximation of the gradient (4). (ii) Since we only update θ once at each time t instead of finding a near-stationary point θ ′ such that || [25, 26] , the gradient normt i=0 L i (θ ′ ; (s E i , a E i ))|| ≤ ϵ as in|| t i=0 ∇L i (θ t ; (s E i , a E i ))|| is not stabilized under the threshold ϵ at every time t. Therefore the local regret (i.e.,T -1 t=0 || 1 t+1 t i=0 ∇L i (θ t ; (s E i , a E i ))|| 2) is hard to quantify and may not be sub-linear in T . What's worse, the input data is not i.i.d. but correlated, i.e., the input data (s E t , a E t ) at time t is affected by the input data (s E t-1 , a E t-1 ) at last step. This correlation makes it even more difficult to quantify the local regret.To solve the first challenge, we adopt the idea of two-timescale stochastic approximation [27] where the lower level updates in a faster timescale and the upper level updates in a slower timescale. The policy update is faster because it converges linearly under a fixed reward function [35] while the reward update is slower given that we choose α t ∝ (t + 1) -1/2 . Intuitively, since the policy update is faster than the reward update, the reward parameter is "relatively fixed" compared to the policy. It is expected that π t+1 shall stay close to π θt and at last converges to π θt when t increases.To solve the second challenge, we divide our analysis into two steps: (i) We quantify the difference of the gradient norms between the current correlated state-action distribution P π E t (•, •) and a stationary state-action distribution for any loss function L i , i ≥ 0. Note that P π E t+1 (•, •) is affected by P π E t (•, •). (ii) We quantify the local regret under the stationary distribution. The benefit of doing so is that the input data is i.i.d. under the stationary distribution, and thus we can cast the online gradient descent method as a stochastic gradient descent method and quantify its local regret. Finally, we can quantify the local regret under the current correlated distribution P π E t (•, •) by combining (i) and (ii). We start our analysis with the definitions of stationary state distribution and stationary state-action distribution. For a given policy π, the corresponding stationary state distribution is µ π (s) ≜ (1γ) ∞ t=0 γ t P π t (s) and the stationary state-action distribution is µ π (s, a) ≜ (1 -γ) There exist constants C M > 0 and ρ ∈ (0, 1) such that for any policy π and any t ≥ 0, the following holds for the Markov chain induced by the policy π and the state transition function P :sup S0∼P0 d TV (P π t (•), µ π (•)) ≤ C M ρ t where d TV (P 1 (•), P 2 (•)) ≜ 1 2 s∈S |P 1 (s) -P 2 (s)|ds is the total variation distance between the two state distributions P 1 and P 2 , S 0 is the initial state, and P π t (•) is the state distribution induced by the policy π at time t. Assumptions 1-2 are common in RL [36, 37, 38, 39] . Assumption 2 holds for any time-homogeneous Markov chain with finite state space or any uniformly ergodic Markov chain with general state space. Proposition 1. Suppose Assumptions 1-2 hold and α t ∈ (0, 1-γ λ ), we have the following relation for any i ≥ 0 and any θ t , t ≥ 0:E (S E i ,A E i )∼P π E i (•,•) ||∇L i (θ t ; (S E i , A E i ))|| 2 -E (S E i ,A E i )∼µ π E (•,•) ||∇L i (θ t ; (S E i , A E i ))|| 2 , ≤ 8C M C2 r 2 -γ 1 -γ 2 ρ i γ 2i ,where(S E i , A E i ) ∼ P π E i (•, •) means that (S E i , A E i ) is drawn from the correlated distribution P π E i (•, •) and (S E i , A E i ) ∼ µ π E (•, •) means that (S E i , A E i ) is drawn from the stationary distribution µ π E (•, •).Proposition 1 quantifies the gap of gradient norms between the current correlated distribution P π E i and the stationary distribution µ π E . We next quantify the local regret under the stationary distribution µ π E with the following lemma:Lemma 2. Suppose Assumptions 1-2 hold and chooseα t = (1-γ)(t+1) -1/2 λ, it holds that:E {(S E t ,A E t )∼µ π E (•,•)} t≥0 T -1 t=0 || 1 t + 1 t i=0 ∇L i (θ t ; (S E i , A E i ))|| 2 ≤ D 1 (log T + 1) + D 2 √ T + D 3 √ T (log T + 1),where D 1 , D 2 , and D 3 are positive constants whose expressions can be found in Appendix B.4.Lemma 2 quantifies the local regret under the stationary distribution µ π E . With Proposition 1 and Lemma 2, we can quantify the local regret under the current correlated distribution.Theorem 1. Suppose Assumptions 1-2 hold and chooseα t = (1-γ)(t+1) -1/2 λ, we have that: E {(S E t ,A E t )∼P π E t (•,•)} t≥0 T -1 t=0 || 1 t + 1 t i=0 ∇L i (θ t ; (S E i , A E i ))|| 2 ≤ D 1 + 8C M C2 r (2 -γ) 2 (1 -ργ 2 )(1 -γ) 2 (log T + 1) + D 2 √ T + D 3 √ T (log T + 1).E {(S E t ,A E t )∼P π E t (•,•)} t≥0 T -1 t=0 L t (θ t ; (S E t , A E t )) -min θ E {(S E t ,A E t )∼P π E t (•,•)} t≥0 T -1 t=0 L t (θ; (S E t , A E t )) ≤ D 4 + D 5 (log T + 1),where D 4 and D 5 are positive constants whose expressions are in Appendix B.6.Since there is only one training trajectory and this trajectory is not complete during the learning process, we need to add a regularization term to avoid overfitting. Inspired by humans' using relevant experience to help do inference, we introduce the meta-regularization λ 2 ||θ -θ|| 2 where λ is the hyper-parameter and the meta-prior θ is learned from "relevant experience". In specific, we introduce a set of relevant tasks {T j } j∼P T where each task T j is an IRL problem and P T is the implicit task distribution. The tasks {T j } j∼P T are relevant in the sense that they share the components (S, A, γ, P 0 , P ) of the MDP with our in-trajectory learning problem. However, the expert's reward functions of different tasks are different and are drawn from an unknown reward function distribution. For example, in the stock market case mentioned in the introduction, the experts of different tasks invest in the same stock market but may have different preferences. As standard in meta-learning [40, 41, 42] , we assume that the expert's reward function r E of our in-trajectory learning problem is also drawn from the same unknown reward function distribution. Note that the reward functions of the relevant tasks {T j } j∼P T are different from r E even if they are drawn from the same unknown reward function distribution.For each task T j , there is a batch of trajectories and we divide this batch into two sets, i.e., D tr j and D eval j . The training set D tr j only has one trajectory, just as our in-trajectory learning problem, and the evaluation set D eval j has abundant trajectories. Define the loss function on a certain data setD ≜ {ζ v } m v=1 as L(θ, D) ≜ - m v=1 ∞ t=0 γ t log π θ (a v t |s v t ).The goal of each task T j is to learn a task-specific adaptation ϕ j using the training set D tr j , such that ϕ j can minimize the test loss L(ϕ j , D eval j ) on the evaluation set D eval j . The goal of meta-regularization is to find a meta-prior θ, from which such task-specific adaptations ϕ j can be adapted to all tasks {T j } j∼P T . In specific, meta-regularization [24] proposes a bi-level optimization problem (5) . The lower-level problem uses only one trajectory D tr j to find the task-specific adaptation ϕ j such that the meta-regularized loss function L(ϕ, D tr j ) + λ 2(1-γ) ||ϕ -θ|| 2 is minimized. The upper-level problem is to find a meta-prior θ such that the corresponding task-specific adaptations {ϕ j } j∼P T can minimize the expected loss function L(ϕ j , D eval j ) over the evaluation sets of all tasks {T i } j∼P T .EQUATION)The lower-level loss function in (5) is the offline version of our in-trajectory loss function (1) (i.e., L(ϕ,D tr j ) + λ 2(1-γ) ||ϕ -θ|| 2 = ∞ t=0 L t (ϕ; (s tr t , a tr t )))where (s tr t , a tr t ) ∈ D tr j . Our in-trajectory learning problem can also be regarded as to find a task-specific adaptation. Note that the in-trajectory learning problem is online while the lower-level problem in ( 5) is offline because the in-trajectory problem is ongoing where we keep observing new state-action pairs. In contrast, the lower-level problem in ( 5) is based on "experience" that has already happened. Due to the space limit, we include the algorithm and theoretical guarantees of solving the problem (5) in Appendix C. 
experiments: 
 We present three experiments to show the effectiveness of MERIT-IRL. We use four baselines for comparisons. (i) IT-IRL: this method is MERIT-IRL without meta-regularization. (ii) Naive MERIT-IRL: this method has the meta-regularization term but uses the naive way (in the middle of Figure 1 ) to update reward. (iii) Naive IT-IRL: this method uses the naive way to update the learned reward and does not have the meta-regularization term. (iv) Hindsight: this method is meta-regularized ML-IRL [5] which can access the complete expert trajectory and uses the standard IRL (visualized in the left of Figure 1 ) with meta-regularization to update the learned reward. The experiment details are in Appendix D.In this subsection, we consider the target velocity problem for three MuJoCo robots: HalfCheetah, Walker, and Hopper. The target velocity problem is widely used in meta-RL [43] and meta-IRL [44] . In specific, the robots aim to maintain a target velocity in each task and the target velocity of different tasks is different. To test the performance of MERIT-IRL, we use 10 test tasks whose target velocity is randomly between 1.5 and 2.0. In the test tasks, there is only one expert trajectory and the state-action pairs of this trajectory are sequentially revealed (to MERIT-IRL, IT-IRL, Naive MERIT-IRL, and Naive IT-IRL) in an online fashion. The baseline Hindsight uses the complete expert trajectory to learn a reward function. The ground truth reward is designed as -|v -v target | (as in [43] ) where v is the current robot velocity and v target is the target velocity. To learn the meta-prior θ, we use 50 relevant tasks whose target velocity is randomly between 0 and 3. 2c show the in-trajectory learning performance where the x-axis is the time step t of the expert trajectory and the y-axis is the cumulative reward of the learned policy π t when only the first t steps of the expert trajectory are observed. The x-limit is 1, 000 because the trajectory length in MuJoCo is 1, 000. Note that the baseline "Hindsight" is not in-trajectory learning since it learns from a complete expert trajectory. For comparison, we use two horizontal lines (close to each other) to show the performance of Hindsight and the expert in the figures. Figure 2a shows that MERIT-IRL achieves similar performance with the expert when only 40% of the complete expert trajectory (t = 400) is observed while IT-IRL can only achieve performance close to the expert after observing more than 90% of the complete expert trajectory (t = 900). This shows the effectiveness of the meta-regularization. Naive MERIT-IRL and Naive IT-IRL fail to imitate the expert even if the complete expert trajectory is observed (t = 1, 000). This shows the effectiveness of our special design of the reward update. The discussions on Figures 2b and 2c are in Appendix D.2.Table 1 shows the results after observing the complete expert trajectory. MERIT-IRL performs much better than IT-IRL, Naive MERIT-IRL, and Naive IT-IRL. MERIT-IRL achieves similar performance with Hindsight and expert. Note that it is not expected that MERIT-IRL outperforms Hindsight since Hindsight uses the complete expert trajectory to learn.RL to train a stock trading agent has been widely studied in AI for finance [45, 46, 47] . In this experiment, we use IRL to learn the reward function (i.e., investing preference) of the target investor in a stock market scenario. In specific, we use the real-world data of 30 constituent stocks in Dow Jones Industrial Average from 2021-01-01 to 2022-01-01. We use a benchmark called "FinRL" [47] to configure the real-world stock data into an MDP environment. The target investor (i.e., expert) has an initial asset of $1, 000 and trades stocks on every stock market opening day. The stock market opens 252 days between 2021-01-01 and 2022-01-01, and thus the trajectory length is 252. The reward function of the target investor is defined as p 1 -p 2 where p 1 is the investor's profit which is the money earned from trading stocks subtracting the transaction cost, and p 2 models the investor's preference of whether willing to take risks. In specific, p 2 is positive if the investor buys stocks whose turbulence indices are larger than a certain turbulence threshold, and zero otherwise. The value of p 2 depends on the type and amount of the trading stocks. The turbulence thresholds of different investors are different. The turbulence index measures the price fluctuation of a stock. If the turbulence index is high, the corresponding stock has a high fluctuating price and thus is risky to buy [47] . Therefore, an investor unwilling to take risks has a relatively low turbulence threshold. We include experiment details in Appendix D.3. To test performance, we use 10 test tasks whose turbulence thresholds are randomly between 45 and 50. To learn θ, we use 50 relevant tasks whose turbulence thresholds are randomly between 30 and 60.Figure 2d shows that MERIT-IRL achieves similar cumulative reward with the expert at t = 140 which is less than 60% of the whole trajectory, while the three in-trajectory baselines fail to imitate the expert before the ongoing trajectory terminates. The last row in Table 1 shows that MERIT-IRL achieves similar performance with Hindsight and the expert. More discussions on the results are in Appendix D.3.This part presents the experiment of learning from an ongoing shooter trajectory. Following [12] , we model the shooter's movement as a navigation problem. We build a simulator in Gazebo (Figure 3a ) where the shooter moves from the door (lower left corner) to the red target (upper right corner).The learner observes the ongoing trajectory of the shooter and keeps updating the learned reward and policy. In our case, the complete shooter trajectory has the length of 140. Figures 3b-3g show our in-trajectory learning performance where the heat maps visualize the learned reward. We normalize the learned reward to [0, 1]. We can observe that as the ongoing trajectory is expanding, the learned reward function becomes more and more precise to locate the goal area. When t = 40, we cannot tell the goal area from the heat map (Figure 3b ). However, as the time t grows, we can almost locate the goal area when t = 60 (Figure 3c ) and precisely locate the goal area when t = 80 (Figure 3d ). Figure 3h shows the policy learning performance. Since there is no ground truth reward in this problem, we use "success rate" to quantify the performance of the learned policy. The success rate is the rate that the learned policy successfully reaches the goal. From 3h, we can see that MERIT-IRL outperforms the other baselines and can achieve 100% success rate when t = 80 (i.e., only observing 57% of the complete trajectory). Note that we do not include Hindsight and Expert in Figure 3 since they both achieve 100% success rate. 
conclusion: 
 This paper proposes MERIT-IRL, the first in-trajectory inverse reinforcement learning theoretical framework that learns a reward function while observing an initial portion of a trajectory and keeps updating the learned reward function when extended portions (i.e., new state-action pairs) of the trajectory are observed. Experiments show that MERIT-IRL can imitate the expert from the ongoing expert trajectory before it terminates.This appendix consists of four parts: related works, proof, meta-regularization algorithm and convergence guarantee, and Experiment details. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [Yes]Justification: We include the type of operating system, CPU, and RAM used in the first paragraph in Appendix D.Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute. • The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?Answer: [Yes] Justification: This paper follows NeurIPS Code of Ethnics.Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [Yes] Justification: We discuss the potential negative societal impact in Appendix E.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: This paper poses no such risks because we do not have data nor model to release.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [Yes] Justification: We use the SAC code from a Github repository, and we clearly state it at the top of that code script.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. 
new assets: 
 Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?Answer: [Yes] Justification: The submitted code can be considered as an asset, and we provide a file along with the code to document the code.Guidelines:• The answer NA means that the paper does not release new assets.• Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was obtained from people whose asset is used. • At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file. 
crowdsourcing and research with human subjects: 
 Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?Answer: [NA]Justification: The paper does not involve crowdsourcing nor research with human subjects.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper. • According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector. 
institutional review board (irb) approvals or equivalent for research with human subjects: 
 Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?Answer: [NA]Justification: The paper does not involve crowdsourcing nor research with human subjects.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.• Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review. 
 
 Appendix: Applying IRL to predict from ongoing trajectories. Papers [48, 49, 50] use standard IRL to predict goals of incomplete (or ongoing) trajectories. In specific, they first learn the reward function corresponding to each potential goal candidate from complete trajectories in the training phase and then use Bayesian methods to pick the most likely goal candidate of incomplete trajectories in the testing phase. However, these works are not in-trajectory learning since they do not learn a reward function from an incomplete ongoing trajectory.Online non-convex optimization. This paper casts the in-trajectory learning problem as an online non-convex bi-level optimization problem where at each online iteration, a new state-action pair is input. Current literature on online non-convex optimization has two major categories. The first one is to use the regret originally defined in online convex optimization [51, 52] . However, it assumes to find a global optimal solution of a non-convex optimization problem at each online iteration. Therefore, the second category studies "local regret" [25, 26] and uses follow-the-leader-based methods to minimize the local regret. However, the follow-the-leader-based methods need to solve a non-convex optimization problem to obtain a near-stationary point at each online iteration, which can be computationally expensive and time-consuming. If the streaming data arrives at a fast speed, the computation at each online iteration may not be finished before the next data arrives. The computational burden of each online iteration can be mitigated by online gradient descent (OGD) methods where we only partially solve the non-convex optimization problem by one-step gradient descent at each online iteration. While OGD is widely studied in online convex optimization, it is rarely studied in online non-convex optimization. [11] uses OGD to quantify the local regret, however, its analysis only holds when the input data is identically independent distributed (i.i.d.). In contrast, the input data in our problem is not i.i.d. In specific, the input data at time t (i.e., (S E t , A E t )) is affected by the input data at last step (i.e., (S E t-1 , A E t-1 )). This temporal correlation between any two consecutive input data makes it difficult to analyze the growth rate of the local regret.Regularization and meta-learning in IRL. Moreover, the data of in-trajectory learning is extremely lacking since there is only one demonstrated trajectory and this trajectory is not complete during the learning process. The lack of data can easily lead to overfitting and a common way to alleviate this problem is to use regularizers [21, 53] . Inspired by humans' using relevant experience to help the inference, we introduce a novel regularization method called meta-regularization [24, 54] . Compared to the regularizers commonly used in IRL [21, 53] , the meta-regularizer provides humanexperience-like prior information which helps recover the reward function from few data. Similar to the meta-initialization method [54, 43] commonly used in IRL [55] , meta-regularization provides an initialization that the algorithm starts at. However, more importantly, meta-regularization also provides a regularization term to avoid overfitting.A.1 Distinction from Maximum-likelihood inverse reinforcement learning (ML-IRL) [5] We discuss our distinctions from ML-IRL from the following three aspects: problem setting, algorithm design, and theoretical analysis.Distinction in problem setting. We study in-trajectory IRL and formulate an online optimization problem, while ML-IRL studies standard IRL and formulates an offline optimization problem.Distinctions in algorithm design. ML-IRL and our algorithm both update policy and reward in a single loop. However, we propose a novel reward update mechanism specially designed for the in-trajectory learning case. This special design requires to use the current learned policy to complete the expert trajectory, which gives the algorithm the ability to consider for the future. This special design of reward update is novel compared to ML-IRL.Distinctions in theoretical analysis. The analysis in our paper is substantially different from that in ML-IRL due to three facts: (1) The input data in our paper is not i.i.d., while the input data in ML-IRL is i.i.d. (2) We solve an online optimization problem, while ML-IRL solves an offline optimization problem. (3) Our analysis holds for continuous state-action space, while the analysis of ML-IRL is limited to finite state-action space. We now discuss the distinctions in theoretical analysis caused by the three facts in detail.In our case, the input data is not i.i.d. but temporally correlated, i.e., the input data (s t , a t ) is affected by the input data (s t-1 , a t-1 ) at last time step. In contrast, the input data in ML-IRL is i.i.d. sampled from a pre-collected data set. To solve this non i.i.d. issue of the input data, we propose a novel theoretical technique that has three steps (detailed in Subsection 4.2). Step 1: We propose the stationary distribution µ π E and quantify the gradient norm difference between the real distribution P π E t and this stationary distribution µ π E in Proposition 1.Step 2: We quantify the local regret over the stationary distribution in Lemma 2. The benefit of doing this is that the input data can be regarded as i.i.d. sampled from this stationary distribution. Step 3: We combine step 1 and step 2, and quantify the (local) regret over the real distribution, where the data is not i.i.d., in Theorem 1 and Theorem 2. We can see that step 1 and step 3 are to solve the non i.i.d. issue of the input data, so that the corresponding theorem statements (Proposition 1, Theorem 1, and Theorem 2) are novel compared to ML-IRL because ML-IRL does not have this non i.i.d. issue. The only theorem statement relevant to ML-IRL is Lemma 2 in step 2 where we both analyze the algorithm over a stationary distribution, and the data is i.i.d. sampled from the stationary distribution.However, Lemma 2 in step 2 still has significant distinctions from ML-IRL because Lemma 2 quantifies the local regret in the context of online optimization, while ML-IRL quantifies convergence in the context of offline optimization. First, the objective function is dynamically changing in the online setting because the learner observes a new state-action pair at each online iteration, while the objective function is fixed in ML-IRL. Second, the local regret contains the term L t (θ t ; (s E t , a E t )), however, θ t is computed before the learner knows (s E t , a E t ). This makes it more difficult to quantify the local regret because the learner does not know L t when it computes θ t . These two difficulties do not appear in the offline optimization in ML-IRL. To solve these two issues, we need to additionally construct a new time-invariant function L in Appendix B.4 and quantify the convergence of the new function L. Then, in order to quantify the local regret of {L t } t≥0 , we need to quantify the difference between the real loss function {L t } t≥0 and the constructed loss function L.Moreover, our theoretical analysis holds for continuous state-action space while the theoretical analysis in ML-IRL is limited to finite state-action space. The extension to continuous state-action space brings new difficulties and requires significant novel analysis. In general, the difficulties stem from two aspects: (1) The constants in ML-IRL, e.g., the smoothness constant of the loss function L and the coefficient of convergence rate, include the term |S| × |A|. When the state-action space is continuous, those constants are not finite because |S| × |A| is now infinite. To address this issue, we propose new methods to bound those constants. For example, in order to show that the loss function L is smooth, rather than using ||∇L(θ 1 ) -∇L(θ 2 )|| to find the smoothness constant as in ML-IRL, we aim to show that ||∇ 2 L(θ)|| is upper bounded by a constant C L in Lemma A.2 and this constantC L does not rely on |S| × |A|. Given that ||∇ 2 L(θ)|| ≤ C L , the loss function L is C L -smooth. (2)Since the action space A is finite in ML-IRL, their proved properties of the Q-function Q soft (e.g., Lipschitz continuity, contraction property, monotonic improvement, and smoothness) can be easily extended to the value function V soft by summing over different actions a ∈ A. When the action space becomes continuous, summing over infinitely many different actions does not preserve those properties. Thus we have to propose new methods to prove those propoerties of the value function V soft . In specific, we prove the Lipschitz continuity, contraction property, monotonic improvement, and smoothness of the value function V soft in Claims 3-5 in Appendix B.4.This section provides the proof of all the proposition, lemmas, and theorems in the paper. To start with, we first introduce the expression of soft Q-function and soft Bellman policy.The soft Q-function and soft value function are:Q soft θ,π (s, a) ≜ r θ (s, a) + γ s ′ ∈S P (s ′ |s, a)V soft θ,π (s ′ )ds ′ , V soft θ,π (s) ≜ E π S,A ∞ t=0 γ t r θ (S t , A t ) -log π(A t |S t ) S 0 = s E 0 .The soft Bellman policy is as follows:π θ (a|s) = exp(Q soft θ (s, a)) exp(V soft θ (s)) , Q soft θ (s, a) = r θ (s, a) + γ s ′ ∈S P (s ′ |s, a)V soft θ (s ′ )ds ′ , V soft θ (s) = log a∈A exp(Q soft θ (s, a))da .It has been proved [33] that the soft Bellman policy π θ is the optimal solution of the lower-level problem (4). We defineJ θ (s) ≜ E π θ S,A [ ∞ t=0 γ t r θ (S t , A t )|S 0 = s]as the expected cumulative reward of policy π θ starting from state s andJ θ (s, a) ≜ E π θ S,A [ ∞ t=0 γ t r θ (S t , A t )|S 0 = s, A 0 = a]. Lemma 3. We have the gradient ∇ θ log π θ (a|s) = E π θ S,A [ ∞ t=0 γ t ∇ θ r θ (S t , A t )|S 0 = s, A 0 = a] -E π θ S,A [ ∞ t=0 γ t ∇ θ r θ (S t , A t )|S 0 = s]. Proof. Define Z θ (s, a) ≜ exp(Q soft θ (s, a)) and Z θ (s) ≜ exp(V soft θ (s)), therefore Z θ is smooth in θ given that it is a composition of logarithmic, exponential, and linear functions of r θ and r θ is smooth in θ (Assumption 1).∇ θ log Z θ (s) = a∈A ∇ θ Z θ (s, a)da Z θ (s) , = a∈A Z θ (s, a) Z θ (s) ∇ θ log Z θ (s, a)da, = a∈A π θ (a|s) ∇ θ r θ (s, a) + γ s ′ ∈S P (s ′ |s, a)∇ θ log Z θ (s ′ )ds ′ da, = a∈A π θ (a|s) ∇ θ r θ (s, a) + γ s ′ ∈S P (s ′ |s, a) a ′ ∈A ∇ θ r θ (s ′ , a ′ ) + γ s ′′ ∈S P (s ′′ |s ′ , a ′ )∇ θ log Z θ (s ′′ )ds ′′ da ′ ds ′ da.Keep the expansion, we can get∇ θ log Z θ (s) = E π θ S,A [ ∞ t=0 γ t ∇ θ r θ (S t , A t )|S 0 = s] and similarly we can get ∇ θ log Z θ (s, a) = E π θ S,A [ ∞ t=0 γ t ∇ θ r θ (S t , A t )|S 0 = s, A 0 = a]. Thus we have the gradient ∇ θ log π θ (a|s) = ∇ θ log Z θ (s, a) -∇ θ log Z θ (s). B.2 Proof of Lemma 1 Recall that t i=0 L i (θ; (s E i , a E i )) = - t i=0 γ i log π θ (a E i |s E i ).When the dynamics P is deterministic, we have that∇ t i=0 L i (θ; (s E i , a E i )) = - t i=0 γ i ∇ θ log π θ (a E i |s E i ), = - t i=0 γ i ∇ θ Q soft θ (s E i , a E i ) -∇ θ V soft θ (s E i ) , = - t i=0 γ i ∇ θ r θ (s E i , a E i ) + γ∇ θ V soft θ (s E i+1 ) -∇ θ V soft θ (s E i ) , = - t i=0 γ i ∇ θ r θ (s E i , a E i ) - t+1 i=1 γ i ∇ θ V soft θ (s E i ) + t i=0 γ i ∇ θ V soft θ (s E i ), = - t i=0 γ i ∇ θ r θ (s E i , a E i ) -γ t+1 ∇ θ V soft θ (s E t+1 ) + ∇ θ V soft θ (s E 0 ), (a) = - t i=0 γ i ∇ θ r θ (s E i , a E i ) -E π θ S,A ∞ i=t+1 γ i ∇ θ r θ (S i , A i )|S i = s E t+1 + E π θ S,A ∞ i=0 γ i ∇ θ r θ (S i , A i )|S 0 = s E 0 , = - t i=0 γ i ∇ θ r θ (s E i , a E i ) -E π θ S,A ∞ i=t+1 γ i ∇ θ r θ (S i , A i )|S t = s E t , A t = a E t + E π θ S,A ∞ i=0 γ i ∇ θ r θ (S i , A i )|S 0 = s E 0 ,where equality (a) follows from the proof of Lemma 3.When the dynamics P is stochastic, we can prove that the above gradient is an unbiased estimate of∇E {(S E i ,A E i )∼P π E i (•,•)(•,•)} i≥0 t i=0 L i (θ; (S E i , A E i )) : ∇E {(S E i ,A E i )∼P π E i (•,•)(•,•)} i≥0 t i=0 L i (θ; (S E i , A E i )) , = ∇E {(S E i ,A E i )∼P π E i (•,•)(•,•)} i≥0 - t i=0 γ i ∇ θ log π θ (A E i |S E i ) , = E {(S E i ,A E i )∼P π E i (•,•)(•,•)} i≥0 - t i=0 γ i [∇ θ r θ (S E i , A E i ) + γE Si+1∼P (•|S E i ,A E i ) [∇ θ V soft θ (S i+1 )] -∇ θ V soft θ (S E i )] , = E {(S E i ,A E i )∼P π E i (•,•)(•,•)} i≥0 - t i=0 γ i [∇ θ r θ (S E i , A E i ) + γ∇ θ V soft θ (S E i+1 ) -∇ θ V soft θ (S E i )] , = E {(S E i ,A E i )∼P π E i (•,•)(•,•)} i≥0 - t i=0 γ i ∇ θ r θ (S E i , A E i ) -γ t+1 ∇ θ V soft θ (S E t+1 ) + E π θ S,A ∞ i=0 γ i ∇ θ r θ (S i , A i )|S 0 = S E 0 , (b) = E {(S E i ,A E i )∼P π E i (•,•)(•,•)} i≥0 - t i=0 γ i ∇ θ r θ (S E i , A E i ) -E π θ S,A [ ∞ i=t+1 γ i ∇ θ r θ (S i , A i )|S t = S E t , A t = A E t ] + E π θ S,A [ ∞ i=0 γ i ∇ θ r θ (S i , A i )|S 0 = S E 0 ] ,where equality (b) follows from the fact thatE {(S E i ,A E i )∼P π E i (•,•)(•,•)} i≥0 E π θ S,A [ ∞ i=t+1 γ i ∇ θ r θ (S i , A i )|S t = S E t , A t = A E t ] , = E {(S E i ,A E i )∼P π E i (•,•)(•,•)} i≥0 E π θ S,A [ ∞ i=t+1 γ i ∇ θ r θ (S i , A i )|S t+1 = S E t+1 ] , because P π E t+1 (•) = P π E t (S E t , A E t )P (•|S E t , A E t ) and S E t+1 ∼ P (•|S E t , A E t). Since we quantify the local regret in expectation in Theorem 1, this unbiased estimate can be used when the dynamics is stochastic.From Assumption 2, we know that d TV (Pπ E t (•), µ π E (•)) = 1 2 s∈S |P π E t (s) -µ π E (s)|ds ≤ C M ρ twhere the initial state is s 0 . For any state-action pair (s, a) ∈ S × A, we know that P π E t (s, a) = P π E t (s)π E (a|s) and µ π E (s, a) = µ π E (s)π E (a|s). Therefore, we have that:d TV (P π E (•, •), µ π E (•, •)), = 1 2 s∈S a∈A |P π E t (s)π E (a|s) -µ π E (s)π E (a|s)|dsda, = 1 2 s∈S a∈A |P π E t (s) -µ π E (s)|π E (a|s)dsda, = 1 2 s∈S |P π E t (s) -µ π E (s)|ds, ≤ C M ρ t .Claim 1. The trajectory of θ t is bounded, i.e., ||θ t -θ|| ≤ 2 Cr λ for any t ≥ 0.Proof.EQUATION≤ (1 -EQUATION≤ (1 -α t λ(1 -γ t+1 ) 1 -γ )||θ t -θ|| + 2α t Cr 1 -γ , ≤ (1 - α t λ 1 -γ )||θ t -θ|| + 2α t Cr 1 -γ ,where (a) follows triangle inequality and (b) uses the upper bound of ∇ θ r θ in Assumption 1. Therefore, we have the following relation:||θ t+1 -θ|| - 2 Cr λ ≤ (1 - α t λ 1 -γ ) ||θ t -θ|| - 2 Cr λ , ⇒ ||θ t -θ|| ≤ (1 - α t λ 1 -γ ) t ||θ 0 -θ|| - 2 Cr λ + 2 Cr λ , (c) = 2 Cr λ 1 -(1 - α t λ 1 -γ ) t (d) ≤ 2 Cr λ ,where (c) follows the fact that θ 0 = θ and (d) follows the fact that α t ≤ 1-γ λ .Recall that the loss functionL i (θ; (s E i , a E i )) = -γ i log π θ (a E i |s E i ) + λγ i 2 ||θ -θ|| 2 and thus ∇L i (θ; (s E i , a E i )) = -γ i [∇ θ Q soft θ (s E i , a E i ) -∇ θ V soft θ (s E i )] + λγ i (θ -θ). From Lemma 3, we know that ∇ θ V soft θ (s E i ) = E π θ S,A [ ∞ t=0 γ t ∇ θ r θ (S t , A t )|S 0 = s E i ] and ∇ θ Q soft θ (s E i , a E i ) = E π θ S,A [ ∞ t=0 γ t ∇ θ r θ (S t , A t )|S 0 = s E i , A 0 = a E i ]. Then, ||∇ θ V soft θ (s E i )|| ≤ Cr 1-γ and ||∇ θ Q soft θ (s E i , a E i )|| ≤ Cr 1-γ . Now we can see that ||∇L i (θ t ; ; (s E i , a E i ))|| = γ i ||∇ θ Q soft θt (s E i , a E i ) -∇ θ V soft θt (s E i ) + λ(θ t -θ)||, ≤ γ i ||∇ θ Q soft θt (s E i , a E i ) -∇ θ V soft θt (s E i ) + λ(θ t -θ)|| ≤ γ i 2 Cr 1 -γ + 2 Cr , ⇒ ||∇L i (θ t ; (s E i , a E i ))|| 2 ≤ 4 C2 r γ 2i 2 -γ 1 -γ 2 .Therefore, we have thatE (S E i ,A E i )∼P π E i (•,•) ||∇L i (θ t ; (S E i , A E i ))|| 2 -E (S E i ,A E i )∼µ π E (•,•) ||∇L i (θ t ; (S E i , A E i ))|| 2 , = s∈S a∈A P π E i (s, a)||∇L i (θ t ; (s, a))|| 2 dads - s∈S a∈A µ π E (s, a)||∇L i (θ t ; (s, a))|| 2 dads , ≤ s∈S a∈A |P π E i (s, a) -µ π E (s, a)| • ||∇L i (θ t ; (s, a))|| 2 dads, ≤ 2C M ρ i • 4 C2 r γ 2i 2 -γ 1 -γ 2 = 8C M C2 r 2 -γ 1 -γ 2 ρ i γ 2i .Lemma 4. Suppose Assumptions 1-2 hold, the we have the following for any (s, a) ∈ S × A and any θ 1 , θ 2 , t: Lemma 3) . Therefore, we have that||∇L t (θ 1 , (s, a))-∇L t (θ 2 , (s, a))|| ≤ C L ||θ 1 -θ 2 || and |Q soft θ1,π θ 1 (s, a)-Q soft θ2,π θ 2 (s, a)| ≤ C Q ||θ 1 -θ 2 ||, where C L = 2 Cr 1-γ + 4 C3 r (1-γ) 4 + λ and C Q = Cr 1-γ . Proof. Note that Q soft θ,π θ = Q soft θ and ∇ θ Q soft θ (s, a) = E π θ S,A [ ∞ t=0 γ t ∇ θ r θ (S t , A t )|S 0 = s, A 0 = a] (proof of||∇ θ Q soft θ (s, a)|| ≤ Cr 1 -γ ≜ C Q We know from Lemma 1 that ∇L t (θ; (s E t , a E t )) = -γ t [∇ θ Q soft θ (s E t , a E t )-∇ θ V soft θ (s E t )]+λγ t (θ-θ). To find the smoothness constant of L t , we need to compute the Hessian of L t . First, we have that∇ 2 θθ Q soft θ (s, a) = ∇ θ E π θ S,A [ ∞ t=0 γ t ∇ θ r θ (S t , A t )|S 0 = s, A 0 = a], = ∇ 2 θθ r θ (s, a) + γ s ′ ∈S P (s ′ |s, a)∇ θ E π θ S,A [ ∞ t=0 γ t ∇ θ r θ (S t , A t )|S 0 = s ′ ]ds ′ , = ∇ 2 θθ r θ (s, a) + γ s ′ ∈S P (s ′ |s, a)∇ θ a ′ ∈A π θ (a ′ |s ′ )E π θ S,A [ ∞ t=0 γ t ∇ θ r θ (S t , A t )|S 0 = s ′ , A 0 = a ′ ]da ′ ds ′ , = ∇ 2 θθ r θ (s, a) + γ s ′ ∈S P (s ′ |s, a) a ′ ∈A ∇ θ π θ (a ′ |s ′ ) • E π θ S,A [ ∞ t=0 γ t ∇ θ r θ (S t , A t )|S 0 = s ′ , A 0 = a ′ ] + π θ (a ′ |s ′ ) • ∇ θ E π θ S,A [ ∞ t=0 γ t ∇ θ r θ (S t , A t )|S 0 = s ′ , A 0 = a ′ ] da ′ ds ′ .Keep the expansion, we can get∇ 2 θθ Q soft θ (s, a) = E π θ S,A [ ∞ t=0 γ t ∇ 2 θθ r θ (S t , A t )|S 0 = s 0 , A 0 = a 0 ] + E π θ S,A ∞ i=0 γ i ∇ θ π θ (A i |S i ) • E π θ S ′ ,A ′ [ ∞ t=0 γ t ∇ θ r θ (S ′ t , A ′ t )|S ′ 0 = S i , A ′ 0 = A i ] S 0 = s 0 , A 0 = a 0 .Now we take a look at the second term in the above equality:∇ θ π θ (a|s) • E π θ S,A [ ∞ t=0 γ t ∇ θ r θ (S t , A t )|S 0 = s, A 0 = a], = π θ (a|s)∇ θ log π θ (a|s) • E π θ S,A [ ∞ t=0 γ t ∇ θ r θ (S t , A t )|S 0 = s, A 0 = a], = π θ (a|s) ∇ θ Q soft θ (s, a) -∇ θ V soft θ (s) • E π θ S,A [ ∞ t=0 γ t ∇ θ r θ (S t , A t )|S 0 = s, A 0 = a], ⇒ ∇ θ π θ (a|s) • E π θ S,A [ ∞ t=0 γ t ∇ θ r θ (S t , A t )|S 0 = s, A 0 = a] , ≤ ( Cr 1 -γ + Cr 1 -γ ) • Cr 1 -γ = 2 C3 r (1 -γ) 3 .Therefore, we have that||∇ 2 θθ Q soft θ (s, a)|| ≤ E π θ S,A [ ∞ t=0 γ t ∇ 2 θθ r θ (S t , A t )|S 0 = s 0 , A 0 = a 0 ] + E π θ S ′ ,A ′ ∞ i=0 γ i ∇ θ π θ (A ′ i |S ′ i ) • E π θ S,A [ ∞ t=0 γ t ∇ θ r θ (S t , A t )|S 0 = S ′ i , A 0 = A ′ i ] , ≤ Cr 1 -γ + ∞ t=0 γ t 2 C3 r (1 -γ) 3 = Cr 1 -γ + 2 C3 r (1 -γ) 4 .Similarly, we can get||∇ 2 θθ V soft θ (s)|| ≤ Cr 1-γ + 2 C3 r (1-γ) 4. Therefore, we have thatEQUATIONThis proof is based on the proof in ML-IRL [5] . The differences are: (i) their proof only holds for finite state-action space while we extend to continuous state-action space; (ii) their analysis is for offline settings while we extend to online settings to quantify the local regret. We first introduce the following claims which serve as building blocks in this subsection.Claim 2. For any given policy π and state-action pair (s, a), it holds that |Q soft θ1,π (s, a) -Q soft θ2,π (s, a)| ≤ C Q ||θ 1 -θ 2 || and |V soft θ1,π (s) -V soft θ2,π (s)| ≤ C Q ||θ 1 -θ 2 ||.Proof.Q soft θ1,π (s, a) -Q soft θ2,π (s, a), = E π S,A ∞ t=0 γ t r θ1 (S t , A t ) -log π(A t |S t ) S 0 = s, A 0 = a -E π S,A ∞ t=0 γ t r θ2 (S t , A t ) -log π(A t |S t ) S 0 = s, A 0 = a , = E π S,A ∞ t=0 γ t [r θ1 (S t , A t ) -r θ2 (S t , A t )] S 0 = s, A 0 = a , ⇒ |Q θ1,π (s, a) -Q θ2,π (s, a)| ≤ ∞ t=0 γ t Cr ||θ 1 -θ 2 || = Cr 1 -γ ||θ 1 -θ 2 || = C Q ||θ 1 -θ 2 ||.Similarly, we can get that|V soft θ1,π (s) -V soft θ2,π (s)| ≤ E π S,A ∞ t=0 γ t [r θ1 (S t , A t ) -r θ2 (S t , A t )] S 0 = s , ≤ ∞ t=0 γ t Cr ||θ 1 -θ 2 || = Cr 1 -γ ||θ 1 -θ 2 || = C Q ||θ 1 -θ 2 ||.Claim 3. The soft Bellman operator T soft θ :(T soft θ Q)(s, a) ≜ r θ (s, a) + γ s ′ ∈S P (s ′ |s, a) log a ′ ∈A exp(Q(s ′ , a ′ ))da ′ ds ′ , (T soft θ V )(s) ≜ log a∈A exp r θ (s, a) + γ s ′ ∈S P (s ′ |s, a)V (s ′ )ds ′ da ,is a contraction map with constant γ.Proof. It has been proved that T soft θ Q is a contraction map with constant γ (Appendix A.2 in [33] ). Here we show that T soft θ V is a contraction map with constant γ. Define a norm of V as Similarly, we can get||V 1 -V 2 || = sup s∈S |V 1 (s) -V 2 (s)| and suppose ||V 1 -V 2 || = ϵ. Then we have that T soft θ V 1 (s) = log a∈A exp r θ (s, a) + γ s ′ ∈S P (s ′ |s, a)V 1 (s ′ )ds ′ da , ≤ log a∈A exp r θ (s, a) + γ s ′ ∈S P (s ′ |s, a)[V 2 (s ′ ) + ϵ]ds ′ da , = logEQUATION≥ r θt (s, a) + γs ′ ∈S P (s ′ |s, a)E A ′ ∼πt+1(•|s ′ ) [Q soft θt,πt (s ′ , A ′ ) -log π t+1 (A ′ |s ′ )]ds ′ , = r θt (s, a) + γ s ′ ∈S P (s ′ |s, a) log a ′ ∈A exp(Q soft θt,πt (s ′ , a ′ ))da ′ ds ′ , = T soft θ (Q soft θt,πt )(s, a),where (i) follow equations ( 2)-( 3) in [34] and (ii) follows policy improvement theorem (Theorem 4 in [33] ). Similarly, we can get thatV soft θt,πt+1 (s) = E A∼πt+1(•|s) [Q soft θt,πt+1 (s, A) -log π t+1 (A|s)], ≥ E A∼πt+1(•|s) [Q soft θt,πt (s, A) -log π t+1 (A|s)], = log a∈A exp(Q soft θt,πt (s, a))da , = log a∈A exp r θt (s, a) + γ s ′ ∈S P (s ′ |s, a)V soft θt,πt (s ′ )ds ′ da , = T soft θt (V soft θt,πt )(s).Claim 5. The following holds for any (s, a) ∈ S × A and θ 1 , θ 2 , t:|V soft θ1 (s, a) -V soft θ2 (s, a)| ≤ C Q ||θ 1 -θ 2 ||. Proof. Note that ∇ θ V soft θ (s) = E π θ S,A [ ∞ t=0 γ t ∇ θ r θ (S t , A t )|S 0 = s] (proof of Lemma 3), therefore ||∇ θ V soft θ (s)|| ≤ Cr 1 -γ = C Q .We first show the convergence of π t in Algorithm 1. For any (s, a) ∈ S × A, we know that| log π t+1 (a|s) -log π θt (a|s)| ≤ |Q soft θt,πt (s, a) -Q soft θt (s, a)| + |V soft θt,πt (s) -V soft θt (s)|.Now we take a look at the termEQUATIONEQUATIONEQUATIONEQUATIONwhere (a) follows Lemma 2 and Claim 2, (b) follows the fact that π θ is the optimal solution, (c) follows Claim 4, (d) follows the fact that Q soft θt-1 is a fixed point of T soft θt-1 (Theorem 2 in [33] ), and (e) follows Claim 3. EQUATIONEQUATIONwhere (h) follows claim 1. Recall that| log π t+1 (a|s) -log π θt (a|s)| ≤ |Q soft θt,πt (s, a) -Q soft θt (s, a)| + |V soft θt,πt (s) -V soft θt (s)|. Summing from i = 0 to t, we get t i=1 |Q soft θi,πi (s, a) -Q soft θi (s, a)| + |V soft θi,πi (s) -V soft θi (s)| , ≤ t i=1 4C Q ||θ i -θ i-1 || + γ |Q soft θi-1 (s, a) -Q soft θi-1,πi-1 (s, a)| + |V soft θi-1,πi-1 (s) -V soft θi-1 (s)| , ⇒ (1 -γ) t-1 i=0 |Q soft θi,πi (s, a) -Q soft θi (s, a)| + |V soft θi,πi (s) -V soft θi (s)| , (i) ≤ 16C Q Cr 1 -γ t i=1 α i-1 + |Q soft θ0 (s, a) -Q soft θ0,π0 (s, a)| + |V soft θ0,π0 (s) -V soft θ0 (s)| -|Q soft θt (s, a) -Q soft θt,πt (s, a)| -|V soft θt,πt (s) -V soft θt (s)| , ⇒ 1 t t-1 i=0 |Q soft θi,πi (s, a) -Q soft θi (s, a)| + |V soft θi,πi (s) -V soft θi (s)| ≤ 16C Q Cr t(1 -γ) 2 t i=1 α i-1 + 1 t(1 -γ) |Q soft θ0 (s, a) -Q soft θ0,π0 (s, a)| + |V soft θ0,π0 (s) -V soft θ0 (s)| -|Q soft θt (s, a) -Q soft θt,πt (s, a)| -|V soft θt,πt (s) -V soft θt (s)| , = D1 √ t + D2 t ,where (i) follows ( 8), D1 =16C Q Cr (1-γ) 2 , and D2 = 1 1-γ |Q soft θ0 (s, a) -Q soft θ0,π0 (s, a)| + |V soft θ0,π0 (s) - V soft θ0 (s)| -|Q soft θt (s, a) -Q soft θt,πt (s, a)| -|V soft θt,πt (s) -V soft θt (s)|. Therefore, we can see thatEQUATIONDefine the loss functionL(θ) ≜ E (S,A)∼µ π E (•,•) -log π θ (A|S) + λ 2 ||θ -θ|| 2 , then we can see that E (S E i ,A E i )∼µ π E (•,•) [L i (θ; (S E i , A E i ))] = γ i L(θ). Moreover, we have thatEQUATIONEQUATIONwhere (j) follows Lemma 3 and (k) follows Claim 1.Therefore, we have thatEQUATIONwhere (l ′ ) follows the fact that a bounded variable X ∈ [-a, a] has bounded variance at most a 2 . Now we take a look at the term g t -1-γ t+1 1-γ ∇ L(θ t ):E (S,A)∼µ π E (•,•) g t - 1 -γ t+1 1 -γ ∇ L(θ t ) , = E {(S E i ,A E i )∼µ π E (•,•)} i≥0 g t - t i=0 ∇L i (θ t ; (S E i , A E i )) + E {(S E i ,A E i )∼µ π E (•,•)} i≥0 t i=0 ∇L i (θ t ; (S E i , A E i )) - 1 -γ t+1 1 -γ ∇ L(θ t ) , = E {(S E i ,A E i )∼µ π E (•,•)} i≥0 g t - t i=0 ∇L i (θ t ; (S E i , A E i )) , = E {(S E i ,A E i )∼µ π E (•,•)} i≥0 ∞ i=0 γ i ∇ θ r θt (s ′ i , a ′ i ) -E π θ t S,A [ ∞ i=0 γ i ∇ θ r θt (S i , A i )|S 0 = S E 0 ] + E {(S E i ,A E i )∼µ π E (•,•)} i≥0 ∞ i=t+1 γ i ∇ θ r θt (s ′′ i , a ′′ i ) -E π θ t S,A [ ∞ i=t+1 γ i ∇ θ r θt (S i , A i )|S t = S E t , A t = A E t ] , = E {(S E i ,A E i )∼µ π E (•,•)} i≥0 E πt+1 S,A [ ∞ i=0 γ i ∇ θ r θt (S i , A i )|S 0 = S E 0 ] -E π θ t S,A [ ∞ i=0 γ i ∇ θ r θt (S i , A i )|S 0 = S E 0 ] + E πt+1 S,A [ ∞ i=t+1 γ i ∇ θ r θt (S i , A i )|S t = S E t , A t = A E t ] -E π θ t S,A [ ∞ i=t+1 γ i ∇ θ r θt (S i , A i )|S t = S E t , A t = A E t ] .From equation (64) in [5] , we know thatE πt+1 S,A [ ∞ i=0 γ i ∇ θ r θt (S i , A i )|S 0 = s 0 ] -E π θ t S,A [ ∞ i=0 γ i ∇ θ r θt (S i , A i )|S 0 = s 0 ] , ≤ 2 Cr 1 -γ s∈S a∈A |Q soft θt (s, a) -Q soft θt,πt (s, a)|dads, ≤ 2 Cr C d 1 -γ sup (s,a)∈S×A {|Q soft θt (s, a) -Q soft θt,πt (s, a)|},where C d is the product of the area of S and the area of A.Therefore, we can get thatEQUATIONFrom ( 7) and ( 8), we know thatEQUATION)and similarly we can see thatEQUATIONTelescoping from i = 0 to t -1, we getEQUATIONwhere (l) follows ( 12) and (m) follows (13) . Similarly, we can see thatEQUATIONNow, we start to quantify the local regret:L(θ i+1 ) ≥ L(θ i ) + [∇ L(θ i )] ⊤ (θ i+1 -θ i ) - C L 2 ||θ i+1 -θ i || 2 , (n) ≥ L(θ i ) + α t [∇ L(θ i )] ⊤ g i - 8α 2 i C2 r C L (1 -γ) 2 , = L(θ i ) + α i 1 -γ i+1 1 -γ ||∇ L(θ i )|| 2 + α i [∇ L(θ i )] ⊤ (g i - 1 -γ i+1 1 -γ ∇ L(θ i )) - 8α 2 i C2 r C L (1 -γ) 2 , ≥ L(θ i ) + α i 1 -γ i+1 1 -γ ||∇ L(θ i )|| 2 -α i ||∇ L(θ i )|| • ||g i - 1 -γ i+1 1 -γ ∇ L(θ i )|| - 8α 2 i C2 r C L (1 -γ) 2 , (o) ≥ L(θ i ) + α i 1 -γ i+1 1 -γ ||∇ L(θ i )|| 2 -α i 2 Cr (2 -γ) 1 -γ • ||g i - 1 -γ i+1 1 -γ ∇ L(θ i )|| - 8α 2 i C2 r C L (1 -γ) 2 , ⇒ E {(S E i ,A E i )∼µ π E (•,•)} i≥0 t-1 i=0 α i 1 -γ i+1 1 -γ ||∇ L(θ i )|| 2 , ≤ L(θ t ) -L(θ 0 ) + 2 Cr (2 -γ) 1 -γ t-1 i=0 α i E {(S E i ,A E i )∼µ π E (•,•)} i≥0 ||g i - 1 -γ i+1 1 -γ ∇ L(θ i )|| + t-1 i=0 8α 2 i C2 r C L (1 -γ) 2 , (p) ≤ L(θ t ) -L(θ 0 ) + 8 C2 r C d (2 -γ) (1 -γ) 3 E {(S E i ,A E i )∼µ π E (•,•)} i≥0 α 0 |Q soft θ0,π0 (S E 0 , A E 0 ) -Q soft θ0 (S E 0 , A E 0 )| -α t |Q soft θt,πt (S E t , A E t ) -Q soft θt (S E t , A E t )| + 32C Q C2 r C d (1 -γ) 3 + 8 C2 r C L (1 -γ) 2 t-1 i=0 α 2 i ,where (n) follows ( 8), (o) follows ( 10), (p) follows (15) . Therefore, we have thatEQUATION)EQUATION)whereD 2 = L(θ T ) -L(θ 0 ) + 8 C2 r C d (2-γ) (1-γ) 3 E {(S E i ,A E i )∼µ π E (•,•)} i≥0 α 0 |Q soft θ0,π0 (S E 0 , A E 0 ) - Q soft θ0 (S E 0 , A E 0 )|-α T |Q soft θ T ,π T (S E T , A E T )-Q soft θ T (S E T , A E T )| and D 3 = 2(1-γ) λ 32C Q C2 r C d (1-γ) 3 + 8 C2 r C L (1-γ) 2 .Then we can see thatE {(S E i ,A E i )∼µ π E (•,•)} i≥0 T -1 t=0 || 1 t + 1 t i=0 ∇L i (θ t ; (S E i , A E i ))|| 2 , ≤ 2E {(S E i ,A E i )∼µ π E (•,•)} i≥0 T -1 t=0 || 1 t + 1 t i=0 ∇L i (θ t ; (S E i , A E i )) -γ i ∇ L(θ t )|| 2 + 2E {(S E i ,A E i )∼µ π E (•,•)} i≥0 T -1 t=0 || 1 -γ t (t + 1)(1 -γ) ∇ L(θ t )|| 2 , ≤ 2E {(S E i ,A E i )∼µ π E (•,•)} i≥0 T -1 t=0 || 1 t + 1 t i=0 ∇L i (θ t ; (S E i , A E i )) -γ i ∇ L(θ t )|| 2 + 2E {(S E i ,A E i )∼µ π E (•,•)} i≥0 T -1 t=0 ||∇ L(θ t )|| 2 , (q) ≤ T -1 t=0 8 C2 r (2 -γ) 2 (t + 1)(1 -γ) 4 + 2E {(S E i ,A E i )∼µ π E (•,•)} i≥0 T -1 t=0 ||∇ L(θ t )|| 2 , ≤ D 1 (log T + 1) + D 2 √ T + D 3 √ T (log T + 1),whereD 1 = 8 C2 r (2-γ) 2(1-γ) 4 . The (q) follows (11) . Note that to achieve this local regret rate, we actually need to take an extra expectation over the dynamics P because we need to roll out π t to formulate g t . Here, we omit the expectation over the dynamics.We know thatEQUATIONwhere (a) follows ( 18) and (11) .Therefore,EQUATION≤ D 1 log T + D 2 √ T + D 3 log T √ T + T -1 t=0 1 t + 1 t i=0 8C M C2 r 2 -γ 1 -γ 2 ρ i γ 2i , ≤ D 1 log T + D 2 √ T + D 3 log T √ T + T -1 t=0 1 t + 1 • 8C M C2 r 2 -γ 1 -γ 2 1 1 -ργ 2 , ≤ D 1 + 8C M C2 r (2 -γ) 2 (1 -ργ 2 )(1 -γ) 2 log T + D 2 √ T + D 3 log T √ T ,where (s) follows ( 19) and Proposition 1. Note that to achieve this local regret rate, we actually need to take an extra expectation over the dynamics P because we need to roll out π t to formulate g t . Here, we omit the expectation over the dynamics.Suppose the expert reward function r E and the parameterized reward function r θ are both linear, i.e., r E = θ ⊤ E ϕ and r θ = θ ⊤ ϕ, where ϕ : S × A → R n + is an n-dimensional feature vector such that ||ϕ(s, a)|| ≤ Cr for any (s, a) ∈ S × A. The proof follows the similar idea with that of Theorem 1 where follow two-step process: step (i) quantifies the regret under the stationary distribution µ π E (•, •) and step (ii) quantifies the difference between the correlated distribution P π E t and the stationary distribution µ π E . We start our proof with the following claim: Claim 6. If the parameterized reward function r θ is linear, the function L(θ) is λ-strongly convex for any θ. ∇ L(θ; ( S, Ā)) = E π θ S,A ∞ i=0 γ i ϕ(S i , A i ) S 0 = S -E π θ S,A ∞ i=0 γ i ϕ(S i , A i ) S 0 = S, A 0 = Ā +λ(θ-θ).Therefore, we have that∇ 2 θθ L(θ; ( S, Ā)), = ∇ θ E π θ S,A ∞ i=0 γ i ϕ(S i , A i ) S 0 = S -∇ θ E π θ S,A ∞ i=0 γ i ϕ(S i , A i ) S 0 = S, A 0 = Ā + λ.Now, we take a look at∇ θ E π θ S,A ∞ i=0 γ i ϕ(S i , A i ) S 0 = S, A 0 = Ā = ∇ θ ϕ( S, Ā) + s1∈S P (s 1 | S, Ā) at+1∈A π θ (a 1 |s 1 )E π θ S,A ∞ i=1 γ i ϕ(S i , A i ) S 1 = s 1 , A 1 = a 1 da 1 ds 1 , = s1∈S P (s 1 | S, Ā) a1∈A ∇ θ π θ (a 1 |s 1 ) • E π θ S,A ∞ i=1 γ i ϕ(S i , A i ) S 1 = s 1 , A 1 = a 1 + π θ (a 1 |s 1 ) • ∇ θ E π θ S,A ∞ i=1 γ i ϕ(S i , A i ) S 1 = s 1 , A 1 = a 1 da 1 ds 1 .Keep the expansion, we can see that∇ θ E π θ S,A ∞ i=0 γ i ϕ(S i , A i ) S 0 = S, A 0 = Ā , = E π θ S,A ∞ i=1 ∇ θ π θ (A ′ i |S ′ i ) • E π θ S,A ∞ i=1 γ i ϕ(S i , A i ) S 1 = S ′ 1 , A 1 = A ′ 1 S ′ 0 = S, A ′ 0 = Ā , ∇ θ E π θ S,A ∞ i=0 γ i ϕ(S i , A i ) S 0 = S , = E π θ S,A ∞ i=0 ∇ θ π θ (A ′ i |S ′ i ) • E π θ S,A ∞ i=0 γ i ϕ(S i , A i ) S 0 = S ′ 0 , A 0 = A ′ 0 S ′ 0 = S ,Thus we have thatEQUATIONwhere (a) follows Lemma 3,X ≜ E π θ S,A [ ∞ i=0 γ i ϕ(S i , A i )|S 0 = S, A 0 = A] is a random vector, EX ≜ E π θ S,A [ ∞ i=0 γ i ϕ(S i , A i )|S 0 = S]is the expectation of X over the action distribution, and Cov(X) is the covariance matrix of the random vector X with itself, which is always positive definite because the policy π θ is always stochastic. Therefore, we can see that||∇ 2 θθ L(θ)|| = ||Cov(X) + λ|| (b) ≥ λ,where (b) follows (20) .Step (i). We first quantify the regret under the stationary distributionEQUATIONwhere (c) follows (8) Since L(θ) is λ-strongly convex, we have thatEQUATIONwhere (d) follows (21) , and (e) follows Claim 1 which shows that the trajectory of θ t is bounded and thus there is a positive constant Ĉ such that ||θ t -θ * || ≤ Ĉ.Telescoping ( 22) from t = 0 to t = T -1, we can see thatEQUATIONwhere (f ) follows ( 16), and D4 =1-γ-λα0 2α0 E (S E t ,A E t )∼µ π E (•,•) [||θ t -θ * || 2 ] - 1-γ 2α T -1 (1-γ T ) E (S E t ,A E t )∼µ π E (•,•) [||θ T -θ * || 2 ] + 4 CrCd Ĉ (1-γ) 2 [|Q soft θ0,π0 (S, A) -Q soft θ0 (S, A)| - |Q soft θ T ,π T (S, A) -Q soft θ T (S, A)|].Step (ii). We now quantify the difference between the stationary distribution µ π E (•, •) and the correlated distribution P π E t (•, •). Note that ||θ t || is bounded (proved in Claim 1), the soft Bellman policy π θ is continuous in θ and (s, a), and we assume that the state-action space is bounded, there is a positive constant C π such that || log π θt (a|s)|| ≤ C π for any (s, a) ∈ S × A. We start with the following relation:EQUATIONTherefore, we have thatEQUATION≤ C π C M 1 -γρ + D4 + 32C Q C d Ĉ C2 r λ(1 -γ) 3 (log T + 1) + C π C M 1 -γρ , = D 4 + D 5 (log T + 1),where (f ) follows ( 23) and ( 24), D 4 = 2CπC M 1-γρ + D4 , andD 5 = 32C Q C d Ĉ C2 r λ(1-γ) 3 .To solve problem (5), we use a double-loop method, i.e., we first solve the lower-level problem for K iterations to get an approximate ϕ j,K of ϕ j and then use the approximate ϕ j,K to solve the upper-level problem. We do not use a single-loop method to solve (5) because we need to get the task-specific adaptation ϕ j for each task T j . The single-loop method only partially solves the lower-level problem by one-step gradient descent and thus the obtained parameter can be far away from ϕ j .Lemma 5. The gradient of the lower-level problem in (5) is E π ϕ S,A ∞ t=0 γ t ∇ ϕ r ϕ (S t , A t ) S 0 = s tr 0 - ∞ t=0 γ t ∇ ϕ r ϕ (s tr t , a tr t ) + λ 1-γ (ϕ -θ) where (s tr t , a tr t ) ∈ D tr j .We roll out the policy π ϕ from s tr t to get a trajectory s ϕ 0 , a ϕ 0 , • • • where s ϕ 0 = s tr t and approximate the lower-level gradient byg ϕ = ∞ t=0 γ t ∇ ϕ r ϕ (s ϕ t , a ϕ t ) - ∞ t=0 γ t ∇ ϕ r ϕ (s tr t , a tr t ) + λ 1-γ (ϕ -θ).We update ϕ j,k+1 = ϕ j,k -β k g ϕ j,k for K times to get ϕ j,K where β k is the step size and ϕ j,k is the parameter at time k, and use ϕ j,K to calculate the approximate of the hyper-gradient d d θ L(ϕ j , D eval j ). Lemma 6. The hyper-gradient (i.e., gradient of the upper-level problem in (5))is d d θ L(ϕ j , D eval j ) = I + 1-γ λ ∇ 2 ϕϕ L(ϕ j , D tr j ) -1 ∇ ϕ L(ϕ j , D eval j ),where∇ ϕ L(ϕ j , D eval j ) = |D eval j | • E π ϕ j S,A ∞ t=0 γ t ∇ ϕ r ϕj (S t , A t ) S 0 ∼ P 0 - |D eval j | v=1 ∞ t=0 γ t ∇ ϕ r ϕj (s v t , a v t ), ∇ 2 ϕϕ L(ϕ j , D tr j ) = E π ϕ j S,A ∞ t=0 γ t ∇ 2 ϕϕ r ϕj (S t , A t ) S 0 = s tr 0 - ∞ t=0 γ t ∇ 2 ϕϕ r ϕj (s tr t , a tr t ) + e. The |D eval j | is the number of trajectories in D eval j , (s v t , a v t ) ∈ D eval j, and e is an extra term whose expression can be found in Appendix C.2.To approximate the hyper-gradient, we first roll out π ϕ j,K to get two trajectories sϕ j,K 0 , a ϕ j,K 0 , • • • and sϕ j,K 0 , āϕ j,K 0 , • • • where s ϕ j,K 0 is drawn from P 0 and sϕ j,K 0 = s tr 0 . We estimate ∇ ϕ L(ϕ j , D eval j ) via ∇ϕ L(ϕ j,K , D eval j ) = |D eval j | • ∞ t=0 γ t ∇ ϕ r ϕ j,K (s ϕ j,K t , a ϕ j,K t ) - |D eval j | v=1 ∞ t=0 γ t ∇ ϕ r ϕ j,K (s v t , a v t ) and estimate the term ∇ 2 ϕϕ L(ϕ j , D tr j ) via ∇2 ϕϕ L(ϕ j,K , D tr j ) = ∞ t=0 γ t ∇ 2 ϕϕ r ϕ j,K (s ϕ j,K t , āϕ j,K t ) - ∞ t=0 γ t ∇ 2 ϕϕ r ϕ j,K (s tr t , a tr t ). Therefore, we can approximate the hyper-gradient termd d θ L(ϕ j , D eval j ) via h j = [I + 1-γ λ ∇2 ϕϕ L(ϕ j,K , D tr j )] -1 ∇ϕ L(ϕ j,K , D eval j ).We omit the extra term e in the approximate h j and its impact on the convergence can be bounded (proved in Appendix C.4).To solve the upper-level problem in (5) , at each iteration n, we sample a batch of B tasks, and compute the task-specific adaptation ϕ j,K and the hyper-gradient h j for each task. The update law to solve the upper-level problem is: θn+1 = θnτn B B j=1 h j where τ n is the step size. Note that the time index k is for the lower-level problem and n is for the upper-level problem.Algorithm 2 Meta-regularization Input: Initialized meta-prior θ0 and task-specific adaptation ϕ j,0 Output: Learned prior θN1: for n = 0, 1, • • • , N -1 do 2:Sample a batch of B tasks {T j } B j=1 ∼ P Tfor each task T j do 4:for k = 0, 1, • • • , K -1 do 5:Compute the soft Bellman policy π ϕ j,k via soft Q-learning or soft actor-criticRoll out the policy π ϕ j,k to get a trajectory sϕ j,k 0 , a ϕ j,k 0 , • • • 7: Compute the gradient g ϕ j,k = ∞ t=0 γ t ∇ ϕ r ϕ j,k (s ϕ j,k t , a ϕ j,k t ) - ∞ t=0 γ t ∇ ϕ r ϕ j,k (s tr t , a tr t ) + λ 1-γ (ϕ j,k -θn ) C.1 Proof of Lemma 5The proof is similar to that of Lemma 1. We first prove the case of deterministic dynamics and the corresponding result can be an unbiased estimate in cases of stochastic dynamics (proved in Subsection B.2).EQUATION= Eπ ϕ S,A ∞ t=0 γ t ∇ ϕ r ϕ (S t , A t ) S 0 = s tr 0 - ∞ t=0 γ t ∇ ϕ r ϕ (s tr t , a tr t ),where (a) follows the proof of Lemma 3.Since the lower-level problem of ( 5) is unconstrained and ϕ i is the optimal solution, we know thatEQUATIONWe further take derivative of both sides in (25) with respect to θ and we get that∇ 2 ϕϕ L(ϕ j , D tr j ) + λ 1 -γ ∇θϕ j - λ 1 -γ = 0 ⇒ ∇θϕ j = I + 1 -γ λ ∇ 2 ϕϕ L(ϕ j , D tr j ) -1.Therefore, we have thatd d θ L(ϕ j , D eval j ) = (∇θϕ j ) ⊤ ∇ ϕ L(ϕ j , D eval j ) = I + 1 -γ λ ∇ 2 ϕϕ L(ϕ j , D tr j ) -1 ∇ ϕ L(ϕ j , D eval j ).Similar to Lemma 5, we can know thatEQUATIONwhere(s v t , a v t ) ∈ ζ v and ζ v ∈ D eval j .Since there is usually abundant data in D eval j and S 0 ∼ P 0 , we can reformulate (26) as the following:∇ ϕ L(ϕ j , D eval j ) ≈ |D eval j | • E π ϕ j S,A ∞ t=0 γ t ∇ ϕ r ϕj (S t , A t ) S 0 ∼ P 0 - |D eval j | v=1 ∞ t=0 γ t ∇ ϕ r ϕj (s v t , a v t ).Claim 7. The second-order information∇ 2 ϕϕ Q soft ϕ (s, a) = ∆(s, a) + E π ϕ S,A [ ∞ t=0 γ t Cov(S t )|S 0 = s, A 0 = a] and ∇ 2 ϕϕ V soft ϕ (s) = ∆(s) + E π ϕ S,A [ ∞ t=0 γ t Cov(S t )|S 0 = s] where ∆(s, a) = E π ϕ S,A [ ∞ t=0 γ t ∇ 2 ϕϕ r ϕ (S t , A t )|S 0 = s, A 0 = a], ∆(s) = E π ϕ S,A [ ∞ t=0 γ t ∇ 2 ϕϕ r ϕ (S t , A t )|S 0 = s], and Cov(s) ≜ a∈A π ϕ (a|s)[∆(s, a) -∆(s)]∆(s)da is the covariance matrix of ∆(s, •) at state s.Now we take a look at the term ∇ 2 ϕϕ L(ϕ j , D tr j ) and consider the case of deterministic dynamics:EQUATION= Eπ ϕ j S,A [ ∞ t=0 γ t ∇ 2 ϕϕ r ϕj (S t , A t )|S 0 = s tr 0 ] - ∞ t=0 γ t ∇ 2 ϕϕ r ϕj (s tr t , a tr t ) + E π ϕ j S,A [ ∞ t=0 γ t Cov(S t )|S 0 = s tr 0 ],where (a) follows Claim 7. As proved in Subsection B.2, we can still use this expression in the case of stochastic dynamics. We define e ≜ Eπ ϕ j S,A [ ∞ t=0 γ t Cov(S t )|S 0 = s tr 0 ].However, e is intractable to compute because it requires to compute COV(S t ) at every visited state. To approximate the covariance matrix COV(S t ), we need to empirically roll out the policy π ϕj from S t for enough times to get enough samples. We need to do these policy roll-outs at every state S t . For example, suppose we roll out the policy π ϕj ten times to get ten samples at each state S t . Empirically, we need to do these roll-outs 10 × T where T is a very large integer that we regard as infinity because the trajectory horizon is infinite. This is intractable because we need to roll out the policy for too many times. Moreover, we cannot guarantee that we can approximate COV(S t ) well given that we only use ten samples to approximate it.We know that ||∇ 2 ϕϕ L(ϕ,EQUATION1-γ C L where (a) follows (6) . Therefore, the lower-level objective function in ( 8) isC L 1-γ -smooth. Moreover, since λ ≥ C L 2 + η, then ||∇ 2 ϕϕ L(ϕ, D tr j )|| ≤ C L -2η 2(1-γ). Therefore, the lower-level objective function in ( 8) is 2η 1-γ -strongly convex. Following the standard result for strongly-convex and smooth stochastic optimization, we can reach the result in Lemma 7.In this proof, we first bound the hyper-gradient approximation error (i.e., || d d θ L(ϕ j , D eval j ) -h j ||) and then prove the convergence. Define hj≜ [I + 1-γ λ ∇2 ϕϕ L(ϕ j , D tr j )] -1 ∇ ϕ L(ϕ j , D eval j ) where ∇2 ϕϕ L(ϕ j , D tr j ) ≜ E π ϕ j S,A [ ∞ t=0 γ t ∇ 2 ϕϕ r ϕj (S t , A t )|S 0 = s tr 0 ] - ∞ t=0 γ t ∇ 2ϕϕ r ϕj (s tr t , a tr t ). Therefore, we have thatEQUATIONEQUATIONwhere (a) follows the fact that . Therefore,||I + 1-γ λ ∇ 2 ϕϕ L(ϕ j , D tr j )|| ≥ 1 -|| 1-γ λ ∇ 2 ϕϕ L(ϕ j , D tr j )|| ≥ 1 - C L -2η 2λ given that ||∇ 2 ϕϕ L(ϕ, D tr j )|| ≤ C L -2η 2(1-γ) (provedEQUATIONEQUATIONwhere EQUATIONwhere (c) follows ( 27)- (28) . Define F ( θ) as E j∼P T [L(ϕ j , D eval j )] under the meta-prior θ. Note that||h j || ≤ ||∆ -1 ϕ j,K || • ||∇ ϕ L(ϕ j,K , D eval j )|| ≤ λ λ-2 Cr • |D eval j | • 2 Cr 1-γ . Therefore, F ( θn+1 ) ≥ F ( θn ) + (∇F ( θn )) ⊤ ( θn+1 -θn ) - |D eval |(C L -2η) 4(1 -γ) || θn+1 -θn || 2 , ≥ F ( θn ) + τ n B B j=1 (∇F ( θn )) ⊤ h j - |D eval |(C L -2η)τ 2 n 4(1 -γ) || 1 B B j=1 h j || 2 , ≥ F ( θn ) + τ n B B j=1 (∇F ( θn )) ⊤ h j - |D eval |(C L -2η)τ 2 n 4(1 -γ) • λ λ -2 Cr • |D eval j | • 2 Cr 1 -γ , ≥ F ( θn ) + τ n B B j=1 (∇F ( θn )) ⊤ h j - 2λ Cr |D eval | 2 (C L -2η)τ 2 n 4(1 -γ) 2 (λ -2 Cr ) , ⇒ E[F ( θn+1 )] ≥ E[F ( θn )] + τ n E[||∇F ( θn )|| 2 ] + τ n B B j=1 E[h j - d d θ L(ϕ j , D eval j )] + τ n B B j=1 E[ d d θ L(ϕ j , D eval j ) -∇F ( θn )] - 2λ Cr |D eval | 2 (C L -2η)τ 2 n 4(1 -γ) 2 (λ -2 Cr ) , (d) ≥ E[F ( θn )] + τ n E[||∇F ( θn )|| 2 ] + τ n (C 1 + O( 1 K )) - 2λ Cr |D eval | 2 (C L -2η)τ 2 n 4(1 -γ) 2 (λ -2 Cr ) , ⇒ 1 N N -1 n=0 τ N E[||∇F ( θn )|| 2 ] ≤ 1 N N -1 n=0 τ n E[||∇F ( θn )|| 2 ], ≤ 1 N [F ( θN ) -F ( θ0 )] + 1 N N -1 n=0 τ n (C 1 + O( 1 K )) + 1 N N -1 n=0 2λ Cr |D eval | 2 (C L -2η)τ 2 n 4(1 -γ) 2 (λ -2 Cr ) , ⇒ 1 N N -1 n=0 E[||∇F ( θn )|| 2 ] ≤ O( 1 √ N + log N √ N + 1 K ) + C 1 ,where |D eval | ≜ sup i∼P T {|D eval j |} and (d) follows (29) .The code was running on a laptop whose processor is AMD Ryzen 7 4700U with Radeon Graphics, 2.00GHz, and the installed RAM is 20.0GB. The operating system is Ubuntu 18.04. We use a neural network to parameterize the learned reward function. The neural network has two hidden layers where each hidden layer has 64 neurons. The activation functions are respectively ReLU and Tanh.Here we provide the update rule for each baseline. Given a learned reward function r θ , the policy updates of the four baselines are the same with that of MERIT-IRL, i.e., one-step policy iteration. The difference is the reward update.IT-IRL: IT-IRL is MERIT-IRL without the meta-regularization term. Therefore, the reward update of IT-IRL isθ t+1 = θ t -α t g ′ t where g ′ t = ∞ i=0 γ i ∇ θ r θt (s ′ i , a ′ i ) - ∞ i=0 γ i ∇ θ r θt (s ′′ i , a ′′ i ).Recall from Subsection 4.1 that {(s ′ i , a ′ i )} i≥0 is generated by the learned policy π θt starting from the initial state s ′ 0 = s E 0 , and {(s ′′ i , a ′′ i )} i≥0 is generated by the learned policy π θt starting from (s ′′ t , a ′′ t ) where (s ′′ i , a ′′ i ) = (s E i , a E i ) for 0 ≤ i ≤ t. Naive MERIT-IRL: This method has the meta-regularization term, however, it uses the naive way (depicted in the middle of Figure 1 ) to update the reward function. In specific, it only compares the partial expert trajectory {s E i , a E i } t i=0 and partial learner trajectory {s ′ i , a ′ i } t i=0 . Therefore, the reward update of Naive MERIT-IRL is θ t+1 = θ t -α t g ′′ t where g′′ t = t i=0 γ i ∇ θ r θt (s ′ i , a ′ i ) - t i=0 γ i ∇ θ r θt (s E i , a E i ) + λ(1-γ t+1 ) 1-γ (θ -θ).Naive IT-IRL: This method does not have the meta-regularization term and uses the naive way to update the reward function. Therefore, the reward update of Naive IT-IRL isθ t+1 = θ t -α t g ′′′ t where g ′′′ t = t i=0 γ i ∇ θ r θt (s ′ i , a ′ i ) - t i=0 γ i ∇ θ r θt (s E i , a E i ).Hindsight: This method is a standard IRL method with the meta-regularization term where the complete expert trajectory {s E i , a E i } i≥0 and the complete learner trajectory {s ′ i , a ′ i } i≥0 are compared to update the reward function. Therefore, the reward update of Hindsight isθ t+1 = θ t -α t g ′′′′ t where g ′′′′ t = ∞ i=0 γ i ∇ θ r θt (s ′ i , a ′ i ) - ∞ i=0 γ i ∇ θ r θt (s E i , a E i ) + λ(1-γ t+1 ) 1-γ (θ -θ).Figure 2b shows that MERIT can achieve similar performance with the expert after t = 600 while the other three in-trajectory learning baselines fail to imitate the expert before the ongoing trajectory terminates. Note that the naive methods (i.e., Naive MERIT-IRL and Naive IT-IRL) have much smaller improvement from t = 0 compared to MERIT-IRL and IT-IRL. The reason is that the naive reward update method is flawed. Intuitively, the reward update mechanism of these two baselines are myopic as explained in Subsection 4.1. Theoretically, the gradients g ′′ t of Naive MERIT-IRL and g ′′′ t of Naive IT-IRL are biased estimate of (4) even if π t approaches π θt since (4) includes the trajectory suffix (i > t) terms while g ′′ t and g ′′′ t only include the trajectory prefix (i ≤ t) terms. MERIT-IRL performs much better than IT-IRL. The reason is that the meta-regularization term restricts the learned reward parameter within a certain neighborhood of the meta-prior θ (proved in Appendix B.3). Given that θ is trained over a family of relevant tasks, it is expected that the actual reward function parameter of our task shall be "close" to θ [24, 43, 56] , i.e., inside this neighborhood. Therefore, MERIT-IRL can efficiently learn the expert's reward function. On the contrary, IT-IRL does not have the meta-prior θ as a guidance and thus has to search over the whole parameter space, which is extremely difficult to learn the expert's reward function when the data is lacking. Note that MERIT-IRL and Naive MERIT-IRL have better initial performance than IT-IRL and Naive IT-IRL since MERIT-IRL and Naive MERIT-IRL starts at the meta-prior θ while IT-IRL and Naive IT-IRL initializes randomly.Figure 2c shows that MERIT can achieve similar performance with the expert after t = 500 while the other three in-trajectory learning baselines fail to imitate the expert before the ongoing trajectory terminates.We use the real-world data of 30 constitute stocks in Dow Jones Industrial Average from 2021-01-01 to 2022-01-01. The 30 stocks are respectively: 'AXP', 'AMGN', 'AAPL', 'BA', 'CAT', 'CSCO', 'CVX', 'GS', 'HD', 'HON', 'IBM', 'INTC', 'JNJ', 'KO', 'JPM', 'MCD', 'MMM', 'MRK', 'MSFT', 'NKE', 'PG', 'TRV', 'UNH', 'CRM', 'VZ', 'V', 'WBA', 'WMT', 'DIS', 'DOW'.The state of the stock market MDP is the perception of the stock market, including the open/close price of each stock, the current asset, and some technical indices [47] . The action has the same dimension as the number of stocks where each dimension represents the amount of buying/selling the corresponding stock. The detailed formulation of the MDP can be found in FinRL [47, 57] .The turbulence index is a technical index of stock market and is included as a dimension of the state [47, 57] . The function p 2 is defined as the amount of buying the stocks whose turbulence index is larger than the turbulence threshold. Therefore, the more the target investor buys the stocks whose turbulence index is larger than the turbulence threshold, the larger p 2 will be and thus the smaller reward the target investor will receive.Discussion on the experiment results. In Figure 2d , MERIT-IRL can achieve the similar cumulative reward with the expert when only the first 60% of the trajectory is observed while IT-IRL can achieve performance close to the expert after t = 220. This shows that the meta-regularization can help imitate the expert faster. In contrast, Naive MERIT-IRL and Naive IT-IRL barely improves because the naive reward update method is flawed. Intuitively, the reward update mechanism of these two baselines are myopic as explained in Subsection 4.1. Theoretically, the gradients g ′′ t of Naive MERIT-IRL and g ′′′ t of Naive IT-IRL are biased estimate of (4) even if π t approaches π θt since (4) includes the trajectory suffix (i > t) terms while g ′′ t and g ′′′ t only include the trajectory prefix (i ≤ t) terms. The last row in Table 1 shows the final results of the algorithms. We can see that MERIT-IRL achieves much better performance than the other in-trajectory learning baselines (i.e., IT-IRL, Naive MERIT-IRL, and Naive IT-IRL). MERIT-IRL achieves comparable performance with Hindsight and the expert. Note that it is not expected that MERIT-IRL outperforms Hindsight since Hindsight has the complete expert trajectory to learn.Since MERIT-IRL can infer the reward function of the expert, potential negative societal impact may occur when the learner is malicious. Take the stock market experiment as an example, private information like preferences or habits of the investors may be leaked by using MERIT-IRL. To avoid this situation, the investors needs to take additional strategies such as protecting its investment data from unsecure resources.From the objective (2), we can see that the goal of MERIT-IRL is to align with the expert demonstration, i.e., finding a reward function such that its corresponding policy makes the expert trajectory most likely. An ideal case is that we can also directly quantify the reward learning performance and study the reward identifiability issue. Thus, a future work is to study the reward identifiability issue in the context of in-trajectory IRL. 


Decision: This paper considers in-trajectory IRL, where a reward function and a corresponding policy need to be learned from an ongoing trajectory. The authors introduce an online learning algorithm to address this IRL problem with incomplete expert demonstrations. The paper includes a thorough theoretical analysis of the proposed solution, as well as a convincing empirical analysis on simulated data and some toy problems. A reviewer raised the issue regarding the identifiability of reward functions, but other reviewers think that this is a minor issue in the context of the other contributions of this work.

Reviews: review: paper_summary: paper_summary: The authors consider a new problem setting, called in-trajectory IRL, where a reward function and a corresponding policy need to be learned from an ongoing trajectory. The authors propose a novel reward update mechanism specially designed for this scenario and incorporate a meta-regularization strategy to embed prior knowledge and avoid overfitting. Theoretical analysis is provided for the convergence of the algorithm towards stationary points (and global under linear reward parametrization). MuJoCo benchmark and a real-world stock market example are used for experiments.
strength_weakness: strength_weakness: 1.	Assumption 1 assumes that the parameterized reward is smooth, which can be a strong assumption, especially for neural networks with non-smooth activation functions such as ReLU.
2.	The meta-regularization part seems to be important to the performance. However, the meta-learning needs to pre-collect data for many related tasks, which can be difficult in real world.
questions: questions: How the authors collect data for the meta-regularization in the experiment?

Other questions please refer to the Weaknesses.
limitations: limitations: The authors have discussed the limitations in Appendix F.
paper_summary: paper_summary: The paper "Learn Incrementally from An Ongoing Trajectory: A Provable In-Trajectory Inverse Reinforcement Learning Framework" proposes an innovative approach to inverse reinforcement learning. The authors introduce an online learning algorithm to address the IRL problem with incomplete expert demonstrations. A thorough theoretical analysis guarantees convergence, and a comprehensive experimental section validates the approach.
strength_weakness: strength_weakness: 1.In the experiments, I don’t understand why different algorithms have different initial points? When t=0, are you using a same random reward function or the prior-meta reward function to train your policy?
questions: questions: 1. Can the author explain why comparing the suffixes \(\{s_i', a_i'\}\) and \(\{s_i'', a_i''\}\) encourages the reward function to predict the future? Since you are completing the incomplete trajectory using the same policy, can reward function can learn something even if both are generated by the same policy.


2. Just wondering how you complete the incomplete trajectories in MuJoCo using saved states, since the state in MuJoCo only includes partial information about the simulator.
limitations: limitations: The authors address the limitations of this work.
paper_summary: paper_summary: In this paper, a novel framework for performing Inverse Reinforcement Learning (IRL) from an ongoing trajectory, i.e., to learn a reward function that induces an optimal policy that best explains the expert's demonstrations sequentially, without waiting to having observed the expert's trajectory entirely. Authors propose an online learning algorithm for solving the problem, and this algorithm has the added feature of meta-regularization. Both a theoretical and empirical analysis of the algorithm are provided to validate the results.
strength_weakness: strength_weakness: - There is no clear discussion and intuition of what kind of reward function is extracted by the algorithm and what it can be used for. For instance, various works about identifiability or the feasible set concern what we can do with the extracted rewards, because in most cases we cannot just extract a single reward explaining the demonstrations. However, this work does not analyse this fact.
- The presentation of the contents and contributions is poor.
questions: questions: - What reward are you extracting among all the rewards that explain the observed demonstrations? What can it be used for?
- Since in RL what matters is the cumulative sum of rewards, how can you be sure that you extract a meaningful reward even though you have not observed the expert's policy for the entire horizon?
limitations: limitations: The authors have adequately addressed the limitations and potential negative societal impact of their work.

Comments: comment: Dear authors, I had already read your comments. Although I appreciated the additional comments, I have decided to keep the score I assigned.
Dear reviewer,

Thanks again for your review. We have addressed all your comments. Could you please reevlaute our paper based on our response?

Best,  
Authors.
Dear reviewer,

Thanks for mentioning (1) why it should be useful to learn a reward function incrementally given that this increases the reward unidentifiability issue, and (2) the writing of the problem setting. We address these two comments below.
 
**For the comment (1)**, we answer from two aspects: (i) the connection between learning a useful reward and reward identifiability, and (ii) why the incrementally learned reward is useful.
 
(i) The fundamental usefulness of the learned reward is to explain the expert demonstrations. As mentioned in the first paragraph in our previous response, solving the reward identifiability issue is sufficient but not necessary to learn a reward function to explain the demonstrations. We agree that learning a reward incrementally can make it harder to solve reward unidentifiability issue. However, our algorithm can still learn a reward that explains the expert demonstrations despite the learned reward function may be different from the ground truth. In fact, shown in Table 1 in our paper, the optimal policy corresponding to the learned reward can generate trajectories whose cumulative ground truth reward is close to the expert cumulative ground truth reward, i.e., the learned policy generates trajectories close to the expert trajectories. 

(ii) Moreover, compared to imitation learning that directly learns an imitating policy, our learned reward can be used for conterfactual analysis [C8], e.g., instantly estimating the policies under different environment dynamics. Take the stock market as an example, the reward function captures the investor's risk tolerance [C11]. In our experiment, we learn the investor's risk tolerance incrementally in the stock market of Dow Jones Industrial Average (DJIA). The incrementally learned reward can instantly update the risk tolerance of the target investor. The instantly updated reward has two benefits. First, we can use the latest reward to recommend stocks as soon as possible, which gives us advantages to win this customer before our competitors.  Second, we can use the latest reward to estimate the investment behaviors preferred by the target investor in some other stock markets, e.g., CCXT (cryptocurrency) and  QuantConnect  (US securities) [C12], so that we can not only recommend stocks in the stock market where we collect data, i.e., DJIA, but also recommend stocks in other stock markets, e.g., CCXT and QuantConnect. If we use imitation learning, we can definitely learn an instant imitating policy and use this imitating policy to recommend stocks of DJIA as soon as possible. However, the imitating policy learned by imitation learning cannot be used to recommend stocks in CCXT and QuantConnect because they have different dynamics. In contrast, we can still apply the learned reward to these two new markets to learn the corresponding optimal policies and use the corresponding optimal policies to recommend stocks, because the investor's risk tolerance does not change even if the stock markets are different. We include an additional experiment result below where we use the data collected in DJIA to learn the reward function of the target investor and then apply the learned reward to CCXT and QuantConnect. We compare the cumulative reward between the optimal policy under the learned reward and the expert in these two different markets.
|                                   | CCXT                          | QuantConnect                   |
|:---:|:---:|:--:|
| Learned policy under the learned reward | 562.18 ± 34.02                 | 491.72 ± 18.25                 |
| Expert                            | 571.83 ± 27.16                 | 502.82 ± 14.26                 |

From the results above, we can see that even if in new stock markets with different dynamics, the learned reward from DJIA can still be used to generate policies in the new stock markets and the generated policies can still achieve similar cumulative ground truth reward with the expert in the new stock markets. This shows that the learned reward successfully captures the investor's risk tolerance.

**For the comment (2)**, we will add more explanations about the problem formulation (2)-(3) as follows: (i) we will highlight that the method we use to learn a reward function is maximum likelihood IRL (ML-IRL) and provide the intuition of ML-IRL where we aim to learn a reward function that makes the demonstration most likely; (ii) we will show our connection to the standard IRL where our problem formulation (2)-(3) will reduce to the formulation of ML-IRL when the complete trajectory can be observed; (iii) we will discuss the motivation to learn a reward function incrementally.
 
[C11] Qizhou Sun, X. Gong, and Y.-W. Si, "Transaction-aware inverse reinforcement learning for trading in stock markets," Applied Intelligence, 2023.
 
[C12] Xiaoyang Liu, et al. "FinRL-Meta: Market environments and benchmarks for data-driven financial reinforcement learning." NeurIPS, 2022.
I thank the authors for the time taken to answer to my questions. However, I am still convinced of the score that I assigned to this paper, because I do not understand why it should be useful to learn a reward function incrementally, given that this increases the usual identifiability problems of IRL. In addition, the problem setting is written in a not clear manner, that does not permit to fully understand the paper.
Thanks for the detailed response. The authors have done a great job answering my questions. I have no concerns nor questions about the assumption and the meta-regularization part now. I thus increase my rating. The meta-regularization is novel to IRL and the in-trajectory learning is an intereting new problem setting. I recommend acceptance of this paper.
I thank the authors for responding to my comments and providing these clarifications. I am happy to increase my score, assuming you can incorporate the global clarifications into the text.