# Structural Estimation of Markov Decision Processes in High-Dimensional State Space with Finite-Time Guarantees

arXiv: https://arxiv.org/abs/2210.01282 · HTML: https://mlsanity.com/paper/2210.01282/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Placed in Inverse reinforcement learning, one of 13 directions in Offline RL and imitation learning from data.
- Builds on 23 of its 53 references that are in the map.
- First posted on arXiv 4 Oct 2022.

## Placed in

- Offline RL and imitation learning from data / [Inverse reinforcement learning](https://mlsanity.com/offlinerl/inverse-reinforcement-learning/)

## Builds on (most cited first, 23 of 23)

- [Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor](https://mlsanity.com/paper/1801.01290/) (2018)
- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [Generative Adversarial Imitation Learning](https://mlsanity.com/paper/1606.03476/) (2016)
- [Deep Reinforcement Learning for Autonomous Driving: A Survey](https://mlsanity.com/paper/2002.00444/) (2020)
- [Reinforcement Learning with Deep Energy-Based Policies](https://mlsanity.com/paper/1702.08165/) (2017)
- [Gradient Descent Provably Optimizes Over-parameterized Neural Networks](https://mlsanity.com/paper/1810.02054/) (2018)
- [Learning Robust Rewards with Adversarial Inverse Reinforcement Learning](https://mlsanity.com/paper/1710.11248/) (2017)
- [Reinforcement Learning in Healthcare: A Survey](https://mlsanity.com/paper/1908.08796/) (2019)
- [A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximation](https://mlsanity.com/paper/1806.02450/) (2018)
- [IQ-Learn: Inverse soft-Q Learning for Imitation](https://mlsanity.com/paper/2106.12142/) (2021)
- [Maximum Entropy Deep Inverse Reinforcement Learning](https://mlsanity.com/paper/1507.04888/) (2015)
- [Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularization](https://mlsanity.com/paper/2007.06558/) (2020)
- [A Finite Time Analysis of Two Time-Scale Actor Critic Methods](https://mlsanity.com/paper/2005.01350/) (2020)
- [A Near-Optimal Algorithm for Stochastic Bilevel Optimization via Double-Momentum](https://mlsanity.com/paper/2102.07367/) (2021)
- [Finite-Sample Analysis for SARSA with Linear Function Approximation](https://mlsanity.com/paper/1902.02234/) (2019)
- [State Alignment-based Imitation Learning](https://mlsanity.com/paper/1911.10947/) (2019)
- [f-IRL: Inverse Reinforcement Learning via State Marginal Matching](https://mlsanity.com/paper/2011.04709/) (2020)
- [State-only Imitation with Transition Dynamics Mismatch](https://mlsanity.com/paper/2002.11879/) (2020)
- [Robust Inverse Reinforcement Learning under Transition Dynamics Mismatch](https://mlsanity.com/paper/2007.01174/) (2020)
- [On Computation and Generalization of Generative Adversarial Imitation Learning](https://mlsanity.com/paper/2001.02792/) (2020)
- [When Will Generative Adversarial Imitation Learning Algorithms Attain Global Convergence](https://mlsanity.com/paper/2006.13506/) (2020)
- [Inverse Reinforcement Learning with Explicit Policy Estimates](https://mlsanity.com/paper/2103.02863/) (2021)
- [A Relation Analysis of Markov Decision Process Frameworks](https://mlsanity.com/paper/2008.07820/) (2020)

## Built on by (most cited first, 12 of 12)

- [Reinforcement Learning with Human Feedback: Learning Dynamic Choices via Pessimism](https://mlsanity.com/paper/2305.18438/) (2023)
- [Getting More Juice Out of the SFT Data: Reward Learning from Human Demonstration Improves SFT for LLM Alignment](https://mlsanity.com/paper/2405.17888/) (2024)
- [When Demonstrations Meet Generative World Models: A Maximum Likelihood Framework for Offline Inverse Reinforcement Learning](https://mlsanity.com/paper/2302.07457/) (2023)
- [Imitation Learning in Discounted Linear MDPs without exploration assumptions](https://mlsanity.com/paper/2405.02181/) (2024)
- [Optimistically Optimistic Exploration for Provably Efficient Infinite-Horizon Reinforcement and Imitation Learning](https://mlsanity.com/paper/2502.13900/) (2025)
- [A Bayesian Approach to Robust Inverse Reinforcement Learning](https://mlsanity.com/paper/2309.08571/) (2023)
- [A Unified Linear Programming Framework for Offline Reward Learning from Human Demonstrations and Feedback](https://mlsanity.com/paper/2405.12421/) (2024)
- [Learning Reward and Policy Jointly from Demonstration and Preference Improves Alignment](https://mlsanity.com/paper/2406.06874/) (2024)
- [From Demonstrations to Rewards: Alignment Without Explicit Human Preferences](https://mlsanity.com/paper/2503.13538/) (2025)
- [Stability and Generalization for Bellman Residuals](https://mlsanity.com/paper/2508.18741/) (2025)
- [DeepHalo: A Neural Choice Model with Controllable Context Effects](https://mlsanity.com/paper/2601.04616/) (2026)
- [Recursive Deep Inverse Reinforcement Learning](https://mlsanity.com/paper/2504.13241/) (2025)

## Abstract (arXiv)

We consider the task of estimating a structural model of dynamic decisions by a human agent based upon the observable history of implemented actions and visited states. This problem has an inherent nested structure: in the inner problem, an optimal policy for a given reward function is identified while in the outer problem, a measure of fit is maximized. Several approaches have been proposed to alleviate the computational burden of this nested-loop structure, but these methods still suffer from high complexity when the state space is either discrete with large cardinality or continuous in high dimensions. Other approaches in the inverse reinforcement learning (IRL) literature emphasize policy estimation at the expense of reduced reward estimation accuracy. In this paper we propose a single-loop estimation algorithm with finite time guarantees that is equipped to deal with high-dimensional state spaces without compromising reward estimation accuracy. In the proposed algorithm, each 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 sublinearly. Finally, by using robotics control problems in MuJoCo and their transfer settings, we show that the proposed algorithm achieves superior performance compared with other IRL and imitation learning benchmarks.