Extracted main text — title through conclusion, appendix excluded. This is what our citation measures are computed over, published so the extraction can be checked by eye.
75,286 characters · 13 sections · 70 citation commands
Structural Estimation of Markov Decision Processes in High-Dimensional State Space with Finite-Time Guarantees
We consider the task of estimating a structural model of dynamic decisions by a single human agent based upon the observable history of implemented actions and visited states. This problem has been studied as the estimation of dynamic discrete choice (DDC) models in econometrics and inverse reinforcement learning (IRL) in artificial intelligence and machine learning research.
Rust is a seminal piece in the literature on dynamic discrete choice estimation. In that paper, the estimation task is formulated as a bi-level optimization problem where the inner problem is a stochastic dynamic programming problem and the outer problem is the likelihood maximization of observed actions and states. Rust proposed an iterative nested fixed point algorithm in which the inner dynamic programming problem is solved repeatedly followed by maximum likelihood updates of the structural parameters. Over the years, a significant literature on alternative estimation methods requiring less computational effort has been developed. For example, Hotz and Hotz1994 proposed two-step algorithms which avoid the repeated solution of the inner stochastic dynamic programming problem. In the first step, a non-parametric estimator of the policy (also referred to as conditional choice probabilities) is obtained and the inverse of a map from differences in Bellman's value function for different states to randomized policies is computed. In the second step, a pseudo log-likelihood is maximized. Two-step estimators may suffer from substantial finite sample bias if the estimated policies in the first step are of poor quality. Sequential estimators which are recursively obtained by alternating between pseudo-likelihood maximization and improved policy estimation are considered in Aguirregabiria_2002. In general, the computational burden for all these methods is significant when the state space is either discrete with large cardinality, or they are continuous in high dimensions. Discretization may be avoided by using forward Monte Carlo simulations Bajari_2007, Reich but this also becomes computationally demanding in high dimensions. A constrained optimization approach for maximum likelihood estimation of dynamic discrete choice models is considered in Su_2012. However, the number of constraints needed to represent Bellman's equation becomes a significant computational burden with discrete state space with large cardinality or continuous state space in high dimensions.
{ Recent work has addressed the computational challenges posed by high-dimensional state space. For example, in adusumilli2022temporaldifference the authors extend the CCP estimator approach proposed in Hotz by considering a functional approximation approach coupled with a temporal difference (TD) algorithm to maximize pseudo-likelihood. In Chernozhukov the authors consider an approach to adjust the CCP estimator to account for finite simple bias in high-dimensional settings. }
The literature in IRL features the seminal work ziebart2008maximum in which a model for the expert's behavior is formulated as the policy that maximizes entropy subject to a constraint requiring that the expected features under such policy match the empirical averages in the expert's observation dataset.\footnote{ In section (ref), we show that if the reward is linearly parametrized, the maximum entropy formulation in ziebart2008maximum is the dual of the maximum likelihood formulation of the estimation problem.} The algorithms developed for maximum entropy estimation ziebart2008maximum,ziebart2010modeling,wulfmeier2015maximum have a nested loop structure, alternating between an outer loop with a reward update step, and an inner loop that calculates the explicit policy estimates. The computational burden of this nested structure is manageable in tabular environments, but it becomes significant in high dimensional settings requiring value function approximation.
Recent works have developed algorithms to alleviate the computational burden of nested-loop estimation methods. For example, in garg2021iq, the authors propose to transform the standard formulation of IRL into a single-level problem by estimating the Q-function rather than estimating the reward function and associated optimal policy separately. However, the implicit reward function in the Q-function identified is a poor estimate since it is not guaranteed to satisfy Bellman's equation. Finally, ni2020f considers an approach called $f$-IRL for estimating rewards based on the minimization of several measures of divergence with respect to the expert's state visitation measure. The approach is limited to estimating rewards that only depend on state. While the results reported are based upon a single-loop implementation, the paper does not provide a convergence guarantee to support performance.
{ In contrast to the lines of works surveyed above, we focus our efforts in developing estimation algorithms with finite-time guarantees for computing high-quality estimators}. { Towards addressing this challenge}, in this paper, we propose a class of new algorithms which only require a finite number of computational steps for a class of (non-linearly parameterized) structural estimation problems { assuming the environment dynamics are known (or samples from the environment dynamics are available “on-line")}. Specifically, the proposed algorithm has a single-loop structure wherein a single-step update of the estimated policy is followed by an update of the reward parameter. We show that the algorithm has strong theoretical guarantees: to achieve certain $\epsilon$-approximate stationary solution for a non-linearly parameterized problem, it requires $\mathcal{O}(\epsilon^{-2})$ steps of policy and reward updates each. To our knowledge, it is the first algorithm which has finite-time guarantee for the structural estimation of an MDP under nonlinear parameterization of the reward function. We conduct extensive experiments to demonstrate that the proposed algorithm outperforms many state-of-the-art IRL algorithms in {\it both} policy estimation and reward recovery. In particular, when transferring to a new environment, the performance of state-of-the-art reinforcement learning (RL) algorithms, using estimated rewards outperform those that use rewards recovered from existing IRL and imitation learning benchmarks.
{Finally, we consider the extension to the “off-line" case in which the estimation task also includes the environment dynamics. Referring to our recent work (see offline-irl23), we consider a two-stage estimation approach. First, a maximum likelihood model of dynamics is identified. However, this first stage estimator of the environment dynamics may be inaccurate due to limited data coverage. Thus, in the second stage, a “conservative" reward estimator is obtained by introducing a penalty for model uncertainty. }
The structure of this paper is as follows. In Sec. (ref), we introduce the basic setting for structural estimation of MDPs. In Sec. (ref), we introduce the problem formulation of the maximum likelihood IRL. In Sec. (ref), we introduce a single-loop algorithm for estimation and formalize a finite-time performance guarantee for high dimensional states. In Sec. (ref), we present the convergence results of our proposed single-loop algorithm. In Sec. (ref), we consider the case with linearly parameterized rewards to show the proposed algorithm converges sublinearly to the maximum likelihood estimator. This results is proven by establishing a duality relationship between maximum entropy IRL and maximum likelihood IRL. In Sec. (ref), we consider the case in which the agent's preferences can be represented by a reward that is only a function of the state. {In Sec. (ref) we outline the extension of the proposed algorithms to the offline case.} Finally, in Sec. (ref), we present the numerical results.
We now review the basic setting for dynamic discrete choice model as given for example in Rust1994. At time $t \geq 0$, the agent implements an action $a_{t}$ from a finite (discrete) action space $\mathcal{A}$ and receives a reward $r(s_{t}, a_{t};\theta) + \epsilon_t(a_t)$, where $s_t\in \mathcal{S}$ is the state at time $t$, $r(s_{t}, a_{t};\theta)$ is the reward associated to the state-action pair $(s_{t}, a_{t})$ with $\theta \in \mathbb{R}^p$ a parameter and $\epsilon_t(a_t):\mathbb{R}^{|\mathcal{A}|}\to\mathbb{R}$ is a random perturbation which is observable by the agent (decision maker) but not by the modeler.
Upon implementing the action $a_{t} \in \mathcal{A}$, the state evolves according to a Markov process with kernel $P(s_{t+1}|s_t, a_t)$. Moreover, let $\mu(\epsilon_t|s_t)$ denote the probability distribution for the random perturbation, where the probability distribution is a function of the state.
Let $\pi(\cdot\mid s_t,\epsilon_t) $ denote a randomized policy, i.e. $\pi(a_t|s_t,\epsilon_t)$ is the probability that action $a_t$ is implemented when the state is $s_t$ and the observed reward perturbation vector is $\epsilon_t$.
The agent's optimal policy is characterized by the value function:
where the expectation is taken with respect to $a_t \sim \pi(\cdot|s_t,\epsilon_t), s_{t+1} \sim P(\cdot|s_t,a_t), \epsilon_{t+1} \sim \mu(\cdot|s_{t+1})$ and $\gamma \in [0,1)$ is the discount factor. The Bellman equation is:
where $Q_{\theta}:\mathcal{S} \times \mathcal{A} \mapsto \mathbb{R}$ is the fixed point of the {\em soft}-Bellman operator:
As the realization of the reward perturbations is not observable by the modeler, a parametrized model of the agent's behavior is a map $\pi_{\theta}(\cdot|s_t)$ which satisfies Bellman's optimality as follows:
{Assume observations are in the form of expert state-action trajectories $\tau^{\rm E}=\{(s_t,a_t)\}_{t\geq0}$ drawn from a ground-truth (or “expert") policy $\pi^{\rm E}$, i.e. $a_t \sim \pi^{\rm E}(\cdot|s_t)$, $s_{t+1} \sim P(\cdot|s_t,a_t)$ and $s_0 \sim \rho(\cdot)$, where $\rho(\cdot)$ denotes the initial distribution of the first state $s_0$}. The expected discounted log-likelihood of observing such trajectory under model $\pi_{\theta}$ can be written as:{
}
Given that the term $ {\mathbb{E}_{\tau^{\rm E} \sim \pi^{\rm E}}} \bigg[\sum_{t = 0}^{\infty} \gamma^t \log P(s_{t+1}|s_t,a_t) \bigg] $ is independent of the reward parameter $\theta$, the maximum likelihood estimation problem can be formulated as follows:
where $Q_{\theta}$ is the fixed point of the {\em soft}-Bellman operator in (ref).
In the next subsection we review the literature on the entropy-regularized RL model and then highlight the formal equivalence of entropy-regularized IRL with the dynamic discrete choice model just introduced in (ref).
A recent literature has considered MDP models with information processing costs Tishby2011,Ortega_2013,Matejka_2015,Hansen_2018. In these papers, optimal behavior is modeled as the solution to the following problem:
where $\rho(\cdot)$ denotes the initial distribution of the first state $s_0$, $\tau^A$ is a trajectory generate from the agent policy $\pi$ and $c(\cdot)$ is a function representing the information processing cost. A common specification is $c(\pi(\cdot|s_t))=\alpha D_{\rm KL}(\pi(\cdot|s_t) ||\pi_{0}(\cdot|s_t))$, where $D_{\rm KL}(\pi(\cdot|s_t) ||\pi_{0}(\cdot|s_t))=\sum\limits_{a\in \mathcal{A}}\pi (a|s_t)\log \frac{\pi (a|s_t)}{\pi _{0}(a|s_t)} $ is Kullback-Leibler divergence between $\pi(\cdot|s_t)$ and a reference (or default) policy $\pi_0(\cdot|s_t)$ and $\alpha \geq 0$ is a scale parameter. As the objective function above can be re-scaled by $\frac{1}{\alpha}$, we can set $\alpha=1$. To model no prior knowledge the reference policy $\pi_0$ is the uniformly random policy, i.e. $\pi _{0}(a)=\frac{1}{|\mathcal{A}|}$ for any $a \in \mathcal{A}$. In this case, we can further rewrite the problem as:
where $ \mathcal{H}(\pi(\cdot|s_t))=-\sum\limits_{a\in A}\pi (a|s_t)\log \pi (a|s_t)$ is the entropy of $\pi(\cdot|s_t)$. This model has also been recently used in the RL literature haarnoja2017reinforcement, haarnoja2018soft,cayci2021linear,cen2021fast where it is commonly referred to as an {\em entropy regularized} MDP.
Denoting the expert policy as $\pi^{\rm E}$ and assuming an entropy-regularized MDP model for behavior. and the model for dynamic behavior described, the inverse reinforcement learning (IRL) problem can be formulated as follows:
When the reward perturbations $\epsilon_t(a)$ follow i.i.d. Gumbel distribution with zero mean and variance $\frac{\pi^2}{6}$ for $a \in A$, the models of behavior (ref) and (ref) are equivalent (see Proposition 1 in Mai_2020). {Specifically, the fixed point $Q_{\theta}(s,a)$ of the Bellman operator $\Lambda_{\theta}$ in (ref) and the optimal policy (ref) are of the form:
As has been shown in haarnoja2018soft,cen2021fast, the policy described in (ref) corresponds to the optimal policy in (ref) so that
}
{
The existing solution and approximation methodologies for solving (ref) (or equivalently, (ref)) are ill-equipped for dealing with the high dimensional state space. For example, the algorithms considered in (e.g. Rust1994,ziebart2010modeling,wulfmeier2015maximum) rely on a nested-loop structure which requires the solution of a fixed-point problem in the inner-loop before making any updates to the parameter estimates for the outer-loop. Evidently, in high dimensional environments. the inner-loop solution renders the nested-loop structure computationally intractable.
Similarly, with high dimensional continuous state, a discretization approach (e.g. Su_2012) to solving the inner problem (ref) (or equivalently, (ref)) is computationally intractable. Forward Monte Carlo simulations Bajari_2007, Reich is an alternative to discretization but this is also computationally demanding in high dimensions.
Approximation algorithms (e.g. Hotz,Hotz1994, garg2021iq, ni2020f) reduce the computational burden of the nested-loop structure. However, the resulting estimates may be of poor quality. For example, the CCP estimator from Hotz,Hotz1994 may suffer from finite sample bias because in high dimensional state space, initial policy estimates (i.e. conditional choice probabilities) based upon empirical frequencies are likely of poor quality. Sequential estimators Aguirregabiria_2002 reduce bias at the expense of significant computational burden. The reward estimates in garg2021iq do not approximate a solution to the inner problem and are thus likely to be of poor quality. Recently, adusumilli2022temporaldifference and Chernozhukov have proposed approaches to account for finite-sample bias in CCP estimators in high dimensional environments.
In the present paper we introduce a new class of single-loop algorithms which exhibit finite-time guarantees of performance for solving (ref)) (or more precisely, its approximated version to be introduced in the next section).
As many papers in the dynamic discrete choice (DDC) estimation literature (e.g. Rust1994 rely on a two-stage approach to estimating dynamics (first stage) and rewards (second stage), the results obtained in this paper address the computational complexity of the {\em second} stage estimation task. This issue was ignored in Rust due the scale of the problem. However, computational complexity is an important concern in high-dimensional environments.
In Section (ref), we also discuss how to extend the proposed method to the two-stage problem / offline setting where estimating dynamics should be considered. }
{ In practice, the IRL problem (ref) (and its equivalent (ref)) can only be approximated with a {\em finite} set of observed trajectories as the ground-truth behavior model (or “expert" policy) $\pi^{\rm E}$ is not known. Let $\mathcal{D} := \{ \tau^{\rm E} \}$ denote a finite dataset of state-action trajectories independently drawn from the expert policy and the environment dynamics. Let $\tau^{\rm E}\sim \mathcal{D}$ denote a uniformly sampled trajectory from $\mathcal{D}$. Using a finite dataset, a natural choice for an {\em empirical} approximation to the estimation problem is the following:
However, with high-dimensional state space, the above approximation $\widetilde{L}(\theta,\mathcal{D})$ is likely to incur significant error because the observed transitions in the data may not adequately describe the ground-truth transition kernel. In what follows, we introduce a different {\em surrogate} empirical objective $\widehat{L}(\theta,\mathcal{D})$ which provides a better approximation to the original likelihood function $L(\theta)$ given in (ref) with high-dimensional state.
To motivate the definition of $\widehat{L}(\theta,\mathcal{D})$, let us start by expressing the likelihood function ${L}(\theta) := \mathbb{E}_{\tau^{\rm E} \sim \pi^{\rm E}} \bigg[ \sum_{t = 0}^{\infty} \gamma^t \log \pi_{\theta}(a_t | s_t) \bigg]$ in terms of the difference in expected value:
where $(i)$ follows the closed-form expression of the optimal policy $\pi_{\theta}$ in (ref), $(ii)$ follows the expression of the soft value function $V_{\theta}$ in (ref) and $(iii)$ follows from the fixed point definition in (ref).
Observe that in the above decomposition, the first term is related to the expert policy $\pi^{\rm E}$, while the second term is related to the initial distribution $\rho$ and the transition kernel $P$. Note that in practice we only have limited observations of expert trajectories from a fixed dataset $\mathcal{D}$, but cannot directly sample the trajectory from the expert policy $\pi^{\rm E}$ in an online manner. Hence, we need to construct an estimation problem which utilizes limited observations of expert trajectories to approximate the original maximum likelihood objective in (ref). Since we assume the {\it online} setting in which the transition kernel $P$ and the initial distribution $\rho$ are either available for access or known, we can construct a {\it surrogate} approximation to the likelihood as follows:
In contrast, if we conduct the same analysis on the {\it empirical} approximation $\widetilde{L}(\theta;\mathcal{D})$ presented in (ref), we obtain:
where the second term is the error introduced by approximating the transition using finite data.
From the above analysis, we argue that the {\it surrogate} approximation $\widehat{L}(\theta;\mathcal{D})$ in (ref) is a more accurate objective function as compared to the {\it empirical} likelihood $\widetilde{L}(\theta;\mathcal{D})$ in (ref). Below we show under a mild assumption, $\widehat{L}(\theta;\mathcal{D})$ can well-approximate $L(\theta)$ when data is large enough.
The proof of Lemma (ref) can be found in Section (ref) in the electronic companion.
In the rest of this work, we will consider the following surrogate estimation problem:
}
The main idea in the proposed algorithm is to alternate between one step of policy update to improve the solution of the lower-level problem, and one step of the parameter update which improves the upper-level likelihood objective. At each iteration $k$, given the current policy $\pi_k$ and the reward parameter $\theta_k$, a new policy $\pi_{k+1}$ is generated from the policy improvement step, and $\theta_{k+1}$ is generated by the reward optimization step.
{In Sec. (ref) - Sec. (ref), we will design an algorithm to solve the approximated maximum likelihood problem (ref). We emphasize that in Sec. (ref) - Sec. (ref), we assume an {\it online} setting where the learner knows the transition kernel $P(s_{t+1}|s_t,a_t)$ or can sample from it. The motivation is that understanding how to develop efficient algorithms for the {\it online} setting is the basis for addressing the more challenging {\it offline} setting. In Sec. (ref) we will briefly outline how to extend this work to the offline setting.} Below we present the details of our algorithm at a given iteration $k$.
{\bf Policy Improvement Step.} Let us consider optimizing the lower-level problem (ref), when the reward parameter $\theta_k$ is held fixed. Towards this end, we define the so-called soft Q-function and soft value functions under a given policy-reward pair $(\pi_k,\theta_k)$:
Similarly, if the policy is {\it optimal} for a given parameter $\theta$ (as defined in (ref)), then we will denote the associated soft Q-function and soft value function as $Q_{\theta}$ and $V_{\theta}$.
To obtain an estimate of the policy at iteration $k$, let us suppose that we have access to an estimate of the soft Q-function, denoted as $\widehat{Q}_k(s,a)$, which satisfies $\| \widehat{Q}_k - Q_k \|_{\infty} \leq \epsilon_{\rm app}$, with $\epsilon_{\rm app}>0$ being the approximation error. Then the estimated policy will be generated according to
When $\epsilon_{\rm app}=0$, or equivalently when $\widehat{Q}_k(s,a)={Q}_k(s,a),\;\forall~s \in \mathcal{S}, a \in \mathcal{A}$, and when $r(\cdot, \cdot;\theta_k)$ is fixed, the above update is referred to as the {\it soft policy iteration}; {it is known that the policy will be monotonically improved by soft policy iteration and will converge linearly to the optimal policy; see cen2021fast.} {In practice, when we do not have direct access to the exact soft Q-function $Q_k$, one could use an {\it estimated} soft Q-function $\widehat{Q}_k$ to perform the approximated soft policy iteration in (ref), which can be obtained by following the update schemes in soft Q-learning haarnoja2017reinforcement or soft Actor-Critic (SAC) haarnoja2018soft.}
{\bf Reward Optimization Step.} We propose to use a stochastic gradient-type algorithm to optimize the reward parameter $\theta$. Towards this end, let us first derive the exact gradient $\nabla_{\theta} L(\theta)$. See the supplementary material for detailed proof.
{We note that the gradient expression (ref) takes the same form as the one given in a recent work sanghvi2021inverse. However, our proof which focuses on the {\em infinite} horizon case is different. Moreover, we further derive the gradient expression of the sample-based estimation problem $\widehat{L}(\theta; \mathcal{D})$ which has not been considered in sanghvi2021inverse. }
In order to obtain stochastic estimators of the empirical gradient $\nabla_{\theta} \widehat{L}(\theta_k; \mathcal{D})$, we take { two} approximation steps: 1) approximate the optimal policy $\pi_{\theta_k}$ by $\pi_{k+1}$ in (ref), since the optimal policy $\pi_{\theta_k}$ is not available throughout the algorithm; { 2) sample the trajectory $\tau^{\rm A}$ from the current policy $\pi_{k+1}$.}
Following the approximation steps mentioned above, we construct a stochastic estimator $g_k$ to approximate the {empirical gradient $\nabla_{\theta} \widehat{L}(\theta_k; \mathcal{D})$ in (ref)} as follows:
With the stochastic gradient estimator $g_k$, the reward parameter $\theta_k$ is updated as:
where $\alpha$ is the stepsize in updating the reward parameter.
Alg. (ref) summarizes the proposed two-step approach for solving the IRL problem (ref). {It is worth mentioning that the proposed algorithm can also be used to solve the DDC problem (ref) due to the equivalence between (ref) and (ref).}
Before closing this section, let us note that the generic alternating update strategy adopted by our algorithm is efficient, since completely solving the policy optimization subproblem all the time could be redundant, and could induce heavy computation burden. Such a kind of strategy has been used in many other RL related settings as well. For example, the well-known actor-critic (AC) algorithm for policy optimization konda1999actor,wu2020finite,hong2020two alternates between one step of policy update, and one step of critic parameter update. However, these types of algorithm are known to be challenging to analyze, partly because when the inner problem (e.g., the policy optimization problem (ref)) is not solved exactly, the update direction for the main parameter (e.g., $\theta$ in (ref)) can be very far from the desired descent directions. That is, $g_k$ in (ref) can be a very coarse approximation of the exact gradient {$\nabla_{\theta} \widehat{L}(\theta_k; \mathcal{D})$ as expressed in (ref)}. In the subsequent sections, we develop techniques to address the above mentioned changes.
Our analysis is based upon the so-called {\it two-timescale} stochastic approximation (TTSA) approach borkar1997stochastic,hong2020two, where the lower-level problem updates in a faster time-scale (i.e., converges faster) compared with its upper-level counterpart. Intuitively, the TTSA enables the $\pi_{k+1}$ to track the optimal $\pi_{\theta_k}$, so that the gradient estimate $g_k$ will stay close to the gradient {$\nabla_{\theta} \widehat{L}(\theta_k)$}. Indeed, Alg. (ref) has the desired two-timescale phenomenon because the policy update (ref) converges linearly to the optimal policy under a fixed reward function cen2021fast (hence it is `fast'); while the reward parameter update (ref) does not have such linear convergence property (hence it is `slow'). To begin our analysis, let us first present a few technical assumptions.
Assumption (ref) assumes the Markov chain mixes at a geometric rate. It is a common assumption in the iterature of RL bhandari2018finite,zou2019finite,wu2020finite, which holds for any time-homogeneous Markov chain with finite-state space or any uniformly ergodic Markov chain with general state space.
Assumption (ref) assumes that the parameterized reward function has bounded gradient and is Lipschitz smooth. Such assumption in Lipschitz property are common in the literature of min-max / bi-level optimization jin2020local,hong2020two,guan2021will,khanduri2021near,chen2021closing. Based on Assumptions (ref) - (ref), we next provide the following Lipschitz properties:
{The full proof of the result is delegated to Sec. (ref) in the companion of the paper.}
Next we present the main results, which show the convergence speed of the policy $\{ \pi_k \}_{k \geq 0}$ and the reward parameter $\{ \theta_k \}_{k \geq 0}$ in the Alg. (ref). Please see Appendix (ref) for the detailed proof.
In Theorem (ref), we present the finite-time guarantee for the convergence of the Alg. (ref). We note that our theoretical guarantee is different from the existing works, such as cen2021fast which showed the convergence rate of soft policy iteration under a {\it fixed} reward function. Theorem (ref) analyzes a more challenging setting where {\it both} the policy and reward parameter are kept changing. To our knowledge, this is the first result that characterizes the finite-time convergence for an algorithm developed for either the structural estimation problem (ref) or the maximum likelihood IRL problem (ref). {In the following result, we characterize the dimension dependence of the performance of the policy estimated with Algorithm 1.}
{ {\bf Remark 3}: It is worth mentioning here that the Lipschitz constant $L_c$ in (ref) is given by: $$L_c = \frac{2L_q L_r C_d \sqrt{ | \mathcal{S}| \cdot |\mathcal{A}| } }{1 - \gamma} + \frac{2 L_g}{1 - \gamma},$$ where $C_d$ is a constant given in (ref). Hence, $L_c$, as well as the subsequent convergence rate of the algorithm in Theorem 1, are dependent on the dimension of the problem (i.e., the size of the state and action space). However, the empirical evidence (to be presented in Sec. (ref)) strongly indicates that the proposed algorithm performs well with high-dimensional neural network representations. This is mainly because our formulation allows us to directly take (approximate) gradient steps on updating $\theta_k$, and that for fixed reward parameterization $\theta_k$, the lower-level policy optimization problem we are interested in has a closed-form solution (as a function of the corresponding $Q_k$). We believe that the extension of the analysis for our algorithm with function approximations (for the parameterized Q-function and the policy) will result in bounds that have less dependence upon the dimension of the basis at the expense of additional approximation error term. The extension of our convergence analysis with function approximations is left for future research. }
The result in Theorem 1 can be further strengthened when rewards are a linear function of (possibly non-linear) features, i.e. $ r(s,a;\theta) = \phi(s,a)^{\top} {\theta}$ with $\phi:\mathbb{R}^{|S|\times |A|} \rightarrow \mathbb{R}^p$ and the distribution of observations is consistent with optimal behavior for a ground truth parameter $\theta^*$, $\pi^E=\pi_{\theta^*}$.
In this setting, the result in Theorem 1 can be strengthened to finite-time convergence to the optimal solution. To show this result we first establish a duality relationship between the estimation problem in (ref), and the maximum entropy estimator Ziebart_2013 which is the solution to the following problem:
where (ref) requires that the expected discounted feature value under the model matches the { expected} discounted feature under the finite dataset $\mathcal{D}$ of collected expert trajectories. When the expert policy is known or available for access, the maximum entropy estimation problem is defined as in (ref) by replacing (ref) with
The following result formalizes the relationship between the maximum entropy estimation problem (ref) and the estimation problem (ref).
Please see the detailed proof in Appendix (ref).
{
{\bf Proof:} The first result is a direct consequence of Theorem (ref) since the estimation problem (ref) is a dual problem. Then we prove {\em (ii)} by contradiction. Let $\widehat{\theta}_1, \widehat{\theta}_2$ denote two distinct solutions of the estimation problem (ref), which is the dual problem w.r.t. the maximum entropy IRL problem (ref). From (ref) it follows that
Let $Q_{\widehat{\theta}_i}$ denote the unique fixed point of the soft-Bellman operator and $\tilde{Q}_{\widehat{\theta}_i}(s,a):=Q_{\widehat{\theta}_i}(s,a)-Q_{\widehat{\theta}_i}(s,\tilde{a})$ for all $a\in A$. The following mapping (from the parameter space to the policy space) $$\pi_{\widehat{\theta}_i}(a|s):=\frac{\exp{\tilde{Q}_{\widehat{\theta}_i}(s,a)}}{\sum_{a'\in A}\exp{\tilde{Q}_{\widehat{\theta}_i}(s,a')}}$$ is one-to-one (see Proposition 1 in Hotz) and $\pi_{\widehat{\theta}_1}\neq \pi_{\widehat{\theta}_2}$. By Theorem 2 (strong duality), it holds that $$ \mathbb{E}_{\tau^{\rm A} \sim \pi_{\widehat{\theta}_i}} \big[ \sum_{t = 0}^{\infty} \gamma^t \log \pi_{\widehat{\theta}_i}(a_t | s_t) \big] = \mathbb{E}_{\tau^{\rm A} \sim \widehat{\pi}} \big[ \sum_{t = 0}^{\infty} \gamma^t \log \widehat{\pi} (a_t | s_t) \big] $$ where $\widehat{\pi}$ is an optimal solution to primal problem (ref). This is a contradiction to the uniqueness of the optimal solution $\widehat{\pi}$ since the maximum entropy objective (ref) is {strictly concave}. Hence, we can show that the optimal solution to (ref) is unique. $\blacksquare$
Note that the concavity property does not hold for the estimation objective in Rust1994. For example, the undiscounted empirical likelihood for Group 2 data in Rust can be shown to be non-concave.
Moreover, we note that the bi-level formulations (ref) and (ref) are quite involved, and it is difficult to directly show the concavity of the problems (ref) and (ref) with nonlinear reward parameterization. Based upon our observations under linear reward parameterization, as well as the finite sample guarantee given in Lemma (ref), we have the following corollary:
{\bf Proof:} {The finite-time guarantee $\mathbb{E}\big[\|\nabla \widehat{L}(\widehat{\theta}_K,\mathcal{D})\|^2\big] \leq \mathcal{O}(K^{-1/2})$ implies $\|\nabla \widehat{L}(\widehat{\theta}_K,\mathcal{D})\|^2 \rightarrow 0$ in probability. By compactness, the set of accumulation points of the sequence $\{\widehat{\theta}_K:K\in \mathbb{N}^+\}$ is non-empty. By Corollary 1{\em (ii)}, the set of limit points is a singleton, hence $\widehat{\theta}_K \rightarrow \widehat{\theta}$ in probability. } To prove the performance guarantee in (ref), we can show the following decomposition of the error between the log likelihood objective evaluated at $\theta^*$ and $\widehat{\theta}$, respectively. With probability greater than $1 - \delta$, the following result holds:
where $(i)$ follows (ref) in Lemma (ref). Since we have defined $\widehat{\theta}$ as the optimal solution to $\widehat{L}(\cdot;\mathcal{D})$, we know that $\widehat{L}(\theta;\mathcal{D}) - \widehat{L}(\widehat{\theta};\mathcal{D}) \leq 0$ for any $\theta$. Plugging this result into (ref), the following result holds with probability greater than $1 - \delta$:
Hence, when the number of expert trajectories in the demonstration dataset satisfies $|\mathcal{D}|\geq \frac{2C_r^2}{\epsilon^2 (1 - \gamma)^2} \ln\big( \frac{2}{\delta} \big) $, then with probability greater than $1 - \delta$, we obtain
where $\theta^*$ is the ground truth parameter, which is optimal w.r.t. the log-likelihood objective $L(\cdot)$ defined in (ref). The corollary is proved. $\blacksquare$
It is worth mentioning that when relaxing the assumption that the ground-truth reward value $r(s,\tilde{a};\theta^*)$ for a reference action $\tilde{a} \in A$ and $s \in S$ is known, we will no longer have a guarantee on parameter convergence. However, as shown below, the policy obtained by Algorithm 1 still converges to the expert policy.
{By defining the state-action visitation measure $d^{\rm E}(s,a) := (1-\gamma)\pi^{\rm E}(a|s)\sum_{t = 0}^{\infty} \gamma^t P^{\pi^{\rm E}}(s_t = s| s_0 \sim \rho)$ under the expert policy $\pi^{\rm E}$, we can rewrite the expression of the log-likelihood objective $L(\cdot)$ in (ref) for any reward parameter $\theta$ as below:
} Then the $\epsilon$-optimal solution on the maximum likelihood IRL problem (ref) implies:
where $d^{\rm E}(s,a) := (1-\gamma)\pi^{\rm E}(a|s)\sum_{t = 0}^{\infty} \gamma^t P^{\pi^{\rm E}}(s_t = s| s_0 \sim \rho)$ denotes the state-action visitation measure under the expert policy $\pi^{\rm E}$. Assume the expert behaviors are consistent with optimal behavior for a ground truth reward parameter $\theta^*$, then it follows $\pi^{\rm E} = \pi_{\theta^*}$. Due to this property, we can obtain the following result:
Hence, Corollary (ref) provides a formal guarantee that the recovered policy $\pi_{\widehat{\theta}}$ solved from the empirical estimation problem (ref) is $\epsilon$-close to the expert policy $\pi^{\rm E}$ measured by the KL divergence.
{\bf Remark 4:} We also believe the results for the linear reward parametrization case can be generalized to certain nonlinear parametric rewards representations. Such is the case, for example, of {\it overparameterized} neural networks. In this setting, under certain structural assumptions such as Neural Tangent Kernel and Local Linearity (see du2018gradient and Jacot_2018) we expect that the resulting reward representation is approximately linear in the parameters. Hence, it would be possible to identify the global optimal reward estimator. These directions are left for future research. }
{In this section we consider the IRL problems when the reward is only a function of the state. A lower dimensional representation of the agent's preferences (i.e. in terms only of states as opposed to states {\em and} actions) is more likely to facilitate counterfactual analysis such as predicting the optimal policy under different environment dynamics and/or learning new tasks. This is because the estimation of preferences which are only defined in terms of states is less sensitive to the specific environment dynamics in the expert's demonstration dataset. } {Moreover, in application such as healthcare yu2021reinforcement and autonomous driving kiran2021deep, where simply imitating the expert policy can potentially result in poor performance, since the learner and the expert may have different transition dynamics. Similar points have also been argued in recent works gangwani2020state,ni2020f,viano2021robust.
Next, let us briefly discuss how we can understand (ref) and Alg. (ref), when the reward is parameterized as a state-only function.} First, it turns out that there is an equivalent formulation of (ref), when the expert trajectories only contain the visited states.
Please see the Section (ref) in the supplementary material for detailed derivation. Intuitively, the above lemma says that, when dealing with the state-only IRL, (ref) minimizes the gap between the soft value functions of the optimal policy $\pi_{\theta}$ and the { expert policy $\pi^{\rm E}$}. {Moreover, Alg. (ref) can also be easily implemented with the state-only reward. In fact, the entire algorithm essentially stays the same, and the only change is that $r(s,a;\theta)$ will be replaced by $r(s;\theta)$. In this way, by only using the visited states in the trajectories, one can still compute the stochastic gradient estimator in (ref). Therefore, even under the state-only IRL setting where the expert dataset only contains visited states, our formulation and the proposed algorithm still work if we parameterize the reward as a state-only function.} Moreover, it is straightforward to show that the convergence results in Theorem (ref) also hold under the state-only IRL setting.
{ Throughout this paper, we have focused on the {\it online} setting where the transition kernel $P(s_{t+1}|s_t,a_t)$ is known or alternatively, samples from such kernel are available to the learner in an online fashion. However, in many applications this assumption does not hold and the available data is fixed. In such an {\em offline} setting, one strategy to deal with the problem is to estimate {\it both} the transition kernel and the reward function based on the finite dataset of state-action sequences. In our follow-up work offline-irl23 to the present paper, we have extended Algorithm 1 to the offline setting. In particular, a two-stage estimation procedure has been proposed, where in the first stage a maximum likelihood estimate of the transition kernel is obtained from transition triples $(s,a,s')$ in a transition dataset denoted as $\mathcal{D}^T$, i.e. $ \hat{P} := \arg \max_{\tilde{P}} \mathbb{E}_{(s,a,s^\prime) \sim \mathcal{D}^T}\bigg[ \log \tilde{P}(s^\prime|s,a)\bigg].$ Given that finite-data estimation of high-dimensional environment dynamics likely leads to an inaccurate model, in the second stage, a “conservative" reward estimator is obtained using $\hat{P}$ by introducing a regularization term $U(s,a)$ to account model uncertainty:
The regularization term in the lower level problem (ref) induces {\em conservative} policies which assign low probability to state-action pairs in which $\widehat{P}$ cannot provide an accurate prediction on the dynamics. Clearly, the second stage is closely related to the online setting discussed in this work. Therefore algorithms and intuitions developed in the present work for the online setting is crucial for the offline setting as well.
There are many other outstanding issues to be resolved for the offline setting. For example, how well the estimated transition function can be recovered, how the error will propagate to the error of the reward estimation, and how to compute (stochastic) gradient for the new formulation (ref) and (ref). Since these investigations are out of the scope of this paper, we refer the readers to in offline-irl23 for more details.}
In this section, we test the performance of our algorithm { with limited expert trajectories} on a diverse collection of RL tasks and environments. In each experiment set, we train algorithms until convergence and average the scores of the trajectories over multiple random seeds.
{\bf Mujoco Tasks For Inverse Reinforcement Learning.} In this experiment set, we test the performance of our algorithm on imitating the expert behavior. We consider several high-dimensional robotics control tasks in Mujoco todorov2012mujoco. {Two classes of existing algorithms are considered as the comparison baselines: 1) imitation learning algorithms that only learn the policy to imitate the expert, including Behavior Cloning (BC) pomerleau1988alvinn and Generative Adversarial Imitation Learning (GAIL) ho2016generative; 2) IRL algorithms which learn a reward function {\it and} a policy simultaneously, including Adversarial Inverse Reinforcement Learning (AIRL) fu2017learning, $f$-IRL ni2020f and IQ-Learn garg2021iq.} To ensure fair comparison, all imitation learning / IRL algorithms use soft Actor-Critic haarnoja2018soft as the base RL algorithm. For the expert dataset, we use the data provided in the official implementation\footnote{\url{https://github.com/twni2016/f-IRL}} of $f$-IRL.
In this experiment, we implement two versions of our proposed algorithm: ML-IRL(State-Action) where the reward is parameterized as a function of state and action; ML-IRL(State-Only) which utilizes the state-only reward function. In Table (ref), we present the simulation results under a limited data regime where only five expert trajectories are collected. {The scores (cumulative rewards) reported in the table is averaged over $5$ random seeds. In each random seed, we train algorithm from initialization and collect $20$ trajectories to average their cumulative rewards after the algorithms converge. } According to the results reported in Table (ref) { where we run the experiments with only five expert trajectories in the demonstration dataset $\mathcal{D}$}, it shows that our proposed algorithms outperform the baselines on most tasks.
{We observe that BC fails to imitate the expert's behavior. It is likely due to the fact that BC is based on supervised learning and thus could not learn a good policy under such a limited data regime.} Moreover, we notice the training of IQ-Learn is unstable, likely due to its inaccurate approximation to the soft Q-function. Therefore, in the Mujoco tasks where IQ-Learn does not perform well, we cannot match the results presented in the original paper garg2021iq. For those cases, we directly report results from the original paper (and mark them by $*$ in Table (ref)). The results of AIRL are not presented in Table (ref) since it performs poorly even after spending significant efforts in parameter tuning; note that similar observations have been made in liu2019state,ni2020f.
{\bf Transfer Learning Across Changing Dynamics.} We further evaluate IRL algorithms on the transfer learning setting. We follow the environment setup in fu2017learning, where two environments with different dynamics are considered: {\tt{Custom-Ant}} vs {\tt{Disabled-Ant}}. We compare ML-IRL(State-Only) with several existing IRL methods: 1) AIRL fu2017learning, 2) $f$-IRL ni2020f; 3) IQ-Learn garg2021iq.
We consider two transfer learning settings: 1) data transfer; 2) reward transfer. For both settings, the expert dataset / trajectories are generated in {\tt{Custom-Ant}}. In the data transfer setting, we train IRL agents in {\tt{Disabled-Ant}} by using the expert trajectories, which are generated in {\tt{Custom-Ant}}. In the reward transfer setting, we first use IRL algorithms to infer the reward functions in {\tt{Custom-Ant}}, and then transfer these recovered reward functions to {\tt{Disabled-Ant}} for further evaluation. {In both settings, we also train SAC with the ground-truth reward in {\tt{Disabled-Ant}} and report the scores.}
The numerical results are reoprted in Table (ref). the proposed ML-IRL(State-Only) achieves superior performance compared with the existing IRL benchmarks in both settings. We notice that IQ-Learn fails in both settings since it indirectly recovers the reward function from a soft Q-function approximator, which could be inaccurate and is highly dependent upon the environment dynamics. Therefore, the reward function recovered by IQ-Learn cannot be disentangled from the expert actions and environment dynamics, which leads to its failures in the transfer learning tasks.
The nested structure of the structural estimation of MDPs entails a significant computational burden in environments with a high-dimensional continuous state or discrete state with large cardinality. To alleviate such burden several approaches have been proposed in both the econometrics (dynamic discrete choice estimation) and artificial intelligence (inverse reinforcement learning) literature. For example, the approximation algorithms in Hotz,Hotz1994 reduce the computational burden but the resulting estimates suffer from finite sample bias because in high dimensional state space, initial policy estimates are likely of poor quality. Recent approaches in inverse reinforcement learning that lessen the computational burden garg2021iq, ni2020f do so either at the expense of reward estimation accuracy or lack theoretical guarantees.
In this paper we introduce a class of single-loop algorithms for the structural estimation of MDPs with non-linear parametrization. In each iteration a policy improvement step is followed by a stochastic gradient step for likelihood maximization. We show that the proposed algorithm converges to a stationary solution with a finite-time guarantee. Further, if the reward is parameterized linearly, we show that the algorithm approximates the maximum likelihood estimator in sub-linear time. Extensive experimentation in standard testbeds for robotics control problems show that the proposed algorithm achieves superior performance compared with other IRL and imitation learning approaches. In future work we will consider extensions of the proposed algorithm when a model of the state dynamics is not available and thus must also be estimated.