0
$\begingroup$

In Page 5 Sample Efficient Actor-Critic with Experience Replay, the authors define an optimization problem with a linearized KL divergence constraint (Eq.11)as follow $$ \min_z{1\over 2}\Vert \hat g_t^{acer}-z\Vert_2^2\\ s.t.k^Tz\le\delta\\ where\quad k=\nabla_{\phi_\theta}D_{KL}[f(\cdot|\phi_{\theta_a}(x_t))\Vert f(\cdot|\phi_{\theta}(x_t))] $$ where $f(\cdot|\phi_{\theta_a}(x_t))$ denotes the policy network, $f$ alone is the categorical distribution. $\phi_{\theta_a}$ is the average policy network, whose parameters are updated according to: $\theta_a\leftarrow\alpha\theta_a+(1-\alpha)\theta$. They solve this quadratic programming problem, getting the solution: $$ z^*=\hat g_t^{acer}-\max\left\{0, {k^T\hat g_t^{acer}-\delta\over \Vert k\Vert_2^2}\right\}k\tag 1 $$ I cannot see how they get this. where does the maximum term come from? To my best knowledge, the KKT conditions can be written as $$ \begin{align} z-\hat g_t^{acer}+\lambda k&=0\\ \lambda(k^Tz-\delta)&=0\\ \lambda&\ge0 \end{align} $$ from which I get $$ z^*=\begin{cases} k^{-1}\delta&\mathrm{if}\ \lambda>0\\ \hat g_t^{acer}&\mathrm{if}\ \lambda=0 \end{cases} $$ This seems not consistent with Equation1. Where do I make mistakes?

$\endgroup$
1
$\begingroup$

Formulating Lagrange function as $$ L(z, \lambda) = \frac{1}{2} || \hat g_{t}^{acer} - z ||^2 - \lambda \left( k^T z - \delta \right), \quad \lambda \leq 0. $$

The KKT conditions should be: \begin{aligned} z-\hat g_t^{acer}- \frac{1}{2} \lambda k&=0 \quad (1)\\ k^Tz-\delta&=0 \quad(2)\\ \lambda&\le 0 \quad(3) \end{aligned} Thus, from (1), $z = \hat g_t^{acer} + \frac{1}{2} \lambda k$, substituting $z$ in (2), obtaining: $k^{T} (\hat g_t^{acer} + \frac{1}{2} \lambda k) - \delta = 0$.

We can get $$ \lambda = \frac{2 (\delta - k^{T} \hat g_t^{acer})}{||k||^{2}} \quad (4) $$ combining (3) and (1), the solution should be:

\begin{aligned} z^{*} &= \hat g_{t}^{acer} + \min \left\{ 0, \frac{ \delta - k^{T} \hat g_t^{acer}}{||k||^{2}} \right\} k \\ &= \hat g_{t}^{acer} - \max \left\{ 0, \frac{ k^{T} \hat g_t^{acer} - \delta}{||k||^{2}} \right\} k \\ \end{aligned}

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.