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.

本文提出了一种单步估计算法，用于处理高维状态空间，同时又不会降低奖励估计精度的问题。该算法通过随机梯度最大化似然函数，使每次策略改进都能够进行。研究表明，该算法可以达到平稳状态，同时在 MuJoCo 机器人控制问题和其转移设置中，相比其他逆向强化学习算法和模仿学习基准，该算法表现更好。

高维状态空间中具有有限时间保证的马尔可夫决策过程的结构估计

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

Estimating the joint probability mass function (PMF) of a set of random
variables lies at the heart of statistical learning and signal processing.
Without structural assumptions, such as modeling the variables as a Markov
chain, tree, or other graphical model, joint PMF estimation is often considered
mission impossible - the number of unknowns grows exponentially with the number
of variables. But who gives us the structural model? Is there a generic,
`non-parametric' way to control joint PMF complexity without relying on a
priori structural assumptions regarding the underlying probability model? Is it
possible to discover the operational structure without biasing the analysis up
front? What if we only observe random subsets of the variables, can we still
reliably estimate the joint PMF of all? This paper shows, perhaps surprisingly,
that if the joint PMF of any three variables can be estimated, then the joint
PMF of all the variables can be provably recovered under relatively mild
conditions. The result is reminiscent of Kolmogorov's extension theorem -
consistent specification of lower-dimensional distributions induces a unique
probability measure for the entire process. The difference is that for
processes of limited complexity (rank of the high-dimensional PMF) it is
possible to obtain complete characterization from only three-dimensional
distributions. In fact not all three-dimensional PMFs are needed; and under
more stringent conditions even two-dimensional will do. Exploiting multilinear
algebra, this paper proves that such higher-dimensional PMF completion can be
guaranteed - several pertinent identifiability results are derived. It also
provides a practical and efficient algorithm to carry out the recovery task.
Judiciously designed simulations and real-data experiments on movie
recommendation and data classification are presented to showcase the
effectiveness of the approach.

本文介绍了一种使用多线性代数方法实现关键点之间联合概率质量函数估计的方法，并给出了用于实现复杂度有限的高维概率的完整特征的证明和几个相关的可识别性结果。