## 3 Inferring an Agent's Desires
### Reward Function Discrimination
#### 3.1.3.2 Maximum Causal Entropy IRL  
Transition dynamics play an important role in MDPs. [PERSON] et al. [39] frame the agent's decision making in the MDP as two interacting stochastic processes: the environment's transition dynamics \(T\) (assumed to be known--given or estimated from data), and the agent's policy \(\pi\) (unknown in the IRL problem). For each time step \(t\) in the sequence \((1,\ldots,H)\), the state and action values are random variables \(S_{t}\), \(A_{t}\). These can be collected into the random sequences \(\mathbf{S}_{1:H}\), \(\mathbf{A}_{1:H}\), respectively, and they determine the interaction between the processes. When considered together, they form a trajectory \(\tau\).  
In the MaxEnt approach [52], information is lost by failing to consider causality (time direction) in the trajectory distribution \(\Pr(\tau|\theta,T)\equiv\Pr(\mathbf{S}_{1:H},\mathbf{A}_{1:H})\). This is addressed in [39; 63] by proposing to use an alternative way to decompose this joint probability by using causally conditioned probabilities [64],  
\[\begin{split}\Pr(\mathbf{S}_{1:H},\mathbf{A}_{1:H})& =\Pr(\mathbf{S}_{1:H}||\mathbf{A}_{1:H-1})\Pr(\mathbf{A}_{1:H}|| \mathbf{S}_{1:H})\\ &=\prod_{t=1}^{H}\Pr(S_{t}|\mathbf{S}_{1:t-1},\mathbf{A}_{1:t-1} )\prod_{t=1}^{H}\Pr(A_{t}|\mathbf{A}_{1:t-1},\mathbf{S}_{1:t})\end{split} \tag{36}\]  
wherein future state variable outcomes have no effect on preceding variables. The state transition dynamics follow the Markov property, and thus have a causally conditioned probability \(T(\mathbf{S}_{1:H}||\mathbf{A}_{1:H-1})=\prod_{t=1}^{H}T(S_{t},|S_{t-1},A_{t-1})\). An agent's policy can also be modelled as a causally conditioned probability distribution, though the factors in the product of probabilities may not be Markovian, so \(\pi(\mathbf{A}_{1:H}||\mathbf{S}_{1:H})=\prod_{t=1}^{H}\pi(A_{t},|\mathbf{A}_{ 1:t-1},\mathbf{S}_{1:t})\). The goal in this framing of the IRL problem is to find the maximum causal entropy (MaxCausalEnt) policy estimator  
\[\hat{\pi}^{*}=\operatorname*{arg\,max}_{\hat{\pi}(\mathbf{A}_{1:H}||\mathbf{S }_{1:H})}\mathbb{E}_{\tau}[-\log\hat{\pi}(\mathbf{a}_{1:H}||\mathbf{s}_{1:H})], \tag{37}\]  
such that  
\[\mathbb{E}_{\tau}[\Phi(\tau)]=\hat{\Phi}(\tau_{\mathbb{E}}),\]  
\[\sum_{A_{t}}\Pr(A_{t}|\mathbf{S}_{1:t},\mathbf{A}_{1:t-1})=1\quad\forall \mathbf{S}_{1:t},\mathbf{A}_{1:t-1}.\]Assuming, as is usually the case, that the features decompose linearly in time makes the optimisation much simpler. The distribution (first-order Markovian policy) that optimises this constrained problem is a Boltzmann policy (Section 2.3) and takes the recursive form  
\[\begin{split}&\pi_{\theta}(A_{t}\mid S_{t})=\frac{Z_{A_{t}|S_{t}, \theta}}{Z_{S_{t},\theta}}\\ &\log Z_{A_{t}|S_{t},\theta}=\theta^{\intercal}\phi(S_{t},A_{t}) +\sum_{S_{t+1}}P(S_{t+1}\mid S_{t},A_{t})\log Z_{S_{t+1},\theta}\\ &\log Z_{S_{t},\theta}=\log\sum_{A_{t}}Z_{A_{t}|S_{t},\theta}= \text{LogSumExp}_{A_{t}|S_{t},\theta}\}.\end{split} \tag{38}\]  
An estimate of \(\theta\) can be obtained through optimisation on the gradient computed through the calculation procedure in Algorithm 7. MaxCausalEnt was later expanded to the infinite time horizon setting [65; 66].  
```
AlgorithmMaxCausalEntInference(\(\theta\))
1 for\(t\gets H\)to\(1\)do
2 if\(t=H\)then
3\(\log Z_{A_{t}|S_{t},\theta}\leftarrow\theta^{\intercal}\phi(S_{t},A_{t})\) \(\forall A_{t},S_{t}\)
4 else
5\(\log Z_{A_{t}|S_{t},\theta}\leftarrow\theta^{\intercal}\phi(S_{t},A_{t})+ \mathbb{E}_{S_{t+1}}[\log Z_{S_{t+1},\theta}|S_{t},A_{t}]\) \(\forall A_{t},S_{t}\)
6 end if
7\(\log Z_{S_{t},\theta}\leftarrow\text{softmax}_{A_{t}}\log Z_{A_{t}|S_{t}, \theta}\) \(\forall S_{t}\)
8\(\Pr(A_{t}|S_{t})\leftarrow\frac{Z_{A_{t}|S_{t},\theta}}{Z_{S_{t},\theta}}\) \(\forall A_{t},S_{t}\)
9 end for
10 return\(\Pr(A|S)\)
```  
**Algorithm 7**Maximum causal entropy algorithm [63; 67]