I have been wrestling with this for quite a long time but couldn't convince myself that the following is true:enter image description here

What I do understand: $\theta_a$ denotes the set of points that are within the ellipsoid. Also, $A_{t, a}$ is a matrix that "describes" the shape of the ellipsoid. $\hat{\theta}_{t,a}$ is the red point that is the center of the ellipsoid, and $c_t$ is the "radius" of the ellipsoid.

I cannot show to myself that $\displaystyle\max_{\theta_{a}} x_{t,a}^{T} \theta_{a}$ can be derived into the LHS form: $x_{t,a}^{T} \hat{\theta}_{t,a} + c_t \sqrt{x_{t,a}^{T} A_{t,a}^{-1} x_{t,a}}$

Can anyone show me how this is true?


For more context, you can view it here: http://www.yisongyue.com/courses/cs159/lectures/LinUCB.pdf


1 Answer 1


There must be something wrong if you look at the dimensions. Actually the constraint should be $$(\theta_a-\hat{\theta}_{t,a})^TA_{t,a}(\theta_a-\hat{\theta}_{t,a})\leq c_t^2.$$

The inner product takes its maximum on the boundary of the ellipsoid so we can make the constraint a equation. The gradient of Lagrange function has to be zero at the maximum: $$\left\{\begin{array}{rcl} x+2\lambda A(\theta-\hat{\theta}) &=&\vec{0} \\ (\theta-\hat{\theta})^TA(\theta-\hat{\theta})-c^2&=&0 \end{array}\right.$$

So $$x^T(\theta-\hat{\theta})=2\lambda(\theta-\hat{\theta})^TA(\theta-\hat{\theta})=2\lambda c^2,$$ $$x^TA^{-1}x=4\lambda^2(\theta-\hat{\theta})^TAA^{-1}A(\theta-\hat{\theta})=4\lambda^2c^2,$$ which implies $x^T\theta=x^T\hat{\theta}\pm c\sqrt{x^TA^{-1}x}$. Since it's the maximum we take the positive sign here, so we have the LHS you wanted.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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