## 2 Background
### Problem Formulation and Notation  
The problem setting for IRL, as for RL, is a (finite) MDP, characterised by the tuple \((\mathcal{S},\mathcal{A},T,D,\gamma,R)\) with  
* \(\mathcal{S}=\{s_{1},s_{2},\dots\}\)--a (finite) set of _states_
* \(\mathcal{A}=\{a_{1},a_{2},\dots,a_{k}\}\)--a finite set of \(k\)_actions_
* \(T=\{\Pr(s^{\prime}|s,a):s,s^{\prime}\in\mathcal{S},a\in\mathcal{A}\}\)--the state _transition probabilities_ when performing \(a\) in \(s\)
* \(D=\{\Pr(s_{0}=s):s\in S\}\)--a probability distribution over \(S\) from which the initial state is drawn (\(s_{0}\)\(\sim\)\(D\))
* \(\gamma\in[0,1)\)--a time _discount factor_
* \(R:\mathcal{S}\times\mathcal{A}\to\mathbb{R}\)--a _reward function_ whose absolute value is bounded by \(R_{max}\).  
Behaviour within an MDP is dictated by a policy. A deterministic policy is a function \(\pi:\mathcal{S}\to\mathcal{A}\), yielding an action choice \(a\) for a given state \(s\). A stochastic policy is a probability distribution over actions given a state \(\pi(a|s)=P(a|s)\). A mixed policy \(\psi\) is a distribution over a set of deterministic stationary policies \(\Pi\), with \(\lambda_{k}=P(\pi=\pi_{k})\), or equivalently, a convex combination with coefficients \(\sum_{k}\lambda_{k}=1\). Mixed policies are executed by selecting a policy \(\pi_{k}\) with probability \(\lambda_{k}\) at the start of the MDP and following this policy for the entirety of the problem. A policy is optimal when it maximises its associated value function, or \"expected sum of discounted rewards\",  
\[V^{\pi}=\mathbb{E}_{(s_{t},a_{t})\sim d_{\pi,T}}[\sum_{t=0}^{\infty}\gamma^{ t}R(s_{t},a_{t})|D,T,\pi]=\mathbb{E}_{s_{0}\sim D}[V^{\pi}(s_{0})], \tag{1}\]  
where \(d_{\pi,T,t}\) is the state-action distribution at time \(t\), a result of the agent's policy and the environment's transition probabilities, with \(s_{0}\) drawn from \(D\). The Bellman equationprovides a way to recursively compute the values of states under a policy. For a given MDP, \(V^{\pi}\) satisfies  
\[V^{\pi}(s)=R(s)+\gamma\sum_{s^{\prime}\in\mathcal{S}}T(s,\pi(s),s^{\prime})V^{ \pi}(s^{\prime})\qquad\forall s\in\mathcal{S},a\in\mathcal{A}. \tag{2}\]  
An additional auxiliary function commonly used in MDP settings is the \(Q\)-function  
\[Q^{\pi}(s,a)=R(s,a)+\gamma\sum_{s^{\prime}\in\mathcal{S}}T(s,a,s^{\prime})V^{ \pi}(s^{\prime})\qquad\forall s\in\mathcal{S},a\in\mathcal{A}, \tag{3}\]  
which defines the cumulative reward to be expected from performing action \(a\) while in state \(s\), and can be used to obtain an optimal policy \(\pi^{*}(s)\in\arg\max_{a\in\mathcal{A}}Q^{\pi}(s,a;R)\) for a given \(R\).  
A useful representation of a policy is its discounted state-action visitation distribution, or _occupancy_. A policy \(\pi\) and its occupancy measure \(\mu^{\pi}\) can be used interchangeably for a given environment--occupancy provides a representation of the policy as influenced by the transition dynamics of the environment. By employing Kronecker delta notation (\(\delta_{ij}=1\) if \(i=j\), \(0\) otherwise), the occupancy is  
\[\mu^{\pi}(s,a)=\mathbb{E}_{(s_{i},a_{t})\sim d_{\pi,T,t}}[\sum_{t=0}^{\infty} \gamma^{t}\delta_{s_{i}s}\delta_{a_{t}a}|D,T,\pi] \tag{4}\]  
and is sufficiently defined through the linear Bellman flow constraints [34]  
\[\begin{array}{l}\mu^{\pi}(s)=D(s)+\gamma\sum_{s^{\prime}\in\mathcal{S}}\sum _{a\in\mathcal{A}}\mu^{\pi}(s^{\prime},a)T(s,a,s^{\prime})\,\\ \mu^{\pi}(s)=\sum_{a\in\mathcal{A}}\mu^{\pi}(s,a)\,\\ \mu^{\pi}(s,a)\geq 0\.\end{array} \tag{5}\]  
These constraints define a set \(\mathcal{G}\) of all the constraint-satisfying occupancies, each of which can be represented as a vector \(\mu^{\pi}\in\mathbb{R}^{|\mathcal{S}\times\mathcal{A}|}\)[35].