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.
107,178 characters · 29 sections · 125 citation commands
An Empirical Risk Minimization Approach for Offline Inverse RL and Dynamic Discrete Choice Model
Keywords: Dynamic Discrete Choice, Offline Inverse Reinforcement Learning, Gradient-based methods, Empirical Risk Minimization, Neural Networks
Learning from previously collected datasets has become an essential paradigm in sequential decision-making problems where exploration during interactions with the environment is infeasible (e.g., self-driving cars, medical applications) or leveraging large-scale offline data is preferable (e.g., social science, recommendation systems, and industrial automation) levine2020offline. However, in such cases, defining a reward function (a flow utility function) that accurately captures the underlying decision-making process is often challenging due to the unobservable/sparse rewards zolna2020offline and complexity of real-world environments foster2021offline. To circumvent these limitations, learning from expert demonstrations has gained prominence, motivating approaches such as Imitation Learning (IL) and offline Inverse Reinforcement Learning (offline IRL) or equivalently, Dynamic Discrete Choice (DDC) model estimation\footnote{Refer to Section (ref) for the equivalence between Offline Maximum Entropy IRL (MaxEnt-IRL) and DDC.}.
While IL directly learns a policy by mimicking expert actions, it is susceptible to distribution shift, i.e., when the testing environment (reward, transition function) is different from the training environment. On the other hand, offline IRL (or DDC) aims to infer the underlying reward function that best explains expert behavior. Given that this reward function is identified under a suitable normalization assumption, a new policy can be trained after a change in the environment's transition dynamics (e.g., modifications in recommendation systems) or in the reward function (e.g., marketing interventions). This capability enables offline IRL (or DDC) to be employed in counterfactual simulations, such as evaluating the effects of different policy decisions without direct experimentation. However, an imprecise reward function can lead to suboptimal policy learning and unreliable counterfactual analyses, ultimately undermining its practical utility. As a result, offline IRL (or DDC)'s key metric becomes the precision of reward inference.
While the precise reward function estimation objective has been studied in recent offline IRL literature, theoretically guaranteed existing methods that satisfy the Bellman equation have been limited to explicitly learning a transition model (e.g., zeng2023understanding). However, the statistical complexity for learning a transition model increases exponentially as the state dimension increases. Furthermore, if relearning the transition function is required every time it changes, the premise of IRL for counterfactual simulations may be undermined. In addition, the errors from the transition function estimation can propagate and compound in the later estimation stage. The Dynamic Discrete Choice (DDC) literature in econometrics has separately explored the problem towards the goal of precise reward estimation rust1994structural, hotz1993conditional, aguirregabiria2007sequential, su2012constrained, adusumilli2019temporal, kristensen2021solving, geng2023data. However, existing methodologies with theoretical precision guarantees suffer from the curse of dimensionality (computational or statistical complexity exponentially grows as state dimension increases kristensen2021solving) or algorithmic instability beyond linear reward functions adusumilli2019temporal. This motivates us to ask the following question:
Our contributions. In this paper, we propose an Empirical Risk Minimization (ERM)--based gradient-based method for IRL/DDC as an inverse Q-learning method. This method provably finds the true parameter $\boldsymbol{\theta}$ for $Q^*$ estimation (up to statistical error, which diminishes at an $O(N^{-1/2})$ rate with $N$ samples) with $O(T^{-1/4})$ rate of convergence, where $T$ is the number of gradient iterations. In addition, the true reward function can be computed from the estimated $Q^\ast$ with no extra statistical or computational cost, given the estimated $Q^\ast$ function. In developing this method, we make the following technical contributions:
In addition to establishing theoretical global convergence guarantees, we demonstrate the empirical effectiveness of the algorithm through standard benchmark simulation experiments. Specifically, we evaluate using a series of simulations: (1) The Rust bus engine replacement problem rust1987optimal, which is the standard framework for evaluation used in the dynamic discrete choice literature, and (2) A high-dimensional variant of the Rust bus-engine problem, where we allow a very large state space. In both settings, we show that our algorithm outperforms/matches the performance of existing approaches. It is particularly valuable in large state-space settings, where many of the standard algorithms become infeasible due to their need to estimate state-transition probabilities. We expect our approach to be applicable to a variety of business and economic problems where the state and action space are infinitely large, and firms/policy-makers do not have {\it a priori} knowledge of the parametric form of the reward function and/or state transitions.
The remainder of the paper is organized as follows. In Section (ref), we discuss related work in greater detail. Section (ref) introduces the problem setup and provides the necessary background. In Section (ref), we present the ERM-IRL framework, followed by an algorithm for solving it in Section (ref). Section (ref) establishes the global convergence guarantees of the proposed algorithm. Finally, Section (ref) presents experimental results demonstrating the effectiveness of our approach.
The formulations of DDC and (Maximum Entropy) IRL are fundamentally equivalent (see Section (ref) for details). In the econometrics literature, stochastic decision-making behaviors are usually considered to come from the random utility model mcfadden2001economic, which assumes that the effect of unobserved covariates appears in the form of additive and conditionally independent randomness in agent utilities rust1994structural. On the other hand, in the computer science literature, stochastic decision-making behaviors are modeled as a `random choice'. That is, the assumption is that agents play a stochastic strategy (where they randomize their actions based on some probabilities). This model difference, however, is not a critical differentiator between the two literatures. The two modeling choices yield equivalent optimality equations, meaning that the inferred rewards are identical under both formulations ermon2015learning.
The main difference between DDC and IRL methods stems from their distinct objectives. DDC's objective is to estimate the exact reward function that can be used for subsequent counterfactual policy simulations (e.g., sending a coupon to a customer to change their reward function). Achieving such strong identifiability necessitates a strong anchor action assumption (Assumption (ref)). A direct methodological consequence of this pursuit for an exact function is the requirement to solve the Bellman equation, which in turn causes significant scalability issues. On the other hand, IRL's objective is to identify a set of reward functions that are compatible with the data. This allows for a weaker identification assumption ng1999policy than DDC's assumption (Assumption (ref)) and avoids the computational burden inherent in the DDC framework caused by the Bellman equation.
Table (ref) compares DDC and IRL methods based on several characteristics, which are defined here as they correspond to the table's columns. The first set of characteristics is typically satisfied by IRL methods but not by DDC methods with global optimality. One-shot optimization indicates that a method operates on a single timescale without requiring an inner optimization loop or inner numerical integration like forward roll-outs. Transition Estimation-Free signifies that the method avoids the explicit estimation of a transition function. A method is considered Gradient-based if its primary optimization process relies on gradient descent, and Scalable if it can handle state spaces of at least $20^{10}$.
Conversely, a different set of characteristics is often satisfied by DDC methods. The Bellman equation criterion is met if the estimation procedure fits the estimated $r$-function or $Q^\ast$-function to the Bellman equation; this definition excludes occupancy-matching methods (e.g., IQ-Learn garg2021iq, Clare yue2023clare; see Appendix (ref)) and the semi-gradient method adusumilli2019temporal, which minimizes the projected squared Bellman error for linear value functions sutton2018reinforcement. Global optimality refers to a theoretical guarantee of convergence to the globally optimal $r$ or $Q^\ast$ beyond linear value function approximation. The $\triangle$ symbol indicates a conditional guarantee; for instance, Approximate Value Iteration (AVI) adusumilli2019temporal is marked with a $\triangle$ due to the known instability of fitted fixed-point methods beyond the linear reward/value class wang2021instabilities,jiangoffline. ML-IRL is also marked with a $\triangle$ because its guarantee applies only to linear reward functions. For methods that achieve global optimality, the table also lists their sample complexity. A rate of $1 / \sqrt{N}$ implies that the estimated parameter $\hat{\boldsymbol{\theta}}$ converges to the true parameter $\boldsymbol{\theta}^\ast$ at that rate, where $N$ is the sample size.
The seminal paper by Rust rust1987optimal pioneered this literature, demonstrating that a DDC model can be solved by solving a maximum likelihood estimation problem that runs above iterative dynamic programming. As previously discussed, this method is computationally intractable as the size of the state space increases.
hotz1993conditional introduced a method which is often called the two-step method conditional choice probability (CCP) method, where the CCPs and transition probabilities estimation step is followed by the reward estimation step. The reward estimation step avoids dynamic programming by combining simulation with the insight that differences in value function values can be directly inferred from data without solving Bellman equations. However, simulation methods are, in principle, trajectory-based numerical integration methods that also suffer scalability issues. Fortunately, we can sometimes avoid simulation altogether by utilizing the problem structure, such as regenerative/terminal actions (known as finite dependence arcidiacono2011conditional). Still, this method requires explicit estimation of the transition function, which is not the case in our paper. This paper established an insight that there exists a one-to-one correspondence between the CCPs and the differences in $Q^*$-function values, which was formalized as the identification result by magnac2002identifying.
su2012constrained propose that we can avoid dynamic programming or simulation by formulating a nested linear programming problem with Bellman equations as constraints of a linear program. This formulation is based on the observation that Bellman equations constitute a convex polyhedral constraint set. While this linear programming formulation significantly increases the computation speed, it is still not scalable in terms of state dimensions.
As the above methods suffer scalability issues, methods based on parametric/nonparametric approximation have been developed. Parametric policy iteration benitez2000comparison and sieve value function iteration arcidiacono2013approximating parametrize the value function by imposing a flexible functional form. kristensen2021solving also proposed methods that combine smoothing of the Bellman operator with sieve-based approximations, targeting the more well-behaved integrated or expected value functions to improve computational performance. However, standard sieve methods that use tensor product basis functions, such as polynomials, can suffer from a computational curse of dimensionality, as the number of basis functions required for a given accuracy grows exponentially with the number of state variables. norets2012estimation proposed that neural network-based function approximation reduces the computational burden of Markov Chain Monte Carlo (MCMC) estimation, thereby enhancing the efficiency and scalability. Also leveraging Bayesian MCMC techniques, imai2009bayesian developed an algorithm that integrates the DP solution and estimation steps, reducing the computational cost associated with repeatedly solving the underlying dynamic programming problem to be comparable to static models, though it still requires transition probabilities for calculating expectations. arcidiacono2016estimation formulates the problem in continuous time, where the sequential nature of state changes simplifies calculations. However, these continuous-time models still rely on specifying transition dynamics via intensity matrices. geng2020deep proposed that the inversion principle of hotz1993conditional enables us to avoid reward parameterization and directly (non-parametrically) estimate value functions, along with solving a much smaller number of soft-Bellman equations, which do not require reward parametrization to solve them. barzegary2022recursive and geng2023data independently proposed state aggregation/partition methods that significantly reduce the computational burden of running dynamic programming with the cost of optimality. While geng2023data uses $k$-means clustering kodinariya2013review, sinaga2020unsupervised, barzegary2022recursive uses recursive partitioning (RP). As discussed earlier, combining approximation with dynamic programming induces unstable convergence except when the value function is linear in state jiangoffline.
adusumilli2019temporal proposed how to adapt two popular temporal difference (TD)-based methods (an approximate dynamic programming-based method and a semi-gradient descent method based on tsitsiklis1996analysis) for DDC. As discussed earlier, approximate dynamic programming-based methods are known to suffer from a lack of provable convergence beyond linear reward models jiangoffline, tsitsiklis1996feature, van2018deep, wang2021instabilities\footnote{In fact, “fitted fixed point methods can diverge even when all of the following hold: infinite data, perfect optimization with infinite computation, 1-dimensional function class (e.g., linear) with realizability (Assumption (ref))... (the instability is) not merely a theoretical construction: deep RL algorithms are known for their instability and training divergence...” jiangoffline}; the semi-gradient method is a popular, efficient approximation method that has theoretical assurance of convergence to projected squared Bellman error minimizers for linear reward/value functions sutton2018reinforcement. feng2020global showed global concavity of value function under certain transition functions and monotonicity of value functions in terms of one-dimensional state, both of which are easily satisfied for applications in social science problems. However, those conditions are limitedly satisfied for the problems with larger dimensional state space.
\; The most widely used inverse reinforcement learning model, Maximum-Entropy inverse reinforcement learning (MaxEnt-IRL), assumes that the random choice happens due to agents choosing the optimal policy after penalization of the policy by its Shannon entropy ermon2015learning. In addition to the equivalence of MaxEnt-IRL to DDC (See ermon2015learning and Web Appendix $\S$(ref)), the identifiability condition for DDC magnac2002identifying was rediscovered by cao2021identifiability for MaxEnt-IRL. zeng2023understanding proposes a two-step maximum likelihood-based method that can be considered as a conservative version of CCP method of hotz1993conditional\footnote{When there is no uncertainty in the transition function, approximated trajectory gradient of Offline IRL method degenerates to forward simulation-based gradient in CCP estimator method of hotz1993conditional.}. Despite that their method is proven to be convergent, it requires the explicit estimation of the transition function, and its global convergence was only proven for linear reward functions.
finn2016connection showed that a myopic\footnote{See cao2021identifiability for more discussion on this.} version of MaxEnt-IRL can be solved by the Generative Adversarial Network (GAN) training framework goodfellow2020generative. fu2017learning extended this framework to a non-myopic version, which is proven to recover the reward function and the value function (up to policy invariance) but only under deterministic transitions. Note that GAN approaches identify rewards only up to policy invariance ng1999policy, which implies that counterfactual analysis is impossible. The GAN approach has been extended to $Q$-estimation methods that use fixed point iteration geng2020deep, geng2023data. ni2021f has shown that the idea of training an adversarial network can also be used to calculate the gradient direction for minimizing the myopic version of negative log likelihood\footnote{Minimizing negative log-likelihood is equivalent to minimizing KL divergence. See the Proof of Lemma (ref).}. zhan2024model proposed a GAN approach that is provably equivalent to negative log likelihood minimization objective without satisfying the Bellman equation (i.e., behavioral cloning torabi2018behavioral). Indeed, GAN approaches are known to work well for Imitation Learning (IL) tasks zare2024survey. However, as discussed earlier, solving for IL does not allow us to conduct a counterfactual simulation.
A family of methods starting from ho2016generative tries to address the inverse reinforcement learning problem from the perspective of occupancy matching, i.e., finding a policy that best matches the behavior of data. garg2021iq proposed how to extend the occupancy matching approach of ho2016generative to directly estimate $Q$-function instead of $r$. Given the assumption that the Bellman equation holds, this approach allows a simple gradient-based solution, as the occupancy matching objective function they maximize becomes concave. yue2023clare modifies ho2016generative to conservatively deal with the uncertainty of transition function. Recently, occupancy matching-based inverse reinforcement learning has been demonstrated at a planetary scale in Google Maps, delivering significant global routing improvements barnes2023massively. Despite their simplicity and scalability, one caveat of occupancy matching approaches is that the estimated $Q$ from solving the occupancy matching objective may not satisfy the Bellman equation (See Appendix (ref)). This also implies that computing $r$ from $Q$ using the Bellman equation is not a valid approach.
We consider a single-agent Markov Decision Process (MDP) defined as a tuple $\left(\mathcal{S}, \mathcal{A}, P, \nu_0, r, \beta\right)$ where $\mathcal{S}$ denotes the state space and $\mathcal{A}$ denotes a finite action space, $P \in \Delta_{\mathcal{S}}^{\mathcal{S} \times \mathcal{A}}$ is a Markovian transition kernel, $\nu_0 \in \Delta_{\mathcal{S}}$ is the initial state distribution over $\mathcal{S}$, $r \in \mathbb{R}^{\mathcal{S} \times \mathcal{A}}$ is a deterministic reward function and $\beta \in(0,1)$ a discount factor. Given a stationary Markov policy $\pi \in \Delta_{\mathcal{A}}^{\mathcal{S}}$, an agent starts from initial state $s_0$ and takes an action $a_h\in \mathcal{A}$ at state $s_h\in \mathcal{S}$ according to $a_h\sim\pi\left(\cdot \mid s_h\right)$ at each period $h$. Given an initial state $s_0\sim \nu_0$, we define the distribution of state-action sequences for policy $\pi$ over the sample space $(\mathcal{S} \times \mathcal{A})^{\infty}=\left\{\left(s_0, a_0, s_1, a_1, \ldots\right): s_h \in \mathcal{S}, a_h \in \mathcal{A}, h \in \mathbb{N}\right\}$ as $\mathbb{P}_{\nu_0,\pi}$. We also use $\mathbb{E}_{\nu_0,\pi}$ to denote the expectation with respect to $\mathbb{P}_{\nu_0,\pi}$.
Following existing literature geng2020deep, fu2017learning, ho2016generative, we consider the entropy-regularized optimal policy, which is defined as
where $\mathcal{H}$ denotes the Shannon entropy and $\lambda$ is the regularization coefficient. Throughout, we make the following assumption on the agent's decisions.
Throughout the paper, we use $\lambda = 1$, the setting which is equivalent to dynamic discrete choice (DDC) model with mean zero T1EV distribution (see Web Appendix $\S$(ref) for details); all the results of this paper easily generalize to other values of $\lambda$. Given $\pi^*$, we define the value function $V^*$ as: $$ V^*(s) := \mathbb{E}_{\pi^*} \biggl[\sum_{h=0}^\infty \beta^h \bigl(r(s_h, a_h) + \mathcal{H}(\pi^*(\cdot \mid s_h))\bigr) \biggm| s_0 = s\biggr]. $$ Similarly, we define the $Q^*$ function as follows: $$Q^*(s, a):=r\left(s, a\right)+\beta \cdot \mathbb{E}_{s^\prime \sim P(s,a)}\left[{V}^*\left(s^\prime\right)\mid s, a\right]$$ Given state $s$ and policy $\pi^*$, let $\mathbf{q} = [q_1 \ldots q_{|\mathcal{A}|}]$ denote the probability distribution over the action space $\mathcal{A}$, such that:
Then, according to Assumption (ref), the value function $V^*$ must satisfy the recursive relationship defined by the Bellman equation as follows:
Further, we can show that (see Web Appendix $\S$(ref)):
Throughout, we define a function $V_Q$ as
where $ V_{Q^\ast} = V^\ast$.
Following the literature rust1994structural, magnac2002identifying, we assume that the reward the agent observes at state $s\in\mathcal{S}$ and $a\in\mathcal{A}$ can be expressed as $r(s,a) + \epsilon_a$, where $\epsilon_a\overset{i.i.d.}{\sim} G(\delta, 1)$ is the random part of the reward, where $G$ is Type 1 Extreme Value (T1EV) distribution (i.e., Gumbel distribution)\footnote{This reward form is often referred to as additive and conditionally independent form.}. The mean of $G(\delta, 1)$ is $\delta + \gamma$, where $\gamma$ is the Euler constant. Throughout the paper, we use $\delta=-\gamma$, which makes $G$ a mean 0 distribution.\footnote{All the results of this paper easily generalize to other values of $\delta$.} Under this setup, we consider the optimal stationary policy and its corresponding value function defined as $$\pi^\ast:=\operatorname{argmax}_{\pi \in \Delta_{\mathcal{A}}^{\mathcal{S}}}\mathbb{E}_{\nu_0,\pi,G}\left[\sum_{h=0}^{\infty} \beta^h( r\left(s_h, a_h\right)+\epsilon_{a_h})\right]$$ $$V^\ast(s):=\operatorname{max}_{\pi \in \Delta_{\mathcal{A}}^{\mathcal{S}}}\mathbb{E}_{\nu_0,\pi,G}\left[\sum_{h=0}^{\infty} \beta^h( r\left(s_h, a_h\right)+\epsilon_{a_h})\mid s_0=s\right]$$ Throughout, we make the following assumption on agent's decisions.
According to Assumption (ref), the value function $V^\ast$ must satisfy the recursive relationship, often called the Bellman equation, as follows:
where the second equality is from Lemma (ref). We further define the $Q^\ast$ function as $$ Q^*(s, a):=r(s, a)+\beta \cdot \mathbb{E}_{s^{\prime} \sim P(s, a)}\left[V^*\left(s^{\prime}\right) \mid s, a\right] $$ We can show that (see Web Appendix $\S$(ref)):
The Bellman equations of MaxEnt-IRL with \(\lambda = 1\) (Equation (ref)) and DDC with \(\delta = -\gamma\) (Equation (ref)) are equivalent. Consequently, the optimal \(Q^*\) values obtained from solving these Bellman equations are the same for both MaxEnt-IRL and DDC. Furthermore, the optimal policy induced by \(Q^*\) is identical in both frameworks. Therefore, we can infer that solving one problem is equivalent to solving the other. Throughout, all the discussions we make for \(\lambda = 1\) in MaxEnt-IRL and \(\delta = -\gamma\) in DDC extend directly to any \(\lambda \neq 1\) and \(\delta \neq -\gamma\), respectively. This equivalence is a folk theorem that was first observed in ermon2015learning.
In both settings, the goal is to recover the underlying reward function $r$ that explains an agent's demonstrated behavior. Given the equivalence between them, we can now formulate a unified problem statement that encompasses both Offline Maximum Entropy Inverse Reinforcement Learning (Offline MaxEnt-IRL) and the Dynamic Discrete Choice (DDC) model estimation.
To formalize this, consider a dataset consisting of state-action-next state sequences collected from an agent's behavior: $\mathcal{D}:=\left(\left(s_0, a_0, s_0^\prime\right), \left(s_1, a_1,s_1^\prime\right), \ldots, \left(s_N, a_N,s_N^\prime\right)\right)$. Following Assumption (ref), we assume that the data was generated by the agent playing the optimal policy $\pi^*$ when interacting with the MDP $\left(\mathcal{S}, \mathcal{A}, P, \nu_0, r, \beta\right)$.
Restricting to \(\bar{\mathcal{S}}\) is essential, as the dataset \(\mathcal{D}\) only contains information about states visited under \(\pi^*\). Inferring rewards beyond this set would be ill-posed due to a lack of data, making \(\bar{\mathcal{S}}\) the natural domain for learning. Similarly, Computing MSE using the expert policy's state-action distribution is natural since the goal is to recover the reward function that explains the expert’s behavior. \\ \; \\ \noindentRemark (Counterfactual policy optimization without estimating $P$). Given logged interaction data \(\mathcal{D} = \{(s_i, a_i, s'_i)\}_{i=1}^N\) and a recovered reward function \(\hat{r}\), suppose the analyst wishes to evaluate the effect of a counterfactual intervention on the reward—e.g., modifying incentives or preferences—which induces a new estimated reward function \(\hat{r}_{\mathrm{cf}}(s, a)\), such as $ \hat{r}_{\mathrm{cf}}(s, a)=\hat{r}(s, a)+\Delta(s, a) $, where $\Delta$ encodes the intervention. Using the augmented dataset $$ \hat{\mathcal{D}}_{\mathrm{cf}}=\left\{\left(s_i, a_i, \hat{r}_{\mathrm{cf}}\left(s_i, a_i\right), s_i^{\prime}\right)\right\}_{i=1}^N, $$ any standard modern offline-RL algorithm (e.g., Conservative Q-Learning kumar2020conservative) can be applied to $\hat{\mathcal{D}}_{\mathrm{cf}}$ to obtain the counterfactual optimal policy without requiring an explicit estimate of the transition function $P$. These methods operate via empirical Bellman backups over observed transitions and are fully model-free.
In contrast, when the counterfactual intervention alters the $P$ itself, one must estimate $P$, model the intervention accordingly, and perform model-based planning (e.g., sutton2018reinforcement).
As we defined in Definition (ref), our goal is to learn the agent's reward function $r(s, a)$ given offline data $\mathcal{D}$. However, without additional assumptions on the reward structure, this problem is ill-defined because many reward functions can explain the optimal policy fu2017learning, ng1999policy. To address this issue, following the DDC literature rust1994structural, magnac2002identifying, hotz1993conditional and recent IRL literature geng2020deep, we assume that there is an anchor action $a_s$ in each state $s$, such that the reward for each of state-anchor action combination is known.
Note that the optimal policy remains the same irrespective of the choice of the anchor action $a_s$ and the reward value at the anchor action $r(s, a_s)$ (at any given $s$). As such, Assumption (ref) only helps with identification and does not materially affect the estimation procedure. That is, for the sake of choosing an arbitrary reward function that is compatible with the optimal policy (i.e., the IRL objective), an arbitrary choice of $a_s$ and the $r(s,a_s)$ value is justified.
In Lemma (ref), we formally establish that Assumptions (ref) and (ref) uniquely identify $Q^\ast$ and $r$. See Web Appendix $\S$(ref) for the proof.
In the first part of the theorem, we show that, after constraining the reward functions for anchor actions, we can recover the unique $Q^\ast$-function for the optimal policy from the observed choices and the Bellman equation for the anchor-action (written in terms of log-sum-exp of $Q$-values). The second step follows naturally, where we can show that reward functions are then uniquely recovered from $Q^*$-functions using the Bellman equation.
There are two key concepts used for describing a gradient-based algorithm for IRL/DDC: the Bellman error and the Temporal Difference (TD) error. In this section, we define each of them and discuss their relationship. We start by defining $\mathcal{Q}=\left\{Q: \mathcal{S} \times \mathcal{A} \rightarrow \mathbb{R} \mid\|Q\|_{\infty}<\infty\right\}$. By rust1994structural, $\beta<1$ (discount factor less than one) implies $Q^* \in \mathcal{Q}$. Next, we define the Bellman operator as $\mathcal{T}: \mathcal{Q} \mapsto \mathcal{Q}$ as follows: $$\mathcal{T}Q(s, a) \notag := r(s, a) + \beta \cdot \mathbb{E}_{s' \sim P(s, a)} \bigl[ V_Q(s') \bigr] $$ According to the Bellman equation shown in Equation (ref), $Q^*$ satisfies $\mathcal{T}Q^*(s, a) - Q^*(s, a)=0$; in fact, $Q^*$ is the unique solution to $\mathcal{T}Q(s, a) - Q(s, a)=0$; see rust1994structural. Based on this observation, we define the following notions of error.
In practice, we don't have direct access to $\mathcal{T}$ unless we know (or have a consistent estimate of) the transition kernel $P\in\Delta_\mathcal{S}^{\mathcal{S}\times\mathcal{A}}$. Instead, we can compute an empirical Sampled Bellman operator $\hat{\mathcal{T}}$, defined as $$ \hat{\mathcal{T}}Q(s, a, s') = r(s, a) + \beta \cdot V_Q(s^\prime). $$
Lemma (ref) states the relationship between the TD error terms and Bellman error terms.
Given Lemma (ref), we would like to find the unique $\hat{Q}$ that satisfies
where $\bar{\mathcal{S}}$ (the reachable states from $\nu_0$, $\pi^\ast$) was defined as: $$ \bar{\mathcal{S}}=\left\{s \in \mathcal{S} \mid \operatorname{Pr}\left(s_t=s \mid s_0 \sim \nu_0, \pi^*\right)>0 \text { for some } t \geq 0\right\} $$ Now note that:
and
Therefore equations (ref) becomes
We now propose a one-shot Empirical Risk Minimization framework (ERM-IRL/ERM-DDC) to solve the Equation (ref). First, we recast the IRL problem as the following expected risk minimization problem under an infinite data regime.
\noindentRemark. The joint minimization of the Negative Log Likelihood (NLL) term and Bellman Error (BE) term is the key novelty in our approach. Prior work on the IRL and DDC literature hotz1993conditional, zeng2023understanding typically minimizes the log-likelihood of the observed choice probabilities (the NLL term), given observed or estimated state transition probabilities. The standard solution is to first estimate/assume state transition probabilities, then obtain estimates of future value functions, plug them into the choice probability, and then minimize the NLL term. In contrast, our recast problem avoids the estimation of state-transition probabilities and instead jointly minimizes the NLL term along with the Bellman error term. This is particularly helpful in large state spaces since the estimation of state-transition probabilities can be infeasible/costly in such settings. In Theorem (ref), we show that the solution to our recast problem in Equation (ref) identifies the reward function.
Essentially, Theorem (ref) ensures that solving Equation (ref) gives the exact $r$ and $Q^\ast$ up to $\bar{\mathcal{S}}$ and thus provides the solution to the DDC/IRL problem defined in Definition (ref).
Having established the identification guarantees for the ERM-IRL/DDC framework, it is natural to compare this formulation to the identification properties of Imitation Learning (IL) torabi2018behavioral, rajaraman2020toward, foster2024behavior. Unlike IRL, which seeks to infer the underlying reward function that explains expert behavior, IL directly aims to recover the expert policy without modeling the transition dynamics. The objective of imitation learning is often defined as finding a policy $\hat{p}$ with $\min _{\hat{p}} \mathbb{E}_{(s, a) \sim \pi^\ast, \nu_0}\left[\ell\left(\hat{p}(a \mid s), \pi^\ast(a \mid s)\right)\right]$, $\ell$ is the cross-entropy loss or equivalently,
Equation (ref) is exactly what a typical Behavioral Cloning (BC) torabi2018behavioral minimizes under entropy regularization, as the objective of BC is
where $\hat{p}_Q(a\mid s) = \frac{Q(s,a)}{\sum_{\tilde{a}\in\mathcal{A} }Q(s,\tilde{a})}$. Note that the solution set of Equation (ref) fully contains the solution set of Equation (ref), which identifies the $Q^\ast$ for offline IRL/DDC. This means that any solution to the offline IRL/DDC problem also minimizes the imitation learning objective, but not necessarily vice versa. Consequently, under entropy regularization, the IL objective is fundamentally easier to solve than the offline IRL/DDC problem, as it only requires minimizing the negative log-likelihood term without enforcing Bellman consistency. One of the key contributions of this paper is to formally establish and clarify this distinction: IL operates within a strictly simpler optimization landscape than the offline IRL/DDC, making it a computationally and statistically more tractable problem. This distinction further underscores the advantage of Behavioral Cloning (BC) over ERM-IRL/DDC for imitation learning (IL) tasks-—since BC does not require modeling transition dynamics or solving an optimization problem involving the Bellman residual, it benefits from significantly lower computational and statistical complexity, making it a more efficient approach for IL.
While behavioral cloning (BC) is often sufficient for IL foster2024behavior, i.e., reproducing the expert’s actions under the same dynamics and incentive structure, it fundamentally lacks the ingredients needed for counterfactual reasoning. Because BC learns a direct mapping $s \mapsto a$ without ever inferring the latent reward $r(s,a)$, it has no principled way to predict what an expert would do if (i) the transition kernel $P$ were perturbed (e.g., a new recommendation algorithm) or (ii) the reward landscape itself were altered (e.g., a firm introduces monetary incentives). In such scenarios the state–action pairs generated by the expert no longer follow the original occupancy measure, so a cloned policy is forced to extrapolate outside its training distribution—precisely where imitation learning is known to fail.
Recovering the reward resolves this limitation. Once we have a consistent estimate $\hat r$ (or, equivalently, $\hat Q^{\ast}$), we can decouple policy evaluation from the historical data: any hypothetical change to $P$ or the reward can be encoded and handed to a standard offline RL, which recomputes the optimal policy for the new MDP without further demonstrations. In other words, rewards serve as a portable, mechanism‑level summary of preferences that supports robust counterfactual simulation, policy optimization, and welfare analysis—capabilities that pure imitation methods cannot provide.
While the idea of expected risk minimization -- minimizing Equation (ref) -- is straightforward, empirically approximating $\mathcal{L}_{B E}(Q)(s, a) = (\mathcal{T} Q(s, a)-Q(s, a))^2$ and its gradient is quite challenging. As discussed in Section (ref), $\mathcal{T}Q$ is not available unless we know the transition function. As a result, we have to rely on an estimate of $\mathcal{T}$. A natural choice, common in TD-methods, is $\hat{\mathcal{T}} Q\left(s, a, s^{\prime}\right)=r(s, a)+\beta \cdot V_Q(s^\prime)$ which is computable given $Q$ and data $\mathcal{D}$. Thus, a natural proxy objective to minimize is:
Temporal Difference (TD) methods typically use stochastic approximation to obtain an estimate of this proxy objective tesauro1995temporal, adusumilli2019temporal. However, the issue with TD methods is that minimizing the proxy objective will not minimize the Bellman error in general (see Web Appendix $\S$(ref) for details), because of the extra variance term, as shown below.
As defined, $\hat{\mathcal{T}}$ is a one-step estimator, and the second term in the above equation does not vanish even in infinite data regimes. So, simply using the TD approach to approximate squared Bellman error provides a biased estimate. Intuitively, this problem happens because expectation and square are not exchangeable, i.e., $\mathbb{E}_{ s^\prime \sim P(s, a)}\left[\delta_{Q}\left(s,a, s^\prime\right)\mid s, a\right]^2 \neq \mathbb{E}_{ s^\prime \sim P(s, a)}\left[\delta_{Q}\left(s,a, s^\prime\right)^2\mid s, a\right]$. This bias in the TD approach is a well-known problem called the double sampling problem munos2003error, lagoudakis2003least,sutton2018reinforcement, jiangoffline. To remove this problematic square term, we employ an approach often referred to as the “Bi-Conjugate Trick” antos2008learning, dai2018sbeed, patterson2022generalized which replaces a square function with a linear function called the bi-conjugate:
By further re-parametrizing $h$ using $\zeta = h - r(s,a) + Q(s,a)$, after some algebra, we arrive at Lemma (ref). See Web Appendix $\S$(ref) for the detailed derivation.
The reformulation of $\mathcal{L}_{BE}$ proposed in Lemma (ref) enjoys the advantage of minimizing the squared TD-error ($\mathcal{L}_{TD}$) but without bias. Combining Theorem (ref) and Lemma (ref), we arrive at the following Theorem (ref), which gives the expected risk minimization formulation of IRL we propose.
Equation (ref) in Theorem (ref) is a mini-max problem in terms of $Q\in\mathcal{Q}$ and the introduced dual function $\zeta\in \mathbb{R}^{S\times A}$. To summarize, term 1) is the negative log-likelihood equation, term 2) is the TD error, and term 3) introduces a dual function $\zeta$. The introduction of the dual function $\zeta$ in term 3) may seem a bit strange. In particular, note that $\arg\max_{\zeta \in \mathbb{R}} -\mathbb{E}_{s^{\prime} \sim P(s, a)}\left[\left(V_Q\left(s^{\prime}\right)-\zeta\right)^2 \mid s, a\right]$ is just $\zeta = \mathbb{E}_{s'\sim P(s,a)}[V\left(s^{\prime}\right)|s,a]$. However, we do not have access to the transition kernel and the state and action spaces may be large. Instead, we think of $\zeta$ as a function of states and actions, $\zeta(s,a)$ as introduced in Lemma (ref). This parametrization allows us to optimize over a class of functions containing $\zeta(s,a)$ directly.
Given that the minimax resolution for the expected risk minimization problem in Theorem (ref) finds $Q^\ast$ under an infinite number of data, we now discuss the case when we are only given a finite dataset $\mathcal{D}$ instead. For this, let's first rewrite the Equation (ref) as
where $\widetilde{\zeta} \in \operatorname{argmin}_{\zeta\in \mathbb{R}^{S\times A}}\mathbb{E}_{(s, a) \sim \pi^*, \nu_0, s^{\prime} \sim P(s, a)}\bigl[\mathbf{1}_{a=a_s} \bigl\{\left(V_{Q}\left(s^{\prime}\right)-\zeta(s,a)\right)^2 \bigr\}\bigr]$. But such $\widetilde{\zeta}$ also satisfies $\widetilde{\zeta}\in \operatorname{argmin}_{\zeta\in \mathbb{R}^{S\times A}}\mathbb{E}_{(s, a) \sim \pi^*, \nu_0, s^{\prime} \sim P(s, a)}\bigl[ \left(V_{Q}\left(s^{\prime}\right)-\zeta(s,a)\right)^2 \bigr] $, because
Substituting Equation (ref) and Equation (ref)'s expectation over the data distribution with the empirical mean over the data, we arrive at the empirical risk minimization formulation defined in Definition (ref).
As formulated in Equation (ref), our empirical risk minimization objective is a minimax optimization problem that involves inner maximization over $\zeta$ and outer minimization over $Q$. This structure is a direct consequence of introducing the dual function $\zeta$ to develop an unbiased estimator, thereby circumventing the double sampling problem discussed previously. In the next section, we introduce GLADIUS, a practical, alternating gradient ascent-descent algorithm specifically designed to solve this minimax problem and learn the underlying reward function from the data.
Algorithm (ref) solves the empirical risk minimization problem in Definition (ref) through an alternating gradient ascent descent algorithm we call Gradient-based Learning with Ascent-Descent for Inverse Utility learning from Samples (GLADIUS). Given the function class $\mathcal{Q}$ of value functions, let $Q_{\boldsymbol{\theta}_2}\in\mathcal{Q}$ and $\zeta_{\boldsymbol{\theta}_1}\in\mathbb{R}^{S\times A}$ denote the functional representation of $Q$ and $\zeta$. Our goal is to learn the parameters $\boldsymbol{\theta}^*= \{\boldsymbol{\theta}_1^*, \boldsymbol{\theta}_2^* \}$, that together characterize $\hat{Q}$ and $\hat{\zeta}$. Each iteration in the GLADIUS algorithm consists of the following two steps:
Note that $\mathcal{D}$ can be used instead of using batches $B_1$ and $B_2$; the usage of batches is to keep the computational/memory complexity $O(|B_1=B_2|)$ instead of $O(|\mathcal{D}|)$.
After a fixed number of gradient steps of $Q_{\boldsymbol{\theta}_1}$ and $\zeta_{\boldsymbol{\theta}_2}$ (which we can denote as $\hat{Q}$ and $\hat{\zeta}$), we can compute the reward prediction $\hat{r}$ as $\hat{r}(s,a) = \hat{Q}(s,a) - \beta \hat{\zeta}(s,a)$ due to Theorem (ref).
When the transition function is deterministic (e.g., in rafailov2024r, guo2025deepseek, zhong2024dpo) meaning that for any state-action pair \((s, a)\), the next state \(s'\) is uniquely determined, the ascent step involving \(\zeta\) is no longer required. This is because the term \(\left(V_{Q}\left(s^{\prime}\right)-\zeta(s,a)\right)^2\) (highlighted in orange in Equation (ref) and (ref)) becomes redundant in the empirical ERM-IRL objective, because $\max_{\zeta \in \mathbb{R}} -\mathbb{E}_{s^{\prime} \sim P(s, a)}\left[\left(V_Q\left(s^{\prime}\right)-\zeta\right)^2 \mid s, a\right]$ is always $0$. Consequently, the optimization simplifies to:
Under deterministic transitions, the GLADIUS algorithm reduces to gradient descents for \( Q_{\boldsymbol{\theta}} \), eliminating the need for the alternating ascent-descent update steps. Consequently, the estimated reward function is computed as:
Key Differences in the Deterministic Case:
This modification makes GLADIUS computationally more efficient when applied to deterministic environments while maintaining the correct theoretical formulation of the $Q^\ast$ and reward functions.
This section establishes the optimization guarantees used by GLADIUS. The empirical objective in Equation (ref) is a minimax problem: for fixed $Q$, the auxiliary block $\zeta$ is a least-squares regression target and the corresponding maximization problem is strongly concave, while the $Q$-block is generally nonconvex because of the Bellman residual term bas2021logistic. Our analysis therefore does not rely on convexity of the $Q$-objective. Instead, we show that the empirical $Q$-objective and the auxiliary regression objective satisfy Polyak-\Lojasiewicz (PL) inequalities under an empirical Jacobian conditioning condition.
The result is formulated for continuous state spaces and finite action spaces. The state space $\mathcal S$ is not discretized. The finite-dimensional matrices that appear below arise only because the empirical objective evaluates $Q_\theta$ and $\zeta_\phi$ at finitely many state-action points observed in the dataset. The proof also avoids the stronger full-column-rank condition \[ \inf_{\|h\|_2=1}\sup_{(s,a)\in\mathcal S\times\mathcal A}|h^\top\nabla_\theta Q_\theta(s,a)|>0. \] Instead, the analysis uses empirical-output Jacobian conditioning. The verification of this condition for linear and sufficiently wide neural-network parametrizations is deferred to Appendix (ref).
Let $\mathcal S$ be a finite-dimensional state space and let $\mathcal A$ be a finite action space. Consider the parametrized class \[ \mathcal{Q} = \left\{Q_{\boldsymbol{\theta}}:\mathcal S\times\mathcal A\to\mathbb R \mid \boldsymbol{\theta}\in\Theta\subseteq\mathbb R^{d_\theta},\ Q_{\boldsymbol{\theta}}\in\mathcal F\right\}. \] The class $\mathcal F$ may be linear, polynomial, or a neural-network class.
Assumption (ref), standard in offline RL and value-function approximation chen2019information,xie2021batch,zhan2022offline,zanette2023realizability,jiangoffline, is used below only through the empirical evaluations generated by the observed continuous-state sample.
Under this parametrization, the population objective is
and the empirical objective is
Here $V_Q(s)=\log\sum_{b\in\mathcal A}\exp(Q(s,b))$ and $\hat p_Q(b\mid s)=\exp(Q(s,b))/\sum_{c\in\mathcal A}\exp(Q(s,c))$.
Let $\mathcal D$ denote the observed finite dataset. The empirical objective (ref) is computed from $\mathcal D$ and consists of the NLL term, the Bellman-error term, and the auxiliary $\zeta$-regression term. For the Bellman-error term, the action is the anchor action $a_s$. No sample splitting or independence between objective-specific index sets is required.
Let $\mathcal X_Q=\mathcal X_Q(\mathcal D)$ denote the finite set of sampled states at which the empirical objective evaluates $Q_\theta$. Since $\mathcal A$ is finite, define the empirical $Q$-evaluation set \[ Z_Q=Z_Q(\mathcal D):=\mathcal X_Q\times\mathcal A =\{z_1,\ldots,z_M\}, \qquad M:=|Z_Q|. \] Let \[ Z_\zeta=Z_\zeta(\mathcal D)=\{\bar z_1,\ldots,\bar z_G\}, \qquad G:=|Z_\zeta|, \] be the distinct state-action pairs at which the auxiliary network $\zeta_\phi$ is evaluated. The exact grouping of the empirical averages and weights is deferred to Appendix (ref). Define \[ \mathbf Q_\theta(Z_Q):= \bigl(Q_\theta(z_1),\ldots,Q_\theta(z_M)\bigr)^\top, \qquad J_Q(\theta;Z_Q):=D_\theta\mathbf Q_\theta(Z_Q), \] and \[ \boldsymbol\zeta_\phi(Z_\zeta):= \bigl(\zeta_\phi(\bar z_1),\ldots,\zeta_\phi(\bar z_G)\bigr)^\top, \qquad J_\zeta(\phi;Z_\zeta):=D_\phi\boldsymbol\zeta_\phi(Z_\zeta). \]
Let $S_{\mathcal D_N}$ denote the set of empirical minimizers of $\widehat R_Q$. Let $\widehat\theta_T$ be the $Q$-parameter returned by Algorithm (ref) after $T$ SGDA iterations with stepsizes of the form $\eta_t=c_1/(c_2+t)$. The empirical PL theorem above supplies the optimization geometry required by standard two-sided-PL minimax convergence results yang2020global. The guarantee is an empirical optimization guarantee; population excess-risk control is obtained by combining this optimization bound with algorithmic stability/generalization bounds for Bellman-residual minimization.
We now present results from simulation experiments, comparing the performance of our approach with that of several benchmark algorithms. In this section, we use the high-dimensional version of the canonical bus engine replacement problem (rust1994structural) as the setting for our experiments. Later, in $\S$(ref), we use the OpenAI gym benchmark environment experiments with a discrete action space (Lunar Lander, Acrobot, and Cartpole) brockman2016openai as in garg2021iq for the related but easier problem of imitation learning.
This bus engine setting has been extensively used as the standard benchmark for the reward learning problem in the DDC literature in economics hotz1993conditional, aguirregabiria2002swapping, kasahara2009nonparametric, arcidiacono2011conditional, arcidiacono2011practical, su2012constrained, norets2009inference, chiong2016duality, reich2018divide, chernozhukov2022locally, geng2023data, barzegary2022recursive, yang2024estimation.
The bus engine replacement problem rust1987optimal is a simple regenerative optimal stopping problem. In this setting, the manager of a bus company operates many identical buses. As a bus accumulates mileage, its per-period maintenance cost increases. The manager can replace the engine in any period (which then becomes as good as new, and this replacement decision resets the mileage to one). However, the replacement decision comes with a high fixed cost. Each period, the manager makes a dynamic trade-off between replacing the engine and continuing with maintenance. We observe the manager's decisions for a fixed set of buses, i.e., a series of states, decisions, and state transitions. Our goal is to learn the manager's reward function from these observed trajectories under the assumption that he made these decisions optimally.
Dataset. There are $N$ independent and identical buses (trajectories) indexed by $j$, each of which has $100$ periods over which we observe them, i.e., $h\in\{1\ldots 100\}$. Each bus's trajectory starts with an initial mileage of 1. The only reward-relevant state variable at period $h$ is the mileage of bus $x_{jh} \in \{1, 2, \ldots 20\}$.
Decisions and rewards.\;\; There are two possible decisions at each period, replacement or continuation, denoted by $d_{jh} = \{0,1\}$. $d_{jh}=1$ denotes replacement, and there is a fixed cost $\theta_1$ of replacement. Replacement resets the mileage to 1, i.e., the engine is as good as new. $d_{jh}=0$ denotes maintenance, and the cost of maintaining the engine depends on the mileage as follows: $\theta_0 x_{jh}$. Intuitively, the manager can pay a high fixed cost $\theta_1$ for replacing an engine in this period but doing so reduces future maintenance costs since the mileage is reset to 1. In all our experiments, we set $\theta_0 = 1$ (maintenance cost) and $\theta_1 = 5$ (replacement cost). Additionally, we set the discount factor to $\beta = 0.95$.
State transitions at each period.\;\; If the manager chooses maintenance, the mileage advances by 1, 2, 3, or 4 with a $1/4$ probability each. If the manager chooses to replace the engine, then the mileage is reset to 1. That is, $\mathbb{P}(\{x_{j(h+1)}=x_{jh}+k\}\mid d_{jh}=0 ) = 1/4$, $k\in \{1,2,3,4\}$ and $\mathbb{P}\{x_{j(h+1)}=1\mid d_{jh}=1\}=1$. When the bus reaches the maximum mileage of 20, we assume that mileage remains at 20 even if the manager continues to choose maintenance.
High-dimensional setup.\;\; In some simulations, we consider a high-dimensional version of the problem, where we now modify the basic set-up described above to include a set of $K$ high-dimensional state variables, similar to geng2023data. Assume that we have access to an additional set of $K$ state variables $\{s^1_{jh}, s^2_{jh}, s^3_{jh} \ldots s^K_{jh}\}$, where each $s^k_{jh}$ is an i.i.d random draw from $\{-10, -9, \ldots, 9, 10\}$. We vary $K$ from 2 to 100 in our empirical experiments to test the sensitivity of our approach to the dimensionality of the problem. Further, we assume that these high-dimensional state variables $s_{jh}^k$s do not affect the reward function or the mileage transition probabilities. However, the researcher does not know this. So, they are included in the state space, and ideally, our algorithm should be able to infer that these state variables do not affect rewards and/or value function and recover the true reward function.
Traing/testing split. Throughout, we keep 80% of the trajectories in any experiment for training/learning the reward function, and the remaining 20% is used for evaluation/testing.
Functional form. For the oracle methods, we use the reward functions' true parametric form, i.e., a linear function. For other methods (including ours), we used a multi-layer perceptron (MLP) with two hidden layers and 10 perceptrons for each hidden layer for the estimation of $Q$-function.
We compare our algorithm against a series of standard, or state-of-art benchmark algorithms in the DDC and IRL settings. \\ Rust (Oracle) \; Rust is an oracle-like fixed point iteration baseline that uses the nested fixed point algorithm rust1987optimal. It assumes the knowledge of: (1) linear parametrization of rewards by $\theta_1$ and $\theta_2$ as described above, and (2) the exact transition probabilities. \\ ML-IRL (Oracle)\; ML-IRL from zeng2023understanding is the state-of-the-art offline IRL algorithm that minimizes negative log-likelihood of choice (i.e., the first term in Equation (ref)). This method requires a separate estimation of transition probabilities, which is challenging in high-dimensional settings. So, we make the same oracle assumptions as we did for Rust (Oracle), i.e., assume that transition probabilities are known. Additionally, to further improve this method, we leverage the finite dependence property of the problem arcidiacono2011conditional, which helps avoid roll-outs. \\ SAmQ\; SAmQ geng2023data fits approximated soft-max Value Iteration (VI) to the observed data. We use the SAmQ implementation provided by the authors\footnote{\href{https://github.com/gengsinong/SAmQ}{https://github.com/gengsinong/SAmQ}}. However, their code did not scale due to a memory overflow issue, and did not work for scenarios with 2500 (i.e., 250,000 samples) trajectories or more. \\ IQ-learn\; IQ-learn is a popular gradient-based method, maximizing the occupancy matching objective (which does not guarantee that the Bellman equation is satisfied; see Web Appendix $S$(ref)) for details. \\ BC\; Behavioral Cloning (BC) simply minimizes the expected negative log-likelihood. This simple algorithm outperforms zeng2023understanding, li2022rethinkingvaluedice many recent algorithms such as ValueDICE kostrikov2019imitation. See $\S$(ref) for detailed discussions.
Table (ref) provides a table of simulation experiment results without dummy variables, i.e., with only mileage ($x_{jh}$) as the relevant state variable. The performance of algorithms was compared in terms of mean absolute percentage error (MAPE) of $r$ estimation, which is defined as $\frac{1}{N} \sum_{i=1}^N \left|\frac{\hat{r}_i-r_i}{r_i}\right| \times 100$, where $N$ is the total number of samples from expert policy $\pi^*$ and $\hat{r}_i$ is each algorithm's estimator for the true reward $r_i$.\footnote{In the simulation we consider, we don't have a state-action pair with true reward near 0.}\footnote{As we assume that the data was collected from agents following (entropy regularized) optimal policy $\pi^*$ (Assumption (ref)), the distribution of states and actions in the data is the best data distribution choice.}
We find that GLADIUS performs much better than non-Oracle baselines and performs at least on par with, or slightly better than, Oracle baselines. A natural question here is: why do the Oracle baselines that leverage the exact transition function and the precise linear parametrization not beat our approach? The main reason for this is the imbalance of state-action distribution from expert policy: (See Table (ref) and Web Appendix $\S$(ref))
Finally, it is not surprising to see IQ-learn and BC underperform in the reward function estimation task since they do not require/ensure that the Bellman condition holds. See Appendix (ref) for a detailed discussion.
Figure (ref) (below) presents high-dimensional experiments, where states were appended with dummy variables. Each dummy variable is of dimension 20. Note that a state space of dimensionality $20^{10}$ (10 dummy variables with 20 possible values each) is equivalent to $10^{13}$, which is infeasible for existing exact methods (e.g., Rust) and methods that require transition probability estimation (e.g., ML-IRL). Therefore, we only present comparisons to the non-oracle methods.
We find that our approach outperforms benchmark algorithms, including SAmQ, IQ‑learn, and BC (see Figure (ref)). Moreover, as illustrated in the right panel of Figure (ref), the MAPE grows sub‑linearly with the size of the state space (note the logarithmic \(x\)-axis). Remarkably, even in the extreme setting with \(K=100\) dummy variables—an astronomically large discrete state space of \(20^{100}\!\approx\!10^{130}\) distinct configurations—GLADIUS’s MAPE rises only to about 10%. This limited loss in precision due to such a massive dimensional expansion underscores the method’s robustness and practical scalability to very high-dimensional applications.
One of the key contributions of this paper is the characterization of the relationship between imitation learning (IL) and inverse reinforcement learning (IRL)/Dynamic Discrete Choice (DDC) model, particularly through the ERM-IRL/DDC framework. Given that much of the IRL literature has historically focused on providing experimental results for IL tasks, we conduct a series of experiments to empirically validate our theoretical findings. Specifically, we aim to test our prediction in Section (ref) that behavioral cloning (BC) should outperform ERM-IRL for IL tasks, as BC directly optimizes the negative log-likelihood objective without the additional complexity of Bellman error minimization. By comparing BC and ERM-IRL across various IL benchmark tasks, we demonstrate that BC consistently achieves better performance in terms of both computational efficiency and policy accuracy, reinforcing our claim that IL is a strictly easier problem than IRL.
As in garg2021iq, we employ three OpenAI Gym environments for algorithms with discrete actions brockman2016openai: Lunar Lander v2, Cartpole v1, and Acrobot v1. These environments are widely used in IL and RL research, providing well-defined optimal policies and performance metrics.
Dataset. For each environment, we generate expert demonstrations using a pre-trained policy. We use publicly available expert policies\footnote{\url{https://huggingface.co/sb3/}} trained via Proximal Policy Optimization (PPO) schulman2017proximal, as implemented in the Stable-Baselines3 library raffin2021stable. Each expert policy is run to generate demonstration trajectories, and we vary the number of expert trajectories across experiments for training. For all experiments, we used the expert policy demonstration data from 10 episodes for testing.
Performance Metric. The primary evaluation metric is % optimality, defined as:
For each baseline, we report the mean and standard deviation of 100 evaluation episodes after training. A higher % optimality indicates that the algorithm's policy closely matches the expert. The 1000-episodic mean and standard deviation ([mean$\pm$std]) of the episodic reward of expert policy for each environment was $[232.77\pm73.77]$ for Lunar-Lander v2 (larger the better), $[-82.80\pm27.55]$ for Acrobot v1 (smaller the better), and $[500\pm 0]$ for Cartpole v1 (larger the better).
Training Details. All algorithms were trained for 5,000 epochs. Since our goal in this experiment is to show the superiority of BC for IL tasks, we only include ERM-IRL and IQ-learn garg2021iq as baselines. Specifically, we exclude baselines such as Rust rust1987optimal and ML-IRL zeng2023understanding, which require explicit estimation of transition probabilities.
Table (ref) presents the % optimality results for Lunar Lander v2, Cartpole v1, and Acrobot v1. As predicted in our theoretical analysis, BC consistently outperforms ERM-IRL in terms of % optimality, validating our theoretical claims.
In this paper, we propose a provably globally convergent empirical risk minimization framework that combines non-parametric estimation methods (e.g., machine learning methods) with IRL/DDC models. This method's convergence to global optima stems from our new theoretical finding that the Bellman error (i.e., Bellman residual) satisfies the Polyak-Łojasiewicz (PL) condition, which is a weaker but almost equally useful condition as strong convexity for providing theoretical assurances.
The three key advantages of our method are: (1) it is easily applicable to high-dimensional state spaces, (2) it can operate without the knowledge of (or requiring the estimation of) state-transition probabilities, and (3) it is applicable to infinite state spaces. These three properties make our algorithm practically applicable and useful in high-dimensional, infinite-size state and action spaces that are common in business and economics applications. We demonstrate our approach's empirical performance through extensive simulation experiments (covering both low and high-dimensional settings). We find that, on average, our method performs quite well in recovering rewards in both low and high-dimensional settings. Further, it has better/on-par performance compared to other benchmark algorithms in this area (including algorithms that assume the parametric form of the reward function and knowledge of state transition probabilities) and is able to recover rewards even in settings where other algorithms are not viable.