The fourth point in A1
Thanks very much for your reply.
The last term in Eq 21 ($\mathbb{E}[\nabla \text{KL}(\pi_i(s_i) \| \pi_{i}^{min}(s_i))]$), which is a gradient with respect to the parameters of $\pi_i$ of a KL between $\pi_i$ and $\pi_i^{min}$. As we said in **A3**, we sampled multiple policies in the policy hull of $\Pi_i^t$ and used the sampled min policy (say $\hat{\pi}_i^{min}$) to approximate the true $\pi_i^{min}$:
- We first obtain the fixed policy $\hat{\pi}_i^{min}$.
- Then, the last term in Eq 21 becomes $\mathbb{E}[\nabla \text{KL}(\pi_i(s_i) \| \hat{\pi}_{i}^{min}(s_i))]$, where $\hat{\pi}_i^{min}$ is a **constant**.
More precisely, if we undstand it correctly, the reviewer's question is whether the above two steps make sense in approximating $ \nabla \min_{\pi_i^k} \mathbb{E} [ \text{KL}(\pi_i(s_i) \| \pi_{i}^{k}(s_i))]$. The answer is yes:
- In Equation 15 in the paper, we have used a property that $\nabla_{\theta} \mathbb{E}[\text{KL}(\pi_i(s_i; \theta) \| \pi_i^{min}(s_i))] \in \partial_{\theta} \min_{\pi_i^k} \mathbb{E}[\text{KL}(\pi_i(s_i; \theta) \| \pi_{i}^{k}(s_i))] $, where $\pi_i^{min}(s_i) = \arg\min_{\pi_i^k} \mathbb{E}[\text{KL}(\pi_i(s_i; \theta) \| \pi_{i}^{k}(s_i))] $.
- To show the correctness of the equation above, we can prove a proposition as follows:
> *Proposition*: For any locally Lipschitz continue function $f(x,y)$, assume $\min_y f(x, y)$ is well-defined, then
$ \partial_x f(x,y) |\_{y \in \arg\min f(x, y)} \in \partial_x \min_{y} f(x, y)$ (1),
where $\partial f$ is the generalized gradient [1], which is the convex hull of the limits of the form $\lim \nabla f (x + h_i) $ where $h_i \rightarrow 0$.
- The proposition is an immediate result according to [1].
> *proof*: According to Theorem 2.1 (property (4)) in [1], (1) is immediate, as $\partial_x \max_{y} g(x, y)$ (or $\partial_x \min_{y} f(x, y)$) is the convex hull of $\\{\partial_x g(x,y) |{y \in \arg\max g(x, y)} \\}$.
- Note that the generalized gradient $\partial_x f(x, y)$ is the set of subgradients when $f(x, y)$ is convex on $x$ [1] (Proposition 1.2).
- This theory has been used widely in existing literature. For example:
1. GAN (Proposition 2) [2], which shows that the subgradient of the generator G can be obtained by computing the gradient of G at the optimal discriminator D.
2. ED (Theorem 1) [3], which proves that the gradient of $\pi_{\theta_i}$'s value against a best response, $\beta = b_{-i}(\pi_{\theta_i})$, is a generalized gradient of $\pi_{\theta_i}$'s worst-case value function, i.e.,
$\nabla_{\theta_i} v_{i}(\pi_{\theta_i}, \beta)|\_{\beta = b_{-i}(\pi_{\theta_i})} \in \partial_{\theta_i} \min_{\pi_{-i}} v_{i}(\pi_{\theta_i}, \pi_{-i})$
Hope the above clarifies your concern, and we will make it clearer in the revision. We would be happy to discuss if there is still anything unclear.
[1] Clarke, Frank H. "Generalized gradients and applications." Transactions of the American Mathematical Society 205 (1975): 247-262.
[2] Goodfellow, Ian, et al. "Generative adversarial nets." Advances in neural information processing systems 27 (2014).
[3] Lockhart, Edward, et al. "Computing approximate equilibria in sequential adversarial games by exploitability descent." arXiv preprint arXiv:1903.05614 (2019).