## 3 Inferring an Agent's Desires
### Reward Function Discrimination
#### 3.1.2 Policy Walk  
[PERSON] and [PERSON] [59] formally state the problem as Bayesian inference (hereafter Bayesian IRL). Their PolicyWalk MH algorithm (Algorithm 5) allows for domain knowledge to be incorporated in the prior, with the potential for further improvement in estimation accuracy. Their approach models the likelihood of state-action pairs as the occupancy under the expert's policy \(\Pr((s_{t},a_{t})|R)=\mu_{E}(s_{t},a_{t})\) with a Boltzmann distribution assumption (Section 2.3). Unlike its use in [53] (Section 3.1.1.6), here the normalisation in the likelihood has to be done over all \((s_{t},a_{t})\in\tau\), which may be intractable depending on the state space. Fortunately, because the algorithm only uses ratios of the densities, the normalising constant \(Z\) can be discarded, and the resultant likelihood is  
\[\Pr(\tau|R,\pi)\propto\exp\left(\alpha\sum_{(s_{t},a_{t})\in\tau}Q^{\pi}(s_{t},a_{t};R)\right); \tag{29}\]  
hence, the posterior is  
\[\Pr(R,\pi|\tau)\propto p=\exp\left(\alpha\sum_{(s_{t},a_{t})\in\tau}Q^{\pi}(s_{ t},a_{t};R)\right)\Pr(R), \tag{30}\]  
where \(p\) is used as the acceptance probability distribution in the MH procedure. ```
AlgorithmPolicyWalk(\(\tau\), \(P\))
1\(p\leftarrow\exp\left(\alpha\sum_{(s_{i},a_{i})\in\tau}Q^{\pi}(s_{i},a_{i},R) \right)\Pr(R)\)
2\(\mathcal{R}\leftarrow\mathbb{R}^{|S|}/\delta\)Partition with step size \(\delta\)
3\(R\leftarrow\texttt{RandomVector}(\mathcal{R})\)
4\(\pi\leftarrow\texttt{PolicyIteration}(\texttt{MDP}\backslash\texttt{R},\ R)\)
5 while\(k<K\)do
6\(W\leftarrow\{\text{neighbours of $R$ in $\mathcal{R}$}\}\)\(|W|=2|S|\)
7\(\tilde{R}\sim\text{Uniform}(W)\)
8\(\mathbf{Q}^{\pi,\tilde{R}}\leftarrow\mathcal{Q}^{\pi}(s,a,\tilde{R})\)\(\forall(s,a)\in\mathcal{S}\times\mathcal{A}\)Store Q-values in matrix
9 if\(\exists(s,a)\in\mathcal{S}\times\mathcal{A},\mathbf{Q}^{\pi,\tilde{R}}(s,\pi(s) )<\mathbf{Q}^{\pi,\tilde{R}}(s,a)\)then
10\(\tilde{\pi}\leftarrow\texttt{PolicyIteration}(\texttt{MDP}\backslash\texttt{R},\ \tilde{R},\ \pi)\)Update \(\pi\) wrt \(\tilde{R}\)
11 else
12\(\tilde{\pi}\leftarrow\pi\)
13 end if
14\((R,\pi)\leftarrow(\tilde{R},\tilde{\pi})\)with probability \(\min\{1,\frac{p(\tilde{R},\tilde{\pi})}{p(R,\pi)}\}\)
15 end while return\(R\)
```  
**Algorithm 5**Policy Walk Algorithm [59]  
For the prior \(\Pr(R)\), they invoke the principle of maximum entropy to assume the rewards are independent and identically distributed. Three different prior distribution candidates are proposed:  
* for prior-agnostic context, a uniform distribution over \([-R_{\max},R_{\max}]^{|S|}\) or an improper prior \(\Pr(R)=1\) over \(\mathbb{R}^{|S|}\);
* for real-world MDP with parsimonious reward structures, a Gaussian or Laplacian prior (over \(\mathbb{R}^{|S|}\)); and
* for planning-type problems, where most states can be expected to have low or negative rewards, with some having high rewards, a Beta distribution (over \(\mathbb{R}^{|S|}\)). An important distinction is that the PolicyWalk algorithm estimates the value of \(R\) at each of the states directly, and therefore it does not make use of features or a (linear) function approximator for \(R\) as in the previously discussed methods. Although they show substantial improvements over the method in [40] for \(|S|\leq 1000\), larger (or infinite) state spaces may not be feasible to learn over with this approach. The loss functions used in their evaluation experiments are the \(\ell 2\)-norm between the estimated and true reward functions \(R\), and the \(\ell 1\)-norm for the estimated policy \(\pi\) evaluated under the true \(R\). Bayesian IRL methods are limited in scalability, as they have to define probabilities and/or calculate value or quality function values for every point in the state-action space. Furthermore, as in other previous methods, large computational overheads are associated with the need to optimise the policy in the MDP. The authors posit that the max-margin method from [40] is a special case of Bayesian IRL where the obtained \(R\) is the MAP estimate with a Laplacian prior.