maximizing inner product of vectors in an ellipsoid and a given vector
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}) &amp;=&amp;\vec{0} \\
(\theta-\hat{\theta})^TA(\theta-\hat{\theta})-c^2&amp;=&amp;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.