That syntax is actually rather questionable formally, since it treats the big-O as a function, which it is not. But with a bit of slop the rule to interpret these is rather simple. The big-O stands for some function with the asymptotic behaviour given by the big-O.
I'll start with the full syntax of the big-O notation:
$$ f(n) = O(g(n)) $$
means that
$$ \exists C~\exists n_0~\forall n > n_0: f(n) \leq Cg(n). $$
So when we write "complexity is $O(n)$", we are really saying complexity is $c(n)$ for which $c(n) = O(n)$.
Alternatively we can say $O(g(n))$ is a set of functions defined as
$$ O(g(n)) = { f(n) | \exists C~\exists n_0~\forall n>n_0: f(n) \leq Cg(n) }. $$
And write $f(n) \in O(g(n))$ instead. While this definition is more logical, it seems to be less used in textbooks.
Now if we say that complexity is $2^{O(n)}$, we can't expand it simply as $c(n) = 2^{O(n)}$, because we didn't define that. 743
So instead we replace the big-O with a function that conforms to the big-O. Like this:
$$ c(n) = 2^{f(n)},\ f(n) = O(n) $$
And you can expand any other expression containing big-O. The approach applies to any expression having big-O as subexpression, so $O(n)^n$ is just
$$ c(n) = f(n)^n,\ f(n) = O(n) $$
In the set notation it makes even more sense, because
$$ g(F) = { g \circ f | f \ in F } $$
where $g$ is a function and $f$ is a set of functions with one argument is the only logical definition of expression involving set of functions. So than:
$$ 2^{O(n)} = { 2^{f(n)} | f(n) \in O(n) } $$
and
$$ O(n)^n = { f(n)^n | f(n) \in O(n) }. $$
As for $O(\epsilon^{1/2^n})$, that's just standard big-O notation:
$$ f(n) = O(\epsilon^{1/2^n}) $$ $$ \exists C~\exists n_o~\forall n>n_0: f(n) < C\epsilon^{1/2^n} $$
(which tends to $1$ as $n$ tends to $\infty$). The $\epsilon$ would usually be some tunable parameter in the algorithm. 743