## 3 Inferring an Agent's Desires
### Reward Function Discrimination
#### 3.1.2 Policy Walk
This argument is later extended by [PERSON] and [PERSON] [60] (Section 3.1.4). The solution space for this method is the same as in [53], as per the analysis in [61]. 3.1.2.3. Structured Generalisation [PERSON] and [PERSON] [62] contribute a principled generalisation of the Bayesian IRL approach (Section 3.1.2.2) with structured priors on rewards and policies. Given a controlled Markov process \(\
u=\{\mathcal{S},\mathcal{A},T\}\) and a discount factor \(\gamma\) (or priors thereof), a prior for a stochastic reward function \(\Pr(\rho|v)\) over the space of reward functions \(\mathcal{R}\), and a prior for the policy \(\Pr(\pi|\rho_{E},\
u)\) over the policy space \(\Pi\); with joint prior \(\forall\pi\in P\subset\Pi,\rho\in R\subset\mathcal{R}\)  
\[\Pr(\pi,\rho|\
u)\triangleq\int_{\rho\in R}\Pr(\pi|\rho,\
u)\mathrm{d}\Pr( \rho|\
u) \tag{31}\]  
the posterior on reward functions is  
\[\Pr(\rho|\tau,\
u)=\Pr(\rho|\mathbf{s}_{1:H},\mathbf{a}_{1:H},\
u)=\frac{ \int_{\rho}\int_{\Pi}\pi(\mathbf{a}_{1:H}|\mathbf{s}_{1:H})\mathrm{d}\Pr(\pi| \rho,\
u)\mathrm{d}\Pr(\rho|\
u)}{\int_{\mathcal{R}}\int_{\Pi}\pi(\mathbf{a} _{1:H}|\mathbf{s}_{1:H})\mathrm{d}\Pr(\pi|\rho,\
u)\mathrm{d}\Pr(\rho|\
u)}. \tag{32}\]  
With this statistical model and the usual Boltzmann action choice probability assumption (Section 2.3), they derive two MH algorithms: direct sampling from the joint posterior distribution \(\Pr(\pi,\rho|\tau)\), and a hybrid Gibbs sampler procedure with a reward sequence augmentation of the model with \(\Pr(r_{t}|s_{t},a_{t},\rho_{E})\). These algorithms do not require the demonstrations to be optimal, and are capable of finding policies that outperform the agent's actual policy with respect to its reward function, as well as revealing policies that perform better than those recovered with previous IRL methods. 3.1.3. Maximum Entropy Methods Bayesian IRL methods compute the likelihood as the total probability over each action choice in a trajectory. This fails to account for global interdependencies of choices along a trajectory. Maximum entropy methods focus on modelling the likelihood of entire trajectories \(\Pr(\tau|R)\) as a whole, as opposed to individual action choices. They resolve the ambiguity between trajectories, constrained to matching feature counts by maximising the entropy of the distribution. 3.1.3.1. Maximum Entropy IRL [PERSON] et al. [52] provided a definitive method by which to discriminate between reward function candidates by focusing on the characterisation of the likelihood \(\Pr(\tau|\theta)\). Although previous probabilistic approaches worked with distributions over policies, inevitably focusing on local action choices [53; 59], this method is based on a distribution over entire trajectories that is normalised globally. Multiple trajectories with the same feature counts may obtain the same rewards under a given \(R_{\theta}\). Through the principle of maximum entropy, they obtain a distribution that removes any preferences for trajectories beyond the requirement of matching feature counts, thereby resolving the ambiguity. It attributes equal probabilities to trajectories with equal rewards, and exponentially higher probabilities to trajectories with higher rewards, and does so globally over the trajectories (as opposed to locally at the action level as is the case in [49; 59]). For observed trajectory realisations \(\tau_{j=1:m}^{E}\), this is equivalent to maximising the likelihood of the observed trajectories under a maximum entropy exponential family of distributions \((\exp\left(\theta^{\mathsf{T}}\Phi(\tau)\right))_{\theta\in\Theta}\). Thus, learning from observation entails finding \(\theta^{*}=\arg\max_{\theta}L(\theta)\), where  
\[L(\theta)=\sum_{\tau_{j=1:m}^{E}}\log\Pr(\tau_{j}^{E}|\theta,T). \tag{33}\]  
With a partition function \(Z\) assumed constant for all \((s,a,s^{\prime})\), and assuming the effects of transition dynamics on behaviour are negligible, the distribution of interest for nondeterministic MDPs (which extends trivially to deterministic MDPs) is  
\[