## 3 Inferring an Agent's Desires
### Reward Function Discrimination
#### 3.1.1 Maximum Margin Methods  
3.1.1.1. Foundational Work  
To extend the method to infinite state spaces, the authors resorted to a linear approximation of \(R\) with given fixed features. This approach to the problem is the canonical form of the so-called maximum-margin class of IRL techniques, the goal of which is to estimate a reward function that maximises the difference between an optimal policy and the rest of the available policies [27], or equivalently, a set of weights \(\theta\) that parameterise a reward function \(R_{\theta}\), such that under \(R_{\theta}\), \(V^{\pi^{*}}\geq V^{\pi}\) for all \(\pi\). This particular method requires a way to approximate the value of \(V^{\pi}\) under any MDP. Invoking Equation (7), the task is then to find the \(\theta\) that maximises, for a sample \(S_{0}\subset\mathcal{S}\) of the state space  
\[\sum_{s\in S_{0}}\min_{a\in\mathcal{A}\setminus a_{1}}\{p(\mathbb{E}_{s^{ \prime}\sim T(s,a_{1})}[V^{\pi}(s^{\prime})]-\mathbb{E}_{s^{\prime}\sim T(s,a )}[V^{\pi}(s^{\prime})])\} \tag{15}\]  
with  
\[ \begin{array}{ll}|\theta_{i}|\leq 1&i=1,2,\ldots,d\\ p(x)=\left\{\begin{array}{ll}x&x\geq\ 0\\ 2x&x<0,\end{array}\right.\end{array} \]  
where \(p\) is a penalty function for states in which \(\pi\) is not optimal under \(\hat{R}\). The penalty weight value of 2 in \(p\) is arbitrarily chosen. The original paper asserts that results were not sensitive to this value. Finally, further generalising the method, they introduced an algorithm to find \(\hat{R}\) such that a policy \(\pi\) to be determined maximises \(V^{\pi}\) when a set \(\mathcal{D}\) of trajectories \(\tau\) through \(S\) is given in lieu of \(\pi_{E}\). This algorithm requires (i) a way to approximate \(V^{\pi}\) (as above), (ii) a way to find an optimal policy \(\pi_{k}\) under any \(R\) (techniques from the RL literature can be employed to this end), and (iii) the ability to simulate trajectories starting from \(s_{0}\) under policy \(\pi\) in the MDP. Approximations of the feature expectations and the value function can be obtained by performing \(m\) Monte Carlo trajectories of length \(H\) under \(\pi\), and averaging over their values (for a large \(H\), the difference as compared with an infinite time horizon is negligible):  
\[\vartheta^{\pi}(s_{0})=\frac{1}{m}\sum_{j=1}^{m}\sum_{t=0}^{H_{j}}\gamma^{t} \phi(s_{t}^{(j)}) \tag{16}\]  
\[\tilde{V}^{\pi}(s_{0})=\vartheta^{\mathsf{T}}\vartheta^{\pi}(s_{0}). \tag{17}\]  
Similarly, we can obtain approximations for the expert's feature expectations, but note that their accuracy is contingent on the size of the set of demonstrations provided, as well as the fact that some states may not be visited in some cases. In their final algorithm, shown in Algorithm 1, the optimisation step is similar to Equation (15), with the same constraints, but replacing the expectation by the empirical average \(\tilde{V}^{\pi}\) from Equation (17), and the domain \(\mathcal{S}\times\mathcal{A}\setminus a_{1}\) by the set of policies \(\Pi\). The initial state \(s_{0}\) is fixed for all the trajectories, but this results in no loss of generality if we let \(s_{0}\) be a dummy state and set \(T(s_{0},a,s_{1})=D(s_{1})\) for all \(a\in\mathcal{A}\).