## 3 Inferring an Agent's Desires
### Reward Function Discrimination
#### 3.1.1.3 Multiplicative Weights Apprenticeship Learning  
[PERSON] and [PERSON] [43] expand on the apprenticeship learning algorithm in [42] with algorithmic tools from game theory. Further constraining the ranges of \(\phi(s)\in[-1,1]^{d}\) and \(\theta\in\Theta_{C}=\{\theta\in\mathbb{R}^{d}:||\theta||_{1}=1\text{ and }\theta\succeq 0\}\) allows for defining the margin \(V^{\pi}-V^{\pi_{E}}\geq\min_{i}\{v_{i}^{\pi}-v_{i}^{\pi_{E}}\}\) to be maximised. The goal is defined through the game value (note the difference in symbols \(v\), \(v\))  
\[v^{*}=\max_{\psi\in\
abla}\min_{\theta\in\Theta_{C}}\left(\theta^{\mathsf{T}}v _{\psi}-\theta^{\mathsf{T}}v_{E}\right), \tag{18}\]  
i.e., \(\psi^{*}\) is the mixed policy that maximises \(V^{\psi}-V^{\pi_{E}}\) for the worst-case possibility for \(\theta^{*}\), a sensible constraint because \(\theta^{*}\) is unknown. This allows for a zero-sum game formulation, though only abstractly, so the \"players\" are not the observer and actor, but the rewards and the policy (this is the foundational concept of adversarial IRL methods, reviewed in Section 3.1.7). \"Min player\" sets the reward by choosing \(\theta\), and \"max player\" chooses a mixed policy \(\psi\), adversarially. As such, the game can be defined via a \(d\times|\Pi|\) game matrix with \(G(i,k)=v^{k}(i)-v_{E}(i)\), where \(i\) indices over the feature dimensions \(d\) and \(k\) over the policies in \(\Pi\), the space of policies \(\pi\). From this, we have  
\[v^{*}=\max_{\psi\in\
abla}\min_{\theta\in\Theta_{C}}\theta^{\mathsf{T}}G\psi= \min_{\theta\in\Theta_{C}}\max_{\psi\in\
abla}\theta^{\mathsf{T}}G\psi\geq 0 \tag{19}\]  
in [PERSON]'s minimax form [44]. The 0 lower bound is explained as follows. The stricter constraint setting \(\theta\in\Theta_{C}\) is equivalent to assuming all the features \"got the sign right\" in relation to how they contribute to the reward (because the weights are all positive). This assumption results in \(\psi^{*}\) having higher value than \(\pi_{E}\) when \(v^{\psi^{*}}\succeq v^{\pi_{E}}\) regardless of the value of the actual weights \(\theta^{*}\).  
To solve this optimisation problem, they adapt the multiplicative weights algorithm from [45]. This algorithm has two main steps. (1) Given min player \"strategy\" \(\theta\), find \(\psi^{*}=\arg\max_{\psi\in\
abla}\theta^{\mathsf{T}}G\psi\) (i.e., find an optimal policy in the MDP with known \(R\), through any MDP solver); (2) Given max player \"strategy\" \(\psi\), compute \((\theta^{(i)})^{\mathsf{T}}G\psi\) for each of the \(d\) pure (i.e., one-hot) strategies \(\theta^{(i)}\) (i.e., compute the feature expectations \(v\in\mathbb{R}^{d}\) of the given policy \(\psi\), which can be done by solving \(d\) systems of linear equations, or approximated iteratively). These steps in Algorithm 3 are equivalent to the projection algorithm from [42]. The complexity of these steps scales with the size of MDP\(\backslash\)R, and not with \(G\). There is similarity in the higher bound approximation step in [46] (Algorithm 4, line 12).  
The mixed policy returned by the Multiplicative Weights AL algorithm consists of a uniform distribution over estimated policies \(\hat{\pi}\) that are \(\varepsilon_{\pi}\)-optimal, meaning \(|V(\hat{\pi})-V(\pi^{*})|\leq\varepsilon_{\pi}\). The game matrix \(G\) is slightly modified and makes use of \(\varepsilon_{v}\)-good feature expectations estimates, meaning \(||\hat{\sigma}-v^{\pi}||_{\infty}\leq\varepsilon_{v}\).