## 3 Inferring an Agent's Desires
### Reward Function Characterisation  
Early IRL methods assumed linear approximations of the reward function over basis functions, or features \(\phi(s,a)\). Features have a natural interpretation as elements of the environment that can be perceived and on the basis of which decisions are made. Each feature may be more or less valuable to the decision-making process given context and goals, and they may have complex, logical, hierarchical relationships amongst them and with respect to the rewards (beyond linear). Some approaches include \"raw\" or \"primitive\" features that can simply be enumerated without taking their relevance into account, and which form the basis on which to compose more complex or abstract features. In most IRL methods, \(R\) defines how to combine and how much value to attribute to features, placing them at the core of the problem. Important considerations arise from this, such as whether they are perceived equally by the actor and the observer, including issues of partial observability, beliefs, perspective taking, and differing ways to interpret and combine raw features. A notable exception in early methods is Bayesian IRL (Stein  
A method to automatically initialise and adapt feature parameterisations in continuous space is proposed in [PERSON] and [PERSON] (2016) (Section 3.1.5). The features are normalised Gaussian radial basis function kernels  
\[\phi_{i}(s;\theta_{\phi})=\frac{\exp\left(\theta_{\phi_{i}}^{\mathsf{T}}G(s) \right)}{\sum_{j}\exp\left(\theta_{\phi_{j}}^{\mathsf{T}}G(s)\right)} \tag{50}\]  
with \(G(s)=[1,s_{k},s_{k}s_{l}]\ \ \forall k\leq l\). The value function is linear in the kernels  
\[V(s;\theta_{V},\theta_{\phi})=\theta_{V}^{\mathsf{T}}\phi(s;\theta_{\phi}). \tag{51}\]  
In [PERSON] et al. (2017), the observer learns a regression tree over \(\mathcal{S}\) to represent the reward function, with the branching determined by (binary) feature primitives \(\phi^{(0)}(s)\in\{0,1\}^{d_{0}}\), yielding features \(\phi\) that are logical combinations of these primitives. This way, instead of minimising a measure of deviation from expert demonstrations as in previous methods, their algorithm discovers regions of the state-action space where the expressiveness of the features is insufficient with respect to \(R\), and updates the features accordingly, by iteratively alternating between an \(R\) optimisation step and a \(\phi\) fitting step. The tree has \(d\) leaf nodes each containing a set of states \(S_{i}\subseteq\mathcal{S}\), for \(i=1,\ldots,d\). The features can be interpreted as indicator functions \(\phi_{i}(s)=I(s\in S_{i})\). Features deeper in the tree are more complex combinations of feature primitives. For the optimisation step, \(R\) is constrained by \(\mathcal{D}\), because the optimal policy under \(R\) must be consistent with the demonstrations; the current features \(\phi\), so that \(R\) must minimise the sum of squares error with its projection onto the feature space. The projection is performed by means of \(G_{R\phi}\in\mathbb{R}^{d\times|\mathcal{S}|}\) and \(G_{\phi R}\in\mathbb{R}^{|\mathcal{S}|\times d}\), defined to be  
\[G_{R\phi}(S_{i},s)= \begin{cases}|S_{i}|^{-1}&\text{if }s\in\ S_{i}\\ 0&\text{otherwise}\end{cases} \qquad\ G_{\phi R}(s,S_{i})= \begin{cases}1&\text{if }s \in\ S_{i}\\ 0&\text{otherwise}\end{cases} \]  
so that the vector \(G_{\phi R}G_{R\phi}R\in\mathbb{R}^{|\mathcal{S}|}\) encodes the reward for each state, computed as the average reward over the states in the \(S_{i}\) that \(s\) belongs to. They set the optimisation step as a sparse quadratic program  
\[\min_{R,R_{\phi},V}\frac{1}{|\mathcal{S}||\mathcal{A}|}||R-G_{\phi R}R_{\phi} ||_{2}^{2}+\frac{\lambda}{K}||NR_{\phi}||_{1}, \tag{52}\]  
such that  
\[